diff --git a/src/proto_alpha/lib_plugin/RPC.ml b/src/proto_alpha/lib_plugin/RPC.ml index 390c49976a3891dd9085c1db97aa3f3166912404..d88e154fd4969546328033a60fda42644fd07f74 100644 --- a/src/proto_alpha/lib_plugin/RPC.ml +++ b/src/proto_alpha/lib_plugin/RPC.ml @@ -2292,6 +2292,9 @@ module Sc_rollup = struct end module Dal = struct + let path : RPC_context.t RPC_path.context = + RPC_path.(open_root / "context" / "dal") + module S = struct let dal_confirmed_slot_headers_history = let output = Data_encoding.option Dal.Slots_history.encoding in @@ -2302,8 +2305,22 @@ module Dal = struct DAL is enabled, or [None] otherwise." ~output ~query - RPC_path.( - open_root / "context" / "dal" / "confirmed_slot_headers_history") + RPC_path.(path / "confirmed_slot_headers_history") + + let shards_query = + RPC_query.( + query (fun level -> level) + |+ opt_field "level" Raw_level.rpc_arg (fun t -> t) + |> seal) + + let shards = + RPC_service.get_service + ~description:"Get the shard assignements for a given level" + ~query:shards_query + ~output: + Data_encoding.( + list (tup2 Signature.Public_key_hash.encoding (tup2 int16 int16))) + RPC_path.(path / "shards") end let register_dal_confirmed_slot_headers_history () = @@ -2315,10 +2332,17 @@ module Dal = struct Dal.Slots_storage.get_slot_headers_history ctxt >|=? Option.some else return None) - let register () = register_dal_confirmed_slot_headers_history () - let dal_confirmed_slots_history ctxt block = RPC_context.make_call0 S.dal_confirmed_slot_headers_history ctxt block () () + + let register_shards () = + Registration.register0 ~chunked:true S.shards @@ fun ctxt level () -> + let level = Option.value level ~default:(Raw_level.of_int32_exn 0l) in + Dal_services.shards ctxt ~level + + let register () = + register_dal_confirmed_slot_headers_history () ; + register_shards () end module Tx_rollup = struct diff --git a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL index fb3eb85045a76f3b58563d1465a5f71a38a3b083..938c2e763d8e46691969ce7a5b064a09c3ed0ab8 100644 --- a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL +++ b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL @@ -257,6 +257,7 @@ "Delegate_services", "Voting_services", "Tx_rollup_services", + "Dal_services", "Alpha_services", "Main" diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 3136936c9afff065e7f3911a5f249c01cddcca42..e38886e200e8fadedfc5b43746dc21ef66dfb421 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2837,6 +2837,10 @@ module Dal : sig module Endorsement : sig type t + type shard_index = int + + module Shard_map : Map.S with type key = shard_index + val encoding : t Data_encoding.t val empty : t @@ -2847,9 +2851,22 @@ module Dal : sig val expected_size_in_bits : max_index:Slot_index.t -> int - val shards : context -> endorser:public_key_hash -> int list + val shards_of_endorser : + context -> endorser:public_key_hash -> shard_index list option val record_available_shards : context -> t -> int list -> context + + type committee = { + pkh_to_shards : (shard_index * int) Signature.Public_key_hash.Map.t; + shard_to_pkh : Signature.Public_key_hash.t Shard_map.t; + } + + val compute_committee : + context -> + (Slot.t -> (context * Signature.Public_key_hash.t) tzresult Lwt.t) -> + committee tzresult Lwt.t + + val init_committee : context -> committee -> context end type slot_id = {published_level : Raw_level.t; index : Slot_index.t} @@ -2969,6 +2986,10 @@ module Dal_errors : sig | Dal_publish_slot_header_candidate_with_low_fees of {proposed_fees : Tez.t} | Dal_endorsement_size_limit_exceeded of {maximum_size : int; got : int} | Dal_publish_slot_header_duplicate of {slot_header : Dal.Slot.Header.t} + | Dal_data_availibility_endorser_not_in_committee of { + endorser : Signature.Public_key_hash.t; + level : Level.t; + } end (** This module re-exports definitions from {!Sc_rollup_storage} and diff --git a/src/proto_alpha/lib_protocol/apply.ml b/src/proto_alpha/lib_protocol/apply.ml index a64fe7b54a81cf56e109b9c0bc336257a665c812..1a6144dd2ce6e8ff18f23cbc9328e24b7a877ee3 100644 --- a/src/proto_alpha/lib_protocol/apply.ml +++ b/src/proto_alpha/lib_protocol/apply.ml @@ -2171,7 +2171,7 @@ let apply_contents_list (type kind) ctxt chain_id (mode : mode) operation should be merged with an endorsement or at least refined. *) Dal_apply.apply_data_availability ctxt slot_availability ~endorser - >>=? fun ctxt -> + >>?= fun ctxt -> return ( ctxt, Single_result (Dal_slot_availability_result {delegate = endorser}) ) @@ -2682,7 +2682,7 @@ let finalize_application ctxt block_data_contents ~round ~predecessor_hash may_start_new_cycle ctxt in let* ctxt = Amendment.may_start_new_voting_period ctxt in - let* ctxt, dal_slot_availability = Dal_apply.dal_finalisation ctxt in + let* ctxt, dal_slot_availability = Dal_apply.finalisation ctxt in let* _inbox, _diff, ctxt = Sc_rollup.Inbox.add_end_of_level ctxt in let balance_updates = migration_balance_updates @ baking_receipts @ cycle_end_balance_updates diff --git a/src/proto_alpha/lib_protocol/dal_apply.ml b/src/proto_alpha/lib_protocol/dal_apply.ml index 4ab9ec5145e5c9d08e1a061e72035185f5441c28..617e99089a7aa58eab5294f50737da81b0493aba 100644 --- a/src/proto_alpha/lib_protocol/dal_apply.ml +++ b/src/proto_alpha/lib_protocol/dal_apply.ml @@ -57,10 +57,13 @@ let validate_data_availability ctxt data_availability = (Dal_endorsement_size_limit_exceeded {maximum_size; got = size}) let apply_data_availability ctxt data_availability ~endorser = - assert_dal_feature_enabled ctxt >>?= fun () -> - let shards = Dal.Endorsement.shards ctxt ~endorser in - Dal.Endorsement.record_available_shards ctxt data_availability shards - |> return + assert_dal_feature_enabled ctxt >>? fun () -> + match Dal.Endorsement.shards_of_endorser ctxt ~endorser with + | None -> + let level = Level.current ctxt in + error (Dal_data_availibility_endorser_not_in_committee {endorser; level}) + | Some shards -> + Ok (Dal.Endorsement.record_available_shards ctxt data_availability shards) let validate_publish_slot_header ctxt Dal.Slot.Header.{id = {index; _}; _} = assert_dal_feature_enabled ctxt >>? fun () -> @@ -81,7 +84,7 @@ let apply_publish_slot_header ctxt slot_header = if updated then ok ctxt else error (Dal_publish_slot_header_duplicate {slot_header}) -let dal_finalisation ctxt = +let finalisation ctxt = only_if_dal_feature_enabled ctxt ~default:(fun ctxt -> return (ctxt, None)) @@ -104,3 +107,22 @@ let dal_finalisation ctxt = *) Dal.Slot.finalize_pending_slot_headers ctxt >|=? fun (ctxt, slot_availability) -> (ctxt, Some slot_availability)) + +let initialisation ctxt ~level = + let open Lwt_tzresult_syntax in + only_if_dal_feature_enabled + ctxt + ~default:(fun ctxt -> return ctxt) + (fun ctxt -> + let pkh_from_tenderbake_slot slot = + Stake_distribution.slot_owner ctxt level slot + >|=? fun (ctxt, consensus_pk1) -> (ctxt, consensus_pk1.delegate) + in + (* This committee is cached because it is the one we will use + for the validation of the DAL endorsements. *) + let* committee = + Alpha_context.Dal.Endorsement.compute_committee + ctxt + pkh_from_tenderbake_slot + in + return (Alpha_context.Dal.Endorsement.init_committee ctxt committee)) diff --git a/src/proto_alpha/lib_protocol/dal_apply.mli b/src/proto_alpha/lib_protocol/dal_apply.mli index 0f02a75a8ec41d830f84b2b5f82138b6e2d9d373..6d7b5ff1b2ce437283635ce92afac85dd6645f81 100644 --- a/src/proto_alpha/lib_protocol/dal_apply.mli +++ b/src/proto_alpha/lib_protocol/dal_apply.mli @@ -38,10 +38,7 @@ val validate_data_availability : t -> Dal.Endorsement.t -> unit tzresult [endorsement] into the [ctxt] assuming [endorser] issued those endorsements. *) val apply_data_availability : - t -> - Dal.Endorsement.t -> - endorser:Signature.Public_key_hash.t -> - t tzresult Lwt.t + t -> Dal.Endorsement.t -> endorser:Signature.Public_key_hash.t -> t tzresult (** [validate_publish_slot_header ctxt slot] ensures that [slot_header] is valid and cannot prevent an operation containing [slot_header] to be @@ -54,10 +51,16 @@ val validate_publish_slot_header : t -> Dal.Slot.Header.t -> unit tzresult already a slot header. *) val apply_publish_slot_header : t -> Dal.Slot.Header.t -> t tzresult -(** [dal_finalisation ctxt] should be executed at block finalisation +(** [finalisation ctxt] should be executed at block finalisation time. A set of slots available at level [ctxt.current_level - lag] is returned encapsulated into the endorsement data-structure. [lag] is a parametric constant specific to the data-availability layer. *) -val dal_finalisation : t -> (t * Dal.Endorsement.t option) tzresult Lwt.t +val finalisation : t -> (t * Dal.Endorsement.t option) tzresult Lwt.t + +(** [initialize ctxt ~level] should be executed at block + initialisation time. It allows to cache the committee for [level] + in memory so that every time we need to use this committee, there + is no need to recompute it again. *) +val initialisation : t -> level:Level.t -> t tzresult Lwt.t diff --git a/src/proto_alpha/lib_protocol/dal_endorsement_repr.ml b/src/proto_alpha/lib_protocol/dal_endorsement_repr.ml index 0232bab896baa62aec6de7e48e9f129a7baa6ea5..3ab3a78b6ff7553ef7d4c37751600ae76ffa2d8f 100644 --- a/src/proto_alpha/lib_protocol/dal_endorsement_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_endorsement_repr.ml @@ -78,6 +78,14 @@ let expected_size_in_bits ~max_index = | Error _ -> (* Happens if max_index < 1 *) 0 | Ok t -> occupied_size_in_bits t +type shard_index = int + +module Shard_map = Map.Make (struct + type t = shard_index + + let compare = Compare.Int.compare +end) + module Accountability = struct (* DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3109 @@ -86,8 +94,6 @@ module Accountability = struct *) type t = Bitset.t list - type shard = int - let init ~length = let l = List.init diff --git a/src/proto_alpha/lib_protocol/dal_endorsement_repr.mli b/src/proto_alpha/lib_protocol/dal_endorsement_repr.mli index c607964d4840b39edbdbfd12ecd974a829c615a9..0a47007c346af0a05d553180546369291dda46af 100644 --- a/src/proto_alpha/lib_protocol/dal_endorsement_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_endorsement_repr.mli @@ -67,6 +67,11 @@ val occupied_size_in_bits : t -> int [max_index]. *) val expected_size_in_bits : max_index:Dal_slot_repr.Index.t -> int +(** A shard_index aims to be a positive number. *) +type shard_index = int + +module Shard_map : Map.S with type key = shard_index + (** This module is used to record the various data-availability endorsements. @@ -85,9 +90,6 @@ module Accountability : sig Consider using the [Bounded] module. In particular, change the semantics of [is_slot_available] accordingly. *) - (** A shard aims to be a positive number. *) - type shard = int - (** [init ~length] initialises a new accountability data-structures with at most [length] slots and where for every slot, no shard is available. *) @@ -98,7 +100,7 @@ module Accountability : sig are available. It is the responsibility of the caller to ensure the shard indices are positive numbers. A negative shard index is ignored. *) - val record_shards_availability : t -> available_slots -> shard list -> t + val record_shards_availability : t -> available_slots -> shard_index list -> t (** [is_slot_available t ~threshold ~number_of_shards slot] returns [true] if the number of shards recorded in [t] for the [slot] is diff --git a/src/proto_alpha/lib_protocol/dal_errors_repr.ml b/src/proto_alpha/lib_protocol/dal_errors_repr.ml index a7c0744ec79e02bc1097222f03c467406159d36a..f41922589142ddbdbb9a0b430b170f4eecabcd2f 100644 --- a/src/proto_alpha/lib_protocol/dal_errors_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_errors_repr.ml @@ -36,6 +36,14 @@ type error += } | Dal_endorsement_size_limit_exceeded of {maximum_size : int; got : int} | Dal_publish_slot_header_duplicate of {slot_header : Dal_slot_repr.Header.t} + | Dal_rollup_already_registered_to_slot_index of + (Sc_rollup_repr.t * Dal_slot_repr.Index.t) + | Dal_requested_subscriptions_at_future_level of + (Raw_level_repr.t * Raw_level_repr.t) + | Dal_data_availibility_endorser_not_in_committee of { + endorser : Signature.Public_key_hash.t; + level : Level_repr.t; + } let () = let open Data_encoding in @@ -162,4 +170,78 @@ let () = (function | Dal_publish_slot_header_duplicate {slot_header} -> Some slot_header | _ -> None) - (fun slot_header -> Dal_publish_slot_header_duplicate {slot_header}) + (fun slot_header -> Dal_publish_slot_header_duplicate {slot_header}) ; + register_error_kind + `Permanent + ~id:"Dal_rollup_already_subscribed_to_slot" + ~title:"DAL rollup already subscribed to slot" + ~description + ~pp:(fun ppf (rollup, slot_index) -> + Format.fprintf + ppf + "Rollup %a is already subscribed to data availability slot index %a" + Sc_rollup_repr.pp + rollup + Dal_slot_repr.Index.pp + slot_index) + Data_encoding.( + obj2 + (req "rollup" Sc_rollup_repr.encoding) + (req "slot_index" Dal_slot_repr.Index.encoding)) + (function + | Dal_rollup_already_registered_to_slot_index (rollup, slot_index) -> + Some (rollup, slot_index) + | _ -> None) + (fun (rollup, slot_index) -> + Dal_rollup_already_registered_to_slot_index (rollup, slot_index)) ; + let description = + "Requested List of subscribed rollups to slot at a future level" + in + register_error_kind + `Temporary + ~id:"Dal_requested_subscriptions_at_future_level" + ~title:"Requested list of subscribed dal slots at a future level" + ~description + ~pp:(fun ppf (current_level, future_level) -> + Format.fprintf + ppf + "The list of subscribed dal slot indices has been requested for level \ + %a, but the current level is %a" + Raw_level_repr.pp + future_level + Raw_level_repr.pp + current_level) + Data_encoding.( + obj2 + (req "current_level" Raw_level_repr.encoding) + (req "future_level" Raw_level_repr.encoding)) + (function + | Dal_requested_subscriptions_at_future_level (current_level, future_level) + -> + Some (current_level, future_level) + | _ -> None) + (fun (current_level, future_level) -> + Dal_requested_subscriptions_at_future_level (current_level, future_level)) ; + register_error_kind + `Permanent + ~id:"Dal_data_availibility_endorser_not_in_committee" + ~title:"The endorser is not part of the DAL committee for this level" + ~description:"The endorser is not part of the DAL committee for this level" + ~pp:(fun ppf (endorser, level) -> + Format.fprintf + ppf + "The endorser %a is not part of the DAL committee for the level %a" + Signature.Public_key_hash.pp + endorser + Level_repr.pp + level) + Data_encoding.( + obj2 + (req "endorser" Signature.Public_key_hash.encoding) + (req "level" Level_repr.encoding)) + (function + | Dal_data_availibility_endorser_not_in_committee {endorser; level} -> + Some (endorser, level) + | _ -> None) + (fun (endorser, level) -> + Dal_data_availibility_endorser_not_in_committee {endorser; level}) diff --git a/src/proto_alpha/lib_protocol/dal_services.ml b/src/proto_alpha/lib_protocol/dal_services.ml new file mode 100644 index 0000000000000000000000000000000000000000..65ee5bb1b9b5d432aee104d77dd10e3b465cf564 --- /dev/null +++ b/src/proto_alpha/lib_protocol/dal_services.ml @@ -0,0 +1,49 @@ +(*****************************************************************************) +(* *) +(* Open Source License *) +(* Copyright (c) 2022 Nomadic Labs *) +(* *) +(* Permission is hereby granted, free of charge, to any person obtaining a *) +(* copy of this software and associated documentation files (the "Software"),*) +(* to deal in the Software without restriction, including without limitation *) +(* the rights to use, copy, modify, merge, publish, distribute, sublicense, *) +(* and/or sell copies of the Software, and to permit persons to whom the *) +(* Software is furnished to do so, subject to the following conditions: *) +(* *) +(* The above copyright notice and this permission notice shall be included *) +(* in all copies or substantial portions of the Software. *) +(* *) +(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*) +(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *) +(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL *) +(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*) +(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING *) +(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER *) +(* DEALINGS IN THE SOFTWARE. *) +(* *) +(*****************************************************************************) + +open Alpha_context + +let assert_dal_feature_enabled ctxt = + let open Constants in + let Parametric.{dal = {feature_enable; _}; _} = parametric ctxt in + error_unless + Compare.Bool.(feature_enable = true) + Dal_errors.Dal_feature_disabled + +let shards ctxt ~level = + let open Lwt_tzresult_syntax in + let open Dal.Endorsement in + assert_dal_feature_enabled ctxt >>?= fun () -> + let level = Level.from_raw ctxt level in + let pkh_from_tenderbake_slot slot = + Stake_distribution.slot_owner ctxt level slot + >|=? fun (ctxt, consensus_key) -> (ctxt, consensus_key.delegate) + in + (* We do not cache this committee. This function being used by RPCs + to know the DAL committee at some particular level. *) + let* committee = + Dal.Endorsement.compute_committee ctxt pkh_from_tenderbake_slot + in + Signature.Public_key_hash.Map.bindings committee.pkh_to_shards |> return diff --git a/src/proto_alpha/lib_protocol/dal_services.mli b/src/proto_alpha/lib_protocol/dal_services.mli new file mode 100644 index 0000000000000000000000000000000000000000..d6394f128decf75158f7871bf0b034b09ea36af6 --- /dev/null +++ b/src/proto_alpha/lib_protocol/dal_services.mli @@ -0,0 +1,33 @@ +(*****************************************************************************) +(* *) +(* Open Source License *) +(* Copyright (c) 2022 Nomadic Labs *) +(* *) +(* Permission is hereby granted, free of charge, to any person obtaining a *) +(* copy of this software and associated documentation files (the "Software"),*) +(* to deal in the Software without restriction, including without limitation *) +(* the rights to use, copy, modify, merge, publish, distribute, sublicense, *) +(* and/or sell copies of the Software, and to permit persons to whom the *) +(* Software is furnished to do so, subject to the following conditions: *) +(* *) +(* The above copyright notice and this permission notice shall be included *) +(* in all copies or substantial portions of the Software. *) +(* *) +(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*) +(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *) +(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL *) +(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*) +(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING *) +(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER *) +(* DEALINGS IN THE SOFTWARE. *) +(* *) +(*****************************************************************************) + +(** [shards ctxt ~level] returns the DAL committee as an association + list that associates to the public key hash [pkh] of the member of + the committee an interval [(s,n)], meaning that the slots + [s;s+1;...;s+n-1] belongs to [pkh]. It is guaranteed that [n>0]. *) +val shards : + Alpha_context.t -> + level:Alpha_context.Raw_level.t -> + (Signature.Public_key_hash.t * (int * int)) list tzresult Lwt.t diff --git a/src/proto_alpha/lib_protocol/dune b/src/proto_alpha/lib_protocol/dune index 70b931f52b641519290273a132ad23232974a7b7..e2ce10c4a8c1744376202868378e7a4dfa17e540 100644 --- a/src/proto_alpha/lib_protocol/dune +++ b/src/proto_alpha/lib_protocol/dune @@ -261,6 +261,7 @@ Delegate_services Voting_services Tx_rollup_services + Dal_services Alpha_services Main)) @@ -531,6 +532,7 @@ delegate_services.ml delegate_services.mli voting_services.ml voting_services.mli tx_rollup_services.ml tx_rollup_services.mli + dal_services.ml dal_services.mli alpha_services.ml alpha_services.mli main.ml main.mli (:src_dir TEZOS_PROTOCOL)) @@ -781,6 +783,7 @@ delegate_services.ml delegate_services.mli voting_services.ml voting_services.mli tx_rollup_services.ml tx_rollup_services.mli + dal_services.ml dal_services.mli alpha_services.ml alpha_services.mli main.ml main.mli (:src_dir TEZOS_PROTOCOL)) (action @@ -1036,6 +1039,7 @@ delegate_services.ml delegate_services.mli voting_services.ml voting_services.mli tx_rollup_services.ml tx_rollup_services.mli + dal_services.ml dal_services.mli alpha_services.ml alpha_services.mli main.ml main.mli (:src_dir TEZOS_PROTOCOL)) (action diff --git a/src/proto_alpha/lib_protocol/main.ml b/src/proto_alpha/lib_protocol/main.ml index 1abe8b2569cd334303b2f54490ae310e8736aa4e..d8fc06e5a01db373561caf6c98a8990033c42484 100644 --- a/src/proto_alpha/lib_protocol/main.ml +++ b/src/proto_alpha/lib_protocol/main.ml @@ -171,6 +171,7 @@ let prepare_ctxt ctxt mode ~(predecessor : Block_header.shell_header) = ~endorsement_level:predecessor_level ~preendorsement_level in + Dal_apply.initialisation ~level:predecessor_level ctxt >>=? fun ctxt -> return ( ctxt, migration_balance_updates, diff --git a/src/proto_alpha/lib_protocol/raw_context.ml b/src/proto_alpha/lib_protocol/raw_context.ml index c18130400cfb740e58f855e3d3db1d73f8ca7a1a..d26a3dc7197198a0c4ddc2bd12fd4973ba477919 100644 --- a/src/proto_alpha/lib_protocol/raw_context.ml +++ b/src/proto_alpha/lib_protocol/raw_context.ml @@ -223,6 +223,18 @@ module Raw_consensus = struct {t with grand_parent_branch = Some grand_parent_branch} end +type dal_committee = { + pkh_to_shards : + (Dal_endorsement_repr.shard_index * int) Signature.Public_key_hash.Map.t; + shard_to_pkh : Signature.Public_key_hash.t Dal_endorsement_repr.Shard_map.t; +} + +let empty_dal_committee = + { + pkh_to_shards = Signature.Public_key_hash.Map.empty; + shard_to_pkh = Dal_endorsement_repr.Shard_map.empty; + } + type back = { context : Context.t; constants : Constants_parametric_repr.t; @@ -262,6 +274,7 @@ type back = { - We need to provide an incentive to avoid byzantines to post dummy slot headers. *) dal_endorsement_slot_accountability : Dal_endorsement_repr.Accountability.t; + dal_committee : dal_committee; } (* @@ -819,6 +832,7 @@ let prepare ~level ~predecessor_timestamp ~timestamp ctxt = dal_endorsement_slot_accountability = Dal_endorsement_repr.Accountability.init ~length:constants.Constants_parametric_repr.dal.number_of_slots; + dal_committee = empty_dal_committee; }; } @@ -1534,39 +1548,105 @@ module Dal = struct ~threshold ~number_of_shards + type committee = dal_committee = { + pkh_to_shards : + (Dal_endorsement_repr.shard_index * int) Signature.Public_key_hash.Map.t; + shard_to_pkh : Signature.Public_key_hash.t Dal_endorsement_repr.Shard_map.t; + } + (* DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3110 - We have to choose for the sampling. Here we use the one used by - the consensus which is hackish and probably not what we want at - the end. However, it should be enough for a prototype. This has a - very bad complexity too. *) - let rec compute_shards ?(index = 0) ctxt ~endorser = - let max_shards = - ctxt.back.constants.dal.cryptobox_parameters.number_of_shards + A committee is selected by the callback function + [pkh_from_tenderbake_slot]. We use a callback because of circular + dependencies. It is not clear whether it will be the final choice + for the DAL committee. The current solution is a bit hackish but + should work. If we decide to differ from the Tenderbake + committee, one could just draw a new committee. + + The problem with drawing a new committee is that it is not + guaranteed that everyone in the DAL committee will be in the + Tenderbake committee. Consequently, either we decide to have a + new consensus operation which does not count for Tenderbake, + and/or we take into account for the model of DAL that at every + level, a percentage of DAL endorsements cannot be received. *) + let compute_committee ctxt pkh_from_tenderbake_slot = + let Constants_parametric_repr. + { + dal = {cryptobox_parameters = {number_of_shards; _}; _}; + consensus_committee_size; + _; + } = + ctxt.back.constants + in + (* We first draw a committee by drawing slots from the Tenderbake + committee. To have a compact representation of slots, we can + sort the Tenderbake slots by [pkh], so that a committee is + actually only an interval. This is done by recomputing a + committee from the first one. *) + let update_committee committee pkh ~slot_index ~power = + { + pkh_to_shards = + Signature.Public_key_hash.Map.update + pkh + (function + | None -> Some (slot_index, power) + | Some (initial_shard_index, old_power) -> + Some (initial_shard_index, old_power + power)) + committee.pkh_to_shards; + shard_to_pkh = + List.fold_left + (fun shard_to_pkh slot -> + Dal_endorsement_repr.Shard_map.add slot pkh shard_to_pkh) + committee.shard_to_pkh + Misc.(slot_index --> (slot_index + (power - 1))); + } + in + let rec compute_power index committee = + if Compare.Int.(index < 0) then return committee + else + let shard_index = index mod consensus_committee_size in + Slot_repr.of_int shard_index >>?= fun slot -> + pkh_from_tenderbake_slot slot >>=? fun (_ctxt, pkh) -> + (* The [Slot_repr] module is related to the Tenderbake committee. *) + let slot_index = Slot_repr.to_int slot in + (* An optimisation could be to return only [pkh_to_shards] map + because the second one is not used. This can be done later + on if it is a good optimisation. *) + let committee = update_committee committee pkh ~slot_index ~power:1 in + compute_power (index - 1) committee + in + (* This committee is an intermediate to compute the final DAL + commitee. This one only projects the Tenderbake committee into + the DAL committee. The next one reorder the slots so that they + are grouped by public key hash. *) + compute_power (number_of_shards - 1) empty_dal_committee + >>=? fun unordered_committee -> + let dal_committee = + Signature.Public_key_hash.Map.fold + (fun pkh (_, power) (total_power, committee) -> + let committee = + update_committee committee pkh ~slot_index:total_power ~power + in + let new_total_power = total_power + power in + (new_total_power, committee)) + unordered_committee.pkh_to_shards + (0, empty_dal_committee) + |> snd + in + return dal_committee + + let init_committee ctxt committee = + {ctxt with back = {ctxt.back with dal_committee = committee}} + + let shards_of_endorser ctxt ~endorser:pkh = + let rec make acc (initial_shard_index, power) = + if Compare.Int.(power <= 0) then List.rev acc + else make (initial_shard_index :: acc) (initial_shard_index + 1, power - 1) in - Slot_repr.Map.fold_e - (fun _ (consensus_key, power) (index, shards) -> - let limit = Compare.Int.min (index + power) max_shards in - (* Early fail when we have reached the desired number of shards *) - if Compare.Int.(index >= max_shards) then Error shards - else if - Signature.Public_key_hash.(consensus_key.consensus_pkh = endorser) - then - let shards = Misc.(index --> (limit - 1)) in - Ok (index + power, shards) - else Ok (index + power, shards)) - ctxt.back.consensus.allowed_endorsements - (index, []) - |> function - | Ok (index, []) -> - (* This happens if the number of Tenderbake slots is below the - number of shards. Therefore, we reuse the committee using a - shift (index being the size of the committee). *) - compute_shards ~index ctxt ~endorser - | Ok (_index, shards) -> shards - | Error shards -> shards - - let shards ctxt ~endorser = compute_shards ~index:0 ctxt ~endorser + Signature.Public_key_hash.Map.find_opt + pkh + ctxt.back.dal_committee.pkh_to_shards + |> Option.map (fun pre_shards -> make [] pre_shards) end (* The type for relative context accesses instead from the root. In order for diff --git a/src/proto_alpha/lib_protocol/raw_context.mli b/src/proto_alpha/lib_protocol/raw_context.mli index e8a284fd5ca57075c27ba72dcfc8252fca518d19..b0f1bd110c078786190644f6b5b24c8c4ce1168d 100644 --- a/src/proto_alpha/lib_protocol/raw_context.mli +++ b/src/proto_alpha/lib_protocol/raw_context.mli @@ -418,7 +418,57 @@ module Dal : sig [0;number_of_slots - 1], returns [false]. *) val is_slot_index_available : t -> Dal_slot_repr.Index.t -> bool - (** [shards ctxt ~endorser] returns the shard assignment for the - [endorser] for the current level. *) - val shards : t -> endorser:Signature.Public_key_hash.t -> int list + (** [shards_of_endorser ctxt ~endorser] returns the shard assignment + of the DAL committee of the current level for [endorser]. This + function never returns an empty list. *) + val shards_of_endorser : + t -> endorser:Signature.Public_key_hash.t -> int list option + + (** The DAL committee is a subset of the Tenderbake committee. A + shard from [0;number_of_shards] is associated to a public key + hash. For efficiency reasons, the committee is two-folds: a + mapping public key hash to shards and shards to public key + hashes. The DAL committee ensures the shards associated to the + same public key hash are contiguous. The list of shards is + represented as two natural numbers [(initial, power)] which + encodes the list of shards: + [initial;initial + 1;...;initial + power - 1]. + + This data-type ensures the following invariants: + + - \forall pkh shard, find pkh_to_shards pkh = Some (start,n) -> + \forall i, i \in [start; start + n -1] -> find shard_to_pkh shard + = Some pkh + + - forall pkh shard, find shard_to_pkh shard = Some pkh -> + \exists (start,n), find pkh_to_shards pkh = Some (start,n) /\ + start <= shard <= start + n -1 + + - Given an endorser, all its shards assignement are contiguous + *) + type committee = { + pkh_to_shards : + (Dal_endorsement_repr.shard_index * int) Signature.Public_key_hash.Map.t; + shard_to_pkh : Signature.Public_key_hash.t Dal_endorsement_repr.Shard_map.t; + } + + (** [compute_committee ctxt pkh_from_tenderbake_slot] computes the + DAL committee using the [pkh_from_tenderbake_slot] function. This + functions takes into account the fact that the DAL committee and + the Tenderbake committee may have different size. If the DAL + committee is smaller, then we simply take a projection of the + Tenderbake committee for the first [n] slots. If the DAL + committee is larger, shards are computed moduloe the Tenderbake + committee. Slots assignements are reordered for a given a public + key hash, to ensure all the slots (or shards in the context of + DAL) shards are contiguous (see {!type:committee}). *) + val compute_committee : + t -> + (Slot_repr.t -> (t * Signature.Public_key_hash.t) tzresult Lwt.t) -> + committee tzresult Lwt.t + + (** [init_committee ctxt committee] returns a context where the + [committee] is cached. The committee is expected to be the one + for the current level. *) + val init_committee : t -> committee -> t end diff --git a/src/proto_alpha/lib_protocol/test/integration/validate/generator_descriptors.ml b/src/proto_alpha/lib_protocol/test/integration/validate/generator_descriptors.ml index 14c622a5fd6e70d8cd67f7a7da186b96ff792bf5..6bb880073e97597502b805daacd90817596a619e 100644 --- a/src/proto_alpha/lib_protocol/test/integration/validate/generator_descriptors.ml +++ b/src/proto_alpha/lib_protocol/test/integration/validate/generator_descriptors.ml @@ -630,7 +630,31 @@ let endorsement_descriptor = List.filter_map_es gen state.delegates); } +let dal_slot_availibility ctxt delegate = + let open Lwt_result_syntax in + let level = Alpha_context.Level.current ctxt in + let pkh_from_tenderbake_slot slot = + Alpha_context.Stake_distribution.slot_owner ctxt level slot + >|=? fun (ctxt, consensus_pk1) -> (ctxt, consensus_pk1.delegate) + in + let* committee = + Alpha_context.Dal.Endorsement.compute_committee + ctxt + pkh_from_tenderbake_slot + in + match + Environment.Signature.Public_key_hash.Map.find + delegate + committee.pkh_to_shards + with + | None -> return_none + | Some _interval -> + (* The content of the endorsement does not matter for covalidity. *) + let attestation = Dal.Endorsement.empty in + return_some (Dal_slot_availability (delegate, attestation)) + let dal_slot_availability_descriptor = + let open Lwt_result_syntax in { parameters = (fun params -> @@ -643,12 +667,17 @@ let dal_slot_availability_descriptor = opt_prelude = None; candidates_generator = (fun state -> - let open Lwt_result_syntax in - let gen (del, _) = - let op = Dal_slot_availability (del, Dal.Endorsement.empty) in - Op.pack_operation (B state.block) None (Single op) + let gen (delegate, _) = + let* ctxt = Context.to_alpha_ctxt (B state.block) in + let* op = + dal_slot_availibility ctxt delegate >|= Environment.wrap_tzresult + in + return + (op + |> Option.map (fun op -> + Op.pack_operation (B state.block) None (Single op))) in - return (List.map gen state.delegates)); + List.filter_map_es gen state.delegates); } module Manager = Manager_operation_helpers diff --git a/tezt/lib_tezos/RPC.ml b/tezt/lib_tezos/RPC.ml index e96f271dd2bb0464abdf813cce92b6c1d125a8e2..ccf6983076a9643cf7edce1a10229754960b20c1 100644 --- a/tezt/lib_tezos/RPC.ml +++ b/tezt/lib_tezos/RPC.ml @@ -1109,4 +1109,17 @@ let get_chain_block_votes_total_voting_power ?(chain = "main") ?(block = "head") ["chains"; chain; "blocks"; block; "votes"; "total_voting_power"] Fun.id +let get_chain_block_context_dal_shards ?(chain = "main") ?(block = "head") + ?level () = + let query_string = + match level with + | None -> [] + | Some offset -> [("level", string_of_int offset)] + in + make + GET + ["chains"; chain; "blocks"; block; "context"; "dal"; "shards"] + ~query_string + Fun.id + let make = RPC_core.make diff --git a/tezt/lib_tezos/RPC.mli b/tezt/lib_tezos/RPC.mli index 818c2df7762d04957fb49a00ee45aeeee85c3321..49c5b86ae3d17f7b6166bdbf1fcdc1e32b4fdb2d 100644 --- a/tezt/lib_tezos/RPC.mli +++ b/tezt/lib_tezos/RPC.mli @@ -967,3 +967,7 @@ val get_chain_block_votes_successor_period : [block] defaults to ["head"]. *) val get_chain_block_votes_total_voting_power : ?chain:string -> ?block:string -> unit -> JSON.t t + +(** RPC: [GET /chains/[chain]/blocks/[block]/context/dal/shards?level=[level]] *) +val get_chain_block_context_dal_shards : + ?chain:string -> ?block:string -> ?level:int -> unit -> JSON.t t diff --git a/tezt/manual_tests/dal.ml b/tezt/manual_tests/dal.ml new file mode 100644 index 0000000000000000000000000000000000000000..f003316eec99295c4c92823291b1abb74dd270b5 --- /dev/null +++ b/tezt/manual_tests/dal.ml @@ -0,0 +1,105 @@ +(*****************************************************************************) +(* *) +(* Open Source License *) +(* Copyright (c) 2022 Nomadic Labs *) +(* *) +(* Permission is hereby granted, free of charge, to any person obtaining a *) +(* copy of this software and associated documentation files (the "Software"),*) +(* to deal in the Software without restriction, including without limitation *) +(* the rights to use, copy, modify, merge, publish, distribute, sublicense, *) +(* and/or sell copies of the Software, and to permit persons to whom the *) +(* Software is furnished to do so, subject to the following conditions: *) +(* *) +(* The above copyright notice and this permission notice shall be included *) +(* in all copies or substantial portions of the Software. *) +(* *) +(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*) +(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *) +(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL *) +(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*) +(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING *) +(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER *) +(* DEALINGS IN THE SOFTWARE. *) +(* *) +(*****************************************************************************) + +let dal_distribution = + Protocol.register_test + ~__FILE__ + ~title:"Get the DAL distribution" + ~tags:["dal"; "distribution"] + ~supports:Protocol.(From_protocol 15) + @@ fun protocol -> + let _data_dir = + Cli.get ~default:None (fun data_dir -> Some (Some data_dir)) "data-dir" + in + let levels = + Cli.get ~default:10 (fun levels -> int_of_string_opt levels) "levels" + in + let output_file = + match + Cli.get + ~default:None + (fun output_file -> Some (Some output_file)) + "output-file" + with + | None -> + Test.fail "Specify an output file with --test-arg output-file=" + | Some output_file -> output_file + in + let* parameter_file = Rollup.Dal.Parameters.parameter_file protocol in + let* node, client = + Client.init_with_protocol ~parameter_file ~protocol `Client () + in + let* () = Client.bake_for_and_wait client in + let* number_of_shards = + let* constants = + RPC.Client.call client (RPC.get_chain_block_context_constants ()) + in + JSON.(constants |-> "dal" |-> "number_of_shards" |> as_int) |> return + in + let results = + Array.init levels (fun _ -> + Array.make number_of_shards Constant.bootstrap1.public_key_hash) + in + let* current_level = + RPC.Client.call client (RPC.get_chain_block_helper_current_level ()) + in + let rec iter offset = + let level = current_level.level + offset in + if offset < 0 then unit + else + let* json = + RPC.(call node @@ get_chain_block_context_dal_shards ~level ()) + in + List.iter + (fun json -> + let pkh = JSON.(json |=> 0 |> as_string) in + let initial_slot = JSON.(json |=> 1 |=> 0 |> as_int) in + let power = JSON.(json |=> 1 |=> 1 |> as_int) in + for slot = initial_slot to initial_slot + power - 1 do + let line = Array.get results offset in + Array.set line slot pkh + done) + (JSON.as_list json) ; + iter (offset - 1) + in + let* () = iter (levels - 1) in + with_open_out output_file (fun oc -> + output_string oc "levels, " ; + for slot = 0 to number_of_shards - 1 do + output_string oc (Format.asprintf "pkh for slot %d, " slot) + done ; + output_string oc "\n" ; + for i = 0 to levels - 1 do + output_string oc (Format.asprintf "level %d, " i) ; + for slot = 0 to number_of_shards - 1 do + let pkh = results.(i).(slot) in + output_string oc pkh ; + output_string oc ", " + done ; + output_string oc "\n" + done) ; + unit + +let register protocols = dal_distribution protocols diff --git a/tezt/manual_tests/main.ml b/tezt/manual_tests/main.ml index f138e513b8d73efc84c8c47662ec1abcdd447806..03c34805bc9b6b4f6faca4f781bcdc61e49659f9 100644 --- a/tezt/manual_tests/main.ml +++ b/tezt/manual_tests/main.ml @@ -31,5 +31,6 @@ let () = Migration.register () ; Migration_voting.register [Kathmandu] ; Stresstest_command.register ~protocols:Protocol.all ; + Dal.register [Alpha] ; (* Test.run () should be the last statement, don't register afterwards! *) Test.run () diff --git a/tezt/tests/dal.ml b/tezt/tests/dal.ml index 474c85042ccc49d1cf69c904dab32d1bbe2559f9..bd8b8516654bb3d289aa6f368665e1ab5f0ddf6f 100644 --- a/tezt/tests/dal.ml +++ b/tezt/tests/dal.ml @@ -235,6 +235,14 @@ let test_feature_flag _protocol _sc_rollup_node _sc_rollup_address node client = (feature_flag = false) bool ~error_msg:"Feature flag for the DAL should be disabled") ; + let*? process = + RPC.(Client.spawn client @@ get_chain_block_context_dal_shards ()) + in + let* () = + Process.check_error + ~msg:(rex "Data-availability layer will be enabled in a future proposal") + process + in let* (`OpHash oph1) = Operation.Consensus.( inject