diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index e11b723cb0305bac58a6e7ed08af5c5500bf19f0..8190c6c0a56bdebc4de5c23672448e7109c8bcb4 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2782,10 +2782,9 @@ module Dal : sig val expected_size_in_bits : max_index:Slot_index.t -> int - val shards_of_attester : - context -> attester:public_key_hash -> shard_index list option + val power_of_attester : context -> attester:public_key_hash -> int option - val record_attested_shards : context -> t -> int list -> context + val record_number_of_attested_shards : context -> t -> int -> context type committee = { pkh_to_shards : (shard_index * int) Signature.Public_key_hash.Map.t; diff --git a/src/proto_alpha/lib_protocol/dal_apply.ml b/src/proto_alpha/lib_protocol/dal_apply.ml index ee1a82bfb95497cd7cb94c6717eca696126284cb..4ea774778029370577824613745075c77af6a05b 100644 --- a/src/proto_alpha/lib_protocol/dal_apply.ml +++ b/src/proto_alpha/lib_protocol/dal_apply.ml @@ -67,7 +67,7 @@ let validate_block_attestation ctxt level consensus_key attestation = in let attester = pkh_of_consensus_key consensus_key in fail_when - (Option.is_none @@ Dal.Attestation.shards_of_attester ctxt ~attester) + (Option.is_none @@ Dal.Attestation.power_of_attester ctxt ~attester) (Dal_data_availibility_attester_not_in_committee {attester; level}) let validate_mempool_attestation ctxt attestation = @@ -85,12 +85,16 @@ let apply_attestation ctxt consensus_key level attestation = let open Result_syntax in let* () = assert_dal_feature_enabled ctxt in let attester = pkh_of_consensus_key consensus_key in - match Dal.Attestation.shards_of_attester ctxt ~attester with + match Dal.Attestation.power_of_attester ctxt ~attester with | None -> (* This should not happen: operation validation should have failed. *) error (Dal_data_availibility_attester_not_in_committee {attester; level}) - | Some shards -> - return (Dal.Attestation.record_attested_shards ctxt attestation shards) + | Some power -> + return + (Dal.Attestation.record_number_of_attested_shards + ctxt + attestation + power) (* This function should fail if we don't want the operation to be propagated over the L1 gossip network. Because this is a manager diff --git a/src/proto_alpha/lib_protocol/dal_attestation_repr.ml b/src/proto_alpha/lib_protocol/dal_attestation_repr.ml index 43688eb26a6ca9d8c1a1e403389a155552feb633..920e04d7da5c538073280427030a9d51c463aee4 100644 --- a/src/proto_alpha/lib_protocol/dal_attestation_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_attestation_repr.ml @@ -91,50 +91,51 @@ end) module Accountability = struct type attested_slots = t - (* DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3109 - - Think hard about this data structure and whether it needs to be - optimized. - *) - - (* A list of set of shard indexes (a set of shards per slot) *) - type t = Bitset.t list - - let init ~length = - let l = - List.init - ~when_negative_length: - "Dal_attestation_repr.Accountability.init: length cannot be negative" - length - (fun _ -> Bitset.empty) + module SlotMap = Map.Make (Compare.Int) + + type t = {number_of_attested_shards : int SlotMap.t; number_of_slots : int} + + let init ~number_of_slots = + {number_of_attested_shards = SlotMap.empty; number_of_slots} + + (* This function must be called at most once for a given attester; otherwise + the count will be flawed. *) + let record_number_of_attested_shards t baker_attested_slots + number_of_baker_shards = + let rec iter slot_index map = + if Compare.Int.(slot_index >= t.number_of_slots) then map + else + let map = + match Bitset.mem baker_attested_slots slot_index with + | Error _ -> + (* impossible, as [slot_index] is non-negative *) + map + | Ok true -> + (* slot is attested by baker *) + SlotMap.update + slot_index + (function + | None -> Some number_of_baker_shards + | Some old_number_of_attested_shards -> + Some + (old_number_of_attested_shards + number_of_baker_shards)) + map + | Ok false -> + (* slot is not attested by baker, nothing to update *) + map + in + iter (slot_index + 1) map in - match l with Error msg -> invalid_arg msg | Ok l -> l - - let record_slot_shard_availability bitset shards = - List.fold_left - (fun bitset shard -> - Bitset.add bitset shard |> Result.value ~default:bitset) - bitset - shards - - let record_attested_shards shard_bitset_per_slot attested_slots shards = - List.mapi - (fun slot bitset -> - match Bitset.mem attested_slots slot with - | Error _ -> - (* slot index is above the length provided at initialisation *) - bitset - | Ok slot_attested -> - if slot_attested then record_slot_shard_availability bitset shards - else bitset) - shard_bitset_per_slot - - let is_slot_attested shard_bitset_per_slot ~threshold ~number_of_shards index - = - match List.nth shard_bitset_per_slot (Dal_slot_index_repr.to_int index) with - | None -> false - | Some bitset -> - let number_of_attested_shards = Bitset.hamming_weight bitset in - Compare.Int.( - number_of_attested_shards >= threshold * number_of_shards / 100) + let number_of_attested_shards = iter 0 t.number_of_attested_shards in + {t with number_of_attested_shards} + + let is_slot_attested t ~threshold ~number_of_shards slot_index = + let index = Dal_slot_index_repr.to_int slot_index in + let number_of_attested_shards = + match SlotMap.find index t.number_of_attested_shards with + | None -> 0 + | Some v -> v + in + Compare.Int.( + number_of_attested_shards >= threshold * number_of_shards / 100) end diff --git a/src/proto_alpha/lib_protocol/dal_attestation_repr.mli b/src/proto_alpha/lib_protocol/dal_attestation_repr.mli index 20f45a10a1f666dd946ec200b28787282cb089f1..a9edc93ac34c401191bc219e44ccc5fc49ef9290 100644 --- a/src/proto_alpha/lib_protocol/dal_attestation_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_attestation_repr.mli @@ -97,24 +97,23 @@ module Accountability : sig Consider using the [Bounded] module. In particular, change the semantics of [is_slot_attested] accordingly. *) - (** [init ~length] initialises a new accountability data-structure - with at most [length] slots and where for every slot, no shard is + (** [init ~number_of_slots] initialises a new accountability data-structure + with [number_of_slots] slots and where for every slot, no shard is available. *) - val init : length:int -> t - - (** [record_attested_shards t slots shards] records that for all - slots declared available in [slots], the shard indices in [shards] - are deemed available. It is the responsibility of the caller to ensure - the shard indices are positive numbers. A negative shard index is - ignored. *) - val record_attested_shards : t -> attested_slots -> shard_index list -> t - - (** [is_slot_attested t ~threshold ~number_of_shards slot] returns - [true] if the number of shards recorded in [t] for the [slot] is - above the [threshold] with respect to the total number of shards - specified by [number_of_shards]. Returns [false] otherwise or if - the [index] is out of the interval [0;length] where [length] is - the value provided to the [init] function. *) + val init : number_of_slots:int -> t + + (** [record_number_of_attested_shards t slots number] records that, for all + slots declared available in [slots], the given [number] of shard indices + are deemed available. This function must be called at most once for a + given attester; otherwise the count will be flawed. *) + val record_number_of_attested_shards : t -> attested_slots -> int -> t + + (** [is_slot_attested t ~threshold ~number_of_shards slot] returns [true] if + the number of shards recorded in [t] for the [slot] is above the + [threshold] with respect to the total number of shards specified by + [number_of_shards]. Returns [false] otherwise or if the [index] is out of + the interval [0; number_of_slots - 1] where [number_of_slots] is the value + provided to the [init] function. *) val is_slot_attested : t -> threshold:int -> number_of_shards:int -> Dal_slot_index_repr.t -> bool end diff --git a/src/proto_alpha/lib_protocol/raw_context.ml b/src/proto_alpha/lib_protocol/raw_context.ml index 48a1358402c0a6f320e3084b8a00a978e6fa74d3..b0fe9d38b8fcdb384cd66da7d8a591814f580ccc 100644 --- a/src/proto_alpha/lib_protocol/raw_context.ml +++ b/src/proto_alpha/lib_protocol/raw_context.ml @@ -881,7 +881,8 @@ let prepare ~level ~predecessor_timestamp ~timestamp ~adaptive_issuance_enable ~length:constants.Constants_parametric_repr.dal.number_of_slots; dal_attestation_slot_accountability = Dal_attestation_repr.Accountability.init - ~length:constants.Constants_parametric_repr.dal.number_of_slots; + ~number_of_slots: + constants.Constants_parametric_repr.dal.number_of_slots; dal_committee = empty_dal_committee; dal_cryptobox = None; adaptive_issuance_enable; @@ -1828,12 +1829,12 @@ module Dal = struct let number_of_slots ctxt = ctxt.back.constants.dal.number_of_slots - let record_attested_shards ctxt attestation shards = + let record_number_of_attested_shards ctxt attestation number = let dal_attestation_slot_accountability = - Dal_attestation_repr.Accountability.record_attested_shards + Dal_attestation_repr.Accountability.record_number_of_attested_shards ctxt.back.dal_attestation_slot_accountability attestation - shards + number in {ctxt with back = {ctxt.back with dal_attestation_slot_accountability}} @@ -1955,15 +1956,11 @@ module Dal = struct let init_committee ctxt committee = {ctxt with back = {ctxt.back with dal_committee = committee}} - let shards_of_attester ctxt ~attester: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 + let power_of_attester ctxt ~attester:pkh = Signature.Public_key_hash.Map.find_opt pkh ctxt.back.dal_committee.pkh_to_shards - |> Option.map (fun pre_shards -> make [] pre_shards) + |> Option.map snd 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 d6494485dd963a99a2e7a28b3ee8acc7201c73c8..a6fc18439b4f940849481eb9cfd373adb6707174 100644 --- a/src/proto_alpha/lib_protocol/raw_context.mli +++ b/src/proto_alpha/lib_protocol/raw_context.mli @@ -433,12 +433,10 @@ module Dal : sig val number_of_slots : t -> int - (** [record_attested_shards ctxt attestation shards] records that the - list of shards [shards] were attested (declared available by some - attester). The function assumes that a shard belongs to the - interval [0; number_of_shards - 1]. Otherwise, for each shard - outside this interval, it is a no-op. *) - val record_attested_shards : t -> Dal_attestation_repr.t -> int list -> t + (** [record_number_of_attested_shards ctxt attestation number_of_shards] + records that the [number_of_shards] shards were attested (declared + available by some attester). *) + val record_number_of_attested_shards : t -> Dal_attestation_repr.t -> int -> t (** [register_slot_header ctxt slot_header] returns a new context where the new candidate [slot] have been taken into @@ -458,11 +456,11 @@ module Dal : sig [0;number_of_slots - 1], returns [false]. *) val is_slot_index_attested : t -> Dal_slot_index_repr.t -> bool - (** [shards_of_attester ctxt ~attester] returns the shard assignment - of the DAL committee of the current level for [attester]. This - function never returns an empty list. *) - val shards_of_attester : - t -> attester:Signature.Public_key_hash.t -> int list option + (** [power_of_attester ctxt ~attester] returns the number of shards assigned + to [attester] at the current level. It never returns [Some 0]. Instead, it + returns [None] if the attester is not in the DAL committee. *) + val power_of_attester : + t -> attester:Signature.Public_key_hash.t -> int option (** The DAL committee is a subset of the Tenderbake committee. A shard from [0; number_of_shards - 1] is associated to a public key diff --git a/src/proto_alpha/lib_protocol/test/integration/consensus/test_attestation.ml b/src/proto_alpha/lib_protocol/test/integration/consensus/test_attestation.ml index 3d41a37340b9a61aadc055e7d12afd86394060b6..d3d30db6a04bf9869c61befa9f52b3ee0d4128fc 100644 --- a/src/proto_alpha/lib_protocol/test/integration/consensus/test_attestation.ml +++ b/src/proto_alpha/lib_protocol/test/integration/consensus/test_attestation.ml @@ -760,6 +760,65 @@ let test_attester_not_in_dal_committee () = let* _ = iter b 0 in return_unit +let test_dal_attestation_threshold () = + let open Lwt_result_wrap_syntax in + let n = 100 in + let* genesis, contracts = Context.init_n n ~consensus_threshold:0 () in + let contract = Stdlib.List.hd contracts in + let* { + parametric = + { + dal = + { + attestation_lag; + attestation_threshold; + cryptobox_parameters = {number_of_shards; _}; + _; + }; + _; + }; + _; + } = + Context.get_constants (B genesis) + in + let slot_index = Dal.Slot_index.zero in + let commitment = Alpha_context.Dal.Slot.Commitment.zero in + let commitment_proof = Alpha_context.Dal.Slot.Commitment_proof.zero in + let slot_header = + Dal.Operations.Publish_commitment.{slot_index; commitment; commitment_proof} + in + let* op = Op.dal_publish_commitment (B genesis) contract slot_header in + let* b = Block.bake genesis ~operation:op in + let* b = Block.bake_n (attestation_lag - 1) b in + let* dal_committee = Context.Dal.shards (B b) () in + let attestation = Dal.Attestation.commit Dal.Attestation.empty slot_index in + let dal_content = {attestation} in + let min_power = attestation_threshold * number_of_shards / 100 in + Log.info "Number of minimum required attested shards: %d" min_power ; + let* _ = + List.fold_left_es + (fun (acc_ops, acc_power) (pkh, (_first_index, power)) -> + let* op = Op.attestation ~delegate:pkh ~dal_content b in + let ops = op :: acc_ops in + let power = acc_power + power in + let* _b, (metadata, _ops) = + Block.bake_with_metadata ~operations:ops b + in + let attested_expected = power >= min_power in + let attested = + Dal.Attestation.is_attested metadata.dal_attestation slot_index + in + Log.info "With %d power, the slot is attested: %b " power attested ; + Check.(attested = attested_expected) + Check.bool + ~error_msg: + "Unexpected attestation status for slot 0: got %L, expected %R " ; + return (ops, power)) + ([], 0) + dal_committee + in + return_unit + let tests = [ (* Positive tests *) @@ -819,6 +878,10 @@ let tests = "attester not in DAL committee" `Quick test_attester_not_in_dal_committee; + Tztest.tztest + "DAL attestation_threshold" + `Quick + test_dal_attestation_threshold; ] let () =