a16z: Details the feasibility of trusted setup ceremonies on decentralized chains

Although the Trusted Setup Ceremony has always challenged the crypto community, it is definitely the most exciting part of the crypto community. The goal of the ceremony is to generate reliable cryptographic keys used to secure crypto wallets, blockchain protocols or zero-knowledge proof systems. These procedures are the root of trust in the security of the project, so it is critical to ensure flawless operation and execution of trusted setup ceremonies.

At present, there are various forms of trusted setup ceremony for blockchain projects, including but not limited to blowtorches, radioactive dust, and airplanes, etc. All of these forms have one thing in common, that is, they all rely on a centralized coordination device. This article will show how to decentralize the process by replacing the centralized coordinator with smart contracts, and at the same time we will open-source a library that allows anyone to run on Ethereum known by crypto practitioners as Kate-Zaverucha-Goldberg ( KZG) or “powers-of-tau” ritual.

Our decentralized approach has limitations, but it still works. Due to current on-chain data limitations, the size of the encryption parameters must remain no larger than 64 KB. But there is no limit to the number of participants, and anyone can submit a contribution at any time. Applications of these short parameters include small zero-knowledge SNARKs, data availability sampling, and Verkle trees, among others.

The History and Mechanisms of the Credible Setting Ceremony

In a typical trusted setup ceremony, a group of participants will collaborate to generate a set of cryptographic parameters. Each party uses locally generated encrypted information to generate data that helps create these parameters. Proper settings can ensure that encrypted information will not be leaked, encrypted information can only be used as specified in the protocol, and these encrypted information will be completely destroyed at the end of the ceremony. The entire process can be considered secure as long as at least one party in the ceremony maintains honesty and destroys the encrypted information (after the ceremony). (provided the code is free of errors, of course)

Some of the most prominent rituals were launched by Zcash, a privacy-oriented blockchain project. Participants in these ceremonies generate public parameters designed to allow Zcash users to construct and verify private cryptographic transactions. Six participants held the first Zcash ceremony Sprout in 2016. Two years later, crypto researcher Ariel Gabizon, now chief scientist at Aztec, discovered a devastating error in the design of the ceremony, inherited from a fundamental research paper. The vulnerability could allow attackers to create unlimited Zcash coins without being detected. The Zcash team kept the breach a secret for seven months until the system upgrade Sapling, whose ceremony involved 90 participants, resolved the issue. While an attack based on a security breach would not affect the privacy of user transactions, the prospect of infinite forgery undermines the security premise of Zcash. (Theoretically, it is impossible to know if an attack has occurred.)

Another notable example of a trusted setup is the perpetual “tau-power-of-tau” ceremony, designed primarily for Semaphore, a privacy-preserving technology for anonymous signaling on Ethereum. The setup uses a BN254 elliptic curve and has so far had 71 participants. Other notable projects have since used this setup to run their own rituals on top, including Tornado.Cash, Hermez Network, and Loopring. Aztec held a similar ceremony on the BLS12_381 elliptic curve, with 176 participants participating in zkSync, a “layer 2” Ethereum scaling solution that uses zero-knowledge aggregation. Filecoin, a decentralized data storage protocol, held a ceremony with 19 and 33 participants in Phase 1 and Phase 2, respectively, forking the original repository. Celo, a layer 1 blockchain, also held a ceremony for their lightweight client, Plumo.

Permanent ceremonies have no restrictions on the number of participants. In other words, anyone can participate in any level of security without trusting others to run a trusted setup ceremony. A trusted actor ensures the safety of all outcome parameters; the chain is as strong as its strongest link. As the name suggests, perpetual rituals can be performed in perpetuity, just like the premise of the original tau power ritual. That said, projects often decide on specific start and end times for rituals so they can embed the generated parameters into the protocol without worrying about constantly updating them.

Ethereum plans to run a smaller trusted setup ceremony for the upcoming ProtoDankSharding and DankSharding upgrades. These two upgrades will increase the amount of data the Ethereum chain provides to clients for storage. This data is valid for the recommended 30 to 60 days. The ceremony is under active development and is scheduled to run for around six weeks early next year. (See kzg-ceremony-specs for more details) And it’s shaping up to be the largest blockchain trusted setup ceremony to date.

Paranoia is a “virtue,” especially when it comes to believable setting rituals. If a machine’s hardware or software is compromised, the security of the secrets it generates can be compromised. Sneaky side-channel attacks that leak secrets are also hard to rule out. For example, a cell phone can monitor the operation of a computer by recording the sound waves of CPU vibrations. In practice, due to the difficulty of eliminating all possible side-channel attacks — including those that haven’t been discovered or disclosed — there have even been proposals to fly machines into space to perform rituals there.

