search

zcash / zips

Zcash Improvement Proposals
https://zips.z.cash
MIT License
274 stars 155 forks source link

[ZIP 2] Design considerations for Network Upgrades #362

Open daira opened 7 years ago

daira commented 7 years ago

Issue by nathan-at-least Wednesday Jun 08, 2016 at 15:30 UTC Originally opened as https://github.com/zcash/zips/issues/53

What do protocol upgrades look like? Are there forwards compatibility features such as in the block header?

daira commented 7 years ago

Comment by matthewdgreen Wednesday Jun 08, 2016 at 16:17 UTC

Long bunch of half-baked thoughts below.

What I'd really like to do is understand what a Zcash protocol upgrade looks like, worked out on a step-by-step basis. Note that for now I'm only concerned with changes to the anonymous payment protocol -- not the PoW or other components. From what I understand, there's no "soft fork" way to handle this upgrade. Still, even a hard fork isn't going to be instantaneous, so the question is what that looks like -- and what does it mean for nodes that don't immediately upgrade.

The general idea as I've understood it is that transactions have a version number. In a perfect world, this would allow for a smooth transition, since ZCash v1 and v2 transactions can be thought of as two separate currencies, each with its own accumulator. Which brings me to the first question: do we currently have support for multiple accumulators in the block format? If we add it in a hard fork, will every existing client blow up, or can it be done in a legacy-compatible way?

If we have support for multiple accumulators, then some kind of smooth transition would (at least in theory) be possible using a one-way exchange mechanism. Funds could be spent from v1 (which all nodes can verify) and entombed into the v2 tree (which only a minority supports initially) without anyone having a real problem -- as long as transfers could not go in the opposite direction. The wrinkle here is that ZCash also supports a non-anonymous currency, and so this would have to also deal with transactions that go v2->non-anonymous->v1. This could be prevented, but it starts to get complex very, very fast. And we would have to add all of these features now in order to make any of this work.

The alternative is... well, I'm not sure. Is there a mechanism for older clients to deal with the fact that there are now v2 transactions in the blockchain? Should those clients just shut down and say "upgrade me please"? Additionally -- is there an N-last-blocks-support-v2 voting mechanism in place to determine when v2 transactions will be allowed? Is this necessary? Can we really support upgrades without thinking about any of this?

Anyway, that was a lot of questions. I'm going to restate them all in a list:

  1. Do we currently have support for multiple accumulators in the block format? If we add it in a hard fork, will every existing client blow up, or can this be smoothly added without breaking legacy clients?
  2. How do we schedule a hard-fork to support V2 clients? Is this an N-last-blocks mechanism that we design in the future, or does it require thought now?
  3. What do older clients do when they start seeing v2 transactions and block headers they can't deal with? Is there any way they can continue operating, or do they just shut down and say "upgrade me please"?
  4. What is the minimal set of features that need to exist to support a smooth upgrade, and what does it look like?
  5. What if we just want to upgrade the pairing curve, or use new proving parameters? Does this require a full v2 upgrade, or is there a more gentle upgrade mechanism possible for this special case?

Sorry this is half-baked. Would like to hear thoughts...

daira commented 7 years ago

Comment by zookozcash Wednesday Jun 08, 2016 at 17:39 UTC

Good questions, Matt.

  1. No, there's only a single accumulator currently.
  2. I think we can safely put off the designing of the scheduling. It'll probably end up being scheduled in much the same way softforks have been scheduled in Bitcoin, the way a hardfork was scheduled in Ethereum, and the way a hardfork might be scheduled for Bitcoin in the future.

  3. I think that even if we can figure out how to let old clients continue in that case, that we shouldn't. I think old clients should just tell their users "I cannot safely tell you anything about this blockchain, even about the parts that I still recognize, because there are parts in here that I do not recognize, and the blockchain is a whole unit -- it's not safe to interpret subsets of it."

    (Note: whether there could be a safe and principled way to do that is an open science problem. We've gnawed on it a little bit, but we're not going to be able to solve it before Sprout begins.)

  4. We've gnawed on this question quite a lot. You can see our notes here: https://github.com/zcash/zcash/labels/future%20proofing and more specifically here: https://github.com/zcash/zcash/labels/hard-fork%20management . The minimal set that we've decided on for Sprout is visible here: https://github.com/zcash/zcash/issues?utf8=%E2%9C%93&q=is%3Aopen+label%3A%22hard-fork+management%22++label%3A%22in+1.0%22
  5. It is the same.
daira commented 7 years ago

