Paper 2023/969

Revisiting the Nova Proof System on a Cycle of Curves

Wilson Nguyen, Stanford University
Dan Boneh, Stanford University
Srinath Setty, Microsoft Research

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 1.46 seconds. 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. We also show that Nova's IVC proofs are malleable and discuss several mitigations.

Available format(s)
Cryptographic protocols
Publication info
incremental verifiable computationrecursive proof systemsvulnerabilitycycle of elliptic curvesIVC
Contact author(s)
wdnguyen @ cs stanford edu
dabo @ cs stanford edu
srinath @ microsoft com
2023-06-20: approved
2023-06-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Wilson Nguyen and Dan Boneh and Srinath Setty},
      title = {Revisiting the Nova Proof System on a Cycle of Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2023/969},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.