Fry Based Polynomial Commitments

Lecture Eight of ZK Learning MOOC

Slide1: 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

Slide2: 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

Slide3: 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

Slide4: 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

Slide5: 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

Slide6: 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

Slide7: 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

Slide8: 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

Slide9: 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

Other Free PPT Tools

Icon 1
Icon 2

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
Icon 1
Icon 2

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
Icon 1
Icon 2

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
Icon 1
Icon 2

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
Icon 1
Icon 2

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
Icon 1
Icon 2

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
Icon 1
Icon 2

Docx to PPT using AI

Transform Word documents into dynamic presentations. Suitable for administrators and writers enhancing their documents visually.

Create PPT from Docx
Icon 1
Icon 2

Tome Url to PPT using AI

Stuck with a Tome presentation? Convert it to PowerPoint format for use with Google Slides or PowerPoint effortlessly.

Create PPT from Tome.app Url
Icon 1
Icon 2

Gamma Url to PPT using AI

Stuck with a Gamma presentation? Convert it to PowerPoint format for use with Google Slides or PowerPoint effortlessly.

Create PPT from Gamma Url
Icon 1
Icon 2

Image to PPT using AI

Convert Image to PPT with a single click. Click "upload Image" select your image and we will create presentation with the same.

Create PPT from Image
Icon 1
Icon 2

Video to PPT using AI

Easily convert video content into engaging slide presentations. Perfect for businesses, educators, and content creators looking to turn videos into informative presentations.

Convert Video to PPT
Icon 1
Icon 2

MagicChart

Create charts from text online instantly. Streamline data visualization for presentations and reports.

Create Chart from Text
Icon 1
Icon 2

PPT to JPG

Convert PowerPoint slides to high-quality JPG images online. Useful for archiving or sharing presentations visually.

Create JPG from PPT
Icon 1
Icon 2

PPT to PDF

Turn your PowerPoint presentations into PDFs seamlessly. Ideal for securing and distributing presentations professionally.

Create PDF from PPT
Icon 1
Icon 2

PPT to MP4

Convert PowerPoint slides into MP4 videos. Great for creating shareable video content from presentations.

Create MP4 from PPT
Icon 1
Icon 2

PPT to Text

Single click convert Your PPT to TXT File in Seconds - Free, Secure, and User-Friendly!

Convert PPT to Text
Icon 1
Icon 2

PPT to Better PPT

have a rought ppt just text and want to make it better? we will take the test and generate one using magicslides.app

Design My PPT
Icon 1
Icon 2

PDF to JPG

Convert PDF to high-quality JPG images online. Useful for archiving or sharing presentations visually.

Create JPG from PDF
Icon 1
Icon 2

PPT Translator

Easily translate PowerPoint presentations while retaining formatting.

Translate PPT

This presentation was made with Youtube to PPT