search

zcash / zcash

Zcash - Internet Money
https://z.cash/
Other
4.92k stars 2.03k forks source link

Proof precomputation #3632

Open ebfull opened 5 years ago

ebfull commented 5 years ago

Most of the time spent constructing a Sapling transaction is spent constructing Spend proofs. In theory we could compute these in advance, though the proofs would "fall behind" as the accumulator grows. I want to explore precomputation ideas, such as:

  1. Construct Spend proofs periodically in the background (once a day? once an hour?) using the most recent accumulator. We could coalesce notes in the background, also, to minimize the number of proofs we have to construct.
  2. Changing the construction somehow, e.g., making Spend proofs commit to the merkle root and either open it directly or use another, presumably cheaper proof to demonstrate that the merkle root is a previous anchor.
  3. It's also true that we can do some partial zk-SNARK precomputation based on a partial witness, but this probably won't lead to much benefit. Most of the cost of zk-SNARK proof generation is computing a polynomial that depends on the complete witness and then evaluating that (very dense) polynomial over the parameters.

This helps considerably when we're exploring the space of newer proving systems (with no parameter setup, for example) which may have poor proving performance for Sapling-size circuits.

daira commented 5 years ago

Several ideas along these lines were discussed in #43. That ticket was closed on the grounds that the complication was unnecessary after Sapling, but that conclusion may not hold for other proof systems.