Snarkpack

\gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\e{\operatorname{e}} \gdef\g{\mathrm{g}} \gdef\k#1{\mathbf{#1}}

Recall a Groth16 verification with verification key \p{\k D,\k E,\k F,\k G,\k L_i} and proof \p{w_i, A, B, C}. It's made to sum to zero and signs are absorbed into the constants.

0 = \e(A, B) + \e(\k E, \k F) + \e\p{ \sum_{i ∊ [0, p)} w_i ⋅ \k L_i, \k G} + \e\p{C, \k D}

Take n proofs \p{w_{ij}, A_j, B_j, C_j} and linearly combine them using r_j:

\begin{aligned} 0 & = \sum_j r_j ⋅ \p{\e(A_j, B_j) + \e(\k E, \k F) + \e\p{ \sum_{i ∊ [0, p)} w_{ij} ⋅ \k L_i, \k G} + \e\p{C_j, \k D} } \\ & = \sum_j \e\p{r_j ⋅ A_j, B_j} + \e\p{\sum_j r_j ⋅ \k E, \k F} + \e\p{\sum_j \sum_{i ∊ [0, p)} r_j ⋅ w_{ij} ⋅ \k L_i, \k G} + \e\p{\sum_{i ∊ [0, p)} r_j ⋅ C, \k D} \\ \end{aligned}

Question. Can we proof soundness if the prover only provided \sum_{i ∊ [0, p)} r_j ⋅ A_j and/or the equivalent for B or C? Extreme case

0 = \e(A, B) + \e(\k E, \k F) + \e\p{\sum_j \sum_{i ∊ [0, p)} r_j ⋅ w_i ⋅ \k L_i, \k G} + \e\p{C, \k D}

where r_j is derived by pseudorandom function from w_{ij}.


https://eprint.iacr.org/2021/529

Remco Bloemen
Math & Engineering
https://2π.com