Topic: Saving some internal nodes (siblings) in a proof batch if they're calculatable (Read 86 times)

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.pdf

2-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.