GENES: An Efficient Recursive zk-SNARK and Its Novel Application in Blockchain

Abstract

The rapid development of blockchain has significantly promoted research on zero-knowledge proofs (ZKPs), especially zero-knowledge succinct noninteractive arguments of knowledge (zk-SNARK). As is well known, protocol proof and verification time, as well as proof size, are the main obstacles that restrict the implementation of ZKPs in practical applications, so they have become the main concerns of researchers in recent years. This work achieves a new recursive zk-SNARK called GENES, which does not have a trusted setup and is secure under the standard discrete logarithm assumption. GENES is designed from the form of the rank-1 constraint system (R1CS) satisfiability problem. Recursive proof composition is achieved by merging multiple R1CS instances, which transforms the verification of numerous proofs into the verification of a single proof. Moreover, multi-helpers amortize proof commitments in this study, significantly reducing the computational pressure and time cost of proof generation. Compared with previous work, GENES effectively improves the proof time and verification time, but at the cost of larger proof sizes. We provide a blockchain Layer-1 scaling solution leveraging GENES to demonstrate its practicality.

1. Introduction

Zero-knowledge proofs (ZKPs), first introduced by Goldwasser et al. [1], are cryptographic protocols that enable a prover to demonstrate the validity of a statement to a verifier without revealing any additional information. With their inherent properties of completeness, soundness, and zero knowledge, ZKPs have found widespread applications in privacy-preserving computation, verifiable computation, and efficient cryptographic protocols [2,3,4,5,6,7]. Over the past decade, the rapid growth of blockchain technology has further driven advancements in ZKP techniques, particularly in the development of zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) [8,9].

zk-SNARKs [10] can offer succinct proofs with sizes independent of the complexity of the statement being proven, making them highly suitable for blockchain applications, where constraints on storage and computational resources demand compact and efficient cryptographic solutions. A typical zk-SNARK construction involves translating the statement into a circuit satisfiability (C-SAT) problem, building information-theoretic proofs, and then using cryptographic compilers to generate succinct non-interactive proofs. These methods are categorized into several types based on their underlying technologies, including quadratic arithmetic programs (QAP) [11,12,13,14], doubly efficient interactive proofs (DEIP) [15,16,17,18], inner product arguments (IPA) [19,20,21], and secure multi-party computation (MPC)-in-the-head [22,23,24].

Despite recent advancements, existing zk-SNARK protocols exhibit notable limitations in efficiency, particularly when applied to large-scale proof statements. A primary constraint arises from the widespread reliance on polynomial-based encodings of constraints, as employed in protocols such as the IPA-based zk-SNARKs by Bünz et al. [20] and subsequent refinements by Bowe et al. [21]. While polynomial encodings provide theoretical soundness, they introduce significant inefficiencies in two key dimensions. First, the computational overhead associated with proof generation and verification increases substantially as the size of the proof statement grows, thereby limiting scalability. Second, polynomial encodings lack a straightforward mechanism to decompose large proof statements into smaller sub-proofs, an essential requirement for enabling efficient recursive or aggregated proof constructions. These limitations hinder the practical applicability of zk-SNARK protocols in blockchain scenarios requiring high scalability and computational efficiency.

Rank-1 Constraint System (R1CS) provides a structured and efficient alternative to address these challenges. R1CS is a common target program [25,26] for high-level programming language compilers with a simple form, and any C-SAT problem can be represented by an R1CS satisfiability problem [16,27]. Its compact representation of constraints not only reduces the computational complexity of proof generation and verification but also facilitates the decomposition of large proof statements. By transitioning from polynomial-based encodings to R1CS, zk-SNARK protocols can overcome existing inefficiencies and enhance their applicability to computationally intensive and large-scale applications.

Motivated by these challenges, this study proposes a novel recursive IPA-based zk-SNARK protocol that addresses the inefficiencies of existing constructions. Unlike traditional approaches, our protocol directly encodes constraints as R1CS instances, a more compact and efficient representation compared to polynomial encodings. Our protocol is built on a new R1CS merging scheme, enabling an efficient recursive composition method. This advancement significantly enhances the practical utility of zk-SNARKs for computationally intensive applications, enabling the extension of zk-SNARKs in blockchain scenarios, such as for layer-1 solutions.

1.1. Contributions

Our starting point is the general construction of an IPA-based ZKP protocol by Bünz et al. [20], which was constructed from polynomials. We propose an efficient recursive zk-SNRAK protocol and apply it to blockchain to improve scalability in this study. The main contributions are as follows:

• We designed the protocol directly from the form of a rank-1 constraint system (R1CS) satisfiability problem (rather than reducing it to polynomial constraints) in bulletproofs, and for the first time in this variant, we propose a recursive zk-SNARK scheme called GENES, which is based on the R1CS merging scheme and without a trusted setup.
• We analyzed its security under the standard discrete logarithm (DLOG) assumption and compared it with bulletproofs and halo to demonstrate its efficiency advantages.
• We propose a novel application of GENES, which can be considered the first Layer-1 scaling solution in blockchain using a zk-SNARK protocol.

1.2. Releted Works

zk-SNARKs. To construct IPA-based zk-SNARKs, Bootle et al. [28] first proposed IPA in 2016 and used it to construct a non-interactive zero-knowledge argument of knowledge (NIZKAoK) with logarithmic-level communication complexity. The prover uses IPA to prove through the method of recursion and looping, which has two public vector commitments, and the inner product of these two commitments is equal to a certain public value. Bünz et al. [20] improved Bootle’s scheme by combining two vector commitments into one commitment and constructing an efficient range proof protocol called bulletproofs. This achieved lower total communication traffic but with linear proof generation and verification time, which is very expensive compared to other protocols. Bowe et al. [21] improved IPA-based schemes in bulletproofs by constructing a single variable polynomial commitment and amortization strategy. They defined a new circle of curves and built the first recursive zk-SNARK without trusted setup and cycles of expensive pairing friendly elliptic curves, which is called halo. A common alternative to building zk-SNARKs from polynomial constraints is building them from R1CS. Recently, Kothapalli et al. [29] constructed a recursive SNARK protocol based on relaxed R1CS, which is simpler and more efficiently achievable. The succinctness of a SNARK implemented through the sum-check protocol can ensure a fast verifier, but to some extent, the verifier may incur high computational costs.

zk-SNARKs for blockchain. Existing ZKP applications for blockchain systems can be broadly divided into two types. One is used to build cryptocurrency and hide the transfer and balance involved in the blockchain ledger through the ZKP protocol, such as Monero [30] based on bulletproofs [20], and Pinocchio coin [31] based on Pinocchio [32]. One is used in layer-2 scaling solutions, such as Polygon [33] based on plonk [34], Zcash [35] based on halo [21], and a new protocol Pianist [36], which has recently been proposed to achieve scalable zkRollups through fully distributed zero knowledge proofs. However, the current ZKP applications do not consider how to achieve layer-1 expansion by improving the scalability of the blockchain itself.

We begin the rest of the paper with useful preliminaries in Section 2, such as R1CS, commitments, IPA, and (zk-)SNARK. In Section 3, we describe our recursive zk-SNARK scheme, including construction methods, complexity, and security analysis. In Section 4, we compare our scheme with previous schemes and demonstrate the advantages of our scheme. In Section 5, we propose a novel application of GENES to enhance the throughput of blockchain systems. Finally, Section 6 concludes this research.

2. Preliminaries

2.1. Rank-1 Constraint System (R1CS)

Definition 1 (R1CS).

