Use a better optimized numeric library than GMP

[vkomenda]

According to the results of the competition the GMP dependency is a performance bottleneck. It should be replaced on x86_64 with a better optimized library such as MPIR.

MPIR is supported by Flint, ~which in turn has Rust bindings~. The available Rust bindings for Flint are not suitable in their present state because they build Flint using the GMP dependency instead of MPIR. So possibly instead of the redirection via Flint, direct MPIR bindings could be provided.

Although MPIR is faster than GMP, it supports less CPU architectures, e.g, it doesn't support ARM at the moment. For completeness we would need either a Cargo feature allowing to choose between the two libraries, or an intermediate crate providing bindings to either of the two libraries. Issue #7 discussed a backend along these lines. I personally think a Cargo feature would suffice to switch between MPIR and GMP because these have a high degree of similarity.

[burdges]

I suspect any VDF must be tuned to a particular architecture for deployment anyways, but maybe it simplifies downstream code if everything runs on ARM too.

[burdges]

Anyone who wants to write MPIR bindings, or do other optimizations, could apply for funding at https://github.com/w3f/Web3-collaboration

I'd personally prefer we spend any VDF budget on isogenies because isogenies VDFs are much more flexible, and the work yields soo many other cool toys, but some MPIR bindings sound inexpensive and handy regardless.

[vkomenda]

Do you mean pairing-based isogeny VDFs or trapdoor-based ones? Is there any particular kind of isogenies that offers itself to implementation?

[burdges]

I meant the pairing-based isogeny VDF, mostly because its proofs are composable, which likely improves liveness in some applicaitons. It provides encryption to the future too, but no idea how one uses that. It also yields a small but quantum annoying signature and VRF, which support aggregation for a common signer. And some IBE/IBS scheme with better aggregation but quantum annoyance only per issued key. And more..

[DemiMarie]

@burdges can you explain “quantum annoying”?

[vkomenda]

@DemiMarie, it's from the paper: "if the adversary cannot break sequentiality, even when he is allowed a quantum precomputation before seeing the point Q, we say that the VDF is quantum annoying."

[burdges]

Almost all existing public key cryptography has the property that a quantum computer can break the public key itself. And they classical computer can decrypt everything after that. In a quantum annoying scheme, the adversary cannot break the public key but they can break individual key exchanges or forge individual signatures.

Imaginary quadratics VDFs are quantum annoying because we believe the adversary must use the quantum computer separately to learn the group order for each discriminant. Also, the isogenies VDF using pairings is quantum annoying because they must compute the discrete log for H_2(m) separately for each m.

As another example, an axolotl double ratchet is arguably quantum annoying too, but an adversary has more time to run the quantum computer for key exchange cases, so this does nothing.

[burdges]

Also relevant for https://github.com/cambrian/accumulator most likely.