diff --git a/src/lib_bls12_381/bls12_381.ml b/src/lib_bls12_381/bls12_381.ml index 953efe3e32cbb10d7b07557760f343fe6f3c33f3..fc9c494c363ec685ae68d5b87353399ada029580 100644 --- a/src/lib_bls12_381/bls12_381.ml +++ b/src/lib_bls12_381/bls12_381.ml @@ -53,6 +53,17 @@ module type CURVE = sig (** Build a OCaml array of [t] values from the contiguous C array *) val of_affine_array : affine_array -> t array + (** [affine_array_of_compressed_bytes_opt pts] builds a contiguous C + array and populate it with the points [pts] in affine + coordinates from their compressed representation in bytes. + + If [subgroup_check] is set, the function also checks if the + points are in the prime subgroup. + + Use it with {!affine_add_bulk} to get better performance *) + val affine_array_of_compressed_bytes_opt : + subgroup_check:bool -> Bytes.t array -> affine_array option + (** Return the number of elements in the array *) val size_of_affine_array : affine_array -> int @@ -115,6 +126,10 @@ module type CURVE = sig val add_bulk : t list -> t + (** [affine_add_bulk xs] returns the sum of the elements of [xs] by + performing only one allocation for the output. *) + val affine_add_bulk : affine_array -> t + (** [double g] returns [2g] *) val double : t -> t diff --git a/src/lib_bls12_381/bls12_381.mli b/src/lib_bls12_381/bls12_381.mli index 492e2ff65226f5252163180b25afe7d5c24a6cf8..e304187dab1bbff44eeb33fb069dede963f93450 100644 --- a/src/lib_bls12_381/bls12_381.mli +++ b/src/lib_bls12_381/bls12_381.mli @@ -124,6 +124,17 @@ module type CURVE = sig (** Build a OCaml array of [t] values from the contiguous C array *) val of_affine_array : affine_array -> t array + (** [affine_array_of_compressed_bytes_opt pts] builds a contiguous C + array and populate it with the points [pts] in affine + coordinates from their compressed representation in bytes. + + If [subgroup_check] is set, the function also checks if the + points are in the prime subgroup. + + Use it with {!affine_add_bulk} to get better performance *) + val affine_array_of_compressed_bytes_opt : + subgroup_check:bool -> Bytes.t array -> affine_array option + (** Return the number of elements in the array *) val size_of_affine_array : affine_array -> int @@ -210,6 +221,10 @@ module type CURVE = sig allocation overhead of using [n] times {!add}. *) val add_bulk : t list -> t + (** [affine_add_bulk xs] returns the sum of the elements of [xs] by + performing only one allocation for the output. *) + val affine_add_bulk : affine_array -> t + (** [double g] returns [2g] *) val double : t -> t diff --git a/src/lib_bls12_381/blst_bindings_stubs.c b/src/lib_bls12_381/blst_bindings_stubs.c index 09d4589bca31df336a0cdbbb0b1a34261310fc8f..70ec762ab89406aa87e8af778faa360c04e8d590 100644 --- a/src/lib_bls12_381/blst_bindings_stubs.c +++ b/src/lib_bls12_381/blst_bindings_stubs.c @@ -7,6 +7,7 @@ #include #include #include +#include #include #include @@ -588,6 +589,58 @@ CAMLprim value caml_blst_p1_set_coordinates_stubs(value buffer, value x, CAMLreturn(CAML_BLS12_381_OUTPUT_SUCCESS); } +CAMLprim value caml_blst_p1_affine_array_of_compressed_bytes_stubs( + value affine_points, value points_in_bytes, value npoints, + value subgroup_check) { + CAMLparam4(affine_points, points_in_bytes, npoints, subgroup_check); + int npoints_c = Int_val(npoints); + blst_p1_affine *affine_points_c = Blst_p1_affine_val(affine_points); + bool subgroup_check_c = Bool_val(subgroup_check); + int r = 0; + bool in_g1 = true; + + for (int i = 0; i < npoints_c; i++) { + r = blst_p1_uncompress(affine_points_c + i, + Bytes_val(Field(points_in_bytes, i))); + // fails if the point is not on the curve + if (r != 0) { + CAMLreturn(Val_int(r)); + } + if (subgroup_check_c) { + in_g1 = blst_p1_affine_in_g1(affine_points_c + i); + // fails if the point is not in the group + if (!in_g1) { + CAMLreturn(Val_int(BLST_POINT_NOT_IN_GROUP)); + } + } + } + + CAMLreturn(Val_int(r)); +} + +CAMLprim value caml_blst_p1s_add_stubs(value jacobian_res, value affine_points, + value npoints) { + CAMLparam3(jacobian_res, affine_points, npoints); + int npoints_c = Int_val(npoints); + blst_p1_affine *affine_points_c = Blst_p1_affine_val(affine_points); + + blst_p1_affine **addr_ps = + (blst_p1_affine **)calloc(npoints_c, sizeof(blst_p1_affine *)); + if (addr_ps == NULL) { + CAMLreturn(CAML_BLS12_381_OUTPUT_OUT_OF_MEMORY); + } + for (int i = 0; i < npoints_c; i++) { + addr_ps[i] = affine_points_c + i; + } + + blst_p1s_add(Blst_p1_val(jacobian_res), (const blst_p1_affine **)addr_ps, + npoints_c); + + free(addr_ps); + + CAMLreturn(CAML_BLS12_381_OUTPUT_SUCCESS); +} + static struct custom_operations blst_p2_ops = {"blst_p2", custom_finalize_default, custom_compare_default, @@ -740,6 +793,58 @@ CAMLprim value caml_blst_p2_set_coordinates_stubs(value buffer, value x, CAMLreturn(CAML_BLS12_381_OUTPUT_SUCCESS); } +CAMLprim value caml_blst_p2_affine_array_of_compressed_bytes_stubs( + value affine_points, value points_in_bytes, value npoints, + value subgroup_check) { + CAMLparam4(affine_points, points_in_bytes, npoints, subgroup_check); + int npoints_c = Int_val(npoints); + blst_p2_affine *affine_points_c = Blst_p2_affine_val(affine_points); + bool subgroup_check_c = Bool_val(subgroup_check); + int r = 0; + bool in_g2 = true; + + for (int i = 0; i < npoints_c; i++) { + r = blst_p2_uncompress(affine_points_c + i, + Bytes_val(Field(points_in_bytes, i))); + // fails if the point is not on the curve + if (r != 0) { + CAMLreturn(Val_int(r)); + } + if (subgroup_check_c) { + in_g2 = blst_p2_affine_in_g2(affine_points_c + i); + // fails if the point is not in the group + if (!in_g2) { + CAMLreturn(Val_int(BLST_POINT_NOT_IN_GROUP)); + } + } + } + + CAMLreturn(Val_int(r)); +} + +CAMLprim value caml_blst_p2s_add_stubs(value jacobian_res, value affine_points, + value npoints) { + CAMLparam3(jacobian_res, affine_points, npoints); + int npoints_c = Int_val(npoints); + blst_p2_affine *affine_points_c = Blst_p2_affine_val(affine_points); + + blst_p2_affine **addr_ps = + (blst_p2_affine **)calloc(npoints_c, sizeof(blst_p2_affine *)); + if (addr_ps == NULL) { + CAMLreturn(CAML_BLS12_381_OUTPUT_OUT_OF_MEMORY); + } + for (int i = 0; i < npoints_c; i++) { + addr_ps[i] = affine_points_c + i; + } + + blst_p2s_add(Blst_p2_val(jacobian_res), (const blst_p2_affine **)addr_ps, + npoints_c); + + free(addr_ps); + + CAMLreturn(CAML_BLS12_381_OUTPUT_SUCCESS); +} + // Pairing CAMLprim value caml_blst_miller_loop_stubs(value buffer, value g2, value g1) { diff --git a/src/lib_bls12_381/g1.ml b/src/lib_bls12_381/g1.ml index 16a719b7c07c8e216c8e76a3a815d56af541e49b..70ba6a84829f1fc5256cef200dc42644196db25d 100644 --- a/src/lib_bls12_381/g1.ml +++ b/src/lib_bls12_381/g1.ml @@ -91,6 +91,13 @@ module Stubs = struct external set_affine_coordinates : affine -> Fq.t -> Fq.t -> int = "caml_blst_p1_set_coordinates_stubs" + external affine_array_of_compressed_bytes : + affine_array -> Bytes.t array -> int -> bool -> int + = "caml_blst_p1_affine_array_of_compressed_bytes_stubs" + + external affine_add_bulk : jacobian -> affine_array -> int -> int + = "caml_blst_p1s_add_stubs" + external pippenger : jacobian -> jacobian array -> @@ -150,6 +157,18 @@ module G1 = struct ignore @@ Stubs.continuous_array_get p l i ; p) + let affine_array_of_compressed_bytes_opt ~subgroup_check points_in_bytes = + let npoints = Array.length points_in_bytes in + let buffer = Stubs.allocate_g1_affine_contiguous_array npoints in + let res = + Stubs.affine_array_of_compressed_bytes + buffer + points_in_bytes + npoints + subgroup_check + in + if res = 0 then Some (buffer, npoints) else None + let size_of_affine_array (_, n) = n let copy src = @@ -239,6 +258,11 @@ module G1 = struct List.iter (fun x -> ignore @@ Stubs.dadd buffer buffer x) xs ; buffer + let affine_add_bulk (affine_points, npoints) = + let buffer = Stubs.allocate_g1 () in + ignore @@ Stubs.affine_add_bulk buffer affine_points npoints ; + buffer + let double x = let buffer = Stubs.allocate_g1 () in ignore @@ Stubs.double buffer x ; diff --git a/src/lib_bls12_381/g2.ml b/src/lib_bls12_381/g2.ml index 4fb5452cb1a3067812a6b3d037076c8efa8e3abb..e6fc65508f08979b4d96fc12973ecd5cc839dbb6 100644 --- a/src/lib_bls12_381/g2.ml +++ b/src/lib_bls12_381/g2.ml @@ -90,6 +90,13 @@ module Stubs = struct external set_affine_coordinates : affine -> Fq2.t -> Fq2.t -> int = "caml_blst_p2_set_coordinates_stubs" + external affine_array_of_compressed_bytes : + affine_array -> Bytes.t array -> int -> bool -> int + = "caml_blst_p2_affine_array_of_compressed_bytes_stubs" + + external affine_add_bulk : jacobian -> affine_array -> int -> int + = "caml_blst_p2s_add_stubs" + external pippenger : jacobian -> jacobian array -> @@ -147,6 +154,18 @@ module G2 = struct ignore @@ Stubs.continuous_array_get p l i ; p) + let affine_array_of_compressed_bytes_opt ~subgroup_check points_in_bytes = + let npoints = Array.length points_in_bytes in + let buffer = Stubs.allocate_g2_affine_contiguous_array npoints in + let res = + Stubs.affine_array_of_compressed_bytes + buffer + points_in_bytes + npoints + subgroup_check + in + if res = 0 then Some (buffer, npoints) else None + let size_of_affine_array (_, n) = n let copy src = @@ -237,6 +256,11 @@ module G2 = struct List.iter (fun x -> ignore @@ Stubs.dadd buffer buffer x) xs ; buffer + let affine_add_bulk (affine_points, npoints) = + let buffer = Stubs.allocate_g2 () in + ignore @@ Stubs.affine_add_bulk buffer affine_points npoints ; + buffer + let double x = let buffer = Stubs.allocate_g2 () in ignore @@ Stubs.double buffer x ; diff --git a/src/lib_bls12_381/test/test_ec_make.ml b/src/lib_bls12_381/test/test_ec_make.ml index 88771f3ccd6086c353bd41f35a4b09050c2c2f35..ab50e7406c3bcc56448970ffd77422368eb127bf 100644 --- a/src/lib_bls12_381/test/test_ec_make.ml +++ b/src/lib_bls12_381/test/test_ec_make.ml @@ -30,6 +30,14 @@ module MakeBulkOperations (G : Bls12_381.CURVE) = struct let xs = List.init n (fun _ -> G.random ()) in assert (G.(eq (List.fold_left G.add G.zero xs) (G.add_bulk xs))) + let test_affine_bulk_add () = + let n = 10 + Random.int 1_000 in + let xs = Array.init n (fun _ -> G.random ()) in + let xs_affine = G.to_affine_array xs in + let xs = Array.to_list xs in + assert ( + G.(eq (List.fold_left G.add G.zero xs) (G.affine_add_bulk xs_affine))) + let test_pippenger () = let n = 1 + Random.int 5 in let start = Random.int n in @@ -68,6 +76,20 @@ module MakeBulkOperations (G : Bls12_381.CURVE) = struct let p' = Array.to_list p' in assert (List.for_all2 G.eq p p') + let test_affine_array_of_compressed_bytes () = + let n = 1 + Random.int 1000 in + let points = Array.init n (fun _ -> G.random ()) in + let points_in_bytes = Array.map G.to_compressed_bytes points in + let aux ~subgroup_check = + let affine_points = + G.affine_array_of_compressed_bytes_opt ~subgroup_check points_in_bytes + in + let points' = G.of_affine_array (Option.get affine_points) in + assert (Array.for_all2 G.eq points points') + in + aux ~subgroup_check:true ; + aux ~subgroup_check:false + let test_size_of_affine_array () = let n = 1 + Random.int 1000 in let p = Array.init n (fun _ -> G.random ()) in @@ -223,7 +245,12 @@ module MakeBulkOperations (G : Bls12_381.CURVE) = struct ( "Bulk operations", [ test_case "bulk add" `Quick (repeat 10 test_bulk_add); + test_case "affine bulk add" `Quick (repeat 10 test_affine_bulk_add); test_case "to_affine_array" `Quick (repeat 10 test_to_affine_array); + test_case + "affine_array_of_compressed_bytes" + `Quick + (repeat 10 test_affine_array_of_compressed_bytes); test_case "size_of_affine_array" `Quick diff --git a/src/lib_bls12_381_signature/bls12_381_signature.ml b/src/lib_bls12_381_signature/bls12_381_signature.ml index 72779d7c39bd51d3644538083ef66fecbe5e4e0e..ab106572ca775b79fbbb80bd53c049ff1cffd9db 100644 --- a/src/lib_bls12_381_signature/bls12_381_signature.ml +++ b/src/lib_bls12_381_signature/bls12_381_signature.ml @@ -242,19 +242,28 @@ module MinPk = struct else false) let aggregate_signature_opt signatures = - let rec aux signatures acc = - match signatures with - | [] -> Some acc - | signature :: signatures -> ( - let signature = Bls12_381.G2.of_compressed_bytes_opt signature in - match signature with - | None -> None - | Some signature -> - let acc = Bls12_381.G2.(add signature acc) in - aux signatures acc) + let signatures = + Bls12_381.G2.affine_array_of_compressed_bytes_opt + ~subgroup_check:true + (Array.of_list signatures) in - let res = aux signatures Bls12_381.G2.zero in - Option.map Bls12_381.G2.to_compressed_bytes res + Option.map + (fun signatures -> + let res = Bls12_381.G2.affine_add_bulk signatures in + Bls12_381.G2.to_compressed_bytes res) + signatures + + let aggregate_public_key_opt ?(subgroup_check = true) pks = + let pks = + Bls12_381.G1.affine_array_of_compressed_bytes_opt + ~subgroup_check + (Array.of_list pks) + in + Option.map + (fun pks -> + let res = Bls12_381.G1.affine_add_bulk pks in + Bls12_381.G1.to_compressed_bytes res) + pks let core_aggregate_verify pks_with_msgs aggregated_signature ciphersuite = let rec aux aggregated_signature pks_with_msgs ctxt = @@ -402,15 +411,10 @@ module MinPk = struct let aggregate_verify pks_with_pops msg aggregated_signature = let pks_bytes = List.map fst pks_with_pops in - let pks_opts = List.map Bls12_381.G1.of_compressed_bytes_opt pks_bytes in - let pks_are_ok = List.for_all Option.is_some pks_opts in - if not pks_are_ok then false + let aggregated_pk = aggregate_public_key_opt pks_bytes in + if Option.is_none aggregated_pk then false else - let pks = List.map Option.get pks_opts in - let aggregated_pk = - List.fold_left Bls12_381.G1.add Bls12_381.G1.zero pks - in - let aggregated_pk = Bls12_381.G1.to_compressed_bytes aggregated_pk in + let aggregated_pk = Option.get aggregated_pk in let signature_check = verify aggregated_pk msg aggregated_signature in let pop_checks = List.for_all @@ -549,19 +553,28 @@ module MinSig = struct else false) let aggregate_signature_opt signatures = - let rec aux signatures acc = - match signatures with - | [] -> Some acc - | signature :: signatures -> ( - let signature = Bls12_381.G1.of_compressed_bytes_opt signature in - match signature with - | None -> None - | Some signature -> - let acc = Bls12_381.G1.(add signature acc) in - aux signatures acc) + let signatures = + Bls12_381.G1.affine_array_of_compressed_bytes_opt + ~subgroup_check:true + (Array.of_list signatures) in - let res = aux signatures Bls12_381.G1.zero in - Option.map Bls12_381.G1.to_compressed_bytes res + Option.map + (fun signatures -> + let res = Bls12_381.G1.affine_add_bulk signatures in + Bls12_381.G1.to_compressed_bytes res) + signatures + + let aggregate_public_key_opt ?(subgroup_check = true) pks = + let pks = + Bls12_381.G2.affine_array_of_compressed_bytes_opt + ~subgroup_check + (Array.of_list pks) + in + Option.map + (fun pks -> + let res = Bls12_381.G2.affine_add_bulk pks in + Bls12_381.G2.to_compressed_bytes res) + pks let core_aggregate_verify pks_with_msgs aggregated_signature ciphersuite = let rec aux aggregated_signature pks_with_msgs ctxt = @@ -709,15 +722,10 @@ module MinSig = struct let aggregate_verify pks_with_pops msg aggregated_signature = let pks_bytes = List.map fst pks_with_pops in - let pks_opts = List.map Bls12_381.G2.of_compressed_bytes_opt pks_bytes in - let pks_are_ok = List.for_all Option.is_some pks_opts in - if not pks_are_ok then false + let aggregated_pk = aggregate_public_key_opt pks_bytes in + if Option.is_none aggregated_pk then false else - let pks = List.map Option.get pks_opts in - let aggregated_pk = - List.fold_left Bls12_381.G2.add Bls12_381.G2.zero pks - in - let aggregated_pk = Bls12_381.G2.to_compressed_bytes aggregated_pk in + let aggregated_pk = Option.get aggregated_pk in let signature_check = verify aggregated_pk msg aggregated_signature in let pop_checks = List.for_all