# Powers of Tau - Notes

### References

BGM17 - https://eprint.iacr.org/2017/1050.pdf
KMSV21 (Snark Ceremonies) - https://eprint.iacr.org/2021/219.pdf
GKMMM18 - https://eprint.iacr.org/2018/280.pdf

## Rationale

These notes provide an overview for how a trusted setup ceremony works and enlists the simplifications that one can employ for non-Groth16 trusted setups. The Ignition ceremony also employs these simplifications, however since it was for a large setup, it also included a chunking mechanism.

****
There are many different variants of the powers of tau ceremony. The most popular being the Groth16 variant from the BGM17 paper. Fortunately, papers have been written since BGM17 which significantly simplify the powers of tau ceremony.

If the setup is for a non-Groth16 powers of tau ceremony, further simplifications can be applied and even moreso in terms of code complexity for small ceremonies. To list a few simplifications:

- No need to hash the protocol view, which implies that instead of storing each participants SRS forever, you only need to store 2 group elements
- No need for a hash to group implementation due to simpler proofs of knowledge
- For small ceremonies (< $2^{18})$, one can simply send the whole SRS to each participant instead of sending chunks of it.

> The first two point is still employed in most powers of tau implementations I have seen.

Although it is suggested to make your own implementation, rarely does anyone do this. In part, I believe it is due to some of the complexities that large BGM17 ceremonies have, lack of a clear specification to do so and also in part due to the additional effort needed versus downloading a binary.

To the above point, I observed that most implementations in the wild are forks of older code with the setup size changed or the group changed. The plumo ceremony adds optimistic pipelining, this is not needed for small ceremonies however.

# High level overview


The diagram above shows what is happening at a very high level in a powers of tau ceremony.

- Each participant has a private key or a secret scalar that they wish to mix into the powers of tau ceremony.
- When it is the participants turn to contribute, they will receive the current powers of tau and if they are honest, they will update it with their secret scalar as specified, producing a valid update proof.

The arrows in the diagram illustrate a participant passing an update proof plus the new powers of tau to the next participant.

### Coordinator

The above diagram is quite problematic, if you look deeper.
- First of all, how does the current participant know who to send the update proof and the transformed powers of tau to? We want participants to join arbitrarily.
- Secondly, a malicious participant could launch a denial of service attack on the next participant, if they knew who they were, with the goal of censoring honest participants.
- Lastly, the update proofs need to be saved, this is what we use to verify the integrity of the ceremony after the fact and allow attestations. A dishonest party could simply decide to throw their valid proof away, making all update proofs that came after them invalid.

The solution is to introduce a coordinator. We trust the coordinator to be the middle-man between participants, save the update proofs and co-ordinate the queue of participants.

> **Important**: The coordinator is able to throw away your contribution. It is not enough to attest to being a part of the ceremony, one must also check that their contribution was also included. I am of the opinion that there should be two attestations, one to claim that you did indeed contribute and another to claim that you checked that your contribution was included in the final SRS.

>When was the last time you saw a trusted setup attestation and decided to verify it was included in the SRS :eyes:

### Verifier

In practice, the job of the coordinator is split further. The coordinator now only co-ordinates participants. We add another actor called a verifier whose sole job is to verify that when a participant makes an update to the SRS and submits an update proof, the participant followed the protocol and made a valid update.

The verifier signals to the coordinator that everything is correct and the coordinator takes the updated SRS and sends it to the next participant.

# Implementer notes

## Notation

**Bilinear groups**

A pairing is a non-degenerate bilinear map $e : \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ . $\mathbb{G}_1$ and $\mathbb{G}_2$ are distinct subgroups of prime order $r$ and $\mathbb{G}_T$ is a multiplicative subgroup also of prime order $r$ of a finite field extension. We denote the generators of each respective group as $g_1, g_2,g_T$ such that $e(g_1,g_2) = g_T$

We denote $\mathbb{G^*}_1,\mathbb{G^*}_2$ as the non-zero (additive notation) or non-identity elements of $\mathbb{G}_1, \mathbb{G}_2$

**Scalar multiplication**

