From 32352cc34d99a0dfcbbd6c37b791d48bf4c01b37 Mon Sep 17 00:00:00 2001 From: Eugen Zalinescu Date: Tue, 10 Dec 2024 21:19:57 +0100 Subject: [PATCH 1/3] DAL/Crypto: add Trap module --- src/lib_crypto_dal/trap.ml | 46 +++++++++++++++++++++++++++++++++++++ src/lib_crypto_dal/trap.mli | 32 ++++++++++++++++++++++++++ 2 files changed, 78 insertions(+) create mode 100644 src/lib_crypto_dal/trap.ml create mode 100644 src/lib_crypto_dal/trap.mli diff --git a/src/lib_crypto_dal/trap.ml b/src/lib_crypto_dal/trap.ml new file mode 100644 index 000000000000..e16df6d9c819 --- /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 000000000000..06ce7207b3fb --- /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 -- GitLab From f1bb031e8c545578cd193d0c61136561078110c0 Mon Sep 17 00:00:00 2001 From: Eugen Zalinescu Date: Wed, 11 Dec 2024 17:36:54 +0100 Subject: [PATCH 2/3] Env: expose Dal.share_is_trap function --- src/lib_protocol_environment/environment_V14.ml | 7 +++++++ src/lib_protocol_environment/sigs/v14.ml | 6 ++++++ src/lib_protocol_environment/sigs/v14/dal.mli | 6 ++++++ 3 files changed, 19 insertions(+) diff --git a/src/lib_protocol_environment/environment_V14.ml b/src/lib_protocol_environment/environment_V14.ml index a550eaf2227c..2641ed79ab85 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 59d033c61e99..646a1f2d647d 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 77014baac50c..ca18be9d83b1 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 -- GitLab From 75df436ca5844310cfe04b5a134cb6ce96513b62 Mon Sep 17 00:00:00 2001 From: Eugen Zalinescu Date: Wed, 11 Dec 2024 18:12:27 +0100 Subject: [PATCH 3/3] DAL/Alpha: expose share_is_trap --- .../lib_protocol/alpha_context.mli | 6 +++++ src/proto_alpha/lib_protocol/dal_slot_repr.ml | 23 ++++++++++++++++ .../lib_protocol/dal_slot_repr.mli | 27 +++++++++++++++++++ 3 files changed, 56 insertions(+) diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index df2f28456d6a..56d9a7883520 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 ba38d541a24e..a86489112f8d 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 925b06ce9368..f80275a69a99 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 -- GitLab