• Recall: How to build an Efficient SNARK?
• What is a Polynomial Commitment?
  • A bit more formality
• Group Theory
  • Generator of a Group
  • Discrete Logarithm Assumption
  • Diffie-Hellman Assumption
  • Bilinear Pairing
    • Example: Diffie-Hellman
    • Example: BLS Signature
• KZG Poly-Commit Scheme with Pairings
  • q-Strong Bilinear Diffie-Hellman
  • Knowledge of Exponent (KoE)
  • Generic Group Model (GGM)
  • Properties of KZG
  • Powers of Tau Ceremony
  • Variants of KZG
    • Multivariate KZG
    • Achieving Zero-Knowledge
    • Batch Proofs on a Single Polynomial
    • Batch Proofs on Multiple Polynomials
• Bulletproofs
  • The Magic Trick
• More Poly-Commit Schemes
  • Hyrax
  • Dory
  • Dark
• Summary

Recall: How to build an Efficient SNARK?

There are various paradigms on building SNARKs, but the general paradigm is made up of two steps:

1. A functional commitment scheme, which is a cryptographic object
2. A suitable interactive oracle proof (IOP), which is an information theoretic object

In Lecture 5, we have seen PLONK, which operated with:

1. A univariate polynomial commitment scheme
2. PLONK polynomial IOP

In Lecture 4, we have seen another method using the sum-check protocol:

1. A multivariate polynomial commitment scheme
2. Sum-check protocol for IOP

In this lecture, we will dive deeper into polynomial commitment schemes, in particular those that are based on bilinear pairings and discrete logarithm.

What is a Polynomial Commitment?

Consider a family of polynomials $\mathcal{F}$. The prover has some polynomial $f\in \mathcal{F}$ that is a function $f:X\to Y$. The interactions of a polynomial commitment scheme look like the following:

sequenceDiagram
	actor P as Prover
	actor V as Verifier

	note over P: f ∈ F

	P ->> V: (1) com_f := commit(f)
	V ->> P: (2) u ∈ X
	P ->> V: (3) v ∈ Y, proof π
	note over V: (4) Accept or Reject

Let us explain each numbered step in this sequence diagram:

1. Prover commits to the polynomial, and sends the commitment $co{m}_f$, also shown as $\boxed{f}$.
2. The verifier would like to query this polynomial at some value $u$, so it sends this to the prover.
3. Prover evaluates $v:=f(u)$ and sends this to verifier, along with a proof $\pi$ that indeed $v=f(u)$ and $f\in \mathcal{F}$.
4. The verifier will verify this proof, and accept if it is valid.

A bit more formality

Let's make a more formal definition of polynomial commitments now. They are made of 4 algorithms:

• $keygen(\lambda ,\mathcal{F})\to gp$ generate public parameters given the polynomial family and security parameter $\lambda$. Note the $gp$ is also known as "common reference string", or "public key" too.
• $commit(gp,f)\to co{m}_f$ computes the commitment to the given polynomial.
• $eval(gp,f,u)\to v,\pi$ is the evaluation method that the prover uses to compute $v:=f(u)$ and generate a proof that $v=f(u)$ this is true and $f\in \mathcal{F}$.
• $verify(gp,co{m}_f,u,v,\pi )\to \{0,1\}$ verifies an evaluation, and it will either accept or reject (which is why I used a bit to represent output).

Polynomial commitment has the following properties:

Correctness: if the prover is honest, and follows the given algorithms above, then $verify$ should always accept. We won't go too much into this one yet.

Knowledge Soundness: for every polynomial time adversary $A=(A_0,A_1)$ such that:

• $gp\leftarrow keygen(\lambda ,\mathcal{F})$
• $co{m}_f\leftarrow A_0(gp)$
• $v,\pi \leftarrow A_1(gp,u)$

where $\mathrm{Pr}[V(vp,x,\pi )=\text{accept}]=1$, then there is an efficient extractor $E$ that uses $A_1$ as a black box (oracle) such that:

• $gp\leftarrow keygen(\lambda ,\mathcal{F})$
• $co{m}_f\leftarrow A_0(gp)$
• $f\leftarrow E(gp,co{m}_f)$

