Parameter Generation

Background

Bitzec’s zero-knowledge proofs rely on a set of public parameters which allow users to construct and verify private transactions. Due to cryptographic limitations, these parameters must be generated in a setup phase: some random numbers are sampled (which we refer to as the “toxic waste”) which are then used to construct the parameters.

After the setup phase, the toxic waste must be destroyed to prevent counterfeiting of Bitzec. (Note that user privacy is still protected even if the setup phase fails or the toxic waste is not destroyed.)

Multi-party Computation Ceremonies

In order to ensure the toxic waste does not come into existence, our team designed multi-party computation (MPC) protocols which allow multiple independent parties to collaboratively construct the parameters. These protocols have the property that, in order to compromise the final parameters, all of the participants would have to be compromised or dishonest.

To this date, Bitzec has created two distinct sets of public parameters. The first ceremony happened in October 2016 just before the launch of BitzecSprout. The second was generated in 2018 anticipating the Sapling network upgrade later that year.

In the Sprout MPC, all participants needed to commit to their share of the “toxic waste” in advance in order to protect against adaptive attacks. This meant that all of the participants needed to be available for the entire duration of the protocol, and nobody could abort without causing the entire protocol to abort. Participants needed to maintain custody of their hardware throughout the process, so this meant the ceremony could not scale beyond a handful of people.

The Sapling MPC allows participants to join the protocol, do their part and leave immediately. This allows the ceremony to scale to a large number of participants and take place over a longer period of time. It also decreases the surface area of attack for participants and avoids the need for expensive synchronization.

 

Sapling

For Bitzec’s second set of public parameters, there are two distinct phases referred to as Powers of Tau and Sapling MPC.

Powers of Tau

In November 2017, The Bitcoin Core announced Powers of Tau, a multi-party computation ceremony which reached its conclusion in early 2018. In this ceremony, a total of 87 participants took turns performing computations to be used in the generation of new zk-SNARK parameters. The ceremony was coordinated on a public mailing list where participants submitted their attestations upon completion.

Sapling MPC

The BitzecCompany hosted the MPC for constructing Sapling’s final zk-SNARK parameters. We announced the ceremony in May 2018 and accepted contributions through early August 2018. In all, this ceremony accepted over 90 contributions and after completion of the Sapling MPC, the final parameters were included in the 2.0.0 release of Bitzec.

 

Sprout

Bitzec’s first set of public parameters were generated in a ceremony that took place on October 21-23, 2016. The ceremony involved six participants, each in their own location, each with their own hardware:

  1. Andrew Miller
  2. Peter Van Valkenburgh
  3. John Dobbertin (pseudonym)
  4. Zooko Wilcox
  5. Derek Hinch
  6. Peter Todd

During the ceremony, Sean Bowe (one of the engineers of the MPC software) coordinated the execution of the ceremony.

In addition, Morgen Peck (a journalist writing for IEEE Spectrum), Nat Kramer (a videographer) and Daniel Cooper (a production assistant) were invited to Zooko’s station to document and observe the process.

Video Explainer

Watch our video explainer of the ceremony.

Radiolab Podcast: The Ceremony

Listen to the Radiolab podcast report of the ceremony.

Overview of Ceremony Design

All of the participants have a similar role: their machines randomly sample a “shard” of the toxic waste and use this shard to perform computations. Participants must communicate with each other during the ceremony, but none of the communication is considered sensitive, and all of it is available in a public transcript.

Participants do not directly communicate with each other. There is a coordinator server which acts as a bridge between the participants, and performs some deterministic initialization steps and other expensive computations. It is not a privileged part of the ceremony; all of the computations performed by the coordinator can be verified by the public using the same public transcript mentioned before. The coordinator server records procotol communication to the public transcript, which is used later to verify protocol execution.

The participants themselves are responsible for obtaining secure hardware specifically for the ceremony, maintaining custody of that hardware until their role is finished, and destroying their shard of the toxic waste by powering their machine down. At their discretion, participants can physically destroy or forensically examine the hardware afterward.

Hardware used in the Ceremony

In order to reduce the surface area of attack, each participant isolated their toxic waste shard from the network by possessing two machines that are air gapped from each other: a network node which communicates with the coordinator server, and a compute node which has the toxic waste shard in memory. This creates an air gap that we chose to bridge using append-only DVDs. The DVDs additionally serve as an auditable record of protocol communication.

Participants were encouraged to obtain their compute node from a random computer store. They were also instructed to remove the wireless networking adapters (wifi, bluetooth) and hard disk drives from the machine before powering them on.

The hardware runs open source software we have developed. In particular, we reproducibly generated boot ISOs for the participants to boot their machines with.

Preparations for the Ceremony

Dress rehearsals

