Scalable batch verification of ECDSA for blockchain using IVC

Abstract

With the rising volume of transactions on blockchains, signature verification becomes a critical bottleneck of efficiency, hindering scalability and performance. This paper presents a general approach to batch verification of arbitrary signatures on blockchain. By leveraging the memory-friendliness of incremental verifiable computation (IVC) and optimizing for blockchain environments, the proposed scheme can enhance scalability, reduce memory consumption, and ensure compatibility with common devices while supporting an arbitrary number of signature verifications. This approach allows for the concurrent generation of IVC proofs while receiving signatures from other nodes, making it particularly well-suited for low-latency blockchain applications. As a concrete instantiation of our approach, we introduce \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} (Batch ECDSA Transaction verification Scheme), where the underlying SNARK is instantiated by \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n} with Bulletproof commitment. Our implementation, evaluated on a virtual machine with 8 cores and 16 GB RAM, shows significant performance gains compared to {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}}, which is the direct construction using \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n} with \mathsf{B}\mathsf{u}\mathsf{l}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{p}\mathsf{r}\mathsf{o}\mathsf{o}\mathsf{f} commitment to verify a batch of ECDSA. The comparison shows that \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} speeds up the prover by 3–7 times and the verifier by 48–240 times when handling up to 2^{11} ECDSA signatures, the maximum batch size supported by {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}}. For larger batches exceeding 2^{10}, our scheme outperforms the baseline approach, which verifies ECDSA signatures one by one without any proof system. Our verifier achieved a speedup of 21–174 times compared to the baseline as the batch size grows to 2^{20}. Furthermore, \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} exhibits a remarkably low memory footprint, with peak memory usage remaining below 1 GB.

Graphical abstract

Keywords

batch verification / ECDSA / IVC / blockchain

1 Introduction

A digital signature is a cryptographic mechanism that allows a signer to authenticate a message using his private key. Anyone can then verify the validity of the signature using the corresponding public key. This authentication functionality has led to the widespread adoption of digital signatures in various applications. The rise of blockchain technology has further increased the popularity of digital signatures. In a blockchain system, when a transfer occurs, it must be accompanied by a digital signature. The transaction can be recorded on the blockchain only if it is verified by a sufficient number of nodes (participants). As the number of transactions grows, the workload for verifying these signatures increases dramatically. This presents a significant challenge for blockchain scalability, as the time it takes to verify signatures can become a bottleneck, limiting the blockchain’s overall throughput and performance.

Batch verification of digital signatures offers a promising approach to address this problem. By verifying multiple signatures simultaneously, batch verification significantly reduces the overall verification time compared to individual verification. In particular, customized signatures tailored for batch verification can leverage homomorphic properties to significantly improve the verification process. For example, the aggregate BLS signature [1] can be constructed by adding up multiple individual BLS signatures simply, resulting in a nearly 50\mathrm{\%} reduction in verification time.

While customized signatures like BLS offer significant advantages for batch verification, adapting standard schemes like ECDSA for efficient batch verification remains an active area of research, due to ECDSA’s widespread adoption and strong security track record. However, existing batch verification techniques for standard signature schemes often face limitations. Harn [2] proposes schemes for batch verification of RSA signatures, but these schemes only support multiple signatures signed by the same private key. Karati et al. [3–5] present improvements for batch verification of ECDSA signature, but the batch size is bounded by a constant number t\le 9, making it impractical for a large number of signatures. Although there are efficient methods for batch verification of variants of ECDSA [6,7], these non-standard ECDSA signatures either have security issues or are inefficient.

Recently, packing signatures inside SNARK, which is used in zkRollup [8–11], has been an emerging approach to prove the validity of a batch of transactions. The advantage of this approach lies in its ability to support arbitrary signature schemes without restrictions on the algebraic structure. Verifying a signature inside SNARK allows a prover to prove the validity of the signature by running the SNARK protocol and sending a succinct proof to the verifier. The verifier can check the validity of the signature by verifying the SNARK proof instead of running the signature verification algorithm.

However, many SNARKs that are highly efficient in verification often take substantial time and memory resources to generate proofs due to complex computation. For instance, consider the implementation of SNARKs on a virtual machine with 8 cores and 16 GB of RAM, where the actual available memory is about 12.78 GB. If we apply \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n} [12] with \mathsf{B}\mathsf{u}\mathsf{l}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{p}\mathsf{r}\mathsf{o}\mathsf{o}\mathsf{f} commitment [13], which has a fast prover for a batch of ECDSA signatures, the memory consumption grows linearly with the number of signatures. The resulting scheme can support at most about 2^{11} signatures with peak memory usage exceeding 10 GB of RAM. On the other hand, if applying \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} [14] with univariate polynomial \mathsf{K}\mathsf{Z}\mathsf{G} commitment [15], which has a short proof and a fast verifier, it can support only one ECDSA signature, with peak memory usage exceeding 9.76 GB of RAM. Consequently, generating proofs for a large number of signatures within a reasonable timeframe becomes a significant bottleneck for blockchain systems. This resource-intensive process hinders the participation of low-performance devices in batch verification, potentially limiting the scalability and accessibility of blockchain systems.

1.1 Our contributions

To address the aforementioned challenges, we provide a general construction for the batch verification of signatures in blockchain. Our approach takes advantage of the memory-friendliness of incremental verifiable computation (IVC) and the blockchain setting to enhance scalability and reduce memory consumption, making it compatible with common devices and supporting an arbitrary number of signature verifications. Combined with the state-of-the-art folding scheme [16], our construction can achieve a balance between prover/verifier time and proof size, optimizing proof generation efficiency while introducing minimal overhead for verification. Another notable advantage of our approach is that the prover can generate IVC proofs concurrently with receiving signatures from other nodes in a blockchain system. Unlike most existing batch verification schemes that start generating proofs only after collecting enough valid signatures, our approach leverages the incremental nature of IVC to efficiently utilize the waiting time for signatures. This allows for a reduction in the overall block validation time, making it particularly advantageous in low-latency blockchain environments where minimizing delays is crucial.

Our construction is general and can apply to any type of signature. For concrete construction, we present \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} (Batch ECDSA Transaction verification Scheme) for batch verification of the ECDSA signature. In \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S}, we instantiate the SNARK after the IVC by \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n} [12] with \mathsf{B}\mathsf{u}\mathsf{l}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{p}\mathsf{r}\mathsf{o}\mathsf{o}\mathsf{f} [13] commitment, which is transparent without any trusted setup. We implement it on a virtual machine with 8 cores and 16 GB of RAM, and make a comparison with the original construction SNARK {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}}, which invokes the SNARK \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n} [12] with \mathsf{B}\mathsf{u}\mathsf{l}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{p}\mathsf{r}\mathsf{o}\mathsf{o}\mathsf{f} [13] commitment to verify a batch of ECDSA directly. The results of our comparison show that \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} speeds up the prover by 3–17 times and the verifier by 48–240 times when the number of ECDSA signatures is up to 2^{11}. This batch size is the maximum that can be supported by {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}} with 16 GB of RAM. For batch sizes exceeding 2^{10}, our scheme becomes more efficient compared to the baseline approach, which verifies ECDSA signatures one by one without any proof system. Our verifier achieved a speedup of 21–174 times compared to the baseline when the batch size reaches 2^{20}. Notably, even when the baseline approach was optimized for parallelism, our single-threaded scheme outperformed it when the batch size surpassed 2^{13}. The performance gap continued to widen with larger batch sizes, and at 2^{20} signatures, our verifier demonstrated a speedup of 3–30 times. Furthermore, the peak memory usage of \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} grows slowly and stays almost constant at less than 1 GB, which ensures compatibility with most low and mid-range devices.

We also conduct a comparison with a non-transparent SNARK \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} with \mathsf{K}\mathsf{Z}\mathsf{G} polynomial commitment [15], which has a short proof and a fast verifier. Due to the bilinear pairing, the R1CS in \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} should be defined on a pairing-friendly elliptic curve instead of the curve of ECDSA. Therefore, the number of constraints will increase significantly and result in a slower prover and limited scalability. Due to memory limitations, \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} could only support a single ECDSA signature in 16 GB of RAM. When there is only one ECDSA signature, \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} speeds up the prover by 10 times, while the verifier time and the proof size are larger than \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} by about 12 times. However, we improved the scalability significantly that supports an arbitrary number of signatures and the proof size is nearly constant when the batch size is less than 2^{14}. Since \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} needs to generate proofs for multiple signatures separately, the verifier time and proof size of \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} can be amortized efficiently.

Other applications. We present a construction that efficiently verifies a large batch of signatures within a proof system, trading increased prover time for significantly reduced verification complexity. This approach is particularly beneficial for zkRollup applications. Furthermore, our construction has promising applications in image authenticity verification, a critical concern in the era of AI-generated content. Standards like C2PA [17], supported by Adobe, Arm, Intel, Microsoft, and Truepic, advocate for embedding digital signatures within each photograph captured by cameras. When acquiring images from photography platforms, verifying these signatures is crucial to ensure their origin from authentic cameras and to mitigate the risk of AI-generated forgeries. Our scheme offers an efficient solution for verifying the authenticity of a large number of downloaded images.

2 Technique overview

Given a batch of signatures, verifying them inside a SNARK requires transforming the signature verification algorithm into an appropriate arithmetic circuit. In this work, we use the widely studied R1CS constraints system as the arithmetized form. Intuitively, pairing-based SNARK schemes like \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} are well-suited for blockchain applications due to their succinctness. However, applying it to verify concrete signature schemes such as ECDSA presents challenges. Most of the ECDSA verifier’s operations occur on the base field of the elliptic curve \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1} while the R1CS in \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} is defined on the scalar field of pairing-friendly elliptic curves, such as \mathtt{B}\mathtt{L}\mathtt{S}\mathtt{12}\mathtt{\_}\mathtt{381} whose scalar field size is smaller than that of \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1}.

Consequently, it needs to simulate operations on a larger field using a smaller field. It will result in many non-native field operations and lead to a significant increase in the number of constraints. Even worse, the prover’s time and space complexity in \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} is asymptotically O(N\log N), where N is the number of constraints. Since the prover must execute complex computations including Fast Fourier Transformation (FFT) for long high-degree polynomials, the prover cost will limit the number of signatures handled in a batch.

One of our ideas in this work is to use SNARK whose finite field matches that of ECDSA. That is, we represent the ECDSA verification algorithm in R1CS constraints over some elliptic curve whose scalar field is the same as the base field of \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1}. One of the candidate elliptic curves is \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{q}\mathtt{256}\mathtt{k}\mathtt{1} [18]. Since \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{q}\mathtt{256}\mathtt{k}\mathtt{1} is not pairing-friendly, we use \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} under the discrete logarithm hardness assumption without bilinear pairing. This approach is similar to the work [19]. The distinct advantages of {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}} are the fast prover and the succinct proof size. However, using it alone will not achieve the desired high throughput. If applying {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}} to each signature, t proofs would be generated for t signatures. Verifying t proofs may not always be more efficient than verifying t ECDSA signatures. Alternatively, if invoking the {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}} one time to prove a batch of ECDSA, it is hard to support large batch sizes of signatures due to the memory limits.

To compress proof length, reduce verification time, and increase throughput, we propose a folding-based technique for batch verification of signatures. This technique leverages the folding scheme from the IVC protocol Nova [16] to compress t ECDSA signatures into a constant size, independent of t. In our scheme, a batch of signatures is divided into blocks of equal size, and the folding scheme is applied between these blocks. However, the folding scheme in Nova is embedded in an IVC protocol, where the full computation is a chain connected by the inputs and outputs of each step rather than independent sub-computations. If simply applying the folding scheme and proving the folding process step by step, the verifier will only receive the last proof. While the validity of this proof indicates that there exist t valid instances that have been folded, they are not necessarily the t signatures claimed by the prover. In other words, the proven statements may not be consistent with the signatures recorded on the blockchain.

To address this issue, we introduce an additional commitment, which is a chain of collision-resistant hash functions, to bind the statements and construct the IVC chain. Specifically, we have the verifier compute the hash chain locally to ensure the consistency of the signature to be proven. Note that this commitment must also be proven in R1CS, and using hash functions like SHA-256 over an extended binary field will dramatically increase the number of constraints due to the bitwise operations involved. To improve the prover efficiency, we choose the SNARK-friendly hash function \mathsf{P}\mathsf{o}\mathsf{s}\mathsf{e}\mathsf{i}\mathsf{d}\mathsf{o}\mathsf{n} to minimize the prover overhead. Details of the construction can be found in Section 5.2.