An R1CS instance is a tuple $(\mathbb{F},\mathit{A}, \mathit{B}, \mathit{C}, \mathit{i}\mathit{o}, m, n)$, where $\mathit{i}\mathit{o}$ denotes the public input and output vectors, $\mathit{A}, \mathit{B}, \mathit{C}\in {\mathbb{F}}_p^{m\times m}$, $m \ge \left|\mathit{i}\mathit{o}\right|+1$, and n denotes the maximum number of nonzero values in all matrices. The R1CS problem is satisfiable if and only if there is evidence $\mathit{w}\in {\mathbb{F}}_p^{m-( |\mathit{i}\mathit{o}|+1)}$ for an R1CS (instance, witness) pair <$(\mathbb{F},\mathit{A}, \mathit{B}, \mathit{C}, \mathit{i}\mathit{o}, m, n)$, $\mathit{w}$>, such that $\mathit{A}·{(\mathit{i}\mathit{o},1,\mathit{w})}^T\circ \mathit{B}·{(\mathit{i}\mathit{o},1,\mathit{w})}^T=\mathit{C}·{(\mathit{i}\mathit{o},1,\mathit{w})}^T$.

2.2. Commitments

Definition 2 (Commitment [32]).

A (non-interactive) commitment scheme includes three PPT algorithms (Setup, Com, Open) with the following semantics:

• pp ← Setup$\left(1^{\lambda }\right)$: Takes the security parameter $\lambda$ as input, and the Setup algorithm is used to generate the common parameters pp.
• c ← Com_pp$(x; r)$: The Commitment algorithm defines the function mapping $M\times R \to C$, where $M$, $R$, and $C$ denote plaintext space, random number space, and commitment space, respectively. Specifically, for messages $x \in M$ and random numbers $r \in R$, commitment c is generated.
• {0, 1} ← Open_pp$(c, x, r)$: The Open algorithm defines the function mapping $C\times M\times R \to$ 0/1. Specifically, for commitment c, messages $x \in M$, and random numbers $r \in R$, it outputs 0/1, representing successfully opened or not, respectively.

Two basic properties exist for a commitment scheme: hiding and binding. Among them, the hiding commitment refers to the inability of the adversary to obtain the value of m after obtaining commitment c, while binding refers to the fact that a commitment c can only be opened to one value during the Open phase.

2.3. Inner Product Argument (IPA)

Definition 3 (IPA [28]).

Prover P proves to verifier V that for common inputs $G,H\in \mathbb{G}$, ${\mathit{G},\mathit{H}\in \mathbb{G}}^n$ and public scalar $z\in {\mathbb{Z}}_p$, P has $vectors \mathit{a},\mathit{b}$ that satisfy $G=\mathit{a}·\mathit{G}$, $H=\mathit{b}·\mathit{H}$ and $\mathit{a}·\mathit{b}=z$. We denote the statement (Public Input, Witness) below.

$$\left\{\right(\mathit{G},\mathit{H},G,H,z;\mathit{a},\mathit{b}):G=\mathit{a}·\mathit{G}\wedge H=\mathit{b}·\mathit{H}\wedge \mathit{a}·\mathit{b}=z\}$$

Moreover, if commitments $G$ and $H$ are combined into one commitment $P=a·G+b·H$, the above statement can be rewritten as below.

$$\left\{\right(\mathit{G},\mathit{H},G,H,z;\mathit{a},\mathit{b}):P=\mathit{a}·\mathit{G}+\mathit{b}·\mathit{H}\wedge z=\mathit{a}·\mathit{b}\}$$

The core idea of the inner product argument is to reduce the statement for a vector of length n to an equivalent statement for a vector of length n/2 based on the random challenge from V. After the vector is continuously reduced to a scalar, P only needs to send a scalar directly.

2.4. Succinct Noninteractive Argument of Knowledge (SNARK)

Definition 4 (SNARK and zk-SNARK).

Take ($x,w$)$\in \mathcal{R}$, which is a polynomial time-decidable binary relation for an NP language $\mathcal{L}$($\mathcal{R}$) with statement $x$ and witness $w$. A SNARK is a triple of the PPT algorithms (Setup, Prove, Verify), defined as follows:

• $\sigma$ ← Setup$\left(1^{\lambda },\mathcal{R}\right)$: The Setup algorithm takes the unary representation of the safety parameter λ and relationship $\mathcal{R}$ as inputs and generates a common reference string $\sigma$.
• $\pi$ ← Prove$(\mathcal{R},\sigma ,x,w)$: Given relationship $\mathcal{R}$, common reference string $\sigma$, statement $x$ and witness $w$, the Prove algorithm generates proof $\pi$.
• {0, 1} ← Verify$(\mathcal{R},\sigma ,\pi )$: Taking relationship $\mathcal{R}$, common reference string $\sigma$ and proof $\pi$ as input, the Verify algorithm verifies if the proof is correct.

A SNARK should satisfy the following security properties:

• Completeness. For all $x\in \mathcal{L}\left(\mathcal{R}\right)$, if an honest prover generates a proof with valid witness $w$, the verifier will definitely accept it.
• Knowledge Soundness. If any PPT adversary $\mathcal{A}$ can generate valid proof with witness $w$ for $x\notin \mathcal{L}\left(\mathcal{R}\right)$, then a polynomial extractor ${\mathcal{X}}_{\mathcal{A}}$ can extract $w$ and access any state of $\mathcal{A}$, whose probability is negligible.
• Succinctness. The proof size sent by the Prover does not exceed poly($\lambda$)($\left|x\right|+\left|w\right|$).
• A zk-SNARK refers to a SNARK with zero knowledge, which needs to additionally satisfy the following property:
• Zero-knowledge. The Prover can prove the truth of a statement to the Verifier without disclosing any information other than correctness.

2.5. Notations

In this paper, we denote $\mathsf{\lambda }$ as the security parameter and abbreviate probabilistic polynomial time as PPT. $\mathbb{G}$ denotes a cyclic group of prime order p, and ${\mathbb{G}}^{\mathrm{n}}$ is the vector spaces of dimension n over $\mathbb{G}$. Generators of $\mathbb{G}$ are denoted by G, H ∈$\mathbb{G}$. ${\mathbb{Z}}_{\mathrm{p}}$ denotes a ring of integers modulo p, and ${\mathbb{Z}}_{\mathrm{p}}^{\mathrm{m}\times \mathrm{n}}$ is a set of m × n matrices in which the elements are in ${\mathbb{Z}}_{\mathrm{p}}$. We use lowercase bold to denote vectors; that is, $\mathbf{a}\in {\mathbb{Z}}_{\mathrm{p}}^{1\times \mathrm{n}}$ represents a row vector ${(\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{n}})$ with a dimension of n on ${\mathbb{Z}}_{\mathrm{p}}$, where ${\mathbb{Z}}_{\mathrm{p}}^{1\times \mathrm{n}}$ is abbreviated as ${\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}}$ for ease of expression. Uppercase bold denotes matrices; that is, $\mathbf{A}\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}\times \mathrm{m}}$ is a matrix with n rows and m columns. $\mathbf{A}·\mathbf{a}$ denotes the matrix multiplication of matrix A and vector a. $\mathrm{y}\leftarrow \mathrm{A}(\mathrm{x},\mathrm{r})$ denotes the process of algorithm A generating $\mathrm{y}$ with $\mathrm{x}$ as input and $\mathrm{r}$ as random input. ${\mathrm{\varnothing }}_{\mathbf{m}}$ denotes a constraint instance on multiplication gates. $\mathrm{r}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{F}}_{\mathrm{p}}$ denotes the uniform sampling of an element from ${\mathbb{F}}_{\mathrm{p}}$. a $\stackrel{?}{=}$ b indicates verifying whether a is equal to b.

