Zcash: Mini-roadmap: Rollback Circuit-breakers → Notaries → Hybrid PoW+PoS

[nathan-at-least]

In light of the growing frequency and scale of rollback attacks, a recent example being the attack on ETC announced by Coinbase, we are investigating ways to shore up rollback protection for Zcash. One such trajectory involves "notaries", as I outline here.

Centralization and Trade-offs:

When I say "notary" here, I mean a more-or-less statically defined (thus privileged) node that attests to which blockchain histories are legitimate. People may accurately criticize this as "centralization". I think a more precise criticism is that entry and exit to the roster is costly and political, rather than open (and ideally meritorious). In my view, the potential for abuse of this kind of political gate-keeping and associated privilege generally increases over time, and therefore I only propose any notary design with the explicit understanding that we intend to replace it with a non-static, permissionless entry/exit system in the future. (Edit: That could include simply reverting back to pure proof-of-work, to be clear. It could be anything, so long as it's permissionless entry/exit.)

I sometimes think of proof-of-work and (ideal secure) proof-of-stake as a dynamic roster system of privileged nodes (miners, stakers) where we've done our best to replace the political gate-keeper with random selection, using mining rewards or staking penalties to approximate to merit.

Okay, but why take on the risk and cost in the first place? To protect against rollback attacks. (See Alternatives below.)

Common Definitions:

In every stage, the "ideal goal" is to prevent a rollback of k blocks. (Don't assume this k is the same as any k in other tickets for now.) For concreteness, define k = 10.

To "prevent a rollback of k blocks" in _the ideal_ means "if all nodes, globally agree on a current best chain tip at height H, then no current or future nodes will ever accept a history which does not include the block at H - k."

The Mini-Roadmap: (It's mini because it's not comprehensive for Zcash, but topical. Is it a "lane-map"?)

Phases which involve consensus changes are explicitly marked as such and all other stages do not require consensus changes.

1. Naive Local Circuit-Breaker - If my node sees a rollback ≥ k blocks, emit a warning and exit, then we all agree to only follow the chronologically-first chain, such as by checkpointing it statically.

   Introduces a DOS vector, but at least no exchange will honor a rolled back deposit, etc. The recovery process where "we all agree" is manual, painful, and confusing, but at least there's some up-front expectation.

2. Local Rollback Blacklist Policy - If my node sees a rollback ≥ k blocks, blacklist the block immediately after the common ancestor which my node saw last.

   This may be too vulnerable to network segregation attacks, and maybe we should skip this phase altogether. Thoughts? What if in addition to the blacklist, warnings are emitted, explorers and exchanges show blacklisted blocks, etc… to prompt "social recovery"?

3. Opt-in Static Roster Notary Policy - All nodes have a baked in list of official notaries, which are operated by [insert set of reliable, well-known orgs to operate notaries]. When a majority of notaries sign a block, treat that block as a checkpoint (that is, reject any block which does not descend from the most recent checkpoint). If there is no such checkpoint more recent than 2*k blocks from the local nodes current tip, enter network freeze mode. Notaries immediately sign a block when it has k confirmations on their local best tip (thus it's at height H-k).

   Users have to turn this on in their config file, but that probably doesn't matter very much except for a smooth rollout, because what matters is if the majority hash-rate, exchanges, explorers, wallets, etc… turn it on.

   Requires notable network changes. May introduce network-specific attack vectors (such as dropping notary signatures selectively). May introduce network roll-out complexity.

   TODO: Do notaries follow the checkpointing rule themselves? Edit: Yes, because if they attest to a checkpoint that excludes a prior checkpoint, that's incoherent. All nodes should probably implement notary functionality, so that as little as possible is unique about notaries. Nodes should not relay non-notary attestations.

4. Opt-Out Static Roster Notary Policy - Same as above except turned on by default.

5. CONSENSUS CHANGE Consensus-enforced Static Roster Notary Policy - Same as above except enforced by consensus, thus blocks must include attestations. Probably a lot I haven't thought of yet here.

6. CONSENSUS CHANGE Hybrid PoS + PoW - Same as above, except the roster changes dynamically based on staked bonds. Lots of hand-waving here.

Alternatives:

The most pressing argument against all of these alternatives (except the dominant ASIC case, which currently already applies to Zcash) is time-sensitivity. We need rollback protection sooner than NU2 Blossom, and Blossom already excludes any such feature changes.

• Become THE dominant GPU-mined PoW system. An attacker's opportunity cost is whatever else they could apply those GPU resources to. The only way this seems feasible to me is if GPU mining a single coin generated substantially more revenue than all other uses of GPUs. We can't cause the mining revenue to increase by our actions, nor can we notably affect the rest of the GPU economy.
• Become the dominant ASIC-mined PoW for a specific PoW algorithm. The common argument I like is that ASIC miners do not want to degrade their future revenue by undermining confidence in the coin since that would exacerbate their ASIC capital depreciation. It appears that rollback attacks do not seem to cause an obvious price decline currently, however, as this @kerooke tweet and other cases have shown.
• Switch to a pure Proof-of-Stake system. I'm not yet familiar enough with such systems to have confidence in their security, nor do I have confidence in the high-order / economic effects.
• Switch to a hybrid PoW+PoS system. Since I'm already familiar with the security and (kinda) the economics of PoW, I feel more comfortable (currently) reasoning about hybrid systems. This is a natural extension of the static notary mini-roadmap proposed in this ticket. A full hybrid consensus change is not feasible on a short time-scale, but interim stages are. Implementing the interim stages does not _require_ us to adopt the subsequent consensus changes, either.
• Others that I'm missing?

Related: Rollback Protection label

[defuse]

How effective these defenses are will depend on the adversary's capabilities. Let's be clear about the threat model here. Some types of adversary we should consider:

• F0: The adversary has enough hashpower to carry out a 51% attack for some finite length of time.
• FE: F0, plus complete control over an exchange's network traffic.
• FN: F0, plus complete control over all notaries' network traffic.
• FEN: FE and FN.
• I0: The adversary has enough hashpower to carry out a 51% attack indefinitely (feasible if most hashpower is becomes rentable by the highest bidder).
• IE, IN, IEN defined similarly.
• S0: The adversary can cause a network partition longer than k blocks (or one happens by accident).

(Feel free to edit this comment to add more as you see fit, so that the list is all in one place.)

Ideally, the defense should have no effect (with high probability) unless there is at least an F0 adversary present.

An I0 adversary can continually cause rollbacks and keep the network offline indefinitely if we err on the side of halting the network when there's a rollback, although they would have little on-chain financial incentive to do so. They might have off-chain incentive, like shorting Zcash, or if they just want to take down the network. Continuing operation of the network in this case would require an entirely new consensus mechanism.

FEN seems like the right model to me; we should strive to prevent rollback attacks by FEN adversaries. If we have to assume the adversary is weaker than FEN, then FE is more reasonable than FN. This is because it would be easier for a smallish number of notaries to defend themselves against FN adversaries by connecting to the network from many (secret) vantage points, compared to requiring every possible victim of a rollback attack to do the same.

[leto]

@defuse that is an extremely useful threat model, thank you.

Komodo has been running a system similar to what is described in this issue, for the "Consensus-enforced Static Roster Notary Policy" for about 2 years, and currently protects about 50 blockchains from rollback/re-org/double spent attacks. Various exchanges use it, and we actively see attempted re-org attacks, which fail.

If Zcash adopts a similar system (which I support), some questions to think about are:

• How many notaries will you have?
• Who will run notary nodes and what are their financial incentives to do so?
• What happens when X% of notary nodes are hacked/compromised/evil/offline?

I am interested to see how the Zcash community approaches and solves these issues. This document gives an overview of KMD notaries, from the perspective of adding them to an external coin:
https://github.com/leto/mastering_komodo_dpow/blob/master/mastering_komodo_dpow.md

[nathan-at-least]

What about adding a feature that requires the block hash at height N must be foo? We've had multiple conversations about this and there are probably tickets that should be cross-linked here.