Future of `PrimeFieldBits`

[kayabaNerve]

Serai extensively use makes use of PrimeFieldBits to perform a decompositions of scalars. We need to:

• Use chunks of the bit decomposition to index tables for multi-scalar multiplications
• Use the explicit bit decomposition within a zero-knowledge proof
• Consider a scalar as an integer, which requires mapping it to an integer type, which the bit decomposition enabled (as byte representations are opaque)
• And in theory/historically, split a scalar into a list of values each of low-norm (e.g. 16 16-bit chunks), when we need low-norm values but don't need the inefficiency of representing each individual bit individually. One example would be the cross-group Discrete-Log equality proof which we implemented per-bit, but could be optimized into 64-bit chunks with use of a range proof

Without PrimeFieldBits, the only other way to decompose a scalar currently is:

• Checking the LSB with PrimeField::is_odd.
• Clearing the LSB by subtracting Field::ONE.
• Shifting the number down via dividing by two.

for NUM_BITS iterations, which is absurd.

Unfortunately, RustCrypto is dropping support for PrimeFieldBits. While I understand the reasoning against the bitvec dependency, that doesn't change we need this functionality.

zkcrypto/rfcs#4 would fix this as any solution for a non-opaque representation of a scalar is sufficient for all of these use cases. I also believe there may be some discussion for an amenable trait in elliptic-curve, though I personally don't appreciate the size/scope of the elliptic-curve crate and would prefer something appropriately small/minimal for this. We could define our own trait, but then it's another piece of Serai machinery which really should be upstreamed... Until then, we can simply not update? or maintain forks? but those decisions also suck.

[kayabaNerve]

The underlying concerns regarding bitvec are very warranted, and Serai should likely try to remove it as a dependency. I believe we also used it in the Substrate libraries... The shame is, we still need an alternative solution for multiexp. One bad idea I had was to use specialization, where there technically is limited stable runtime reflection over if a type implements a trait? This causes multiexp to work in general (poorly) but ideally yes, use an optimized implementation for bit decomposition...