๐งต How do we provide instant on-chain randomness on @Aptos_Network?
One key ingredient is a fast Lagrange interpolation algorithm from our 2020 work (& my PhD thesis) with @bennypinkas, @ittaia et al (alinush.github.io/2020/03/12/scalable-bls-threshold-signatures.html)
So, if you're doing threshold BLS, read below...๐
Aggregating t-out-of-n threshold signatures typically involves (1) computing Lagrange coefficients and (2) doing a multi-exponentiation with them over the signature shares.
(1) is always done *naively* in O(t^2) time
(2) is (more-or-less) O(t) time
This does not scale well ๐ข๐
Why the inefficient O(t^2) time? Because of the difficulty of computing the denominators of each Lagrange coefficient L_i^P(0) below, which requires evaluating t different products of the form \prod_{j\in P, j\ne i} (i-j), where P is the set of signers that we aggregate from.
Our work (1) makes computing all Lagrange denominators efficient in O(t log^2 t) time via a polynomial multipoint evaluation, (2) implements it efficiently, and (3) applies to BLS.
Generally, it applies to any Lagrange-based threshold cryptosystem.
See ieeexplore.ieee.org/document/9152696
Why do we care? For @Aptos_Network randomness ๐ฒ , we must do a threshold signature in the PoS setting! This involves (1) rounding validator stakes down to small weights, (2) assigning each validator as many shares as they have weight & (3) doing a *weighted* threshold signature!
Even with careful rounding of stakes, the total weight (i.e., # of signers in the threshold scheme) can be anywhere from 1,000 to 10,000 (cc
@chelseakomlo), which will be rather slow.
So, our 2020 work allows us to get *much* better performance ๐
Improvement ranges anywhere from 2x to 10x at our scales.
See some concrete numbers below ๐
Fast Lagrange is just one of the ingredients we use to make instant randomness on @Aptos_Network possible!
And we hope you use it in your own Rust-based work (see github.com/aptos-labs/aptos-core/blob/9a45f0844a82a331f27bc692de8e81ed5c5b8c06/crates/aptos-dkg/src/algebra/lagrange.rs#L134)
Stay tuned to hear about the next ones! ๐ป ๐ก
alin.apt
@alinush407
I put the "crypto" in "cryptocurrency" | Founding Team & Head of Cryptography at @AptosLabs