We run Nova with the SNARK {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}} on our modified IVC chain. In contrast to verifying each ECDSA signature inside {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}} directly and separately, we package multiple signatures via the folding scheme before executing the SNARK. The prover time for each signature is amortized. Finally, only one IVC proof is produced, independent of the number of signatures. The proof size is O(N+\log N) where N is the number of R1CS constraints of one ECDSA verifier.

Remark (General Arithmetization) In this work, we use the R1CS arithmetized form consistent with the basic implementation of Nova. Note that some variants of Nova can support the Plonkish circuits [20] and even the more general CCS (customizable constraint system) [21], and our scheme also supports these arithmetization methods. To avoid abstract definitions and make it easier to understand, we use the original R1CS-based Nova that is sufficient to describe our construction intuitively. When considering Plonkish circuits, we can get a construction that replaces the \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n} with Plonk, which is a non-transparent SNARK with an updatable CRS.

3 Related work

In the last decade, researchers have designed a lot of distinctive proof systems. The trade-off between the prover and verifier time and proof length has always been a hard task. Known for its constant-size succinctness and efficient verification, SNARK schemes such as [14,22,23] are widely used in blockchain [9–11,24] but are often limited by the size of the circuit because the proof time is too slow. Other proof systems [12,25–28] that do not contain complex computations focus on efficient provers that can generate proofs in optimal linear time about the circuit scale, but either the proof size or the verifier time is at least an order of magnitude higher than above SNARK schemes. A recent work [29] proposes an efficient multilinear polynomial commitment scheme, Basefold, which has a faster prover. They construct SNARK from Basefold and prove a single ECDSA signature takes only 122 ms and verifier time is 24 ms on a server with 256 GB of RAM. However, the proof size is up to 5.5 MB. [30] also proposes a SNARK with a fast prover and a proof size of about 1 MB for ECDSA. They are both much larger than our scheme. When considering a large batch of signatures, even if using the batching techniques in [31], the prover time and verifier time are linear about the number of signatures. Our verifier time is independent of this. Some IVC can be used in Ethereum’s zero-knowledge virtual machines (zkEVMs). But unlike our work, they view the entire block verification process as a virtual machine execution and apply IVC to the computation and memory operations, rather than designing for the specific algorithms. Some projects like [32] use Plonky2 [33] to prove the execution of zkEVM, including verifying ECDSA signatures. However, Plonky2 is not friendly to batch verification, it will be inefficient when proving multiple ECDSA signatures.

To reduce the time and memory requirements of SNARK while maintaining its succinctness and verification efficiency, a new approach involves delegating the complex proving algorithm to powerful devices. A resource-limited prover can simply rent a resource-rich server or distributed computing in a cluster of machines like [34]. However, this will leak the information of the prover to these machines, and it cannot be used for zero-knowledge proof. To protect privacy, [35,36] distributes the secret witness among n>1 parties and uses the MPC protocol to complete the proving algorithm. A drawback of delegating the proof generation to multiple servers is that at least a subset of the servers must be trusted. Garg et al. [37] propose a private delegation with a single server, which is based on the fully homomorphic commitment scheme (FHCom), a heavyweight cryptographic component. They give an analysis of asymptotic complexity without concrete implementation. The delegation scheme gains efficiency entirely due to the higher performance of the servers, each of which executes nearly the same amount of work as the original prover and does not reduce it. Liu et al. [8] construct a distributed Plonk by splitting one large circuit into many small circuits, reducing the computation of each server. The execution of MPC and distributed computations require communication between participants or participants and the delegator or the so-called master node, where network throughput is a critical factor that contributes to the prover time. In this work, we construct a protocol in which low-performance devices can engage locally without delegation.

Recently, several studies have utilized SNARK to construct aggregate signatures, multi-signatures, and threshold signatures [38–40]. In these constructions, the prover only needs to provide SNARK proof for the existence of valid signatures for fixed public keys and public messages, without revealing the signatures to the verifier. Similarly, in some zkRollup designs, transactions are packaged at Layer 2, with metadata sent to Layer 1 along with a SNARK proof verifying the validity of these transactions. This metadata only includes the users’ public keys and the transaction details, omitting the signatures, which helps compress the blockchain size by saving storage space. In this context, signatures are treated as part of the SNARK witness, needing only to prove their existence, so the verifier lacks any information about the signatures. This differs from the batch verification approach considered in this paper, where signatures serve as common inputs for both the prover and verifier. While our scheme can also transfer the signatures to the witness of the IVC and eliminate the need for signature storage, retaining the original signatures of transactions is essential for practical blockchain applications when considering accountability and dispute resolution. For instance, when a user wants to retrieve a historical transaction, they only need to access the relevant transaction and its signature, rather than the entire block (or batch). Furthermore, transaction signatures are crucial for resolving disputed transactions in financial scenarios. Without the original signatures, dispute resolution, audits, and reviews would be significantly more complicated.

4 Preliminaries

4.1 Notation

We use λ as the security parameter and \mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\mathsf{(}\cdot \mathsf{)} as the negligible function. Let \mathbb{F} be the finite field with |\mathbb{F}|=2^{\mathrm{\Theta }(\lambda )}. The bold letter \mathit{a} denote the vector and {\mathit{a}}_i denote the ith element of \mathit{a}. For vector \mathit{a}\in {\mathbb{F}}^m and \mathit{b}\in {\mathbb{F}}^m, \mathit{a}\circ \mathit{b}=(a_1{b}_1,\dots ,a_m{b}_m) is their Hadamard product. [n] represents the set \{1,\dots ,n\}, [a,b] represents integers in the range from a to b.

4.2 Building block

Definition 1 (Non-interactive Argument and SNARK). An argument for a language L is a protocol between the prover \mathcal{P} and verifier \mathcal{V} and consists of a tuple of PPT algorithms (\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}) with the following interface:

− \mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}: On input security parameter \lambda, outputs public parameters \mathsf{p}\mathsf{p}.

− \mathcal{K}(\mathsf{p}\mathsf{p},\mathcal{R})\to (\mathsf{p}\mathsf{k},\mathsf{v}\mathsf{k}): On input public parameters \mathsf{p}\mathsf{p} and the relation \mathcal{R}, outputs proving key \mathsf{p}\mathsf{k} and verifier key \mathsf{v}\mathsf{k}.

− \mathcal{P}(\mathsf{p}\mathsf{k},\mathbb{u},\mathbb{w})\to \pi : On inputs \mathsf{p}\mathsf{p}, instance \mathbb{u} and witness \mathbb{w}, outputs the proof π.

− \mathcal{V}(\mathsf{v}\mathsf{k},\mathbb{u},\pi )\to \{0,1\}: On inputs \mathsf{p}\mathsf{p}, instance \mathbb{u} and proof π, outputs 1 or 0 to indicate accept or reject, respectively.

(\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}) is a non-interactive argument if the communication between the prover \mathcal{P} and verifier \mathcal{V} only includes a proof π.

Let {\mathcal{R}}_L be a relation consists of all instance-witness pairs (\mathbb{u},\mathbb{w}) with \mathbb{u}\in L. A non-interactive argument (\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}) needs to satisfy the following properties:

● Perfect completeness: For any PPT adversary \mathcal{A},

\mathrm{P}\mathrm{r}\left[\begin{array}{ll}\begin{array}{l}\mathrm{\exists }\mathbb{w},\mathrm{s}.\mathrm{t}.(\mathbb{u},\mathbb{w})\in {\mathcal{R}}_L,\\ (\mathsf{p}\mathsf{k},\mathsf{v}\mathsf{k})\leftarrow \mathcal{K}(\mathsf{p}\mathsf{p},{\mathcal{R}}_L),\\ \pi \leftarrow \mathcal{P}(\mathsf{p}\mathsf{k},\mathbb{u},\mathbb{w}),\\ \mathcal{V}(\mathsf{v}\mathsf{k},\mathbb{u},\pi )=1\end{array}& \begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathcal{G}(1^{\lambda }),\\ \mathbb{u}\leftarrow \mathcal{A}(\mathsf{p}\mathsf{p},L),\\ \mathbb{u}\in L\end{array}\end{array}\right]=1.

● Soundness: For any polynomial time adversaries {\mathcal{P}}^{\ast }, for ϵ=\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(\lambda ),

\mathrm{P}\mathrm{r}\left[\begin{array}{ll}\begin{array}{l}\mathcal{V}(\mathsf{v}\mathsf{k},\mathbb{u},\pi )=1,\\ \mathbb{u}\notin L\end{array}& \begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathcal{G}(1^{\lambda }),\\ (\mathbb{u},\pi )\leftarrow {\mathcal{P}}^{\ast }(\mathsf{p}\mathsf{p}),\\ (\mathsf{p}\mathsf{k},\mathsf{v}\mathsf{k})\leftarrow \mathcal{K}(\mathsf{p}\mathsf{p},{\mathcal{R}}_L)\end{array}\end{array}\right]\le ϵ.

We call the non-interactive argument with knowledge-soundness defined as below a non-interactive argument of knowledge (NARK).

● Knowledge-soundness: For any PPT potentially malicious prover {\mathcal{P}}^{\ast }, there exists a polynomial-time extractor \mathcal{E} such that such that for all randomness ρ, for ϵ=\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(\lambda ),

\mathrm{P}\mathrm{r}\left[\begin{array}{ll}\begin{array}{l}\mathcal{V}(\mathsf{v}\mathsf{k},\mathbb{u},\pi )=1,\\ (\mathbb{u},\mathbb{w})\notin {\mathcal{R}}_L\end{array}& \begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathcal{G}(1^{\lambda }),\\ (\mathbb{u},\pi )\leftarrow {\mathcal{P}}^{\ast }(\mathsf{p}\mathsf{p};\rho ),\\ (\mathsf{p}\mathsf{k},\mathsf{v}\mathsf{k})\leftarrow \mathcal{K}(\mathsf{p}\mathsf{p},{\mathcal{R}}_L),\\ \mathbb{w}\leftarrow \mathcal{E}(\mathsf{p}\mathsf{p};\rho )\end{array}\end{array}\right]\le ϵ.

A NARK (\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}) is succinct if the length of the proof π is sublinear to the length of the witness \mathbb{w}, and we call it succinct non-interactive argument of knowledge (SNARK).

Definition 2 (Incrementally Verifiable Computation (IVC)) An incrementally verifiable computation scheme consists of a triple of PPT algorithms (\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}) with the following interface:

− \mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}: On input security parameter \lambda, outputs public parameters \mathsf{p}\mathsf{p}.

− \mathcal{K}(\mathsf{p}\mathsf{p},\mathsf{F})\to (\mathsf{p}\mathsf{k},\mathsf{v}\mathsf{k}): On input public parameters \mathsf{p}\mathsf{p} and a function \mathsf{F}:\{0,1{\}}^a\times \{0,1{\}}^b\to \{0,1{\}}^a, outputs prover and verifier key (\mathsf{p}\mathsf{k},\mathsf{v}\mathsf{k}).

− \mathcal{P}(\mathsf{p}\mathsf{k},(i,z_0,z_i),{\mathsf{a}\mathsf{u}\mathsf{x}}_{i-1},{\mathrm{\Pi }}_{i-1})\to {\mathrm{\Pi }}_i: On input \mathsf{p}\mathsf{k}, an index i\in {\mathbb{N}}^{\ast }, the input z_0\in \{0,1{\}}^a with optional advice {\mathsf{a}\mathsf{u}\mathsf{x}}_{i-1}\in \{0,1{\}}^b and a claimed output z_i\in \{0,1{\}}^a, an IVC proof {\mathrm{\Pi }}_{i-1}, outputs the updated IVC proof {\mathrm{\Pi }}_i.

− \mathcal{V}(\mathsf{v}\mathsf{k},(i,z_0,z_i),{\mathrm{\Pi }}_i)\to \{0,1\}: On input \mathsf{v}\mathsf{k}, an index i\in {\mathbb{N}}^{\ast }, the input z_0\in \{0,1{\}}^a and a claimed output z_i\in \{0,1{\}}^a, an IVC proof {\pi }_i, outputs 1 or 0 to indicate accept or reject, respectively.

An IVC scheme (\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}) satisfies perfect completeness if for any PPT adversary \mathcal{A}:

