Implement checkpointing

d1ll0n commented 4 years ago

Purpose

Most blockchains require an ability to checkpoint, save and revert database states. This library should support this kind of functionality, as it is generally useful and is a prerequisite for many blockchain designs.

Functions

The functions that should be supported are:

checkpoint() - mark the current database state as something that can be returned to
commit() - apply all the changes which have been applied since the last checkpoint to the underlying database, then remove the checkpoint
revert() - undo all the changes which have occurred since the last checkpoint and delete the checkpoint

Process

The merkle-patricia-tree library supports checkpointing and uses a similar underlying data store to that used by this library. We should take the methods used by MPT to implement checkpointing and apply them to the SMT library.

Scratch Database MPT has a database wrapper called a scratch database. The scratch wrapper takes an existing database and saves it as the "upstream" database, then creates a new in-memory database which is the "scratch" database. When it is called on to retrieve a key from the database, it first checks if the scratch database contains the requested key. If it does not contain the key, it queries the upstream database.

Checkpoint When the merkle tree is checkpointed, the current database is used to create a scratch database, which is set as the internal database.

Commit When a checkpoint is committed, a read stream on the scratch database and a write stream on the upstream database are created. All the key-value pairs in the scratch database are written to the upstream database, then the upstream database is set as the internal database and the scratch database is deleted.

Revert When a checkpoint is reverted, the upstream database is set as the internal database and the scratch database is deleted.

Questions

How will this affect root hash derivation, if at all?

d1ll0n commented 4 years ago

I began working on some of the needed functionality in the checkpoints branch. Here's the commit with some of the code for a scratch database and checkpoint tree.

karlfloersch commented 4 years ago

Just saw this! Excited for this feature!!!

d1ll0n / sparse-merkle-tree