Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[proposal]: implement a method that could create a sub-range proof from the existing Proof #218

Open
vgonkivs opened this issue Jul 10, 2023 · 1 comment

Comments

@vgonkivs
Copy link
Member

vgonkivs commented Jul 10, 2023

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.

@staheri14
Copy link
Contributor

@vgonkivs As discussed previously, the idea of extracting proofs for smaller ranges from namespace proofs for larger ranges makes sense to me. 👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants