search

serai-dex / serai

Other
239 stars 45 forks source link

Reduced-complexity DKG #132

Open kayabaNerve opened 1 year ago

kayabaNerve commented 1 year ago

https://eprint.iacr.org/2022/1389.pdf details a DKG which they claim runs in O(n) without faults, yet in O(n log n) with arbitrary faults.

The existing DKG operates in O(n^2), and moving to O(n) is possible yet while introducing malleability which presumably violates the safety of the protocol.

We will prove in §5.3 that this approach ensures correctness, i.e., nodes always output the correct ADKG public key and threshold public keys.

The transformation in this paper is proven to be correct.

While this details a network protocol, which we don't need as we report coordination back to Substrate which uses Tendermint, the cryptographic performance gain would be massive. For 500 validators, it'd move from 250k point muls to just 4483 (assuming log2).

kayabaNerve commented 11 months ago

https://eprint.iacr.org/2023/992 relevant.

kayabaNerve commented 2 weeks ago

https://eprint.iacr.org/2024/876 achieves O(1) per-party upload/download. For our use case, it'd be O(1) upload with O(n) download (ignoring the complexity of gossip and Tendermint). This would let us greatly reduce max Tributary TX sizes (tightening our DoS resilience).

It does have a constant round complexity (comparable to current) as well.

Assuming the academia holds up, it should be the clear-winner unless the constant size ends up as several kB?