(** Merkle proofs for content-addressed trees.

    Proofs are sparse trees where unvisited paths are replaced by their hash
    ("blinded"). They allow verification of computations without full tree
    access.

    {[
      (* Producer has full tree access *)
      let proof, result = Proof.produce store tree (fun t ->
        let v = Tree.find t ["foo"; "bar"] in
        (t, v))

      (* Verifier only needs the proof *)
      match Proof.verify proof (fun t ->
        let v = Tree.find t ["foo"; "bar"] in
        (t, v)) with
      | Ok (_, v) -> (* v is trusted *)
      | Error `Proof_mismatch -> (* invalid proof *)
    ]}

    Compatible with ATProto's MST proof format when using the MST codec. *)

(** {1 Proof Trees} *)

type 'hash kinded_hash = [ `Contents of 'hash | `Node of 'hash ]
(** Hash tagged with its kind. *)

(** Sparse tree with blinded (hash-only) subtrees. *)
type ('hash, 'contents) tree =
  | Contents of 'contents
  | Blinded_contents of 'hash
  | Node of ('hash, 'contents) node
  | Blinded_node of 'hash

and ('hash, 'contents) node = (string * ('hash, 'contents) tree) list
(** Node entries, sorted by key. *)

(** {1 Proofs} *)

type ('hash, 'contents) t
(** A Merkle proof with before/after state hashes. *)

val v :
  before:'hash kinded_hash ->
  after:'hash kinded_hash ->
  ('hash, 'contents) tree ->
  ('hash, 'contents) t
(** [v ~before ~after tree] creates a proof that state changed from [before] to
    [after], with [tree] containing the minimal data needed to verify. *)

val before : ('hash, _) t -> 'hash kinded_hash
(** [before p] is the root hash before the computation. *)

val after : ('hash, _) t -> 'hash kinded_hash
(** [after p] is the root hash after the computation. *)

val state : ('hash, 'contents) t -> ('hash, 'contents) tree
(** [state p] is the sparse tree proving the computation. *)

val pp :
  (Format.formatter -> 'hash -> unit) ->
  (Format.formatter -> 'contents -> unit) ->
  Format.formatter ->
  ('hash, 'contents) t ->
  unit
(** [pp pp_hash pp_contents fmt p] pretty-prints a proof. *)

(** {1 Producing and Verifying Proofs}

    These operations are parameterized by a codec for hashing. *)

module Make (C : Codec.S) : sig
  type hash = C.hash
  type contents = string

  module Tree : sig
    type t
    (** Proof-aware tree that records accesses during [produce]. *)

    val find : t -> string list -> contents option
    (** [find t path] returns the contents at [path], or [None] if not found. *)

    val find_tree : t -> string list -> t option
    (** [find_tree t path] returns the subtree at [path], or [None] if not
        found. *)

    val mem : t -> string list -> bool
    (** [mem t path] checks whether a value exists at [path]. *)

    val list : t -> string list -> (string * [ `Node | `Contents ]) list
    (** [list t path] returns the children of [path], each tagged as either a
        node or contents. *)

    val add : t -> string list -> contents -> t
    (** [add t path contents] returns a new tree with contents added or updated
        at [path]. *)

    val add_tree : t -> string list -> t -> t
    (** [add_tree t path subtree] returns a new tree with [subtree] grafted at
        [path]. *)

    val remove : t -> string list -> t
    (** [remove t path] returns a new tree with the value at [path] removed. *)

    val hash : t -> hash
    (** [hash t] computes the root hash of the tree. *)
  end

  val produce :
    hash Backend.t -> hash -> (Tree.t -> Tree.t * 'a) -> (hash, contents) t * 'a
  (** [produce backend root_hash f] runs [f] on the tree at [root_hash],
      recording all accesses. Returns a proof containing only accessed paths. *)

  val verify :
    (hash, contents) t ->
    (Tree.t -> Tree.t * 'a) ->
    (Tree.t * 'a, [ `Proof_mismatch of string ]) result
  (** [verify proof f] replays [f] on the proof tree. Returns [Ok] if the result
      tree's hash matches [after proof], [Error] otherwise. *)

  val to_tree : (hash, contents) t -> Tree.t
  (** [to_tree proof] converts a proof to a tree for inspection. *)

  val hash_of_tree : (hash, contents) tree -> hash kinded_hash
  (** [hash_of_tree t] computes the root hash of a proof tree. *)
end

module Git : module type of Make (Codec.Git)
module Mst : module type of Make (Codec.Mst)