From 82c813808e0a6c8ef568b066cf11e27e70c26d82 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 7 Sep 2022 17:48:16 +0200 Subject: [PATCH 1/3] Proto/Dal: add the notion of slot's page --- src/proto_alpha/lib_protocol/alpha_context.ml | 4 ++ .../lib_protocol/alpha_context.mli | 24 ++++++++++ src/proto_alpha/lib_protocol/dal_slot_repr.ml | 46 +++++++++++++++++++ .../lib_protocol/dal_slot_repr.mli | 35 ++++++++++++++ 4 files changed, 109 insertions(+) diff --git a/src/proto_alpha/lib_protocol/alpha_context.ml b/src/proto_alpha/lib_protocol/alpha_context.ml index b35c7c7e6b0a..e68f131f46a4 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.ml +++ b/src/proto_alpha/lib_protocol/alpha_context.ml @@ -105,6 +105,10 @@ module Dal = struct include Raw_context.Dal end + module Page = struct + include Dal_slot_repr.Page + end + module Slot = struct include Dal_slot_repr include Dal_slot_storage diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 49237ff8ca15..f4c3b75f106f 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2772,6 +2772,30 @@ module Dal : sig val record_available_shards : context -> t -> int list -> context end + module Page : sig + type content = bytes + + module Index : sig + type t = int + + val encoding : int Data_encoding.t + + val pp : Format.formatter -> int -> unit + + val compare : int -> int -> int + + val equal : int -> int -> bool + end + + type t = {slot_index : Slot_index.t; page_index : Index.t} + + val encoding : t Data_encoding.t + + val pp : Format.formatter -> t -> unit + + val equal : t -> t -> bool + end + (** This module re-exports definitions from {!Dal_slot_repr}, {!Dal_slot_storage} and {!Raw_context.Dal}. *) module Slot : sig diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 252986e9be93..3f190f1578c9 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -69,11 +69,57 @@ type t = {level : Raw_level_repr.t; index : Index.t; header : header} type slot = t +type slot_index = Index.t + let equal ({level; index; header} : t) s2 = Raw_level_repr.equal level s2.level && Index.equal index s2.index && Header.equal header s2.header +module Slot_index = Index + +module Page = struct + type content = Bytes.t + + module Index = struct + type t = int + + let zero = 0 + + let encoding = Data_encoding.int16 + + let pp = Format.pp_print_int + + let compare = Compare.Int.compare + + let equal = Compare.Int.equal + end + + type t = {slot_index : Slot_index.t; page_index : Index.t} + + let encoding = + let open Data_encoding in + conv + (fun {slot_index; page_index} -> (slot_index, page_index)) + (fun (slot_index, page_index) -> {slot_index; page_index}) + (obj2 + (req "slot_index" Slot_index.encoding) + (req "page_index" Index.encoding)) + + let equal page page' = + Slot_index.equal page.slot_index page'.slot_index + && Index.equal page.page_index page'.page_index + + let pp fmt {slot_index; page_index} = + Format.fprintf + fmt + "(slot_index: %a, page_index: %a)" + Slot_index.pp + slot_index + Index.pp + page_index +end + let encoding = let open Data_encoding in conv diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli index 6ea6004d57e6..af6f3479ed8b 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli @@ -92,6 +92,40 @@ type slot = t val equal : t -> t -> bool +type slot_index = Index.t + +(** A DAL slot is decomposed to a successive list of pages with fixed content + size. The size is chosen so that it's possible to inject a page in a Tezos + L1 operation if needed during the proof phase of a refutation game. +*) +module Page : sig + type content = Bytes.t + + module Index : sig + type t = int + + val zero : int + + val encoding : int Data_encoding.t + + val pp : Format.formatter -> int -> unit + + val compare : int -> int -> int + + val equal : int -> int -> bool + end + + (** A page is identified by its slots index and by its own index in the list + of pages of the slot. *) + type t = {slot_index : slot_index; page_index : Index.t} + + val equal : t -> t -> bool + + val encoding : t Data_encoding.t + + val pp : Format.formatter -> t -> unit +end + (** The encoding ensures the slot is always a non-negative number. *) val encoding : t Data_encoding.t @@ -128,3 +162,4 @@ module Slot_market : sig (** [candidates t] returns a list of slot candidates. *) val candidates : t -> slot list end + -- GitLab From 6bf4991cb5e13784af6921ede4fe21007e5195d9 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 8 Sep 2022 11:40:24 +0200 Subject: [PATCH 2/3] Proto/Dal: add a skip list pointer in storage for attested slots --- src/proto_alpha/lib_protocol/alpha_context.ml | 2 + .../lib_protocol/alpha_context.mli | 10 ++ src/proto_alpha/lib_protocol/dal_slot_repr.ml | 93 +++++++++++++++++++ .../lib_protocol/dal_slot_repr.mli | 18 ++++ .../lib_protocol/dal_slot_storage.ml | 41 +++++--- .../lib_protocol/dal_slot_storage.mli | 5 + src/proto_alpha/lib_protocol/storage.ml | 14 +++ src/proto_alpha/lib_protocol/storage.mli | 7 ++ tezt/tests/dal.ml | 19 +++- 9 files changed, 191 insertions(+), 18 deletions(-) diff --git a/src/proto_alpha/lib_protocol/alpha_context.ml b/src/proto_alpha/lib_protocol/alpha_context.ml index e68f131f46a4..28f16f6e67b7 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.ml +++ b/src/proto_alpha/lib_protocol/alpha_context.ml @@ -114,6 +114,8 @@ module Dal = struct include Dal_slot_storage include Raw_context.Dal end + + module Slots_history = Dal_slot_repr.Slots_history end module Dal_errors = Dal_errors_repr diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index f4c3b75f106f..a17ea7ca716c 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2820,6 +2820,16 @@ module Dal : sig val finalize_pending_slots : context -> (context * Endorsement.t) tzresult Lwt.t end + + module Slots_history : sig + type t + + (* FIXME/DAL: https://gitlab.com/tezos/tezos/-/issues/3766 + Do we need to export this? *) + val genesis : t + + val equal : t -> t -> bool + end end (** This module re-exports definitions from {!Dal_errors_repr}. *) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 3f190f1578c9..4a8e070b8b01 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -177,3 +177,96 @@ module Slot_market = struct let candidates t = t.slots |> Slot_index_map.to_seq |> Seq.map snd |> List.of_seq end + +module Slots_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 = slot + + let to_bytes = Data_encoding.Binary.to_bytes_exn encoding + end + + module Content_prefix = struct + let _prefix = "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) + module Merkle_list = Merkle_list.Make (Leaf) (Content_hash) + + (* Pointers of the skip lists are used to encode the content and the + backpointers. *) + module Pointer_prefix = struct + let _prefix = "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 = 2 + end + + module Skip_list = Skip_list_repr.Make (Skip_list_parameters) + + module V1 = struct + (* The content of a cell is the hash of all the slot headers + 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 = slot + + (* A pointer to a cell is the hash of its content and all the back + pointers. *) + type ptr = Pointer_hash.t + + type t = (content, ptr) Skip_list.cell option + + let slot_encoding = encoding + + let encoding = + Skip_list.encoding Pointer_hash.encoding encoding |> Data_encoding.option + + let genesis : t = None + + let hash_skip_list_cell 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 slot_encoding current_slot + :: List.map Pointer_hash.to_bytes back_pointers_hashes + |> Pointer_hash.hash_bytes + + let add_confirmed_slot t slot = + match t with + | None -> Some (Skip_list.genesis slot) + | Some t -> + let content = slot in + let prev_cell_ptr = hash_skip_list_cell t in + Skip_list.next ~prev_cell:t ~prev_cell_ptr content |> Option.some + + let add_confirmed_slots t slots = List.fold_left add_confirmed_slot t slots + + let equal = Option.equal @@ Skip_list.equal Pointer_hash.equal equal + end + + include V1 +end diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli index af6f3479ed8b..28a2f0ea488c 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli @@ -163,3 +163,21 @@ module Slot_market : sig val candidates : t -> slot list end +module Slots_history : sig + (** Abstract representation of a skip list specialized for + confirmed slot headers. *) + type t + + (** Encoding of the datatype. *) + val encoding : t Data_encoding.t + + (** First cell of this skip list. *) + val genesis : t + + (** [add_confirmed_slots cell slots] updates the given structure + [cell] with the list of [slots]. *) + val add_confirmed_slots : t -> slot list -> t + + (** [equal a b] returns true iff a is equal to b. *) + val equal : t -> t -> bool +end diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.ml b/src/proto_alpha/lib_protocol/dal_slot_storage.ml index e2883ffd8be2..937d2d6359a2 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_storage.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_storage.ml @@ -32,27 +32,42 @@ let finalize_current_slots ctxt = | [] -> Lwt.return ctxt | _ :: _ -> Storage.Dal.Slot_headers.add ctxt current_level.level slots -let compute_available_slots ctxt slots = - let fold_available_slots available_slots slot = +let compute_available_slots ctxt seen_slots = + let fold_available_slots (rev_slots, available_slots) slot = if Raw_context.Dal.is_slot_available ctxt slot.Dal_slot_repr.index then - Dal_endorsement_repr.commit available_slots slot.Dal_slot_repr.index - else available_slots + ( slot :: rev_slots, + Dal_endorsement_repr.commit available_slots slot.Dal_slot_repr.index ) + else (rev_slots, available_slots) in - List.fold_left fold_available_slots Dal_endorsement_repr.empty slots + List.fold_left + fold_available_slots + ([], Dal_endorsement_repr.empty) + seen_slots + +let get_slots_history ctxt = + Storage.Dal.Slots_history.find ctxt >|=? function + | None -> Dal_slot_repr.Slots_history.genesis + | Some slots_history -> slots_history + +let update_skip_list ctxt ~confirmed_slots = + get_slots_history ctxt >>=? fun slots_history -> + Dal_slot_repr.Slots_history.add_confirmed_slots slots_history confirmed_slots + |> Storage.Dal.Slots_history.add ctxt + >>= fun ctxt -> return ctxt let finalize_pending_slots ctxt = - let current_level = Raw_context.current_level ctxt 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 current_level.level dal.endorsement_lag) with + match Raw_level_repr.(sub raw_level dal.endorsement_lag) with | None -> return (ctxt, Dal_endorsement_repr.empty) | Some level_endorsed -> ( Storage.Dal.Slot_headers.find ctxt level_endorsed >>=? function | None -> return (ctxt, Dal_endorsement_repr.empty) - | Some slots -> - let available_slots = compute_available_slots ctxt slots in - (* DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3112 - - At this point, available slots can be integrated into - SCORU inboxes *) + | Some seen_slots -> + let rev_confirmed_slots, available_slots = + compute_available_slots ctxt seen_slots + in + let confirmed_slots = List.rev rev_confirmed_slots in + update_skip_list ctxt ~confirmed_slots >>=? fun ctxt -> Storage.Dal.Slot_headers.remove ctxt level_endorsed >>= fun ctxt -> return (ctxt, available_slots)) diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.mli b/src/proto_alpha/lib_protocol/dal_slot_storage.mli index fd38008a4e3b..3c6c1fb7edde 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_storage.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_storage.mli @@ -63,3 +63,8 @@ val finalize_current_slots : Raw_context.t -> Raw_context.t Lwt.t [current_level - lag] level are removed from the context. *) val finalize_pending_slots : Raw_context.t -> (Raw_context.t * Dal_endorsement_repr.t) tzresult Lwt.t + +(** [get_slots_history ctxt] returns the current value of slots_history stored + in [ctxt], or Slots_history.genesis if no value is stored yet. *) +val get_slots_history : + Raw_context.t -> Dal_slot_repr.Slots_history.t tzresult Lwt.t diff --git a/src/proto_alpha/lib_protocol/storage.ml b/src/proto_alpha/lib_protocol/storage.ml index 97151f463c95..0ed27eb90751 100644 --- a/src/proto_alpha/lib_protocol/storage.ml +++ b/src/proto_alpha/lib_protocol/storage.ml @@ -1958,6 +1958,9 @@ module Dal = struct This is only for prototyping. Probably something smarter would be to index each header directly. *) + (* DAL/FIXME: https://gitlab.com/tezos/tezos/-/issues/3684 + + This storage should be carbonated. *) module Slot_headers = Level_context.Make_map (Registered) @@ -1969,6 +1972,17 @@ module Dal = struct let encoding = Data_encoding.(list Dal_slot_repr.encoding) end) + + module Slots_history = + Make_single_data_storage (Registered) (Raw_context) + (struct + let name = ["slots_history"] + end) + (struct + type t = Dal_slot_repr.Slots_history.t + + let encoding = Dal_slot_repr.Slots_history.encoding + end) end module Zk_rollup = struct diff --git a/src/proto_alpha/lib_protocol/storage.mli b/src/proto_alpha/lib_protocol/storage.mli index f8362f85abc1..afb9deace229 100644 --- a/src/proto_alpha/lib_protocol/storage.mli +++ b/src/proto_alpha/lib_protocol/storage.mli @@ -888,11 +888,18 @@ module Sc_rollup : sig end module Dal : sig + (** This is a temporary storage for slot header proposed onto the L1. *) module Slot_headers : Non_iterable_indexed_data_storage with type t = Raw_context.t and type key = Raw_level_repr.t and type value = Dal_slot_repr.slot list + + (** This is a permanent storage for slot header confirmed by the L1. *) + module Slots_history : + Single_data_storage + with type t := Raw_context.t + and type value = Dal_slot_repr.Slots_history.t end module Zk_rollup : sig diff --git a/tezt/tests/dal.ml b/tezt/tests/dal.ml index 8a1d86495b41..ac3fb9d6f89c 100644 --- a/tezt/tests/dal.ml +++ b/tezt/tests/dal.ml @@ -381,11 +381,20 @@ let test_slot_management_logic = bool ~error_msg:"Expected slot 1 to be available") ; let* bytes = RPC_legacy.raw_bytes client in - if not JSON.(bytes |-> "dal" |> is_null) then - Test.fail - "Expected the context to contain no more information about the DAL \ - anymore." ; - unit + let dal_keys = ["slots_history"] in + match JSON.(bytes |-> "dal" |> as_object_opt) with + | None -> + Test.fail + "Expected the context to contain information about the DAL (%a)." + Format.(pp_print_list (fun fmt -> fprintf fmt "%s")) + dal_keys + | Some l -> + List.iter + (fun (k, _) -> + if not @@ List.mem k dal_keys then + Test.fail "Unexpected entry %s in context/DAL" k) + l ; + unit (* Tests for integration between Dal and Scoru *) let rollup_node_subscribes_to_dal_slots _protocol sc_rollup_node -- GitLab From 84365089868eae0a8287ade6f7172f01d28c7bc8 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Thu, 8 Sep 2022 14:35:02 +0200 Subject: [PATCH 3/3] Proto/DAL: Prefix level field with published_ in slot for readability --- src/proto_alpha/lib_protocol/alpha_context.mli | 6 +++++- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 16 ++++++++-------- src/proto_alpha/lib_protocol/dal_slot_repr.mli | 5 ++++- .../test/helpers/operation_generator.ml | 4 ++-- .../validate/manager_operation_helpers.ml | 4 ++-- 5 files changed, 21 insertions(+), 14 deletions(-) diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index a17ea7ca716c..6b6009cc14fc 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2801,7 +2801,11 @@ module Dal : sig module Slot : sig type header = Dal.commitment - type t = {level : Raw_level.t; index : Slot_index.t; header : header} + type t = { + published_level : Raw_level.t; + index : Slot_index.t; + header : header; + } val zero : header diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index 4a8e070b8b01..d21abd25886b 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -65,14 +65,14 @@ type header = Header.t let zero = Dal.Commitment.zero -type t = {level : Raw_level_repr.t; index : Index.t; header : header} +type t = {published_level : Raw_level_repr.t; index : Index.t; header : header} type slot = t type slot_index = Index.t -let equal ({level; index; header} : t) s2 = - Raw_level_repr.equal level s2.level +let equal ({published_level; index; header} : t) s2 = + Raw_level_repr.equal published_level s2.published_level && Index.equal index s2.index && Header.equal header s2.header @@ -123,19 +123,19 @@ end let encoding = let open Data_encoding in conv - (fun {level; index; header} -> (level, index, header)) - (fun (level, index, header) -> {level; index; header}) + (fun {published_level; index; header} -> (published_level, index, header)) + (fun (published_level, index, header) -> {published_level; index; header}) (obj3 (req "level" Raw_level_repr.encoding) (req "index" Data_encoding.uint8) (req "header" Header.encoding)) -let pp fmt {level; index; header} = +let pp fmt {published_level; index; header} = Format.fprintf fmt - "level: %a index: %a header: %a" + "published_level: %a index: %a header: %a" Raw_level_repr.pp - level + published_level Format.pp_print_int index Header.pp diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli index 28a2f0ea488c..9c483bc8ddbe 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli @@ -86,7 +86,10 @@ end type header = Header.t -type t = {level : Raw_level_repr.t; index : Index.t; header : header} +(** For Layer-1, a slot is described by the level at which it is published, + the slot's index (in the list of slots), and the slot's header + (KATE commitment hash). *) +type t = {published_level : Raw_level_repr.t; index : Index.t; header : header} type slot = t diff --git a/src/proto_alpha/lib_protocol/test/helpers/operation_generator.ml b/src/proto_alpha/lib_protocol/test/helpers/operation_generator.ml index da3b7a29a3e3..d645e1bdb48c 100644 --- a/src/proto_alpha/lib_protocol/test/helpers/operation_generator.ml +++ b/src/proto_alpha/lib_protocol/test/helpers/operation_generator.ml @@ -652,10 +652,10 @@ let generate_transfer_ticket random_state : let generate_dal_publish_slot_header random_state : Kind.dal_publish_slot_header Kind.manager Operation.t = let gen_dal_publish _ = - let level = Alpha_context.Raw_level.of_int32_exn Int32.zero in + let published_level = Alpha_context.Raw_level.of_int32_exn Int32.zero in let index = Alpha_context.Dal.Slot_index.zero in let header = Alpha_context.Dal.Slot.zero in - let slot = Alpha_context.Dal.Slot.{level; index; header} in + let slot = Alpha_context.Dal.Slot.{published_level; index; header} in Dal_publish_slot_header {slot} in generate_manager random_state gen_dal_publish diff --git a/src/proto_alpha/lib_protocol/test/integration/validate/manager_operation_helpers.ml b/src/proto_alpha/lib_protocol/test/integration/validate/manager_operation_helpers.ml index 92f448bbdcbe..c1bd639da1e3 100644 --- a/src/proto_alpha/lib_protocol/test/integration/validate/manager_operation_helpers.ml +++ b/src/proto_alpha/lib_protocol/test/integration/validate/manager_operation_helpers.ml @@ -1026,10 +1026,10 @@ let mk_sc_rollup_return_bond (oinfos : operation_req) (infos : infos) = sc_rollup let mk_dal_publish_slot_header (oinfos : operation_req) (infos : infos) = - let level = Alpha_context.Raw_level.of_int32_exn Int32.zero in + let published_level = Alpha_context.Raw_level.of_int32_exn Int32.zero in let index = Alpha_context.Dal.Slot_index.zero in let header = Alpha_context.Dal.Slot.zero in - let slot = Alpha_context.Dal.Slot.{level; index; header} in + let slot = Alpha_context.Dal.Slot.{published_level; index; header} in Op.dal_publish_slot_header ?fee:oinfos.fee ?gas_limit:oinfos.gas_limit -- GitLab