 Recall: How to build an Efficient SNARK?
 What is a Polynomial Commitment?
 Group Theory
 KZG PolyCommit Scheme with Pairings
 Bulletproofs
 More PolyCommit Schemes
 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:
 A functional commitment scheme, which is a cryptographic object
 A suitable interactive oracle proof (IOP), which is an information theoretic object
In Lecture 5, we have seen PLONK, which operated with:
 A univariate polynomial commitment scheme
 PLONK polynomial IOP
In Lecture 4, we have seen another method using the sumcheck protocol:
 A multivariate polynomial commitment scheme
 Sumcheck 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 $F$. The prover has some polynomial $f∈F$ that is a function $f:X→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:
 Prover commits to the polynomial, and sends the commitment $com_{f}$, also shown as $f $.
 The verifier would like to query this polynomial at some value $u$, so it sends this to the prover.
 Prover evaluates $v:=f(u)$ and sends this to verifier, along with a proof $π$ that indeed $v=f(u)$ and $f∈F$.
 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(λ,F)→gp$ generate public parameters given the polynomial family and security parameter $λ$. Note the $gp$ is also known as "common reference string", or "public key" too.
 $commit(gp,f)→com_{f}$ computes the commitment to the given polynomial.
 $eval(gp,f,u)→v,π$ 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∈F$.
 $verify(gp,com_{f},u,v,π)→{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←keygen(λ,F)$
 $com_{f}←A_{0}(gp)$
 $v,π←A_{1}(gp,u)$
where $Pr[V(vp,x,π)=accept]=1$, then there is an efficient extractor $E$ that uses $A_{1}$ as a black box (oracle) such that:
 $gp←keygen(λ,F)$
 $com_{f}←A_{0}(gp)$
 $f←E(gp,com_{f})$
where $Pr[f(u)=vandf∈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 $G$ and an operation $∗$. It satisfies the following properties:
 Closure: $∀a,b∈G$ it holds that $a∗b∈G$. In other words, the result of this operation is still an element of this group, it is closed in this group!
 Associativity: $∀a,b,c∈G$ it holds that $(a∗b)∗c=a∗(b∗c)$. The order of execution should not matter.
 Identity: $∃e∈G$ such that $∀a∈G$ it holds that $e∗a=a∗e=a$. We call $e$ the identity element, because the result of operating on it is identical to the operand.
 Inverse: $∀a∈G,∃b∈G$ such that $a∗b=b∗a=e$. This is very important to keep in mind.
For example, the set of integers $Z={…,−1,0,1,…}$ 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 $mod$ some prime number $p$, which is the set ${1,2,…,p−1}$ under the multiplication operation $×$. This is denoted as $Z_{p}$.
 Elliptic curves, we will not go into this yet though.
Generator of a Group
An element $g∈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 $Z_{7}={1,2,3,4,5,6}$. See what happens if we take powers of 3 in this group.
$1$  $2$  $3$  $4$  $5$  $6$ 

$3_{6}$  $3_{2}$  $3_{1}$  $3_{4}$  $3_{5}$  $3_{3}$ 
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 $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∈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 postquantum secure.
DiffieHellman Assumption
You might remember this duo from the DiffieHellman KeyExchange [DiffieHellamn'76]. The paper is based on the DiffieHellman Assumption, which is very similar to the discrete logarithm assumption.
 given $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:
 $G$: the base group, a multiplicative cyclic group
 $G_{T}$: the target group, yet another multiplicative cyclic group
 $p$: the order of both $G$ and $G_{T}$
 $g$: the generator of base group $G$
 $e$: a pairing operation $e:G×G→G_{T}$
The pairing must have the following bilinearity property:
$∀P,Q,∈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: DiffieHellman
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 DiffieHellman 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 [BonehLynnShacham'01] is an example usage of bilinear pairings. It is a signature scheme with the following functions:
 $keygen(p,G,g,G_{T},e)→(sk=x,pk=g_{x})$ that is the secret (private) key and public key respectively
 $sign(sk,m)→σ=H(m)_{x}$ where $H$ is a cryptographic hash function that maps the message space to $G$
 $verify(pk,σ,m)→{0,1}$ will verify if $e(H(m),g_{x})=e(σ,g)$. Notice that $g_{x}$ comes from $pk$, and $H$ is a known public hash function
KZG PolyCommit 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 $F=F_{p}[X]$ and some polynomial that you would like to commit $f∈F$. You also have a bilinear pairing $p,G,q,G_{T},e$. Let's see how KZG works with these.

$keygen(λ,F)→gp$
 Sample a random $τ∈F_{P}$
 Set $gp=(g,g_{τ},g_{τ_{2}},…,g_{τ_{d}})$
 Delete $τ$, 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)→com_{f}$
 The polynomial is represented with its coefficients $f(x)=f_{0}+f_{1}x.+f_{2}x_{2}+…+f_{d}x_{d}$.
 The commitment is $com_{f}=g_{f(τ)}$. How can this be done without knowing $τ$? Well, that is where $gp$ comes into play.
 Notice that $g_{f(τ)}=g_{f_{0}=f_{1}τ+f_{2}τ_{2}+…+f_{d}τ_{d}}$
 Its equal to $(g)_{f_{0}}+(g_{τ})_{f_{1}}+(g_{τ_{2}})_{f_{2}}+…(g_{τ_{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)→v,π$
 A verifier wants to query this polynomial at point $u$, and you would like to show that $f(u)=v$ along with a proof $π$ 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 $π=g_{q(τ)}$ which you can do without knowing $τ$ but instead using $gp$, as shown in the last bullet under $commit$.

$verify(gp,com_{f},u,v,π)→{0,1}$
 The idea is to check the equation at point $τ$ as $g_{f(τ)−f(u)}=g_{(τ−u)q(τ)}$.
 The verifier knows $g_{(τ−u)}$ as $g_{τ}$ is in $gp$ and $g_{u}$ the verifier can calculate, and it also knows $g_{q(τ)}$ because that is the proof $π$ sent by the prover. However, DiffieHellman assumption tells us that just by knowing these two, the verifier can't compute $g_{(τ−u)q(τ)}$. So what do we do?
 We can use a bilinear pairing! We will make use of the pairing $e(com_{f}/g_{v},g)=e(g_{(τ−u)},π)$. Notice that this pairing translates to $e(g,g)_{f(τ)−f(u)}=e(g,g)_{(τ−u)q(τ)}$. 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) = (xu)q(x) %% verify P >> V: v, proof π = g^q(t) note over V: g^(tu) = g^t / g^u note over V: e(com_f / g^v, g) ?= e(g^(tu), π) note over V: if true, Accept, otherwise Reject
qStrong Bilinear DiffieHellman
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 "qStrong Bilinear DiffieHellman" (short for qSBDH) assumption. That is, given $(p,G,g,G_{T},e)$ and $(g,g_{τ},g_{τ_{2}},…,g_{τ_{d}})$ it is hard to compute $e(g,g)_{τ−u1}$ for any $u$. This is a stronger assumption that computational DiffieHellman.
Let us prove the soundness then! We will do a Proof by Contradiction. Suppose $v_{∗}=f(u)$ yet a fake proof $π_{∗}$ passes the verification. We begin the proof by writing the bilinear pairing equivalence that the verifier checks for:
$e(com_{f}/g_{v_{∗}},g)=e(g_{τ−u},π_{∗})$
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(τ)−v_{∗}},g)=e(g_{τ−u},π_{∗})$
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(τ)−f(u)+f(u)−v_{∗}},g)=e(g_{τ−u},π_{∗})$
Now define $δ=f(u)−v_{∗}$, which is nonzero because we have said above that $v_{∗}=f(u)$. We rewrite the left handside:
$e(g_{(τ−u)q(τ)+δ},g)=e(g_{τ−u},π_{∗})$
As a result of pairing, we can move the exponents outside $e$ as:
$e(g,g)_{(τ−u)q(τ)+δ}=e(g,π_{∗})_{τ−u}$
Dividing both sides by $e(g,g)_{τ−u}$ we get:
$e(g,g)_{δ}=(e(g,π_{∗})/e(g,g)_{q(τ)})_{τ−u}$
Finally, taking both sides to power $−1/(τ−u)$ leads to a contradiction!
$e(g,g)_{τ−uδ}=e(g,π_{∗})/e(g,g)_{q(τ)}$
Notice the left side that is $e(g,g)_{τ−uδ}$, which is what qSBDH was about! Even more, the right side of the equation only has globally available variables, so this means that the prover can break qSBDH assumption.
Knowledge of Exponent (KoE)
We have said that we assume the prover knows $f$ such that $com_{f}=g_{f(τ)}$. How can we make sure of this? Here is how:
 Again you have $gp=(g,g_{τ},g_{τ_{2}},…,g_{τ_{d}})$
 Sample some random $α$ compute $gp_{α}=(g_{α},g_{ατ},g_{ατ_{2}},…,g_{ατ_{d}})$
 Now compute two commitments instead of one, $com_{f}=g_{f(τ)}$ and $com_{f}=g_{αf(τ)}$
