DownloadCreate AI Presentation

Fry Based Polynomial Commitments

Lecture Eight of ZK Learning MOOC

Introduction

  • Lecture Eight
  • Covering Fry based polynomial commitments and the Fiat Shamir transformation
  • Polynomial IOP and polynomial commitment scheme combine to form an interactive argument (SNARK)
  • Different protocols have unique performance profiles and trade-offs

Polynomial IOP and Commitment Scheme

  • Polynomial IOP: Prover's first message specifies a large polynomial H
  • Verifier evaluates H at a single point of their choosing
  • Subsequent messages are short and fully read by the verifier
  • Verifier decides whether to accept or reject the claim as valid
  • Polynomial Commitment Scheme: Allows the prover to simulate the polynomial IOP
  • Verifiable evaluation proofs for the polynomial commitment scheme

Performance Profiles of Polynomial IOP and Commitment Schemes

  • Different polynomial IOPs and polynomial commitment schemes have unique performance profiles
  • Consider trade-offs such as prover time, verification costs, and security
  • Transparent and plausibly post-quantum secure options
  • Polynomial commitment schemes categorized based on pairing friendly, discrete logarithm, and hashing

Transparent SNARKs

  • Examples: Halo 2, Starks, Fractal, Aurora, Virgo
  • Halo 2: Shortest proofs, slow verifier
  • Starks, Fractal, Aurora, Virgo: Combining polynomial IOP with fry-based commitments
  • Pros: Shortest proofs among plausibly post-quantum snarks
  • Cons: Proofs still large, limited flexibility in field used

Non-Transparent SNARKs

  • Examples: Groth16, Marlin, Planck
  • Groth16: Best verification costs, circuit-specific trusted setup
  • Marlin, Planck: Trusted setup independent, larger proofs, slower prover
  • Pros: Trusted setup independence, applicable to various circuit types
  • Cons: Larger proofs, slower prover compared to Groth16
  • Final choice depends on circuit type and specific requirements

Fry Based Polynomial Commitments

  • Prover only commits to evaluations of Q for points in a carefully chosen subset
  • Subset Omega consists of nth roots of unity
  • Size of Omega depends on the blow-up factor
  • Prover time grows with the blow-up factor
  • Verification costs decrease logarithmically with the blow-up factor
  • Optimal blow-up factor balances prover and verifier costs

The Subset Omega

  • Omega consists of nth roots of unity
  • Primitive nth root of unity, square yields an N/2 root of unity
  • Each nth root has a corresponding negative nth root
  • Largest power of two dividing N relates to the field size
  • Subset Omega depends on the power of two dividing the field size minus one

Example of Roots of Unity

  • Example: Prime field of order 41
  • Size of multiplicative subgroup: 40
  • Divisible by 8 (largest power of two dividing 40)
  • Eight 8th roots of unity: 1, -1, 9, -9, 3, -3, 14, -14
  • Fry commits to evaluations on a through to Unity

Low Degree Test in Fry

  • Verifier inspects a few entries of the committed vector
  • Authentication paths provided by prover for each query
  • Traditional low degree tests impractical in the context of fry
  • Fry's low degree test will be interactive
  • Combines a folding phase and a random challenge phase

Related Presentations

The Impact of Music on Our Lives

Multiplying Polynomials

Understanding the CPU: An Inside Look

The Challenges of Linux for Desktop Users

Exploring Transcranial Magnetic Stimulation for Depression Treatment

Embracing Challenges and Reaching Dreams