From 79f4807ba9d32fa9206550c82004e9000ed203b3 Mon Sep 17 00:00:00 2001 From: Olha Nemkovych Date: Fri, 21 Nov 2025 13:44:10 +0100 Subject: [PATCH 1/6] Proto: adding empty SWRR sampler module --- src/proto_alpha/lib_protocol/TEZOS_PROTOCOL | 1 + src/proto_alpha/lib_protocol/dune | 4 ++++ src/proto_alpha/lib_protocol/swrr_sampler.ml | 6 ++++++ src/proto_alpha/lib_protocol/swrr_sampler.mli | 6 ++++++ 4 files changed, 17 insertions(+) create mode 100644 src/proto_alpha/lib_protocol/swrr_sampler.ml create mode 100644 src/proto_alpha/lib_protocol/swrr_sampler.mli diff --git a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL index cd5ab26f0369..b418a18d45db 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 91d4bf6c99cf..4949243fd34d 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/swrr_sampler.ml b/src/proto_alpha/lib_protocol/swrr_sampler.ml new file mode 100644 index 000000000000..fba29ef90100 --- /dev/null +++ b/src/proto_alpha/lib_protocol/swrr_sampler.ml @@ -0,0 +1,6 @@ +(*****************************************************************************) +(* *) +(* SPDX-License-Identifier: MIT *) +(* Copyright (c) 2025 Nomadic Labs, *) +(* *) +(*****************************************************************************) \ No newline at end of file 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 000000000000..fba29ef90100 --- /dev/null +++ b/src/proto_alpha/lib_protocol/swrr_sampler.mli @@ -0,0 +1,6 @@ +(*****************************************************************************) +(* *) +(* SPDX-License-Identifier: MIT *) +(* Copyright (c) 2025 Nomadic Labs, *) +(* *) +(*****************************************************************************) \ No newline at end of file -- GitLab From ad0e58d436ed4de246c992c2bc8d0d519c9c3666 Mon Sep 17 00:00:00 2001 From: Lucas Randazzo Date: Fri, 21 Nov 2025 14:18:38 +0100 Subject: [PATCH 2/6] Proto: SWRR storage --- src/proto_alpha/lib_protocol/storage.ml | 26 ++++++++++++++++++++++++ src/proto_alpha/lib_protocol/storage.mli | 12 +++++++++++ 2 files changed, 38 insertions(+) diff --git a/src/proto_alpha/lib_protocol/storage.ml b/src/proto_alpha/lib_protocol/storage.ml index 18b37fe0eee0..39345190f47a 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 95bb6114fb51..ec2958e73306 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 : -- GitLab From 515e9ee7fc57f3041b999f4b1af0f736c353ce9b Mon Sep 17 00:00:00 2001 From: Olha Nemkovych Date: Fri, 21 Nov 2025 16:57:23 +0100 Subject: [PATCH 3/6] Proto: implementation select_bakers_at_cycle_end --- src/proto_alpha/lib_protocol/swrr_sampler.ml | 77 ++++++++++++++++++- src/proto_alpha/lib_protocol/swrr_sampler.mli | 14 +++- 2 files changed, 89 insertions(+), 2 deletions(-) diff --git a/src/proto_alpha/lib_protocol/swrr_sampler.ml b/src/proto_alpha/lib_protocol/swrr_sampler.ml index fba29ef90100..7e624b9ec5fe 100644 --- a/src/proto_alpha/lib_protocol/swrr_sampler.ml +++ b/src/proto_alpha/lib_protocol/swrr_sampler.ml @@ -3,4 +3,79 @@ (* SPDX-License-Identifier: MIT *) (* Copyright (c) 2025 Nomadic Labs, *) (* *) -(*****************************************************************************) \ No newline at end of file +(*****************************************************************************) + +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 rec loop i ctxt acc = + if Compare.Int.(i >= nb_slots) then + let bakers = List.rev acc in + let*! raw_ctxt = + Storage.Stake.Selected_bakers.add ctxt target_cycle bakers + in + return raw_ctxt + else + let* ctxt, best_pkh_opt, updated_rev = + List.fold_left_es + (fun (ctxt, best_opt, 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 new_credit = Z.add old_credit (Z.of_int64 weight) in + (* TO DO change from Int64 to Z *) + + let best_opt = + match best_opt with + | None -> Some (pkh, new_credit) + | Some (_best_pkh, best_credit) + when Compare.Z.(new_credit > best_credit) -> + Some (pkh, new_credit) + | Some _ as x -> x + in + let acc = (pkh, new_credit) :: acc in + return (ctxt, best_opt, acc)) + (ctxt, None, []) + stakes_pkh + in + let best_pkh, best_credit, updated = + match best_pkh_opt with + | Some (pkh, credit) -> + let updated = List.rev updated_rev in + (pkh, credit, updated) + | None -> assert false + (* only happens if stakes_pkh is empty, which shouldn't happen *) + in + let winner_credit = Z.sub best_credit total_stake in + + let* ctxt = + List.fold_left_es + (fun ctxt (pkh, credit) -> + let credit = + if Signature.Public_key_hash.equal pkh best_pkh then winner_credit + else credit + in + Storage.Contract.SWRR_credit.update + ctxt + (Contract_repr.Implicit pkh) + credit) + ctxt + updated + in + loop (i + 1) ctxt (best_pkh :: acc) + in + loop 0 ctxt [] + +let get_baker _ _ _ = assert false (* TO DO *) diff --git a/src/proto_alpha/lib_protocol/swrr_sampler.mli b/src/proto_alpha/lib_protocol/swrr_sampler.mli index fba29ef90100..93284f82a74f 100644 --- a/src/proto_alpha/lib_protocol/swrr_sampler.mli +++ b/src/proto_alpha/lib_protocol/swrr_sampler.mli @@ -3,4 +3,16 @@ (* SPDX-License-Identifier: MIT *) (* Copyright (c) 2025 Nomadic Labs, *) (* *) -(*****************************************************************************) \ No newline at end of file +(*****************************************************************************) + +(** [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 -- GitLab From 01018a45f8e83e0f8071d9ef8ef8871d143a991f Mon Sep 17 00:00:00 2001 From: Olha Nemkovych Date: Fri, 28 Nov 2025 11:44:36 +0100 Subject: [PATCH 4/6] Proto: optimized swrr iteration --- src/proto_alpha/lib_protocol/swrr_sampler.ml | 120 ++++++++++--------- 1 file changed, 66 insertions(+), 54 deletions(-) diff --git a/src/proto_alpha/lib_protocol/swrr_sampler.ml b/src/proto_alpha/lib_protocol/swrr_sampler.ml index 7e624b9ec5fe..bebc437b9350 100644 --- a/src/proto_alpha/lib_protocol/swrr_sampler.ml +++ b/src/proto_alpha/lib_protocol/swrr_sampler.ml @@ -5,6 +5,8 @@ (* *) (*****************************************************************************) +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 @@ -16,66 +18,76 @@ let select_bakers_at_cycle_end ctxt ~target_cycle = let blocks_per_cycle = Constants_storage.blocks_per_cycle ctxt in let nb_slots = Int32.to_int blocks_per_cycle in - let rec loop i ctxt acc = + 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 - let*! raw_ctxt = - Storage.Stake.Selected_bakers.add ctxt target_cycle bakers - in - return raw_ctxt + (credit_list, bakers) else - let* ctxt, best_pkh_opt, updated_rev = - List.fold_left_es - (fun (ctxt, best_opt, 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 new_credit = Z.add old_credit (Z.of_int64 weight) in - (* TO DO change from Int64 to Z *) - - let best_opt = - match best_opt with - | None -> Some (pkh, new_credit) - | Some (_best_pkh, best_credit) - when Compare.Z.(new_credit > best_credit) -> - Some (pkh, new_credit) - | Some _ as x -> x - in - let acc = (pkh, new_credit) :: acc in - return (ctxt, best_opt, acc)) - (ctxt, None, []) - stakes_pkh + (* 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 - let best_pkh, best_credit, updated = - match best_pkh_opt with - | Some (pkh, credit) -> - let updated = List.rev updated_rev in - (pkh, credit, updated) - | None -> assert false - (* only happens if stakes_pkh is empty, which shouldn't happen *) + (* 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 - let winner_credit = Z.sub best_credit total_stake in - - let* ctxt = - List.fold_left_es - (fun ctxt (pkh, credit) -> - let credit = - if Signature.Public_key_hash.equal pkh best_pkh then winner_credit - else credit - in - Storage.Contract.SWRR_credit.update - ctxt - (Contract_repr.Implicit pkh) - credit) + 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 - updated - in - loop (i + 1) ctxt (best_pkh :: acc) + (Contract_repr.Implicit pkh) + credit) + ctxt + new_credits in - loop 0 ctxt [] + return ctxt let get_baker _ _ _ = assert false (* TO DO *) -- GitLab From 917b2498ea8b29f47bd39a6cc592c20a435b20b2 Mon Sep 17 00:00:00 2001 From: Olha Nemkovych Date: Fri, 28 Nov 2025 12:18:20 +0100 Subject: [PATCH 5/6] Proto: implement get_baker swrr --- src/proto_alpha/lib_protocol/swrr_sampler.ml | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-) diff --git a/src/proto_alpha/lib_protocol/swrr_sampler.ml b/src/proto_alpha/lib_protocol/swrr_sampler.ml index bebc437b9350..adddb2ebd199 100644 --- a/src/proto_alpha/lib_protocol/swrr_sampler.ml +++ b/src/proto_alpha/lib_protocol/swrr_sampler.ml @@ -90,4 +90,20 @@ let select_bakers_at_cycle_end ctxt ~target_cycle = in return ctxt -let get_baker _ _ _ = assert false (* TO DO *) +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) -- GitLab From 2a6d4a04380103aac5576e8a25c000bc3d67f29d Mon Sep 17 00:00:00 2001 From: Lucas Randazzo Date: Fri, 28 Nov 2025 14:58:24 +0100 Subject: [PATCH 6/6] Docs: update changelog --- docs/protocols/alpha.rst | 11 +++++++++++ 1 file changed, 11 insertions(+) diff --git a/docs/protocols/alpha.rst b/docs/protocols/alpha.rst index f4451c3e0424..af8f42ff2682 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 ----------------------- -- GitLab