Saving some internal nodes (siblings) in a proof batch if they're calculatable

[Shymaa-Arafat]

1-The idea is not purely mine, it is from the paper U 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
  =⟩ Four instead of 9
  

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 and we can re calculate it.

[adiabat]

Yes, all proof and verification code in this repo does this and has from the start.