A Technical Explanation of the Aleo Setup Ceremony

In this post, we wanted to take the time to explain why the Aleo community’s contributions to our setup ceremony are so valuable. Known as “Powers of Tau”, this Multi Party Computation (MPC) is the technical backbone that provides one of the key security bases of our proof systems. This security is built on cryptography, so be warned that there will be some maths — but any complex notation will be kept to a minimum as we try to explain the deeper ideas involved.

The Aleo setup ceremony currently has more contributions than the previous record, Tornado Cash’s ceremony’s 1114 contributions!

Zero-Knowledge Proofs

Aleo uses zero-knowledge proofs (ZKPs) to achieve privacy and scalability. A native transaction on the Aleo chain is a ZKP. Specifically, Aleo uses a type of ZKP called a zkSNARK (which stands for a zero-knowledge Succinct Non-interactive ARgument of Knowledge). In order to be fully trustless, our zkSNARK must use a random number during the production of a proof.

It’s very important that this number be random; if users could reason their way to the number before the moment it was needed (because it was dictated by logic, rather than randomness), they could forge proofs and compromise security.

People often take randomness for granted because it is supplied by a “trusted third party.” But what if they aren’t trustworthy? Powers of Tau eliminates this uncertainty. Instead of trusting a single party, Aleo’s setup is open to anybody, encouraging multiple, independent contributors. If any one of them is honest, then the number(s) generated is/are guaranteed to be random.

Once the ceremony is done, we can start using the parameters in our proof systems and generate secure proofs. This is a very important milestone in the journey to mainnet.

Commitment Schemes

zkSNARKs require this randomness for several reasons. For example, transactions in zero knowledge proofs require a “commitment scheme,” or a two-phase protocol that allows the system to commit to a chosen value without revealing said value. Although there are various types, our commitment scheme uses a polynomial (a function of x where all powers are whole, positive numbers such as f(x)=x²+x+3) because, if 2 polynomials are different, the chance that they evaluate to the same value is unrealistically low under the right conditions. We explain this polynomial commitment scheme below.

Any cryptographic commitment scheme needs two features. First, the polynomial, which once committed to, must be “locked in” — i.e. the prover or other parties shouldn’t be able to change it, otherwise they could simply change the polynomial to make it seem like their inputs are correct. This is called the binding property. Second, the commitment shouldn’t reveal any information about the polynomial, and no one should be able to use the commitment to find anything out about the polynomial. This is called the hiding property.

Polynomial commitments applied in zkSNARKs virtually guarantee that someone with the right outputs must thus have the right inputs.

Note, then, that it is very important that the polynomial commitment be created in a way that cannot be gamed. In order to do this, the solution requires using randomness. But this again raises a problem: how can we trust that the polynomial was evaluated at a random point? For example, what if the first thing a prover has to do is commit to a polynomial they want to keep secret? The only thing that may be random at this point is the polynomial they created, and if they use that to generate the randomness then they have to show us the polynomial, which is exactly what we were trying to avoid.

In practice, we will have the polynomial to be committed to,

A generic polynomial of degree n

and a curve point, P. The commitment scheme involves finding f(𝜏)P; this will be the commitment. 𝜏 will be an unknown value. So the randomness in practice is evaluating f(x) at an unknown value. How can we find f(𝜏)P without anybody knowing 𝜏?

The solution is the Powers of Tau ceremony.

Before we delve more into the ceremony, there are a couple more ideas that are worth fleshing out.

Discrete Logarithm Assumption

You have probably seen that our blockchains and proof systems often make use of elliptic curves to function. For the purposes of this explanation, the inner workings of these curves is irrelevant, except for one detail explained below.

Let’s say we have a point P on our elliptic curve. We can add the point P to itself and get back 2P. You can see a visual of how we do this below (draw a tangent at P, note the other place it crosses the curve, and then reflect across the x-axis).

Doubling an elliptic curve point

Add P to 2P, and we get 3P. You can see a visual of how we add different points below (draw a line between the two points, note the third position this lines crosses the curve at, and then reflect in the x-axis).

Adding two distinct elliptic curve points, P and Q, together to make R

We can keep adding P to itself to get kP for some k. Now imagine somebody comes to you with some point R which they say is equal to 27P. You would be able to calculate 27P and check that it is equal. But the key thing is that if you received R and wanted to find what P was multiplied by to get there, there would be no easy way to do it. Essentially, you would have to calculate 2P and compare it, and then 3P, and then 4P, and so on.

This is called the Discrete Logarithm Assumption (DLA). It is easy to work out kP from k and P, but finding k from kP is actually phenomenally difficult.

There is one way to make this problem easier. If k can be anywhere between 1 and 100, we can simplify the computation to the problem of finding some k’ between 1 to 10 (but we can only make it smaller once because we can only exploit the symmetry once).

Specifically, if n is the upper bound, we can reduce it to the square root of n. So if you are presented some R=kP where kis somewhere between 1 and 10,000, we can reduce this to a problem where k’ is between 1 and what?

Perhaps you are not convinced by this method of randomness, and it seems like people would be able to work out the value of k. Let’s give an example to demonstrate how untrue that really is.

At Aleo we use the BLS12–377 curve, where k can be anywhere between 1 and p, where we have that

p=8444461749428370424248824938781546531375899335154063827935233455917409239041,

meaning that p’ is about 91893752504881257701523279626832445440, which is about 10³⁸. Now imagine that you can check one million possibilities a second, 10⁶, which is pretty fast. Let’s see how long it will take to check half of the possibilities.

(10³⁸÷2)÷(10⁶)÷(60×60×24×365) ≈ 10²⁴years.

