Merkle Tree implementation in Ligo

Question

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.

Answer 1

From 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

Answer 2

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)