Moreover, let $〈\mathbf{a},\mathbf{b}〉=\sum _{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{a}}_{\mathrm{i}}{·\mathrm{b}}_{\mathrm{i}}$ denote the inner product between vector a and vector b, and $\mathbf{a}\circ \mathbf{b}={(\mathrm{a}}_1·{\mathrm{b}}_1,\dots ,{{\mathrm{a}}_{\mathrm{n}}·\mathrm{b}}_{\mathrm{n}})\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}}$ denote the Hadamard product of the two vectors. $\mathrm{p}\left(\mathrm{X}\right)=\sum _{\mathrm{i}=1}^{\mathrm{d}}{\mathbf{p}}_{\mathrm{i}}·{\mathrm{X}}^{\mathrm{i}}\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}}\left[\mathrm{X}\right]$ denotes vector polynomials where ${\mathbf{p}}_{\mathrm{i}}$ is a vector in ${\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}}$. We write $\mathrm{t}\left(\mathrm{X}\right)=〈\mathrm{l}\left(\mathrm{X}\right),\mathrm{r}\left(\mathrm{X}\right)〉$ to represent the inner product between two vector polynomials $\mathrm{l}\left(\mathrm{X}\right),\mathrm{r}\left(\mathrm{X}\right)$.

3. Our Scheme

3.1. Algorithm Definition of GENES

Definition 5 (GENES).

Let $\mathcal{R}$ denote a circuit relation that is transformed by the statement to be proved. This paper often omits $\sigma$ and $r$ for convenience. A GENES system comprises four probabilistic polynomial-time (PPT) algorithms as follows.

• $\sigma$ ← setup$\left(1^{\mathsf{\lambda }},\mathcal{R}\right)$: Takes security parameter $\lambda$ and relation $\mathcal{R}$ as input; the algorithm returns public parameter $\sigma$ used to generate and verify the proofs for circuit $\mathcal{R}$.
• $c$ ← commit$\left(\mathsf{\sigma },\mathrm{p};\mathrm{r}\right)$: The algorithm returns committed value $c$, where $p$ denotes the parameter that needs to be committed, and $r$ denotes the blinding factor.
• $\pi$ ← prove$(\mathsf{\sigma },{(\mathbf{a}}_{\mathbf{L}}{,\mathbf{a}}_{\mathbf{R}},{\mathbf{a}}_{\mathbf{O}},\mathbf{b}),\mathbf{v})$: The algorithm returns proof $\pi$ for $\mathcal{R}$, where ${(\mathbf{a}}_{\mathbf{L}}{,\mathbf{a}}_{\mathbf{R}},{\mathbf{a}}_{\mathbf{O}},\mathbf{b})$ denotes the input IO and $\mathit{v}$ denotes the secret witness.
• {0, 1} ← verify$(\sigma ,c,\mathsf{\pi })$: Takes as input public parameter $\sigma$, proof $\pi$ and commitment c, it returns 1 if $\pi$ makes clear that the prover knows the secret $\mathit{v}$ such that $\mathcal{R}({(\mathbf{a}}_{\mathbf{L}}{,\mathbf{a}}_{\mathbf{R}},{\mathbf{a}}_{\mathbf{O}},\mathbf{b}),\mathbf{v})=1$.

3.2. Our Concrete GENES Scheme

R1CS in GENES. Bulletproofs [20] presents a form of the R1CS satisfiability problem [37] that comprises two sets of constraints: multiplication gates (Hadamard product relation) and linear constraints. Its inner relation for R1CS can be replaced with the efficient IPA in bulletproofs [20], which produces short Pedersen commitment proofs for arbitrary circuits. The following is the form of the multiplication gate constraint:

$${\mathit{a}}_L{\circ \mathit{a}}_R={\mathit{a}}_O$$

(1)

where ${\mathbf{a}}_{\mathrm{L}}{,\mathbf{a}}_{\mathrm{R}}$, and ${\mathbf{a}}_{\mathrm{O}}$ are the left input, right input, and output, respectively, of all multiplication gates in the circuit with ${\mathbf{a}}_{\mathrm{L}},{\mathbf{a}}_{\mathrm{R}},{\mathbf{a}}_{\mathrm{O}},\mathbf{b}\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}}$. The form of the linear constraint is as follows:

$${\mathit{W}}_L·{\mathit{a}}_L+{\mathit{W}}_R·{\mathit{a}}_R+{\mathit{W}}_O·{\mathit{a}}_O={\mathit{W}}_V·\mathit{v}+\mathit{c}$$

(2)

where the linear constraint matrix is ${\mathbf{W}}_{\mathrm{L}},{\mathbf{W}}_{\mathrm{R}},{\mathbf{W}}_{\mathrm{O}}\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{Q}\times \mathrm{n}},{\mathbf{W}}_{\mathrm{V}}\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{Q}\times \mathrm{m}}$.

We propose a more relaxed gate constraint and GENES protocol by modifying the R1CS described above. To design a recursive SNARK scheme, we refer to the method of Tzialla et al. [38] and modify multiplication gate constraint (1) by introducing an expanded equation, which is a relaxed gate constraint. In particular, we define a “slack” vector $\mathrm{b}\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}}$ and scalar $\mathrm{u}\in {\mathbb{F}}_{\mathrm{p}}$, and transform the satisfiability check into checking

$${\mathit{a}}_L{\circ \mathit{a}}_R={u\mathit{a}}_O+\mathit{b}$$

(3)

For a “base” instance $\mathbf{b}=0$ and $\mathrm{u}=1$, we obtain the original multiplication gate constraint Equation (1). The extra slack variables are added to make aggregation possible; aggregated instances have other values of $\mathrm{u}$ and $\mathbf{b}$ that are combined with linear constraint (2) to produce a more “relaxing” constraint system (CS) instance. Our protocol comprises four algorithms (setup, commit, prove, verify) based on an R1CS and inner product proof.

First, for a given multiplicative gate constraint of number n and linear constraint of number $\mathrm{Q}$, the setup algorithm can produce a common reference string ($\mathbb{G},{\mathbb{F}}_{\mathrm{p}}$, G, H, G, H) for group $\mathbb{G}$ of prime order $\mathrm{p}$, with random elements G, H ∈ ${\mathbb{G}}^{\mathrm{n}}$ and G, H ∈ $\mathbb{G}$. We write <(Public Input; Witness): Relation> to denote the relationship $\mathcal{R}$ between the prover and verifier, which is as follows:

$$\mathcal{R}=\left\{\begin{array}{c}\left(\mathit{V}\in {\mathbb{G}}^m,{\mathit{W}}_L,{\mathit{W}}_R,{\mathit{W}}_O\in {{\mathbb{Z}}_p^{Q\times n},\mathit{W}}_V\in {\mathbb{Z}}_p^{Q\times m},\mathit{c}\in {\mathbb{Z}}_p^Q;{\mathit{a}}_L,{\mathit{a}}_R,{\mathit{a}}_O,\mathit{b}\in {\mathbb{Z}}_p^n,u\in {\mathbb{F}}_p,\mathit{v},\mathit{\gamma }\in {\mathbb{Z}}_p^m\right):\\ V_j=commit(v_j,{\gamma }_j)\forall j\in [1,m]\\ \wedge {\mathit{a}}_L{\circ \mathit{a}}_R={u\mathit{a}}_O+b\\ \wedge {\mathit{W}}_L·{\mathit{a}}_L+{\mathit{W}}_R·{\mathit{a}}_R+{\mathit{W}}_O·{\mathit{a}}_O={\mathit{W}}_V·v+c.\end{array}\right\}$$

(4)