For $a \in F_r$, we denote $a \cdot g_1 = [a]_1$ and $a \cdot g_2 = [a]_2$

## Structured Reference String - Nomenclature

*Common Reference String*

A common reference string(CRS) is a binary string which is common between the prover and verifier in a proving system. This string does not need to have structure.

*Uniform Reference String*

A uniform reference string(URS) is a type of CRS that was generated such that there is no immediate structure to it; exploitable trapdoor. An example of this are the group elements needed in a pedersen hash. There is a trapdoor, but it is not exploitable unless one knows how to break the discrete logarithm.

*Structured Reference String*

A Structured Reference String(SRS) is a Common Reference String(CRS) with structure embedded into it. Depending on the proving system, the structure needed will vary. For example, the SRS needed for Groth16 according to BGM17 differs from the SRS needed for PLONK. In fact, if one uses a powers of tau ceremony for Groth16 to generate a SRS for PLONK, each contributor will do atleast three times the work needed, moreover they will generate more structure than is needed. The latter point may cause complications in the future.

> To be clear, we are not referring to the extra work one does in phase 2 for Groth16, there is extra work needed in phase 1!

The SRS's known so far have trapdoors which _can_ be exploitable if particular information used to generate the structure is known. This seems to be an inherent property of SRS's.

## Structured Reference String - Definition

We want to compute the structured reference string needed for KZG:

$$SRS_n = \{[\tau^0]_1, [\tau^1]_1, [\tau^2]_1 ,... [\tau^{n-1}]_1, [\tau^0]_2,[\tau^1]_2 \}$$

Compactly written:

$$SRS_n = \{\{[\tau^i]_1\}_{0...n-1}, \{{[\tau^i]_2}\}_{0...1}\}$$

*Read: For an SRS of size n, we want to compute n $G_1$ elements and 2 $G_2$ elements.
The n $G_1$ elements are increasing powers of a scalar tau starting from zero to n-1; The 2 $G_2$ elements follow the same structure except n is 2*

