1 of 113

7 of 113

definitions

polynomial oracle

polynomial f

"encode"

prover

8 of 113

definitions

polynomial oracle

polynomial f

"encode"

evaluation point z

"query"

verifier

prover

9 of 113

definitions

polynomial oracle

polynomial f

"encode"

evaluation point z

evaluation f(z)

"respond"

"query"

verifier

prover

10 of 113

definitions

polynomial oracle

polynomial commitment

polynomial f

"encode"

"commit"

evaluation point z

evaluation f(z)

"respond"

"query"

verifier

prover

11 of 113

definitions

polynomial oracle

polynomial commitment

polynomial f

"encode"

"commit"

evaluation point z

evaluation f(z)

"respond"

"query"

verifier

prover

"open"

12 of 113

definitions

polynomial oracle

polynomial commitment

polynomial f

"encode"

"commit"

evaluation point z

evaluation f(z)

"prove"

"respond"

"query"

verifier

prover

"open"

13 of 113

the fine print

Marlin (Appendix B.1)

pages 54–55 of 75

14 of 113

big picture

computer science

information theory

cryptography

circuit

witness

universal

SNARK

15 of 113

big picture

computer science

information theory

cryptography

circuit

witness

universal

SNARK

polynomial oracles

16 of 113

big picture

computer science

information theory

cryptography

circuit

witness

interactive oracle proof

universal

SNARK

polynomial oracles

17 of 113

big picture

computer science

information theory

cryptography

hash function

circuit

witness

interactive oracle proof

random oracle

universal

SNARK

polynomial oracles

18 of 113

big picture

computer science

information theory

cryptography

hash function

polynomial oracles

circuit

witness

polynomial commitment

interactive oracle proof

random oracle

universal

SNARK

19 of 113

big picture

computer science

information theory

cryptography

hash function

polynomial oracles

circuit

witness

polynomial commitment

interactive oracle proof

random oracle

universal

SNARK

20 of 113

big picture

computer science

information theory

cryptography

hash function

polynomial oracles

circuit

witness

polynomial commitment

interactive oracle proof

random oracle

universal

SNARK

perfect soundness

statistical soundness

computational soundness

Compilers

boundary compilers

computer science to information theory—oracle encoding
information theory to cryptographic—instantiation/materialisation

internal compilers

code => circuit/RAM program => R1CS => QAP
within every bucket there are is significant massaging

the "computer science" includes both software (compilers, formal verifications, RAM programs) and hardware (circuits, gates, wires)
commonly known as the frontend, includes terms such as (R1CS, QAP)
Fiat-Shamir transformation provides the N in SNARK
polynomial oracles provides the S in SNARK
the "information theory" and "cryptography" historically lumped into the "backend"—the boundary much clearer today
the circuit is encoded to a set of polynomial oracles in an offline phase called "preprocessing" or "holography"
the preprocessing is trustless—"polynomials be polynomials" and "polynomials don't care"
the witness is encoded into a polynomial, traditionally in Lagrange form
the focus of today's talk is top right corner (polynomial oracles and polynomial commitments)
it's amazing that polynomial commitments can be "elevated/amplified" to SNARKs

Things that old SNARKs got "wrong":

Missing out on interaction (e.g. PCPs) for the sake of theoretical purity—interaction is extremely powerful in practice
Missing out on preprocessing, again for the sake of theoretical purity—preprocessing is extremely powerful in practice
Picking the wrong oracle type/cryptographic primitive (see "tug of war" slides)

21 of 113

tug of war

oracle type

cryptographic primitive

set

accumulator

expressiveness

cost

22 of 113

tug of war

oracle type

cryptographic primitive

set

accumulator

vector

vector commitment

expressiveness

cost

23 of 113

tug of war

oracle type

cryptographic primitive

set

accumulator

vector

vector commitment

low degree

low degree test

expressiveness

cost

FRI

24 of 113

tug of war

oracle type

cryptographic primitive

set

accumulator

vector

vector commitment

low degree

low degree test

polynomial

polynomial commitment

expressiveness

cost

FRI

25 of 113

tug of war

oracle type

cryptographic primitive

set

accumulator

vector

vector commitment

