diff --git a/docs/protocols/alpha.rst b/docs/protocols/alpha.rst index f4451c3e0424cb82e085eaf897fdcbe5505aaeb1..af8f42ff26827e53bf9a5553aa16f57867e79852 100644 --- a/docs/protocols/alpha.rst +++ b/docs/protocols/alpha.rst @@ -17,6 +17,17 @@ Environment Version Smart Rollups ------------- +Consensus +---------- + + - Implemented a new algorithm for the baker selection. The current Alias + method is used to determine the validator that should bake a block + for a given level and round. After the feature flag ``swrr_new_baker_lottery_enable`` + is activated, the selection would use SWRR (Smooth Weighted Round Robin), + which is a deterministic method to distribute the round 0 of all the levels + for a given cycle. The higher rounds are then using a shifted version of this list. + This method still remains proportional to the stake of the baker, and aims to + reduce variability of block distribution, especially for small bakers. (MR :gl:`!20084`) Data Availability Layer ----------------------- diff --git a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL index cd5ab26f03692b7b6e45626ea7e9ddcf52695720..b418a18d45dbbbc0bc10349b4d225fd5e146e035 100644 --- a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL +++ b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL @@ -180,6 +180,7 @@ "Shared_stake", "Delegate_consensus_key", "Delegate_storage", + "Swrr_sampler", "Delegate_sampler", "Delegate_rewards", "Consensus_parameters_storage", diff --git a/src/proto_alpha/lib_protocol/dune b/src/proto_alpha/lib_protocol/dune index 91d4bf6c99cf2d44f4e511f2571f5c255b0260bf..4949243fd34dd4ad369c6f7b72740fe727493fef 100644 --- a/src/proto_alpha/lib_protocol/dune +++ b/src/proto_alpha/lib_protocol/dune @@ -197,6 +197,7 @@ Shared_stake Delegate_consensus_key Delegate_storage + Swrr_sampler Delegate_sampler Delegate_rewards Consensus_parameters_storage @@ -499,6 +500,7 @@ shared_stake.ml shared_stake.mli delegate_consensus_key.ml delegate_consensus_key.mli delegate_storage.ml delegate_storage.mli + swrr_sampler.ml swrr_sampler.mli delegate_sampler.ml delegate_sampler.mli delegate_rewards.ml delegate_rewards.mli consensus_parameters_storage.ml consensus_parameters_storage.mli @@ -803,6 +805,7 @@ shared_stake.ml shared_stake.mli delegate_consensus_key.ml delegate_consensus_key.mli delegate_storage.ml delegate_storage.mli + swrr_sampler.ml swrr_sampler.mli delegate_sampler.ml delegate_sampler.mli delegate_rewards.ml delegate_rewards.mli consensus_parameters_storage.ml consensus_parameters_storage.mli @@ -1091,6 +1094,7 @@ shared_stake.ml shared_stake.mli delegate_consensus_key.ml delegate_consensus_key.mli delegate_storage.ml delegate_storage.mli + swrr_sampler.ml swrr_sampler.mli delegate_sampler.ml delegate_sampler.mli delegate_rewards.ml delegate_rewards.mli consensus_parameters_storage.ml consensus_parameters_storage.mli diff --git a/src/proto_alpha/lib_protocol/storage.ml b/src/proto_alpha/lib_protocol/storage.ml index 18b37fe0eee0090e30fcfbd2d84348e5cdec44e1..39345190f47a8bf34e67b8d169357910cd473308 100644 --- a/src/proto_alpha/lib_protocol/storage.ml +++ b/src/proto_alpha/lib_protocol/storage.ml @@ -396,6 +396,18 @@ module Contract = struct end)) (Make_index (Contract_repr.Index)) + module SWRR_credit = + Indexed_context.Make_map + (Registered) + (struct + let name = ["swrr_credit"] + end) + (struct + type t = Z.t + + let encoding = Data_encoding.z + end) + module Counter = Indexed_context.Make_map (Registered) @@ -1311,6 +1323,19 @@ module Cycle = struct (req "active_stake" Stake_repr.encoding))) end) + module Selected_bakers = + Indexed_context.Make_map + (Registered) + (struct + let name = ["selected_bakers"] + end) + (struct + type t = Signature.Public_key_hash.t list + + let encoding = + Data_encoding.(Variable.list Signature.Public_key_hash.encoding) + end) + module Total_active_stake = Indexed_context.Make_map (Registered) @@ -1504,6 +1529,7 @@ module Stake = struct module Selected_distribution_for_cycle = Cycle.Selected_stake_distribution module Total_active_stake = Cycle.Total_active_stake + module Selected_bakers = Cycle.Selected_bakers end type consensus_pk_in_R = Cycle.consensus_pk_in_R = { diff --git a/src/proto_alpha/lib_protocol/storage.mli b/src/proto_alpha/lib_protocol/storage.mli index 95bb6114fb510c29f10ac107cd9966790bb1c4bf..ec2958e7330634b572d0036f2abf22e0f3a37cce 100644 --- a/src/proto_alpha/lib_protocol/storage.mli +++ b/src/proto_alpha/lib_protocol/storage.mli @@ -209,6 +209,12 @@ module Contract : sig with type elt = Contract_repr.t and type t = Raw_context.t * Contract_repr.t + module SWRR_credit : + Indexed_data_storage + with type key = Contract_repr.t + and type value = Z.t + and type t := Raw_context.t + (** Tez that were part of frozen deposits (either [own_frozen] or [staked_frozen] in {!Staking_balance}) but have been requested to be unstaked by a staker. @@ -611,6 +617,12 @@ module Stake : sig and type value = (Signature.Public_key_hash.t * Stake_repr.t) list and type t := Raw_context.t + module Selected_bakers : + Indexed_data_storage + with type key = Cycle_repr.t + and type value = Signature.Public_key_hash.t list + and type t := Raw_context.t + (** Sum of the active stakes of all the delegates with {!Constants_parametric_repr.minimal_stake} *) module Total_active_stake : diff --git a/src/proto_alpha/lib_protocol/swrr_sampler.ml b/src/proto_alpha/lib_protocol/swrr_sampler.ml new file mode 100644 index 0000000000000000000000000000000000000000..adddb2ebd1998e3835aaf0c1100d2a7254fd5e1e --- /dev/null +++ b/src/proto_alpha/lib_protocol/swrr_sampler.ml @@ -0,0 +1,109 @@ +(*****************************************************************************) +(* *) +(* SPDX-License-Identifier: MIT *) +(* Copyright (c) 2025 Nomadic Labs, *) +(* *) +(*****************************************************************************) + +type credit_info = {pkh : Signature.public_key_hash; credit : Z.t; stake : Z.t} + +let select_bakers_at_cycle_end ctxt ~target_cycle = + let open Lwt_result_syntax in + let* total_stake = Stake_storage.get_total_active_stake ctxt target_cycle in + let total_stake = Z.of_int64 (Stake_repr.staking_weight total_stake) in + + let* ctxt, stakes_pkh = + Stake_storage.get_selected_distribution ctxt target_cycle + in + let blocks_per_cycle = Constants_storage.blocks_per_cycle ctxt in + let nb_slots = Int32.to_int blocks_per_cycle in + + let* init_credit_list = + List.fold_left_es + (fun acc (pkh, stake) -> + let* credit_opt = + Storage.Contract.SWRR_credit.find ctxt (Contract_repr.Implicit pkh) + in + let old_credit = Option.value ~default:Z.zero credit_opt in + let weight = Stake_repr.staking_weight stake in + let acc = + {pkh; credit = old_credit; stake = Z.of_int64 weight} :: acc + in + return acc) + [] + stakes_pkh + in + + let rec loop i (credit_list : credit_info list) + (acc : Signature.public_key_hash list) : + credit_info list * Signature.public_key_hash list = + if Compare.Int.(i >= nb_slots) then + let bakers = List.rev acc in + (credit_list, bakers) + else + (* Increase everyone's credit by their stake, and find the max *) + let best_credit_info_opt, updated_credit_list = + List.fold_left + (fun (current_best_credit_opt, updated_credit_list) + {pkh; credit; stake} + -> + let new_credit = Z.add credit stake in + let new_credit_info = {pkh; credit = new_credit; stake} in + match current_best_credit_opt with + (* First iteration, so the first credit is the best *) + | None -> (Some new_credit_info, updated_credit_list) + (* The new staker has better credit: we add the previous one to the list, and keep going. *) + | Some previous_best_credit + when Compare.Z.(new_credit > previous_best_credit.credit) -> + ( Some new_credit_info, + previous_best_credit :: updated_credit_list ) + (* The new credit is still less than the best. *) + | Some _ as x -> (x, new_credit_info :: updated_credit_list)) + (None, []) + credit_list + in + (* At this point `updated_credit_list` doesn't contain `best_credit_info_opt`, so we can simply update it and add it to the list. *) + let updated_credit_list, acc = + match best_credit_info_opt with + | None -> (updated_credit_list, acc) (* Should not happen *) + | Some ({credit; pkh; _} as best_credit_info) -> + ( {best_credit_info with credit = Z.sub credit total_stake} + :: updated_credit_list, + pkh :: acc ) + in + loop (i + 1) updated_credit_list acc + in + let new_credits, selected_bakers = loop 0 init_credit_list [] in + (* update context *) + let*! ctxt = + Storage.Stake.Selected_bakers.add ctxt target_cycle selected_bakers + in + let* ctxt = + List.fold_left_es + (fun ctxt {pkh; credit; _} -> + Storage.Contract.SWRR_credit.update + ctxt + (Contract_repr.Implicit pkh) + credit) + ctxt + new_credits + in + return ctxt + +let get_baker ctxt level round = + let open Lwt_result_syntax in + let cycle = level.Level_repr.cycle in + let pos = level.Level_repr.cycle_position in + let*? round_int = Round_repr.to_int round in + + let* selected_bakers = Storage.Stake.Selected_bakers.get ctxt cycle in + let len = List.length selected_bakers in + let idx = (Int32.to_int pos + (3 * round_int)) mod len in + + match List.nth_opt selected_bakers idx with + | None -> + assert + false (* should not happen if select_bakers_at_cycle_end is correct *) + | Some pkh -> + let* pk = Delegate_consensus_key.active_pubkey ctxt pkh in + return (ctxt, pk) diff --git a/src/proto_alpha/lib_protocol/swrr_sampler.mli b/src/proto_alpha/lib_protocol/swrr_sampler.mli new file mode 100644 index 0000000000000000000000000000000000000000..93284f82a74f21721ce42a98d4325b1896078352 --- /dev/null +++ b/src/proto_alpha/lib_protocol/swrr_sampler.mli @@ -0,0 +1,18 @@ +(*****************************************************************************) +(* *) +(* SPDX-License-Identifier: MIT *) +(* Copyright (c) 2025 Nomadic Labs, *) +(* *) +(*****************************************************************************) + +(** [select_bakers_at_cycle_end ctxt ~target_cycle] called to select the bakers at the end of a cycle + and it will precompute the list of round 0 bakers for the [target_cycle]. +*) +val select_bakers_at_cycle_end : + Raw_context.t -> target_cycle:Cycle_repr.t -> Raw_context.t tzresult Lwt.t + +val get_baker : + Raw_context.t -> + Level_repr.t -> + Round_repr.round -> + (Raw_context.t * Delegate_consensus_key.pk) tzresult Lwt.t