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

https://forum.polkadot.network/t/generalized-storage-proofs/1315

2/26/2024e(A_1,B_1) \cdot e(A_2,B_2) = e([\alpha_1]_1, [\beta_1]_2) \cdot e([\alpha_2]_1, [\beta_2]_2) \cdot e( Z_{\mathsf{sec}} + Z_{\mathsf{pub}}, [\gamma]) \cdot e(C_1+C_2, [\delta]_2) \mathperiod

11/21/2023Ideally, almost all rewards in Kusama/Polkadot would come from work done securing parachains like backing and approval checkers, including work supporting XCMP, and availability. We do need participation in relay chain block production and finality, so some rewards must continue, but their levels shall wind up greatly reduced.

10/7/2023https://github.com/paritytech/substrate/pull/13031 https://github.com/paritytech/ark-substrate https://github.com/w3f/ark-scale/ Coordinates Affine coordinates and serialized forms differe in Arkworks and ZCash/BLST, but an easy conversion is given by https://github.com/MystenLabs/fastcrypto/tree/main/fastcrypto-zkp/src/bls12381

6/6/2023
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up