That’s a million, billion, billion years. Bearing in mind that the universe has only existed for 13.8 billion years (10¹⁰), we begin to see that finding k’ becomes, for all intents and purposes, impossible.

A DLA based commitment scheme

Let’s combine the above two ideas, and introduce the Kate (pronounced Kah-tay) commitment scheme.

The prover has a polynomial, f(x)=x²+x+1, that they want to commit to. They can create the elliptic curve point P=(𝜏²+𝜏+1)G. By the DLA discussed above, nobody can work out the value of 𝜏²+𝜏+1 from P; so we have the hiding property. And once the value P has been broadcast, we seemingly have the binding property. It’s a very elegant scheme, and this property is further used in the Marlin proof system (our Universal SNARK).

An interesting thing is that we can create this scenario where the prover will be able to create P=(𝜏²+𝜏+1)G without giving anybody knowledge of 𝜏; they only have to know what G, 𝜏G, and 𝜏²G are.

This is extremely important, because if people knew 𝜏 it would ruin the binding property that we naively thought was guaranteed. Where did we slip in our reasoning?

At a later point in the proof system, we will want the prover to use f(x) to do something, and we can check that they are actually using f(x) via the commitment P. However, if the prover knows 𝜏, they can create another polynomial g(x) and use that. As long as g(𝜏) = f(𝜏), the proof will still be valid, which destroys the security of our proof system.

You see, we thought that by creating P, we were committing to the polynomial f(x). In actuality, we were committing to a polynomial that has a specific value at the point 𝜏. If somebody knew what 𝜏 was, they would be free to use any polynomial g(x) they wished, provided that it had the same value as f(x) at (i.e. g(𝜏) = f(𝜏)). Making such a polynomial g(x) is actually really easy to do if you know 𝜏.

Thus we would need a scenario where people don’t know 𝜏, but do know 𝜏G, and 𝜏²G, 𝜏³G, and so on. This is exactly what the Powers of Tau ceremony is for.

Note: the highest power in the example polynomial we used above, f(x)=x²+x+1, is x². If the highest power was x³⁰, we would have needed to know 𝜏G, and 𝜏²G, …, 𝜏³⁰G. In reality, the highest power of 𝜏 that we expect to have will be around 250 million, so this is what the setup ceremony will go up to.

Interlude: Type of randomness

We have an interesting situation here in terms of randomness that we couldn’t help from commenting on. Under normal scenarios, we might ask for a random number between 1 and 100, and get the answer 50; but once the answer 50 was given, we would not be able to use it again because it would stop being random.

However, notice that 𝜏 is actually a specific number, and it never changes. Yet every time we work out f(𝜏)G, it is actually equivalent to working out the value of f(x) at a random point, because nobody knows 𝜏. Thus we have generated randomness, but for strange reasons, we can keep using it.

Multi Party Computation

Note: we switch from using 𝜏 to using x because it is the more common notation.

Let’s imagine that two people want to generate coefficients for the Kate commitment scheme described above. Person 1 will pick a random x₁, and broadcast x₁G but not x₁ (and remember, nobody can work out x₁ from x₁G due to the DLA). Person 2 then takes x₁G, and adds it to itself x₂ times, yielding x₁x₂G and broadcasts that. Now everybody can see x₁x₂G=xG, but the only way to work out x is if Person 1 or 2 shares their knowledge of xᵢ with the other.

If either Person 1 or 2 is honest, they will delete their xᵢ the moment it is no longer required, thus guaranteeing the security of their protocol.

This is it, this is the core idea of the ceremony; security is guaranteed if a single person in the ceremony is honest. Each participant contributes their shard, xᵢ, and then deletes it the moment they no longer need it. In order to maximise the likelihood of an honest participant, we want to maximise the number of participants.

In order to achieve this, we have made the ceremony open to anybody who wishes to join.

What happens in the ceremony?

Person 1 chooses a random x₁, and broadcasts:

Person 2 takes chooses a random x₂, and broadcasts:

Persons 3 to (n-1): …

Person n chooses a random xₙ, and broadcasts:

At this point we are done, and we define x as:

After doing their part, the participants delete their shards xᵢ. Provided that at least a single one of them did so, everybody will know the powers xᶦG, but nobody will know x (and cannot reasonably find x due to the DLA). The possibility of making x by the participants colluding and sharing their xᵢ with each other is made impossible when a single xᵢ is deleted.

Will they be honest?

If you think about it, it makes very little sense for a bad party to join the ceremony if they want to find x. Let’s say x will be split into k pieces. A bad actor would not learn any of the k required keys if they joined the ceremony (they would learn the extra key k+1 that they created by participating); so why even bother?

It is more probable that any incremental participant is honest, and if we get lots of people in the ceremony, the chance that not a single one of them is honest is low.

Updateable

It is also possible to take the generated parameters and redo the ceremony; i.e. if previously we had k lots of xᵢ from kpeople, we can add another m lots of xᵢ without removing the ones already there. This is not desirable, but if people are worried about the honesty of participants in the future, it remains a possibility.

Why so many ceremonies?

Different proof systems have different requirements depending on how they have used the core idea. Marlin has a universal reference string, meaning that the Powers of Tau produced for it can be used on any circuit built in Marlin. In contrast, Groth16 requires a unique setup ceremony for each type of circuit, and we make use of both of these proof systems to achieve a few different properties in our blockchain.

Moreover, in the ZEXE model that Aleo uses, we use 1-depth proof recursion for additional scalability and functional privacy. All this is a long way of saying that we need to set up several different proof systems, some of which are easier to do than others. As such, we split the setup ceremony into 3 parts.

Please refer to our post here to see a bit more about what each ceremony is for, and if you want to see a few more details about how the ceremony works, check out this post. If you’re feeling really adventurous, why not check out the original Powers of Tau paper!