Currently, the script for serious ritual participants is usually as follows. Buy a new machine (uncontaminated hardware). Risk isolation by removing all network cards (to prevent local secrets from being leaked). Run the machine in a remote undisclosed location in a Faraday cage (to frustrate potential snoopers). Set a large amount of entropy and hard-copy data for pseudo-random encrypted message generators, such as random input or seeds of video files (to make encrypted messages difficult to crack). Finally, destroy encrypted information – and any traces of encrypted information – by burning everything to ashes.

Coordinate trusted setup ceremonies

All trusted setup ceremonies rely on a centralized coordinator. Coordinators are individuals or private servers or other entities who are delegated to register and order participants, act as relays by forwarding information from the previous participant to the next, and keep a centralized log of all communications for auditing purposes. The coordinator is usually also responsible for permanently providing the logs to the public, although it must be acknowledged that such a centralized system is prone to information loss due to poor management or some impersonal factors.

Ironically, when decentralization is a core tenet of the crypto ethos, crypto projects must rely on centralized trusted setup rituals. Therefore, we decided to demonstrate the feasibility of holding a small ceremony for perpetual powers-of-tau directly on the Ethereum blockchain. The setup is completely decentralized, permissionless, censorship resistant, and secure as long as any one participant is honest. At current prices, attending the ceremony costs only $7 to $400, depending on the size of the desired outcome parameter (in this case, between 8 and 1024 tau).

a16z: Discuss in detail the feasibility of trusted setup ceremonies on decentralized chains

As of now, we recommend against using the code for anything other than experimental purposes. It would be greatly appreciated if anyone who finds any problem with the code reports it to us. We’d love to collect feedback and reviews on our approach.

Learn about the KZG or “powers-of-tau” ceremony

Let’s explore one of the most popular trusted setups, known as KZG, or the “powers-of-tau” ceremony. Thanks to Ethereum co-founder Vitalik Buterin, whose blog post on trusted setups informed our thinking in this section. This setup generates an encoding of powers-of-tau, so named because “tau” happens to be the variable used to represent the secret generated by the participant:

a16z: Discuss in detail the feasibility of trusted setup ceremonies on decentralized chains

For some applications (e.g. Groth16, the popular zkSNARK proof scheme designed by Jens Groth in 2016), the first stage of setup is followed by a second stage, the multi-party computation (MPC) ceremony, to generate parameters for a specific SNARK circuit. However, our work only focuses on the first phase. The first stage – generating powers of tau – can already be used as a fundamental building block for general-purpose SNARKs such as PLONK and SONIC, as well as other cryptographic applications such as KZG commitments, Verkle trees, and data availability sampling. (DAS). In general, generic SNARK parameters should be very large so that they can support large and useful circuits. Circuits with more gates are generally more useful because they can capture large computations; the power of tau roughly corresponds to the number of gates in the circuit. Therefore, a typical setup size is |pp|= ~40 GB, capable of supporting a circuit of ~2 28 Gas. Putting such large parameters on-chain is not feasible given Ethereum’s current constraints, but smaller trusted setup ceremonies useful for small SNARK circuits, Verkle trees or DAS can be run on-chain.

The Ethereum Foundation plans to run several smaller ceremonies for powers-of-tau with sizes ranging from 200 KB to 1.5 MB. While larger rituals may look better, in reality, bigger isn’t always better, considering that larger parameters can create more useful SNARK circuits. Certain applications (like DAS) specifically require a smaller application! [The reason is very technical, but if you’re curious, it’s because of settings with powers of n (in G) 1) Only KZG commitments to polynomials of degree ≤ n are allowed, which is important for ensuring that polynomials under KZG commitments can be derived from any n Reconstruction is critical in this assessment. This property supports data availability sampling: each time a random evaluation of the polynomial is successfully obtained (sampled), it guarantees that the polynomial can be completely reconstructed with probability t/n. If you want to learn more about DAS, check out this article by Buterin on the Ethereum Research Forum.

We designed a smart contract that can be deployed on the Ethereum blockchain to run a trusted setup ceremony. The contract stores public parameters entirely on-chain and participates through user transaction collection.

New participants first read these parameters:

a16z: Discuss in detail the feasibility of trusted setup ceremonies on decentralized chains

Then sample the random key τ’ and compute the updated parameters:

a16z: Discuss in detail the feasibility of trusted setup ceremonies on decentralized chains

