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

Add Merkle tree to Symbolic #418

Open
2 of 4 tasks
vlasin opened this issue Dec 23, 2024 · 0 comments · May be fixed by #441
Open
2 of 4 tasks

Add Merkle tree to Symbolic #418

vlasin opened this issue Dec 23, 2024 · 0 comments · May be fixed by #441
Assignees

Comments

@vlasin
Copy link
Contributor

vlasin commented Dec 23, 2024

Implement Merkle tree type in Symbolic, borrowing ideas from the already implemented List and Hash data types.

  • Define MerkleTree d x type to represent the tree of depth d (i.e., with $2^d$ leafs)
  • Define MerkleTreePath d x type (a wrapper around Vector d (Bool (Context x)) or similar) to represent the path to a particular leaf in a tree.
  • Define the following functions, filling in the appropriate type constraints:
-- | Finds an element satisfying the constraint
find :: (x -> Bool (Context x)) -> MerkleTree d x -> Maybe (Context x) x

-- | Finds a path to an element satisfying the constraint
findPath :: (x -> Bool (Context x)) -> MerkleTree d x -> Maybe (Context x) (MerkleTreePath d x)

-- | Returns the element corresponding to a path
lookup :: MerkleTree d x -> MerkleTreePath d x -> x

-- | Inserts an element at a specified position in a tree
insert :: MerkleTree d x -> MerkleTreePath d x -> x -> MerkleTree d x

-- | Replaces an element satisfying the constraint. A composition of `findPath` and `insert`
replace :: (x -> Bool (Context x)) ->  MerkleTree d x -> x -> MerkleTree d x

-- | Returns the next path in a tree
incrementPath :: MerkleTreePath d x -> MerkleTreePath d x
  • Add tests to verify (among other things) the circuit efficiency of those operations and their compositions. For example, a composition of findPath and lookup should only do d hashes in-circuit (instead of naive 2*d) since we verify the same path from the leaf to the root.
@hovanja2011 hovanja2011 linked a pull request Jan 14, 2025 that will close this issue
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

Successfully merging a pull request may close this issue.

2 participants