\begin{array}{rl}\mathrm{P}\mathrm{r}& [\begin{array}{l}\mathcal{V}(\mathsf{v}\mathsf{k},(i+1,z_0,z_{i+1}),{\mathrm{\Pi }}_{i+1})=1\end{array}\\ & \overline{)\begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathcal{G}(1^{\lambda }),\\ (\mathsf{F},i,z_0,z_i,{\mathsf{a}\mathsf{u}\mathsf{x}}_i,{\mathrm{\Pi }}_i)\leftarrow \mathcal{A}(\mathsf{p}\mathsf{p}),\\ (\mathsf{p}\mathsf{k},\mathsf{v}\mathsf{k})\leftarrow \mathcal{K}(\mathsf{p}\mathsf{p},\mathsf{F}),\\ z_{i+1}=\mathsf{F}(z_i,{\mathsf{a}\mathsf{u}\mathsf{x}}_i),\\ \mathcal{V}(i,z_0,z_i,{\mathrm{\Pi }}_i)=1,\\ {\mathrm{\Pi }}_{i+1}\leftarrow \mathcal{P}(\mathsf{p}\mathsf{k},(i+1,z_0,z_{i+1}),{\mathsf{a}\mathsf{u}\mathsf{x}}_i,{\mathrm{\Pi }}_i)\end{array}}]=1.\end{array}

An IVC scheme (\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}) satisfies knowledge-soundness if for any constant n\in {\mathbb{N}}^{\ast }, and PPT potentially malicious prover {\mathcal{P}}^{\ast }, there exists a polynomial-time extractor \mathcal{E} such that for all randomness ρ, for ϵ=\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(\lambda ),

\mathrm{P}\mathrm{r}\left[\begin{array}{ll}\begin{array}{l}{z}_n\ne z,\\ \mathcal{V}(\mathsf{p}\mathsf{p},z_0,z,\mathrm{\Pi })=1\end{array}& \begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathcal{G}\left(1^{\lambda }\right),\\ (\mathsf{F},z_0,z,\mathrm{\Pi })\leftarrow {\mathcal{P}}^{\ast }(\mathsf{p}\mathsf{p},\rho ),\\ (\mathsf{p}\mathsf{k},\mathsf{v}\mathsf{k})\leftarrow \mathcal{K}(\mathsf{p}\mathsf{p},\mathsf{F}),\\ ({\mathsf{a}\mathsf{u}\mathsf{x}}_i{)}_{i=0}^{n-1}\leftarrow \mathcal{E}(\mathsf{p}\mathsf{p};\rho ),\\ \mathrm{\forall }i\in [n]:\\ z_i\leftarrow \mathsf{F}\left(z_{i-1},{\mathsf{a}\mathsf{u}\mathsf{x}}_{i-1}\right)\end{array}\end{array}\right]\le ϵ.

Definition 3 (Commitment Scheme). A commitment scheme is a pair of PPT algorithms (\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p},\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{m}\mathsf{i}\mathsf{t}) with the following interface:

− \mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^{\lambda })\to \mathsf{p}\mathsf{p}: On input security parameter λ, outputs public parameter \mathsf{p}\mathsf{p}.

− \mathsf{C}\mathsf{o}\mathsf{m}\mathsf{m}\mathsf{i}\mathsf{t}(\mathsf{p}\mathsf{p},m)\to c: On input public parameter \mathsf{p}\mathsf{p} and the message m\in \mathbb{F}, outputs a commitment c.

The Commitment scheme in this work needs to satisfy the following properties:

● Binding: for any PPT adversary \mathcal{A} and ϵ=\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(\lambda ),

\mathrm{P}\mathrm{r}\left[\begin{array}{ll}\begin{array}{l}{m}_0\ne m_1\wedge \\ \mathsf{C}\mathsf{o}\mathsf{m}\mathsf{m}\mathsf{i}\mathsf{t}(\mathsf{p}\mathsf{p},m_0)\\ =\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{m}\mathsf{i}\mathsf{t}(\mathsf{p}\mathsf{p},m_1)\end{array}& \begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}\left(1^{\lambda }\right),\\ (m_0,m_1)\leftarrow \mathcal{A}(\mathsf{p}\mathsf{p})\end{array}\end{array}\right]\le ϵ.

● Additively homomorphic: Given two commitments c_0,c_1 respect to message m_0,m_1, it must hold that c_0+c_1= \mathsf{C}\mathsf{o}\mathsf{m}\mathsf{m}\mathsf{i}\mathsf{t}(\mathsf{c}\mathsf{k},m_0+m_1).

Another property of the commitment scheme is called hiding, which requires that the commitment itself does not reveal any information about the committed value. The commitment scheme usually commits to a message with randomness to satisfy the hiding property. For simplicity, the randomness in the commitment is omitted in this work. Note that we aim to generate proofs for public signatures without using secret inputs and the hiding property is not necessary for the commitment in our scheme. In particular, the concrete instantiation of our commitment does not need to take randomness as input.

Definition 4 (Hash Functions) A hash function on \mathbb{F} is a pair of efficient algorithms (\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p},\mathsf{H})

− \mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^{\lambda })\to \mathsf{p}\mathsf{p}: On input security parameter λ, outputs public parameters \mathsf{p}\mathsf{p}.

− \mathsf{H}(\mathsf{p}\mathsf{p},m)\to h: On inputs public parameters \mathsf{p}\mathsf{p} and message m\in \{0,1{\}}^{\ast }, outputs a hash value h\in \mathbb{F}.

● Collision-resistant: A hash function is collision-resistant if for every efficient adversary \mathcal{A} and ϵ=\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(\lambda ),

\mathrm{P}\mathrm{r}\left[\begin{array}{ll}\begin{array}{l}\mathsf{H}(\mathsf{p}\mathsf{p},m_0)=\mathsf{H}(\mathsf{p}\mathsf{p},m_1)\\ \wedge m_0\ne m_1\end{array}& \begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}\left(1^{\lambda }\right)\\ (m_0,m_1)\leftarrow \mathcal{A}(\mathsf{p}\mathsf{p})\end{array}\end{array}\right]\le ϵ.

● Zero-testing: Let \mathsf{C}\mathsf{o}\mathsf{m}\mathsf{m}\mathsf{i}\mathsf{t} be the commit algorithm of a commitment scheme that has the binding property, and \mathsf{P}:\mathbb{F}\to {\mathbb{F}}^d[X] be a deterministic function that maps a field element to a polynomial with degree d=\mathcal{O}(\lambda ). A hash function has the general zero testing property if for every PPT adversary \mathcal{A}, for ϵ=\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(\lambda ),

\mathrm{P}\mathrm{r}\left[\begin{array}{ll}\begin{array}{l}h\leftarrow \mathsf{H}(\mathsf{p}\mathsf{p},\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{m}\mathsf{i}\mathsf{t}(\mathsf{p}\mathsf{p},p)),\\ \mathsf{P}(p)(h)=0\end{array}& \begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}\left(1^{\lambda }\right),\\ p\leftarrow \mathcal{A}(\mathsf{p}\mathsf{p})\end{array}\end{array}\right]\le ϵ.

Definition 5 (Committed Relaxed R1CS). Let \mathbb{F} denotes a finite field, consider the parameters m,\ell \in \mathbb{N} where m>\ell. A committed relaxed R1CS instance is a tuple \mathbb{U}=(\overline{E},s,\overline{W},x), where s\in \mathbb{F},x\in {\mathbb{F}}^{\ell }, and \overline{E} and \overline{W} are commitments to E\in {\mathbb{F}}^m and W\in {\mathbb{F}}^{m-\ell -1}. A committed relaxed R1CS instance \mathbb{U}=(\overline{E},s,\overline{W},x) is satisfiable with respect to the structure \mathsf{s}=(A,B,C) if there exist a relaxed witness \mathbb{W}=(E,W) such that (\mathbb{U},\mathbb{W})\in {\mathcal{R}}_{\mathsf{s}}, where the committed relaxed R1CS relation {\mathcal{R}}_{\mathsf{s}} is defined by

{\mathcal{R}}_{\mathsf{s}}:=\left\{\begin{array}{l}\left(\mathbb{U},\mathbb{W}\right):\begin{array}{l}\overline{E}=\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{m}\mathsf{i}\mathsf{t}({\mathsf{p}\mathsf{p}}_{\mathsf{E}},E),\\ \overline{W}=\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{m}\mathsf{i}\mathsf{t}({\mathsf{p}\mathsf{p}}_{\mathsf{W}},W),\\ Z=(W,x,s),\\ A\cdot Z\circ B\cdot Z=s\cdot (C\cdot Z)+E\end{array}\end{array}\right\}.

There are at most k=\mathrm{\Omega }(m) non-zero elements in each of the matrix A,B,C\in {\mathbb{F}}^{m\times m}. When setting s=1,\overline{E}=\overline{\mathbf{0}}, the committed relaxed R1CS instance is a standard R1CS instance, where the constraint equation is defined as A\cdot Z\circ B\cdot Z=C\cdot Z.

As explained in Definition 3, unlike Nova, the randomness of the commitment in this work is omitted.

Definition 6 (Folding Scheme). A folding scheme for committed relaxed R1CS consists of a tuple of algorithms (\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}):

− \mathcal{G}(1^{\lambda })\to \mathsf{p}\mathsf{p}: On input security parameter λ, outputs public parameters \mathsf{p}\mathsf{p}.

− \mathcal{K}(\mathsf{p}\mathsf{p},\mathsf{s})\to \mathsf{p}\mathsf{k}: On inputs public parameters \mathsf{p}\mathsf{p}, a common structure \mathsf{s}, outputs proving key \mathsf{p}\mathsf{k}.

− \mathcal{P}(\mathrm{p}\mathrm{k},(\mathbb{U},\mathbb{W}),(\mathbb{u},\mathbb{w}))\to (\overline{T},({\mathbb{U}}^{\prime }\mathbb{,}{\mathbb{W}}^{\prime })): On inputs proving key \mathsf{p}\mathsf{k}, two committed relaxed R1CS instance-witness pair (\mathbb{U}\mathbb{,}\mathbb{W}),(\mathbb{u}\mathbb{,}\mathbb{w}), outputs a folded committed relaxed R1CS instance-witness pair ({\mathbb{U}}^{\prime }\mathbb{,}{\mathbb{W}}^{\prime }) with a folding proof \overline{T}.

− \mathcal{V}(\mathsf{p}\mathsf{p},\mathbb{U}\mathbb{,}\mathbb{u},\overline{T})\to {\mathbb{U}}^{\prime }: On inputs public parameters \mathsf{p}\mathsf{p}, two committed relaxed R1CS instance \mathbb{U}\mathbb{,}\mathbb{u}, and a folding proof \overline{T}, outputs a folded committed relaxed R1CS instance {\mathbb{U}}^{\prime }.

A folding scheme satisfies perfect completeness if for all PPT adversaries \mathcal{A},

\mathrm{P}\mathrm{r}\left[\begin{array}{ll}\begin{array}{l}{\mathbb{U}}^{\prime }={\mathbb{U}}^{″},\\ ({\mathbb{U}}^{\prime },{\mathbb{W}}^{\prime })\in {\mathcal{R}}_{\mathsf{s}}\end{array}& \begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathcal{G}\left(1^{\lambda }\right),\\ ((\mathbb{U},\mathbb{W}),(\mathbb{u},\mathbb{w}))\leftarrow \mathcal{A}(\mathsf{p}\mathsf{p}),\\ (\mathbb{U},\mathbb{W})\in {\mathcal{R}}_{\mathsf{s}},(\mathbb{u},\mathbb{w})\in {\mathcal{R}}_{\mathsf{s}},\\ \mathsf{p}\mathsf{k}\leftarrow \mathcal{K}(\mathsf{p}\mathsf{p},\mathsf{s}),\\ (\overline{T},{\mathbb{U}}^{\prime },{\mathbb{W}}^{\prime }),\\ \leftarrow \mathcal{P}(\mathsf{p}\mathsf{k},(\mathbb{U}\mathbb{,}\mathbb{W}),(\mathbb{u}\mathbb{,}\mathbb{w})),\\ {\mathbb{U}}^{″}\leftarrow \mathcal{V}(\mathsf{p}\mathsf{p},\mathbb{U},\mathbb{u},\overline{T})\end{array}\end{array}\right]=1.

A folding scheme satisfies knowledge soundness if for any PPT potentially malicious {\mathcal{P}}^{\ast } and ϵ=\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(\lambda ), there is a PPT extractor \mathcal{E} such that

