Constant-Size Commitments to Polynomials and Their Applications

01 Claim ledger

What the paper is allowed to say

Each row is a sentence already in the study. The status is the same on every row: a model claim, not a live measurement.

1. Claim 01 · Paper model

   One element, the whole polynomial

   The commitment does not grow with the degree, up to the size of the setup. That is why later systems use it for large objects such as data blobs and circuits.

2. Claim 02 · Paper model

   Openings are the feature

   A hash would also bind. A hash would not let you prove the value at one index without revealing a large neighbourhood. The pairing equation is what makes the opening small.

3. Claim 03 · Paper model

   The setup is a real trust

   The structured string is a sequence of encrypted powers of a secret. Anyone who knows the secret can open the commitment dishonestly. A ceremony is an attempt to ensure nobody knows it.

4. Claim 04 · Paper model

   It is a brick

   KZG does not sample data, order transactions, or prove a virtual machine. Protocols that say they use KZG still have to say what polynomial they commit to and what else is checked.

02 Three cuts

Observation, model, falsifier

A desk does not stop at the summary. Each claim is cut three ways, using only this study's own assumptions and checks. Nothing here is a new figure.

1. 01 One element, the whole polynomial

   Observation

   What the study says

   The commitment does not grow with the degree, up to the size of the setup. That is why later systems use it for large objects such as data blobs and circuits.

   Model

   What has to hold

   The degree of the polynomial is within the length of the setup. A longer polynomial is not committed by that string.

   Falsifier

   What would retire it

   What polynomial is being committed to?

2. 02 Openings are the feature

   Observation

   What the study says

   A hash would also bind. A hash would not let you prove the value at one index without revealing a large neighbourhood. The pairing equation is what makes the opening small.

   Model

   What has to hold

   The pairing assumptions in the paper hold for the chosen groups.

   Falsifier

   What would retire it

   Is an opening checked on chain, or merely assumed?

3. 03 The setup is a real trust

   Observation

   What the study says

   The structured string is a sequence of encrypted powers of a secret. Anyone who knows the secret can open the commitment dishonestly. A ceremony is an attempt to ensure nobody knows it.

   Model

   What has to hold

   The setup secret was destroyed. Knowledge of it breaks binding.

   Falsifier

   What would retire it

   Which ceremony produced the setup, and how was the secret destroyed?

4. 04 It is a brick

   Observation

   What the study says

   KZG does not sample data, order transactions, or prove a virtual machine. Protocols that say they use KZG still have to say what polynomial they commit to and what else is checked.

   Model

   What has to hold

   The degree of the polynomial is within the length of the setup. A longer polynomial is not committed by that string.

   Falsifier

   What would retire it

   What polynomial is being committed to?

03 Sequence

One action, as an operating tape

1. 01A setup publishes encrypted powers of a secret and discards the secret.
2. 02The prover evaluates their polynomial against that string and publishes one group element as the commitment.
3. 03To claim the polynomial takes a value at a point, the prover publishes a quotient commitment.
4. 04The verifier checks a pairing product. It does not read the coefficients.
5. 05Multiple openings can be batched by later techniques. The 2010 paper is the single opening and the binding.

04 Load-bearing

The argument, and where a pitch drops it

1. Constant size moved the risk into the ceremony

   The cut

   The attractive property is exactly what a trapdoor undermines. A system that cannot name its powers-of-tau ceremony has a constant-size proof and an unnamed trusted party.

   Why it carries weight

   If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.

   Where it is dropped

   A universal setup shared by many teams is still a setup. Updatability has to be proved of the ceremony they actually ran.

2. Commitments are not availability

   The cut

   A commitment can be published while the polynomial's actual coefficients are withheld. Sampling and dispersal, as in the fraud-and-data-availability line, are what talk about publication. KZG is what those schemes often commit with.

   Why it carries weight

   If this cut is skipped, the paper's name is being used without the mechanism that makes the name mean anything.

   Where it is dropped

   KZG is not a blockchain, a rollup, or a sampling protocol. It is a commitment.

05 Register

What has to be true

• Model · Not re-measured

  The pairing assumptions in the paper hold for the chosen groups.

• Model · Not re-measured

  The setup secret was destroyed. Knowledge of it breaks binding.

• Model · Not re-measured

  The degree of the polynomial is within the length of the setup. A longer polynomial is not committed by that string.

• Model · Not re-measured

  The verifier checks the pairing against the public setup everyone agreed on.

06 Divergence

What happened after the paper

PLONK-style proofs and several data-availability designs use KZG as the polynomial commitment. Verkle trees and blob constructions sit in the same family. The 2010 paper does not mention blobs. It is the citation for the commitment, and the ceremony of each later system is a separate object that has to be audited on its own.

A later client, parameter set, or reward formula is a different object. Cite this paper for the mechanism. Cite a primary release for the network. This desk has not re-run the proof.

07 Pre-mortem

What to check before you use the idea

1. Kill test 1What polynomial is being committed to?
2. Kill test 2Which ceremony produced the setup, and how was the secret destroyed?
3. Kill test 3Is an opening checked on chain, or merely assumed?
4. Kill test 4What ensures the underlying data, not just the commitment, was published?
5. 0 of 4 marked on this browser. A mark is a reading note, not a pass, a rating, or a recommendation.

08 Anatomy

The paper, in the order a builder needs

09 Lexicon

Terms, opened into the record

Polynomial commitment

A short object that binds the prover to one polynomial and lets them open it at chosen points.

Powers of tau

The structured setup: encrypted successive powers of a secret that must not be retained.

10 Repository

Every linked record on this page

Underlined words open a page that already exists: a concept, a protocol profile, a failure record, or another paper. If a word is not underlined, this desk does not have a record for it.

11 Related

The next papers, as theses

• PLONK · 2019

  PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

  A SNARK with a universal and updatable structured reference string. One setup can serve many circuits. The proofs are larger than Groth16, and there is still a setup.

• Fraud and data availability proofs · 2018

  Fraud and Data Availability Proofs

  Light clients can refuse a block if a fraud proof shows it is invalid, but only if the block's data was actually published. The paper shows how erasure coding and sampling let clients check publication without downloading everything.

• Celestia · 2019

  LazyLedger: A Distributed Data Availability Ledger With Client-Side Smart Contracts

  Al-Bassam's LazyLedger paper, the research origin of Celestia. The base layer orders and makes data available. It does not execute application transitions. Clients check availability with sampling, and applications execute on their own.