1# Implementing the powers of tau contributor
  2*2023-01-02*
  3
  4In the following notes we go over the ideas behind the *Powers of Tau* ceremony, how participants contribute and how the contributions are verified.
  5
  6The powers of tau are used in schemes such as KZG Commitments, and by consequence in the Plonk-KZG and in Verkle Trees use cases, which the later ones are in the Ethereum roadmap, but probably the ceremony output will be used in many other applications.
  7The ceremony is named also as *Trusted Setup Ceremony*, and *SRS* (Structured Reference String) in Plonk and Sonic papers. 
  8
  9Specifically these notes focus on the powers of tau ceremony that is [being prepared in Ethereum](https://github.com/ethereum/kzg-ceremony). For learning about the specifics of the powers of tau reasoning, I've used the following two documents:
 10
 11- [KZG10-Ceremony-audit-report.pdf, by SECBIT Labs](https://github.com/ethereum/kzg-ceremony/blob/main/KZG10-Ceremony-audit-report.pdf)
 12- [*Why and how zkSNARKs work*, by Maksym Petkus](https://arxiv.org/abs/1906.07221v1)
 13
 14Additionally, [this article by Vitalik Buterin](https://vitalik.ca/general/2022/03/14/trustedsetup.html) explains the ideas behind trusted setups.
 15
 16The contents of these notes are distributed as follows:
 17<br><span style="margin-right:40px;"></span>
 18    <a style="color:gray;" href="#the-main idea">The main idea</a>
 19<br><span style="margin-right:40px;"></span>
 20    <a style="color:gray;" href="#preliminaries">Preliminaries</a>
 21<br><span style="margin-right:40px;"></span>
 22    <a style="color:gray;" href="#participant-contribution">Participant contribution</a>
 23<br><span style="margin-right:40px;"></span>
 24    <a style="color:gray;" href="#proof-of correct computation">Proof of correct computation</a>
 25<br><span style="margin-right:40px;"></span>
 26    <a style="color:gray;" href="#contribution-verification">Contribution verification</a>
 27<br><span style="margin-right:40px;"></span>
 28    <a style="color:gray;" href="#full-flow">Full flow</a>
 29<br><span style="margin-right:40px;"></span>
 30    <a style="color:gray;" href="#conclusions">Conclusions</a>
 31
 32Across these notes some snippets of Sage code are provided, the full Sage code can be found [here](https://github.com/arnaucube/math/blob/master/powersoftau.sage), and also a [full implementation in Go](https://github.com/arnaucube/eth-kzg-ceremony-alt) which also contains a CLI to participate in the upcomming Ethereum KZG-Ceremony.
 33
 34
 35### The main idea
 36The main idea is that we want to compute $\tau^0, \tau^1, \tau^2, \ldots, \tau^{n-1}$, where $\tau$ should be unknown. In order to achieve this, we use some technics to combine different $\tau$s from different contributors, in a way where we obtain the powers of a tau which is a combination of the different secret taus ($\tau_{p_i}$) of the different participants.
 37
 38The $\tau_{p_i}$ should be secret for each participant, furthermore, it should be generated from some source of randomness and destroyed at the end.
 39
 40As we've mentioned, we want to come up with the powers of tau where tau is a combination of the taus from all the participants, in a way where as long as there is at least one honest participant, which does not share their part of the final tau, the combined-tau can not be recovered and the ceremony is assumed to be safe.
 41
 42This is important, because if somebody has knowledge of the tau value, could generate fake proofs. As an example [this article by Kobi Gurkan](https://medium.com/qed-it/how-toxic-is-the-waste-in-a-zksnark-trusted-setup-9b250d59bdb4) shows how fake BCTV14a proofs can be generated if tau is known.
 43
 44This is relevant in the context of [KZG Commitments](https://arnaucube.com/blog/kzg-commitments.html), specially in the roadmap of Ethereum.
 45Ethereum will run the Ceremony which will be used at least in [EIP-4844](https://eips.ethereum.org/EIPS/eip-4844). That's why EF's is encouraging people to participate in various ways, as the Ceremony is considered safe as long as there is at least one honest participant, with the idea that if you participate, assuming that you consider yourself honest, you can consider the Ceremony safe.
 46
 47The output of the ceremony will be used in the Ethereum VerkleTrees, which uses KZG Commitments, but also it will be useful for Plonk-KZG proofs.
 48
 49So the best way to trust the output of the ceremony is by becoming a participant yourself!, Furhermore, by participating with your own code ^^
 50
 51### Preliminaries
 52
 53**Pairing**<br>
 54We will try to focus only in the concepts that we strictly need for the implementation, so we will treat Pairings as a black box with some simplified properties.
 55
 56For our use case, we use asymmetric bilinear pairings. We can see an asymmetric bilinear pairing as a function that maps an element from the group $\mathbb{G_1}$ and another one from $\mathbb{G_2}$ into an el element of the group $\mathbb{G_T}$.
 57
 58$$e: \mathbb{G_1} \times \mathbb{G_2} \longrightarrow \mathbb{G_T}$$
 59
 60For our use case, we'll focus only on one property, *bilinearity*.
 61
 62Let $a, b \in \mathbb{F_q}$, $\mathbb{G}_1 = \langle G \rangle$ and $\mathbb{G}_2 = \langle H \rangle~$ (In other words, $G$ is the generator of $\mathbb{G}_1$, and $H$ is the generator of $\mathbb{G}_2$).
 63
 64Then, the bilinearity property tells us that
 65
 66$$e(a \cdot G,~b \cdot H) = e((a \cdot b) \cdot G,~H) = e(G,~(a \cdot b) \cdot H)$$
 67
 68For better readability, we will use the following notation to represent the scalar point multiplication:
 69
 70$$[x]_1 = x \cdot G \in \mathbb{G}_1\newline
 71[x]_2 = x \cdot H \in \mathbb{G}_2$$
 72
 73So, our previous bilinearity example would look like
 74
 75$$e([a]_1, [b]_2) = e([a \cdot b]_1, [1]_2) = e([1]_1, [a \cdot b]_2)$$
 76
 77In our practical use case, we use the [BLS12-381](https://hackmd.io/@benjaminion/bls12-381) pairing, where $\mathbb{G}_1, \mathbb{G}_2$ are elliptic curve groups, thus the points $G, H$ are elliptic curve points.
 78
 79**Code**<br>
 80For the code examples we'll use [SageMath](https://www.sagemath.org), but the code would look quite similar in Python, and the same logic can be implemented in any language.
 81
 82
 83### Participant contribution
 84In the context of SRS (Structured Reference String), the powers of tau consist of an array containing the scalar multiplication of the generator point by each power of tau, eg. $\tau^0 \cdot G,~\tau^1 \cdot G,~\tau^2 \cdot G,~\tau^3 \cdot G \ldots$
 85
 86For our case, we'll generate $n$ powers of tau on $\mathbb{G}_1$, and $m$ on $\mathbb{G}_2$. We will denote the combination of both $\mathbb{G}_1$ and $\mathbb{G}_2$ powers of tau by SRS.
 87
 88Each participant will obtain the previous-participant generated SRS, which is formed by
 89
 90$$\{ [\tau^0]_1, [\tau^1]_1, [\tau^2]_2, \ldots, [\tau^{n-1}]_1 \},\\
 91\{ [\tau^0]_2, [\tau^1]_2, [\tau^2]_2, \ldots, [\tau^{m-1}]_2 \}$$
 92
 93for simplicity, we will represent it as
 94
 95$$\{~[~\tau^i]_1~\}^{n-1}_{i=0},~\{~[~\tau^i]_2~\}^{m-1}_{j=0}$$
 96
 97
 98Each participant generates their secret random tau $\tau_p$, which to avoid confusion we will denote as $p \in \mathbb{F}_r$. From it, the participant can compute $[p]_2 \in \mathbb{G}_2$.
 99
100Then the participant proceeds to update the reference string (SRS), by multiplying each element by $p^i$:
101
102$$\{~ p^i \cdot [~ \tau^i]_1~\}^{n-1}_{i=0},~\{~ p^i \cdot [~\tau^i]_2~\}^{m-1}_{j=0}$$
103
104which, by the properties of scalar multiplication of a point, is equivalent to
105
106$$\{~ [~ (p \cdot \tau)^i]_1~\}^{n-1}_{i=0},~\{~ [~ (p \cdot \tau)^i]_2~\}^{m-1}_{j=0}$$
107
108and we denote $p \cdot \tau$ as $\tau'$, so we can write the previous expression as
109
110$$\{~[~\tau'^i]_1~\}^{n-1}_{i=0},~\{~[~\tau'^i]_2~\}^{m-1}_{j=0}$$
111
112which is
113
114$$\{ [(\tau \cdot p)^0]_1, [(\tau \cdot p)^1]_1, [(\tau \cdot p)^2]_2, \ldots, [(\tau \cdot p)^{n-1}]_1 \},\\
115\{ [(\tau \cdot p)^0]_2, [(\tau \cdot p)^1]_2, [(\tau \cdot p)^2]_2, \ldots, [(\tau \cdot p)^{m-1}]_2 \}$$
116
117Notice that the contributor does not know the previous $\tau$, but can obtain $(\tau \cdot p)^i$.
118
119<br><br>
120We can express the previous logic as follows:
121
122```python
123def compute_contribution(new_tau, prev_srs):
124    g1s = [None] * len(prev_srs[0])
125    g2s = [None] * len(prev_srs[1])
126    srs = [g1s, g2s]
127    Q = e.r
128
129    # compute [τ'⁰]₁, [τ'¹]₁, [τ'²]₁, ..., [τ'ⁿ⁻¹]₁, where n = len(prev_srs.G1s)
130    for i in range(0, len(prev_srs[0])):
131        srs[0][i] = (new_tau^i) * prev_srs[0][i]
132    
133    # compute [τ'⁰]₂, [τ'¹]₂, [τ'²]₂, ..., [τ'ⁿ⁻¹]₂, where n = len(prev_srs.G2s)
134    for i in range(0, len(prev_srs[1])):
135        srs[1][i] = (new_tau^i) * prev_srs[1][i]
136
137    return srs
138```
139
140### Proof of correct computation
141The participant will compute the proof, which consists of
142
143$$\pi = ([\tau']_1,~[p]_2)$$
144
145which is equivalent to $\pi = (\tau' \cdot G,~p \cdot H) = ((p \cdot \tau) \cdot G,~p \cdot H)$
146
147In the next section we will see how this is used to verify the contribution correct computation.
148
149<br>
150We implement this logic as follows:
151
152```python
153def generate_proof(tau, prev_srs, new_srs):
154    # g_1^{tau'} = g_1^{p * tau} = SRS_G1s[1] * p
155    g1_ptau = prev_srs[0][1] * tau
156    # g_2^{p}
157    g2_p = tau * e.G2
158    return [g1_ptau, g2_p]
159```
160
161### Contribution verification
162This is the interesting part. We want to check that the new SRS is well computed from the previous SRS together with the new tau. We want to avoid accepting contributions that do not follow the powers of tau structure, or that contain empty elements or that do not derive from the previous SRS.
163
164Following the powers of tau structure means that
165
166$$\tau'^{i+1} = \tau' \cdot \tau'^i ~~\forall~i \in [1, n-1]$$
167
168And the relation between the new SRS and the previous SRS is
169
170$$\tau' = \tau \cdot p$$
171where $\tau$ is the secret element from the previous SRS and $p$ is the secret one from the new SRS, resulting in the combined $\tau'$.
172
173Now, we're interested into how we can check these relations in the context of the SRS elements. A new contribution can be verified as follows:
174
1751. Check that elements of the new SRS are non-empty, non-zero and in the correct prime order subgroups.
1762. Get the proof ($\pi = ([\tau']_1, [p]_2)$), and confirm that the 1st element is equal to the element in position 1 $[\tau'^1]_1$ of the new SRS (which corresponds to $\tau'$ powered to $1$).
177
1783. Check that $\tau'$ (the new SRS) is correctly related to $\tau$ (the previous SRS).
179
180    To check this, we rely on the pairing properties and we use the proof value generated by the contributor, which consists of $[p]_2$
181
182    $$e([\tau]_1, [p]_2) \stackrel{?}{=} e([\tau']_1, [1]_2)$$
183    
184    We can see how this holds, as $\tau' = p \cdot \tau$, and by the bilinear property of the pairing (see [Preliminearies section](#preliminaries)) we have $e(a \cdot G, b \cdot H) = e((a \cdot b) \cdot G, H)$, which in our notation is represented as
185    
186    $$e([a]_1, [b]_2) = e([a \cdot b]_1, [1]_2)$$
187    
188    by applying this to our case we can see that:
189    
190    $$e([\tau]_1, [p]_2) = e([\tau \cdot p]_1, [1]_2) = e([\tau']_1, [1]_2)$$
191
1924. Check if the new SRS follows the powers of tau structure:
193
194    $$e([\tau'^i]_1, [\tau']_2) \stackrel{?}{=} e([\tau'^{i+1}]_1, [1]_2) ~~ \forall ~i \in [1, n-1]$$
195    $$e([\tau']_1, [\tau'^j]_2) \stackrel{?}{=} e([1]_1, [\tau'^{j+1}]_2) ~~ \forall ~i \in [1, m-1]$$
196    
197    Which, again, by the bilinarity property, we can see that
198    
199    $$e([\tau'^i]_1, [\tau']_2) = e([\tau'^{i+1}]_1, [1]_2)$$
200    
201    is enforcing that $\tau'^i \cdot \tau'^1 = \tau'^{i+1}$.
202    
203    And the same for
204    
205    $$e([\tau']_1, [\tau'^j]_2) = e([1]_1, [\tau'^{j+1}]_2)$$
206    
207    which checks that $\tau'^1 \cdot \tau'^j = \tau'^{j+1}$.
208    
209    With this check, we're ensuring that each power of tau of the SRS is consistent with the previous one.
210
211
212<br><br>
213The complete verification function would look like
214
215```python
216def verify(prev_srs, new_srs, proof):
217    # 1. check that elements of the newSRS are valid points
218    for i in range(0, len(new_srs[0])-1):
219        assert new_srs[0][i] != None
220        assert new_srs[0][i] != e.E1(0)
221	assert new_srs[0][i] in e.E1
222    for i in range(0, len(new_srs[1])-1):
223        assert new_srs[1][i] != None
224        assert new_srs[1][i] != e.E1(0)
225	assert new_srs[1][i] in e.E2
226
227    # 2. check proof.G1PTau == newSRS.G1Powers[1]
228    assert proof[0] == new_srs[0][1]
229
230    # 3. check newSRS.G1s[1] (g₁^τ'), is correctly related to prev_srs.G1s[1] (g₁^τ)
231	#   e([τ]₁, [p]₂) == e([τ']₁, [1]₂)
232    assert e.pair(prev_srs[0][1], proof[1]) == e.pair(new_srs[0][1], e.G2)
233
234    # 4. check newSRS following the powers of tau structure
235    # i) e([τ'ⁱ]₁, [τ']₂) == e([τ'ⁱ⁺¹]₁, [1]₂), for i ∈ [1, n−1]
236    for i in range(0, len(new_srs[0])-1):
237        assert e.pair(new_srs[0][i], new_srs[1][1]) == e.pair(new_srs[0][i+1], e.G2)
238
239    # ii) e([τ']₁, [τ'ʲ]₂) == e([1]₁, [τ'ʲ⁺¹]₂), for j ∈ [1, m−1]
240    for i in range(0, len(new_srs[1])-1):
241        assert e.pair(new_srs[0][1], new_srs[1][i]) == e.pair(e.G1, new_srs[1][i+1])
242```
243
244
245### Full flow
246Now that we have the three methods (*compute_contribution, generate_proof, verify*), it's a matter of using them.
247
248First let's add a couple of helpers to our code:
249```python
250# here we import the BLS12-381 pairing machinery
251load("bls12-381.sage") # file from https://github.com/arnaucube/math/blob/master/bls12-381.sage
252e = Pairing()
253
254# this method generates a SRS filled by the generator points of G1 & G2
255def new_empty_SRS(nG1, nG2):
256    g1s = [None] * nG1
257    g2s = [None] * nG2
258    for i in range(0, nG1):
259        g1s[i] = e.G1
260    for i in range(0, nG2):
261        g2s[i] = e.G2
262
263    return [g1s, g2s]
264```
265
266Let's do the flow:
267```python
268# generate a fake previous-SRS
269(prev_srs) = new_empty_SRS(5, 3)
270
271# set a random value to be used for our tau
272random = 12345 # this would be a random value
273tau = e.F1(random)
274
275# compute our contribution, from the previous SRS and our tau
276new_srs = compute_contribution(tau, prev_srs)
277
278# generate a proof of correct computation of our contribution
279proof = generate_proof(tau, prev_srs, new_srs)
280
281# verify the proof for the given prev_srs and the new_srs
282verify(prev_srs, new_srs, proof)
283```
284
285## Conclusions
286
287As we've seen, we can prove and verify the correct computation of the new SRS with few operations.
288
289From here the next thing would be to implement the [interaction with the Sequencer](https://github.com/ethereum/kzg-ceremony-specs/blob/master/apiSpec/sequencerApi.yml), in order to authenticate the participant, fetch the previous SRS, and send the new SRS and proof.
290
291You can find the Sage example that we've been using [here](https://github.com/arnaucube/math/blob/master/powersoftau.sage), and a full Go implementation here: https://github.com/arnaucube/eth-kzg-ceremony-alt (which uses [Kilic's BLS12-381 implementation](https://github.com/kilic/bls12-381), and includes also the interaction with the Sequencer and a CLI).
292There is also the EF's rust implementation [small-powers-of-tau](https://github.com/crate-crypto/small-powers-of-tau) which has been audited. The same logic can be implemented in the language of your choice.
293<br><br>
294
295<a href="https://github.com/arnaucube/eth-kzg-ceremony-alt" target="_blank" title="https://github.com/arnaucube/eth-kzg-ceremony-alt">
296<img src="img/posts/powersoftau/kzg-ceremony-screenshot.png" style="width:100%;" />
297<span style="font-size:80%; color:gray;font-style:italic;">Screenshot of the eth-kzg-ceremony-alt CLI after contributing to the testnet ceremony.</a>
298</a>
299
300
301Another interesting piece is the *randomness generation*. In our example, for simplicity, tau was hardcoded in the code, but in the real world case we would use some source of randomness to generate our secret value. Here you can get [as creative as you can](https://www.youtube.com/watch?v=I4cDAqeEmpU), and probably we will see some cool approaches for the Ethereum-KZG-Ceremony.
302
303This ceremony output is quite important, as it will be used in many applications once available. It will be used in the Ethereum protocol for the KZG Commitments on EIP-4844, but also on many other applications (some of them unrelated to Ethereum!). For example, any (up to the degree upperbound) Plonk-KZG deployment could reuse this ceremony to avoid needing to compute their own.
304So it's important to gather a notable amount of participants in the ceremony, and probably participate to it by yourself! (as if you're contributing you know that at least there has been one honest contribution (you)).
305
306You can find more info on the Ethereum's KZG Ceremony here: https://ceremony.ethereum.org (which includes also a nice contributor webapp to participate from the browser).
307