(1/24) KZG Polynomial Commitments: The Complete Guide
Our goal: 1) prove we are committed to a specific set of data and 2) allow others to verify specific points within that dataset.
Want to see some mathematical magic? This megathread is for you!
(2/24) Elliptic curve cryptography and KZG polynomial commitments are HARD. This thread aims to give you a high level understanding of how KZG commitments work, while the linked threads go MUCH deeper.
Just remember: pink border = summary, blue border = details
(3/24) Before we get to KZG, let's first cover the basics: polynomial commitments.
First, take your dataset and break it into discrete chunks. Then, plot them on a graph and draw a line through those point. Now derive the formula for that line.
twitter.com/SalomonCrypto/status/1581462447491194880
(4/24) This formula is a polynomial, a special type of equation that has some very powerful mathematical properties.
This polynomial holds the same information as the raw data, but we can also use it to generate new points... maybe a point in between two "real" points.
(5/24) In fact, one of these "non-real" points will serve as our commitment: it confirms a party has complete knowledge of the dataset (else they would not be able to generate the polynomial) but it does not leak any of the underlying data.
Now, which "non-real" point to use...
(6/24) Ideally we'd like to use a completely random point, one that no malicious party could know beforehand. Then the prover couldn't precompute some points that look valid, but don't actually check out.
But where are we going to find a random number?
(7/24) Well, dear reader, at this point you may be asking yourself "where are the elliptic curves?!?!" This is your time!
We are going to use an elliptic curve!
twitter.com/SalomonCrypto/status/1581695845023350785
(8/24) (Modular) elliptic curves have many incredibly useful properties that we will be relying on. In particular, we care that:
- elliptic curve points can be added together
- when added repeatedly, it is INCREDIBLY difficult to figure how many times a point has been added
(9/24) Using these properties, we can hide a secret (random) number inside an elliptic curve. After we go through the trusted process and the secret number is permanently destroyed, the only knowledge of that value will be permanently hidden in the folds of the elliptic curve.
twitter.com/SalomonCrypto/status/1581864402076151809
(10/24) The result of the trusted setup is a Structured Reference String (SRS). The SRS conveys enough information that the random number is accessible for our polynomial (and therefore our polynomial commitment scheme) while still keeping the value entirely secret.
(11/24) Note: one SRS can be used by an arbitrary number of people; only one trusted setup (or one trusted setup per application) are needed for ALL KZG commitments.
For those interested in real world implementations, Vitalik has you covered:
vitalik.ca/general/2022/03/14/trustedsetup.html
(12/24) Another note, terminology.
Interactive Proof System: a method by which one party (prover) can prove to another (verifier) that a statement is true.
KZG: a prover can confirm a specific piece of data is in a dataset without revealing any other info about the dataset.
(13/24) Once we have our SRS and we've generated the polynomial from our data, we are ready to begin.
The prover is going to begin by applying the SRS to the data polynomial, generating a point on the elliptic curve.
We call this point a commitment.
twitter.com/SalomonCrypto/status/1582538525517369344
(14/24) The commitment will serve as an anchor, tying the prover to the original dataset. Any changes to the underlying data will result in a new polynomial and therefore a new commitment.
Changes to the data = previous commitments will generate invalid proofs.
(15/24) Now it's time for the verifier to test the prover. The verifier will select a position and request a proof based around that specific chunk of data.
The prover will divide the data polynomial to create a new quotient polynomial.
twitter.com/SalomonCrypto/status/1583283784761233408
(16/24) This division is the crux of the KZG commitment scheme. Polynomial division is a (relatively) easy procedure; as long as an honest prover has full access to the data (and therefore the data polynomial), he can create and evaluate this new quotient polynomial.
(17/24) The prover replies back with two items: the evaluation of quotient polynomial using the elliptic curve and the result of the polynomial evaluated at that position.
The former is an elliptic curve point, the later the data polynomial evaluation.
(18/24) Before we move on, let's consider the polynomial evaluation.
Remember, the polynomial is an expression that describes how our data looks when plotted on a graph. The evaluation of that function is simply just the data at that position!
(19/24) To finish our proof cycle, the verifier (who does not have access to the full dataset and therefore cannot generate the data or quotient polynomial) is going to ensure the provers response reconciles with the commitment.
But first, we are going to need one more tool.
(20/24) In order to combine the pieces sent by the prover, the verifier is going to need to multiply elliptic curve points. Unfortunately, this just isn't possible; that's not how elliptic curves work.
Fortunately, we have a substitute: elliptic curve pairings.
twitter.com/SalomonCrypto/status/1583168818381172736
(21/24) And now, finally, we are ready to verify our proof.
The verifier constructs two expressions and checks them for equivalence. If they are equivalent, the verifier can be certain that the prover did the (polynomial) division and therefore still has the original data.
twitter.com/SalomonCrypto/status/1583542847759753217
(22/24) The commitment acts as an anchor, a proof entails quick polynomial division and verification is a simple check.
The verifier can know with mathematical certainty that the prover is honoring their commitment; whatever data is there is the same that created the commitment.
(23/24) So, in summary, a KZG commitment is a polynomial commitment scheme used to bind a prover to a specific set of data.
KZG commitments also have a very useful feature: they can be opened (audited) at any position without revealing any unrelated data.
(24/24) Looking to go deeper? Here are the resources I turned to again and again as I wrote this series:
twitter.com/SalomonCrypto/status/1583573077081792512