[proposal]: implement a method that could create a sub-range proof from the existing `Proof`
- Dominant language
- Go
- Stars
- 122
- Forks
- 53
- Avg merge
- 1d 15h
- Merged PRs (30d)
- 5
Description
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.
Contributor guide
Research direction
Start by reading the existing Proof and leafHashes implementations, then trace how proof nodes are created and verified. Work through the provided eight-share example for the [s2;s4) range and define the method's expected inputs and output. Done means a smaller proof can be recomputed without traversing the tree and its verification behavior is covered by tests.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- cryptography
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100