Paper 2024/507

An Efficient SNARK for Field-Programmable and RAM Circuits

Jehyuk Jang, Tokamak Network
Jamie Judd, Tokamak Network
Abstract

The advancement of succinct non-interactive argument of knowledge (SNARK) with constant proof size has significantly enhanced the efficiency and privacy of verifiable computation. Verifiable computation finds applications in distributed computing networks, particularly in scenarios where nodes cannot be generally trusted, such as blockchains. However, fully harnessing the efficiency of SNARK becomes challenging when the computing targets in the network change frequently, as the SNARK verification can involve some untrusted preprocess of the target, which is expected to be reproduced by other nodes. This problem can be addressed with two approaches: One relieves the reproduction overhead by reducing the dimensionality of preprocessing data; The other utilizes verifiable machine computation, which eliminates the dependency on preprocess at the cost of increased overhead to SNARK proving and verification. In this paper, we propose a new SNARK with constant proof size applicable to both approaches. The proposed SNARK combines the efficiency of Groth16 protocol, albeit lacking universality for new problems, and the universality of PlonK protocol, albeit with significantly larger preprocessing data dimensions. Consequently, we demonstrate that our proposed SNARK maintains the efficiency and the universality while significantly reducing the dimensionality of preprocessing data. Furthermore, our SNARK can be seamlessly applied to the verifiable machine computation, requiring a proof size smaller about four to ten times than other related works.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
zero-knowledge proofSNARKverifiable computationpreprocessargument of knowledgecircuitrandom access machine
Contact author(s)
cjhyuck213 @ gmail com
jamie @ tokamak network
History
2024-04-01: revised
2024-03-30: received
See all versions
Short URL
https://ia.cr/2024/507
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/507,
      author = {Jehyuk Jang and Jamie Judd},
      title = {An Efficient {SNARK} for Field-Programmable and {RAM} Circuits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/507},
      year = {2024},
      url = {https://eprint.iacr.org/2024/507}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.