From d1ea03fac693762401c8056570fdbe2da00585de Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Mon, 5 Feb 2024 13:27:25 +0100 Subject: [PATCH 1/3] DAL/Tests: temporarily disable tests involivng skip lists --- .../lib_protocol/test/pbt/test_dal_slot_proof.ml | 6 ++++++ .../lib_protocol/test/pbt/test_sc_rollup_encoding.ml | 8 +++++++- .../lib_protocol/test/unit/test_dal_slot_proof.ml | 6 ++++++ 3 files changed, 19 insertions(+), 1 deletion(-) diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml b/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml index f0f13d6f0c0d..6b0eaf499035 100644 --- a/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml +++ b/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml @@ -31,6 +31,11 @@ Subject: Refutation proof-related functions of Dal *) +(* +TODO: https://gitlab.com/tezos/tezos/-/issues/6895 + +Adapt/re-enable tests + open Protocol module Make (Parameters : sig @@ -258,3 +263,4 @@ let () = (Protocol.name ^ ": Dal slots refutation game") Test.tests |> Lwt_main.run +*) diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml b/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml index 544f3e0a1fec..6cb575788d64 100644 --- a/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml +++ b/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml @@ -119,7 +119,12 @@ let gen_inbox level = module Index = Dal_slot_index_repr -let gen_dal_slots_history () = +let gen_dal_slots_history () = Gen.return Dal_slot_repr.History.genesis +(* +TODO: https://gitlab.com/tezos/tezos/-/issues/6895 + +Adapt/re-enable tests + let open Gen in let open Dal_slot_repr in (* Generate a list of (level * confirmed slot ID). *) @@ -155,6 +160,7 @@ let gen_dal_slots_history () = @@ Stdlib.failwith (Format.asprintf "%a" Error_monad.pp_print_trace @@ Environment.wrap_tztrace e) +*) let gen_inbox_history_proof inbox_level = let open Gen in diff --git a/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml b/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml index 097df4eaef74..0a58a7e3cc91 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml @@ -31,6 +31,11 @@ Subject: These unit tests check proof-related functions of Dal slots. *) +(* +TODO: https://gitlab.com/tezos/tezos/-/issues/6895 + +Adapt/re-enable tests + open Protocol module S = Dal_slot_repr module H = S.Header @@ -442,3 +447,4 @@ let tests = let () = Alcotest_lwt.run ~__FILE__ Protocol.name [("dal slot proof", tests)] |> Lwt_main.run +*) -- GitLab From fafd56cb332bdd223320e55e1520ba2398d5f834 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Tue, 6 Feb 2024 17:00:38 +0100 Subject: [PATCH 2/3] Proto/Dal: plug the new DAL skip list in the rest of the code --- .../files/alpha__smart_rollup__game.ksy | 56 +- .../lib_protocol/alpha_context.mli | 10 +- src/proto_alpha/lib_protocol/dal_apply.ml | 5 +- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 798 +----------------- .../lib_protocol/dal_slot_repr.mli | 63 +- .../lib_protocol/dal_slot_storage.ml | 40 +- .../lib_protocol/dal_slot_storage.mli | 8 +- .../lib_sc_rollup_node/dal_slots_tracker.ml | 8 + .../test/test_octez_conversions.ml | 64 +- ...a refutation game are slashed-rewarded.out | 4 +- 10 files changed, 241 insertions(+), 815 deletions(-) diff --git a/contrib/kaitai-struct-files/files/alpha__smart_rollup__game.ksy b/contrib/kaitai-struct-files/files/alpha__smart_rollup__game.ksy index de8c67bc55bf..b45db8af9902 100644 --- a/contrib/kaitai-struct-files/files/alpha__smart_rollup__game.ksy +++ b/contrib/kaitai-struct-files/files/alpha__smart_rollup__game.ksy @@ -13,6 +13,14 @@ types: if: (state_tag == bool::true) - id: tick type: n + attested: + seq: + - id: level + type: s4 + - id: index + type: u1 + - id: commitment + size: 48 back_pointers: seq: - id: back_pointers_entries @@ -57,20 +65,26 @@ types: type: s4 content_0: seq: - - id: level - type: s4 - - id: index + - id: content_tag type: u1 - - id: commitment - size: 48 + enum: content_tag + - id: unattested + type: unattested + if: (content_tag == content_tag::unattested) + - id: attested + type: attested + if: (content_tag == content_tag::attested) dal_snapshot: seq: - - id: index - type: n - - id: content - type: content_0 - - id: back_pointers - type: back_pointers_2 + - id: dal_snapshot_tag + type: u1 + enum: dal_snapshot_tag + - id: dal_skip_list_legacy + size: 57 + if: (dal_snapshot_tag == dal_snapshot_tag::dal_skip_list_legacy) + - id: dal_skip_list + type: skip_list + if: (dal_snapshot_tag == dal_snapshot_tag::dal_skip_list) dissecting: seq: - id: dissection @@ -148,10 +162,30 @@ types: if: (state_tag == bool::true) - id: tick type: n + skip_list: + seq: + - id: index + type: n + - id: content + type: content_0 + - id: back_pointers + type: back_pointers_2 + unattested: + seq: + - id: level + type: s4 + - id: index + type: u1 enums: bool: 0: false 255: true + content_tag: + 0: unattested + 1: attested + dal_snapshot_tag: + 0: dal_skip_list_legacy + 1: dal_skip_list game_state_tag: 0: dissecting 1: final_move diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 4d06cd4ab584..7fa209b847e6 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2841,7 +2841,7 @@ module Dal : sig val finalize_current_slot_headers : context -> context Lwt.t val finalize_pending_slot_headers : - context -> (context * Attestation.t) tzresult Lwt.t + context -> number_of_slots:int -> (context * Attestation.t) tzresult Lwt.t end module Operations : sig @@ -2886,11 +2886,17 @@ module Dal : sig Bounded_history_repr.S with type key = hash and type value = t val add_confirmed_slot_headers_no_cache : - t -> Slot.Header.t list -> t tzresult + t -> + Raw_level.t -> + number_of_slots:int -> + Slot.Header.t list -> + t tzresult val add_confirmed_slot_headers : t -> History_cache.t -> + Raw_level.t -> + number_of_slots:int -> Slot.Header.t list -> (t * History_cache.t) tzresult diff --git a/src/proto_alpha/lib_protocol/dal_apply.ml b/src/proto_alpha/lib_protocol/dal_apply.ml index 074be3f0ac7a..08113b8437aa 100644 --- a/src/proto_alpha/lib_protocol/dal_apply.ml +++ b/src/proto_alpha/lib_protocol/dal_apply.ml @@ -190,7 +190,10 @@ let finalisation ctxt = - disallow proofs involving pages of slots that have been confirmed at the level where the game started. *) - let+ ctxt, attestation = Dal.Slot.finalize_pending_slot_headers ctxt in + let number_of_slots = (Constants.parametric ctxt).dal.number_of_slots in + let+ ctxt, attestation = + Dal.Slot.finalize_pending_slot_headers ctxt ~number_of_slots + in (ctxt, Some attestation)) let compute_committee ctxt level = diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index f6a6db2cd244..af0bae750632 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -70,21 +70,6 @@ module Header = struct let equal {id; commitment} s2 = slot_id_equal id s2.id && Commitment.equal commitment s2.commitment - let compare_slot_id {published_level; index} s2 = - let c = Raw_level_repr.compare published_level s2.published_level in - if Compare.Int.(c <> 0) then c - else Dal_slot_index_repr.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 = Dal_slot_index_repr.zero; - } - - let zero = {id = zero_id; commitment = Commitment.zero} - let id_encoding = let open Data_encoding in conv @@ -229,13 +214,6 @@ module History = struct (* History is represented via a skip list. The content of the cell is the hash of a merkle proof. *) - (* A leaf of the merkle tree is a slot. *) - module Leaf = struct - type t = Header.t - - let to_bytes = Data_encoding.Binary.to_bytes_exn Header.encoding - end - module Content_prefix = struct let (_prefix : string) = "dash1" @@ -250,7 +228,6 @@ module History = struct end module Content_hash = Blake2B.Make (Base58) (Content_prefix) - module Merkle_list = Merkle_list.Make (Leaf) (Content_hash) (* Pointers of the skip lists are used to encode the content and the backpointers. *) @@ -289,711 +266,6 @@ module History = struct | _ -> None) (fun () -> Add_element_in_slots_skip_list_violates_ordering) - module Skip_list = struct - include Skip_list.Make (Skip_list_parameters) - - (** 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 next ~prev_cell ~prev_cell_ptr elt = - let open Result_syntax in - let* () = - error_when - (Compare.Int.( <= ) - (Header.compare_slot_id - elt.Header.id - (content prev_cell).Header.id) - 0) - Add_element_in_slots_skip_list_violates_ordering - in - return @@ next ~prev_cell ~prev_cell_ptr elt - - let search ~deref ~cell ~target_id = - Lwt.search ~deref ~cell ~compare:(fun slot -> - Header.compare_slot_id slot.Header.id target_id) - end - - 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 - - (* 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 history_encoding = - Skip_list.encoding Pointer_hash.encoding Header.encoding - - let equal_history : history -> history -> bool = - Skip_list.equal Pointer_hash.equal Header.equal - - let encoding = history_encoding - - 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 - Data_encoding.Binary.to_bytes_exn Header.encoding 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:Header.pp ~pp_ptr:Pointer_hash.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) - - let add_confirmed_slot_header (t, cache) slot_header = - 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 add_confirmed_slot_headers_no_cache = - let open Result_syntax in - let no_cache = History_cache.empty ~capacity:0L in - fun t slots -> - let+ cell, (_ : History_cache.t) = - List.fold_left_e add_confirmed_slot_header (t, no_cache) slots - in - cell - - (* Dal proofs section *) - - (** An inclusion proof, for a page ID, is a list of the slots' history - skip list's cells that encodes a minimal path: - - from a starting cell, which serves as a reference. It is usually called - 'snapshot' below, - - to a final cell, that is either the exact target cell in case the slot - of the page is confirmed, or a cell whose slot ID is the smallest - that directly follows the page's slot id, in case the target slot - is not confirmed. - - Using the starting cell as a trustable starting point (i.e. maintained - and provided by L1), and combined with the extra information stored in - the {!proof} type below, one can verify if a slot (and then a page of - that slot) is confirmed on L1 or not. *) - type inclusion_proof = history list - - (** (See the documentation in the mli file to understand what we want to - prove in game refutation 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; - - - [history_cache], a sufficiently large slots history cache, to navigate - back through the successive cells of the skip list. Typically, - the cache should at least contain the cell whose slot ID is [page_id.slot_id] - in case the page is confirmed, or the cell whose slot ID is immediately - after [page_id.slot_id] in case of an unconfirmed page. Indeed, - inclusion proofs encode paths through skip lists' cells where the head - is the reference/snapshot cell and the last element is the target slot - in or the nearest upper slot (w.r.t [page_id]'s slot id and to - skip list elements ordering) ; - - - [page_info], that provides the page's information (the content and - the slot membership proof) 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 { - prev_cell : history; - (** [prev_cell] is the cell of the skip list containing a - (confirmed) slot, and whose ID is the biggest (w.r.t. to skip - list elements ordering), but smaller than [page_id.slot_id]. *) - next_cell_opt : history option; - (** [next_cell_opt] is the cell that immediately follows [prev_cell] - in the skip list, if [prev_cell] is not the latest element in - the list. Otherwise, it's set to [None]. *) - next_inc_proof : inclusion_proof; - (** [inc_proof] is a (minimal) path in the skip list that proves - cells inclusion. In case, [next_cell_opt] contains some cell - 'next_cell', the head of the list is the [slots_history] - provided to produce the proof, and the last cell is - 'next_cell'. In case [next_cell_opt] is [None], the list is - empty. - - We maintain the following invariant in case the inclusion - proof is not empty: - ``` - (content next_cell).id > page_id.slot_id > (content prev_cell).id AND - hash prev_cell = back_pointer next_cell 0 AND - Some next_cell = next_cell_opt AND - head next_inc_proof = slots_history - ``` - - Said differently, `next_cell` and `prev_cell` are two consecutive - cells of the skip list whose contents' IDs surround the page's - slot ID. Moreover, the head of the list should be equal to - the initial (snapshotted) slots_history skip list. - - The case of an empty inclusion proof happens when the inputs - are such that: `page_id.slot_id > (content slots_history).id`. - The returned proof statement implies the following property in this case: - - ``` - next_cell_opt = None AND prev_cell = slots_history - ``` - *) - } - (** The case where the slot's page doesn't exist or is not - confirmed on L1. *) - - 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) - (obj4 - (req "kind" (constant "unconfirmed")) - (req "prev_cell" history_encoding) - (req "next_cell_opt" (option history_encoding)) - (req "next_inc_proof" (list history_encoding))) - (function - | Page_unconfirmed {prev_cell; next_cell_opt; next_inc_proof} -> - Some ((), prev_cell, next_cell_opt, next_inc_proof) - | _ -> None) - (fun ((), prev_cell, next_cell_opt, next_inc_proof) -> - Page_unconfirmed {prev_cell; next_cell_opt; next_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_history_opt = Format.pp_print_option 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 {prev_cell; next_cell_opt; next_inc_proof} -> - Format.fprintf - fmt - "Page_unconfirmed (prev_cell = %a | next_cell = %a | \ - prev_inc_proof:[size=%d@ | path=%a])" - pp_history - prev_cell - pp_history_opt - next_cell_opt - (List.length next_inc_proof) - pp_inclusion_proof - next_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; - } - - let produce_proof_repr dal_params page_id ~page_info ~get_history slots_hist - = - let open Lwt_result_syntax in - let Page.{slot_id; page_index = _} = page_id in - (* We search for a slot whose ID is equal to target_id. *) - let*! search_result = - Skip_list.search ~deref:get_history ~target_id:slot_id ~cell:slots_hist - in - match (page_info, 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)." - | Some (page_data, page_proof), Found target_cell -> - (* The slot to which the page is supposed to belong is found. *) - let Header.{id; commitment} = Skip_list.content target_cell in - (* We check that the slot is not the dummy slot. *) - let*? () = - error_when - Compare.Int.(Header.compare_slot_id id Header.zero.id = 0) - (dal_proof_error - "Skip_list.search returned 'Found ': No existence \ - proof should be constructed with the slot zero.") - in - let*? () = - check_page_proof dal_params page_proof page_data page_id commitment - in - let inc_proof = List.rev search_result.Skip_list.rev_path in - let*? () = - error_when - (List.is_empty inc_proof) - (dal_proof_error "The inclusion proof cannot be empty") - in - (* All checks succeeded. We return a `Page_confirmed` proof. *) - return - ( Page_confirmed {inc_proof; target_cell; page_data; page_proof}, - Some page_data ) - | None, Nearest {lower = prev_cell; upper = next_cell_opt} -> - (* There is no previously confirmed slot in the skip list whose ID - corresponds to the {published_level; slot_index} information - given in [page_id]. But, `search` returned a skip list [prev_cell] - (and possibly [next_cell_opt]) such that: - - the ID of [prev_cell]'s slot is the biggest immediately smaller than - the page's information {published_level; slot_index} - - if not equal to [None], the ID of [next_cell_opt]'s slot is the smallest - immediately bigger than the page's slot id `slot_id`. - - if [next_cell_opt] is [None] then, [prev_cell] should be equal to - the given history_proof cell. *) - let* next_inc_proof = - match search_result.Skip_list.rev_path with - | [] -> assert false (* Not reachable *) - | prev :: rev_next_inc_proof -> - let*? () = - error_unless - (equal_history prev prev_cell) - (dal_proof_error - "Internal error: search's Nearest result is \ - inconsistent.") - in - return @@ List.rev rev_next_inc_proof - in - return - (Page_unconfirmed {prev_cell; next_cell_opt; next_inc_proof}, None) - | None, Found _ -> - tzfail - @@ dal_proof_error - "The page ID's slot is confirmed, but no page content and proof \ - are provided." - | Some _, Nearest _ -> - 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; page_index = _} = page_id in - match proof with - | Page_confirmed {target_cell; page_data; page_proof; inc_proof} -> - (* If the page is supposed to be confirmed, the last cell in - [inc_proof] should store the slot of the page. *) - let Header.{id; commitment} = Skip_list.content target_cell in - let* () = - error_when - Compare.Int.(Header.compare_slot_id id Header.zero.id = 0) - (dal_proof_error - "verify_proof_repr: cannot construct a confirmation page \ - proof with 'zero' as target slot.") - in - let* () = - verify_inclusion_proof inc_proof ~src:snapshot ~dest:target_cell - in - (* 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 all checks succeed, we return the data/content of the page. *) - return_some page_data - | Page_unconfirmed {prev_cell; next_cell_opt; next_inc_proof} -> - (* The page's slot is supposed to be unconfirmed. *) - let ( < ) a b = Compare.Int.(Header.compare_slot_id a b < 0) in - (* We retrieve the last cell of the inclusion proof to be able to - call {!verify_inclusion_proof}. We also do some well-formedness on - the shape of the inclusion proof (see the case [Page_unconfirmed] - of type {!proof}). *) - let* () = - match next_cell_opt with - | None -> - let* () = - error_unless - (List.is_empty next_inc_proof) - (dal_proof_error - "verify_proof_repr: invalid next_inc_proof") - in - (* In case the inclusion proof has no elements, we check that: - - the prev_cell slot's id is smaller than the unconfirmed slot's ID - - the snapshot is equal to the [prev_cell] skip list. - - This way, and since the skip list is sorted wrt. - {!compare_slot_id}, we are sure that the skip list whose head - is [snapshot] = [prev_cell] cannot contain a slot whose ID is - [slot_id]. *) - error_unless - ((Skip_list.content prev_cell).id < slot_id - && equal_history snapshot prev_cell) - (dal_proof_error "verify_proof_repr: invalid next_inc_proof") - | Some next_cell -> - (* In case the inclusion proof has at least one element, - we check that: - - the [prev_cell] slot's id is smaller than [slot_id] - - the [next_cell] slot's id is greater than [slot_id] - - the [next_cell] cell is a direct successor of the - [prev_cell] cell. - - the [next_cell] cell is a predecessor of [snapshot] - - Since the skip list is sorted wrt. {!compare_slot_id}, and - if the call to {!verify_inclusion_proof} succeeds, we are - sure that the skip list whose head is [snapshot] cannot - contain a slot whose ID is [slot_id]. *) - let* () = - error_unless - ((Skip_list.content prev_cell).id < slot_id - && slot_id < (Skip_list.content next_cell).id - && - let prev_cell_pointer = - Skip_list.back_pointer next_cell 0 - in - match prev_cell_pointer with - | None -> false - | Some prev_ptr -> - Pointer_hash.equal prev_ptr (hash prev_cell)) - (dal_proof_error - "verify_proof_repr: invalid next_inc_proof") - in - verify_inclusion_proof - next_inc_proof - ~src:snapshot - ~dest:next_cell - in - return_none - - 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 - 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 - -module History_v2 = struct - (* History is represented via a skip list. The content of the cell - is the hash of a merkle proof. *) - - [@@@ocaml.warning "-a"] - - module Content_prefix = struct - let (_prefix : string) = "dash1" - - (* 32 *) - let b58check_prefix = "\002\224\072\094\219" (* dash1(55) *) - - let size = Some 32 - - let name = "dal_skip_list_content" - - let title = "A hash to represent the content of a cell in the skip list" - end - - module Content_hash = Blake2B.Make (Base58) (Content_prefix) - - (* Pointers of the skip lists are used to encode the content and the - backpointers. *) - module Pointer_prefix = struct - let (_prefix : string) = "dask1" - - (* 32 *) - let b58check_prefix = "\002\224\072\115\035" (* dask1(55) *) - - let size = Some 32 - - let name = "dal_skip_list_pointer" - - let title = "A hash that represents the skip list pointers" - end - - module Pointer_hash = Blake2B.Make (Base58) (Pointer_prefix) - - module Skip_list_parameters = struct - let basis = 4 - end - - type error += Add_element_in_slots_skip_list_violates_ordering_v2 - - let () = - register_error_kind - `Temporary - ~id:"Dal_slot_repr.add_element_in_slots_skip_list_violates_ordering_v2" - ~title:"Add an element in slots skip list that violates ordering v2" - ~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_v2 -> Some () - | _ -> None) - (fun () -> Add_element_in_slots_skip_list_violates_ordering_v2) - module Content = struct (** 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 @@ -1091,7 +363,7 @@ module History_v2 = struct let* () = error_unless well_ordered - Add_element_in_slots_skip_list_violates_ordering_v2 + Add_element_in_slots_skip_list_violates_ordering in return @@ next ~prev_cell ~prev_cell_ptr elt @@ -1145,10 +417,10 @@ module History_v2 = struct (fun _ -> None) (fun ((), _) -> genesis); case - ~title:"dal_skip_list_v2" + ~title:"dal_skip_list" (Tag 1) (obj2 - (req "kind" (constant "dal_skip_list_v2")) + (req "kind" (constant "dal_skip_list")) (req "skip_list" (Skip_list.encoding Pointer_hash.encoding Content.encoding))) @@ -1185,7 +457,7 @@ module History_v2 = struct module History_cache = Bounded_history_repr.Make (struct - let name = "dal_slots_cache_v2" + let name = "dal_slots_cache" end) (Pointer_hash) (struct @@ -1249,8 +521,7 @@ module History_v2 = struct 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 + | [], _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 @@ -1260,7 +531,7 @@ module History_v2 = struct mk_unattested i :: res |> ok else (* i > s.Header.id.index *) - tzfail Add_element_in_slots_skip_list_violates_ordering_v2 + tzfail Add_element_in_slots_skip_list_violates_ordering in aux all_indices attested_slot_headers @@ -1417,40 +688,40 @@ module History_v2 = struct DAL proof's encoding should be bounded *) let proof_encoding = Data_encoding.(bytes Hex) - type error += Dal_invalid_proof_serialization_v2 + type error += Dal_invalid_proof_serialization let () = register_error_kind `Permanent - ~id:"Dal_slot_repr.invalid_proof_serialization_v2" - ~title:"Dal invalid proof serialization v2" + ~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_v2 -> Some () | _ -> None) - (fun () -> Dal_invalid_proof_serialization_v2) + (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_v2 + | None -> tzfail Dal_invalid_proof_serialization | Some serialized_proof -> return serialized_proof - type error += Dal_invalid_proof_deserialization_v2 + type error += Dal_invalid_proof_deserialization let () = register_error_kind `Permanent - ~id:"Dal_slot_repr.invalid_proof_deserialization_v2" - ~title:"Dal invalid proof deserialization v2" + ~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_v2 -> Some () | _ -> None) - (fun () -> Dal_invalid_proof_deserialization_v2) + (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_v2 + | None -> tzfail Dal_invalid_proof_deserialization | Some deserialized_proof -> return deserialized_proof let pp_inclusion_proof = Format.pp_print_list pp_history @@ -1487,27 +758,27 @@ module History_v2 = struct inc_proof) type error += - | Dal_proof_error_v2 of string - | Unexpected_page_size_v2 of {expected_size : int; page_size : int} + | 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_v2" - ~title:"Dal proof error v2" + ~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_v2 e -> Some e | _ -> None) - (fun e -> Dal_proof_error_v2 e) + (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_v2" - ~title:"Unexpected page size v2" + ~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) -> @@ -1519,13 +790,13 @@ module History_v2 = struct size) (obj2 (req "expected_size" int16) (req "page_size" int16)) (function - | Unexpected_page_size_v2 {expected_size; page_size} -> + | Unexpected_page_size {expected_size; page_size} -> Some (expected_size, page_size) | _ -> None) (fun (expected_size, page_size) -> - Unexpected_page_size_v2 {expected_size; page_size}) + Unexpected_page_size {expected_size; page_size}) - let dal_proof_error reason = Dal_proof_error_v2 reason + let dal_proof_error reason = Dal_proof_error reason let proof_error reason = error @@ dal_proof_error reason @@ -1549,7 +820,7 @@ module History_v2 = struct fail_with_error_msg "Segment_index_out_of_range" | Error `Page_length_mismatch -> tzfail - @@ Unexpected_page_size_v2 + @@ Unexpected_page_size { expected_size = dal_params.page_size; page_size = Bytes.length data; @@ -1732,11 +1003,11 @@ module History_v2 = struct let* proof_repr = deserialize_proof serialized_proof in verify_proof_repr dal_params page_id snapshot proof_repr - (* TODO: will be uncommented incrementally on the next MRs *) - - (* - 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 = @@ -1748,7 +1019,6 @@ module History_v2 = struct true | _ -> false) end - *) end include V1 diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli index 14c6089761d9..0c4b0eec52ca 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli @@ -219,7 +219,20 @@ module History : sig (** Encoding of the datatype. *) val encoding : t Data_encoding.t - (** First cell of this skip list. *) + (** The genesis skip list that contains one dummy cell. This cell has + {!Raw_level_repr.root} as published level and no attested slots. Since Dal + is not necessarily activated in the genesis block (e.g. this will be the case + on mainnet), the skip list is reset at the first call to + {!add_confirmed_slot_headers} to enforce the invariant that there are no gaps + in the levels of the cells of the skip list. + + So, a skip list is initialized with this genesis cell. It's then replaced + with a growing (non-dummy) skip list as soon as a call to + {!add_confirmed_slot_headers} with a level bigger than + {!Raw_level_repr.root} is performed. This allows to activate Dal at any + level and having a contiguous skip list (w.r.t. L1 levels). This + representation allows to produce simpler proofs with a bounded history + cache. *) val genesis : t (** Returns the hash of an history. *) @@ -235,19 +248,40 @@ module History : sig module History_cache : Bounded_history_repr.S with type key = hash and type value = t - (** [add_confirmed_slots hist cache slot_headers] updates the given structure - [hist] with the list of [slot_headers]. The given [cache] is also updated to - add successive values of [cell] to it. *) + (** [add_confirmed_slots hist cache published_level ~number_of_slots + slot_headers] updates the given structure [hist] with the list of + [slot_headers]. The given [cache] is also updated to add successive values + of [cell] to it. + + + This function checks the following pre-conditions before updating the + list: + + - The given [published_level] should match all the levels of the slots in + [slot_headers], if any; + + - [published_level] is the successor the last inserted cell's level. + + - [slot_headers] is sorted in increasing order w.r.t. slots indices. + *) val add_confirmed_slot_headers : - t -> History_cache.t -> Header.t list -> (t * History_cache.t) tzresult + t -> + History_cache.t -> + Raw_level_repr.t -> + number_of_slots:int -> + Header.t list -> + (t * History_cache.t) tzresult - (** [add_confirmed_slot_headers_no_cache cell slot_headers] same as - {!add_confirmed_slot_headers}, but no cache is updated. *) - val add_confirmed_slot_headers_no_cache : t -> Header.t list -> t tzresult + (** Similiar to {!add_confirmed_slot_headers}, but no cache is provided or + updated. *) + val add_confirmed_slot_headers_no_cache : + t -> Raw_level_repr.t -> number_of_slots:int -> Header.t list -> t tzresult (** [equal a b] returns true iff a is equal to b. *) val equal : t -> t -> bool + val pp : Format.formatter -> t -> unit + (** {1 Dal slots/pages proofs} *) (** When a SCORU kernel's inputs come from the DAL, they are provided as @@ -295,6 +329,10 @@ module History : sig page's content and proof are given. It also fails if the slot is confirmed but no or bad information about the page are provided. + Note that, in case the level of the page is far in the past (the Dal skip + list was not populated yet or the slots of the associated level are not + valid anymore) should be handled by the caller. + [dal_parameters] is used when verifying that/if the page is part of the candidate slot (if any). *) @@ -326,7 +364,14 @@ module History : sig | Unexpected_page_size of {expected_size : int; page_size : int} module Internal_for_tests : sig - val content : t -> Header.t + (** 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 + + (** Returns the content of the last cell in the given skip list. *) + val content : t -> cell_content (** [proof_statement_is serialized_proof expected] will return [true] if the deserialized proof and the [expected] proof shape match and [false] diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.ml b/src/proto_alpha/lib_protocol/dal_slot_storage.ml index f1e8a0900b69..f04bc3bf354b 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_storage.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_storage.ml @@ -52,34 +52,44 @@ let get_slot_headers_history ctxt = | None -> Dal_slot_repr.History.genesis | Some slots_history -> slots_history -let update_skip_list ctxt ~confirmed_slot_headers = +let update_skip_list ctxt ~confirmed_slot_headers ~level_attested + ~number_of_slots = let open Lwt_result_syntax in let* slots_history = get_slot_headers_history ctxt in let*? slots_history = Dal_slot_repr.History.add_confirmed_slot_headers_no_cache + ~number_of_slots slots_history + level_attested confirmed_slot_headers in let*! ctxt = Storage.Dal.Slot.History.add ctxt slots_history in return ctxt -let finalize_pending_slot_headers ctxt = +let finalize_pending_slot_headers ctxt ~number_of_slots = let open Lwt_result_syntax in let {Level_repr.level = raw_level; _} = Raw_context.current_level ctxt in let Constants_parametric_repr.{dal; _} = Raw_context.constants ctxt in match Raw_level_repr.(sub raw_level dal.attestation_lag) with | None -> return (ctxt, Dal_attestation_repr.empty) - | Some level_attested -> ( + | Some level_attested -> let* seen_slots = Storage.Dal.Slot.Headers.find ctxt level_attested in - match seen_slots with - | None -> return (ctxt, Dal_attestation_repr.empty) - | Some seen_slots -> - let rev_attested_slot_headers, attestation = - compute_attested_slot_headers ctxt seen_slots - in - let attested_slot_headers = List.rev rev_attested_slot_headers in - let* ctxt = - update_skip_list ctxt ~confirmed_slot_headers:attested_slot_headers - in - let*! ctxt = Storage.Dal.Slot.Headers.remove ctxt level_attested in - return (ctxt, attestation)) + let* ctxt, attestation, confirmed_slot_headers = + match seen_slots with + | None -> return (ctxt, Dal_attestation_repr.empty, []) + | Some seen_slots -> + let rev_attested_slot_headers, attestation = + compute_attested_slot_headers ctxt seen_slots + in + let attested_slot_headers = List.rev rev_attested_slot_headers in + let*! ctxt = Storage.Dal.Slot.Headers.remove ctxt level_attested in + return (ctxt, attestation, attested_slot_headers) + in + let* ctxt = + update_skip_list + ctxt + ~confirmed_slot_headers + ~level_attested + ~number_of_slots + in + return (ctxt, attestation) diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.mli b/src/proto_alpha/lib_protocol/dal_slot_storage.mli index b1f5d7dce078..eafa34e3cc61 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_storage.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_storage.mli @@ -58,13 +58,15 @@ val find_slot_headers : context. *) val finalize_current_slot_headers : Raw_context.t -> Raw_context.t Lwt.t -(** [finalize_pending_slot_headers ctxt] finalizes pending slot headers which - are old enough (i.e. registered at level [current_level - +(** [finalize_pending_slot_headers ctxt ~number_of_slots] finalizes pending slot + headers which are old enough (i.e. registered at level [current_level - attestation_lag]). All slots marked as available are returned. All the pending slots at [current_level - attestation_lag] level are removed from the context. *) val finalize_pending_slot_headers : - Raw_context.t -> (Raw_context.t * Dal_attestation_repr.t) tzresult Lwt.t + Raw_context.t -> + number_of_slots:int -> + (Raw_context.t * Dal_attestation_repr.t) tzresult Lwt.t (** [get_slot_headers_history ctxt] returns the current value of slots_history stored in [ctxt], or Slots_history.genesis if no value is stored yet. *) diff --git a/src/proto_alpha/lib_sc_rollup_node/dal_slots_tracker.ml b/src/proto_alpha/lib_sc_rollup_node/dal_slots_tracker.ml index 1282cb8011c0..a8c1d2f8d66e 100644 --- a/src/proto_alpha/lib_sc_rollup_node/dal_slots_tracker.ml +++ b/src/proto_alpha/lib_sc_rollup_node/dal_slots_tracker.ml @@ -312,10 +312,18 @@ module Confirmed_slots_history = struct let* pred = Node_context.get_predecessor node_ctxt head in let* slots_history = slots_history_of_hash node_ctxt pred in let* slots_cache = slots_history_cache_of_hash node_ctxt pred in + let* level = + Node_context.level_of_hash + node_ctxt + confirmation_info.published_block_hash + in + let*? level = Raw_level.of_int32 level |> Environment.wrap_tzresult in let*? slots_history, slots_cache = Dal.Slots_history.add_confirmed_slot_headers + ~number_of_slots:constants.dal.number_of_slots slots_history slots_cache + level slots_to_save |> Environment.wrap_tzresult in diff --git a/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml b/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml index 80a056097578..a2c3695b9fb5 100644 --- a/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml +++ b/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml @@ -220,7 +220,12 @@ let compare_slot_header_id (s1 : Octez_smart_rollup.Dal.Slot_header.id) let c = Int32.compare s1.published_level s2.published_level in if c <> 0 then c else Int.compare s1.index s2.index -let gen_slot_headers = +let gen_slot_headers = QCheck2.Gen.return [] +(* +TODO: https://gitlab.com/tezos/tezos/-/issues/6895 + +Adapt/re-enable tests + let open QCheck2.Gen in let size = int_bound 50 in let+ l = list_size size gen_slot_header in @@ -229,16 +234,44 @@ let gen_slot_headers = (h2 : Octez_smart_rollup.Dal.Slot_header.t) -> compare_slot_header_id h1.id h2.id) l + |> fun l -> + match l with + | [] -> [] + | (h : Octez_smart_rollup.Dal.Slot_header.t) :: _ -> + let min_level = h.id.published_level in + (* smallest level *) + List.mapi + (fun i (h : Octez_smart_rollup.Dal.Slot_header.t) -> + (* patch the published level to comply with the invariants *) + let published_level = Int32.(add min_level (of_int i)) in + let h = {h with id = {h.id with published_level}} in + (published_level, [h])) + l +*) let gen_slot_history = let open Protocol.Alpha_context in let open QCheck2.Gen in - let h = Dal.Slots_history.genesis in let+ l = gen_slot_headers in let l = - List.map (Sc_rollup_proto_types.Dal.Slot_header.of_octez ~number_of_slots) l + List.map + (fun (lvl, h) -> + ( Raw_level.of_int32_exn lvl, + List.map + (Sc_rollup_proto_types.Dal.Slot_header.of_octez ~number_of_slots) + h )) + l in - Dal.Slots_history.add_confirmed_slot_headers_no_cache h l |> function + List.fold_left_e + (fun hist (published_level, attested_slots) -> + Dal.Slots_history.add_confirmed_slot_headers_no_cache + ~number_of_slots + hist + published_level + attested_slots) + Dal.Slots_history.genesis + l + |> function | Error e -> Stdlib.failwith (Format.asprintf "%a" Environment.Error_monad.pp_trace e) | Ok v -> Sc_rollup_proto_types.Dal.Slot_history.to_octez v @@ -246,13 +279,28 @@ let gen_slot_history = let gen_slot_history_cache = let open Protocol.Alpha_context in let open QCheck2.Gen in - let h = Dal.Slots_history.genesis in - let c = Dal.Slots_history.History_cache.empty ~capacity:Int64.max_int in let+ l = gen_slot_headers in + let cache = Dal.Slots_history.History_cache.empty ~capacity:Int64.max_int in let l = - List.map (Sc_rollup_proto_types.Dal.Slot_header.of_octez ~number_of_slots) l + List.map + (fun (lvl, h) -> + ( Raw_level.of_int32_exn lvl, + List.map + (Sc_rollup_proto_types.Dal.Slot_header.of_octez ~number_of_slots) + h )) + l in - Dal.Slots_history.add_confirmed_slot_headers h c l |> function + List.fold_left_e + (fun (hist, cache) (published_level, attested_slots) -> + Dal.Slots_history.add_confirmed_slot_headers + ~number_of_slots + hist + cache + published_level + attested_slots) + (Dal.Slots_history.genesis, cache) + l + |> function | Error e -> Stdlib.failwith (Format.asprintf "%a" Environment.Error_monad.pp_trace e) | Ok (_, c) -> Sc_rollup_proto_types.Dal.Slot_history_cache.to_octez c diff --git a/tezt/tests/expected/sc_rollup.ml/Alpha- arith - participant of a refutation game are slashed-rewarded.out b/tezt/tests/expected/sc_rollup.ml/Alpha- arith - participant of a refutation game are slashed-rewarded.out index 438bdbb6e684..dd1dc9010ea4 100644 --- a/tezt/tests/expected/sc_rollup.ml/Alpha- arith - participant of a refutation game are slashed-rewarded.out +++ b/tezt/tests/expected/sc_rollup.ml/Alpha- arith - participant of a refutation game are slashed-rewarded.out @@ -108,7 +108,7 @@ This sequence of operations was run: ./octez-client --wait none timeout dispute on smart rollup '[SMART_ROLLUP_HASH]' with '[PUBLIC_KEY_HASH]' against '[PUBLIC_KEY_HASH]' from bootstrap1 Node is bootstrapped. -Estimated gas: 3715.525 units (will add 100 for safety) +Estimated gas: 3715.433 units (will add 100 for safety) Estimated storage: no bytes added Operation successfully injected in the node. Operation hash is '[OPERATION_HASH]' @@ -131,7 +131,7 @@ This sequence of operations was run: First staker (Alice): [PUBLIC_KEY_HASH] Second staker (Bob): [PUBLIC_KEY_HASH] This smart rollup refutation timeout was successfully applied - Consumed gas: 3715.459 + Consumed gas: 3715.367 Refutation game status: Game ended: [PUBLIC_KEY_HASH] lost because: timeout Balance updates: Frozen_bonds([PUBLIC_KEY_HASH],[SMART_ROLLUP_HASH]) ... -ęś©10000 -- GitLab From 1c01acde0e91331b3030fd330f3df6a48862dcd3 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 8 Feb 2024 13:52:26 +0100 Subject: [PATCH 3/3] Proto/Dal: check that add_confirmed_slot_headers takes slots of same level --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index af0bae750632..adc528fa144a 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -542,6 +542,15 @@ module History = struct let add_confirmed_slot_headers (t : t) cache published_level ~number_of_slots attested_slot_headers = let open Result_syntax in + let* () = + List.iter_e + (fun slot_header -> + error_unless + Raw_level_repr.( + published_level = slot_header.Header.id.published_level) + Add_element_in_slots_skip_list_violates_ordering) + attested_slot_headers + in let* slot_headers = fill_slot_headers ~number_of_slots -- GitLab