[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3656019.3676898acmconferencesArticle/Chapter ViewAbstractPublication PagespactConference Proceedingsconference-collections
research-article

SZKP: A Scalable Accelerator Architecture for Zero-Knowledge Proofs

Published: 13 October 2024 Publication History

Abstract

Zero-Knowledge Proofs (ZKPs) are an emergent paradigm in verifiable computing. In the context of applications like cloud computing, ZKPs can be used by a client (called the verifier) to verify the service provider (called the prover) is in fact performing the correct computation based on a public input. A recently prominent variant of ZKPs is zkSNARKs, generating succinct proofs that can be rapidly verified by the end user. However, proof generation itself is very time consuming per transaction. Two key primitives in proof generation are the Number Theoretic Transform (NTT) and Multi-scalar Multiplication (MSM). These primitives are prime candidates for hardware acceleration, and prior works have looked at GPU implementations and custom RTL. However, both algorithms involve complex dataflow patterns – standard NTTs have irregular memory accesses for butterfly computations from stage to stage, and MSMs using Pippenger’s algorithm have data-dependent memory accesses for partial sum calculations. We present SZKP, a scalable accelerator framework that is the first ASIC to accelerate an entire proof on-chip by leveraging structured dataflows for both NTTs and MSMs. SZKP achieves conservative full-proof speedups of over 400 ×, 3 ×, and 12 × over CPU, ASIC, and GPU implementations.

References

[1]
2017. NVIDIA TESLA V100 GPU ARCHITECTURE. https://images.nvidia.com/content/volta-architecture/pdf/volta-architecture-whitepaper.pdf
[2]
2018. libsnark: a C++ library for zkSNARK proofs.https://github.com/scipr-lab/libsnark
[3]
2019. AMD DOUBLES DOWN – AND UP – WITH ROME EPYC SERVER CHIPS. https://www.nextplatform.com/2019/08/07/amd-doubles-down-and-up-with-rome-epyc-server-chips/
[4]
2019. AMD EPYC 7502. https://www.amd.com/en/products/cpu/amd-epyc-7502
[5]
2024. AMD EPYC 7502. https://www.techpowerup.com/cpu-specs/epyc-7502.c2250
[6]
2024. Beyond ZK: Next Steps for Compliance and Constrained Encryption on Blockchains. https://a16zcrypto.com/posts/videos/beyond-zk-next-steps-for-compliance-and-constrained-encryption-on-blockchains/
[7]
2024. NVIDIA GTX 1080i. https://www.techpowerup.com/gpu-specs/geforce-gtx-1080-ti.c2877
[8]
D. H. Bailey. 1989. FFTs in external or hierarchical memory. In Supercomputing ’89:Proceedings of the 1989 ACM/IEEE Conference on Supercomputing. 234–242. https://doi.org/10.1145/76263.76288
[9]
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. 2013. Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. Cryptology ePrint Archive, Paper 2013/879. https://eprint.iacr.org/2013/879 https://eprint.iacr.org/2013/879.
[10]
Juan Benet and Nicola Greco. 2017. Filecoin: A decentralized storage network. In Information and Communications Security. Protocol Labs, Cham, 1–36.
[11]
Daniel J. Bernstein, Jeroen Doumen, Tanja Lange, and Jan-Jaap Oosterwijk. 2012. Faster batch forgery identification. Cryptology ePrint Archive, Paper 2012/549. https://eprint.iacr.org/2012/549 https://eprint.iacr.org/2012/549.
[12]
James W. Cooley, Peter A. W. Lewis, and Peter D. Welch. 1969. The Fast Fourier Transform and Its Applications. IEEE Transactions on Education 12, 1 (1969), 27–34. https://doi.org/10.1109/TE.1969.4320436
[13]
Nanotechnology Products Database. 2023. TSMC 16FF+ (FinFET Plus). (2023). https://product.statnano.com/product/6775/16ff-(finfet-plus)
[14]
Franz Franchetti, Tze Meng Low, Doru Thom Popovici, Richard M. Veras, Daniele G. Spampinato, Jeremy R. Johnson, Markus Püschel, James C. Hoe, and José M. F. Moura. 2018. SPIRAL: Extreme Performance Portability. Proc. IEEE 106, 11 (2018), 1935–1968. https://doi.org/10.1109/JPROC.2018.2873289
[15]
Mario Garrido. 2022. A Survey on Pipelined FFT Hardware Architectures. J. Signal Process. Syst. 94, 11 (nov 2022), 1345–1364. https://doi.org/10.1007/s11265-021-01655-1
[16]
Shafi Goldwasser, Silvio Micali, and Chales Rackoff. 2019. The Knowledge Complexity of Interactive Proof-Systems. Association for Computing Machinery, New York, NY, USA, 203–225. https://doi.org/10.1145/3335741.3335750
[17]
Jens Groth. 2016. On the Size of Pairing-based Non-interactive Arguments. Cryptology ePrint Archive, Paper 2016/260. https://eprint.iacr.org/2016/260 https://eprint.iacr.org/2016/260.
[18]
Jongmin Kim, Sangpyo Kim, Jaewan Choi, Jaiyoung Park, Donghwan Kim, and Jung Ho Ahn. 2023. SHARP: A Short-Word Hierarchical Accelerator for Robust and Practical Fully Homomorphic Encryption. In Proceedings of the 50th Annual International Symposium on Computer Architecture (Orlando, FL, USA) (ISCA ’23). Association for Computing Machinery, New York, NY, USA, Article 18, 15 pages. https://doi.org/10.1145/3579371.3589053
[19]
Jongmin Kim, Gwangho Lee, Sangpyo Kim, Gina Sohn, Minsoo Rhu, John Kim, and Jung Ho Ahn. 2022. ARK: Fully Homomorphic Encryption Accelerator with Runtime Data Generation and Inter-Operation Key Reuse. In 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO). 1237–1254. https://doi.org/10.1109/MICRO56248.2022.00086
[20]
Sangpyo Kim, Jongmin Kim, Michael Jaemin Kim, Wonkyung Jung, John Kim, Minsoo Rhu, and Jung Ho Ahn. 2022. BTS: An Accelerator for Bootstrappable Fully Homomorphic Encryption. In Proceedings of the 49th Annual International Symposium on Computer Architecture (New York, New York) (ISCA ’22). Association for Computing Machinery, New York, NY, USA, 711–725. https://doi.org/10.1145/3470496.3527415
[21]
David G. Korn and Jules J. Lambiotte. 1979. Computing the Fast Fourier Transform on a Vector Computer. Math. Comp. 33, 147 (1979), 977–992. http://www.jstor.org/stable/2006072
[22]
Ahmed Kosba. 2019. jsnark: a Java library for building circuits for preprocessing zk-SNARKs.https://github.com/akosba/jsnark
[23]
Patrick Longa and Michael Naehrig. 2016. Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography. Cryptology ePrint Archive, Paper 2016/504. https://eprint.iacr.org/2016/504 https://eprint.iacr.org/2016/504.
[24]
Tao Lu, Chengkun Wei, Ruijing Yu, Chaochao Chen, Wenjing Fang, Lei Wang, Zeke Wang, and Wenzhi Chen. 2022. cuZK: Accelerating Zero-Knowledge Proof with A Faster Parallel Multi-Scalar Multiplication Algorithm on GPUs. Cryptology ePrint Archive, Paper 2022/1321. https://eprint.iacr.org/2022/1321 https://eprint.iacr.org/2022/1321.
[25]
Weiliang Ma, Qian Xiong, Xuanhua Shi, Xiaosong Ma, Hai Jin, Haozhao Kuang, Mingyu Gao, Ye Zhang, Haichen Shen, and Weifang Hu. 2023. GZKP: A GPU Accelerated Zero-Knowledge Proof System. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (Vancouver, BC, Canada) (ASPLOS 2023). Association for Computing Machinery, New York, NY, USA, 340–353. https://doi.org/10.1145/3575693.3575711
[26]
Lingchuan Meng, Yevgen Voronenko, Jeremy R. Johnson, Marc Moreno Maza, Franz Franchetti, and Yuzhen Xie. 2010. Spiral-generated modular FFT algorithms. In Proceedings of the 4th International Workshop on Parallel and Symbolic Computation (Grenoble, France) (PASCO ’10). Association for Computing Machinery, New York, NY, USA, 169–170. https://doi.org/10.1145/1837210.1837235
[27]
Ahmet Can Mert, Emre Karabulut, Erdinç Öztürk, Erkay Savaş, and Aydin Aysu. 2022. An Extensive Study of Flexible Design Methods for the Number Theoretic Transform. IEEE Trans. Comput. 71, 11 (2022), 2829–2843. https://doi.org/10.1109/TC.2020.3017930
[28]
Jianqiao Mo, Jayanth Gopinath, and Brandon Reagen. 2023. HAAC: A Hardware-Software Co-Design to Accelerate Garbled Circuits. In Proceedings of the 50th Annual International Symposium on Computer Architecture (Orlando, FL, USA) (ISCA ’23). Association for Computing Machinery, New York, NY, USA, Article 10, 13 pages. https://doi.org/10.1145/3579371.3589045
[29]
Peter L. Montgomery. 1985. Modular Multiplication Without Trial Division. Math. Comp. 44, 170, 519–521. http://www.jstor.org/stable/2007970
[30]
Marshall C. Pease. 1968. An Adaptation of the Fast Fourier Transform for Parallel Processing. J. ACM 15, 2 (apr 1968), 252–264. https://doi.org/10.1145/321450.321457
[31]
Nicholas Pippenger. 1976. On the evaluation of powers and related problems. In 17th Annual Symposium on Foundations of Computer Science (sfcs 1976). 258–263. https://doi.org/10.1109/SFCS.1976.21
[32]
Sujoy Sinha Roy, Furkan Turan, Kimmo Jarvinen, Frederik Vercauteren, and Ingrid Verbauwhede. 2019. FPGA-based High-Performance Parallel Architecture for Homomorphic Computing on Encrypted Data. Cryptology ePrint Archive, Paper 2019/160. https://eprint.iacr.org/2019/160 https://eprint.iacr.org/2019/160.
[33]
Nikola Samardzic, Axel Feldmann, Aleksandar Krastev, Srinivas Devadas, Ronald Dreslinski, Christopher Peikert, and Daniel Sanchez. 2021. F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption. In MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture (Virtual Event, Greece) (MICRO ’21). Association for Computing Machinery, New York, NY, USA, 238–252. https://doi.org/10.1145/3466752.3480070
[34]
Nikola Samardzic, Axel Feldmann, Aleksandar Krastev, Nathan Manohar, Nicholas Genise, Srinivas Devadas, Karim Eldefrawy, Chris Peikert, and Daniel Sanchez. 2022. CraterLake: A Hardware Accelerator for Efficient Unbounded Computation on Encrypted Data. In Proceedings of the 49th Annual International Symposium on Computer Architecture (New York, New York) (ISCA ’22). Association for Computing Machinery, New York, NY, USA, 173–187. https://doi.org/10.1145/3470496.3527393
[35]
Deepraj Soni, Negar Neda, Naifeng Zhang, Benedict Reynwar, Homer Gamil, Benjamin Heyman, Mohammed Nabeel, Ahmad Al Badawi, Yuriy Polyakov, Kellie Canida, Massoud Pedram, Michail Maniatakos, David Bruce Cousins, Franz Franchetti, Matthew French, Andrew Schmidt, and Brandon Reagen. 2023. RPU: The Ring Processing Unit. In 2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 272–282. https://doi.org/10.1109/ISPASS57527.2023.00034
[36]
Jiaheng Zhang, Zhiyong Fang, Yupeng Zhang, and Dawn Song. 2020. Zero Knowledge Proofs for Decision Tree Predictions and Accuracy. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (Virtual Event, USA) (CCS ’20). Association for Computing Machinery, New York, NY, USA, 2039–2053. https://doi.org/10.1145/3372297.3417278
[37]
Ye Zhang, Shuo Wang, Xian Zhang, Jiangbin Dong, Xingzhong Mao, Fan Long, Cong Wang, Dong Zhou, Mingyu Gao, and Guangyu Sun. 2021. PipeZK: Accelerating Zero-Knowledge Proof with a Pipelined Architecture. In 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA).
[38]
Zhichao Zhao and T.-H. Hubert Chan. 2016. How to Vote Privately Using Bitcoin. In Information and Communications Security, Sihan Qing, Eiji Okamoto, Kwangjo Kim, and Dongmei Liu (Eds.). Springer International Publishing, Cham, 82–96.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
PACT '24: Proceedings of the 2024 International Conference on Parallel Architectures and Compilation Techniques
October 2024
375 pages
ISBN:9798400706318
DOI:10.1145/3656019
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 October 2024

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Cryptography
  2. Hardware Acceleration
  3. Zero-Knowledge Proofs

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Funding Sources

Conference

PACT '24
Sponsor:

Acceptance Rates

Overall Acceptance Rate 121 of 471 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 151
    Total Downloads
  • Downloads (Last 12 months)151
  • Downloads (Last 6 weeks)45
Reflects downloads up to 26 Dec 2024

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

HTML Format

View this article in HTML Format.

HTML Format

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media