"Linear" hashing function Say we have two chunks of data $X$ and $Y$, which may be of different sizes, is there a non-trivial function $hash$, and operation $*$, such that:

$$hash(X+Y) = hash(X) * hash(Y)$$

...where $+$ is concatenation, and $*$ is associative (but not necessarily commutative)?

Clearly $hash$ being the identity function, with $*:=+$, satisfies this. However, what if we put usual constraints on $hash$ -- say, its output is always $n$-bits, where $n$ is small -- and $*$ has to be reasonably economical?

My intuition is saying that no such $(hash,*)$ exists, because:


In the general case, there would be a loss of entropy in hashing and I don't believe this can be deterministic.
Merkle trees are a thing, which implies there's no better option.


(n.b., I realise "linear", in the linear algebra sense, isn't the correct word to use here, but for want of a better term!)
Sure.  These are known as homomorphic hash functions.  There are many schemes: see e.g., https://crypto.stackexchange.com/q/6497/351 for one possible entry point into the literature.

One example construction is to let $\mathbb{G}$ be a group with group operation $*$ and let $h:\{0,1\} \to \mathbb{G}$ be an arbitrary function, then extend $h$ to a function $h:\{0,1\}^* \to \mathbb{G}$ by associativity, i.e.,

$$h(x_1 x_2 \dots x_n) = h(x_1) * \cdots * h(x_n).$$

Then you can choose any group $\mathbb{G}$ of your choice.  If you want $*$ to be non-commutative, choose a non-abelian group $\mathbb{G}$.  One plausible choice is $\mathbb{G} = SL_2(\mathbb{F})$ over some finite field $\mathbb{F}$; see https://crypto.stackexchange.com/q/17730/351.



Your reasons why it can't exist are not valid.  I don't know what "there would be a loss of entropy" means; any hash function always causes a loss  of entropy (if the domain is larger than the range), thanks to the pigeonhole principle, but that doesn't mean hash functions don't exist or can't be deterministic.  The existence of Merkle trees doesn't preclude the existence of other solutions.