gnosis / dex-zksnarks

Code to generate snark proofs for batch auction result validation of the Gnosis d.exchange
46 stars 7 forks source link

Parellelized reading of the R1CS #41

Closed fleupold closed 5 years ago

fleupold commented 5 years ago

This diff speed up reading the R1CS when trying to generate proofs with bellman by using a parallel map/reduce strategy for generating the R1CS based on the lines read from the input (code inspiration: https://gist.github.com/thereal1024/8075982816643cf9d5bd5851b61b63cc).

The main steps are:

  1. Map: each line to constraint_index => variable, coefficient, a|b|c matrix
  2. Reduce based on constraint_index => sum all linear terms (variable * coefficient) for each matrix and return the linear combination
  3. Create constraints A * B = C for each such linear combination

We can expect this change to speed up reading the R1CS by at least a factor of two (From 2hours to < 1 hour for 268M constraints). Running it on 17M constraint system yielded the following results (note the time for "Done Reading"):

Before

0 start generate_random_parameters
  0 Reading Witness
  2 Reading QAP
  323 Done Reading
2275 start prepare_verifying_key
2275 start create_random_proof
  0 Reading Witness
  2 Reading QAP
  316 Done Reading
2723 start verify_proof
2723 Done

After

0 start generate_random_parameters
  0 Reading Witness
  2 Reading QAP
    7 A done
    28 B done
    44 C done
    73 grouped
    77 reduced
  114 Done Reading
2113 start prepare_verifying_key
2113 start create_random_proof
  0 Reading Witness
  3 Reading QAP
    9 A done
    31 B done
    48 C done
    93 grouped
    100 reduced
  125 Done Reading
2376 start verify_proof