# Aggregation of Merkle proofs from homomorphic hashes ## Failures Let $H_1 : F_r^2 \to E$ denote a Pedersen commitment map on the elliptic curve $E$ over $F_q$, given by $(u,v) \mapsto u A + v B$. Let $\psi : F_q \to F_r$ be easily computable, so that $H : F_q^2 \to F_q$ given by $(u,v) \mapsto \psi(H_1(u,v).x)$ is a Pedersen hash. Alternatively let $\psi' : F_q \times F_r^2 \to F_r$ be easily computable so that $H' : F_r^2 \to F_r$ given by $(u,v) \mapsto \psi(H_1(u,v).x,u,v)$ is some Pedersen-like hash. An example being $\psi'(x,u,v) = (u+v) \psi(x)$. <!-- *Lemma.* $H'$ has whatever collision resistance properties you desire. *Proof idea.* We break DDH otherwise. (Or use AGM here too?) --> We define the conditional swap function $M : F_q^2 \times \{0,1\} \to F_q$ by $$M(p,c,o) = \begin{cases} (p,c) & \mathrm{if\ } o=0 \\ (c,p) & \mathrm{if\ } o=1 \\ \end{cases}$$ Let $\bar{P} = [(p_0,c_0,o_0),\ldots,(p_n,c_n,o_n)]$ denote a Merkle copath from leaf $p_0$ to root $p_{n+1}$, meaning $p_{j+1} := H(M(P_j))$ for $j \le n$ (or similarly with $H'$). Can we prove the leaf $p_0$ by merging the $H_1$ invocations using linearity? Aka does the relation $\mathcal{R}$ prove membership of $p_0$ under $p_{n+1}$? \mathcal{R}' = \Bigg\{ (p_0,p_{n+1})\, ; \bar{P},\bar{Z} \, \Bigg| \begin{aligned} \sum_{0 < j \le n+1} Z_j &= H_1\Big(\sum_{j \le n} M(P_j)\Big) \,\textrm{ in E} \\ p_{j+1} &= (p_j + c_j) \psi( Z_j.x ) \bmod q \quad\forall j \le n \\ \end{aligned} \Bigg\} $\mathcal{R}$ similarly but $p_{j+1} = \psi( Z_j.x ) \bmod q$. *Definition.* The strong algebraic group model (sAGM) says adversaries must write elliptic curve points as linear combinations of supplied points. In our case, this means $u A + v B$. We consider a collision adversary who choses $\bar{P}$ and $\bar{Z}$ to satisfy $\mathcal{R}$. In sAGM, our adversary chooses their $\bar{Z}$ by choosing $u_j,v_j$ to define $Z_j := u_j A + v_j B$, subject to $$\sum_{j \le n} (u_j,v_j) = \sum_{j \le n} M(P_j) \tag{\dagger}$$ We assume $(u_j,v_j) \mapsto Z_j.x$ is a random oracle, although this should be replaced by another randomness assumption. *Attack on $\mathcal{R}$.* Adversary select their $p_0$. Adversary fixes their $o_j$ to be half 0s and half 1s. Also, the adversary selects their $u_j,v_j$, which then define $p_{j+1} = \psi(Z_j.x)$, with $u_n,v_n,p_{n+1}$ honest. Now the adversary chooses $c_j$ that sum up correctly in $(\dagger)$. *Attack on $\mathcal{R}'$.* Aside from $(\dagger)$, we demand $p_{j+1} = (p_j + c_j) \psi( Z_j.x ) \bmod q$ holds for $j \le n$. If we fix $p_{j+1}$ and $Z_j$ then we have a line in $(p_j,c_j)$ with slope one. Also $Z_j$ determines a plane in $(p_{j+1},p_j,c_j) \in F_q^3$ but with $(p_j,c_j)$ lines having slope one. We set $m_n = \psi( Z_n.x )^{-1}$ so $c_j = m_n \, p_{j+1} - p_j$. Now $\dagger$ becomes $$\sum_{j \le n} (u_j,v_j) = \sum_{j \le n} M( p_j,\, m_j \, p_{j+1} - p_j,\, o_j )$$ Any adversary who fixes their $\bar{Z}$ first, must choose these $\bar{p} = (p_0,\ldots,p_{n+1})$, so that both equalities hold. If our $m_j$ are random oracles then these two equations lie in fairly general position, no? <s>I'd expect they run a generalized birthday attack against only $\lambda$ bits, because they can choose most $p_j$ freely.</s> ## Success? Consider $H_1$ given by $(u,v) \mapsto u A + v B + u v C$. We replace $\dagger$ by this equation $$\begin{eqnarray} \sum_{j \le n} (u_j,v_j) &=& \sum_{j \le n} M(P_j) \\ \sum_{j \le n} w_j &=& \sum_{j \le n} p_j c_j \\ \end{eqnarray} \tag{\dagger}$$ We likely break this $\mathcal{R}$ for this flavor, again without the generalized birthday bound. We no longer have limitless choices for the $\bar{c}$ however. We set $m_n = \psi( Z_n.x )^{-1}$ so $c_j = m_n \, p_{j+1} - p_j$. Now $\dagger$ becomes $$\begin{eqnarray} \sum_{j \le n} (u_j,v_j) &=& \sum_{j \le n} M( p_j, m_j \, p_{j+1} - p_j, o_j) \\ \sum_{j \le n} w_j &=& \sum_{j \le n} m_j \, p_{j+1} p_j - p_j^2 \\ \end{eqnarray} \tag{\dagger}$$ Any adversary who fixes their $\bar{Z}$ first, must choose these $\bar{p} = (p_0,\ldots,p_{n+1})$, so that all three equalities hold. <s>If our $m_j$ are random oracles then I'd expect they run a generalized birthday attack against $2 \lambda$ bits or worse.</s> We likely break this if the $o_j$ swap side once in the middle.