Pessimistic Proof End-to-End Components

[bpfarmer]

Trying to braindump before I go on paternity leave (😅) and this has come up a few times, so I think that it's worth sketching out what exactly is needed to get the pessimistic proof generation working in production. Apologies if this already exists elsewhere!

There are a few steps:

1. CDK chain/zkEVM produces a block/batch. The relevant info for the PP is the new leaves added to the chain's LET and any claims made against other chains' LETs.
2. The chain must somehow provide the new LET leaves (BridgeExit), the set of claims (ImportedBridgeExit) to the service that is generating the pessimistic proof.
3. The service responsible for generating the pessimistic proof loads the nullifier set and local balance tree, computes required witness data for both trees, and then computes the changes from the chain's batch to both the nullifier set and local balance tree, before generating additional witness data necessary to prove that updates are valid.

Note: in the current version of the LocalBalanceTree it looks like we're loading the entire tree in memory in the proof. Given that this tree can track an unlimited number of tokens, we should instead pass in specific paths corresponding to each TokenAddress that is either claimed or withdrawn in the block.

4. The service generating the pessimistic proof passes witness data to the prover:
   • The set of ImportedLocalExitRoot, LocalExitTreePath, ImportedBridgeExit necessary for the PP to verify that a claim is valid.
   • The previous LocalExitRoot and set of BridgeExit necessary to build/verify the update to the network's LocalExitTree
   • The previous NullifierRoot and NullifierPath, NetworkNullifierPath required to verify updates to the nullifier set.
   • The previous BalanceRoot and BalancePath required to verify updates to the local balance tree.
5. The local Pessimistic Proof is generated.
6. A new GlobalExitRoot must be generated, and all instances of ImportedLocalExitRoot must be checked for inclusion in this GER. First, we prove that an imported LER is a subtree of a given LER, and then prove that the given LER is included in the GER. Ideally this is done off-chain in a proof, such that all PPs are aggregated and used to generate a new GER, and then we check subtree inclusion. However, it could also be done on L1.
7. The Pessimistic Proof is forwarded to L1 and verified on-chain.

I want to specifically call out (2) as a component that I haven't seen, and also note that there is non-trivial devops work required to run the proving service. I would defer to John Hilliard, but I don't think that proving will be super resource-intensive, but we should have a plan to actually run the prover in production.

I know that we're working on (3), (4), (5), but I think that (1), (2), (6), (7) haven't been started yet, and we don't have a concrete plan or resourcing for running (3), (4), (5) in a production environment. Happy to be corrected though!