search

tangle-network / cggmp-threshold-ecdsa

MPC protocols for threshold ECDSA
GNU General Public License v3.0
46 stars 10 forks source link

perf: safe-prime generation #46

Open ivokub opened 11 months ago

ivokub commented 11 months ago

Issue summary

CGGMP paper requires that the ring-Pedersen parameters is a product of safe primes. For security we need to generate 1024 bit safe primes, which is quite time-consuming. One issue is that right now we're using kzen-paillier for generating Paillier keys. It uses fixed number of Miller-Rabin primality checks, but it is more than recommended.

Additionally, we could use https://eprint.iacr.org/2003/186.pdf - right now we sieve p,q individually but the paper recommends an unified sieve, giving potentially 15x speedup

luca992 commented 11 months ago

Is this as result of #34 ? I'm using the multi-party-ecdsa implementation here now as if seems it is actually being maintained... But it seems like it is a lot slower now.

tmpfs commented 11 months ago

@luca992, the c-split fixes did have a significant performance impact for DKG (particularly noticeable in webassembly), however I think @ivokub is referring to additional (upcoming) performance impact but happy to be corrected.

For more confidence in the security of this implementation I think we need to prefer correctness over performance.

luca992 commented 11 months ago

@tmpfs yeah for sure. There's no point to any of it if it's not secure haha. But it is a bit slow now. On wasm with the config parties: 5, threshold: 2 it is taking about 5 minutes to generate keys now... it was less than one before if I recall correctly... this is when running keygen all on one machine with a round_based Simulation. Is there a faster way to do key gen if I don't care about distributed generation?

Ps I can make a seprate issue if this is not relevant here

ivokub commented 11 months ago

Hi @luca992, yes the tests are now taking longer as we are now sampling safe primes as according to the paper. Additionally, https://github.com/webb-tools/cggmp-threshold-ecdsa/pull/44 introduces additonal overhead as we fix the protocol in more places.

This issue should make the impact less noticeable. There are two main things which make tests slow - the key generation is run in a single thread and the safe prime generation is not optimal. There is a paper referenced in the first post, which should help with the second. And in practice, keys are generated in parallel which should help with the first.

luca992 commented 11 months ago

Just another stat: on wasm in a single threaded simulation doing key refresh from parties: 5, threshold: 2 -> parties: 6, threshold: 2 is takes about 40 minutes

Doing it in a single threaded way with wasm just really isn't realistic anymore

tmpfs commented 11 months ago

@luca992 yeh that's not a sensible thing to do and doesn't reflect real world usage, for my webassembly use case I run each party in separate browser tabs and use playwright to orchestrate.

Chrome and Webkit tend to take about 2-4 minutes (including signing too) but Firefox is crazy slow.

https://github.com/mpc-sdk/framework#end-to-end-tests