Add trie support for "pruned tries"

[jochem-brouwer]

There are many (?) cases where one would just want to get the root of the trie and not care about older versions of the trie (i.e. setRoot to rollback to an older version of the root). However, it seems that currently the trie always keeps track of older versions ("archive" mode), which is not desired in some situations. There should be a flag which allows pruning older versions of the trie - if one writes to the same key then the old value of the key should be destroyed and the new value should be added.

const { Trie, LevelDB } = require('@ethereumjs/trie')
const { Level } = require('level')

const trie = new Trie({ db: new LevelDB(new Level('MY_TRIE_DB_LOCATION')) })

async function test() {
  await trie.put(Buffer.from('test'), Buffer.from('1'))
  await trie.put(Buffer.from('test'), Buffer.from('2'))
  await trie.put(Buffer.from('test'), Buffer.from('3'))
  await trie.put(Buffer.from('test'), Buffer.from('4'))
  await trie.put(Buffer.from('test'), Buffer.from('5'))
  await trie.put(Buffer.from('test'), Buffer.from('6'))

  // this logs 7 keys but I only want 1 key to be stored with the value 6
  console.log(await trie.db._leveldb.keys().all())
}

test()

Thanks @faustbrian for this test case.

[holgerd77]

Just some thoughts, not sure if this is going too far here, but since I already had them I thought that I could write them down. 😋

Just thought that this collides a bit with the trie library inheritance structure we have atm since this pruned Trie will likely (?) not be a checkpointed one (and if it turns out it rather is in the structure we come up with the following thoughts would still make sense...).

So the thing is: I wonder if we have the optimal hierarchy with Trie -> CheckpointTrie -> SecureTrie. This is already artificially limiting since this leads to the situation that a SecureTrie by design also always is a CheckpointTrie, which is from a logical standpoint totally unrelated. So I wonder if we would want to replace the SecureTrie class by a simple secure option in the base trie, and if this option is set just route everwhhere where something is hashed in the SecureTrie context (mostly a key) through a simple private helper function like:

_applySecure(value) { // Please come up with a better name here
  if (this.secure) {
    return this.hash(value)
  }
}

This should lead to the same result and would free us from the limitations of the current design (which might be helpful in other cases as well).

Ok, just a thought, might have down-sides. 😋

[faustbrian]

Just thought that this collides a bit with the trie library inheritance structure we have atm since this pruned Trie will likely (?) not be a checkpointed one (and if it turns out it rather is in the structure we come up with the following thoughts would still make sense...).

At least for my use-case I would still need it to support checkpointed and/or secure so that I can make copies and overwrite on-disk writes by those copies 😅

[faustbrian]

I'm not sure if adding more and more options is really the right way. The constructors and options are already fairly complex. Wouldn't composition make a lot more sense? Then you could do decorateCheckpoint(decorateSecure(new Trie())) and get a trie instance that has all kinds of behaviours without having to deal with inheritance or more and more flags and options. This would be more of a functional approach.

[holgerd77]

I'm not sure if adding more and more options is really the right way. The constructors and options are already fairly complex. Wouldn't composition make a lot more sense? Then you could do decorateCheckpoint(decorateSecure(new Trie())) and get a trie instance that has all kinds of behaviours without having to deal with inheritance or more and more flags and options. This would be more of a functional approach.

I get your point, also I am totally interested in the composition pattern you proposed, we would strongly need this e.g. to rework the tx library at some point, since this is also based - inappropriately - on inheritance at the moment, and this is getting more and more clunky with the addition of new tx types since new types do not necessarily inherit the features from old types but just swap out selected features or completely omit some.

Could you expand on how you would technically implement this? I looked into TypeScript mixins some time ago but was coming to the conclusion that this might have too many side effects for the pure JavaScript world, so I dropped this specific one. So if you have got a small code example that would be great! 🙂

---

In this specific case I have still a mild tendency that (yet another 😋) option would do it. Methods from base trie and secure trie are really 1:1 the same (if I have not overlooked something), also implementation structures 1:1 align, and this could be really completely encapsulated with this one internal method I suggested above (so it would actually lead to the deletion of a lot of code).

I also feel it a bit easier for people to upgrade, since they could stay in the same initialization framing with just changing the trie name to create (new SecureTrie -> new CheckpointTrie) and add the option.

That said, tendency is really mildly here. I am very open to let me convince, either if you have a very strong opinion here or if others from the team chime in. 😋

[holgerd77]

rework the tx library at some point

Actually this is so important that I would somewhat be inclined to eventually even still do in this release round it if you come up with a robust pattern for that. Tx types with new signature schemes or whatever new stuff (e.g. the sharding tx type) are crumbling in.

[faustbrian]

For now I think adding an option is fine, was more talking long-term. Don't have any concrete snippet at hand for the trie package but the gist of it is basically https://mskutle.dev/blog/object-composition-in-javascript like that post. I'll take a look at the tx library on the weekend and check if there's something we can do quick and clean for composition.

[faustbrian]

@holgerd77 Took a look at a few packages over the last days and moving them to a more functional approach is quite an undertaking so this should probably be something that gets properly planned for the next batch of major releases rather than rushing it for the sake of having it.

[holgerd77]

@holgerd77 Took a look at a few packages over the last days and moving them to a more functional approach is quite an undertaking so this should probably be something that gets properly planned for the next batch of major releases rather than rushing it for the sake of having it.

Yes yes, you are very much totally right. This was likely just some "wish-thinking". It's mainly the tx library as a candidate "no 1" for this, since this is getting so broad with the tx type construct, but I guess we can very much still live with the current design for another year or so and plan and execute on some substantial and thought through rewrite along.

[faustbrian]

I'll work on a more functional-style PoC for the Trie library as I find time over the next weeks so that could maybe serve as a foundation for planning further changes.

[faustbrian]

@jochem-brouwer what do you estimate how long this would take once you tackle it? Saw that assigned the hours effort label.

[jochem-brouwer]

@faustbrian I'd say about 4 hours, but this depends on a few assumptions which I made in order to implement it. If that works then it should be doable in that time, but if I find some hiccups then this would take longer. In my head this would work, but not sure if it actually does :smile:

There is a structural question here though which we have raised before; ideally, Trie should use decorators for SecureTrie (hash keys) and CheckpointTrie (allow checkpointing). If we also add PrunedTrie then I'm not sure if we should add this as decorator as well - we can also just move this as option inside Trie (so the base trie)?

[faustbrian]

I would probably keep the decorators for another major release and go with an option for now unless a subclass is required to keep it maintainable due to the complexity. I'm currently toying around with a more functional programming style trie and there's quite big changes in how it's used and it feels a bit out of place with all the other libraries being class based and heavily making use of inheritance.

I'll probably try to open a PR with a preview in September when I have a bit more time to polish it and iron out some last quirks.