\begin{array}{l}\mathrm{P}\mathrm{r}\left[\begin{array}{ll}\begin{array}{l}(\mathbb{U},\mathbb{W})\in {\mathcal{R}}_{\mathsf{s}},\\ (\mathbb{u},\mathbb{w})\in {\mathcal{R}}_{\mathsf{s}}\end{array}& \begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathcal{G}\left(1^{\lambda }\right),\\ (\mathsf{s},\mathbb{U},\mathbb{u})\leftarrow {\mathcal{P}}^{\ast }(\mathsf{p}\mathsf{p},\rho ),\\ (\mathbb{w},\mathbb{W})\leftarrow \mathcal{E}(\mathsf{p}\mathsf{p},\rho )\end{array}\end{array}\right]\ge \\ \mathrm{P}\mathrm{r}\left[\begin{array}{ll}\begin{array}{l}({\mathbb{U}}^{\prime },{\mathbb{W}}^{\prime })\in {\mathcal{R}}_{\mathsf{s}}\end{array}& \begin{array}{l}\mathsf{p}\mathsf{p}\leftarrow \mathcal{G}\left(1^{\lambda }\right),\\ (\mathsf{s},\mathbb{U},\mathbb{u})\leftarrow {\mathcal{P}}^{\ast }(\mathsf{p}\mathsf{p},\rho ),\\ \mathsf{p}\mathsf{k}\leftarrow \mathcal{G}(\mathsf{p}\mathsf{p},\mathsf{s}),\\ (\overline{T},{\mathbb{U}}^{\prime },{\mathbb{W}}^{\prime })\leftarrow {\mathcal{P}}^{\ast }(\mathsf{p}\mathsf{k},\rho ),\\ {\mathbb{U}}^{\prime }\leftarrow \mathcal{V}(\mathsf{v}\mathsf{k},\mathbb{U},\mathbb{u},\overline{T})\end{array}\end{array}\right]-ϵ.\end{array}

Let \mathsf{H} denote the Hash function in Denifition 4, which satisfies the collision-resistant property and general zero testing property. A folding scheme (\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}) is non-interactive if the communication between \mathcal{P} and \mathcal{V} only includes a proof \overline{T}, and the randomness r used to generate the outputs is computed as \mathsf{H}(\mathsf{v}\mathsf{k},\mathbb{U},\mathbb{u},\overline{T}) by \mathcal{P} and \mathcal{V} locally.

Definition 7 (Digital Signature in Hash-and-Sign Paradigm) A digital signature scheme consists of a tuple of PPT algorithms ({\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}}_{\mathsf{s}\mathsf{i}\mathsf{g}},{\mathsf{G}\mathsf{e}\mathsf{n}}_{\mathsf{s}\mathsf{i}\mathsf{g}},\mathsf{S}\mathsf{i}\mathsf{g}\mathsf{n},\mathsf{V}\mathsf{e}\mathsf{r}\mathsf{i}\mathsf{f}\mathsf{y}), which are defined as follows.

− \mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{p}\mathsf{p}): On input public parameters, outputs a keypair (sk,pk).

− \mathsf{S}\mathsf{i}\mathsf{g}\mathsf{n}(sk,m)\to \sigma : On input a signing key \mathsf{s}\mathsf{k} and a message m, outputs the σ as signature of m.

− \mathsf{V}\mathsf{e}\mathsf{r}\mathsf{i}\mathsf{f}\mathsf{y}(pk,\sigma ,m)\to \{0,1\}: On input a signature σ with its message m and public key pk, outputs 1 or 0 to indicate whether the signature passes the verification or not.

Given a hash function \mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h} with collision-resistant property, if the algorithm \mathsf{S}\mathsf{i}\mathsf{g}\mathsf{n} and \mathsf{V}\mathsf{e}\mathsf{r}\mathsf{i}\mathsf{f}\mathsf{y} are executed as the following process, the digital signature scheme is in the hash-and-sign paradigm.

− \mathsf{S}\mathsf{i}\mathsf{g}\mathsf{n}(sk,m)\to \sigma : On input a signing key \mathsf{s}\mathsf{k} and a message m, computes that

● e\leftarrow \mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}(m),

● \sigma \leftarrow {\mathsf{S}\mathsf{i}\mathsf{g}\mathsf{n}}^{\prime }(sk,e).

− \mathsf{V}\mathsf{e}\mathsf{r}\mathsf{i}\mathsf{f}\mathsf{y}(pk,\sigma ,m)\to \{0,1\}: On input a signature σ with its message m and public key pk,

● e\leftarrow \mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}(m),

● \{0,1\}\leftarrow {\mathsf{V}\mathsf{e}\mathsf{r}\mathsf{i}\mathsf{f}\mathsf{y}}^{\prime }(pk,e).

The algebraic group model (AGM). In the algebraic group model, AGM [41], an algebraic adversary should output a representation vector whenever it outputs a group element in terms of all the group elements that have been seen by the adversary so far. We use capital letter X to denote a group element, let (G_1,\dots ,G_k) be all group elements known to the adversary, \mathit{x} is the corresponding representation vector of X such that X=\sum _{i=1}^k{\mathit{x}}_i{G}_i.

Refined AGM for Nova. To cover the situations in Nova, a refined AGM was introduced in [42] that proposes three requirements:

(1) All group elements in the input of the algebraic adversary are common random strings.

(2) Adversarial algorithms are non-interactive and cannot obtain any additional information by querying.

(3) Pre-declared multiple encodings are allowed and the adversary should output all relevant representation vectors. In particular, when the adversary outputs a represent vector \mathit{a} of group element A, if a group element B is embedded in \mathit{a} by another encoding way, the algebraic adversary should output the representation vector \mathit{b} of B as well.

4.3 Overview of Nova

Consider an IVC statement as shown in Fig.1. For a function \mathsf{F}:{\mathbb{F}}^{a\times b}\to {\mathbb{F}}^a, there exist auxiliary inputs ({\mathsf{a}\mathsf{u}\mathsf{x}}_0,\dots ,{\mathsf{a}\mathsf{u}\mathsf{x}}_{n-1}) such that

\mathsf{F}(\dots \mathsf{F}(\mathsf{F}(z_0,{\mathsf{a}\mathsf{u}\mathsf{x}}_0),{\mathsf{a}\mathsf{u}\mathsf{x}}_1)\dots ,{\mathsf{a}\mathsf{u}\mathsf{x}}_{n-1})=z_n.

To prove this statement, the function \mathsf{F} will be arithmetized as some committed relaxed R1CS constraints by the IVC prover and verifier before running the Nova IVC scheme [16] iteratively. For i\in [n], in the ith iteration, the prover claims that the i-th step is evaluated correctly, i.e., \mathsf{F}(z_i,{\mathsf{a}\mathsf{u}\mathsf{x}}_i)=z_{i+1}, and all the previous i-1 steps are also evaluated correctly, i.e.,

\mathsf{F}(\dots (\mathsf{F}(\mathsf{F}(z_0,{\mathsf{a}\mathsf{u}\mathsf{x}}_0),{\mathsf{a}\mathsf{u}\mathsf{x}}_1),\dots ),{\mathsf{a}\mathsf{u}\mathsf{x}}_{i-1})=z_i.

As shown in Fig.2, in the ith iteration, a folding scheme is invoked to fold the current instance {\mathbb{u}}_i into a folded instance {\mathbb{U}}_i that will be updated to {\mathbb{U}}_{i+1}. In addition, a new instance {\mathbb{u}}_{i+1} is introduced to represent the execution of the step function and the folding process. Precisely, the instance {\mathbb{u}}_{i+1} is a standard R1CS instance arithmetizing the trace of an augment function F^{\prime }, which includes computing \mathsf{F}(z_i,{\mathsf{a}\mathsf{u}\mathsf{x}}_i)=z_{i+1}, generating {\mathbb{U}}_{i+1} and checking some consistency between two neighboring iterations by a hash function \mathsf{H}. The satisfiability of {\mathbb{u}}_{i+1} implies the computation from z_i to z_{i+1} and the folding process for getting {\mathbb{U}}_{i+1} are correctly executed. The instance {\mathbb{U}}_{i+1} is a committed relaxed R1CS instance, and its satisfiability implies the satisfiability of the instance of {\mathbb{U}}_i and {\mathbb{u}}_i, which further implies the correctness of the computation from z_0 to z_i by recursion. The hash function \mathsf{H} can be seen as a binding commitment to z_i, the consistency between the current input and last output is checked by it in the instance {\mathbb{u}}_i. Therefore, the correctness of the IVC statement can be delayed until the end to be checked.

Nova on cycle of elliptic curves. Let E_1,E_2 represent two elliptic curves that satisfy the “cyclic” property. More precisely, the base field {\mathbb{F}}_p of E_1 is exactly the scalar field of E_2, and the base field {\mathbb{F}}_q of E_2 is exactly the scalar field of E_1.

In the actual structure, due to the need for additive homomorphism in the folding scheme, the commitment scheme in the R1CS instance is realized by the Pedersen vector commitment, which is defined over elliptic curve groups. Note that operations on the elliptic curve’s base field dominate the folding scheme’s verification algorithm, while the R1CS constraints are specified on its scalar field. If one describes the verification algorithm of the folding scheme on the scalar field directly, it will lead to many operations on the non-native field that incur a lot of R1CS constraints. An innovative approach in the implementation of Nova [43] is using a cycle of elliptic curves, the correctness of the folding scheme on one curve can be checked on another curve. Precisely, the folding scheme is executed on both elliptic curves E_1 and E_2 while the step function \mathsf{F} is represented only on one elliptic curve, without loss of generality, E_1. The folding scheme verifier on E_1 is represented as R1CS constraints over the scalar field {\mathbb{F}}_p of the curve E_2, while the folding scheme verifier on E_2 is represented as R1CS constraints over the scalar field {\mathbb{F}}_q of E_1.

In the original Nova, operations on two curves are switched in a crossover manner, finally, the IVC protocol outputs a proof consisting of 4 instance-witness pairs. Nguyen et al. [44] found security problems with such an implementation and proposed the refined Nova, where the operations on the two elliptic curves are performed in alternating order, ultimately generating 3 instance-witness pairs as the IVC proof.

Compress with SNARK. If one wants to check the correctness of the computation of the first i iterations of the IVC scheme, one can easily run the IVC verifier on the IVC proof of the ith iteration, which results in a slower verification. In Nova, a SNARK protocol is introduced additionally at the end of the IVC, making it sufficient to check the validity of the succinct proofs of the SNARK. This compression process with SNARK is implemented by \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}, which in fact can be replaced by any appropriate SNARK with a commitment scheme that satisfies the requirements of the folding scheme. Due to the concrete efficiency requirements in practice.

In addition to the efficiency benefits, compressing with SNARK at the end of the IVC chain also serves some security purposes. As mentioned in [44], there may exist a malleability attack in Nova IVC when the step function is non-deterministic. Adding a SNARK protocol with zero-knowledge property can prevent this attack by hiding auxiliary inputs from the adversary, as long as the zkSNARK is simulation extractable. Looking ahead, since the step function in our scheme is deterministic, we do not require the zero-knowledge property and the attack in [44] cannot apply to our scheme.

5 Batch verification of ECDSA in Nova

In this section, we present a general construction for batch verification of signatures based on the Nova IVC scheme. We optimize the instantiation and construct a transparent scheme \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} for batch verification of ECDSA. Before introducing our construction, we show a simple attempt and its security problem in Section 5.1. We argue that a regular IVC scheme cannot support batch verification of signatures.

5.1 A simple attempt

As mentioned in Section 2, applying the folding scheme directly and proving the folding process cannot guarantee the consistency of the signatures claimed by the prover and those received by the verifier. To achieve consistency, a hash function can be added as in Fig.2 for checking the equality of instances between two neighboring steps, as shown in Fig.3. Symbol definitions of Fig.3 are the same as in Fig.2. “=1” in step i means z_i will be set to 1 when running the hash function \mathsf{H} to check the equivalence. The blue font indicates the state implied if the statements in the box above it are true. We treat the output of \mathsf{F} as a variable, denoted by z. In addition to running the verification algorithm of the signature, the function \mathsf{F} checks the correctness of the previous step. For each i\in [n], z_i=1 if and only if \mathsf{V}\mathsf{e}\mathsf{r}\mathsf{i}\mathsf{f}\mathsf{y}(p{k}_i,{\sigma }_i,m_i)=1 and z_{i-1}=1.

After building the connection, we find that the construction is equivalent to the IVC chain in Fig.4. In the IVC construction, the prover should prove the computation of \mathsf{F}(\dots \mathsf{F}(\mathsf{F}(z_0,y_0),y_1)\dotsy_{n-1})=z_n. Since the function \mathsf{F} is a common parameter and z_0=z_n=1 is the public instance, the IVC statement will be accepted if the IVC proof passes the verification. Thus all n executions of the function \mathsf{F} are correct, which implies that all n signatures are valid.

