Document Open Access Logo

Revisiting the Nova Proof System on a Cycle of Curves

Authors Wilson D. Nguyen, Dan Boneh, Srinath Setty

PDF
Thumbnail PDF

File

LIPIcs.AFT.2023.18.pdf
  • Filesize: 0.87 MB
  • 22 pages

Document Identifiers

Author Details

Wilson D. Nguyen
  • Stanford University, CA, USA
Dan Boneh
  • Stanford University, CA, USA
Srinath Setty
  • Microsoft Research, Redmond, WA, USA

Funding

This work was partially funded by NSF, DARPA, the Simons Foundation, and NTT Research. Opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of DARPA.

Cite As Get BibTex

Wilson D. Nguyen, Dan Boneh, and Srinath Setty. Revisiting the Nova Proof System on a Cycle of Curves. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.AFT.2023.18

Abstract

Nova is an efficient recursive proof system built from an elegant folding scheme for (relaxed) R1CS statements. The original Nova paper (CRYPTO'22) presented Nova using a single elliptic curve group of order p. However, for improved efficiency, the implementation of Nova alters the scheme to use a 2-cycle of elliptic curves. This altered scheme is only described in the code and has not been proven secure. In this work, we point out a soundness vulnerability in the original implementation of the 2-cycle Nova system. To demonstrate this vulnerability, we construct a convincing Nova proof for the correct evaluation of 2^{75} rounds of the Minroot VDF in only 116 milliseconds. We then present a modification of the 2-cycle Nova system and formally prove its security. The modified system also happens to be more efficient than the original implementation. In particular, the modification eliminates an R1CS instance-witness pair from the recursive proof. The implementation of Nova has now been updated to use our optimized and secure system. In addition, we show that the folding mechanism at the core of Nova is malleable: given a proof for some statement z, an adversary can construct a proof for a related statement z', at the same depth as z, without knowledge of the witness for z'.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptanalysis and other attacks
Keywords
  • Cryptographic Protocols
  • Recursive Proof Systems
  • Folding
  • Vulnerability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Benedikt Bünz and Binyi Chen. ProtoStar: Generic efficient accumulation/folding for special sound protocols. Cryptology ePrint Archive, Paper 2023/620, 2023. URL: https://eprint.iacr.org/2023/620.
  2. Benedikt Bünz, Alessandro Chiesa, William Lin, Pratyush Mishra, and Nicholas Spooner. Proof-carrying data without succinct arguments. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021, Part I, volume 12825 of Lecture Notes in Computer Science, pages 681-710, Virtual Event, August 16-20 2021. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-84242-0_24.
  3. Quang Dao and Paul Grubbs. Spartan and bulletproofs are simulation-extractable (for free!). In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023, Part II, volume 14005 of Lecture Notes in Computer Science, pages 531-562, Lyon, France, April 23-27 2023. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-031-30617-4_18.
  4. Quang Dao, Jim Miller, Opal Wright, and Paul Grubbs. Weak fiat-shamir attacks on modern proof systems. Cryptology ePrint Archive, Paper 2023/691, 2023. URL: https://eprint.iacr.org/2023/691.
  5. Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, and Amit Sahai. Robust non-interactive zero knowledge. In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 566-598, Santa Barbara, CA, USA, August 19-23 2001. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/3-540-44647-8_33.
  6. Morris Dworkin. SHA-3 standard: Permutation-based hash and extendable-output functions, 2015-08-04 2015. URL: https://doi.org/10.6028/NIST.FIPS.202.
  7. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, Advances in Cryptology - CRYPTO'86, volume 263 of Lecture Notes in Computer Science, pages 186-194, Santa Barbara, CA, USA, August 1987. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/3-540-47721-7_12.
  8. Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. Poseidon: A new hash function for zero-knowledge proof systems. In Michael Bailey and Rachel Greenstadt, editors, USENIX Security 2021: 30th USENIX Security Symposium, pages 519-535. USENIX Association, August 11-13 2021. Google Scholar
  9. Jens Groth. Simulation-sound NIZK proofs for a practical language and constant size group signatures. In Xuejia Lai and Kefei Chen, editors, Advances in Cryptology - ASIACRYPT 2006, volume 4284 of Lecture Notes in Computer Science, pages 444-459, Shanghai, China, December 3-7 2006. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/11935230_29.
  10. Dmitry Khovratovich, Mary Maller, and Pratyush Ranjan Tiwari. MinRoot: Candidate sequential function for Ethereum VDF. Cryptology ePrint Archive, Paper 2022/1626, 2022. URL: https://eprint.iacr.org/2022/1626.
  11. Abhiram Kothapalli and Srinath Setty. HyperNova: Recursive arguments for customizable constraint systems. Cryptology ePrint Archive, Paper 2023/573, 2023. URL: https://eprint.iacr.org/2023/573.
  12. Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla. Nova: Recursive zero-knowledge arguments from folding schemes. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022, Part IV, volume 13510 of Lecture Notes in Computer Science, pages 359-388, Santa Barbara, CA, USA, August 15-18 2022. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-031-15985-5_13.
  13. Nicholas Mohnblatt. Sangria: A folding scheme for PLONK, 2023. URL: https://github.com/geometryresearch/technical_notes/blob/main/sangria_folding_plonk.pdf.
  14. Nova Contributors. Nova implementation, 2022. URL: https://github.com/Microsoft/Nova.
  15. oskarth. Towards a nova-based ZK virtual machine. https://zkresear.ch/t/towards-a-nova-based-zk-vm/105, 2023.
  16. Pasta Contributors. Pasta curves, 2020. URL: https://github.com/zcash/pasta_curves.
  17. Carla Ràfols and Alexandros Zacharakis. Folding schemes with selective verification. Cryptology ePrint Archive, Report 2022/1576, 2022. URL: https://eprint.iacr.org/2022/1576.
  18. Srinath Setty. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology - CRYPTO 2020, Part III, volume 12172 of Lecture Notes in Computer Science, pages 704-737, Santa Barbara, CA, USA, August 17-21 2020. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-56877-1_25.
  19. Srinath Setty. Nova pull request 167, 2023. URL: https://github.com/Microsoft/Nova/pull/167.
  20. Supernational. Open VDF: Accelerating the nova snark-based vdf. https://medium.com/supranational/open-vdf-accelerating-the-nova-snark-based-vdf-2d00737029bd, 2023.
  21. Paul Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In Ran Canetti, editor, TCC 2008: 5th Theory of Cryptography Conference, volume 4948 of Lecture Notes in Computer Science, pages 1-18, San Francisco, CA, USA, March 19-21 2008. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-540-78524-8_1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact