“Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings” Summary

Hankyung Ko
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).

Hankyung Ko

Written by

Currently pursuing PhD degree at Hanyang University, Seoul, Korea. www.linkedin.com/in/hankyung-ko-b892a7119

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade