Paper 2024/1651

One-Shot Native Proofs of Non-Native Operations in Incrementally Verifiable Computations

Tohru Kohrita, Nil Foundation
Patrick Towa, Aztec Labs
Zachary J. Williamson, Aztec Labs
Abstract

Proving non-native operations is still a bottleneck in existing incrementally verifiable computations. Prior attempts to solve this issue either simply improve the efficiency of proofs of non-native operations or require folding instances in each curve of a cycle. This paper shows how to avoid altogether in-circuit proofs of non-native operations in the incre- mental steps, and only record them in some auxiliary proof information. These operations are proved natively at the end of the computation, at the cost of only a small constant number (four or five) of non-native field multiplications to go from a non-native operation record to a native one. To formalise the security guarantees of the scheme, the paper introduces the concept of incrementally verifiable computation with auxiliary proof information, a relaxation of the standard notion of incrementally veri- fiable computation. The knowledge-soundness now guarantees the cor- rectness of a computation only if the piece of information attached to a proof is valid. This new primitive is thus only to be used if there is an efficient mechanism to verify the validity of that information. This relaxation is exactly what enables a construction which does not require in-circuit proofs of non-native operations during the incremental part of the computation. Instantiated in the Plonk arithmetisation, the construction leads to savings in circuit-gate count (compared to standard folding-based constructions) of at least one order of magnitude, and that can go up to a factor of 50.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
IVC;Recursive Arguments;SNARKs
Contact author(s)
tohru kohrita @ gmail com
patrick towa @ gmail com
zac @ aztecprotocol com
History
2024-10-14: revised
2024-10-13: received
See all versions
Short URL
https://ia.cr/2024/1651
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1651,
      author = {Tohru Kohrita and Patrick Towa and Zachary J. Williamson},
      title = {One-Shot Native Proofs of Non-Native Operations in Incrementally Verifiable Computations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1651},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1651}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.