Amortized Commitment. The purpose of GENES is to construct a recursive succinct ZKP system by merging the R1CS methods (see the merging scheme). In our protocol, different multiplication gate inputs and outputs ${\mathbf{a}}_{\mathrm{L}},{\mathbf{a}}_{\mathrm{R}},{\mathbf{a}}_{\mathrm{O}}$ and variable vectors $\mathbf{b}$ satisfy R1CS with the same weight matrix ${\mathbf{W}}_{\mathrm{L}},{\mathbf{W}}_{\mathrm{R}},{\mathbf{W}}_{\mathrm{O}}$ and constant vector $\mathbf{c}$. We can amortize away (by constructing multiple R1CS) the linear-time construction overhead of CS and the proof overhead of the original commitment vector ${\mathbf{a}}_{\mathrm{L}},{\mathbf{a}}_{\mathrm{R}},{\mathbf{a}}_{\mathrm{O}},\mathbf{b}$ using an untrusted third party “helper”.

Merge R1CS. The merging scheme is based on the constraint equation of the relaxation above. Consider the following multiplication gate constraint instance: $\mathrm{\varnothing }={(\mathbf{a}}_{\mathrm{L}}{,\mathbf{a}}_{\mathrm{R}},{\mathbf{a}}_{\mathrm{O}},\mathbf{b},\mathrm{u})$. Now, consider the following two instances:

$${\varnothing }_{\mathit{m}\mathbf{1}}={(\mathit{a}}_{L1}{, \mathit{a}}_{R1},{{ \mathit{a}}_{O1},\mathit{b}}_{\mathbf{1}},u_1)$$

(5)

$${\varnothing }_{\mathit{m}\mathbf{2}}=\left({\mathit{a}}_{L2}{, \mathit{a}}_{R2},{ \mathit{a}}_{O2},{\mathit{b}}_{\mathbf{2}},u_2\right)$$

(6)

that is,

$${\mathit{a}}_{L1}{\circ \mathit{a}}_{R1}={u_1\mathit{a}}_{O1}+{\mathit{b}}_1, { \mathit{a}}_{L2}{\circ \mathit{a}}_{R2}={u_2\mathit{a}}_{O2}+{\mathit{b}}_2$$

(7)

For ${\mathbf{W}}_{\mathrm{L}}·{\mathbf{a}}_{\mathrm{L}1}+{\mathbf{W}}_{\mathrm{R}}·{\mathbf{a}}_{\mathrm{R}1}+{\mathbf{W}}_{\mathrm{O}}·{\mathbf{a}}_{\mathrm{O}1}-{\mathbf{W}}_{\mathrm{V}}·{\mathbf{v}}_1=\mathbf{c}$ and ${\mathbf{W}}_{\mathrm{L}}·{\mathbf{a}}_{\mathrm{L}2}+{\mathbf{W}}_{\mathrm{R}}·{\mathbf{a}}_{\mathrm{R}2}+{\mathbf{W}}_{\mathrm{O}}·{\mathbf{a}}_{\mathrm{O}2}-{\mathbf{W}}_{\mathrm{V}}·{\mathbf{v}}_2=\mathbf{c}$.

By randomly sampling $\mathrm{r}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{F}}_{\mathrm{p}}$ and using linear combinations, the verifier merges them into a new instance. For the left side of the multiplication gate, the constraint equation is as follows:

$$\left({\mathit{a}}_{L1}+r{\mathit{a}}_{L2}\right)\circ \left({\mathit{a}}_{R1}+r{\mathit{a}}_{R2}\right)-{(u}_1+r{u}_2\left)\right({\mathit{a}}_{O1}+{r\mathit{a}}_{O2})$$

(8)

This expands into the following formulas (grouping the 1, $\mathrm{r}$ and ${\mathrm{r}}^2$ terms together):

$${\mathit{a}}_{L1}{\circ \mathit{a}}_{R1}-{u_1\mathit{a}}_{O1}$$

(9)

$$r({\mathit{a}}_{L1}{\circ \mathit{a}}_{R2}+{\mathit{a}}_{L2}{\circ \mathit{a}}_{R1}-u_1{ \mathit{a}}_{O2}-u_2{ \mathit{a}}_{O1})$$

(10)

$$r^2{ (\mathit{a}}_{L2}{\circ \mathit{a}}_{R2}-{u_2\mathit{a}}_{O2})$$

(11)

The first term is only ${\mathbf{b}}_{\mathbf{1}}$ and the third term is ${\mathrm{r}}^2{\mathbf{b}}_{\mathbf{2}}$. The prover simply provides the middle term (without the $\mathrm{r}$ factor), and the randomization forces the prover to be honest.

That is, for the linear constraint equation,

$${\mathit{W}}_L·\left({\mathit{a}}_{L1}+r{\mathit{a}}_{L2}\right)+{\mathit{W}}_R·\left({\mathit{a}}_{R1}+r{\mathit{a}}_{R2}\right)+{\mathit{W}}_O·({\mathit{a}}_{O1}+{r\mathit{a}}_{O2})-{\mathit{W}}_V·\left({\mathit{v}}_1+r{\mathit{v}}_2\right)=(1+\mathit{r})\mathit{c}$$

is obviously true.

Further, we can obtain the following new constraint instances:

$${\varnothing }_{{\mathit{m}}_{\mathit{n}\mathit{e}\mathit{w}}}\leftarrow \left({\mathit{a}}_{L1}+r{\mathit{a}}_{L2},{\mathit{a}}_{R1}+r{\mathit{a}}_{R2},{\mathit{a}}_{O1}+r{\mathit{a}}_{O2},{\mathit{b}}_{\mathbf{1}}+r^2{\mathit{b}}_{\mathbf{2}}+r\mathit{T},u_1+r{u}_2\right)$$

(12)

where $\mathbf{U}\leftarrow {\mathbf{a}}_{\mathrm{L}1}{\circ \mathbf{a}}_{\mathrm{R}2}+{\mathbf{a}}_{\mathrm{L}2}{\circ \mathbf{a}}_{\mathrm{R}1}-{\mathrm{u}}_1{\mathbf{a}}_{\mathrm{O}2}-{\mathrm{u}}_2{\mathbf{a}}_{\mathrm{O}1}$ for ${\mathrm{\varnothing }}_{\mathbf{m}1}$ and ${\mathrm{\varnothing }}_{\mathbf{m}2},$ making the equation operate with this new value.

For efficiency, the prover sends commit $\left({\mathbf{a}}_{\mathrm{L}1}{,\mathbf{a}}_{\mathrm{R}1}\right)$, commit $\left({\mathbf{a}}_{\mathrm{O}1}\right)$, commit $\left({\mathbf{b}}_1\right)$ and commit $\left({\mathbf{a}}_{\mathrm{L}2}{,\mathbf{a}}_{\mathrm{R}2}\right)$, commit $\left({\mathbf{a}}_{\mathrm{O}2}\right)$, commit $\left({\mathbf{b}}_2\right)$ to the verifier which one was provided by ${\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{p}\mathrm{e}\mathrm{r}}_1$ and ${\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{p}\mathrm{e}\mathrm{r}}_2$, respectively. In addition, the prover includes additively homomorphic commitments to $\mathbf{U}$ in the instance, that is, provides commit $\left({\mathbf{U}}_1\right)$ rather than sending it directly. Then, instead of computing (linearly sized) $\mathbf{b}$, ${(\mathbf{a}}_{\mathrm{L}}{,\mathbf{a}}_{\mathrm{R}}),{\mathbf{a}}_{\mathrm{O}}$, the verifier homomorphically computes commitments to $\mathbf{b}$, ${(\mathbf{a}}_{\mathrm{L}}{,\mathbf{a}}_{\mathrm{R}}),{\mathbf{a}}_{\mathrm{O}}$ as part of the new instance, resulting in proofs and verification times of constant size. The merging scheme is a public coin, and we can make it non-interactive via the Fiat–Shamir transform [39]. We can recursively merge multiple R1CS using this scheme. In particular, to reduce verification circuit depth (reduced verifying complex arguments), we can split a complex proof problem into several simple proof problems by setting a recursion threshold and performing recursive proof operations by converting it into multiple fixed-weight R1CS satisfiability problems. Thus, the verification operation in linear time is executed only once after the recursion, eliminating the requirement for a complete succinct argument and preventing unnecessary duplication of calculations.

