From 430af7475363b966174832046be7d2edc7720a79 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 23 Oct 2024 17:47:54 +0200 Subject: [PATCH 1/4] DAL/Proto: copy module V1 of skip lists to namespace V2 to start its incremental migration The commit mainly consists in duplicating the code, disabling unsed module warning with [@@@warning "-32"], and commenting the content of the module. In the next commits / MRs, we will inrementally uncomment and adapt the code to work with Content_v2.t. Then, we will be able to plug it (We include it instead of 'include V1' --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 661 ++++++++++++++++++ 1 file changed, 661 insertions(+) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 977758c6110b..832395cdc3ee 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1314,5 +1314,666 @@ module History = struct end end + module V2 = struct + [@@@warning "-32"] + + (* + module Content = Content_v1 + module Skip_list = Mk_skip_list (Content) + + type content = Content.t + + (* A pointer to a cell is the hash of its content and all the back + pointers. *) + type hash = Pointer_hash.t + + type history = (content, hash) Skip_list.cell + + type t = history + + 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" + (Tag 1) + (obj2 + (req "kind" (constant "dal_skip_list")) + (req + "skip_list" + (Skip_list.encoding Pointer_hash.encoding Content.encoding))) + (fun x -> Some ((), x)) + (fun ((), x) -> x); + ] + + let equal_history : history -> history -> bool = + Skip_list.equal Pointer_hash.equal Content.equal + + let encoding = history_encoding + + let equal : t -> t -> bool = equal_history + + let hash cell = + let current_slot = Skip_list.content cell in + let back_pointers_hashes = Skip_list.back_pointers cell in + Content.to_bytes current_slot + :: List.map Pointer_hash.to_bytes back_pointers_hashes + |> Pointer_hash.hash_bytes + + let pp_history fmt (history : history) = + let history_hash = hash history in + Format.fprintf + fmt + "@[hash : %a@;%a@]" + Pointer_hash.pp + history_hash + (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 + let name = "dal_slots_cache" + end) + (Pointer_hash) + (struct + type t = history + + let encoding = history_encoding + + let pp = pp_history + + 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 + let* new_head = + 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) + else + Skip_list.next + ~prev_cell:t + ~prev_cell_ptr + next_cell_content + ~number_of_slots + in + let new_head_hash = hash new_head in + let* cache = History_cache.remember new_head_hash new_head cache 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 + slot_headers_with_statuses = + 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 + (* TODO: Follow-up MR: Take the value of _s_status and _s_publisher into + account. *) + let attested_slot_headers = + List.map (fun (slot, _pub, _status) -> slot) slot_headers_with_statuses + 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 + | 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 + in + aux all_indices attested_slot_headers + + (* 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 update_skip_list (t : t) cache published_level ~number_of_slots + slot_headers_with_statuses = + let open Result_syntax in + let* () = + List.iter_e + (fun (slot_header, _slot_publisher, _status) -> + error_unless + Raw_level_repr.( + published_level = slot_header.Header.id.published_level) + Add_element_in_slots_skip_list_violates_ordering) + slot_headers_with_statuses + in + let* slot_headers = + fill_slot_headers + ~number_of_slots + ~published_level + slot_headers_with_statuses + in + List.fold_left_e (add_cell ~number_of_slots) (t, cache) slot_headers + + let update_skip_list_no_cache = + let empty_cache = History_cache.empty ~capacity:0L in + fun t published_level ~number_of_slots slot_headers_with_statuses -> + let open Result_syntax in + let+ cell, (_ : History_cache.t) = + update_skip_list + t + empty_cache + published_level + ~number_of_slots + slot_headers_with_statuses + in + cell + + (* Dal proofs section *) + + (** An inclusion proof is a sequence (list) of cells from the Dal skip list, + represented as [c1; c2; ...; cn], that encodes a minimal path from the + head [c1] (referred to as the "reference" or "snapshot" cell below) to a + target cell [cn]. Thanks to the back-pointers, it can be demonstrated + that the successive elements of the sequence are indeed cells of the + skip list. *) + type inclusion_proof = history list + + (** (See the documentation in the mli file to understand what we want to + prove in a refutation game involving Dal and why.) + + A Dal proof is an algebraic datatype with two cases, where we basically + prove that a Dal page is confirmed on L1 or not. Being 'not confirmed' + here includes the case where the slot's header is not published and the + case where the slot's header is published, but the attesters didn't + confirm the availability of its data. + + To produce a proof representation for a page (see function + {!produce_proof_repr} below), we assume given: + + - [page_id], identifies the page; + + - [slots_history], a current/recent cell of the slots history skip list. + Typically, it should be the skip list cell snapshotted when starting the + refutation game; + + - [get_history], a sufficiently large slots history cache, encoded as a + function from pointer hashes to their corresponding skip lists cells, to + navigate back through the successive cells of the skip list. The cache + should at least contain the cells starting from the published level of + the page ID for which we want to generate a proof. Indeed, inclusion + proofs encode paths through skip lists' cells where the head is the + reference/snapshot cell and the last element is the target cell inserted + at the level corresponding to the page's published level). Note that, the + case where the level of the page is far in the past (i.e. the skip list + was not populated yet) should be handled by the caller ; + + - [page_info], provides information for [page_id]. In case the page is + supposed to be confirmed, this argument should contain the page's + content and the proof that the page is part of the (confirmed) slot + whose ID is given in [page_id]. In case we want to show that the page is + not confirmed, the value [page_info] should be [None]. + + [dal_parameters] is used when verifying that/if the page is part of + the candidate slot (if any). *) + type proof_repr = + | Page_confirmed of { + target_cell : history; + (** [target_cell] is a cell whose content contains the slot to + which the page belongs to. *) + inc_proof : inclusion_proof; + (** [inc_proof] is a (minimal) path in the skip list that proves + cells inclusion. The head of the list is the [slots_history] + provided to produce the proof. The last cell's content is + the slot containing the page identified by [page_id], + that is: [target_cell]. *) + page_data : Page.content; + (** [page_data] is the content of the page. *) + page_proof : Page.proof; + (** [page_proof] is the proof that the page whose content is + [page_data] is actually the [page_id.page_index]th page of + the slot stored in [target_cell] and identified by + [page_id.slot_id]. *) + } (** The case where the slot's page is confirmed/attested on L1. *) + | Page_unconfirmed of {target_cell : history; inc_proof : inclusion_proof} + (** The case where the slot's page doesn't exist or is not confirmed + on L1. The fields are similar to {!Page_confirmed} case except + that we don't have a page data or proof to check. + + As said above, in case the level of the page is far in the past + (for instance, the skip list was not populated yet or the slots of + that level are not valid to be imported by the DAL anymore) should + be handled by the caller. In fact, the [proof_repr] type here only + covers levels where a new cell has been added to the skip list. *) + + let proof_repr_encoding = + let open Data_encoding in + let case_page_confirmed = + case + ~title:"confirmed dal page proof representation" + (Tag 0) + (obj5 + (req "kind" (constant "confirmed")) + (req "target_cell" history_encoding) + (req "inc_proof" (list history_encoding)) + (req "page_data" (bytes Hex)) + (req "page_proof" Page.proof_encoding)) + (function + | Page_confirmed {target_cell; inc_proof; page_data; page_proof} -> + Some ((), target_cell, inc_proof, page_data, page_proof) + | _ -> None) + (fun ((), target_cell, inc_proof, page_data, page_proof) -> + Page_confirmed {target_cell; inc_proof; page_data; page_proof}) + and case_page_unconfirmed = + case + ~title:"unconfirmed dal page proof representation" + (Tag 1) + (obj3 + (req "kind" (constant "unconfirmed")) + (req "target_cell" history_encoding) + (req "inc_proof" (list history_encoding))) + (function + | Page_unconfirmed {target_cell; inc_proof} -> + Some ((), target_cell, inc_proof) + | _ -> None) + (fun ((), target_cell, inc_proof) -> + Page_unconfirmed {target_cell; inc_proof}) + in + + union [case_page_confirmed; case_page_unconfirmed] + + (** Proof's type is set to bytes and not a structural datatype because + when a proof appears in a tezos operation or in an rpc, a user can not + reasonably understand the proof, thus it eases the work of people decoding + the proof by only supporting bytes and not the whole structured proof. *) + + type proof = bytes + + (** DAL/FIXME: https://gitlab.com/tezos/tezos/-/issues/4084 + DAL proof's encoding should be bounded *) + let proof_encoding = Data_encoding.(bytes Hex) + + type error += Dal_invalid_proof_serialization + + let () = + register_error_kind + `Permanent + ~id:"Dal_slot_repr.invalid_proof_serialization" + ~title:"Dal invalid proof serialization" + ~description:"Error occured during dal proof serialization" + Data_encoding.unit + (function Dal_invalid_proof_serialization -> Some () | _ -> None) + (fun () -> Dal_invalid_proof_serialization) + + let serialize_proof proof = + let open Result_syntax in + match Data_encoding.Binary.to_bytes_opt proof_repr_encoding proof with + | None -> tzfail Dal_invalid_proof_serialization + | Some serialized_proof -> return serialized_proof + + type error += Dal_invalid_proof_deserialization + + let () = + register_error_kind + `Permanent + ~id:"Dal_slot_repr.invalid_proof_deserialization" + ~title:"Dal invalid proof deserialization" + ~description:"Error occured during dal proof deserialization" + Data_encoding.unit + (function Dal_invalid_proof_deserialization -> Some () | _ -> None) + (fun () -> Dal_invalid_proof_deserialization) + + let deserialize_proof proof = + let open Result_syntax in + match Data_encoding.Binary.of_bytes_opt proof_repr_encoding proof with + | None -> tzfail Dal_invalid_proof_deserialization + | Some deserialized_proof -> return deserialized_proof + + let pp_inclusion_proof = Format.pp_print_list pp_history + + let pp_proof ~serialized fmt p = + if serialized then Format.pp_print_string fmt (Bytes.to_string p) + else + match deserialize_proof p with + | Error msg -> Error_monad.pp_trace fmt msg + | Ok proof -> ( + match proof with + | Page_confirmed {target_cell; inc_proof; page_data; page_proof} -> + Format.fprintf + fmt + "Page_confirmed (target_cell=%a, data=%s,@ \ + inc_proof:[size=%d |@ path=%a]@ page_proof:%a)" + pp_history + target_cell + (Bytes.to_string page_data) + (List.length inc_proof) + pp_inclusion_proof + inc_proof + Page.pp_proof + page_proof + | Page_unconfirmed {target_cell; inc_proof} -> + Format.fprintf + fmt + "Page_unconfirmed (target_cell = %a | inc_proof:[size=%d@ | \ + path=%a])" + pp_history + target_cell + (List.length inc_proof) + pp_inclusion_proof + inc_proof) + + type error += + | Dal_proof_error of string + | Unexpected_page_size of {expected_size : int; page_size : int} + + let () = + let open Data_encoding in + register_error_kind + `Permanent + ~id:"dal_slot_repr.slots_history.dal_proof_error" + ~title:"Dal proof error" + ~description:"Error occurred during Dal proof production or validation" + ~pp:(fun ppf e -> Format.fprintf ppf "Dal proof error: %s" e) + (obj1 (req "error" (string Plain))) + (function Dal_proof_error e -> Some e | _ -> None) + (fun e -> Dal_proof_error e) + + let () = + let open Data_encoding in + register_error_kind + `Permanent + ~id:"dal_slot_repr.slots_history.unexpected_page_size" + ~title:"Unexpected page size" + ~description: + "The size of the given page content doesn't match the expected one." + ~pp:(fun ppf (expected, size) -> + Format.fprintf + ppf + "The size of a Dal page is expected to be %d bytes. The given one \ + has %d" + expected + size) + (obj2 (req "expected_size" int16) (req "page_size" int16)) + (function + | Unexpected_page_size {expected_size; page_size} -> + Some (expected_size, page_size) + | _ -> None) + (fun (expected_size, page_size) -> + Unexpected_page_size {expected_size; page_size}) + + let dal_proof_error reason = Dal_proof_error reason + + let proof_error reason = error @@ dal_proof_error reason + + let check_page_proof dal_params proof data ({Page.page_index; _} as pid) + commitment = + let open Result_syntax in + let* dal = + match Dal.make dal_params with + | Ok dal -> return dal + | Error (`Fail s) -> proof_error s + in + let fail_with_error_msg what = + Format.kasprintf proof_error "%s (page id=%a)." what Page.pp pid + in + match Dal.verify_page dal commitment ~page_index data proof with + | Ok true -> return_unit + | Ok false -> + fail_with_error_msg + "Wrong page content for the given page index and slot commitment" + | Error `Segment_index_out_of_range -> + fail_with_error_msg "Segment_index_out_of_range" + | Error `Page_length_mismatch -> + tzfail + @@ Unexpected_page_size + { + expected_size = dal_params.page_size; + page_size = Bytes.length data; + } + + (** The [produce_proof_repr] function assumes that some invariants hold, such as: + - The DAL has been activated, + - The level of [page_id] is after the DAL activation level. + + Under these assumptions, we recall that we maintain an invariant + ensuring that we a have a cell per slot index in the skip list at every level + after DAL activation. *) + let produce_proof_repr dal_params page_id ~page_info ~get_history slots_hist + = + let open Lwt_result_syntax in + let Page.{slot_id = target_slot_id; page_index = _} = page_id in + (* We first search for the slots attested at level [published_level]. *) + let*! search_result = + Skip_list.search ~deref:get_history ~target_slot_id ~cell:slots_hist + in + (* The search should necessarily find a cell in the skip list (assuming + enough cache is given) under the assumptions made when calling + {!produce_proof_repr}. *) + match search_result.Skip_list.last_cell with + | Deref_returned_none -> + tzfail + @@ dal_proof_error + "Skip_list.search returned 'Deref_returned_none': Slots history \ + cache is ill-formed or has too few entries." + | No_exact_or_lower_ptr -> + tzfail + @@ dal_proof_error + "Skip_list.search returned 'No_exact_or_lower_ptr', while it is \ + initialized with a min elt (slot zero)." + | Nearest _ -> + (* This should not happen: there is one cell at each level + after DAL activation. The case where the page's level is before DAL + activation level should be handled by the caller + ({!Sc_refutation_proof.produce} in our case). *) + tzfail + @@ dal_proof_error + "Skip_list.search returned Nearest', while all given levels to \ + produce proofs are supposed to be in the skip list." + | Found target_cell -> ( + let inc_proof = List.rev search_result.Skip_list.rev_path in + match (page_info, Skip_list.content target_cell) with + | Some (page_data, page_proof), Attested {commitment; id = _} -> + (* The case where the slot to which the page is supposed to belong + is found and the page's information are given. *) + let*? () = + (* We check the page's proof against the commitment. *) + check_page_proof + dal_params + page_proof + page_data + page_id + commitment + in + (* All checks succeeded. We return a `Page_confirmed` proof. *) + return + ( Page_confirmed {target_cell; inc_proof; page_data; page_proof}, + Some page_data ) + | None, Unattested _ -> + (* The slot corresponding to the given page's index is not found in + the attested slots of the page's level, and no information is + given for that page. So, we produce a proof that the page is not + attested. *) + return (Page_unconfirmed {target_cell; inc_proof}, None) + | None, Attested _ -> + (* Mismatch: case where no page information are given, but the + slot is attested. *) + tzfail + @@ dal_proof_error + "The page ID's slot is confirmed, but no page content and \ + proof are provided." + | Some _, Unattested _ -> + (* Mismatch: case where page information are given, but the slot + is not attested. *) + tzfail + @@ dal_proof_error + "The page ID's slot is not confirmed, but page content and \ + proof are provided.") + + let produce_proof dal_params page_id ~page_info ~get_history slots_hist = + let open Lwt_result_syntax in + let* proof_repr, page_data = + produce_proof_repr dal_params page_id ~page_info ~get_history slots_hist + in + let*? serialized_proof = serialize_proof proof_repr in + return (serialized_proof, page_data) + + (* Given a starting cell [snapshot] and a (final) [target], this function + checks that the provided [inc_proof] encodes a minimal path from + [snapshot] to [target]. *) + let verify_inclusion_proof inc_proof ~src:snapshot ~dest:target = + let assoc = List.map (fun c -> (hash c, c)) inc_proof in + let path = List.split assoc |> fst in + let deref = + let open Map.Make (Pointer_hash) in + let map = of_seq (List.to_seq assoc) in + fun ptr -> find_opt ptr map + in + let snapshot_ptr = hash snapshot in + let target_ptr = hash target in + error_unless + (Skip_list.valid_back_path + ~equal_ptr:Pointer_hash.equal + ~deref + ~cell_ptr:snapshot_ptr + ~target_ptr + path) + (dal_proof_error "verify_proof_repr: invalid inclusion Dal proof.") + + let verify_proof_repr dal_params page_id snapshot proof = + let open Result_syntax in + let Page.{slot_id = Header.{published_level; index}; page_index = _} = + page_id + in + let* target_cell, inc_proof, page_proof_check = + match proof with + | Page_confirmed {target_cell; inc_proof; page_data; page_proof} -> + let page_proof_check = + Some + (fun commitment -> + (* We check that the page indeed belongs to the target slot at the + given page index. *) + let* () = + check_page_proof + dal_params + page_proof + page_data + page_id + commitment + in + (* If the check succeeds, we return the data/content of the + page. *) + return page_data) + in + return (target_cell, inc_proof, page_proof_check) + | Page_unconfirmed {target_cell; inc_proof} -> + return (target_cell, inc_proof, None) + in + let cell_content = Skip_list.content target_cell in + (* We check that the target cell has the same level and index than the + page we're about to prove. *) + let cell_id = Content.content_id cell_content in + let* () = + error_when + Raw_level_repr.(cell_id.published_level <> published_level) + (dal_proof_error "verify_proof_repr: published_level mismatch.") + in + let* () = + error_when + (not (Dal_slot_index_repr.equal cell_id.index index)) + (dal_proof_error "verify_proof_repr: slot index mismatch.") + in + (* We check that the given inclusion proof indeed links our L1 snapshot to + the target cell. *) + let* () = + verify_inclusion_proof inc_proof ~src:snapshot ~dest:target_cell + in + match (page_proof_check, cell_content) with + | None, Unattested _ -> return_none + | Some page_proof_check, Attested {commitment; _} -> + let* page_data = page_proof_check commitment in + return_some page_data + | Some _, Unattested _ -> + error + @@ dal_proof_error + "verify_proof_repr: the unconfirmation proof contains the \ + target slot." + | None, Attested _ -> + error + @@ dal_proof_error + "verify_proof_repr: the confirmation proof doesn't contain the \ + attested slot." + + let verify_proof dal_params page_id snapshot serialized_proof = + let open Result_syntax in + let* proof_repr = deserialize_proof serialized_proof in + verify_proof_repr dal_params page_id snapshot proof_repr + + module Internal_for_tests = struct + type cell_content = Content.t = + | Unattested of Header.id + | Attested of Header.t + + let content = Skip_list.content + + let proof_statement_is serialized_proof expected = + match deserialize_proof serialized_proof with + | Error _ -> false + | Ok proof -> ( + match (expected, proof) with + | `Confirmed, Page_confirmed _ | `Unconfirmed, Page_unconfirmed _ -> + true + | _ -> false) + end + *) + end + include V1 end -- GitLab From 833bca048b247778e59365c9e15b6ac076848cc7 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 24 Oct 2024 16:40:56 +0200 Subject: [PATCH 2/4] DAL/Proto: avoid errors' titles clash between V1 and V2 modules This will be fixed when addressing https://gitlab.com/tezos/tezos/-/issues/7574 --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 12 ++++++------ 1 file changed, 6 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 832395cdc3ee..95c50369ab74 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -735,7 +735,7 @@ module History = struct module History_cache = Bounded_history_repr.Make (struct - let name = "dal_slots_cache" + let name = "dal_slots_cache_" end) (Pointer_hash) (struct @@ -1395,7 +1395,7 @@ module History = struct module History_cache = Bounded_history_repr.Make (struct - let name = "dal_slots_cache" + let name = "dal_slots_cache_v2" end) (Pointer_hash) (struct @@ -1646,7 +1646,7 @@ module History = struct let () = register_error_kind `Permanent - ~id:"Dal_slot_repr.invalid_proof_serialization" + ~id:"Dal_slot_repr.invalid_proof_serialization_" ~title:"Dal invalid proof serialization" ~description:"Error occured during dal proof serialization" Data_encoding.unit @@ -1664,7 +1664,7 @@ module History = struct let () = register_error_kind `Permanent - ~id:"Dal_slot_repr.invalid_proof_deserialization" + ~id:"Dal_slot_repr.invalid_proof_deserialization_" ~title:"Dal invalid proof deserialization" ~description:"Error occured during dal proof deserialization" Data_encoding.unit @@ -1718,7 +1718,7 @@ module History = struct let open Data_encoding in register_error_kind `Permanent - ~id:"dal_slot_repr.slots_history.dal_proof_error" + ~id:"dal_slot_repr.slots_history.dal_proof_error_" ~title:"Dal proof error" ~description:"Error occurred during Dal proof production or validation" ~pp:(fun ppf e -> Format.fprintf ppf "Dal proof error: %s" e) @@ -1730,7 +1730,7 @@ module History = struct let open Data_encoding in register_error_kind `Permanent - ~id:"dal_slot_repr.slots_history.unexpected_page_size" + ~id:"dal_slot_repr.slots_history.unexpected_page_size_" ~title:"Unexpected page size" ~description: "The size of the given page content doesn't match the expected one." -- GitLab From ab890e387bddeecdc60abd276e3e04052feb4f46 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 24 Oct 2024 08:46:59 +0200 Subject: [PATCH 3/4] DAL/Proto: Start migrating module V2 to use Content_v2.t For the moment, we just change module Content = Content_v2 and uncomment all (first) functions that don't need to be adapted --- 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 95c50369ab74..795972d5611d 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1317,8 +1317,7 @@ module History = struct module V2 = struct [@@@warning "-32"] - (* - module Content = Content_v1 + module Content = Content_v2 module Skip_list = Mk_skip_list (Content) type content = Content.t @@ -1435,6 +1434,8 @@ module History = struct let* cache = History_cache.remember new_head_hash new_head cache 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: -- GitLab From 8c7916a1612c5031ccb477166f856708d21f2a22 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 24 Oct 2024 09:03:07 +0200 Subject: [PATCH 4/4] DAL/Proto: Adapt function `fill_slot_headers` used when adding cells to the skip list Auxilliary function `fill_slot_headers` is used by exported functions `update_skip_list` and `update_skip_list_no_cache` to insert new cells to the skip list at every new levels. For that, slot ids for which some commitments have been published [attested_lag] earlier are inserted with the `Published` variant (either attested or not). Slot indices for which no publication is included, a cell with a content `Unpublished` is inserted. At every level, cells are inserted in increasing order w.r.t. the slot ids in their content. --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 37 ++++++++++++------- 1 file changed, 23 insertions(+), 14 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 795972d5611d..d7398f9ae5b0 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1434,8 +1434,6 @@ module History = struct let* cache = History_cache.remember new_head_hash new_head cache 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: @@ -1453,32 +1451,42 @@ module History = struct 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 - (* TODO: Follow-up MR: Take the value of _s_status and _s_publisher into - account. *) - let attested_slot_headers = - List.map (fun (slot, _pub, _status) -> slot) slot_headers_with_statuses + let mk_unpublished index = + Content.Unpublished 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 + | _, [] -> List.map mk_unpublished indices |> ok | [], _s :: _ -> tzfail Add_element_in_slots_skip_list_violates_ordering - | i :: indices', s :: slots' -> + | i :: indices', (s, publisher, status) :: slots' -> if I.(i = s.Header.id.index) then let* res = aux indices' slots' in - Content.Attested s :: res |> ok + let Dal_attestation_repr.Accountability. + {is_proto_attested; attested_shards; total_shards} = + status + in + let content = + Content.( + Published + { + header = s; + publisher; + is_proto_attested; + attested_shards; + total_shards; + }) + in + content :: res |> ok else if I.(i < s.Header.id.index) then let* res = aux indices' slots in - mk_unattested i :: res |> ok + mk_unpublished i :: res |> ok else (* i > s.Header.id.index *) tzfail Add_element_in_slots_skip_list_violates_ordering in - aux all_indices attested_slot_headers + aux all_indices slot_headers_with_statuses (* 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 @@ -1518,6 +1526,7 @@ module History = struct in cell + (* (* Dal proofs section *) (** An inclusion proof is a sequence (list) of cells from the Dal skip list, -- GitLab