Now we can make use of bilinear pairings: if $e(com_{f},g_{α})=e(com_{f},g)$ there exists an extractor $E$ that extracts $f$ such that $com_{f}=g_{f(τ)}$. 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 $gp_{α}$
 Commit computes both $com_{f}$ and $com_{f}$
 Verify additionally checks $e(com_{f},g_{α})=e(com_{f},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_{τ},g_{τ_{2}},…,g_{τ_{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 $O(d)$ group exponentiations and $O(1)$ commitment size
 Eval requires $O(d)$ group exponentiations, and $q(x)$ can be computed efficiently in linear time
 Proof size is $O(1)$ for the single group element
 Verifier time is $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_{τ},g_{τ_{2}},…,g_{τ_{d}})=(g_{1},g_{2},…,g_{d})$
 As a participant in this ceremony, you sample some random $s$, and obtain new $gp_{′}$ as:
$gp_{′}=(g_{1},g_{2},…,g_{d})=(g_{sτ},g_{(sτ)_{2}},…,g_{(sτ)_{d}})$
 This can go on for many participants, see for example Perpetual Powers of Tau.
A new method [NikolaenkoRagsdaleBonneauBoneh'22] provides a way to check the correctness of $gp_{′}$ too. The idea is:
 the contributor knows $s$ such that $g_{1}=(g_{1})_{s}$
 and $gp_{′}$ consists of consecutive powers $e(g_{i},g_{1})=e(g_{i+1},g)$ where $g_{1}=1$
Variants of KZG
We will look at several extensions of KZG univariate polynomial commitment scheme.
Multivariate KZG
[PapamanthouShiTamassia'13] describes a way to use KZG for multivariate polynomials. The idea is:
$f(x_{1},x_{2},…,x_{k})−f(u_{1},u_{2},…,u_{k})=i=1∑k (x_{i}−u_{i})q_{i}(x)$
 Keygen will sample $τ=τ_{1},τ_{2},…,τ_{k}$ to compute $gp$ as $g$ raised to all possible monomials of $τ$
 Commit will compute $com_{f}=g_{f(τ_{1},τ_{2},…,τ_{k})}$
 Eval will compute a group element for each polynomial $π_{i}=g_{q_{i}(τ)}$
 Verify will check $e(com_{f}/g_{v},g)=∏_{i=1}e(g_{τ_{i}−u_{i}},π_{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 Sumcheck protocol or GKR protocol as the IOP to obtain a SNARK.
Achieving ZeroKnowledge
Plain KZG is not zeroknowledge, e.g. $com_{f}=g_{f(τ)}$ is deterministic. Also remember that to formally show zeroknowledgeness, 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 $com_{f}=g_{f(τ)+rη}$
 Eval will also be masked as follows:
$f(x)+ry−f(u)=(x−u)(q(x)+r_{′}y)+y(r−r_{′}(x−u))$
The proof will therefore be $π=g_{q(τ)+r_{′}η},g_{r−r_{′}(τ−u)}$. Note that this looks much like the bivariate extension of KZG, but the other polynomial is like some added randomness to provide zeroknowledge property.
Batch Proofs on a Single Polynomial
Prover wants to prove $f$ at multiple points $u_{1},u_{2},…,u_{m}$ for $m<d$. The key idea is to extrapolate $f(u_{1}),f(u_{2}),…,f(u_{m})$ to obtain $h(x)$. Then,
 we find a quotient polynomial from $f(x)−h(x)=∏_{i=1}(x−u_{i})q(x)$
 the proof then becomes $π=g_{q(τ)}$
 verifier will check $e(com_{f}/g_{h(τ)},g)=e(g_{∏_{i=1}(τ−u_{i})},π)$
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∈[n],j∈[m]$. The key idea is to extrapolate $f_{i}(u_{i,1}),f_{i}(u_{i,2}),…,f_{i}(u_{i,m})$ to obtain $h_{i}(x)$. Then,
 we find quotient polynomials from $f_{i}(x)−h_{i}(x)=∏_{j=1}(x−u_{i,j})q_{i}(x)$
 the proof will have all $q_{i}(x)$ in a random linear combination
Bulletproofs
Although the powersoftau 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 $G$, resulting in $gp=(g_{0},g_{1},…,g_{d})$
 $commit(gp,f)→com_{f}$
 suppose you have a polynomial $f(x)=f_{0}+f_{1}x+f_{2}x_{2}+…f_{d}x_{d}$
 commitment is $com_{f}=g_{0}g_{1}…g_{d}$
 notice that this is a "vector commitment" version of a Pedersen Commitment
Then, do $eval$ and $verify$ recursively around $gd$ 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_{′}$ of degree $d/2$
 update the global parameter to be $gp_{′}$
 $verify(gp,com_{f},u,v,π)$
 check $v=v_{L}+v_{R}×u_{d/2}$
 generate $r$ randomly
 update $com_{′}=L_{r}×com_{f}×R_{r_{−1}}$ (this is the magic trick)
 update the global parameter to be $gp_{′}$
 set $v_{′}=rv_{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:
$com_{f}=g_{0}g_{1}g_{2}g_{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}g_{3}$
 right half: $R=g_{0}g_{1}$
Did you notice the crisscross 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:
$com_{′}=L_{r}×com_{f}×R_{r_{−1}}$
$com_{′}=(g_{0}g_{2})(g_{1}g_{3})$
$com_{′}=(g_{0}g_{2})_{rf_{0}+f_{2}}×(g_{1}g_{3})_{rf_{1}+f_{3}}$
Now notice that this commitment is what you would have gotten if you had:
 a polynomial $f_{′}(x)=(rf_{0}+f_{2})+(rf_{1}+f_{3})x$
 and $gp_{′}=(g_{0}g_{2},g_{1}g_{3})$
Both are half the size of what we had started with! If you keep doing this recursively, you will end up with a degree1 polynomial in around $gd$ steps. Without caring about zeroknowledge property, the prover could simply send the constant sized polynomial for the last step to prove the evaluation.
Also to mention, you could take "oddelements & evenelements" instead of "lefthalf & righthalf" 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 constsized polynomial note over V: accept or reject
More PolyCommit Schemes
More advanced schemes based on dlog with transparent setup are out there, and we will go over them quickly.
Hyrax
Hyrax [WahbyTziallaShelatThalerWalfish'18] improves the verifier time to $O(d )$ by representing the coefficients as a 2D matrix. This way, it commits to the matrix rowwise, and does reduction columnwise. Proof size also becomes $O(d )$.
Dory
Dory [Lee'21] delegates the structured computation to the prover using inner pairing product arguments [BMMTV'21]. This way, verifier time becomes $O(gd)$ and prover time becomes $O(d )$ exponentiations plus $O(d)$ field operations, so prover time is still linear but in practice it is a bit more efficient.
Dark
Dark [BünzFischSzepieniec'20] achieves $O(gd)$ 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.
Scheme  Prover Time  Proof Size  Verifier Time  Setup Phase  Cryptographic primitive 

KZG  $O(d)$  $O(1)$  $O(1)$  Trusted  Pairing 
Bulletproofs  $O(d)$  $O(gd)$  $O(d)$  Transparent  Discretelog 
Hyrax  $O(d)$  $O(d )$  $O(d )$  Transparent  Discretelog 
Dory  $O(d)$  $O(gd)$  $O(gd)$  Transparent  Pairing 
Dark  $O(d)$  $O(gd)$  $O(gd)$  Transparent  Unknown order Group 