From 6ce728946522f4ec249ca5ad22db901ce58d8c98 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Wed, 22 Feb 2023 13:27:02 +0100 Subject: [PATCH 1/4] DAL/crypto: commit returns an error --- src/bin_dal_node/RPC_server.ml | 9 ++- src/bin_dal_node/slot_manager.ml | 34 ++++++++- src/bin_dal_node/slot_manager_legacy.ml | 31 +++++++- src/lib_crypto_dal/cryptobox.ml | 40 ++++++++--- src/lib_crypto_dal/cryptobox.mli | 72 +++++++++++++++---- src/lib_crypto_dal/cryptobox_intf.ml | 47 ++++++++---- src/lib_crypto_dal/test/test_dal_cryptobox.ml | 15 ++-- src/lib_dal_node/test/test_lib_dal_node.ml | 14 +++- .../environment_V7.ml | 3 +- .../environment_V8.ml | 3 +- .../environment_V9.ml | 3 +- .../lib_protocol/test/helpers/dal_helpers.ml | 27 ++++++- .../lib_sc_rollup_node/refutation_game.ml | 9 ++- .../lib_protocol/test/helpers/dal_helpers.ml | 30 +++++++- .../lib_protocol/test/helpers/dal_helpers.mli | 6 ++ .../test/pbt/test_dal_slot_proof.ml | 2 +- .../lib_sc_rollup_node/refutation_game.ml | 9 ++- tezt/lib_tezos/rollup.ml | 26 ++++--- tezt/lib_tezos/rollup.mli | 6 +- tezt/tests/dal.ml | 13 ++-- 20 files changed, 324 insertions(+), 75 deletions(-) diff --git a/src/bin_dal_node/RPC_server.ml b/src/bin_dal_node/RPC_server.ml index bd19f1cf940f..6da60bf1bc06 100644 --- a/src/bin_dal_node/RPC_server.ml +++ b/src/bin_dal_node/RPC_server.ml @@ -76,8 +76,13 @@ module Slots_handlers = struct (* Storage consistency ensures we can always compute the polynomial from the slot. *) assert false - | Ok polynomial -> - return_some (Cryptobox.prove_commitment cryptobox polynomial))) + | Ok polynomial -> ( + match Cryptobox.prove_commitment cryptobox polynomial with + (* [polynomial] was produced with the parameters from + [cryptobox], thus we can always compute the proof from + [polynomial]. *) + | Error _ -> assert false + | Ok proof -> return_some proof))) let put_commitment_shards ctxt commitment () with_proof = call_handler2 ctxt (fun store {cryptobox; _} -> diff --git a/src/bin_dal_node/slot_manager.ml b/src/bin_dal_node/slot_manager.ml index 4cd9c8dd6f6b..266c23280960 100644 --- a/src/bin_dal_node/slot_manager.ml +++ b/src/bin_dal_node/slot_manager.ml @@ -25,7 +25,9 @@ include Slot_manager_legacy -type error += Invalid_slot_size of {provided : int; expected : int} +type error += + | Invalid_slot_size of {provided : int; expected : int} + | Invalid_degree of string let () = register_error_kind @@ -43,7 +45,16 @@ let () = (function | Invalid_slot_size {provided; expected} -> Some (provided, expected) | _ -> None) - (fun (provided, expected) -> Invalid_slot_size {provided; expected}) + (fun (provided, expected) -> Invalid_slot_size {provided; expected}) ; + register_error_kind + `Permanent + ~id:"dal.node.invalid_degree_string" + ~title:"Invalid degree" + ~description:"The degree of the polynomial is too high" + ~pp:(fun ppf msg -> Format.fprintf ppf "%s" msg) + Data_encoding.(obj1 (req "msg" string)) + (function Invalid_degree msg -> Some msg | _ -> None) + (fun msg -> Invalid_degree msg) (* Used wrapper functions on top of Cryptobox. *) @@ -57,6 +68,23 @@ let polynomial_from_slot cryptobox slot = let {slot_size = expected; _} = parameters cryptobox in Error (Errors.other [Invalid_slot_size {provided; expected}]) +let commit cryptobox polynomial = + let open Result_syntax in + match Cryptobox.commit cryptobox polynomial with + | Ok cm -> return cm + | Error + (`Invalid_degree_strictly_less_than_expected Cryptobox.{given; expected}) + -> + Error + (Errors.other + [ + Invalid_degree + (Format.sprintf + "Got %d, expecting a value strictly less than %d" + given + expected); + ]) + let commitment_should_exist node_store cryptobox commitment = let open Lwt_result_syntax in let*! exists = @@ -69,7 +97,7 @@ let commitment_should_exist node_store cryptobox commitment = let add_commitment node_store slot cryptobox = let open Lwt_result_syntax in let*? polynomial = polynomial_from_slot cryptobox slot in - let commitment = Cryptobox.commit cryptobox polynomial in + let*? commitment = commit cryptobox polynomial in let*! exists = Store.Legacy.exists_slot_by_commitment node_store cryptobox commitment in diff --git a/src/bin_dal_node/slot_manager_legacy.ml b/src/bin_dal_node/slot_manager_legacy.ml index 27eb321b1288..47cee902b5fe 100644 --- a/src/bin_dal_node/slot_manager_legacy.ml +++ b/src/bin_dal_node/slot_manager_legacy.ml @@ -34,6 +34,7 @@ type error += | Slot_not_found | Illformed_pages | Invalid_shards_slot_header_association + | Invalid_degree_strictly_less_than_expected of {given : int; expected : int} let () = register_error_kind @@ -107,7 +108,25 @@ let () = Format.fprintf ppf "Association between shards and slot header is invalid") Data_encoding.(unit) (function Invalid_shards_slot_header_association -> Some () | _ -> None) - (fun () -> Invalid_shards_slot_header_association) + (fun () -> Invalid_shards_slot_header_association) ; + register_error_kind + `Permanent + ~id:"dal.node.invalid_degree" + ~title:"Invalid degree" + ~description:"The degree of the polynomial is too high" + ~pp:(fun ppf (given, expected) -> + Format.fprintf + ppf + "Got %d, expecting a value strictly less than %d" + given + expected) + Data_encoding.(obj2 (req "given" int31) (req "expected" int31)) + (function + | Invalid_degree_strictly_less_than_expected {given; expected} -> + Some (given, expected) + | _ -> None) + (fun (given, expected) -> + Invalid_degree_strictly_less_than_expected {given; expected}) type slot = bytes @@ -120,10 +139,18 @@ let polynomial_from_shards cryptobox shards = | `Invalid_shard_length msg ) -> Error [Merging_failed msg] +let commit cryptobox polynomial = + match Cryptobox.commit cryptobox polynomial with + | Ok cm -> Ok cm + | Error + (`Invalid_degree_strictly_less_than_expected Cryptobox.{given; expected}) + -> + Error [Invalid_degree_strictly_less_than_expected {given; expected}] + let save_shards store cryptobox commitment shards = let open Lwt_result_syntax in let*? polynomial = polynomial_from_shards cryptobox shards in - let rebuilt_commitment = Cryptobox.commit cryptobox polynomial in + let*? rebuilt_commitment = commit cryptobox polynomial in let*? () = if Cryptobox.Commitment.equal commitment rebuilt_commitment then Ok () else Result_syntax.fail [Invalid_shards_slot_header_association] diff --git a/src/lib_crypto_dal/cryptobox.ml b/src/lib_crypto_dal/cryptobox.ml index fb91d0e6f225..dcc77c1ba109 100644 --- a/src/lib_crypto_dal/cryptobox.ml +++ b/src/lib_crypto_dal/cryptobox.ml @@ -272,6 +272,8 @@ module Inner = struct let encoding = raw_encoding end + type ('a, 'b) error_container = {given : 'a; expected : 'b} + (* Number of bytes fitting in a Scalar.t. Since scalars are integer modulo r~2^255, we restrict ourselves to 248-bit integers (31 bytes). *) let scalar_bytes_amount = Scalar.size_in_bytes - 1 @@ -937,7 +939,13 @@ module Inner = struct in Ok (Polynomials.copy ~len p) - let commit t p = Srs_g1.pippenger t.srs.raw.srs_g1 p + let commit t p = + let degree = Polynomials.degree p in + if degree >= t.k then + Error + (`Invalid_degree_strictly_less_than_expected + {given = degree; expected = t.k}) + else Ok (Srs_g1.pippenger t.srs.raw.srs_g1 p) (* p(X) of degree n. Max degree that can be committed: d, which is also the SRS's length - 1. We take d = t.k - 1 since we don't want to commit @@ -1316,10 +1324,11 @@ module Inner = struct Implements the "Multi-reveals" section above. *) let verify t ~commitment ~srs_point ~domain ~root ~evaluations ~proof = let open Bls12_381 in + let open Result_syntax in (* Compute r_i(x). *) let remainder = interpolation_poly ~root ~domain ~evaluations in (* Compute [r_i(τ)]_1. *) - let commitment_remainder = commit t remainder in + let* commitment_remainder = commit t remainder in (* Compute [w^{i * l}]. *) let root_pow = Scalar.pow root (Z.of_int (Domains.length domain)) in (* Compute [τ^l]_2 - [w^{i * l}]_2). *) @@ -1332,8 +1341,12 @@ module Inner = struct by checking [0]_1 ?= -e(c-[r_i(τ)]_1, g_2) + e(π, [τ^l]_2 - [w^{i * l}]_2) = e([r_i(τ)]_1-c, g_2) + e(π, [τ^l]_2 - [w^{i * l}]_2). *) - Pairing.pairing_check - [(diff_commits, G2.(copy one)); (proof, commit_srs_point_minus_root_pow)] + Ok + (Pairing.pairing_check + [ + (diff_commits, G2.(copy one)); + (proof, commit_srs_point_minus_root_pow); + ]) let _save_precompute_shards_proofs (preprocess : shards_proofs_precomputation) filename = @@ -1383,9 +1396,12 @@ module Inner = struct let root = Domains.get t.domain_n shard_index in let domain = Domains.build t.shard_length in let srs_point = t.srs.kate_amortized_srs_g2_shards in - if verify t ~commitment ~srs_point ~domain ~root ~evaluations ~proof then - Ok () - else Error `Invalid_shard + match + verify t ~commitment ~srs_point ~domain ~root ~evaluations ~proof + with + | Ok true -> Ok () + | Ok false -> Error `Invalid_shard + | Error e -> Error e let prove_page t p page_index = if page_index < 0 || page_index >= t.pages_per_slot then @@ -1396,7 +1412,7 @@ module Inner = struct let quotient, _ = Polynomials.(division_xn p l Scalar.(negate (pow wi (Z.of_int l)))) in - Ok (commit t quotient) + commit t quotient (* Parses the [slot_page] to get the evaluations that it contains. The evaluation points are given by the [slot_page_index]. *) @@ -1441,7 +1457,7 @@ module Inner = struct | _ -> Scalar.(copy zero)) in let root = Domains.get t.domain_k page_index in - if + match verify t ~commitment @@ -1450,8 +1466,10 @@ module Inner = struct ~root ~evaluations ~proof - then Ok () - else Error `Invalid_page + with + | Ok true -> Ok () + | Ok false -> Error `Invalid_page + | Error e -> Error e end include Inner diff --git a/src/lib_crypto_dal/cryptobox.mli b/src/lib_crypto_dal/cryptobox.mli index 106d916ddae5..679ac7a8c461 100644 --- a/src/lib_crypto_dal/cryptobox.mli +++ b/src/lib_crypto_dal/cryptobox.mli @@ -106,6 +106,8 @@ type commitment_proof type page_proof +type ('a, 'b) error_container = {given : 'a; expected : 'b} + module Verifier : VERIFIER with type t = t @@ -113,6 +115,7 @@ module Verifier : and type commitment = commitment and type commitment_proof = commitment_proof and type page_proof = page_proof + and type ('a, 'b) error_container = ('a, 'b) error_container include VERIFIER @@ -121,6 +124,7 @@ include and type commitment := commitment and type commitment_proof := commitment_proof and type page_proof := page_proof + and type ('a, 'b) error_container := ('a, 'b) error_container (** The primitives exposed in this modules require some preprocessing. This preprocessing generates data from an unknown @@ -186,9 +190,15 @@ val polynomial_to_slot : t -> polynomial -> slot (** [commit t polynomial] returns the commitment associated to a polynomial [p]. - Fails with [`Degree_exceeds_srs_length] if the degree of [p] - exceeds the SRS size. *) -val commit : t -> polynomial -> commitment + Fails with [`Invalid_degree_strictly_less_than_expected _] + if the degree of [p] exceeds the SRS size. *) +val commit : + t -> + polynomial -> + ( commitment, + [> `Invalid_degree_strictly_less_than_expected of (int, int) error_container] + ) + Result.t (** A portion of the data represented by a polynomial. *) type share @@ -262,6 +272,8 @@ type shard_proof Fails with: - [Error `Invalid_shard] if the verification fails + - [Error `Invalid_degree_strictly_less_than_expected _] if the + SRS contained in [t] is too small to proceed with the verification - [Error (`Shard_index_out_of_range msg)] if the shard index is not within the range [0, number_of_shards - 1] (where [number_of_shards] is found in [t]). @@ -277,18 +289,54 @@ val verify_shard : commitment -> shard -> shard_proof -> - (unit, [> `Shard_index_out_of_range of string | `Invalid_shard]) result + ( unit, + [> `Invalid_degree_strictly_less_than_expected of (int, int) error_container + | `Invalid_shard + | `Shard_index_out_of_range of string ] ) + Result.t + +(** [prove_commitment t polynomial] produces a proof that the slot represented + by [polynomial] has its size bounded by [slot_size] declared in [t]. -(** [prove_commitment t polynomial] produces a proof that the - slot represented by [polynomial] has its size bounded by - [t.slot_size]. *) -val prove_commitment : t -> polynomial -> commitment_proof + Fails with: + - [Error `Invalid_degree_strictly_less_than_expected _] if the SRS + contained in [t] is too small to produce the proof *) +val prove_commitment : + t -> + polynomial -> + ( commitment_proof, + [> `Invalid_degree_strictly_less_than_expected of (int, int) error_container] + ) + Result.t + +(** [prove_page t polynomial n] produces a proof for the [n]-th page of + the [slot] such that [polynomial = polynomial_from_slot t slot]. + This proof can be used to verify given a commitment to a slot that + a byte sequence is indeed the [n]-th page of the slot + (see Ensures section below). -(** [prove_page] produces a proof that the [n]th page computed - is part of a commitment. This page corresponds to the original - data and are split into [C.page_size]. *) + Fails with: + - [Error `Invalid_degree_strictly_less_than_expected _] if the SRS + contained in [t] is too small to produce the proof + - [Error (`Segment_index_out_of_range msg)] if the page index + is not within the range [0, slot_size/page_size - 1] + (where [slot_size] and [page_size] are found in [t]). + + Ensures: + - [verify_page t commitment ~page_index page page_proof = Ok ()] if + and only if + [page = Bytes.sub slot (page_index * t.page_size) t.page_size]), + [page_proof = prove_page t polynomial page_index], + [p = polynomial_from_slot t slot], + and [commitment = commit t p]. *) val prove_page : - t -> polynomial -> int -> (page_proof, [> `Segment_index_out_of_range]) result + t -> + polynomial -> + int -> + ( page_proof, + [> `Invalid_degree_strictly_less_than_expected of (int, int) error_container + | `Segment_index_out_of_range ] ) + Result.t (** [prove_shards t polynomial] produces [number_of_shards] proofs (π_0, ..., π_{number_of_shards}) for the elements of diff --git a/src/lib_crypto_dal/cryptobox_intf.ml b/src/lib_crypto_dal/cryptobox_intf.ml index 106e992eacc3..0b356f4a7dea 100644 --- a/src/lib_crypto_dal/cryptobox_intf.ml +++ b/src/lib_crypto_dal/cryptobox_intf.ml @@ -72,6 +72,8 @@ module type VERIFIER = sig number_of_shards : int; } + type ('a, 'b) error_container = {given : 'a; expected : 'b} + (** An encoding for values of type {!type-parameters}. *) val parameters_encoding : parameters Data_encoding.t @@ -94,12 +96,11 @@ module type VERIFIER = sig module Commitment_proof : COMMITMENT_PROOF with type t := commitment_proof - (** [verify_commitment t commitment proof] checks whether - [commitment] is valid. In particular, it checks - that the size of the data committed via [commitment] does not - exceed [t.slot_size]. The verification time is constant. + (** [verify_commitment t commitment proof] returns [true] if and only if the + size of the data committed via [commitment] does not exceed the + [slot_size] declared in [t]. - Fails if the size of the srs on the group G2 is too small. *) + The verification time is constant. *) val verify_commitment : t -> commitment -> commitment_proof -> bool (** The original slot can be split into a list of pages of fixed @@ -117,14 +118,27 @@ module type VERIFIER = sig (** [pages_per_slot t] returns the number of expected pages per slot. *) val pages_per_slot : parameters -> int - (** [verify_page t srs commitment page page_proof] returns [Ok ()] - if the [proof] certifies that the [slot_page] is indeed included - in the slot committed with commitment [commitment]. - Returns [Error `Invalid_page] otherwise. - - Fails if the index of the page is out of range or if the page is - not of the expected length [page_size] given for the - initialisation of [t]. *) + (** [verify_page t commitment ~page_index page proof] returns [Ok ()] + if the [proof] certifies that the [page] is the [page_index]-th page + of the slot with the given [commitment]. + + Fails with: + - [Error `Invalid_page] if the verification Fails + - [Error `Invalid_degree_strictly_less_than_expected _] if the SRS + contained in [t] is too small to proceed with the verification + - [Error `Page_length_mismatch] if the page is not of the expected + length [page_size] given for the initialisation of [t] + - [Error `Segment_index_out_of_range] if [page_index] is out of the + range [0, slot_size/page_size - 1] where [slot_size] and [page_size] + are given for the initialisation of [t] + + Ensures: + - [verify_page t commitment ~page_index page proof = Ok ()] if + and only if + [page = Bytes.sub slot (page_index * t.page_size) t.page_size]), + [proof = prove_page t polynomial page_index], + [p = polynomial_from_slot t slot], + and [commitment = commit t p]. *) val verify_page : t -> commitment -> @@ -132,7 +146,10 @@ module type VERIFIER = sig page -> page_proof -> ( unit, - [> `Segment_index_out_of_range | `Page_length_mismatch | `Invalid_page] - ) + [> `Invalid_degree_strictly_less_than_expected of + (int, int) error_container + | `Invalid_page + | `Page_length_mismatch + | `Segment_index_out_of_range ] ) Result.t end diff --git a/src/lib_crypto_dal/test/test_dal_cryptobox.ml b/src/lib_crypto_dal/test/test_dal_cryptobox.ml index f7d849632b45..6936aa5698b1 100644 --- a/src/lib_crypto_dal/test/test_dal_cryptobox.ml +++ b/src/lib_crypto_dal/test/test_dal_cryptobox.ml @@ -282,7 +282,7 @@ module Test = struct (let open Tezos_error_monad.Error_monad.Result_syntax in let* t = Cryptobox.make (get_cryptobox_parameters params) in let* p = Cryptobox.polynomial_from_slot t params.slot in - let cm = Cryptobox.commit t p in + let* cm = Cryptobox.commit t p in let number_of_pages = params.slot_size / params.page_size in let page_index = Random.int number_of_pages in let* pi = Cryptobox.prove_page t p page_index in @@ -307,7 +307,7 @@ module Test = struct (let open Tezos_error_monad.Error_monad.Result_syntax in let* t = Cryptobox.make (get_cryptobox_parameters params) in let* p = Cryptobox.polynomial_from_slot t params.slot in - let cm = Cryptobox.commit t p in + let* cm = Cryptobox.commit t p in let enc_shards = Cryptobox.shards_from_polynomial t p in let shard_proofs = Cryptobox.prove_shards t p in let shard_index = Random.int params.number_of_shards in @@ -340,10 +340,9 @@ module Test = struct (let open Tezos_error_monad.Error_monad.Result_syntax in let* t = Cryptobox.make (get_cryptobox_parameters params) in let* p = Cryptobox.polynomial_from_slot t params.slot in - let cm = Cryptobox.commit t p in - let pi = Cryptobox.prove_commitment t p in - let check = Cryptobox.verify_commitment t cm pi in - Ok check) + let* cm = Cryptobox.commit t p in + let* pi = Cryptobox.prove_commitment t p in + return (Cryptobox.verify_commitment t cm pi)) |> function | Ok true -> true | _ -> false) @@ -394,8 +393,8 @@ module Test = struct let* p1 = Cryptobox.polynomial_from_slot t1 slot1 in let* p2 = Cryptobox.polynomial_from_slot t2 slot2 in - let cm1 = Cryptobox.commit t1 p1 in - let cm2 = Cryptobox.commit t2 p2 in + let* cm1 = Cryptobox.commit t1 p1 in + let* cm2 = Cryptobox.commit t2 p2 in Ok (Cryptobox.Commitment.equal cm1 cm2)) |> function | Ok check -> assert check diff --git a/src/lib_dal_node/test/test_lib_dal_node.ml b/src/lib_dal_node/test/test_lib_dal_node.ml index 7be67d0fbbe6..3156b9615288 100644 --- a/src/lib_dal_node/test/test_lib_dal_node.ml +++ b/src/lib_dal_node/test/test_lib_dal_node.ml @@ -50,7 +50,19 @@ let shards_from_bytes dal b = | Ok v -> v | Error _ -> Stdlib.failwith "DAL ERROR: polynomial_from_slot failed" in - let commitment = Cryptobox.commit dal polynomial in + let commitment = + match Cryptobox.commit dal polynomial with + | Ok cm -> cm + | Error + (`Invalid_degree_strictly_less_than_expected + Cryptobox.{given; expected}) -> + Stdlib.failwith + (Format.sprintf + "DAL ERROR: commit failed with: got %d, expecting a value \ + strictly less than %d" + given + expected) + in let shards = Cryptobox.shards_from_polynomial dal polynomial in (commitment, shards) diff --git a/src/lib_protocol_environment/environment_V7.ml b/src/lib_protocol_environment/environment_V7.ml index 551614b2dc8a..097ad3585b26 100644 --- a/src/lib_protocol_environment/environment_V7.ml +++ b/src/lib_protocol_environment/environment_V7.ml @@ -1415,7 +1415,8 @@ struct match verify_page t sh ~page_index:page.index page.content proof with | Error `Page_length_mismatch -> Ok false | Error `Segment_index_out_of_range -> Error `Segment_index_out_of_range - | Error `Invalid_page -> Ok false + | Error (`Invalid_page | `Invalid_degree_strictly_less_than_expected _) -> + Ok false | Ok () -> Ok true let commitment_proof_encoding = Commitment_proof.encoding diff --git a/src/lib_protocol_environment/environment_V8.ml b/src/lib_protocol_environment/environment_V8.ml index d99e65dc5a57..96145abbe2bc 100644 --- a/src/lib_protocol_environment/environment_V8.ml +++ b/src/lib_protocol_environment/environment_V8.ml @@ -1453,7 +1453,8 @@ struct match verify_page t commitment ~page_index page page_proof with | Error `Page_length_mismatch -> Error `Page_length_mismatch | Error `Segment_index_out_of_range -> Error `Segment_index_out_of_range - | Error `Invalid_page -> Ok false + | Error (`Invalid_page | `Invalid_degree_strictly_less_than_expected _) -> + Ok false | Ok () -> Ok true end end diff --git a/src/lib_protocol_environment/environment_V9.ml b/src/lib_protocol_environment/environment_V9.ml index 7fe120cd5822..066e5ed17c8a 100644 --- a/src/lib_protocol_environment/environment_V9.ml +++ b/src/lib_protocol_environment/environment_V9.ml @@ -1459,7 +1459,8 @@ struct match verify_page t commitment ~page_index page page_proof with | Error `Page_length_mismatch -> Error `Page_length_mismatch | Error `Segment_index_out_of_range -> Error `Segment_index_out_of_range - | Error `Invalid_page -> Ok false + | Error (`Invalid_page | `Invalid_degree_strictly_less_than_expected _) -> + Ok false | Ok () -> Ok true end end diff --git a/src/proto_016_PtMumbai/lib_protocol/test/helpers/dal_helpers.ml b/src/proto_016_PtMumbai/lib_protocol/test/helpers/dal_helpers.ml index 091177e0f1a5..74403d532910 100644 --- a/src/proto_016_PtMumbai/lib_protocol/test/helpers/dal_helpers.ml +++ b/src/proto_016_PtMumbai/lib_protocol/test/helpers/dal_helpers.ml @@ -105,13 +105,38 @@ struct | Ok p -> return p | Error `Segment_index_out_of_range -> fail [Test_failure "compute_proof_segment: Segment_index_out_of_range"] + | Error + (`Invalid_degree_strictly_less_than_expected + Cryptobox.{given; expected}) -> + fail + [ + Test_failure + (Format.sprintf + "Got %d, expecting a value strictly less than %d" + given + expected); + ] let mk_slot ?(level = level_one) ?(index = S.Index.zero) ?(fill_function = fun _i -> 'x') () = let open Result_syntax in let slot_data = Bytes.init params.slot_size fill_function in let* polynomial = dal_mk_polynomial_from_slot slot_data in - let commitment = Cryptobox.commit cryptobox polynomial in + let* commitment = + match Cryptobox.commit cryptobox polynomial with + | Ok cm -> return cm + | Error + (`Invalid_degree_strictly_less_than_expected + Cryptobox.{given; expected}) -> + fail + [ + Test_failure + (Format.sprintf + "Got %d, expecting a value strictly less than %d" + given + expected); + ] + in return ( slot_data, polynomial, diff --git a/src/proto_016_PtMumbai/lib_sc_rollup_node/refutation_game.ml b/src/proto_016_PtMumbai/lib_sc_rollup_node/refutation_game.ml index 2f958d8d1cdc..ba55e062656a 100644 --- a/src/proto_016_PtMumbai/lib_sc_rollup_node/refutation_game.ml +++ b/src/proto_016_PtMumbai/lib_sc_rollup_node/refutation_game.ml @@ -110,7 +110,14 @@ module Make (Interpreter : Interpreter.S) : (match e with | `Fail s -> "Fail " ^ s | `Segment_index_out_of_range -> "Segment_index_out_of_range" - | `Slot_wrong_size s -> "Slot_wrong_size: " ^ s) + | `Slot_wrong_size s -> "Slot_wrong_size: " ^ s + | `Invalid_degree_strictly_less_than_expected + Cryptobox.{given; expected} -> + Format.sprintf + "Invalid_degree: got %d, expecting a value strictly less than \ + %d" + given + expected) (** When the PVM is waiting for a Dal page input, this function attempts to retrieve the page's content from the store, the data of its slot. Then it diff --git a/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml b/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml index dfa140faa7f5..a5bd9846c600 100644 --- a/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml +++ b/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml @@ -100,19 +100,47 @@ struct (Format.sprintf "polynomial_from_slot: Slot_wrong_size (%s)" s); ] + let dal_commit cryptobox polynomial = + let open Result_syntax in + match Cryptobox.commit cryptobox polynomial with + | Ok cm -> return cm + | Error + (`Invalid_degree_strictly_less_than_expected + Cryptobox.{given; expected}) -> + fail + [ + Test_failure + (Format.sprintf + "commit: Invalid_degree (got %d, expecting a value strictly \ + less than %d)" + given + expected); + ] + let dal_mk_prove_page polynomial page_id = let open Result_syntax in match Cryptobox.prove_page cryptobox polynomial page_id.P.page_index with | Ok p -> return p | Error `Segment_index_out_of_range -> fail [Test_failure "compute_proof_segment: Segment_index_out_of_range"] + | Error + (`Invalid_degree_strictly_less_than_expected + Cryptobox.{given; expected}) -> + fail + [ + Test_failure + (Format.sprintf + "Got %d, expecting a value strictly less than %d" + given + expected); + ] let mk_slot ?(level = level_one) ?(index = Slot_index.zero) ?(fill_function = fun _i -> 'x') () = let open Result_syntax in let slot_data = Bytes.init params.slot_size fill_function in let* polynomial = dal_mk_polynomial_from_slot slot_data in - let commitment = Cryptobox.commit cryptobox polynomial in + let* commitment = dal_commit cryptobox polynomial in return ( slot_data, polynomial, diff --git a/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.mli b/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.mli index b7b7db7f0b6a..ce6d0ac9baff 100644 --- a/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.mli +++ b/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.mli @@ -64,6 +64,12 @@ end) : sig (** Returns the slot's polynomial from the given slot's data. *) val dal_mk_polynomial_from_slot : bytes -> Cryptobox.polynomial tzresult + (* Commits to the given polynomial. *) + val dal_commit : + Cryptobox.t -> + Cryptobox.polynomial -> + (Cryptobox.commitment, error trace) result + (** Using the given slot's polynomial, this function computes the page proof of the page whose ID is provided. *) val dal_mk_prove_page : diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml b/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml index 73c35f58da13..899a53fe8e77 100644 --- a/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml +++ b/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml @@ -79,7 +79,7 @@ struct (fun _i -> 'x') in let* polynomial = dal_mk_polynomial_from_slot slot_data in - let commitment = Cryptobox.commit ARG.cryptobox polynomial in + let* commitment = dal_commit ARG.cryptobox polynomial in let add_slot level sindex (cell, cache, slots_info) skip_slot = let index = Option.value_f diff --git a/src/proto_alpha/lib_sc_rollup_node/refutation_game.ml b/src/proto_alpha/lib_sc_rollup_node/refutation_game.ml index 03d1c60622d7..ed54943089a6 100644 --- a/src/proto_alpha/lib_sc_rollup_node/refutation_game.ml +++ b/src/proto_alpha/lib_sc_rollup_node/refutation_game.ml @@ -110,7 +110,14 @@ module Make (Interpreter : Interpreter.S) : (match e with | `Fail s -> "Fail " ^ s | `Segment_index_out_of_range -> "Segment_index_out_of_range" - | `Slot_wrong_size s -> "Slot_wrong_size: " ^ s) + | `Slot_wrong_size s -> "Slot_wrong_size: " ^ s + | `Invalid_degree_strictly_less_than_expected + Cryptobox.{given; expected} -> + Format.sprintf + "Invalid_degree: got %d, expecting a value strictly less than \ + %d" + given + expected) (** When the PVM is waiting for a Dal page input, this function attempts to retrieve the page's content from the store, the data of its slot. Then it diff --git a/tezt/lib_tezos/rollup.ml b/tezt/lib_tezos/rollup.ml index 8f110a854e20..d2d27425fc4a 100644 --- a/tezt/lib_tezos/rollup.ml +++ b/tezt/lib_tezos/rollup.ml @@ -837,20 +837,30 @@ module Dal = struct module Commitment = struct let dummy_commitment ?(on_error = - fun str -> Test.fail "Rollup.Dal.dummy_commitment failed: %s" str) - cryptobox message = + function + | `Slot_wrong_size str -> + Test.fail "Rollup.Dal.dummy_commitment failed: %s" str + | `Invalid_degree_strictly_less_than_expected + Cryptobox.{given; expected} -> + Test.fail + "Rollup.Dal.dummy_commitment failed: got %d, expecting a value \ + strictly less than %d" + given + expected) cryptobox message = let parameters = Cryptobox.Verifier.parameters cryptobox in let padding_length = parameters.slot_size - String.length message in let padded_message = if padding_length > 0 then pad padding_length message else message in let slot = String.to_bytes padded_message in - match Cryptobox.polynomial_from_slot cryptobox slot with - | Ok r -> - let c = Cryptobox.commit cryptobox r in - let p = Cryptobox.prove_commitment cryptobox r in - (c, p) - | Error (`Slot_wrong_size str) -> on_error str + let open Tezos_error_monad.Error_monad.Result_syntax in + (let* p = Cryptobox.polynomial_from_slot cryptobox slot in + let* cm = Cryptobox.commit cryptobox p in + let* proof = Cryptobox.prove_commitment cryptobox p in + Ok (cm, proof)) + |> function + | Ok res -> res + | Error e -> on_error e let to_string commitment = Cryptobox.Commitment.to_b58check commitment end diff --git a/tezt/lib_tezos/rollup.mli b/tezt/lib_tezos/rollup.mli index 510d14f23226..cb14f6ed1859 100644 --- a/tezt/lib_tezos/rollup.mli +++ b/tezt/lib_tezos/rollup.mli @@ -379,7 +379,11 @@ module Dal : sig module Commitment : sig val dummy_commitment : - ?on_error:(string -> Cryptobox.commitment * Cryptobox.commitment_proof) -> + ?on_error: + ([ `Invalid_degree_strictly_less_than_expected of + (int, int) Cryptobox.error_container + | `Slot_wrong_size of slot ] -> + Cryptobox.commitment * Cryptobox.commitment_proof) -> Cryptobox.t -> string -> Cryptobox.commitment * Cryptobox.commitment_proof diff --git a/tezt/tests/dal.ml b/tezt/tests/dal.ml index c7e1fa4548b0..edd44a63cde3 100644 --- a/tezt/tests/dal.ml +++ b/tezt/tests/dal.ml @@ -1302,7 +1302,12 @@ let commitment_of_slot cryptobox slot = (Rollup.Dal.content_of_slot slot |> Bytes.of_string) |> Result.get_ok in - Cryptobox.commit cryptobox polynomial + match Cryptobox.commit cryptobox polynomial with + | Ok cm -> cm + | Error + (`Invalid_degree_strictly_less_than_expected Cryptobox.{given; expected}) + -> + Test.fail "Got %d, expecting a value strictly less than %d" given expected let test_dal_node_test_post_commitments _protocol parameters cryptobox _node _client dal_node = @@ -1386,19 +1391,19 @@ let test_dal_node_test_get_commitment_slot _protocol parameters cryptobox _node _client dal_node = let slot_size = parameters.Rollup.Dal.Parameters.cryptobox.slot_size in let slot = Rollup.Dal.make_slot ~slot_size (generate_dummy_slot slot_size) in - let commit = + let commitment = Cryptobox.Commitment.to_b58check @@ commitment_of_slot cryptobox slot in let* () = let* response = - RPC.call_raw dal_node @@ Rollup.Dal.RPC.get_commitment_slot commit + RPC.call_raw dal_node @@ Rollup.Dal.RPC.get_commitment_slot commitment in return @@ RPC.check_string_response ~code:404 response in let* _commitment = RPC.call dal_node (Rollup.Dal.RPC.post_commitment slot) in (* commit = _commitment already tested in /POST test. *) let* got_slot = - RPC.call dal_node (Rollup.Dal.RPC.get_commitment_slot commit) + RPC.call dal_node (Rollup.Dal.RPC.get_commitment_slot commitment) in Check.(Rollup.Dal.content_of_slot slot = Rollup.Dal.content_of_slot got_slot) Check.string -- GitLab From f2a5c07cb473d68524272375b79c0f7ef23ed123 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Fri, 24 Feb 2023 11:09:06 +0100 Subject: [PATCH 2/4] DAL/crypto: fix wording --- src/lib_crypto_dal/cryptobox.mli | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/lib_crypto_dal/cryptobox.mli b/src/lib_crypto_dal/cryptobox.mli index 679ac7a8c461..3d50c46a161a 100644 --- a/src/lib_crypto_dal/cryptobox.mli +++ b/src/lib_crypto_dal/cryptobox.mli @@ -66,8 +66,8 @@ open Cryptobox_intf time [O(n log n)] (see {{: https://eprint.iacr.org/2023/033.pdf}Fast amortized KZG proofs}). *) -(** Initial values to parametrize dal cryptographic primitives. It used to build - a value of type [t] *) +(** Initial values for the parameters of the DAL cryptographic primitives. + It used to build a value of type [t]. *) type parameters = { redundancy_factor : int; page_size : int; -- GitLab From 9a071c6151b76532490552b084e0f7f906075621 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Tue, 28 Feb 2023 14:34:34 +0100 Subject: [PATCH 3/4] DAL/crypto: improve documentation header --- src/lib_crypto_dal/cryptobox.mli | 31 +++++++++++++------------------ 1 file changed, 13 insertions(+), 18 deletions(-) diff --git a/src/lib_crypto_dal/cryptobox.mli b/src/lib_crypto_dal/cryptobox.mli index 3d50c46a161a..9c8132c232ba 100644 --- a/src/lib_crypto_dal/cryptobox.mli +++ b/src/lib_crypto_dal/cryptobox.mli @@ -27,14 +27,14 @@ open Cryptobox_intf (** {0 Cryptography for the Data Availability Layer} - The data availability layer (DAL) reduces the storage strain on the + The Data Availability Layer (DAL) reduces the storage strain on the blockchain by only storing on-chain constant-size cryptographic {!type:commitment}s to arbitrary data blobs called {!type:slot}s. The slots themselves are stored off-chain and are made available by the DAL. - A slot is encoded with an MDS (Maximum Distance Separable) code. The - resulting encoded slot is partitioned into {!type:shard}s, allowing - retrieval of the slot with any subset of + A slot is encoded with some redundancy using a so-called MDS (Maximum + Distance Separable) code. The resulting encoded slot is partitioned into + {!type:shard}s, allowing retrieval of the slot with any subset of [{!recfield:parameters.number_of_shards}/{!recfield:parameters.redundancy_factor}] out of [{!recfield:parameters.number_of_shards}] shards. By doing so, we can guarantee high data availability provided a certain fraction of @@ -43,22 +43,17 @@ open Cryptobox_intf {!recfield:parameters.redundancy_factor}. MDS codes have no unnecessary redundancy. - Compatibility between the commitment scheme and the MDS code is achieved - by using the KZG polynomial commitment scheme and Reed-Solomon - codes. Indeed, Reed-Solomon codes are evaluations of polynomials, and KZG - allows proving and verifying evaluations of polynomials. - - The DAL nodes can verify in constant time that they downloaded the correct - shard using constant-sized - {{: https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf}KZG proofs} + One can verify in constant time that the correct shard was retrieved + using a constant-sized + {{: https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf}KZG proof} {!type:shard_proof} (see function [verifyEval] in section 3.3) and the - slot commitment. This mitigates the barriers in terms of bandwidth and - storage to participate in the DAL network so that more actors can increase - its efficacy and security -- to prevent data availability attacks, for instance. + slot commitment. - The L1 can also verify in constant time that it downloaded the correct - slot segment called {type:Verifier.page} it queried using KZG proofs - {!type:page_proof} and the slot commitment. + A {!type:slot} is partioned into + [{!recfield:parameters.slot_size}/{!recfield:parameters.page_size}] segments + called {!type:Verifier.page}s of size {!recfield:parameters.page_size}. + One can also verify in constant time that the correct page + was retrieved using a KZG proof {!type:page_proof} and the slot commitment. A challenge is to keep the proving time for the {!type:shard_proof}s almost proportional to the length [n] of the slot encoded with the MDS -- GitLab From bf67f81815c34a898c2ab32afb65593e642fdae8 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Fri, 24 Feb 2023 15:43:48 +0100 Subject: [PATCH 4/4] DAL/crypto: test wrong page --- src/lib_crypto_dal/test/test_dal_cryptobox.ml | 46 +++++++++++++++++++ 1 file changed, 46 insertions(+) diff --git a/src/lib_crypto_dal/test/test_dal_cryptobox.ml b/src/lib_crypto_dal/test/test_dal_cryptobox.ml index 6936aa5698b1..5dcee34c721e 100644 --- a/src/lib_crypto_dal/test/test_dal_cryptobox.ml +++ b/src/lib_crypto_dal/test/test_dal_cryptobox.ml @@ -294,6 +294,51 @@ module Test = struct | Ok () -> true | _ -> false) + (* The verification of a page fails on input the wrong page (or the wrong proof). *) + let test_page_proofs_invalid = + let open QCheck2 in + Test.make + ~name:"DAL cryptobox: test page proofs invalid page" + ~print:print_parameters + generate_parameters + (fun params -> + init params ; + assume (ensure_validity params) ; + (let open Tezos_error_monad.Error_monad.Result_syntax in + let* t = Cryptobox.make (get_cryptobox_parameters params) in + let* p = Cryptobox.polynomial_from_slot t params.slot in + let* cm = Cryptobox.commit t p in + let number_of_pages = params.slot_size / params.page_size in + let page_index_prove = Random.int number_of_pages in + let page_index_verify = Random.int number_of_pages in + assume (page_index_prove <> page_index_verify) ; + let* proof = Cryptobox.prove_page t p page_index_prove in + let page_prove = + Bytes.sub + params.slot + (page_index_prove * params.page_size) + params.page_size + in + let page_verify = + Bytes.sub + params.slot + (page_index_verify * params.page_size) + params.page_size + in + (* We need [page_prove] and [page_verify] to be distinct, otherwise + [Cryptobox.verify_page] will return [Ok ()] (we want to input an + incorrect page to trigger the [`Invalid_page] error). *) + assume (Bytes.compare page_prove page_verify <> 0) ; + Cryptobox.verify_page + t + cm + ~page_index:page_index_verify + page_verify + proof) + |> function + | Error `Invalid_page -> true + | _ -> false) + (* Tests that a shard comes from the erasure-encoded slot. *) let test_shard_proofs = let open QCheck2 in @@ -435,6 +480,7 @@ let () = Test.test_erasure_code_failure_not_enough_shards; Test.test_erasure_code_failure_invalid_shard_length; Test.test_page_proofs; + Test.test_page_proofs_invalid; Test.test_shard_proofs; Test.test_commitment_proof; Test.test_polynomial_slot_conversions; -- GitLab