I am looking for an implementation of a merkle tree, in ligo. Could somebody help me please?
From Slack, to share the answers for others its posted on Stackexchange.
Tezos Stack Exchange is a question and answer site for users, experts, and developers of the Tezos blockchain project. It only takes a minute to sign up.
Sign up to join this communityFrom Tom Jack:
I don't know of any existing implementation but I sketched this once or twice before. Its completely untested and likely wrong but:
type dir =
[@layout:comb]
| Left
| Right
type step =
[@layout:comb]
{dir : dir;
left : bytes;
right : bytes}
type proof = step list
let validate (proof : proof) (root : bytes) : bytes =
List.fold_left
(fun ((root, step) : bytes * step) ->
if root = Crypto.blake2b (Bytes.pack (step.left, step.right))
then
match step.dir with
| Left -> step.left
| Right -> step.right
else failwith "invalid proof")
root
proof
From Anshu Jalan:
For the root computation, the smaller hash comes first (at least if you want it to be interoperable with the industry standard merklejs library)