low degree

low degree test

polynomial

polynomial commitment

inner product

inner product argument

expressiveness

cost

FRI

The cryptography (other than the hash function) is segregated/contained in the "main" oracle instantiation. The cryptographic primitive instantiating the oracles is a workhorse which can be blackboxed.

Examples include:

Set—RSA (and class group) accumulator, pairing-based accumulator
Vector—Merkle tree, vector commitment in groups of unknown order
Polynomial proximity—FRI, DEEP-FRI (Reed-Solomon codes)
Polynomial—KZG10, DARK
Inner product—non-universal Kate, bulletproof

Hierarchy of oracles and cryptographic primitives:

as we will see, all low degree proofs generalise to polynomial commitments

Practicality barrier (the leap from polynomial commitment to inner product argument)

efficiency and power are at odds—need to tradeoff
non-universal setup (Groth16) or constant-time verifier (Bulletproof)

have to encode the linear queries into the trusted setup (circuit "pollution")

polynomial commitments are the "sweet spot"

26 of 113

part 1—context

part 2—landscape

part 3—mechanics

part 4—gadgets

27 of 113

setup and commitment

	FRI
	hash function
setup	H hash function w in F root of unity
commitment	root(f(w⁰), ..., f(w^kd))

28 of 113

setup and commitment

	FRI	KZG
	hash function	pairing group
setup	H hash function w in F root of unity	G₁, G₂ groups g₁, g₂ generators e pairing s in F secret
commitment	root(f(w⁰), ..., f(w^kd))	a₀s⁰g₁ + ... + a_ns^dg₁

29 of 113

setup and commitment

	FRI	KZG	DARK
	hash function	pairing group	unknown order group
setup	H hash function w in F root of unity	G₁, G₂ groups g₁, g₂ generators e pairing s in F secret	G unknown order g in G random q large integer
commitment	root(f(w⁰), ..., f(w^kd))	a₀s⁰g₁ + ... + a_ns^dg₁	a₀q⁰g + ... + a_dq^dg

30 of 113

setup and commitment

	FRI	KZG	DARK	Bulletproof
	hash function	pairing group	unknown order group	discrete log group
setup	H hash function w in F root of unity	G₁, G₂ groups g₁, g₂ generators e pairing s in F secret	G unknown order g in G random q large integer	G elliptic curve g_i in G independent
commitment	root(f(w⁰), ..., f(w^kd))	a₀s⁰g₁ + ... + a_ns^dg₁	a₀q⁰g + ... + a_dq^dg	a₀g₀ + ... + a_dg_d

algebraic

(with linear homomorphism)

The three algebraic commitments have a similar feel which is not super surprising.
The information theoretic does the best it can—evaluate, and "grapple" onto algebraic where possible, namely the field F
Unsurprisingly, we use existing commitment schemes.
Only care about binding—hiding (i.e. zero-knowledge) can be achieved at the application layer

hash function

The root of unity must be a large primitive root of unity ("large" means a small constant times degree of f)
The "rate" is the ratio between the size of <w> and the degree of f. (What is the inverse of the rate called?)

pairing

The secret scalar s is encoded in a "powers of s" (specifically the monomials sⁱg₁ for i = 0, ..., d_maxas well as sg₂.)

UO group

UO stands for "Unknown Order"
q large means O(p log(d))

discrete log

Notice that if g = (g_i) and a = (a_i) then the commitment is the inner product <a, g>
Independence of the g_i is with respect to discrete log
The g_i can be generated using a random oracle to G
The basis elements are going to evolve with the polynomial—they are not fixed

31 of 113

comparing setups

	FRI
	hash function
transparent
succinct
unbounded
updatable
post-quantum

32 of 113

comparing setups

	FRI	KZG
	hash function	pairing group
transparent
succinct
unbounded
updatable
post-quantum

33 of 113

comparing setups

	FRI	KZG	DARK
	hash function	pairing group	RSA group	class group	Jacobian group
transparent
succinct
unbounded
updatable
post-quantum

34 of 113

comparing setups

	FRI	KZG	DARK			Bulletproof
	hash function	pairing group	RSA group	class group	Jacobian group	discrete log group
