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

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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.

作者简介

D. Kondyrev

Novosibirsk State University

编辑信件的主要联系方式.
Email: dkondyrev@gmail.com
俄罗斯联邦, Pirogova st. 2, Novosibirsk, 630090

参考

  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.

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © Russian Academy of Sciences, 2024

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».