“Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings” Summary
Nov 4 · 2 min read
presented by Mary Maller, Markulf Kohlweiss, Sean Bowe, and Sarah Meiklejohn, in CCS 2019.
Motivation
- Nearly trustless SNARK Setup
- zk-SNARK :
1) generic computation zero-knowledge proof
2) fast to verify
3) small proofs - requires parameter setup
1) universal parameters : only one setup
2) updatable parameters : setup never ends
3) Linear-sized parameters
* Previous updatable setup scheme (Groth et al. “Updatable and Universal CRS with applications to zk-SNARK”) has quadratic-sized universal crs
Polynomial Commitments

Constraints Systems (Bootle et al. Arithmetization)
- Let a, b, c be a witness assignment, and k be an instance assignment.



The basic Sonic Protocol
- The prover construct r(X,Y) by using their hidden witness a, b, c.

Polynomial Commitment Scheme
- evaluation binding :
given a commitment F, an adversary cannot open F to two different evaluations v1 and v2. - bounded polynomial extractable :
any algebraic adversary that opens a commitment F knows an opening f(X) with powers -d ≤ i ≤ max, i ≠ -d+max. - f(X) - f(z) is divisible by (X - z).

