merkle.ml

let check_merkle_lookup
  : type a.
    depth:int
  -> root:Hash.Var.t
  -> entry:Hash.Var.t
  -> Bool_var.t list
  -> ((hash, a) Merkle_tree.t, unit) T.t
  =
  fun ~depth ~root ~entry addr ->
    let initial_path =
      let open Value_computation in
      let open Let_syntax in
      let%map tree = get_state
      and vals = List.map ~f:Bool_var.value addr
      in
      Merkle_tree.get_path tree vals
    in
    let pop =
      let open Value_computation in
      let open Let_syntax in
      match%bind get_state with
      | p :: path ->
        let%map () = set_state path in
        p
      | _ -> failwith "Path not long enough"
    in
    with_state initial_path begin
      let rec go (addr : Bool_var.t list) acc =
        match addr with
        | [] ->
          add_constraint (Hash.Var.equal acc root)
        | b :: addr' ->
          let%bind h = Hash.Var.create pop in
          let acc' = Hash.Var.hash ~swap:b acc h in
          go addr' acc'
      in
      go addr entry
    end
;;