From 6bf9c4e63c87a3e1d967b2e6a90775935a7e6a31 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 16 Oct 2024 14:43:50 +0200 Subject: [PATCH 1/6] Dal/Proto: add a storage entry of the successive cells of the skip list of a level --- src/proto_alpha/lib_protocol/storage.ml | 19 +++++++++++++++++++ src/proto_alpha/lib_protocol/storage.mli | 23 +++++++++++++++++++++++ 2 files changed, 42 insertions(+) diff --git a/src/proto_alpha/lib_protocol/storage.ml b/src/proto_alpha/lib_protocol/storage.ml index 1beea88cb703..ef1e8648fed2 100644 --- a/src/proto_alpha/lib_protocol/storage.ml +++ b/src/proto_alpha/lib_protocol/storage.ml @@ -2193,6 +2193,25 @@ module Dal = struct let encoding = Dal_slot_repr.History.encoding end) + + module LevelHistories = + Make_single_data_storage (Registered) (Raw_context) + (struct + let name = ["slot_headers_successive_histories_of_level"] + end) + (struct + type t = + (Dal_slot_repr.History.Pointer_hash.t * Dal_slot_repr.History.t) + list + + let encoding = + let open Data_encoding in + let module H = Dal_slot_repr.History in + list + (obj2 + (req "cell_hash" H.Pointer_hash.encoding) + (req "cell" H.encoding)) + end) end end diff --git a/src/proto_alpha/lib_protocol/storage.mli b/src/proto_alpha/lib_protocol/storage.mli index f48967588c42..9250bbf2c8ed 100644 --- a/src/proto_alpha/lib_protocol/storage.mli +++ b/src/proto_alpha/lib_protocol/storage.mli @@ -1022,6 +1022,29 @@ module Dal : sig Single_data_storage with type t := Raw_context.t and type value = Dal_slot_repr.History.t + + (** This single entry stores the cells of the DAL skip list constructed + during the block under validation. The list is expected to have exactly + [number_of_slots] elements. Its cells ordering is not specified (and not + relevant). A cell's binary encoding is bounded (the only part that is + evolving in size over time is the number of backpointers, which is + bounded by 64). *) + module LevelHistories : + Single_data_storage + with type t := Raw_context.t + and type value = + (* We sometimes need to access all the cells at once (e.g. if we want + to index them, like it'd currently done by the DAL node). In some + other situations, we may want to only access a specific cell, given + its published level and the index of the corresponding DAL slot. + + We could index the list as an irmin sub-tree for this second usage, + but this would require some extra work to access the slot id and to + populate the sub-tree. For the moment, it's sufficient and more + convenient to have a "small" list of elements of the form (hash, + cell) and search inside it when needed (e.g. to know if a slot is + attested or to access its attestation ratio). *) + (Dal_slot_repr.History.Pointer_hash.t * Dal_slot_repr.History.t) list end end -- GitLab From 79d1868f3a4166899b10a61d55af32db0de8542b Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 16 Oct 2024 14:54:52 +0200 Subject: [PATCH 2/6] Dal/Proto: remember the cells of the DAL skip list at each level in the context --- src/proto_alpha/lib_protocol/dal_slot_storage.ml | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.ml b/src/proto_alpha/lib_protocol/dal_slot_storage.ml index 944056b4f2b3..6171670f2582 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_storage.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_storage.ml @@ -57,15 +57,27 @@ let get_slot_headers_history ctxt = let update_skip_list ctxt ~confirmed_slot_headers ~level_attested ~number_of_slots = let open Lwt_result_syntax in + let open Dal_slot_repr.History in let* slots_history = get_slot_headers_history ctxt in - let*? slots_history = - Dal_slot_repr.History.add_confirmed_slot_headers_no_cache + let*? slots_history, cache = + (* DAL/FIXME: https://gitlab.com/tezos/tezos/-/issues/7126 + + Handle DAL parameters (number_of_slots) evolution. + *) + (* We expect to put exactly [number_of_slots] cells in the cache. *) + let cache = History_cache.empty ~capacity:(Int64.of_int number_of_slots) in + add_confirmed_slot_headers ~number_of_slots slots_history + cache level_attested confirmed_slot_headers in let*! ctxt = Storage.Dal.Slot.History.add ctxt slots_history in + let*! ctxt = + History_cache.(view cache |> Map.bindings) + |> Storage.Dal.Slot.LevelHistories.add ctxt + in return ctxt let finalize_pending_slot_headers ctxt ~number_of_slots = -- GitLab From ea942976eced31779d79e472baabc4864bb8a5f5 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 16 Oct 2024 15:25:12 +0200 Subject: [PATCH 3/6] Dal/Proto: expose the function find_level_histories in alpha_context --- src/proto_alpha/lib_protocol/alpha_context.mli | 5 +++++ src/proto_alpha/lib_protocol/dal_slot_storage.ml | 2 ++ src/proto_alpha/lib_protocol/dal_slot_storage.mli | 10 ++++++++++ 3 files changed, 17 insertions(+) diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index e8c1e5bbce67..d0ab59bc6560 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2939,6 +2939,11 @@ module Dal : sig module Slots_storage : sig val get_slot_headers_history : context -> Slots_history.t tzresult Lwt.t + + val find_level_histories : + context -> + (Slots_history.Pointer_hash.t * Slots_history.t) list option tzresult + Lwt.t end end diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.ml b/src/proto_alpha/lib_protocol/dal_slot_storage.ml index 6171670f2582..6245a97db954 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_storage.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_storage.ml @@ -25,6 +25,8 @@ let find_slot_headers ctxt level = Storage.Dal.Slot.Headers.find ctxt level +let find_level_histories ctxt = Storage.Dal.Slot.LevelHistories.find ctxt + let finalize_current_slot_headers ctxt = Storage.Dal.Slot.Headers.add ctxt diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.mli b/src/proto_alpha/lib_protocol/dal_slot_storage.mli index 4dc2d270fca3..792b69997e05 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_storage.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_storage.mli @@ -53,6 +53,16 @@ val find_slot_headers : Raw_level_repr.t -> Dal_slot_repr.Header.t list option tzresult Lwt.t +(** [find_level_histories ctxt] returns the cells of the DAL skip list produced + at the current level alongside their hashes. Returns [None] if no entry is + present in the storage (yet). The function fails if the reading from the + context fails. *) +val find_level_histories : + Raw_context.t -> + (Dal_slot_repr.History.Pointer_hash.t * Dal_slot_repr.History.t) list option + tzresult + Lwt.t + (** [finalize_current_slot_headers ctxt] finalizes the current slot headers posted on this block and marks them as pending into the context. *) -- GitLab From 0cf5298c5234956a2198da789c3f8009fba7d864 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 16 Oct 2024 15:35:56 +0200 Subject: [PATCH 4/6] Dal/plugin: add an RPC to fetch the skip list cells produced during a level --- src/proto_alpha/lib_plugin/RPC.ml | 32 ++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-) diff --git a/src/proto_alpha/lib_plugin/RPC.ml b/src/proto_alpha/lib_plugin/RPC.ml index b3a2351cad7e..56a610eef18e 100644 --- a/src/proto_alpha/lib_plugin/RPC.ml +++ b/src/proto_alpha/lib_plugin/RPC.ml @@ -3043,6 +3043,25 @@ module Dal = struct ~query:level_query ~output RPC_path.(path / "published_slot_headers") + + let skip_list_cells_of_level = + let output = + Data_encoding.( + list + (tup2 + Dal.Slots_history.Pointer_hash.encoding + Dal.Slots_history.encoding)) + in + RPC_service.get_service + ~description: + "Returns the cells of the DAL skip list constructed during this \ + targeted block and stored in the context. The cells ordering in the \ + list is not specified (not relevant). The list is expected to be \ + empty if the entry is not initialized in the context (yet), or to \ + have a size that coincides with the number of DAL slots otherwise." + ~query:RPC_query.empty + ~output + RPC_path.(path / "skip_list_cells_of_level") end let register_dal_commitments_history () = @@ -3088,6 +3107,9 @@ module Dal = struct let dal_published_slot_headers ctxt block ?level () = RPC_context.make_call0 S.published_slot_headers ctxt block level () + let skip_list_cells_of_level ctxt block () = + RPC_context.make_call0 S.skip_list_cells_of_level ctxt block () () + let register_published_slot_headers () = let open Lwt_result_syntax in Registration.register0 ~chunked:true S.published_slot_headers @@ -3100,10 +3122,18 @@ module Dal = struct Environment.Error_monad.tzfail @@ Published_slot_headers_not_initialized level + let register_skip_list_cells_of_level () = + let open Lwt_result_syntax in + Registration.register0 ~chunked:true S.skip_list_cells_of_level + @@ fun ctxt () () -> + let* result = Dal.Slots_storage.find_level_histories ctxt in + match result with Some l -> return l | None -> return [] + let register () = register_dal_commitments_history () ; register_shards () ; - register_published_slot_headers () + register_published_slot_headers () ; + register_skip_list_cells_of_level () end module Forge = struct -- GitLab From 2c70402251fb510578e3592bd00abd5891da2355 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 16 Oct 2024 17:37:23 +0200 Subject: [PATCH 5/6] DAL/Proto-lib: partly implement indexing using the skip list cells stored in the context --- .../lib_dal/dal_plugin_registration.ml | 136 +++--------------- 1 file changed, 18 insertions(+), 118 deletions(-) diff --git a/src/proto_alpha/lib_dal/dal_plugin_registration.ml b/src/proto_alpha/lib_dal/dal_plugin_registration.ml index 5ecadaaae6b6..6a22f2c84a53 100644 --- a/src/proto_alpha/lib_dal/dal_plugin_registration.ml +++ b/src/proto_alpha/lib_dal/dal_plugin_registration.ml @@ -155,26 +155,23 @@ module Plugin = struct let cell_hash = Dal.Slots_history.hash - (* - This function mimics what the protocol does in - {!Dal_slot_storage.finalize_pending_slot_headers}. Given a block_info at - some level L, an RPC context, the DAL constants for level L, and for level - L - attestation_lag - 1, the this function computes the cells produced by the - DAL skip list during the level L using: + (* This function returns the list of cells of the DAL skip list constructed + at the level of the block whose info are given. For that, it calls the + {!Plugin.RPC.Dal.skip_list_cells_of_level} RPC that directly retrieves + the list of cells from the L1 context. In case the entry in the context + is not initialized yet, the empty list is returned. + + Compared to the old implementation in {!cells_of_level_legacy}, this + version is much simpler as it doesn't redo the computations. On the + contrary, the legacy version accesses published DAL commitments and the + attestation bitset in the block's metadata, and then reconstructs the + cells of the skip list by calling the appropriate DAL function in the + protocol. *) - - The information telling which slot headers were waiting for attestation - at level [L - attestation_lag]; - - - The bitset of attested slots at level [L] in the block's metadata. - - It is assumed that at level L the DAL is enabled. - - The ordering of the elements in the returned list is not relevant. - *) let cells_of_level (block_info : block_info) ctxt ~dal_constants - ~pred_publication_level_dal_constants = + ~pred_publication_level_dal_constants:_ = let open Lwt_result_syntax in - (* 0. Let's call [attested_level] the block's level. *) + let cpctxt = new Protocol_client_context.wrap_rpc_context ctxt in let attested_level = block_info.header.shell.level in let published_level = Int32.sub @@ -184,107 +181,10 @@ module Plugin = struct (* 1. There are no cells for [published_level = 0]. *) if published_level <= 0l then return [] else - let* feature_enable, prev_number_of_slots = - if published_level = 1l then - (* For this level, cannot retrieve the constants (as [pred - publication_level = 0]), but dummy values will suffice. *) - return (false, 0) - else - let* prev_constants = - Lazy.force pred_publication_level_dal_constants - in - return - ( prev_constants.Dal_plugin.feature_enable, - prev_constants.number_of_slots ) - in - let cpctxt = new Protocol_client_context.wrap_rpc_context ctxt in - (* 2. We retrieve the last cell of the DAL skip list from the context, - if any. It's the one stored in the context at [attested_level - - 1]. If no cell is stored yet, we return the genesis cell. *) - let* previous_cell = - let* previous_cell_opt = - (* Should not be negative as [attestation_lag > 0]. *) - let prev_level = Int32.pred attested_level in - Plugin.RPC.Dal.dal_commitments_history - cpctxt - (`Main, `Level prev_level) - in - return - @@ Option.value previous_cell_opt ~default:Dal.Slots_history.genesis - in - let* attested_slot_headers = - if not feature_enable then - (* There are no published headers, because the DAL was not enabled, - and therefore there are no attested headers. *) - return [] - else - (* 3. We retrieve the slot headers published at level [level - - attestation_lag] from the context. *) - let* published_slot_headers = - if published_level = 1l then return [] - else - Plugin.RPC.Dal.dal_published_slot_headers - cpctxt - (`Main, `Level published_level) - () - in - (* 4. We retrieve the bitset of attested slots at level [level]. *) - let* attested_slots = - let*? metadata = - Option.to_result - block_info.metadata - ~none: - (TzTrace.make - @@ Layer1_services.Cannot_read_block_metadata block_info.hash - ) - in - return metadata.protocol_data.dal_attestation - in - let is_slot_attested slot = - Dal.Attestation.is_attested - attested_slots - slot.Dal.Slot.Header.id.index - in - (* 5. We filter the list of slot headers published at [level - - attestation_lag] and keep only those attested at level [level]. *) - let attested_slot_headers, _attested_slots_bitset = - Dal.Slot.compute_attested_slot_headers - ~is_slot_attested - published_slot_headers - in - return attested_slot_headers - in - let*? published_level = - Raw_level.of_int32 published_level |> Environment.wrap_tzresult - in - (* 6. Starting from the [previous_cell], we insert the successive cells - of level [level] in the skip list thanks to function - {!add_confirmed_slot_headers}. The function is fed with an empty - history cache, so the returned [cache] contains exactly the cells - produced for this [level]. *) - let*? _last_cell, cache = - let capacity = - Int64.of_int - @@ max prev_number_of_slots dal_constants.number_of_slots - in - Dal.Slots_history.add_confirmed_slot_headers - previous_cell - (Dal.Slots_history.History_cache.empty ~capacity) - published_level - (* FIXME/DAL: https://gitlab.com/tezos/tezos/-/issues/3997 - - Not resilient to DAL parameters change. *) - ~number_of_slots:dal_constants.number_of_slots - attested_slot_headers - |> Environment.wrap_tzresult - in - (* 7. We finally export and return the cells alongside their hashes as a - list. *) - let last_cells = - let open Dal.Slots_history.History_cache in - view cache |> Map.bindings - in - return last_cells + Plugin.RPC.Dal.skip_list_cells_of_level + cpctxt + (`Main, `Level attested_level) + () end module RPC = struct -- GitLab From 8cb4451110874683d8a258cfde6767c344cb0edd Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Mon, 21 Oct 2024 12:02:39 +0200 Subject: [PATCH 6/6] DAL/Proto: explicit the size of lists in the storage --- src/proto_alpha/lib_protocol/storage.ml | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/src/proto_alpha/lib_protocol/storage.ml b/src/proto_alpha/lib_protocol/storage.ml index ef1e8648fed2..8d295e9b4de1 100644 --- a/src/proto_alpha/lib_protocol/storage.ml +++ b/src/proto_alpha/lib_protocol/storage.ml @@ -2178,6 +2178,9 @@ module Dal = struct let name = ["slot_headers"] end) (struct + (* The size of the list below is at most equal to the + [number_of_slots] as declared in the DAL parameters of the + protocol. *) type t = Dal_slot_repr.Header.t list let encoding = Data_encoding.(list Dal_slot_repr.Header.encoding) @@ -2200,6 +2203,8 @@ module Dal = struct let name = ["slot_headers_successive_histories_of_level"] end) (struct + (* The size of the list below is always equal to the [number_of_slots] + as declared in the DAL parameters of the protocol. *) type t = (Dal_slot_repr.History.Pointer_hash.t * Dal_slot_repr.History.t) list -- GitLab