Source file sapling_storage.ml

(*****************************************************************************)
(*                                                                           *)
(* Open Source License                                                       *)
(* Copyright (c) 2019-2020 Nomadic Labs <contact@nomadic-labs.com>           *)
(*                                                                           *)
(* Permission is hereby granted, free of charge, to any person obtaining a   *)
(* copy of this software and associated documentation files (the "Software"),*)
(* to deal in the Software without restriction, including without limitation *)
(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
(* and/or sell copies of the Software, and to permit persons to whom the     *)
(* Software is furnished to do so, subject to the following conditions:      *)
(*                                                                           *)
(* The above copyright notice and this permission notice shall be included   *)
(* in all copies or substantial portions of the Software.                    *)
(*                                                                           *)
(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
(* DEALINGS IN THE SOFTWARE.                                                 *)
(*                                                                           *)
(*****************************************************************************)

module type COMMITMENTS = sig
  val init : Raw_context.t -> Storage.Sapling.id -> Raw_context.t Lwt.t

  val default_root : Sapling.Hash.t

  val get_root :
    Raw_context.t ->
    Storage.Sapling.id ->
    (Raw_context.t * Sapling.Hash.t) tzresult Lwt.t

  val add :
    Raw_context.t ->
    Storage.Sapling.id ->
    Sapling.Commitment.t list ->
    int64 ->
    (Raw_context.t * int) tzresult Lwt.t

  val get_from :
    Raw_context.t ->
    Storage.Sapling.id ->
    int64 ->
    Sapling.Commitment.t list tzresult Lwt.t
end

module Commitments : COMMITMENTS = struct
  module H = Sapling.Hash

  (** Incremental Merkle Tree
   *
   * A tree of height h contains 2^h leaves and h+1 levels of nodes with
   * leaves at level 0 and root at level h.
   *
   * The leaves are commitments and the tree it is treated as always filled
   * with a default value H.uncommitted. This allows to have proofs of
   * membership, or witnesses, of fixed size.
   *
   * All the nodes at the same level of an empty tree have the same hash,
   * which can be computed from the default value of the leaves. This is
   * stored in the [uncommitted] list.
   *
   * Any subtree filled with default values is represented by the Empty
   * constructor and given its height it's possible to compute its hash
   * using the [uncommitted] list.
   *
   * The leaves are indexed by their position [pos], ranging from 0 to
   * (2^h)-1. The encoding of [pos] limits the possible size of the tree.
   * In any case the only valid height for the Sapling library is 32, so even
   * if the library encodes positions as uint64, they never exceed uint32.
   *
   * The tree is incremental in the sense that leaves cannot be modified but
   * only added and exclusively in successive positions.
   *
   * Given that elements are added and retrieved by position, it is possible
   * to use this information to efficiently navigate the tree.
   * Given a tree of height [h] and a position [pos], if pos < pow2 (h-1) only
   * the left subtree needs to be inspected recursively. Otherwise only the
   * right needs to be visited, decreasing [pos] by [pow2 (h-1)].
   *
   * In order to avoid storing the height for each subtree (or worse
   * recomputing it), each function with suffix `_height` expects the height
   * of the tree as parameter. These functions are only for internal use and
   * are later aliased by functions using the default height of a Sapling
   * incremental Merkle tree.
   *
   * Each node of the tree is indexed starting from the root at index 1,
   * followed by its left child at index 2, right child at index 3 and so on
   * until the last leaf at index 2^(depth+1)-1, or in terms of height
   * 2^(32 - height +1) -1.
   * The functions left and right return the index of the left and right child
   * of a node.
   *)

  let pow2 h = Int64.(shift_left 1L h)

  let max_height = 32

  let max_size = pow2 max_height

  let assert_node node height =
    assert (
      let first_of_height = pow2 (max_height - height) in
      let first_of_next_height = Int64.shift_left first_of_height 1 in
      Compare.Int64.(node >= first_of_height && node < first_of_next_height))

  let assert_height height =
    assert (Compare.Int.(height >= 0 && height <= max_height))

  let assert_pos pos height =
    assert (Compare.Int64.(pos >= 0L && pos <= pow2 height))

  let default_root = H.uncommitted ~height:max_height

  let init = Storage.Sapling.commitments_init

  let get_root_height ctx id node height =
    assert_node node height ;
    assert_height height ;
    Storage.Sapling.Commitments.find (ctx, id) node >|=? function
    | (ctx, None) ->
        let hash = H.uncommitted ~height in
        (ctx, hash)
    | (ctx, Some hash) -> (ctx, hash)

  let left node = Int64.mul node 2L

  let right node = Int64.(add (mul node 2L) 1L)

  (* Not tail-recursive *)
  let rec split_at n l =
    if Compare.Int64.(n = 0L) then ([], l)
    else
      match l with
      | [] -> ([], l)
      | x :: xs ->
          let (l1, l2) = split_at Int64.(pred n) xs in
          (x :: l1, l2)

  (* [insert tree height pos cms] inserts the list of commitments
     [cms] in the tree [tree] of height [height] at the next position [pos].
     Returns the context, the size of the added storage, and the hash of the
     node. Not tail-recursive.
     Pre: incremental tree /\
          size tree + List.length cms <= pow2 height /\
          pos = size tree /\
     Post: incremental tree /\
           to_list (insert tree height pos cms) = to_list t @ cms *)
  let[@coq_struct "height"] rec insert ctx id node height pos cms =
    assert_node node height ;
    assert_height height ;
    assert_pos pos height ;
    match (height, cms) with
    | (_, []) ->
        get_root_height ctx id node height >|=? fun (ctx, h) -> (ctx, 0, h)
    | (0, [cm]) ->
        let h = H.of_commitment cm in
        Storage.Sapling.Commitments.init (ctx, id) node h
        >|=? fun (ctx, size) -> (ctx, size, h)
    | _ ->
        let height = height - 1 in
        (if Compare.Int64.(pos < pow2 height) then
         let at = Int64.(sub (pow2 height) pos) in
         let (cml, cmr) = split_at at cms in
         insert ctx id (left node) height pos cml >>=? fun (ctx, size_l, hl) ->
         insert ctx id (right node) height 0L cmr >|=? fun (ctx, size_r, hr) ->
         (ctx, size_l + size_r, hl, hr)
        else
          get_root_height ctx id (left node) height >>=? fun (ctx, hl) ->
          let pos = Int64.(sub pos (pow2 height)) in
          insert ctx id (right node) height pos cms
          >|=? fun (ctx, size_r, hr) -> (ctx, size_r, hl, hr))
        >>=? fun (ctx, size_children, hl, hr) ->
        let h = H.merkle_hash ~height hl hr in
        Storage.Sapling.Commitments.add (ctx, id) node h
        >|=? fun (ctx, size, _existing) -> (ctx, size + size_children, h)

  let[@coq_struct "height"] rec fold_from_height ctx id node ~pos ~f ~acc height
      =
    assert_node node height ;
    assert_height height ;
    assert_pos pos height ;
    Storage.Sapling.Commitments.find (ctx, id) node
    (* we don't count gas for this function, it is called only by RPC *)
    >>=?
    function
    | (_ctx, None) -> return acc
    | (_ctx, Some h) ->
        if Compare.Int.(height = 0) then return (f acc h)
        else
          let full = pow2 (height - 1) in
          if Compare.Int64.(pos < full) then
            fold_from_height ctx id (left node) ~pos ~f ~acc (height - 1)
            >>=? fun acc ->
            (* Setting pos to 0 folds on the whole right subtree *)
            fold_from_height ctx id (right node) ~pos:0L ~f ~acc (height - 1)
          else
            let pos = Int64.(sub pos full) in
            fold_from_height ctx id (right node) ~pos ~f ~acc (height - 1)

  let root_node = 1L

  let get_root ctx id = get_root_height ctx id root_node max_height

  (* Expects pos to be the next position to insert. Pos is also the number of
     inserted leaves.
     A commitment should always be added together with a corresponding
     ciphertext in the same position.
     [insert] is not tail-recursive so we put a hard limit on the size of the
     list of commitments. The use of [split_at] has O(n logn) complexity that is
     less relevant on a smaller list. *)
  let add ctx id cms pos =
    let l = List.length cms in
    assert (Compare.Int.(l <= 1000)) ;
    let n' = Int64.(add pos (of_int l)) in
    assert (Compare.Int64.(n' <= max_size)) ;
    insert ctx id root_node max_height pos cms >|=? fun (ctx, size, _h) ->
    (ctx, size)

  let get_from ctx id pos =
    fold_from_height
      ctx
      id
      root_node
      ~pos
      ~f:(fun acc c -> H.to_commitment c :: acc)
      ~acc:[]
      max_height
    >|=? fun l -> List.rev l
end

module Ciphertexts = struct
  let init ctx id = Storage.Sapling.ciphertexts_init ctx id

  (* a ciphertext should always be added together with a corresponding
     commitment in the same position *)
  let add ctx id c pos = Storage.Sapling.Ciphertexts.init (ctx, id) pos c

  let get_from ctx id offset =
    let rec aux (ctx, acc) pos =
      Storage.Sapling.Ciphertexts.find (ctx, id) pos >>=? fun (ctx, c) ->
      match c with
      | None -> return (ctx, List.rev acc)
      | Some c -> aux (ctx, c :: acc) (Int64.succ pos)
    in
    aux (ctx, []) offset
end

(* Collection of nullifiers w/o duplicates, append-only. It has a dual
   implementation with a hash map for constant `mem` and with a ordered set to
   retrieve by position.  *)
module Nullifiers = struct
  let init = Storage.Sapling.nullifiers_init

  let size ctx id = Storage.Sapling.Nullifiers_size.get (ctx, id)

  let mem ctx id nf = Storage.Sapling.Nullifiers_hashed.mem (ctx, id) nf

  (* Allows for duplicates as they are already checked by verify_update before
     updating the state.
     Not tail-recursive so we put a hard limit on the size of the
     list of nullifiers. *)
  let add ctx id nfs =
    assert (Compare.Int.(List.compare_length_with nfs 1000 <= 0)) ;
    size ctx id >>=? fun nf_start_pos ->
    List.fold_right_es
      (fun nf (ctx, pos, acc_size) ->
        Storage.Sapling.Nullifiers_hashed.init (ctx, id) nf
        >>=? fun (ctx, size) ->
        Storage.Sapling.Nullifiers_ordered.init (ctx, id) pos nf >|=? fun ctx ->
        (ctx, Int64.succ pos, Z.add acc_size (Z.of_int size)))
      nfs
      (ctx, nf_start_pos, Z.zero)
    >>=? fun (ctx, nf_end_pos, size) ->
    Storage.Sapling.Nullifiers_size.update (ctx, id) nf_end_pos >|=? fun ctx ->
    (ctx, size)

  let get_from ctx id offset =
    let[@coq_struct "pos"] rec aux acc pos =
      Storage.Sapling.Nullifiers_ordered.find (ctx, id) pos >>=? function
      | None -> return @@ List.rev acc
      | Some c -> aux (c :: acc) (Int64.succ pos)
    in
    aux [] offset
end

(** Bounded queue of roots. The full size is initialized with the default
    uncommitted root, that's why roots storage doesn't need to be carbonated.
    A maximum of one new root is added per protocol level.
    If multiple transactions for the same shielded pool are processed during the
    same contract call or several calls in the same block, only the last root
    will be stored.
    This property prevents transactions in the same block from depending on each
    other and guarantees that a transaction will be valid for a least two hours
    (hence the 120 size) after being forged. *)
module Roots = struct
  let size = 120l

  (* pos is the index of the last inserted element *)

  let get ctx id =
    Storage.Sapling.Roots_pos.get (ctx, id) >>=? fun pos ->
    Storage.Sapling.Roots.get (ctx, id) pos

  let init ctx id =
    let[@coq_struct "pos"] rec aux ctx pos =
      if Compare.Int32.(pos < 0l) then return ctx
      else
        Storage.Sapling.Roots.init (ctx, id) pos Commitments.default_root
        >>=? fun ctx -> aux ctx (Int32.pred pos)
    in
    aux ctx (Int32.pred size) >>=? fun ctx ->
    Storage.Sapling.Roots_pos.init (ctx, id) 0l >>=? fun ctx ->
    let level = (Raw_context.current_level ctx).level in
    Storage.Sapling.Roots_level.init (ctx, id) level

  let mem ctx id root =
    Storage.Sapling.Roots_pos.get (ctx, id) >>=? fun start_pos ->
    let rec aux pos =
      Storage.Sapling.Roots.get (ctx, id) pos >>=? fun hash ->
      if Compare.Int.(Sapling.Hash.compare hash root = 0) then return true
      else
        let pos = Int32.(pred pos) in
        let pos = if Compare.Int32.(pos < 0l) then Int32.pred size else pos in
        if Compare.Int32.(pos = start_pos) then return false else aux pos
    in
    aux start_pos

  (* allows duplicates *)
  let add ctx id root =
    Storage.Sapling.Roots_pos.get (ctx, id) >>=? fun pos ->
    let level = (Raw_context.current_level ctx).level in
    Storage.Sapling.Roots_level.get (ctx, id) >>=? fun stored_level ->
    if Raw_level_repr.(stored_level = level) then
      (* if there is another add during the same level, it will over-write on
         the same position *)
      Storage.Sapling.Roots.add (ctx, id) pos root >|= ok
    else
      (* it's the first add for this level *)
      (* TODO(samoht): why is it using [update] and not [init] then? *)
      Storage.Sapling.Roots_level.update (ctx, id) level >>=? fun ctx ->
      let pos = Int32.rem (Int32.succ pos) size in
      Storage.Sapling.Roots_pos.update (ctx, id) pos >>=? fun ctx ->
      Storage.Sapling.Roots.add (ctx, id) pos root >|= ok
end

(** This type links the permanent state stored in the context at the specified
    id together with the ephemeral diff managed by the Michelson
    interpreter. After a successful execution the diff can be applied to update
    the state at id. The first time a state is created its id is None, one will
    be assigned after the first application. *)
type state = {
  id : Lazy_storage_kind.Sapling_state.Id.t option;
  diff : Sapling_repr.diff;
  memo_size : Sapling_repr.Memo_size.t;
}

let empty_diff =
  Sapling_repr.{commitments_and_ciphertexts = []; nullifiers = []}

let empty_state ?id ~memo_size () = {id; diff = empty_diff; memo_size}

(** Returns a state from an existing id. *)
let state_from_id ctxt id =
  Storage.Sapling.Memo_size.get (ctxt, id) >|=? fun memo_size ->
  ({id = Some id; diff = empty_diff; memo_size}, ctxt)

let rpc_arg = Storage.Sapling.rpc_arg

let get_memo_size ctx id = Storage.Sapling.Memo_size.get (ctx, id)

let init ctx id ~memo_size =
  Storage.Sapling.Memo_size.add (ctx, id) memo_size >>= fun ctx ->
  Storage.Sapling.Commitments_size.add (ctx, id) Int64.zero >>= fun ctx ->
  Commitments.init ctx id >>= fun ctx ->
  Nullifiers.init ctx id >>= fun ctx ->
  Roots.init ctx id >>=? fun ctx -> Ciphertexts.init ctx id >|= ok

(* Gas costs for apply_diff. *)
let sapling_apply_diff_cost ~inputs ~outputs =
  let open Saturation_repr in
  add
    (safe_int 1_300_000)
    (add
       (scale_fast (mul_safe_of_int_exn 5_000) (safe_int inputs))
       (scale_fast (mul_safe_of_int_exn 55_000) (safe_int outputs)))

(** Applies a diff to a state id stored in the context. Updates Commitments,
    Ciphertexts and Nullifiers using the diff and updates the Roots using the
    new Commitments tree. *)
let apply_diff ctx id diff =
  let open Sapling_repr in
  let nb_commitments = List.length diff.commitments_and_ciphertexts in
  let nb_nullifiers = List.length diff.nullifiers in
  let sapling_cost =
    sapling_apply_diff_cost ~inputs:nb_nullifiers ~outputs:nb_commitments
  in
  Raw_context.consume_gas ctx sapling_cost >>?= fun ctx ->
  Storage.Sapling.Commitments_size.get (ctx, id) >>=? fun cm_start_pos ->
  let cms = List.rev_map fst diff.commitments_and_ciphertexts in
  Commitments.add ctx id cms cm_start_pos >>=? fun (ctx, size) ->
  Storage.Sapling.Commitments_size.update
    (ctx, id)
    (Int64.add cm_start_pos (Int64.of_int nb_commitments))
  >>=? fun ctx ->
  List.fold_right_es
    (fun (_cm, cp) (ctx, pos, acc_size) ->
      Ciphertexts.add ctx id cp pos >|=? fun (ctx, size) ->
      (ctx, Int64.succ pos, Z.add acc_size (Z.of_int size)))
    diff.commitments_and_ciphertexts
    (ctx, cm_start_pos, Z.of_int size)
  >>=? fun (ctx, _ct_end_pos, size) ->
  Nullifiers.add ctx id diff.nullifiers >>=? fun (ctx, size_nf) ->
  let size = Z.add size size_nf in
  match diff.commitments_and_ciphertexts with
  | [] ->
      (* avoids adding duplicates to Roots *)
      return (ctx, size)
  | _ :: _ ->
      Commitments.get_root ctx id >>=? fun (ctx, root) ->
      Roots.add ctx id root >|=? fun ctx -> (ctx, size)

let add {id; diff; memo_size} cm_cipher_list =
  assert (
    List.for_all
      (fun (_cm, cipher) ->
        Compare.Int.(Sapling.Ciphertext.get_memo_size cipher = memo_size))
      cm_cipher_list) ;
  {
    id;
    diff =
      {
        diff with
        commitments_and_ciphertexts =
          List.rev cm_cipher_list @ diff.commitments_and_ciphertexts;
      };
    memo_size;
  }

let root_mem ctx {id; _} tested_root =
  match id with
  | Some id -> Roots.mem ctx id tested_root
  | None ->
      return
        Compare.Int.(
          Sapling.Hash.compare tested_root Commitments.default_root = 0)

(* to avoid a double spend we need to check the disk AND the diff *)
let nullifiers_mem ctx {id; diff; _} nf =
  let exists_in_diff =
    List.exists
      (fun v -> Compare.Int.(Sapling.Nullifier.compare nf v = 0))
      diff.nullifiers
  in
  if exists_in_diff then return (ctx, true)
  else
    match id with
    | None -> return (ctx, false)
    | Some id -> Nullifiers.mem ctx id nf

(* Allows for duplicates as they are already checked by verify_update before
   updating the state. *)
let nullifiers_add {id; diff; memo_size} nf =
  {id; diff = {diff with nullifiers = nf :: diff.nullifiers}; memo_size}

type root = Sapling.Hash.t

let root_encoding = Sapling.Hash.encoding

let get_diff ctx id ?(offset_commitment = 0L) ?(offset_nullifier = 0L) () =
  if
    not
      Sapling.Commitment.(
        valid_position offset_commitment && valid_position offset_nullifier)
  then failwith "Invalid argument."
  else
    Commitments.get_from ctx id offset_commitment >>=? fun commitments ->
    Roots.get ctx id >>=? fun root ->
    Nullifiers.get_from ctx id offset_nullifier >>=? fun nullifiers ->
    Ciphertexts.get_from ctx id offset_commitment
    (* we don't count gas for RPCs *)
    >|=? fun (_ctx, ciphertexts) ->
    match List.combine ~when_different_lengths:() commitments ciphertexts with
    | Error () -> failwith "Invalid argument."
    | Ok commitments_and_ciphertexts ->
        (root, Sapling_repr.{commitments_and_ciphertexts; nullifiers})