Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Large zk-SNARK MPCs #2247

Open
ebfull opened this issue Apr 9, 2017 · 26 comments

Comments

6 participants
@ebfull
Copy link
Contributor

commented Apr 9, 2017

I personally believe that Zcash's next multi-party computation for Sapling should not include a small handful of people but instead such a large collection of disparate reputable individuals that it is vanishingly unlikely for all of them to be compromised or collaborating in secret. This is both a fantastic improvement over our previous ceremony in terms of the faith users can put in our project and ultimately saves us logistical and operational security costs.

However, the old MPC design does not scale well to a large number of participants for a couple reasons. We had to carefully synchronize individuals, and those individuals needed to maintain custody of their hardware even when it was no longer their turn. Since the computations and bandwidth costs are so great, it's a bit surprising that we even managed to make it work with six people.


I am proposing that we start an MPC project (called Preston for now) which behaves like a "randomness accumulator" in that there is no pre-determined set of participants, and no synchronization needs. It is circuit-agnostic and can be continually strengthened by the community over time.

Then, we have a Sapling MPC which uses the most recent "state" of the Preston accumulator. This MPC is circuit-specific but much cheaper than the Preston MPC. As with the Preston MPC, there is no pre-determined set of participants and it behaves like a randomness accumulator. At least one person must be honest in both MPCs.

