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

Other Free PPT Tools

Topic to PPT using AI

Generate engaging presentations quickly from just a keyword. Ideal for students and educators needing fast, content-rich slides.

Create PPT from Topic
AI

YouTube to PPT using AI

Turn YouTube videos into informative slide presentations. Excellent for marketers and creators looking to expand their video content's reach.

Create PPT from YouTube
AI

AI PitchDeck Generator

Turn Pitch Deck into informative slide presentations. Excellent for business and startup looking to present his business.

Create PPT from Pitch Deck
AI

Text to PPT using AI

Generate engaging presentations quickly from just a keyword. Ideal for students and educators needing fast, content-rich slides.

Create PPT from Text
AI

URL to PPT using AI

Effortlessly convert any web page into a comprehensive presentation. Perfect for professionals and researchers presenting web-based data.

Create PPT from URL
AI

PDF to PPT using AI

Convert PDF files to PowerPoint slides easily. Essential for analysts and consultants dealing with detailed reports.

Create PPT from PDF
AI