However, in the IVC context, each y_i is the auxiliary input of \mathsf{F}, which is not explicitly sent to the verifier. An important fact is that auxiliary inputs are non-deterministic and not unique. In applications such as blockchain transactions where the verifier must receive all signatures, each y_i must be public and deterministic. The construction in Fig.3 only claims that the prover knows some valid signature triples (p{k}_0^{\ast },{\sigma }_0^{\ast },m_0^{\ast }),\dots ,(p{k}_n^{\ast },{\sigma }_n^{\ast },m_n^{\ast }) if there are n steps in total. Still, these n signatures may not be consistent with the n signatures (p{k}_0,{\sigma }_0,m_0),\dots ,(p{k}_n,{\sigma }_n,m_n) sent to the verifier in advance. So a malicious prover can send a batch of invalid signatures and instead generate proofs using some trivial valid signatures, such as (p{k}^{\ast },{\sigma }^{\ast },\mathbf{0}) where the p{k}^{\ast } is the public key of the prover who naturally knows its private key p{k}^{\ast }, thereby tricking the verifier without attacking against the unforgeability of the signature scheme. In blockchain, this attack will lead to fake transactions, so we must ensure the consistency of the verified signatures between the prover and verifier.

5.2 Batch verification of signature in Nova

We first propose a general IVC-based construction for batch verification of arbitrary digital signatures. Suppose the prover has verified all signatures at the beginning of the protocol and sent the valid ones among them to the verifier. In Section 5.1 for simplicity, we use the function \mathsf{F} to represent only one signature verification. In fact, multiple signatures can be contained in one step of the IVC, where the concrete efficiency depends on the number of signatures in each step.

Suppose that the verifier receives t\in {\mathbb{N}}^{\ast } signatures in total. The t signatures will be divided into n=\lceil \frac{t}{b}\rceil blocks, where b\in \{1,\dots ,t\} is the block size that describes the number of signatures in a block. Each step of the IVC handles one block so that n is the number of steps of IVC. For each i\in [n], we set the input to each \mathsf{F} is a vector {\mathit{y}}_i={\left[\left(p{k}_{i,j},{\sigma }_{i,j},m_{i,j}\right)\right]}_{j\in [b]}. Let {\mathit{z}}_i denote the output vector of \mathsf{F}, which indicates the verification result of the signatures in {\mathit{y}}_i. The description of \mathsf{F}:{\mathbb{F}}^a\to {\mathbb{F}}^b where |{\mathit{y}}_i|=a,|{\mathit{z}}_i|=|{\mathbf{1}}^b|=b is public.

The main idea of our construction is depicted in Fig.5. Instead of taking \mathsf{F} as a step function in IVC simply, we introduce an additional collision-resistant hash function \mathsf{H}:\{0,1{\}}^{\ast }\to \mathbb{F}. In the naïve construction in Section 5.1, since each input {\mathit{y}}_i is the auxiliary input and {\mathit{z}}_i as an intermediate value will not be sent to the verifier, the function \mathsf{F} is treated as a non-deterministic function. It fails to work in the context of verifying deterministic signatures. We use hash function \mathsf{H} as a commitment to these non-deterministic inputs and outputs, and the binding property relies on the collision resistance of the hash function. We initialize h_0 to a public value, and then sequentially take {\mathit{y}}_i and {\mathit{z}}_i as input to \mathsf{H} like the Merkle-Damgard structure until h_n is output as the resulting commitment. In applications such as blockchain, it is not enough for the prover only to send the commitment to the signatures and then apply a probabilistic proof protocol. Since the verifier can access all these signatures, the verifier must also compute the commitment. Finally, all hash values are connected into an IVC chain as Fig.1, where the statement is that h_i=\mathsf{H}\left(h_{i-1},{\mathit{y}}_{i-1},\mathsf{F}({\mathit{y}}_{i-1})\right) for all i\in [n].

We modify the scheme proposed in [16] to obtain the formal description of the IVC scheme. Compared to the original definition, we view \mathsf{H}\circ \mathsf{F} as a composite function. In the i-th step of IVC, the prover computes and proves an augment function F^{\prime } shown in Fig.6. The modified IVC scheme is shown in Fig.7. \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S} shown in Fig.8 denotes the non-interactive folding scheme in Definition 6. Let \mathsf{t}\mathsf{r}\mathsf{a}\mathsf{c}\mathsf{e} denote the execution of the augment function F^{\prime }, which can be represented as a committed relaxed R1CS with structure {\mathsf{s}}_{F^{\prime }}. The instance-witness pair (\mathbb{u},\mathbb{w}) describes the trace of F^{\prime } in each step of IVC. First, F^{\prime } executes the step function \mathsf{H}\circ \mathsf{F} on h_{i-1},{\mathit{y}}_{i-1} to obtain the incremental computation result h_i=\mathsf{H}(h_{i-1},{\mathit{y}}_{i-1},\mathsf{F}({\mathit{y}}_{i-1})). Second, F^{\prime } runs the verifier of \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S} to fold two committed relaxed R1CS instances {\mathbb{U}}_i and {\mathbb{u}}_i into a new instance {\mathbb{U}}_{i+1}. Then the IVC prover generates {\mathbb{u}}_{i+1} to describe the trace of the ith invocation of the augment function F^{\prime }. The instance {\mathbb{u}}_{i+1} claims the correctness of \mathsf{H}\circ \mathsf{F} and folding process in the ith step.

We provide our full protocol (\mathcal{G},\mathcal{K},\mathcal{P},\mathcal{V}) for batch signature verification in Fig.9. Similarly, we assume that the prover has sent the signature information \mathit{y}=[{\mathit{y}}_{i,j}{]}_{i\in [n],j\in [b]} to the verifier and claims that all these signatures are valid, i.e., \mathrm{\forall }i\in [n],j\in [b],\mathsf{F}({\mathit{y}}_{i,j})={\mathit{z}}_{i,j}=1, which implies that \mathit{z}=[{\mathit{z}}_{i,j}{]}_{i\in [n],j\in [b]}={\mathbf{1}}^t. Firstly, the prover computes the hash chain with length n to obtain the commitment h_n. Then the prover runs the IVC prover for the IVC chain in 5 to generate an IVC proof Π. Due to the large proof size, instead of running the IVC verifier, the SNARK prover \mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{P} will be invoked on the folded IVC proof. After receiving a proof from the prover, the verifier checks the commitment by comparing the h_n from the prover and h that is computed locally on \mathit{y} and \mathit{z}, where \mathit{z} is set to {\mathbf{1}}^t to enforce the prover can only prove valid signatures. Then the verifier runs the folding scheme verifier \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}\mathsf{.}\mathsf{V} and the SNARK verifier \mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K}\mathsf{.}\mathsf{V} on the folded IVC instance. If all conditions are met, the verifier accepts the statement, which implies all received signatures are valid.

5.3 Batch verification of ECDSA

Intuitively, we can apply the protocol in Fig.9 to the batch verification of ECDSA by setting the function \mathsf{F} as the verification of ECDSA. Although this protocol is general for arbitrary signature schemes, the selection of parameters and realization of some functionalities may affect the efficiency in practical applications.

5.3.1 Optimizations on frontend implementation

The standard ECDSA signature [45] is shown in Fig.10. The process of compiling the verification algorithm to an arithmetic representation such as R1CS is often called the frontend of the protocol. The frontend efficiency plays an important role in the overall proving process, and it is measured by the size of the arithmetic representation, which in this work refers to the number of R1CS formed constraints.

Hash functions. Since the hash function \mathsf{H} is a part of the step function in the IVC statement, it needs to be arithmetized as R1CS defined over a large field that the commitment scheme and SNARK protocol defined on. To reduce the number of constraints, we use the SNARK-friendly Hash function, \mathsf{P}\mathsf{o}\mathsf{s}\mathsf{e}\mathsf{i}\mathsf{d}\mathsf{o}\mathsf{n} [46], to instantiate it. Similarly, the folding scheme verification algorithm as shown in Fig.2 will also be proven in R1CS, so we can also use \mathsf{P}\mathsf{o}\mathsf{s}\mathsf{e}\mathsf{i}\mathsf{d}\mathsf{o}\mathsf{n} to generate the randomness in the \mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S} as long as it satisfies the general zero testing property in Definition 4. Since the \mathsf{P}\mathsf{o}\mathsf{s}\mathsf{e}\mathsf{i}\mathsf{d}\mathsf{o}\mathsf{n} is used as a random oracle in the original non-interactive folding scheme in Nova, it can be deduced that \mathsf{P}\mathsf{o}\mathsf{s}\mathsf{e}\mathsf{i}\mathsf{d}\mathsf{o}\mathsf{n} has the general zero-testing property in the AGM According to Lemma 1.

Lemma 1 ([42]). The random oracle has the zero-testing property.

Notice that the hash function \mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h} in ECDSA is instantiated by Keccak-256 in many blockchain applications. Applying the general protocol in Fig.9 on the function \mathsf{E}\mathsf{C}\mathsf{D}\mathsf{S}\mathsf{A}\mathsf{.}\mathsf{V}\mathsf{e}\mathsf{r}\mathsf{i}\mathsf{f}\mathsf{y} requires to compile the Keccak-256 defined over the expansion of binary field {\mathbb{F}}_2 as constraints over a large field {\mathbb{F}}_p, which will significantly increase the size of the R1CS.

In the SNARK scheme, the verifier must compute the local commitment to the public inputs, which include the signed messages in this work. Furthermore, as Keccak-256 can be evaluated very efficiently on the CPU, it is not necessary for the verifier to delegate this computation to the prover. Therefore, for a batch of signatures in the hash-and-sign paradigm, we replace the message m_{i,j} in the input {\mathit{y}}_i of \mathsf{F}\circ \mathsf{H} with its digest e_{i,j}=\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}(m_{i,j}), and the function \mathsf{F} is changed to {\mathsf{V}\mathsf{e}\mathsf{r}\mathsf{i}\mathsf{f}\mathsf{y}}^{\prime } which is the part of \mathsf{V}\mathsf{e}\mathsf{r}\mathsf{i}\mathsf{f}\mathsf{y} in Fig.10 except for the step 2.

Elliptic curve. The standard ECDSA is defined on the elliptic curve \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1}, denoted E_1. Let {\mathbb{F}}_p denote its base field and {\mathbb{F}}_q denote its scalar field. When considering verifying the ECDSA inside a proof system, we usually represent the evaluation of the verification process as R1CS constraints over a finite field \mathbb{F}. Due to the group-based folding scheme, we instantiate the homomorphic commitment on the elliptic curve group where the discrete logarithm problem is hard. Therefore the finite field \mathbb{F} should be a scalar field of some elliptic curve E_2. If the field \mathbb{F} differs from the domain of the evaluation, all non-native operations must be simulated over \mathbb{F}. In particular, simulating operations over larger fields on a smaller field additionally increases extensive constraints. Using the state-of-the-art frontend techniques in [47,48], we compute the number of constraints required to simulate each operation of E_1 on the scalar field of E_2, which is set to three cases of elliptic curves. The results are shown in Tab.1.

Therefore, to minimize the prover time, we avoid non-native operations as much as possible in our scheme \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S}. We compare the number of constraints of simulation for non-native operations over the native curves in Tab.1. The number of constraints of non-native group operations is larger than that of non-native field operations, so group operations are more expensive to simulate than common field operations. In the verification of Fig.10, there are not only field operations over {\mathbb{F}}_q such as multiplication and inverse modulo q, but also group operations such as point addition and scalar multiplication. Since the group operations are implemented over the base field {\mathbb{F}}_p of E_1, we let {\mathbb{F}}_p to be the scalar of E_2 so that we only need to simulate a few of operations of {\mathbb{F}}_q on {\mathbb{F}}_p. On the other hand, the verification of the folding scheme is dominated by group operations and it will also be represented as R1CS constraints. Like Nova, we use a cycle of elliptic curves, E_1 and E_2, to make it efficient. We set the E_2 as the primary curve and E_1 as the secondary curve to execute the verification of the folding scheme alternately, the ECDSA verification is only represented on the primary curve. Fortunately, the elliptic curve \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{q}\mathtt{256}\mathtt{k}\mathtt{1} [18] perfectly forms a cycle with \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1}, so we instantiate the E_2 by \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{q}\mathtt{256}\mathtt{k}\mathtt{1} to complete the IVC scheme. Furthermore, the scalar field {\mathbb{F}}_p is larger than {\mathbb{F}}_q, so there are no additional constraints for simulating the multiplication and addition modulo q. Therefore, \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{q}\mathtt{256}\mathtt{k}\mathtt{1} is optimal to instantiate E_2.

5.3.2 Optimization on backend implementation

