Trie pruning does not work with variable-length keys

[jochem-brouwer]

To reproduce, change this into prune.spec.ts:

  it('should prune when keys are updated or deleted (with `useRootPersistence` enabled)', async (st) => {
    for (let testID = 0; testID < 10000; testID++) {
      const trie = await Trie.create({ useNodePruning: true, useRootPersistence: true })
      const keys: string[] = []
      for (let i = 0; i < 100; i++) {
        keys.push(crypto.randomBytes(Math.floor(Math.random() * 31) + 1))

Either the prune verifier throws, or we get a stack underflow error when putting key/values.

[jochem-brouwer]

This is most likely caused by the fact that BranchNodes and ExtensionNodes now can have values (as opposed to hashed tries). This could be an entry-point to figure out what is going wrong in the pruning.

[holgerd77]

How would you judge the importance of this issue? 🤔 Was this triggered along a discussion with @faustbrian ?

[faustbrian]

@holgerd77 it was. Our application keeps crashing at one point because the trie gets corrupted if we use the pruning with tries that use variable-length keys.

[holgerd77]

@holgerd77 it was. Our application keeps crashing at one point because the trie gets corrupted if we use the pruning with tries that use variable-length keys.

Ah ok, thanks! And did you (Jochem and you) made some way solving this issue, e.g. in the chat? If so, can you copy some first solution suggestions or the like over? That would be helpful here.

[jochem-brouwer]

Hi @holgerd77, we have only discussed how to reproduce it (see the code posted) and I also noted that it is likely due to ExtensionNodes/BranchNodes now having values (which is also in the issue) - so all information is here :)