← Back to all posts Case Study

Implementing Trusted Setup Ceremony for Ethereum’s EIP-4844

Posted by Grzegorz Swirski on Jun 11, 2024

Dencun upgrade went live promising up to 10x cost savings to L2 operators. In the lead up to the upgrade, the Ethereum community performed the largest trusted setup ceremony to date, with over 140k participants. Reilabs contributed the backend and parts of cryptography code to this ceremony.

Two years in the making, EIP-4844—also known as proto-danksharding—is a massive upgrade that has laid the foundations for the future scaling and optimization of Ethereum. In the words of Vitalik Buterin—Ethereum’s co-founder—"scaling ceased to be a "zero-to-one" problem, and became a "one-to-N" problem”.

A major prerequisite for the EIP-4844 upgrade was performing a trusted setup ceremony: a way for Ethereum’s community to ensure the security of the newly proposed extension. The ceremony was a great success, with over 141,000 people contributing. Reilabs is proud to have been part of the journey, having contributed parts of the trusted setup specifications, as well as the backend implementation of the main KZG Summoning Ceremony that was run by the Ethereum Foundation.

The cryptographic primitives and protocol design chosen here will form the basis for further work, such as data availability sampling and full blockchain sharding. Even today, at the beginning of the optimization journey, Scroll predicts that their L2 rollup will offer 10x lower transaction costs thanks to EIP-4844 data blobs.

Blob Storage

At the high-level, EIP-4844 allows transactions to attach big blobs of data cheaply (125 kB today with the goal of up to 16 MB in the future). Access to these blobs is limited for computations on chain. Despite this, the implementation is more than sufficient for rollups to publish their data and verify its correctness on chain far more cheaply than if they relied on calldata.

As part of the implementation, transactions reference blobs in a tamper-proof way; nobody can change the contents of the blob after it has been posted to the blockchain and pretend it’s the original. One way to “commit” to a blob is to simply hash the contents of it, but Ethereum researchers had something better in mind: KZG commitments. Among other benefits, KZG is much friendlier for use within ZK rollups and will also enable data availability sampling (DAS) in the future. With DAS, Ethereum nodes can check only a small sample of data rather than hash the whole blob—something that would become prohibitively expensive once blobs become larger or more numerous.

IMG_9D7D1CB1CC01-1.jpeg

The only problem with KZG is that we needed the trusted setup ceremony. This post explains why.

KZG Polynomial Commitments

This post will only present high-level ideas to build intuition about the KZG’s trusted setup. If you want to dive deeper, we highly recommend:

First, let’s represent our blobs (blocks of data) as polynomials (functions in the shape of \( f(x) = \alpha_0 x^0 + \alpha_1 x^1 + ... + \alpha_n x^n \) ). The easiest way to do it is to use subsequent bytes of the blob as each of the coefficients \(\alpha_i\).

KZG is a “polynomial commitment scheme”. It allows one actor, the prover, to first “commit” to a specific polynomial (a specific sequence of coefficients \(\alpha_i\)) and later prove that evaluations of that polynomial at various points (by substituting \(x\) in the polynomial equation) were done correctly.

The first element of KZG’s “magic” on which we will focus today is how the commitment works. We will ask the prover to evaluate the polynomial at a secret point called \(\tau\) (the Greek letter tau). Nobody knows \(\tau\) , not even the prover, which makes it impossible for the prover to cheat during the later stages of the protocol.

evaluate.png

The natural first question: how can you calculate \(f(x)\) if you don’t know the \(x\)?!

Powers of Tau

Let’s take a quick detour into elliptic curve cryptography. The security of many cryptographic protocols based on elliptic curves hinges on the fact that while multiplication is relatively easy and fast, reversing it is almost impossible.

You can think of an elliptic curve as a set of points on a plane. You can add two points together to obtain another point on the curve, or you can multiply it by a number \(n\) (called a scalar) which is equivalent to adding the same point to itself \(n\) times.

