# Merkle tree alternating hash and polynomial I want to get feedback on the security of a modified merkle tree data structure. Using the image above as a reference assume I have a random oracle function $$H$$. Assume $$H$$ outputs a value in $$\mathbb{F}_p$$, and all math is happening in this field too.

The standard approach to calculate $$D$$ is

$$B = H(A, C)$$

$$F = H(E, G)$$

$$D = H(B, F)$$

The approach I'm considering alternates between hash function and polynomial. To calculate $$D$$ I would use $$H$$ in the first level:

$$B = H(A, C)$$

$$F = H(E, G)$$

Then use multiplication in the second level:

$$D = B * F$$

Then to calculate the parent of $$D$$ I would do $$H(D, D_{sibling})$$, then above that I would use multiplication again.

I'm wondering, is this guarded by Schwartz–Zippel? $$B$$ and $$F$$ should both be randomly distributed in $$\mathbb{F}_p$$, is $$B*F$$ a polynomial of degree 2? Does the case of $$B = F$$ matter? e.g. $$A = E \land C = G$$

When making a merkle proof I'd include the pre-image of any nodes that are combined with multiplication. So in the below tree I would prove membership of $$J$$ in $$A$$ by supplying: $$J$$, $$K$$, $$I$$, $$Z$$, $$C$$.

          A
/      \
B        C
/  \     /  \
D    E   F    G
/ \  / \ / \  / \
Z  I J  K L  M N  O


I would then compute

$$B = H(Z, I) * H(J, K)$$

$$A = H(B, C)$$

• What are you trying to achieve? Apr 8 at 5:41
• This approach reduces the cost of insertion/update by 30-50%. Apr 8 at 14:31

Here's the issue: for multiplication, you can compute preimages. You don't say what ring you compute the multiplication over, but for anything reasonable, given a target $$C$$ and several possible values $$A_1, A_2, ...$$, you can usually find a $$B$$ for which $$A_i \times B = C$$ for some $$i$$ (and if it's a finite field, unless $$A_1 = 0$$, only one value is needed).
Here's why that's an issue: suppose you see a Merkle tree proof that $$A$$ is a part of the Merkle tree; that proof consists of the values of $$B$$ and $$F$$. We want to prove that $$A'$$ is a part of the Merkle tree; we generate several values $$B_1, B_2,...$$, compute $$H(A, B_i)$$, and for that set of values, find an $$F'$$ such that $$H(A, B_i) \times F' = D$$; and we're done.
• I'm imagining only making proofs in ZK and always proving the pre-image of both $B$ and $F$ before multiplying. Would that solve the problem? Apr 7 at 21:35