From 727b1524156b37fcc71c46ec0d59468dcacd0e3f Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Fri, 2 Feb 2024 17:28:10 +0100 Subject: [PATCH 1/8] Proto/Dal: expose infix compare functions in dal_slot_index_repr --- src/proto_alpha/lib_protocol/dal_slot_index_repr.ml | 6 ++++-- src/proto_alpha/lib_protocol/dal_slot_index_repr.mli | 6 ++---- 2 files changed, 6 insertions(+), 6 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_index_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_index_repr.ml index d9fd7c365b67..ce2abb9d0910 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_index_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_index_repr.ml @@ -72,9 +72,11 @@ let to_int slot_index = slot_index [@@ocaml.inline always] let to_int_list l = l [@@ocaml.inline always] -let compare = Compare.Int.compare +include Compare.Make (struct + type nonrec t = t -let equal = Compare.Int.equal + let compare = Compare.Int.compare +end) let slots_range ~number_of_slots ~lower ~upper = let open Result_syntax in diff --git a/src/proto_alpha/lib_protocol/dal_slot_index_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_index_repr.mli index 1a65d785d38f..380825600d5a 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_index_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_index_repr.mli @@ -54,10 +54,6 @@ val to_int : t -> int val to_int_list : t list -> int list -val compare : t -> t -> int - -val equal : t -> t -> bool - (** [slots_range ~number_of_slots ~lower ~upper] returns the list of slots indexes between [lower] and [upper]. @@ -73,3 +69,5 @@ val slots_range_opt : (** [is_succ elt ~succ] returns true if and only if elt + 1 = succ. *) val is_succ : t -> succ:t -> bool + +include Compare.S with type t := t -- GitLab From ec645ec51ddf3e82a86b4de95f4020e7297d46c3 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 31 Jan 2024 13:04:32 +0100 Subject: [PATCH 2/8] Proto/Dal: start switching to new content for skip lists in V1 module --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 13 +++++-------- 1 file changed, 5 insertions(+), 8 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index b274fc0d70e1..6800eee62fb2 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1110,14 +1110,8 @@ module History_v2 = struct Lwt.search ~deref ~cell ~compare:(compare_with_slot_id target_slot_id) end - (* TODO: will be uncommented incrementally on the next MRs *) - (* module V1 = struct - (* The content of a cell is the hash of all the slot commitments - represented as a merkle list. *) - (* TODO/DAL: https://gitlab.com/tezos/tezos/-/issues/3765 - Decide how to store attested slots in the skip list's content. *) - type content = Header.t + type content = Content.t (* A pointer to a cell is the hash of its content and all the back pointers. *) @@ -1127,6 +1121,9 @@ module History_v2 = struct type t = history + (* TODO: will be uncommented incrementally on the next MRs *) + + (* let history_encoding = Skip_list.encoding Pointer_hash.encoding Header.encoding @@ -1715,8 +1712,8 @@ module History_v2 = struct true | _ -> false) end + *) end include V1 -*) end -- GitLab From 27b81e09e812b4eba353febd41f86eb834a5ae75 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 31 Jan 2024 13:22:57 +0100 Subject: [PATCH 3/8] Proto/Dal: define the new value of genesis skip list --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 6800eee62fb2..47c11d9958e7 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1121,6 +1121,9 @@ module History_v2 = struct type t = history + let genesis, genesis_level = + (Skip_list.genesis Content.zero, Content.zero_level) + (* TODO: will be uncommented incrementally on the next MRs *) (* @@ -1134,8 +1137,6 @@ module History_v2 = struct let equal : t -> t -> bool = equal_history - let genesis : t = Skip_list.genesis Header.zero - let hash cell = let current_slot = Skip_list.content cell in let back_pointers_hashes = Skip_list.back_pointers cell in -- GitLab From f3b717ac4998d5022797add0088dd1f1ee37d0cd Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 31 Jan 2024 13:36:58 +0100 Subject: [PATCH 4/8] Proto/Dal: migrate encoding, with retro-compatibility for old genesis --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 35 +++++++++++++++++-- 1 file changed, 32 insertions(+), 3 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 47c11d9958e7..f8c442abb9cd 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1124,12 +1124,41 @@ module History_v2 = struct let genesis, genesis_level = (Skip_list.genesis Content.zero, Content.zero_level) + let history_encoding = + let open Data_encoding in + (* The history_encoding is given as a union of two versions of the skip + list. The legacy case is only used to deserialize the skip list cells + which may appear in refutation games started on a previous version of + the protocol, before the activation of the DAL. In this case, the + snapshotted cells are always the genesis one and cannot be used by the + players so we deserialize it on the fly to the new representation of + the genesis cell. *) + union + ~tag_size:`Uint8 + [ + case + ~title:"dal_skip_list_legacy" + (Tag 0) + (obj2 + (req "kind" (constant "dal_skip_list_legacy")) + (req "skip_list" (Data_encoding.Fixed.bytes Hex 57))) + (fun _ -> None) + (fun ((), _) -> genesis); + case + ~title:"dal_skip_list_v2" + (Tag 1) + (obj2 + (req "kind" (constant "dal_skip_list_v2")) + (req + "skip_list" + (Skip_list.encoding Pointer_hash.encoding Content.encoding))) + (fun x -> Some ((), x)) + (fun ((), x) -> x); + ] + (* TODO: will be uncommented incrementally on the next MRs *) (* - let history_encoding = - Skip_list.encoding Pointer_hash.encoding Header.encoding - let equal_history : history -> history -> bool = Skip_list.equal Pointer_hash.equal Header.equal -- GitLab From ec048af4362fd8f5f985954b81885ed0d0af479c Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 31 Jan 2024 14:01:21 +0100 Subject: [PATCH 5/8] Proto/Dal: adapt more functions to the new skip lists content --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index f8c442abb9cd..5034dffdc2c6 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1156,11 +1156,8 @@ module History_v2 = struct (fun ((), x) -> x); ] - (* TODO: will be uncommented incrementally on the next MRs *) - - (* let equal_history : history -> history -> bool = - Skip_list.equal Pointer_hash.equal Header.equal + Skip_list.equal Pointer_hash.equal Content.equal let encoding = history_encoding @@ -1169,7 +1166,7 @@ module History_v2 = struct let hash cell = let current_slot = Skip_list.content cell in let back_pointers_hashes = Skip_list.back_pointers cell in - Data_encoding.Binary.to_bytes_exn Header.encoding current_slot + Data_encoding.Binary.to_bytes_exn Content.encoding current_slot :: List.map Pointer_hash.to_bytes back_pointers_hashes |> Pointer_hash.hash_bytes @@ -1180,9 +1177,11 @@ module History_v2 = struct "@[hash : %a@;%a@]" Pointer_hash.pp history_hash - (Skip_list.pp ~pp_content:Header.pp ~pp_ptr:Pointer_hash.pp) + (Skip_list.pp ~pp_content:Content.pp ~pp_ptr:Pointer_hash.pp) history + let pp = pp_history + module History_cache = Bounded_history_repr.Make (struct @@ -1199,6 +1198,9 @@ module History_v2 = struct let equal = equal_history end) + (* TODO: will be uncommented incrementally on the next MRs *) + + (* let add_confirmed_slot_header (t, cache) slot_header = let open Result_syntax in let prev_cell_ptr = hash t in -- GitLab From 0bb66eb1164d65b61c2606aa51614fb55a4b0c76 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 31 Jan 2024 14:42:27 +0100 Subject: [PATCH 6/8] Proto/Dal: helper function to insert cells in the skip list and cache --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 26 +++++++++++++++++++ 1 file changed, 26 insertions(+) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 5034dffdc2c6..d1d9597ecd45 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1198,6 +1198,32 @@ module History_v2 = struct let equal = equal_history end) + (* Insert a cell in the skip list [t] and the corresponding association [(hash(t), + t)] in the given [cache]. + + Note that if the given skip list contains the genesis cell, its content is + reset with the given content. This ensures the invariant that + there are no gaps in the successive cells of the list. *) + let add_cell (t, cache) next_cell_content ~number_of_slots = + let open Result_syntax in + let prev_cell_ptr = hash t in + let Header.{published_level; _} = + Skip_list.content t |> Content.content_id + in + if Raw_level_repr.equal published_level genesis_level then + (* If this is the first real cell of DAL, replace dummy genesis. *) + return (Skip_list.genesis next_cell_content, cache) + else + let* cache = History_cache.remember prev_cell_ptr t cache in + let* new_head = + Skip_list.next + ~prev_cell:t + ~prev_cell_ptr + next_cell_content + ~number_of_slots + in + return (new_head, cache) + (* TODO: will be uncommented incrementally on the next MRs *) (* -- GitLab From 43a08906d253bd4a99949de982ce60deb788ecf8 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 31 Jan 2024 14:59:09 +0100 Subject: [PATCH 7/8] Proto/Dal: expand slot headers lists to Content.t list with all indices --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 40 +++++++++++++++++++ 1 file changed, 40 insertions(+) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index d1d9597ecd45..a63ebc980840 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1224,6 +1224,46 @@ module History_v2 = struct in return (new_head, cache) + (* Given a list [attested_slot_headers] of well-ordered (wrt slots indices) + (attested) slot headers, this function builds an extension [l] of + [attested_slot_headers] such that: + + - all elements in [attested_slot_headers] are in [l], + + - for every slot index i in [0, number_of_slots - 1] that doesn't appear + in [attested_slot_headers], an unattested slot id is inserted in [l], + + - [l] is well sorted wrt. slots indices. *) + let fill_slot_headers ~number_of_slots ~published_level + attested_slot_headers = + let open Result_syntax in + let module I = Dal_slot_index_repr in + let* all_indices = + I.slots_range ~number_of_slots ~lower:0 ~upper:(number_of_slots - 1) + in + let mk_unattested index = + Content.Unattested Header.{published_level; index} + in + (* Hypothesis: both lists are sorted in increasing order w.r.t. slots + indices. *) + let rec aux indices slots = + match (indices, slots) with + | _, [] -> List.map mk_unattested indices |> ok + | [], s :: _ -> + tzfail Add_element_in_slots_skip_list_violates_ordering_v2 + | i :: indices', s :: slots' -> + if I.(i = s.Header.id.index) then + let* res = aux indices' slots' in + Content.Attested s :: res |> ok + else if I.(i < s.Header.id.index) then + let* res = aux indices' slots in + mk_unattested i :: res |> ok + else + (* i > s.Header.id.index *) + tzfail Add_element_in_slots_skip_list_violates_ordering_v2 + in + aux all_indices attested_slot_headers + (* TODO: will be uncommented incrementally on the next MRs *) (* -- GitLab From 04dc5f1df6a31b6dcefee71aaa670a9708cd5c4f Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 31 Jan 2024 15:08:00 +0100 Subject: [PATCH 8/8] Proto/Dal: adapt the 'add_confirmed_slot_headers__xxx' functions --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 40 ++++++++++++------- 1 file changed, 25 insertions(+), 15 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index a63ebc980840..2bbc29eec02a 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1264,28 +1264,38 @@ module History_v2 = struct in aux all_indices attested_slot_headers - (* TODO: will be uncommented incrementally on the next MRs *) - - (* - let add_confirmed_slot_header (t, cache) slot_header = + (* Assuming a [number_of_slots] per L1 level, we will ensure below that we + insert exactly [number_of_slots] cells in the skip list per level. This + will simplify the shape of proofs and help bounding the history cache + required for their generation. *) + let add_confirmed_slot_headers (t : t) cache published_level + ~number_of_slots attested_slot_headers = let open Result_syntax in - let prev_cell_ptr = hash 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_header in - return (new_cell, cache) - - let add_confirmed_slot_headers (t : t) cache slot_headers = - List.fold_left_e add_confirmed_slot_header (t, cache) slot_headers + let* slot_headers = + fill_slot_headers + ~number_of_slots + ~published_level + attested_slot_headers + in + List.fold_left_e (add_cell ~number_of_slots) (t, cache) slot_headers let add_confirmed_slot_headers_no_cache = - let open Result_syntax in - let no_cache = History_cache.empty ~capacity:0L in - fun t slots -> + let empty_cache = History_cache.empty ~capacity:0L in + fun t published_level ~number_of_slots slots -> + let open Result_syntax in let+ cell, (_ : History_cache.t) = - List.fold_left_e add_confirmed_slot_header (t, no_cache) slots + add_confirmed_slot_headers + t + empty_cache + published_level + ~number_of_slots + slots in cell + (* TODO: will be uncommented incrementally on the next MRs *) + + (* (* Dal proofs section *) (** An inclusion proof, for a page ID, is a list of the slots' history -- GitLab