Migrate simple Sparse Merkle tree #21
Assignees
Comments
vlopes11
added a commit
that referenced
this issue
Dec 8, 2022
This commit introduces the `SparseMerkleTree` and `TreeStorage`. The sparse merkle tree is a concrete structure that will provide the functionalities of a keyed naive SMT with inclusion proof. It introduces the `MerklePath` structure to fully encapsulate a merkle opening verification - however, it can be just converted into a vector of digests so it will be compatible with the opening prior to this commit. It also introduces the tree storage trait, a backend definition that will be the responsible to manage the state of a tree. This brings the advantage of decoupling the implementation logic of the merkle tree with its backend requirements, and will use `alloc::borrow::Cow` instead of either references or owned values to give further flexibility to the storage. Some storages will lock its own state to fetch a value, and they might provide values to multi-threaded applications - hence, extending the lock might not be desirable for fetched values. In such cases, the storage will have the option to return the value as owned, freeing it from its lifetime bound. There is a memory storage added that will provide in-memory tree storage, backed by `BTreeMap`. closes #21
vlopes11
added a commit
that referenced
this issue
Dec 8, 2022
This commit introduces the `SparseMerkleTree` and `TreeStorage`. The sparse merkle tree is a concrete structure that will provide the functionalities of a keyed naive SMT with inclusion proof. It introduces the `MerklePath` structure to fully encapsulate a merkle opening verification - however, it can be just converted into a vector of digests so it will be compatible with the opening prior to this commit. It also introduces the tree storage trait, a backend definition that will be the responsible to manage the state of a tree. This brings the advantage of decoupling the implementation logic of the merkle tree with its backend requirements, and will use `alloc::borrow::Cow` instead of either references or owned values to give further flexibility to the storage. Some storages will lock its own state to fetch a value, and they might provide values to multi-threaded applications - hence, extending the lock might not be desirable for fetched values. In such cases, the storage will have the option to return the value as owned, freeing it from its lifetime bound. There is a memory storage added that will provide in-memory tree storage, backed by `BTreeMap`. closes #21
vlopes11
added a commit
that referenced
this issue
Dec 8, 2022
This commit introduces the `SparseMerkleTree` and `TreeStorage`. The sparse merkle tree is a concrete structure that will provide the functionalities of a keyed naive SMT with inclusion proof. It introduces the `MerklePath` structure to fully encapsulate a merkle opening verification - however, it can be just converted into a vector of digests so it will be compatible with the opening prior to this commit. It also introduces the tree storage trait, a backend definition that will be the responsible to manage the state of a tree. This brings the advantage of decoupling the implementation logic of the merkle tree with its backend requirements, and will use `alloc::borrow::Cow` instead of either references or owned values to give further flexibility to the storage. Some storages will lock its own state to fetch a value, and they might provide values to multi-threaded applications - hence, extending the lock might not be desirable for fetched values. In such cases, the storage will have the option to return the value as owned, freeing it from its lifetime bound. There is a memory storage added that will provide in-memory tree storage, backed by `BTreeMap`. closes #21
vlopes11
added a commit
that referenced
this issue
Dec 8, 2022
This commit introduces the `SparseMerkleTree` and `TreeStorage`. The sparse merkle tree is a concrete structure that will provide the functionalities of a keyed naive SMT with inclusion proof. It introduces the `MerklePath` structure to fully encapsulate a merkle opening verification - however, it can be just converted into a vector of digests so it will be compatible with the opening prior to this commit. It also introduces the tree storage trait, a backend definition that will be the responsible to manage the state of a tree. This brings the advantage of decoupling the implementation logic of the merkle tree with its backend requirements, and will use `alloc::borrow::Cow` instead of either references or owned values to give further flexibility to the storage. Some storages will lock its own state to fetch a value, and they might provide values to multi-threaded applications - hence, extending the lock might not be desirable for fetched values. In such cases, the storage will have the option to return the value as owned, freeing it from its lifetime bound. There is a memory storage added that will provide in-memory tree storage, backed by `BTreeMap`. closes #21
vlopes11
added a commit
that referenced
this issue
Dec 12, 2022
This commit moves the previous implementation of `SparseMerkleTree` from miden-core to this crate. It also include a couple of new tests, a bench suite, and a couple of minor fixes. The original API was preserved to maintain compatibility with `AdviceTape`. closes #21
vlopes11
added a commit
that referenced
this issue
Dec 12, 2022
This commit moves the previous implementation of `SparseMerkleTree` from miden-core to this crate. It also include a couple of new tests, a bench suite, and a couple of minor fixes. The original API was preserved to maintain compatibility with `AdviceTape`. closes #21
vlopes11
added a commit
that referenced
this issue
Dec 12, 2022
This commit moves the previous implementation of `SparseMerkleTree` from miden-core to this crate. It also include a couple of new tests, a bench suite, and a couple of minor fixes. The original API was preserved to maintain compatibility with `AdviceTape`. closes #21
vlopes11
added a commit
that referenced
this issue
Dec 13, 2022
This commit moves the previous implementation of `SparseMerkleTree` from miden-core to this crate. It also include a couple of new tests, a bench suite, and a couple of minor fixes. The original API was preserved to maintain compatibility with `AdviceTape`. closes #21
vlopes11
added a commit
that referenced
this issue
Dec 13, 2022
This commit moves the previous implementation of `SparseMerkleTree` from miden-core to this crate. It also include a couple of new tests, a bench suite, and a couple of minor fixes. The original API was preserved to maintain compatibility with `AdviceTape`. closes #21
vlopes11
added a commit
that referenced
this issue
Dec 13, 2022
This commit moves the previous implementation of `SparseMerkleTree` from miden-core to this crate. It also include a couple of new tests, a bench suite, and a couple of minor fixes. The original API was preserved to maintain compatibility with `AdviceTape`. closes #21
vlopes11
added a commit
that referenced
this issue
Dec 14, 2022
This commit moves the previous implementation of `SparseMerkleTree` from miden-core to this crate. It also include a couple of new tests, a bench suite, and a couple of minor fixes. The original API was preserved to maintain compatibility with `AdviceTape`. closes #21
|
Closed by #27 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
We have an implementation of a simple SMT in the main Miden repo here. We should migrate this implementation to this crate, probably under
src/merkle/simple_smt.rs.We can improve the implementation and documentation during the migration process, but I would spend too much time on this.
The text was updated successfully, but these errors were encountered: