From e1f24f06d18cec3455d2f80715a188d9bc3a4b47 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 18:52:26 +0200 Subject: [PATCH 01/22] DAL/crypto: simplify slot segment proof --- src/lib_crypto_dal/dal_cryptobox.ml | 45 ++--------------------------- 1 file changed, 2 insertions(+), 43 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index 94a8725710b7..7a720660208f 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -551,18 +551,6 @@ module Inner = struct let* data = polynomial_from_bytes' t slot in Ok (Evaluations.interpolation_fft2 t.domain_k data) - let eval_coset_array t eval segment = - let coset = - Array.init - (1 lsl Z.(log2up (of_int t.segment_len))) - (fun _ -> Scalar.(copy zero)) - in - for elt = 0 to t.segment_len - 1 do - let idx = (elt * t.nb_segments) + segment in - coset.(elt) <- Array.get eval idx - done ; - coset - let eval_coset t eval slot offset segment = for elt = 0 to t.segment_len - 1 do let idx = (elt * t.nb_segments) + segment in @@ -828,43 +816,14 @@ module Inner = struct (proof, G2.(add h_secret (negate (mul (copy one) point)))); ]) - (* Assumptions: - - Polynomial.degree p = k - - (x^l - z) | p(x) - Computes the quotient of the division of p(x) by (x^l - z). *) - let compute_quotient t p l z = - let div = Array.init (t.k - l + 1) (fun _ -> Scalar.(copy zero)) in - let i = ref 0 in - (* Computes 1/(x^l - z) mod x^{k - l + 1} - = \sum_{i=0}^{+\infty} -z^{-1}^{i+1} X^{i\times l} mod x^{k - l + 1}. *) - while !i * l < t.k - l + 1 do - div.(!i * l) <- - Scalar.negate (Scalar.inverse_exn (Scalar.pow z (Z.of_int (!i + 1)))) ; - i := !i + 1 - done ; - let div = Polynomials.of_dense div in - (* p(x) * 1/(x^l - z) mod x^{k - l + 1} = q(x) since deg q <= k - l. *) - fft_mul t.domain_2k [p; div] |> Polynomials.copy ~len:(t.k - l + 1) - let prove_segment t trusted_setup p segment_index = if segment_index < 0 || segment_index >= t.nb_segments then Error `Segment_index_out_of_range else let l = 1 lsl Z.(log2up (of_int t.segment_len)) in let wi = Domains.get t.domain_k segment_index in - let domain = Domains.build ~log:Z.(log2up (of_int t.segment_len)) in - let eval_p = Evaluations.(evaluation_fft t.domain_k p |> to_array) in - let eval_coset = eval_coset_array t eval_p segment_index in - let remainder = - Kate_amortized.interpolation_h_poly wi domain eval_coset - |> Array.of_list |> Polynomials.of_dense - in - let quotient = - compute_quotient - t - (Polynomials.sub p remainder) - l - (Scalar.pow wi (Z.of_int l)) + let quotient, _ = + Polynomials.division_xn p l Scalar.(negate (pow wi (Z.of_int l))) in commit trusted_setup quotient -- GitLab From f3cd80b69eac688ca602a4ce7cafa93675c7e4f7 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 18:59:11 +0200 Subject: [PATCH 02/22] DAL/crypto: delete dead code --- src/lib_crypto_dal/kate_amortized.ml | 23 ----------------------- 1 file changed, 23 deletions(-) diff --git a/src/lib_crypto_dal/kate_amortized.ml b/src/lib_crypto_dal/kate_amortized.ml index 8187510dbf2e..bc53874ade73 100644 --- a/src/lib_crypto_dal/kate_amortized.ml +++ b/src/lib_crypto_dal/kate_amortized.ml @@ -39,29 +39,6 @@ module Kate_amortized = struct type srs = G1.t list * G2.t - (* For x ∈ F, create [x^i]₁ list, 0 ≤ i < d. *) - let create_srs1 d x = - let rec encoded_pow_x acc xi i = - if i = 0 then List.rev acc - else encoded_pow_x (xi :: acc) (G1.mul xi x) (i - 1) - in - encoded_pow_x [] G1.(copy one) d - - (* Returns ([[x⁰]₁, [x¹]₁, …, [x^(d-1)]₁], [[x^l]₂]) for x ∈ F and d, l int. *) - let gen_srs ~l ~size:d x = - let xl = Scalar.pow x (Z.of_int l) in - let srs2 = G2.(mul (copy one) xl) in - let l1 = create_srs1 d x in - (l1, srs2) - - (* Returns [[x⁰]₁, [x¹]₁, …, [x^(d-1)]₁] for x ∈ F and d. *) - let gen_srs_g1 ~size:d x = create_srs1 d x - - (* Returns [x^l]₂ for x ∈ F and l int. *) - let gen_srs_g2 ~l x = - let xl = Scalar.pow x (Z.of_int l) in - G2.(mul (copy one) xl) - type commitment = G1.t let commit p (srs1, _) = -- GitLab From 603f282cdfea3c48578679fbce07d1024070322b Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 19:03:18 +0200 Subject: [PATCH 03/22] DAL/crypto: simplify interpolation_h_poly --- src/lib_crypto_dal/kate_amortized.ml | 16 ++++++---------- 1 file changed, 6 insertions(+), 10 deletions(-) diff --git a/src/lib_crypto_dal/kate_amortized.ml b/src/lib_crypto_dal/kate_amortized.ml index bc53874ade73..8feb1b1151e3 100644 --- a/src/lib_crypto_dal/kate_amortized.ml +++ b/src/lib_crypto_dal/kate_amortized.ml @@ -246,17 +246,13 @@ module Kate_amortized = struct (* h = polynomial such that h(y×domain[i]) = zi. *) let interpolation_h_poly y domain z_list = - let h = - Array.to_list (Scalar.ifft ~domain:(Domain.inverse domain) ~points:z_list) - in + Scalar.ifft_inplace ~domain:(Domain.inverse domain) ~points:z_list ; let inv_y = Scalar.inverse_exn y in - let rec mul_h_coefs (inv_yi, acc) h_list = - match h_list with - | [] -> List.rev acc - | h :: tl -> - mul_h_coefs (Scalar.mul inv_yi inv_y, Scalar.mul h inv_yi :: acc) tl - in - mul_h_coefs (Scalar.(copy one), []) h + Array.fold_left_map + (fun inv_yi h -> Scalar.(mul inv_yi inv_y, mul h inv_yi)) + Scalar.(copy one) + z_list + |> snd (* Part 3.2 verifier : verifies that f(w×domain.(i)) = evaluations.(i). *) let verify cm_f (srs1, srs2l) domain (w, evaluations) proof = -- GitLab From 3535e91216d01f33bf4623129021127fd015360f Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Fri, 29 Jul 2022 14:42:18 +0200 Subject: [PATCH 04/22] DAL/crypto: simplify commit --- src/lib_crypto_dal/kate_amortized.ml | 29 ++++++++++++---------------- 1 file changed, 12 insertions(+), 17 deletions(-) diff --git a/src/lib_crypto_dal/kate_amortized.ml b/src/lib_crypto_dal/kate_amortized.ml index 8feb1b1151e3..61abb253f421 100644 --- a/src/lib_crypto_dal/kate_amortized.ml +++ b/src/lib_crypto_dal/kate_amortized.ml @@ -41,22 +41,17 @@ module Kate_amortized = struct type commitment = G1.t - let commit p (srs1, _) = - (* TODO remove these convertions *) - let p = Array.of_list p in - let commit_kate_amortized srs1 p = - if p = [||] then G1.(copy zero) - else if Array.(length p > length srs1) then - raise - (Failure - (Printf.sprintf - "Kzg.compute_encoded_polynomial : Polynomial degree, %i, \ - exceeds srs’ length, %i." - (Array.length p) - (Array.length srs1))) - else G1.pippenger ~start:0 ~len:(Array.length p) srs1 p - in - commit_kate_amortized srs1 p + let commit p srs = + if p = [||] then G1.(copy zero) + else if Array.(length p > length srs) then + raise + (Failure + (Printf.sprintf + "Kzg.compute_encoded_polynomial : Polynomial degree, %i, exceeds \ + srs’ length, %i." + (Array.length p) + (Array.length srs))) + else G1.pippenger ~start:0 ~len:(Array.length p) srs p let inverse domain = let n = Array.length domain in @@ -257,7 +252,7 @@ module Kate_amortized = struct (* Part 3.2 verifier : verifies that f(w×domain.(i)) = evaluations.(i). *) let verify cm_f (srs1, srs2l) domain (w, evaluations) proof = let h = interpolation_h_poly w domain evaluations in - let cm_h = commit h (srs1, srs2l) in + let cm_h = commit h srs1 in let l = Domain.length domain in let sl_min_yl = G2.(add srs2l (negate (mul (copy one) (Scalar.pow w (Z.of_int l))))) -- GitLab From 36191988499327515fb314371aafe2730bdd4de2 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 19:07:17 +0200 Subject: [PATCH 05/22] DAL/crypto: delete dead code --- src/lib_crypto_dal/kate_amortized.ml | 50 ---------------------------- 1 file changed, 50 deletions(-) diff --git a/src/lib_crypto_dal/kate_amortized.ml b/src/lib_crypto_dal/kate_amortized.ml index 61abb253f421..418d812652f5 100644 --- a/src/lib_crypto_dal/kate_amortized.ml +++ b/src/lib_crypto_dal/kate_amortized.ml @@ -73,56 +73,6 @@ module Kate_amortized = struct let res = G1.ifft ~domain:(inverse domain2m) ~points:u in Array.sub res 0 (Array.length domain2m / 2) - (* Complete Toeplitz computation. *) - let build_h_list_complete a_list srs (domain2m : Domain.t) m = - let domain2m_inv = Domain.inverse domain2m in - let domain2m = inverse domain2m_inv in - let y = G1.fft ~domain:domain2m ~points:srs in - let v = Scalar.fft ~domain:domain2m ~points:a_list in - let u = Array.map2 G1.mul y v in - let res = G1.ifft ~domain:domain2m_inv ~points:u in - Array.sub res 0 m - - (* Part 2 *) - - (** coefs = [f₀, f₁, …, fm-1], where m is degree - domain2m = [ω⁰, ω¹, ω², …, ω^(2^k-1)], ω k-th root of unity and 2^k >= 2m - srs1 = [[1]₁, [s]₁, [s²]₁, …, [s^(m-1)]₁] - no verification in code for sizes. *) - let build_ct_list ~nb_proofs ~degree (coefs : Scalar.t list) (srs1, _srs2) - domain2m = - (* dump f₀ because we don’t need it for computation ; add zero at the end of - list to maintain size. *) - let coefs = List.tl (coefs @ [Scalar.(copy zero)]) in - let h_list = - (* Computed following https://alinush.github.io/2020/03/19/multiplying-a-vector-by-a-toeplitz-matrix.html *) - let padded_srs = - List.rev_append srs1 (List.init degree (fun _ -> G1.(copy zero))) - in - let y = Array.of_list padded_srs in - let a_list = - let get_and_remove_last l = - let rec aux acc l = - match l with - | [] -> failwith "Empty list." - | [fm] -> (List.rev acc, fm) - | fi :: h -> aux (fi :: acc) h - in - aux [] l - in - let f_list_without_m, fm = get_and_remove_last coefs in - let rec fill_with_zero_and_fm m acc = - if m = 0 then fm :: acc - else fill_with_zero_and_fm (m - 1) (Scalar.(copy zero) :: acc) - in - fill_with_zero_and_fm degree f_list_without_m - in - build_h_list_complete (Array.of_list a_list) y domain2m degree - in - let domain = Domain.build ~log:nb_proofs in - let domain = inverse (Domain.inverse domain) in - G1.fft ~domain ~points:h_list - (* part 3.2 *) let diff_next_power_of_two x = -- GitLab From c734920dbab4fb2f9fd84a134dda7b876adb8377 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 19:07:47 +0200 Subject: [PATCH 06/22] DAL/crypto: delete signatures --- src/lib_crypto_dal/kate_amortized.ml | 80 ---------------------------- 1 file changed, 80 deletions(-) diff --git a/src/lib_crypto_dal/kate_amortized.ml b/src/lib_crypto_dal/kate_amortized.ml index 418d812652f5..11f83621b208 100644 --- a/src/lib_crypto_dal/kate_amortized.ml +++ b/src/lib_crypto_dal/kate_amortized.ml @@ -210,83 +210,3 @@ module Kate_amortized = struct let diff_commits = G1.(add cm_h (negate cm_f)) in Pairing.pairing_check [(diff_commits, G2.(copy one)); (proof, sl_min_yl)] end - -module type Kate_amortized_sig = sig - module Scalar : Ff_sig.PRIME with type t = Bls12_381.Fr.t - - type srs - - val gen_srs : l:int -> size:int -> Scalar.t -> srs - - val gen_srs_g1 : size:int -> Scalar.t -> srs - - val gen_srs_g2 : l:int -> Scalar.t -> srs - - type proof - - type commitment - - val commit : Scalar.t list -> srs -> commitment - - module Domain : sig - type t - - val build : int -> t - - val get : t -> int -> Scalar.t - - val map : (Scalar.t -> Scalar.t) -> t -> Scalar.t array - end - - (* part 2 proofs *) - - (** [build_ct_list ~nb_proofs:2ⁿ ~degree:m [f₀, f₁, …, fm-1] srs domain2m] - returns multiple proofs for polynomial f₀ + f₁X + … on the 2ⁿ-th roots of - unity *) - val build_ct_list : - nb_proofs:int -> - degree:int -> - Scalar.t list -> - srs -> - Domain.t -> - proof array - - (* part 3.2 proofs *) - - val preprocess_multi_reveals : - chunk_len:int -> - degree:int -> - srs -> - Scalar.t array * commitment array option array - - (** [multiple_multi_reveals_with_preprocessed_srs ~chunk_len:r - ~chunk_count:(n-r) ~degree:m [f₀, f₁, …, fm-1] precomputed] returns the - 2ⁿ⁻ʳ proofs (each proof stands for for 2ʳ evaluations) for polynomial - f₀ + f₁X + … as in part 3.2. *) - val multiple_multi_reveals_with_preprocessed_srs : - chunk_len:int -> - chunk_count:int -> - degree:int -> - Scalar.t list -> - Domain.t * commitment array option array -> - proof array - - (** Same as multiple_multi_reveals_with_preprocessed_srs without preprocessing - the SRS computations. *) - val multiple_multi_reveals : - chunk_len:int -> - chunk_count:int -> - degree:int -> - preprocess:Scalar.t array * commitment array option array -> - Scalar.t list -> - proof array - - (* h = polynomial such that h(y×domain[i]) = zi. *) - val interpolation_h_poly : - Scalar.t -> Domain.t -> Scalar.t array -> Scalar.t list - - (** [verify cm_f srs domain (w, evaluations) proof] returns true iff for all i, - f(w×domain.(i) = evaluations.(i)). *) - val verify : - commitment -> srs -> Domain.t -> Scalar.t * Scalar.t array -> proof -> bool -end -- GitLab From 69263e78551d4ff8609c6b211c56204a8aff1138 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 19:10:06 +0200 Subject: [PATCH 07/22] DAL/crypto: delete extra function --- src/lib_crypto_dal/kate_amortized.ml | 30 ++++++++++------------------ 1 file changed, 10 insertions(+), 20 deletions(-) diff --git a/src/lib_crypto_dal/kate_amortized.ml b/src/lib_crypto_dal/kate_amortized.ml index 11f83621b208..6f67bea6b2d3 100644 --- a/src/lib_crypto_dal/kate_amortized.ml +++ b/src/lib_crypto_dal/kate_amortized.ml @@ -109,13 +109,21 @@ module Kate_amortized = struct in (domain2m, Array.init l precompute_srsj) + (* Generate proofs of part 3.2. *) + (** n, r are powers of two, m = 2^(log2(n)-1) coefs are f polynomial’s coefficients [f₀, f₁, f₂, …, fm-1] domain2m is the set of 2m-th roots of unity, used for Toeplitz computation (domain2m, precomputed_srs_part) = preprocess_multi_reveals r n m (srs1, _srs2) returns proofs of part 3.2. *) - let multiple_multi_reveals_with_preprocessed_srs ~chunk_len ~chunk_count - ~degree coefs (domain2m, precomputed_srs_part) = + let multiple_multi_reveals ~chunk_len ~chunk_count ~degree + ~preprocess:(domain2m, precomputed_srs_part) coefs = + let n = chunk_len + chunk_count in + assert (2 <= chunk_len) ; + assert (chunk_len < n) ; + assert (is_pow_of_two degree) ; + assert (1 lsl chunk_len <= degree) ; + assert (degree <= 1 lsl n) ; let l = 1 lsl chunk_len in (* Since we don’t need the first coefficient f₀, we remove it and add a zero as last coefficient to keep the size unchanged *) @@ -171,24 +179,6 @@ module Kate_amortized = struct let phidomain = inverse (Domain.inverse phidomain) in G1.fft ~domain:phidomain ~points:hl - (* Generate proofs of part 3.2. *) - let multiple_multi_reveals ~chunk_len ~chunk_count ~degree ~preprocess f = - let n = chunk_len + chunk_count in - assert (2 <= chunk_len) ; - assert (chunk_len < n) ; - assert (is_pow_of_two degree) ; - assert (1 lsl chunk_len <= degree) ; - assert (degree <= 1 lsl n) ; - let proof = - multiple_multi_reveals_with_preprocessed_srs - ~chunk_len - ~chunk_count - ~degree - f - preprocess - in - proof - (* h = polynomial such that h(y×domain[i]) = zi. *) let interpolation_h_poly y domain z_list = Scalar.ifft_inplace ~domain:(Domain.inverse domain) ~points:z_list ; -- GitLab From 5646d14b46e95870b5f06fe7c038d5ceb3051c8f Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 19:12:13 +0200 Subject: [PATCH 08/22] DAL/crypto: rename variables --- src/lib_crypto_dal/kate_amortized.ml | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/src/lib_crypto_dal/kate_amortized.ml b/src/lib_crypto_dal/kate_amortized.ml index 6f67bea6b2d3..1f8d5492c365 100644 --- a/src/lib_crypto_dal/kate_amortized.ml +++ b/src/lib_crypto_dal/kate_amortized.ml @@ -88,9 +88,9 @@ module Kate_amortized = struct let preprocess_multi_reveals ~chunk_len ~degree (srs1, _srs2) = let l = 1 lsl chunk_len in let k = - let m_sur_l = degree / l in - let log_inf = Z.log2 (Z.of_int m_sur_l) in - if 1 lsl log_inf < m_sur_l then log_inf else log_inf + 1 + let ratio = degree / l in + let log_inf = Z.log2 (Z.of_int ratio) in + if 1 lsl log_inf < ratio then log_inf else log_inf + 1 in let domain2m = Domain.build ~log:k in let precompute_srsj j = -- GitLab From 25d60fe627ec9de4cc97a47ed7e32dd7b3d79914 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 19:13:27 +0200 Subject: [PATCH 09/22] DAL/crypto: fix assert --- src/lib_crypto_dal/kate_amortized.ml | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/src/lib_crypto_dal/kate_amortized.ml b/src/lib_crypto_dal/kate_amortized.ml index 1f8d5492c365..888f2d19dd82 100644 --- a/src/lib_crypto_dal/kate_amortized.ml +++ b/src/lib_crypto_dal/kate_amortized.ml @@ -95,8 +95,6 @@ module Kate_amortized = struct let domain2m = Domain.build ~log:k in let precompute_srsj j = let quotient = (degree - j) / l in - (*if quotient = 0 then None - else*) let padding = diff_next_power_of_two (2 * quotient) in let srsj = Array.init @@ -122,7 +120,7 @@ module Kate_amortized = struct assert (2 <= chunk_len) ; assert (chunk_len < n) ; assert (is_pow_of_two degree) ; - assert (1 lsl chunk_len <= degree) ; + assert (1 lsl chunk_len < degree) ; assert (degree <= 1 lsl n) ; let l = 1 lsl chunk_len in (* Since we don’t need the first coefficient f₀, we remove it and add a zero -- GitLab From 36af3b2f4a0fb20c0de44c1191a259b8803ebc00 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Fri, 29 Jul 2022 11:23:19 +0200 Subject: [PATCH 10/22] DAL/crypto: delete kate amortized module --- src/lib_crypto_dal/dal_cryptobox.ml | 219 +++++++++++++++--- src/lib_crypto_dal/dal_cryptobox.mli | 8 +- src/lib_crypto_dal/dal_cryptobox_intf.ml | 5 +- src/lib_crypto_dal/kate_amortized.ml | 200 ---------------- src/lib_crypto_dal/test/test_dal_cryptobox.ml | 6 +- 5 files changed, 200 insertions(+), 238 deletions(-) delete mode 100644 src/lib_crypto_dal/kate_amortized.ml diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index 7a720660208f..43abb6495a49 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -61,8 +61,6 @@ let () = (fun parameter -> No_trusted_setup parameter) module Inner = struct - open Kate_amortized - (* Scalars are elements of the prime field Fr from BLS. *) module Scalar = Bls12_381.Fr module Polynomial = Bls12_381_polynomial.Polynomial @@ -81,9 +79,9 @@ module Inner = struct type polynomial = Polynomials.t - type commitment = Kate_amortized.commitment + type commitment = Bls12_381.G1.t - type shard_proof = Kate_amortized.proof + type shard_proof = Bls12_381.G1.t type commitment_proof = Bls12_381.G1.t @@ -694,11 +692,10 @@ module Inner = struct let commit' : type t. (module Bls12_381.CURVE with type t = t) -> - polynomial -> + scalar array -> t array -> (t, [> `Degree_exceeds_srs_length of string]) Result.t = fun (module G) p srs -> - let p = Polynomials.to_dense_coefficients p in if p = [||] then Ok G.(copy zero) else if Array.(length p > length srs) then Error @@ -710,7 +707,10 @@ module Inner = struct else Ok (G.pippenger ~start:0 ~len:(Array.length p) srs p) let commit trusted_setup p = - commit' (module Bls12_381.G1) p trusted_setup.srs_g1 + commit' + (module Bls12_381.G1) + (Polynomials.to_dense_coefficients p) + trusted_setup.srs_g1 (* p(X) of degree n. Max degree that can be committed: d, which is also the SRS's length - 1. We take d = k - 1 since we don't want to commit @@ -726,7 +726,9 @@ module Inner = struct let prove_commitment trusted_setup p = commit' (module Bls12_381.G1) - (Polynomials.mul (Polynomials.of_coefficients [(Scalar.(copy one), 0)]) p) + Polynomials.( + to_dense_coefficients + (mul (Polynomials.of_coefficients [(Scalar.(copy one), 0)]) p)) trusted_setup.srs_g1 (* FIXME https://gitlab.com/tezos/tezos/-/issues/3389 @@ -736,19 +738,169 @@ module Inner = struct let open Result_syntax in let open Bls12_381 in let* commit_xk = - commit' - (module G2) - (Polynomials.of_coefficients [(Scalar.(copy one), 0)]) - trusted_setup.srs_g2 + commit' (module G2) [|Scalar.(copy one)|] trusted_setup.srs_g2 in Ok (Pairing.pairing_check [(cm, commit_xk); (proof, G2.(negate (copy one)))]) + let inverse domain = + let n = Array.length domain in + Array.init n (fun i -> + if i = 0 then Bls12_381.Fr.(copy one) else Array.get domain (n - i)) + + (* First part of Toeplitz computing trick involving srs. *) + let build_srs_part_h_list srs domain2m = + let domain2m = inverse (Domains.inverse domain2m) in + Bls12_381.G1.fft ~domain:domain2m ~points:srs + + let build_h_list_with_precomputed_srs a_list (domain2m, precomputed_srs) = + let y = precomputed_srs in + let v = Scalar.fft ~domain:domain2m ~points:a_list in + Array.map2 (fun yi vi -> Bls12_381.G1.mul yi vi) y v + + (* Final ifft of Toeplitz computation. *) + let build_h_list_final u domain2m = + let res = Bls12_381.G1.ifft ~domain:(inverse domain2m) ~points:u in + Array.sub res 0 (Array.length domain2m / 2) + + (* part 3.2 *) + + let diff_next_power_of_two x = + let logx = Z.log2 (Z.of_int x) in + if 1 lsl logx = x then 0 else (1 lsl (logx + 1)) - x + + let is_pow_of_two x = + let logx = Z.log2 (Z.of_int x) in + 1 lsl logx = x + + (* Implementation of fast amortized Kate proofs + https://github.com/khovratovich/Kate/blob/master/Kate_amortized.pdf). *) + + (* Precompute first part of Toeplitz trick, which doesn't depends on the + polynomial’s coefficients. *) + let preprocess_multi_reveals ~chunk_len ~degree (srs1, _srs2) = + let l = 1 lsl chunk_len in + let k = + let ratio = degree / l in + let log_inf = Z.log2 (Z.of_int ratio) in + if 1 lsl log_inf < ratio then log_inf else log_inf + 1 + in + let domain2m = Domains.build ~log:k in + let precompute_srsj j = + let quotient = (degree - j) / l in + let padding = diff_next_power_of_two (2 * quotient) in + let srsj = + Array.init + ((2 * quotient) + padding) + (fun i -> + if i < quotient then srs1.(degree - j - ((i + 1) * l)) + else Bls12_381.G1.(copy zero)) + in + build_srs_part_h_list srsj domain2m + in + (domain2m, Array.init l precompute_srsj) + + (** Generate proofs of part 3.2. + n, r are powers of two, m = 2^(log2(n)-1) + coefs are f polynomial’s coefficients [f₀, f₁, f₂, …, fm-1] + domain2m is the set of 2m-th roots of unity, used for Toeplitz computation + (domain2m, precomputed_srs_part) = preprocess_multi_reveals r n m (srs1, _srs2) + *) + let multiple_multi_reveals ~chunk_len ~chunk_count ~degree + ~preprocess:(domain2m, precomputed_srs_part) coefs = + let n = chunk_len + chunk_count in + assert (2 <= chunk_len) ; + assert (chunk_len < n) ; + assert (is_pow_of_two degree) ; + assert (1 lsl chunk_len < degree) ; + assert (degree <= 1 lsl n) ; + let l = 1 lsl chunk_len in + (* Since we don’t need the first coefficient f₀, we remove it and add a zero + as last coefficient to keep the size unchanged *) + let coefs = List.tl (coefs @ [Scalar.(copy zero)]) in + let coefs = Array.of_list coefs in + let compute_h_j j = + let rest = (degree - j) mod l in + let quotient = (degree - j) / l in + if quotient = 0 then None + else + (* Padding in case quotient is not a power of 2 to get proper fft in + Toeplitz matrix part. *) + let padding = diff_next_power_of_two (2 * quotient) in + let a_list = + (* fm, 0, …, 0, f₁, f₂, …, fm-1 *) + let a_array = + Array.init + ((2 * quotient) + padding) + (fun i -> + if i <= quotient + (padding / 2) then Scalar.(copy zero) + else coefs.(rest + ((i - (quotient + padding)) * l) - 1)) + in + a_array.(0) <- coefs.(degree - j - 1) ; + a_array + in + let res = + Some + (* Toeplitz stuff *) + (build_h_list_with_precomputed_srs + a_list + (domain2m, precomputed_srs_part.(j))) + in + res + in + let hl : segment_proof array = + match compute_h_j 0 with + | None -> [||] + | Some sum -> + let rec sum_hj j = + if j = l then () + else + match compute_h_j j with + | None -> () + | Some hj -> + (* sum.(i) <- sum.(i) + hj.(i) *) + Array.iteri + (fun i hij -> sum.(i) <- Bls12_381.G1.add sum.(i) hij) + hj ; + sum_hj (j + 1) + in + sum_hj 1 ; + build_h_list_final sum domain2m + in + let phidomain = Domains.build ~log:chunk_count in + let phidomain = inverse (Domains.inverse phidomain) in + Bls12_381.G1.fft ~domain:phidomain ~points:hl + + (* h = polynomial such that h(y×domain[i]) = zi. *) + let interpolation_h_poly y domain z_list = + Scalar.ifft_inplace ~domain:(Domains.inverse domain) ~points:z_list ; + let inv_y = Scalar.inverse_exn y in + Array.fold_left_map + (fun inv_yi h -> Scalar.(mul inv_yi inv_y, mul h inv_yi)) + Scalar.(copy one) + z_list + |> snd + + (* Part 3.2 verifier : verifies that f(w×domain.(i)) = evaluations.(i). *) + let verify cm_f (srs1, srs2l) domain (w, evaluations) proof = + let open Bls12_381 in + let open Result_syntax in + let h = interpolation_h_poly w domain evaluations in + let* cm_h = commit' (module G1) h srs1 in + let l = Domains.length domain in + let sl_min_yl = + G2.(add srs2l (negate (mul (copy one) (Scalar.pow w (Z.of_int l))))) + in + let diff_commits = G1.(add cm_h (negate cm_f)) in + Ok + (Pairing.pairing_check + [(diff_commits, G2.(copy one)); (proof, sl_min_yl)]) + let eval_to_array e = Array.init (Domains.length e) (Domains.get e) let precompute_shards_proofs t trusted_setup = let eval, m = - Kate_amortized.preprocess_multi_reveals + preprocess_multi_reveals ~chunk_len:t.evaluations_per_proof_log ~degree:t.k (trusted_setup.srs_g1, trusted_setup.kate_amortized_srs_g2_shards) @@ -780,7 +932,7 @@ module Inner = struct let prove_shards t srs p = let preprocess = precompute_shards_proofs t srs in - Kate_amortized.multiple_multi_reveals + multiple_multi_reveals ~chunk_len:t.evaluations_per_proof_log ~chunk_count:t.proofs_log ~degree:t.k @@ -789,22 +941,24 @@ module Inner = struct let verify_shard t trusted_setup cm {index = shard_index; share = shard_evaluations} proof = - let d_n = Kate_amortized.Domain.build ~log:t.evaluations_log in - let domain = Kate_amortized.Domain.build ~log:t.evaluations_per_proof_log in - Kate_amortized.verify + let d_n = Domains.build ~log:t.evaluations_log in + let domain = Domains.build ~log:t.evaluations_per_proof_log in + verify cm (trusted_setup.srs_g1, trusted_setup.kate_amortized_srs_g2_shards) domain - (Kate_amortized.Domain.get d_n shard_index, shard_evaluations) + (Domains.get d_n shard_index, shard_evaluations) proof let _prove_single trusted_setup p z = - let q = - fst - @@ Polynomials.( - division_xn (p - constant (evaluate p z)) 1 (Scalar.negate z)) + let q, _ = + Polynomials.( + division_xn (p - constant (evaluate p z)) 1 (Scalar.negate z)) in - commit' (module Bls12_381.G1) q trusted_setup.srs_g1 + commit' + (module Bls12_381.G1) + (Polynomials.to_dense_coefficients q) + trusted_setup.srs_g1 let _verify_single trusted_setup cm ~point ~evaluation proof = let h_secret = Array.get trusted_setup.srs_g2 1 in @@ -823,7 +977,7 @@ module Inner = struct let l = 1 lsl Z.(log2up (of_int t.segment_len)) in let wi = Domains.get t.domain_k segment_index in let quotient, _ = - Polynomials.division_xn p l Scalar.(negate (pow wi (Z.of_int l))) + Polynomials.(division_xn p l Scalar.(negate (pow wi (Z.of_int l)))) in commit trusted_setup quotient @@ -834,9 +988,7 @@ module Inner = struct if slot_segment_index < 0 || slot_segment_index >= t.nb_segments then Error `Slot_segment_index_out_of_range else - let domain = - Kate_amortized.Domain.build ~log:Z.(log2up (of_int t.segment_len)) - in + let domain = Domains.build ~log:Z.(log2up (of_int t.segment_len)) in let slot_segment_evaluations = Array.init (1 lsl Z.(log2up (of_int t.segment_len))) @@ -861,13 +1013,12 @@ module Inner = struct Scalar.of_bytes_exn dst | _ -> Scalar.(copy zero)) in - Ok - (Kate_amortized.verify - cm - (trusted_setup.srs_g1, trusted_setup.kate_amortized_srs_g2_segments) - domain - (Domains.get t.domain_k slot_segment_index, slot_segment_evaluations) - proof) + verify + cm + (trusted_setup.srs_g1, trusted_setup.kate_amortized_srs_g2_segments) + domain + (Domains.get t.domain_k slot_segment_index, slot_segment_evaluations) + proof end include Inner diff --git a/src/lib_crypto_dal/dal_cryptobox.mli b/src/lib_crypto_dal/dal_cryptobox.mli index 0d80fb5bcf4a..afae376490db 100644 --- a/src/lib_crypto_dal/dal_cryptobox.mli +++ b/src/lib_crypto_dal/dal_cryptobox.mli @@ -152,7 +152,13 @@ type shard_proof [commitment] using [proof]. The verification time is constant. The [srs] should be the same as the one used to produce the commitment. *) -val verify_shard : t -> srs -> commitment -> shard -> shard_proof -> bool +val verify_shard : + t -> + srs -> + commitment -> + shard -> + shard_proof -> + (bool, [> `Degree_exceeds_srs_length of string]) result (** [prove_commitment srs polynomial] produces a proof that the commitment produced by the function [commit] is indeed a diff --git a/src/lib_crypto_dal/dal_cryptobox_intf.ml b/src/lib_crypto_dal/dal_cryptobox_intf.ml index 73005e70edd1..fb9e459a75df 100644 --- a/src/lib_crypto_dal/dal_cryptobox_intf.ml +++ b/src/lib_crypto_dal/dal_cryptobox_intf.ml @@ -123,5 +123,8 @@ module type VERIFIER = sig commitment -> segment -> segment_proof -> - (bool, [> `Slot_segment_index_out_of_range]) Result.t + ( bool, + [> `Degree_exceeds_srs_length of string | `Slot_segment_index_out_of_range] + ) + Result.t end diff --git a/src/lib_crypto_dal/kate_amortized.ml b/src/lib_crypto_dal/kate_amortized.ml deleted file mode 100644 index 888f2d19dd82..000000000000 --- a/src/lib_crypto_dal/kate_amortized.ml +++ /dev/null @@ -1,200 +0,0 @@ -(*****************************************************************************) -(* *) -(* Open Source License *) -(* Copyright (c) 2022 Nomadic Labs *) -(* *) -(* Permission is hereby granted, free of charge, to any person obtaining a *) -(* copy of this software and associated documentation files (the "Software"),*) -(* to deal in the Software without restriction, including without limitation *) -(* the rights to use, copy, modify, merge, publish, distribute, sublicense, *) -(* and/or sell copies of the Software, and to permit persons to whom the *) -(* Software is furnished to do so, subject to the following conditions: *) -(* *) -(* The above copyright notice and this permission notice shall be included *) -(* in all copies or substantial portions of the Software. *) -(* *) -(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*) -(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *) -(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL *) -(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*) -(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING *) -(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER *) -(* DEALINGS IN THE SOFTWARE. *) -(* *) -(*****************************************************************************) - -(* Implementation of fast amortized Kate proofs - https://github.com/khovratovich/Kate/blob/master/Kate_amortized.pdf). *) - -module Kate_amortized = struct - module Scalar = Bls12_381.Fr - module G1 = Bls12_381.G1 - module G2 = Bls12_381.G2 - module GT = Bls12_381.GT - module Pairing = Bls12_381.Pairing - module Domain = Bls12_381_polynomial.Polynomial.Domain - module Polynomial = Bls12_381_polynomial.Polynomial - - type proof = G1.t - - type srs = G1.t list * G2.t - - type commitment = G1.t - - let commit p srs = - if p = [||] then G1.(copy zero) - else if Array.(length p > length srs) then - raise - (Failure - (Printf.sprintf - "Kzg.compute_encoded_polynomial : Polynomial degree, %i, exceeds \ - srs’ length, %i." - (Array.length p) - (Array.length srs))) - else G1.pippenger ~start:0 ~len:(Array.length p) srs p - - let inverse domain = - let n = Array.length domain in - Array.init n (fun i -> - if i = 0 then Bls12_381.Fr.(copy one) else Array.get domain (n - i)) - - (* First part of Toeplitz computing trick involving srs. *) - let build_srs_part_h_list srs domain2m = - let domain2m = inverse (Domain.inverse domain2m) in - G1.fft ~domain:domain2m ~points:srs - - let build_h_list_with_precomputed_srs a_list (domain2m, precomputed_srs) = - let y = precomputed_srs in - let v = Scalar.fft ~domain:domain2m ~points:a_list in - Array.map2 (fun yi vi -> G1.mul yi vi) y v - - (* Final ifft of Toeplitz computation. *) - let build_h_list_final u domain2m = - let res = G1.ifft ~domain:(inverse domain2m) ~points:u in - Array.sub res 0 (Array.length domain2m / 2) - - (* part 3.2 *) - - let diff_next_power_of_two x = - let logx = Z.log2 (Z.of_int x) in - if 1 lsl logx = x then 0 else (1 lsl (logx + 1)) - x - - let is_pow_of_two x = - let logx = Z.log2 (Z.of_int x) in - 1 lsl logx = x - - (* Precompute first part of Toeplitz trick, which doesn't depends on the - polynomial’s coefficients. *) - let preprocess_multi_reveals ~chunk_len ~degree (srs1, _srs2) = - let l = 1 lsl chunk_len in - let k = - let ratio = degree / l in - let log_inf = Z.log2 (Z.of_int ratio) in - if 1 lsl log_inf < ratio then log_inf else log_inf + 1 - in - let domain2m = Domain.build ~log:k in - let precompute_srsj j = - let quotient = (degree - j) / l in - let padding = diff_next_power_of_two (2 * quotient) in - let srsj = - Array.init - ((2 * quotient) + padding) - (fun i -> - if i < quotient then srs1.(degree - j - ((i + 1) * l)) - else G1.(copy zero)) - in - build_srs_part_h_list srsj domain2m - in - (domain2m, Array.init l precompute_srsj) - - (* Generate proofs of part 3.2. *) - - (** n, r are powers of two, m = 2^(log2(n)-1) - coefs are f polynomial’s coefficients [f₀, f₁, f₂, …, fm-1] - domain2m is the set of 2m-th roots of unity, used for Toeplitz computation - (domain2m, precomputed_srs_part) = preprocess_multi_reveals r n m (srs1, _srs2) - returns proofs of part 3.2. *) - let multiple_multi_reveals ~chunk_len ~chunk_count ~degree - ~preprocess:(domain2m, precomputed_srs_part) coefs = - let n = chunk_len + chunk_count in - assert (2 <= chunk_len) ; - assert (chunk_len < n) ; - assert (is_pow_of_two degree) ; - assert (1 lsl chunk_len < degree) ; - assert (degree <= 1 lsl n) ; - let l = 1 lsl chunk_len in - (* Since we don’t need the first coefficient f₀, we remove it and add a zero - as last coefficient to keep the size unchanged *) - let coefs = List.tl (coefs @ [Scalar.(copy zero)]) in - let coefs = Array.of_list coefs in - let compute_h_j j = - let rest = (degree - j) mod l in - let quotient = (degree - j) / l in - if quotient = 0 then None - else - (* Padding in case quotient is not a power of 2 to get proper fft in - Toeplitz matrix part. *) - let padding = diff_next_power_of_two (2 * quotient) in - let a_list = - (* fm, 0, …, 0, f₁, f₂, …, fm-1 *) - let a_array = - Array.init - ((2 * quotient) + padding) - (fun i -> - if i <= quotient + (padding / 2) then Scalar.(copy zero) - else coefs.(rest + ((i - (quotient + padding)) * l) - 1)) - in - a_array.(0) <- coefs.(degree - j - 1) ; - a_array - in - let res = - Some - (* Toeplitz stuff *) - (build_h_list_with_precomputed_srs - a_list - (domain2m, precomputed_srs_part.(j))) - in - res - in - let hl = - match compute_h_j 0 with - | None -> failwith "Nothing to compute." - | Some sum -> - let rec sum_hj j = - if j = l then () - else - match compute_h_j j with - | None -> () - | Some hj -> - (* sum.(i) <- sum.(i) + hj.(i) *) - Array.iteri (fun i hij -> sum.(i) <- G1.add sum.(i) hij) hj ; - sum_hj (j + 1) - in - sum_hj 1 ; - build_h_list_final sum domain2m - in - let phidomain = Domain.build ~log:chunk_count in - let phidomain = inverse (Domain.inverse phidomain) in - G1.fft ~domain:phidomain ~points:hl - - (* h = polynomial such that h(y×domain[i]) = zi. *) - let interpolation_h_poly y domain z_list = - Scalar.ifft_inplace ~domain:(Domain.inverse domain) ~points:z_list ; - let inv_y = Scalar.inverse_exn y in - Array.fold_left_map - (fun inv_yi h -> Scalar.(mul inv_yi inv_y, mul h inv_yi)) - Scalar.(copy one) - z_list - |> snd - - (* Part 3.2 verifier : verifies that f(w×domain.(i)) = evaluations.(i). *) - let verify cm_f (srs1, srs2l) domain (w, evaluations) proof = - let h = interpolation_h_poly w domain evaluations in - let cm_h = commit h srs1 in - let l = Domain.length domain in - let sl_min_yl = - G2.(add srs2l (negate (mul (copy one) (Scalar.pow w (Z.of_int l))))) - in - let diff_commits = G1.(add cm_h (negate cm_f)) in - Pairing.pairing_check [(diff_commits, G2.(copy one)); (proof, sl_min_yl)] -end diff --git a/src/lib_crypto_dal/test/test_dal_cryptobox.ml b/src/lib_crypto_dal/test/test_dal_cryptobox.ml index e08a177d1d8b..c200ee887389 100644 --- a/src/lib_crypto_dal/test/test_dal_cryptobox.ml +++ b/src/lib_crypto_dal/test/test_dal_cryptobox.ml @@ -94,13 +94,15 @@ module Test = struct match Dal_cryptobox.IntMap.find 0 enc_shards with | None -> Ok () | Some eval -> - assert ( + let* check = Dal_cryptobox.verify_shard t trusted_setup comm {index = 0; share = eval} - shard_proofs.(0)) ; + shard_proofs.(0) + in + assert check ; let* pi = Dal_cryptobox.prove_commitment trusted_setup p in let* check = -- GitLab From 5d40d9f6e3b998a7caaeb324a2e0bca072f1b826 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 19:52:24 +0200 Subject: [PATCH 11/22] DAL/crypto: simplify multi-multi reveal --- src/lib_crypto_dal/dal_cryptobox.ml | 71 ++++++++++++----------------- 1 file changed, 29 insertions(+), 42 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index 43abb6495a49..d5c16a02d1cd 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -822,50 +822,37 @@ module Inner = struct let compute_h_j j = let rest = (degree - j) mod l in let quotient = (degree - j) / l in - if quotient = 0 then None - else - (* Padding in case quotient is not a power of 2 to get proper fft in - Toeplitz matrix part. *) - let padding = diff_next_power_of_two (2 * quotient) in - let a_list = - (* fm, 0, …, 0, f₁, f₂, …, fm-1 *) - let a_array = - Array.init - ((2 * quotient) + padding) - (fun i -> - if i <= quotient + (padding / 2) then Scalar.(copy zero) - else coefs.(rest + ((i - (quotient + padding)) * l) - 1)) - in - a_array.(0) <- coefs.(degree - j - 1) ; - a_array - in - let res = - Some - (* Toeplitz stuff *) - (build_h_list_with_precomputed_srs - a_list - (domain2m, precomputed_srs_part.(j))) + (* Padding in case quotient is not a power of 2 to get proper fft in + Toeplitz matrix part. *) + let padding = diff_next_power_of_two (2 * quotient) in + let a_list = + (* fm, 0, …, 0, f₁, f₂, …, fm-1 *) + let a_array = + Array.init + ((2 * quotient) + padding) + (fun i -> + if i <= quotient + (padding / 2) then Scalar.(copy zero) + else coefs.(rest + ((i - (quotient + padding)) * l) - 1)) in - res + a_array.(0) <- coefs.(degree - j - 1) ; + a_array + in + build_h_list_with_precomputed_srs + a_list + (domain2m, precomputed_srs_part.(j)) in - let hl : segment_proof array = - match compute_h_j 0 with - | None -> [||] - | Some sum -> - let rec sum_hj j = - if j = l then () - else - match compute_h_j j with - | None -> () - | Some hj -> - (* sum.(i) <- sum.(i) + hj.(i) *) - Array.iteri - (fun i hij -> sum.(i) <- Bls12_381.G1.add sum.(i) hij) - hj ; - sum_hj (j + 1) - in - sum_hj 1 ; - build_h_list_final sum domain2m + let sum = compute_h_j 0 in + let hl = + let rec sum_hj j = + if j = l then () + else + let hj = compute_h_j j in + (* sum.(i) <- sum.(i) + hj.(i) *) + Array.iteri (fun i hij -> sum.(i) <- Bls12_381.G1.add sum.(i) hij) hj ; + sum_hj (j + 1) + in + sum_hj 1 ; + build_h_list_final sum domain2m in let phidomain = Domains.build ~log:chunk_count in let phidomain = inverse (Domains.inverse phidomain) in -- GitLab From 507fa61147a60386408a07053d1d731a8e4e6674 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 19:59:59 +0200 Subject: [PATCH 12/22] DAL/crypto: simplify multi reveal preprocessing --- src/lib_crypto_dal/dal_cryptobox.ml | 28 +++++++++------------------- 1 file changed, 9 insertions(+), 19 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index d5c16a02d1cd..f45044a4e0a7 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -748,11 +748,6 @@ module Inner = struct Array.init n (fun i -> if i = 0 then Bls12_381.Fr.(copy one) else Array.get domain (n - i)) - (* First part of Toeplitz computing trick involving srs. *) - let build_srs_part_h_list srs domain2m = - let domain2m = inverse (Domains.inverse domain2m) in - Bls12_381.G1.fft ~domain:domain2m ~points:srs - let build_h_list_with_precomputed_srs a_list (domain2m, precomputed_srs) = let y = precomputed_srs in let v = Scalar.fft ~domain:domain2m ~points:a_list in @@ -778,14 +773,14 @@ module Inner = struct (* Precompute first part of Toeplitz trick, which doesn't depends on the polynomial’s coefficients. *) - let preprocess_multi_reveals ~chunk_len ~degree (srs1, _srs2) = + let preprocess_multi_reveals ~chunk_len ~degree srs1 = let l = 1 lsl chunk_len in let k = let ratio = degree / l in let log_inf = Z.log2 (Z.of_int ratio) in if 1 lsl log_inf < ratio then log_inf else log_inf + 1 in - let domain2m = Domains.build ~log:k in + let domain = Domains.build ~log:k |> Domains.inverse |> inverse in let precompute_srsj j = let quotient = (degree - j) / l in let padding = diff_next_power_of_two (2 * quotient) in @@ -796,15 +791,15 @@ module Inner = struct if i < quotient then srs1.(degree - j - ((i + 1) * l)) else Bls12_381.G1.(copy zero)) in - build_srs_part_h_list srsj domain2m + Bls12_381.G1.fft ~domain ~points:srsj in - (domain2m, Array.init l precompute_srsj) + (domain, Array.init l precompute_srsj) (** Generate proofs of part 3.2. n, r are powers of two, m = 2^(log2(n)-1) coefs are f polynomial’s coefficients [f₀, f₁, f₂, …, fm-1] domain2m is the set of 2m-th roots of unity, used for Toeplitz computation - (domain2m, precomputed_srs_part) = preprocess_multi_reveals r n m (srs1, _srs2) + (domain2m, precomputed_srs_part) = preprocess_multi_reveals r n m srs1 *) let multiple_multi_reveals ~chunk_len ~chunk_count ~degree ~preprocess:(domain2m, precomputed_srs_part) coefs = @@ -883,16 +878,11 @@ module Inner = struct (Pairing.pairing_check [(diff_commits, G2.(copy one)); (proof, sl_min_yl)]) - let eval_to_array e = Array.init (Domains.length e) (Domains.get e) - let precompute_shards_proofs t trusted_setup = - let eval, m = - preprocess_multi_reveals - ~chunk_len:t.evaluations_per_proof_log - ~degree:t.k - (trusted_setup.srs_g1, trusted_setup.kate_amortized_srs_g2_shards) - in - (eval_to_array eval, m) + preprocess_multi_reveals + ~chunk_len:t.evaluations_per_proof_log + ~degree:t.k + trusted_setup.srs_g1 let _save_precompute_shards_proofs (preprocess : shards_proofs_precomputation) filename = -- GitLab From 48398b4a14c9c42b1cd7f9b16b1a2d89fd2c203e Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Mon, 25 Jul 2022 23:25:56 +0200 Subject: [PATCH 13/22] DAL/crypto: fix srs length --- src/lib_crypto_dal/dal_cryptobox.ml | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index f45044a4e0a7..42854fff7b99 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -340,8 +340,8 @@ module Inner = struct Scalar.of_string "20812168509434597367146703229805575690060615791308155437936410982393987532344" in - let srs_g1 = create_srs (module Bls12_381.G1) t.slot_size secret in - let srs_g2 = create_srs (module Bls12_381.G2) t.slot_size secret in + let srs_g1 = create_srs (module Bls12_381.G1) t.k secret in + let srs_g2 = create_srs (module Bls12_381.G2) t.k secret in { srs_g1; srs_g2; -- GitLab From ec30ac170fc6a2c557ececb2ec6934692d0547b4 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Tue, 26 Jul 2022 11:04:09 +0200 Subject: [PATCH 14/22] DAL/crypto: use inplace FFTs --- src/lib_crypto_dal/dal_cryptobox.ml | 75 +++++++++++++---------------- 1 file changed, 34 insertions(+), 41 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index 42854fff7b99..0c3ecc91d3f5 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -749,14 +749,8 @@ module Inner = struct if i = 0 then Bls12_381.Fr.(copy one) else Array.get domain (n - i)) let build_h_list_with_precomputed_srs a_list (domain2m, precomputed_srs) = - let y = precomputed_srs in - let v = Scalar.fft ~domain:domain2m ~points:a_list in - Array.map2 (fun yi vi -> Bls12_381.G1.mul yi vi) y v - - (* Final ifft of Toeplitz computation. *) - let build_h_list_final u domain2m = - let res = Bls12_381.G1.ifft ~domain:(inverse domain2m) ~points:u in - Array.sub res 0 (Array.length domain2m / 2) + Scalar.fft_inplace ~domain:domain2m ~points:a_list ; + Array.map2 Bls12_381.G1.mul precomputed_srs a_list (* part 3.2 *) @@ -774,6 +768,7 @@ module Inner = struct (* Precompute first part of Toeplitz trick, which doesn't depends on the polynomial’s coefficients. *) let preprocess_multi_reveals ~chunk_len ~degree srs1 = + let open Bls12_381 in let l = 1 lsl chunk_len in let k = let ratio = degree / l in @@ -784,14 +779,15 @@ module Inner = struct let precompute_srsj j = let quotient = (degree - j) / l in let padding = diff_next_power_of_two (2 * quotient) in - let srsj = + let points = Array.init ((2 * quotient) + padding) (fun i -> - if i < quotient then srs1.(degree - j - ((i + 1) * l)) - else Bls12_381.G1.(copy zero)) + if i < quotient then G1.copy srs1.(degree - j - ((i + 1) * l)) + else G1.(copy zero)) in - Bls12_381.G1.fft ~domain ~points:srsj + G1.fft_inplace ~domain ~points ; + points in (domain, Array.init l precompute_srsj) @@ -803,6 +799,7 @@ module Inner = struct *) let multiple_multi_reveals ~chunk_len ~chunk_count ~degree ~preprocess:(domain2m, precomputed_srs_part) coefs = + let open Bls12_381 in let n = chunk_len + chunk_count in assert (2 <= chunk_len) ; assert (chunk_len < n) ; @@ -810,48 +807,44 @@ module Inner = struct assert (1 lsl chunk_len < degree) ; assert (degree <= 1 lsl n) ; let l = 1 lsl chunk_len in - (* Since we don’t need the first coefficient f₀, we remove it and add a zero - as last coefficient to keep the size unchanged *) - let coefs = List.tl (coefs @ [Scalar.(copy zero)]) in - let coefs = Array.of_list coefs in + (* We don’t need the first coefficient f₀. *) let compute_h_j j = let rest = (degree - j) mod l in let quotient = (degree - j) / l in (* Padding in case quotient is not a power of 2 to get proper fft in Toeplitz matrix part. *) let padding = diff_next_power_of_two (2 * quotient) in - let a_list = - (* fm, 0, …, 0, f₁, f₂, …, fm-1 *) - let a_array = - Array.init - ((2 * quotient) + padding) - (fun i -> - if i <= quotient + (padding / 2) then Scalar.(copy zero) - else coefs.(rest + ((i - (quotient + padding)) * l) - 1)) - in - a_array.(0) <- coefs.(degree - j - 1) ; - a_array + (* fm, 0, …, 0, f₁, f₂, …, fm-1 *) + let a_array = + Array.init + ((2 * quotient) + padding) + (fun i -> + if i <= quotient + (padding / 2) then Scalar.(copy zero) + else Scalar.copy coefs.(rest + ((i - (quotient + padding)) * l))) in + if j <> 0 then a_array.(0) <- Scalar.copy coefs.(degree - j) ; build_h_list_with_precomputed_srs - a_list + a_array (domain2m, precomputed_srs_part.(j)) in let sum = compute_h_j 0 in - let hl = - let rec sum_hj j = - if j = l then () - else - let hj = compute_h_j j in - (* sum.(i) <- sum.(i) + hj.(i) *) - Array.iteri (fun i hij -> sum.(i) <- Bls12_381.G1.add sum.(i) hij) hj ; - sum_hj (j + 1) - in - sum_hj 1 ; - build_h_list_final sum domain2m + + let rec sum_hj j = + if j = l then () + else + let hj = compute_h_j j in + (* sum.(i) <- sum.(i) + hj.(i) *) + Array.iteri (fun i hij -> sum.(i) <- G1.add sum.(i) hij) hj ; + sum_hj (j + 1) in + sum_hj 1 ; + (* Toeplitz matrix-vector multiplication *) + Bls12_381.G1.ifft_inplace ~domain:(inverse domain2m) ~points:sum ; + let hl = Array.sub sum 0 (Array.length domain2m / 2) in + (* Kate amortized FFT *) let phidomain = Domains.build ~log:chunk_count in let phidomain = inverse (Domains.inverse phidomain) in - Bls12_381.G1.fft ~domain:phidomain ~points:hl + G1.fft ~domain:phidomain ~points:hl (* h = polynomial such that h(y×domain[i]) = zi. *) let interpolation_h_poly y domain z_list = @@ -914,7 +907,7 @@ module Inner = struct ~chunk_count:t.proofs_log ~degree:t.k ~preprocess - (Polynomials.to_dense_coefficients p |> Array.to_list) + (Polynomials.to_dense_coefficients p) let verify_shard t trusted_setup cm {index = shard_index; share = shard_evaluations} proof = -- GitLab From f396fbbbf42c8a7630163b6b92e66c480e5f8764 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Tue, 26 Jul 2022 09:34:46 +0200 Subject: [PATCH 15/22] DAL/crypto: simplify kate amortized --- src/lib_crypto_dal/dal_cryptobox.ml | 22 ++++++++-------------- 1 file changed, 8 insertions(+), 14 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index 0c3ecc91d3f5..e5ac01525d46 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -748,12 +748,6 @@ module Inner = struct Array.init n (fun i -> if i = 0 then Bls12_381.Fr.(copy one) else Array.get domain (n - i)) - let build_h_list_with_precomputed_srs a_list (domain2m, precomputed_srs) = - Scalar.fft_inplace ~domain:domain2m ~points:a_list ; - Array.map2 Bls12_381.G1.mul precomputed_srs a_list - - (* part 3.2 *) - let diff_next_power_of_two x = let logx = Z.log2 (Z.of_int x) in if 1 lsl logx = x then 0 else (1 lsl (logx + 1)) - x @@ -815,20 +809,18 @@ module Inner = struct Toeplitz matrix part. *) let padding = diff_next_power_of_two (2 * quotient) in (* fm, 0, …, 0, f₁, f₂, …, fm-1 *) - let a_array = + let points = Array.init ((2 * quotient) + padding) (fun i -> if i <= quotient + (padding / 2) then Scalar.(copy zero) else Scalar.copy coefs.(rest + ((i - (quotient + padding)) * l))) in - if j <> 0 then a_array.(0) <- Scalar.copy coefs.(degree - j) ; - build_h_list_with_precomputed_srs - a_array - (domain2m, precomputed_srs_part.(j)) + if j <> 0 then points.(0) <- Scalar.copy coefs.(degree - j) ; + Scalar.fft_inplace ~domain:domain2m ~points ; + Array.map2 G1.mul precomputed_srs_part.(j) points in let sum = compute_h_j 0 in - let rec sum_hj j = if j = l then () else @@ -838,12 +830,14 @@ module Inner = struct sum_hj (j + 1) in sum_hj 1 ; + (* Toeplitz matrix-vector multiplication *) - Bls12_381.G1.ifft_inplace ~domain:(inverse domain2m) ~points:sum ; + G1.ifft_inplace ~domain:(inverse domain2m) ~points:sum ; let hl = Array.sub sum 0 (Array.length domain2m / 2) in - (* Kate amortized FFT *) + let phidomain = Domains.build ~log:chunk_count in let phidomain = inverse (Domains.inverse phidomain) in + (* Kate amortized FFT *) G1.fft ~domain:phidomain ~points:hl (* h = polynomial such that h(y×domain[i]) = zi. *) -- GitLab From 9497b8c1a86cb345d3f30e4670cebecf517ca6df Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Tue, 26 Jul 2022 09:42:51 +0200 Subject: [PATCH 16/22] DAL/crypto: simplify verify_commitment --- src/lib_crypto_dal/dal_cryptobox.ml | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index e5ac01525d46..d83d5d383595 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -735,13 +735,15 @@ module Inner = struct Generalize this function to pass the degree in parameter. *) let verify_commitment trusted_setup cm proof = - let open Result_syntax in let open Bls12_381 in - let* commit_xk = - commit' (module G2) [|Scalar.(copy one)|] trusted_setup.srs_g2 + let check = + match Array.get trusted_setup.srs_g2 0 with + | exception Invalid_argument _ -> false + | commit_xk -> + Pairing.pairing_check + [(cm, commit_xk); (proof, G2.(negate (copy one)))] in - Ok - (Pairing.pairing_check [(cm, commit_xk); (proof, G2.(negate (copy one)))]) + Ok check let inverse domain = let n = Array.length domain in -- GitLab From 1dca323a0b116f8d4d7011c7648738fdc0a1ce40 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Tue, 26 Jul 2022 13:10:14 +0200 Subject: [PATCH 17/22] DAL/crypto: 1.3x faster decoding --- src/lib_crypto_dal/dal_cryptobox.ml | 62 ++++++++++------------------- 1 file changed, 21 insertions(+), 41 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index d83d5d383595..322c140bc56c 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -222,9 +222,6 @@ module Inner = struct (* Builds group of nth roots of unity, a valid domain for the FFT. *) let make_domain n = Domains.build ~log:Z.(log2up (of_int n)) - (* Memoize intermediate domains for the FFTs. *) - let intermediate_domains : Evaluations.domain IntMap.t ref = ref IntMap.empty - type t = { redundancy_factor : int; slot_size : int; @@ -486,36 +483,6 @@ module Inner = struct let evaluations = List.map (evaluation_fft d) ps in interpolation_fft d (mul_c ~evaluations ()) - (* Divide & conquer polynomial multiplication with FFTs, assuming leaves are - polynomials of equal length. For n the degree of the returned polynomial, - k = |ps|, runs in time O(n log n log k). *) - let poly_mul t ps = - let split = List.fold_left (fun (l, r) x -> (x :: r, l)) ([], []) in - let rec poly_mul_aux ps = - match ps with - | [x] -> x - | _ -> - let a, b = split ps in - let a = poly_mul_aux a in - let b = poly_mul_aux b in - let deg = Polynomials.degree a + 1 (* deg a = deg b in our case. *) in - (* Computes adequate domain for the FFTs. *) - let d = - match IntMap.find deg !intermediate_domains with - | Some d -> d - | None -> - let d = - Domains.subgroup - ~log:(Z.log2up (Z.of_int (2 * deg))) - t.domain_n - in - intermediate_domains := IntMap.add deg d !intermediate_domains ; - d - in - fft_mul d [a; b] - in - poly_mul_aux ps - (* We encode by segments of [segment_size] bytes each. The segments are arranged in cosets to evaluate in batch with Kate amortized. *) @@ -655,18 +622,31 @@ module Inner = struct This also reduces the depth of the recursion tree of the poly_mul function from log(k) to log(number_of_shards), so that the decoding time reduces from O(k*log^2(k) + n*log(n)) to O(n*log(n)). *) - let factors = + let split = List.fold_left (fun (l, r) x -> (x :: r, l)) ([], []) in + let f1, f2 = IntMap.bindings shards (* We always consider the first k codeword vector components. *) |> Tezos_stdlib.TzList.take_n (t.k / t.shard_size) - |> List.rev_map (fun (i, _) -> - Polynomials.of_coefficients - [ - (Scalar.negate (Domains.get t.domain_n (i * t.shard_size)), 0); - (Scalar.(copy one), t.shard_size); - ]) + |> split + in + let f11, f12 = split f1 in + let f21, f22 = split f2 in + + let prod = + List.fold_left + (fun acc (i, _) -> + Polynomials.mul_xn + acc + t.shard_size + (Scalar.negate (Domains.get t.domain_n (i * t.shard_size)))) + Polynomials.one in - let a_poly = poly_mul t factors in + let p11 = prod f11 in + let p12 = prod f12 in + let p21 = prod f21 in + let p22 = prod f22 in + + let a_poly = fft_mul t.domain_2k [p11; p12; p21; p22] in (* 2. Computing formal derivative of A(x). *) let a' = Polynomials.derivative a_poly in -- GitLab From cf12c4fbcd4dbc5ea37c8a64c4edeb3e7700cbdc Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Fri, 29 Jul 2022 14:50:07 +0200 Subject: [PATCH 18/22] DAL/crypto: open Result_syntax module at the top of polynomial_from_shards --- src/lib_crypto_dal/dal_cryptobox.ml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index 322c140bc56c..9fe4511b644d 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -592,6 +592,7 @@ module Inner = struct Ok n_poly let polynomial_from_shards t shards = + let open Result_syntax in if t.k > IntMap.cardinal shards * t.shard_size then Error (`Not_enough_shards @@ -655,7 +656,6 @@ module Inner = struct let eval_a' = Evaluations.evaluation_fft t.domain_n a' in (* 4. Computing N(x). *) - let open Result_syntax in let* n_poly = compute_n t eval_a' shards in (* 5. Computing B(x). *) -- GitLab From bfe5c31ad9f2114ffe6dab2a0964a4bc7b7a1729 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Fri, 29 Jul 2022 15:11:51 +0200 Subject: [PATCH 19/22] DAL/crypto: fix typos --- src/lib_crypto_dal/dal_cryptobox.mli | 20 ++++++++++---------- src/lib_crypto_dal/dal_cryptobox_intf.ml | 23 ++++++++++++----------- 2 files changed, 22 insertions(+), 21 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.mli b/src/lib_crypto_dal/dal_cryptobox.mli index afae376490db..31a0637a7627 100644 --- a/src/lib_crypto_dal/dal_cryptobox.mli +++ b/src/lib_crypto_dal/dal_cryptobox.mli @@ -49,7 +49,7 @@ type srs (aka trusted setup) is required. It is the responsibility of the shell and the protocol to ensure - that both the [Verifier] and the [Builder] as instantiated with the + that both the [Verifier] and the [Builder] are instantiated with the same parameters and use the same trusted setup. *) module Verifier : VERIFIER @@ -69,10 +69,10 @@ end module IntMap : Tezos_error_monad.TzLwtreslib.Map.S with type key = int -(** A slot is just some data represented as bytes. *) +(** A slot is a byte sequence corresponding to some data. *) type slot = bytes -(** The field used by the polynomial. *) +(** The finited field used by the polynomial. *) type scalar (** A polynomial is another representation for a slot. One advantage @@ -95,7 +95,7 @@ val polynomial_evaluate : polynomial -> scalar -> scalar (** [polynomial_from_slot t slot] returns a polynomial from the a slot [slot]. - Fail with [`Slot_wrong_size] when the slot size is different from + Fails with [`Slot_wrong_size] when the slot size is different from [CONFIGURATION.slot_size]. *) val polynomial_from_slot : t -> bytes -> (polynomial, [> `Slot_wrong_size of string]) Result.t @@ -106,7 +106,7 @@ val polynomial_to_bytes : t -> polynomial -> bytes (** [commit polynomial] returns the commitment associated to a polynomial [p]. - Fail with [`Degree_exceeds_srs_length] if the degree of [p] + Fails with [`Degree_exceeds_srs_length] if the degree of [p] exceeds the SRS size. *) val commit : srs -> @@ -140,15 +140,15 @@ val polynomial_from_shards : share IntMap.t -> (polynomial, [> `Invert_zero of string | `Not_enough_shards of string]) result -(** [shards_from_polynomial t polynomial] compute all the shards +(** [shards_from_polynomial t polynomial] computes all the shards encoding the original [polynomial]. *) val shards_from_polynomial : t -> polynomial -> share IntMap.t -(** A proof that a shard belong to some commitment. *) +(** A proof that a shard belongs to some commitment. *) type shard_proof (** [verify_shard t srs commitment shard proof] allows to check - whether [shard] is a porition of the data corresopding to the + whether [shard] is a portion of the data corresponding to the [commitment] using [proof]. The verification time is constant. The [srs] should be the same as the one used to produce the commitment. *) @@ -161,8 +161,8 @@ val verify_shard : (bool, [> `Degree_exceeds_srs_length of string]) result (** [prove_commitment srs polynomial] produces a proof that the - commitment produced by the function [commit] is indeed a - commitment of the polynomial. *) + slot represented by [polynomial] has its size bounded by the + maximum slot size. *) val prove_commitment : srs -> polynomial -> diff --git a/src/lib_crypto_dal/dal_cryptobox_intf.ml b/src/lib_crypto_dal/dal_cryptobox_intf.ml index fb9e459a75df..ab6bbeb4014f 100644 --- a/src/lib_crypto_dal/dal_cryptobox_intf.ml +++ b/src/lib_crypto_dal/dal_cryptobox_intf.ml @@ -48,8 +48,8 @@ module type VERIFIER = sig (** A precomputed set of constants *) type t - (** [make] precomputes the set of values needed by cryptographic primitives - defined in this module and store them in a value of type [t] *) + (** [make] precomputes the set of values needed by the cryptographic + primitives defined in this module and stores them in a value of type [t] *) val make : redundancy_factor:int -> slot_size:int -> @@ -60,17 +60,18 @@ module type VERIFIER = sig (** A trusted setup. Namely Structured Reference String. Those are data necessary to make the cryptographic primitives - secured. In particular, to prevent an attacker to forge two + secured. In particular, to prevent an attacker from forging two polynomials with the same commitment. *) type srs (** [load_srs ()] loads a trusted [srs]. If the [srs] is already loaded, it is given directly. Otherwise, the trusted [srs] is read from two dedicated files. The function assumes those files - are located in some predetermined directories - UNIX-compatible. The [srs] depends on the [slot_size] - parameters. Loading the first time an srs is consequently costly - while the other times would be cheap. + are located in some predetermined UNIX-compatible directories. + + The [srs] depends on the [slot_size] parameters. Loading the + first time an srs is consequently costly while the other times + would be cheap. We assume the [srs] won't change many times. The shell ensures that a bounded and small number of [srs] can be loaded at the @@ -90,8 +91,8 @@ module type VERIFIER = sig val commitment_proof_encoding : commitment_proof Data_encoding.t (** [verify_commitment srs commitment proof] checks whether - [commitment] is a valid [commitment]. In particular, it check - that the size of the data committed via [commitment] do not + [commitment] is valid. In particular, it checks + that the size of the data committed via [commitment] does not exceed [C.slot_size]. The verification time is constant. *) val verify_commitment : srs -> @@ -111,10 +112,10 @@ module type VERIFIER = sig (** An encoding for the proof of a segment. *) val segment_proof_encoding : segment_proof Data_encoding.t - (** [verify_segment t commitment segment segment_proof] returns [Ok + (** [verify_segment t srs commitment segment segment_proof] returns [Ok true] if the [proof] certifies that the [slot_segment] is indeed included in the slot committed with commitment - [comitment]. Returns [Ok false] otherwise. + [commitment]. Returns [Ok false] otherwise. Fails if the index of the segment is out of range. *) val verify_segment : -- GitLab From 5e72b1785fcc41836c59c2c4837bf497b7de7c80 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Fri, 29 Jul 2022 16:11:15 +0200 Subject: [PATCH 20/22] Environment: fix verify_segment signature --- src/lib_protocol_environment/sigs/v7.ml | 5 ++++- src/lib_protocol_environment/sigs/v7/dal.mli | 5 ++++- 2 files changed, 8 insertions(+), 2 deletions(-) diff --git a/src/lib_protocol_environment/sigs/v7.ml b/src/lib_protocol_environment/sigs/v7.ml index 7117c2904784..88bdf4d3d3ba 100644 --- a/src/lib_protocol_environment/sigs/v7.ml +++ b/src/lib_protocol_environment/sigs/v7.ml @@ -11392,7 +11392,10 @@ val verify_segment : commitment -> segment -> segment_proof -> - (bool, [> `Slot_segment_index_out_of_range]) Result.t + ( bool, + [> `Degree_exceeds_srs_length of string | `Slot_segment_index_out_of_range] + ) + Result.t end # 134 "v7.in.ml" diff --git a/src/lib_protocol_environment/sigs/v7/dal.mli b/src/lib_protocol_environment/sigs/v7/dal.mli index 008cc82a163c..e67ba680953d 100644 --- a/src/lib_protocol_environment/sigs/v7/dal.mli +++ b/src/lib_protocol_environment/sigs/v7/dal.mli @@ -116,4 +116,7 @@ val verify_segment : commitment -> segment -> segment_proof -> - (bool, [> `Slot_segment_index_out_of_range]) Result.t + ( bool, + [> `Degree_exceeds_srs_length of string | `Slot_segment_index_out_of_range] + ) + Result.t -- GitLab From 20c70b138140442d08213983d2627815ae974bd3 Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Wed, 3 Aug 2022 09:37:16 +0200 Subject: [PATCH 21/22] DAL/crypto: replace match by if-then-else --- src/lib_crypto_dal/dal_cryptobox.ml | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index 9fe4511b644d..6d309441ed9d 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -547,14 +547,13 @@ module Inner = struct let codeword = encode t p in let len_shard = t.n / t.number_of_shards in let rec loop i map = - match i with - | i when i = t.number_of_shards -> map - | _ -> - let shard = Array.init len_shard (fun _ -> Scalar.(copy zero)) in - for j = 0 to len_shard - 1 do - shard.(j) <- codeword.((t.number_of_shards * j) + i) - done ; - loop (i + 1) (IntMap.add i shard map) + if i = t.number_of_shards then map + else + let shard = Array.init len_shard (fun _ -> Scalar.(copy zero)) in + for j = 0 to len_shard - 1 do + shard.(j) <- codeword.((t.number_of_shards * j) + i) + done ; + loop (i + 1) (IntMap.add i shard map) in loop 0 IntMap.empty -- GitLab From e500ba45c8b940a547ad7af624fd7ff979f44fda Mon Sep 17 00:00:00 2001 From: Julien Coolen Date: Wed, 3 Aug 2022 10:08:44 +0200 Subject: [PATCH 22/22] DAL/crypto: rename `Slot_segment_index_out_of_range to `Segment_index_out_of_range --- src/lib_crypto_dal/dal_cryptobox.ml | 2 +- src/lib_crypto_dal/dal_cryptobox_intf.ml | 3 +-- src/lib_protocol_environment/sigs/v7.ml | 3 +-- src/lib_protocol_environment/sigs/v7/dal.mli | 3 +-- 4 files changed, 4 insertions(+), 7 deletions(-) diff --git a/src/lib_crypto_dal/dal_cryptobox.ml b/src/lib_crypto_dal/dal_cryptobox.ml index 6d309441ed9d..34b06533c6da 100644 --- a/src/lib_crypto_dal/dal_cryptobox.ml +++ b/src/lib_crypto_dal/dal_cryptobox.ml @@ -931,7 +931,7 @@ module Inner = struct let verify_segment t trusted_setup cm {index = slot_segment_index; content = slot_segment} proof = if slot_segment_index < 0 || slot_segment_index >= t.nb_segments then - Error `Slot_segment_index_out_of_range + Error `Segment_index_out_of_range else let domain = Domains.build ~log:Z.(log2up (of_int t.segment_len)) in let slot_segment_evaluations = diff --git a/src/lib_crypto_dal/dal_cryptobox_intf.ml b/src/lib_crypto_dal/dal_cryptobox_intf.ml index ab6bbeb4014f..393406f170ac 100644 --- a/src/lib_crypto_dal/dal_cryptobox_intf.ml +++ b/src/lib_crypto_dal/dal_cryptobox_intf.ml @@ -125,7 +125,6 @@ module type VERIFIER = sig segment -> segment_proof -> ( bool, - [> `Degree_exceeds_srs_length of string | `Slot_segment_index_out_of_range] - ) + [> `Degree_exceeds_srs_length of string | `Segment_index_out_of_range] ) Result.t end diff --git a/src/lib_protocol_environment/sigs/v7.ml b/src/lib_protocol_environment/sigs/v7.ml index 88bdf4d3d3ba..25b535dcb140 100644 --- a/src/lib_protocol_environment/sigs/v7.ml +++ b/src/lib_protocol_environment/sigs/v7.ml @@ -11393,8 +11393,7 @@ val verify_segment : segment -> segment_proof -> ( bool, - [> `Degree_exceeds_srs_length of string | `Slot_segment_index_out_of_range] - ) + [> `Degree_exceeds_srs_length of string | `Segment_index_out_of_range] ) Result.t end # 134 "v7.in.ml" diff --git a/src/lib_protocol_environment/sigs/v7/dal.mli b/src/lib_protocol_environment/sigs/v7/dal.mli index e67ba680953d..aa58b208c14c 100644 --- a/src/lib_protocol_environment/sigs/v7/dal.mli +++ b/src/lib_protocol_environment/sigs/v7/dal.mli @@ -117,6 +117,5 @@ val verify_segment : segment -> segment_proof -> ( bool, - [> `Degree_exceeds_srs_length of string | `Slot_segment_index_out_of_range] - ) + [> `Degree_exceeds_srs_length of string | `Segment_index_out_of_range] ) Result.t -- GitLab