This is to save some nodes when u r fetching a batch of Merkle proofs/witnesses, say for one block, by more than getting common internal nodes only once.
1-The idea is not purely mine, it is from the paper I found under
Sparse Merkle Trees (SMT) in their terminology.
"
Efficient Sparse Merkle Trees
Caching Strategies and Secure (Non-)Membership Proofs"
https://eprint.iacr.org/2016/683.pdf2-Although different you can find some problem isomorphism if we consider fetching a batch of proofs, say for a block needed by a Pollard node, as getting a sparse subtrees from the original trees in the forest.
3-Anyways the idea is more understandable through figures, our famous tree
Now if we want proofs say for 3,5,6
They will be
2,8,13,14
4,11,12,14
7,10,12,14
Which we can get 12&14 once, making the batch size 4+3+2=
9 nodes
They show up further improvement:
They say
- 12 can be recalculated from 2,8
- 13 from 10,11
- and even more 10,11 also can be calculated from 4,7 (since we have 5,6 to validate)
- Thus the only needed nodes are 2,8,4,7
=⟩
4 instead of 9
Another example could be say 0,7 (to see the effect of being scattered at the tree borders)
Proofs would be:
P0: 1,9,13,14
P1: 6,10,12,14
12,13,14 can be calculated from available data
(12 from 0,1,9 & 13 from 10,6,7)
So it is enough to fetch
1,6,9,10 i.e. 4 nodes for 2elements
There is a formula & recursive fn on what to fetch& what to calculate that I still have to figure out. As a first thought we could say
any internal(inner) node with a required to validate leaf under one of its children is not needed; the other child will be selected in an earlier step as a sibling so we can re calculate this one.