where $\mathrm{Pr}[f(u)=v\text{ and }f\in \mathcal{F}]>1-ϵ$. Meaning that if the prover can convince the verifier about some committed polynomial $f$, then an efficient extractor can "extract" that $f$ from the prover via some algorithm, and then find out that indeed the evaluations are correct, with at most some negligible probability of failure.

Group Theory

It will be good to refresh our memory on some of the preliminary concepts, starting with group theory!

A group is a set $\mathbb{G}$ and an operation $\ast$. It satisfies the following properties:

• Closure: $\forall a,b\in \mathbb{G}$ it holds that $a\ast b\in \mathbb{G}$. In other words, the result of this operation is still an element of this group, it is closed in this group!
• Associativity: $\forall a,b,c\in \mathbb{G}$ it holds that $(a\ast b)\ast c=a\ast (b\ast c)$. The order of execution should not matter.
• Identity: $\exists e\in \mathbb{G}$ such that $\forall a\in \mathbb{G}$ it holds that $e\ast a=a\ast e=a$. We call $e$ the identity element, because the result of operating on it is identical to the operand.
• Inverse: $\forall a\in \mathbb{G},\exists b\in \mathbb{G}$ such that $a\ast b=b\ast a=e$. This is very important to keep in mind.

For example, the set of integers $\mathbb{Z}=\{\dots ,-1,0,1,\dots \}$ under addition operation $+$ satisfies all these properties. You might also be familiar with rational numbers, real numbers, complex numbers and such.

In cryptography, here are some commonly used groups:

• Positive integers $\mathrm{mod}$ some prime number $p$, which is the set $\{1,2,\dots ,p-1\}$ under the multiplication operation $\times$. This is denoted as ${\mathbb{Z}}_p^{\ast }$.
• Elliptic curves, we will not go into this yet though.

Generator of a Group

An element $g\in \mathbb{G}$ that generates all the other elements in the group by taking its powers is called the generator of that group. For example, consider the multiplicative group ${\mathbb{Z}}_7^{\ast }=\{1,2,3,4,5,6\}$. See what happens if we take powers of 3 in this group.

Notice that $3^6=1$, so you can continue to powering $3^7=3$, $3^8=2$ and so on but you will keep getting the same values. Furthermore, there can be multiple generators within a group!

Discrete Logarithm Assumption

So think of a some group $\mathbb{G}$ with $p$ elements. You could represent the group by literally writing out all its $p$ elements. Alternatively, you could just note down the generator $g$ and find its $p$ powers to obtain the group elements; keep in mind that there may be different generators too. With that in mind, let us look at the discrete logarithm problem:

• given $y\in \mathbb{G}$ find $x$ such that $g^x=y$

It turns out that this is very hard to do, you basically have to try your luck with $x$. There are some clever methods too, but it is the general consensus that this problem is computationally hard, meaning that you can't solve it in polynomial time.

Quantum computers can actually solve this in polynomial time, and any scheme that uses discrete log is therefore not post-quantum secure.

Diffie-Hellman Assumption