Corresponding to the frontend, the process of executing a protocol on a given arithmeticized representation is called the backend. At the end of the IVC scheme, we add a general SNARK to compress the proof size as shown in Fig.9. Using \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n} with \mathsf{B}\mathsf{u}\mathsf{l}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{p}\mathsf{r}\mathsf{o}\mathsf{o}\mathsf{f} commitment scheme as the SNARK is natural because it is not only designed for R1CS satisfiability but can be compatible with the additive homomorphic commitment based on the discrete logarithm problem. Moreover, it is transparent and has a prover with linear complexity about the size of a committed relaxed R1CS instance. Although the proof size of the \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} is not a constant, the size of the final proof π in our scheme is independent of the number of signatures. The reason is that we apply the \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} only once on a committed relaxed R1CS instance-witness pair ({\mathbb{U}}^{\prime },{\mathbb{W}}^{\prime }) with a constant scale, instead of verifying a batch of ECDSA signatures inside \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} directly. The proof size depends only on the fixed block size and the ECDSA verification itself, not on the total number of signatures.

Tab.2 compares our scheme with the approaches used \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} and \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} directly for batch verification of ECDSA. The batch size is t=nb where b is the number of signatures in each step of IVC, and n is the number of steps. Let O(k) MSM represent O(k)-sized multi-scalar multiplication, O(k) FFT represent O(k)-sized FFT costs O(k\log k) field operations. N denotes the number of constraints of one ECDSA verification over the scalar field of \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1}, N^{\prime }(>N) denotes the number of constraints of one ECDSA verification simulated on \mathtt{B}\mathtt{L}\mathtt{S}\mathtt{12}\mathtt{\_}\mathtt{381}, and N^{″}(\gtrsim N) denotes N plus the number of constraints of a hash function \mathsf{H}. Since the prover time is dominated by complex computations such as MSM and FFT, we count the times they must be executed in the protocol. We evaluate the proof size and verifier time by elements and operations of the cryptographic group or field. In the batch verification of ECDSA, the number of constraints of each instance is fixed, so N,N^{\prime }, and N^{″} are constants and the unique variable in this evaluation is the batch size t. The proof size of \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} increases with t, the proof size of \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} is always a constant, and the proof of our scheme is also a constant since the block size b is pre-determined.

6 Security

In this section, we analyze the security of our general construction of the non-interactive argument in Section 5.2. The completeness relies on the completeness of the IVC scheme and the SANRK schemes. The soundness is determined by the knowledge-soundness of the IVC and the soundness of the SANRK schemes.

The knowledge soundness of the original Nova IVC relies on the knowledge soundness of the non-interactive folding scheme (\mathsf{N}\mathsf{I}\mathsf{F}\mathsf{S}) in the standard model, where the non-interactive property is realized by instantiating the random oracle with a cryptographic hash function. However in the batch verification of signatures, if the parameter n is as large as O(\lambda ), this proof strategy will not work. As mentioned in [42], the original Nova follows a general recursive proof strategy, where the IVC extractor \mathcal{E} generates {\mathcal{E}}_i from {\mathcal{E}}_{i+1} for i\in [n] and it holds that

\mathsf{t}\mathsf{i}\mathsf{m}\mathsf{e}({\mathcal{E}}_i)>\mathsf{t}\mathsf{i}\mathsf{m}\mathsf{e}({\tilde{\mathcal{E}}}_i)+\mathsf{t}\mathsf{i}\mathsf{m}\mathsf{e}({\mathcal{A}}_i)>2\cdot \mathsf{t}\mathsf{i}\mathsf{m}\mathsf{e}({\mathcal{E}}_{i+1}).

This proof strategy is applicable when considering a batch of no more than t signatures, where t=nb,n=O(\log \lambda ) for a fixed b. When the number of signatures is so large that n=O(\lambda ), the running time of the extractor \mathcal{E} will be 2^{O(\lambda )}, it cannot extract all IVC witness in the polynomial time. If the \lambda \le 2^{128}, the original knowledge soundness proof can only support steps and bounds the 128b signatures in total, limiting the scalability in the blockchain in practice. Although the throughput may be improved by choosing a bigger b, an oversized circuit in one step will cost a lot of memory and offset the benefit of IVC to compress the circuit size. Therefore, we use the knowledge soundness proof in AGM proposed by [42] on the Group-based Non-Interactive Folding Scheme shown in Fig.8. Another advantage of this proof strategy is eliminating the heuristic manner in the arithmetization of oracles.

Lemma 2 (Completeness of IVC). The construction in Fig.7 is an IVC scheme that satisfies completeness.

Proof Sketch For i\ge 0, given a valid IVC proof {\mathrm{\Pi }}_i= \left(({\mathbb{U}}_i,{\mathbb{W}}_i),({\mathbb{u}}_i,{\mathbb{w}}_i)\right). Suppose the IVC prover runs the protocol honestly as Fig.7 and outputs a new IVC proof {\mathrm{\Pi }}_{i+1}= \left(({\mathbb{U}}_{i+1},{\mathbb{W}}_{i+1}),({\mathbb{u}}_{i+1},{\mathbb{w}}_{i+1})\right). Because {\mathrm{\Pi }}_i is valid, then ({\mathbb{U}}_i,{\mathbb{W}}_i)\in {\mathcal{R}}_{\mathsf{s}} and ({\mathbb{u}}_i,{\mathbb{w}}_i)\in {\mathcal{R}}_{\mathsf{s}} for a certain public relation {\mathcal{R}}_{\mathsf{s}}. Because the prover run the folding scheme to obtain ({\mathbb{U}}_{i+1},{\mathbb{W}}_{i+1}), it is the folded result of ({\mathbb{U}}_i,{\mathbb{W}}_i) and ({\mathbb{u}}_i,{\mathbb{w}}_i) so that ({\mathbb{U}}_{i+1},{\mathbb{W}}_{i+1})\in {\mathcal{R}}_{\mathsf{s}} by the completeness of the folding scheme. Finally, the instance-witness pair ({\mathbb{u}}_i,{\mathbb{w}}_i) describes the correct execution of the ith augment function, it must hold that ({\mathbb{u}}_i,{\mathbb{w}}_i)\in {\mathcal{R}}_{\mathsf{s}} as long as the prover run the entire protocol honestly. The formal proof is provided in Appendix A. 　　　　　　　□

Lemma 3 (Knowledge Soundness of IVC). If the hash function \mathsf{H} has the general zero-testing property and the discrete logarithm assumption holds in the group \mathbb{G}, then the IVC scheme in Fig.7 combined with the group-based folding scheme based on \mathbb{G} and \mathsf{H} (Fig.8) satisfies knowledge soundness in the refined AGM.

Proof We follow the proof strategy of [44]. For an IVC scheme with n=poly(\lambda ) steps, the functions \mathsf{F}\mathsf{,}\mathsf{H}, \mathsf{p}\mathsf{p}\leftarrow \mathcal{G}(1^{\lambda }), and (\mathsf{p}\mathsf{k}\mathsf{,}\mathsf{v}\mathsf{k})\leftarrow \mathcal{K}(\mathsf{p}\mathsf{p},\mathsf{F}\mathsf{,}\mathsf{H}), consider a polynomial time algebraic adversary {\mathcal{P}}^{\ast } on inputs \mathsf{p}\mathsf{p}=({\mathsf{p}\mathsf{p}}_E,{\mathsf{p}\mathsf{p}}_W) and outputs h_0,h,\mathrm{\Pi } with set S of representation vectors following multi-encoding. We construct a extractor \mathcal{E} on input (\mathsf{p}\mathsf{p},h_0,h), outputs (h_i{)}_{i=1}^{n-1} and ({\mathit{y}}_i,{\mathit{z}}_i{)}_{i=0}^{n-1} such that h_n=h and \mathsf{H}\left(h_{i-1},{\mathit{y}}_{i-1},{\mathit{z}}_{i-1}\right)=h_i where {\mathit{z}}_{i-1}=\mathsf{F}({\mathit{y}}_{i-1}). We construct \mathcal{E} by sub-extractor {\mathcal{E}}_i for all i\in [n-1] in reverse order. In each step, given (h_i,\dots ,h_n),\left(({\mathit{y}}_i,{\mathit{z}}_i),\dots ,({\mathit{y}}_{n-1},{\mathit{z}}_{n-1})\right), and an accepting IVC proof {\mathrm{\Pi }}_i, {\mathcal{E}}_i outputs h_{i-1}, ({\mathit{y}}_{i-1},{\mathit{z}}_{i-1}) and an IVC proof {\mathrm{\Pi }}_{i-1}. After all n-1 sub-extractors {\mathcal{E}}_i are constructed, the IVC extractor \mathcal{E} runs them to extract the final outputs \left(({\mathit{y}}_0,{\mathit{z}}_0),\dots ,({\mathit{y}}_{n-1},{\mathit{z}}_{n-1})\right). The constructions of {\mathcal{E}}_i and \mathcal{E} are described in Fig.11.

The correctness of the extracted witness from \mathcal{E} relies on the correctness of the outputs of each {\mathcal{E}}_i. By Lemma 4, each {\mathrm{\Pi }}_{i-1} are valid and h_{i-1},{\mathit{y}}_{i-1},{\mathit{z}}_{i-1} extracted in the ith step satisfies that h_i=\mathsf{H}(h_{i-1},{\mathit{y}}_{i-1},{\mathit{z}}_{i-1}), where {\mathit{z}}_{i-1}=\mathsf{F}({\mathit{y}}_{i-1}).

Lemma 4 Consider the input and output

(h_i,\dots ,h_n),\left(({\mathit{y}}_i,{\mathit{z}}_i),\dots ,({\mathit{y}}_{n-1},{\mathit{z}}_{n-1})\right),

such that h_{j+1}=\mathsf{H}(h_j,{\mathit{y}}_j,{\mathit{z}}_j) and {\mathit{z}}_j=\mathsf{F}({\mathit{y}}_j) for all j=i,\dots ,n-1. Let S be a set of representation vectors output by {\mathcal{P}}^{\mathcal{\ast }}, and assume that {\mathrm{\Pi }}_i=\left(({\mathbb{U}}_i,{\mathbb{W}}_i),({\mathbb{u}}_i,{\mathbb{w}}_i)\right) is a valid IVC proof combined with the group-based folding scheme in Fig.8. If the hash function \mathsf{H} has the general zero-testing property and the discrete logarithm assumption holds in the group \mathbb{G}, then the PPT sub-extractor {\mathcal{E}}_i outputs a valid IVC proof {\mathrm{\Pi }}_{i-1}=(({\mathbb{U}}_{i-1}, {\mathbb{W}}_{i-1}),({\mathbb{u}}_{i-1},{\mathbb{w}}_{i-1})) and \left(h_{i-1},{\mathit{y}}_{i-1},{\mathit{z}}_{i-1}\right) satisfy {\mathit{z}}_{i-1}=\mathsf{F}({\mathit{y}}_{i-1}) and h_i=\mathsf{H}(h_{i-1},{\mathit{y}}_{i-1},{\mathit{z}}_{i-1}).

The proof of Lemma 4 is the same as the Lemma 3 of [44] and is provided in Appendix B. 　　　　　　　　　　　□

Theorem 1 (Completeness). The general construction for batch verification of valid signatures in Fig.9 is a non-interactive argument that satisfies completeness.

Proof Given a batch of signatures, suppose the prover verifies them and takes t=nb valid signatures \mathit{y} with their verification result \mathit{z} as inputs, and runs the protocol as in Fig.9, outputs a proof π. Because the t signatures are valid, for i\in [n], \mathsf{F}({\mathit{y}}_i)={\mathit{z}}_i={\mathbf{1}}^b, where b is the block size. Because the prover computes the hash chain and runs the IVC prover in Fig.7 honestly, h_i=\mathsf{H}\left(h_{i-1},{\mathit{y}}_i,{\mathbf{1}}^b\right) and {\mathrm{\Pi }}_i is a valid IVC proof for all i\in [n]. The last IVC proof {\mathrm{\Pi }}_n=\left((\mathbb{U},\mathbb{W}),(\mathbb{u},\mathbb{w})\right) is valid implies that (\mathbb{U},\mathbb{W}),(\mathbb{u},\mathbb{w})\in {\mathcal{R}}_{\mathsf{s}}, and checks 4 and 5 of the verifier will pass by the completeness of the IVC scheme. Then the prover obtains \left({\mathbb{U}}^{\prime },{\mathbb{W}}^{\prime },\overline{T^{\prime }}\right) by the folding scheme, so the \left({\mathbb{U}}^{\prime },{\mathbb{W}}^{\prime }\right)\in {\mathcal{R}}_{\mathsf{s}} under the completeness of the folding scheme. Furthermore, the completeness of the SNARK scheme guarantees that {\pi }^{\prime } is valid. All conditions of the verifier can be met. 　　　□