We can take one of the points from the curve (let’s call it a generator \(g\)) and multiply it by a number \(a\) to obtain a new point \(b = a \cdot g\) (where \(g\) is added \(a\) times). This process is relatively fast: by leveraging the same trick that is used for fast exponentiation, we can calculate \(b\) in \(O(log a)\) additions.

Calculating b = 38 * g using only 7 additions.
Calculating b = 38 ⋅ g using only 7 additions.

The reverse is a different story. If we know \(g\) and \(b\), there are no clever tricks to find \(a\). You need to try every single possible value of \(a\) which on a classical computer, in all practical applications, would take thousands of years. This difficulty is referred to as an “elliptic curve discrete logarithm problem”, or ECDLP.

But let’s get back to our polynomial evaluation at a the secret value \(\tau\).

Let’s consider elliptic curve points as arguments to our polynomial. We can leverage the above property to hide \(\tau\) by multiplying it with the generator \(g\). In order to use KZG, we’ll seed our protocol with a publicly known sequence of numbers (called “powers of tau”): \(\tau^0g, \tau^1g, \tau^2g, ..., \tau^ng\). Even though the sequence is public, and the \(g\) is public, if we were handed such a sequence, we still wouldn’t know what \(\tau\) was. And while we cannot quite calculate \(f(\tau)\) , we can very easily calculate \(f(\tau) \cdot g\) by multiplying each polynomial coefficient with a corresponding tau element:

\(\alpha_0\tau^0g + \alpha_1\tau^1g + ... + \alpha_n\tau^ng = (\alpha_0\tau^0 + \alpha_1\tau^1 + ... + \alpha_n\tau^n) \cdot g = f(\tau) \cdot g\)

The result is obviously obfuscated by \(g\), but thanks to the rest of the KZG protocol, the verifying party will still be able to check if the prover did everything correctly.

Multi-Party Computation

Eagle-eyed readers will notice that the security of our protocol depends on being handed powers of tau in a way where nobody knows the tau! We don’t trust anyone—we’re blockchain cryptographers after all!—so we’ll use a simple trick and invite a lot of participants to perform a secure multi-party computation.

The process of obtaining powers of tau (sometimes called trusted setup or Structured Reference String - SRS) is called a “trusted setup ceremony”. Participants take turns and each one of them will bring a part of the secret. As long as at least one of the participants destroys their secret (or simply doesn’t share it with anybody else), the full secret remains safe.

mpc sequencer.png

How do we implement that? It’s actually very easy!

We initialize the powers of tau to a series of \(g, g, g, ..., g\) . The first person selects their \(r_1\) at random—usually using multiple sources of entropy—and the new Powers of Tau become \(r_1^0g, r_1^1g, ..., r_1^ng\). The second person selects their random number \(r_2\) in the same way and Powers of Tau become \(r_2^0r_1^0g, r_2^1r_1^1g, ..., r_2^nr_1^ng\). Each subsequent person multiplies each element of the sequence by powers of their secret \(r_i\).

Notice that the properties of elliptic curves, and the generator element \(g\), keep everyone’s secret secure.

After each turn \(i\), the secret is then \(\tau = r_i \cdot ... \cdot r_2 \cdot r_1\) and nobody can know \(\tau\) since it’s hidden by \(g\).

Trusted Setup Ceremony

We’re happy to report that we’ve had over 141,000 people contributing as part of the Ethereum trusted setup ceremony, often from competing organizations! We can be certain that not all of them colluded together.

Reilabs was responsible for implementing both the cryptography for the ceremony, as well as a mechanism to allow participants to fairly “take turns” to make their contributions.

Preventing Attacks on the KZG Ceremony

To ensure correctness of the ceremony, we need to make sure that contributions are performed correctly.

The most obvious problem is that we cannot allow users to multiply the series by \(0\). If we did, the whole thing becomes zero, forever.

A less obvious problem is that users could cheat and multiply by something that is not a sequence of powers of the same number \(x\) (i.e. not \(x^0, x^1, ...x^n\)). Luckily, we can verify this using pairings.

