From ab3c1272efebf5858e1df478f6d81aa92732e86d Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Sat, 17 Sep 2022 20:35:35 +0200 Subject: [PATCH] Proto/Dal: fix invariant check before adding an elt to skip list --- src/proto_alpha/bin_sc_rollup_node/daemon.ml | 2 +- .../bin_sc_rollup_node/dal_slots_tracker.ml | 5 +- .../lib_protocol/alpha_context.mli | 8 +- src/proto_alpha/lib_protocol/dal_apply.ml | 2 +- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 122 +++++++++++------- .../lib_protocol/dal_slot_repr.mli | 8 +- .../lib_protocol/dal_slot_storage.ml | 5 +- src/proto_alpha/lib_protocol/raw_context.ml | 2 +- .../test/helpers/operation_generator.ml | 2 +- .../validate/manager_operation_helpers.ml | 2 +- 10 files changed, 93 insertions(+), 65 deletions(-) diff --git a/src/proto_alpha/bin_sc_rollup_node/daemon.ml b/src/proto_alpha/bin_sc_rollup_node/daemon.ml index 9b2ef8f7c7db..f6857ac08d2c 100644 --- a/src/proto_alpha/bin_sc_rollup_node/daemon.ml +++ b/src/proto_alpha/bin_sc_rollup_node/daemon.ml @@ -114,7 +114,7 @@ module Make (PVM : Pvm.S) = struct in tzfail (Sc_rollup_node_errors.Lost_game (loser, reason, slashed_amount)) | Dal_publish_slot_header {slot}, Dal_publish_slot_header_result _ -> - let {Dal.Slot.index; _} = slot in + let {Dal.Slot.id = {index; _}; _} = slot in (* DAL/FIXME: https://gitlab.com/tezos/tezos/-/issues/3510 We store slot headers for all slots. In practice, it would be convenient to store only information about diff --git a/src/proto_alpha/bin_sc_rollup_node/dal_slots_tracker.ml b/src/proto_alpha/bin_sc_rollup_node/dal_slots_tracker.ml index d8161819b31f..3a0f24f88e1e 100644 --- a/src/proto_alpha/bin_sc_rollup_node/dal_slots_tracker.ml +++ b/src/proto_alpha/bin_sc_rollup_node/dal_slots_tracker.ml @@ -168,7 +168,7 @@ let confirmed_slots node_ctxt (Layer1.Head {hash; _} as head) = let save_confirmed_slot_headers node_ctxt hash slots_to_save = List.iter_s - (fun ({Dal.Slot.index; _} as slot) -> + (fun (Dal.Slot.{id = {index; _}; _} as slot) -> Store.Dal_confirmed_slots.add node_ctxt.Node_context.store ~primary_key:hash @@ -262,7 +262,8 @@ module Confirmed_slots_history = struct let slots_to_save = let open Dal in List.fast_sort - (fun {Slot.index = a; _} {Slot.index = b; _} -> Slot_index.compare a b) + (fun Slot.{id = {index = a; _}; _} {id = {index = b; _}; _} -> + Slot_index.compare a b) slots_to_save in let*! pred = Layer1.predecessor store head in diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 91f1226c6362..f977739306f9 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2804,11 +2804,9 @@ module Dal : sig (** This module re-exports definitions from {!Dal_slot_repr}, {!Dal_slot_storage} and {!Raw_context.Dal}. *) module Slot : sig - type t = { - published_level : Raw_level.t; - index : Slot_index.t; - header : Slot_header.t; - } + type id = {published_level : Raw_level.t; index : Slot_index.t} + + type t = {id : id; header : Slot_header.t} val encoding : t Data_encoding.t diff --git a/src/proto_alpha/lib_protocol/dal_apply.ml b/src/proto_alpha/lib_protocol/dal_apply.ml index a0ade2f5fd3b..34c812e5a87f 100644 --- a/src/proto_alpha/lib_protocol/dal_apply.ml +++ b/src/proto_alpha/lib_protocol/dal_apply.ml @@ -62,7 +62,7 @@ let apply_data_availability ctxt data_availability ~endorser = Dal.Endorsement.record_available_shards ctxt data_availability shards |> return -let validate_publish_slot_header ctxt Dal.Slot.{index; _} = +let validate_publish_slot_header ctxt Dal.Slot.{id = {index; _}; _} = assert_dal_feature_enabled ctxt >>? fun () -> let open Tzresult_syntax in let open Constants in diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index a948984b0d80..a55d4036ff18 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -63,30 +63,35 @@ module Index = struct let equal = Compare.Int.equal end -type t = { - published_level : Raw_level_repr.t; - index : Index.t; - header : Header.t; -} +type id = {published_level : Raw_level_repr.t; index : Index.t} + +type t = {id : id; header : Header.t} type slot = t type slot_index = Index.t -let slot_equal ({published_level; index; header} : t) s2 = +let slot_id_equal ({published_level; index} : id) s2 = Raw_level_repr.equal published_level s2.published_level && Index.equal index s2.index - && Header.equal header s2.header -let zero = +let slot_equal ({id; header} : t) s2 = + slot_id_equal id s2.id && Header.equal header s2.header + +let compare_slot_id ({published_level; index} : id) s2 = + let c = Raw_level_repr.compare published_level s2.published_level in + if Compare.Int.(c <> 0) then c else Index.compare index s2.index + +let zero_id = { (* We don't expect to have any published slot at level Raw_level_repr.root. *) published_level = Raw_level_repr.root; index = Index.zero; - header = Header.zero; } +let zero = {id = zero_id; header = Header.zero} + module Slot_index = Index module Page = struct @@ -134,14 +139,16 @@ end let slot_encoding = let open Data_encoding in conv - (fun {published_level; index; header} -> (published_level, index, header)) - (fun (published_level, index, header) -> {published_level; index; header}) + (fun {id = {published_level; index}; header} -> + (published_level, index, header)) + (fun (published_level, index, header) -> + {id = {published_level; index}; header}) (obj3 (req "level" Raw_level_repr.encoding) (req "index" Data_encoding.uint8) (req "header" Header.encoding)) -let pp_slot fmt {published_level; index; header} = +let pp_slot fmt {id = {published_level; index}; header} = Format.fprintf fmt "published_level: %a index: %a header: %a" @@ -171,8 +178,8 @@ module Slot_market = struct let length {length; _} = length let register t new_slot = - if not Compare.Int.(0 <= new_slot.index && new_slot.index < t.length) then - None + if not Compare.Int.(0 <= new_slot.id.index && new_slot.id.index < t.length) + then None else let has_changed = ref false in let update = function @@ -181,7 +188,7 @@ module Slot_market = struct Some new_slot | Some x -> Some x in - let slots = Slot_index_map.update new_slot.index update t.slots in + let slots = Slot_index_map.update new_slot.id.index update t.slots in let t = {t with slots} in Some (t, !has_changed) @@ -237,34 +244,63 @@ module Slots_history = struct let basis = 2 end - type error += Add_element_in_slots_skip_list_violates_ordering - - let () = - register_error_kind - `Temporary - ~id:"Dal_slot_repr.add_element_in_slots_skip_list_violates_ordering" - ~title:"Add an element in slots skip list that violates ordering" - ~description: - "Attempting to add an element on top of the Dal confirmed slots skip \ - list that violates the ordering." - Data_encoding.unit - (function - | Add_element_in_slots_skip_list_violates_ordering -> Some () - | _ -> None) - (fun () -> Add_element_in_slots_skip_list_violates_ordering) - module Skip_list = struct include Skip_list_repr.Make (Skip_list_parameters) - let next ~compare ~prev_cell ~prev_cell_ptr elt = + (** All confirmed DAL slots will be stored in a skip list, where only the + last cell is remembered in the L1 context. The skip list is used in + the proof phase of a refutation game to verify whether a given slot + exists (i.e., confirmed) or not in the skip list. The skip list is + supposed to be sorted, as its 'search' function explicitly uses a given + `compare` function during the list traversal to quickly (in log(size)) + reach the target if any. + + In our case, we will store one slot per cell in the skip list and + maintain that the list is well sorted (and without redundancy) w.r.t. + the [compare_slot_id] function. + + Below, we redefine the [next] function (that allows adding elements + on top of the list) to enforce that the constructed skip list is + well-sorted. We also define a wrapper around the search function to + guarantee that it can only be called with the adequate compare function. + *) + + let compare = compare_slot_id + + let compare_lwt a b = Lwt.return @@ compare a b + + type error += Add_element_in_slots_skip_list_violates_ordering + + let () = + register_error_kind + `Temporary + ~id:"Dal_slot_repr.add_element_in_slots_skip_list_violates_ordering" + ~title:"Add an element in slots skip list that violates ordering" + ~description: + "Attempting to add an element on top of the Dal confirmed slots skip \ + list that violates the ordering." + Data_encoding.unit + (function + | Add_element_in_slots_skip_list_violates_ordering -> Some () + | _ -> None) + (fun () -> Add_element_in_slots_skip_list_violates_ordering) + + let next ~prev_cell ~prev_cell_ptr elt = let open Tzresult_syntax in - let c = compare elt (content prev_cell) in let* () = error_when - Compare.Int.(c <= 0) + (Compare.Int.( <= ) (compare elt.id (content prev_cell).id) 0) Add_element_in_slots_skip_list_violates_ordering in return @@ next ~prev_cell ~prev_cell_ptr elt + + let search ~deref ~cell_ptr ~id_target = + search ~deref ~cell_ptr ~compare:(compare_lwt id_target) + + (* FIXME/DAL: search will be used in refutation proof. But we need to + introduce it here to explain why we need an ordering on the skip list's + elements. *) + let _ = ignore search end module V1 = struct @@ -327,18 +363,12 @@ module Slots_history = struct let equal = equal_history end) - let add_confirmed_slot = - let compare (s1 : slot) s2 = - Raw_level_repr.compare s1.published_level s2.published_level - in - fun (t, cache) slot -> - let open Tzresult_syntax in - let prev_cell_ptr = hash_skip_list_cell t in - let* cache = History_cache.remember prev_cell_ptr t cache in - let* new_cell = - Skip_list.next ~compare ~prev_cell:t ~prev_cell_ptr slot - in - return (new_cell, cache) + let add_confirmed_slot (t, cache) slot = + let open Tzresult_syntax in + let prev_cell_ptr = hash_skip_list_cell t in + let* cache = History_cache.remember prev_cell_ptr t cache in + let* new_cell = Skip_list.next ~prev_cell:t ~prev_cell_ptr slot in + return (new_cell, cache) let add_confirmed_slots (t : t) cache slots = List.fold_left_e add_confirmed_slot (t, cache) slots diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli index 79e0662d7598..9ff394e16f45 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli @@ -89,11 +89,9 @@ end (** For Layer-1, a slot is described by the level at which it is published, the slot's index (in the list of slots), and the slot's header (KATE commitment hash). *) -type t = { - published_level : Raw_level_repr.t; - index : Index.t; - header : Header.t; -} +type id = {published_level : Raw_level_repr.t; index : Index.t} + +type t = {id : id; header : Header.t} type slot = t diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.ml b/src/proto_alpha/lib_protocol/dal_slot_storage.ml index e34d6a94191d..d5374f52bdb5 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_storage.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_storage.ml @@ -33,10 +33,11 @@ let finalize_current_slots ctxt = | _ :: _ -> Storage.Dal.Slot_headers.add ctxt current_level.level slots let compute_available_slots ctxt seen_slots = + let open Dal_slot_repr in let fold_available_slots (rev_slots, available_slots) slot = - if Raw_context.Dal.is_slot_available ctxt slot.Dal_slot_repr.index then + if Raw_context.Dal.is_slot_available ctxt slot.id.index then ( slot :: rev_slots, - Dal_endorsement_repr.commit available_slots slot.Dal_slot_repr.index ) + Dal_endorsement_repr.commit available_slots slot.id.index ) else (rev_slots, available_slots) in List.fold_left diff --git a/src/proto_alpha/lib_protocol/raw_context.ml b/src/proto_alpha/lib_protocol/raw_context.ml index 6ca0e5e0fbf7..59cecc74b496 100644 --- a/src/proto_alpha/lib_protocol/raw_context.ml +++ b/src/proto_alpha/lib_protocol/raw_context.ml @@ -1562,7 +1562,7 @@ module Dal = struct %d. Found: %a." length Dal_slot_repr.Index.pp - slot.Dal_slot_repr.index) + slot.Dal_slot_repr.id.index) Data_encoding.( obj2 (req "length" int31) (req "slot" Dal_slot_repr.encoding)) (function diff --git a/src/proto_alpha/lib_protocol/test/helpers/operation_generator.ml b/src/proto_alpha/lib_protocol/test/helpers/operation_generator.ml index 0709c58728e4..9cb8fc76f58b 100644 --- a/src/proto_alpha/lib_protocol/test/helpers/operation_generator.ml +++ b/src/proto_alpha/lib_protocol/test/helpers/operation_generator.ml @@ -663,7 +663,7 @@ let generate_dal_publish_slot_header random_state : let published_level = Alpha_context.Raw_level.of_int32_exn Int32.zero in let index = Alpha_context.Dal.Slot_index.zero in let header = Alpha_context.Dal.Slot_header.zero in - let slot = Alpha_context.Dal.Slot.{published_level; index; header} in + let slot = Alpha_context.Dal.Slot.{id = {published_level; index}; header} in Dal_publish_slot_header {slot} in generate_manager random_state gen_dal_publish diff --git a/src/proto_alpha/lib_protocol/test/integration/validate/manager_operation_helpers.ml b/src/proto_alpha/lib_protocol/test/integration/validate/manager_operation_helpers.ml index b3394c31f09c..9915b8ec7120 100644 --- a/src/proto_alpha/lib_protocol/test/integration/validate/manager_operation_helpers.ml +++ b/src/proto_alpha/lib_protocol/test/integration/validate/manager_operation_helpers.ml @@ -1029,7 +1029,7 @@ let mk_dal_publish_slot_header (oinfos : operation_req) (infos : infos) = let published_level = Alpha_context.Raw_level.of_int32_exn Int32.zero in let index = Alpha_context.Dal.Slot_index.zero in let header = Alpha_context.Dal.Slot_header.zero in - let slot = Alpha_context.Dal.Slot.{published_level; index; header} in + let slot = Alpha_context.Dal.Slot.{id = {published_level; index}; header} in Op.dal_publish_slot_header ?fee:oinfos.fee ?gas_limit:oinfos.gas_limit -- GitLab