Verifying Zcash Sapling Parameters

#1

Note: the forum software is limiting my newly created account to a maximum of two links, so I’ve been forced to remove some useful links here, but you should be able to find them by visiting the GitHub issue.

Continuing from the discussion in this GitHub issue, I will use this thread to document my odyssey in attempting to verify the Zcash Sapling parameters.

Previously I left off trying to follow @str4d’s instructions to get the phase1radix2m13 phase1radix2m17 phase1radix2m21 files from BitTorrent (which were not easy to obtain due to a lack of seeders. You’re also supposed to generate these yourself, but that can take 100 hours). If you’d like to try this yourself, you can follow @ebfull’s updated instructions.

So I’m pleased to report that I was able to finally run the sapling-mpc code using the distributed sapling-output.params sapling-spend.params sprout-groth16.params params (by concatenating them) and the 3 phase1 params mentioned previously (retrieved from Bittorrent).

The program spat out a bunch of hashes, and all of them matched the ones listed here (max links reached), with the exception that two extra hashes were listed that do not exist on the wiki:

be38cb76c0472b182afc24b55b844068645be98dfc47ce43d8714134c02259c7192d925e25d9ab8ebd4cd8a2d35ddd28a0957ae50e0cf97923685f81a48bdfd1
403af2d88508dccfc7c70aac5a3e58a9ab0509a476e0fba1a6b249c30953a97ae8cbe6fac3b324e0919c6015e8e0139f08682eb22ef48e0f4db4ce898e9bd18e

What the existence of these extra hashes means — I have no idea.

As I do not understand the math behind the MPC ceremony, I do not know whether these hash listings are useful, meaningful, or are at all able to prevent any sort of attack.

I’m also waiting for the machine to generate the phase1 parameters itself from the transcript log and will compare them with the Bittorrent ones once it does.

All-in-all, given the supposed importance of verifying these parameters, I am pretty disturbed by how difficult this whole process has been, and how few people seem to have done this.

And again I stress, that given all of the uncertainties involved, I’m not sure how much stock should be placed even into a verified ceremony, and I again urge Zcash to consider moving away from them.

4 Likes
#2

I was coordinating the Sapling MPC. So it is possible that I simply failed to update the Wiki with their contributions. However I do have logs of every thing so it will be simple for me to look up whom made those contributions and add them to the wiki.

I’m also re-running the powers of tau verification and I will report on performance and time to reproduce.

Double Checking hashes now.

3 Likes
#3

Hello @taoeffect , welcome to the Forum. Since you are obviously not a spammer I have bumped your forum trust level so you can post more links.

The large MPC that you are verifying is the best process for generating zkSNARK parameters that has been designed yet. Having many more participants spread thorough out the world, and only a single one of the the nearly 200 has to destroy thier piece for it to be secure is much better than the original Sprout (only 6 participants) ceremony was.

But that’s not to say the protocol can’t be better, as you mentioned, having a trustless system like STARKs would certainly be the best way to go (and Zooko agrees) https://twitter.com/StarkWareLtd/status/1092819152039903233?s=09

Hopefully STARKs will be ready for use in a production Blockchain like Zcash soon.

1 Like
#4

Clarification: a single piece of each of the rounds needs to be unrecoverable, which means it’s around 1 in 100. That’s still significantly better than the first MPC, and the two MPCs themselves also had better security properties (each piece only needed to be accessible for the duration of the contribution, instead of the entire ceremony, so the compromise window was significantly shortened).

6 Likes
#5

The two hashes you encounter:

be38cb76c0472b182afc24b55b844068645be98dfc47ce43d8714134c02259c7192d925e25d9ab8ebd4cd8a2d35ddd28a0957ae50e0cf97923685f81a48bdfd1
403af2d88508dccfc7c70aac5a3e58a9ab0509a476e0fba1a6b249c30953a97ae8cbe6fac3b324e0919c6015e8e0139f08682eb22ef48e0f4db4ce898e9bd18e

The second one is the random beacon. We can put this in the wiki in order to improve clarity. The first one was just accidentally omitted from the wiki we think (the same participant went twice). @naimed will update this ASAP.

3 Likes
#6

I am confused, here you’re replying to to @Shawn, who suggests there were 200 members, but the link you just posted is thanking “roughly 94 participants”, which coincides with the 95/96 (?) participants implied by the number of hashes output?

So what is this business about 200 participants?

#7

Powers of Tau (phase 1) had 88 participants https://www.zfnd.org/blog/conclusion-of-powers-of-tau/

The Powers of Tau attestations and hashes can be found here: https://github.com/ZcashFoundation/powersoftau-attestations

Sapling MPC (phase 2) had another 90+

