Reduced-complexity DKG

[kayabaNerve]

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]

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

[kayabaNerve]

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?

[kayabaNerve]

The one-round DKG (#589) we have now is quite good, despite still being linear. O(1) code via experimental lattice cryptography can definitely take a backseat.

[kayabaNerve]

While this can still count as a long-term goal, the current DKG is great. I don't expect a less-bandwidth robust DKG, with cryptography we're able to implement and willing to use, to come any time soon and it's definitely no longer a priority.