0

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.

2 Answers 2

2

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
0

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)

enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.