Polynomial commitment and inner product argument. To ensure that the proofs are smaller, the prover must provide a succinct protocol for this last step. In our protocol, in the last step of the merging scheme, we adopt the IPA method in bulletproofs [20] to implement a relatively concise protocol. The entire agreement process of the GENES is shown in Algorithm 1.

Algorithm 1. The Entire GENES Protocol

Input: $\mathsf{\sigma },{\mathbf{W}}_{\mathrm{L}},{\mathbf{W}}_{\mathrm{R}},{\mathbf{W}}_{\mathrm{O}}\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{Q}\times \mathrm{n}},{\mathbf{W}}_{\mathrm{V}}\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{Q}\times \mathrm{m}},\mathbf{c}\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{Q}},{\mathrm{u}}_{\mathrm{i}}\in {\mathbb{F}}_{\mathrm{p}},\mathsf{\gamma }\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{m}};{\mathbf{a}}_{\mathrm{L}}{,\mathbf{a}}_{\mathrm{R}}{,\mathbf{a}}_{\mathrm{o}},\mathbf{b}\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}}$ Output: {Verifier accepts, Verifier rejects} Prover & Helper commit: Helper $\mathrm{i},\forall \mathrm{i}\in [1,\mathrm{M}]$ ${\mathsf{\alpha }}_{\mathrm{i}},{\mathsf{\beta }}_{\mathrm{i}},{\mathsf{\mu }}_{\mathrm{i}}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_{\mathrm{p}},\forall \mathrm{i}\in [1,\mathrm{M}]$ ${\mathrm{A}}_{{\mathrm{I}}_{\mathrm{i}}}$ = commit $\left(\mathsf{\sigma },\left({\mathbf{a}}_{\mathrm{L}\mathrm{i}}{,\mathbf{a}}_{\mathrm{R}\mathrm{i}}\right);{\mathsf{\alpha }}_{\mathrm{i}}\right)$ ${\mathrm{A}}_{{\mathrm{O}}_{\mathrm{i}}}$ = commit $\left(\mathsf{\sigma },{\mathbf{a}}_{\mathrm{O}\mathrm{i}};{\mathsf{\beta }}_{\mathrm{i}}\right)$ ${\mathrm{B}}_{\mathrm{i}}$ = commit $\left(\mathsf{\sigma },{\mathbf{b}}_{\mathrm{i}};{\mathsf{\mu }}_{\mathrm{i}}\right)$ $\stackrel{{\mathrm{A}}_{{\mathrm{I}}_{\mathrm{i}}},{\mathrm{A}}_{{\mathrm{O}}_{\mathrm{i}}},{\mathrm{B}}_{\mathrm{i}}}{\to }$ Prover: ${\mathbf{a}}_{\mathrm{L}}\leftarrow {\mathbf{a}}_{\mathrm{L}1},{\mathbf{a}}_{\mathrm{R}}\leftarrow {\mathbf{a}}_{\mathrm{R}1},{\mathbf{a}}_{\mathrm{O}}\leftarrow {\mathbf{a}}_{\mathrm{O}1},\mathrm{u}\leftarrow {\mathrm{u}}_1$ $\mathrm{F}\mathrm{o}\mathrm{r} \mathrm{i}=2,\mathrm{i}<=\mathrm{M},\mathrm{i}++$: //Merge recursively until the last CS instance (${\mathbf{a}}_{\mathrm{L}\mathrm{M}}{,\mathbf{a}}_{\mathrm{R}\mathrm{M}}{,\mathbf{a}}_{\mathrm{O}\mathrm{M}},{\mathbf{b}}_{\mathrm{M}})$ is collapsed $\stackrel{{\mathrm{r}}_{\mathrm{i}}\in {\mathbb{F}}_{\mathrm{p}}^{\mathrm{*}}}{\leftarrow }$ ${\mathsf{\rho }}_{\mathrm{j}}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_{\mathrm{p}},\forall \mathrm{j}\in \left[1,\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{M}\right]$ ${\mathbf{U}}_{\mathrm{j}}\leftarrow {\mathbf{a}}_{\mathrm{L}}{\circ \mathbf{a}}_{\mathrm{R}\mathrm{i}}+{\mathbf{a}}_{\mathrm{L}\mathrm{i}}{\circ \mathbf{a}}_{\mathrm{R}}-{\mathrm{u}\mathbf{a}}_{\mathrm{O}\mathrm{i}}-{\mathrm{u}}_{\mathrm{i}}{\mathbf{a}}_{\mathrm{O}}$ ${\mathrm{U}}_{\mathrm{j}}$ = commit $\left(\mathsf{\sigma },{\mathbf{U}}_{\mathrm{j}};{\mathsf{\rho }}_{\mathrm{j}}\right)$ $\stackrel{{\mathrm{U}}_{\mathrm{j}}}{\to }$ ${\mathbf{a}}_{\mathrm{L}}\leftarrow {\mathbf{a}}_{\mathrm{L}}+\mathrm{r}{\mathbf{a}}_{\mathrm{L}\mathrm{i}}$,${{\mathbf{a}}_{\mathrm{R}}\leftarrow \mathbf{a}}_{\mathrm{R}}+\mathrm{r}{\mathbf{a}}_{\mathrm{R}\mathrm{i}}$,${{\mathbf{a}}_{\mathrm{O}}\leftarrow \mathbf{a}}_{\mathrm{O}}+\mathrm{r}{\mathbf{a}}_{\mathrm{O}\mathrm{i}}, \mathrm{u}\leftarrow \mathrm{u}+\mathrm{r}{\mathrm{u}}_2$ $\mathsf{\chi }\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_{\mathrm{p}}$ ${\mathbf{s}}_{\mathrm{L}}{,\mathbf{s}}_{\mathrm{R}}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}}$ S = commit $\left(\mathsf{\sigma },\left({\mathbf{s}}_{\mathrm{L}}{,\mathbf{s}}_{\mathrm{R}}\right);\mathsf{\chi }\right)$ $\stackrel{\mathrm{S}}{\to }$ $\stackrel{\mathrm{y},\mathrm{z}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_{\mathrm{p}}^{\mathrm{*}}}{\leftarrow }$ $〈{\mathbf{a}}_{\mathrm{L}}{\circ \mathbf{a}}_{\mathrm{R}}-{\mathrm{u}\mathbf{a}}_{\mathrm{O}}-\mathbf{b},{\mathbf{y}}^{\mathrm{n}}〉+〈\mathrm{z}{\mathbf{z}}^{\mathrm{Q}},{\mathbf{W}}_{\mathrm{L}}·{\mathbf{a}}_{\mathrm{L}}+{\mathbf{W}}_{\mathrm{R}}·{\mathbf{a}}_{\mathrm{R}}+{\mathbf{W}}_{\mathrm{O}}·{\mathbf{a}}_{\mathrm{O}}-{\mathbf{W}}_{\mathrm{V}}·\mathbf{v}-\mathbf{c}〉=0$ $\mathsf{\delta }\left(\mathrm{y},\mathrm{z}\right)=〈{\mathbf{y}}^{-\mathrm{n}}\circ \left(\mathrm{z}{\mathbf{z}}^{\mathrm{Q}}·{\mathbf{W}}_{\mathrm{R}}\right),\mathrm{z}{\mathbf{z}}^{\mathrm{Q}}·{\mathbf{W}}_{\mathrm{L}}〉$ ${\mathbf{a}}_{\mathrm{L}}\leftarrow {\mathbf{a}}_{\mathrm{L}}+{\mathbf{s}}_{\mathrm{L}}·{\mathrm{X}}^2,{\mathbf{a}}_{\mathrm{R}}\leftarrow {\mathbf{a}}_{\mathrm{R}}+{\mathbf{s}}_{\mathrm{R}}·{\mathrm{X}}^2$ $\mathrm{l}\left(\mathrm{X}\right)=({\mathbf{a}}_{\mathrm{L}}+{\mathbf{s}}_{\mathrm{L}}·{\mathrm{X}}^2)·\mathrm{X}+\mathrm{u}{\mathbf{a}}_{\mathrm{O}}·{\mathrm{X}}^2+{\mathbf{y}}^{-\mathrm{n}}\circ \left(\mathrm{z}{\mathbf{z}}^{\mathrm{Q}}·{\mathbf{W}}_{\mathrm{R}}\right)·\mathrm{X}+{\mathbf{s}}_{\mathrm{L}}·{\mathrm{X}}^3\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}}\left[\mathrm{X}\right]$ $\mathrm{r}\left(\mathrm{X}\right)={\mathrm{u}\mathbf{y}}^{\mathrm{n}}\circ ({\mathbf{a}}_{\mathrm{R}}+{\mathbf{s}}_{\mathrm{R}}·{\mathrm{X}}^2)·\mathrm{X}-{\mathbf{y}}^{\mathrm{n}}+\mathrm{z}{\mathbf{z}}^{\mathrm{Q}}·{(\mathbf{W}}_{\mathrm{L}}·\mathrm{X}+{\mathbf{W}}_{\mathrm{O}})+{\mathbf{y}}^{\mathrm{n}}\circ {\mathbf{s}}_{\mathrm{R}}·{\mathrm{X}}^3\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}}[\mathrm{X}]$ $\mathrm{t}\left(\mathrm{X}\right)=〈\mathrm{l}\left(\mathrm{X}\right),\mathrm{r}\left(\mathrm{X}\right)〉={\displaystyle \sum _{\mathrm{i}=1}^6}{\mathrm{t}}_{\mathrm{i}}·{\mathrm{X}}^{\mathrm{i}}\in {\mathbb{Z}}_{\mathrm{p}}[\mathrm{X}]$ ${\mathrm{t}}_2=2\mathrm{n}\mathrm{d} \mathrm{d}\mathrm{e}\mathrm{g}\mathrm{r}\mathrm{e}\mathrm{e} \mathrm{o}\mathrm{f}〈\mathrm{l}\left(\mathrm{X}\right),\mathrm{r}\left(\mathrm{X}\right)〉=〈\mathbf{b},{\mathbf{y}}^{\mathrm{n}}〉+〈\mathrm{z}{\mathbf{z}}^{\mathrm{Q}}·{\mathbf{W}}_{\mathrm{V}},\mathbf{v}〉+〈\mathrm{z}{\mathbf{z}}^{\mathrm{Q}},\mathbf{c}〉+\mathsf{\delta }\left(\mathrm{y},\mathrm{z}\right){\in \mathbb{Z}}_{\mathrm{p}}$ ${\mathsf{\tau }}_{\mathrm{i}}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_{\mathrm{p}}$ $\forall \mathrm{i}\in \left[1,3,4,5,6\right]$ ${\mathrm{T}}_{\mathrm{i}}$ = commit$\left(\mathsf{\sigma },{\mathrm{t}}_{\mathrm{i}};{\mathsf{\tau }}_{\mathrm{i}}\right)$ $\stackrel{{\mathrm{T}}_1,{\mathrm{T}}_3,{\mathrm{T}}_4,{\mathrm{T}}_5,{\mathrm{T}}_6}{\to }$ $\stackrel{\mathrm{x}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_{\mathrm{p}}^{\mathrm{*}}}{\leftarrow }$ Prover prove: $\mathbf{l}=\mathrm{l}\left(\mathrm{x}\right)\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}},\mathbf{r}=\mathrm{r}\left(\mathrm{x}\right)\in {\mathbb{Z}}_{\mathrm{p}}^{\mathrm{n}},\widehat{\mathrm{t}}=〈\mathbf{l},\mathbf{r}〉{\in \mathbb{Z}}_{\mathrm{p}}$ ${\mathsf{\tau }}_{\mathrm{x}}={\displaystyle \sum _{\mathrm{i}=1}^6}{\mathsf{\tau }}_{\mathrm{i}}·{\mathrm{x}}^{\mathrm{i}}+{\mathrm{x}}^2〈\mathrm{z}{\mathbf{z}}^{\mathrm{Q}},\mathsf{\gamma }·{\mathbf{W}}_{\mathrm{V}}〉\in {\mathbb{Z}}_{\mathrm{p}},\mathsf{\varsigma }=\mathsf{\alpha }·\mathrm{x}+\mathsf{\beta }·{\mathrm{x}}^2+\mathsf{\mu }·{\mathrm{x}}^3+\mathsf{\chi }·{\mathrm{x}}^4{\in \mathbb{Z}}_{\mathrm{p}}$ $\stackrel{\mathbf{l},\mathbf{r},\widehat{\mathrm{t}},{\mathsf{\tau }}_{\mathrm{x}},\mathsf{\varsigma }}{\to }$ Verifier Verify: ${\mathrm{A}}_{\mathrm{I}}={\mathrm{A}}_{\mathrm{I}1}+\sum _{\mathrm{i}=2}^{\mathrm{M}}{\mathrm{r}}^{\mathrm{i}}{·\mathrm{A}}_{\mathrm{I}\mathrm{i}}$, ${{\mathrm{A}}_{\mathrm{O}}=\mathrm{A}}_{\mathrm{O}1}+\sum _{\mathrm{i}=2}^{\mathrm{M}}{\mathrm{r}}^{\mathrm{i}}·{\mathrm{A}}_{\mathrm{O}\mathrm{i}}$, $\mathrm{B}=\mathrm{r}{·\mathrm{U}}_{\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{M}}+\sum _{\mathrm{i}=2}^{\mathrm{M}}{(\mathrm{r}}^2·{\mathrm{B}}_{\mathrm{i}}+{\mathrm{B}}_{\mathrm{i}-1})$ ${\mathbf{H}}^{’}=〈\mathbf{H},{\mathbf{y}}^{-\mathrm{n}}〉$ ${\mathrm{W}}_{\mathrm{L}}=〈\mathrm{z}{\mathbf{z}}^{\mathrm{Q}}·{\mathbf{W}}_{\mathrm{L}},{\mathbf{H}}^{’}〉$, ${\mathrm{W}}_{\mathrm{R}}=〈{\mathbf{y}}^{-\mathrm{n}}\circ (\mathrm{z}{\mathbf{z}}^{\mathrm{Q}}·{\mathbf{W}}_{\mathrm{R}}),\mathbf{G}〉$, ${\mathrm{W}}_{\mathrm{O}}=〈\mathrm{z}{\mathbf{z}}^{\mathrm{Q}}·{\mathbf{W}}_{\mathrm{O}},{\mathbf{H}}^{’}〉$ $\widehat{\mathrm{t}}\stackrel{?}{=}〈\mathbf{l},\mathbf{r}〉$ $$\begin{gathered} \widehat{\mathrm{t}}·\mathrm{G}+{\mathsf{\tau }}_{\mathrm{x}}·\mathrm{H}\stackrel{?}{=}{\mathrm{x}}^2·\left(〈\mathbf{b},{\mathbf{y}}^{\mathrm{n}}〉+〈\mathrm{z}{\mathbf{z}}^{\mathrm{Q}},\mathbf{c}〉+\mathsf{\delta }\left(\mathrm{y},\mathrm{z}\right)\right)·\mathrm{G}+{\mathrm{x}}^2·〈\left(\mathrm{z}{\mathbf{z}}^{\mathrm{Q}}·{\mathbf{W}}_{\mathrm{V}},\mathbf{v}\right),\mathbf{V}〉 \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+{\displaystyle \prod _{\mathrm{i}=1,3,4,5,6}^6}{\mathrm{x}}^{\mathrm{i}}·{\mathrm{T}}_{\mathrm{i}}, \end{gathered}$$ $\mathrm{P}=\mathrm{x}{·\mathrm{A}}_{\mathrm{I}}+{\mathrm{x}}^2{·\mathrm{A}}_{\mathrm{O}}-〈{\mathbf{y}}^{\mathrm{n}},{\mathbf{H}}^{’}〉+\mathrm{x}·{\mathrm{W}}_{\mathrm{L}}+\mathrm{x}·{\mathrm{W}}_{\mathrm{R}}+{\mathrm{W}}_{\mathrm{O}}+{\mathrm{x}}^3·\mathrm{S}$ $\mathrm{P}\stackrel{?}{=}〈\mathsf{\varsigma },\mathrm{H}〉+〈\mathbf{l},\mathbf{G}〉+〈\mathbf{r},{\mathbf{H}}^{’}〉$ If all checks succeed: Verifier accepts Else: Verifier rejects

