We re-introduce the Tonelli-Shank square root algoritm that was removed
in zcash/halo2#120, to use in no-std mode (the table-based impl requires
allocations, and also uses 29kiB of memory which is a problem for
constrained environments that typically need no-std).
The `FieldExt` trait was originally the only trait implemented in this
crate. When we added `ff` support, we reworked `FieldExt` to be an
extension trait on top of `ff::PrimeField`, but left the existing impls
in `FieldExt`. This resulted in some circular dependencies that prevent
us from making `FieldExt` conditional (e.g. for no-std support).
This commit removes the cycles like so:
- `ff::PrimeField::{from_repr, to_repr}` were implemented as calls to
`FieldExt::{from_bytes, to_bytes}`. The field encoding/decoding logic
is moved into the `ff::PrimeField` trait impl, and `FieldExt` now
calls into `ff::PrimeField`.
- `ff::Field::sqrt` was implemented in terms of `FieldExt::sqrt_alt`.
Given that the latter is a trivial wrapper around the `SqrtTables`
implementation, we duplicate the call to eliminate the cycle.
- `ff::Field::random` used `FieldExt::from_bytes_wide`, which wraps
either `Fp::from_u512` or `Fq::from_u512`. We now use these internal
methods directly.
They already implement CofactorGroup (trivially, with the prime-order
subgroup being Self); this just enables Pallas and Vesta to be used in
cofactor-aware protocols that also want to leverage the affine point
representation.
The previous `CurveAffine::get_xy` method returned the coordinates as
`CtOption<(C::Base, C::Base)>`. However, `ConditionallySelectable` is
not implemented for any tuple or array types, making it impossible to
use any of the useful `CtOption` methods like `and_then`. We replace it
with `CurveAffine::coordinates -> CtOption<Coordinates<Self>>` and
`impl ConditionallySelectable for Coordinates` to enable operating over
coordinates in constant time.
Jack Grigg
porcuquine
ebfull
Daira Hopwood
Steven
Steven Smith
dignifiedquire