and publish them on-chain with attached proving three things:

  • Knowledge of discrete logarithms: Participants know τ’. (Prove that the latest contribution to the Trusted Setup Ceremony builds on the work of all previous participants.
  • pp is well-formed 1: These elements do encode incremental powers. (Good form to verify the contribution of new participants to the ceremony.
  • Update not erased: τ’ ≠ 0. (Defense against attackers who try to disrupt the system by deleting all participants’ past work.

The smart contract verifies the proof, and if it is correct, it updates the public parameters it stores. You can find more details about the math and the reasoning behind it in the repository.

Calculate Gas Cost

The main challenge in running setup on-chain is making the trusted setup ceremony as efficient as possible. Ideally, submitting a donation will cost no more than $50. (Large projects might be able to subsidize gas for contributors, in which case it’s easier to imagine hundreds of participants spending $100 each). Below, we provide more details on the most expensive part of the setup. Lower gas cost will reduce contribution cost and allow longer parameters to be built (more tau power and bigger SNARK circuits)!

Our setup is for elliptic curve BN254 (also known as BN256, BN128 and alt_bn128), which supports the following precompiled contracts on Ethereum:

ECADD allows adding two elliptic curve points, i.e. computing [α+β]1 from [α]1 and [β]1: Gas cost 150

ECMULT allows elliptic curve points to be multiplied by scalars, i.e. compute [a*α]1 from a and [α]1: Gas cost 6,000

ECPAIR allows checking the product of elliptic curve pairs, i.e. computing e([α1]1, [β1]2) * … *e([α1]1, [β1]2) = 1, which is equivalent to checking α1*β1+ . .. + αk*βk= 0 : Gas cost 34,000 * k + 45,000

If Ethereum can enable BLS12_381 (as suggested in EIP-2537), our setup contract could easily be used for other curves as well.

Let’s estimate updating the settings to

a16z: Discuss in detail the feasibility of trusted setup ceremonies on decentralized chains

Gas cost to verify the proof. As mentioned above, each participant updates the settings and submits a three-component proof. Components 1 and 3 of the proof – “discrete log knowledge” and “updates are non-erasable” – are very cheap to verify. The challenge is to verify that component 2, “good formability of pp”1”, is on-chain. It requires a large multiscalar multiplication (MSM) and two pairings:

a16z: Discuss in detail the feasibility of trusted setup ceremonies on decentralized chains

where ρ0,…,?n-1 are pseudorandomly sampled scalars. As far as precompiled smart contracts are concerned:

a16z: Discuss in detail the feasibility of trusted setup ceremonies on decentralized chains

Gas cost of storing data. Each participant also stores on-chain updates as call data (68 gas per byte), which takes n*64*68 gas. (A note for those familiar with elliptic curve cryptography: according to our measurements for n = 256, storing the compression points will make decompression dominate the overall cost.

The estimated gas cost is as follows:

a16z: Discuss in detail the feasibility of trusted setup ceremonies on decentralized chains

Of course we are also exploring solutions to reduce gas costs.

Open source library: evm-powers-of-tau

We have open sourced our EVM-based powers-of-tau ceremony at github.com/a16z/evm-powers-of-tau. Using our strategy for rituals is simple and transparent:

  • Deploy storage and verification contracts (contracts/KZG.sol)
  • Participants read ritual parameters from previous transaction invocation data
  • The participant generates a key locally, computes the updated parameters
  • Contributors generate their proofs: pi1, pi2
  • Contributors submit updated parameters to smart contracts deployed on the public blockchain via KZG.potUpdate()
  • The smart contract will verify the validity of the update, recovering in case of malformed submissions
  • Steps 2-5 can be performed permanently by multiple contributors, each step increasing the security of the ceremony
  • Whenever developers are confident in the quantity and quality of submissions, they can query the blockchain for current parameters and use these values ​​as encryption keys.

Our repository uses arkworks-rs to calculate steps 2 and 3 (rust calculations can be found in src/pot_update.rs), but users may want to write their own. The entire end-to-end flow of update submissions can be found in the integration tests in tests/integration_test.rs.

Note that we chose to use calldata to store updated powers-of-tau parameters on-chain because it is orders of magnitude cheaper than storage. An ethers-rs based query for this data can be found in src/query.rs.

Finally, proofs and detailed equations can be found in the technical report at techreport/main.pdf.

future work plan

Before using this trusted setup ceremony in a production environment, we recommend a full review of the mathematical proof and example implementation first.

With implementation, the transaction cost of the update ceremony grows linearly with the size of the setup. For most applications (SNARKs, DAS) we want to set n >= 256, which currently costs $73 per update.

We may be able to achieve sublinear verification cost growth with efficient update computation of STARK proofs and vector commitments to updated values. This structure will also remove the dependency on the Ethereum L1 BN254 precompile, allowing the more popular BLS12-381 curve to be used.

All ritual strategies are weighed and tested iteratively. We consider this structure to be robust and well verifiable and censorship resistant. But again, until more work is done to validate the soundness of our method, a high degree of caution is still required to directly use this scheme mentioned in the paper.

Posted by:CoinYuppie,Reprinted with attribution to:https://coinyuppie.com/a16z-details-the-feasibility-of-trusted-setup-ceremonies-on-decentralized-chains/
Coinyuppie is an open information publishing platform, all information provided is not related to the views and positions of coinyuppie, and does not constitute any investment and financial advice. Users are expected to carefully screen and prevent risks.

Like (0)
Donate Buy me a coffee Buy me a coffee
Previous 2022-09-08 10:25
Next 2022-09-08 10:27

Related articles