Comparative efficiency analysis of hashing algorithms for applications in zk-SNARK circuits in distributed ledgers

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

The paper presents a comparative efficiency analysis of hashing algorithms in terms of applicability in zk-SNARK based systems. We have considered the hash functions sha256, sha3, blake2, mimc and poseidon, which are most widely used in modern distributed ledgers. To conduct experiments with measuring parameters, an infrastructure based on the ZoKrates toolbox was developed. A series of measurements with different input data was carried out for each algorithm. The number of constraints in the R1CS representation of the algorithm, the length of the proof key and the verification key, the running time of the setup phase of the protocol, and the proof generation time were measured. Based on the obtained results, we determined the boundaries of the practical applicability of algorithms for the problem of proving the knowledge of the preimage of a hash function using zk-SNARK circuits in distributed ledgers, and also identified emerging efficiency problems.

About the authors

D. О. Kondyrev

Novosibirsk State University

Author for correspondence.
Email: dkondyrev@gmail.com
Russian Federation, Pirogova st. 2, Novosibirsk, 630090

References

  1. Kondyrev D.O. Overview of privacy preserving technologies for distributed ledgers // Eurasian Journal of Mathematical and Computer Applications. 2021. V. 9. № 1. P. 55–68.
  2. Ben-Sasson E., Chiesa A., Genkin D., Tromer E., Virza M. SNARKs for C: Verifying program executions succinctly and in zero knowledge // CRYPTO'2013, LNCS. 2013. V. 8043. P. 90–108.
  3. Ben-Sasson E., Chiesa A., Garman C., Green M., Miers I., Tromer E., Virza M. Zerocash: Decentralized anonymous payments from bitcoin // IEEE Symp. Security and Privacy, San Jose, USA. 2014. P. 459–474.
  4. NIST. FIPS PUB180–2, Secure hash standard. 2002.
  5. NIST. FIPS PUB202, SHA-3 standard: permutation-based hash and extendable-output functions. 2015.
  6. Aumasson J.P., Neves S., Wilcox-O’Hearn Z., Winnerlein C. BLAKE2: simpler, smaller, fast as MD5 // ACNS2013, Proceedings of the 11th International Conference Applied Cryptography and Network Security, Banff, AB, Canada. 2013. V. 7954 of LNCS, P. 119–135.
  7. Grassi L., Khovratovich D., Rechberger C., Roy A., Schofnegger M. Poseidon: A New Hash Function for Zero-Knowledge Proof Systems // Proceedings of the 30th USENIX Security Symposium. 2021. V. 2021.
  8. Albrecht M., Grassi L., Rechberger C., Roy A., Tiessen T. MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity // ASIACRYPT 2016. Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam. 2016. Part I. V. 10031 of LNCS. P. 191–219.
  9. Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C, John Wiley & Sons Inc., 1996, 2nd ed.
  10. Sun X., Yu F.R., Zhang P., Sun Z., Xie W., Peng X. A survey on zero-knowledge proof in blockchain // IEEE network. 2021. V. 35. № 4. P. 198–205.
  11. Konkin A., Zapechnikov S. Zero knowledge proof and ZK-SNARK for private blockchains // Journal of Computer Virology and Hacking Techniques. 2023. P. 1–7.
  12. Thibault L.T., Sarry T., Hafid A.S. Blockchain scaling using rollups: A comprehensive survey // IEEE Access. 2022.
  13. Raikwar M., Gligoroski D., Kralevska K. SoK of Used Cryptography in Blockchain // IEEE Access. 2019. V. 7. P. 148550–148575.
  14. Wang L., Shen X., Li J., Shao J., Yang Y. Cryptographic primitives in blockchains // Journal of Network and Computer Applications. 2019. V. 127. P. 43–58.
  15. Virza M. On Deploying Succinct Zero-Knowledge Proofs // PhD Thesis. Massachusetts Institute of Technology. 2017. 131 p.
  16. Eberhardt J. Scalable and Privacy-preserving Off-chain Computations // PhD Thesis. Technical University of Berlin. 2021. 284 p.
  17. Yaga D., Mell P., Roby N., Scarfone K. Blockchain technology overview // NIST Interagency/Internal Report (NISTIR) – 8202. 2018.
  18. Grassi L., Khovratovich D., Luftenegger R., Rechberger C., Schofnegger M., Walch R. Reinforced concrete: A fast hash function for verifiable computation // Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022. P. 1323–1335.
  19. Eberhardt J., Tai S. ZoKrates – scalable privacy-preserving off-chain computations // IEEE Intern. Conf. Blockchain. Halifax, Canada. 2018. P. 1084–1091.
  20. https://github.com/Zokrates/ZoKrates – ZoKrates.
  21. Groth J. On the size of pairing-based non-interactive arguments // EUROCRYPT 2016. Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria. 2016. Part II 35. P. 305–326.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences