From 824c808b907d5c65ed316e2740cb41c7bad74f36 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 24 Oct 2024 17:08:03 +0200 Subject: [PATCH 1/7] DAL/Proto: Adapt 'internal_for_tests' module --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 0d7af9300b66..1913b65761b4 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -1972,13 +1972,19 @@ module History = struct 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 + | Unpublished of Header.id + | Published of { + header : Header.t; + publisher : Signature.public_key_hash; + is_proto_attested : bool; + attested_shards : int; + total_shards : int; + } - let content = Skip_list.content + let content cell : cell_content = Skip_list.content cell let proof_statement_is serialized_proof expected = match deserialize_proof serialized_proof with @@ -1989,7 +1995,6 @@ module History = struct true | _ -> false) end - *) end include V1 -- GitLab From 380494789e966ee653cef624a614cc8cb19aeefa Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 24 Oct 2024 17:24:27 +0200 Subject: [PATCH 2/7] DAL/Proto: plugin module V2 and adapt tests --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 13 ++++++------ .../lib_protocol/dal_slot_repr.mli | 21 ++++++++++++++----- .../lib_protocol/test/helpers/dal_helpers.ml | 3 ++- 3 files changed, 24 insertions(+), 13 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 1913b65761b4..0a1ac2052071 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -371,8 +371,6 @@ module History = struct end module Content_v2 = struct - [@@@warning "-32"] - (** Each cell of the skip list is either a slot id (i.e. a published level and a slot index) for which no slot header is published or a published slot header associated to the address which signed the L1 operation, the @@ -658,6 +656,8 @@ module History = struct end module V1 = struct + [@@@warning "-32"] + module Content = Content_v1 module Skip_list = Mk_skip_list (Content) @@ -1197,7 +1197,8 @@ module History = struct "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 produce_proof dal_params page_id ~page_info ~get_history slots_hist : + (proof * proof option, error trace) result Lwt.t = let open Lwt_result_syntax in let* proof_repr, page_data = produce_proof_repr dal_params page_id ~page_info ~get_history slots_hist @@ -1301,7 +1302,7 @@ module History = struct | Unattested of Header.id | Attested of Header.t - let content = Skip_list.content + let content cell : cell_content = Skip_list.content cell let proof_statement_is serialized_proof expected = match deserialize_proof serialized_proof with @@ -1315,8 +1316,6 @@ module History = struct end module V2 = struct - [@@@warning "-32"] - module Content = Content_v2 module Skip_list = Mk_skip_list (Content) @@ -1997,5 +1996,5 @@ module History = struct end end - include V1 + include V2 end diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli index 09c655731a35..26fb6ed0acae 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli @@ -383,11 +383,22 @@ module History : sig | Unexpected_page_size of {expected_size : int; page_size : int} module Internal_for_tests : sig - (** The content of a cell in the DAL skip list. We don't store the slot - headers directly to refactor the common [published_level] and save - space. This is important for refutation proofs, as they have to fit in - an L1 operation. *) - type cell_content = Unattested of Header.id | Attested of Header.t + (** The content of a cell in the DAL skip list. We have [number_of_slots] + new cells per level (one per slot index). For a given slot index in + [0..number_of_slots-1], the commitment is either [Unpublished] or + [Published]. In this second case, we attach extra information in + addition to the id such as the commitment, the publisher, the number of + attested shards and whether the commitment is attested from the point of + view of the protocol. *) + type cell_content = + | Unpublished of Header.id + | Published of { + header : Header.t; + publisher : Signature.public_key_hash; + is_proto_attested : bool; + attested_shards : int; + total_shards : int; + } (** Returns the content of the last cell in the given skip list. *) val content : t -> cell_content diff --git a/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml b/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml index 30c2635cac09..b896155b7c4a 100644 --- a/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml +++ b/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml @@ -69,7 +69,8 @@ let derive_dal_parameters (reference : Cryptobox.parameters) ~redundancy_factor } let content_slot_id = function - | Hist.Internal_for_tests.Unattested id | Attested {id; _} -> id + | Hist.Internal_for_tests.Unpublished id | Published {header = {id; _}; _} -> + id module Make (Parameters : sig val dal_parameters : Alpha_context.Constants.Parametric.dal -- GitLab From 523fcfde11b04622dc48f8f8fbf2ee3fe35c27ba Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 24 Oct 2024 17:50:21 +0200 Subject: [PATCH 3/7] DAL/Proto: Removed unused V1 code --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 687 +----------------- 1 file changed, 6 insertions(+), 681 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 0a1ac2052071..f0775eaf581d 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -314,15 +314,17 @@ module History = struct (fun () -> Add_element_in_slots_skip_list_violates_ordering) module Content_v1 = struct + (* ADAL/TODO: https://gitlab.com/tezos/tezos/-/issues/7554 + + Legacy code used for migration to Content_v2. The whole [Content_v1] (and + its dependencies) should be removed 3 months after the activation of this + protocol. See issue above for more details. *) + (** Each cell of the skip list is either a slot header that has been attested, or a published level and a slot index for which no slot header is attested (so, no associated commitment). *) type t = Unattested of Header.id | Attested of Header.t - let content_id = function - | Unattested slot_id -> slot_id - | Attested {id; _} -> id - let encoding = let open Data_encoding in union @@ -349,23 +351,6 @@ module History = struct (fun ((), slot_header) -> Attested slot_header); ] - let equal t1 t2 = - match (t1, t2) with - | Unattested sid1, Unattested sid2 -> Header.slot_id_equal sid1 sid2 - | Attested sh1, Attested sh2 -> Header.equal sh1 sh2 - | Unattested _, _ | Attested _, _ -> false - - let zero, zero_level = - let zero_level = Raw_level_repr.root in - let zero_index = Dal_slot_index_repr.zero in - (Unattested {published_level = zero_level; index = zero_index}, zero_level) - - let pp fmt = function - | Unattested slot_id -> - Format.fprintf fmt "Unattested (%a)" Header.pp_id slot_id - | Attested slot_header -> - Format.fprintf fmt "Attested (%a)" Header.pp slot_header - let to_bytes current_slot = Data_encoding.Binary.to_bytes_exn encoding current_slot end @@ -655,666 +640,6 @@ module History = struct Lwt.search ~deref ~cell ~compare:(compare_with_slot_id target_slot_id) end - module V1 = 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 : - (proof * proof option, error trace) result Lwt.t = - 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 cell : cell_content = Skip_list.content cell - - 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 - module V2 = struct module Content = Content_v2 module Skip_list = Mk_skip_list (Content) -- GitLab From 54740cdee8c3937f9acbb34d19e8a60e32661360 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 24 Oct 2024 19:27:11 +0200 Subject: [PATCH 4/7] DAL/Proto: remove temporary prefixes of error titles Fixes https://gitlab.com/tezos/tezos/-/issues/7574 --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index f0775eaf581d..593b6f3edaf1 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -718,7 +718,7 @@ module History = struct module History_cache = Bounded_history_repr.Make (struct - let name = "dal_slots_cache_v2" + let name = "dal_slots_cache" end) (Pointer_hash) (struct @@ -979,7 +979,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 @@ -997,7 +997,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 @@ -1051,7 +1051,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) @@ -1063,7 +1063,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 97d5d6706a8fd0e241e10d8906fcb5e23e2d3eb7 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 24 Oct 2024 19:25:55 +0200 Subject: [PATCH 5/7] DAL/tezt: adapt kaitai to new skip list cells' content --- .../files/alpha__smart_rollup__game.ksy | 56 +++++++++++++++++++ 1 file changed, 56 insertions(+) diff --git a/client-libs/kaitai-struct-files/files/alpha__smart_rollup__game.ksy b/client-libs/kaitai-struct-files/files/alpha__smart_rollup__game.ksy index bde33b4a1bc5..dfc069ff0f67 100644 --- a/client-libs/kaitai-struct-files/files/alpha__smart_rollup__game.ksy +++ b/client-libs/kaitai-struct-files/files/alpha__smart_rollup__game.ksy @@ -74,6 +74,12 @@ types: - id: attested type: attested if: (content_tag == content_tag::attested) + - id: unpublished + type: unpublished + if: (content_tag == content_tag::unpublished) + - id: published + type: published + if: (content_tag == content_tag::published) dal_snapshot: seq: - id: dal_snapshot_tag @@ -152,6 +158,41 @@ types: type: b1be - id: payload type: b7be + public_key_hash: + seq: + - id: public_key_hash_tag + type: u1 + enum: public_key_hash_tag + - id: ed25519 + size: 20 + if: (public_key_hash_tag == public_key_hash_tag::ed25519) + - id: secp256k1 + size: 20 + if: (public_key_hash_tag == public_key_hash_tag::secp256k1) + - id: p256 + size: 20 + if: (public_key_hash_tag == public_key_hash_tag::p256) + - id: bls + size: 20 + if: (public_key_hash_tag == public_key_hash_tag::bls) + published: + seq: + - id: publisher + type: public_key_hash + doc: A Ed25519, Secp256k1, P256, or BLS public key hash + - id: is_proto_attested + type: u1 + enum: bool + - id: attested_shards + type: u2be + - id: total_shards + type: u2be + - id: published_tag + type: u1 + enum: published_tag + - id: v0 + type: v0 + if: (published_tag == published_tag::v0) refuted_stop_chunk: seq: - id: state_tag @@ -176,6 +217,12 @@ types: type: s4be - id: index type: u1 + unpublished: + seq: + - id: level + type: s4be + - id: index + type: u1 v0: seq: - id: level @@ -193,12 +240,21 @@ enums: content_tag: 0: unattested 1: attested + 2: unpublished + 3: published dal_snapshot_tag: 0: dal_skip_list_legacy 1: dal_skip_list game_state_tag: 0: dissecting 1: final_move + public_key_hash_tag: + 0: ed25519 + 1: secp256k1 + 2: p256 + 3: bls + published_tag: + 0: v0 turn_tag: 0: alice 1: bob -- GitLab From b0f25bb7a233fce9420b7af2a2c024587759002f Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 24 Oct 2024 19:25:40 +0200 Subject: [PATCH 6/7] DAL/tezt: adapt tests to new skip list cells' content --- tezt/tests/dal.ml | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/tezt/tests/dal.ml b/tezt/tests/dal.ml index fe692af7732d..1b7a181e338d 100644 --- a/tezt/tests/dal.ml +++ b/tezt/tests/dal.ml @@ -4939,18 +4939,25 @@ module History_rpcs = struct int ~error_msg:"Unexpected cell index: got %L, expected %R")) ; let cell_kind = JSON.(content |-> "kind" |> as_string) in + (* ADAL/TODO: https://gitlab.com/tezos/tezos/-/issues/7554 + + Remove the legacy cases below once migration from Q to R is done. See + issue above for more details. *) + let content_is_legacy = + cell_kind = "attested" || cell_kind = "unattested" + in let expected_kind = if cell_level <= first_level || cell_slot_index != slot_index then - "unattested" + if content_is_legacy then "unattested" else "unpublished" else ( at_least_one_attested_status := true ; - "attested") + if content_is_legacy then "attested" else "published") in Check.( (cell_kind = expected_kind) string ~error_msg:"Unexpected cell kind: got %L, expected %R") ; - (if cell_kind = "attested" then + (if cell_kind = "published" || cell_kind = "attested" then let commitment = JSON.(content |-> "commitment" |> as_string) in Check.( (commitment = commitments.(cell_level - (first_level + 1))) -- GitLab From 84ca25ddc155d3b4a82c62a2b5b2bb36fe29cd60 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Fri, 25 Oct 2024 19:49:50 +0200 Subject: [PATCH 7/7] DAL/Tezt: temporarily disable a test that needs cells migration --- tezt/tests/dal.ml | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/tezt/tests/dal.ml b/tezt/tests/dal.ml index 1b7a181e338d..b898f68cf29c 100644 --- a/tezt/tests/dal.ml +++ b/tezt/tests/dal.ml @@ -5086,7 +5086,9 @@ module History_rpcs = struct (Dal_node.string_of_skip_list_storage_backend skip_list_storage_backend) in - let tags = ["rpc"; "skip_list"; Tag.memory_3k] in + (* TODO: This test will be re-enabled in MR: + https://gitlab.com/tezos/tezos/-/merge_requests/15448 *) + let tags = ["rpc"; "skip_list"; Tag.memory_3k; Tag.ci_disabled] in let tags = if skip_list_storage_backend = Dal_node.SQLite3 then skip_list_sqlite3_tag :: tags -- GitLab