3.3. Complexity Analysis

In this section, we analyze the complexity of the proof generation and verification processes for several zkSNARK protocols, focusing on our work in comparison with other prominent zk-SNARK schemes, including bulletproofs [20], plonk [34], and halo [21], which demonstrates the computational advantages of GENES, particularly in terms of verification complexity.

3.3.1. Proof Generation Complexity

Table 1. Comparison of proof generation complexity for several zk-SNARK protocols.

Scheme	Best-Case Complexity	Average Complexity	Worst-Case Complexity
Bulletproofs [20]	O(n)	O(n)	O(n)
Plonk [34]	O(nlogn)	O(nlogn)	O(nlogn)
Halo [21]	O(nlogn)	O(nlogn)	O(nlogn)
GENES (our work)	O(n)	O(n)	O(n)

provides a comparison of the proof generation complexities for different zk-SNARK protocols, denoted as the optimal, average, and worst-case complexities, where n represents the number of constraints (i.e., the number of gates or variables in the circuit).

GENES has a proof generation complexity of O(n), which is linear in the number of constraints n. The linear complexity allows GENES to scale efficiently with increasing problem size, and its complexity remains stable regardless of the recursive depth or the number of constraints. In contrast, bulletproofs [20] exhibits similar an optimal complexity of O(n), which stems from its efficient inner-product argument structure, making it well-suited for applications requiring compact proofs without relying on trusted setups. However, its reliance on polynomial encoding contributes to a higher computation cost in practical implementations. The proof generation complexity of plonk [34] is O(nlogn), which is slightly higher than bulletproofs [20] and GENES due to its reliance on Fast Fourier Transform (FFT) and polynomial interpolation for constructing polynomial commitments. These operations are computationally intensive and their cost grows logarithmically with the circuit size, which limits scalability for applications requiring frequent proof generation. Halo [21] has the same proof generation complexity of O(nlogn), as it also involves FFT and polynomial-related operations in its recursive proof construction. Although its recursive design enhances scalability, the additional computational overhead makes it less efficient than GENES.

