Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data

Provided by: Tel Aviv University
Topic: Security
Format: PDF
Succinct Non-interactive ARguments of Knowledge (SNARKs), and their generalization to distributed computations by Proof-Carrying Data (PCD), are powerful tools for enforcing the correctness of dynamically evolving computations among multiple mutually-untrusting parties. The authors present recursive composition and bootstrapping techniques that: transform any SNARK with an expensive preprocessing phase into a SNARK without such a phase, transform any SNARK into a PCD system for constant-depth distributed computations and transform any PCD system for constant-depth distributed computations into a PCD system for distributed computation over paths of fixed polynomial length. Their transformations apply to both the public- and private-verification settings, and assume the existence of CRHs; for the private-verification setting, they additionally assume FHE.

Find By Topic