Incremental tree?

[sanderpick]

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]

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]

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]

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