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

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