Revisiting the Nova Proof System on a Cycle of Curves

Wilson Nguyen; Dan Boneh; Srinath Setty

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

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 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: incremental verifiable computation recursive proof systems vulnerability cycle of elliptic curves IVC
Contact author(s): wdnguyen @ cs stanford edu
dabo @ cs stanford edu
srinath @ microsoft com
History: 2023-06-20: approved; 2023-06-20: received; See all versions
Short URL: https://ia.cr/2023/969
License: CC BY

BibTeX

@misc{cryptoeprint:2023/969,
      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},
      url = {https://eprint.iacr.org/2023/969}
}