SRI Zero-Knowledge Component: Sparse Merkle Tree

[biscuitdey]

Overview

Implement a Sparse Merkle tree to store the root of the Merkle Tree of the document to be baselined.

Reference

• Documentation
• References

Assumptions

• Sparse Merkle Tree will be stored in a private IPFS instance
• Sparse Merkle Tree will be accessible to and shared amongst all the participants of the Workgroup

Acceptance

• Able to insert a leaf into the tree
• Able to receive a proof on whether a leave exists in the tree or not
• All participants of the Workgroup able to access the tree

Tasks

• [ ] Construct a Sparse Merkle tree
• [ ] Insert a Leaf
• [ ] Create a proof of existence of a leaf
• [ ] Verify the proof of existence of a leaf

[Therecanbeonlyone1969]

There are two concepts here we need to distinguish and they may or may not be treated differently:

1. The state of a BPI Account which is the common agreed upon state (and its history) between the counterparties to an agreement. This state will typically be comprised of more than one document, and will evolve as more and more documents are added. When the state advances we need to verify that it advances correctly. That also means that the old state is no longer valid (replay protection), which also needs to be verified.
2. The state of a document advancing the state of a BPI Account, and the correctness of the document as compared to itself and the BPI Account state. That means that the proof of correctness must also contain a proof that the correct state of the BPI account is used in the verification of the document e.g. discount value and whether it is the current value.

That means we need several merkle trees, and not all of them must be sparse.

The BPI account state can be dense, the BPI account state no longer valid will require a sparse merkle tree. We might have a regular merkle tree representing the state of a document, the root of which will be represented in a leaf of the dense merkle tree.

These are just some initial thoughts of how the state of BPI Accounts and documents can be organized.

Please, suggest / improve away.