You might remember this duo from the Diffie-Hellman Key-Exchange [Diffie-Hellamn'76]. The paper is based on the Diffie-Hellman Assumption, which is very similar to the discrete logarithm assumption.

• given $\mathbb{G},g,g^x,g^y$ compute $g^{xy}$

This is a stronger assumption that the discrete logarithm assumption, meaning that it "assumes more stuff". In other words, if discrete logarithm assumption breaks, you can break this one too. What you could do it, simply find $x$ from $g^x$ and $y$ from $g^y$ and just compute $g^{xy}$.

To our best knowledge, this is also a hard problem and there is no efficient solution yet.

Bilinear Pairing

Bilinear pairings are an awesome building block that we will make use of. You have the following:

• $\mathbb{G}$: the base group, a multiplicative cyclic group
• ${\mathbb{G}}_T$: the target group, yet another multiplicative cyclic group
• $p$: the order of both $\mathbb{G}$ and ${\mathbb{G}}_T$
• $g$: the generator of base group $\mathbb{G}$
• $e$: a pairing operation $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$

The pairing must have the following bilinearity property:

$$\forall P,Q,\in \mathbb{G}:e(P^x,Q^y)=e(P,Q{)}^{xy}$$

Note that computing $e$ itself may be efficient or not, that depends on the groups that are being used. Also note that you could have two different base groups, unlike our example above which just uses on base group for both $P$ and $Q$.

Example: Diffie-Hellman

Consider $e(g,g{)}^{xy}$, what can this be equal to?

• $e(g,g{)}^{xy}=e(g^x,g^y)$
• $e(g,g{)}^{xy}=e(g^{xy},g)$

That means $e(g^x,g^y)=e(g^{xy},g)$. We know that given $g^x,g^y$ we can't compute $g^{xy}$ that is the Diffie-Hellman assumption. However, what if someone claims that they have computed $g^{xy}$? Well, we can check this without learning what $x,y$ is simply with the aforementioned equality.

Example: BLS Signature

BLS signature [Boneh-Lynn-Shacham'01] is an example usage of bilinear pairings. It is a signature scheme with the following functions:

• $keygen(p,\mathbb{G},g,{\mathbb{G}}_T,e)\to (sk=x,pk=g^x)$ that is the secret (private) key and public key respectively
• $sign(sk,m)\to \sigma =H(m{)}^x$ where $H$ is a cryptographic hash function that maps the message space to $\mathbb{G}$
• $verify(pk,\sigma ,m)\to \{0,1\}$ will verify if $e(H(m),g^x)=e(\sigma ,g)$. Notice that $g^x$ comes from $pk$, and $H$ is a known public hash function

KZG Poly-Commit Scheme with Pairings

Remember we had went over KZG in the previous lecture, but there at some point we had to mention "pairings". Now, we will look at KZG again but with pairings included.

Suppose you have a univariate polynomial function family $\mathcal{F}={\mathbb{F}}_p^{(\le d)}[X]$ and some polynomial that you would like to commit $f\in \mathcal{F}$. You also have a bilinear pairing $p,\mathbb{G},q,{\mathbb{G}}_T,e$. Let's see how KZG works with these.

• $keygen(\lambda ,\mathcal{F})\to gp$

  • Sample a random $\tau \in {\mathbb{F}}_P$
  • Set $gp=(g,g^{\tau },g^{{\tau }^2},\dots ,g^{{\tau }^d})$
  • Delete $\tau$, its toxic waste at this point and you should make sure no one gets it. If they do, they can generate fake proofs. This is why a trusted setup is required for KZG.

• $commit(gp,f)\to co{m}_f$

  • The polynomial is represented with its coefficients $f(x)=f_0+f_{1}x.+f_2{x}^2+\dots +f_d{x}^d$.
  • The commitment is $co{m}_f=g^{f(\tau )}$. How can this be done without knowing $\tau$? Well, that is where $gp$ comes into play.
  • Notice that $g^{f(\tau )}=g^{f_0=f_1\tau +f^2{\tau }^2+\dots +f_d{\tau }^d}$
  • Its equal to $(g{)}^{f_0}+(g^{\tau }{)}^{f_1}+(g^{{\tau }^2}{)}^{f_2}+\dots (g^{{\tau }^d}{)}^{f_d}$ which can be done using just the elements in the public parameters $gp$ and the coefficients of $f$.

• $eval(gp,f,u)\to v,\pi$

  • A verifier wants to query this polynomial at point $u$, and you would like to show that $f(u)=v$ along with a proof $\pi$ that this is indeed true.
  • To do this, first you find a quotient polynomial $q(x)$ such that $f(x)-f(u)=(x-u)q(x)$. Note that $u$ is a a root of $f(x)-f(u)$.
  • Then, your proof is $\pi =g^{q(\tau )}$ which you can do without knowing $\tau$ but instead using $gp$, as shown in the last bullet under $commit$.

• $verify(gp,co{m}_f,u,v,\pi )\to \{0,1\}$

  • The idea is to check the equation at point $\tau$ as $g^{f(\tau )-f(u)}=g^{(\tau -u)q(\tau )}$.
  • The verifier knows $g^{(\tau -u)}$ as $g^{\tau }$ is in $gp$ and $g^u$ the verifier can calculate, and it also knows $g^{q(\tau )}$ because that is the proof $\pi$ sent by the prover. However, Diffie-Hellman assumption tells us that just by knowing these two, the verifier can't compute $g^{(\tau -u)q(\tau )}$. So what do we do?
  • We can use a bilinear pairing! We will make use of the pairing $e(co{m}_f/g^v,g)=e(g^{(\tau -u)},\pi )$. Notice that this pairing translates to $e(g,g{)}^{f(\tau )-f(u)}=e(g,g{)}^{(\tau -u)q(\tau )}$. The verifier can simply check this equality, and accepts if it is correct.

sequenceDiagram
  actor P as Prover
  actor V as Verifier

  %% keygen
  note over P, V: gp = (g, g^t, g^(t^2), ..., g^(t^d))

  %% comittment
  note over P: f ∈ F
  P ->> V: com_f := g^f(t)

  %% eval
  V ->> P: u
  note over P: v = f(u)
  note over P: f(x)-f(u) = (x-u)q(x)

  %% verify
  P ->> V: v, proof π = g^q(t)
  note over V: g^(t-u) = g^t / g^u
  note over V: e(com_f / g^v, g) ?= e(g^(t-u), π)
  note over V: if true, Accept, otherwise Reject

q-Strong Bilinear Diffie-Hellman

What about the properties of KZG?

• Correctness: if the prover is honest, then the verifier will always accept.
• Soundness: how likely is a fake proof to be verified?

The answer to this comes from something called "q-Strong Bilinear Diffie-Hellman" (short for q-SBDH) assumption. That is, given $(p,\mathbb{G},g,{\mathbb{G}}_T,e)$ and $(g,g^{\tau },g^{{\tau }^2},\dots ,g^{{\tau }^d})$ it is hard to compute $e(g,g{)}^{\frac{1}{\tau -u}}$ for any $u$. This is a stronger assumption that computational Diffie-Hellman.

Let us prove the soundness then! We will do a Proof by Contradiction. Suppose $v^{\ast }\ne f(u)$ yet a fake proof ${\pi }^{\ast }$ passes the verification. We begin the proof by writing the bilinear pairing equivalence that the verifier checks for:

$$e(co{m}_f/g^{v^{\ast }},g)=e(g^{\tau -u},{\pi }^{\ast })$$

We will assume that the prover knows $f$, which is a strong assumption but we will explain it later (see Knowledge of Exponent). Therefore, we have the following equivalence:

$$e(g^{f(\tau )-v^{\ast }},g)=e(g^{\tau -u},{\pi }^{\ast })$$

Now the trick of the proof: we add $f(u)-f(u)$ to the leftmost exponent, which is effectively adding 0 so it does not change anything.

$$e(g^{f(\tau )-f(u)+f(u)-v^{\ast }},g)=e(g^{\tau -u},{\pi }^{\ast })$$

Now define $\delta =f(u)-v^{\ast }$, which is non-zero because we have said above that $v^{\ast }\ne f(u)$. We rewrite the left hand-side:

$$e(g^{(\tau -u)q(\tau )+\delta },g)=e(g^{\tau -u},{\pi }^{\ast })$$

As a result of pairing, we can move the exponents outside $e$ as:

$$e(g,g{)}^{(\tau -u)q(\tau )+\delta }=e(g,{\pi }^{\ast }{)}^{\tau -u}$$

Dividing both sides by $e(g,g{)}^{\tau -u}$ we get:

$$e(g,g{)}^{\delta }={\left(e(g,{\pi }^{\ast })/e(g,g{)}^{q(\tau )}\right)}^{\tau -u}$$

Finally, taking both sides to power $-1/(\tau -u)$ leads to a contradiction!

$$e(g,g{)}^{\frac{\delta }{\tau -u}}=e(g,{\pi }^{\ast })/e(g,g{)}^{q(\tau )}$$

Notice the left side that is $e(g,g{)}^{\frac{\delta }{\tau -u}}$, which is what q-SBDH was about! Even more, the right side of the equation only has globally available variables, so this means that the prover can break q-SBDH assumption.

Knowledge of Exponent (KoE)

We have said that we assume the prover knows $f$ such that $co{m}_f=g^{f(\tau )}$. How can we make sure of this? Here is how:

• Again you have $gp=(g,g^{\tau },g^{{\tau }^2},\dots ,g^{{\tau }^d})$
• Sample some random $\alpha$ compute $g{p}^{\alpha }=(g^{\alpha },g^{\alpha \tau },g^{\alpha {\tau }^2},\dots ,g^{\alpha {\tau }^d})$
• Now compute two commitments instead of one, $co{m}_f=g^{f(\tau )}$ and $co{m}_f^{\prime }=g^{\alpha f(\tau )}$

Now we can make use of bilinear pairings: if $e(co{m}_f,g^{\alpha })=e(co{m}_f^{\prime },g)$ there exists an extractor $E$ that extracts $f$ such that $co{m}_f=g^{f(\tau )}$. This extractor will extract $f$ in our proof above, where we assumed the prover knows $f$.

Let us then describe the KZG with knowledge soundness:

• Keygen generates both $gp$ and $g{p}^{\alpha }$
• Commit computes both $co{m}_f$ and $co{m}_f^{\prime }$
• Verify additionally checks $e(co{m}_f,g^{\alpha })=e(co{m}_f^{\prime },g)$

Note that this doubles the cost of key generation and commitments, as well as the verifier time.

Generic Group Model (GGM)

GGM [Shoup'97], [Maurer'05] can replace the KoE assumption and reduce commitment size in KZG. The informal definition is that the adversary is only given an oracle to compute the group operation, that is: given $(g,g^{\tau },g^{{\tau }^2},\dots ,g^{{\tau }^d})$ the adversary can only compute their linear combinations.

Properties of KZG

So let us write down the properties of KZG.

• Keygen requires trusted setup
• Commit requires $\mathcal{O}(d)$ group exponentiations and $\mathcal{O}(1)$ commitment size
• Eval requires $\mathcal{O}(d)$ group exponentiations, and $q(x)$ can be computed efficiently in linear time
• Proof size is $\mathcal{O}(1)$ for the single group element
• Verifier time is $\mathcal{O}(1)$ for the pairing check

Powers of Tau Ceremony

Okay, trusted setup sucks but we can make it a bit nicer: instead of letting one party come up with the global parameters, we will distribute this process to multiple parties. In doing so, even if only one party is honest and gets rid of the "toxic waste", then that is enough for us so that no one will be able to reconstruct the trapdoor. Here is how:

• Suppose your global parameters are $gp$ right now:

$$gp=(g^{\tau },g^{{\tau }^2},\dots ,g^{{\tau }^d})=(g_1,g_2,\dots ,g_d)$$

• As a participant in this ceremony, you sample some random $s$, and obtain new $g{p}^{\prime }$ as:

$$g{p}^{\prime }=(g_1^s,g_2^{s^2},\dots ,g_d^{s^d})=(g^{s\tau },g^{(s\tau {)}^2},\dots ,g^{(s\tau {)}^d})$$

• This can go on for many participants, see for example Perpetual Powers of Tau.

A new method [Nikolaenko-Ragsdale-Bonneau-Boneh'22] provides a way to check the correctness of $g{p}^{\prime }$ too. The idea is:

• the contributor knows $s$ such that $g_1^{\prime }=(g_1{)}^s$
• and $g{p}^{\prime }$ consists of consecutive powers $e(g_i^{\prime },g_1^{\prime })=e(g_{i+1}^{\prime },g)$ where $g_1^{\prime }\ne 1$

Variants of KZG

We will look at several extensions of KZG univariate polynomial commitment scheme.

Multivariate KZG

[Papamanthou-Shi-Tamassia'13] describes a way to use KZG for multivariate polynomials. The idea is:

$$f(x_1,x_2,\dots ,x_k)-f(u_1,u_2,\dots ,u_k)=\sum _{i=1}^k(x_i-u_i)q_i(\vec{x})$$

• Keygen will sample $\vec{\tau }={\tau }_1,{\tau }_2,\dots ,{\tau }_k$ to compute $gp$ as $g$ raised to all possible monomials of $\vec{\tau }$
• Commit will compute $co{m}_f=g^{f({\tau }_1,{\tau }_2,\dots ,{\tau }_k)}$
• Eval will compute a group element for each polynomial ${\pi }_i=g^{q_i(\vec{\tau })}$
• Verify will check $e(co{m}_f/g^v,g)={\prod }_{i=1}^{k}e(g^{{\tau }_i-u_i},{\pi }_i)$

Notice that the proof size and verifier time is greater here.

You can find in practice vSQL [ZGKPP'17] and Libra [XZZPS'19] that makes use of multivariate KZG as the commitment scheme and Sum-check protocol or GKR protocol as the IOP to obtain a SNARK.

Achieving Zero-Knowledge

Plain KZG is not zero-knowledge, e.g. $co{m}_f=g^{f(\tau )}$ is deterministic. Also remember that to formally show zero-knowledgeness, we need a simulator construction that can simulate the view of the commitment scheme.

[ZGKPP'18] shows a method to do this by masking with randomizers.

• Commit will compute the masked $co{m}_f=g^{f(\tau )+r\eta }$
• Eval will also be masked as follows:

$$f(x)+ry-f(u)=(x-u)(q(x)+r^{\prime }y)+y(r-r^{\prime }(x-u))$$

The proof will therefore be $\pi =g^{q(\tau )+r^{\prime }\eta },g^{r-r^{\prime }(\tau -u)}$. Note that this looks much like the bivariate extension of KZG, but the other polynomial is like some added randomness to provide zero-knowledge property.

Batch Proofs on a Single Polynomial

Prover wants to prove $f$ at multiple points $u_1,u_2,\dots ,u_m$ for $m<d$. The key idea is to extrapolate $f(u_1),f(u_2),\dots ,f(u_m)$ to obtain $h(x)$. Then,

• we find a quotient polynomial from $f(x)-h(x)={\prod }_{i=1}^m(x-u_i)q(x)$
• the proof then becomes $\pi =g^{q(\tau )}$
• verifier will check $e(co{m}_f/g^{h(\tau )},g)=e(g^{{\prod }_{i=1}^m(\tau -u_i)},\pi )$

Batch Proofs on Multiple Polynomials

Prover wants to prove $f$ at multiple points and polynomials $f_i(u_{i,j})=v_{i,j}$ for $i\in [n],j\in [m]$. The key idea is to extrapolate $f_i(u_{i,1}),f_i(u_{i,2}),\dots ,f_i(u_{i,m})$ to obtain $h_i(x)$. Then,

• we find quotient polynomials from $f_i(x)-h_i(x)={\prod }_{j=1}^m(x-u_{i,j})q_i(x)$
• the proof will have all $q_i(x)$ in a random linear combination

Bulletproofs

Although the powers-of-tau ceremony helps on the "trusted setup" problem, Bulletproofs [BCCGP'16], [BBBPWM'18] completely remove the "trusted setup" problem of KZG!

• $keygen$
  • Bulletproofs have a "transparent setup" phase, which is to simply $d+1$ randomly sampled elements from a group $\mathbb{G}$, resulting in $gp=(g_0,g_1,\dots ,g_d)$
• $commit(gp,f)\to co{m}_f$
  • suppose you have a polynomial $f(x)=f_0+f_{1}x+f_2{x}^2+\dots f_d{x}^d$
  • commitment is $co{m}_f=g_0^{f_0}{g}_1^{f_1}\dots g_d^{f_d}$
  • notice that this is a "vector commitment" version of a Pedersen Commitment

Then, do $eval$ and $verify$ recursively around $\log d$ times:

• $eval(gp,f,u)$
  • find $v=f(u)$
  • compute $L,R,v_l,v_r$
  • receive a random $r$ from verifier and reduce $f$ to $f^{\prime }$ of degree $d/2$
  • update the global parameter to be $g{p}^{\prime }$
• $verify(gp,co{m}_f,u,v,\pi )$
  • check $v=v_L+v_R\times u^{d/2}$
  • generate $r$ randomly
  • update $co{m}^{\prime }=L^r\times co{m}_f\times R^{r^{-1}}$ (this is the magic trick)
  • update the global parameter to be $g{p}^{\prime }$
  • set $v^{\prime }=r{v}_L+r_R$

The idea of Bulletproofs is to recursively divide a polynomial in two polynomials, and commit to those smaller polynomials, eventually reducing whatever degree you have started with to 1.

The Magic Trick

So let's go over what happens in that magical line where we obtain the new commitment given $L,R$ (left & right respectively). Suppose we have a polynomial of degree 3

$$f(x)=f_0+f_{1}x+f_2{x}^2+f_3{x}^3$$

and our commitment is:

$$co{m}_f=g_0^{f_0}{g}_1^{f_1}{g}_2^{f_2}{g}_3^{f_3}$$

The prover splits the polynomial into two polynomials of half the degree:

• left half: $f_L(x)=f_0+f_{1}x$
• right half: $f_R(x)=f_2+f_{3}x$

It will also commit the each half:

• left half: $L=g_2^{f_0}{g}_3^{f_1}$
• right half: $R=g_0^{f_2}{g}_1^{f_3}$

Did you notice the criss-cross between the group elements and their exponents? The $g$ terms are fitting nicely with the coefficients, but the exponents are actually belonging to the other polynomial! This is a way of "relating" both halves together, so to restrain the prover to some extent and keep the computations sound.

The magical line is the following:

$$co{m}^{\prime }=L^r\times co{m}_f\times R^{r^{-1}}$$

$$co{m}^{\prime }=\left(g_0^{f_0+r^{-1}{f}_2}{g}_2^{r{f}_0+f_2}\right)\left(g_1^{f_1+r^{-1}{f}_3}{g}_3^{r{f}_1+f_3}\right)$$

$$co{m}^{\prime }={\left(g_0^{r^{-1}}{g}_2\right)}^{r{f}_0+f_2}\times {\left(g_1^{r^{-1}}{g}_3\right)}^{r{f}_1+f_3}$$

Now notice that this commitment is what you would have gotten if you had:

• a polynomial $f^{\prime }(x)=(r{f}_0+f_2)+(r{f}_1+f_3)x$
• and $g{p}^{\prime }=\left(g_0^{r^{-1}}{g}_2,g_1^{r^{-1}}{g}_3\right)$

Both are half the size of what we had started with! If you keep doing this recursively, you will end up with a degree-1 polynomial in around $\log d$ steps. Without caring about zero-knowledge property, the prover could simply send the constant sized polynomial for the last step to prove the evaluation.

Also to mention, you could take "odd-elements & even-elements" instead of "left-half & right-half" for this process, which is similar to what is done in FFT, and it would still work!

sequenceDiagram
	actor P as Prover
	actor V as Verifier

  %% keygen
	note over P, V: gp = (g_0, g_1, g_2, ..., g_d)

	%% comittment
	note over P: f ∈ F
	P ->> V: com_f := g_0f^0 * g_1f^1 * ... * g_df^d

  %% eval
	V ->> P: u
  note over P: v = f(u)
	P ->> V: v

	loop while deg(f) > 1
	note over V: sample random r
	V ->> P: r

  note over P: L, R := split(f)
	P ->> V: v_L = L(u), com_L, v_R = R(u), com_R
	note over P: f' := reduce(L, R, r)

  %% verify
  note over V: assert: v == v_L + v_R * u^2
	note over V: com' = L^r * com_f * R^{r^-1}
	note over V: update gp as gp'
	note over V: v' = r * v_L + v_R
	note over V, P: recurse with f', com', v', gp'
	end

	note over V, P: prove eval of a const-sized polynomial
	note over V: accept or reject

More Poly-Commit Schemes

More advanced schemes based on d-log with transparent setup are out there, and we will go over them quickly.

Hyrax

Hyrax [Wahby-Tzialla-Shelat-Thaler-Walfish'18] improves the verifier time to $\mathcal{O}(\sqrt{d})$ by representing the coefficients as a 2D matrix. This way, it commits to the matrix row-wise, and does reduction column-wise. Proof size also becomes $\mathcal{O}(\sqrt{d})$.

Dory

Dory [Lee'21] delegates the structured computation to the prover using inner pairing product arguments [BMMTV'21]. This way, verifier time becomes $\mathcal{O}(\log d)$ and prover time becomes $\mathcal{O}(\sqrt{d})$ exponentiations plus $\mathcal{O}(d)$ field operations, so prover time is still linear but in practice it is a bit more efficient.

Dark

Dark [Bünz-Fisch-Szepieniec'20] achieves $\mathcal{O}(\log d)$ proof size and verifier time! The trick here is to use group of an unknown order.

Summary

Here is a quick summary of all the methods covered in this lecture.