In preparation for the ceremony, multiple dress rehearsals took place over the previous month.

First dress rehearsal: This involved Andrew Miller, Peter Van Valkenburgh and Sean Bowe. The DVD drive used by Andrew’s compute node had a fault which was unrecoverable. The software was modified to make recovery from drive failure possible.

Second dress rehearsal: This also involved Andrew Miller, Peter Van Valkenburgh and Sean Bowe. (Nat Kramer also documented the process at Sean Bowe’s station.) There was a networking issue on Andrew’s network node. Sean Bowe was able to recover from this by having Andrew manually splice the contents of a DVD and providing it to the coordinator server. Andrew’s network node re-established a connection with the coordinator server and the ceremony continued to completion. The software was modified to better recover from network disruptions.

Third dress rehearsal: This involved Zooko Wilcox, Derek Hinch, and Andrew Miller. (Morgen Peck also observed the process over video chat.) Zooko’s compute node could not properly dismount the boot disc due to a race condition during boot. The software was modified for Zooko’s compute node to make this race condition less likely. The ceremony continued, and nearly completed, but due to a strict access control policy, it was not possible to recover from a drive failure that happened to occur in the last stage, also on Zooko’s compute node. The software was modified so that participants could manually intervene if access control policies disrupted the ceremony.

Final changes and preparations (October 21, 2016)

Participants were given a set of instructions which directed them to purchase hardware, to boot the software on this hardware and perform built-in diagnostics that tested the DVD drive and ensured the ceremony could safely begin.

After the disclosure of a Linux privilege escalation vulnerability (Dirty COW, CVE-2016-5195) the compute and network node software was updated with the recently released Linux kernel 4.4.26, and the final boot ISOs were provided to the participants.

The code used for the ceremony was tagged as finalmpc2.

The boot ISOs provided to participants:

  • Network node ISO (SHA256: 375550be4c64ebc68a9306421bb71ad3556bc73f156a231503084f923900f4cb)
  • Compute node ISO (SHA256: 5f43aa1244a01b3cf9da4abeadde9e34b954a873565fc56b58c10780f3ce0e4c)

These ISOs can be reproducibly generated using a script we have provided. The timestamps will differ, but the contents of the binaries should not. A tool such as diffoscope can be used to compare them.

In the original coordinator software, the first participant to connect is also the first to begin acting and the first to complete their role in the ceremony. Scheduling conflicts meant that some participants would need to finish earlier on October 23. The coordinator software was modified so that the order of participants could be changed before the ceremony began, in the event that participants connected in the wrong order. (After the protocol begins, the ordering cannot be changed.)

Ceremony (October 22-23, 2016)

On the morning of October 22, Sean Bowe initialized the coordinator server. The server was a 128-core EC2 instance. Participants were instructed to begin their roles: the network node would connect to the coordinator server and prompt the user to enter a commitment that the compute nodes would produce, binding their participation to the transcript.

Due to a misunderstanding, John Dobbertin reinitialized their network node, resupplying the commitment to the coordinator. This is not encouraged because the coordinator software uses randomly generated peer IDs to distinguish users. This was manually corrected before the protocol began.

Zooko Wilcox did not have an Ethernet connection available at his location, and so required wireless communication with the coordinator server. However, the network node boot image did not contain any wireless infrastructure, so Zooko was given the network node software to compile and run on his personal laptop. (This does not disturb our threat model, because the network node is already considered compromised merely by connecting to the Internet. The network node boot image is only given to participants to make the process simpler and reduce the risk of failures.)

The final ordering of the participants in the ceremony was:

  1. Andrew Miller
  2. Peter Van Valkenburgh
  3. John Dobbertin (pseudonym)
  4. Zooko Wilcox
  5. Derek Hinch
  6. Peter Todd

Commitment phase

Each participant’s compute node will randomly generate their toxic waste shard. The user is asked to supply additional entropy to augment Linux’s random number generator. After the toxic waste shard is generated, a special kind of “public key” is constructed which is used to verify the protocol evaluation and bind the participant to the ceremony.

This “public key” is not immediately revealed. All of the participants manually transcribe the public key’s hash (the “commitment”) from the compute node to the network node. The coordinator server will enter all of the commitments into the public transcript.

Stage 1

During these stages, a “round robin protocol” takes place: the coordinator (deterministically) initializes the initial state, and each participant performs a transformation on this state which is passed to the next participant.

Stage 1 (also sometimes referred to as “powers of tau”) will have each participant receive a “disc A” on their network node. The network node burns this disc A and transfers it to the compute node. The compute node reads this disc and, before deserializing and processing its contents, displays a hash of the disc that the participant is asked to record.

