Paper 2023/974

MuxProofs: Succinct Arguments for Machine Computation from Vector Lookups

Zijing Di, Stanford University
Lucas Xia, Stanford University
Wilson Nguyen, Stanford University
Nirvan Tyagi, Stanford University
Abstract

Proofs for machine computation prove the correct execution of arbitrary programs that operate over fixed instruction sets (e.g., RISC-V, EVM, Wasm). A standard approach for proving machine computation is to prove a universal set of constraints that encode the full instruction set at each step of the program execution. This approach incurs a proving cost per execution step on the order of the total sum of instruction constraints for all of the instructions in the set, despite each step of the program only executing a single instruction. Existing proving approaches that avoid this universal cost per step (and incur only the cost of a single instruction's constraints per step) either fail to provide zero-knowledge or rely on recursive proof composition for which security relies on the heuristic instantiation of the random oracle. We present new protocols for proving machine execution that resolve these limitations, enabling prover efficiency on the order of only the executed instructions while achieving zero-knowledge and avoiding recursive proofs. Our core technical contribution is a new primitive that we call a succinct vector lookup argument which enables a prover to build up a machine execution ``on-the-fly''. We propose succinct vector lookups for both univariate polynomial and multivariate polynomial commitments in which vectors are encoded on cosets of a multiplicative subgroup and on subcubes of the boolean hypercube, respectively. We instantiate our proofs for machine computation by integrating our vector lookups with existing efficient, succinct non-interactive proof systems for NP.

Note: Full version for ASIACRYPT accepted paper. Includes new result of multivariate subcube lookup argument.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2024
Keywords
zero-knowledge proofsmachine executionlookup arguments
Contact author(s)
nirvan tyagi @ gmail com
History
2024-10-14: last of 2 revisions
2023-06-21: received
See all versions
Short URL
https://ia.cr/2023/974
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/974,
      author = {Zijing Di and Lucas Xia and Wilson Nguyen and Nirvan Tyagi},
      title = {{MuxProofs}: Succinct Arguments for Machine Computation from Vector Lookups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/974},
      year = {2023},
      url = {https://eprint.iacr.org/2023/974}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.