From edd1e97ae0898377ac579f1a82056704c3dea276 Mon Sep 17 00:00:00 2001 From: Marina Polubelova Date: Tue, 6 Jun 2023 15:49:42 +0200 Subject: [PATCH 1/3] Plompiler/optimizer: use tail-rec map in more places --- src/lib_plompiler/optimizer.ml | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/src/lib_plompiler/optimizer.ml b/src/lib_plompiler/optimizer.ml index 98df8ae0209d..c1696760a067 100644 --- a/src/lib_plompiler/optimizer.ml +++ b/src/lib_plompiler/optimizer.ml @@ -101,6 +101,7 @@ open Optimizer_helpers 4. Transform pseudo blocks to actual blocks (also considering the non-linear computations that were left aside) and join blocks that operate on independent wires together. *) +let list_map f l = (* avoid stack overflows *) List.rev_map f l |> List.rev let nb_wires_arch = Csir.nb_wires_arch @@ -648,12 +649,12 @@ let add_boolean_checks ~boolean_vars gates = else constr in (* First try to add them on existing constraints, through the qbool selector *) - let gates = List.map (fun gate -> Array.map shared_a gate) gates in + let gates = list_map (fun gate -> Array.map shared_a gate) gates in (* Then, try to use constraints that do not use the a wire *) - let gates = List.map (fun gate -> Array.mapi (unused_a ~gate) gate) gates in + let gates = list_map (fun gate -> Array.mapi (unused_a ~gate) gate) gates in (* Finally, add manual constraints for the remaining boolean variables *) let new_bool_gates = - List.map CS.mk_bool_constr (ISet.to_seq !bool_vars_map |> List.of_seq) + list_map CS.mk_bool_constr (ISet.to_seq !bool_vars_map |> List.of_seq) |> Array.of_list in List.rev (new_bool_gates :: gates) @@ -735,8 +736,7 @@ let inline_renamings ~nb_inputs ~range_checked gates = IMap.filter ( <> ) renaming |> IMap.bindings |> List.map fst in let rename i = Option.value ~default:i @@ IMap.find_opt i renaming in - let map f l = (* avoid stack overflows *) List.rev_map f l |> List.rev in - (map (CS.rename_wires ~rename) gates, free_wires) + (list_map (CS.rename_wires ~rename) gates, free_wires) (* We remove all constraints of the form [a * x - a * x = 0], which may be the result of having renamed some variables *) -- GitLab From 96c3717f01b7a93e51af07ec50bfbdc384e5765f Mon Sep 17 00:00:00 2001 From: Marina Polubelova Date: Tue, 6 Jun 2023 16:46:08 +0200 Subject: [PATCH 2/3] Plompiler: generalize padding to handle sha512 --- src/lib_plompiler/gadget_sha2.ml | 18 ++-- src/lib_plompiler/plompiler.ml | 1 + src/lib_plonk/test_plompiler/test_sha2.ml | 100 +++++++++++++++++++--- 3 files changed, 101 insertions(+), 18 deletions(-) diff --git a/src/lib_plompiler/gadget_sha2.ml b/src/lib_plompiler/gadget_sha2.ml index e906a2ea3421..d03b29829b9a 100644 --- a/src/lib_plompiler/gadget_sha2.ml +++ b/src/lib_plompiler/gadget_sha2.ml @@ -155,19 +155,27 @@ functor fun msg -> with_label ~label:"Sha2.padding" @@ - (* TODO generalize to other versions *) let l = Bytes.length msg in let k = - let k = (448 - (l + 1)) mod 512 in - if k > 0 then k else k + 512 + let k = (V.block_size - (2 * V.word_size) - (l + 1)) mod V.block_size in + if k > 0 then k else k + V.block_size in let* padding = let bitlist = List.(init k (Fun.const false) @ [true]) in Bytes.constant @@ Utils.of_bitlist bitlist in let* binary_l = - Z.of_int l |> Z.to_bits |> Stdlib.Bytes.of_string - |> Bytes.constant ~le:true + let ocaml_bytes = Z.of_int l |> Z.to_bits |> Stdlib.Bytes.of_string in + let ocaml_bytes = + let len = Stdlib.Bytes.length ocaml_bytes in + let len_padded = V.word_size / 4 in + if len = len_padded then ocaml_bytes + else + let bytes_padded = Stdlib.Bytes.make len_padded '\000' in + Stdlib.Bytes.blit ocaml_bytes 0 bytes_padded 0 len ; + bytes_padded + in + Bytes.constant ~le:true ocaml_bytes in ret @@ Bytes.concat [|msg; padding; binary_l|] diff --git a/src/lib_plompiler/plompiler.ml b/src/lib_plompiler/plompiler.ml index 01e734bee028..6dd0d242159c 100644 --- a/src/lib_plompiler/plompiler.ml +++ b/src/lib_plompiler/plompiler.ml @@ -79,6 +79,7 @@ module Gadget = struct module Blake2s = Gadget_blake2s.Blake2s module ArithMod25519 = Gadget_mod_arith.ArithMod25519 module Sha256 = Gadget_sha2.SHA256 + module Sha512 = Gadget_sha2.SHA512 end include Gadget diff --git a/src/lib_plonk/test_plompiler/test_sha2.ml b/src/lib_plonk/test_plompiler/test_sha2.ml index 4df0788d73e5..8a153bf535a5 100644 --- a/src/lib_plonk/test_plompiler/test_sha2.ml +++ b/src/lib_plonk/test_plompiler/test_sha2.ml @@ -28,7 +28,7 @@ open Plonk_test module CS = Plonk.Circuit open Helpers -module Internal : Test = +module Internal_sha256 : Test = functor (L : LIB) -> @@ -180,7 +180,7 @@ functor @ tests_sum1 @ tests_padding @ tests_initial_hash end -module External : Test = +module External_sha256 : Test = functor (L : LIB) -> @@ -190,23 +190,23 @@ functor open Utils (L) - module H = Plompiler.Gadget.Sha256 (L) + module H256 = Plompiler.Gadget.Sha256 (L) let bytes_of_hex = Plompiler.Utils.bytes_of_hex - let test_digest i o () = + let test_digest_sha256 i o () = let* i = input ~kind:`Public i in let* o = input o in - let* o' = H.digest i in + let* o' = H256.digest i in assert_equal o o' - let tests_digest = + let tests_digest_sha256 = List.map (fun (i, o) -> let name = "SHA256.test_digest" ^ i in let i = input_bytes @@ Stdlib.Bytes.of_string i in let o = input_bytes @@ bytes_of_hex (String.concat "" o) in - test ~valid:true ~name ~flamegraph:true @@ test_digest i o) + test ~valid:true ~name ~flamegraph:false @@ test_digest_sha256 i o) [ ( "abc", [ @@ -232,23 +232,97 @@ functor ] ); ] - let tests = tests_digest + let tests = tests_digest_sha256 + end + +module External_sha512 : Test = +functor + (L : LIB) + -> + struct + open L + open Bytes + + open Utils (L) + + module H512 = Plompiler.Gadget.Sha512 (L) + + let bytes_of_hex = Plompiler.Utils.bytes_of_hex + + let test_digest_sha512 i o () = + let* i = input ~kind:`Public i in + let* o = input o in + let* o' = H512.digest i in + assert_equal o o' + + let tests_digest_sha512 = + List.map + (fun (i, o) -> + let name = "SHA512.test_digest" ^ i in + let i = input_bytes @@ Stdlib.Bytes.of_string i in + let o = input_bytes @@ bytes_of_hex (String.concat "" o) in + test ~valid:true ~name ~flamegraph:false @@ test_digest_sha512 i o) + [ + ( "abc", + [ + "DDAF35A1"; + "93617ABA"; + "CC417349"; + "AE204131"; + "12E6FA4E"; + "89A97EA2"; + "0A9EEEE6"; + "4B55D39A"; + "2192992A"; + "274FC1A8"; + "36BA3C23"; + "A3FEEBBD"; + "454D4423"; + "643CE80E"; + "2A9AC94F"; + "A54CA49F"; + ] ); + ( "abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu", + [ + "8E959B75"; + "DAE313DA"; + "8CF4F728"; + "14FC143F"; + "8F7779C6"; + "EB9F7FA1"; + "7299AEAD"; + "B6889018"; + "501D289E"; + "4900F7E4"; + "331B99DE"; + "C4B5433A"; + "C7D329EE"; + "B6DD2654"; + "5E96E55B"; + "874BE909"; + ] ); + ] + + let tests = tests_digest_sha512 end let tests = - let both = + let sha256 = [ - ("Internal", (module Internal : Test)); - ("External", (module External : Test)); + ("Internal_sha256", (module Internal_sha256 : Test)); + ("External_sha256", (module External_sha256 : Test)); ] in + let sha512 = [("External_sha512", (module External_sha512 : Test))] in (* This test uses plonk and it is marked quick so that it is always run by the CI *) - List.map (fun (name, m) -> Alcotest.test_case name `Quick (to_test m)) both + List.map + (fun (name, m) -> Alcotest.test_case name `Quick (to_test m)) + (sha256 @ sha512) @ List.map (fun (name, m) -> Alcotest.test_case (name ^ " plonk") `Slow (to_test ~plonk:(module Plonk.Main_protocol) m)) - both + sha256 -- GitLab From bda17056fca152e920d7bf9554df399bd0e5c706 Mon Sep 17 00:00:00 2001 From: Marina Polubelova Date: Fri, 9 Jun 2023 10:58:05 +0200 Subject: [PATCH 3/3] Plompiler: promote regressions --- src/lib_plonk/test_plompiler/test-quick.expected | 12 ++++++++++++ src/lib_plonk/test_plompiler/test-slow.expected | 12 ++++++++++++ 2 files changed, 24 insertions(+) diff --git a/src/lib_plonk/test_plompiler/test-quick.expected b/src/lib_plonk/test_plompiler/test-quick.expected index d582f753012a..ede6379e09d4 100644 --- a/src/lib_plonk/test_plompiler/test-quick.expected +++ b/src/lib_plonk/test_plompiler/test-quick.expected @@ -1828,6 +1828,18 @@ Constraints: 254898 SHA256.test_digestabcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq_optimized: Constraints: 253938 +SHA512.test_digestabc: +Constraints: 324914 + +SHA512.test_digestabc_optimized: +Constraints: 323866 + +SHA512.test_digestabcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu: +Constraints: 649650 + +SHA512.test_digestabcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu_optimized: +Constraints: 647730 + Anemoi.test_round.valid: Constraints: 20 diff --git a/src/lib_plonk/test_plompiler/test-slow.expected b/src/lib_plonk/test_plompiler/test-slow.expected index caec18262439..ec1f969e23e1 100644 --- a/src/lib_plonk/test_plompiler/test-slow.expected +++ b/src/lib_plonk/test_plompiler/test-slow.expected @@ -4408,6 +4408,18 @@ Constraints: 254898 SHA256.test_digestabcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq_optimized: Constraints: 253938 +SHA512.test_digestabc: +Constraints: 324914 + +SHA512.test_digestabc_optimized: +Constraints: 323866 + +SHA512.test_digestabcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu: +Constraints: 649650 + +SHA512.test_digestabcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu_optimized: +Constraints: 647730 + SHA256.test_ch: Constraints: 72 -- GitLab