**Note:** [This polynomial commitment scheme](https://eprint.iacr.org/2020/081.pdf) has a variant which require 3 $\mathbb{G}_2$ elements. Once the ceremony is setup, we would not be able to support it. So its important to ensure we only want to support the KZG polynomial commitment scheme.

## Structured Reference String - Ceremony

A trusted setup ceremony can be described using four stages; initialisation, contribution, finalisation, verification.

**Initialisation**

Here we decide what the default SRS will be. The SRS that one starts with can be $\{[1]_1, [1]_1, [1]_1 ,... [1]_1, [1]_2,[1]_2\}$ or it could be the SRS from a previous ceremony. The default SRS does not need to be secure, however using a previous SRS increases the amount of trust one has in the final SRS because a malicious actor(s) now needs to have known the secret information from the previous ceremony _and_ the ceremony about to start.

> It is not the responsibility of _this_ ceremony to check/verify the previous ceremony, someone deciding how much trust they want to place on the security of the final SRS, will need to do this themselves.

**Contribution**

This is the stage where each participant is able to update the SRS. If it is the first participant, they will update the default SRS. For all other participants, they will update the SRS from the previous participant.

Each participant must compute an update proof, if this proof is invalid or missing. The coordinator will simply throw away the accompanying SRS and the next participant in the queue will be given the previous SRS.

Here a malicious group of participants could attempt to make launch a denial of service attack, by making invalid proof and holding up the queue for honest participants. The most common way to thwart this is to manually add participants to the queue after KYC or requiring them to join a social media group like a telegram group chat. This of course doesn't scale.

Another way is to add an authorisation layer, this means that each participant must now authorise themselves via Github or through some other social media site's API before they are granted access to the queue.

> We only need a single honest participant here, so one could do a mixture of both methods. First KYC trusted participants and then allow anyone to participate through an authorisation layer.

**Finalisation**

Suppose you are the final participant in the queue. There will be nomore updates to the SRS. A dishonest party would pick a secret value such that the final SRS is biased. They may, for example, try to ensure that the bottom two bits of each group element is zero or they may try and produce a group element to which they know the discrete log.

We therefore specify that the last participant will be a random beacon. The random beacon is essentially an algorithm that can produce unpredictable and public randomness. We use this so that the final SRS is as uniform as possible. In practice, we use the block hash of a future block on some well known blockchain.

> Perfectly random beacons are hard.

> Snark ceremonies show that the random beacon is not needed, we only require that the last participant cannot bias the SRS enough to have any advantage. It is to my belief, that this is a better model as there is no guarantee that miners for example will not try to bias the SRS once they know what block will be used.

**Verification**

Verification is completed concurrently in the contribution phase. After each contribution, a verifier checks that the previous SRS was updated correctly by checking the update proof and that the SRS has the correct structure.

## Outline

In the rest of the document, we will outline the algorithms used in the trusted setup ceremony. Note, that these algorithms are self contained. Meaning one can implement tests for each one without knowing how the ceremony works exactly.

## Algorithm : Shared Secret Relation

$$R_{ss} = \{ ([\tau]_1, w = [a_0]_2,[a_1]_2,..,[a_n]_2) | \tau =\prod_{i=0}^{n} a_i\}$$

Informally: given a scalar $\tau \in F_r$, we want to show that it can be decomposed into a product of scalars $(a_0,a_1,..,a_n)$ without revealing what the decomposition is or what $\tau$ is.

Lets outline how the prover will prove this:

- First the prover will commit to the running product of $(a_0,a_1,..,a_n)$ $D = ([1]_1,[a_0]_1, [a_0a_1]_1, ...,[a_0a_1a_2...a_n]_1)$
- Observe, that adjacent elements in $D$ differ multiplicatively by a single $a_i$ element. If we can show this for each adjacent element, then it is clear that the last element must contain all of the previous $a_i$ elements.

To check each adjacent element does indeed differ by the multiplication of an $a_i$, we can use a pairings check.

Lets show an example with $D_1$ and $D_2$:

$$e(D_2, [1]_2) == e(D_1,[a_1]_2)$$

$$\rightarrow e([a_0a_1]_1, [1]_2) == e([a_0],[a_1]_2)$$

In general:

$$e(D_{i+1}, [1]_2) = e(D_i, w_i)$$

This requires $2n-2$ pairings which is expensive, in the appendix 1, we show a way to reduce this cost with a random variable.

**Note**

- In addition to providing the witness, the prover may also need to provide the new accumulated point, if the shared secret is being made by many different users. Indeed this is case for the trusted ceremony. We will see that the running product is collection of degree-1 elements in each SRS.
- **MUST** check that $[a_i]_2$ is not zero, and correspondingly that $[\tau]_1$ is non-zero

## Algorithm : Proof of knowledge of discrete logarithm

A proof of knowledge is needed so that any protocol which uses the SRS can also prove knowledge soundness.

Most implementations contain a more complex proof of knowledge(PoK) which is both non-malleable and zero knowledge. This is the case for Snark Ceremonies and BGM17. Moreover, BGM17 also required hashing the protocol view, which was subsequently shown to not be needed in Snark Ceremonies, although many powers of tau still do this.

GKMMM18 proved that although one still needs a proof of knowledge, it does not need to be non-malleable or zero knowledge for universal SNARKs.

> It has not been proven for Groth16, however it has been said to be possible.

The idea for this simpler proof of knowledge is that if you can update $[\tau]_1$ to $[\tau \cdot x]_1$ and you are able to produce $[x]_2$, then the knowledge of exponent assumption, implies that you know the scalar $x$. Interestingly, previous proofs of knowledge implicitly followed a similar logic, except $[\tau]_1$ was some point generated by calling a random oracle.

**Importantly**: This means that for the proof of knowledge, we need only provide $[x]_2$ and update the SRS correctly. Moreover, since this is needed for the shared secret relation, the proof of knowledge is implied. Meaning, we do not need to explicitly check for it using a pairing.

## Algorithm : Incremental powers of tau check

We want to check that the SRS is going up in increasing powers of tau and that there are $n$ $\mathbb{G}_1$ elements and 2 $\mathbb{G}_2$ elements.

$$SRS_n = \{[\tau^0]_1, [\tau^1]_1, [\tau^2]_1 ,... [\tau^{n-1}]_1, [\tau^0]_2,[\tau^1]_2 \}$$

We can check the first condition by using the pairing equation:

$$e([\tau^{i+1}], [\tau^0]_2) == e([\tau^i], [\tau^1]_2) \text{ for i = 0...n-2}$$

This requires $2(n-1)$ pairings. Appendix 1 shows how to reduce this to 2 pairings and 2 size $n$ multi exponentiations.

The second condition can be checked by counting the group elements.

## Toy Example

*Below is a toy example to show how one uses the algorithms above*

Lets assume we have three SRS's (The first is the default SRS):

$$SRS_{n,0} = \{[a^0]_1, [a^1]_1, [a^2]_1 ,... [a^{n-1}]_1, [a^0]_2,[a^1]_2 \}$$

$$SRS_{n,1} = \{[(a\cdot b)^0]_1, [(a \cdot b)^1]_1, [(a \cdot b)^2]_1 ,... [(a \cdot b)^{n-1}]_1, [(a \cdot b)^0]_2,[(a \cdot b)^1]_2 \}$$

$$SRS_{n,2} = \{[(a\cdot b \cdot c)^0]_1, [(a \cdot b \cdot c)^1]_1, [(a \cdot b \cdot c)^2]_1 ,... [(a \cdot b \cdot c)^{n-1}]_1, [(a \cdot b \cdot c)^0]_2,[(a \cdot b \cdot c)^1]_2 \}$$

**Shared secret relation**

We want to check that $SRS_{n,2}$ was formed by multiplying $SRS_{n,1}$ by some secret scalar and $SRS_{n,1}$ was formed by multiplying $SRS_{n,0}$ by some secret scalar.

$$SRS_{n,0} \rightarrow^b SRS_{n,1} \rightarrow^c SRS_{n,2}$$

Observe that this is the same as checking that $SRS_{n,2}$ contains the secrets from the previous SRS's.

$$a \rightarrow^b (a \cdot b) \rightarrow^c (a \cdot b \cdot c)$$

Reducing this to the shared secret relation:

- Take the degree-1 element from each SRS, $D = ([a^1]_1, [(a \cdot b)^1]_1,[(a \cdot b \cdot c)^1]_1)$. This will be the running product in the relation.
- Assume that after each update, the participant outputted a witness for the shared secret relation. This witness serves as a proof of update. Hence, we should have, $w = ([r]_2, [k]_2)$

**Proof of knowledge**

Read section on proof of knowledge. This is implied from the shared secret relation.

**Incremental powers of tau check**

The reduction to this check is quite straightforward. However, we can make a few observations:

- We only need to check $SRS_{n,2}$ after the fact. If the last SRS passes the check, then the previous SRS's must have passed the check too.

> During the ceremony, before a new player contributes on top of an SRS, it should be checked, so that participants are building on top of valid SRS's.

- This means that, we do not need to store every SRS once the ceremony is over, just the last one. In fact, we only ever need to store the previous and the latest SRS during the ceremony.

> Previous ceremonies stored each SRS because their proof of knowledge required each player to hash the protocol view. We do not have this proof of knowledge, so we do not need to.

## Suggestions

- Since for the shared secret relation, one must output a commitment to their contribution $[x]_2$. It is easy to observe when two contributors use the same randomness. This is effectively the same as those two contributors colluding. This could happen due to bad randomness, we should reject these contributions.
- Points can be uncompressed for small powers of tau. A $2^{16}$ setup requires less than 8MB for the SRS for bls12-381.
- Although points are uncompressed, one should still check that the points are in the specified group and have the correct order.
- Zero checks should be eagerly performed. After a participant updates the SRS, they should check if any of the points are zero. The verifier will also check this and reject that contribution if so.

## Appendix 1 - Incremental powers of tau check (Batching)

The idea is that instead of checking:

$$e([\tau^{i+1}], [\tau^0]_2) == e([\tau^i], [\tau^1]_2) \text{ for i = 0...n-2}$$

We can instead sample uniformly random scalars $z_0,...,z_{n-2} \in F_r$, then instead check that:

$$\sum_{i=0}^{n-2} e([z_i\cdot \tau^{i+1}], [\tau^0]_2) == \sum_{i=0}^{n-2} e([z_i \cdot \tau^i], [\tau^1]_2)$$

Which is the same as:

$$ e([\sum_{i=0}^{n-2}z_i\cdot \tau^{i+1}], [\tau^0]_2) == e([\sum_{i=0}^{n-2}z_i \cdot \tau^i], [\tau^1]_2)$$

The above notation is concise however it may also be jarring, so using a small example:

Assume we have the following list: $$A = ([1]_1,[s]_1, [s^2]_1,[s^3]_1, [s^4]_1, [s^5]_1)$$

From $A$, we compute two shifted variants of $A$:
$$A_{\text{shiftL}} = ([1]_1, [s]_1, [s^2]_1,[s^3]_1, [s^4]_1)$$
$$A_{\text{shiftR}} = ([s]_1, [s^2]_1,[s^3]_1, [s^4]_1, [s^5]_1)$$

Inspecting, it is clear that if $A$ passes the incremental powers of tau check, then the i'th element in $A_{\text{shiftL}}$ multiplied by $s$ equals $A_{\text{shiftR}}$. ie

$$A_{\text{shiftL}}[i] \cdot s = A_{\text{shiftR}}[i] \text{ for all i}$$

If we sample uniformly random variables $z_i \in F_r$, then with probability over $z_i$, the following also holds:

$$A_{\text{shiftL}}[i] \cdot z_i \cdot s = A_{\text{shiftR}}[i] \cdot z_i \text{ for all i}$$

$$ \rightarrow \sum_i A_{\text{shiftL}}[i] \cdot z_i \cdot s = \sum_i A_{\text{shiftR}}[i] \cdot z_i$$

$$ \rightarrow s \cdot \sum_i A_{\text{shiftL}}[i] \cdot z_i = \sum_i A_{\text{shiftR}}[i] \cdot z_i$$

$$\text{let L} = \sum_i A_{\text{shiftL}}[i] \cdot z_i, \text{let R} = \sum_i A_{\text{shiftR}}[i] \cdot z_i$$

$$ \rightarrow s \cdot L = R$$

The equality can be checked as follows:

$$e(L,[s]_2) = e(R, [1]_2)$$

This is the same as the equation we initially showed.

## Appendix 2: Non-Malleable ZK Proof of knowledge of discrete logarithm (Groth16)

> This is the PoK which can be used with Groth16, given that there is no proof for the simpler version.
### Notation

**Random Oracle**

We will use $\mathbb{RO}_K(A,B) = T$ to denote a call to a random oracle which takes as input $A,B$ and returns $T$. The type of $T$ is $K$.

Example1. $\mathbb{RO}_{\mathbb{G}_1}(A) = P$ means that we have a random oracle which takes as input $A$ and returns $P \in \mathbb{G}_1$. The type of $A$ should be clarified by the protocol in which the random oracle is being used.

For group elements, we may redundantly write $\mathbb{RO}_{\mathbb{G}_1}(A) = [p]_1$ to mean the same thing.

### Protocol

$$R_{dl} = \{(\phi = ([x]_1, [y]_2), w) | x = y = w\}$$

Informally, given an element in $\mathbb{G}_1$ and $\mathbb{G}_2$, we want to prove that they have the same discrete logarithm, ie both points were multiplied by the same scalar.

**Prover**

1. $[r]_1 = \mathbb{RO}_{\mathbb{G}_1}(\phi)$
2. $\pi = [rw]_1$

**Verifier**

1. $[r] _1= \mathbb{RO}_{\mathbb{G}_1}(\phi)$
2. Check the following conditions:
- $e([x],[1]_2) == e([1]_1,[y])_2$
- $e(\pi, [1]_2) == e([r]_1, [y]_2)$

**Notes:**

- The random oracle function **MUST** return a group element $[r]_1$ such that $r$ is unknown. In other words, it is a hash to group algorithm.
- The proof for completeness is quite straightforward from the fact that $e$ is a bilinear map. For soundness, one can check the Snark ceremonies paper.