Merkleization

[Scooletz]

Implement Merkleization for the tree

• precommit hook for injecting Merkleization Merkle foundations with pre-commit hook #96
• serialization of Branch, Leaf and Extension to a Span (De)serialization of Merkle Nodes #98
• calculation of Keccaks for the nodes Merkle Node Keccak #104
• capturing all keys inserted in a block and passing them as the precommit to the Merkleization Commit information #111
• constructing the Merkle root hash by walking the keys from the above Merkle construct introduced #113
• tracking the dirty status for Merkle tree nodes Merkle construct introduced #113
• deletes Merkle construct introduced #113
• Keccak memoization
• storage handling (separate storage in block and bottom up calculation)
• squashing into PagedDb

The last 3 will be addressed in separate issues.

[emlautarom1]

To start working on this, I suggest writing some test on the current Nethermind client (here, probably: https://github.com/NethermindEth/nethermind/blob/22cc2b238e72e59a28c4b9e99019a4a145cc5895/src/Nethermind/Nethermind.Trie.Test/TrieTests.cs#L26) and check what we get as the RootHash. Then, migrate those tests into Paprika and use the obtained hashes as expected values during testing.

[emlautarom1]

Following the approach described above, I've written the following test in the Nethermind client (NC moving forward) and translated it into Paprika:

[Test]
public void Single_account()
{
    MemDb memDb = new();
    using TrieStore trieStore = new(memDb, Prune.WhenCacheReaches(1.MB()), Persist.EveryBlock, _logManager);
    PatriciaTree patriciaTree = new(trieStore, _logManager);

    var key = new Keccak(new byte[] { 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7 });
    var account = new Account(23, 13);

    patriciaTree.Set(key.Bytes, new AccountDecoder().Encode(account).Bytes);
    patriciaTree.Commit(blockNumber: 0);
    patriciaTree.UpdateRootHash();

    var rootHash = patriciaTree.RootHash;
    TestContext.WriteLine(rootHash);
}

This, translated to Paprika looks something like:

[Test]
public void Single_account()
{
    using var db = PagedDb.NativeMemoryDb(SmallDb);

    var key = Values.Key0;
    var account = new Account(Values.Balance0, Values.Nonce0);

    using (var batch = db.BeginNextBatch())
    {
        batch.Set(key, account);
        batch.Commit(CommitOptions.FlushDataAndRoot);
    }

    using (var batch = db.BeginReadOnlyBatch())
    {
        var rootHash = batch.GetRootHash();
        var expectedRootHash =
            new Keccak(Convert.FromHexString("E2533A0A0C4F1DDB72FEB7BFAAD12A83853447DEAAB6F28FA5C443DD2D37C3FB"));

        Assert.That(rootHash, Is.EqualTo(expectedRootHash));
    }
}

Key and Account are expected to be the same in both projects.

This raises a couple of questions:

• Is the NC test setup (ex. memDb, trieStore) and Paprika test setup (ex. NativeMemoryDb) correct?
• Is NC serializing the Account in the same way as Paprika?
• Could the blockNumber required when committing in NC be problematic?
• I added GetRootHash to the IReadOnlyBatch interface for now. Is that correct, or should we define it somewhere else?

[emlautarom1]

As for testing, eventually I think it could be useful to have some sort of test generator on NC: this generator would randomly produce a sequence of actions (setting, committing, ???), execute them, compute the root hash, and then save the sequence into a file. Then, Paprika could load those files, run the same actions, compute the root hash and validate it against the expected hash.

[LukaszRozmej]

As for testing, eventually I think it could be useful to have some sort of test generator on NC: this generator would randomly produce a sequence of actions (setting, committing, ???), execute them, compute the root hash, and then save the sequence into a file. Then, Paprika could load those files, run the same actions, compute the root hash and validate it against the expected hash.

why not bring Nethermind Client modules to Paprika or Paprika to Nethermind Client for this and actually have it integrated? Or create a 3rd project that would integrate and fuzz both and then compare.

[Scooletz]

This raises a couple of questions:

* Is the NC test setup (ex. `memDb`, `trieStore`) and Paprika test setup (ex. `NativeMemoryDb`) correct?
* Is NC serializing the Account in the same way as Paprika?
* Could the `blockNumber` required when committing in NC be problematic?
* I added `GetRootHash` to the `IReadOnlyBatch` interface for now. Is that correct, or should we define it somewhere else?

What NC does it uses the RLP serialization of a TreeNode that is of type of Leaf and then hashes it. It uses the idiomatic way of storing nodes. In Paprika if you'd like to get a hash of a leaf, you need to gather parts, write their RLP and then Keccak the output.

I don't think the block number is problematic at all, as Paprika needs to deliver a single hash at the end of the day. The hash is the hash of the state tree. The rest, how it's used etc. it's up to NC.

It's fine to have GetRootHash it there for now and discuss later. Especially, that once #88 is merged the API usage will change a bit. I think it should not impact your work as the underlying premise is to still be working with the existing components of the tree (data pages etc.)

As for testing, eventually I think it could be useful to have some sort of test generator on NC: this generator would randomly produce a sequence of actions (setting, committing, ???), execute them, compute the root hash, and then save the sequence into a file. Then, Paprika could load those files, run the same actions, compute the root hash and validate it against the expected hash.

That would be the ultimate testing scenario. Initially, it'd be great to have a suite of unit tests that are capable of showing that basic scenarios are covered. Unfortunately one needs to write the same tests with NC first so that the value is calculated properly. We could have a submodule for NC or build some parts as packages to be reused.

[LukaszRozmej]

For parallelization - if you can flatten the work items, then you can easily parallelize the whole process, regardless of branching. Even if you can't it is possible to parallelize it based on some counter. In NC we use Semaphore for that and either visit children in single-threaded manner if threads are saturated or invoke a multi-threading visit if there are threads available.

[Scooletz]

Memoization will be addressed at #120

[Scooletz]

Storage will be handled at #121

[Scooletz]

The PageDb component will be handled at #122

[Scooletz]

The leftovers are in separate issues.