search

dmfxyz / murky

Merkle Proof Generator and Validator in Solidity
MIT License
410 stars 39 forks source link

Incremental tree? #10

Open sanderpick opened 1 year ago

sanderpick commented 1 year ago

Any ideas on how one might build a tree incrementally? I'd like to add a leaf in a contract function and save the root in contract storage. Then, later check that some supplied hash is part of the tree in a different function (different txn). i.e., an inclusion proof against a dynamic tree.

Cheers!

dmfxyz commented 1 year ago

Murky does not currently support this. However there's an interesting article here: https://ethresear.ch/t/efficient-on-chain-dynamic-merkle-tree/11054.

Obviously open to contributions, or may take a look at this myself (not sure when).

sanderpick commented 1 year ago

Very cool, thanks for the tip. I played around with it a bit here. The general class of sparse merkle trees (MMRs specifically) is pretty compelling for efficiently proving off chain dynamic state. To make this compelling as an addition to murky / a standalone lib, I think it would have to come with tooling to build the trees and get proofs in various languages.

yorhodes commented 11 months ago

there is an incremental tree implementation here https://github.com/hyperlane-xyz/hyperlane-monorepo/blob/main/solidity/contracts/libs/Merkle.sol as well as accompanying rust tooling https://github.com/hyperlane-xyz/hyperlane-monorepo/blob/main/rust/hyperlane-core/src/accumulator/merkle.rs