diff --git a/src/lib_crypto_dal/trap.ml b/src/lib_crypto_dal/trap.ml new file mode 100644 index 0000000000000000000000000000000000000000..e16df6d9c819da4071e717fda5690cd5fde6c9d0 --- /dev/null +++ b/src/lib_crypto_dal/trap.ml @@ -0,0 +1,46 @@ +(*****************************************************************************) +(* *) +(* SPDX-License-Identifier: MIT *) +(* SPDX-FileCopyrightText: 2024 Nomadic Labs, *) +(* *) +(*****************************************************************************) + +module Dal_share_hash = struct + module H = + Tezos_crypto.Blake2B.Make + (Tezos_crypto.Base58) + (struct + let name = "pkh_and_dal_share_hash" + + let title = "A hash of a pkh and a DAL share" + + let b58check_prefix = "\077\167\043" (* shh(53) for "share hash" *) + + let size = Some 32 + end) + + include H +end + +let two_to_hash_size = Z.(shift_left one Dal_share_hash.size) + +(* This function checks that `hash(delegate . share) < trap_rate * 2^|hash|`, + where the dot denotes concatenation and |v| the length of the bitstring v. *) +let share_is_trap delegate share ~(traps_fraction : Q.t) = + let open Error_monad.Result_syntax in + let* pkh_bytes = + Data_encoding.Binary.to_bytes + Tezos_crypto.Signature.Public_key_hash.encoding + delegate + in + let+ share_bytes = + Data_encoding.Binary.to_bytes Cryptobox.share_encoding share + in + let hash = + Dal_share_hash.(hash_bytes [pkh_bytes; share_bytes] |> to_bytes) + |> Bytes.to_string |> Z.of_bits + in + let threshold = + two_to_hash_size |> Q.of_bigint |> Q.mul traps_fraction |> Q.to_bigint + in + Z.leq hash threshold diff --git a/src/lib_crypto_dal/trap.mli b/src/lib_crypto_dal/trap.mli new file mode 100644 index 0000000000000000000000000000000000000000..06ce7207b3fbddc9ba3b6adae9e7c4ed825d7e9a --- /dev/null +++ b/src/lib_crypto_dal/trap.mli @@ -0,0 +1,32 @@ +(*****************************************************************************) +(* *) +(* SPDX-License-Identifier: MIT *) +(* SPDX-FileCopyrightText: 2024 Nomadic Labs, *) +(* *) +(*****************************************************************************) + +(** [share_is_trap pkh share ~traps_fraction] determines whether the given + [share] is classified as a "trap" for the delegate identified by [pkh], + based on the fraction [traps_fraction] of shards that should be traps. + + The function computes the hash of the concatenation of [pkh] and [share], + denoted as `hash(pkh . share)`, where the dot represents concatenation. + It then checks if this hash value is less than `trap_rate * 2^n`, where + `n` is the (fixed) bit size of the hash. + + The function returns: + + - [Ok true] if the share is considered a trap for the given [pkh]. + + - [Ok false] if the share is not a trap. + + - [Error write_error] if there is an issue encoding [pkh] or [share]. + + This function assumes [trap_rate] is valid (i.e., a rational number within + [0, 1]). +*) +val share_is_trap : + Tezos_crypto.Signature.Public_key_hash.t -> + Cryptobox.share -> + traps_fraction:Q.t -> + (bool, Data_encoding.Binary.write_error) result diff --git a/src/lib_protocol_environment/environment_V14.ml b/src/lib_protocol_environment/environment_V14.ml index a550eaf2227c7fa9d5be63046a19503827d0628b..2641ed79ab8542eaa7f976abf24c8347e6ff5958 100644 --- a/src/lib_protocol_environment/environment_V14.ml +++ b/src/lib_protocol_environment/environment_V14.ml @@ -1587,6 +1587,13 @@ struct | Error (`Invalid_page | `Invalid_degree_strictly_less_than_expected _) -> Ok false | Ok () -> Ok true + + let share_is_trap delegate share ~traps_fraction = + match + Tezos_crypto_dal.Trap.share_is_trap delegate share ~traps_fraction + with + | Error _e -> Error `Decoding_error + | Ok b -> Ok b end module Skip_list = Skip_list diff --git a/src/lib_protocol_environment/sigs/v14.ml b/src/lib_protocol_environment/sigs/v14.ml index 59d033c61e99453958e6ee9e996c2eb041ee8efd..646a1f2d647df68002d2754fa8d1eca542ebc798 100644 --- a/src/lib_protocol_environment/sigs/v14.ml +++ b/src/lib_protocol_environment/sigs/v14.ml @@ -12473,6 +12473,12 @@ val verify_shard : | `Shard_length_mismatch | `Shard_index_out_of_range of string ] ) Result.t + +val share_is_trap : + Signature.Public_key_hash.t -> + share -> + traps_fraction:Q.t -> + (bool, [> `Decoding_error]) Result.t end # 140 "v14.in.ml" diff --git a/src/lib_protocol_environment/sigs/v14/dal.mli b/src/lib_protocol_environment/sigs/v14/dal.mli index 77014baac50c4e5c39228d09ee5b4c2053f453a0..ca18be9d83b1feab3db8f4cb9cb513bb18a2b27a 100644 --- a/src/lib_protocol_environment/sigs/v14/dal.mli +++ b/src/lib_protocol_environment/sigs/v14/dal.mli @@ -141,3 +141,9 @@ val verify_shard : | `Shard_length_mismatch | `Shard_index_out_of_range of string ] ) Result.t + +val share_is_trap : + Signature.Public_key_hash.t -> + share -> + traps_fraction:Q.t -> + (bool, [> `Decoding_error]) Result.t diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index df2f28456d6a336d27e1707bad1e2b96f0296090..56d9a7883520392f8160d4b475f47bd8a53a5f04 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -2924,6 +2924,12 @@ module Dal : sig type t = {shard : Dal.shard; proof : Dal.shard_proof} val verify : cryptobox -> Slot.Commitment.t -> t -> unit tzresult + + val share_is_trap : + Signature.Public_key_hash.t -> + Dal.share -> + traps_fraction:Q.t -> + bool tzresult end module Operations : sig diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index ba38d541a24e814878a4020123aa6c1801c7f40f..a86489112f8db41cc4bb5b1ca557e885feba90f4 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -167,6 +167,29 @@ module Shard_with_proof = struct fail_with_error_msg "Shard_length_mismatch" | Error (`Shard_index_out_of_range str) -> fail_with_error_msg ("Shard_index_out_of_range (" ^ str ^ ")") + + type error += Dal_encoding_error_in_share_is_trap + + let () = + let open Data_encoding in + let description = + "An encoding error occurred while checking whether a shard is a trap." + in + register_error_kind + `Permanent + ~id:"dal_slot_repr.shard_with_proof.share_is_trap_error" + ~title:"encoding error in Dal.share_is_trap" + ~description + ~pp:(fun ppf () -> Format.fprintf ppf "%s" description) + unit + (function Dal_encoding_error_in_share_is_trap -> Some () | _ -> None) + (fun () -> Dal_encoding_error_in_share_is_trap) + + let share_is_trap delegate share ~traps_fraction = + let open Result_syntax in + match Dal.share_is_trap delegate share ~traps_fraction with + | Ok res -> return res + | Error `Decoding_error -> error Dal_encoding_error_in_share_is_trap end module Page = struct diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli index 925b06ce936844479360492ab1dde73679f9e422..f80275a69a996bd8b264581fd71d67cc270437fb 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli @@ -146,6 +146,33 @@ module Shard_with_proof : sig the shard in [t] and the provided [commitment]. Returns [Dal_shard_proof_error] if the verification fails. *) val verify : Dal.t -> Commitment.t -> t -> unit tzresult + + (** [share_is_trap pkh share ~traps_fraction] determines whether the given + [share] is classified as a "trap" for the delegate identified by [pkh], + based on the fraction [traps_fraction] of shards that should be traps. + + The function computes the hash of the concatenation of [pkh] and [share], + denoted as `hash(pkh . share)`, where the dot represents concatenation. + It then checks if this hash value is less than `traps_fraction * 2^n`, where + `n` is the (fixed) bit size of the hash. + + The function returns: + + - [Ok true] if the share is considered a trap for the given [pkh]. + + - [Ok false] if the share is not a trap. + + - [Error Dal_encoding_error_in_share_is_trap] if there is an issue encoding + [pkh] or [share]. + + This function assumes [traps_fraction] is valid (i.e., a rational number within + [0, 1]). +*) + val share_is_trap : + Signature.Public_key_hash.t -> + Dal.share -> + traps_fraction:Q.t -> + bool tzresult end (** A DAL slot is decomposed to a successive list of pages with fixed content