SnarkPack: Practical SNARK Aggregation

Nicolas Gailly¹, Mary Maller², and Anca Nitulescu¹

¹ Protocol Labs.

² Ethereum Fondation.

fnikkolasg, ancag@protocol.ai, mary.maller@ethereum.org

Abstract.

Zero-knowledge SNARKs (zk-SNARKs) are non-interactive proof systems with short and eciently veriable proofs that do not reveal anything more than the correctness of the statement. zk-SNARKs are widely used in decentralised systems to address privacy and scalability concerns. A major drawback of such proof systems in practice is the requirement to run a trusted setup for the public parameters. Moreover, these parameters set an upper bound to the size of the computations or statements to be proven, which results in new scalability problems. We design and implement SnarkPack, a new argument that further reduces the size of SNARK proofs by means of aggregation. Our goal is to provide an o-the-shelf solution that is practical in the following sense: (1) it is compatible with existing deployed SNARK systems, (2) it does not require any extra trusted setup. SnarkPack is designed to work with Groth16 scheme and has logarithmic size proofs and a verier that runs in logarithmic time in the number of proofs to be aggregated. Most importantly, SnarkPack reuses the public parameters from Groth16 system. SnarkPack can aggregate 8192 proofs in 8.7s and verify them in 163ms, yielding a verication mechanism that is exponentially faster than other solutions. SnarkPack can be used in blockchain applications that rely on many SNARK proofs such as Proof-of-Space or roll-up solutions.

1 Introduction

Arguments of Knowledge. Decentralised systems make extensive use of protocols that enable a prover to post a statement together with a short proof, such that any verier can publicly check that the statement (e.g., correctness of a computation, claims of storage etc.) is true while expending fewer resources, e.g. less time than would be required to re-execute the computation.

SNARKs are such proofs that allow one party to demonstrate knowledge of a satisfying witness to some NP statement and have verication time and proof size independent of the size of this witness. If these proofs also conceal anything else about the witness we refer to them as zk-SNARKs. In the last decade, there has + been a series of works on constructing SNARKs [BCI 13, GGPR13, PHGR13, BCTV14, Gro16] with constant-size proofs that rely on trusted setups.

SNARKs are becoming very popular in real-world applications such as delegated computation or blockchain systems: as examples of early practical use + case, Zerocash [BCG 14] showed how to use zk-SNARKs in distributed ledgers to achieve payment systems with strong privacy guarantees. The Zerocash protocol, with some modications, is now commercially deployed in several cryptocurrencies, e.g. Zcash.

More recent zk-SNARK use cases are Aztec and zkSync, two projects boosting the scalability and privacy of Ethereum smart contracts³. Another example of SNARK application is the Filecoin System⁴ that implements a decentralized storage solution for the internet.

The rapid and massive adoption of SNARK schemes has created new scalability challenges for blockchain systems: the generation of trusted setups requires complicated ceremonies, proving large statements has signicant overhead, and verifying multiple proofs is expensive even with batching.

Trusted Setup Ceremony. All the constant-size zk-SNARK schemes have a common major disadvantage in practice: they rely on some public parameters, the structured reference string (SRS), that are generated by a trusted setup. In theory, this setup is run by a trusted third party, while in practice, such a string can be generated by a so called "ceremony", a multi-party computation between + participants who are believed not to collude as shown in [ABL 19, BGM17, ⁺ BCG 15]. Generating such a trusted setup is a cumbersome task. These ceremonies are expensive in terms of resources, they must follow specic rules, and they are generally hard to organise: hundreds of participants with powerful machines need to join eorts to perform a multi-party computation over multiple months.

Groth16. The construction by Groth [Gro16] is the state-of-the-art for pairingbased zk-SNARKs. Groth16 requires the computation to be expressed as an arithmetic circuit and relies on some trusted setup to prove the circuit satisability. Due to its short proof size (3 group elements) and verier’s eciency, Groth16 has become a de facto standard in blockchain projects. This results in a great number of available implementations, code auditing, and multiple trusted setup ceremonies run by independent institutions.

Motivation. Importantly, the trusted setup in SNARK schemes sets an upper bound on the size of computations that can be proven (number of constraints in the circuit description). Because modern applications have an increased demand for the size of circuits, Groth16 is starting to face scalability problems. A simple solution would be to split the computation in dierent pieces and prove them independently in smaller circuits, but this increases the number of proofs to be added to a single statement and the verication time.

We address this problem by demonstrating a method to reduce the overhead in communication and verication time for multiple proofs without the need of further larger trusted setup ceremonies.

3 Aztec, https://zk.money; zksync, https://zksync.io; https://ethereum.org

4 Filecoin, https://filecoin.io https://filecoin.io

4 Filecoin, https://filecoin.io

Filecoin System. One example is Filecoin [Lab18] proof-of-space blockchain. To onboard storage in the network, Filecoin miners post a Groth16 proof that they correctly computed a Proof-of-Space [Fis19]. Each proof guarantees that the miner correctly \reserves" 32GB of storage to the network and consists of 10 dierent SNARKs. The chain currently processes a large number of proofs each day: approximately 500,000 Groth16 proofs, representing 15 PiB of storage.

Contribution. We explore reducing proof size and verier time for SNARKs even further by examining techniques to aggregate proofs without the requirement for additional trusted setups.

We design SnarkPack, an argument that allows to aggregate n Groth16 zk- SNARKs with a O(logn) proof size and verier time. Our scheme is based on a trusted setup that can be constructed from two dierent existing ceremonies (e.g. the "powers of tau" for Zcash [Zca18] and Filecoin [Fil20]).

Being able to rely on the security of well-known trusted setups for which the ceremonies have been largely publicly advertised is a great practical advantage and makes SnarkPack immediately useful in real-world applications.

Our techniques are generic and can also apply to other pairing-based SNARKs. The roadmap is similar, since all such SNARK constructions require the generation of "powers of tau" for the setup ceremony and then have a few pairing check equations in the verication algorithm. However, we choose to focus on Groth16 proofs and tailor optimisations for this case, since it is the most popular scheme among practitioners. Therefore, SnarkPack is the rst practical system that can be used in blockchain applications to reduce the on-chain work by employing veriable outsourcing to process a large number of proofs o-chain. This applies broadly to any system that needs to delegate batches of state updates to an untrusted server.

Related Work. Prior works have built similar schemes for recursion or aggregation of proofs, but they all have critical shortcomings when it comes to implementing them in real-world systems.

• Bunz et al. [BMM 19] presented a scheme for aggregating Groth16 proofs that requires a specic trusted setup to construct the structured reference string (SRS) necessary to verify such aggregated proofs. Our result is conceptually similar to that of Bunz et al. while beneting from many optimizations. We focus specically on aggregating proofs generated using the same Groth16 SRS
• which is the common use case, as opposed to the generic result in [BMM 19] that allows aggregation of proofs from dierent SRSes. Our result can be extended to support this latter case as well.

While our techniques built on top of inner pairing arguments with logarithmic verier previously introduced by [DRZ20], we build new such schemes that avoid the need of a dierent trusted setup ceremony (other than the existing SNARK + setup). Our approach for aggregation is preferable to [BMM 19] in practical use cases.

Other approaches to aggregation rely on recursive composition. In more de- + tail, [BCG 20] propose a new SNARK for the circuit that contains n copies of the Groth16 verier’s circuit. However, constructing arithmetic circuits for pairings is expensive (e.g., computing a pairing on the BLS12-377 curve requires + 15000 constraints as shown in [BCG 20]). The advantage of using such expensive schemes for aggregation is their transparent setup.

$$ \approx15000 $$

However, the costs are signicant compared with our scheme: they compute FFTs, which require time O(nlogn), the verier performs O(n) cryptographic operations as opposed to O(n) eld operations in our scheme and they require special cycles of curves.

$$ O(n\log n) $$

$$ O(n) $$

$$ O(n) $$

SnarkPack has the best of both worlds: it benets from the power of structured public parameters to avoid expensive computations, while it does not require additional trust assumptions, as it relies on already available trusted setup transcripts for the underlying Groth16 scheme.

Technical Overview. To explain how SnarkPack works, we need to consider 3 multiplicative cyclic groups G₁*;G₂;* G_Tof order p equipped with the bilinear a b map, also called "pairing" e : G₁ G₂*!* G_Tsuch that 8a;b 2 Z_p: e(g;h) = ^ab e(g;h).

$$ \mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T} $$

$$ e:\mathbb{G}{1}\times\mathbb{G}{2}\to\mathbb{G}_{T} $$

$$ \forall a,b\in\mathbb{Z}_{p}:e(g^{a},h^{b})= $$

$$ e(g,h)^{a b} $$

Groth16 proofs = (A;B;C) for statements u = a consist of 3 group elements A;C 2 G₁ and B 2 G₂. The high-level idea of Groth16 aggregation is quite simple: Since Groth16 verication consists in checking a pairing equation between the proof elements = (A;B;C), instead of checking that n dierent pairing equations are simultaneously satised, it is sucient to prove that only one inner pairing product of a random linear combination of these initial equations dened by a verier’s random challenge r 2 Z_pholds. In a bit more detail, Groth16 verication asks to check an equation of the type e(A_i;B_i) = Y_ie(C_i;D) for Y_i2 G_T;D 2 G₂ where Y_iis a value computed from each statement u_i= a_i, D 2 G₂ is a xed verication key and_i= (A_i;B_i;C_i)_in=01are proof triples.

$$ \pi=(A,B,C) $$

$$ u=\mathbf{a} $$

$$ A,C,\in,\mathbb{G}_{1} $$

$$ B\in\mathbb{G}_{2} $$

$$ \pi=(A,B,C) $$

$$ r\in\mathbb{Z}_{p} $$

$$ e(A_{i},B_{i})=Y_{i}{\cdot}e(C_{i},D), $$

$$ Y_{i}\in\mathbb{G}{T},D\in\mathbb{G}{2} $$

$$ Y_{i} $$

$$ u_{i}=\mathbf{a}_{i} $$

$$ D\in\mathbb{G}_{2} $$

$$ \pi_ {i} = \left(A _ {i}, B _ {i}, C _ {i}\right) _ {i = 0} ^ {n - 1} $$

The aggregation will instead check a single randomized equation:

$$ \prod_{i=0}^{n-1}e(A_{i},B_{i})^{r^{i}}=\prod_{i=0}^{n-1}Y_{i}^{r^{i}}\cdot e\big(\prod_{i=0}^{n-1}C_{i}^{r^{i}},D\big). $$

Q_n ¹_i 0 We denote by Y := Y_irso this can be rewritten as: prod i=0

$$ Y_{p r o d}^{\prime}:=\prod_{i=0}^{n-1}Y_{i}^{r^{i}} $$

$$ Z _ {A B} = Y _ {p r o d} ^ {\prime} \cdot e \left(Z _ {C}, D\right), \quad \text {w h e r e} Z _ {A B} := \prod_ {i = 0} ^ {n - 1} e \left(A _ {i}, B _ {i}\right) ^ {r ^ {i}} \text {a n d} Z _ {C} := \prod_ {i = 0} ^ {n - 1} C _ {i} ^ {r ^ {i}}. $$

What is left after checking that this unied equation holds is to verify that the elements Z_AB;Z_Care consistent with the initial proof triples in the sense that they compute the required inner product. This is done by applying an argument that proves two dierent inner pairing product relations:

$$ Z_{A B},Z_{C} $$

{ TIPP: the target inner pairing product takes some initial committed vectors Qn 1 A 2 G₁*;* B 2 G₂ and shows that Z_AB=_i=0e(A_i;B_i);

$$ \mathbf{A}\in\mathbb{G}{1},\mathbf{B}\in\mathbb{G}{2} $$

$$ Z_{A B}=\prod_{i=0}^{n-1}e(A_{i},B_{i}) $$

{ MIPP: the multi-exponentiation inner product takes a committed vector Qn 1i C 2 G₁ and a vector r 2 Z_pand shows that Z_C=_i=0C_ir.

$$ \mathbb{C}\in\mathbb{G}_{1} $$

$$ \mathbf{r}\in\mathbb{Z}_{p} $$

$$ Z_{C}=\prod_{i=0}^{n-1}C_{i}^{r^{i}} $$

New Commitment Schemes. The key ingredient for SnarkPack is the ecient realisation of the two specialised inner pairing product arguments following the ideas initially proposed by [DRZ20] and generalised to other inner products by ⁺ [BMM 19]. These require a special commitment scheme that allows a party to commit to vectors of group elements in both source groups G₁ and G₂ with further homomorphic and collapsing properties.

$$ [ \mathrm {B M M} ^ {+} 1 9 ] $$

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{2} $$

We therefore introduce two new Pair Group Commitment schemes described in Section 3 that enable to commit to vectors A*;* C 2 G₁*;* B 2 G₂. Our commitments are doubly-homomorphic with respect to the message space and key space and they have a collapsing property. Both schemes have constant-size commitments and are proved to be binding based on assumptions that hold in the generic group model. Our second scheme has the advantage that it allows a party to commit to two vectors from two dierent groups with no size overhead. We think these schemes can be of independent interest in protocols that need to commit to source-group elements.

$$ \mathbf{A},\mathbf{C}\in\mathbb{G}{1},\mathbf{B}\in\mathbb{G}{2} $$

Reusing Groth16 Trusted Setup. The advantage of our commitment schemes is that they can reuse existing public setups for Groth16 to generate their structured commitment keys.

The public parameters required for the generation of the commitment keys can be extracted from two compatible copies of Groth16 SRS.

For a given bilinear group (p; G₁*;G₂;* G_T), Groth16 SRS consist (among other elements) of consecutive powers of some random evaluation point in both i i d d groups G₁ and G₂ : fg gⁱ2 G₁*; fh g*ⁱ2 G₂*:* We will call these "powers of tau".

$$ (p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T}) $$

$$ \tau $$

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}{2}:{g^{\tau^{i}}}{i}\in\mathbb{G}{1}^{d},{h^{\tau^{i}}}{i}\in\mathbb{G}_{2}^{d} $$

$$ \mathrm{{t\ t a u}}^{\prime} $$

The generation of SnarkPack public parameters (the commitment keys) comes naturally from two ceremonies for Groth16 setup (also known as "powers of tau") for the same generators g and h and dierent powers a =¹and b =₂: n n m m g;h;g₁;:::;g₁;h₁;:::;h₁, o_ne up to n and the other g₂:::;g₂;h₂;:::;h₂ up to m n.

$$ \mathrm{\ t a u^{\flat})} $$

$$ g $$

$$ a=\tau_{1} $$

$$ b=\tau_{2} $$

$$ g,h,g^{\tau_{1}},\ldots,g^{\tau_{1}^{n}},h^{\tau_{1}},\ldots,h^{\tau_{1}^{n}} $$

$$ g^{\tau_{2}}\ldots,g^{\tau_{2}^{m}},h^{\tau_{2}},\ldots,h^{\tau_{2}^{m}} $$

$$ m\geq n $$

Our assumptions rely on the fact that cross powers (e.g. g^{1 2}) are not known to the prover. Since the two SRSes we use are the result of two independent ceremonies, it is unlikely that such terms can be learned since₁and₂were destroyed after the SRS generation.

$$ (\operatorname{e.g.}g^{\tau_{1}\tau_{2}}) $$

$$ \tau_{1} $$

$$ \tau_{2} $$

In practice, we fortunately have at least two ceremonies that satisfy the requirements for same group generators and dierent powers: Such values can be obtained from the powers of tau transcript of Zcash [Zca18] and Filecoin 19 127 [Lab18]. The SRS created goes up to n = 2 for₁and m = 2 for₂.

$$ n=2^{19} $$

$$ \tau_{1} $$

$$ m=2^{127} $$

$$ \tau_{2} $$

Implementation. In Section 6 we provide benchmarks and optimisation details for our implementation in Rust, and evaluate its eciency against batching. SnarkPack is exponentially more ecient than aggregation via batching: it takes 163ms to verify an aggregated proof for 8192 proofs (including unserialization) versus 621ms when doing batch verication. The former is of 40kB in size. The aggregator can aggregate 8192 proofs in 8.7s.

2 Preliminaries

Bilinear Groups. A bilinear group is given by a description gk = (p; G₁*;G₂;* G_T) such that

$$ \mathsf{g k}=(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T}) $$