Comment by daira Wednesday Jun 08, 2016 at 23:35 UTC

I would like to see the block and transaction version numbers split into (major, minor) version tuples, where:

This would improve our ability to make various kinds of changes while minimising negative security and functionality impacts on downrev clients. Note that I don't agree in general that the versions can accurately be modelled as different currencies or that they will in general require different accumulators; we should try at all costs to avoid that unless the desired change absolutely requires it. (One approach is to upgrade the accumulator state on triggering the fork, but have a way to apply old-version transactions to the new accumulator.)

Related: https://github.com/zcash/zcash/issues/114

daira commented 7 years ago

Comment by daira Wednesday Jun 08, 2016 at 23:40 UTC

In any case, I'm not sure that this belongs in the protocol specification, because it's too speculative. (We don't actually have to decide on the approach until we do a particular hardfork, and for a given hardfork we may do something different than what was anticipated by any discussion in the spec.) I'd be happy about having a separate document that discusses upgrade approaches, with some examples of potential upgrades.

daira commented 7 years ago

Comment by matthewdgreen Wednesday Jun 08, 2016 at 23:52 UTC

I agree that having a more fine-grained version numbering scheme is a good idea.

My big question is: are there any interesting (main protocol) changes that could count as "minor" version revs? Here I'm thinking about things like (1) upgrading the pairing curve size, (2) re-generating zkSNARK parameters with a larger MPC group, (3) miscellaneous trivial optimizations to the circuit.

These are about as "small" a protocol change as you can expect, without the change just being trivial. The commonality of each of the above is that they /only/ affect the Prove/Verify part of the protocol, and do not affect the commitment or tree construction. So a client would not be able to verify the correctness of any zkSNARK proof, but might be able to plow on if it trusted that other miners were verifying the proofs correctly.

After some discussions with Ian I am pessimistic that we could make such a thing work, and if that's true, it means that "minor" revs are going to be pretty trivial things not related to significant protocol changes. Do you agree with this?

If you do agree, then my conclusion is that our upgrade policy is going to consist of (1) immediate hard fork, where all clients have to upgrade, or (2) some complicated thing with multiple trees and a one-way flow from currency v1 to currency v2. I don't yet see an option (3).

Obviously for the immediate September release, we're going with (1). But I don't know if that's a sustainable long-term policy if ZCash is successful. So I'd like to think a bit about what a more sustainable upgrade policy would look like. Separate documents are just fine.

daira commented 7 years ago

Comment by zookozcash Wednesday Jun 08, 2016 at 23:59 UTC

I just want to say that I'm delighted that you're thinking about these issues, Matt. (And, apparently, Ian.)

daira commented 7 years ago

Comment by matthewdgreen Thursday Jun 09, 2016 at 00:04 UTC

PS I don't think a protocol upgrade is that speculative. We know we probably have to adjust the curve size in the near term, and param re-gen is always a real possibility. The main protocol spec should at least talk about how this will be done, even if it's only "we will do a hard fork using the standard approach of Bitcoin etc."

daira commented 7 years ago

Comment by jl777 Thursday Jun 09, 2016 at 00:05 UTC

One idea is making backward compatible forks, like the segwit softfork trick. older nodes still work, but need to trust the newer nodes are validating the new formats. Since each fork will have the code to handle the older variants, the only issue is a bit of code bloat as each new variant is release.

With a deprecation policy of 2 updates (or 1 year), then as long as the old clients upgrade within a year, it would operate seamlessly on the mainchain. The downside is that the nodes that dont upgrade need to trust the upgraded nodes. However if a supermajority has upgraded to trigger the softfork, this is probably not such an issue

daira commented 7 years ago

Comment by zookozcash Thursday Jun 09, 2016 at 00:07 UTC

Indeed, I intend to push for other upgrades which require revving the protocol in addition to the ones you mention, Matt. I think we should, in general, be a little bit more like Ethereum (planned compatibility-breaking protocol upgrades) than Bitcoin currently is (no compatibility-breaking protocol upgrades).

daira commented 7 years ago

Comment by zookozcash Thursday Jun 09, 2016 at 00:10 UTC

@jl777: re https://github.com/zcash/zips/issues/53#issuecomment-224767451, I'm opposed to that technique of hacking the protocol to enable backward-compatible upgrades. I think it is better to have backward-incompatible upgrades -- clients that don't upgrade will fail safe, and clients that want to proceed without accepting the same upgrade will fork.

daira commented 7 years ago

Comment by matthewdgreen Thursday Jun 09, 2016 at 00:12 UTC

There is a related issue, which is that over time our trees are going to fill up, which means that the serial number database is going to get big. We're going to need to deal with this. The approach we had discussed (way back when) was to periodically start a new tree, and allow transfers from tree 1 to tree 2. I guess the point here is that this "new tree" approach also happens to work well for (major version) protocol upgrades. But this is a long-term problem.

daira commented 7 years ago

Comment by jl777 Thursday Jun 09, 2016 at 00:13 UTC

I just wanted to point out the possibility of being able to do both.

bitcoin's segwit softfork is a compatibility breaking change, but it does it by creating two classes of nodes. older ones that need to rely on the supermajority. so even though the new protocol is not understood by the older nodes, they can still operate on the network and can update.

so it is at the same time what you want (backward incompatible) but users dont need to upgrade immediately and the existing coins would still be valid. Having to transfer old format coins into new sounds like quite an usability issue...

daira commented 7 years ago

Comment by jl777 Thursday Jun 09, 2016 at 00:14 UTC

What about having new versions handle all the historical trees, at least for one year or so for each filled up tree? 1GB per year for the new dataset isnt such a problem, especially if it allows seamless user experience

daira commented 7 years ago

Comment by matthewdgreen Thursday Jun 09, 2016 at 00:15 UTC

I agree. In the short term we can do hard forks, but these are going to get harder and harder as we go forward. I think Ethereum is a good model of a "young" network that can get away with things, whereas Bitcoin is what happens when you get really successful.

daira commented 7 years ago

Comment by matthewdgreen Thursday Jun 09, 2016 at 00:17 UTC

We can have new versions handle the historical trees. We had also talked about constructing a serial number Merkle tree, and having clients prove that their serial number is not in the tree. This turned out to be all sorts of painful, but it might allow people to spend currency in those legacy trees even a long time after they're not supported.

daira commented 7 years ago

Comment by jl777 Thursday Jun 09, 2016 at 00:18 UTC

once there is a large installed base, hardforks become less and less practical. Its more work to support multiple trees, but if it is expected that a single tree isnt enough, then supporting multiple trees seem like a requirement. I cant see forcing users to convert old tree coins into new tree coins as a good idea. It also seems to open a privacy issue as to convert old coins requires another tx and increases the footprint that can be attacked, if only the IP usage footprint

daira commented 7 years ago

Comment by jl777 Thursday Jun 09, 2016 at 00:23 UTC

This isnt needed for first version, but I think as soon as the first tree goes live the second version with multiple tree support is important, especially as it closes the attack vector of filling up a tree. I assume the cost is the 1GB of new data per tree, which even annually can be absorbed. The zcash chain is already on the large side with the headers and tx already much bigger than normal protocol.

Maybe the txversion just indexes into the appropriate tree? have no idea what has to happen with the crypto math, but at least the info is there as to what tree is being used. mixing transactions with coins from different trees could be constrained by having a special import old coins, if that causes issues with the cryptomath, so as soon as someone wants to spend old coins, they would need to update so they can convert, but until then they can still receive and see their balances with the old version

Does that work?

daira commented 7 years ago

Comment by zookozcash Thursday Jun 09, 2016 at 00:38 UTC

I have a proposal that I've written but haven't posted yet that interacts with this. I call it the "Chinese New Year" proposal.

daira commented 7 years ago

Comment by matthewdgreen Thursday Jun 09, 2016 at 11:17 UTC

From a crypto perspective, having multiple trees ought to be pretty straightforward. From an engineering perspective it'll probably be a nightmare. You would need to add separate fields to indicate (tree transaction is being spent from), (tree transaction is being added to). Alternatively you could only allow spending within a given tree, and force people to go back to non-anonymous coin if they want to bridge two different trees.

The more interesting question is how you use this idea to prune the serial number database. If you "expire" trees after some long period of time, you no longer have to keep those serial numbers around at the Verifier -- but at the cost of destroying all the money contained within those trees, which doesn't seem right.

The other approach (mentioned above) is for "old" trees, create a serial number tree and with each transaction, include a non-membership proof that your serial number is not in the tree. But then /that/ tree must be extended each time somebody spends, and I worry that updating it will get hideous. Maybe it could all be allowed as a kind of "legacy support" mode, and the additional costs supported with relatively higher transaction fees.

This is all getting far away from the initial idea of upgrades -- which in the short term is going to end up being "hard fork" for a long time. I still think in the long run something like this still needs to be built, both for scalability and upgrade purposes.