Trie: implement createRangeProof

[jochem-brouwer]

Related to #1054

createRangeProof allows users to feed a start key and an end key (unhashed), where the returned proof can be fed into verifyRangeProof in order to prove the range. (This can also be used in snap sync)

Note: this is not optimal, because the optimized version would require a flat key/value database. This implementation naively walks the trie, and is thus I/O heavy.

Super WIP.

[codecov[bot]]

Codecov Report

Merging #2243 (2b470ca) into master (a87f179) will decrease coverage by 0.09%. The diff coverage is n/a.

:exclamation: Current head 2b470ca differs from pull request most recent head 9a4bf0d. Consider uploading reports for the commit 9a4bf0d to get more accurate results

Flag	Coverage Δ
block	92.83% <ø> (+0.05%)	:arrow_up:
blockchain	88.47% <ø> (+0.08%)	:arrow_up:
client	87.05% <ø> (-0.03%)	:arrow_down:
common	98.09% <ø> (-0.01%)	:arrow_down:
devp2p	92.48% <ø> (+0.17%)	:arrow_up:
ethash	∅ <ø> (∅)
evm	79.11% <ø> (+0.02%)	:arrow_up:
rlp	∅ <ø> (∅)
statemanager	88.47% <ø> (+0.30%)	:arrow_up:
trie	?
tx	97.98% <ø> (-0.01%)	:arrow_down:
util	92.33% <ø> (ø)
vm	85.31% <ø> (+0.04%)	:arrow_up:

Flags with carried forward coverage won't be shown. Click here to find out more.

[jochem-brouwer]

not ok 1 Error: invalid two edge elements proof: the length of firstKey should be equal to the length of lastKey
  ---
    operator: error
    stack: |-
      Error: invalid two edge elements proof: the length of firstKey should be equal to the length of lastKey
          at verifyRangeProof (/home/jochem/Documents/ejs/ethereumjs-monorepo/packages/trie/src/proof/range.ts:494:11)
          at Trie.verifyRangeProof (/home/jochem/Documents/ejs/ethereumjs-monorepo/packages/trie/src/trie/trie.ts:729:28)
          at Test.<anonymous> (/home/jochem/Documents/ejs/ethereumjs-monorepo/packages/trie/test/proof.spec.ts:181:16)
          at processTicksAndRejections (node:internal/process/task_queues:96:5)

Right we do not support this. (Geth also does not support this at this point)

[jochem-brouwer]

Hmm OK now I get

not ok 1 Error: invalid keys order
  ---
    operator: error
    stack: |-
      Error: invalid keys order
          at verifyRangeProof (/home/jochem/Documents/ejs/ethereumjs-monorepo/packages/trie/src/proof/range.ts:427:13)
          at Trie.verifyRangeProof (/home/jochem/Documents/ejs/ethereumjs-monorepo/packages/trie/src/trie/trie.ts:729:28)
          at Test.<anonymous> (/home/jochem/Documents/ejs/ethereumjs-monorepo/packages/trie/test/proof.spec.ts:184:16)
          at processTicksAndRejections (node:internal/process/task_queues:96:5)
  ...

The keys seem to be in right order though, so thats weird.

[jochem-brouwer]

OK had to take some time to find some gotcha's here, but this is ready for a first round of reviews. I'm not entirely sure about the implemented API and the code is also a bit dirty, but the tests at least show that the 4 cases (have to check if these are all cases).

@g11tech @scorbajio Do you guys want to give this a first look? I need to add tests same as in #2203 so we can randomly start to test big random tries.

[jochem-brouwer]

OK, the random range proof is failing, so there is something wrong here.

[g11tech]

OK had to take some time to find some gotcha's here, but this is ready for a first round of reviews. I'm not entirely sure about the implemented API and the code is also a bit dirty, but the tests at least show that the 4 cases (have to check if these are all cases).

@g11tech @scorbajio Do you guys want to give this a first look? I need to add tests same as in #2203 so we can randomly start to test big random tries.

thanks @jochem-brouwer for this awesome PR! will have a look and try it out and hopefully we can push this to the goal line this week!

[g11tech]

@jochem-brouwer i have digged into the PR, looks incredible :fire: , will try next running it to get a feel of the walkTrie helper :+1:

[scorbajio]

Hmm OK now I get

not ok 1 Error: invalid keys order
  ---
    operator: error
    stack: |-
      Error: invalid keys order
          at verifyRangeProof (/home/jochem/Documents/ejs/ethereumjs-monorepo/packages/trie/src/proof/range.ts:427:13)
          at Trie.verifyRangeProof (/home/jochem/Documents/ejs/ethereumjs-monorepo/packages/trie/src/trie/trie.ts:729:28)
          at Test.<anonymous> (/home/jochem/Documents/ejs/ethereumjs-monorepo/packages/trie/test/proof.spec.ts:184:16)
          at processTicksAndRejections (node:internal/process/task_queues:96:5)
  ...

The keys seem to be in right order though, so thats weird.

I'm not seeing this error. It might be from the randomized trie tests, though.

[jochem-brouwer]

Follow-up PR #2672