# 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.