Witness-Succinct Universally-Composable SNARKs

Chaya Ganesh, Yashvanth Kondi, Claudio Orlandi, Mahak Pancholi, Akira Takahashi, Daniel Tschudi

Abstract

Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zkSNARKs) are pivotal for verifiable computing, yet they often face a trade-off between security in complex environments and proof efficiency. This paper introduces a novel compiler that transforms standard zkSNARKs into versions that are both universally composable (UC) and witness-succinct. By achieving black-box straight-line extraction with constant-sized proofs, this work bridges the gap between the "gold standard" of security and the practical requirements of decentralized systems like blockchains.

Introduction

In privacy-preserving technologies, zkSNARKs allow a Prover to convince a Verifier of a statement's truth without revealing the underlying witness. However, a significant hurdle is Universal Composability (UC). For a protocol to be UC-secure, a Simulator must be able to extract the secret witness from a malicious prover in a straight-line (no rewinding) and black-box (no internal code access) manner.

Historically, achieving this level of extractability required sacrificing witness succinctness. Provers typically had to encrypt the entire witness and attach it to the proof, leading to proof sizes proportional to the witness size. This paper presents a breakthrough that maintains constant proof sizes while ensuring UC security.

Methodology: The Commit-then-Extract Compiler

The authors propose a compiler utilizing a "Commit-then-Extract" approach grounded in arithmetization and Fischlin’s Transformation.

  1. Polynomial Encoding: The witness $w$ is encoded as the coefficients of a polynomial $f(x)$.
  2. Succinct Commitment: A constant-sized Polynomial Commitment Scheme (PCS), specifically the KZG scheme, is used to commit to this polynomial.
  3. Forced Revelation (Fischlin’s Technique): To enable black-box extraction without bloating the proof, a "Proof-of-Work" mechanism is employed. The prover must find specific points where the polynomial evaluates to values that, when hashed with a Random Oracle, result in a specific prefix (e.g., a string of zeros).
  4. Straight-line Extraction: In the Global Random Oracle (GROM) model, a UC Simulator can monitor queries to the oracle. By observing the polynomial evaluations logged there, the simulator can reconstruct the entire polynomial—and thus the witness—without the witness ever being explicitly included in the proof.

Key Results and Comparison

The primary contribution is the first construction to simultaneously achieve UC-security, black-box straight-line extraction (BBE and SLE), and constant-sized proofs ($O(1)$ relative to the witness).

Comparison of various SNARK schemes across security and extraction properties.

As shown in Figure 1, existing schemes like STARK, Aurora, and RedShift achieve BBE and SLE but do not offer the constant proof sizes associated with KZG-based schemes. Conversely, popular schemes like Groth16 and PLONK offer SLE but fail to provide BBE. The proposed "Ours" constructions (integrated with GM17 or ARS20 and KZG10) are the first to check all these critical boxes in the GROM model while maintaining simulation-extractability (SIMEXT).

Discussion and Future Work

While this work bypasses the "folklore" limit that UC-security requires witness encryption, it does introduce some trade-offs. The resulting SNARKs inherit knowledge assumptions from their base components, and the prover's computational load increases due to the Proof-of-Work required by Fischlin's transform.

Future research may focus on "transparent" instantiations that eliminate the need for a Trusted Setup (like the "Powers of Tau" ceremonies) by utilizing alternative commitment schemes, such as those found in Bulletproofs, while maintaining the desired extraction properties.

Summary updated

BibTeX
@inproceedings{ganesh2023witness,
  author = {Chaya Ganesh and Yashvanth Kondi and Claudio Orlandi and Mahak Pancholi and Akira Takahashi and Daniel Tschudi},
  title = {{Witness-Succinct Universally-Composable SNARKs}},
  booktitle = {EUROCRYPT},
  year = {2023},
  doi = {10.1007/978-3-031-30617-4\_11},
}
Figure