a16z: Discuss in detail the feasibility of trusted setting ceremony on the decentralized chain
Original compilation: Amber, Foresight News
Original compilation: Amber, Foresight News
Although the Trusted Setup Ceremony has always challenged the crypto community, it is definitely the part that excites the crypto community the most. The goal of the ceremony is to generate reliable cryptographic keys that can be used to secure cryptographic wallets, blockchain protocols, or zero-knowledge proof systems. These procedures are the root of trust for the project's security, so it is critical to ensure impeccable operations and perform trusted setup ceremonies.
At present, there are various forms of credible setting ceremony for blockchain projects, including but not limited to blowtorches, radioactive dust, and airplanes, etc., and 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, while at the same time we will open source a library that allows anyone to run on Ethereum. KZG) or "powers-of-tau" ritual.
Our decentralized approach has limitations, but it's still useful. Due to current on-chain data limits, the size of encrypted parameters must remain no larger than 64 KB. But there is no upper limit to the number of participants, and anyone can contribute at any time. Applications of these short parameters include small zero-knowledge SNARKs, data availability sampling, and Verkle trees, among others.
History and Mechanisms of Credible Setup Rituals
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 the data that helps create these parameters. Appropriate settings can ensure that encrypted information will not be leaked, encrypted information can only be used in accordance with the agreement, and these encrypted information will be completely destroyed at the end of the ceremony. As long as at least one party in the ceremony is honest and destroys the encrypted message (after the ceremony), the entire process can be considered secure. (Of course, the premise is that the code is error-free)
Some of the most prominent ceremonies 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 encrypted transactions. Six participants hosted the first Zcash ceremony Sprout in 2016. Two years later, encryption researcher Ariel Gabizon, now chief scientist at Aztec, discovered a devastating error in the ritual's design, inherited from a fundamental research paper. The vulnerability could have enabled an attacker to create infinite Zcash coins without being detected. The Zcash team kept the bug a secret for seven months until a system upgrade, Sapling, whose ceremony involved 90 participants, fixed the issue. While attacks based on security breaches would not affect the privacy of user transactions, the prospect of infinite forgery undermines Zcash's security premise. (Theoretically, it's impossible to know if an attack occurred.)
Another notable example of a trusted setup is the permanent "tau-power-of-tau" ceremony designed primarily for Semaphore, a privacy-preserving technology used for anonymous signaling on Ethereum. The setup uses the BN254 elliptic curve and has 71 participants so far. Other notable projects later used this setup to run their own ceremonies on top, including Tornado.Cash, the Hermez network, and Loopring. Aztec held a similar ceremony on the BLS12_381 elliptic curve with 176 participants for zkSync, a "layer two" Ethereum scaling solution that uses zero-knowledge rollups. Filecoin, a decentralized data storage protocol, forked the original repository in a ceremony with 19 and 33 participants in Phases 1 and 2, respectively. Celo, a layer 1 blockchain, also hosted a ceremony for their lightweight client, Plumo.
Permanent ceremonies have no limit on the number of participants. In other words, anyone can participate with any level of security, rather than trusting others to run trusted setup ceremonies. A trusted actor ensures the security of all outcome parameters; a chain is as strong as its strongest link. As the name suggests, a permanent ritual can be performed forever, just like the premise of the original tau power ritual. That said, projects often decide on specific start and end times for ceremonies 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 that the Ethereum chain provides to clients for storage. This data is valid for a recommended 30 to 60 days. The ceremony is in 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 setup 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 give away secrets are also difficult to rule out. For example, a cell phone can monitor the operation of a computer by recording the sound waves of the CPU vibrating. In practice, because it is so difficult to eliminate all possible side-channel attacks—including those that have not been discovered or disclosed—it has even been proposed to fly the machine into space to perform the ceremony there.
Currently, the script for rigorous ritual participants usually follows. Buy a new machine (untainted hardware). Risk isolation by removing all network cards (to prevent local secrets from leaking). Run the machine at a remote, undisclosed location in a Faraday cage (to thwart would-be 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, the encrypted information - and any trace of it - is destroyed by burning everything to ashes.
Coordinate Trusted Setup Ceremony
All trusted setup ceremonies rely on a centralized coordinator. Coordinators are individuals or private servers or other entities that are entrusted with registering and ordering participants, acting as relays by forwarding information from previous participants to the next, and keeping a centralized log of all communications for auditing purposes. The coordinator is usually also responsible for permanently providing logs to the public, but it must be admitted that such a centralized system is prone to information loss due to poor management or some non-human factors.
Ironically, when decentralization is a core tenet of crypto ethos, crypto projects must rely on centralized trusted setup rituals. We therefore decided to demonstrate the feasibility of holding a small ceremony for perpetual powers-of-tau directly on the Ethereum blockchain. The setup is fully 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).
As of now, we advise against using the code for any purpose other than experimental purposes. If anyone finds any issues with the code to report it to us, we would appreciate it. We'd love to gather 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 the KZG, or "powers-of-tau" ritual. Thanks to Ethereum co-founder Vitalik Buterin, whose blog post on trusted setups informed our thinking in this section. This setting generates a powers-of-tau encoding, so named because "tau" happens to be the variable used to represent the participant-generated secret:
For some applications (e.g. Groth16, the popular zkSNARK proof scheme devised by Jens Groth in 2016), the first phase of setup is followed by a second phase, the multi-party computation (MPC) ceremony, to generate parameters for a specific SNARK circuit. However, our work only focuses on the first stage. 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, general-purpose SNARK parameters should be very large so that they can support large and useful circuits. Circuits containing more gates are generally more useful because they can capture large computations; the number of powers of tau roughly corresponds to the number of gates in the circuit. Thus, a typical setup size is |pp|= ~40 GB, capable of supporting ~2 circuits of 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 could be run on-chain.
The Ethereum Foundation plans to run several smaller ceremonies for powers-of-tau ranging in size from 200 KB to 1.5 MB. While larger ceremonies may look better, considering that larger parameters can create more useful SNARK circuits, in reality, bigger is not always better. Certain applications (like DAS) specifically require a smaller application! [The reason is very technical, but if you're curious, it's because settings with powers of n (in G)1) only allow KZG commitments for polynomials of degree ≤ n, which is essential for ensuring that polynomials under KZG commitments can be drawn from any n Reconstruction is critical in this assessment. This property supports data-availability sampling: every 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 post by Buterin on the Ethereum Research Forum.
We designed a smart contract that can be deployed on the Ethereum blockchain to run trusted setup ceremonies. The contract stores public parameters entirely on-chain and collects participation through transactions from users.
New participants first read these parameters:
Then sample the random key τ' and compute the updated parameters:
And publish them on the chain, and attach proof of three things:
Knowledge of discrete logarithms: Participants know τ'. (Proof that the latest contribution to the credible setup ceremony builds on the work of all previous participants.
pp is well-formed1: these elements do encode incremental powers. (Verified good form of new participant's contribution to the ceremony.
Updates are not erased: τ' ≠ 0. (Defense against attackers who try to compromise 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 of running setup on-chain is making the trusted setup ceremony as efficient as possible. Ideally, the fee for submitting a contribution should not exceed $50. (Large projects may be able to subsidize gas for contributors, in which case hundreds of participants spending $100 each is easier to imagine). Below, we provide more details on the most expensive parts of the setup. Lower Gas costs will reduce contribution costs and allow building longer parameters (more tau power and larger SNARK circuits)!
Our setup works on 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 pairs of elliptic curves, i.e. computing e([α1]1, [β1]2) * ... *e([α1]1, [β1]2) = 1, equivalent to checking α1*β1+ . .. + αk*βk= 0 : Gas cost 34,000 * k + 45,000
If Ethereum is able to enable BLS12_381 (as proposed in EIP-2537), our setup contract could easily be used for other curves as well.
Let's estimate update the setting to
Gas cost to verify the proof. As mentioned above, each participant updates the settings and submits a proof with three components. 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:
where ρ0,...,𝝆n-1 are pseudo-randomly sampled scalars. In terms of pre-compiled smart contracts, one needs:
Gas cost for storing data. Each participant also stores on-chain updates as call data (68 gas per byte), accounting for n * 64 * 68 gas. (One note for those familiar with elliptic curve cryptography: from our measurements for n = 256, storing the compression points would make decompression dominate the overall cost.
The estimated Gas cost is as follows:
Of course, we are still exploring solutions to reduce Gas costs.
Open source library: evm-powers-of-tau
We have open-sourced the EVM-based powers-of-tau ritual at github.com/a16z/evm-powers-of-tau. Rituals are simple and transparent using our strategy:
Deploy storage and verification contract (Contracts/KZG.sol)
Participants read ceremony parameters from previous transaction call data
Participant generates a key locally, computes 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, reverting in case of a malformed commit
Multiple contributors can perpetuate steps 2-5, each of which increases 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 those 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 an update submission can be found in the integration tests at 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 storing. An ethers-rs based query for this data can be found in src/query.rs.
Finally, the proof 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 first doing a thorough review of the mathematical proof and example implementation.
As implemented, the transaction cost of the update ceremony grows linearly with the set size. For most applications (SNARKs, DAS), we want to set n >= 256, which currently costs $73 per update.
We may be able to achieve sub-linear verification cost growth through efficiently updated STARK proofs of computation and vector commitments to updated values. This structure will also remove the dependency on the Ethereum L1 BN254 precompilation, allowing the more popular BLS12-381 curve to be used.
Original link
