Restarting the Semaphore random value generation process

March 22, 2020

In early March 2020, I announced a series of computational steps that would create a random value which we would use to start phase 2 of the multi-party setup ceremony for the Semaphore zk-SNARK circuit (read this blog post to learn more about it). Unfortunately, we did not do a thorough enough job with committing to key parameters and details about the process we would perform, which could raise doubts about its trustworthiness and security. As such, we have decided to re-run the random value generation and apply the lessons learned over the past week to ensure that we follow a water-tight process.

Timeline of events

March 4 2020: I posted in the README file of the appliedzkp/semaphore-phase2-setup repository that we would use response 0022 from Perpetual Powers of Tau as the starting point for the ceremony.

March 5 2020: I updated the README to state that we would use challenge 0023 (derived from 0022) as the starting point.

March 6 2020: we announced that we would use the hash of block #9619000 of the Ethereum mainnet as the VDF input

March 7 2020: we started the VDF with the value 0x35ffdfc6198abafc21076172b0fb01c4eaf3d15d11a74e6df287ba2694e70b08

March 10 2020:** I updated the README to state that we would use challenge 0024.

March 11 2020: we completed the VDF and began computing 242 iterations of the SHA256 hash function on the value efed6b7c6e565e539d2d08cf77e73b0bc07657090ffb477da1d1eea7d7852592

Why this is problematic

The problem with the above timeline of events is that the change made on March 10 reduced the security of the random number generation. If we were malicious and extremely computationally resourceful, such that we had secretly completed the VDF and SHA256 iterations earlier than announced, we could have made that change because we favoured the random value generated using challenge 0024 over the random value generated using 0023.

Instead, I should have stuck to the challenge file at the same time that we committed to the block hash we would use as the random number (i.e. on March 6). It is true that adding more contributions to phase 1 of the ceremony increases its security, since it presumes non-collusion of all participants, and the more participants there are, the harder for all of them to collude. Moreover, the latest participant at the time was Vitalik Buterin, a very prominent figure in the Ethereum ecosystem, and including his contribution would lend more credibility to the process. Yet, announcing a different challenge file while we were computing the random value could raise legitimate questions about its integrity and our intentions.

In addition, the README file we published lacked many details such as the endianness of the block hash, the commit hashes of software we would use, the hash of the Semaphore circuit and its constraints, and technical information about the VDF function.

Finally, we realised that we did not have to perform iterated SHA256 hashes on the output of the VDF, even though the team that performed Zcash’s ceremony did this. We decided on this as the VDF already provides the benefits of performing the iterated hashes, and the iterated hashes are slow to verify.

Lessons learned

When we announce that we will restart the random value generation process, we will include all of the following information in the README located here, and more:

  1. The Ethereum mainnet block hash we will use. This will be a block in the future (not #9619000).

  2. The challenge file upon which we will apply the random value

  3. The number of VDF iterations we will use

  4. The fact that we will not perform iterated SHA256 hashes on the VDF output

  5. The exact commit hashes of the phase2-bn254 binaries we will use to apply the random value to the challenge file

  6. The exact steps we will take

  7. A cryptographic signature of all the above information

One more change to the process

In addition, we will make one change to the process, but for a reason unrelated to the challenge file. We realised that applying 242 SHA256 hash iterations to the VDF output slows down the verification of the random value from seconds to hours. Furthermore, applying a hash chain defeats the purpose of using a VDF in the first place. As such, we decided to only apply the VDF and skip the hash chain.

Finally, we will use the VDF output (not the output of the iterated hashes) as the random value.

Conclusion

The Applied ZKP team, responsible for the development and release of Semaphore, takes security very seriously. If application developers are to use Semaphore for real-world applications, some of which will involve on-chain economic activity, it is imperative that our multi-party setup ceremony be unquestionably secure. Although re-running the random value generation process will delay the start of phase 2 of the ceremony, we believe that this is in the best interest of all.

Re-running the process takes time, but we have learned a lot and will transfer the knowledge we gained to other teams who wish to run a phase 2 ceremony.

Please see this updated repository for the latest details on how we will perform the ceremony.

Restarting the Semaphore random value generation process - March 22, 2020 - Koh Wei Jie