From 58d31ecde9c26556f708f5d9c70a32683e704df6 Mon Sep 17 00:00:00 2001 From: marcbeunardeau Date: Wed, 31 Jan 2024 14:14:26 +0100 Subject: [PATCH 1/7] DAL/Crypto_box: add a multi shard verification --- src/lib_crypto_dal/cryptobox.ml | 54 +++++++++++++ src/lib_crypto_dal/cryptobox.mli | 14 +++- src/lib_crypto_dal/test/test_dal_cryptobox.ml | 61 +++++++++++++++ src/lib_kzg/kate_amortized.ml | 76 ++++++++++++++++++- src/lib_kzg/kate_amortized.mli | 16 +++- 5 files changed, 217 insertions(+), 4 deletions(-) diff --git a/src/lib_crypto_dal/cryptobox.ml b/src/lib_crypto_dal/cryptobox.ml index 9a3b17034282..cb88e8e7c2cc 100644 --- a/src/lib_crypto_dal/cryptobox.ml +++ b/src/lib_crypto_dal/cryptobox.ml @@ -971,6 +971,60 @@ module Inner = struct then Ok () else Error `Invalid_shard + let verify_shard_multi (t : t) commitment shard_list proof_list = + let out_of_range_list = + List.filter + (fun shard -> shard.index < 0 || shard.index >= t.number_of_shards) + shard_list + in + let error_message = + String.concat + "\n" + (List.map + (fun shard -> + Printf.sprintf + "Shard index out of range: got index %d, expected index within \ + range [%d, %d]." + shard.index + 0 + (t.number_of_shards - 1)) + out_of_range_list) + in + if out_of_range_list != [] then + Error (`Shard_index_out_of_range error_message) + else + let length_mismatch_list = + let expected_shard_length = t.shard_length in + + List.filter + (fun shard -> + let got_shard_length = Array.length shard.share in + expected_shard_length <> got_shard_length) + shard_list + in + if length_mismatch_list != [] then Error `Shard_length_mismatch + else + let root_list = + List.map + (fun shard -> + Domain.get t.domain_erasure_encoded_polynomial_length shard.index) + shard_list + in + let evaluations_list = List.map (fun shard -> shard.share) shard_list in + let domain = Domain.build t.shard_length in + let srs_point = t.srs_verifier.shards in + if + Kate_amortized.verify_multi + t.kate_amortized + ~commitment + ~srs_point + ~domain + ~root_list + ~evaluations_list + ~proof_list + then Ok () + else Error `Invalid_shard + let prove_page t p page_index = if page_index < 0 || page_index >= t.pages_per_slot then Error `Page_index_out_of_range diff --git a/src/lib_crypto_dal/cryptobox.mli b/src/lib_crypto_dal/cryptobox.mli index 5f228685485a..c0716a12bf44 100644 --- a/src/lib_crypto_dal/cryptobox.mli +++ b/src/lib_crypto_dal/cryptobox.mli @@ -194,7 +194,7 @@ val polynomial_to_slot : t -> polynomial -> slot Fails with [`Invalid_degree_strictly_less_than_expected _] if the degree of [p] exceeds the SRS size. - + Fails with [`Prover_SRS_not_loaded] if the prover’s SRS is not loaded (ie: [init_dal_verifier] has been used to load the SRS). *) val commit : @@ -321,6 +321,18 @@ val verify_shard : | `Shard_index_out_of_range of string ] ) Result.t +val verify_shard_multi : + t -> + commitment -> + shard list -> + shard_proof list -> + ( unit, + [> `Invalid_degree_strictly_less_than_expected of (int, int) error_container + | `Invalid_shard + | `Shard_length_mismatch + | `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]. diff --git a/src/lib_crypto_dal/test/test_dal_cryptobox.ml b/src/lib_crypto_dal/test/test_dal_cryptobox.ml index da466e0f0831..377c53de47f5 100644 --- a/src/lib_crypto_dal/test/test_dal_cryptobox.ml +++ b/src/lib_crypto_dal/test/test_dal_cryptobox.ml @@ -17,6 +17,10 @@ module Test = struct let randrange ?(min = 0) max = QCheck2.Gen.(generate1 (int_range min (max - 1))) + (* [randrange ?(min=0) max] returns a random integer in the range [min, max - 1]. *) + let randrange_list ?(min = 0) ~len max = + QCheck2.Gen.(generate ~n:len (int_range min (max - 1))) + let out_of_range ~min ~max = let left = QCheck2.Gen.(Int.min_int -- (min - 1)) in let right = QCheck2.Gen.(max -- Int.max_int) in @@ -467,6 +471,62 @@ module Test = struct | Ok () -> true | _ -> false) + (* Tests that a shard comes from the erasure-encoded slot. *) + let test_shard_proofs_multi = + let open QCheck2 in + let open Error_monad.Result_syntax in + Test.make + ~name:"shard proofs multi" + ~print:print_parameters + generate_parameters + (fun params -> + Cryptobox.Internal_for_tests.init_prover_dal () ; + assert (ensure_validity params) ; + (let* t = make params in + let* polynomial = Cryptobox.polynomial_from_slot t params.slot in + let* commitment = Cryptobox.commit t polynomial in + let shards = Cryptobox.shards_from_polynomial t polynomial in + let precomputation = Cryptobox.precompute_shards_proofs t in + let shard_proofs = + Cryptobox.prove_shards t ~polynomial ~precomputation + in + let shard_index_list = + randrange_list ~len:params.number_of_shards params.number_of_shards + in + + let shard_to_verify = + List.map + (fun shard_index -> + match + Seq.find + (fun ({index; _} : Cryptobox.shard) -> index = shard_index) + shards + with + | None -> + (* The shard index was sampled within the bounds, so this case + (the queried index is out of bounds) doesn't happen. *) + assert false + | Some shard -> shard) + shard_index_list + in + (* Testing the initialisation logic, even if the prover’s would be + enough to verify *) + Cryptobox.Internal_for_tests.init_verifier_dal () ; + let* t = make params in + let shard_proof_list = + List.map + (fun shard_index -> shard_proofs.(shard_index)) + shard_index_list + in + Cryptobox.verify_shard_multi + t + commitment + shard_to_verify + shard_proof_list) + |> function + | Ok () -> true + | _ -> false) + let test_shard_proofs_invalid_parameter () = (* The following parameters used to be accepted by the [ensure_validity] function, while they were actually unsupported (they indeed break an @@ -1050,6 +1110,7 @@ let () = test_page_proofs; test_page_proofs_invalid; test_shard_proofs; + test_shard_proofs_multi; test_shard_proof_invalid; test_commitment_proof; test_commitment_proof_invalid; diff --git a/src/lib_kzg/kate_amortized.ml b/src/lib_kzg/kate_amortized.ml index c178833c5c62..3f31dcc082ad 100644 --- a/src/lib_kzg/kate_amortized.ml +++ b/src/lib_kzg/kate_amortized.ml @@ -15,7 +15,13 @@ let preprocess_encoding : preprocess t = let open Data_encoding in tup2 Domain.encoding (array G1_carray.encoding) -type shard_proof = G1.t +(*Adding repr to inlcude the proof in the transcript*) +type shard_proof = Commitment.t [@@deriving repr] + +type commitment = Commitment.t + +(*Adding repr to include evaluations_list in the transcript*) +type eval_list = Scalar.t array list [@@deriving repr] let commit t = Commitment.commit t.srs_g1 @@ -361,3 +367,71 @@ let verify t ~commitment ~srs_point ~domain ~root ~evaluations ~proof = = 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)] + +(*Batched version of the verify functions, which verify the correctness of opening + of multiple multi reveals. + Inspired from page 13 of https://eprint.iacr.org/2019/953.pdf + With commmitment = c, remainder list = R_i + (IFFT of the evaluations, root_list = w_i + (indicating the shifts of the subgroup we are verifying evaluations agains, proof_list = pi_i, + we generate a pseudo random alpha and verify : + e(c, \sum_i w_i R_i,1)*e(sum_i aplha_i*w_i*pi_i,[X]) =? 1 *) +let verify_multi t ~commitment ~srs_point ~domain ~root_list ~evaluations_list + ~proof_list = + let open Bls12_381 in + (* Compute r_i(x). *) + let remainder_list = + List.map2 + (fun root evaluations -> interpolation_poly ~root ~domain ~evaluations) + root_list + evaluations_list + in + let transcript = + List.fold_left + (fun transcript proof -> + Utils.Transcript.expand shard_proof_t proof transcript) + Utils.Transcript.empty + proof_list + in + let transcript = + Utils.Transcript.expand eval_list_t evaluations_list transcript + in + (* We use Fiat-Shamir here to get some pseudo randomness. + Since alpha is only used on the verifier side we could + use real randomness as well. *) + let alpha, _ = Utils.Fr_generation.random_fr transcript in + (*TODO optimize*) + let alpha_list = + List.init (List.length proof_list) (fun i -> Scalar.pow alpha (Z.of_int i)) + in + let batched_remainder = + List.fold_left2 + (fun acc remainder_i alpha_i -> + Poly.(acc + mul_by_scalar alpha_i remainder_i)) + Poly.zero + remainder_list + alpha_list + in + let commitment_remainder_batched = commit t batched_remainder in + let root_pow_list = + List.map + (fun root -> Scalar.pow root (Z.of_int (Domain.length domain))) + root_list + in + let sum_alpha_i = List.fold_left Scalar.add Scalar.zero alpha_list in + let batched_commitment = G1.mul commitment sum_alpha_i in + let alpha_i_root_pow_i = List.map2 Scalar.mul alpha_list root_pow_list in + let w_batched = + G1.pippenger (Array.of_list proof_list) (Array.of_list alpha_i_root_pow_i) + in + let left = + G1.( + add + batched_commitment + (add w_batched (negate commitment_remainder_batched))) + in + let w_batched_2 = + G1.( + negate @@ pippenger (Array.of_list proof_list) (Array.of_list alpha_list)) + in + Pairing.pairing_check [(left, G2.one); (w_batched_2, srs_point)] diff --git a/src/lib_kzg/kate_amortized.mli b/src/lib_kzg/kate_amortized.mli index 9574be521dd7..46141f028508 100644 --- a/src/lib_kzg/kate_amortized.mli +++ b/src/lib_kzg/kate_amortized.mli @@ -13,9 +13,11 @@ val preprocess_encoding : preprocess t type shard_proof = Commitment.Single_G1.t +type commitment = Commitment.Single_G1.t + val preprocess_equal : preprocess -> preprocess -> bool -val commit : public_parameters -> Poly.t -> shard_proof +val commit : public_parameters -> Poly.t -> commitment val preprocess_multiple_multi_reveals : public_parameters -> preprocess @@ -27,10 +29,20 @@ val multiple_multi_reveals : val verify : public_parameters -> - commitment:shard_proof -> + commitment:commitment -> srs_point:G2.t -> domain:Domain.t -> root:scalar -> evaluations:scalar array -> proof:shard_proof -> bool + +val verify_multi : + public_parameters -> + commitment:commitment -> + srs_point:G2.t -> + domain:Domain.t -> + root_list:scalar list -> + evaluations_list:scalar array list -> + proof_list:shard_proof list -> + bool -- GitLab From aa9f2ac2cfada70af7c6520e830670fc87df5257 Mon Sep 17 00:00:00 2001 From: marcbeunardeau Date: Mon, 5 Feb 2024 13:24:55 +0100 Subject: [PATCH 2/7] Tezt/DAL: add multi shard verif to benchmarks --- tezt/tests/dal.ml | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) diff --git a/tezt/tests/dal.ml b/tezt/tests/dal.ml index cbdf19be9ade..4dd62dbf174a 100644 --- a/tezt/tests/dal.ml +++ b/tezt/tests/dal.ml @@ -4827,6 +4827,29 @@ let dal_crypto_benchmark () = let*? () = verify_shard dal commitment shard shard_proof in ()) in + let bench_i_shard_verif i = + Seq.zip shards shard_proofs |> Seq.take i |> List.of_seq |> List.split + |> fun (shard_list, shard_proof_list) -> + let message = + Format.asprintf + "verify shard multi (size: %d) (number_of_shards:%d)" + (Bytes.length + (Data_encoding.Binary.to_bytes_exn + share_encoding + (List.hd shard_list).share)) + (List.length shard_list) + in + Profiler.record_f Profiler.main message @@ fun () -> + let*? () = + verify_shard_multi dal commitment shard_list shard_proof_list + in + () + in + bench_i_shard_verif 1 ; + bench_i_shard_verif 5 ; + bench_i_shard_verif 20 ; + bench_i_shard_verif 100 ; + bench_i_shard_verif 2048 ; let pages = Seq.ints 0 |> Seq.take nb_pages |> Seq.map (fun i -> Bytes.sub slot (i * page_size) page_size) -- GitLab From 4b8ceb199247fe98b44f123e416351caf5152a16 Mon Sep 17 00:00:00 2001 From: marcbeunardeau Date: Thu, 8 Feb 2024 10:27:41 +0100 Subject: [PATCH 3/7] Kzg/Kate_amortized: correct a comment --- src/lib_kzg/kate_amortized.ml | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/lib_kzg/kate_amortized.ml b/src/lib_kzg/kate_amortized.ml index 3f31dcc082ad..17db2a7788af 100644 --- a/src/lib_kzg/kate_amortized.ml +++ b/src/lib_kzg/kate_amortized.ml @@ -313,8 +313,8 @@ let multiple_multi_reveals t ~preprocess:(domain, sj) ~coefficients : let domain = Domain.build t.number_of_shards in G1_carray.(to_array (evaluation_ecfft ~domain ~points)) -(* [interpolation_poly root domain evaluations] returns the unique - polynomial P of degree [< Domains.length domain] verifying +(* [interpolation_poly root domain evaluations] returns the + polynomial P of minimam degree ([< Domains.length domain]) verifying P(root * domain[i]) = evaluations[i]. Requires: -- GitLab From 01bb980008cd1a8567f11d3d0e7c0b5000062766 Mon Sep 17 00:00:00 2001 From: marcbeunardeau Date: Wed, 14 Feb 2024 11:49:26 +0100 Subject: [PATCH 4/7] DAL/batched vrif: add the commitment to the transcript --- src/lib_kzg/kate_amortized.ml | 17 ++++++++--------- 1 file changed, 8 insertions(+), 9 deletions(-) diff --git a/src/lib_kzg/kate_amortized.ml b/src/lib_kzg/kate_amortized.ml index 17db2a7788af..a8758871d465 100644 --- a/src/lib_kzg/kate_amortized.ml +++ b/src/lib_kzg/kate_amortized.ml @@ -386,21 +386,20 @@ let verify_multi t ~commitment ~srs_point ~domain ~root_list ~evaluations_list root_list evaluations_list in - let transcript = + let alpha = + (* We use Fiat-Shamir here to get some pseudo randomness. + Since alpha is only used on the verifier side we could + use real randomness as well. *) List.fold_left (fun transcript proof -> Utils.Transcript.expand shard_proof_t proof transcript) Utils.Transcript.empty proof_list + |> Utils.Transcript.expand eval_list_t evaluations_list + |> Utils.Transcript.expand shard_proof_t commitment + |> Utils.Fr_generation.random_fr |> fst in - let transcript = - Utils.Transcript.expand eval_list_t evaluations_list transcript - in - (* We use Fiat-Shamir here to get some pseudo randomness. - Since alpha is only used on the verifier side we could - use real randomness as well. *) - let alpha, _ = Utils.Fr_generation.random_fr transcript in - (*TODO optimize*) + (* TODO optimize *) let alpha_list = List.init (List.length proof_list) (fun i -> Scalar.pow alpha (Z.of_int i)) in -- GitLab From f562903abc23ce4d10c6a2aa6d2416f796885b19 Mon Sep 17 00:00:00 2001 From: marcbeunardeau Date: Wed, 14 Feb 2024 15:42:39 +0100 Subject: [PATCH 5/7] DAL/test: change randrange_list function --- src/lib_crypto_dal/test/test_dal_cryptobox.ml | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/src/lib_crypto_dal/test/test_dal_cryptobox.ml b/src/lib_crypto_dal/test/test_dal_cryptobox.ml index 377c53de47f5..34bdaa0b51e0 100644 --- a/src/lib_crypto_dal/test/test_dal_cryptobox.ml +++ b/src/lib_crypto_dal/test/test_dal_cryptobox.ml @@ -17,9 +17,11 @@ module Test = struct let randrange ?(min = 0) max = QCheck2.Gen.(generate1 (int_range min (max - 1))) - (* [randrange ?(min=0) max] returns a random integer in the range [min, max - 1]. *) + (* [randrange ?(min=0) ~len max] returns a list of random integer of len between + one and len in the range [min, max - 1]. *) let randrange_list ?(min = 0) ~len max = - QCheck2.Gen.(generate ~n:len (int_range min (max - 1))) + QCheck2.Gen.( + generate ~n:(generate1 (int_range 1 len)) (int_range min (max - 1))) let out_of_range ~min ~max = let left = QCheck2.Gen.(Int.min_int -- (min - 1)) in -- GitLab From 520e37fa37c3135da6e6bd842fe86d8ce443cb7d Mon Sep 17 00:00:00 2001 From: marcbeunardeau Date: Wed, 14 Feb 2024 15:59:57 +0100 Subject: [PATCH 6/7] DAL/test: add a negative test for multi shard verif --- src/lib_crypto_dal/test/test_dal_cryptobox.ml | 54 +++++++++++++++++++ 1 file changed, 54 insertions(+) diff --git a/src/lib_crypto_dal/test/test_dal_cryptobox.ml b/src/lib_crypto_dal/test/test_dal_cryptobox.ml index 34bdaa0b51e0..2b3cfbae1e73 100644 --- a/src/lib_crypto_dal/test/test_dal_cryptobox.ml +++ b/src/lib_crypto_dal/test/test_dal_cryptobox.ml @@ -585,6 +585,60 @@ module Test = struct | Error `Invalid_shard -> true | _ -> false) + let test_shard_proof_multi_invalid = + let open QCheck2 in + let open Error_monad.Result_syntax in + Test.make + ~name:"invalid shard proof" + ~print:print_parameters + ~count:30 + generate_parameters + (fun params -> + Cryptobox.Internal_for_tests.init_prover_dal () ; + assert (ensure_validity params) ; + (let* t = make params in + let* polynomial = Cryptobox.polynomial_from_slot t params.slot in + let* commitment = Cryptobox.commit t polynomial in + let shards = Cryptobox.shards_from_polynomial t polynomial in + let precomputation = Cryptobox.precompute_shards_proofs t in + let shard_proofs = + Cryptobox.prove_shards t ~precomputation ~polynomial + in + let shard_index_list = + randrange_list ~len:params.number_of_shards params.number_of_shards + in + let altered_shard_proofs_shard_list = + List.map + (fun shard_index -> + match + Seq.find + (fun ({index; _} : Cryptobox.shard) -> index = shard_index) + shards + with + | None -> + (* The shard index was sampled within the bounds, so this case + (the queried index is out of bounds) doesn't happen. *) + assert false + | Some shard -> + let altered_proof = + Cryptobox.Internal_for_tests.alter_shard_proof + shard_proofs.(shard_index) + in + (shard, altered_proof)) + shard_index_list + in + let shard_list, altered_shard_proofs_list = + List.split altered_shard_proofs_shard_list + in + Cryptobox.verify_shard_multi + t + commitment + shard_list + altered_shard_proofs_list) + |> function + | Error `Invalid_shard -> true + | _ -> false) + (* Tests that the slot behind the commitment has its size bounded by [t.slot_size]. *) let test_commitment_proof = -- GitLab From 28e334d12b698e4b516643e9c6bf66beee0962cc Mon Sep 17 00:00:00 2001 From: marcbeunardeau Date: Wed, 14 Feb 2024 16:07:46 +0100 Subject: [PATCH 7/7] DAL/cryptobox.mli : add comment --- src/lib_crypto_dal/cryptobox.mli | 34 ++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) diff --git a/src/lib_crypto_dal/cryptobox.mli b/src/lib_crypto_dal/cryptobox.mli index c0716a12bf44..184733a104bf 100644 --- a/src/lib_crypto_dal/cryptobox.mli +++ b/src/lib_crypto_dal/cryptobox.mli @@ -321,6 +321,40 @@ val verify_shard : | `Shard_index_out_of_range of string ] ) Result.t +(** + Batched version of verify_shard, for better verifier performance. + [verify_shard_multi t commitment shard_list proof_list] + returns [Ok ()] + if for all i List.nth i [shard] is an element of [shards_from_polynomial p] + where [commitment = commit t p] for some polynomial [p], + and the proofs are correctly generated. + + The verification time smaller than calling List.lenght shard_list + times the verify_shard function. + + Requires: + - The SRS (structured reference string) contained in [t] + should be the same as the one used to produce the [commitment] + and [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_length_mismatch] if one of the shard is not of the expected + length [shard_length] given for the initialisation of [t] + - [Error (`Shard_index_out_of_range msg)] if one of the shard index + is not within the range [0, number_of_shards - 1] + (where [number_of_shards] is found in [t]). + + Ensures: + - [verify_shard_multi t commitment shard_list proof_list = Ok ()] if + and only if + [Array.mem (List.nth i shard_list) (shards_from_polynomial t polynomial]), + [precomputation = precompute_shards_proofs t], + [List.nth i proof_list = (prove_shards t ~precomputation ~polynomial). + (List. nth i (shard_list.index))], for all i + and [commitment = commit t p]. *) val verify_shard_multi : t -> commitment -> -- GitLab