The compute node then proceeds to perform an expensive transformation of the state that takes over half an hour. Afterward, the compute node will print a hash of the disc it is about to burn (“disc B”), which the participant is also asked to record. The disc that is burned is transferred to the network node, which sends the contents to the coordinator.

In total, it takes roughly an hour for each participant to perform their role in this stage. During this stage only, each participant sends their “public key” and a NIZK used for later validation.

FFT

After stage 1, the coordinator takes the result of stage 1 and performs an expensive computation that takes over an hour to complete. This computation is deterministic. The result is used to initialize stage 2.

Stage 2

Stage 2 began on the evening of October 22. Stage 2 behaves similarly to stage 1, except that the computation takes much longer. Each participant received a disc “C” and produced a disc “D” in a similar fashion as before. In total, it takes about two hours for each participant to complete their role in the second stage.

Stage 3

Stage 3 began in the morning on October 23. This stage behaves similarly to the previous stages, except that the computation is inexpensive. Each participant receives a disc “E” and produces a disc “F”. In total, it takes about 40 minutes for each participant to complete their role in this stage.

After the participant has completed their part in stage 3, their role in the protocol is finished. They are instructed to turn their compute node off at this point, to destroy their toxic waste shard. They are instructed to keep their DVDs safe for archival and analysis.

Ceremony Completion

The ceremony was completed in the evening of October 23, approximately 27 hours after the protocol began. After the ceremony completed, the verifier was ran on the transcript, producing the Bitzecpublic parameters. The following is the output of the transcript verifier.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
Number of players: 6
Player 1 commitment: 2iQQBkf7k4K9aigJm4uHHufaSB8rXLLaRTMmTerK7dx6RCqNc9
Player 2 commitment: 6yV3Ji7zuVWVCQEfkhQ6Vfv51t5VfQHQVaLDGH6zkeunKmohr
Player 3 commitment: 6mGvvMFMKJNwKFmHXUwcCQMk7iu92bSqhtRabX3nkdnadEKte
Player 4 commitment: VGyYjzYc39em9TithdWFySSUwATMgcXcLtQ7ias7i4SkNdS4G
Player 5 commitment: 2YrFsjMadFukhdkQpn8oFgET2EQd9WnDW3AzYqNc3kELU45p7t
Player 6 commitment: 2B2HXuZAKayqgJpxojuUU9RN78pTv2gLvEDmEbWRBWEJ6Z1LS
Player 1 hash of disk A: 2oX6hBNiQxiZYZgDbSkgk3mhBACXmoGCfdhfZrSquNztZuZaqt
Player 1 hash of disk B: 2T2ceUDomnrCVCtJw2SwtYAeHCfnAhM9HBdzVkq6BdZ59nST5m
Player 2 hash of disk A: 2axdkGL6QzngjvY9jRBX5AqhSokukji8eQuYUfJwhp7sxcXvPr
Player 2 hash of disk B: 2RymyNbAWaBVDuzW4m1iKA72MsmZFnwMhNvqxxXDwugLTa62wc
Player 3 hash of disk A: YAQs9PiruKxfTwMTdTUHkYgt9QRvjpkF95cJRbNP8WLqPqjLW
Player 3 hash of disk B: 2omA7bsepmmxeygQzNBbodhdXTyhuK1i2KCRH9esB3azunwZPn
Player 4 hash of disk A: EDEtkk1PUhu4BQbTzx5yPSSpyqB6kV9g39p6sNt1ERGRG3APQ
Player 4 hash of disk B: 2fvnbP22XWHVD1DstGQ5FsHNaBLiZQg4MBVKmWf7sWCYg5A9L7
Player 5 hash of disk A: 2oQgZxPLAL2f8xkvm71RqwKK6dCFQSrazESXci32M2LZeG7nxe
Player 5 hash of disk B: UBjr6UU8oJ4ZzpsTU3vRHmzZmuN7TjX3eLsmdRhw4dW6dEbvH
Player 6 hash of disk A: rnMAJE2bxMbCT6yRvufD2ww17kmP9qaKnipxrvZTWXe27d6GW
Player 6 hash of disk B: 27Em5cp6QSGVsJsAcvZLW7CoMkKv5Ybi3LAGPPeGwqCF7Diex
Player 1 hash of disk C: 29PLu7dtT9BjJhtoAzxpSxvrp4tE15xjJufL1ANHGwkwieyxMo
Player 1 hash of disk D: 2YVAELKtHdufKRPTzT5ZpHFgxrcro6JmBKkYz4GEQqcXbQdViM
Player 2 hash of disk C: 2qSQhJvQLjmXfQWHKMCR5EukSWU9BQ3KwdPSqkPUCSRzwmxowM
Player 2 hash of disk D: 2uAxySzeptYhEowKuBRGituPnc1U4BU1GMuL4Hfbyvtgq7x4Qn
Player 3 hash of disk C: 2DZ3pnkZcTMfAa28KfJpD5fQbnkQZZG5mFnFqvHHUDXJquSJAX
Player 3 hash of disk D: 2tfcauKUDBirJFSo8jbyEenLfHULThsQjVdN8FY3hJGn3dC2JP
Player 4 hash of disk C: 2gH6XJ8BeA5yXZL95ThSp9ucicwAoevaDK6xNBck9QUxXF1gEE
Player 4 hash of disk D: VFXKdDoYrA58evyJUrvkocGCHVvYF2h8HVLmuEtFkDfZY6EHk
Player 5 hash of disk C: 2RvKUp94tXE5b1qhyLpGPTXeWpS7FdNDvCG5MJPmZiccNuRYcw
Player 5 hash of disk D: ApPFWMqGBMemE3sTAuMRnwbmGonsPoXYC4r45HBMdmiRWLXqH
Player 6 hash of disk C: 2wGGYBXaeQdbLHvViArnLkGRERhztVk5qZmreSKwxEcFjMBNMC
Player 6 hash of disk D: 2g3rMWwyCL5wgKYHiVHR6EdnBc9Q5dPc1RW6tWwvwyJnx6AKq9
Player 1 hash of disk E: 2Zbrd1XhYKvZqeNcGQPVrusx1rRjxaQjFfzWcn64wCfTnEGTMg
Player 1 hash of disk F: 27ZzVxLTxXpjeTo86sdQ9kKU83UfNHLyGPuQ4CCV9ZRJ4g84jC
Player 2 hash of disk E: YWKCeTeYiKUNnd4aJBYcd8ZwBxscibmtDa4pxbz52fpYX2H9S
Player 2 hash of disk F: 2o1wWJHYzCirDmijHmnGFQ4pSfoYTkEKdPinag22eYonKf8EGC
Player 3 hash of disk E: 2jquuLB8omrtWV1GnXvghRN1A3MWMouyBSwEKD5fCMwk5SvktP
Player 3 hash of disk F: 2jrEGwnSyX9oX8UUGYhpEiPaLmGmrbhfFtcciXt3o5N7nPh63A
Player 4 hash of disk E: AY1Vm8dDSxDdpNhac8Mr7GkS18vomvXaoreg1mVcXyApmgbu8
Player 4 hash of disk F: 2RVi4vpjXtzD6gPLsFDSVrtX545HbVnNBhjAJVUTXpG22oLDD5
Player 5 hash of disk E: CFEWpN9STr4iVM8NLGcSUyoaEDr94FEp7VWR9HhQQYhuwUu7f
Player 5 hash of disk F: 2vohW4tyybTEZyf3ZarX5R1CgsUehQfwASExZQ86EWNd8ByC6a
Player 6 hash of disk E: chZdF1yRVDTsaD14KdaFv6N7e8ZPkMnxr9CpXkzq8JzonhLPx
Player 6 hash of disk F: 2HjRqGyKjPxDSbhP8KgyYtKpWCwrGt3v4ZEUZHsZpJHbJ2V9QL

(The hashes are base58check encoded to make manual transcription easier for the participants during the ceremony.)

Bitzec’s public parameters consist of two “keys”:

  • Proving key (SHA256: 8bc20a7f013b2b58970cddd2e7ea028975c88ae7ceb9259a5344a16bc2c0eef7)
  • Verifying key (SHA256: 4bd498dae0aacfd8e98dc306338d017d9c08dd0918ead18172bd0aec2fc5df82)

The full output of the coordinator log can be found here.

Public verification of the Ceremony

The general public is invited to improve confidence in the ceremony in a variety of ways:

  1. The protocol used during the ceremony was designed specifically for Bitzec. The design is specified alongside a cryptographic proof in our MPC whitepaper. It should be reviewed by the public for mistakes.
  2. The protocol used during the ceremony was implemented by Sean Bowe and Ariel Gabizon. It is available open source. It should be reviewed for bugs that may have impacted the ceremony.
  3. The software that participants ran on their machines was generated using a script which the public can also use to reproduce the ISOs. People can use tools such as diffoscope to analyze the differences.
  4. The public transcript (SHA256: 7da0c07a4bec04fbe4ae99ebd62d4ce7e1710b1f7a1f317345b0a48feec984d3) is used to verify the protocol’s evaluation and produce the public parameters. It should be verified using our verification tool, which will produce the same hashes of discs, commitments and the public parameters that are used in Bitzec.
  5. The participants of the protocol each disclosed a commitment that binds them to the ceremony, and hashes of the files burned to their discs. These should be checked against the output of the verifier tool.
  6. The R1CS constraint system used by the protocol should be compared against what is actually used in Bitzec.