0xpolygonmiden / crypto Goto Github PK
View Code? Open in Web Editor NEWCryptographic primitives used in Polygon Miden rollup
License: MIT License
Cryptographic primitives used in Polygon Miden rollup
License: MIT License
The MerklePath
structure assumes the input node is an argument of the verification
Lines 25 to 39 in 6bd6b9e
But MerklePathSet
injects the input node as the first element of the path
crypto/src/merkle/merkle_path_set.rs
Lines 33 to 64 in 66da469
And, when queried, it will remove it
crypto/src/merkle/merkle_path_set.rs
Lines 118 to 119 in 66da469
It should probably store the path only with the siblings, having a different strategy to store the leaf node, if required
After this refactor is done, MerklePathSet
should consume the MerklePath
functions to compute roots and verify openings.
This method is needed to support MASM implementation of Tiered STM. The signature of the method could be:
pub fn get_leaf_depth(&self, root: Word, index: u64) -> Result<u8, MerkleError>
This method would traverse the tree specified by the root
from the top and return as soon as it finds a leaf node (i.e., node with no children) or a root of an empty subtree.
The error conditions would be:
root
in the store.Right now we're trying to implement ECDSA ( over ec_ext5
curve ) signature verification routine in Miden assembly, for which all necessary underlying constructions are almost ready
But if you notice carefully, you'll see for this we had to write important cryptographic primitives inside test directory of https://github.com/maticnetwork/miden which is not good. I'd like to have all Miden related cryptographic requirements living here and get them imported as development dependencies for ensuring that test vectors can be generated on-the-fly and functional correctness of Miden assembly implementations can be ensured that way. This also makes dependency graph more modular which makes it easier to comprehend and finally audit.
So I'll move all these routines here ( now living here ) so that we have ECDSA ( over ec_ext5
curve ) keygen/ sign/ verify implemented.
Ideally, we'd use an official implementation, but I couldn't find any native Rust implementations. There is one project (PQ Cyrpto) which provides Rust bindings for C implementation. But I'm not sure that's the right way to go.
I think the verification part should be relatively simple to implement, but the signing part is quite complicated.
In terms of API we should expose, I think we should use a "compressed" public key, where the key is basically a hash of the actual public key. Then, the signature would consist of the actually signature + the expanded public key. For the hash function used to "compress" the key we should use RPO so that it is easy to "unhash" within the VM.
We want to add benchmarks to the repo which test how various hash functions perform against each other.
The hash functions to be included:
We should benchmark this on a few machines (e.g., AMD, Intel, Apple) and put a summary table in the main readme file.
The working group coordinator ensures scope & progress tracking are transparent and accurate. They will:
A tiered sparse merkle tree will be a compound of sparse merkle trees combined into tiers. It will map 256-bits keys to 256-bits values, and will extend the functionality of sparse merkle trees.
Keys and values are arrays of 64-bits field elements F
. We will use the last limb of the key to represent our traversing key
.
T
: Depth per tier, set to 16
.M
: Maximum number of tiers, set to 4
.D
: Maximum depth of the tree, set to T ā
M = 64
H({F}) -> F
: Hash primitive of choiceH_{t}({F}) -> F
: Hash in domain t
, where the maximum t = D = 64
H_0(depth) -> F
: Set of empty sub-tree constants for a target depth.Requirements:
H_0(depth) -> F
H_{t}({F}) -> F
Node(state, depth, index) -> Node Value: F
Traverse(state, bits) -> Target Node Depth Index: (F, F)
Traverse Key(Key, B) -> Bits: F
For a state
of the tree (i.e. root), given a key, it will lookup its structure and find the appropriate node for that key. This will be referenced as target node
within this document.
Lookup(Root, Key, Value) -> (Depth, Index)
For the first tier, we will:
bits := Traverse Key(Key, B)
for B = T = 16
Traverse key will get the most significant bits B
from the traversing key
of Key
.
V := H_{B}(Key, Value)
target node
via a traverse function (depth, index) := Traverse(state, bits)
The tree traversal is straightforward as it will be the same as a regular sparse merkle tree. For the sake of simplicity, we use below a T = 4
and a 8-bits key 0b10010110
.
We start from the orange root, traverse the green nodes in accordance to the most significant bits of the key, and finish at the purple target node. The index pair for that tree will be (depth = 4, index = 9)
.
N := Node(state, depth, index)
N
equals V
or H_0(depth)
, returns (depth, index)
. Otherwise, continue traversing until the next tier.For the second tier t = 2
, we will:
bits := Traverse Key(Key, B)
for B = t ā
T = 2 ā
16 = 32
N := H_{B}(Key, Value)
target node
via a traverse function (depth, index) := Traverse(state, bits)
V := Node(state, depth, index)
N
equals V
, returns (depth, index)
. If V = H_0(depth)
, returns (depth, index)
of the previous iteration.Otherwise, continue traversing until B = 64
. If we reach the maximum depth = D = 64
, returns (64, index)
, where index
is the traversed value for that maximum depth.
Requirements:
Order Leaves By Key({(Key, Value)}) -> {(Key, Value})
The last tier might contain multiple leaves per node. We introduce a Node Value Last Tier(leaves: {Key, Value}) -> F
procedure to compute the node values, and will behave as follows
leaves
via ordered leaves := Order Leaves By Key(leaves)
D = 64
as Node Value Last Tier(ordered leaves: {Key, Value}) -> H_64(ordered leaves)
Requirements:
H_{t}({F}) -> F
Last Tier Leaves(index) -> {(Key, Value)}
Lookup(Root, Key, Value) -> (Depth, Index)
Merkle Opening(Root, V, index, Merkle Path) -> boolean
Merkle Path(Root, depth, index) -> Merkle Path
Node(state, depth, index) -> Node Value: F
Node Value Last Tier(leaves) -> F
To check if a candidate leaf (Key, Value)
opens to a state Root
, we proceed as follows:
target node
via (depth, index) := Lookup(Root, Key, Value)
N := H_{depth}(Key, Value)
64
, fetch all leaves of the target node
via leaves := Last Tier Leaves(index)
, assert (Key, Value)
belongs to leaves
, and replace N := Node Value Last Tier(leaves)
V := Node(Root, depth, index)
target node
via P := Merkle Path(Root, depth, index)
Merkle Opening(Root, V, index, P)
Note: Both Merkle Path
and Merkle Opening
definitions doesn't belong to the scope of this document and are assumed to be known by the reader.
Requirements:
Fetch Pre Image(Root, depth, index) -> {F}
H_0(depth) -> F
H_{t}({F}) -> F
Last Tier Leaves(index) -> {(Key, Value)}
Lookup(Root, Key, Value) -> (Depth, Index)
Merkle Opening(Root, V, index, Merkle Path) -> boolean
Merkle Path(Root, depth, index) -> Merkle Path
Node(state, depth, index) -> Node Value: F
Node Value Last Tier(leaves) -> F
To check if a candidate leaf (Key, Value)
doesn't exist for a state Root
, we proceed as follows:
target node
via (depth, index) := Lookup(Root, Key, Value)
N := Node(Root, depth, index)
target node
via P := Merkle Path(Root, depth, index)
Merkle Opening(Root, V, P)
In order to prove non-membership, we need to open the pre-image of target node
and assert it doesn't contain the candidate leaf. The proof that we know a pre-image that will compute the opening correctly will suffice to prove the non-membership.
N = H_0(depth)
, then the proof holds.depth < D
, we fetch the pre-image (Key', Value') := Fetch Pre Image(Root, depth, index)
and assert N = H_{depth}(Key', Value') && Key != Key' && Value != Value'
. We can, alternatively, skip the value check as the key could independently verify the set membership - that would be up to the target use case.depth = D
, then we fetch leaves := Last Tier Leaves(index)
, assert (Key, Value)
doesn't exist in leaves
, and assert N = Node Value Last Tier(leaves)
.Requirements:
Fetch Pre Image(Root, depth, index) -> {F}
H_0(depth) -> F
H_{t}({F}) -> F
Insert Leaf(Root, N, depth, index, Key, Value) -> New Root: F
Last Tier Leaves(index) -> {(Key, Value)}
Lookup(Root, Key, Value) -> (Depth, Index)
Node(state, depth, index) -> Node Value: F
Node Value Last Tier(leaves) -> F
Traverse(state, bits) -> Target Node Depth Index: (F, F)
Traverse Key(Key, B) -> Bits: F
The insertion of a leaf (Key, Value)
for a state Root
should be implemented as follows:
target node
via (depth, index) := Lookup(Root, Key, Value)
N := H_{depth}(Key, Value)
V := Node(Root, depth, index)
V = H_0(depth)
, then Insert Leaf(Root, N, depth, index, Key, Value)
depth = D = 64
, then we fetch leaves := Last Tier Leaves(index)
, append (Key, Value)
to the set leaves
(note that a set cannot hold duplicated values), compute the node value N := Node Value Last Tier(leaves)
, and Insert Leaf(Root, N, depth, index, Key, Value)
Finally, if the previous cases aren't met, we have a collision. We should promote both leaves until they don't collide.
next tier depth := depth + T
(Sibling Key, Sibling Value) := Fetch Pre Image(Root, depth, index)
sibling bits := Traverse Key(Sibling Key, next tier depth)
target sibling node
via the traverse function (sibling new depth, sibling new index) := Traverse(state, sibling bits)
bits := Traverse Key(Key, next tier depth)
target node
via the traverse function (new depth, new index) := Traverse(state, bits)
If new depth = D = 64
, then we insert the sibling and leaf into their indexes using the previous method for the maximum depth.
Otherwise, if new index != sibling new index
, it means we can insert the nodes back into the tree:
Sibling N := H_{new depth}(Sibling Key, Sibling Value)
, then New Root := Insert Leaf(Root, Sibling N, new depth, sibling new index, Sibling Key, Sibling Value)
Note that this command should override the previous leaf from the set. It means it should behave the same as if we entirely removed the sibling from the set, and inserted it into the new depth and index.
N := H_{new depth}(Key, Value)
, then Insert Leaf(New Root, N, new depth, new index, Key, Value)
Finally, if new index = sibling new index
, we repeat the procedure, promoting the leaves to the next tier.
The Lookup
operation is used for all the routines. These are the requirements for its implementation.
H_0(depth) -> F
H_{t}({F}) -> F
Node(state, depth, index) -> Node Value: F
Traverse(state, bits) -> Target Node Depth Index: (F, F)
Traverse Key(Key, B) -> Bits: F
The remainder operations will require:
Fetch Pre Image(Root, depth, index) -> {F}
Insert Leaf(Root, N, depth, index, Key, Value) -> New Root: F
Last Tier Leaves(index) -> {(Key, Value)}
Merkle Opening(Root, V, index, Merkle Path) -> boolean
Merkle Path(Root, depth, index) -> Merkle Path
Node Value Last Tier(leaves) -> F
Order Leaves By Key({(Key, Value)}) -> {(Key, Value})
These implementations will require new VM instructions and/or advice provider modification:
H_{t}({F}) -> F
Hash in domain is currently not supported as VM instruction
Insert Leaf(Root, N, depth, index, Key, Value) -> New Root: F
We can map (depth, index) -> (Key, Value)
via the advice provider, but we cannot insert a leaf on an arbitrary index.
The advice provider will allow us to map values to sequence of values. This theoretically can solve any situation, but might be too resource demanding to work with. Example:
If I'm to implement the Node(state, depth, index) -> Node Value: F
, then I can do the following:
x := H(state, depth, index)
x -> v
This means we will have to store every node, not only as a node, but also as a value mapping.
If we have a way to perform a custom request that will take n
numbers as argument, we can easily implement more functions:
N
that will work as function selector(N, state, depth, index)
N
, the advice provider will know it should use the 3 arguments to fetch the node for the given state at depth+index, and return itThe VM supports a mtree_get
operation. This operation references a tree by its root. For the VM to work with the tree's data (for queries / updates / copies), the VM has to load the data into memory. This could be optimized to only load the necessary data in memory.
Open questions are: At which point will this be a good strategy? (code complexity vs. performance gains)
This is an example for current error:
Failed to compile test source.: ImportedProcModuleNotFound(ProcedureId([76, 6, 174, 102, 136, 197, 185, 191, 0, 2, 63, 207, 185, 182, 172, 255, 235, 226, 6, 56]))
The ProcedureId
is not useful to a human, so it would be useful to have the original name in there too.
Additionally it would be nice to have a levenshtein distance or something similar to propose a fix.
As it stands there is not way to load an instantiated data structure (Mmr
, Smt
, MerkleTree
) into the MerkleStore
. The MerkleStore
API expects iterators of a specific format depending on the structure being loaded. We should implement methods on Mmr
, Smt
, MerkleTree
that produce the required iterators that will allow the instantiated data structures to be loaded into the MerkleStore
.
ATM the first few characters in the search take a lot of time, subsequent runs are much faster, I assume it is because as the data is filtered down the search has to run on fewer entries and becomes faster.
Possible solutions:
Miden VM depends on RandomCoin
, RandomCoinError
, which are currently being imported from Winterfell. It would be better to import them from this miden-crypto
package instead.
We should add them to this package as re-exports and then update the dependencies in miden-vm
when the next version of this package is released.
We should add wrappers for BLAKE3 hash function into hash
module. These could be similar to the ones implemented in Winterfell. In terms of variants, would be great to have the following:
Blake3_256
- same as in Winterfell.Blake3_192
- same as in Winterfell.Blake3_160
- a version of BLAKE3 with output truncated to 20 bytes.It would be very useful to have no-std
support for the crypto crate. Most of the code should already support this, we just need to update crate metadata to enable this. We can do this similarly to how it is done in the main Miden repo.
Setup basic CI checks to assert the correctness of the implementation.
The same model used in Miden VM will be replicated here, that is:
next
Using this sample program:
begin
adv.keyval
end
Causes the VM to fail with:
thread 'main' panicked at 'internal error: entered unreachable code', assembly/src/assembler/span_builder.rs:154:13
On latest next
commit 1de0502d087ced0bb9d7e1d754669244c7c177a7 .
Update by @grjte on 2023/03/09:
we now intend to implement MerkleStore
to hold all Merkle-based data in the advice provider as described by @bobbinth in this comment below: #89 (comment)
One of the Merkle tree-based data structures we have is a MerklePathSet
. This data structure can be viewed as a set of Merkle paths resolving to the same root. Current limitation is that all paths must be of the same length - but I'm wondering if we can remove this limitation.
If we do, this updated data structure could be named PartialMerleTree
and it could look something like this:
In the above, we know node value at (index = 0, depth = 2)
but we don't know node value at (index = 0, depth = 3)
.
I think such a data structure shouldn't be too difficult to implement, and the nice thing is that it will work naturally with our mtree_get
and mtree_set
instructions for any node depth.
For mtree_set
specifically, we can easily replace a node in one PartialMerkleTree
with a root of another PartialMerkleTree
(assuming the combined depth doesn't exceed 64). However, we would not be able to replace a node in a PartialMerkleTree
with a root of a Sparse Merkle tree (or rather that would be a very expensive operation).
So, I'm wondering if we could take this a step further.
A MerkleStore
could be data structure similar to PartialMerkleTreee
but such that we allow nodes to be roots of empty subtrees at no extra cost. For example:
In the above, E2
is a root of an empty subtree of depth 2. Instead of storing all the leaves of this subtree explicitly, we just store E2
.
If we can implement this data structure efficiently (and I don't know if we'll run into some complications here), we could potentially replace other Merkle tree-based data structures with it. Specifically:
SimpleSmt
would be a special case of this data structure such that we know values of all leaves.MerkleTree
would also be a special case such that we know all the leaves and most of them are non-zero.TieredSmt
would also be a special case such that we allow leaves only on specific tiers and impose additional structure on the leaf nodes.MerklePathSet
.The main benefit (the way I see it) is that we end up with a single data structure which is easily "composable" - i.e., we can relatively easily replace a node in MerkleStore
with a root of another MerkleStore
to combine two trees.
This is a proposal on how to represent multiple versions of the supported data structures efficiently in memory and disk.
Properties of this proposal:
On any Merkle structure, the contents of a internal node depends on the contents of the leaves, this proposal assumes there is no additional data in any of the internal nodes, i.e the leaves alone are sufficient to reconstruct the structures.
The idea is to maintain a log of the changes to the leaves. This could be as simple as:
#[repr(transparent)]
struct Append {
el: Word,
}
struct Log {
Vec<Append>
}
The above representation is optimal w.r.t storage, since only the data that can't be recomputed is stored. It is a great representation for archive nodes and for a warp sync style protocol.
Caching: With the above when a tree is required, it would need to be reconstructed from the log, this would be very wasteful for the most important case, using the last version of the tree. A solution is to have snapshots of the tree managed in a caching strategy, a proposed strategy is latest
version + LRU
cache of size snapshots
every
The log proposed above is only for append operations, this is useful for structures like MMR, but it is not so useful for a tiered sparse merkle tree, that structure supports deletion, which is internally implemented as setting a specific leaf back to the zero value. This opens first design point
I'm going to assume the later, the idea is that a tailored log would permit better optimizations to exist, for example, the log above uses a transparent operation, whereas the following representation for a tiered sparse merkle tree needs extra space for the tagged union.
Second log:
enum Op {
Insert{leaf: Word}, // alternatively would be (key, value)
Delete{pos: usize},
}
struct Op {
Vec<Append>
}
Moving backwards: The caching above would be limited in size, for example, we could implement a LRU cache with 2 entries in addition to the latest version. If these entries are for versions [1024, 2048]
but the structure receives a request for version 1000
, without the ability to move backwards in time a new structure starting from 0
would have to be constructed. If the version can go backwards then only 24
ops would have to be applied.
To achieve this, the insert operation would need to declare what it overwrote, e.g.:
enum Op {
Insert{new: Word, old: Word}, // alternatively old: usize, this would require a full log
Delete{pos: usize},
}
struct Op {
Vec<Append>
}
When going backwards in the tiered sparse Merkle tree history, the Insert
would mean replace the value in new
with old
.
The structure represented here uses version numbers to represent the data structure, this may be fine on some use cases, but for the advice provider in the VM the goal is to support mtree_get
, which operates on the structure hash instead of its version number.
To support this we can add reverse maps:
BTreeMap<Word, usize>
Using this map we can lookup the corresponding tree. This proposal has the map outside of the operation log, the operation log stays more compact that way, and it allows for the map above to have fewer entries if necessary.
Right now it's little hard for us to test our implementation of ECDSA over Secp256k1 curve ( in Miden assembly, see 0xPolygonMiden/miden-vm#489 ), so we generate test cases using https://github.com/itzmeanjan/secp256k1.git which is somewhat constraining. I'd ideally like to generate random test vectors much more flexibly and pass them through both tunnels i.e.
tunnel0 -> Rust implementation of some logic
tunnel1 -> Miden Assembly implementation of same logic
and finally compare their output.
We kind of do that right now by putting important crypographic construction's logic inside test directory. For more context, I suggest you to look at 0xPolygonMiden/miden-vm#481 , 0xPolygonMiden/miden-vm#482 , 0xPolygonMiden/miden-vm#487 & 0xPolygonMiden/miden-vm#489 . I want all those cryptographic constructions to be living here, which can be much more easily audited on a later date. And that'll make writing test cases much more flexible. We'll just import Secp256k1 implementation from this crate and use it for generating test vectors in our standard library tests.
Note
This is also applicable for Falcon512 signature implementation, there we also have limited test coverage. See 0xPolygonMiden/miden-vm#368 (review) where @bobbinth suggested that. We've tried to address it 0xPolygonMiden/miden-vm#398 but not very satisfying still.
Following the same pattern to add leaves of other algorithms into the MerkleStore
, we should introduce the following methods:
MerkeStore::with_tiered_smt<R, I>(
mut self,
entries: R
) -> Result<Self, MerkleError>
where
R: IntoIterator<IntoIter = I>,
I: Iterator<Item = (Word, Word)>
MerkeStore::add_tiered_smt<R, I>(
&mut self,
entries: R
) -> Result<Word, MerkleError>
where
R: IntoIterator<IntoIter = I>,
I: Iterator<Item = (Word, Word)>
with_tiered_smt
will be a builder pattern, and add_tiered_smt
will return the new root.
The inclusion should follow the implementation described in #22
Originally posted by @bobbinth in 0xPolygonMiden/miden-vm#808 (comment)
NodeIndex
, introduced to help the indexation of Merkle tree nodes, is the responsible to perform efficient & correct traversal over trees.
Lines 6 to 11 in 0799b1b
As pointed here, we have some common patterns that will be beneficial if generalized
crypto/src/merkle/merkle_tree.rs
Lines 101 to 109 in 0799b1b
In that case, it's easier for the compiler if we iterate n
times, instead of while !index.is_root()
.
With that said, it might be beneficial if we have an API in NodeIndex
that will allow traversal to the root & execution of simple functions, while always guaranteeing a friendly interface with the compiler.
One option would be to create a #[inline(always)]
NodeIndex::traverse_to_root<F, A, T>(&mut self, f: F, args: A) where A: BorrowMut<T>, F: FnMut(&mut Self, &mut T)
and always perform the loop there.
Our current MerklePathSet
is rather inefficient because it stores a lot of extra data (which leads to a lot of extra work on updates). I think we can replace it with something more efficient which could work more like SimpleSmt
. The struct could look something like this (though maybe there are other better ways):
pub struct SimpleSmt {
root: Word,
max_depth: u8,
leaves: BTreeMap<u64, Word>,
branches: BTreeMap<NodeIndex, BranchNode>,
}
struct BranchNode {
left: RpoDigest,
right: RpoDigest,
}
The basic idea is that the struct could contain Merkle paths of various lengths (max length of 64) but it would do so without duplicating most of the internal nodes.
This struct could have additional convenience functions:
inner_nodes()
returning an iterator similar to what we do for MerkleTree
, SimpleSmt
, and Mmr
.paths()
returning a set of paths contained in the partial Merkle tree.To give a more concrete example, consider the tree below:
In this tree, we know only the grey nodes (both light and dark grey) - white nodes are not known to us. Thus, the tree contains 4 full Merkle paths (to indexes 2, 3, 10, and 11).
The tree can be fully defined by the dark grey nodes (and only these ones will need to be serialized), but when we instantiate it in memory, we would also compute the light grey nodes to simplify updates and tree traversals.
As part of the design in #22 for a tiered compact SMT, we need to create domain separation between internal nodes and leaf nodes i.e. each type of node should be hashed differently.
The rule that was proposed by @bobbinth is the following:
hash(left,right)
where right
and left
are the left and right child, respectively.hash(r,v)
where r
is the remaining key
(i.e. with the prefix leading to the current position removed) and v
is the values associated with key
. Further, we set one of the capacity registers to the depth i.e. 16, 32, 48 or 64.At the moment, accessing the capacity registers externally is not possible to realize point 2. The following issue aims at exposing some methods from RPO so that point 2 above can be implemented in the final implementation of our compact SMT #22 .
We should add benchmarks for RPO implementation in this crate. These should be similar to the benchmarks in the Winterfell repo. The things which would be good to benchmark are:
merge()
function).hash_elements()
function).We need to export the winter-crypto traits in order to access the available functionality downstream.
0.1.2
introduced en encapsulation of winter-crypto
via this library, so the imports are now extracted from here to miden.
Alternatively, we can export the entire winter-crypto library as re-export, but the ideal approach would be to cherry pick the types as we will have more control over what is used downstream.
We are currently defining the collision resistance of Rpo256 as a constant for the type.
However, this will not always be true, as we might drop it to 126-bits, depending on the capacity registers setup.
Ideally, we should split the Rpo256
into two distinct types, and set the collision attribute/capacity setup strategies individually. This way, we would create a better distinction and unmistakable representation of what we should expect from the implementation.
We should evaluate the options we have available and solve the comment below.
Originally posted by @bobbinth in #68 (comment)
The virtual machine has the following instructions: mtree_get
, mtree_set
. These instructions use the tree's root to identify the target tree of the operation.
That means it is possible to write code that runs mtree_get
in a tree backup by a Merkle Mountain Range, and mtree_set
the data into a Simple Merkle Tree.
The open questions are, which combinations of trees and operations should be supported?
Sparse Merkle Tree | Merkle Mountain Range | Simple Merkle Tree | |
---|---|---|---|
Sparse Merkle Tree | x | ||
Merkle Mountain Range | ? | x | |
Simple Merkle Tree | ? | ? | x |
Note: This is not important for mtree_cwm
since we can assume the resulting copy has the same type, i.e. the instruction does not have a way to change the resulting tree type. This could in theory be modified by the VM's advice provider though.
The following issue aims at implementing the idea of a tiered sparse Merkle tree as proposed by @bobbinth in #22. The aim of such an implementation is to get a gauge of the out-of-VM performance and complexity so that these could be compared with their counterparts for the VM.
Operations at depths greater than 64 can for the time being use the idea of a sorted list as explained here. In the future we might use a more robust solution if the latter proves frail in some realistic scenarios.
Currently, Rpo256::hash
is expecting well-delimited field elements. However, we will panic in case the length isn't evenly divided by the field element length.
The following snippet will cause the panic
use miden_crypto::hash::rpo::Rpo256;
let message = vec![0_u8; 111];
let message = Rpo256::hash(&message);
thread 'main' panicked at 'source slice length (6) does not match destination slice length (7)', src/hash/rpo/mod.rs:120:42
We should probably pad the bytes with zeroes here
Lines 118 to 120 in 3c60484
Because chunks
, as opposed to chunks_exact
, might yield slices with a length smaller than the specified amount of bytes
The MerkleStore
API uses Word
instead of Digest
for all of it's public methods (with_merkle_tree
/ with_sparse_merkle_tree
/ get_node
etc). All merkle objects in the MerkleStore
are natively of type Digest
i.e. they are the digest of a hashing permutation - this is inclusive of leaves, inner nodes and the root. Should the API be updated such that it expects arguments of type Digest
instead of Word
or is there some reason behind using Word
?
In many situations it may be convenient to be able to put a digest as a key into a BTreeMap
. But with the current implementation this is not possible to do directly. So, what we do now is convert a digest into [u8; 32]
and then use this value as a key in a BTreeMap
.
We can probably just implement Ord
(and other requited traits) directly on RpoDigest256 to enable using it in a BTreeMap
.
When fetching a leaf from a SimpleSmt
the lookup should be infallible. Hence we should replace ok_or(...)
with expect(..)
in the code below.
crypto/src/merkle/simple_smt/mod.rs
Lines 132 to 135 in 52db23c
Currently SimpleSmt
backend uses mappings of indexes to tuples of nodes that are used to compose a child.
crypto/src/merkle/simple_smt/mod.rs
Lines 153 to 172 in 0799b1b
It could be beneficial to reevaluate this approach and maybe use simple NodeIndex |-> Node
mappings so traversal will be cheaper and node values will be readily available.
It might be desirable to have a general storage trait so all the tree implementations (mountain range, sparse merkle tree, etc) can be purely functional and focus only on algorithm optimization, leaving storage optimization details outside of their scope.
A tree-like storage is usually composed of simple map-like operations for nodes and leaves. They are distinguished because leaves are often some arbitrary data while nodes are tuples of the digest of a given hash implementation.
The issue started with the PR #27 , but it was better to decouple such big topic from the implementation of the SMT itself.
Here is a suggested implementation with comments:
#![no_std]
extern crate alloc;
// cow is optimal to ease the storage requirements on whether or not he will pass references or
// owned values. sometimes the storage might have to fetch the data from async contexts - to not
// force the storage to hold the lock of the context while the data is being processed by the
// consumer, it will have the option to send it as owned. in other cases, the fetch operation is
// trivial (i.e. memory maps such as BTreeMap) so the storage can just return a reference.
use alloc::borrow::Cow;
// the hasher will be the responsible to define the concrete digest implementation for nodes and
// merge them, producing merkle paths.
use winter_crypto::Hasher;
// a tree node is either a single node (likely the root) or a pair with two digests, one
// representing a left value, the other a right value.
pub enum TreeNode<D> {
Pair { left: D, right: D },
Single(D),
}
// a tree storage is a common definition of map-like implementations optimized for merkle trees.
pub trait TreeStorage: Sized {
// defines the index of a leaf in the tree. it is often just a single scalar value whereas a
// node is indexed by a pair defining both the depth and its index for that depth. the leaf
// will often have as depth the maximum value allowed for the concrete instance.
type LeafIndex;
// usually a pair defining the depth + index of the node for that depth.
type NodeIndex;
// an arbitrary error definition defined by the provider.
type Error;
// a common hash definition used for the backend. the purpose is to define the digest
// concretely, allowing the storage to implement its functionality efficiently since it will be
// aware of the details of the digest - such as bits count, parity, etc.
type Hasher: Hasher;
// a leaf that is separated from the nodes of the tree. usually the leaf contains information
// relevant for the consumers of the tree, while the nodes contains only the required digest to
// traverse the tree and generate paths.
type Leaf: Clone;
// create a new tree with for a given depth.
fn new_with_depth(depth: u32) -> Result<Self, Self::Error>;
// fetch the depth of the storage so tree implementers will be able to contruct merkle paths.
fn depth(&self) -> u32;
// fetch the fixed empty digest for a given depth, provided the upstream branch for that depth
// is composed only of empty leaves.
fn empty_digest(
&self,
depth: u32,
) -> Result<Option<Cow<'_, <Self::Hasher as Hasher>::Digest>>, Self::Error>;
// append a new leaf to the storage, replacing a previous value, if applicable. we opt to not
// return the previous value so the storage can freely discard the replaced value. if the user
// needs the previous value, he can call `Self::get_leaf` and check the underlying `Option`.
fn insert_leaf<L>(&mut self, index: Self::LeafIndex, leaf: L) -> Result<(), Self::Error>
where
L: Into<Self::Leaf>;
// fetch a previously inserted leaf. usually the index will be a common reference scalar (i.e.
// u64).
fn get_leaf(&self, index: &Self::LeafIndex)
-> Result<Option<Cow<'_, Self::Leaf>>, Self::Error>;
// append a new node to the storage, replacing a previous value, if applicable. it follows the
// same pattern of `Self::insert_leaf`; thus, it will not return the previous value.
fn insert_node<N>(&mut self, index: Self::NodeIndex, node: N) -> Result<(), Self::Error>
where
N: Into<TreeNode<<Self::Hasher as Hasher>::Digest>>;
// fetch a previously inserted node. usually the index will be a pair defining both the depth,
// and the index of the node for that depth.
fn get_node(&self, index: &Self::NodeIndex)
-> Result<Option<Cow<'_, Self::Leaf>>, Self::Error>;
}
// create a new list of pairs `(depth, digest)` for a provided hasher and a given depth. it is a
// generic implementation to initialize storages and provide the empty digests via
// [`TreeStorage::empty_digest`]. we don't make assumptions on how the user wants to store this
// list so it is returned as a generic iterator, allowing the user to collect it how it best suits
// him.
pub fn compute_empty_digests<H>(depth: u32) -> impl Iterator<Item = (u32, H::Digest)>
where
H: Hasher,
{
(0..=depth).scan(H::Digest::default(), move |state, i| {
Some((depth - i, core::mem::replace(state, H::merge(&[*state; 2]))))
})
}
Tree types that should support delete:
These two won't support deleted:
We should add implementations of Sparse Merkle tree.
Specifically, I'm thinking of the following variants:
/merkle/simple_smt.rs
module)./merkle/compact_smt.rs
module).References:
@Al-Kindi-0, @bobbinth, @grjte, @vlopes11, @hackaugusto
The working group coordinator ensures scope & progress tracking are transparent and accurate. They will:
Implement Merkle mountain range in Rust and Miden Assembly.
The MMR is an append-only log used for the notes database, which stores all notes ever created. This data structure was chosen because notes can be easily added even if most nodes have been discarded. Additionally, inclusion witnesses never become stale (although they may need to be extended)
The MMR can also be used to track the history of the chain, as described here: 0xPolygonMiden/miden-base#17
@hackaugusto , @bobbinth, @Al-Kindi-0
(Augusto to do the work, Bobbin & Al for discussion & review)
The working group coordinator ensures scope & progress tracking are transparent and accurate. They will:
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.
AccountStorage
is structured as follow:
pub struct AccountStorage {
slots: SimpleSmt, // SMT of depth 8
store: MerkleStore, // Merkle store for any tree data
}
The leaves of the SimpleSmt
can represent roots of Merkle structures stored in the MerkleStore
. For more information on this implementation see here. To support such an implementation we need the ability to extract Merkle structures from the MerkleStore
based on their roots. The interface we would need to implement is:
impl MerkleStore {
pub fn subtree(&self, root: Word) -> MerkleStore
}
Or maybe even:
impl MerkleStore {
pub fn subset(&self, roots: &[Word]) -> MerkleStore
}
The instruction mtree_cwm
is defined as:
Copies a Merkle tree with root R and updates a node at depth d and index i in the copied tree to value Vā².
We currently have the following tree implementations:
For all the data structures above, depending on the size of the tree a copy is potentially a very expensive operation. The issue is about how to design the above structure as so to support a more efficient mtree_cwm
To combine two MerkleStore
s we should implement .inner_nodes()
on MerkleStore
such that we can achieve the following:
merkle_store.extend(other_merkle_store.inner_nodes());
The following issue aims at implementing the idea of a tiered sparse Merkle tree as proposed by @bobbinth in #22 in Miden assembly. The aim of such an implementation is to get a gauge of the performance and complexity of such an approach so that bottlenecks are identified and new VM instructions and decorators are introduced if needed.
When a user inserts a new element into a Sparse Merkle Tree, if that tree has a conflict, this operation becomes two inserts (the old element has to be pushed down a level, and the new element has to be inserted).
This causes hashing of the complete merkle path twice, once for each update. It may make sense to batch operations and remove the extra unnecessary work (in the above example, that would be the hashing from the common parent up to the root)
Currently Word
is a type alias
Lines 24 to 34 in 0c242d2
However, it is a critical component of our stack as it is used everywhere, in different forms. One example is RpoDigest
:
Lines 7 to 11 in 0c242d2
They both have the same structure, but different concrete types. This leads to many cases where unsafe optimizations are required, such as in here:
One of the problems highlighted by this PR is the need to convert between Word
and RpoDigest
efficiently (i.e. without copying/allocating) & safely.
We could achieve major simplification if:
Word
was a structRpo256
was a Word
The original issue describing the need for compact SMTs is here and the PR which has a partially working implementation is here.
The high-level summary is that we need to support a Sparse Merkle tree which enables keys of size ~256 bits. This SMT would be used in many places in the VM. For example, account storage, account vaults, account database, nullifier database etc.
We need to balance efficiency both in Rust and in Miden assembly. There are many implementations of SMTs out there (e.g., Jellyfish Merkle Tree), however, my intuition is that implementing them will be pretty costly in Miden assembly because of the large number of conditional checks.
So, while this issue is not about Miden assembly, we should probably get a good idea of how the construction we come up with will be implemented in Miden assembly and what the associated costs would be (i.e., in terms of cycle counts for both get
and set
operations).
One approach is to build a "Tiered tree". In this tree, the first
I think the performance targets could be something like (in an average case):
Currently, the key bits are documented as 63-bit
crypto/src/merkle/simple_smt/mod.rs
Lines 9 to 13 in 398af59
However, we take u64
as arguments. This difference might create a confusion downstream.
crypto/src/merkle/simple_smt/mod.rs
Lines 153 to 154 in 398af59
One option is to, instead, take a Felt
as argument. But then, we also need to rework the rpo module documentation that also mentions 64-bit
- and it is important we keep consistency between these, as RPO is the backend of SimpleSmt
Lines 60 to 65 in 398af59
Originally posted by @grjte in #64 (comment)
ATM the search input is only visible when the page is scrolled all the way to the top, if the users don't pay attention they may not realize that search is available, and users that know of the search feature have to scroll all the way back to the top to use it.
A solution is to add the search input along side the table's header, which is sticky and always visible.
There may be some optimisations we can implement on the MerkleStore
to improve it's performance. We should benchmark to asses impact on performance of the changes. The two optimisations we should consider are:
BTreeMap
store with a HashMap
, specifically hashbrown
which is no_std
compatible.MerkleStore
are the digests of the Rpo hash function, which is cryptographically secure, we should see if we can avoid performing an additional hash when we do lookups and inserts by replacing the standard hasher. For inspiration on how this can be implemented we can take a look at the nohash-hasher
library.A declarative, efficient, and flexible JavaScript library for building user interfaces.
š Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ššš
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ā¤ļø Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.