Feature/Enhancement Request: sparse Merkle tree

[k98kurz]

Feature or Enhancement?

• (x) New feature
• ( ) Enhancement of existing feature

Description

Development on this started a while ago, but it was not completed.

• Remove custom serialization and use packify instead
• Sparse tree generation
• VM updates
• Working inclusion proofs
• Unit/e2e tests for tree generation and inclusion proofs
• Implement exclusion proofs (note VM changes in comments, if any)
• Unit/e2e tests for exclusion proofs

Additional context

• What's a Sparse Merkle Tree?
• Sparse Merkle Trees
• Efficient Sparse Merkle Trees

[k98kurz]

Exclusion proofs are fairly easy: just provide a valid proof from the indexed null node that would have been the location of the requested node. Editing the original issue to break out the individual tasks a bit further.

[k98kurz]

This whole thing is rather convoluted compared to a regular Merkle tree, so I am rescheduling this for a future release.