From 8f104fc26e6fed8060d66151fbde90546a3916af Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Thu, 17 Nov 2022 16:31:28 +0100 Subject: [PATCH 1/8] proto/scoru: remove inbox merkelized_operation this commit won't compile, It's only to reduce the diff of the next commit that introduced the new inbox level tree logic using the merkelized payload hashes module --- .../lib_protocol/alpha_context.mli | 123 ---- .../lib_protocol/sc_rollup_inbox_repr.ml | 630 ------------------ .../lib_protocol/sc_rollup_inbox_repr.mli | 234 ------- 3 files changed, 987 deletions(-) diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 67ce9fefef12..33401afc5576 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -3316,129 +3316,6 @@ module Sc_rollup : sig val serialized_proof_encoding : serialized_proof Data_encoding.t - module type Merkelized_operations = sig - type tree - - type inbox_context - - val hash_level_tree : tree -> Hash.t - - val new_level_tree : inbox_context -> tree Lwt.t - - val add_messages : - inbox_context -> - History.t -> - t -> - Raw_level.t -> - Inbox_message.serialized list -> - tree option -> - (tree * History.t * t) tzresult Lwt.t - - val add_messages_no_history : - inbox_context -> - t -> - Raw_level.t -> - Inbox_message.serialized list -> - tree option -> - (tree * t) tzresult Lwt.t - - val get_message_payload : - tree -> Z.t -> Inbox_message.serialized option Lwt.t - - val form_history_proof : - inbox_context -> - History.t -> - t -> - tree option -> - (History.t * history_proof) tzresult Lwt.t - - val take_snapshot : t -> history_proof - - type inclusion_proof - - val inclusion_proof_encoding : inclusion_proof Data_encoding.t - - val pp_inclusion_proof : Format.formatter -> inclusion_proof -> unit - - val number_of_proof_steps : inclusion_proof -> int - - val verify_inclusion_proof : - inclusion_proof -> history_proof -> history_proof tzresult - - type proof - - val pp_proof : Format.formatter -> proof -> unit - - val to_serialized_proof : proof -> serialized_proof - - val of_serialized_proof : serialized_proof -> proof option - - val verify_proof : - Raw_level.t * Z.t -> - history_proof -> - proof -> - inbox_message option tzresult Lwt.t - - val produce_proof : - inbox_context -> - History.t -> - history_proof -> - Raw_level.t * Z.t -> - (proof * inbox_message option) tzresult Lwt.t - - val empty : inbox_context -> Raw_level.t -> t Lwt.t - - module Internal_for_tests : sig - val eq_tree : tree -> tree -> bool - - val produce_inclusion_proof : - History.t -> - history_proof -> - history_proof -> - inclusion_proof option tzresult - - val serialized_proof_of_string : string -> serialized_proof - - val inbox_message_counter : t -> Z.t - end - end - - include - Merkelized_operations - with type tree = Context.tree - and type inbox_context = Context.t - - module type P = sig - module Tree : - Context.TREE with type key = string list and type value = bytes - - type t = Tree.t - - type tree = Tree.tree - - val commit_tree : t -> string list -> tree -> unit Lwt.t - - val lookup_tree : t -> Hash.t -> tree option Lwt.t - - type proof - - val proof_encoding : proof Data_encoding.t - - val proof_before : proof -> Hash.t - - val verify_proof : - proof -> (tree -> (tree * 'a) Lwt.t) -> (tree * 'a) option Lwt.t - - val produce_proof : - Tree.t -> - tree -> - (tree -> (tree * 'a) Lwt.t) -> - (proof * 'a) option Lwt.t - end - - module Make_hashing_scheme (P : P) : - Merkelized_operations with type tree = P.tree and type inbox_context = P.t - val add_external_messages : context -> string list -> (t * Z.t * context) tzresult Lwt.t diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml index 855088a64605..62dfb6d94528 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml @@ -356,634 +356,4 @@ type serialized_proof = string let serialized_proof_encoding = Data_encoding.(string' Hex) -module type Merkelized_operations = sig - type inbox_context - - type tree - - val hash_level_tree : tree -> Hash.t - - val new_level_tree : inbox_context -> tree Lwt.t - - val add_messages : - inbox_context -> - History.t -> - t -> - Raw_level_repr.t -> - Sc_rollup_inbox_message_repr.serialized list -> - tree option -> - (tree * History.t * t) tzresult Lwt.t - - val add_messages_no_history : - inbox_context -> - t -> - Raw_level_repr.t -> - Sc_rollup_inbox_message_repr.serialized list -> - tree option -> - (tree * t) tzresult Lwt.t - - val get_message_payload : - tree -> Z.t -> Sc_rollup_inbox_message_repr.serialized option Lwt.t - - val form_history_proof : - inbox_context -> - History.t -> - t -> - tree option -> - (History.t * history_proof) tzresult Lwt.t - - val take_snapshot : t -> history_proof - - type inclusion_proof - - val inclusion_proof_encoding : inclusion_proof Data_encoding.t - - val pp_inclusion_proof : Format.formatter -> inclusion_proof -> unit - - val number_of_proof_steps : inclusion_proof -> int - - val verify_inclusion_proof : - inclusion_proof -> history_proof -> history_proof tzresult - - type proof - - val pp_proof : Format.formatter -> proof -> unit - - val to_serialized_proof : proof -> serialized_proof - - val of_serialized_proof : serialized_proof -> proof option - - val verify_proof : - Raw_level_repr.t * Z.t -> - history_proof -> - proof -> - Sc_rollup_PVM_sig.inbox_message option tzresult Lwt.t - - val produce_proof : - inbox_context -> - History.t -> - history_proof -> - Raw_level_repr.t * Z.t -> - (proof * Sc_rollup_PVM_sig.inbox_message option) tzresult Lwt.t - - val empty : inbox_context -> Raw_level_repr.t -> t Lwt.t - - module Internal_for_tests : sig - val eq_tree : tree -> tree -> bool - - val produce_inclusion_proof : - History.t -> - history_proof -> - history_proof -> - inclusion_proof option tzresult - - val serialized_proof_of_string : string -> serialized_proof - - val inbox_message_counter : t -> Z.t - end -end - -module type P = sig - module Tree : Context.TREE with type key = string list and type value = bytes - - type t = Tree.t - - type tree = Tree.tree - - val commit_tree : Tree.t -> string list -> Tree.tree -> unit Lwt.t - - val lookup_tree : Tree.t -> Hash.t -> tree option Lwt.t - - type proof - - val proof_encoding : proof Data_encoding.t - - val proof_before : proof -> Hash.t - - val verify_proof : - proof -> (tree -> (tree * 'a) Lwt.t) -> (tree * 'a) option Lwt.t - - val produce_proof : - Tree.t -> tree -> (tree -> (tree * 'a) Lwt.t) -> (proof * 'a) option Lwt.t -end - -module Make_hashing_scheme (P : P) : - Merkelized_operations with type tree = P.tree and type inbox_context = P.t = -struct - module Tree = P.Tree - - type inbox_context = P.t - - type tree = P.tree - - let hash_level_tree level_tree = Hash.of_context_hash (Tree.hash level_tree) - - let set_number_of_messages tree number_of_messages = - let number_of_messages_bytes = - Data_encoding.Binary.to_bytes_exn Data_encoding.n number_of_messages - in - Tree.add tree number_of_messages_key number_of_messages_bytes - - (** Initialise the merkle tree for a new level in the inbox. *) - let new_level_tree ctxt = - let tree = Tree.empty ctxt in - set_number_of_messages tree Z.zero - - let add_message inbox payload level_tree = - let open Lwt_result_syntax in - let message_index = inbox.message_counter in - let message_counter = Z.succ message_index in - let*! level_tree = - Tree.add - level_tree - (key_of_message message_index) - (Bytes.of_string - (payload : Sc_rollup_inbox_message_repr.serialized :> string)) - in - let*! level_tree = set_number_of_messages level_tree message_counter in - let nb_messages_in_commitment_period = - Int64.succ inbox.nb_messages_in_commitment_period - in - let inbox = - { - current_level_proof = inbox.current_level_proof; - level = inbox.level; - old_levels_messages = inbox.old_levels_messages; - message_counter; - nb_messages_in_commitment_period; - } - in - return (level_tree, inbox) - - let get_message_payload level_tree message_index = - let open Lwt_syntax in - let key = key_of_message message_index in - let* bytes = Tree.(find level_tree key) in - return - @@ Option.map - (fun bs -> - Sc_rollup_inbox_message_repr.unsafe_of_string (Bytes.to_string bs)) - bytes - - (** [no_history] creates an empty history with [capacity] set to - zero---this makes the [remember] function a no-op. We want this - behaviour in the protocol because we don't want to store - previous levels of the inbox. *) - let no_history = History.empty ~capacity:0L - - let take_snapshot inbox = inbox.old_levels_messages - - let key_of_level level = - let level_bytes = - Data_encoding.Binary.to_bytes_exn Raw_level_repr.encoding level - in - Bytes.to_string level_bytes - - let commit_tree ctxt tree inbox_level = - let key = [key_of_level inbox_level] in - P.commit_tree ctxt key tree - - let form_history_proof ctxt history inbox level_tree = - let open Lwt_result_syntax in - let*! () = - let*! tree = - match level_tree with - | Some tree -> Lwt.return tree - | None -> new_level_tree ctxt - in - commit_tree ctxt tree inbox.level - in - let prev_cell = inbox.old_levels_messages in - let prev_cell_ptr = hash_history_proof prev_cell in - let*? history = History.remember prev_cell_ptr prev_cell history in - let level_proof = current_level_proof inbox in - let cell = Skip_list.next ~prev_cell ~prev_cell_ptr level_proof in - return (history, cell) - - (** [archive_if_needed ctxt history inbox new_level level_tree] - is responsible for ensuring that the {!add_messages} function - below has a correctly set-up [level_tree] to which to add the - messages. If [new_level] is a higher level than the current inbox, - we create a new inbox level tree at that level in which to start - adding messages, and archive the earlier levels depending on the - [history] parameter's [capacity]. If [level_tree] is [None] (this - happens when the inbox is first created) we similarly create a new - empty level tree. - - This function and {!form_history_proof} are the only places we - begin new level trees. *) - let archive_if_needed ctxt history inbox new_level level_tree = - let open Lwt_result_syntax in - if Raw_level_repr.(inbox.level = new_level) then - match level_tree with - | Some tree -> return (history, inbox, tree) - | None -> - let*! tree = new_level_tree ctxt in - return (history, inbox, tree) - else - let* history, old_levels_messages = - form_history_proof ctxt history inbox level_tree - in - let*! tree = new_level_tree ctxt in - let inbox = - { - current_level_proof = inbox.current_level_proof; - nb_messages_in_commitment_period = - inbox.nb_messages_in_commitment_period; - old_levels_messages; - level = new_level; - message_counter = Z.zero; - } - in - return (history, inbox, tree) - - let add_messages ctxt history inbox level payloads level_tree = - let open Lwt_result_syntax in - let* () = - fail_when - (match payloads with [] -> true | _ -> false) - Tried_to_add_zero_messages - in - let* () = - fail_when - Raw_level_repr.(level < inbox.level) - (Invalid_level_add_messages level) - in - let* history, inbox, level_tree = - archive_if_needed ctxt history inbox level level_tree - in - let* level_tree, inbox = - List.fold_left_es - (fun (level_tree, inbox) payload -> - add_message inbox payload level_tree) - (level_tree, inbox) - payloads - in - let current_level_proof () = - let hash = hash_level_tree level_tree in - {hash; level} - in - return (level_tree, history, {inbox with current_level_proof}) - - let add_messages_no_history ctxt inbox level payloads level_tree = - let open Lwt_result_syntax in - let+ level_tree, _, inbox = - add_messages ctxt no_history inbox level payloads level_tree - in - (level_tree, inbox) - - (* An [inclusion_proof] is a path in the Merkelized skip list - showing that a given inbox history is a prefix of another one. - This path has a size logarithmic in the difference between the - levels of the two inboxes. - - [Irmin.Proof.{tree_proof, stream_proof}] could not be reused here - because there is no obvious encoding of sequences in these data - structures with the same guarantee about the size of proofs. *) - type inclusion_proof = history_proof list - - let inclusion_proof_encoding = - let open Data_encoding in - list history_proof_encoding - - let pp_inclusion_proof fmt proof = - Format.pp_print_list pp_history_proof fmt proof - - let number_of_proof_steps proof = List.length proof - - let lift_ptr_path deref ptr_path = - let rec aux accu = function - | [] -> Some (List.rev accu) - | x :: xs -> Option.bind (deref x) @@ fun c -> aux (c :: accu) xs - in - aux [] ptr_path - - let verify_inclusion_proof inclusion_proof snapshot_history_proof = - let open Result_syntax in - let rec aux (hash_map, ptr_list) = function - | [] -> error (Inbox_proof_error "inclusion proof is empty") - | [target] -> - let target_ptr = hash_history_proof target in - let hash_map = Hash.Map.add target_ptr target hash_map in - let ptr_list = target_ptr :: ptr_list in - ok (hash_map, List.rev ptr_list, target, target_ptr) - | history_proof :: tail -> - let ptr = hash_history_proof history_proof in - aux (Hash.Map.add ptr history_proof hash_map, ptr :: ptr_list) tail - in - let* hash_map, ptr_list, target, target_ptr = - aux (Hash.Map.empty, []) inclusion_proof - in - let deref ptr = Hash.Map.find ptr hash_map in - let cell_ptr = hash_history_proof snapshot_history_proof in - let* () = - error_unless - (Skip_list.valid_back_path - ~equal_ptr:Hash.equal - ~deref - ~cell_ptr - ~target_ptr - ptr_list) - (Inbox_proof_error "invalid inclusion proof") - in - return target - - type proof = - (* See the main docstring for this type (in the mli file) for - definitions of the three proof parameters [starting_point], - [message] and [snapshot]. In the below we deconstruct - [starting_point] into [(l, n)] where [l] is a level and [n] is a - message index. - - In a [Single_level] proof, [history_proof] is the skip list cell for the - level [l], [inc] is an inclusion proof of [history_proof] into [snapshot] - and [message_proof] is a tree proof showing that - - [exists level_tree . - (hash_level_tree level_tree = level.content) - AND (get_messages_payload n level_tree = (_, message))] - - Note: in the case that [message] is [None] this shows that there's no - value at the index [n]; in this case we also must check that - [history_proof] equals [snapshot] (otherwise, we'd need a [Next_level] - proof instead. *) - | Single_level of {inc : inclusion_proof; message_proof : P.proof} - (* See the main docstring for this type (in the mli file) for - definitions of the three proof parameters [starting_point], - [message] and [snapshot]. In the below we deconstruct - [starting_point] as [(l, n)] where [l] is a level and [n] is a - message index. - - In a [Next_level] proof, [lower_history_proof] is the skip list cell for - the level [l], [inc] is an inclusion proof of [lower_history_proof] into - [snapshot] and [lower_message_proof] is a tree proof showing that there - is no message at [(l, n)] with [lower_message_proof]. - - The first message to read at the next level of [l] is the - first input [Start_of_level]. - *) - | Next_level of {lower_message_proof : P.proof; inc : inclusion_proof} - - let pp_proof fmt proof = - match proof with - | Single_level _ -> Format.fprintf fmt "Single_level inbox proof" - | Next_level _ -> Format.fprintf fmt "Next_level inbox proof" - - let proof_encoding = - let open Data_encoding in - union - ~tag_size:`Uint8 - [ - case - ~title:"Single_level" - (Tag 0) - (obj2 - (req "inclusion_proof" inclusion_proof_encoding) - (req "message_proof" P.proof_encoding)) - (function - | Single_level {inc; message_proof} -> Some (inc, message_proof) - | _ -> None) - (fun (inc, message_proof) -> Single_level {inc; message_proof}); - case - ~title:"Next_level" - (Tag 1) - (obj2 - (req "lower_message_proof" P.proof_encoding) - (req "inclusion_proof" inclusion_proof_encoding)) - (function - | Next_level {lower_message_proof; inc} -> - Some (lower_message_proof, inc) - | _ -> None) - (fun (lower_message_proof, inc) -> - Next_level {lower_message_proof; inc}); - ] - - let of_serialized_proof = Data_encoding.Binary.of_string_opt proof_encoding - - let to_serialized_proof = Data_encoding.Binary.to_string_exn proof_encoding - - let proof_error reason = - let open Lwt_result_syntax in - tzfail (Inbox_proof_error reason) - - let check p reason = unless p (fun () -> proof_error reason) - - (** To construct or verify a tree proof we need a function of type - - [tree -> (tree, result) Lwt.t] - - where [result] is some data extracted from the tree that we care about - proving. [payload_and_message_tree n] is such a function, used for checking - the message at a particular index, [n]. - - For this function, the [result] is - - [payload : Sc_rollup_inbox_message_repr.serialized option] - - where [payload] is [None] if there was no message at the index. *) - let payload_and_message_tree n tree = - let open Lwt_syntax in - let* payload = get_message_payload tree n in - return (tree, payload) - - (** Utility function that handles all the verification needed for a - particular message proof at a particular level. It calls - [P.verify_proof], but also checks the proof has the correct - [P.proof_before] hash. *) - let check_message_proof message_proof level_hash n label = - let open Lwt_result_syntax in - let* () = - check - (Hash.equal level_hash (P.proof_before message_proof)) - (Format.sprintf "message_proof (%s) does not match history" label) - in - let*! result = P.verify_proof message_proof (payload_and_message_tree n) in - match result with - | None -> proof_error (Format.sprintf "message_proof is invalid (%s)" label) - | Some (_, payload_opt) -> return payload_opt - - let verify_proof (l, n) snapshot proof = - assert (Z.(geq n zero)) ; - let open Lwt_result_syntax in - match proof with - | Single_level {inc; message_proof} -> ( - let*? history_proof = verify_inclusion_proof inc snapshot in - let level_proof = Skip_list.content history_proof in - let* payload_opt = - check_message_proof message_proof level_proof.hash n "single level" - in - match payload_opt with - | None -> - if equal_history_proof snapshot history_proof then return_none - else proof_error "payload is None but proof.level not top level" - | Some payload -> - return_some - Sc_rollup_PVM_sig.{inbox_level = l; message_counter = n; payload}) - | Next_level {inc; lower_message_proof} -> ( - let*? lower_history_proof = verify_inclusion_proof inc snapshot in - (* TODO: https://gitlab.com/tezos/tezos/-/issues/3975 - We could prove that the last message to read is SOL, and is - before [n]. *) - let lower_level_proof = Skip_list.content lower_history_proof in - let* should_be_none = - check_message_proof - lower_message_proof - lower_level_proof.hash - n - "lower" - in - match should_be_none with - | None -> - let*? payload = - Sc_rollup_inbox_message_repr.(serialize (Internal Start_of_level)) - in - let inbox_level = Raw_level_repr.succ l in - let message_counter = Z.zero in - return_some - Sc_rollup_PVM_sig.{inbox_level; message_counter; payload} - | Some _ -> proof_error "more messages to read in current level") - - (** Utility function; we convert all our calls to be consistent with - [Lwt_result_syntax]. *) - let option_to_result e lwt_opt = - let open Lwt_syntax in - let* opt = lwt_opt in - match opt with None -> proof_error e | Some x -> return (ok x) - - let produce_proof ctxt history inbox (l, n) = - let open Lwt_result_syntax in - let deref ptr = History.find ptr history in - let compare {hash = _; level} = Raw_level_repr.compare level l in - let result = Skip_list.search ~deref ~compare ~cell:inbox in - let* inc, history_proof = - match result with - | Skip_list.{rev_path; last_cell = Found history_proof} -> - return (List.rev rev_path, history_proof) - | {last_cell = Nearest _; _} - | {last_cell = No_exact_or_lower_ptr; _} - | {last_cell = Deref_returned_none; _} -> - (* We are only interested to the result where [search] than a - path to the cell we were looking for. All the other cases - should be considered as an error. *) - proof_error - (Format.asprintf - "Skip_list.search failed to find a valid path: %a" - (Skip_list.pp_search_result ~pp_cell:pp_history_proof) - result) - in - let* level_tree = - option_to_result - "could not find level_tree in the inbox_context" - (P.lookup_tree ctxt (Skip_list.content history_proof).hash) - in - let* message_proof, payload_opt = - option_to_result - "failed to produce message proof for level_tree" - (P.produce_proof ctxt level_tree (payload_and_message_tree n)) - in - match payload_opt with - | Some payload -> - return - ( Single_level {inc; message_proof}, - Some - Sc_rollup_PVM_sig.{inbox_level = l; message_counter = n; payload} - ) - | None -> - if equal_history_proof inbox history_proof then - return (Single_level {inc; message_proof}, None) - else - let lower_message_proof = message_proof in - let* input_given = - let inbox_level = Raw_level_repr.succ l in - let message_counter = Z.zero in - let*? payload = - Sc_rollup_inbox_message_repr.(serialize (Internal Start_of_level)) - in - return_some - Sc_rollup_PVM_sig.{inbox_level; message_counter; payload} - in - return (Next_level {inc; lower_message_proof}, input_given) - - let empty context level = - let open Lwt_syntax in - let pre_genesis_level = Raw_level_repr.root in - let* initial_level = new_level_tree context in - let* () = commit_tree context initial_level pre_genesis_level in - let initial_level_proof = - let hash = hash_level_tree initial_level in - {hash; level = pre_genesis_level} - in - return - { - level; - message_counter = Z.zero; - nb_messages_in_commitment_period = 0L; - current_level_proof = (fun () -> initial_level_proof); - old_levels_messages = Skip_list.genesis initial_level_proof; - } - - module Internal_for_tests = struct - let eq_tree = Tree.equal - - let produce_inclusion_proof history a b = - let open Result_syntax in - let cell_ptr = hash_history_proof b in - let target_index = Skip_list.index a in - let* history = History.remember cell_ptr b history in - let deref ptr = History.find ptr history in - Skip_list.back_path ~deref ~cell_ptr ~target_index - |> Option.map (lift_ptr_path deref) - |> Option.join |> return - - let serialized_proof_of_string x = x - - let inbox_message_counter = inbox_message_counter - end -end - -include ( - Make_hashing_scheme (struct - module Tree = struct - include Context.Tree - - type t = Context.t - - type tree = Context.tree - - type value = bytes - - type key = string list - end - - type t = Context.t - - type tree = Context.tree - - let commit_tree _ctxt _key _tree = - (* This is a no-op in the protocol inbox implementation *) - Lwt.return () - - let lookup_tree _ctxt _hash = - (* We cannot find the tree without a full inbox_context *) - Lwt.return None - - type proof = Context.Proof.tree Context.Proof.t - - let proof_encoding = Context.Proof_encoding.V1.Tree32.tree_proof_encoding - - let proof_before proof = - match proof.Context.Proof.before with - | `Value hash | `Node hash -> Hash.of_context_hash hash - - let verify_proof p f = - Lwt.map Result.to_option (Context.verify_tree_proof p f) - - let produce_proof _ _ _ = - (* We cannot produce a proof without full inbox_context *) - Lwt.return None - end) : - Merkelized_operations - with type tree = Context.tree - and type inbox_context = Context.t) - type inbox = t diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli index 6019ceac639f..4255d07f7ce5 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli @@ -225,238 +225,4 @@ type serialized_proof val serialized_proof_encoding : serialized_proof Data_encoding.t -(** The following operations are subject to cross-validation between - rollup nodes and the layer 1. *) -module type Merkelized_operations = sig - (** The type for the Merkle trees used in this module. *) - type tree - - (** The context used by the trees. *) - type inbox_context - - (** Standard hashing function used for trees in this module. *) - val hash_level_tree : tree -> Hash.t - - (** Initialise a new level. [new_level_tree ctxt level] is a merkle - tree with no messages yet, but has the [level] stored so we can - check that in proofs. *) - val new_level_tree : inbox_context -> tree Lwt.t - - (** [add_messages ctxt history inbox level payloads level_tree] inserts - a list of [payloads] as new messages in the [level_tree] of the - current [level] of the [inbox]. This function returns the new level - tree as well as updated [inbox] and [history]. - - If the [inbox]'s level is older than [level], the [inbox] is - updated so that the level trees of the levels older than [level] - are archived. To archive a [level_tree] for a given [level], we - push it at the end of the [history] and update the witness of this - history in the [inbox]. The [inbox]'s level tree for the current - level is emptied to insert the [payloads] in a fresh [level_tree] - for [level]. - - This function fails if [level] is older than [inbox]'s [level]. - *) - val add_messages : - inbox_context -> - History.t -> - t -> - Raw_level_repr.t -> - Sc_rollup_inbox_message_repr.serialized list -> - tree option -> - (tree * History.t * t) tzresult Lwt.t - - (** [add_messages_no_history ctxt inbox level payloads level_tree] behaves - as {!add_external_messages} except that it does not remember the inbox - history. *) - val add_messages_no_history : - inbox_context -> - t -> - Raw_level_repr.t -> - Sc_rollup_inbox_message_repr.serialized list -> - tree option -> - (tree * t, error trace) result Lwt.t - - (** [get_message_payload level_tree idx] returns [Some payload] if the - [level_tree] has more than [idx] messages, and [payload] is at - position [idx]. Returns [None] otherwise. *) - val get_message_payload : - tree -> Z.t -> Sc_rollup_inbox_message_repr.serialized option Lwt.t - - (** [form_history_proof ctxt history inbox level_tree] creates the - skip list structure that includes the current inbox level, while - also updating the [history] and making sure the [level_tree] has - been committed to the [ctxt]. - - This is used in [archive_if_needed] to produce the - [old_levels_messages] value for the next level of the inbox. It is - also needed if you want to produce a fully-up-to-date skip list - for proof production. Just taking the skip list stored in the - inbox at [old_levels_messages] will not include the current level - (and that current level could be quite far back in terms of blocks - if the inbox hasn't been added to for a while). *) - val form_history_proof : - inbox_context -> - History.t -> - t -> - tree option -> - (History.t * history_proof) tzresult Lwt.t - - (** This is similar to {!form_history_proof} except that it is just to - be used on the protocol side because it doesn't ensure the history - is remembered or the trees are committed in the context. Used at - the beginning of a refutation game to create the snapshot against - which proofs in that game must be valid. - - One important note: - It takes the snapshot of the inbox for the current level. The snapshot - points to the inbox at the *beginning* of the current block level. - This prevents to create a mid-level snapshot for a refutation game - if new messages are added before and/or after in the same block. - *) - val take_snapshot : t -> history_proof - - (** Given a inbox [A] at some level [L] and another inbox [B] at - some level [L' >= L], an [inclusion_proof] guarantees that [A] is - an older version of [B]. - - To be more precise, an [inclusion_proof] guarantees that the - previous levels [level_tree]s of [A] are included in the previous - levels [level_tree]s of [B]. The current [level_tree] of [A] and [B] - are not considered. - - The size of this proof is O(log_basis (L' - L)). *) - type inclusion_proof - - val inclusion_proof_encoding : inclusion_proof Data_encoding.t - - val pp_inclusion_proof : Format.formatter -> inclusion_proof -> unit - - (** [number_of_proof_steps proof] returns the length of [proof]. *) - val number_of_proof_steps : inclusion_proof -> int - - (** [verify_inclusion_proof proof snapshot] returns [a] iff [proof] is a - minimal and valid proof that [a] is included in [snapshot], fails - otherwise. [a] is part of the proof. *) - val verify_inclusion_proof : - inclusion_proof -> history_proof -> history_proof tzresult - - (** An inbox proof has three parameters: - - - the [starting_point], of type [Raw_level_repr.t * Z.t], specifying - a location in the inbox ; - - - the [message], of type [Sc_rollup_PVM_sig.input option] ; - - - and a reference [snapshot] inbox. - - A valid inbox proof implies the following semantics: beginning at - [starting_point] and reading forward through [snapshot], the first - message you reach will be [message]. - - Usually this is fairly simple because there will actually be a - message at the location specified by [starting_point]. But in some - cases [starting_point] is past the last message within a level, - and then the inbox proof must prove that and also provide another - proof about the message at the beginning of the next non-empty - level. *) - type proof - - val pp_proof : Format.formatter -> proof -> unit - - val to_serialized_proof : proof -> serialized_proof - - val of_serialized_proof : serialized_proof -> proof option - - (** See the docstring for the [proof] type for details of proof semantics. - - [verify_proof starting_point inbox proof] will return the third - parameter of the proof, [message], iff the proof is valid. *) - val verify_proof : - Raw_level_repr.t * Z.t -> - history_proof -> - proof -> - Sc_rollup_PVM_sig.inbox_message option tzresult Lwt.t - - (** [produce_proof ctxt history inbox (level, counter)] creates an - inbox proof proving the first message after the index [counter] at - location [level]. This will fail if the [ctxt] given doesn't have - sufficient data (it needs to be run on an [inbox_context] with the - full history). *) - val produce_proof : - inbox_context -> - History.t -> - history_proof -> - Raw_level_repr.t * Z.t -> - (proof * Sc_rollup_PVM_sig.inbox_message option) tzresult Lwt.t - - (** [empty ctxt level] is an inbox started at some given [level] with no - message at all. *) - val empty : inbox_context -> Raw_level_repr.t -> t Lwt.t - - module Internal_for_tests : sig - val eq_tree : tree -> tree -> bool - - (** [produce_inclusion_proof history a b] exploits [history] to produce - a self-contained proof that [a] is an older version of [b]. *) - val produce_inclusion_proof : - History.t -> - history_proof -> - history_proof -> - inclusion_proof option tzresult - - (** Allows to create a dumb {!serialized_proof} from a string, instead - of serializing a proof with {!to_serialized_proof}. *) - val serialized_proof_of_string : string -> serialized_proof - - (** [inbox_message_counter inbox] returns the [inbox]'s message counter. *) - val inbox_message_counter : t -> Z.t - end -end - -module type P = sig - module Tree : Context.TREE with type key = string list and type value = bytes - - type tree = Tree.tree - - type t = Tree.t - - val commit_tree : t -> string list -> tree -> unit Lwt.t - - val lookup_tree : t -> Hash.t -> tree option Lwt.t - - type proof - - val proof_encoding : proof Data_encoding.t - - val proof_before : proof -> Hash.t - - val verify_proof : - proof -> (tree -> (tree * 'a) Lwt.t) -> (tree * 'a) option Lwt.t - - val produce_proof : - Tree.t -> tree -> (tree -> (tree * 'a) Lwt.t) -> (proof * 'a) option Lwt.t -end - -(** - - This validation is based on a standardized Merkelization - scheme. The definition of this scheme is independent from the exact - data model of the context but it depends on the [Tree] arity and - internal hashing scheme. - - We provide a functor that takes a {!Context.TREE} module from any - context, checks that the assumptions made about tree's arity and - hashing scheme are valid, and returns a standard compliant - implementation of the {!Merkelized_operations}. - -*) -module Make_hashing_scheme (P : P) : - Merkelized_operations with type tree = P.tree and type inbox_context = P.t - -include - Merkelized_operations - with type tree = Context.tree - and type inbox_context = Context.t - type inbox = t -- GitLab From c78963c7af466f9679d87cd5205cd2b6b5f4be71 Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Thu, 17 Nov 2022 16:39:46 +0100 Subject: [PATCH 2/8] proto/scoru: remove message_counter from inbox metadata --- .../lib_protocol/sc_rollup_inbox_repr.ml | 24 +++---------------- 1 file changed, 3 insertions(+), 21 deletions(-) diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml index 62dfb6d94528..528f01fbe94b 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml @@ -202,8 +202,6 @@ module V1 = struct The metadata contains : - [level] : the inbox level ; - - [message_counter] : the number of messages in the [level]'s inbox ; - the number of messages that have not been consumed by a commitment cementing ; - [nb_messages_in_commitment_period] : the number of messages during the commitment period ; - [current_level_proof] : the [current_level] and its root hash ; @@ -222,7 +220,6 @@ module V1 = struct type t = { level : Raw_level_repr.t; nb_messages_in_commitment_period : int64; - message_counter : Z.t; (* Lazy to avoid hashing O(n^2) time in [add_messages] *) current_level_proof : unit -> level_proof; old_levels_messages : history_proof; @@ -238,7 +235,6 @@ module V1 = struct let { level; nb_messages_in_commitment_period; - message_counter; current_level_proof; old_levels_messages; } = @@ -249,7 +245,6 @@ module V1 = struct equal nb_messages_in_commitment_period inbox2.nb_messages_in_commitment_period) - && Z.equal message_counter inbox2.message_counter && equal_level_proof (current_level_proof ()) (inbox2.current_level_proof ()) @@ -259,7 +254,6 @@ module V1 = struct { level; nb_messages_in_commitment_period; - message_counter; current_level_proof; old_levels_messages; } = @@ -268,7 +262,6 @@ module V1 = struct "@[{ level = %a@;\ current messages hash = %a@;\ nb_messages_in_commitment_period = %s@;\ - message_counter = %a@;\ old_levels_messages = %a@;\ }@]" Raw_level_repr.pp @@ -276,15 +269,11 @@ module V1 = struct pp_level_proof (current_level_proof ()) (Int64.to_string nb_messages_in_commitment_period) - Z.pp_print - message_counter pp_history_proof old_levels_messages let inbox_level inbox = inbox.level - let inbox_message_counter inbox = inbox.message_counter - let old_levels_messages inbox = inbox.old_levels_messages let current_level_proof inbox = inbox.current_level_proof () @@ -293,31 +282,26 @@ module V1 = struct Data_encoding.( conv (fun { - message_counter; nb_messages_in_commitment_period; level; current_level_proof; old_levels_messages; } -> - ( message_counter, - nb_messages_in_commitment_period, + ( nb_messages_in_commitment_period, level, current_level_proof (), old_levels_messages )) - (fun ( message_counter, - nb_messages_in_commitment_period, + (fun ( nb_messages_in_commitment_period, level, current_level_proof, old_levels_messages ) -> { - message_counter; nb_messages_in_commitment_period; level; current_level_proof = (fun () -> current_level_proof); old_levels_messages; }) - (obj5 - (req "message_counter" n) + (obj4 (req "nb_messages_in_commitment_period" int64) (req "level" Raw_level_repr.encoding) (req "current_level_proof" level_proof_encoding) @@ -350,8 +334,6 @@ let to_versioned inbox = V1 inbox [@@inline] let key_of_message ix = ["message"; Data_encoding.Binary.to_string_exn Data_encoding.n ix] -let number_of_messages_key = ["number_of_messages"] - type serialized_proof = string let serialized_proof_encoding = Data_encoding.(string' Hex) -- GitLab From 55647c4810224a25165d802e655cd65ccdce5c3d Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Thu, 17 Nov 2022 16:42:40 +0100 Subject: [PATCH 3/8] proto/scoru: replace context tree by skip list for level tree --- src/proto_alpha/bin_sc_rollup_node/context.ml | 47 -- .../bin_sc_rollup_node/context.mli | 38 -- src/proto_alpha/bin_sc_rollup_node/inbox.ml | 65 +- src/proto_alpha/bin_sc_rollup_node/inbox.mli | 19 +- .../bin_sc_rollup_node/refutation_game.ml | 16 +- src/proto_alpha/bin_sc_rollup_node/store.ml | 20 + src/proto_alpha/bin_sc_rollup_node/store.mli | 10 + .../sc_rollup_benchmarks.ml | 11 +- .../lib_protocol/alpha_context.mli | 82 ++- src/proto_alpha/lib_protocol/raw_context.ml | 3 +- src/proto_alpha/lib_protocol/raw_context.mli | 6 +- ...p_inbox_merkelized_payload_hashes_repr.mli | 2 +- .../lib_protocol/sc_rollup_inbox_repr.ml | 630 +++++++++++++++++- .../lib_protocol/sc_rollup_inbox_repr.mli | 177 ++++- .../lib_protocol/sc_rollup_inbox_storage.ml | 5 +- .../lib_protocol/sc_rollup_proof_repr.ml | 23 +- .../lib_protocol/sc_rollup_proof_repr.mli | 8 +- .../test/helpers/sc_rollup_helpers.ml | 108 +-- .../integration/operations/test_sc_rollup.ml | 55 +- .../test/pbt/test_refutation_game.ml | 47 +- .../test/pbt/test_sc_rollup_encoding.ml | 13 +- .../test/unit/test_sc_rollup_game.ml | 3 +- .../test/unit/test_sc_rollup_inbox_legacy.ml | 348 +++++----- 23 files changed, 1252 insertions(+), 484 deletions(-) diff --git a/src/proto_alpha/bin_sc_rollup_node/context.ml b/src/proto_alpha/bin_sc_rollup_node/context.ml index ea9ec24f8d69..104695f9e54c 100644 --- a/src/proto_alpha/bin_sc_rollup_node/context.ml +++ b/src/proto_alpha/bin_sc_rollup_node/context.ml @@ -175,56 +175,9 @@ struct return None end -(** Aggregated collection of messages from the L1 inbox *) -module MessageTrees = struct - type value = tree - - let key = ["message_tree"] - - let find ctxt = IStore.Tree.find_tree ctxt.tree key - - let set ctxt tree = - let open Lwt_syntax in - let* tree = IStore.Tree.add_tree ctxt.tree key tree in - let ctxt = {ctxt with tree} in - return ctxt -end - module Inbox = struct include Sc_rollup.Inbox module Message = Sc_rollup.Inbox_message - - include Sc_rollup.Inbox.Make_hashing_scheme (struct - include - Proof - (Hash) - (struct - let proof_encoding = - Tezos_context_merkle_proof_encoding.Merkle_proof_encoding.V1.Tree32 - .tree_proof_encoding - end) - - type t = rw_index - - let commit_tree index _key tree = - let open Lwt_syntax in - let info () = IStore.Info.v ~author:"Tezos" 0L ~message:"" in - let* (_ : IStore.commit) = - IStore.Commit.v index.repo ~info:(info ()) ~parents:[] tree - in - return () - - let from_inbox_hash inbox_hash = - let ctxt_hash = Hash.to_context_hash inbox_hash in - let store_hash = - IStore.Hash.unsafe_of_raw_string - (Tezos_crypto.Context_hash.to_string ctxt_hash) - in - `Node store_hash - - let lookup_tree index hash = - IStore.Tree.of_hash index.repo (from_inbox_hash hash) - end) end (** State of the PVM that this rollup node deals with. *) diff --git a/src/proto_alpha/bin_sc_rollup_node/context.mli b/src/proto_alpha/bin_sc_rollup_node/context.mli index a437e86b166f..8d1ebea2cd00 100644 --- a/src/proto_alpha/bin_sc_rollup_node/context.mli +++ b/src/proto_alpha/bin_sc_rollup_node/context.mli @@ -23,8 +23,6 @@ (* *) (*****************************************************************************) -open Protocol -open Alpha_context open Store_sigs (** The type of indexed repository for contexts. The parameter indicates if the @@ -152,42 +150,6 @@ end) : sig proof -> (tree -> (tree * 'a) Lwt.t) -> (tree * 'a) option Lwt.t end -(** Aggregated collection of messages from the L1 inbox. *) -module MessageTrees : sig - (** The value of a messages tree *) - type value - - (** [find context] returns the messages tree stored in the [context], if any. *) - val find : _ t -> value option Lwt.t - - (** [set context msg_tree] saves the messages tree [msg_tree] in the context - and returns the updated context. Note: [set] does not perform any write on - disk, this information must be committed using {!commit}. *) - val set : 'a t -> value -> 'a t Lwt.t -end - -(** L1 inboxes representation in the rollup node. This is a version of the - protocols inboxes specialized to message trees ({!MessageTrees}) and which - can produce proofs for inboxes stored in the context. *) -module Inbox : sig - type t = Sc_rollup.Inbox.t - - module Message : module type of Sc_rollup.Inbox_message - - val pp : Format.formatter -> t -> unit - - val encoding : t Data_encoding.t - - val inbox_level : t -> Raw_level.t - - type history_proof = Sc_rollup.Inbox.history_proof - - include - Sc_rollup.Inbox.Merkelized_operations - with type tree = MessageTrees.value - and type inbox_context = rw_index -end - (** State of the PVM that this rollup node deals with *) module PVMState : sig (** The value of a PVM state *) diff --git a/src/proto_alpha/bin_sc_rollup_node/inbox.ml b/src/proto_alpha/bin_sc_rollup_node/inbox.ml index 997f04f8f41e..3de014eee1a2 100644 --- a/src/proto_alpha/bin_sc_rollup_node/inbox.ml +++ b/src/proto_alpha/bin_sc_rollup_node/inbox.ml @@ -38,6 +38,8 @@ module State = struct let add_history = Store.Histories.add + let add_messages_history = Store.Level_tree_histories.add + let level_of_hash = State.level_of_hash (** [inbox_of_head node_ctxt store block] returns the latest inbox at the @@ -165,38 +167,46 @@ let same_inbox_as_layer_1 node_ctxt head_hash inbox = (Sc_rollup.Inbox.equal layer1_inbox inbox) (Sc_rollup_node_errors.Inconsistent_inbox {layer1_inbox; inbox}) -let add_messages (node_ctxt : _ Node_context.t) ctxt level inbox history - messages = +let add_messages level inbox history messages = let open Lwt_result_syntax in - let*! messages_tree = Context.MessageTrees.find ctxt in + let messages_history = + (* TODO: https://gitlab.com/tezos/tezos/-/issues/3978 + + We need to set a geq value than the actual number of messages here. *) + Sc_rollup.Inbox_merkelized_payload_hashes.History.empty ~capacity:10000L + in lift @@ - if messages = [] then return (history, inbox, ctxt) + if messages = [] then return (messages_history, None, history, inbox) else let*? messages = List.map_e Sc_rollup.Inbox_message.serialize messages in (* TODO: https://gitlab.com/tezos/tezos/-/issues/3978 - The number of messages during commitment period is broken with the - unique inbox. *) - (* - let commitment_period = - node_ctxt.protocol_constants.parametric.sc_rollup - .commitment_period_in_blocks |> Int32.of_int - in - let inbox = - Sc_rollup.Inbox.refresh_commitment_period ~commitment_period ~level inbox - in - *) - let* messages_tree, history, inbox = - Context.Inbox.add_messages - node_ctxt.context + + The number of messages during commitment period is broken with the + unique inbox. *) + (* let commitment_period = + * node_ctxt.protocol_constants.parametric.sc_rollup + * .commitment_period_in_blocks |> Int32.of_int + * in + * let inbox = + * Sc_rollup.Inbox.refresh_commitment_period + * ~commitment_period + * ~level + * inbox + * in *) + let*? messages_history, messages_tree, history, inbox = + Sc_rollup.Inbox.add_messages + messages_history history inbox level messages - messages_tree + None in - let*! ctxt = Context.MessageTrees.set ctxt messages_tree in - return (history, inbox, ctxt) + let messages_tree_hash = + Sc_rollup.Inbox_merkelized_payload_hashes.hash messages_tree + in + return (messages_history, Some messages_tree_hash, history, inbox) let process_head (node_ctxt : _ Node_context.t) Layer1.({level; hash = head_hash} as head) = @@ -228,10 +238,19 @@ let process_head (node_ctxt : _ Node_context.t) return (Context.empty node_ctxt.context) else Node_context.checkout_context node_ctxt predecessor.hash in - let* history, inbox, ctxt = - add_messages node_ctxt ctxt level inbox history messages + let* messages_history, messages_hash, history, inbox = + add_messages level inbox history messages in let* () = same_inbox_as_layer_1 node_ctxt head_hash inbox in + let*! () = + match messages_hash with + | None -> Lwt.return_unit + | Some messages_hash -> + State.add_messages_history + node_ctxt.store + messages_hash + messages_history + in let*! () = State.add_inbox node_ctxt.store head_hash inbox in let*! () = State.add_history node_ctxt.store head_hash history in return ctxt diff --git a/src/proto_alpha/bin_sc_rollup_node/inbox.mli b/src/proto_alpha/bin_sc_rollup_node/inbox.mli index 12873db7bc7b..fb58fde7e48e 100644 --- a/src/proto_alpha/bin_sc_rollup_node/inbox.mli +++ b/src/proto_alpha/bin_sc_rollup_node/inbox.mli @@ -67,15 +67,18 @@ val history_of_head : (** [start ()] initializes the inbox to track the messages being published. *) val start : unit -> unit Lwt.t -(** [add_messages node_ctxt ctxt inbox_level inbox history messages] adds +(** [add_messages inbox_level inbox history messages] adds [messages] to the [inbox] whose history is [history]. The new inbox level is - given as [inbox_level]. It takes a context [ctxt] and returns a new - [history], [inbox] and context [ctxt] with an updated message tree. *) + given as [inbox_level]. Returns an updated [history] and [inbox], and a new + [messages_history] and [messages_hash]. *) val add_messages : - Node_context.rw -> - 'a Context.t -> Raw_level.t -> Sc_rollup.Inbox.t -> - Sc_rollup.Inbox.History.t -> - Sc_rollup.Inbox_message.t list -> - (Sc_rollup.Inbox.History.t * Sc_rollup.Inbox.t * 'a Context.t) tzresult Lwt.t + Store.Histories.value -> + Sc_rollup.Inbox_message.t trace -> + (Store.Level_tree_histories.value + * Store.Level_tree_histories.key option + * Store.Histories.value + * Sc_rollup.Inbox.t) + tzresult + Lwt.t diff --git a/src/proto_alpha/bin_sc_rollup_node/refutation_game.ml b/src/proto_alpha/bin_sc_rollup_node/refutation_game.ml index e4e01ac8d505..99482033b09d 100644 --- a/src/proto_alpha/bin_sc_rollup_node/refutation_game.ml +++ b/src/proto_alpha/bin_sc_rollup_node/refutation_game.ml @@ -177,14 +177,9 @@ module Make (Interpreter : Interpreter.S) : Node_context.checkout_context node_ctxt snapshot_hash in let snapshot_ctxt_index = Context.index snapshot_ctxt in - let*! snapshot_messages_tree = Context.MessageTrees.find snapshot_ctxt in - let* snapshot_history, snapshot = - Context.Inbox.form_history_proof - snapshot_ctxt_index - snapshot_history - snapshot_inbox - snapshot_messages_tree - >|= Environment.wrap_tzresult + let*? snapshot_history, snapshot = + Sc_rollup.Inbox.form_history_proof snapshot_history snapshot_inbox + |> Environment.wrap_tzresult in let* dal_slots_history = Dal_slots_tracker.slots_history_of_hash node_ctxt snapshot_head @@ -226,11 +221,12 @@ module Make (Interpreter : Interpreter.S) : match res with Ok data -> return @@ Some data | Error _ -> return None module Inbox_with_history = struct - include Context.Inbox - let history = snapshot_history let inbox = snapshot + + let get_level_tree_history = + Store.Level_tree_histories.get node_ctxt.Node_context.store end module Dal_with_history = struct diff --git a/src/proto_alpha/bin_sc_rollup_node/store.ml b/src/proto_alpha/bin_sc_rollup_node/store.ml index ebfdb2f4753f..fc36d8180fc4 100644 --- a/src/proto_alpha/bin_sc_rollup_node/store.ml +++ b/src/proto_alpha/bin_sc_rollup_node/store.ml @@ -211,6 +211,26 @@ module Histories = let encoding = Sc_rollup.Inbox.History.encoding end) +(** level tree history for the inbox at a given block *) +module Level_tree_histories = + Make_append_only_map + (struct + let path = ["level_tree_histories"] + end) + (struct + type key = Sc_rollup.Inbox_merkelized_payload_hashes.Hash.t + + let to_path_representation = + Sc_rollup.Inbox_merkelized_payload_hashes.Hash.to_b58check + end) + (struct + let name = "level_tree_history" + + type value = Sc_rollup.Inbox_merkelized_payload_hashes.History.t + + let encoding = Sc_rollup.Inbox_merkelized_payload_hashes.History.encoding + end) + module Commitments = Make_append_only_map (struct diff --git a/src/proto_alpha/bin_sc_rollup_node/store.mli b/src/proto_alpha/bin_sc_rollup_node/store.mli index 9031a9921a5f..41088473123b 100644 --- a/src/proto_alpha/bin_sc_rollup_node/store.mli +++ b/src/proto_alpha/bin_sc_rollup_node/store.mli @@ -123,6 +123,16 @@ module Histories : and type value = Sc_rollup.Inbox.History.t and type 'a store = 'a store +(** messages histories from the rollup node. Each history contains the messages + of one level. The store is indexed by a level in order to maintain a small + structure in memory. Only the message history of one level is fetched when + computing the proof. *) +module Level_tree_histories : + Store_sigs.Append_only_map + with type key = Sc_rollup.Inbox_merkelized_payload_hashes.Hash.t + and type value = Sc_rollup.Inbox_merkelized_payload_hashes.History.t + and type 'a store = 'a store + (** Storage containing commitments and corresponding commitment hashes that the rollup node has knowledge of. *) module Commitments : diff --git a/src/proto_alpha/lib_benchmarks_proto/sc_rollup_benchmarks.ml b/src/proto_alpha/lib_benchmarks_proto/sc_rollup_benchmarks.ml index b26521b796ff..2a1d655260c7 100644 --- a/src/proto_alpha/lib_benchmarks_proto/sc_rollup_benchmarks.ml +++ b/src/proto_alpha/lib_benchmarks_proto/sc_rollup_benchmarks.ml @@ -265,19 +265,17 @@ module Sc_rollup_add_external_messages_benchmark = struct add_messages_for_level ctxt inbox in let* _rollup, ctxt = ctxt_with_rollup in - let*! inbox = - Sc_rollup_inbox_repr.empty - (Raw_context.recover ctxt) - (Raw_context.current_level ctxt).level + let inbox = + Sc_rollup_inbox_repr.empty (Raw_context.current_level ctxt).level in let* inbox, ctxt = add_messages_for_level ctxt inbox in let messages = Raw_context.Sc_rollup_in_memory_inbox.current_messages ctxt in - return (inbox, ctxt, messages) + return (inbox, messages) in - let inbox, ctxt, current_messages = + let inbox, current_messages = match Lwt_main.run @@ prepare_benchmark_scenario () with | Ok result -> result | Error _ -> assert false @@ -287,7 +285,6 @@ module Sc_rollup_add_external_messages_benchmark = struct let closure () = ignore (Sc_rollup_inbox_repr.add_messages_no_history - (Raw_context.recover ctxt) inbox last_level [message] diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 33401afc5576..3c35a258bcaf 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -3316,6 +3316,82 @@ module Sc_rollup : sig val serialized_proof_encoding : serialized_proof Data_encoding.t + val add_messages : + Inbox_merkelized_payload_hashes.History.t -> + History.t -> + t -> + Raw_level.t -> + Inbox_message.serialized list -> + Inbox_merkelized_payload_hashes.t option -> + (Inbox_merkelized_payload_hashes.History.t + * Inbox_merkelized_payload_hashes.t + * History.t + * t) + tzresult + + val add_messages_no_history : + t -> + Raw_level.t -> + Inbox_message.serialized list -> + Inbox_merkelized_payload_hashes.t option -> + (Inbox_merkelized_payload_hashes.t * t) tzresult + + val form_history_proof : + History.t -> t -> (History.t * history_proof) tzresult + + val take_snapshot : t -> history_proof + + type inclusion_proof + + val inclusion_proof_encoding : inclusion_proof Data_encoding.t + + val pp_inclusion_proof : Format.formatter -> inclusion_proof -> unit + + val number_of_proof_steps : inclusion_proof -> int + + val verify_inclusion_proof : + inclusion_proof -> history_proof -> history_proof tzresult + + type proof + + val pp_proof : Format.formatter -> proof -> unit + + val to_serialized_proof : proof -> serialized_proof + + val of_serialized_proof : serialized_proof -> proof option + + val verify_proof : + Raw_level.t * Z.t -> + history_proof -> + proof -> + inbox_message option tzresult + + val produce_proof : + get_level_tree_history: + (Inbox_merkelized_payload_hashes.Hash.t -> + Inbox_merkelized_payload_hashes.History.t Lwt.t) -> + History.t -> + history_proof -> + Raw_level.t * Z.t -> + (proof * inbox_message option) tzresult Lwt.t + + val empty : Raw_level.t -> t + + module Internal_for_tests : sig + val eq_tree : + Inbox_merkelized_payload_hashes.t -> + Inbox_merkelized_payload_hashes.t -> + bool + + val produce_inclusion_proof : + History.t -> + history_proof -> + history_proof -> + inclusion_proof option tzresult + + val serialized_proof_of_string : string -> serialized_proof + end + val add_external_messages : context -> string list -> (t * Z.t * context) tzresult Lwt.t @@ -3722,11 +3798,13 @@ module Sc_rollup : sig val reveal : Reveal_hash.t -> string option Lwt.t module Inbox_with_history : sig - include Inbox.Merkelized_operations with type inbox_context = context - val inbox : Inbox.history_proof val history : Inbox.History.t + + val get_level_tree_history : + Inbox_merkelized_payload_hashes.Hash.t -> + Inbox_merkelized_payload_hashes.History.t Lwt.t end module Dal_with_history : sig diff --git a/src/proto_alpha/lib_protocol/raw_context.ml b/src/proto_alpha/lib_protocol/raw_context.ml index ee9815358c6d..3ca2c5123afa 100644 --- a/src/proto_alpha/lib_protocol/raw_context.ml +++ b/src/proto_alpha/lib_protocol/raw_context.ml @@ -258,7 +258,8 @@ type back = { Tez_repr.t Signature.Public_key_hash.Map.t option; tx_rollup_current_messages : Tx_rollup_inbox_repr.Merkle.tree Tx_rollup_repr.Map.t; - sc_rollup_current_messages : Context.tree option; + sc_rollup_current_messages : + Sc_rollup_inbox_merkelized_payload_hashes_repr.t option; dal_slot_fee_market : Dal_slot_repr.Slot_market.t; (* DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3105 diff --git a/src/proto_alpha/lib_protocol/raw_context.mli b/src/proto_alpha/lib_protocol/raw_context.mli index 40e392c4414c..f7e6114a41c1 100644 --- a/src/proto_alpha/lib_protocol/raw_context.mli +++ b/src/proto_alpha/lib_protocol/raw_context.mli @@ -387,9 +387,11 @@ module Tx_rollup : sig end module Sc_rollup_in_memory_inbox : sig - val current_messages : t -> Context.tree option + val current_messages : + t -> Sc_rollup_inbox_merkelized_payload_hashes_repr.t option - val set_current_messages : t -> Context.tree -> t + val set_current_messages : + t -> Sc_rollup_inbox_merkelized_payload_hashes_repr.t -> t end module Dal : sig diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli index 0872181e6c2e..c204bf0f6f45 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli @@ -99,7 +99,7 @@ val get_payload_hash : t -> Sc_rollup_inbox_message_repr.Hash.t val get_index : t -> int (** Given two t [(a, b)] and a {!Sc_rollup_inbox_message_repr.serialized} -[payload], a [proof] guarantees that [payload] hash is equal to [a] and that + [payload], a [proof] guarantees that [payload] hash is equal to [a] and that [a] is an ancestor of [b]; i.e. [get_index a < get_index b]. *) type proof diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml index 528f01fbe94b..b63beccfe5c8 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml @@ -41,10 +41,11 @@ To solve (1), we use a proof tree H which is implemented by a merkelized skip list allowing for compact inclusion proofs (See {!skip_list_repr.ml}). - To solve (2), we maintain a separate proof tree C witnessing the - contents of messages of the current level. + To solve (2), we maintain a separate proof tree C witnessing the contents of + messages of the current level also implemented by a merkelized skip list for + the same reason. - The protocol maintains the hashes of the head of H, and the root hash of C. + The protocol maintains the hashes of the head of H and C. The rollup node needs to maintain a full representation for C and a partial representation for H back to the level of the LCC. @@ -135,17 +136,26 @@ end module Skip_list = Skip_list_repr.Make (Skip_list_parameters) module V1 = struct - type level_proof = {hash : Hash.t; level : Raw_level_repr.t} + type level_proof = { + hash : Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash.t; + level : Raw_level_repr.t; + } let level_proof_encoding = let open Data_encoding in conv (fun {hash; level} -> (hash, level)) (fun (hash, level) -> {hash; level}) - (obj2 (req "hash" Hash.encoding) (req "level" Raw_level_repr.encoding)) + (obj2 + (req + "hash" + Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash.encoding) + (req "level" Raw_level_repr.encoding)) let equal_level_proof {hash; level} level_proof_2 = - Hash.equal hash level_proof_2.hash + Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash.equal + hash + level_proof_2.hash && Raw_level_repr.equal level level_proof_2.level type history_proof = (level_proof, Hash.t) Skip_list.cell @@ -153,7 +163,7 @@ module V1 = struct let hash_history_proof cell = let {hash; level} = Skip_list.content cell in let back_pointers_hashes = Skip_list.back_pointers cell in - Hash.to_bytes hash + Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash.to_bytes hash :: (Raw_level_repr.to_int32 level |> Int32.to_string |> Bytes.of_string) :: List.map Hash.to_bytes back_pointers_hashes |> Hash.hash_bytes @@ -167,7 +177,7 @@ module V1 = struct Format.fprintf fmt "hash: %a@,level: %a" - Hash.pp + Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash.pp hash Raw_level_repr.pp level @@ -212,7 +222,7 @@ module V1 = struct In that situation, an archival process is applied to the metadata. This process saves the [current_level_proof] in the [old_levels_messages] and empties [current_level]. It then - initialises a new level tree for the new messages---note that any + initializes a new level tree for the new messages---note that any intermediate levels are simply skipped. See {!Make_hashing_scheme.archive_if_needed} for details. @@ -221,6 +231,11 @@ module V1 = struct level : Raw_level_repr.t; nb_messages_in_commitment_period : int64; (* Lazy to avoid hashing O(n^2) time in [add_messages] *) + (* TODO: https://gitlab.com/tezos/tezos/-/issues/4242 + + Because there is a current level proof at all level with `sol/eol` we no + longer need to delay the computation. The computation can be done only + once with `eol`. *) current_level_proof : unit -> level_proof; old_levels_messages : history_proof; } @@ -331,11 +346,602 @@ let of_versioned = function V1 inbox -> inbox [@@inline] let to_versioned inbox = V1 inbox [@@inline] -let key_of_message ix = - ["message"; Data_encoding.Binary.to_string_exn Data_encoding.n ix] - type serialized_proof = string let serialized_proof_encoding = Data_encoding.(string' Hex) +type level_tree_proof = { + proof : Sc_rollup_inbox_merkelized_payload_hashes_repr.proof; + payload : Sc_rollup_inbox_message_repr.serialized option; +} + +let level_tree_proof_encoding = + let open Data_encoding in + conv + (fun {proof; payload} -> (proof, (payload :> string option))) + (fun (proof, payload) -> + { + proof; + payload = + Option.map Sc_rollup_inbox_message_repr.unsafe_of_string payload; + }) + (obj2 + (req + "proof" + Sc_rollup_inbox_merkelized_payload_hashes_repr.proof_encoding) + (opt "payload" string)) + +let add_message inbox payload level_tree_history level_tree = + let open Result_syntax in + let* level_tree_history, level_tree = + Sc_rollup_inbox_merkelized_payload_hashes_repr.add_payload + level_tree_history + level_tree + payload + in + let nb_messages_in_commitment_period = + Int64.succ inbox.nb_messages_in_commitment_period + in + let inbox = {inbox with nb_messages_in_commitment_period} in + return (level_tree_history, level_tree, inbox) + +(** [initialize_level_tree_when_needed level_tree_history inbox level_tree + payloads] creates a new [level_tree] with the first element of [payloads] if + [level_tree] is None. *) +let initialize_level_tree_when_needed level_tree_history inbox level_tree + payloads = + (* TODO: https://gitlab.com/tezos/tezos/-/issues/4242 + + This function is needed because a skip list can't be empty. A level + tree is never empty because of `sol` so this corner case can be + removed. *) + let open Result_syntax in + match level_tree with + | Some level_tree -> return (inbox, level_tree_history, level_tree, payloads) + | None -> + let* first_payload, payloads = + match payloads with + | hd :: tl -> return (hd, tl) + | [] -> error Tried_to_add_zero_messages + in + let* level_tree_history, level_tree = + Sc_rollup_inbox_merkelized_payload_hashes_repr.genesis + level_tree_history + first_payload + in + let nb_messages_in_commitment_period = + Int64.succ inbox.nb_messages_in_commitment_period + in + let inbox = {inbox with nb_messages_in_commitment_period} in + return (inbox, level_tree_history, level_tree, payloads) + +(** [no_history] creates an empty history with [capacity] set to + zero---this makes the [remember] function a no-op. We want this + behaviour in the protocol because we don't want to store + previous levels of the inbox. *) +let no_history = History.empty ~capacity:0L + +let take_snapshot inbox = inbox.old_levels_messages + +let form_history_proof history inbox = + let open Result_syntax in + let prev_cell = inbox.old_levels_messages in + let prev_cell_ptr = hash_history_proof prev_cell in + let* history = History.remember prev_cell_ptr prev_cell history in + let level_proof = current_level_proof inbox in + let cell = Skip_list.next ~prev_cell ~prev_cell_ptr level_proof in + return (history, cell) + +(** [archive_if_needed level_tree_history history inbox new_level level_tree] + is responsible for ensuring that the {!add_messages} function + below has a correctly set-up [level_tree] to which to add the + messages. If [new_level] is a higher level than the current inbox, + we create a new inbox level tree at that level in which to start + adding messages, and archive the earlier levels depending on the + [history] parameter's [capacity]. If [level_tree] is [None] (this + happens when the inbox is first created) we similarly create a new + empty level tree. + + This function is the only place we begin new level trees. *) +let archive_if_needed level_tree_history history inbox new_level level_tree + payloads = + let open Result_syntax in + if Raw_level_repr.(inbox.level = new_level) then + match level_tree with + | Some tree -> return (history, inbox, level_tree_history, tree, payloads) + | None -> + let* inbox, level_tree_history, tree, payloads = + initialize_level_tree_when_needed + level_tree_history + inbox + level_tree + payloads + in + return (history, inbox, level_tree_history, tree, payloads) + else + let* history, old_levels_messages = form_history_proof history inbox in + let* inbox, level_tree_history, tree, payloads = + initialize_level_tree_when_needed + level_tree_history + inbox + level_tree + payloads + in + let inbox = + { + current_level_proof = inbox.current_level_proof; + nb_messages_in_commitment_period = + inbox.nb_messages_in_commitment_period; + old_levels_messages; + level = new_level; + } + in + return (history, inbox, level_tree_history, tree, payloads) + +let add_messages level_tree_history history inbox level payloads level_tree = + let open Result_syntax in + let* () = + error_when + (match payloads with [] -> true | _ -> false) + Tried_to_add_zero_messages + in + let* () = + error_when + Raw_level_repr.(level < inbox.level) + (Invalid_level_add_messages level) + in + let* history, inbox, level_tree_history, level_tree, payloads = + archive_if_needed level_tree_history history inbox level level_tree payloads + in + let* level_tree_history, level_tree, inbox = + List.fold_left_e + (fun (level_tree_history, level_tree, inbox) payload -> + add_message inbox payload level_tree_history level_tree) + (level_tree_history, level_tree, inbox) + payloads + in + let current_level_proof () = + let hash = Sc_rollup_inbox_merkelized_payload_hashes_repr.hash level_tree in + {hash; level} + in + return + (level_tree_history, level_tree, history, {inbox with current_level_proof}) + +let add_messages_no_history inbox level payloads level_tree = + let open Result_syntax in + let+ _, level_tree, _, inbox = + add_messages + Sc_rollup_inbox_merkelized_payload_hashes_repr.History.no_history + no_history + inbox + level + payloads + level_tree + in + (level_tree, inbox) + +(* An [inclusion_proof] is a path in the Merkelized skip list + showing that a given inbox history is a prefix of another one. + This path has a size logarithmic in the difference between the + levels of the two inboxes. + + [Irmin.Proof.{tree_proof, stream_proof}] could not be reused here + because there is no obvious encoding of sequences in these data + structures with the same guarantee about the size of proofs. *) +type inclusion_proof = history_proof list + +let inclusion_proof_encoding = + let open Data_encoding in + list history_proof_encoding + +let pp_inclusion_proof fmt proof = + Format.pp_print_list pp_history_proof fmt proof + +let number_of_proof_steps proof = List.length proof + +let lift_ptr_path deref ptr_path = + let rec aux accu = function + | [] -> Some (List.rev accu) + | x :: xs -> Option.bind (deref x) @@ fun c -> aux (c :: accu) xs + in + aux [] ptr_path + +type proof = + (* See the main docstring for this type (in the mli file) for + definitions of the three proof parameters [starting_point], + [message] and [snapshot]. In the below we deconstruct + [starting_point] into [(l, n)] where [l] is a level and [n] is a + message index. + + In a [Single_level] proof, [history_proof] is the skip list cell for the + level [l], [inc] is an inclusion proof of [history_proof] into [snapshot] + and [message_proof] is an inclusion proof of [payload_level_tree] into + [history_proof.content]: + + [exists level_tree, payload_level_tree . + (hash_level_tree level_tree = history_proof.content.hash) + AND (get_messages_payload message_proof = (payload_level_tree, message_opt)) + AND (( + (message_opt = Some message) + AND (Inbox_message.hash_payload message = payload_level_tree.content)) + OR ( + (message_opt = None) + AND (payload_level_tree = level_tree))] + + Note: in the case that [message] is [None] this shows that there's no + value at the index [n]; in this case we also must check that + [history_proof] equals [snapshot] (otherwise, we'd need a [Next_level] + proof instead). *) + | Single_level of {inc : inclusion_proof; message_proof : level_tree_proof} + (* See the main docstring for this type (in the mli file) for + definitions of the three proof parameters [starting_point], + [message] and [snapshot]. In the below we deconstruct + [starting_point] as [(l, n)] where [l] is a level and [n] is a + message index. + + In a [Next_level] proof, [lower_history_proof] is the skip list cell for + the level [l], [inc] is an inclusion proof of [lower_history_proof] into + [snapshot] and [lower_message_proof] is a tree proof showing that there + is no message at [(l, n)] with [lower_message_proof]. + + The first message to read at the next level of [l] is the first input + [Start_of_level]. *) + | Next_level of { + lower_message_proof : level_tree_proof; + inc : inclusion_proof; + } + +let pp_proof fmt proof = + match proof with + | Single_level _ -> Format.fprintf fmt "Single_level inbox proof" + | Next_level _ -> Format.fprintf fmt "Next_level inbox proof" + +let proof_encoding = + let open Data_encoding in + union + ~tag_size:`Uint8 + [ + case + ~title:"Single_level" + (Tag 0) + (obj2 + (req "inclusion_proof" inclusion_proof_encoding) + (req "message_proof" level_tree_proof_encoding)) + (function + | Single_level {inc; message_proof} -> Some (inc, message_proof) + | _ -> None) + (fun (inc, message_proof) -> Single_level {inc; message_proof}); + case + ~title:"Next_level" + (Tag 1) + (obj2 + (req "lower_message_proof" level_tree_proof_encoding) + (req "inclusion_proof" inclusion_proof_encoding)) + (function + | Next_level {lower_message_proof; inc} -> + Some (lower_message_proof, inc) + | _ -> None) + (fun (lower_message_proof, inc) -> + Next_level {lower_message_proof; inc}); + ] + +let of_serialized_proof = Data_encoding.Binary.of_string_opt proof_encoding + +let to_serialized_proof = Data_encoding.Binary.to_string_exn proof_encoding + +(** [verify_level_tree_proof {proof; payload} head_cell_hash n label] handles + all the verification needed for a particular message proof at a particular + level. + + First it checks that [proof] is a valid inclusion of [payload_cell] in + [head_cell] and that [head_cell] hash is [head_cell_hash]. + + Then there is two cases, + + - either [n] is superior to the index of [head_cell] then the provided + [payload] must be empty (and [payload_cell = head_cell]); + + - or [0 < n < max_index head_cell] then the provided payload must exist and + the payload hash must equal the content of the [payload_cell]. +*) +let verify_level_tree_proof {proof; payload} head_cell_hash n label = + let open Result_syntax in + let* payload_cell, head_cell = + Sc_rollup_inbox_merkelized_payload_hashes_repr.verify_proof proof + in + (* Checks that [proof] is a valid inclusion of [payload_cell] in + [head_cell] and that [head_cell] hash is [head_cell_hash]. *) + let* () = + error_unless + (Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash.equal + head_cell_hash + (Sc_rollup_inbox_merkelized_payload_hashes_repr.hash head_cell)) + (Inbox_proof_error + (Format.sprintf "message_proof (%s) does not match history" label)) + in + let max_index = + Sc_rollup_inbox_merkelized_payload_hashes_repr.get_index head_cell + in + (* TODO: https://gitlab.com/tezos/tezos/-/issues/3975 + We could check that index = snapshot_max_index + 1 *) + if Compare.Int.(Z.to_int n > max_index) then + (* [n] is superior to the index of [head_cell] then the provided [payload] + must be empty (,and [payload_cell = head_cell]) *) + let* () = + error_unless + (Option.is_none payload) + (Inbox_proof_error "Payload provided but none expected") + in + let* () = + error_unless + (Sc_rollup_inbox_merkelized_payload_hashes_repr.equal + payload_cell + head_cell) + (Inbox_proof_error "Provided proof is about a unexpected payload") + in + return_none + else + (* [0 < n < max_index head_cell] then the provided [payload] must exists and + [payload_hash] must equal the content of the [payload_cell]. *) + let* payload = + match payload with + | Some payload -> return payload + | None -> + tzfail + (Inbox_proof_error + "Expected a payload but none provided in the proof") + in + let payload_hash = + Sc_rollup_inbox_message_repr.hash_serialized_message payload + in + let proven_payload_hash = + Sc_rollup_inbox_merkelized_payload_hashes_repr.get_payload_hash + payload_cell + in + let* () = + error_unless + (Sc_rollup_inbox_message_repr.Hash.equal + payload_hash + proven_payload_hash) + (Inbox_proof_error + "the payload provided does not match the payload's hash found in \ + the message proof") + in + let payload_index = + Sc_rollup_inbox_merkelized_payload_hashes_repr.get_index payload_cell + in + let* () = + (* TODO: https://gitlab.com/tezos/tezos/-/issues/4259 + + replace the message counter by an int32 so we don't need this + conversion *) + error_unless + (Compare.Int.equal (Z.to_int n) payload_index) + (Inbox_proof_error + (Format.sprintf + "found index in message_proof (%s) is incorrect" + label)) + in + return_some payload + +(** [produce_level_tree_proof get_level_tree_history head_cell_hash ~index] + + [get_level_tree_history cell_hash] is a function that returns an + {!Sc_rollup_inbox_merkelized_payload_hashes_repr.History.t}. The returned + history must contains the cell with hash [cell_hash], all its ancestor cell + and their associated payload. + + [head_cell] the latest cell of the [level_tree] we want to produce a proof on + with hash [head_cell_hash]. + + This function produce either: + + - if [index <= head_cell_max_index], a proof that [payload_cell] with + [index] is an ancestor to [head_cell] where [head_cell] is the cell with + hash [head_cell_hash]. It returns the proof and the payload associated to + [payload_cell]; + + - else a proof that [index] is out of bound for [head_cell]. It returns the + proof and no payload. +*) +let produce_level_tree_proof get_level_tree_history head_cell_hash ~index = + let open Lwt_result_syntax in + (* We first retrieve the history of cells for this level. *) + let*! level_tree_history = get_level_tree_history head_cell_hash in + (* We then fetch the actual head cell in the history. *) + let*? head_cell = + match + Sc_rollup_inbox_merkelized_payload_hashes_repr.History.find + head_cell_hash + level_tree_history + with + | Some {merkelized = head_cell; payload = _} -> ok head_cell + | None -> + error + (Inbox_proof_error + "could not find head_cell in the level_tree_history") + in + let head_cell_max_index = + Sc_rollup_inbox_merkelized_payload_hashes_repr.get_index head_cell + in + (* if [index <= level_tree_max_index] then the index belongs to this level, we + prove its existence. Else the index is out of bounds, we prove its + non-existence. *) + let target_index = Compare.Int.(min index head_cell_max_index) in + (* We look for the cell at `target_index` starting from `head_cell`. If it + exists, we return the payload held in this cell. Otherwise, we prove that + [index] does not exist in this level. *) + let proof = + Sc_rollup_inbox_merkelized_payload_hashes_repr.produce_proof + level_tree_history + head_cell + ~index:target_index + in + match proof with + | Some ({payload; merkelized = _}, proof) -> + if Compare.Int.(target_index = index) then + return {proof; payload = Some payload} + else return {proof; payload = None} + | None -> tzfail (Inbox_proof_error "could not produce a valid proof.") + +let verify_inclusion_proof inclusion_proof snapshot_history_proof = + let open Result_syntax in + let rec aux (hash_map, ptr_list) = function + | [] -> error (Inbox_proof_error "inclusion proof is empty") + | [target] -> + let target_ptr = hash_history_proof target in + let hash_map = Hash.Map.add target_ptr target hash_map in + let ptr_list = target_ptr :: ptr_list in + ok (hash_map, List.rev ptr_list, target, target_ptr) + | history_proof :: tail -> + let ptr = hash_history_proof history_proof in + aux (Hash.Map.add ptr history_proof hash_map, ptr :: ptr_list) tail + in + let* hash_map, ptr_list, target, target_ptr = + aux (Hash.Map.empty, []) inclusion_proof + in + let deref ptr = Hash.Map.find ptr hash_map in + let cell_ptr = hash_history_proof snapshot_history_proof in + let* () = + error_unless + (Skip_list.valid_back_path + ~equal_ptr:Hash.equal + ~deref + ~cell_ptr + ~target_ptr + ptr_list) + (Inbox_proof_error "invalid inclusion proof") + in + return target + +let verify_proof (l, n) inbox_snapshot proof = + assert (Z.(geq n zero)) ; + let open Result_syntax in + match proof with + | Single_level {inc; message_proof} -> ( + let* history_proof = verify_inclusion_proof inc inbox_snapshot in + let level_proof = Skip_list.content history_proof in + let* payload_opt = + verify_level_tree_proof message_proof level_proof.hash n "single level" + in + match payload_opt with + | None -> + if equal_history_proof inbox_snapshot history_proof then return_none + else + tzfail + @@ Inbox_proof_error "payload is None but proof.level not top level" + | Some payload -> + return_some + Sc_rollup_PVM_sig.{inbox_level = l; message_counter = n; payload}) + | Next_level {inc; lower_message_proof} -> ( + let* lower_history_proof = verify_inclusion_proof inc inbox_snapshot in + (* TODO: https://gitlab.com/tezos/tezos/-/issues/3975 + We could prove that the last message to read is SOL, and is + before [n]. *) + let lower_level_proof = Skip_list.content lower_history_proof in + let* should_be_none = + verify_level_tree_proof + lower_message_proof + lower_level_proof.hash + n + "lower" + in + match should_be_none with + | None -> + let* payload = + Sc_rollup_inbox_message_repr.(serialize (Internal Start_of_level)) + in + let inbox_level = Raw_level_repr.succ l in + let message_counter = Z.zero in + return_some Sc_rollup_PVM_sig.{inbox_level; message_counter; payload} + | Some _ -> + tzfail (Inbox_proof_error "more messages to read in current level")) + +let produce_proof ~get_level_tree_history history inbox (l, n) = + let open Lwt_result_syntax in + let deref ptr = History.find ptr history in + let compare {hash = _; level} = Raw_level_repr.compare level l in + let result = Skip_list.search ~deref ~compare ~cell:inbox in + let* inc, history_proof = + match result with + | Skip_list.{rev_path; last_cell = Found history_proof} -> + return (List.rev rev_path, history_proof) + | {last_cell = Nearest _; _} + | {last_cell = No_exact_or_lower_ptr; _} + | {last_cell = Deref_returned_none; _} -> + (* We are only interested to the result where [search] than a + path to the cell we were looking for. All the other cases + should be considered as an error. *) + tzfail + @@ Inbox_proof_error + (Format.asprintf + "Skip_list.search failed to find a valid path: %a" + (Skip_list.pp_search_result ~pp_cell:pp_history_proof) + result) + in + let level_proof = Skip_list.content history_proof in + let* ({payload; proof = _} as message_proof) = + (* TODO: https://gitlab.com/tezos/tezos/-/issues/4259 + + replace the message counter by an int32 so we don't need this + conversion *) + produce_level_tree_proof + get_level_tree_history + level_proof.hash + ~index:(Z.to_int n) + in + match payload with + | Some payload -> + return + ( Single_level {inc; message_proof}, + Some Sc_rollup_PVM_sig.{inbox_level = l; message_counter = n; payload} + ) + | None -> + if equal_history_proof inbox history_proof then + return (Single_level {inc; message_proof}, None) + else + let lower_message_proof = message_proof in + let* input_given = + let inbox_level = Raw_level_repr.succ l in + let message_counter = Z.zero in + let*? payload = + Sc_rollup_inbox_message_repr.(serialize (Internal Start_of_level)) + in + return_some Sc_rollup_PVM_sig.{inbox_level; message_counter; payload} + in + return (Next_level {inc; lower_message_proof}, input_given) + +let empty level = + let pre_genesis_level = Raw_level_repr.root in + let initial_level_proof = + (* TODO: https://gitlab.com/tezos/tezos/-/issues/4242 + + Because there is no empty level with `sol/eol` we don't need the zero + hash but instead we could use the real value. *) + let hash = Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash.zero in + {hash; level = pre_genesis_level} + in + { + level; + nb_messages_in_commitment_period = 0L; + current_level_proof = (fun () -> initial_level_proof); + old_levels_messages = Skip_list.genesis initial_level_proof; + } + +module Internal_for_tests = struct + let eq_tree = Sc_rollup_inbox_merkelized_payload_hashes_repr.equal + + let produce_inclusion_proof history a b = + let open Result_syntax in + let cell_ptr = hash_history_proof b in + let target_index = Skip_list.index a in + let* history = History.remember cell_ptr b history in + let deref ptr = History.find ptr history in + Skip_list.back_path ~deref ~cell_ptr ~target_index + |> Option.map (lift_ptr_path deref) + |> Option.join |> return + + let serialized_proof_of_string x = x +end + type inbox = t diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli index 4255d07f7ce5..375aa11428bb 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli @@ -98,7 +98,7 @@ On the one hand, to reduce the space consumption of rollups on the chain storage, the protocol only stores metadata about the - inbox. The messages of the current level are kept in memory during + inbox. The messages' hash of the current level are kept in memory during block validation only (See {!Raw_context.Sc_rollup_in_memory_inbox}). By contrast, the messages of the previous levels are not kept in the context at all. They can be retrieved from the chain @@ -112,8 +112,8 @@ To cope with the discrepancy of requirements in terms of inbox storage while preserving a consistent Merkelization between the protocol and the rollup node, this module exposes the - hashing schemes used to merkelize the inbox as a functor parameterized - by the exact context where Merkle trees are stored. + functions used to merkelize the inbox with an history (See + {!History_bounded_repr.t}) as parameters to remember. *) @@ -128,10 +128,7 @@ end module V1 : sig (** The type of the inbox for a smart-contract rollup as stored by the protocol in the context. Values that inhabit this type - only act as fingerprint for inboxes. - - Inbox contents is represented using {!Raw_context.TREE.tree}s. - (See below.) *) + only act as fingerprint for inboxes. *) type t val pp : Format.formatter -> t -> unit @@ -150,7 +147,7 @@ module V1 : sig (** A [history_proof] is a [Skip_list.cell] that stores multiple hashes. [Skip_list.content history_proof] gives the hash of the - level tree for this cell, while [Skip_list.back_pointers + [level_proof] for this cell, while [Skip_list.back_pointers history_proof] is an array of hashes of earlier [history_proof]s in the inbox. @@ -198,10 +195,8 @@ module V1 : sig val equal_history_proof : history_proof -> history_proof -> bool - (** [old_levels_messages inbox] returns the skip list of the inbox - history. How much data there actually is depends on the context---in - the L1 most of the history is forgotten and just a root hash of the - skip list is kept. *) + (** [old_levels_messages inbox] returns the latest skip list cell of the inbox + history that is not up to change (i.e. not the current level tree). *) val old_levels_messages : t -> history_proof (** [number_of_messages_during_commitment_period inbox] returns the @@ -225,4 +220,162 @@ type serialized_proof val serialized_proof_encoding : serialized_proof Data_encoding.t +(** [add_messages level_tree_history history inbox level payloads level_tree] + inserts a list of [payloads] as new messages in the [level_tree] and + remember them in [level_tree_history] of the current [level] of the + [inbox]. This function returns the new level tree as well as updated + [inbox], [history] and [level_tree_history]. + + If the [inbox]'s level is older than [level], the [inbox] is + updated so that the level trees of the levels older than [level] + are archived. To archive a [level_tree] for a given [level], we + push it at the end of the [history] and update the witness of this + history in the [inbox]. The [inbox]'s level tree for the current + level is emptied to insert the [payloads] in a fresh [level_tree] + for [level]. + + *) +val add_messages : + Sc_rollup_inbox_merkelized_payload_hashes_repr.History.t -> + History.t -> + t -> + Raw_level_repr.t -> + Sc_rollup_inbox_message_repr.serialized list -> + Sc_rollup_inbox_merkelized_payload_hashes_repr.t option -> + (Sc_rollup_inbox_merkelized_payload_hashes_repr.History.t + * Sc_rollup_inbox_merkelized_payload_hashes_repr.t + * History.t + * t) + tzresult + +(** [add_messages_no_history inbox level payloads level_tree] behaves as + {!add_external_messages} except that it does not remember the inbox and + payload history. *) +val add_messages_no_history : + t -> + Raw_level_repr.t -> + Sc_rollup_inbox_message_repr.serialized list -> + Sc_rollup_inbox_merkelized_payload_hashes_repr.t option -> + (Sc_rollup_inbox_merkelized_payload_hashes_repr.t * t) tzresult + +(** [form_history_proof history inbox] creates the skip list structure that + includes the current inbox level, while also updating the [history]. + + This is used in [archive_if_needed] to produce the [old_levels_messages] + value for the next level of the inbox. It is also needed if you want to + produce a fully-up-to-date skip list for proof production. Just taking the + skip list stored in the inbox at [old_levels_messages] will not include the + current level (and that current level could be quite far back in terms of + blocks if the inbox hasn't been added to for a while). *) +val form_history_proof : History.t -> t -> (History.t * history_proof) tzresult + +(** This is similar to {!form_history_proof} except that it is just to be used + on the protocol side because it doesn't ensure the history is + remembered. Used at the beginning of a refutation game to create the + snapshot against which proofs in that game must be valid. + + One important note: + It takes the snapshot of the inbox for the current level. The snapshot + points to the inbox at the *beginning* of the current block level. This + prevents to create a mid-level snapshot for a refutation game if new + messages are added before and/or after in the same block. *) +val take_snapshot : t -> history_proof + +(** Given a inbox [A] at some level [L] and another inbox [B] at some level [L' + >= L], an [inclusion_proof] guarantees that [A] is an older version of [B]. + + To be more precise, an [inclusion_proof] guarantees that the previous levels + [level_tree]s of [A] are included in the previous levels [level_tree]s of + [B]. The current [level_tree] of [A] and [B] are not considered. + + The size of this proof is O(log_basis (L' - L)). *) +type inclusion_proof + +val inclusion_proof_encoding : inclusion_proof Data_encoding.t + +val pp_inclusion_proof : Format.formatter -> inclusion_proof -> unit + +(** [number_of_proof_steps proof] returns the length of [proof]. *) +val number_of_proof_steps : inclusion_proof -> int + +(** [verify_inclusion_proof proof snapshot] returns [A] iff [proof] is a minimal + and valid proof that [A] is included in [snapshot], fails otherwise. [A] is + part of the proof. *) +val verify_inclusion_proof : + inclusion_proof -> history_proof -> history_proof tzresult + +(** An inbox proof has three parameters: + + - the [starting_point], of type [Raw_level_repr.t * Z.t], specifying + a location in the inbox ; + + - the [message], of type [Sc_rollup_PVM_sig.input option] ; + + - and a reference [snapshot] inbox. + + A valid inbox proof implies the following semantics: beginning at + [starting_point] and reading forward through [snapshot], the first + message you reach will be [message]. + + Usually this is fairly simple because there will actually be a + message at the location specified by [starting_point]. But in some + cases [starting_point] is past the last message within a level, + and then the inbox proof must prove that and also provide another + proof about the message at the beginning of the next non-empty + level. *) +type proof + +val pp_proof : Format.formatter -> proof -> unit + +val to_serialized_proof : proof -> serialized_proof + +val of_serialized_proof : serialized_proof -> proof option + +(** See the docstring for the [proof] type for details of proof semantics. + + [verify_proof starting_point inbox_snapshot proof] will return the third + parameter of the proof, [message], iff the proof is valid. *) +val verify_proof : + Raw_level_repr.t * Z.t -> + history_proof -> + proof -> + Sc_rollup_PVM_sig.inbox_message option tzresult + +(** [produce_proof get_level_tree_history history inbox (level, counter)] + creates an inbox proof proving the first message after the index [counter] + at location [level]. This will fail if the [get_level_tree_history] given + doesn't have sufficient data (it needs to be run on an with a full + history). *) +val produce_proof : + get_level_tree_history: + (Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash.t -> + Sc_rollup_inbox_merkelized_payload_hashes_repr.History.t Lwt.t) -> + History.t -> + history_proof -> + Raw_level_repr.t * Z.t -> + (proof * Sc_rollup_PVM_sig.inbox_message option) tzresult Lwt.t + +(** [empty level] is an inbox started at some given [level] with no message at + all. *) +val empty : Raw_level_repr.t -> t + +module Internal_for_tests : sig + val eq_tree : + Sc_rollup_inbox_merkelized_payload_hashes_repr.t -> + Sc_rollup_inbox_merkelized_payload_hashes_repr.t -> + bool + + (** [produce_inclusion_proof history a b] exploits [history] to produce + a self-contained proof that [a] is an older version of [b]. *) + val produce_inclusion_proof : + History.t -> + history_proof -> + history_proof -> + inclusion_proof option tzresult + + (** Allows to create a dumb {!serialized_proof} from a string, instead of + serializing a proof with {!to_serialized_proof}. *) + val serialized_proof_of_string : string -> serialized_proof +end + type inbox = t diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_storage.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_storage.ml index d96f053ba78d..7b84c14893de 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_storage.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_storage.ml @@ -101,9 +101,8 @@ let add_messages ctxt messages = history. On the contrary, the history is stored by the rollup node to produce inclusion proofs when needed. *) - let* current_messages, inbox = + let*? current_messages, inbox = Sc_rollup_inbox_repr.add_messages_no_history - (Raw_context.recover ctxt) inbox level messages @@ -181,7 +180,7 @@ let add_info_per_level ctxt timestamp predecessor = let init ~timestamp ~predecessor ctxt = let open Lwt_result_syntax in let ({level; _} : Level_repr.t) = Raw_context.current_level ctxt in - let*! inbox = Sc_rollup_inbox_repr.empty (Raw_context.recover ctxt) level in + let inbox = Sc_rollup_inbox_repr.empty level in let* ctxt = Store.Inbox.init ctxt inbox in let* _inbox, _diff, ctxt = add_start_of_level ctxt in let* _inbox, _diff, ctxt = add_info_per_level ctxt timestamp predecessor in diff --git a/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.ml index 2dfe7e8c3cb6..4dd15a754a49 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.ml @@ -193,7 +193,7 @@ let check p reason = let check_inbox_proof snapshot serialized_inbox_proof (level, counter) = match Sc_rollup_inbox_repr.of_serialized_proof serialized_inbox_proof with - | None -> tzfail Sc_rollup_invalid_serialized_inbox_proof + | None -> error Sc_rollup_invalid_serialized_inbox_proof | Some inbox_proof -> Sc_rollup_inbox_repr.verify_proof (level, counter) snapshot inbox_proof @@ -280,10 +280,11 @@ let valid ~metadata snapshot commit_level dal_snapshot dal_parameters match proof.input_proof with | None -> return_none | Some (Inbox_proof {level; message_counter; proof}) -> - let+ inbox_message = + let*? inbox_message = check_inbox_proof snapshot proof (level, Z.succ message_counter) in - Option.map (fun i -> Sc_rollup_PVM_sig.Inbox_message i) inbox_message + return + @@ Option.map (fun i -> Sc_rollup_PVM_sig.Inbox_message i) inbox_message | Some First_inbox_message -> let*? payload = Sc_rollup_inbox_message_repr.(serialize (Internal Start_of_level)) @@ -358,13 +359,13 @@ module type PVM_with_context_and_state = sig val reveal : Sc_rollup_PVM_sig.Reveal_hash.t -> string option Lwt.t module Inbox_with_history : sig - include - Sc_rollup_inbox_repr.Merkelized_operations - with type inbox_context = context - val inbox : Sc_rollup_inbox_repr.history_proof val history : Sc_rollup_inbox_repr.History.t + + val get_level_tree_history : + Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash.t -> + Sc_rollup_inbox_merkelized_payload_hashes_repr.History.t Lwt.t end module Dal_with_history : sig @@ -410,7 +411,11 @@ let produce ~metadata pvm_and_state commit_level = | First_after (level, message_counter) -> let* inbox_proof, input = Inbox_with_history.( - produce_proof context history inbox (level, Z.succ message_counter)) + Sc_rollup_inbox_repr.produce_proof + ~get_level_tree_history + history + inbox + (level, Z.succ message_counter)) in let input = Option.map (fun msg -> Sc_rollup_PVM_sig.Inbox_message msg) input @@ -420,7 +425,7 @@ let produce ~metadata pvm_and_state commit_level = { level; message_counter; - proof = Inbox_with_history.to_serialized_proof inbox_proof; + proof = Sc_rollup_inbox_repr.to_serialized_proof inbox_proof; } in return (Some inbox_proof, input) diff --git a/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.mli index db3b111d423a..652b28109f4e 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_proof_repr.mli @@ -158,13 +158,13 @@ module type PVM_with_context_and_state = sig val reveal : Sc_rollup_PVM_sig.Reveal_hash.t -> string option Lwt.t module Inbox_with_history : sig - include - Sc_rollup_inbox_repr.Merkelized_operations - with type inbox_context = context - val inbox : Sc_rollup_inbox_repr.history_proof val history : Sc_rollup_inbox_repr.History.t + + val get_level_tree_history : + Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash.t -> + Sc_rollup_inbox_merkelized_payload_hashes_repr.History.t Lwt.t end (* FIXME/DAL: https://gitlab.com/tezos/tezos/-/issues/3997 diff --git a/src/proto_alpha/lib_protocol/test/helpers/sc_rollup_helpers.ml b/src/proto_alpha/lib_protocol/test/helpers/sc_rollup_helpers.ml index aadadc9c089b..d562124bb1cc 100644 --- a/src/proto_alpha/lib_protocol/test/helpers/sc_rollup_helpers.ml +++ b/src/proto_alpha/lib_protocol/test/helpers/sc_rollup_helpers.ml @@ -460,69 +460,13 @@ let gen_message_reprs_for_levels_repr ~start_level ~max_level gen_message_repr = in aux [] (max_level - start_level) -module Tree_inbox = struct - open Sc_rollup.Inbox - module Store = Tezos_context_memory.Context +module Level_tree_histories = + Map.Make (Sc_rollup.Inbox_merkelized_payload_hashes.Hash) - module Tree = struct - include Store.Tree - - type tree = Store.tree - - type t = Store.t - - type key = string list - - type value = bytes - end - - type t = Store.t - - type tree = Tree.tree - - let commit_tree store key tree = - let open Lwt_syntax in - let* store = Store.add_tree store key tree in - let* (_ : Tezos_crypto.Context_hash.t) = - Store.commit ~time:Time.Protocol.epoch store - in - return () - - let lookup_tree store hash = - let open Lwt_syntax in - let index = Store.index store in - let* _, tree = - Store.produce_tree_proof - index - (`Node (Hash.to_context_hash hash)) - (fun x -> Lwt.return (x, x)) - in - return (Some tree) - - type proof = Store.Proof.tree Store.Proof.t - - let verify_proof proof f = - Lwt.map Result.to_option (Store.verify_tree_proof proof f) - - let produce_proof store tree f = - let open Lwt_syntax in - let index = Store.index store in - let* proof = Store.produce_tree_proof index (`Node (Tree.hash tree)) f in - return (Some proof) - - let kinded_hash_to_inbox_hash = function - | `Value hash | `Node hash -> Hash.of_context_hash hash - - let proof_before proof = kinded_hash_to_inbox_hash proof.Store.Proof.before - - let proof_encoding = - Tezos_context_merkle_proof_encoding.Merkle_proof_encoding.V1.Tree32 - .tree_proof_encoding -end - -module Store_inbox = struct - include Sc_rollup.Inbox.Make_hashing_scheme (Tree_inbox) -end +let get_level_tree_history level_tree_histories level_tree_hash = + Level_tree_histories.find level_tree_hash level_tree_histories + |> WithExceptions.Option.get ~loc:__LOC__ + |> Lwt.return (* TODO: https://gitlab.com/tezos/tezos/-/issues/3529 @@ -531,12 +475,12 @@ end test/unit/test_sc_rollup_inbox. The main difference is: we use [Alpha_context.Sc_rollup.Inbox] instead of [Sc_rollup_repr_inbox] in the former. *) -let construct_inbox ~inbox ?origination_level ctxt levels_and_inputs = - let open Lwt_syntax in - let open Store_inbox in +let construct_inbox ~inbox ?origination_level levels_and_inputs = + let open Result_syntax in let history = Sc_rollup.Inbox.History.empty ~capacity:10000L in - let rec aux history inbox level_tree = function - | [] -> return (ctxt, level_tree, history, inbox) + let level_tree_histories = Level_tree_histories.empty in + let rec aux level_tree_histories history inbox = function + | [] -> return (level_tree_histories, history, inbox) | ((level, inputs) : Raw_level.t * Sc_rollup.input list) :: rst -> assert ( match origination_level with @@ -549,13 +493,29 @@ let construct_inbox ~inbox ?origination_level ctxt levels_and_inputs = | Reveal _ -> (* We don't produce any reveals. *) assert false) inputs in - let* res = - add_messages ctxt history inbox level payloads level_tree - >|= Environment.wrap_tzresult + let level_tree_history = + Sc_rollup.Inbox_merkelized_payload_hashes.History.empty + ~capacity:1000L + in + let* level_tree_history, level_tree, history, inbox = + Sc_rollup.Inbox.add_messages + level_tree_history + history + inbox + level + payloads + None + |> Environment.wrap_tzresult + in + let level_tree_hash = + Sc_rollup.Inbox_merkelized_payload_hashes.hash level_tree in - let level_tree, history, inbox = - WithExceptions.Result.get_ok ~loc:__LOC__ res + let level_tree_histories = + Level_tree_histories.add + level_tree_hash + level_tree_history + level_tree_histories in - aux history inbox (Some level_tree) rst + aux level_tree_histories history inbox rst in - aux history inbox None levels_and_inputs + aux level_tree_histories history inbox levels_and_inputs diff --git a/src/proto_alpha/lib_protocol/test/integration/operations/test_sc_rollup.ml b/src/proto_alpha/lib_protocol/test/integration/operations/test_sc_rollup.ml index 830092e76688..e7b675475fad 100644 --- a/src/proto_alpha/lib_protocol/test/integration/operations/test_sc_rollup.ml +++ b/src/proto_alpha/lib_protocol/test/integration/operations/test_sc_rollup.ml @@ -2040,18 +2040,7 @@ let test_refute_invalid_metadata () = in assert_refute_result ~game_status:expected_game_status incr -let node_proof_to_protocol_proof p = - let open Data_encoding.Binary in - let open Sc_rollup.Inbox in - let enc = serialized_proof_encoding in - let bytes = - Sc_rollup_helpers.Store_inbox.to_serialized_proof p |> to_bytes_exn enc - in - of_bytes_exn enc bytes |> of_serialized_proof - |> WithExceptions.Option.get ~loc:__LOC__ - let full_history_inbox all_inbox_messages = - let open Lwt_syntax in let open Sc_rollup_helpers in (* Add the SOL/Info_per_level/EOL to the list of inbox messages. *) let all_inbox_messages = @@ -2061,9 +2050,6 @@ let full_history_inbox all_inbox_messages = all_inbox_messages in (* Create a inbox adding the messages from [all_inbox_messages]. *) - let* index = Tezos_context_memory.Context.init "inbox" in - let ctxt = Tezos_context_memory.Context.empty index in - let* inbox = Store_inbox.empty ctxt Raw_level.root in let all_inbox_inputs = List.map (fun (level, messages) -> @@ -2073,28 +2059,33 @@ let full_history_inbox all_inbox_messages = messages )) all_inbox_messages in - Sc_rollup_helpers.construct_inbox ~inbox ctxt all_inbox_inputs + let inbox = Sc_rollup.Inbox.empty Raw_level.root in + Sc_rollup_helpers.construct_inbox ~inbox all_inbox_inputs let input_included ~snapshot ~full_history_inbox (l, n) = let open Sc_rollup_helpers in - let ctxt, level_tree, history, inbox = full_history_inbox in - let* history, history_proof = - Store_inbox.form_history_proof ctxt history inbox level_tree - >|= Environment.wrap_tzresult + let level_tree_histories, history, inbox = full_history_inbox in + let*? history, history_proof = + Sc_rollup.Inbox.form_history_proof history inbox + |> Environment.wrap_tzresult in (* Create an inclusion proof of the inbox message at [(l, n)]. *) let* proof, _ = - Store_inbox.produce_proof ctxt history history_proof (l, n) + Sc_rollup.Inbox.produce_proof + ~get_level_tree_history:(get_level_tree_history level_tree_histories) + history + history_proof + (l, n) >|= Environment.wrap_tzresult in - let proof = node_proof_to_protocol_proof proof in - let+ inbox_message_verified = + let*? inbox_message_verified = Sc_rollup.Inbox.verify_proof (l, n) snapshot proof - >|= Environment.wrap_tzresult + |> Environment.wrap_tzresult in - Option.map - (fun inbox_message -> Sc_rollup.Inbox_message inbox_message) - inbox_message_verified + return + @@ Option.map + (fun inbox_message -> Sc_rollup.Inbox_message inbox_message) + inbox_message_verified (** Test that the protocol adds a [SOL], [Info_per_level] and [EOL] for each Tezos level, even if no messages are added to the inbox. *) @@ -2139,7 +2130,7 @@ let test_automatically_added_internal_messages () = let level_zero = Raw_level.of_int32_exn 0l in let level_one = Raw_level.of_int32_exn 1l in let level_two = Raw_level.of_int32_exn 2l in - let*! ((ctxt, level_tree, history, inbox) as full_history_inbox) = + let*? ((_level_tree_histories, history, inbox) as full_history_inbox) = full_history_inbox [ (level_zero, level_zero_info, []); @@ -2197,13 +2188,9 @@ let test_automatically_added_internal_messages () = in (* Assert the computed inbox and protocol's inbox are equal. *) - let* _history, history_proof = - Sc_rollup_helpers.Store_inbox.form_history_proof - ctxt - history - inbox - level_tree - >|= Environment.wrap_tzresult + let*? _history, history_proof = + Sc_rollup.Inbox.form_history_proof history inbox + |> Environment.wrap_tzresult in Assert.equal ~loc:__LOC__ diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml b/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml index 2c150baead27..cd6d28934185 100644 --- a/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml +++ b/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml @@ -51,6 +51,8 @@ let qcheck_make_lwt_res ?print ?count ~name ~gen f = ~gen (fun a -> Lwt_main.run (f a)) +let lift k = Environment.wrap_tzresult k + let tick_to_int_exn ?(__LOC__ = __LOC__) t = WithExceptions.Option.get ~loc:__LOC__ (Tick.to_int t) @@ -797,7 +799,6 @@ end (** {2. ArithPVM utils} *) module ArithPVM = Arith_pvm -module Store_inbox = Sc_rollup_helpers.Store_inbox module Arith_test_pvm = struct include ArithPVM @@ -1015,12 +1016,13 @@ type player_client = { states : (Tick.t * State_hash.t) list; final_tick : Tick.t; inbox : - Store_inbox.inbox_context - * Store_inbox.tree option + Sc_rollup.Inbox_merkelized_payload_hashes.History.t + Sc_rollup_helpers.Level_tree_histories.t * Inbox.History.t * Inbox.t; levels_and_inputs : (Raw_level.t * input list) list; metadata : Metadata.t; + context : Tezos_context_memory.Context.t; } let pp_levels_and_inputs ~verbose ppf levels_and_inputs = @@ -1047,8 +1049,15 @@ let pp_levels_and_inputs ~verbose ppf levels_and_inputs = levels_and_inputs) let pp_player_client ~verbose ppf - {player; states = _; final_tick; inbox = _; levels_and_inputs; metadata = _} - = + { + player; + states = _; + final_tick; + inbox = _; + levels_and_inputs; + metadata = _; + context = _; + } = Format.fprintf ppf "@[player:@,%a@]@,final tick: %a@,@[levels and inputs:@,%a@]" @@ -1067,12 +1076,11 @@ module Player_client = struct Tezos_context_memory.Context.empty index (** Construct an inbox based on [levels_and_messages] in the player context. *) - let construct_inbox ~inbox ~origination_level ctxt levels_and_messages = - Lwt_main.run + let construct_inbox ~inbox ~origination_level levels_and_messages = + WithExceptions.Result.get_ok ~loc:__LOC__ @@ Sc_rollup_helpers.construct_inbox ~inbox ~origination_level - ctxt levels_and_messages (** Generate [our_states] for [levels_and_inputs] based on the strategy. @@ -1222,9 +1230,7 @@ module Player_client = struct ~max_level levels_and_inputs in - let inbox = - construct_inbox ~inbox ~origination_level ctxt levels_and_inputs - in + let inbox = construct_inbox ~inbox ~origination_level levels_and_inputs in return { player; @@ -1233,6 +1239,7 @@ module Player_client = struct inbox; levels_and_inputs; metadata; + context = ctxt; } end @@ -1276,10 +1283,14 @@ let build_proof ~player_client start_tick (game : Game.t) = (* No messages are added between [game.start_level] and the current level so we can take the existing inbox of players. Otherwise, we should find the inbox of [start_level]. *) - let inbox_context, messages_tree, history, inbox = player_client.inbox in - let* history, history_proof = - Lwt.map Environment.wrap_tzresult - @@ Store_inbox.form_history_proof inbox_context history inbox messages_tree + let level_tree_histories, history, inbox = player_client.inbox in + let get_level_tree_history level_messages_hash = + Level_tree_histories.find level_messages_hash level_tree_histories + |> WithExceptions.Option.get ~loc:__LOC__ + |> Lwt.return + in + let*? history, history_proof = + lift @@ Inbox.form_history_proof history inbox in (* We start a game on a commitment that starts at [Tick.initial], the fuel is necessarily [start_tick]. *) @@ -1297,18 +1308,18 @@ let build_proof ~player_client start_tick (game : Game.t) = let initial_state ~empty:_ = initial_state () - let context = inbox_context + let context = player_client.context let state = state let reveal _ = assert false module Inbox_with_history = struct - include Store_inbox - let history = history let inbox = history_proof + + let get_level_tree_history = get_level_tree_history end (* FIXME/DAL-REFUTATION: https://gitlab.com/tezos/tezos/-/issues/3992 diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml b/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml index 5100b83a4962..6218e001eda9 100644 --- a/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml +++ b/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml @@ -35,7 +35,7 @@ open Protocol open QCheck2 open Lib_test.Qcheck2_helpers -let lift k = Lwt.map Environment.wrap_tzresult k +let lift k = Environment.wrap_tzresult k (** {2 Generators} *) @@ -92,25 +92,22 @@ let gen_inbox level = let* tail = small_list gen_msg in let payloads = hd :: tail in let level_tree_and_inbox = - let open Lwt_result_syntax in - let* ctxt = Context.default_raw_context () in - let inbox_ctxt = Raw_context.recover ctxt in - let*! empty_inbox = Sc_rollup_inbox_repr.empty inbox_ctxt level in + let open Result_syntax in + let empty_inbox = Sc_rollup_inbox_repr.empty level in lift - @@ let*? input_messages = + @@ let* input_messages = List.map_e (fun msg -> Sc_rollup_inbox_message_repr.(serialize (External msg))) payloads in Sc_rollup_inbox_repr.add_messages_no_history - inbox_ctxt empty_inbox level input_messages None in return - @@ (Lwt_main.run level_tree_and_inbox |> function + @@ (level_tree_and_inbox |> function | Ok v -> snd v | Error e -> Stdlib.failwith (Format.asprintf "%a" Error_monad.pp_print_trace e)) diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml index 1cfb6041d6e7..82b77426f8f9 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml @@ -270,10 +270,9 @@ module Arith_pvm = Sc_rollup_helpers.Arith_pvm let test_invalid_serialized_inbox_proof () = let open Lwt_result_syntax in let open Alpha_context in - let* ctxt = Test_sc_rollup_inbox_legacy.create_context () in let rollup = Sc_rollup.Address.zero in let level = Raw_level.(succ root) in - let*! inbox = Sc_rollup.Inbox.empty ctxt level in + let inbox = Sc_rollup.Inbox.empty level in let snapshot = Sc_rollup.Inbox.take_snapshot inbox in let dal_snapshot = Dal.Slots_history.genesis in let dal_parameters = Default_parameters.constants_mainnet.dal in diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml index 035c6dc3c65d..f547fd396f2b 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml @@ -39,6 +39,8 @@ open Sc_rollup_inbox_repr exception Sc_rollup_inbox_test_error of string +let lift res = Environment.wrap_tzresult res + let err x = Exn (Sc_rollup_inbox_test_error x) let rollup = Sc_rollup_repr.Address.hash_string [""] @@ -50,8 +52,37 @@ let inbox_message_testable = Sc_rollup_PVM_sig.pp_inbox_message Sc_rollup_PVM_sig.inbox_message_equal -let create_context () = - Context.init1 () >>=? fun (block, _contract) -> return block.context +module Level_tree_histories = + Map.Make (Sc_rollup_inbox_merkelized_payload_hashes_repr.Hash) + +let get_level_tree_history level_tree_histories level_tree_hash = + Level_tree_histories.find level_tree_hash level_tree_histories + |> WithExceptions.Option.get ~loc:__LOC__ + |> Lwt.return + +let get_message_payload level_tree_histories level_tree index = + let level_tree_hash = + Sc_rollup_inbox_merkelized_payload_hashes_repr.hash level_tree + in + let level_tree_history = + WithExceptions.Option.get ~loc:__LOC__ + @@ Level_tree_histories.find level_tree_hash level_tree_histories + in + let merkelized = + Sc_rollup_inbox_merkelized_payload_hashes_repr.Internal_for_tests + .find_predecessor_payload + level_tree_history + ~index + level_tree + in + let merkelized_and_payload = + Option.bind merkelized (fun m -> + Sc_rollup_inbox_merkelized_payload_hashes_repr.( + History.find (hash m) level_tree_history)) + in + Option.map + (fun m -> m.Sc_rollup_inbox_merkelized_payload_hashes_repr.payload) + merkelized_and_payload let make_payload message = WithExceptions.Result.get_ok ~loc:__LOC__ @@ -63,46 +94,65 @@ let payloads_from_messages = | Inbox_message {payload; _} -> payload | Reveal _ -> assert false) -let populate_inboxes ctxt level history inbox inboxes level_tree - list_of_payloads = - let open Lwt_syntax in - let rec aux level history inbox inboxes level_tree = function - | [] -> return (ok (level_tree, history, inbox, inboxes)) +let populate_inboxes level history inbox inboxes list_of_payloads = + let open Result_syntax in + let rec aux level history level_tree_histories inbox inboxes level_tree = + function + | [] -> return (level_tree_histories, level_tree, history, inbox, inboxes) | [] :: ps -> let level = Raw_level_repr.succ level in - aux level history inbox inboxes level_tree ps + aux level history level_tree_histories inbox inboxes None ps | payloads :: ps -> - add_messages ctxt history inbox level payloads level_tree - >|= Environment.wrap_tzresult - >>=? fun (level_tree, history, inbox') -> + let level_tree_history = + Sc_rollup_inbox_merkelized_payload_hashes_repr.History.empty + ~capacity:1000L + in + let* level_tree_history, level_tree, history, inbox' = + add_messages level_tree_history history inbox level payloads None + |> Environment.wrap_tzresult + in + let level_tree_hash = + Sc_rollup_inbox_merkelized_payload_hashes_repr.hash level_tree + in + let level_tree_histories = + Level_tree_histories.add + level_tree_hash + level_tree_history + level_tree_histories + in let level = Raw_level_repr.succ level in - aux level history inbox' (inbox :: inboxes) (Some level_tree) ps - in - aux level history inbox inboxes level_tree list_of_payloads + aux + level + history + level_tree_histories + inbox' + (inbox :: inboxes) + (Some level_tree) + ps + in + let level_tree_histories = Level_tree_histories.empty in + aux level history level_tree_histories inbox inboxes None list_of_payloads let test_empty () = - create_context () >>=? fun ctxt -> - empty ctxt (Raw_level_repr.of_int32_exn 42l) >>= fun inbox -> + let inbox = empty (Raw_level_repr.of_int32_exn 42l) in fail_unless Compare.Int64.(equal (number_of_messages_during_commitment_period inbox) 0L) (err "An empty inbox should have no available message.") let setup_inbox_with_messages list_of_payloads f = - let open Lwt_syntax in - create_context () >>=? fun ctxt -> - let* inbox = empty ctxt first_level in + let inbox = empty first_level in let history = History.empty ~capacity:10000L in - populate_inboxes ctxt first_level history inbox [] None list_of_payloads - >>=? fun (level_tree, history, inbox, inboxes) -> + populate_inboxes first_level history inbox [] list_of_payloads + >>?= fun (level_tree_histories, level_tree, history, inbox, inboxes) -> match level_tree with | None -> fail (err "setup_inbox_with_messages called with no messages") - | Some tree -> f ctxt tree history inbox inboxes + | Some tree -> f level_tree_histories tree history inbox inboxes let test_add_messages messages = let payloads = List.map make_payload messages in let nb_payloads = List.length payloads in setup_inbox_with_messages [payloads] - @@ fun _ctxt _messages _history inbox _inboxes -> + @@ fun _level_tree_histories _messages _history inbox _inboxes -> fail_unless Compare.Int64.( equal @@ -132,11 +182,11 @@ let check_payload messages external_message = let test_get_message_payload messages = let payloads = List.map make_payload messages in setup_inbox_with_messages [payloads] - @@ fun _ctxt level_tree _history _inbox _inboxes -> + @@ fun level_tree_histories level_tree _history _inbox _inboxes -> List.iteri_es (fun i message -> let expected_payload = encode_external_message message in - get_message_payload level_tree (Z.of_int i) >>= function + get_message_payload level_tree_histories level_tree i |> function | Some payload -> let payload = Sc_rollup_inbox_message_repr.unsafe_to_string payload in fail_unless @@ -151,7 +201,7 @@ let test_inclusion_proof_production (list_of_messages, n) = let open Lwt_result_syntax in let list_of_payloads = List.map (List.map make_payload) list_of_messages in setup_inbox_with_messages list_of_payloads - @@ fun _ctxt _messages history _inbox inboxes -> + @@ fun _level_tree_histories _messages history _inbox inboxes -> let inbox = Stdlib.List.hd inboxes in let old_inbox = Stdlib.List.nth inboxes n in let*? res = @@ -184,7 +234,7 @@ let test_inclusion_proof_verification (list_of_messages, n) = let open Lwt_result_syntax in let list_of_payloads = List.map (List.map make_payload) list_of_messages in setup_inbox_with_messages list_of_payloads - @@ fun _ctxt _messages history _inbox inboxes -> + @@ fun _level_tree_histories _messages history _inbox inboxes -> let inbox = Stdlib.List.hd inboxes in let old_inbox = Stdlib.List.nth inboxes n in let*? res = @@ -218,119 +268,49 @@ let test_inclusion_proof_verification (list_of_messages, n) = different inbox."; ]) -module Tree = struct - open Tezos_context_memory.Context - - type nonrec t = t - - type nonrec tree = tree - - module Tree = struct - include Tezos_context_memory.Context.Tree - - type nonrec t = t - - type nonrec tree = tree - - type key = string list - - type value = bytes - end - - let commit_tree context key tree = - let open Lwt_syntax in - let* ctxt = Tezos_context_memory.Context.add_tree context key tree in - let* (_ : value_key) = commit ~time:Time.Protocol.epoch ~message:"" ctxt in - return () - - let lookup_tree context hash = - let open Lwt_syntax in - let* _, tree = - produce_tree_proof - (index context) - (`Node (Hash.to_context_hash hash)) - (fun x -> Lwt.return (x, x)) - in - return (Some tree) - - type proof = Proof.tree Proof.t - - let verify_proof proof f = - Lwt.map Result.to_option (verify_tree_proof proof f) - - let produce_proof context tree f = - let open Lwt_syntax in - let* proof = - produce_tree_proof (index context) (`Node (Tree.hash tree)) f - in - return (Some proof) - - let kinded_hash_to_inbox_hash = function - | `Value hash | `Node hash -> Hash.of_context_hash hash - - let proof_before proof = kinded_hash_to_inbox_hash proof.Proof.before - - let proof_encoding = - Tezos_context_merkle_proof_encoding.Merkle_proof_encoding.V1.Tree32 - .tree_proof_encoding -end - -(** This is a second instance of the inbox module. It uses the {!Tree} - module above for its Irmin interface, which gives it a full context - and the ability to generate tree proofs. - - It is intended to resemble (at least well enough for these tests) - the rollup node's inbox instance. *) -module Node = Make_hashing_scheme (Tree) - -(** In the tests below we use the {!Node} inbox above to generate proofs, - but we need to test that they can be interpreted and validated by - the protocol instance of the inbox code. We rely on the two - instances having the same encoding, and use this function to - convert. *) -let node_proof_to_protocol_proof p = - let open Data_encoding.Binary in - let enc = serialized_proof_encoding in - let bytes = Node.to_serialized_proof p |> to_bytes_exn enc in - of_bytes_exn enc bytes |> of_serialized_proof - |> WithExceptions.Option.get ~loc:__LOC__ - (** This is basically identical to {!setup_inbox_with_messages}, except that it uses the {!Node} instance instead of the protocol instance. *) let setup_node_inbox_with_messages list_of_payloads f = - let open Node in let open Lwt_syntax in - let* index = Tezos_context_memory.Context.init "foo" in - let ctxt = Tezos_context_memory.Context.empty index in - let* inbox = empty ctxt first_level in + let inbox = empty first_level in let history = History.empty ~capacity:10000L in - let rec aux level history inbox inboxes level_tree = function - | [] -> return (ok (level_tree, history, inbox, inboxes)) + let level_tree_histories = Level_tree_histories.empty in + let rec aux level history level_tree_histories inbox inboxes level_tree = + function + | [] -> + return (ok (level_tree_histories, level_tree, history, inbox, inboxes)) | payloads :: ps -> - add_messages ctxt history inbox level payloads level_tree - >|= Environment.wrap_tzresult - >>=? fun (level_tree, history, inbox') -> + let level_tree_history = + Sc_rollup_inbox_merkelized_payload_hashes_repr.History.empty + ~capacity:1000L + in + add_messages level_tree_history history inbox level payloads None + |> Environment.wrap_tzresult + >>?= fun (level_tree_history, level_tree, history, inbox') -> + let level_tree_hash = + Sc_rollup_inbox_merkelized_payload_hashes_repr.hash level_tree + in + let level_tree_histories = + Level_tree_histories.add + level_tree_hash + level_tree_history + level_tree_histories + in let level = Raw_level_repr.succ level in - aux level history inbox' (inbox :: inboxes) (Some level_tree) ps - in - aux first_level history inbox [] None list_of_payloads - >>=? fun (level_tree, history, inbox, inboxes) -> + aux + level + history + level_tree_histories + inbox' + (inbox :: inboxes) + (Some level_tree) + ps + in + aux first_level history level_tree_histories inbox [] None list_of_payloads + >>=? fun (level_tree_histories, level_tree, history, inbox, inboxes) -> match level_tree with | None -> fail (err "setup_inbox_with_messages called with no messages") - | Some tree -> f ctxt tree history inbox inboxes - -let look_in_tree key tree = - let open Lwt_syntax in - let* x = Tree.Tree.find tree [key] in - match x with - | Some x -> return (tree, x) - | None -> return (tree, Bytes.of_string "nope") - -let key_of_level level = - let level_bytes = - Data_encoding.Binary.to_bytes_exn Raw_level_repr.encoding level - in - Bytes.to_string level_bytes + | Some tree -> f level_tree_histories tree history inbox inboxes let level_of_int n = Raw_level_repr.of_int32_exn (Int32.of_int n) @@ -371,13 +351,19 @@ let test_inbox_proof_production (levels_and_messages, l, n) = levels_and_messages in setup_node_inbox_with_messages list_of_payloads - @@ fun ctxt current_level_tree history inbox _inboxes -> + @@ fun level_tree_histories _current_level_tree history inbox _inboxes -> let open Lwt_result_syntax in - let* history, history_proof = - Node.form_history_proof ctxt history inbox (Some current_level_tree) + let*? history, history_proof = + form_history_proof history inbox |> Environment.wrap_tzresult + in + let*! result = + produce_proof + ~get_level_tree_history:(get_level_tree_history level_tree_histories) + history + history_proof + (l, n) >|= Environment.wrap_tzresult in - let*! result = Node.produce_proof ctxt history history_proof (l, n) in match result with | Ok (proof, input) -> ( (* We now switch to a protocol inbox built from the same messages @@ -387,8 +373,7 @@ let test_inbox_proof_production (levels_and_messages, l, n) = setup_inbox_with_messages (list_of_payloads @ [[make_payload "foo"]]) @@ fun _ctxt _ _history inbox _inboxes -> let snapshot = take_snapshot inbox in - let proof = node_proof_to_protocol_proof proof in - let*! verification = verify_proof (l, n) snapshot proof in + let verification = verify_proof (l, n) snapshot proof in match verification with | Ok v_input -> Alcotest.(check (option inbox_message_testable)) @@ -411,25 +396,30 @@ let test_inbox_proof_verification (levels_and_messages, l, n) = levels_and_messages in setup_node_inbox_with_messages list_of_payloads - @@ fun ctxt current_level_tree history inbox _inboxes -> + @@ fun level_tree_histories _current_level_tree history inbox _inboxes -> let open Lwt_result_syntax in - let* history, history_proof = - Node.form_history_proof ctxt history inbox (Some current_level_tree) + let*? history, history_proof = + form_history_proof history inbox |> Environment.wrap_tzresult + in + let*! result = + produce_proof + ~get_level_tree_history:(get_level_tree_history level_tree_histories) + history + history_proof + (l, n) >|= Environment.wrap_tzresult in - let*! result = Node.produce_proof ctxt history history_proof (l, n) in match result with | Ok (proof, _input) -> ( (* We now switch to a protocol inbox built from the same messages for verification. *) setup_inbox_with_messages (list_of_payloads @ [[make_payload "foo"]]) - @@ fun _ctxt _ _history _inbox inboxes -> + @@ fun _level_tree_histories _ _history _inbox inboxes -> (* Use the incorrect inbox *) match List.hd inboxes with | Some inbox -> ( let snapshot = take_snapshot inbox in - let proof = node_proof_to_protocol_proof proof in - let*! verification = verify_proof (l, n) snapshot proof in + let verification = verify_proof (l, n) snapshot proof in match verification with | Ok _ -> fail [err "Proof should not be valid"] | Error _ -> return (ok ())) @@ -465,27 +455,25 @@ let init_inboxes_histories_with_different_capacities List.init ~when_negative_length:[] nb_levels (fun i -> [string_of_int i]) in let mk_history ?(next_index = 0L) ~capacity () = - let open Lwt_syntax in - create_context () >>=? fun ctxt -> - let* inbox = empty ctxt first_level in + let inbox = empty first_level in let history = Sc_rollup_inbox_repr.History.Internal_for_tests.empty ~capacity ~next_index in let payloads = List.map (List.map make_payload) payloads in - populate_inboxes ctxt first_level history inbox [] None payloads + populate_inboxes first_level history inbox [] payloads in (* Here, we have `~capacity:0L`. So no history is kept *) - mk_history ~capacity:0L () >>=? fun no_history -> + mk_history ~capacity:0L () >>?= fun no_history -> (* Here, we set a [default_capacity] supposed to be greater than [nb_levels], and keep the default [next_index]. This history will serve as a witeness *) - mk_history ~capacity:default_capacity () >>=? fun big_history -> + mk_history ~capacity:default_capacity () >>?= fun big_history -> (* Here, we choose a small capacity supposed to be smaller than [nb_levels] to cover cases where the history is full and older elements should be removed. We also set a non-default [next_index] value to cover cases where the incremented index may overflow or is negative. *) - mk_history ~next_index ~capacity:small_capacity () >>=? fun small_history -> + mk_history ~next_index ~capacity:small_capacity () >>?= fun small_history -> return (no_history, small_history, big_history) (** In this test, we mainly check that the number of entries in histories @@ -506,9 +494,15 @@ let test_history_length let* no_history, small_history, big_history = init_inboxes_histories_with_different_capacities params in - let _level_tree0, history0, _inbox0, _inboxes0 = no_history in - let _level_tree1, history1, _inbox1, _inboxes1 = small_history in - let _level_tree2, history2, _inbox2, _inboxes2 = big_history in + let _level_tree_histories0, _level_tree0, history0, _inbox0, _inboxes0 = + no_history + in + let _level_tree_histories1, _level_tree1, history1, _inbox1, _inboxes1 = + small_history + in + let _level_tree_histories2, _level_tree2, history2, _inbox2, _inboxes2 = + big_history + in let hh0 = I.History.Internal_for_tests.keys history0 in let hh1 = I.History.Internal_for_tests.keys history1 in let hh2 = I.History.Internal_for_tests.keys history2 in @@ -546,9 +540,15 @@ let test_history_prefix params = let* no_history, small_history, big_history = init_inboxes_histories_with_different_capacities params in - let _level_tree0, history0, _inbox0, _inboxes0 = no_history in - let _level_tree1, history1, _inbox1, _inboxes1 = small_history in - let _level_tree2, history2, _inbox2, _inboxes2 = big_history in + let _level_tree_histories0, _level_tree0, history0, _inbox0, _inboxes0 = + no_history + in + let _level_tree_histories1, _level_tree1, history1, _inbox1, _inboxes1 = + small_history + in + let _level_tree_histories2, _level_tree2, history2, _inbox2, _inboxes2 = + big_history + in let hh0 = I.History.Internal_for_tests.keys history0 in let hh1 = I.History.Internal_for_tests.keys history1 in let hh2 = I.History.Internal_for_tests.keys history2 in @@ -587,9 +587,15 @@ let test_inclusion_proofs_depending_on_history_capacity let* no_history, small_history, big_history = init_inboxes_histories_with_different_capacities params in - let _level_tree0, history0, inbox0, _inboxes0 = no_history in - let _level_tree1, history1, inbox1, _inboxes1 = small_history in - let _level_tree2, history2, inbox2, _inboxes2 = big_history in + let _level_tree_histories0, _level_tree0, history0, inbox0, _inboxes0 = + no_history + in + let _level_tree_histories1, _level_tree1, history1, inbox1, _inboxes1 = + small_history + in + let _level_tree_histories2, _level_tree2, history2, inbox2, _inboxes2 = + big_history + in let hp0 = I.old_levels_messages inbox0 in let hp1 = I.old_levels_messages inbox1 in let (hp2 as hp) = I.old_levels_messages inbox2 in @@ -636,17 +642,15 @@ let test_inclusion_proofs_depending_on_history_capacity (** In this test, we make sure that the snapshot of an inbox is taken at the beginning of a block level. *) let test_inbox_snapshot_taking payloads = - let open Lwt_result_syntax in let payloads = List.map make_payload payloads in - create_context () >>=? fun ctxt -> - let*! inbox = empty ctxt first_level in + let inbox = empty first_level in let inbox_level = inbox_level inbox in let expected_snapshot = take_snapshot inbox in (* Now, if we add messages to the inbox at [current_level], the inbox's snapshot for this level should not changed. *) - let* _ = - add_messages_no_history ctxt inbox inbox_level payloads None - >|= Environment.wrap_tzresult + let _ = + add_messages_no_history inbox inbox_level payloads None + |> Environment.wrap_tzresult in let new_snapshot = take_snapshot inbox in fail_unless @@ -666,9 +670,15 @@ let test_for_successive_add_messages_with_different_histories_capacities let* no_history, small_history, big_history = init_inboxes_histories_with_different_capacities params in - let level_tree0, _history0, _inbox0, inboxes0 = no_history in - let level_tree1, _history1, _inbox1, inboxes1 = small_history in - let level_tree2, _history2, _inbox2, inboxes2 = big_history in + let _level_tree_histories0, level_tree0, _history0, _inbox0, inboxes0 = + no_history + in + let _level_tree_histories1, level_tree1, _history1, _inbox1, inboxes1 = + small_history + in + let _level_tree_histories2, level_tree2, _history2, _inbox2, inboxes2 = + big_history + in (* The latest inbox's value shouldn't depend on the value of [bound]. *) let eq_inboxes_list = List.for_all2 ~when_different_lengths:false I.equal in let* () = -- GitLab From 3c8a97a7b0abf22e0e82dc8d291b30379885d4ca Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Thu, 17 Nov 2022 16:56:01 +0100 Subject: [PATCH 4/8] proto/scoru: remove unused function --- src/proto_alpha/lib_protocol/alpha_context.mli | 8 +------- src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml | 5 ----- src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli | 8 +------- 3 files changed, 2 insertions(+), 19 deletions(-) diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 3c35a258bcaf..17aae84fb411 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -3299,13 +3299,7 @@ module Sc_rollup : sig val pp_history_proof : Format.formatter -> history_proof -> unit - module Hash : sig - include S.HASH - - val of_context_hash : Context_hash.t -> t - - val to_context_hash : t -> Context_hash.t - end + module Hash : S.HASH module History : Bounded_history_repr.S diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml index b63beccfe5c8..98db0e5944a8 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml @@ -121,11 +121,6 @@ module Hash = struct let () = Base58.check_encoded_prefix b58check_encoding prefix encoded_size - let of_context_hash context_hash = - Context_hash.to_bytes context_hash |> of_bytes_exn - - let to_context_hash hash = to_bytes hash |> Context_hash.of_bytes_exn - include Path_encoding.Make_hex (H) end diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli index 375aa11428bb..80cc1d935cd9 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli @@ -117,13 +117,7 @@ *) -module Hash : sig - include S.HASH - - val of_context_hash : Context_hash.t -> t - - val to_context_hash : t -> Context_hash.t -end +module Hash : S.HASH module V1 : sig (** The type of the inbox for a smart-contract rollup as stored -- GitLab From fd820f317640d14833d57ab45daaffea2170a3b0 Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Tue, 8 Nov 2022 16:22:51 +0100 Subject: [PATCH 5/8] test/scoru: improve debug msg --- .../lib_protocol/sc_rollup_inbox_repr.mli | 2 ++ .../test/unit/test_sc_rollup_inbox_legacy.ml | 28 ++++++++++++++++--- 2 files changed, 26 insertions(+), 4 deletions(-) diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli index 80cc1d935cd9..38ee7e2bde23 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli @@ -23,6 +23,8 @@ (* *) (*****************************************************************************) +type error += Inbox_proof_error of string + (** Merkelizing inbox for smart-contract rollups. {1 Overview} diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml index f547fd396f2b..2bd242a90ca0 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml @@ -342,6 +342,23 @@ let next_inbox_message levels_and_messages l n = in inbox_message_of_input input) +let fail_with_proof_error_msg errors fail_msg = + let msg = + List.find_map + (function + | Environment.Ecoproto_error + (Sc_rollup_inbox_repr.Inbox_proof_error msg) -> + Some msg + | Environment.Ecoproto_error + (Sc_rollup_inbox_merkelized_payload_hashes_repr + .Merkelized_payload_hashes_proof_error msg) -> + Some msg + | _ -> None) + errors + in + let msg = Option.(msg |> map (fun s -> ": " ^ s) |> value ~default:"") in + fail (err (fail_msg ^ msg)) + let test_inbox_proof_production (levels_and_messages, l, n) = (* We begin with a Node inbox so we can produce a proof. *) let exp_input = next_inbox_message levels_and_messages l n in @@ -373,7 +390,9 @@ let test_inbox_proof_production (levels_and_messages, l, n) = setup_inbox_with_messages (list_of_payloads @ [[make_payload "foo"]]) @@ fun _ctxt _ _history inbox _inboxes -> let snapshot = take_snapshot inbox in - let verification = verify_proof (l, n) snapshot proof in + let verification = + verify_proof (l, n) snapshot proof |> Environment.wrap_tzresult + in match verification with | Ok v_input -> Alcotest.(check (option inbox_message_testable)) @@ -385,8 +404,9 @@ let test_inbox_proof_production (levels_and_messages, l, n) = exp_input v_input ; return_unit - | Error _ -> fail [err "Proof verification failed"]) - | Error _ -> fail [err "Proof production failed"] + | Error errors -> + fail_with_proof_error_msg errors "Proof verification failed") + | Error errors -> fail_with_proof_error_msg errors "Proof production failed" let test_inbox_proof_verification (levels_and_messages, l, n) = (* We begin with a Node inbox so we can produce a proof. *) @@ -424,7 +444,7 @@ let test_inbox_proof_verification (levels_and_messages, l, n) = | Ok _ -> fail [err "Proof should not be valid"] | Error _ -> return (ok ())) | None -> fail [err "inboxes was empty"]) - | Error _ -> fail [err "Proof production failed"] + | Error errors -> fail_with_proof_error_msg errors "Proof production failed" (** This helper function initializes inboxes and histories with different capacities and populates them. *) -- GitLab From 73355a46d7a19d3f34a255848bf996ca87849dfb Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Thu, 10 Nov 2022 12:47:06 +0100 Subject: [PATCH 6/8] tezt/scoru: update regression trace --- tezt/lib_tezos/tezos_regression.ml | 1 + ...y layer node (rollup_node_applies_dal_.out | 10 ++-- ...y layer node (rollup_node_downloads_sl.out | 5 +- ...ces PVM state with messages (external).out | 50 ++++++++----------- ...rypoint- -aux- earliness- 0- external).out | 5 +- ...oint- -default- earliness- 0- external.out | 5 +- ...ces PVM state with messages (external).out | 50 ++++++++----------- ...ntrypoint- -aux- earliness- 0- externa.out | 5 +- ...ntrypoint- -default- earliness- 0- ext.out | 5 +- 9 files changed, 55 insertions(+), 81 deletions(-) diff --git a/tezt/lib_tezos/tezos_regression.ml b/tezt/lib_tezos/tezos_regression.ml index 774b670a7da1..4fff2ab2a451 100644 --- a/tezt/lib_tezos/tezos_regression.ml +++ b/tezt/lib_tezos/tezos_regression.ml @@ -44,6 +44,7 @@ let replace_variables string = ("txc\\w{50}\\b", "[TX_ROLLUP_COMMITMENT_HASH]"); ("scc1\\w{50}\\b", "[SC_ROLLUP_COMMITMENT_HASH]"); ("scib1\\w{50}\\b", "[SC_ROLLUP_INBOX_HASH]"); + ("scib2\\w{50}\\b", "[SC_ROLLUP_INBOX_LEVEL_TREE_HASH]"); ("edpk\\w{50}\\b", "[PUBLIC_KEY]"); ("\\bo\\w{50}\\b", "[OPERATION_HASH]"); ("tz[123]\\w{33}\\b", "[PUBLIC_KEY_HASH]"); diff --git a/tezt/tests/expected/dal.ml/Alpha- Testing rollup and Data availability layer node (rollup_node_applies_dal_.out b/tezt/tests/expected/dal.ml/Alpha- Testing rollup and Data availability layer node (rollup_node_applies_dal_.out index 14a05fe296aa..ea9cc1c5b2af 100644 --- a/tezt/tests/expected/dal.ml/Alpha- Testing rollup and Data availability layer node (rollup_node_applies_dal_.out +++ b/tezt/tests/expected/dal.ml/Alpha- Testing rollup and Data availability layer node (rollup_node_applies_dal_.out @@ -75,11 +75,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1001.226 Resulting inbox state: { level = 5 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 nb_messages_in_commitment_period = 16 - message_counter = 4 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 4 index = 4 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -117,11 +116,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1010.725 Resulting inbox state: { level = 6 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 6 nb_messages_in_commitment_period = 34 - message_counter = 17 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 index = 5 back_pointers = [SC_ROLLUP_INBOX_HASH] diff --git a/tezt/tests/expected/dal.ml/Alpha- Testing rollup and Data availability layer node (rollup_node_downloads_sl.out b/tezt/tests/expected/dal.ml/Alpha- Testing rollup and Data availability layer node (rollup_node_downloads_sl.out index c5c20f9a0f38..b6b8ee2173c0 100644 --- a/tezt/tests/expected/dal.ml/Alpha- Testing rollup and Data availability layer node (rollup_node_downloads_sl.out +++ b/tezt/tests/expected/dal.ml/Alpha- Testing rollup and Data availability layer node (rollup_node_downloads_sl.out @@ -75,11 +75,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1001.226 Resulting inbox state: { level = 5 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 nb_messages_in_commitment_period = 16 - message_counter = 4 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 4 index = 4 back_pointers = [SC_ROLLUP_INBOX_HASH] diff --git a/tezt/tests/expected/sc_rollup.ml/Alpha- arith - node advances PVM state with messages (external).out b/tezt/tests/expected/sc_rollup.ml/Alpha- arith - node advances PVM state with messages (external).out index deea4355e4d7..9f610209309d 100644 --- a/tezt/tests/expected/sc_rollup.ml/Alpha- arith - node advances PVM state with messages (external).out +++ b/tezt/tests/expected/sc_rollup.ml/Alpha- arith - node advances PVM state with messages (external).out @@ -67,11 +67,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.647 Resulting inbox state: { level = 3 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 3 nb_messages_in_commitment_period = 9 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 2 index = 2 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -119,11 +118,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.647 Resulting inbox state: { level = 4 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 4 nb_messages_in_commitment_period = 13 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 3 index = 3 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -171,11 +169,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 5 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 nb_messages_in_commitment_period = 17 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 4 index = 4 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -224,11 +221,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 6 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 6 nb_messages_in_commitment_period = 21 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 index = 5 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -277,11 +273,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 7 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 7 nb_messages_in_commitment_period = 25 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 6 index = 6 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -330,11 +325,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 8 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 8 nb_messages_in_commitment_period = 29 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 7 index = 7 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -383,11 +377,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 9 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 9 nb_messages_in_commitment_period = 33 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 8 index = 8 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -437,12 +430,11 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 10 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 10 nb_messages_in_commitment_period = 37 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 9 index = 9 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -492,12 +484,11 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 11 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 11 nb_messages_in_commitment_period = 41 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 10 index = 10 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -547,12 +538,11 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.681 Resulting inbox state: { level = 12 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 12 nb_messages_in_commitment_period = 45 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 11 index = 11 back_pointers = [SC_ROLLUP_INBOX_HASH] diff --git a/tezt/tests/expected/sc_rollup.ml/Alpha- arith - trigger exec output (entrypoint- -aux- earliness- 0- external).out b/tezt/tests/expected/sc_rollup.ml/Alpha- arith - trigger exec output (entrypoint- -aux- earliness- 0- external).out index fd55e0153617..7cd46743c9a6 100644 --- a/tezt/tests/expected/sc_rollup.ml/Alpha- arith - trigger exec output (entrypoint- -aux- earliness- 0- external).out +++ b/tezt/tests/expected/sc_rollup.ml/Alpha- arith - trigger exec output (entrypoint- -aux- earliness- 0- external).out @@ -57,11 +57,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1001.191 Resulting inbox state: { level = 5 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 nb_messages_in_commitment_period = 15 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 4 index = 4 back_pointers = [SC_ROLLUP_INBOX_HASH] diff --git a/tezt/tests/expected/sc_rollup.ml/Alpha- arith - trigger exec output (entrypoint- -default- earliness- 0- external.out b/tezt/tests/expected/sc_rollup.ml/Alpha- arith - trigger exec output (entrypoint- -default- earliness- 0- external.out index 8d305215b5de..e08d97822c51 100644 --- a/tezt/tests/expected/sc_rollup.ml/Alpha- arith - trigger exec output (entrypoint- -default- earliness- 0- external.out +++ b/tezt/tests/expected/sc_rollup.ml/Alpha- arith - trigger exec output (entrypoint- -default- earliness- 0- external.out @@ -57,11 +57,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1001.123 Resulting inbox state: { level = 5 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 nb_messages_in_commitment_period = 15 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 4 index = 4 back_pointers = [SC_ROLLUP_INBOX_HASH] diff --git a/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - node advances PVM state with messages (external).out b/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - node advances PVM state with messages (external).out index 101b21eaf25d..62ea0181f074 100644 --- a/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - node advances PVM state with messages (external).out +++ b/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - node advances PVM state with messages (external).out @@ -67,11 +67,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.647 Resulting inbox state: { level = 3 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 3 nb_messages_in_commitment_period = 9 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 2 index = 2 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -116,11 +115,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.647 Resulting inbox state: { level = 4 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 4 nb_messages_in_commitment_period = 13 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 3 index = 3 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -165,11 +163,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 5 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 nb_messages_in_commitment_period = 17 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 4 index = 4 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -215,11 +212,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 6 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 6 nb_messages_in_commitment_period = 21 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 index = 5 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -265,11 +261,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 7 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 7 nb_messages_in_commitment_period = 25 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 6 index = 6 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -315,11 +310,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 8 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 8 nb_messages_in_commitment_period = 29 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 7 index = 7 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -365,11 +359,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 9 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 9 nb_messages_in_commitment_period = 33 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 8 index = 8 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -416,12 +409,11 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 10 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 10 nb_messages_in_commitment_period = 37 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 9 index = 9 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -468,12 +460,11 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.664 Resulting inbox state: { level = 11 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 11 nb_messages_in_commitment_period = 41 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 10 index = 10 back_pointers = [SC_ROLLUP_INBOX_HASH] @@ -520,12 +511,11 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1000.681 Resulting inbox state: { level = 12 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 12 nb_messages_in_commitment_period = 45 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 11 index = 11 back_pointers = [SC_ROLLUP_INBOX_HASH] diff --git a/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - trigger exec output (entrypoint- -aux- earliness- 0- externa.out b/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - trigger exec output (entrypoint- -aux- earliness- 0- externa.out index 70fb4ea3efeb..5ffecc22894d 100644 --- a/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - trigger exec output (entrypoint- -aux- earliness- 0- externa.out +++ b/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - trigger exec output (entrypoint- -aux- earliness- 0- externa.out @@ -57,11 +57,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1001.072 Resulting inbox state: { level = 5 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 nb_messages_in_commitment_period = 15 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 4 index = 4 back_pointers = [SC_ROLLUP_INBOX_HASH] diff --git a/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - trigger exec output (entrypoint- -default- earliness- 0- ext.out b/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - trigger exec output (entrypoint- -default- earliness- 0- ext.out index 7e906c3fe615..0631eb3d8211 100644 --- a/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - trigger exec output (entrypoint- -default- earliness- 0- ext.out +++ b/tezt/tests/expected/sc_rollup.ml/Alpha- wasm_2_0_0 - trigger exec output (entrypoint- -default- earliness- 0- ext.out @@ -57,11 +57,10 @@ This sequence of operations was run: This smart contract rollup messages submission was successfully applied Consumed gas: 1001.140 Resulting inbox state: { level = 5 - current messages hash = hash: [SC_ROLLUP_INBOX_HASH] + current messages hash = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 5 nb_messages_in_commitment_period = 15 - message_counter = 3 old_levels_messages = - content = hash: [SC_ROLLUP_INBOX_HASH] + content = hash: [SC_ROLLUP_INBOX_LEVEL_TREE_HASH] level: 4 index = 4 back_pointers = [SC_ROLLUP_INBOX_HASH] -- GitLab From 8c9feb22f8ee55375af30d9d2a0dbc3e090ae3ca Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Mon, 21 Nov 2022 07:46:34 +0100 Subject: [PATCH 7/8] proto/scoru: fix docstring and add comment for inbox --- .../lib_protocol/sc_rollup_inbox_repr.ml | 23 ++++++++++--------- .../lib_protocol/sc_rollup_inbox_repr.mli | 15 ++++++------ 2 files changed, 19 insertions(+), 19 deletions(-) diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml index 98db0e5944a8..8998b93dcf35 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml @@ -518,11 +518,7 @@ let add_messages_no_history inbox level payloads level_tree = (* An [inclusion_proof] is a path in the Merkelized skip list showing that a given inbox history is a prefix of another one. This path has a size logarithmic in the difference between the - levels of the two inboxes. - - [Irmin.Proof.{tree_proof, stream_proof}] could not be reused here - because there is no obvious encoding of sequences in these data - structures with the same guarantee about the size of proofs. *) + levels of the two inboxes. *) type inclusion_proof = history_proof list let inclusion_proof_encoding = @@ -852,11 +848,11 @@ let verify_proof (l, n) inbox_snapshot proof = | Some _ -> tzfail (Inbox_proof_error "more messages to read in current level")) -let produce_proof ~get_level_tree_history history inbox (l, n) = +let produce_proof ~get_level_tree_history history inbox_snapshot (l, n) = let open Lwt_result_syntax in let deref ptr = History.find ptr history in let compare {hash = _; level} = Raw_level_repr.compare level l in - let result = Skip_list.search ~deref ~compare ~cell:inbox in + let result = Skip_list.search ~deref ~compare ~cell:inbox_snapshot in let* inc, history_proof = match result with | Skip_list.{rev_path; last_cell = Found history_proof} -> @@ -864,9 +860,9 @@ let produce_proof ~get_level_tree_history history inbox (l, n) = | {last_cell = Nearest _; _} | {last_cell = No_exact_or_lower_ptr; _} | {last_cell = Deref_returned_none; _} -> - (* We are only interested to the result where [search] than a - path to the cell we were looking for. All the other cases - should be considered as an error. *) + (* We are only interested in the result where [search] returns a path to + the cell we were looking for. All the other cases should be + considered as an error. *) tzfail @@ Inbox_proof_error (Format.asprintf @@ -892,9 +888,14 @@ let produce_proof ~get_level_tree_history history inbox (l, n) = Some Sc_rollup_PVM_sig.{inbox_level = l; message_counter = n; payload} ) | None -> - if equal_history_proof inbox history_proof then + (* No payload means that there is no more message to read at the level of + [history_proof]. *) + if equal_history_proof inbox_snapshot history_proof then + (* if [history_proof] is equal to the snapshot then it means that there + is no more message to read. *) return (Single_level {inc; message_proof}, None) else + (* Else we must read the [sol] of the next level. *) let lower_message_proof = message_proof in let* input_given = let inbox_level = Raw_level_repr.succ l in diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli index 38ee7e2bde23..b6cb7c9b347b 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli @@ -223,8 +223,8 @@ val serialized_proof_encoding : serialized_proof Data_encoding.t [inbox], [history] and [level_tree_history]. If the [inbox]'s level is older than [level], the [inbox] is - updated so that the level trees of the levels older than [level] - are archived. To archive a [level_tree] for a given [level], we + updated so that the level tree of the previous level is + archived. To archive a [level_tree] for a given [level], we push it at the end of the [history] and update the witness of this history in the [inbox]. The [inbox]'s level tree for the current level is emptied to insert the [payloads] in a fresh [level_tree] @@ -261,8 +261,7 @@ val add_messages_no_history : value for the next level of the inbox. It is also needed if you want to produce a fully-up-to-date skip list for proof production. Just taking the skip list stored in the inbox at [old_levels_messages] will not include the - current level (and that current level could be quite far back in terms of - blocks if the inbox hasn't been added to for a while). *) + current level. *) val form_history_proof : History.t -> t -> (History.t * history_proof) tzresult (** This is similar to {!form_history_proof} except that it is just to be used @@ -284,7 +283,7 @@ val take_snapshot : t -> history_proof [level_tree]s of [A] are included in the previous levels [level_tree]s of [B]. The current [level_tree] of [A] and [B] are not considered. - The size of this proof is O(log_basis (L' - L)). *) + The size of this proof is O(log2 (L' - L)). *) type inclusion_proof val inclusion_proof_encoding : inclusion_proof Data_encoding.t @@ -316,9 +315,9 @@ val verify_inclusion_proof : Usually this is fairly simple because there will actually be a message at the location specified by [starting_point]. But in some cases [starting_point] is past the last message within a level, - and then the inbox proof must prove that and also provide another - proof about the message at the beginning of the next non-empty - level. *) + and then the inbox proof's verification assumes that the next input + is the SOL of the next level, if not beyond the snapshot. +*) type proof val pp_proof : Format.formatter -> proof -> unit -- GitLab From 804df10048db18c591fea499d36340fafaedcae3 Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Tue, 22 Nov 2022 07:41:51 +0100 Subject: [PATCH 8/8] node/scoru: remove unused if/then/else the if branch can't be reached with `if/then/else` --- src/proto_alpha/bin_sc_rollup_node/inbox.ml | 65 +++++++++----------- src/proto_alpha/bin_sc_rollup_node/inbox.mli | 2 +- 2 files changed, 29 insertions(+), 38 deletions(-) diff --git a/src/proto_alpha/bin_sc_rollup_node/inbox.ml b/src/proto_alpha/bin_sc_rollup_node/inbox.ml index 3de014eee1a2..f2d7e033fdc7 100644 --- a/src/proto_alpha/bin_sc_rollup_node/inbox.ml +++ b/src/proto_alpha/bin_sc_rollup_node/inbox.ml @@ -176,37 +176,34 @@ let add_messages level inbox history messages = Sc_rollup.Inbox_merkelized_payload_hashes.History.empty ~capacity:10000L in lift - @@ - if messages = [] then return (messages_history, None, history, inbox) - else - let*? messages = List.map_e Sc_rollup.Inbox_message.serialize messages in - (* TODO: https://gitlab.com/tezos/tezos/-/issues/3978 + @@ let*? messages = List.map_e Sc_rollup.Inbox_message.serialize messages in + (* TODO: https://gitlab.com/tezos/tezos/-/issues/3978 - The number of messages during commitment period is broken with the - unique inbox. *) - (* let commitment_period = - * node_ctxt.protocol_constants.parametric.sc_rollup - * .commitment_period_in_blocks |> Int32.of_int - * in - * let inbox = - * Sc_rollup.Inbox.refresh_commitment_period - * ~commitment_period - * ~level - * inbox - * in *) - let*? messages_history, messages_tree, history, inbox = - Sc_rollup.Inbox.add_messages - messages_history - history - inbox - level - messages - None - in - let messages_tree_hash = - Sc_rollup.Inbox_merkelized_payload_hashes.hash messages_tree - in - return (messages_history, Some messages_tree_hash, history, inbox) + The number of messages during commitment period is broken with the + unique inbox. *) + (* let commitment_period = + * node_ctxt.protocol_constants.parametric.sc_rollup + * .commitment_period_in_blocks |> Int32.of_int + * in + * let inbox = + * Sc_rollup.Inbox.refresh_commitment_period + * ~commitment_period + * ~level + * inbox + * in *) + let*? messages_history, messages_tree, history, inbox = + Sc_rollup.Inbox.add_messages + messages_history + history + inbox + level + messages + None + in + let messages_tree_hash = + Sc_rollup.Inbox_merkelized_payload_hashes.hash messages_tree + in + return (messages_history, messages_tree_hash, history, inbox) let process_head (node_ctxt : _ Node_context.t) Layer1.({level; hash = head_hash} as head) = @@ -243,13 +240,7 @@ let process_head (node_ctxt : _ Node_context.t) in let* () = same_inbox_as_layer_1 node_ctxt head_hash inbox in let*! () = - match messages_hash with - | None -> Lwt.return_unit - | Some messages_hash -> - State.add_messages_history - node_ctxt.store - messages_hash - messages_history + State.add_messages_history node_ctxt.store messages_hash messages_history in let*! () = State.add_inbox node_ctxt.store head_hash inbox in let*! () = State.add_history node_ctxt.store head_hash history in diff --git a/src/proto_alpha/bin_sc_rollup_node/inbox.mli b/src/proto_alpha/bin_sc_rollup_node/inbox.mli index fb58fde7e48e..86a3d6e0cfdf 100644 --- a/src/proto_alpha/bin_sc_rollup_node/inbox.mli +++ b/src/proto_alpha/bin_sc_rollup_node/inbox.mli @@ -77,7 +77,7 @@ val add_messages : Store.Histories.value -> Sc_rollup.Inbox_message.t trace -> (Store.Level_tree_histories.value - * Store.Level_tree_histories.key option + * Store.Level_tree_histories.key * Store.Histories.value * Sc_rollup.Inbox.t) tzresult -- GitLab