As @str4d points out, each part was separate so the number of people who would have all colluded together to somehow save all of the shards for each part was nearly 100, not the total 200. Only one person from each phase had to destroy their part for it to be unrecoverable.

5 Likes
#8

I have verified with the individual contributor, kostas, the hash that was missing from the attestation page and I have updated it: https://github.com/zcash-hackworks/sapling-mpc/wiki
as well as added the random beacon hash at the end.

I’m about 85% complete verifying powersoftau. Will post the output when it finishes.

6 Likes
#9

So, forgive me if someone’s asked this before, but can someone clarify how we know that the transcript itself wasn’t forged somehow? Is that because if it was it wouldn’t match the hashes spit out to the participants by the tools (and we’re assuming no issues in the math and no bugs in the code)?

3 Likes
#10

Correct.

  • The hashes are bound to each participant’s contribution, and each participant was instructed to record their hash (and post it publicly, as many did) at the time they made their contribution. Once the final transcript was published, they could check the hashes generated from the transcript to ensure their own hash was included (and anyone who saw them post their hash publicly could perform the same check).
  • Forging the transcript to match a single one of these public hashes would require the ability for the forger to either break pre-image resistance of the hash function, or solve the discrete log problem for elliptic curves. Forging the transcript to match all of the published hashes is significantly more difficult than either of these two options.
  • Anyone can audit the math that was used, because it was openly published in a paper.
  • Anyone can audit the code that was used if they want to check for implementation bugs, because it’s all open source (and in fact some participants in Powers of Tau used an independent implementation).
6 Likes
#11

My verification of the Powers of Tau is complete. It took 867 minutes on a dual processor AMD 7301 machine (16 cores each, x2 threads per core, so 64 threads.)

It did not use a lot of ram but was caching a lot. (One could run this on a n1-highcpu-96 in google cloud and probably do about 50% faster.)

The software produced the expected files.

See output here:

5 Likes
#12

That’s an insanely fast machine, wow! Mine is going to take considerably longer (bare metal, but only 4 threads). However I can confirm that at least up to b39c2f54485df51cd0434b0d3cbfcff7b7cc02c2e941097526cf5e605c9f8aaddd3cf9372d0e567cad8c49d7b507a47dac7510203a7f2f00b7d7810636064f06 the output matches, so I doubt it will deviate.

Also, the sha256sums for the 3 Bittorrent phase1 files matches the output in your gist:

$ sha256sum phase1*
a20e6c6a9934dc43f7d77121ee6214c7ee564789d1b9736174d881091da11387  phase1radix2m13
1bb2de121836af52ab572d16a4310f2d6ef7bf1015398266786dd123ef1ca1e2  phase1radix2m17
90bf83253252120d8162c3c68687ef4c7da94127e2d67683c94a61ac4b471182  phase1radix2m21
3 Likes
#13

It’s pretty fast but there are faster :wink:
Pinging a buddy to see if I can race something else. Any of the bigger AWS or GCP machines should be able to finish in under a day though.

1 Like
#14

I mentioned over Twitter that there is a “trick” that can accelerate verification time of Powers of Tau. The current code checks that each contribution is consistent with the previous state. In actuality, it is only necessary to check that a portion of the update is consistent with the previous state, because it is mathematically impossible for the parameters to otherwise validate. This was not implemented at the time.

The Sapling MPC phase does not inherit this limitation and ensures that the transcript of that phase can be shipped alongside the parameters themselves, so that both can be authenticated at once. This is an important quality that I’ve ensured we can cryptographically inherit in new proving systems, such as Sonic.

4 Likes
#15

Thanks for spurring this on. Better late than never and glad to see several people join in.

At one point I tried to get some folks to help me on a “refereed delegation” for sapling verification. Basically this is performing the verification in a way that there could be simple “fraud proofs” by committing to each intermediate step after verifying each hash. So if someone claimed they ran the verification and it didn’t work, they’d be able to prove it quickly. This is still a good idea for a project. Another related approach would be to build a STARK project for the verifier, though clearly that’s a bit confusing. Anyway, both of these could still be done now, compatible with the existing ceremony.

2 Likes
#16

FWIW, I too can now confirm the powersoftau output. It took about 4 days to finish with 4 threads on a relatively modern CPU. My output matches what @naimed shared, and the 3 critical phase1 files have the correct hashes :slight_smile:

$ sha256sum phase1radix2m{13,17,21}
a20e6c6a9934dc43f7d77121ee6214c7ee564789d1b9736174d881091da11387  phase1radix2m13
1bb2de121836af52ab572d16a4310f2d6ef7bf1015398266786dd123ef1ca1e2  phase1radix2m17
90bf83253252120d8162c3c68687ef4c7da94127e2d67683c94a61ac4b471182  phase1radix2m21
8 Likes