3.3.2. Verification Complexity

Table 2. Comparison of verification complexity for several zk-SNARK protocols.

Scheme	Best-Case Complexity	Average Complexity	Worst-Case Complexity
Bulletproofs [20]	O(logn)	O(logn)	O(logn)
Plonk [34]	O(logn)	O(logn)	O(logn)
Halo [21]	O(logn)	O(logn)	O(logn)
This work	O(1)	O(1)	O(1)

provides a comparison of the verification complexities of the same protocols. GENES achieves a constant verification complexity, O(1), regardless of the number of constraints. This is due to the recursive composition mechanism, which allows the verification process to scale independently of the proof size or the recursive depth. Each verification step only involves a constant amount of work, making it highly efficient for large proofs and recursive proofs. Bulletproofs [20] and plonk [34] exhibit verification complexities of O(logn), meaning their verification time grows logarithmically with respect to the number of constraints. While this is still quite efficient, especially compared to non-zk-SNARK schemes, it is less optimal than GENES’s constant-time verification. Halo [21], while benefiting from its recursive construction, still exhibits a verification complexity of O(logn). This is due to the combination of its recursive nature with polynomial-based encoding, requiring each verification step to check a logarithmic number of intermediate proofs and polynomial evaluations.

Thus, the constant-time verification in GENES presents a clear advantage over other zk-SNARK protocols, particularly in high-throughput blockchain applications where the verification phase can become a bottleneck. As the verification time does not scale with the size of the input, GENES ensures a highly efficient validation process regardless of the proof size.

3.4. Security Analysis

Theorem 1.

The GENES protocol presented in Section 3.2 has perfect completeness, perfect special honest verifier zero-knowledge, and computational witness-extended emulation under the DLOG assumption.

Proof of Theorem 1.

GENES also possesses the three security properties mentioned above under the DLOG assumption. For perfect completeness, the perfect completeness of IPA for an arithmetic circuit is proved in bulletproofs [20]. For perfect completeness, the perfect completeness of the inner product proof for an arithmetic circuit is proved in bulletproofs [20] under the DLOG assumption, which also applies to this study. Thus, if all the gate constraints of the arithmetic circuit are satisfiable, then

$${<\mathbf{a}}_{\mathrm{L}}{\circ \mathbf{a}}_{\mathrm{R}}-{\mathrm{u}\mathbf{a}}_{\mathrm{O}}-\mathbf{b},{\mathbf{y}}^{\mathrm{n}}>+<\mathrm{z}{\mathbf{z}}^{\mathrm{Q}},{\mathbf{W}}_{\mathrm{L}}·{\mathbf{a}}_{\mathrm{L}}+{\mathbf{W}}_{\mathrm{R}}·{\mathbf{a}}_{\mathrm{R}}+{\mathbf{W}}_{\mathrm{O}}·{\mathbf{a}}_{\mathrm{O}}-{\mathbf{W}}_{\mathrm{V}}·\mathbf{v}-\mathbf{c}>=0$$

Then, we can obtain the coefficient $t_2$ of the quadratic term of the polynomial $\mathrm{t}\left(\mathrm{X}\right)$ is 0, so the verifier finally accepts the proof. For the merged scheme, if both instances 1 and 2 are circuit satisfiable, then the merged new instance must be circuit satisfiable, and if the circuit of the new instance is satisfiable, there is a high probability that instances 1 and 2 are also circuit satisfiable [38]. For perfect special honest verifier zero-knowledge, this property is guaranteed by the hiddenness of the commitment and the blinding vectors ${\mathbf{s}}_{\mathrm{L}}{,\mathbf{s}}_{\mathrm{R}}$. For computational witness-extended emulation, this property is guaranteed by the binding of the commitment and evidence-extended emulation of the inner product argument. The latter two properties agree with those of bulletproofs. □

