[proposal]: implement a method that could create a sub-range proof from the existing `Proof`
Opened this issue · 1 comments
The current implementation of Proof allows to prove the inclusion of leaves only within the boundaries which were used during proof creation. In case we need a smaller proof for the same row, we have to traverse the tree and collect subtree roots again. But in fact, having proof and leafHashes are enough to recompute the new proof in place, without tree traversing.
Having a row that contains 8 shares(leaves), where the first 6 shares have the same namespace.ID:
+-----+-----+-----+-----+-----+-----+-----+-----+
| s0 | s1 | s2 | s3 | s4 | s5 | s6 | s7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
Proof for this row will be:
Proof {
start = 0
end = 6
nodes = [][]byte {subtreeRoot([s6;s7]}
}
At some point we need the proof for [s2;s4), so instead of traversing the tree and getting proof for these indexes, we can recompute using existing proof.
//
// Node0_8 Tree Root
// / \
// / \
// Node0_4 Node4_8 Non-Leaf Node
// / \ / \
// / \ / \
// Node0_2 Node2_4 Node4_6 Node6_8 Non-Leaf Node
// / \ / \ / \ / \
// Node0_1 Node1_2 Node2_3 Node3_4 Node4_5 Node5_6 Node6_7 Node7_8 Leaf Hash
// 1 2 3 4 6 7 8 9 Leaf namespace
// 0 1 2 3 4 5 6 7 Leaf index
If we'll take a look at this picture, to prove [s2;s4), we would need Node0_2(we can compute it by hashing s0 and s1), Node4_6(we can compute it by hashing s4 and s5) and Node6_8(already have it in proof.nodes).
This feature will be very helpful for blob service v0.1(cc @nashqueue), where we can have multiple blobs per namespace within the row, but the final indexes for the proof we can have only after fetching and verifying shares.