Theorem 2 (Soundness). If the hash function \mathsf{H} has the collision-resistant property, the IVC scheme in Fig.7 satisfies knowledge soundness for n=O(\lambda ) steps, and \mathsf{S}\mathsf{N}\mathsf{A}\mathsf{R}\mathsf{K} is a SNARK of a valid IVC proof satisfies knowledge soundness, the general construction in Fig.9 is a non-interactive argument for batch verification of t=O(\lambda ) valid signatures satisfies soundness.

Proof Let {\mathcal{P}}^{\ast } be an adversary against the soundness of the general construction in Fig.9 for batch verification of t=O(\lambda ) signatures. {\mathcal{P}}^{\ast } takes public parameters \mathsf{p}\mathsf{p}=({\mathsf{p}\mathsf{p}}_{\mathsf{f}\mathsf{s}},{\mathsf{p}\mathsf{p}}_{\mathsf{s}\mathsf{n}\mathsf{a}\mathsf{r}\mathsf{k}}) and outputs h_0,\mathit{y}=({\mathit{y}}_0,\dots ,{\mathit{y}}_{n-1}) with a proof \pi =(h_n,\mathbb{U},\mathbb{u},\overline{T^{\prime }},{\pi }^{\prime }) for the statement that all t=nb signatures described in \mathit{y} are valid, i,e, \mathrm{\forall }i\in [n],\mathsf{F}({\mathit{y}}_{i-1})={\mathbf{1}}^b. Suppose there exist at least one invalid signature, without loss of generality, the jth signature, the proof π from {\mathcal{P}}^{\ast } pass the verification with probability ϵ(\lambda ), we demonstrate that ϵ(\lambda ) is negligible.

If {\mathcal{P}}^{\ast } follows the protocol honestly, precisely, {\mathcal{P}}^{\ast } runs the prover algorithm in the Fig.9 to prove that \mathsf{F}({\mathit{y}}_{i-1})={\mathit{z}}_{i-1} for all i\in [n], where \mathsf{F}({\mathit{y}}_{j^{\prime }})={\mathit{z}}_{j^{\prime }}\ne {\mathbf{1}}^b,j^{\prime }=\lfloor \frac{j}{n}\rfloor and \mathsf{F}({\mathit{y}}_{i-1})= {\mathit{z}}_{i-1}={\mathbf{1}}^b for all i\ne j^{\prime }. Because the proof is accepted, it must hold that h_n=\mathsf{H}\left(\dots \mathsf{H}\left(\mathsf{H}\left(h_0,{\mathit{y}}_0,{\mathbf{1}}^b\right),{\mathit{y}}_1,{\mathbf{1}}^b\right)\dots ,{\mathit{y}}_n,{\mathbf{1}}^b\right) by the condition 1-3 of the verifier. As the hash function is collision-resistant, it will contract to the Lemma 5. Thus all {\mathit{z}}_{i-1} for i\in [n] are {\mathbf{1}}^b with overwhelming probability. Similarly, if {\mathcal{P}}^{\ast } honestly generate an accepted proof for \mathsf{F}({\mathit{y}}_{i-1}^{\prime })={\mathbf{1}}^b for all i\in [n] but {\mathit{y}}^{\prime }\ne \mathit{y} that sent to the verifier before the protocol, it also cannot pass the verification without a negligible probability.

Lemma 5 [49] If \mathsf{H} is collision-resistant, then the Merkle-Damgard construction of \mathsf{H} is collision-resistant.

If {\mathcal{P}}^{\ast } pass the verification by cheating, all conditions of the verifier will be met. By step 7 of the verifier, {\pi }^{\prime } passes the verification of the SNARK scheme for the instance {\mathbb{U}}^{\prime } computed by running the verifier of the folding scheme. We first construct a SNARK extractor \tilde{\mathcal{E}}, which takes {\mathbb{U}}^{\prime } and the accepted SNARK proof {\pi }^{\prime }, outputs a witness {\mathbb{W}}^{\prime } such that ({\mathbb{U}}^{\prime },{\mathbb{W}}^{\prime })\in {\mathcal{R}}_{\mathsf{s}} with an overwhelming probability. This implies that instances \mathbb{U} and \mathbb{u} are satisfiable, we can run the folding extractor \hat{\mathcal{E}} to extract \mathbb{W} and \mathbb{w} such that (\mathbb{U},\mathbb{W}),(\mathbb{u},\mathbb{w})\in {\mathcal{R}}_{\mathsf{s}}. Then we run the IVC extractor \mathcal{E} that takes (h_0,h) and the accepted IVC proof \mathrm{\Pi }=\left((\mathbb{U},\mathbb{W}),(\mathbb{u},\mathbb{w})\right), outputs \mathit{y}= ({\mathit{y}}_0,\dots ,{\mathit{y}}_{n-1}) satisfies that \mathsf{H}\left(h_{i-1},{\mathit{y}}_{i-1},\mathsf{F}({\mathit{y}}_{i-1})\right)=h_i for all i\in [n]. Following the construction of the IVC extractor in Fig.11, we sequentially construct the sub-extractors {\mathcal{E}}_i for all i\in [n]. If there exists any j\in [n] such that \mathsf{F}({\mathit{y}}_{j-1})= {\mathit{z}}_{j-1}\ne {\mathbf{1}}^b, then it contradicts the collision-resistant property of the hash function \mathsf{H} as above. Suppose the SNARK scheme has the knowledge error {ϵ}_{\mathsf{s}\mathsf{n}\mathsf{a}\mathsf{r}\mathsf{k}}(\lambda ), the IVC scheme has the knowledge error {ϵ}_{\mathsf{i}\mathsf{v}\mathsf{c}}(\lambda ) for n=O(\lambda ) rounds iterations, the non-interactive folding scheme has the knowledge error {ϵ}_{\mathsf{n}\mathsf{i}\mathsf{f}\mathsf{s}}(\lambda ) and the probability of the event that finding a collision for the Merkle-Damgard formed hash chain with length n is {ϵ}_{\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}}(\lambda )\le \mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(\lambda ). Then, our scheme in Fig.9 has the soundness error

ϵ(\lambda )={ϵ}_{\mathsf{s}\mathsf{n}\mathsf{a}\mathsf{r}\mathsf{k}}(\lambda )+{ϵ}_{\mathsf{n}\mathsf{i}\mathsf{f}\mathsf{s}}(\lambda )+{ϵ}_{\mathsf{i}\mathsf{v}\mathsf{c}}(\lambda )+{ϵ}_{\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}}(\lambda )\le \mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(\lambda ).

Finally, because the extractor \tilde{\mathcal{E}},\hat{\mathcal{E}}, and \mathcal{E} can extract the witness in polynomial time, and the hash function can achieve at least 100-bit security, the probability for any PPT {\mathcal{P}}^{\ast } generating an accepted proof for a false statement is negligible. 　　　　　　　　□

7 Implementation

Following the general construction of Section 5.2 and employing the optimization strategies in Section 5.3, we implement our scheme for batch verification of ECDSA in Rust. The experiments were executed on a Virtual Machine with an Intel i7-11800H CPU with 2.30 GHz, 8 cores, and 16 GB of RAM.

The arithmetic circuit R1CS is compiled using the library bellpepper [50]. We implement the IVC with SNARK scheme following the code of Nova [43], where we choose \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1} and \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{q}\mathtt{256}\mathtt{k}\mathtt{1} as the elliptic curve cycle. We set \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{q}\mathtt{256}\mathtt{k}\mathtt{1} as the primary curve and \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1} as the secondary curve. The verification of ECDSA is only defined on the scalar field {\mathbb{F}}_p of \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{q}\mathtt{256}\mathtt{k}\mathtt{1}. The number of R1CS constraints is about 4,000 per ECDSA verification. In experimental testing, we can adjust the block size b. In particular, the function \mathsf{F} represents b ECDSA verification processes on the digest of the message. We have the verifier compute the digest e=\mathsf{h}\mathsf{a}\mathsf{s}\mathsf{h}(m) locally and add this computation time to the verifier time. We fix the message m as a 160-byte value as account information in transactions. We instantiate the hash function \mathsf{H} in our scheme by \mathsf{P}\mathsf{o}\mathsf{s}\mathsf{e}\mathsf{i}\mathsf{d}\mathsf{o}\mathsf{n}, which contains an initialization phase independent of the message and a computation phase that processes messages through the sponge structure. Since the initialization of \mathsf{P}\mathsf{o}\mathsf{s}\mathsf{e}\mathsf{i}\mathsf{d}\mathsf{o}\mathsf{n} is fixed and reusable, it can be seen as the offline computation together with the setup of the proof system for the prover and verifier. We only focus on the online phase related to signatures.

7.1 \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S}

We instantiate the SNARK in our scheme via \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} to obtain a transparent scheme \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S}. As shown in Fig.12, we test the prover time and verifier time with batch sizes t ranging from 1 to 2^{20} ECDSA signatures. We set the block size b=1,2,8,32 in each IVC step, respectively.

We first compare our protocol with the scheme that verified ECDSA inside \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} directly. Since \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} in this paper uses the cycle of curves \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1}\mathtt{/}\mathtt{s}\mathtt{e}\mathtt{c}\mathtt{q}\mathtt{256}\mathtt{k}\mathtt{1}, it is natural to compare it with \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n} using \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1} in the experiments. For the prover time, when the batch size is larger than 2^3, \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} begins to show its advantages. If the batch size is less than 2^9, the prover time will be lower to set b=8, while setting the block size b larger, such as b=32, would make the prover faster if one intends to pack many more signatures. In \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S}, the parameter b determines the number of constraints proven by the final SNARK after IVC. Increasing b speeds up the prover for large batch sizes, while decreasing b speeds up the prover for small batch sizes. Additionally, smaller b results in faster verification and smaller proofs. When t=2^{11}, \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} reaches its upper bound on the number of signatures, the prover time of \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} is about 776 s, while the prover time for b=1,2,8 and 32 in \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} is 248, 160, 62, and 45 s respectively. We speed up the prover by 3~17 times.

For the verifier time, it grows linearly with the number of signatures in \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}}, while in \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} it is almost constant when t\le 2^{14}. When t=2^{11}, \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} reaches its upper bound with a verifier time of 21 s, while the mean of verifier time for different values of b=1,2,8 and 32 in \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} is 87, 118, 180, and 440 ms respectively. We speed up the verifier by 48–240 times. The verifier time of \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} starts to show an increasing trend only when t\ge 2^{15}; the reason is the verifier time is dominated by the SNARK verification process before that and the hash computation of the message is negligible. As the size increases, the hash computation is proportional to the number of messages, so the hash computation starts to dominate the verifier time when t\ge 2^{15}. The baseline with black triangle legend in Fig.12 indicates the verification time of ECDSA signatures without any proof system. Obliviously, \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} will be more efficient when the batch size is larger than 2^{10} compared to the baseline. When t=2^{20}, we speed up the verifier by 21–174 times. Furthermore, even if the baseline is optimized for parallelism as the gray triangle legend, \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} still using a single thread becomes advantageous when the batch size exceeds 2^{13}. The gap when t\ge 2^{13} grows with the batch size. When t=2^{20}, we speed up the verifier by 3~30 times.

Then we compare our scheme with \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n}. In Section 1.1, we mentioned that \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} is based on bilinear pairing, but \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1}\mathtt{/}\mathtt{s}\mathtt{e}\mathtt{c}\mathtt{q}\mathtt{256}\mathtt{k}\mathtt{1} is not pairing-friendly as noted in Section 2. Thus it is difficult to implement the bilinear pairing mapping of \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} on \mathtt{s}\mathtt{e}\mathtt{c}\mathtt{p}\mathtt{256}\mathtt{k}\mathtt{1} efficiently. To ensure fair comparisons, we use the optimal finite field for \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n}, given its reliance on non-native operations. Following the result of [48] that there are about 2^{20} constraints for each ECDSA verification, we substitute the result into the benchmark test to obtain the experiment performance. Since the prover time of \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} is quasi-linear and a large-scale MSM and FFT dominate the time and memory of the prover, the execution quickly reaches the upper bound. \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} can prove only one ECDSA signature in the virtual machine of this experiment. When b=1, the prover takes 1.82 s in \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} and takes 19.46 s in \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} for one ECDSA signature. The single prover in \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} is faster than \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} by about 10 times. \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} has fast verifier with 6.74 ms and an extremely short proof with 0.73 KB. In \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S}, the verifier takes 86.36 ms and the proof size is 9.22 KB. Consequently, the verifier time and the proof size of \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} are larger than \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} by about 12 times. However, these advantages of \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} come at the cost of longer prover time and higher memory consumption, and it is non-transparent with a trusted setup. We improve the scalability significantly that supports an arbitrary number of signatures and the proof size is nearly constant when the batch size is less than 2^{14}. Since \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n} needs to generate proofs for a batch of signatures separately, the verifier time and proof size of \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} can be amortized efficiently.