transparent
succinct
unbounded
updatable
post-quantum

35 of 113

asymptotic performance

	FRI
	hash function
size	O(log²(d))
verifier time	O(log²(d))
prover time	O(d*log(d))

max(commitment time, opening time)

max(commitment size, opening proof size)

36 of 113

asymptotic performance

	FRI	KZG
	hash function	pairing group
size	O(log²(d))	O(1)
verifier time	O(log²(d))	O(1)
prover time	O(d*log(d))	O(d)

max(commitment time, opening time)

max(commitment size, opening proof size)

37 of 113

asymptotic performance

	FRI	KZG	DARK
	hash function	pairing group	unknown order group
size	O(log²(d))	O(1)	O(log(d))
verifier time	O(log²(d))	O(1)	O(log(d))
prover time	O(d*log(d))	O(d)	O(d)

max(commitment time, opening time)

max(commitment size, opening proof size)

38 of 113

asymptotic performance

	FRI	KZG	DARK	Bulletproof
	hash function	pairing group	unknown order group	discrete log group
size	O(log²(d))	O(1)	O(log(d))	O(log(d))
verifier time	O(log²(d))	O(1)	O(log(d))	O(d)
prover time	O(d*log(d))	O(d)	O(d)	O(d)

max(commitment time, opening time)

max(commitment size, opening proof size)

39 of 113

commitment size (with security parameter λ and d ≪ λ)

FRI	KZG	DARK			Bulletproof
hash function	pairing group	RSA group	class group	Jacobian group	discrete log group
O(1) * O(λ)	O(1) * O(λ³)	O(1) * O(λ³)	O(1) * O(λ²)	???	O(1) * O(λ)

subexponential attacks

(sieve based)

polynomial attack

40 of 113

commitment size (with security parameter λ and d ≪ λ)

FRI	KZG	DARK			Bulletproof
hash function	pairing group	RSA group	class group	Jacobian group	discrete log group
O(1) * O(λ)	O(1) * O(λ³)	O(1) * O(λ³)	O(1) * O(λ²)	???	O(1) * O(λ)

secp256k1

256 bits

(32 bytes)

SHA256

256 bits

(32 bytes)

BLS12-381

381 bits

(48 bytes)

subexponential attacks

(sieve based)

RSA

4,096 bits

(512 bytes)

class group

1,827 bits

(229 bytes)

target

128 bits

security

polynomial attack

Jacobian group

303 bits

(38 bytes)

Often dependence on the security parameter λ is hidden under the rug. Explicitly exposing contributions of the security parameter gives a fairer picture and helps understand where the concrete numbers come from. The concrete numbers for the proof sizes can be reused. A breakdown of the contribution of the security parameter for prover and verifier time can similarly be done.

Subexponential attacks

pairing group—Number Field Sieve (NFS). See here and here. The pairing reduces the elliptic curve discrete log problem to a discrete log problem in a finite field. Indeed, the target group is a subgroup of a small extension field of the base field. The extension degree is also known as the embedding degree, which is chosen to be small for efficiency (but not too small to compromise security).
RSA—General Number Field Sieve (GNFS). See here.
class group—Imaginary Quadratic Multiple Polynomial Quadratic Sieve (IP-MPQS) See here and here.

In practice the parameters are set to resist against the strongest attack known. This is scary because the algebraic attacks do get better over time.

Quantum attacks

Only FRI is quantum secure but to target 128 bits of security in the quantum oracle model the hash output needs to be larger than 256 bits. For example, this paper exposes a quantum collision attack which improves on the birthday bound.

41 of 113

part 1—context

part 2—landscape

part 3—mechanics

part 4—gadgets

42 of 113

commit-reduce low degree test

prover

verifier

...

43 of 113

commit-reduce low degree test

prover

verifier

r₀

...

r_log(d)-1

44 of 113

commit-reduce low degree test

prover

verifier

commit(f₀)

r₀

commit(f₁)

...

r_log(d)-1

commit(f_log(d)), aux

f_i+1 = reduce(f_i, r_i)

45 of 113

commit-reduce low degree test

prover

verifier

commit(f₀)

r₀

commit(f₁)

...