{ p is prime, so Z_p= F is a eld.

$$ \mathbb{Z}_{v}=\mathbb{F} $$

{ G₁ = hgi; G₂ = hhi are cyclic groups of prime order p.

$$ \mathbb{G}{1}=\langle g\rangle,\mathbb{G}{2}=\langle h\rangle $$

{ e : G₁ G₂*!* G_Tis a bilinear asymmetric map (pairing), which means that a b ab 8a;b 2 Z_p: e(g;h) = e(g;h).

$$ -\ e:\mathbb{G}{1}\times\mathbb{G}{2}\rightarrow\mathbb{G}_{T} $$

$$ \forall a,b\in\mathbb{Z}_{p}:e\big(g^{a},h^{b}\big)=e\big(g,h\big)^{a b} $$

n n n Vectors. For n-dimensional vectors a 2 Z_p; A 2 G₁; B 2 G₂, we deⁿote the i-th entry by a_i2 Z_p;A_i2 G₁*;B*_i2 G₂ respectively. Let AkA⁰ = (A₀;:::;A_{n 1}; 0n n A⁰₀;:::;A₁) be the concatenation of vectors A*;A⁰ 2 G₁. We write A_[:‘]= ‘ n ‘ (A₀;:::;A^{‘ 1}) 2 G¹and A^[‘:]= (A_‘;:::;A*_{n 1}) 2 G₁ to denote slices of n vectors A 2 G1for 0 ‘ < n 1.

$$ \mathfrak{l}\in\mathbb{Z}{v}^{n},\mathbf{A}\in\mathbb{G}{1}^{n},\mathbf{B}\in\mathbb{G}_{2}^{n} $$

$$ a_{i}\in\mathbb{Z}{p},A{i}\in\mathbb{G}{1},B{i}\in\mathbb{G}_{2} $$

$$ \mathbf{A}|\mathbf{A}^{\prime}=(left_00,,\ldots,A_{n-1}. $$

$$ A_{0}^{\prime},\ldots,A_{n-1}^{\prime}) $$

$$ \mathbf{A},\mathbf{A}^{\prime},\in,\mathbb{G}_{1}^{n} $$

$$ \ \mathbf{A}_{[:\ell]},= $$

$$ \left(A _ {0}, \dots , A _ {\ell - 1}\right) \in \mathbb {G} _ {1} ^ {\ell} $$

$$ \ {bf A A}{[\ell:]},=,(A{\ell},\ldots,A_{n-1}),\in,\mathbb{G}_{1}^{n-\ell} $$

$$ \mathbf{A}\in\mathbb{G}_{1}^{n} $$

$$ 0\leq\ell<n\overset{\cdot}cdot{} $$

We write group operations as multiplications. We dene:

x x ^x n n {A = (A⁰;:::;Aⁿ ₁) 2 G¹for x 2 Z^pa_nd a vector A 2 G₁.

$$

• \mathbf {A} ^ {x} = \left(A _ {0} ^ {x}, \dots , A _ {n - 1} ^ {x}\right) \in \mathbb {G} _ {1} ^ {n} $$

$$ x\in\mathbb{Z}_{p} $$

$$ \mathbf{A}\in\mathbb{G}_{1}^{n} $$

x x₀ xn 1 n n n {A = (A₀;:::;A^{n 1}) 2 G₁ for vectors x 2 Zp*;* A 2 G₁. Q

$$

• \mathbf {A} ^ {\mathbf {x}} = \left(A _ {0} ^ {x _ {0}}, \dots , A _ {n - 1} ^ {x _ {n - 1}}\right) \in \mathbb {G} _ {1} ^ {n} $$

$$ \mathbf{x}\in\mathbb{Z}{p}^{n},\mathbf{A}\in\mathbb{G}{1}^{n} $$

n 1 xi n n {A ^x =ⁱ=0Aifor vectors x 2 Zp*;* A 2 G₁. Q

$$ -\ mathbf A ast\mathbf=prod limits{}}{i=0}^{n-1}A{i}^{x_{i} $$

$$ \mathbf{x}\in\mathbb{Z}{p}^{n},\mathbf{A}\in\mathbb{G}{1}^{n} $$

n 1 n n {A B :=ⁱ⁼⁰e(Aⁱ;Bⁱ) for group vectors A 2 G₁; B 2 G₂. 0ⁿ n {A A⁰ := (A₀A⁰;:::;A A) for vectors *A;*A⁰ 2 G.

$$

• \mathbf {A} * \mathbf {B} := \prod_ {i = 0} ^ {n - 1} e \left(A _ {i}, B _ {i}\right) $$

$$ \mathbf{A}\in\mathbb{G}{1}^{n},\mathbf{B}\in\mathbb{G}{2}^{n}. $$

$$

• \mathbf {A} \circ \mathbf {A} ^ {\prime} := \left(A _ {0} A _ {0} ^ {\prime}, \dots , A _ {n - 1} A _ {n - 1} ^ {\prime}\right) \text {f o r v e c t o r s} \mathbf {A}, \mathbf {A} ^ {\prime} \in \mathbb {G} _ {1} ^ {n}. $$

Relations. We use the notation R to denote an eciently decidable binary relation. For pairs (u;w) 2R we call u the statement and w the witness. We write R = f(u; w) : p(u;w)g to describe an NP relation.

$$ (u,w)\in\mathcal{R} $$

$$ \mathcal{R}={\big(u;w\big):p\big(u,w\big)} $$

Common and Structured Reference String. The common reference string (CRS) model, introduced by Damgard [Dam00], captures the assumption that a trusted setup exists. Schemes proven secure in the CRS model are secure given that the setup was performed correctly. We will use the terminology \Structured Reference String" (SRS) since all our crs strings are structured.

Background on Groth16. We recall here some necessary elements from [Gro16] construction. The denition of zk-SNARKs is given in Appendix A.1. A detailed description of the Groth16 protocol can be found in Appendix C. The main highlights follow:

Setup. For a given bilinear group gk = (p; G₁*;G₂;* G_T), the SRS contains, among other elements, consecutive powers of some random evaluation point s in both idid s d s d groups G₁*;G₂ : fg gⁱ⁼⁰¹2 G₁;* an^d fh gⁱ⁼⁰¹2 G₂*:* tj Prove. A Groth16 proof for a statement u := a = fa^jg⁼⁰(with a₀ = 1) and m a witness w := fa_jg_j=t+1consists in 3 group elements = (A;B;C), where A;C 2 G₁ and B 2 G₂.

$$ \mathfrak{g k}=(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T}) $$

$$ \mathbb{G}{1},\mathbb{G}{2}:{g^{s^{\imath}}}{i=0}^{d-1},\in\mathbb{G}{1}^{d} $$

$$ {h^{s^{i\imath}}}{i=0}^{d-1};\in\mathbb{G}{2}^{d} $$

$$ \ :=\mathbf{a}=\big{a_{j}\big}{j=0}^{t};\big(\mathrm{w i t h};a{0}=1\big) $$

$$ w,:=,{a_{j}}_{j=t+1}^{m} $$

$$ \ \pi\,=,A,B,C), $$

$$ A,\mathcal{C}\in\mathbb{G}_{1} $$

Verify. For the verication algorithm, Groth16 uses only a part of its structured reference string which we will call verication key vk:

$$ B\in\mathring{\mathbb{G}}_{2} $$

$$ \mathsf{v k}:=\Big(P=g^{\alpha},Q=h^{\beta},\ \Big{S_{j}=g^{\frac{\beta v_{j}(s)+\alpha w_{j}(s)+y_{j}(s)}{\gamma}}\Big}_{j=0}^{t},H=h^{\gamma},D=h^{\delta}\Big). $$

Groth16 verication consists in checking a pairing equation between the proof elements = (A;B;C) using the verication key: Yt

$$ \pi=(A,B,C) $$

$$ e(A,B)=e(g^{\alpha},h^{\beta})\cdot e(\prod_{j=0}^{t}S_{j}^{a_{j}},h^{\gamma})\cdot e(C,h^{\delta}). $$

Assumptions. We introduce two new assumptions necessary to prove our schemes are secure. Formal proofs that these assumptions hold in the Generic Group Model can be found in Appendix B.1.

Assumption 1 (ASSGP) The (q;m)-Auxiliary Structured Single Group Pair- ing assumption holds for the bilinear group generator G if for all PPT ad- versaries A we have, on the probability space gk = (p; G₁*;G₂;* G_T) G (1), g $ G₁*;h* $ G₂ and a;b $ Z_pthe following probability is negligible in : 2 3

$$ \ \mathfrak{g}\ \mathfrak{k}=(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T})\leftarrow\mathcal{G}(1^{\lambda}) $$

$$ g\gets!!\mathfrak\phi{\mathbb G}{1},h\gets!\mathfrak\phi{\mathbb G}{2} $$

$$ a,b\gets\sharp\mathbb{T}_{p} $$

$$ \operatorname*{P r}\left[\begin{array}{c|c}{(A_{0},\ldots,A_{q-1})\neq\mathtt{1}{\mathbb{G}{1}}}&{g\xleftarrow{}\ \ mathtt S{}{1},h\leftarrow\mathtt{S S}{2},a,b\leftarrow\mathtt{S Z_{{P}}}}\ {\land\ \prod_{i=0}^{q-1}e(A_{i},h^{b})=1_{\mathbb{G}{T}}}&{\sigma=(g^{a},g^{b},h^{a},h^{b})^{2-}}\ {\land\ \prod{i=0}^{q-1}e(A_{i},h^{b^{i}})=1_{\mathbb{G}{T}}}&{\mathtt{a u x}\leftarrow(g^{a},g^{b^{i}},h^{a},h^{b^{i}}){i=2q}^{-}}\ {}&{\land\ \ \mathbb{A}\leftarrow(mathtt mathtt g k,\sigma,\mathtt{a u x})}\ \end{array}\right]. $$

Assumption 2 (ASDGP) The (q;m)-ASDGP assumption holds for the bilin- ear group generator G if for all PPT adversaries A we have, on the probability space gk = (p; G₁*;G₂;* G_T) G (1), g $ G₁*;h* $ G₂ and a;b $ Z_pthe fol- lowing probability is negligible in : 2 3

$$ \mathrm {g k} = \left(p, \mathbb {G} _ {1}, \mathbb {G} _ {2}, \mathbb {G} _ {T}\right) \leftarrow \mathcal {G} \left(1 ^ {\lambda}\right), g \leftarrow $ \mathbb {G} _ {1}, h \leftarrow $ \mathbb {G} _ {2} a n d $$

$$ a,b\gets\mathtt{s}\mathbb{Z}_{p} $$

$$ \lambda $$

$$ \operatorname*{P r}[\begin{matrix}{(\mathbf{A}\neq\mathbf{1}{\mathbb{G}{1}}\ \lor\ \mathbf{B}\neq\mathbf{1}{\mathbb{G}{2}})\ \wedge}&{g\leftrightarrow\mathbb{G}{1},h\ e\leftrightarrow\mathbb{G}{2},a,b\leftarrow\mathbb{S}{T}}\ {\prod{l=0}^{q-1}e(A_{i},h^{a_{i}})\prod_{l=q}^{2q-1}e(g^{a_{i}},B_{i})={1}{\mathbb{G}{T}}}&{\sigma=(g^{a^{i}},g^{b_{i}},h^{a_{j}})^{\ }}\ {}\end{matrix} $$

We can similarly dene the dual assumptions, by swapping G₁ and G₂ in the denition above.

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{2} $$

3 Pair Group Commitment Schemes

In this section we introduce a new commitment scheme to group elements in a bilinear group. In order to use them in our aggregation protocol, we require the following properties from the commitment schemes:

Computationally Binding Commitment: as per Denition 4

Constant Size Commitment: the commitment value is independent of the length of the committed vector

Doubly-Homomorphic: homomorphic both in the message space and in the key space

$$ \begin{aligned}{\mathsf{C M}(\mathsf{c k}{1}+\mathsf{c k}{2};M_{1}+M_{2})=\mathsf{C M}(\mathsf{c k}{1};M{1})}&{{}+\mathsf{C M}(\mathsf{c k}{1};M{2})+}\ {}&{{}\mathsf{C M}(\mathsf{c k}{2};M{1})+\mathsf{C M}(\mathsf{c k}{2};M{2}).}\ \end{aligned} $$

Collapsing Property: double-homomorphism implies a distributive property between keys and messages that allows multiple messages to be collapsed via a deterministic function Collapse dened as follows: 0 0 11 0 1

$$ \mathsf{C o l a a p s e}\left(\mathsf{C M}\left(\begin{matrix}{\mathsf{c k}{1}|\mathsf{c k}{1}^{\prime}}&{M_{1}|M_{1}}\ {\mathsf{c k}{2}|\mathsf{c k}{2}^{\prime}}&{M_{2}|M_{2}}\ {\mathsf{c k}{3}}&{M{3}}\ \end{matrix}\right)\right)=\mathsf{C M}\left(\begin{matrix}{\mathsf{c k}{1}+\mathsf{c k}{1}^{\prime}}&{M_{1}}\ {\mathsf{c k}{2}+\mathsf{c k}{2}^{\prime}}&{M_{2}}\ {\mathsf{c k}{3}}&{M{3}}\ \end{matrix}\right) $$

There are a few candidates for such schemes, but none of them are adapted for + fullling our goals. The commitment schemes proposed by [DRZ20, BMM 19] work under some new assumption that asks for the commitment keys to be structured in a specic way. In order to use this commitment, we need to run a new trusted setup to generate a commitment key. It would be impossible to consider existing Groth16 setups, since those give away elements that break the binding of the commitment scheme.

$$ 3 \mathrm {M M} ^ {+} 1 9 ] $$

Our main goal is to nd a commitment scheme that uses a structured reference string similar to the one from many popular SNARK implementations, e.g. Groth16.

The commitment scheme proposed by Lai et al. [LMR19] is likely to satisfy these properties, but it is shown to be binding only for unstructured random public parameters; however, in order to obtain a log-time verication Inner Pairing Product Argument scheme, we would need some structure for the commitment keys. We adapt the commitments from [LMR19] to work with structured keys and prove the binding property for an adversary that has access to these structured public parameters under our new assumptions ASSGP and ASDGP.

To optimise the commitment sizes, we dene two dierent variants of the commitment scheme: one that takes a vector of elements of a single group G₁, and one that takes two vectors of points in G₁ and G₂, respectively.

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{2}. $$

Single group version CM_s. This version is useful for the MIPP relation. It n takes one vector A 2 G₁aⁿd outputs two target group elements (T_A;U_A) 2 G²_T as a commitment. KG (1)! ck = (v₁*;*v₂). Sample a;b Z and set

$$ \mathbf{c M}_{s} $$

$$ \mathbf{A}\in\mathbb{G}_{1}^{n} $$

$$ \ T_{A},U_{A});\in\mathbb{G}_{T}^{2} $$

$$ \mathrm {K G} _ {s} \left(1 ^ {\lambda}\right)\rightarrow \mathrm {c k} _ {s}=\left(\mathbf {v} _ {1}, \mathbf {v} _ {2}\right). \text {S a m p l e} a, b \leftarrow \mathbb {s} \mathbb {Z} _ {p} \text {a n d s e t} $$

$$ \mathbf{v}{1}=(h,h^{a},\ldots,h^{a^{n-1}}),\ \ \ \ \mathbf{v}{2}=(h,h^{b},\ldots,h^{b^{n-1}}). $$

$$ \mathsf{C M}{s}(\mathsf{c k}{s}=(\mathbf{v}{1},\mathbf{v}{2}),\mathbf{A}=(A_{0},\ldots,A_{n-1}))\to(T_{A},U_{A}): $$

$$ \ .\ \ T_{A}=\mathbf{A}*\mathbf{v}{1}=e(A{0},h)\cdot e(A_{1},h^{a})\ldots e(A_{n-1},h^{a^{n-\ }}) $$

$$ 2\ U{{A A A}}=\ {bf A}\ast{\bf v}{2}=e(A_{0},h\cdot e(A_{1},h{{}}^{b})\ldots e(A_{n-1},h^{b^{n-1}}) $$

Lemma 1. Under the hardness of (n;m)-ASSGP assumption for m > 2n, this commitment scheme is computationally binding as per Denition 4.

$$ (n,m)\mathrm{\ \ //S S G G} $$

$$ m>2n $$

Proof. Suppose there exists a PPT adversary A that breaks the binding property of the commitment scheme. Then, given the output ((T_A;U_A); A*;A ) of the adversary A, we have that (T_A;U*_A) = (T_A;U_A):

$$ \ {\ }! $$

$$ ((T_{A},U_{A});\mathbf{A},\mathbf{A}^{*}) $$

$$ {\mathcal A}, $$

$$ \left(T_{A},U_{A}\right)=\left(T_{A^{}},U_{A^{}}\right) $$

$$ \begin{array}{l} e \left(A _ {0}, h\right) e \left(A _ {1}, h ^ {a}\right) \dots e \left(A _ {n - 1}, h ^ {a ^ {n - 1}}\right) = e \left(A _ {0} ^ {}, h\right) e \left(A _ {1} ^ {}, h ^ {a}\right) \dots e \left(A _ {n - 1} ^ {}, h ^ {a ^ {n - 1}}\right) \ e \left(A _ {0}, h\right) e \left(A _ {1}, h ^ {b}\right) \dots e \left(A _ {n - 1}, h ^ {b ^ {n - 1}}\right) = e \left(A _ {0} ^ {}, h\right) e \left(A _ {1} ^ {}, h ^ {b}\right) \dots e \left(A _ {n - 1} ^ {}, h ^ {b ^ {n - 1}}\right) \ \end{array} $$

By applying the homomorphic properties of the commitment scheme to these equations we get:

$$ \begin{aligned}{e(A_{0}/A_{0}^{},h)e(A_{1}/A_{1}^{},h^{a})\dots e(A_{n-1}/A_{n-1}^{},h^{a^{n-1}})}&{{}=1}\ {e(A_{0}/A_{0}^{},h)e(A_{1}/A_{1}^{},h^{b})\dots e(A_{n-1}/A_{n-1}^{},h^{b^{n-1}})}&{{}=1}\ \end{aligned} $$

where the vector (A₀=A₀;A₁=A₁;:::A_{n 1}=A_{n 1}) 6= 1_G1. This breaks the (n;m)- ASSGP assumption.

$$ (A_{0}/A_{0}^{},A_{1}/A_{1}^{},\ldots A_{n-1}/A_{n-1}^{*})\neq\mathbf{1}{\mathbb{G}{1}} $$

$$ (n,m) $$

Double group version CM_d. This version is useful for the TIPP relation. n n It takes two vectors A 2 G₁; B 2 G₂aⁿd outputs two target group elements (T_AB;U_AB) 2 G²_Tas a commitment.

$$ \mathbf{c M}_{d} $$

$$ \mathbf{A}\in\mathbb{G}{1}^{n},\mathbf{B}\in\mathbb{G}{2}^{n} $$

$$ \left(T_{A B},U_{A B}\right),\in\mathbb{G}_{T}^{2} $$

KG_d(1)! ck_d= (v₁*;v₂;w₁;*w₂) : Sample a;b $ Z_pand set n 1 n n 1 a a a a² v₁ = (h;h;:::;h); w₁ = (g;:::;g),

$$ a,b\gets\sharp\mathbb{Z}_{p} $$

$$ \mathbf{v}{1}=(h,h^{a},\dots,h^{a^{n-1}}),\quad\mathbf{w}{1}=(g^{a^{n}},\dots,g^{a^{2n-1}}), $$

$$ \mathbf{v}{2}=(h,h^{b},\ldots,h^{b^{n-1}}),\ \ \ \ \mathbf{w}{2}=(g^{b^{n}},\ldots,g^{b^{2n-1}}). $$

$$ {mathsf\mathsf C M}{d}({\mathsf c k}{d},{\mathsf A},{\mathsf B})\to(T_{A B},U_{A B}); $$

$$ 1.\ T_{A B}=\left((\{}\ {\mathrm v_{1}}\ )({\mathrm w_{1}}*{\mathrm B}\right) $$

$$ 2. U _ {A B} = \left(\mathbf {A} * \mathbf {v} _ {2}\right) \left(\mathbf {w} _ {2} * \mathbf {B}\right) $$

Lemma 2. Under the hardness of (n;m)-ASDGP assumption for m > 2n, this commitment scheme is computationally binding.

$$ (n,m)\texttt{A S D G P} $$

$$ m>2n $$

Proof. The proof is analogous to the one of Lemma 1. Since the commitment is homomorphic, breaking the binding is equivalent to nding a non-trivial opening to 1. Thus it breaks the assumption.

Inner Pairing Product Commitments. It is straightforward to check that the two versions of pairing commitment schemes CM_sand CM_dare compatible with inner product arguments, in the sense that they satisfy all the necessary properties: constant size, doubly-homomorphic, and the identity is a collapse function dened Collapse_id(C) = C.

$$ \ {mathrm C}{\mathrm{M}}{}_{s} $$

$$ \ {mathrm C M}_{d} $$

$$ \cdot_{i d}(\mathcal{C})=\mathcal{C} $$

Reusing Groth16 SRS. The two commitment schemes have the advantage that they can reuse two compatible (independent) SNARK setup ceremonies for their structured keys generation and therefore can be easily deployed without requiring a new trusted setup.

The SRSes required for the generation of the public commitment keys should satisfy some properties: We ask for the two ceremonies to use the same basis/generators in the same bilinear group g 2 G₁*;h 2* G₂, but two dierent randomnesses a;b; 2 Z_p;a 6= b for the exponents. The setups consists of conseci i i i a a m b b n utive powers fg;h g^i=0and fg;h gⁱ⁼⁰.

$$ g,\in,\mathbb{G}{1},h,\in,\mathbb{G}{2} $$

$$ a,b,\in\mathbb{Z}_{p},a\neq b $$

$$ {g^{b^{i}},h^{b^{i}}}_{i=0}^{n} $$

$$ {g^{a^{i}},h^{a^{i}}}_{i=0}^{m} $$

Importantly, even if the two setups have dierent dimensions m 6= n, this does not aect the binding of the commitments. The extra elements available to the adversaries are taken into account in the auxiliary input aux in the two assumptions, by setting the parameters accordingly.

$$ m\neq n. $$

4 MT-IPP Scheme

This new protocol will be used to prove two inner pairing product relations that are essential to SNARK aggregation: the multiexponentiation inner product (MIPP) between vectors C and r and the target inner pairing product (TIPP) between vectors A*;B, for vectors A;* C 2 G₁ and B 2 G₂.

$$ \mathbf{A},\mathbf{C}\in\mathbb{G}_{1} $$

$$ \mathbf{B}\in\mathbb{G}_{2} $$

In order to optimize the aggregation contruction, we design a new protocol MT-IPP that \fuses" together proofs for MIPP and TIPP relations. The formal relations R_mippand R_tippare stated in Appendix D.1.

$$ \mathcal{R}_{\mathsf{t i p p}} $$

We recall the two inner product maps for bilinear group gk = (p; G₁*;G₂;* G_T;e) and the combined relation for MT-IPP: Q

$$ \mathcal{R}_{\mathsf{m i p p}} $$

$$ \ \mathfrak{g}\ \mathsf{k}=\left(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T},e\right) $$

n n i 1.Multiexponentiation inner product map G₁ F*!* G₁: C rQ= C^ir

$$ \textstyle{\mathbb{G}{1}^{n}\times\mathbb{F}^{n}\to\mathbb{G}{1};\mathbb{C}*\mathtt{r}=\prod\mathbb{C}{i}^{r{i}}} $$

n n 2.Target inner pairing product map G₁G₂! G_T: A B := e(A_i;B_i) 9

$$ \mathbb{G}{1}^{n}\times\mathbb{G}{2}^{n}\to\mathbb{G}{T}\colon\mathbf{A}\ast\mathbf{{}B}:=\textstyle\prod e(A{i},B_{i}) $$

3.Relation for both MIPP and TIPP: 8 <

$$ \mathcal {R} _ {\mathrm {m t}} := \left{ \begin{array}{c c} \left(\left(T _ {A B}, U _ {A B}\right), \left(T _ {C}, U _ {C}\right)\right), & \left(\mathrm {C M} _ {s} (\mathbf {C}), Z _ {C}, r; \mathbf {C}\right) \in \mathcal {R} _ {\mathrm {m i p p}} \ Z _ {A B}, Z _ {C}, r; \mathbf {A}, \mathbf {B}, \mathbf {C}) & \wedge \ \left(\mathrm {C M} _ {d} (\mathbf {A}, \mathbf {B}), Z _ {A B}, r; \mathbf {A}, \mathbf {B}\right) \in \mathcal {R} _ {\mathrm {t i p p}} \end{array} \right} $$

Construction. Our MT-IPP makes black-box use of the two Pair Group Commitments schemes CM_s= (KG_s;CM_s) and CM_d= (KG_d;CM_d) from Section 3 and KZG Polynomial Commitment KZG: PC = (KZG*:* KG*;KZG:* CM*;KZG:* Open*;* KZG*:* Check) from Appendix A.4.

$$ {mathsf\mathsf C{M}}{s}=({\mathsf{K G}}{s},{\mathsf{C M}}_{s}) $$

$$ {\mathsf{C M}}{d}=\ {{\mathsf{K G}}}{d},{{\mathsf{C M}}}_{d}) $$

$$ \mathsf{K Z G.P C}=\left(\mathsf{K Z G.K G,K Z G.C M,K Z G.O p e n}\right. $$

The scheme consists of 3 algorithms: MT-IPP = (MT*:* Setup*;MT:* Prove*;MT:* Verify):

$$ \mathsf{M T-I P P}=(\mathsf{M T-S e t u p,M T.P r o v e,M T.V e r i f y}) $$

MT*:* Setup(1*; R*_mt)! crs_mt: 1.Run: ck := (v₁;v₂)

$$ {\mathsf{I p}}(1^{\lambda},\ \ {mathcal R R}{\mathsf{m t}})\to{\mathsf{c r s}}{\mathsf{m t}}; $$

$$ 1.\ \operatorname{R u n}\colon\mathsf{c k}{s}:=(\mathbf{v}{1},\mathbf{v}{2})\leftarrow\mathsf{C M}{s}(1^{\lambda}),\ \mathsf{c k}{d}:=(\mathbf{v}{1},\mathbf{v}{2},\mathbf{w}{1},\mathbf{w}{2})\leftarrow\mathsf{C M}{d}(1^{\lambda}). $$

s s d 2.Set commitment keys for KZG*:* PC scheme:

$$ \mathrm {c k} _ {1 v} := \left{h ^ {a ^ {i}} \right} _ {i = 0} ^ {n - 1}, \mathrm {v k} _ {1 v}:= g ^ {a} \quad \mathrm {c k} _ {1 w}:=\left{g ^ {a ^ {i}} \right} _ {i = 0} ^ {2 n - 1}, \mathrm {v k} _ {1 w}:= h ^ {a} $$

$$ \mathsf{c k}{2v}:={h^{b^{i}}}{i=0}^{n-1},;\mathsf{v k}{2v}:=g^{b}\qquad\mathsf{c k}{2w}:={g^{b^{i}}}{i=0}^{2n-1},;\mathsf{v k}{2w}:=h^{b} $$

$$ \mathsf{C k}{k2g}:=(\mathsf{C k}{j\sigma}),,\mathsf{V k}{k2g}:=(\mathsf{V k}{j\sigma}) $$

3.Dene ck_kzg:= (ck^j); vk^kzg:= (vk^j) for j = 1*;2; = v;w. 4.Fix Hash : G⁴!* Z and its description hk.

$$ j=1,2;;\sigma=v,w. $$

$$ {\mathsf{H a s h}}{c o m}\ \colon{\mathbb{G}}{T}^{4}\to{\mathbb{Z}}_{p} $$

$$ \ {sf n}{\sf k}_{c o m} $$

T 5.Fix Hash^x0: Z²_pG^TG₁*!* Z^pand its description hk_x0.

$$ {mathsf\mathsf H a s h}{x{0}}\colon\mathbb{Z}{p}^{2}\times\mathbb{G}{T}\times\mathbb{G}{1}\to\mathbb{Z}{p} $$

$$ {\mathsf{h k}}{x{\ 0}}. $$

6.Fix Hash : Z^pG¹²_T! Z^pand its description hk.

$$ \mathbb{Z}{p},\dot{\times},\mathbb{G}{T}^{12}\to\mathbb{Z}_{p} $$

7.Fix Hash^z: Z^pG²₂G²₁! Z^pand its description hk_z.

$$ {\mathsf H{s h h}}{z}:\mathbb{Z}{p}\times\mathbb{G}{2}^{2}\times\mathbb{G}{1}^{2}\to\mathbb{Z}_{p} $$

$$ \ \mathrm{h}{\mathsf k}_{z} $$

8.Set crs_mt:= (hk_com*;hk_x0;hk;hk_z;ck_s;ck_d;ck_kzg;*vk_kzg).

$$ \mathrm {c r s} _ {\mathrm {m t}} := \left(\mathrm {h k} _ {c o m}, \mathrm {h k} _ {x _ {0}}, \mathrm {h k}, \mathrm {h k} _ {z}, \mathrm {c k} _ {s}, \mathrm {c k} _ {d}, \mathrm {c k} _ {\mathrm {k z g}}, \mathrm {v k} _ {\mathrm {k z g}}\right). $$

$$ \mathsf{M T}.\mathsf{P r o v e}(\mathsf{c r s}{\mathsf{m t}},(T{A B},U_{A B}),(T_{C},U_{C}),Z_{A B},Z_{C},r;\mathbf{A},\mathbf{B},\mathbf{C})\to\pi_{\mathsf{m t}} $$

{ Loop \split & collapse" for step i ‘

1. n⁰ = n_{i 1}*=*2 where n₀ = n = 2

$$ n^{\prime}=n_{i-1}/2 $$

$$ n_{0}=n=2^{\ell} $$

$$ \ \mathrm\it n^{\prime}<1 $$

2.If n⁰ < 1: break

1 1 0 r 0 r 0 r 3.Set B := B*;w₁ := w₁;*w₂ := w₂.

$$ \mathtt{B}^{\prime}:=\mathtt{B}^{\mathtt{r}},\mathtt{w}{1}^{\prime}:=\mathtt{w}{1}^{\mathtt{r}^{-1}},\mathtt{w}{2}^{\prime}:=\mathtt{w}{2}^{\mathtt{r}^{-1}} $$

4.Compute L/R inner products:

$$ \mathrm{L/R/} $$

$$ \left(Z _ {L}\right) _ {A B} = \mathbf {A} _ {\left[ n ^ {\prime}: \right]} * \mathbf {B} _ {\left[: n ^ {\prime} \right]} ^ {\prime} \text {a n d} \left(Z _ {R}\right) _ {A B} = \mathbf {A} _ {\left[: n ^ {\prime} \right]} * \mathbf {B} _ {\left[ n ^ {\prime}: \right]} ^ {\prime} $$

$$ (Z_{L}){C}=\mathbf{C}{[n^{\prime}:]}^{\mathbf{r}{[:n^{\prime}]}}\ \ \mathrm{a n d}\ \ (Z{R}){C}=\mathbf{C}{[[n^{\prime}]}^{\mathbf{r}_{[n^{\prime}]}} $$

5.Compute left cross commitments:

$$ (T_{L},U_{L}){A B}=\mathsf{C M}{d}(\({\bf v}{1},{\bf w}{1}^{\prime};{\bf v}{2},{\bf w}{2}^{\prime});{\bf A}{[n^{\prime}:]}||{\bf0},0||{\bf B}{[:n^{\prime}]}^{\prime})) $$

$$ (T_{L},U_{L}){C}=\ \mathsf{C M}{s}((\mathbf{v}{1},\mathbf{v}{2}),\ \mathbf{C}_{[n^{\prime}:]}||\mathbf{0}) $$

6.Compute right cross commitments:

$$ (T_{R},U_{R}){A B}=\mathsf{C M}{d}((\mathbf{v}{1},\mathbf{w}{1}^{\prime};\mathbf{v}{2},\mathbf{w}{2}^{\prime});\mathbf{0}||\mathbf{A}{[:n^{\prime}]},\mathbf{B}{[n^{\prime}::]}^{\prime}||\ {)} $$

$$ (T_{R},U_{R}){C}=\sf M C M_s((v{1},v_{2}),\ 0\vert\vert C_{[:n^{\prime}]}) $$

7.Compute hash to the vector commitments

$$ h_{c o m}=\mathsf{H a s h}{c o m}((T{A B},U_{A B}),\thinspace(T_{C},U_{C})). $$

8.Compute challenge x_i: x₀ = Hash_x0(r;h_com;Z_AB;Z_C).

$$ x_{i}\colon\mathsf{X}{0}=\mathsf{H a g h}{x_{0}}(r,h_{c o m},Z mathsf{Z}{A B},\mathsf{Z}{\mathcal{C}}) $$

$$ \begin{aligned}{x_{i}=\mathsf{H a s h}\left(x_{i-1};(Z_{L},Z_{R}){A B},(Z{L},Z_{R}){C},(T{L},U_{L};T_{R},U_{R}){A B},\right.}\ {\left.(T{L},U_{L};T_{R},U_{R})_{C}\right)}\ \end{aligned} $$

9.Compute Hadamard products on vectors

$$ \mathbf{A}:=\mathbf{A}{[:n^{\prime}]}\circ\mathbf{A}{[n^{\prime}]]}^{x_{i}},;\mathbf{B}^{\prime}:=\mathbf{B^{\prime}}{[:n^{\prime}]}\circ\mathbf{B^{\prime}}{[n^{\prime}:]}^{x_{i}^{-1}},;\mathbf{C}:=\mathbf{C}{[[n^{\prime}]}\circ\mathbf{C}{[n^{\prime}]]}^{x_{i}} $$

0 0 10.Compute Hadamard products on keys v₁*;v₂ and w₁;*w₂:

$$ \mathbf{v}{1},\mathbf{v}{2} $$

$$ \mathbf{w}{1}^{\prime},\mathbf{w}{2}^{\prime} $$

$$ (\mathbf{v_{1}},\mathbf{v_{2}})\mathrel{\mathop:}=(\mathbf{v_{1}}{[n:n^{\prime}]}\circ\mathbf{v{1}}{[n^{\prime}:]}^{x^{-1}},\mathbf{v{2}}{[:n^{\prime}]}\circ\mathbf{v{2}}_{[n^{\prime}:]}^{x^{-1}}) $$

$$ \left(\mathbf{w}{1}^{\prime},\mathbf{w}{2}^{\prime}\right):=(\mathbf{w}{1{[n{'}}]}^{\prime}\circ\mathbf{w}{1{[n{{'}}:]}}{{'}{}}{}^{x},\mathbf{w}{2{[{:}n{'}]}}^{\prime}\circ\mathbf{w}{2{[{{'}}::]}}^{x}) $$

11.Set n_i= n⁰

$$ n_{i}=n^{\prime} $$

{ Compute proofs (^vj;^wj)^j=1;2of correctness of nal commitment keys 0 0 (v₁;v₂) 2 G²2; (w₁;w₂) 2 G²1(This step is detailed in Appendix E): Q‘ 1j 1 2 1.Dene f (X) = (₁ + x X) and

$$ (\pi_{v_{j}},\pi_{w_{j}})_{j=1,2} $$

$$ (v_{1},v_{2})\in\mathbb{G}{2}^{2},;(w{1}^{\prime},\dot{w}{2}^{\prime})\in\mathbb{G}{1}^{2};(^{\ } $$

$$ \ \mathrm{1.\ }\mathrm{D e f i n e}\ f_{v}(X)=\prod_{j=0}^{\ell-1}(1+x_{\ell-j}^{-1}X^{2^{j}})\ \mathrm{a n d}} $$

$$ \textstyle f_{w}(X)=X^{n}\prod_{i=0}^{\ell-1}\left(1+x_{\ell-j}r^{-2^{j}}X^{2^{j}}\right) $$

j=0 2.Draw challenge z = H^ash_z⁽x_‘;v₁;v₂;w₁;w₂)

$$ z= $$

$$ \ {sf s h h}{z}(x{\ell},v_{1},v_{2},w_{1},w_{2}) $$

fv (a) fv (a) fw (a) fw (b) 3.Prove th^at v₁ = g; v₂ = h, w₁ = g; w₂ = h ^are KZG commitments of f_v(X) by opening evaluations in z

$$ v_{1}\ {\mathrm=}{~}g^{f_{v}(a)},\ v_{2}\ \mathrm{}{=}\ h^{f_{v}(a)},\ w w_{1}\ \mathrm{}{=}\ g^{f_{w}(a)},\ w_{2}\ \mathrm{}{=}\ h^{f_{w}(b)} $$

$$ f_{v}(X) $$

$$ \pi_{v_{j}}\leftarrow\mathsf{K Z G.O p e n}(\mathsf{c k}{j v};v{j},z,f_{v}(z);f_{v}(X))\mathrm{}{f o r}\mathsf{j}=1,2 $$

$$ \pi_ {w _ {j}} \leftarrow \mathrm {K Z G . O p e n} (\mathrm {c k} _ {j w}; w _ {j}, z, f _ {w} (z); f _ {w} (X)) \text {f o r j = 1 , 2} $$

$$ (v_{1},v_{2}),(w_{1}^{\prime},w_{2}^{\prime}) $$

$$ A,B^{\prime},C $$

0 0 { Given the nal elements A;B⁰;C and (v₁;v₂); (w₁;w₂) at the end of the r 0 0 loop after split & collapsing A*;B⁰ = B;C and v₁;v₂;w₁;*w₂, set 0 = A;B ;C; (Z; Z);(Z; Z);(T; U);(T; U);

$$ \mathbf{A},\mathbf{B}^{\prime}=\mathbf{B}^{\mathbf{r}},\mathbf{C} $$

$$ \mathbf{v}{1},\mathbf{v}{2},\mathbf{w}{1}^{\prime},\mathbf{w}{2}^{\prime}. $$

$$ \begin{aligned}{\pi_{\mathsf{m t}}=\big(A,B^{\prime},C,(\mathbf{Z_{L}},\mathbf{Z_{R}}){A B},(\mathbf{Z{L}},\mathbf{Z_{R}}){C},(\mathbf{T{L}},\mathbf{U_{L}}){A B},(\mathbf{T{R}},\mathbf{U_{R}}){A B},}\ {(\mathbf{T{L}},\mathbf{U_{L}}){C},(\mathbf{T{R}},\mathbf{U_{R}}){C},(v{1},v_{2}),(w_{1}^{\prime},w_{2}^{\prime}),(\pi_{v_{j}},\pi_{w_{j}})_{j=1,2}\big)}\ \end{aligned} $$

MT*:* Verify(crs_mt;statement;_mt)! b:

$$ \ (\mathsf{c r s}{\mathsf{m t}},\mathsf{s t a t e m e n t};\pi{\mathsf{m t}})\to b! $$

1.Parse statement = ((T_AB;U_AB); (T_C;U_C);Z_AB;Z_C;r)

$$ =((T_{A B},U_{A B}),(T_{C},U_{C}),Z_{A B},Z_{C},r) $$

2.Compute hash to the commitments

$$ h_{c o m}=\mathsf{H a s h}{c o m}((T{A B},U_{A B}),(T_{C},U_{C})) $$

‘i 3.Reconstruct challenges fx_ig₌₁:

$$ {x_{i}}_{i=1}^{\ell}. $$

$$ x_{0}=\mathsf{H a s h}{x{0}}\big(r,h_{c o m},Z_{A B},Z_{\mathcal{C}}\big) $$

$$ \begin{array}{l} x _ {i} = \operatorname {H a s h} \left(x _ {i - 1}, \left(\mathbf {Z} _ {\mathbf {L}} [ i ], \mathbf {Z} _ {\mathbf {R}} [ i ]\right) _ {A B}, \left(\mathbf {Z} _ {\mathbf {L}} [ i ], \mathbf {Z} _ {\mathbf {R}} [ i ]\right) _ {C}, \right. \ \left(\mathbf {T} _ {\mathbf {L}} [ i ], \mathbf {T} _ {\mathbf {R}} [ i ], \mathbf {U} _ {\mathbf {L}} [ i ], \mathbf {U} _ {\mathbf {R}} [ i ]\right) _ {A B}, \left(\mathbf {T} _ {\mathbf {L}} [ i ], \mathbf {T} _ {\mathbf {R}} [ i ], \mathbf {U} _ {\mathbf {L}} [ i ], \mathbf {U} _ {\mathbf {R}} [ i ]\right) _ {C}\left. \right) \ \end{array} $$

4.Construct products and commitments recursively, i = 1*! ‘*: 1 x

$$ \begin{array}{l} - \left(Z _ {i}\right) _ {A B} = \mathbf {Z} _ {\mathbf {L}} [ i ] _ {A B} ^ {x _ {i}} \cdot \left(Z _ {i - 1}\right) _ {A B} \cdot \mathbf {Z} _ {\mathbf {R}} [ i ] _ {A B} ^ {x _ {i} ^ {- 1}} \ - \left(T _ {i}\right) _ {A B} = \mathbf {T} _ {\mathbf {L}} [ i ] _ {A B} ^ {x _ {i}} \cdot \left(T _ {i - 1}\right) _ {A B} \cdot \mathbf {T} _ {\mathbf {R}} [ i ] _ {A B} ^ {x _ {i} ^ {- 1}} \ - \left(U _ {i}\right) _ {A B} = \mathbf {U} _ {\mathbf {L}} [ i ] _ {A B} ^ {x _ {i}} \cdot \left(U _ {i - 1}\right) _ {A B} \cdot \mathbf {U} _ {\mathbf {R}} [ i ] _ {A B} ^ {x _ {i} ^ {- 1}} \ \mathrm {w h e r e} \left(Z _ {0}\right) _ {A B} = Z _ {A B}, \left(T _ {0}\right)) _ {A B} = T _ {A B}, \left(U _ {0}\right)) _ {A B} = U _ {A B} \ - \left(Z _ {i}\right) _ {C} = \mathbf {Z} _ {\mathbf {L}} [ i ] _ {C} ^ {x _ {i}} \cdot \left(Z _ {i - 1}\right) _ {C} \cdot \mathbf {Z} _ {\mathbf {R}} [ i ] _ {C} ^ {x _ {i} ^ {- 1}} \ - \left(T _ {i}\right) _ {C} = \mathbf {T} _ {\mathbf {L}} [ i ] _ {C} ^ {x _ {i}} \cdot \left(T _ {i - 1}\right) _ {C} \cdot \mathbf {T} _ {\mathbf {R}} [ i ] _ {C} ^ {x _ {i} ^ {- 1}}, \ - \left(U _ {i}\right) _ {C} = \mathbf {U} _ {\mathbf {L}} [ i ] _ {C} ^ {x _ {i}} \cdot \left(U _ {i - 1}\right) _ {C} \cdot \mathbf {U} _ {\mathbf {R}} [ i ] _ {C} ^ {x _ {i} ^ {- 1}} \ \mathrm {w h e r e} \left(Z _ {0}\right) _ {C} = Z _ {C}, \left(T _ {0}\right) _ {C} = T _ {C}, \left(U _ {0}\right) _ {C} = U _ {C} \ \end{array} $$

Q^{‘ 1i} 0 1 2 5.Compute nal vector value from r: r =i⁼⁰(¹ + x r) _‘ i

$$ r{\ \ !,,}r^{\prime}=\prod_{i=0}^{\ell-1}(1+x_{\ell-i}^{-1}r^{2^{i}}) $$

6.Verify nal values (T_‘;U_‘;Z_‘)_AB; (T_‘;U_‘;Z_‘)_C:

$$ (T_{\ell},U_{\ell},Z_{\ell}){A B},(T{\ell},U_{\ell},Z_{\ell})_{C}: $$

? 0 (a)(Z_‘)_AB= e(A;B)

$$ (Z_{\ell})_{A B}\stackrel{?}{=}e(A,B^{\prime}) $$

? r⁰ (b)(Z_‘)_C= C

$$ (Z_{\ell})_{C}\stackrel{?}{=}C^{r^{\prime}} $$

? 0 0? 0 0 (c)Check if (T_‘)_AB= e(A;v₁)e(w₁;B) and (U_‘)_AB= e(A;v₂)e(w₂;B)

$$ \left(T _ {\ell}\right) _ {A B} \stackrel {?} {=} e \left(A, v _ {1}\right) e \left(w _ {1} ^ {\prime}, B ^ {\prime}\right) \text {a n d} \left(U _ {\ell}\right) _ {A B} \stackrel {?} {=} e \left(A, v _ {2}\right) e \left(w _ {2} ^ {\prime}, B ^ {\prime}\right) $$

?? (d)Check if (T_‘)_C= e(C;v₁) and (U_‘)_C= e(C;v₂)

$$ (T_{\ell}){C}\stackrel{?}{=}e(C,v{1}) $$

$$ (U_{\ell}){C}\stackrel e e(e,v{2}) $$

0 0 7.Verify nal commitment keys v₁;v₂;w₁;w₂ as detailed in Appendix E

$$ v_{1},v_{2},w_{1}^{\prime},w_{2}^{\prime} $$

0 0 (a)Reconstruct KZG challenge point: z = Hash_z(x^‘;v₁;v₂;w₁;w₂) Q

$$ z=\mathsf{H a s h}{z}(x{\ell},v_{1},v_{2},w_{1}^{\prime},w_{2}^{\prime}) $$

‘ 1 1j 2 (b)Reconstruct commitment polynomials: f_v(X) =_j=0¹ + x X; ‘ j Q_‘ ¹

$$ f_{v}(X)=\prod_{j=0}^{\ell-1}\left(1+x_{\ell-j}^{-1}X^{2^{j}}\right) $$

$$ f_{w}(X)=X^{n}\prod_{j=0}^{\ell-1}\left(1+x_{\ell-j}r^{-2^{j}}X^{2^{j}}\right) $$

(c)Run verication for openings of evaluations in z for j = 1*;*2: b₁ KZG: Check(vk; v;z;f (z););

$$ j=1,2 $$

$$ b_{1j}\leftarrow\mathsf{K Z G.C h e c k}(\mathsf{v k}{j v};v{j},z,f_{v}(z);\pi_{v_{j}}), $$

$$ b_{2j}\leftarrow\mathsf{K Z G.C h e c k}(\mathsf{v k}{j w};w{j},z,f_{w}(z);\pi_{w_{j}}) $$

Theorem 3. If CM_s;CM_dare computationally binding commitments as per Def- inition 4, the hash functions are modelled as random oracles, and KZG: PC has computational knowledge binding as per Denition 6, then the protocol MT*-*IPP has completeness and computational knowledge soundness (Denition 1) against algebraic adversaries in the random oracle model.

$$ I!f!\ !\ {\sf C M}{s},!{\sf C M}{d} $$

Proof. An adversary breaking soundness of the MT-IPP scheme, either convinces 0 0 the verier of incorrect nal keys v₁;v₂;w₁;w₂ or breaks computational binding of one of CM_s*;*CM_d.

$$ v_{1},v_{2},w_{1}^{\prime},w_{2}^{\prime} $$

$$ {\mathsf{C M}}{s},{\mathsf{C M}}{d} $$

Since both CM_s;CM_dare computationally binding, what is left to show is the completeness and soundness of the proof of correctness of the nal commitment keys. The validity of the nal commitment keys is shown using the KZG: PC scheme. The complete analysis for this step follows in Appendix E.

$$ \ \mathsf{C}\mathbb{N}{s},\mathsf{C}\mathbb{N}{d} $$

5 SnarkPack: Aggregation Scheme

In this section we describe SnarkPack, our new ecient protocol for Groth16 aggregation. The relation proven by SnarkPack can be stated as follows:

Relation for Aggregation. More formally, we introduce the relation for agn n gregating n Groth16 proof vectors A*;* C 2 G₁; B 2 G₂with respect to a xed verication key vk:

$$ \mathbf{A},\mathbf{C}\in\mathbb{G}{1}^{n},\mathbf{B}\in\mathbb{G}{2}^{n} $$

$$ \mathcal{R}{\mathsf{A G G}}:={(\mathbf{u}={\mathbf{a}{i}}{i=0}^{n-1};\pi={(\mathbf{A},\mathbf{B},\mathbf{C})}):\mathsf{V e r i f y}(\mathsf{v k},u{i},\pi_{i})=1,\ \forall i} $$

tj where u_i= a_i= fa_i;jg₌₀;_i= (A_i;B_i;C_i) 2 G₁ G₂ G₁ for i = 0*;:::n* 1.

$$ u_{i}=\mathbf{a}{i}={a{i,j}}{j=0}^{t},\pi{i}=(A_{i},B_{i},C_{i})\in\mathbb{G}{1}\times\mathbb{G}{2}\times\mathbb{G}_{1} $$

The resulting argument for aggregation consists in 3 algorithms SnarkPack = (SP*:* Setup*;SP:* Prove*;SP:* Verify) that work as follows:

SP: Setup(1; RAGG)! (crsagg;vkagg)

$$ (1^{\lambda},\mathcal{R}{\mathsf{A G G}})\to(\mathsf{c r s}{\mathsf{a g g}},\mathsf{v k}_{\mathsf{a g g}}) $$

1.Generate commitment key for CM_d:

$$ \mathrm{C M}_{d}{} $$

$$ \mathsf{c k}{d}=(\mathbf{v}{1},\mathbf{v}{2},\mathbf{w}{1},\mathbf{w}{2})\leftarrow\mathsf{C M}{d}.\mathsf{K G}(1^{\lambda}) $$

2.Set commitment key for CM_s: ck_s= (v₁*;*v₂)

$$ {mathsf\mathsf C{M}}{s}:\mathsf{c k}{s}=\left(\mathbf{v}{1},\mathbf{v}{2}\right) $$

3.Call crs_mtMT*:* Setup(1*; R*_mt)

$$ \mathsf{c r s_{m t}\ \leftarrow M T.S e t u p(1^{\lambda},R_{m t})} $$

tp n 4.Fix hash function Hash^r: Z G⁴_T! Z_pgiven by its description hk_r

$$ :\mathbb{Z}{p}^{t\cdot n}\times\mathbb{G}{T}^{4}\to\mathbb{Z}_{p} $$

$$ {\mathsf{h}}{\mathsf{k}}_{r} $$

5.Set aggregation public parameters: crs_agg= (vk*;crs_mt;*hk_r)

$$ \sf{c r s}{a g g}=(sf V V,C r s{m t},h k_{r}) $$

SP: Prove(crsagg; u; = (A; B;C))!agg

$$ \ (sf C\sf{I}{a g g},\sf{U},\pi=(A,B,C))\rightarrow\pi{a g g} $$

1.Parse proving key crs_agg:= (vk*;crs_mt;ck_s;ck_d;hk) 2.Parse ck = (v₁;v₂);* ck = (v₁*;v₂;w₁;*w₂)

$$ \mathsf{C I S}{\mathsf{a g g}}:=(\mathsf{V k},\mathsf{C r S}{\mathsf{m t}},\mathsf{C k}{\mathsf{s}},\mathsf{C k}{\mathsf{d}},\mathsf{h k}) $$

$$ \operatorname{?a r s e}\ \mathsf{c k}{s}=(\mathbf{v}{1},\mathbf{v}{2}),\ \mathsf{c k}{d}=(\mathbf{v}{1},\mathbf{v}{2},\mathbf{w}{1},\mathbf{w}{2}) $$

3.Commit to A and B:

$$ \mathsf{C M}{d}((\mathbf{v{1}},\mathbf{v_{2}},\mathbf{w_{1}},\mathbf{w_{2}});\mathbf{A},\mathbf{B})=(T_{A B},U_{A B}) $$

4.Commit to C : CM_s((v₁*;v₂); C) = (T_C;U*_C)

$$ \mathsf{C M}{s}((v{1},v_{2});\mathbb{C})=(T_{\mathcal{C}},U_{\mathcal{C}}) $$

5.Hash these commitments h_com= Hash_com((T_AB;U_AB); (T_C;U_C))

$$ h_{c o m}=\mathsf{H a s h}{c o m}((T{A B},U_{A B}),(T_{C},U_{C})) $$

i 6.Derive random challenge r = Hash_r(u*;h*_com) and set r = fr gⁱn₌₀₁

$$ r={\mathsf{H a s h}}{r}(\mathbf{u},h{c o m}) $$

$$ \mathbf{r}={r^{i}}_{i=0}^{n-1} $$

$$ Z_{A B}=\mathbf{A^{r}}*mathbf B, $$

r 7.Compute ZAB= A B Q

r n 1i 8.Compute Z_C= C =_i=0C_ir.

$$ Z_{C}=\mathbf{C}^{\mathbf{r}}=\prod_{i=0}^{n-1}C_{i}^{r_{i}} $$

9.Run MT proof for inner products Z_AB;Z_C;r:

$$ Z_{A B},Z_{C},r\colon $$

mt= MT*:* Prove(crsmt*;* (TAB*;UAB);* (TC*;UC);ZAB;ZC;r*; A*;* B*;* C*;r) 10.Set_agg= ((T_AB;U*_AB); (T_C;U_C);Z_AB;Z_C;_mt) SP*:* Verify(vk_agg; u*;_agg)! b* 1.Parse SNARK instances u = fa_i;jg_{i=0;:::n 1;j=0;:::t} 2.Parse verication key vk^agg:= (vk*;crs_mt;hk) 3.Hash the commitments h_com= Hash_com((T_AB;U*_AB); (T_C;U_C)) tj 4.Parse vk := P = g;Q = h; fS^jg⁼⁰;H = h;D = h 5.Derive random challenge r = Hash_r(u*;h*_com) 6.Set statement = (u*;* (T_AB;U_AB); (T_C;U_C);Z_AB;Z_C;r) 7.Check MT proof b¹MT*:* Verify(crs^mt;statement;^mt) Pn 1 i i=0aijr 8.Compute Z_Sj= S_jfor _all j = 0 :::t 9.Check Groth16 nal equation to the decision bit b₂: Yt Pn 1 i ^? r Z = e(Pⁱ⁼⁰;Q)e( Z;H)e(Z;D) AB Sj C j=0

$$ \pi_{\mathsf{m t}}=\mathsf{M T.P r o v e}(\mathsf{c r s}{\mathsf{m t}},(T{A B},U_{A B}),(T_{C},U_{C}),Z_{A B},Z_{C},r;\mathbf{A}B,\mathbf{B},\mathbf{C},\mathbf{r}) $$

$$ \pi_{\mathsf{a g g}}=((T_{A B},U_{A B}),(T_{C},U_{C}),Z_{A B},Z_{C},\pi_{\mathsf{m t}}) $$

$$ \ (\mathsf{V k}{\mathsf{a g g}},\mathbf{u},\pi{\mathsf{a g g}})\to b $$

$$ \mathbf{u}=\big{a_{i,j}\big}_{i=0,\ldots n-1;j=0,\ldots t} $$

$$ \mathsf{v k}{\mathsf{a g g}}:=(\mathsf{v k},\mathsf{c r s}{\mathsf{m t}},\mathsf{h k}) $$

$$ \tilde{h_{c o m}}=\mathsf{H a s h}{c o m}((T{A B},U_{A B}),(T_{C},U_{C})) $$

$$ {:=\ \big(P=g^{\alpha},Q=h^{\beta},\ {S_{j}}_{i=0}^{t},H=h^{\gamma},D=h^{\delta}\big)} $$

$$ r={mathsf{H a s h}}{r}(\mathbf{u},h{c o m}) $$

$$ =(\mathbf{u},(T_{A B},U_{A B}),(T_{C},U_{C}),Z_{A B},Z_{C},r) $$

$$ b_{1}\leftarrow\ \ {sf M M}.V\r i e f y(c r s_{m t} $$

$$ Z_{S_{i}}=S_{i}^{\sum_{i=0}^{n-1}a_{i j}r^{i}} $$

$$ j=0\ldots t $$

$$ b_{2}: $$

$$ Z_{A B}\overset{?}{=}e(P^{\sum_{i=0}^{n-1}r^{i}},Q)e(\prod_{j=0}^{t}Z_{S_{j}},H)e(Z_{C},D) $$

10.Set decision bit b = b₁ ^ b₂

$$ b=b_{1}\wedge b_{2} $$

6 Implementation

SnarkPack is implemented in Rust and the code is publicly available at the featipp2 branch [Fil21] of the bellperson repository [Fil18a]. The implementation uses the paired [Fil18b] library on the BLS12-381 curve. All proofs to be aggregated are Groth16 proofs with 350 public inputs (instances). All benchmarks are done on a 32 cores / 64 threads machine with AMD Ryzen Threadripper CPUs. Parallelism: It is important to note that the protocol allows for some parallel operations and our implementation makes use of that. Therefore, all benchmarks presented here can change depending on the degree of parallelism of the machine. Trusted Setup: We created a condensed version of the SRS required for our protocol from the powers of tau transcript of both Zcash [Zca18] and Filecoin [Lab18]. The code to assemble the SRS from two powers of tau can be found at 19 [nik21]. The SRS created allows the aggregation of up to 2 proofs.

$$ 2^{19} $$

Field elements compression: The proof requires many pairing operations and multiplications in the target group which employ arithmetic over the nite eld + Fp12. Using algorithms derived from RELIC library [AGM], we implemented compression of these eld elements that still allows some computations without decompression. This led to a 40% reduction in proof size.

$$ \mathbb{F}_{p^{12}} $$

$$ \ \mathrm\ \{[A G M^{+}] $$

Compressing pairing checks: A further performance gain in our SnarkPack is given by the verication batch which applies to the pairing checks from MT-IPP verication: we scale each pairing check of the form e(A;B)e(C;D)::: = T with a random exponent when verifying so we can compress multiple such

$$ e(A,B)e(,C,D)...,=,T $$

Fig. 1. Aggregation Time and Proof size.

checks into one. This randomized checking technique is borrowed from the Zcash specs [HBHW21]. Specically, we have a list P of length n of pairing checks of the form e(A;B)e(C;D)::: = T. To compute a pairing we need to apply two steps: the Miller Loop (ML) and the Final Exponentiation (FE). We take advantage of the homomorphic properties of these two operations to improve the verication time by checking many pairing equations at once. The verier performs the following steps to verify all checks in a compressed manner:

$$ e(A,B)e(C,D,...=T $$

1.Choose n randoms scalars r_iwith r₀ = 1

$$ r_{i} $$

$$ r_{0}=1 $$

2.Randomize each pairing check P_ifor i > 1:

$$ P_{i} $$

$$ i>1 $$

$$ e(A_{i}^{r_{i}},B_{i})e(C_{i}^{r_{i}},D_{i})\cdots=T^{r_{i}} $$

3.Compute the Miller Loop (ML) on the left side of each pairing check:

$$ m_{i}=\mathbb{M L}\big((A_{i}^{r_{i}},B_{i})(C_{i}^{r_{i}},D_{i}),\ldots\big) $$

4.Multiply all results together and apply the Final Exponentiation (FE): Y Y

$$ \operatorname{F E}(\prod_{i}m_{i})=\prod_{i}T_{i}^{r_{i}} $$

Proof Size. The proof size in Fig. 1 compares the size of n proofs versus the size of one aggregated proof. The gure shows that the break-even point where aggregation takes less space than batching occurs around 150 proofs. At 128 proofs, the size of an aggregated proof is 23kB, versus 24kB for individual proofs.

Aggregation time. Fig. 1 shows the time taken by the aggregator (prover) to create an aggregated proof. SnarkPack can aggregate 1024 proofs in 1.4s. The prover is required to compute a logarithmic number of multi-exponentiations and expensive pairing products. Our implementation perform these in parallel and in batches (batching Miller Loop operations).

Verication time. Fig. 2 shows the comparison between the verication of an aggregated proof and other batching techniques described in the Zcash protocol [HBHW21]. Verifying Groth16 proofs in batches is what is commonly used in

Fig. 2. Verifcation time: Aggregation vs Batching.

Zcash as well as Filecoin to get a sublinear verication time. The graph shows that batching is more ecient when verifying fewer than 32 Groth16 proofs but that aggregation becomes exponentially faster after that point. SnarkPack scales logarithmically and can verify 8192 proofs in 163ms, including unserialization. Note that the verication algorithm is linear in terms of the public inputs. In our case, 350 public inputs per proof is small enough to barely count for the total verication time.

Acknowledgements. We would like to thank Benedikt Bunz, Pratyush Mishra, and Psi Vesely for valuable discussions on this work, as well as Ben Fisch and Nicola Greco for the initial intuition of using inner pairing product proofs for aggregating Filecoin SNARK-based proofs. We are also grateful to digniedquire for his contributions to the Rust codebase.

References

⁺ ABL 19.Behzad Abdolmaleki, Karim Baghery, Helger Lipmaa, Janno Siim, and Michal Zajac. UC-secure CRS generation for SNARKs. pages 99{117, 2019. ⁺ AGM.D. F. Aranha, C. P. L. Gouv^ea, T. Markmann, R. S. Wahby, and K. Liao. RELIC is an Ecient LIbrary for Cryptography. https://github.com/ relic-toolkit/relic. ⁺ BCG 14.Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from Bitcoin. Cryptology ePrint Archive, Report 2014/349, 2014. https://eprint.iacr.org/2014/349. ⁺ BCG 15.Eli Ben-Sasson, Alessandro Chiesa, Matthew Green, Eran Tromer, and Madars Virza. Secure sampling of public parameters for succinct zero knowledge proofs. pages 287{304, 2015. ⁺ BCG 20.Sean Bowe, A. Chiesa, Matthew Green, Ian Miers, Pratyush Mishra, and H. Wu. Zexe: Enabling decentralized private computation. 2020 IEEE Symposium on Security and Privacy (SP), pages 947{964, 2020.

⁺ BCI 13.Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct non-interactive arguments via linear interactive proofs. pages 315{333, 2013. BCTV14.Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Succinct non-interactive zero knowledge for a von neumann architecture. pages 781{796, 2014. BGM17.Sean Bowe, Ariel Gabizon, and Ian Miers. Scalable multi-party computation for zk-SNARK parameters in the random beacon model. Cryptology ePrint Archive, Report 2017/1050, 2017. https://eprint.iacr.org/2017/1050. ⁺ BMM 19.Benedikt Bunz, Mary Maller, Pratyush Mishra, Nirvan Tyagi, and Psi Vesely. Proofs for inner pairing products and applications. Cryptology ePrint Archive, Report 2019/1177, 2019. https://eprint.iacr.org/2019/ 1177. Dam00.Ivan Damgard. Ecient concurrent zero-knowledge in the auxiliary string model. pages 418{430, 2000. DRZ20.Vanesa Daza, Carla Rafols, and Alexandros Zacharakis. Updateable inner product argument with logarithmic verier and applications. pages 527{ 557, 2020. Fil18a.Filecoin. bellperson, groth16 library, 2018. https://github.com/ filecoin-project/bellperson. Fil18b.Filecoin. paired: high performance bls12-381 library, 2018. https:// github.com/filecoin-project/paired. Fil20.Filecoin. Filecoin powers of tau ceremony attestations, 2020. https:// github.com/arielgabizon/perpetualpowersoftau. Fil21.Filecoin. Groth16 aggregation library, 2021. https://github.com/ filecoin-project/bellperson/tree/feat-ipp2. Fis19.Ben Fisch. Tight proofs of space and replication, 2019. https://web. stanford.edu/~bfisch/tight_pos.pdf. GGPR13.Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. pages 626{ 645, 2013. Gro16.Jens Groth. On the size of pairing-based non-interactive arguments. pages 305{326, 2016. HBHW21.Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox. Zcash protocol specication, 2021. https://zips.z.cash/protocol/protocol. pdf. KZG10.Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. pages 177{194, 2010. Lab18.Protocol Labs. Filecoin, 2018. https://filecoin.io/filecoin.pdf. LMR19.Russell W. F. Lai, Giulio Malavolta, and Viktoria Ronge. Succinct arguments for bilinear group arithmetic: Practical structure-preserving cryptography. pages 2057{2074, 2019. nik21.nikkolasg. Tau aggregation for ipp, 2021. https://github.com/nikkolasg/ taupipp. PHGR13.Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. Pinocchio: Nearly practical veriable computation. pages 238{252, 2013. Zca18.Zcash. Zcash powers of taus ceremony attestation, 2018. https://github. com/ZcashFoundation/powersoftau-attestations.

A Cryptographic Primitives

A.1 SNARKs

Let R be an eciently computable binary relation which consists of pairs of the form (u;w). A Proof or Argument System for R consists in a triple of PPT algorithms = (Setup*;Prove;*Verify) dened as follows:

Setup(1*; R*)! crs: takes a security parameter and a binary relation R and outputs a common (structured) reference string crs.

$$ \mathfrak{h}(1^{\lambda},\mathcal{R})\rightarrow $$

Prove(crs*;u;w*)! : on input crs, a statement u and the witness w, outputs an argument.

Verify(crs*;u;)!* 1*=*0: on input crs, a statement u, and a proof, it outputs either 1 indicating accepting the argument or 0 for rejecting it.

We call a Succinct Non-interactive ARgument of Knowledge (SNARK) if further it is complete, succinct and satises Knowledge Soundness (also called Proof of Knowledge).

Non-black-box Extraction. The notion of Knowledge Soundness requires the existence of an extractor that can compute a witness whenever the prover A produces a valid argument. The extractor we dened bellow is non-black-box and gets full access to the prover’s state, including any random coins. More formally, a SNARK satises the following denition:

Denition 1(SNARK). = (Setup*;Prove;*Verify) is a SNARK for an NP language L_Rwith corresponding relation R, if the following properties are sat- ised.

$$ L_{\mathcal{R}} $$

Completeness. For all (x;w) 2R, the following holds:

$$ (x,w)\in\mathcal{R} $$

$$ \operatorname*{P r}\left(\mathsf{V e r i f y}(\mathsf{c r s},u,\pi)=1\middle|\begin{matrix}{\mathsf{c r s}\leftarrow\mathsf{S e t u p}(\ {mathtt l^{{lambdalambda}}},\mathcal{R})}\ {\pi\leftarrow\mathsf{P r o v e}(\mathsf{c r s},u,w)}\ \end{matrix}\right)=1 $$

Knowledge Soundness. For any PPT adversary A, there exists a PPT ex- tractor Ext_Asuch that the following probability is negligible in :

$$ \mathsf{E x t}_{\mathcal{A}} $$

$$ \Pr \left( \begin{array}{c c} \operatorname {V e r i f y} (\mathrm {c r s}, u, \pi) = 1 \ \wedge \mathcal {R} (u, w) = 0 \end{array} \right| \begin{array}{c} \mathrm {c r s} \leftarrow \operatorname {S e t u p} \left(1 ^ {\lambda}, \mathcal {R}\right) \ ((u, \pi); w) \leftarrow \mathcal {A} | \chi_ {\mathcal {A}} (\mathrm {c r s}) \end{array} ) = \operatorname {n e g l} (\lambda). $$

Succinctness. For any u and w, the length of the proof is given by j j = poly() polylog(juj + jwj).

$$ |\pi|,= $$

$$ \mathsf{p o l y(\lambda)\ \cdot\mathsf{p o l y l o g}(|u|+|w|)} $$

Zero-Knowledge. A SNARK is zero-knowledge if it does not leak any information besides the truth of the statement. More formally:

Denition 2(zk-SNARK). A SNARK for a relation R is a zk-SNARK if there exists a PPT simulator (S₁; S₂) such that S₁ outputs a simulated common reference string crs and trapdoor td*; S₂ takes as input* crs*, a statement u and* td*,* and outputs a simulated proof; and, for all PPT (stateful) adversaries (A₁; A₂), for a state st*, the following is negligible in :*

$$ (\mathcal{S}{1},\mathcal{S}{2}) $$

$$ \mathcal{S}_{1} $$

$$ \ _{2} $$

$$ (\mathcal{A}{1},\mathcal{A}{2}) $$

$$ \begin{array}{l} \left| \Pr \left( \begin{array}{c c} (u, w) \in \mathcal {R} \wedge \ \mathcal {A} _ {2} (\pi , \mathrm {s t}) = 1 \end{array} \right| \begin{array}{c} \mathrm {c r s} \leftarrow \operatorname {S e t u p} \left(1 ^ {\lambda}\right) \ (u, w, \mathrm {s t}) \leftarrow \mathcal {A} _ {1} \left(1 ^ {\lambda}, \mathrm {c r s}\right) \ \pi \leftarrow \operatorname {P r o v e} \left(\mathrm {c r s}, u, w\right) \end{array} \right) - \ \Pr \left( \begin{array}{c c} (u, w) \in \mathcal {R} \wedge \ \mathcal {A} _ {2} (\pi , \mathrm {s t}) = 1 \end{array} \right| \left. \begin{array}{c} (\mathrm {c r s}, \mathrm {t d}) \leftarrow \mathcal {S} _ {1} \left(1 ^ {\lambda}\right) \ (u, w, \mathrm {s t}) \leftarrow \mathcal {A} _ {1} \left(1 ^ {\lambda}, \mathrm {c r s}\right) \ \pi \leftarrow \mathcal {S} _ {2} \left(\mathrm {c r s}, \mathrm {t d}, u\right) \end{array} \right} \Bigg | = \operatorname {n e g l} (\lambda). \ \end{array} $$

A.2 Commitment Schemes

A non-interactive commitment scheme allows a sender to create a commitment to a secret value. It may later open the commitment and reveal the value or some information about the value in a veriable manner. More formally:

Denition 3(Non-Interactive Commitment). A non-interactive commit- ment scheme is a pair of algorithms Com = (KG*;CM):*

$$ \mathrm {C o m} = (\mathrm {K G}, \mathrm {C M}) $$

KG(1)! ck: given a security parameter, it generates a commitment public key ck*. This* ck implicitly species a message space M_ck, a commitment space C_ckand (optionally) a randomness space R_ck,. This algorithm is run by a trusted or distributed authority.

$$ {\mathsf{K G}}(1^{\lambda})\rightarrow $$

$$ {lambda}, $$

$$ M_{\mathrm{c k}} $$

$$ C_{\mathrm{c k}} $$

$$ R_{\ {bf c c}\ }. $$

CM(ck;m)! C: given ck and a message m, outputs a commitment C. This algorithm species a function Com_ck: M_ckR_ck! C_ck. Given a message m 2 M_ck, the sender (optionally) picks a randomness 2 R_ckand computes the commitment C = Com_ck(m;)

$$ {\mathsf{C M}}({mathsf{c k}};m)\to C $$

$$ \mathsf{C o n}{\mathsf{c k}}:M{\mathsf{c k}}\times\mathcal{R}{\mathsf{c k}}\to\mathcal{C}{\mathsf{c k}} $$

$$ m\in M_{\mathsf{c k}} $$

$$ \rho\in R_{\mathsf{c k}} $$

$$ C,{=},{\mathsf{C o m}}_{\mathsf{c k}}(m,\rho) $$

For deterministic commitments we simply use the notation C = CM(ck;m) := Com_ck(m), while for randomised ones we write C $ CM(ck;m) := Com_ck(m;).

$$ {\mathcal{C}}={\mathsf{C M}}({\mathsf{c k}};m):= $$

$$ \cos_{c k}(m) $$

$$ C\bot M(\ infty m:= $$

A commitment scheme is asked to satisfy one or more of the following properties:

Binding Denition. It is computationally hard, for any PPT adversary A, to come up with two dierent openings m 6= m 2 M_ckfor the same commitment C. More formally:

$$ \mathcal{A}, $$

$$ n\neq m^{*}\in M_{\mathsf{c k}} $$

Denition 4(Computationally Binding Commitment). A commitment scheme Com = (KG*;*CM) is computationally binding if for any PPT adversary A, the following probability is negligible:

$$ \Pr \left[ \begin{array}{c c} m \neq m ^ {} & \mathrm {c k} \leftarrow \mathrm {K G} \left(1 ^ {\lambda}\right) \ \wedge \mathrm {C M} (\mathrm {c k}; m) = \mathrm {C M} (\mathrm {c k}; m ^ {}) = C & \left| (C; m, m ^ {*}) \leftarrow \mathcal {A} (\mathrm {c k}) \right| \end{array} \right] $$

Hiding Denition. A commitment can be hiding in the sense that it does not reveal the secret value that was committed.

Denition 5(Statistically Hiding Commitment). A commitment scheme Com = (KG*;CM) is statistically hiding if it is statistically hard, for any PPT adversary A = (A₀; A₁), to rst generate two messages A₀*(ck)! m₀;m₁ 2 M_ck such that A₁ can distinguish between their corresponding commitments C₀ and C₁ where C₀ $ CM(ck; m₀) and C₁ $ CM(ck; m₁). 2 3

$$ {\mathsf{C o m}}=({\mathsf{K G}},{\mathsf{C M}}) $$

$$ \mathcal{A}=(\mathcal{A}{0},\mathcal{A}{1}) $$

$$ \ {0}(\mathsf{c k})\to m{0},m_{1}\in M_{\mathsf{c k}} $$

$$ \mathcal{A}_{1} $$

$$ C_{0} $$

$$ C_{0}{\leftarrow}\mathsf{S M}(\mathsf{c k};m_{0}) $$

$$ C_{1} $$

$$ C_{1}{\leftarrow}\mathsf{s M}(\mathsf{c k};m_{1}) $$

$$ \operatorname*{P r}[b=b^{\prime}|\begin{array}{c}c{\ \mathsf{c k}\leftarrow\mathsf{K G}(1^{\lambda})}\ {(m_{0},m_{1})\leftarrow\mathsf{A}{0}(\mathsf{c k})}\ {m,1{\ }\leftarrow{0,1},\ C_{b}\leftarrow\ \mathsf{C M}(\mathsf{c k},m_{b})}\ {b^{\prime}\leftarrow\mathcal{A}{1}(\mathsf{c k},c{b})}\ \end{array}]=\mathsf{n e g l}(\lambda). $$

A.3 Polynomial Commitments

Polynomial commitments (PCs) rst introduced by [KZG10] are commitments d for the message space F [X], the ring of polynomials in X with maximum degree d 2 N and coecients in the eld F = Z_p, that support an interactive argument of knowledge (KG*;Open;*Check) for proving the correct evaluation of a committed polynomial at a given point without revealing any other information about the committed polynomial.

$$ \mathbb{F}^{\leq d}[X]. $$

$$ d\in\mathbb{N} $$

$$ \mathbb{F}=\mathbb{Z}_{p}, $$

A polynomial commitment scheme over a eld family F consists in 4 algorithms PC = (KG*;CM;Open;*Check) dened as follows:

$$ \mathcal{F} $$

$$ P C=G,C M,O M e n,C h e c k) $$

KG(1*;d*)! (ck*;vk): given a security parameter xing a eld F family and a maximal degree d samples a group description gk containing a description of a eld F 2F, and commitment and verication keys (ck;*vk). We implicitly assume ck and vk each contain gk.

$$ {\mathsf{K G}}(1^{\lambda},d)\to({\mathsf{c k}},{\mathsf{v k}}) $$

$$ {\mathcal{F}}_{\lambda} $$

$$ \mathbb{F}\in\mathcal{F}_{\lambda} $$

$$ \ {mathfrak g g k} $$

d CM(ck;f (X))! C: given ck and a polynomial f (X) 2 F [X] outputs a commitment C.

$$ {\mathsf{C M}}({\mathsf{c k}};f(X))\to C; $$

$$ f(X)\in\mathbb{F}^{\leq d}[X] $$

Open(ck; C;x;y; f (X))! : given a commitment C, an evaluation point x, a value y and the polynomial f (X) 2 F[X], it output a prove for the relation: 8 9

$$ (\mathsf{c k};,,x,y;f(X))\to\pi! $$

$$ C, $$

$$ x, $$

$$ f(X)\in\mathbb{F}[X] $$

$$ \pi $$

$$ \mathcal {R} _ {\mathrm {k z g}} := \left{(\mathrm {c k}, C, x, y; f (X)): \begin{array}{l l} C = \mathrm {C M} (\mathrm {c k}; f (X)) \ \wedge \deg (f (X)) \leq d \ \wedge y = f (x) \end{array} \right} $$

Check(vk*;C;x;y;)!* 1*=*0: Outputs 1 if the proof veries and 0 if is not a valid proof for the opening (C;x;y).

$$ \cdot({mathsf k v},C,x,y,\pi)\to1/0: $$

$$ (C,x,y) $$

A polynomial commitment satisfy an extractable version of binding stated as follows:

Denition 6(Computational Knowledge Binding). For every PPT ad- versary A that produces a valid proof for statement C;x;y, i.e. such that Check(vk*;C;x;y;) = 1, there is an extractor* Ext_Athat is able to output a pre- image polynomial f(X) with overwhelming probability:

$$ C,x,y, $$

$$ \mathsf{e c k}(\mathsf{v k},C,x,y,\pi)=1 $$

$$ \mathsf{E x t}_{\mathcal{A}} $$

$$ f(X) $$

$$ \operatorname*{P r}\left[\begin{matrix}{{mathsf{C h e c k}}(\mathsf{v k},C,x,y,\pi)=1}&{{mathsf{c k}}\leftarrow{\mathsf{K G}}(1^{\lambda},d)}\ {\wedge C={\mathsf{C M}}(\mathsf{c k};f(X))}&{(C,x,y,\pi;f(X))\leftarrow({\mathcal{A}}\Vert{\mathsf{E x t}}_{\mathcal{A}})(\mathsf{c k})}\ \end{matrix}\right]=1{\mathsf{-}}{mathsf\mathsf n{g l l}}(\lambda). $$

A.4 KZG Polynomial Commitment

We describe the KZG Polynomial Commitment from [KZG10] which allows to check correctness of evaluation openings.

We recall the scheme KZG*:* PC = (KZG*:* KG*;KZG:* CM*;KZG:* Open*;KZG:* Check) dened over bilinear groups gk = (p; G₁*;G₂;* G_T) with G₁ = hgi; G₂ = hhi:

$$ \mathsf{K Z G.P C}=(\mathsf{K Z G.K G,K Z G.C M,K Z G.O p} $$

$$ \mathfrak{g k}=(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T}) $$

$$ \mathbb{G}{1}=\langle g\rangle,\mathbb{G}{2}=\langle h\rangle $$

in KZG*:* KG(1*;n*)! (ck*;vkh): Set keys ck^g= fg gⁱ=01;*vkh= h. P

$$ \mathsf{K Z G}.\mathsf{K G}(1^{\lambda},n)\to(\mathsf{c k},\mathsf{v k}_{h}) $$

$$ {\mathsf{c k}}{g}=\ {g^{\alpha^{i}}}{i=0}^{n-1},\mathsf{v k}_{h}=h^{\alpha} $$

n 1Qn 1i i fi KZG*:* CM(ck_g; f (X))! C_f: For f (X) =_i=0f_iX, computes C_f=_i=0g = ^f ₍₎ g.

$$ \textstyle f(X)=\sum_{i=0}^{n-1}f_{i}X^{i} $$

$$ \mathrm {K Z G . C M} \left(\mathrm {c k} _ {g}; f (X)\right) \rightarrow C _ {f}: $$

$$ g^{f(\alpha)} $$

$$ C_{f}=\prod_{i=0}^{n-1}g^{f_{i}\alpha^{i}}= $$

KZG*:* Open(ck_g; C_f;x;y; f (X))! : For an evaluation point x, a value y, compute the quotient polynomial

$$ \operatorname {O p e n} \left(\mathrm {c k} _ {g}; C _ {f}, x, y; f (X)\right) \rightarrow \pi $$

$$ x, $$

$$ y, $$

$$ q(X)={\frac{f(X)-y}{X-x}} $$

and output prove := C_q= KZG*:* CM(ck_g; q(X)). KZG*:* Check(vk_h= h;C_f;x;y;)! 1*=*0: Check if

$$ \ .\mathsf{C h e c k}(\mathsf{v k}{h}=h^{\alpha},C{f},x,y,\pi)\to1/0\mathrm{}:\:\mathrm{C h C c k~i i} $$

$$ e \left(C _ {f} \cdot g ^ {- y}, h\right) = e \left(C _ {q}, \mathrm {v k} _ {h} \cdot h ^ {- x}\right). $$

The KZG*:* PC scheme works similarly for a pair of keys of the form ck^h= in fh g_i=01*;*vk_g= g, by just swapping the values in the nal pairing equation check to match the correct basis.

$$ {mathsf\mathsf c{k}}_{h}\ = $$

$$ {h^{\alpha^{\imath}}}{i=0}^{n-1},\mathsf{v k}{g},=,g^{\alpha} $$

B Assumptions in GGM

B.1 ASSGP Assumption in GGM

Assumption 4 (ASSGP) The (q;m)-Auxiliary Structured Single Group Pair- ing assumption holds for the bilinear group generator G if for all PPT ad- versaries A we have, on the probability space gk = (p; G₁*;G₂;* G_T) G (1), g $ G₁*;h* $ G₂ and a;b $ Z_pthe following holds: 2 3

$$ T h e;(q,m) $$

$$ {\mathfrak{g k}}=(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T})\leftarrow{mathcal{G}}(1^{\lambda}) $$

$$ g \leftarrow $ \mathbb {G} _ {1}, h \leftarrow $ \mathbb {G} _ {2} $$

$$ a,b\gets\sharp\mathbb{D}_{p} $$

$$ \operatorname*{P r}\left[\begin{matrix}{\mathbf{A}\neq\mathbf{1}{\mathbb{G}{1}}}\ {\wedge;\prod_{i=0}^{q-1}e(A_{i},h^{a^{i}})=1_{\mathbb{G}{T}}}\ {\wedge;\prod{i=0}^{q-1}e(A_{i},h^{b^{i}})=1_{\mathbb{G}{T}}}\ \end{matrix}\right]\left|\begin{matrix}{g\leftarrow\mathtt{s}\mathbb{G}{1},h\leftarrow\mathtt{s}\mathbb{G}{2},a,b\leftarrow\mathtt{s}\mathbb{Z}{T}}\ {\sigma\leftarrow[g^{a},g^{b},h^{a},h^{b}{}^{b}]^{m=1}}\ {\mathsf{a}\mathtt{w}\leftarrow[g^{a},g^{b},h^{b},h^{b^{i}},h^{b}]_{m=2q}^{m=1}}\ {\mathsf{A}\leftarrow\mathtt{A}(\mathtt{g}(\mathtt{k},\sigma,\mathtt{a}\mathtt{a}u\ )}\ \end{matrix}\right]=\mathsf{n e g l}(\lambda) $$

We can similarly dene the dual assumption, by swapping G₁ and G₂ in the denition above.

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{2} $$

Lemma 3. The (q;m)-ASSGP assumption holds in the generic group model.

Proof. Suppose A is an adversary that on input (gk*;;* aux), outputs (A₀;:::;A^{q 1}) 2 qQq 1i Qq 1i a b G₁ such thati=0e(Ai*;h*) = 1GT_andi=0e(Ai;h) = 1GT. Then its GGM Pm j j extractor outputsi(X;Y) =j=0(xjX + yjY + cj) for 0 i < q then we have:

$$ (A_{0},\ldots,A_{q-1})\in $$

$$ \prod_{i=0}^{q-1}e(A_{i},h^{a^{i}})=1_{\mathbb{G}_{T}} $$

$$ \mathbb{G}_{1}^{q} $$

$$ \prod_{i=0}^{q-1}e(A_{i},h^{b^{i}})=1_{\mathbb{G}_{T}} $$

$$ \textstyle\ \ alpha{}{i}(X,Y){\ =\ }\sum{j=0}^{m}(x_{j}X^{j}+y_{j}Y^{j}+c_{j}) $$

$$ 0\leq i<q $$

$$ \alpha_{0}(X,Y)+X\alpha_{1}(X,Y)+X^{2}\alpha_{2}(X,Y)+\cdots+X^{q-1}\alpha_{q-1}(X,Y)=0 $$

(1)

$$ \alpha_{0}(X,Y)+Y\alpha_{1}(X,Y)+Y^{2}\alpha_{2}(X,Y)+\cdots+Y^{q-1}\alpha_{q-1}(X,Y)=0 $$

(2)

Then we have:

$$ \alpha_{0}(X,Y)=-X\alpha_{1}(X,Y)-X^{2}\alpha_{2}(X,Y)-\cdots-X^{q-1}\alpha_{q-1}(X,Y) $$

(3)

$$ \alpha_{0}(X,Y)=-Y\alpha_{1}(X,Y)-Y^{2}\alpha_{2}(X,Y)-\cdots-Y^{q-1}\alpha_{q-1}(X,Y) $$

(4)

If we substract (4) and (3) we got

$$ 0=(X-Y)\alpha_{1}(X,Y)+\cdots+(X^{q-1}-Y^{q-1})\alpha_{q-1}(X,Y) $$

(5)

$$ -(X{-}Y)\alpha_{1}(X,Y)=(X^{2}{-}Y^{2})\alpha_{2}(X,Y){+}\cdots{+}(X^{q-1}-Y^{q-1})\alpha_{q-1}(X,Y) $$

(6)

Now we can divide by (X Y) and obtain:

$$ \begin{aligned}{-\alpha_{1}(X,Y)=}&{{}(X+Y)\alpha_{2}(X,Y)+(X^{2}+X Y+Y^{2})\alpha_{3}(X,Y)+\cdots+}\ {}&{{}+(X^{q-2}+Y X^{q-3}+\cdots+Y^{q-3}X+Y^{q-2})\alpha_{q-1}(X,Y)}\ \end{aligned} $$

(7)

Substitute the expression of₁(X;Y) in equation (3) and remark that all i Xⁱ(X;Y) terms are vanishing:

$$ -\alpha_{1}(X,Y) $$

$$ X^{i}\alpha_{i}(X,Y) $$

$$ \alpha_{0}(X,Y)=X Y[\alpha_{2}(X,Y)+(X+Y)\alpha_{3}(X,Y)+\cdots+(X^{q-3}+\cdots+Y^{q-3})\alpha_{q-1}(X,Y)] $$

(8)

This implies that either₀(X;Y) is a multiple of XY or₀(X;Y) = 0. By the GGM assumption, we have that₀(X;Y) = 0. We continue by replacing₀(X;Y) = 0 in equation (8):

$$ \alpha_{0}(X,Y) $$

$$ \alpha_{0}(X,Y)=0 $$

$$ \alpha_{0}(X,Y)=0 $$

$$ \alpha_{0}(X,Y)=0 $$

$$ \begin{aligned}{}&{{}0=\alpha_{2}(X,Y)+\cdots+(X^{q-3}+X^{q-4}Y+\cdots+Y^{q-3})\alpha_{q-1}(X,Y)}\ {}&{{}-\alpha_{2}(X,Y)=(X+Y)\alpha_{3}(X,Y)+\cdots+(X^{q-3}+\cdots+Y^{q-3})\alpha_{q-1}(X,Y)}\ \end{aligned} $$

(9)

Substitute the expression of₂(X;Y) in equation (4) and remark that all i Yⁱ(X;Y) terms are vanishing:

$$ -\alpha_{2}(X,Y) $$

$$ Y^{i}\alpha_{i}(X,Y) $$

$$ \begin{aligned}{0=-Y}&{{}\alpha_{1}(X,Y)-Y^{2}[(X+Y)\alpha_{3}(X,Y)+\cdots+(X^{q-3}+X^{q-4}Y+}\ {}&{{}\cdots+Y^{q-3})\alpha_{q-1}(X,Y)]-Y^{3}\alpha_{3}(X,Y)-\cdots-Y^{q-1}\alpha_{q-1}(X,Y)}\ \end{aligned} $$

(10)

$$ \begin{aligned}{Y\alpha_{1}(X,Y)}&{{}=Y^{2}X\alpha_{3}(X,Y)\cdots+(X^{q-3}Y^{2}\cdots+X Y^{q-2})\alpha_{q-1}(X,Y)}\ {Y\alpha_{1}(X,Y)}&{{}=Y^{2}X[\alpha_{3}(X,Y)\cdots+(X^{q-4}\cdots+Y^{q-4})\alpha_{q-1}(X,Y)]}\ \end{aligned} $$

(11)

This implies that either₁(X;Y) is a multiple of XY or₁(X;Y) = 0.

$$ \alpha_{1}(X,Y) $$

$$ \alpha_{1}(X,Y)=0 $$

By the GGM assumption, we have that₁(X;Y) = 0.

$$ \alpha_{1}(X,Y)=0 $$

We continue by replacing₁(X;Y) = 0 in equation (11):

$$ \alpha_{1}(X,Y)=0 $$

$$ \begin{aligned}{0=}&{{}\alpha_{3}(X,Y)+\dots(X^{q-4}+X^{q-5}Y\dots+Y^{q-4})\alpha_{q-1}(X,Y)}\ {-\alpha_{3}(X,Y)=}&{{}\ (X^{2}+X Y+Y^{2})\alpha_{4}(X,Y)+\dots}\ \end{aligned} $$

(12)

And so on... till we show that_i(X;Y) = 0 8i = 0 :::q 1. We conclude that the adversarly produced vector (A₀;:::;A_{q 1}) = 1_G1.

$$ \alpha_{i}(X,Y)=0;;\forall i=\ 0,,\ldots,q-1 $$

$$ (left_00,ldots A{}{q-1})=1{\mathbb{G}_{1}} $$

B.2 ASDGP Assumption in GGM

Assumption 5 (ASDGP) The (q;m)-ASDGP assumption holds for the bilin- ear group generator G if for all PPT adversaries A we have, on the probability space gk = (p; G₁*;G₂;* G_T) G (1), g $ G₁*;h* $ G₂ and a;b $ Z_pthe fol- lowing probability is negligible in :

$$ T e\left(q,m\right)\ \ A S D G P $$

$$ \mathsf{g k}:=:(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}{T}):\leftarrow:\mathcal{G}(1^{\lambda}),;g\leftarrow:{\tt s}\mathbb{G}{1},h\leftarrow:{\tt s}\mathbb{G}_{2} $$

$$ \Pr \left[ \begin{array}{c c} \left(\mathbf {A} \neq 1 _ {\mathbb {G} _ {1}} \vee \mathbf {B} \neq 1 _ {\mathbb {G} _ {2}}\right) \wedge \ \prod_ {i = 0} ^ {q - 1} e \left(A _ {i}, h ^ {a ^ {i}}\right) \prod_ {i = q} ^ {2 q - 1} e \left(g ^ {a ^ {i}}, B _ {i}\right) = 1 _ {\mathbb {G} _ {T}} \ \wedge \ \prod_ {i = 0} ^ {q - 1} e \left(A _ {i}, h ^ {b ^ {i}}\right) \prod_ {i = q} ^ {2 q - 1} e \left(g ^ {b ^ {i}}, B _ {i}\right) = 1 _ {\mathbb {G} _ {T}} \end{array} \right| \begin{array}{l l} g \leftarrow $ \mathbb {G} _ {1}, h \leftarrow $ \mathbb {G} _ {2}, a, b \leftarrow $ \mathbb {Z} _ {p} \ \sigma = \left(g ^ {a ^ {i}}, g ^ {b ^ {i}}, h ^ {a ^ {i}}, h ^ {b ^ {i}}\right) \ \mathrm {a u x} = \left(g ^ {a ^ {i}}, g ^ {b ^ {i}}, h ^ {a ^ {i}}, h ^ {b ^ {i}}\right) _ {2 q} ^ {m} \ (\mathbf {A}, \mathbf {B}) \leftarrow \mathcal {A} (\mathrm {g k}, \sigma , \mathrm {a u x}) \end{array} $$

Lemma 4. The (q;m)-ASDGP assumption holds in the generic group model.

Proof. Suppose A is an adversary that on input (gk*;;* aux), outputs A = (A₀; :::;A_{q 1}) and B = (B₀;:::;B_{q 1}) such that:

$$ (\mathsf{g k},\sigma,\mathsf{a u x}) $$

$$ \mathbf{A}=(A_{0} $$

$$ \ldots,A_{q-1}) $$

$$ \mathbf{B}=(B_{0},\ldots,B_{q-1}) $$

$$ \prod_ {i = 0} ^ {q - 1} e \left(A _ {i}, h ^ {a ^ {i}}\right) \prod_ {i = q} ^ {2 q - 1} e \left(g ^ {a ^ {i}}, B _ {i}\right) = 1 _ {\mathbb {G} _ {T}} \text {a n d} \prod_ {i = 0} ^ {q - 1} e \left(A _ {i}, h ^ {b ^ {i}}\right) \prod_ {i = q} ^ {2 q - 1} e \left(g ^ {b ^ {i}}, B _ {i}\right) = 1 _ {\mathbb {G} _ {T}}. $$

P^m j j Then its GGM extractor outputsi(X;Y) =j=0(xjX + y^jY + c^j) and Pm j j i(X;Y) =j=0(xjX + yjY + cj) for 0 i < q such that:

$$ \alpha_{i}(X,Y);=;\textstyle\sum_{j=0}^{m}(x_{j}X^{j}:+:y_{j}Y^{j}:+:c_{j}) $$

$$ \textstyle\beta_{i}(X,Y)=\sum_{j=0}^{m}(x_{j}X^{j}+y_{j}Y^{j}+c_{j}) $$

$$ 0\leq i<q $$

$$ \begin{aligned}{\alpha_{0}(X,Y)+X\alpha_{1}(X,Y)+}&{{}\cdots+X^{q-1}\alpha_{q-1}(X,Y)+}\ {}&{{}\ X^{q}\beta_{0}(X,Y)+\cdots+X^{2q-1}\beta_{q-1}(X,Y)=0}\ \end{aligned} $$

(13)

$$ \begin{array}{l} \alpha_ {0} (X, Y) + Y \alpha_ {1} (X, Y) + \dots + Y ^ {q - 1} \alpha_ {q - 1} (X, Y) + \ + Y ^ {q} \beta_ {0} (X, Y) + \dots + Y ^ {2 q - 1} \beta_ {q - 1} (X, Y) = 0 \ \end{array} $$

(14)

By substracting (14) and (13) we got

$$ 0=(X{-}Y)\alpha_{1}(X,Y){+}cdots(X^{q-1}-Y^{q-1})\alpha_{q-1}(X,{)}+(X^{q}-Y^{q})\beta_{q}(X,{)}+\ldots $$

(15)

Now we can factor (X Y) and then divide by it and obtain:

$$ \begin{aligned}{-\alpha_{1}(X,Y)=}&{{}(X+Y)\alpha_{2}(X,Y)+(X^{2}+X Y+Y^{2})\alpha_{3}(X,Y)+\cdots+}\ {}&{{}+(X^{2q-2}+Y X^{2q-3}+\cdots+Y^{2q-3}X+Y^{2q-2})\beta_{2q-1}(X,Y)\ \ (16)}\ \end{aligned} $$

i q+i Substitute₁(X;Y) in equation (13) and remark that all Xⁱ(X;Y);X^q+i(X;Y) terms are vanishing: 2 0 1 0 1 3

$$ -\alpha_{1}(X,Y) $$

$$ X^{i}\alpha_{i}(X,Y),X^{q+i}\beta_{q+i}(X,Y) $$

$$ \begin{aligned}{\alpha_{0}(X,Y)}&{{}=X\left[\sum_{j=2}^{q-1}\left(\sum_{j=0}^{i-1}X^{i-j-1}Y^{j}\right)\alpha_{i}(X,Y)+\sum_{l=q}^{2q-1}\left(\sum_{j=0}^{i-1}X^{i-j-1}Y^{j}\right)\beta_{i}(X,Y)\right]-}\ {}&{{}-\sum_{i=2}^{q-1}X^{i}\alpha_{i}(X,Y)-\sum_{i=q}^{2q-1}X^{i}\beta_{i}(X,Y)}\ \end{aligned} $$

$$ \alpha_{0}(X,Y)=X\left[\sum_{i=2}^{q-1}\left(\sum_{j=1}^{i-1}X^{i-j-1}Y^{j}\right)\alpha_{i}(X,Y)+\sum_{i=q}^{2q-1}\left(\sum_{j=1}^{i-1}X^{i-j-1}Y^{j}\right)\beta_{i}(X,Y)\right] $$

$$ \alpha_{0}(X,Y)=X Y\left[\sum_{i=2}^{q-1}\left(\sum_{j=1}^{i-1}X^{i-j-1}Y^{j-1}\right)\alpha_{i}(X,Y)+\sum_{i=q}^{2q-1}\left(\sum_{j=1}^{i-1}X^{i-j-1}Y^{j-1}\right)\beta_{i}(X,Y)\right] $$

(17)

This implies that either₀(X;Y) is a multiple of XY or₀(X;Y) = 0.

$$ \alpha_{0}(X,Y) $$

$$ \alpha_{0}(X,Y)=0 $$

By the GGM assumption, we have that₀(X;Y) = 0.

$$ \alpha_{0}(X,Y)=0 $$

We continue by replacing₀(X;Y) = 0 in equation (17): 0 1 0

$$ \alpha_{0}(X,Y)=0 $$

$$ -\alpha_{2}(X,Y)=\sum_{i=3}^{q-1}\left(\sum_{j=1}^{i-1}X^{i-j-1}Y^{j-1}\right)\alpha_{i}(X,Y){\displaystyle+\sum_{i=q}^{2g-1}\left(\sum_{j=1}^{i-1}X^{i-j-1}Y^{j-1}\right)\beta_{i}(X,Y)}. $$

(18)

Substitute the expression of₂(X;Y) in equation (13) or (14) and remark i i i i that all terms Xⁱ(X;Y);X_i(X;Y) (respectively Yⁱ(X;Y);Y_i(X;Y)) terms are vanishing.

$$ -\alpha_{2}(X,Y) $$

$$ X^{i}\alpha_{i}(X,Y),X^{i}\beta_{i}(X,Y) $$

$$ Y^{i}\alpha_{i}(X,Y),Y^{i}\beta_{i}(X,Y), $$

And so on till we show that_i(X;Y) = 0 8i = 0 :::q 1 and_i(X;Y) = 0 8i = q::: 2q 1.

$$ \alpha_{i}(X,Y)=0;;\forall i=0\ldots,q-1 $$

$$ \beta_{i}(X,Y)= $$

$$ 0;\forall i=q\ldots2q-1 $$

We conclude that the adversarly produced vectors (A₀;:::;A_{q 1})=1_G1; (B₀;:::;B_{q 1}) = 1_G2.

$$ \left(A_{0},\ldots,A_{q-1}\right)=1_{\mathbb{G}_{1}} $$

$$ (B_{0},\ldots,B_{q-1})=1_{\mathbb{G}_{2}} $$

C Groth16 Scheme

Let C be an arithmetic circuit over Z_p, with m wires and d multiplication gates. Groth16 scheme proves circuit satisability, using a Quadratic Arithmetic Program (QAP) characterisation. Briey, a QAP as introduced by [GGPR13] is translating a circuit into an equivalent arithmetic relation that holds only if the circuit has a solution.

$$ \mathbb{Z}_{p}. $$

Groth.Setup(1; R) ;;; $ Z_p; s $ Z_p; n vj(s)+wj(s)+yj(s) otn vj(s)+wj(s)+yj(s) o sid crs = QAP*;g;g;g ; fg* gi=01; g; g; j=0 j>t nsit(s)o d 2i s d g;h;h*;h ; fh* gi=01 i=0 n vj(s)+wj(s)+yj(s) ot vk := P = g;Q = h; Sj = g;H = h;D = h j=0 td = (s;;;;) return (crs*;* td) Groth.Prove(crs;u;w) Groth.Verify(vk*;u;) u = (a₁;:::;a^t); a₀* = 1 = (A;B;C) P_ti w = (a_t+1;:::;a_m) v_io(x) = aⁱvⁱ(x) =0 P_m v(x) = aj vj (x)_{t j=0} wio(x) = Pi=0aiwi(x) P vmid(x) = aj vj (x) _t j2Imidyio(x) = P aiyi(x) Pi=0 m w(x) =j=0aj wj (x) v (s) + w (s) + y (s) io io io P fio = wmid(x) =j2Imidaj wj (x) P_m y(x) = aj yj (x) Check j=0 P fio y_mid(x) =_j2Imida_j y_j (x) e(A;B) = e(g;h) e(g;h) e(C;h) (v(x)w(x) y(x)) h(x) = t(x) vmid(s) + wmid(s) + ymid(s) fmid= Groth.Sim(td*;u*) r;u ^$ Z^p a;b ^$ Z_p a = + v(s) + r; b = + w(s) + u ab vio(s) + wio(s) + yio(s) _t(s)h(s)c = c = f_mid+ + ua + rb ur a b c a b c return ( = (A = g;B = h;C = g)) return ( = (A = g;B = h ;C = g))

$$ \begin{aligned}{}&{{}\mathsf{c r s}=\Big(\mathsf{Q A P},g^{\alpha},g^{\beta},g^{\delta},{g^{s^{i}}}{i=0}^{d-1},\ \Big{g^{\frac{\beta w{j}(s)+\alpha w_{j}(s)+y_{j}(s)}{\gamma}}\Big}{j=0}^{t},\Big{g^{\frac{\beta w{j}(s)+\alpha w_{j}(s)+y_{j}(s)}{\delta}}\Big}{j>t},}\ {}&{{}\qquad\qquad\Big{g^{\frac{beta({s})}{\delta}}\Big}{i=0}^{d-2},h^{\beta},h^{\gamma},h^{\delta},{h^{s^{i}}}_{i=0}^{d-1}\Big)}\ \end{aligned} $$

$$ \mathsf{v k}:=\big(P=g^{\alpha},Q=h^{\beta},\ \big{S_{j}=g^{\frac{\beta v_{j}(s)+\alpha w_{j}(s)+y_{j}(s)}{\gamma}}\big}_{j=0}^{\iota},H=h^{\gamma},D=h^{\delta}\big) $$

$$ \mathsf{t d}=(s,\alpha,\beta,\gamma,\delta) $$

$$ \pi=(A,B,C) $$

$$ u=\big(a_{1},\ldots,a_{t}\big),\ a_{0}=1 $$

$$ w=\left(a_{t+1},\ldots,a_{m}\right) $$

$$ v_{i o}(x)=\sum_{i=0}^{t}a_{i}v_{i}(x) $$

$$ v(x)=\sum_{j=0}^{m}a_{j}v_{j}\big(x\big) $$

$$ w_{i o}(x)=\sum_{i=0}^{t}a_{i}w_{i}(x) $$

$$ v _ {m i d} (x) = \sum_ {j \in I _ {m i d}} a _ {j} v _ {j} (x) $$

$$ w(x)=\sum_{j=0}^{m}a_{j}w_{j}(x) $$

$$ y_{i o}(x)=\sum_{i=0}^{t}a_{i}y_{i}(x) $$

$$ w _ {m i d} (x) = \sum_ {j \in I _ {m i d}} a _ {j} w _ {j} (x) $$

$$ f_{i o}=\frac{\beta v_{i o}(s)+\alpha w_{i o}(s)+y_{i o}(s)}{\gamma} $$

$$ y(x)=\sum_{j=0}^{m}a_{j}y_{j}(x) $$

$$ y _ {m i d} (x) = \sum_ {j \in I _ {m i d}} a _ {j} y _ {j} (x) $$

$$ e (A, B) = e \left(g ^ {\alpha}, h ^ {\beta}\right) \cdot e \left(g ^ {f _ {i o}}, h ^ {\gamma}\right) \cdot e \left(C, h ^ {\delta}\right) $$

$$ h(x)=\frac{(v(x)w(x)-y(x))}{t(x)} $$

$$ f_{m i d}=\frac{\beta v_{m i d}(s)+\alpha w_{m i d}(s)+y_{m i d}(s)}{\delta} $$

$$ a=\alpha+v(s)+r\delta,\qquad b=\beta+w(s)+u\delta $$

$$ c=f_{m i d}+\frac{t(s)h(s)}{\delta}+u a+r b-u r\delta $$

$$ \mathbf {r e t u r n} \left(\pi = \left(A = g ^ {a}, B = h ^ {b}, C = g ^ {c}\right)\right) $$

$$ (\pi = \left(A = g ^ {a}, B = h ^ {b}, C = g ^ {c}\right)) $$

Fig. 3. Groth16 Construction from QAP.

m Let Q = (t(x); fv^k(x);w^k(x);y^k(x)g_k⁼⁰) be a Quadratic Arithmetic Program (QAP) which computes C. We denote by I_io= f1*;* 2*;:::tg* the indices corresponding to the public input and public output values of the circuit wires and by I_mid= ft + 1*;:::mg*, the wire indices corresponding to the private input and non-input, non-output intermediate values (for the witness).

$$ Q=(t(x),{v_{k}(x),w_{k}(x),y_{k}(x)}_{k=0}^{m}) $$

$$ I_{i o},=,{1,2,\ldots t} $$

$$ I_{m i d}=\left{t!+!1,\ldots m\right} $$

We describe Groth = (Setup*;Prove;*Verify) scheme in [Gro16] that consists in 3 algorithms as per Figure 3.

D Building Blocks for Aggregation

SRS. We need elements from two independent compatible Groth16 SRS:

{ Common bilinear group description for both SRS: gk = (p; G₁*;G₂;* G_T)

$$ \ {mathfrak z!{\mathsf{k}}}=(p,{\mathbb{G}}{1},{\mathbb{G}}{2},{\mathbb{G}}_{T}) $$

{ Common group generators for both SRS: g 2 G₁*;h 2* G₂

$$ g\in\mathbb{G}{1},h\in\mathbb{G}{2} $$

{ First SRS with random evaluation point a 2 Z_pfor:

$$ a\in\mathbb{Z}_{p} $$

$$ \mathbf{v}{1}={\big(}h,h^{a},\ldots,h^{a^{n-1}}{\big)}{\mathrm{a n d}}\mathbf{w}{1}={\big(}g^{a^{n}},\ldots,g^{a^{2n-1}}{\big)} $$

{ Second SRS with random evaluation point b 2 Z_pfor:

$$ b\in\mathbb{Z}_{p} $$

$$ \mathbf{v}{2}=(h,h^{b},\ldots,h^{b^{n-1}}){\mathrm{a n d}}\mathbf{w}{2}=(g^{b^{n}},\ldots,g^{b^{2n-1}}) $$

Pair Group Commitments. To instantiate our aggregated scheme, we use two new pairing commitment schemes. These schemes need to satisfy special properties (as discussed in Section 3) and they require structured commitment keys ck_s;ck_dof the form ck_s= (v₁;v₂);ck_d= (v₁;w₁;v₂;w₂). We then commit n n to vectors A 2 G₁; B 2 G₂as follows:

$$ \mathsf{c k}{s}=(\mathbf{v}{1},\mathbf{v}{2}),\mathsf{c k}{d}=(\mathbf{v}{1},\mathbf{w}{1},\mathbf{v}{2},\mathbf{w}{2}) $$

$$ \mathsf{C k}{s},\mathsf{C k}{d} $$

$$ \mathbf{A}\in\mathbb{G}{1}^{n},\mathbf{B}\in\mathbb{G}{2}^{n} $$

1.Single group version CM_s(A) := CM_s(ck_s; A) = (T_A;U_A) where

$$ {mathsf\mathsf C{M}}{s}(\ {mathsf A)):=\mathsf{C M}{s}(\mathsf{C k}{s};{\mathsf{A}})=(T{A},U_{A})} $$

$$ T _ {A} = \mathbf {A} * \mathbf {v} _ {1} = e \left(A _ {0}, h\right) e \left(A _ {1}, h ^ {a}\right) \dots \dots e \left(A _ {n - 1}, h ^ {a ^ {n - 1}}\right) $$

$$ U_{A}=\mathbf{A}*ast\mathbf{v}{2}=e(A{0},h)e(A_{1},h^{b})\ldots e(A_{n-1},h^{b^{n-1}}) $$

2.Double group version CM_d(A*;B) := CM_d(ck_d; A;B) = (T_AB;U*_AB) where

$$ {\mathsf{C M}}{d}({\mathbf{A}},{\mathbf{B}}):={\mathsf{C M}}{d}({\mathsf{c k}}{d};{\mathbf{A}},{\mathbf{B}})=(T{A B},U_{A B}) $$

$$ T_{A B}=(\mathbf{A}\mathbf{v_{1}})(\mathbf{w_{1}}\mathbf{B}),\quad U_{A B}=(\mathbf{A}\mathbf{v_{2}})(\mathbf{w_{2}}\mathbf{B}) $$

IPP Protocols. One of the key building blocks for our aggregation protocol are generalized inner product arguments, called GIPA or IPP protocols. These + protocols, as designed in [BMM 19], enable proving the correctness of a large class of inner products between vectors of group and/or eld elements committed using (possibly distinct) doubly-homomorphic commitment schemes.

For our aggregation protocol, we need to instantiate two specialised cases of IPP { multi-exponentiation inner product (MIPP) and an target inner pairing product (TIPP) { using our new commitment schemes under structured references string, and thus, we obtain logarithmic verier time.

D.1 Relation for MT-IPP

Here we dene the relation proven using the merged MT-IPP argument. This is a conjunction of the two relations MIPP and TIPP:

MIPP Relation. The multiexponentiation product relation:

$$ \begin{array}{l} \mathcal {R} _ {\mathrm {m i p p}} := \left{\left(\left(T _ {C}, U _ {C}\right), Z _ {C}, r; \mathbf {C}, \mathbf {r}\right): Z _ {C} = \mathbf {C} * \mathbf {r} \wedge \right. \ \left(T _ {C}, U _ {C}\right) = \mathrm {C M} _ {s} \left(\mathrm {c k} _ {s}; \mathbf {C}\right) \wedge \mathbf {r} = \left(r ^ {i}\right) _ {i = 0} ^ {n - 1}. \ \end{array} $$

TIPP Relation. The target inner pairing relation:

$$ \begin{aligned}{\mathcal{R}{\mathsf{t i p p}}:={((T{A B},U_{A B})}&{{},Z_{A B},r;\mathbf{A},\mathbf{B}):Z_{A B}=\mathbf{A}*\mathbf{B^{r}}\ \wedge\ }\ {}&{{}(T_{A B},U_{A B})=\mathsf{C M}{d}(\mathbf{c k}{d};\mathbf{A},\mathbf{B})\ \wedge\ \mathbf{r}=(r^{i})_{i=0}^{n-1}},}\ \end{aligned} $$

$$ \text {w h e r e} \left(T _ {A B}, U _ {A B}\right) \in \mathbb {G} _ {T} ^ {2}, Z _ {A B} = \mathbf {A} * \mathbf {B} ^ {\mathbf {r}} \in \mathbb {G} _ {T}, \mathbf {A} \in \mathbb {G} _ {1} ^ {n}, \mathbf {B} \in \mathbb {G} _ {2} ^ {n}, r \in \mathbb {Z} _ {p}. $$

MT-IPP Relation. The merged MT-IPP relation:

$$ \mathcal {R} _ {\mathrm {m t}} := \left{ \begin{array}{c c} \left(\left(T _ {A B}, U _ {A B}\right), \left(T _ {C}, U _ {C}\right)\right), & \left(\mathrm {C M} _ {d} (\mathbf {A}, \mathbf {B}), Z _ {A B}, r; \mathbf {A}, \mathbf {B}\right) \in \mathcal {R} _ {\mathrm {t i p p}} \ Z _ {A B}, Z _ {C}, r; \mathbf {A}, \mathbf {B}, \mathbf {C}) & \wedge \ \left(\mathrm {C M} _ {s} (\mathbf {C}), Z _ {C}, r; \mathbf {C}\right) \in \mathcal {R} _ {\mathrm {m i p p}} \end{array} \right} $$

for vectors A*;* C 2 G₁ and B 2 G₂.

$$ \mathbf{A},\mathbf{C}\in\mathbb{G}_{1} $$

$$ \mathbf{B}\in\mathbb{G}_{2} $$

E Final Commitment Keys

In this section, we will detail one step of the MT-IPP protocol: Checking the correctness of the nal commitment key, obtained after all "split & collapse" steps.

Recall that our scheme MT-IPP achieves logarithmic proof size using a specially structured commitment scheme that allows the prover to use one new challenge x_jin each round of recursion to transform the commitments homomorphically. Because of this, the verier must also perform a linear amount of work in rescaling the commitment keys (ck_s*;*ck_d). To avoid having the verier rescale + the commitment keys, our scheme apply the same trick as [DRZ20, BMM 19]: we do this by outsourcing the work of rescaling the commitment keys to the prover.

$$ x_{j} $$

$$ (\mathsf{c k}{s},\mathsf{c k}{d}) $$

Then what is left is to convince a verier that this rescaling was done correctly just by checking a succinct proof on the nal keys.

Proof for Final Key. In our MT-IPP scheme, the prover will compute the nal 0 0 commitment keys v₁;v₂;w₁;w₂ (the result of many rounds of rescaling/collapsing 0 0 v₁*;v₂;w₁;*w₂ until the end of the loop) and then prove that they are well-formed.

$$ K e y. $$

$$ v_{1},v_{2},w_{1}^{\prime},w_{2}^{\prime} $$

$$ \mathbf{v}{1},\mathbf{v}{2},\mathbf{w}{1}^{\prime},\mathbf{w}{2}^{\prime} $$

This is possible due to the structure in the commitment keys. For ease of presentation, we will show how this proof works for a generic vector v, where 2 n 1 v = (v₁;v₂;:::;v₂‘) = (g;g;g;:::g). The other checks for the keys v₁;v₂ and w₁;w₂ work in an analogously fashion.

$$ \mathbf{v}, $$

$$ \mathbf{v}=(v_{1},v_{2},\ldots,v_{2^{\ell}})=(g,g^{\alpha},g^{\alpha^{2}},\ldots g^{\alpha^{n-1}}) $$

$$ v_{1},v_{2} $$

$$ w_{1},w_{2} $$

Let us rst dene the relation to be proven, i.e. the correctness of the nal commitment key v 2 G₁ given the initial key v: n o

$$ v\in\mathbb{G}_{1} $$

$$ \mathcal {R} _ {\mathrm {c k}} := \left{\left(\mathrm {g k}, v, f (X), \mathrm {c k} _ {g} = \left(\left{g ^ {\alpha^ {i}} \right} _ {i = 0} ^ {2 n - 2}, \mathrm {v k} _ {h} = h ^ {\alpha}\right)\right): v = g ^ {f (\alpha)} \right} $$

The argument for the relation R_ckallows the verier to check well-formedness of the nal structured commitment key. The idea is simple: the nal commitment

$$ \mathcal{R}_{\mathrm{c k}} $$ key v is interpreted as a KZG polynomial commitment that the prover must open at a random point z. The verier produces the challenge point z 2 Z_pand the prover provides a valid KZG opening proof of f (z) for the commitment v. The interaction can be removed using Fiat-Shamir heuristic via a collision-resitant hash to generate the challenge z. The proof of security of such a protocol is given + in [BMM 19] in the algebraic group model. In a nutshell, an algebraic adversary that convinces a verier of incorrect keys can extract a valid 2n-SDH instance by breaking knowledge-binding of KZG*:* PC polynomial commitment scheme.

$$ z\in\mathbb{Z}_{p} $$

$$ f(z) $$

$$ [\mathrm{B M M^{+}19}] $$

We will use a polynomial commitment scheme (Denition A.3) that allows for openings of evaluations on a point and proving correctness of these openings. The concrete scheme is called KZG*:* PC and works for both groups G₁ and G₂ as described in Appendix A.4. The verication requires an evaluation of the corresponding polynomial and four pairing checks.

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{2} $$

Polynomial Formula. We will show now, hot to dene the correct polynomials to be committed under KZG*:* PC scheme in order to show that the nal commitment keys were honestly generated.

Recall the structure of the 4 vectors v₁*;v₂ 2 G₂ and w₁;w₂ 2 G₁ used for the commitment keys ck_s;*ck_d:

$$ \mathbf{v}{1},\mathbf{v}{2}\in\mathbb{G}_{2} $$

$$ \mathbf{w}{1},\mathbf{w}{2}\in\mathbb{G}_{1} $$

$$ \mathsf{c k}{s},\mathsf{c k}{d}. $$

$$ \begin{array}{l} \mathbf {v} _ {1} = \left(h, h ^ {a}, \dots , h ^ {a ^ {n - 1}}\right), \quad \mathbf {w} _ {1} = \left(g ^ {a ^ {n}}, \dots , g ^ {a ^ {2 n - 1}}\right), \quad \mathbf {w} _ {\mathbf {1}} ^ {\prime} := \mathbf {w} _ {1} ^ {\mathbf {r} ^ {- 1}} \ \mathbf {v} _ {2} = \left(h, h ^ {b}, \dots , h ^ {b ^ {n - 1}}\right), \quad \mathbf {w} _ {2} = \left(g ^ {b ^ {n}}, \dots , g ^ {b ^ {2 n - 1}}\right), \quad \mathbf {w} _ {2} ^ {\prime} := \mathbf {w} _ {2} ^ {\mathbf {r} ^ {- 1}} \ \end{array} $$

We will show the formulae for the polynomials the two polynomials f_v(X) 0 0 and f_w(X) that we used in our scheme MT-IPP for v₁;v₂ and for w₁;w₂ are correct.

$$ f_{v}(X) $$

$$ f_{w}(X) $$

$$ v_{1},v_{2} $$

$$ w_{1}^{\prime},w_{2}^{\prime} $$

For ease of presentation, we state and prove the formula for a generic vector 2 2‘ 1 ‘ v = (v₁;v₂;:::;v₂‘) = (g;g;g;:::g) of length n = 2 to which we apply the same rescaling as for the commitment keys ck_s*;ck_d. The specic formulae 0 0 for v₁;v₂;w₁;*w₂ are easy to deduce once we have a formula for v.

$$ {\mathbf v=\ }(v_{1},v_{2},\ldots,v_{2^{\ell}})=(g,g^{\alpha},g^{\alpha^{2}},\ldots g^{\alpha^{2^{\ell}-1}}) $$

$$ n=2^{\ell} $$

$$ \mathsf{c k}{s},\mathsf{c k}{d} $$

$$ \mathbf{v}{1},\mathbf{v}{2},\mathbf{w}{1}^{\prime},\mathbf{w}{2}^{\prime} $$

Consider a challenge x_jfor round j, where the total number of rounds is ‘. Note that at each round j we split the sequence v₁;v₂;:::;v_nin half and we use x_jto rescale rst half and the second half of the vector recursively until we end up with a single value v.

$$ x_{j} $$

$$ j, $$

$$ \ell. $$

$$ v_{1},v_{2},\ldots,v_{n} $$

$$ x_{j} $$

We claim that the formula for some initial key v = (v₁ = g;v₂ = g;:::;v_n= n ¹ g) aⁿd for a vector of challenges x₁ :::x_{‘ 1};x_‘is:

$$ \mathtt{V}=\left(v_{1}=g,v_{2}=g^{\alpha},\ldots,v_{n}=\right. $$

$$ g^{\alpha^{n-1}} $$

$$ x_{1}\ldots x_{\ell-1},x_{\ell} $$

$$ v=g^{\prod_{j=0}^{\ell-1}(1+x_{\ell-j}\alpha^{2^{j}})}. $$

We will prove the general formula by induction:

Step 1. Check the formula for ‘ = 1 (initial commitment key v has two elements v₁;v₂): Q₀2j

$$ v_{1},v_{2}) $$

$$ v=v_{1}v_{2}^{x_{1}}=g^{1+x_{1}\alpha}=g^{\prod_{j=0}^{0}(1+x_{\ell-j}\alpha^{2^{j}})}. $$

Step 2. Suppose the statement is true for ‘ 1. We prove it for ‘.

On the rst round, we have a challenge x₁ and we rescale the commitment ‘ key v which has length n = 2 as follows: x v⁰ = v v;

$$ x_{1} $$

$$ n=2^{\ell} $$

$$ \mathbf{v}^{\prime}=\mathbf{v}{[:2^{\ell-1}]}\circ\mathbf{v}{[2^{\ell-1};]}^{x_{1}}, $$

$$ \mathbf{v}^{\prime}=(\overset{\cdot}{g}\cdot\overset{\cdot}{g}^{\overset{\cdot}cdot{x_{1}\alpha^{2^{\ell-1}}}},\overset{\cdot}{g^{\alpha}}\cdot{^{{x_{1}}\alpha^{2^{\ell-1}+1}}},g^{{\alpha^{2}}}\cdot overset{\cdot}{g^{{x_{1}\alpha^{2^{\ell-1}+2}}}},\dots). $$

2‘ 1 2‘ 1 0 x₁ x₁ We can write this dierently as v =(v₁v₁;:::v₂‘ ¹ v₂^{‘ 1}):

$$ \mathbf{v^{\prime}}\mathbf{=}(v_{1}v_{1}^{x_{1}\alpha^{2^{\ell-1}}},\ldots v_{2^{\ell-1}}v_{2^{\ell-1}}^{x_{1}\alpha^{2^{\ell-1}}}) $$

This gives us a nicely written commitment key after rst round

$$ \mathbf{v}^{\prime}=(v_{1}^{1+x_{1}\alpha^{2^{\ell-1}}},v_{2}^{1+x_{1}\alpha^{2^{\ell-1}}},\ldots v_{2^{\ell-1}}^{1+x_{1}\alpha^{2^{\ell-1}}})=\mathbf{v}{[:2^{\ell-1}]}^{1+x{1}\alpha^{2^{\ell-1}}}. $$

We can apply the induction assumption for step ‘ 1 to v_[:2‘ 1_]which is a ‘ 1 commitment key of length 2. This means the nal key for v is:

$$ \mathbf{V}_{[2^{\ell-1}]} $$

$$ 2^{\ell-1} $$

$$ v=\left(g^{\prod_{j=0}^{\ell-2}\left(1+x_{\ell-j}\alpha^{2^{j}}\right)}\right)^{(1+x_{1}\alpha^{2^{\ell-1}})}=g^{\prod_{j=0}^{\ell-1}(1+x_{\ell-j}\alpha^{2^{j}})}. $$

Remark than in more generality, this can be written as:

$$ v=v_{1}^{\prod_{j=0}^{\ell-1}(1+x_{\ell-j}\alpha^{2^{j}})} $$

n n+1 Therefore, if we start with an initial key w = (w₁ = g;w₂ :::;wⁿ= ^{2n 1} g), the nal key w can be written as:

$$ \mathtt{w}=\ (w_{1}=g^{\alpha^{n}},w_{2}^{\alpha^{n+1}}\ldots,w_{n}= $$

$$ g^{\alpha^{2n-1}}) $$

$$ w=w_{1}^{\prod_{j=0}^{\ell-1}(1+x_{\ell-j}\alpha^{2^{j}})}=g^{\alpha^{n}\prod_{j=0}^{\ell-1}(1+x_{\ell-j}\alpha^{2^{j}})} $$