Tab.3 and Tab.4 describe the comparison of proof size between \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} and \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} and \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n}. The batch size t in Tab.3 represents the number of the ECDSA signatures in total and the block size b in Tab.4 represents the number of the ECDSA signatures handled in each step of IVC in \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S}, the proof size of \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} is a constant independent of t for fixed b. Our proof size is larger than the {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}}, because the implementation is over the cycle of elliptic curves, there are two instance-witness pairs at the last of the IVC scheme, i.e., ({\mathbb{U}}^{\prime },{\mathbb{W}}^{\prime }) in Fig.9 is replaced by ({\mathbb{U}}^{(1)},{\mathbb{W}}^{(1)}) and ({\mathbb{U}}^{(2)},{\mathbb{W}}^{(2)}). Finally, there are two SNARK proofs. When a short proof is desired, one can use only one curve to halve the proof size.

For scalability, the upper bound on the number of ECDSA signatures that can be proved at once is 2^{11} in \mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}{\mathsf{n}}_{\mathsf{B}\mathsf{P}} and only one in \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n}. \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} can support arbitrary batch size theoretically, and we show only a portion of the practical intervals in Fig.12 within a practically acceptable time. Thanks to the chain-based IVC construction, our scheme is memory-friendly. The ith step in the chain claims that the previous i steps were executed correctly, which is a compression of the historical state. Each generated IVC proof can be viewed as an update to the current state and the past state can be released. The prover generates the IVC proof and takes a constant memory and a linear time about the number of steps of the IVC chain. On the other hand, we can replace chain-based construction with tree-based construction, which provides a faster prover but costs more memory. This construction is similar to the PCD-based SNARK in [51], but the batch verification for multiple signatures is a natural uniform format, so we do not require a compiler nor do we need to consider the wiring connections between each sub-computation. In this parallel implementation, the time for executing O(t{N}^{″})-sized MSM of the prover in Tab.1 will be reduced to the time for O(\log n\cdot b{N}^{″})-sized MSM, where t=nb and . In addition, the width of the tree can be adjusted according to the optimal number of threads for the device.

8 Conclusion

We present a general approach to batch verification of arbitrary signatures on the blockchain, addressing scalability, memory efficiency, and compatibility with common devices while supporting an arbitrary number of verifications. As a concrete instantiation, we introduce \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} for batch ECDSA verification, demonstrating significant performance improvements over existing methods. The comparison shows that \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} speeds up the prover and the verifier of {\mathsf{S}\mathsf{p}\mathsf{a}\mathsf{r}\mathsf{t}\mathsf{a}\mathsf{n}}_{\mathsf{B}\mathsf{P}} significantly for the large batch of ECDSA signatures. Furthermore, \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} has high scalability that supports an arbitrary number of signatures, which is far superior to the existing SNARK such as \mathsf{M}\mathsf{a}\mathsf{r}\mathsf{l}\mathsf{i}\mathsf{n}. Finally, \mathsf{B}\mathsf{E}\mathsf{A}\mathsf{T}\mathsf{S} exhibits a remarkably low memory footprint, making it compatible with resource-limited devices.

A research direction in the future is how to realize proof acceleration on small finite fields. However, several challenges must be addressed. Firstly, while small finite fields may offer faster field operations, they often lead to increased soundness errors. This necessitates additional security mechanisms, potentially increasing scheme complexity and introducing overhead for the prover. Secondly, simulating non-native operations on smaller fields can result in larger circuit sizes. Since prover time in many proof systems scales linearly with the number of constraints, this circuit size growth can significantly impact prover performance. Finally, in the context of Nova IVC, the use of a cycle of elliptic curves is crucial for efficient proofs. Finding suitable curve pairs that both enhance proof efficiency and adhere to the cycle form presents a significant challenge.

References

[1] Boneh D, Gentry C, Lynn B, Shacham H. Aggregate and verifiably encrypted signatures from bilinear maps. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology. 2003, 416−432

[2] Harn L . Batch verifying multiple RSA digital signatures. Electronics Letters, 1998, 34( 12): 1219–1220

[3] Karati S, Das A, Roychowdhury D, Bellur B, Bhattacharya D, Iyer A. Batch verification of ECDSA signatures. In: Proceedings of the 5th International Conference on Cryptology in Africa on Progress in Cryptology. 2012, 1−18

[4] Karati S, Das A, Roychoudhury D. Randomized batch verification of standard ECDSA signatures. In: Proceedings of the 4th International Conference on Security, Privacy, and Applied Cryptography Engineering. 2014, 237−255

[5] Karati S, Das A. Faster batch verification of standard ECDSA signatures using summation polynomials. In: Proceedings of the 12th International Conference on Applied Cryptography and Network Security. 2014, 438−456

[6] Antipa A, Brown D, Gallant R, Lambert R, Struik R, Vanstone S. Accelerated verification of ECDSA signatures. In: Proceedings of the 12th International Workshop on Selected Areas in Cryptography. 2005, 307−318

[7] Cheon J H, Yi J H. Fast batch verification of multiple signatures. In: Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography. 2007, 442−457

[8] Liu T, Xie T, Zhang J, Song D, Zhang Y. Pianist: scalable zkRollups via fully distributed zero-knowledge proofs. In: Proceedings of 2024 IEEE Symposium on Security and Privacy (SP). 2024, 1777−1793

[9] Polygon. See Polygon.technology/polygon-zkevm website, 2024

[10] Scroll. See Scroll.io/ website, 2025

[11] ZKsync. See Zksync.io/ website , 2024

[12] Setty S. Spartan: efficient and general-purpose zkSNARKs without trusted setup. In: Proceedings of the 40th Annual International Cryptology Conference on Advances in Cryptology. 2020, 704−737

[13] Bünz B, Bootle J, Boneh D, Poelstra A, Wuille P, Maxwell G. Bulletproofs: short proofs for confidential transactions and more. In: Proceedings of 2018 IEEE Symposium on Security and Privacy (SP). 2018, 315−334

[14] Chiesa A, Hu Y, Maller M, Mishra P, Vesely N, Ward N. Marlin: preprocessing zkSNARKs with universal and updatable SRS. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology. 2020, 738−768

[15] Kate A, Zaverucha G M, Goldberg I. Constant-size commitments to polynomials and their applications. In: Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security on Advances in Cryptology. 2010, 177−194

[16] Kothapalli A, Setty S, Tzialla I. Nova: recursive zero-knowledge arguments from folding schemes. In: Proceedings of the 42nd Annual International Cryptology Conference on Advances in Cryptology. 2022, 359−388

[17] C2PA technical specification. See C2pa.org/specifications/specifications/1.1/specs/C2PA_Specification website, 2024

[18] Curve with group order 2^255 − 19. See Moderncrypto.org/mail-archive/curves/2018/000992 website, 2018

[19] Spartan-ECDSA. See Github.com/personaelabs/spartan-ecdsa website, 2024

[20] Bünz B, Chen B. Protostar: generic efficient accumulation/folding for special-sound protocols. In: Proceedings of the 29th International Conference on the Theory and Application of Cryptology and Information Security. 2023, 77−110

[21] Kothapalli A, Setty S. HyperNova: recursive arguments for customizable constraint systems. In: Proceedings of the 44th Annual International Cryptology Conference on Advances in Cryptology. 2024, 345−379

[22] Groth J. On the size of pairing-based non-interactive arguments. In: Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology. 2016, 305−326

[23] Gabizon A, Williamson Z J, Ciobotaru O. PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. See Eprint.iacr.org/2019/953 website, 2019

[24] Zcash. See Zcash.readthedocs.io/en/latest/ website, 2019

[25] Zhang J, Xie T, Zhang Y, Song D. Transparent polynomial delegation and its applications to zero knowledge proof. In: Proceedings of 2020 IEEE Symposium on Security and Privacy (SP). 2020, 859−876

[26] Golovnev A, Lee J, Setty S, Thaler J, Wahby R S. Brakedown: Linear-time and field-agnostic snarks for R1CS. In: Proceedings of Annual International Cryptology Conference. 2023, 193–226

[27] Xie T, Zhang Y, Song D. Orion: zero knowledge proof with linear prover time. In: Proceedings of the 42nd Annual International Cryptology Conference on Advances in Cryptology. 2022, 299−328

[28] Kales D, Zaverucha G. Efficient lifting for shorter zero-knowledge proofs and post-quantum signatures. See Eprint.iacr.org/2022/588 website, 2022

[29] Zeilberger H, Chen B, Fisch B. BaseFold: efficient field-agnostic polynomial commitment schemes from foldable codes. In: Proceedings of the 44th Annual International Cryptology Conference on Advances in Cryptology. 2024, 138−169

[30] Block A R, Fang Z, Katz J, Thaler J, Waldner H, Zhang Y. Field-agnostic SNARKs from expand-accumulate codes. In: Proceedings of the 44th Annual International Cryptology Conference on Advances in Cryptology. 2024, 276−307

[31] Chen B, Bünz B, Boneh D, Zhang Z. HyperPlonk: plonk with linear-time prover and high-degree custom gates. In: Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology. 2023, 499−530

[32] 0xPolygonZero/zk_evm. See Github.com/0xPolygonZero/zk_evm website, 2024

[33] Plonky2. See Github.com/0xPolygonZero/plonky2/blob/main/plonky2/plonky2 website, 2022

[34] Wu H, Zheng W, Chiesa A, Popa R A, Stoica I. DIZK: a distributed zero knowledge proof system. In: Proceedings of the 27th USENIX Conference on Security Symposium. 2018, 675−692

[35] Chiesa A, Lehmkuhl R, Mishra P, Zhang Y. EOS: efficient private delegation of zkSNARK provers. In: Proceedings of the 32nd USENIX Conference on Security Symposium. 2023, 361

[36] Sha J, Liu S . Delegable zk-SNARKs with proxies. Frontiers of Computer Science, 2024, 18( 5): 185812

[37] Garg S, Goel A, Wang M. How to prove statements obliviously? In: Proceedings of the 44th Annual International Cryptology Conference on Advances in Cryptology. 2024, 449−487

[38] Das S, Camacho P, Xiang Z, Nieto J, Bünz B, Ren L. Threshold signatures from inner product argument: succinct, weighted, and multi-threshold. In: Proceedings of 2023 ACM SIGSAC Conference on Computer and Communications Security. 2023, 356−370

[39] Garg S, Jain A, Mukherjee P, Sinha R, Wang M, Zhang Y. hinTS: threshold signatures with silent setup. In: Proceedings of 2024 IEEE Symposium on Security and Privacy (SP). 2024, 3034−3052

[40] Qiu T, Tang Q. Predicate aggregate signatures and applications. In: Proceedings of the 29th International Conference on the Theory and Application of Cryptology and Information Security on Advances in Cryptology. 2023, 279−312

[41] Fuchsbauer G, Kiltz E, Loss J. The algebraic group model and its applications. In: Proceedings of the 38th Annual International Cryptology Conference on Advances in Cryptology. 2018, 33−62

[42] Lee H, Seo J H. On the security of nova recursive proof system. See Eprint.iacr.org/2024/232 website, 2024

[43] Nova. See Github.com/microsoft/Nova website, 2025

[44] Nguyen W, Boneh D, Setty S. Revisiting the nova proof system on a cycle of curves. See Eprint.Iacr.Org/2023/969 website, 2023

[45] National Institute of Standards, Technology. Digital signature standard (DSS). See Csrc.nist.gov/pubs/fips/186–5/final website, 2023

[46] Grassi L, Khovratovich D, Rechberger C, Roy A, Schofnegger M. Poseidon: a new hash function for zero-knowledge proof systems. In: Proceedings of the 30th USENIX Conference on Security Symposium. 2021, 519−535

[47] Kosba A, Papamanthou C, Shi E. xJsnark: a framework for efficient verifiable computation. In: Proceedings of 2018 IEEE Symposium on Security and Privacy (SP). 2018, 944−961

[48] 0xPARC. zk-ECDSA part 2: under the hood. See 0Xparc.org/blog/zk-ecdsa-2 website, 2024

[49] Katz J, Lindell Y. Introduction to Modern Cryptography. 2nd ed. Chapman & Hall/CRC, 2014

[50] bellpepper. See Github.com/lurk-lab/bellpepper website, 2024

[51] Nguyen W, Datta T, Chen B, Tyagi N, Boneh D. Mangrove: a scalable framework for folding-based SNARKs. In: Proceedings of the 44th Annual International Cryptology Conference on Advances in Cryptology. 2024, 308−344

RIGHTS & PERMISSIONS

The Author(s) 2025. This article is published with open access at link.springer.com and journal.hep.com.cn