[Database] Parent-children approach and pruning

[ChihChengLiang]

Problem

As implemented in #619, we store the tree nodes using depth-index as the DB key and the node as value. This gives us a single tree view in the disk, so when the client restarts we don't have to resync from the genesis.

544 describe another way to store tree nodes in DB, which I'll call it parent-children approach. We use the parent node as key, and the left and the right children concatenated together as the value.

The difference between the two approaches is that the latter gives us a historical tree view. When we update a leaf in tree A and updates nodes to get the tree A', in depth-index approach the view of A is lost but the parent-children approach keeps it.

Here we discuss do we need historical tree views for the state tree and pubkey tree.

Do we need the historical state tree view? Probably no.

If a client learns an invalid batch, the client can just halt and wait for the invalid batch to be reverted. In this case, a single state tree view works fine.

If we want to demonstrate the client can withstand a long rollback in history, then we need historical state tree views. But this use case is rare and might be unnecessary.

Do we need the historical pubkey tree view? Probably no, either.

The tree root in BLSAccountRegistry is constantly updating, and the coordinator might be submitting batches whose committed account root is not the latest, or a least not the same one as the listening nodes.

It's fine for the syncer client as they only check signatures against public keys. The process requires no tree nodes. But for the watcher, they need to provide witnesses for the SignatureProof, which needs the historical pubkey tree view.

However, the watcher needs to remember the history of a relatively short time period, maybe a few l1blocks. So we can actually cache the witness and nodes in memory without worrying about the DB.

Solution

Close the issue and stick to the depth-index approach if @jacque006 and @kautukkundan agree with the arguments.

[jacque006]

Very well laid out @ChihChengLiang , given that overview I agree this can be closed

[kautukkundan]

yeah I agree after my previous doubt was resolved, I think we can keep it this way.

[ChihChengLiang]

Thanks for the feedback, let's close this.