r_log(d)-1

commit(f_log(d)), aux

consistency checks

constant polynomial

check

f_i+1 = reduce(f_i, r_i)

The three polynomial commitment schemes with log(d) terms (FRI, DARK, Bulletproof) follow this template for low-degree tests. We could even have pairings follow this template but pairings are sufficiently powerful that interaction is not needed.
The consistency checks say "if f_i+1 has degree k then with high probability f_i has degree 2k"
If f_log(d) is constant and the consistency pass then f₀ has degree at most d, QED.
The consistency check will make use of homomorphisms in commit.
This diagram shows the honest prover behaviour. It's the job of cryptographers to prove soundness for malicious provers.
As an optimisation the r_i can sized like the security parameter, which can be smaller than the field size. Conversely, we need the field size to be large enough, which in some cases is an extra cost.

46 of 113

even-odd and left-right decomposition

f(X) = even(f)(X²) + X*odd(f)(X²)

even-odd decomposition

f(X) = left(f)(X) + X^d/2*right(f)(X)

left-right decomposition

47 of 113

decompose-reduce

f(X) = even(f)(X²) + X*odd(f)(X²)

even-odd decomposition

	hash function (FRI)	UO group (DARK)	discrete log group (Bulletproof)
coefficients	even(f) + r*odd(f)	even(f) + r*odd(f)	rleft(f) + r^-1right(f)
basis	N/A	g	r^-1left(g) + rright(g)

f(X) = left(f)(X) + X^d/2*right(f)(X)

left-right decomposition

48 of 113

consistency checks

FRI (hash function)

DARK (UO group)

Bulletproof (discrete log)

2zf_i+1(z²)

?=

z(f_i(z) + f_i(-z))

+

r_i(f_i(z) - f_i(-z))

49 of 113

consistency checks

FRI (hash function)

DARK (UO group)

Bulletproof (discrete log)

2zf_i+1(z²)

?=

z(f_i(z) + f_i(-z))

+

r_i(f_i(z) - f_i(-z))

commit(f_i+1)

?=

commit(even(f_i))

+

r_i*q*commit(odd(f_i))

50 of 113

consistency checks

FRI (hash function)

DARK (UO group)

Bulletproof (discrete log)

2zf_i+1(z²)

?=

z(f_i(z) + f_i(-z))

+

r_i(f_i(z) - f_i(-z))

commit(f_i+1)

?=

commit(even(f_i))

+

r_i*q*commit(odd(f_i))

commit(f_i+1)

?=

commit(f_i)

+

(r_i)²L + (r_i)^-2R

FRI

z is a random challenge point (chosen at the end of the protocol)
the openings f_i+1(z²), f_i(z), f_i(-z) are accompanied by Merkle proofs (hence the extra log(d) proof size overhead)
the two right-hand terms are (when divided by 2z) even(f)(z) and odd(f)(z)

DARK

Notice that the DARK has a "shift" homomorphism (multiplication by X), so the check is essentially f_i+1 ?= even(f_i) + X*odd(f_i), as required.
Multiplying the commitment commit(odd(f_i)) by q yields the commit(X*odd(f_i))
q is large so need extra auxiliary information for verifier to efficiently check. We use a Wesolowski proof of exponentiation. (Wesolowski proofs are also useful for VDFs and accumulators.)

Bulletproof

The L and R correspond to the cross-product terms <even(f), odd(g)> and <odd(f), even(g)>. (Here f encodes the polynomial coefficients, and g encodes the basis elements.)

General comments

The purple elements are auxiliary information.
For DARK and Bulletproof we work with commitments directly thanks to homomorphisms.

51 of 113

quotient argument openings

f(X) - f(z) = q(X)(X - z)

FRI (hash function)

KZG10 (pairing group)

(f(X) - f(z))/(X - z) low degree proof

(within unique decoding radius)

52 of 113

quotient argument openings

f(X) - f(z) = q(X)(X - z)

FRI (hash function)

KZG10 (pairing group)

e(commit(f) - f(z), g₂)

?=

e(commit(q), (s - z)g₂)

(f(X) - f(z))/(X - z) low degree proof

(within unique decoding radius)

53 of 113

