Revert note commitment and history trees when forking non-finalized chains

[teor2345]

Motivation

When Zebra forks a non-finalized chain, it rebuilds the note commitment trees from the finalized tip.
But this can execute 100 blocks worth of note commitment tree updates, which uses a lot of CPU.

This change is a high priority for miners. They are unlikely to use Zebra unless it is fixed, because it prevents them mining 1-2 blocks after each chain fork.

We're seeing rebuild times of around 75 seconds, which is way too long:

2022-07-20T20:34:08.026902Z INFO {zebrad="b52b10c" net="Main"}:{peer=Out("3.72.134.66:8233")}:msg_as_req{msg="inv"}:inbound:download_and_verify{hash=00000000017131670f50301f97d80699baaef991ffed0c4ec9b6a0b0c189e587}:state: zebra_state::service::non_finalized_state::chain: finished rebuilding note commitment trees after a non-finalized chain fork rebuild_time=75.654621465s fork_height=Height(1744525) fork_tip=block::Hash("0000000000f4dd1105f94c06f28189ebdd60c0895d8931486847cce3278590e5")

Consensus Rules

The consensus rules require the trees to match the chain tip, including all the parent blocks back to genesis.

The revert needs to happen correctly, so the trees match the new fork tip block. (Forking is an efficiency thing, the consensus rules don't specify how to do forks.)

If we remove duplicate storage of tip trees by height and as their own field, we will only have to update them in one place. This makes keeping them consistent very easy.

Designs

Instead of rebuilding the trees from the root, we should remove the trees and anchors that are above the fork.

Refactors:

• replace tip sprout, sapling, orchard, history tree fields with methods that do a lookup using the tip height

Change:

• during a fork, revert sprout, sapling, orchard, history trees by removing anchors and trees above the fork height in revert_chain_with() for sprout, sapling, orchard shielded data, and history trees
• remove the code that rebuilds the history trees in rebuild_trees_parallel()

Cleanup:

• remove Chain::with_trees() and use derive(Clone) instead
• remove unused tree arguments from Chain::fork()
• cleanup any methods in NonFinalizedState that call these methods

Related Work

This might be needed by mining pools.

We added a log in PR #4795, which told us this can take around 75 seconds.

[conradoplg]

Note that it's non-trivial to remove nodes from a Frontier (at least I couldn't figure it out quickly when I tried). But since we store the trees for each height now, we can just start from the fork point and add the new nodes.

[teor2345]

We're seeing rebuild times of around 75 seconds, which is way too long:

2022-07-20T20:34:08.026902Z INFO {zebrad="b52b10c" net="Main"}:{peer=Out("3.72.134.66:8233")}:msg_as_req{msg="inv"}:inbound:download_and_verify{hash=00000000017131670f50301f97d80699baaef991ffed0c4ec9b6a0b0c189e587}:state: zebra_state::service::non_finalized_state::chain: finished rebuilding note commitment trees after a non-finalized chain fork rebuild_time=75.654621465s fork_height=Height(1744525) fork_tip=block::Hash("0000000000f4dd1105f94c06f28189ebdd60c0895d8931486847cce3278590e5")

So this is a high priority.

[upbqdn]

Note that it's non-trivial to remove nodes from a Frontier (at least I couldn't figure it out quickly when I tried).

I think Frontier doesn't support that operation at all.

[teor2345]

Zebra's performance is good enough for now.

[teor2345]

We're not making changes of this size after tagging the release candidate.

[teor2345]

This is mitigated by #5257, which runs these slow updates in a separate thread.

[teor2345]

@mpguerra we've been told by a mining pool that fork speed is a significant issue for them.

I've updated this ticket based on the current code, we've done most of the work here already, due to other state tickets.

[mpguerra]

Thanks for the updates! This seems like a significant change so, in terms of scheduling, we'd probably want to evaluate how this would affect the stable release candidate series and the audit.

[teor2345]

Thanks for the updates! This seems like a significant change so, in terms of scheduling, we'd probably want to evaluate how this would affect the stable release candidate series and the audit.

I think this change is a high priority for miners. They are unlikely to use Zebra unless it is fixed, because it prevents them mining 1-2 blocks after each chain fork.

Here is my evaluation of the complexity of this change:

This change is all contained within the chain.rs module. It should change less than 100 lines of code. As part of this change, we can delete some complex tree update code that's no longer needed.

This will fix a current performance bug in the stable release candidate series. We almost fixed this bug before the audit, because the performance is much worse than zcashd. But we ran out of time.

We already have unit and full sync tests for this code, so it is a low risk change.

[teor2345]

I've added a note about the consensus rules to the ticket description. If we do the change the way I described it in the ticket, then keeping the consensus rules actually becomes a lot simpler.

So I can't see anything complicated about this ticket. Maybe Deirdre or Conrado could double-check?

[mpguerra]

So I can't see anything complicated about this ticket. Maybe Deirdre or Conrado could double-check?

@conradoplg do you mind double checking this?

[conradoplg]

I agree it's not complicated, the old code was basically a workaround, and we will able to replace it with much neater code. This part of the code is well tested so it is unlikely that a bug will be introduced. The hardest part will understanding the old code, but I can help if whoever implements this is not familiar with it.

[teor2345]

I can also help with implementation or reviews.

[mpguerra]

moving this to Sprint 3, we should prioritise testing instead for this sprint