There are numerous advantages to this approach:

  1. During either of these MPCs, participants do not need to maintain custody of their hardware for the entire ceremony. When it's their turn, they get their hardware, perform the computations and then are free to destroy the hardware immediately after they're finished.
  2. There is no synchronization requirements and no pre-determined set of participants, so as a result this allows our MPC to scale to hundreds or thousands of individuals.
  3. Sapling may have a split-circuit design (#2171) in which case we will be performing MPCs for multiple circuits in parallel. By arranging it in this way, the entire MPC is far cheaper overall.
  4. After Sapling, we will likely want to do more MPCs. In which case, we can rely on even stronger Preston parameters as it is continually strengthened by the community.
  5. Projects outside of Zcash can perform cheap zk-SNARK MPCs using the Preston accumulator as a base, so it doubles as a contribution to the broader community.
  6. Each individual participant in the ceremony has total discretion over their efforts to contain their portion toxic waste. Interesting philosophical observation: with this approach all of the pieces of the toxic waste may not even exist simultaneously.

Cryptographically this idea is inspired by @arielgabizon's suggestion to reuse the powers of tau for each ceremony. In order to treat these rounds as individual accumulators, we may need to work with the generic group model, so I will focus on Groth'16 for now.

As with our previous MPC, we extend the CRS to include all of the components of the public transcript. If it is secure to extend the CRS to include the alpha and beta multiples of tau powers, then a circuit-agnostic MPC can be performed over tau/alpha/beta in parallel by asking each participant to perform an FFT over their modified lagrange coefficient accumulators before applying their powers of tau. The coordinator (and transcript verifier) can confirm this was correctly calculated and perform an FFT for the next participant.

The QAP polynomials can then be trivially evaluated in the lagrange basis and used for the next (cheaper) MPC for gamma/delta.

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 10, 2017

Is there a limit on circuit size based on the parameters of the randomness accumulator? Does the accumulator depend on the proving system, as well as the curve?

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 10, 2017

You said that the CRS depends on all the components of the public transcript. Does this mean that the proving+verifying key size increases with the number of participants? If so, is that the number in both MPCs or just the circuit-specific MPC, and what is the size increase per participant?

@ebfull

This comment has been minimized.

Copy link
Contributor Author

commented Apr 10, 2017

Good questions!

Is there a limit on circuit size based on the parameters of the randomness accumulator? Does the accumulator depend on the proving system, as well as the curve?

The randomness accumulator assumes a particular limit on circuit size. I was planning on suggesting that it contain several accumulators operating in parallel over different evaluation domains, up to the size of the existing Zcash circuit (2^21) which is more than enough for our purposes.

Does the accumulator depend on the proving system, as well as the curve?

Yes, both, but there may be a way to partially reuse it for PGHR.

You said that the CRS depends on all the components of the public transcript. Does this mean that the proving+verifying key size increases with the number of participants?

AFAIK we have to consider all the elements of the public transcript part of the CRS for the security proof. The proving and verifying keys remain sized proportionally to the circuit.

@ghost

This comment has been minimized.

Copy link

commented Apr 13, 2017

It's too late, the first keys were generated with a ridiculous small number of people and all using a single DVD, the keys could be in the hands of someone and this person could have printed millions of Zcash already and is just waiting a safe opportunity to unload them in the far future. I guess the only question remaining is whether these millions of secretly generated coins could still be spent after another ceremony.

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 13, 2017

@lethos3: see #2248 (comment)

@daira daira added this to Work Queue in Sapling Protocol Upgrade Apr 20, 2017

@daira daira moved this from Work Queue to Discussion in Sapling Protocol Upgrade Apr 20, 2017

@daira daira added this to 1.1.0: Consensus / Node Rules in Release planning Nov 10, 2017

@daira daira moved this from Sapling specification to Sapling MPC in Release planning Nov 10, 2017

@taoeffect

This comment has been minimized.

Copy link

commented Feb 9, 2019

What is it about the MPC that you believe provides any sort of guarantee that the end result of the MPC isn't tampered with?

@daira

This comment has been minimized.

Copy link
Contributor

commented Feb 9, 2019

@taoeffect : each participant is able to verify that their contribution is part of the final parameters, using the software at https://github.com/ebfull/powersoftau (for powers-of-tau) and https://github.com/zcash-hackworks/sapling-mpc (for phase 2).

@taoeffect

This comment has been minimized.

Copy link

commented Feb 9, 2019

@daira Thanks!

From that second link, the README says:

The tool also prints a hash. This hash is what you and others can use to verify that your contribution actually ended up in the final parameters, so you're encouraged to save it to check later!

It offers no instructions on how to verify that hash. Where are those instructions?

Has anyone successfully done this?

It is also odd that the first link doesn't mention the second link.

EDIT: It's possible I'm misunderstanding something (as both links mention saving hashes, and I'm not familiar with what "phase 2" means)

@mineZcash

This comment has been minimized.

Copy link

commented Feb 10, 2019

@taoeffect I believe the hash that they are referring to is the output when you ran the computation on your PC (if you chose to participate). If you didn't join the MPC you wouldn't have the hash to compare against the final parameters.

Phase 1 was called Powers of Tau, Phase 2 was called Sapling MPC: https://z.cash/blog/completion-of-the-sapling-mpc/

That blog post also has info about how to run the verify utility to see that your hash was included.

@taoeffect

This comment has been minimized.

Copy link

commented Feb 10, 2019

@mineZcash

That blog post also has info about how to run the verify utility to see that your hash was included.

Where? I cannot find any instructions. The only thing I see in the link you sent is:

You can verify the parameters using the verify utility in the sapling-mpc repository.

Which points to a source file.

I am not an expert on Rust but I don't even see where in the source it allows for verification.

  1. Can you point to a single person who has been able to follow these instructions and verify that "your hash was included"?
  2. Can you explain why they must do this manually (EDIT: and privately)? Why isn't this being done in a publicly-verifiable way through pre-commitments and reveals on the blockchain?
@mineZcash

This comment has been minimized.

Copy link

commented Feb 10, 2019

@taoeffect I'm not a developer for Zcash so I don't know why certain methods were chosen over others. AFAIK all the code for both MPCs is available and publicly-verifiable in the aforementioned GitHub repos (which anyone is free to clone for posterity if they wish)

@str4d helped a user on Reddit with instructions on running the verification you may find helpful:

https://www.reddit.com/r/zec/comments/9xf07q/verification_of_powers_of_tau_and_sapling_mpc/

@taoeffect

This comment has been minimized.

Copy link

commented Feb 10, 2019

AFAIK all the code for both MPCs is available and publicly-verifiable in the aforementioned GitHub repos (which anyone is free to clone for posterity if they wish)

It's not enough for the code to be publicly verifiable, one needs to know whether that "hash" (or whatever) that people generated during the MPC was verified by the individuals.

So far you have not linked me to anything indicating that it was. :-\

@str4d helped a user on Reddit with instructions on running the verification you may find helpful:
https://www.reddit.com/r/zec/comments/9xf07q/verification_of_powers_of_tau_and_sapling_mpc/

Here's what @str4d said in that link:

You need to download the whole powersoftau and sapling-mpc repositories, not just the verify.rs files. Then, place each transcript / params file in its corresponding directory, and in each directory run cargo run --release --bin verify.

This too does not indicate that the hash was verified.

Neither the "transcript" nor the "params" represent the hash to-be-verified.

Again, I respectfully ask: can you (or anyone else) point to a single person who has been able to follow these instructions and verify that "your hash was included"?

@mineZcash

This comment has been minimized.

Copy link

commented Feb 10, 2019

one needs to know whether that "hash" (or whatever) that people generated during the MPC was verified by the individuals.

To know that you would need to ask each of the individuals if they have taken the time do so.

Alternatively, you could run any of their publicly posted hashes to verify for yourself: https://github.com/zcash-hackworks/sapling-mpc/wiki

@taoeffect

This comment has been minimized.

Copy link

commented Feb 10, 2019

Alternatively, you could run any of their publicly posted hashes to verify for yourself: https://github.com/zcash-hackworks/sapling-mpc/wiki

Thank you, that is somewhat helpful. However, per both project READMEs, there's still more information required in order to verify, that was only given to participants:

If you've been asked to participate, you were sent a challenge file.

When it's your turn, you'll receive a params file from us.

So, where can these file(s) be accessed?

@daira

This comment has been minimized.

Copy link
Contributor

commented Feb 10, 2019

The whole transcript for powers-of-tau is linked here: https://www.zfnd.org/blog/conclusion-of-powers-of-tau/

For the Sapling MPC, I believe you don't need the transcript, just the final parameters, the hashes, and the verification software. @ebfull, is that correct?

@taoeffect

This comment has been minimized.

Copy link

commented Feb 10, 2019

For the Sapling MPC, I believe you don't need the transcript, just the final parameters, the hashes, and the verification software. @ebfull, is that correct?

Where can I find the final parameters? Are they the same as the ones that downloaded to the .zcash-params folder?

ls -a .zcash-params
.  ..  README  sapling-output.params  sapling-spend.params  sprout-groth16.params  sprout-proving.key  sprout-verifying.key

Is it the sapling-output.params file or the sapling-spend.params file?

@taoeffect

This comment has been minimized.

Copy link

commented Feb 10, 2019

OK, while waiting for a response I decided to try this with both files.

Here is the result of save sapling-output.params as params in the sapling-mpc directory and running cargo run --release --bin verify --features="verification":

$ cargo run --release --bin verify --features="verification"
    Finished release [optimized] target(s) in 0.02s
     Running `target/release/verify`
thread 'main' panicked at 'couldn't deserialize Sapling Output params: Custom { kind: UnexpectedEof, error: StringError("failed to fill whole buffer") }', src/libcore/result.rs:1009:5
note: Run with `RUST_BACKTRACE=1` for a backtrace.

And here is the result of running the same command with sapling-spend.params as params instead:

$ cargo run --release --bin verify --features="verification"
    Finished release [optimized] target(s) in 0.04s
     Running `target/release/verify`
thread 'main' panicked at 'couldn't deserialize Sapling Output params: Custom { kind: UnexpectedEof, error: StringError("failed to fill whole buffer") }', src/libcore/result.rs:1009:5
note: Run with `RUST_BACKTRACE=1` for a backtrace.

Mind you, I had to figure out even how to run the damned verification command out on my own based on putting together crappy info from the random links listed above. Nowhere in the sapling-mpc README are there instructions on how to run this verification procedure, nor is there anything useful in any of the blogs linked above. Furthermore, there is an outstanding issue in the sapling-mpc repository that has gone ignored since May 23 of last year.

I have a hard time believing anyone listed here was successfully able to verify their results.

My question to the Zcash team: what sort of bullshit are you selling to investors and the world, and how is this remotely acceptable?

@daira

This comment has been minimized.

Copy link
Contributor

commented Feb 10, 2019

@taoeffect wrote:

Furthermore, there is an outstanding issue in the sapling-mpc repository that has gone ignored since May 23 of last year.

That has no effect on functionality, it's just a couple of copy-paste mistakes in error messages.

@str4d

This comment has been minimized.

Copy link
Contributor

commented Feb 10, 2019

@taoeffect wrote:

Where can I find the final parameters? Are they the same as the ones that downloaded to the .zcash-params folder?

The params file that you need for the verification binary is the combined file that was being passed between participants during the ceremony - specifically, the final version of that file. It was split into the three individual files you see in ~/.zcash-params (using this binary). You can trivially recreate the params file by concatenating the three individual parameters together like so:

cat ~/.zcash-params/sapling-spend.params >params
cat ~/.zcash-params/sapling-output.params >>params
cat ~/.zcash-params/sprout-groth16.params >>params

Then running the aforementioned command will perform the verification (which will take a while, as it's single-threaded) and eventually print out the list of contribution hashes. It is necessary to verify all three parameters together, as the hash participants recorded is bound to all three parameters.

@taoeffect

This comment has been minimized.

Copy link

commented Feb 11, 2019

Thank you very much @str4d. After ~35 minutes this is the result:

$ cargo run --release --bin verify --features="verification"
    Finished release [optimized] target(s) in 0.05s
     Running `target/release/verify`
thread 'main' panicked at 'Couldn't load phase1radix2m17: Os { code: 2, kind: NotFound, message: "No such file or directory" }', /home/docker/.cargo/registry/src/github.com-1ecc6299db9ec823/phase2-0.2.2/src/lib.rs:448:17
note: Run with `RUST_BACKTRACE=1` for a backtrace.
@str4d

This comment has been minimized.

Copy link
Contributor

commented Feb 11, 2019

Apologies, I'd forgotten about this dependency. You will need to download the following files from the Powers of Tau ceremony, and place them in your current directory:

  • phase1radix2m13
  • phase1radix2m17
  • phase1radix2m21

These are the starting points for the three parameters created in the Sapling MPC.

@str4d

This comment has been minimized.

Copy link
Contributor

commented Feb 11, 2019

I've opened zcash-hackworks/sapling-mpc#2 with some changes to address the above usability issues.

@taoeffect

This comment has been minimized.

Copy link

commented Feb 11, 2019

You will need to download the following files from the Powers of Tau ceremony [..]

These parameters do not seem to exist.

screen shot 2019-02-10 at 8 31 36 pm

@ebfull

This comment has been minimized.

Copy link
Contributor Author

commented Feb 11, 2019

I've written some instructions for verifying both MPCs. I'll continue to edit it as I receive feedback.

I don't think that this github issue is an appropriate place for this conversation? I don't know where else might be. Perhaps the forums, or community chat, the zapps-wg mailing list, etc.. I think this ticket should actually have been closed after Sapling activated.

@taoeffect

This comment has been minimized.

Copy link

commented Feb 11, 2019

I'm happy to pick this up on the forums and post a link here so others can follow along. I should update that now there does seem to be a seeder available to download these parameters from. It will still take some hours to download the transcript though.

Sidenote: @ebfull you may want to include a link to that gist in the two repo READMEs (powersoftau and sampling-mpc)

@taoeffect

This comment has been minimized.

Copy link

commented Feb 11, 2019

OK, I opened up a thread on the forums: https://forum.zcashcommunity.com/t/verifying-zcash-sapling-parameters/32700

Of note, there are some extra hashes in the sapling-mpc output that don't appear on the wiki.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.