search

pepper-project / pequin

A system for verifying outsourced computations, and applying SNARKs. Simplified release of the main Pepper codebase.
Other
122 stars 46 forks source link

mm_pure_arith takes about 30 seconds to prove #50

Open someone235 opened 5 years ago

someone235 commented 5 years ago

It sounds unreasonably long time. Can you please share your benchmarks so I will know if there's something wrong with my machine?

maxhowald commented 5 years ago

You may be running in to a known issue in which the setup step for the database required by computations which make use of the merkle-tree based storage primitives takes an unusually long time.

As a workaround, for computations like matrix multiplication, which don't require these primitives, you can try commenting out these lines and re-compiling the prover and verifier:

https://github.com/pepper-project/pequin/blob/b0fb3ec8f60c94e7bac3a8399d4d39b319d10173/pepper/libv/computation_p.cpp#L36

https://github.com/pepper-project/pequin/blob/b0fb3ec8f60c94e7bac3a8399d4d39b319d10173/pepper/libv/computation_p.cpp#L80-L83

Of course, long term, it would be preferable to detect whether the computation requires this setup step and only execute these lines conditionally.

For reference, on the latest commit (b0fb3ec8f), I see the following output from the prover on a machine with an i5-4400:


root@05bff7c0cdea:/opt/pequin/pepper# time bin/pepper_prover_mm_pure_arith prove mm.pk mm.input mm.out mm.proof
NUMBER OF CONSTRAINTS:  28
reading proving key from file...
Reset time counters for profiling
(enter) Call to r1cs_gg_ppzksnark_prover    [             ] (0.0000s x2.39 from start)
  (enter) Compute the polynomial H              [             ] (0.0000s x0.98 from start)
    (enter) Call to r1cs_to_qap_witness_map     [             ] (0.0001s x1.13 from start)
      (enter) Compute evaluation of polynomials A, B on set S   [             ] (0.0002s x1.00 from start)
      (leave) Compute evaluation of polynomials A, B on set S   [0.0000s x1.02] (0.0003s x1.00 from start)
      (enter) Compute coefficients of polynomial A  [             ] (0.0003s x1.00 from start)
      (leave) Compute coefficients of polynomial A  [0.0001s x0.76] (0.0004s x0.92 from start)
      (enter) Compute coefficients of polynomial B  [             ] (0.0004s x0.92 from start)
      (leave) Compute coefficients of polynomial B  [0.0001s x1.01] (0.0004s x0.94 from start)
      (enter) Compute ZK-patch                      [             ] (0.0005s x0.94 from start)
      (leave) Compute ZK-patch                      [0.0000s x1.01] (0.0005s x0.94 from start)
      (enter) Compute evaluation of polynomial A on set T   [             ] (0.0005s x0.94 from start)
      (leave) Compute evaluation of polynomial A on set T   [0.0001s x1.00] (0.0005s x0.95 from start)
      (enter) Compute evaluation of polynomial B on set T   [             ] (0.0006s x0.95 from start)
      (leave) Compute evaluation of polynomial B on set T   [0.0001s x1.01] (0.0006s x0.95 from start)
      (enter) Compute evaluation of polynomial H on set T   [             ] (0.0006s x0.95 from start)
        (enter) Compute evaluation of polynomial C on set S [             ] (0.0006s x0.95 from start)
        (leave) Compute evaluation of polynomial C on set S [0.0000s x1.02] (0.0006s x0.96 from start)
        (enter) Compute coefficients of polynomial C    [             ] (0.0007s x0.96 from start)
        (leave) Compute coefficients of polynomial C    [0.0001s x1.01] (0.0007s x0.96 from start)
        (enter) Compute evaluation of polynomial C on set T [             ] (0.0007s x0.96 from start)
        (leave) Compute evaluation of polynomial C on set T [0.0001s x1.01] (0.0008s x0.96 from start)
        (enter) Divide by Z on set T                [             ] (0.0008s x0.96 from start)
        (leave) Divide by Z on set T                [0.0000s x1.04] (0.0008s x0.96 from start)
      (leave) Compute evaluation of polynomial H on set T   [0.0002s x1.00] (0.0008s x0.96 from start)
      (enter) Compute coefficients of polynomial H  [             ] (0.0008s x0.96 from start)
      (leave) Compute coefficients of polynomial H  [0.0001s x1.01] (0.0009s x0.97 from start)
      (enter) Compute sum of H and ZK-patch         [             ] (0.0009s x0.97 from start)
      (leave) Compute sum of H and ZK-patch         [0.0000s x1.06] (0.0009s x0.97 from start)
    (leave) Call to r1cs_to_qap_witness_map     [0.0009s x0.96] (0.0009s x0.97 from start)
  (leave) Compute the polynomial H              [0.0009s x0.97] (0.0009s x0.97 from start)
  (enter) Compute the proof                     [             ] (0.0010s x0.97 from start)
    (enter) Compute evaluation to A-query       [             ] (0.0010s x0.97 from start)
    (enter) Process scalar vector               [             ] (0.0010s x0.97 from start)
      * Elements of w skipped: 1 (2.13%)
      * Elements of w processed with special addition: 1 (2.13%)
      * Elements of w remaining: 45 (95.74%)
    (leave) Process scalar vector               [0.0000s x1.02] (0.0010s x0.97 from start)
    (leave) Compute evaluation to A-query       [0.0007s x1.00] (0.0017s x0.98 from start)
    (enter) Compute evaluation to B-query       [             ] (0.0017s x0.98 from start)
    (enter) Process scalar vector               [             ] (0.0017s x0.98 from start)
      * Elements of w skipped: 0 (0.00%)
      * Elements of w processed with special addition: 0 (0.00%)
      * Elements of w remaining: 9 (100.00%)
    (leave) Process scalar vector               [0.0000s x1.02] (0.0017s x0.98 from start)
    (leave) Compute evaluation to B-query       [0.0007s x1.00] (0.0024s x0.99 from start)
    (enter) Compute evaluation to H-query       [             ] (0.0025s x0.99 from start)
    (leave) Compute evaluation to H-query       [0.0043s x1.00] (0.0068s x1.00 from start)
    (enter) Compute evaluation to L-query       [             ] (0.0068s x1.00 from start)
    (enter) Process scalar vector               [             ] (0.0068s x1.00 from start)
      * Elements of w skipped: 0 (0.00%)
      * Elements of w processed with special addition: 0 (0.00%)
      * Elements of w remaining: 18 (100.00%)
    (leave) Process scalar vector               [0.0001s x0.76] (0.0069s x1.00 from start)
    (leave) Compute evaluation to L-query       [0.0007s x0.99] (0.0075s x1.00 from start)
  (leave) Compute the proof                     [0.0078s x1.00] (0.0088s x1.00 from start)
(leave) Call to r1cs_gg_ppzksnark_prover    [0.0088s x1.00] (0.0088s x1.00 from start)
* G1 elements in proof: 2
* G2 elements in proof: 1
* Proof size in bits: 1019

real    0m7.529s
user    0m7.513s
sys 0m0.004s

Note that the actual call to r1cs_gg_ppzksnark_prover only takes a few milliseconds for a computation so small.