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.

Sign up for GitHub

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

Jump to bottom

Implement mtree_verify instruction #848

Closed
bobbinth opened this issue Apr 13, 2023 · 1 comment
Closed

Implement mtree_verify instruction #848

bobbinth opened this issue Apr 13, 2023 · 1 comment
Assignees
@vlopes11
Labels
assembly Related to Miden assembly

Comments

@bobbinth
Copy link
Contributor

Currently, we have an mtree_get instruction which retrieves a leaf from a Merkle tree at the specified index/depth combination. Internally, this instruction relies on MPVERIFY VM operation which verifies a Merkle path.

In some cases, it would be beneficial to have access to the raw MPVERIFY operation as node values may already be on the stack (this is the case, for example, for our SMT implementation in #808). So, I'm thinking we should add an mtree_verify instruction to Miden assembly and this instruction would just call MPVERIFY (and thus take a single cycle). Stack transition for this instruction would be:

[V, d, i, R, ...] -> [V, d, i, R, ...]

That is, the state of the stack would remain unchanged, but the execution will fail if a Merkle path from $V$ to $R$ for the specified $d$ (depth) and $i$ (index) could not be verified.
@bobbinth bobbinth added the assembly Related to Miden assembly label Apr 13, 2023
@bobbinth bobbinth mentioned this issue Apr 13, 2023
Merged
vlopes11 added a commit that referenced this issue Apr 13, 2023
@vlopes11
feat: add mtree_verify
1cf3696 
This commit introduces `mtree_verify`, a function that will perform a
raw [Operation::MpVerify]. It will not manipulate or consume elements of
the stack, and will be optimal in terms of efficiency - consuming a
single cycle.

It aims to support algorithms for multiple tree implementations - such
as Tiered Sparse Merkle tree - that will need to check for Merkle
openings while preserving the stack elements.

closes #848
@vlopes11 vlopes11 mentioned this issue Apr 13, 2023
Merged
vlopes11 added a commit that referenced this issue Apr 13, 2023
@vlopes11
feat: add mtree_verify
9edfe1e 
This commit introduces `mtree_verify`, a function that will perform a
raw [Operation::MpVerify]. It will not manipulate or consume elements of
the stack, and will be optimal in terms of efficiency - consuming a
single cycle.

It aims to support algorithms for multiple tree implementations - such
as Tiered Sparse Merkle tree - that will need to check for Merkle
openings while preserving the stack elements.

closes #848
@bobbinth
Copy link
Contributor Author

Closed by #850.

frisitano pushed a commit that referenced this issue Apr 14, 2023
@vlopes11 @frisitano
feat: add mtree_verify
cfb51a1 
This commit introduces `mtree_verify`, a function that will perform a
raw [Operation::MpVerify]. It will not manipulate or consume elements of
the stack, and will be optimal in terms of efficiency - consuming a
single cycle.

It aims to support algorithms for multiple tree implementations - such
as Tiered Sparse Merkle tree - that will need to check for Merkle
openings while preserving the stack elements.

closes #848
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@vlopes11 vlopes11

Labels
assembly Related to Miden assembly
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@vlopes11 @bobbinth