other openings

DARK (UO group)

Bulletproof (discrete log)

even(f_i)(z), odd(f_i)(z)

<coeff(f), powers(x)>

54 of 113

recent developments

novel constructions

lattice-based polynomial commitment
Jacobian groups with unknown order
sparse polynomial commitments

55 of 113

part 1—context

part 2—landscape

part 3—mechanics

part 4—gadgets

56 of 113

modularity

information theory

cryptography

polynomial commitment

interactive oracle proof

57 of 113

modularity

information theory

cryptography

polynomial commitment

interactive oracle proof

polynomial

gadgets

58 of 113

modularity

information theory

cryptography

polynomial commitment

interactive oracle proof

polynomial

gadgets

59 of 113

testing polynomial identities

f₁, f₂ low-degree polynomials

f₁ = f₂ with high probability

⇔

f₁(z) = f₂(z) at random point z

f₁(X), ..., f_k(X) low-degree polynomials

G(X₁, ..., X_K, Y) low-degree

G(f₁, ..., f_n, Y) = 0 with high probability

⇔

G(f₁, ..., f_n, Y)|_X=z at random point z

fundamental theorem of algebra

Schwartz–Zippel lemma

Schwartz-Zippel

Also known as the fundamental theorem of algebra
The Schwartz-Zippel is possibly the top information theory tool when designing IOPs. It states that two low-degree polynomials are the same iff they agree at one random point. In short, we can polynomial equality to point equality—an exponential increase in performance.
As a general theme, we get a lot of power from (public coin) interaction, and we can get it "for free" (most of the time, see VDF counter-example) thanks to Fiat-Shamir.

generalised Schwartz-Zippel

Allows to prove equalities of polynomial relations.
The free variable Y is used to feed verifier challenges.
Such multivariate polynomial G can be used to build custom gates, e.g. custom PLONK gates. Those are also known in the litterature as "G-gates".
You can also consider Laurent polynomials.

60 of 113

basic tricks

	trick
range	(f // Z_S)*Z_S

61 of 113

range check

commitments to f, f // Z_S

62 of 113

range check

commitments to f, f // Z_S

z

63 of 113

range check

commitments to f, f // Z_S

z

openings of f, f // Z_S at z

64 of 113

range check

commitments to f, f // Z_S

z

openings of f, f // Z_S at z

check that f(z) = (f // Z_S)(z)*Z_S(z)

65 of 113

basic tricks

	trick
range	(f // Z_S)*Z_S
multi-point opening	(f // Z_S)*Z_S + f % Z_S

66 of 113

multi-point opening

commitments to f, f // Z_S plus f % Z_S

in the Lagrange basis

(evaluations of f on S)

67 of 113

multi-point opening

commitments to f, f // Z_S plus f % Z_S

z

in the Lagrange basis

(evaluations of f on S)

68 of 113

multi-point opening

commitments to f, f // Z_S plus f % Z_S

z

openings of f, f // Z_S at z

in the Lagrange basis

(evaluations of f on S)

69 of 113

multi-point opening

commitments to f, f // Z_S plus f % Z_S

z

openings of f, f // Z_S at z

check that f(z) = (f // Z_S)(z)*Z_S(z) + (f % Z_S)(z)

in the Lagrange basis

(evaluations of f on S)

70 of 113

basic tricks

	trick
range	(f // Z_S)*Z_S
multi-point opening	(f // Z_S)*Z_S + f % Z_S
multi-polynomial opening	Y⁰f₀ + ... + Y^kf_k

71 of 113

multi-point opening

f₀(z), ..., f_k(z)

commitments to f₀, ..., f_k

z

72 of 113

multi-point opening

f₀(z), ..., f_k(z)

r

opening of r⁰f₀ + ... + r^kf_k at z

commitments to f₀, ..., f_k

z

commitment

linearity

73 of 113

multi-point opening

f₀(z), ..., f_k(z)

r

opening of r⁰f₀ + ... + r^kf_k at z

check that (r⁰f₀ + ... + r^kf_k)(z) = r⁰f₀(z) + ... + r^kf_k(z)

commitments to f₀, ..., f_k

z

commitment

linearity

74 of 113

basic tricks

	trick
range	(f // Z_S)*Z_S
multi-point opening	(f // Z_S)*Z_S + f % Z_S
multi-polynomial opening	Y⁰f₀ + ... + Y^kf_k
multi-{point, polynomial}	see here
degree bound	X^N-df(X)

range

The goal is to prove that some polynomial f (for which the verifier has a commitment, possibly indirect) vanishes on the set S.
It is a classic trick used in many IOPs. It can be used to prove "ranged" polynomial relations. For example, one can prove ab = c on S by defining f := ab - c and then proving that f vanishes on S. Notice that if the verifier has commitments to a, b, c individually then he also "indirectly" has a commitment to f.
Here Z_S is the (aptly named) vanishing polynomial on the set S.
prover-verifier interactivity:

prover sends commitment to (f // Z_S)
verifier sends evaluation point z
prover check consistency, i.e. (f // Z_S)(z)Z_S(z) + (f % Z_S)(z) = f(z)

If S is the set of n'th roots of unity then Z_S(X) = Xⁿ - 1 so Z_S(z) is cheap to compute (it costs just log(n) multiplications).
If S is known ahead of time and evaluating Z_S is not cheap then we can some preprocess a commitment to Z_S and have the prover open it for the verifier.

multi-polynomial opening

The goal is to prove that f₀, ..., f_k evaluate to specific values by doing just one polynomial opening. This is a cost reduction technique.
We consider
imulate taking a random linear combination of polynomials.
prover-verifier interactivity: (TODO: draw it)

verifier sends evaluation point z
prover sends claimed evaluations of f₀, ..., f_k at z
verifier sends r
prover sends opening of r⁰f₀ + ... + r^kf_k at z
verifier checks consistency (using linearity of commitments)

Taking powers rⁱ of a random challenge r is a ghetto way to "stretch" the randomness for cheap by using Swartz-Zippel.
In theory could replace Yⁱ (8 gas per MULMOD) with the repeated hash Hⁱ(Y) (42 gas per Keccak256).
The multi-polynomial opening trick uses X-polynomials as coefficients of a Y-polynomial. The Y-polynomial is then opened at a random point.
TODO: Does this work for FRI which is not linearly homomorphic?

multi-point opening

Decompose the polynomial f into the "quotient part" and the "remainder part".
The multi-point opening is a generalisation of the range trick. You can think of the range trick as "opening to zero on the range". If the range is known upfront then no information needs to be communicated.

degree bound

The degree bound is useful in the context of Kate where the SRS maximum degree is fixed.
The degree bound is also useful in the context of batching degree bound checks, e.g. for DARKs.

TODO: How does the degree bound work in the Lagrange basis? Readd degree bound.

TODO: How does multi-polynomial opening work in the Lagrange basis?

75 of 113

side note—Lagrange basis

76 of 113

monomial and Lagrange bases

(a₀, ..., a_d)

vector

77 of 113

monomial and Lagrange bases

(a₀, ..., a_d)

vector

a₀X⁰ + ... + a_dX^d

monomial basis

78 of 113

monomial and Lagrange bases

(a₀, ..., a_d)

vector

a₀L₀(X) + ... + a_dL_d(X)

Lagrange basis

a₀X⁰ + ... + a_dX^d

monomial basis

79 of 113

monomial and Lagrange bases

(a₀, ..., a_d)

vector

a₀L₀(X) + ... + a_dL_d(X)

Lagrange basis

a₀X⁰ + ... + a_dX^d

monomial basis

FFT

inverse FFT

80 of 113

barycentric formula

evaluation on i'th root of unity

81 of 113

Montgomery batch inversion

a₀

a₁

a₂

a₃

a₄

a₅

82 of 113

Montgomery batch inversion

a₀

a₁

a₂

a₃

a₄

a₅

a₀

a₀a₁

a₀a₁a₂

a₀a₁a₂a₃

a₀a₁a₂a₃a₄

a₀a₁a₂a₃a₄a₅

83 of 113

Montgomery batch inversion

a₀

a₁

a₂

a₃

a₄

a₅

a₀

a₀a₁

a₀a₁a₂

a₀a₁a₂a₃

a₀a₁a₂a₃a₄

a₀a₁a₂a₃a₄a₅

(a₀a₁a₂a₃a₄a₅)^-1

84 of 113

Montgomery batch inversion

a₀

a₁

a₂

a₃

a₄

a₅

a₀

a₀a₁

a₀a₁a₂

a₀a₁a₂a₃

a₀a₁a₂a₃a₄

a₀a₁a₂a₃a₄a₅

(a₀)^-1

(a₀a₁)^-1

(a₀a₁a₂)^-1

(a₀a₁a₂a₃)^-1

(a₀a₁a₂a₃a₄)^-1

(a₀a₁a₂a₃a₄a₅)^-1

85 of 113

Montgomery batch inversion

a₀

a₁

a₂

a₃

a₄

a₅

a₀

a₀a₁

a₀a₁a₂

a₀a₁a₂a₃

a₀a₁a₂a₃a₄

a₀a₁a₂a₃a₄a₅

(a₀)^-1

(a₀a₁)^-1

(a₀a₁a₂)^-1

(a₀a₁a₂a₃)^-1

(a₀a₁a₂a₃a₄)^-1

(a₀a₁a₂a₃a₄a₅)^-1

(a₀)^-1

(a₁)^-1

(a₂)^-1

(a₃)^-1

(a₄)^-1

(a₅)^-1

86 of 113

/side note—Lagrange basis

87 of 113

more tricks

	Lagrange basis	monomial basis
encode	a₀L₀(X) + ... + a_dL_d(X)	a₀X⁰ + ... + a_dX^d

88 of 113

more tricks

	Lagrange basis	monomial basis
encode	a₀L₀(X) + ... + a_dL_d(X)	a₀X⁰ + ... + a_dX^d
query	f(wⁱ)	f_L(X) + a_iXⁱ + Xⁱ⁺¹f_R(X)

89 of 113

more tricks

	Lagrange basis	monomial basis
encode	a₀L₀(X) + ... + a_dL_d(X)	a₀X⁰ + ... + a_dX^d
query	f(wⁱ)	f_L(X) + a_iXⁱ + Xⁱ⁺¹f_R(X)
shift	f(wⁱX)	Xⁱf(X)

90 of 113

more tricks

	Lagrange basis	monomial basis
encode	a₀L₀(X) + ... + a_dL_d(X)	a₀X⁰ + ... + a_dX^d
query	f(wⁱ)	f_L(X) + a_iXⁱ + Xⁱ⁺¹f_R(X)
shift	f(wⁱX)	Xⁱf(X)
sum	g(wX) = f(X) + g(X)	f(1)

91 of 113

sum argument

commitments to f, g, q

q = (shift(g) - g - f) // Z_S

92 of 113

sum argument

commitments to f, g, q

z

q = (shift(g) - g - f) // Z_S

93 of 113

sum argument

commitments to f, g, q

z

openings of f, g, shift(g), q at z

q = (shift(g) - g - f) // Z_S

94 of 113

sum argument

commitments to f, g, q

z

openings of f, g, shift(g), q at z

check g(wz) - g(z) - f(z) = q(z)Z_S(z)

q = (shift(g) - g - f) // Z_S

shift(g)(z)

95 of 113

more tricks

	Lagrange basis	monomial basis
encode	a₀L₀(X) + ... + a_dL_d(X)	a₀X⁰ + ... + a_dX^d
query	f(wⁱ)	f_L(X) + a_iXⁱ + Xⁱ⁺¹f_R(X)
shift	f(wⁱX)	Xⁱf(X)
sum	g(wX) = f(X) + g(X)	f(1)

sum check alternative

|S|^-1(f(X) % Z_S(X))|_X=0

96 of 113

more tricks

	Lagrange basis	monomial basis
encode	a₀L₀(X) + ... + a_dL_d(X)	a₀X⁰ + ... + a_dX^d
query	f(wⁱ)	f_L(X) + a_iXⁱ + Xⁱ⁺¹f_R(X)
shift	f(wⁱX)	Xⁱf(X)
sum	g(wX) = f(X) + g(X)	f(1)
grand product	g(wX) = f(X)g(X)	see Sonic appendix B

97 of 113

more tricks

	Lagrange basis	monomial basis
encode	a₀L₀(X) + ... + a_dL_d(X)	a₀X⁰ + ... + a_dX^d
query	f(wⁱ)	f_L(X) + a_iXⁱ + Xⁱ⁺¹f_R(X)
shift	f(wⁱX)	Xⁱf(X)
sum	g(wX) = f(X) + g(X)	f(1)
grand product	g(wX) = f(X)g(X)	see Sonic appendix B
permutation	f(X) + Yσ(X) + Z and f(X) + YX + Z grand products	see Sonic appendix A

98 of 113

permutation argument

σ: (a_i) → (a_j) is a permutation

99 of 113

permutation argument

σ: (a_i) → (a_j) is a permutation

⟺

a_i = a_j whenever i = σ(j)

100 of 113

permutation argument

σ: (a_i) → (a_j) is a permutation

⟺

a_i = a_j whenever i = σ(j)

⟺

a_i + i*X = a_j + σ(j)*X whenever i = σ(j)

101 of 113

permutation argument

σ: (a_i) → (a_j) is a permutation

⟺

a_i = a_j whenever i = σ(j)

⟺

a_i + i*X = a_j + σ(j)*X whenever i = σ(j)

⟺

{a_i + i*X} = {a_j + σ(j)*X} as multisets

102 of 113

permutation argument

σ: (a_i) → (a_j) is a permutation

⟺

a_i = a_j whenever i = σ(j)

⟺

a_i + i*X = a_j + σ(j)*X whenever i = σ(j)

⟺

{a_i + i*X} = {a_j + σ(j)*X} as multisets

⟺

product_i(a_i + i*X + Y) = product_j(a_j + σ(j)*X + Y) as polynomials in X, Y

103 of 113

permutation argument

σ: (a_i) → (a_j) is a permutation

⟺

a_i = a_j whenever i = σ(j)

⟺

a_i + i*X = a_j + σ(j)*X whenever i = σ(j)

⟺

{a_i + i*X} = {a_j + σ(j)*X} as multisets

⟺

product_i(a_i + i*X + Y) = product_j(a_j + σ(j)*X + Y) as polynomials in X, Y

⟺

product_i(a_i + i*r₁ + r₂) = product_j(a_j + σ(j)*r₁ + r₂) for random challenges r₁, r₂

104 of 113

even more tricks

	Lagrange basis trick
Hadamard product	f₁(X)f₂(X)

Lagrange superpower

105 of 113

even more tricks

	Lagrange basis trick
Hadamard product	f₁(X)f₂(X)
inner product	sum over f₁(X)f₂(X)

Lagrange superpower

106 of 113

even more tricks

	Lagrange basis trick
Hadamard product	f₁(X)f₂(X)
inner product	sum over f₁(X)f₂(X)
sparse matrix multiplication	two sum cheks; see here

Lagrange superpower

107 of 113

even more tricks

	Lagrange basis trick
Hadamard product	f₁(X)f₂(X)
inner product	sum over f₁(X)f₂(X)
sparse matrix multiplication	two sum cheks; see here
range checks	see Aztec research
RAM read and write	see Aztec research

Lagrange superpower

108 of 113

PLONK constraint system

arithmetic circuit

addition

gates

multiplication gates

wires

public

inputs

109 of 113

PLONK constraint system

arithmetic circuit

addition

gates

multiplication gates

wires

public

inputs

i

110 of 113

PLONK constraint system

arithmetic circuit

addition

gates

multiplication gates

wires

a_L + a_R = a_O

public

inputs

i

111 of 113

PLONK constraint system

arithmetic circuit

addition

gates

multiplication gates

wires

a_L + a_R = a_O

m_Lm_R = m_O

public

inputs

i

112 of 113

PLONK constraint system

arithmetic circuit

addition

gates

multiplication gates

wires

w = concat(

i, # input wires

a_L, a_R, a_O, # ADD wires

m_L, m_R, m_O, # MUL wires

)

w = permute(w, σ)

a_L + a_R = a_O

m_Lm_R = m_O

public

inputs

i

113 of 113

thank you :)