1 of 26

Introduction to KZG (Kate) commitments

How to hash polynomials

Dankrad Feist

Ethereum Foundation (Eth2.0 Research)

2 of 26

Motivation: Data availability sampling and erasure coding
Finite fields
“Hashes of polynomials”
KZG commitments and proofs
Further reading

Outline

3 of 26

Motivation: Data availability sampling and Erasure coding

4 of 26

Data Availability Sampling

Check “random samples” to ensure availability of a data block
Does not depend on honest majority
Need to erasure code data, otherwise an attacker can still hide “small” amounts of data

5 of 26

Erasure coding

Extend the data using a “Reed-Solomon code” (= polynomial interpolation)
Property:

Any 50% of the chunks (d₀ to e₃) are sufficient to reconstruct the whole data

Because of this, we can use random sampling to ensure data availability

E.g. query 30 random blocks; if all are available, probability that less than 50% available is 2^-30

d₀

d₁

d₂

d₃

e₀

e₁

e₂

e₃

Original data

Polynomial extension (degree 3)

6 of 26

Merkle roots as Data Availability Roots

Need to know data (d_i) and extension (e_i) are on one low-degree polynomial

Root

d₀

d₁

d₂

d₃

e₀

e₁

e₂

e₃

7 of 26

But if we just use Merkle roots, then we still need to worry about the extension being correct

d₀

d₁

d₂

d₃

e₀

e₁

e₂

e₃

Original data

Polynomial extension (degree 3)

I’ll just make up the extension!!! They will never be able to reconstruct the data!!!

This requires fraud proofs
Fraud proofs aren’t great: They add a lot of complexity and synchronicity conditions

What if we could find a kind of commitment (“Merkle root”) that always commits to a polynomial?

8 of 26

Finite fields

9 of 26

Field: Think about rational ℚ, real ℝ or complex ℂ numbers

You can do all the basic maths: +, -, *, / [except by 0]
There are some laws: Associative, Commutative, Distributive

but the easiest way to think about it is just “what can you do with rational numbers”

Finite: Unlike ℚ, ℝ, ℂ, which have an infinite number of elements, finite fields only have a finite number of elements

Each element can be represented using the same number of bits

Finite fields: Definition

10 of 26

Consists of the numbers 0, 1, 2, 3, 4
Every operation: Do it first in the integers, then the result is the remainder after division by 5 (“modulo” 5)
Each element (except 0) has a “multiplicative inverse”:

Finite fields: Let’s look at 𝔽₅

This is because 5 is a prime number (works for any prime)

0	-
1	1	1 * 1 = 1
2	3	2 * 3 = (6 = ) 1
3	2	3 * 2 = (6 = ) 1
4	4	4 * 4 = (16 = ) 1

11 of 26

“Hashing polynomials”

12 of 26

A polynomial is an expression of the form

The f_i are the coefficients of the polynomial
The degree of the polynomial is n (if f_n is not zero)
Each polynomial defines a polynomial function
For any k points, there is a polynomial of degree k-1 or lower that goes through all k points
A polynomial of degree n that is not constant has at most n zeros

Reminder: polynomials

13 of 26

Imagine a hash function H(f) that takes a polynomial with some extra functionality:

For each z you can construct a proof P(f, z), that proves that f(z) = y

H(f) and P(f, z) should be small

Polynomial commitments:

“Hash function” for polynomials

14 of 26

Step 1: Choose a random number, say… 3
Step 2: To hash a polynomial, you evaluate it at 3 (set X = 3):

f(X) = X² + 2 X + 4 → H(f) = (9 + 6 + 4) % 5 = 4
g(X) = 2 X³ + 4 X² + X + 2 → H(g) = (54 + 36 + 3 + 2) % 5 = 0�

If the modulus has 256 bits, it’s actually very unlikely that two polynomials have the same “hash”, just like for a normal hash function

Polynomial hashes: The “random evaluation”

15 of 26

We can add two “polynomial hashes”:

H(f) + H(g) = H(f + g)
This is because f(3) + g(3) = (f + g)(3)

We can also multiply two “polynomial hashes”:

H(f) * H(g) = G(f * g)
This is because f(3) * g(3) = (f * g)(3)

Polynomial hashes: Properties of “random evaluation”

16 of 26

An adversary can easily create a collision if they know the random number

What we want: a way to use finite field elements inside a “black box”
Let’s say we have a way to put a secret number in a black box

[s], [s²], [s³], ...

Such that we can multiply it with another number and add it (but not multiply two numbers in a black box)

The problem with “random evaluation”

17 of 26

Elliptic curves are exactly that! A “black box” field element

Elliptic curve G₁ with generator g₁of order p
To represent a field element x ∈ 𝔽_p multiply the generator with x:

x * g₁

We can add elliptic curve elements (g and h) and multiply by field elements (x and y):

x * g, g + h, x * g + y * h ✅
g * h ❌

Notation [x]₁= x * g₁

Elliptic curves to the rescue

18 of 26

KZG commitments

19 of 26

Assume we have the trusted setup [sⁱ]₁,[sⁱ]₂, for i = 0, 1, ... , (some large number)
For a polynomial f(X) defined by

we define the KZG commitment to f as

KZG (Kate) commitments

20 of 26

Notation: e(g, h)
Input: Elements from two elliptic curves G₁, G₂ �and output in the “target group” G_T
The pairing is “bilinear”:

e([a*x]₁, [z]₂) = e([x]₁, [z]₂)^a
e([x]₁, [b*z]₂) = e([x]₁, [z]₂)^b
e([x + y]₁, [z]₂) = e([x]₁, [z]₂) + e([y]₁, [z]₂)
e([x]₁, [z+w]₂) = e([x]₁, [z]₂) + e([x]₁, [w]₂)

Quick recap: pairings

21 of 26

This means we can do “multiplications” (of sorts):�

e([x]₁, [y]₂) = e([1]₁, [y]₂)^x= e([1]₁, [1]₂)^x*y

Notation: [x]_T= e([1]₁, [1]₂)^x �
e([x]₁, [y]₂) = [x * y]_T

Doing multiplications using pairings

22 of 26

Now assume we have two polynomials f(X) and g(X)�

Let’s commit to f(X) in G₁: [f(s)]₁
and g(X) in G₂: [g(s)]₂

Then:

e([f(s)]₁, [g(s)]₂) = [f(s) * g(s)]_T

Doing polynomial multiplications using pairings

23 of 26

Let f(X) be a polynomial and y, z be field elements
Then (by the Factor Theorem) the quotient

is a polynomial exactly if f(z) = y.

Restating, there exists a polynomial q(X) that fulfills the equation

if and only if f(z) = y

The last missing piece: Polynomial quotients

24 of 26

To prove that f(z) = y, compute

and send [q(s)]₁

The verifier checks that

e([f(s)-y]₁, [1]₂) = e([q(s)]₁,[s-z]₂) = [q(s) * (s-z)]_T = [f(s) - y]_T

The KZG proof

25 of 26

Allows us to:

Commit to any polynomial using a single G₁ element [f(s)]₁

Then we can open the commitment at any point z:

Compute f(z) = y
Compute the quotient
Proof: [q(s)]₁

To verify a proof (needs two pairings), use the pairing equation

e([f(s)-y]₁, [1]₂) = e([q(s)]₁,[s-z]₂)

Recap: KZG commitment