Elliptic Curve Pairings

We need a quick detour into Elliptic Curve Pairings to explain how the ceremony ensures that each contribution properly multiplies the Powers of Tau by:

$$r^0, r^1, ..., r^n$$

Certain elliptic curves come equipped with a special function called a “pairing”. Let’s consider two elliptic curve groups \(G_1\), \(G_2\), their generators: \(g_1\), \(g_2\) and an output group \(G_{\tau}\) with a generator \(g_{\tau}\). A pairing is a function such that:

$$e(a \cdot g_1, b \cdot g_2) = g_{\tau}^{a \cdot b}$$

Notice that normally we couldn’t perform a multiplication like that without knowing \(a\) or \(b\). Pairings let us do it, but only once – the result is in a different group and cannot be used as an argument to another pairing.

Our Powers of Tau setup will actually contain an additional element \(\tau \cdot g_2\) and each contribution \(x\) will submit three things:

  1. update \(x^0 \tau^0 g_1, x^1 \tau^1 g_1, x^2 \tau^2 g_1, ..., x^n \tau^n g_1\), (as we have described above)
  2. update \(x \tau g_2\)
  3. provide \(x g_1\) for validation

For each element of the contribution (or simply, for each \(n\)), check if the next element behaves as expected:

\(e((x \tau)^ng_1, x \tau g_2) = e(x \tau^{n+1}g_1, g_2)\)

This check is made much faster in practice by considering all \(n\) terms at once by evaluating a random linear combination of those terms.

Similarly, users could try to cheat by ignoring all previous contributions and submitting only their powers of \(x\) multiplied by \(g_1\). To prevent it, we verify the following pairing: \(e(x g_1, \tau g_2) = e(g_1, x \tau g_2)\).

The other class of attacks are attempts to deny the service to honest participants. To counter the possibility of a single actor controlling the contributions, Reilabs implemented anti-sybil checks: participants needed to prove ownership of an Ethereum wallet address with a sufficient history of operations, or sign in with GitHub.

Each unique wallet or GitHub account was allowed to contribute only once, and at all times we were able to maintain a big “lobby” of eligible users waiting to make their contributions.

Summary

This post has explained the motivation behind performing the huge trusted setup ceremony for Ethereum’s EIP-4844. Everyone who wanted to ensure that the \(\tau\) used for Ethereum’s blobs remained secret could do so by contributing their own piece of that secret. As long as at least one participant—of which we had over one hundred forty one thousand—didn’t collude with the others, the secret is safe.

                   Beautiful trusted setup ceremony frontend created by zkParty.
Beautiful trusted setup ceremony frontend created by zkParty.

Reilabs is really proud of the opportunity we had to contribute this important piece to the Ethereum Foundation’s ceremony. The work was sponsored by Tools for Humanity, contributor to the Worldcoin protocol.

We’re looking forward to future of Ethereum scalability and can’t wait to see how people leverage EIP-4844 blobs in the wild.


Hope you have enjoyed this post. If you'd like to stay up to date and receive emails when new content is published, subscribe here!

Continue Reading

Introducing Hints in Cairo programming language

Reilabs introduces Cairo Hints, an extension to Cairo language that makes STARK programs easier to implement and cheaper to execute. Hints enable developers to supplement their programs with data that is difficult to obtain in ZK circuits, allowing them to solve new classes of problems with Cairo.

Zero Knowledge Systems You Can Trust

The EVM’s ability to run computations on-chain has a major weakness: the cost of running code is often too great. Given a lot of the use-cases for this kind of public computation involve more interesting operations, we’ve seen a rapid rise in the use of systems that aim to alleviate those costs.

Designing and developing upgradable contracts

One of the most foundational concepts on the blockchain is immutability. While this is one of its greatest strengths, it is also a weakness—being able to fix bugs is crucial to building reliable software, but being able to do this is a challenge on chain.