4. GENES Performance Verification

In this section, we verified the performance of the GENES algorithm by comparing it with other related algorithms in terms of prover time, proof size, and verifier time.

We conducted experiments on a computer system equipped with eight physical CPUs and 32G of RAM. To summarize our results, the prover and verifier times of the GENES protocol were significantly reduced compared to those of the popular bulletproofs [20] and halo [21] schemes. This is because GENES is a scheme that can efficiently verify multiple proofs and prove a single complex proof by setting the recursion threshold to split it into several simple proofs (effectively reducing the proof circuit depth) and then performing GENES on several simple proofs to achieve the goal.

4.1. Comparison with Other ZKPs

We implemented GENES through the cryptography library Dalek [40] and built it using ristretto255. As depicted in Figure 1, Figure 2 and Figure 3, our scheme was compared with bulletproofs [20], based on ed25519, and halo [21], based on the custom Tweedledum255 and Tweedledee255 curves.

Figure 1, Figure 2 and Figure 3 compare the prover time cost, proof size, and verifier time cost of the three IPA-based zk-SNARK schemes in practice, respectively. This group of experiments demonstrated that for a 64-bit proof, the prover time of our scheme is 11.3 ms, which was reduced by 79.30% compared to bulletproofs [20] and by 97.10% compared to halo [21]; the verifier time of our scheme was 1.49 ms, which was reduced by 69.02% compared to bulletproofs [20] and by 83.44% compared to halo [21]. Moreover, our scheme has even greater advantages when the proof statement increases, although halo [21] showed better performance than bulletproofs [20]. For the proof size, that is, bandwidth consumption, the halo [21] scheme was approximately 2.3 bytes and has the best performance. Our scheme and that of bulletproofs [20] were approximately 5.73 bytes and 6.23 bytes, respectively. Compared with bulletproofs [20], our scheme had a slightly lower bandwidth cost because we introduced a “helper”. The vector commitment to the circuit constraints ${\mathbf{a}}_{\mathbf{L}},{\mathbf{a}}_{\mathbf{R}},{\mathbf{a}}_{\mathbf{O}}$ and $\mathbf{b}$ in the algorithm are calculated and generated by the helper, which amortizes the prover’s calculation pressure, thereby enabling the network to achieve the effect of load balancing.

It is noteworthy that all three schemes have linear prover time, proof size, and verifier time (not completely succinct), but GENES performed best as the number of circuit constraints varied to varying degrees. This is because although halo [21] performed only the linear time proof in the last iteration, it still needed to perform the log time calculation “internally”. However, our scheme requires only the prover and verifier to calculate the new running instance formed by merging two old instances in the R1CS merging process. This process requires only a few group operations through the Pederson commitment.

4.2. Cost and Benefits of the GENES Merging Scheme

To evaluate the benefits of GENES’s merging scheme, we considered bulletproofs as a variant of GENES, which satisfies instances of R1CS where $\mathbf{b}=\mathbf{0}$ and $\mathrm{u}=1$. Bulletproofs does not employ GENES’s merging scheme. BÜNZ et al. [20] proposed a bulletproof aggregation optimization scheme for $m$ range proofs called bulletproof-agg, which effectively reduces the proof size but does not change the prover time and verifier time (bulletproof-agg does not appear in Figure 4 and Figure 5 because it has the same curve as bulletproofs). To reduce the effect of other factors on the experimental results, we implemented bulletproofs based on the ristretto255 group. The experiment is assumed to prove several proofs of 64-bit size (i.e., the circuit size is $2^6$). Figure 4, Figure 5 and Figure 6 show how the proof time, proof size, and verification time of GENES (using the merged scheme) and bulletproofs/bulletproof-agg (without the merged scheme) change as the number of proofs increases. When the number of proofs reaches $2^{12}$ (approximately 4000 proofs), the prover times of our scheme and bulletproofs are 46.285 s and 0.0165 s, respectively, with our scheme reduced by 99.96% compared to bulletproofs; the verifier times are 6.1 s and 0.00675 s, respectively, which is reduced by 99.89%. In both cases, our scheme improved significantly. However, for the proof size that proves $2^{12}$ proofs, our scheme is approximately 32 bytes larger than the bulletproof-agg scheme.

5. Applications

In this section, we take Ethereum [41] as an example to introduce a novel mechanism leveraging GENES for efficient batch transaction verification, where Ethereum nodes can verify a single proof that aggregates the validity of multiple transactions instead of verifying each transaction individually. This approach reduces the verification burden on Ethereum nodes while ensuring the integrity and correctness of transactions.

5.1. GENES-Based Batch Transaction Verification Mechanism

The core of the batch transaction verification mechanism based on GENES is a new Ethereum block structure, shown in Figure 7. Specifically, we added fields to the block body and header to accommodate individual transaction commitments and an aggregated proof (i.e., the red box in Figure 7). In the proposed mechanism, each transaction that enters the transaction pool includes an associated commitment and proof, which are generated by the transaction generation node or a designated trusted party, ensuring that the transaction satisfies all required conditions (such as correct signatures, nonce checks, and state transitions). When miners package transactions, they store the transaction commitments instead of the transactions themselves in the block body, thereby ensuring transaction privacy. An aggregated proof is then stored in the block header, which combines the proofs of all individual transactions in the block, ensuring that all transactions included in the block are valid. Once the block is completed, the miner broadcasts the block to the Ethereum network. Upon receiving the block, Ethereum nodes only need to verify the aggregated proof in the block header via commitments in block body to ensure the validity of all transactions, without the need to verify each transaction individually. If the aggregated proof is valid, the block is added to the distributed ledger, completing the block finalization process.

5.2. Analysis

The proposed batch transaction verification mechanism aims to enhance Ethereum’s transaction validation process by leveraging GENES, demonstrating significant advantages in security, privacy and efficiency.

In terms of security and privacy, the security of this mechanism relies on the security of GENES. By using GENES to aggregate transaction validity proofs, we ensure that even if a node does not have access to the full transaction pool, it can still verify the correctness of the block with a single proof, which reduces the attack surface for potential malicious actors attempting to introduce invalid transactions into the blockchain. Additionally, by including only transaction commitments in the block body instead of the full trans-action data, the proposed mechanism enhances transaction privacy.

In terms of efficiency, each node in traditional Ethereum [41] needs to repeatedly validate every transaction of the network, which can be computationally expensive, particularly when blocks contain numerous transactions. With GENES, Ethereum nodes only need to verify a single proof, which can be completed in a constant time regardless of the number of transactions in the block. This drastically reduces the verification workload and accelerates block validation, effectively increasing the throughput and scalability of the network.

6. Conclusions

In this study, using the previous protocols by Bünz et al. [20], we utilize the relaxed R1CS method introduced by Kothapalli et al. [29] to propose a recursive zk-SNARK scheme called GENES and analyze its security under the standard DLOG assumption. Our scheme is more efficient than other existing IPA-based ZKP schemes in terms of both proof generation and verification costs. In particular, the prover times of our scheme are 79.30% and 97.10% shorter than those of Bünz et al. [20] and Bowe et al. [21] respectively, and the efficiency advantage becomes more apparent as the proof statement increases. However, despite these advancements, our protocol has a limitation in terms of proof size, which is an important direction for future work. Another future work would be to design some ZKP schemes with extra properties to cope with more complex blockchain scenarios. For example, an interesting issue is how to trace transactions in the blockchain when they are stored in the form of commitments in the block.