zkcrypto / ff Goto Github PK

Rationale:

• 2021 edition support:
  • v2 resolver.
  • rust-version in Cargo.toml
• bitvec 1.0.0 raises its MSRV to 1.56.0.

Rationale:

• Weak dependency features (so we can conditionally enable ff_derive features based on ff features without force-enabling ff_derive).

1.60.0 was released April 7, so we won't be doing this before July at the earliest. ff 0.12 will have MSRV 1.56 (#74).

Over on RustCrypto/traits#1024 we're discussing how to represent a parameter which is ultimately passed to Field::pow_vartime.

I was suggesting representing it as a crypto_bigint::UInt which internally uses 32-bit limbs on 32-bit platforms and 64-bit limbs on 64-bit platforms.

Field::pow_vartime accepts a type that impls AsRef<[u64]> as an exponent, regardless of the target pointer width.

I think it might make sense to allow customizing that in some way to make it easier to support 32-bit limbs on 32-bit platforms.

For example, PrimeFieldBits::ReprBits makes this possible. I'm curious if a similar associated type could be added to describe an array-of-limbs which would let implementations vary the word size based on the target.

(and really, in practice I'd use the same type as PrimeFieldBits::ReprBits)

For a Fermat prime, i.e., a prime of the form 2^k + 1, ff_derive correctly computes s = k and t = 1. But t == 1 is an issue when generating the Tonelli-Shanks implementation, because t_minus_1_over_2 == 0, which causes a panic in the addchain generation.

The following tweak to prime_field_constants_and_sqrt fixes the panic. I have not thoroughly tested the resulting sqrt function, though!

    let sqrt_impl =

      ...

        } else if (modulus % BigUint::from_str("16").unwrap()) == BigUint::from_str("1").unwrap() {
            // Addition chain for (t - 1) // 2
            let t_minus_1_over_2 = if t == BigUint::one() {
                quote!( #name::one() )
            } else {
                pow_fixed::generate(&quote! {self}, (&t - BigUint::one()) >> 1)
            };

    ...

This issue is quite low urgency, given that the largest known Fermat prime is 65537 :)

The ff_derive derived PrimeField implementation fails to derive a sqrt function for primes p = 5 (mod 8) and p = 9 (mod 16), resulting in a compile-time error for these cases. According to the introduction of IACR Preprint 2012/685 (the cited reference for the algorithms used for the p = 3 (mod 4) and p = 1 (mod 16) cases), efficient algorithms do exist for computing square roots over these primes; however, these algorithms are not currently implemented here.

In Issue #33, this limitation is noted explicitly, so it may be that the desired use cases for this library don't require full coverage of odd primes. I just wanted to check whether this is an intentional omission for maintainability, or if it's simply a feature that hasn't been added yet. If it's the latter and maintainers are interested, I might be able to assemble a pull request.

It is unsafe in downstream use cases for PrimeField::to_repr and PrimeField::from_repr to have ambiguous endianness. (E.g., it's oftentimes hard to implement something for ff::PrimeField without assuming something about endianness.)

Can you either add an ENDIANNESS const or functions like to_bytes_le and from_bytes_le?

This is an idea I've been toying with in my head for a little while (and discussed with @str4d at RWC), but I'm not sure whether whether it would work out in practice, so I'm posting it here for discussion. At a high level, the idea is for ff_derive to use a similar strategy as is used by Eigen, particularly its basic internals and lazy evaluation mechanism to provide optimized implementations of entire subexpressions. For instance, in a C++ expression like

mat1 = -mat2 + mat3 + 5 * mat4;

Eigen will skip producing temporaries and instead produce a single fused evaluation loop. Eigen does this using C++ template metaprogramming, while ff_derive would use type-level programming with various trait bounds. This is (thankfully) a less powerful model than C++ templates but I think that it's still possible to do something similar to what Eigen does.

How would this work for ff_derive? Here's one idea. Rather than generating a single type for the finite field (let's call it Fp: Field), ff_derive would generate a main user-facing type (let's call it Fp as before), but the generated type Fp would have impls of Add, Mul, etc whose Outputs would be inner types implementing Into<Fp>. These inner types would also have ops impls of their own, so that a user could write expressions like

let a = (x + y) * z;

and have this produce an optimized implementation of the entire expression. (One thing we cannot do in Rust compared to C++ is overload the assignment operator, so we would likely need users to add .into() to each expression they want to evaluate to an Fp, but I think this isn't a big deal).

There are varying levels of sophistication for this on the ff_derive side, but the obstacle on the ff side is that with this approach it's not possible to implement Field, because the Field trait requires that the Output of the required ops traits is Self. Weakening this to Into<Self> would (I think) remove this obstacle.

This can be a default implementation that just makes code simpler in some cases, even though it doesn't perform any better than writing x.square() * x.

In https://github.com/zkcrypto/ff/blob/e853770f4843e47cd5e07330140b5bd1cdfc9f11/ff_derive/src/lib.rs#LL130C27-L130C36 is mentioned that the generator should be computed by the code instead of being given by the macro caller.

The thing is that I'm not sure how are we supposed to pick a generator when we can have an insane amount of possible valid choices. Is there any logic like picking the lowest or similar that you were thinking on applying here?

+ ?Sized exists in ff but not in ff_derive (On crates.io, local version is fine), this has brought compilation problems in zkcrypto/pairing even after adding ?Sized constraint to the random() functions' type parameters.
Maybe try updating ff_derive's version from 0.4.0 to 0.4.1?
Thanks!

I'm attempting to improve the performance of my EC library, by migrating to this library. I know I'm not supposed to write my own and I do understand that ff does not offer consistent time.
https://gitlab.com/cheako/jtm-rs/-/commit/714b6d624c485882d3c64b7d6b3b0b8cb38ec92f#b24749917179fb5e3e613ed2a703fcdcc6cdf9da_291_226
Here I'm checking if the value module q is negative, my usual calculations are done module p. So my question is, can ff implement signed finite fields? I'm so confused about finite fields in general... I basically brute forced my way through implementing this using num-bigint-dig.

I don't know why these are exposed but they are probably outside the scope of this crate.

The latest version is 0.5.2 in crates.io but 0.5.1 in the Cargo.toml file in this repository.

See https://github.com/filecoin-project/blstrs/runs/5026964292?check_suite_focus=true

Something of a usage question. We're using zkcrypto/ff to derive a prime field for a shared-secret implementation, and also wanted to derive ZeroizeOnDrop from the zeroize crate to limit the time key material is available in memory. However this conflicts with PrimeField's Copy trait, necessitating manual .zeroize() method calls which are more expensive to review.

Is the blanket Copy necessary? What's the best practice here?

Right now we just export this stuff but libraries won't need ff_derive to implement generic code using the ff traits, so those users shouldn't need to pull it in.

Also, learn what's changing with macros in rust 2018 and figure out how to properly handle it.

Right now Field::zero() and Field::one() are static methods of the Field trait.

If they were instead associated constants, e.g. Field::ZERO/Field::ONE, they can be used in const contexts such as defining other constants:

pub struct ProjectivePoint<Fe: Field> { x: Fe, y: Fe, z: Fe }

impl<Fe: Field> ProjectivePoint<Fe> {
    pub const IDENTITY: Self = Self {
        x: Fe::ZERO,
        y: Fe::ONE,
        z: Fe::ZERO,
    };
}

Right now some of it is outdated.

Field is already bound on ConditionallySelectable, so trait implementors are already required to pull in subtle. Having this bound would have simplified #61.

This constricts the Field definition, so requires a minor release.

This is a sub-task of zcash/librustzcash#41. We can discuss the trait refactor specifically here.

The current plan (as of 2020-09-04):

• Rework ff::Field to follow the current bls12_381 and jubjub APIs.
• Add serialization APIs to either ff::Field or ff::PrimeField.
• Remove ff::PrimeFieldRepr.
  • The above three are in zcash/librustzcash#223
• Add ff::PrimeField::ReprEndianness type
• Remove ff::Field::frobenius_map
• Remove ff::SqrtField
  • The above three are in zcash/librustzcash#228
• Add ff::PrimeField::ReprBits type (replacing ff::PrimeField::ReprEndianness)
  • #30

Would be nice to get a bitvec bump now that 1.0 is out:

https://crates.io/crates/bitvec/1.0.0

(NOTE: this question applies to the group crate traits like Group as well, but I thought I'd start here)

The ff::Field trait bounds on both fmt::Debug and fmt::Display.

Looking at bls128_381, it seems all the Display impls are equivalent to Debug:

https://github.com/zkcrypto/bls12_381/blob/0d2c06d/src/scalar.rs#L33-L37

So why not just bound on Debug?

My main motivation for requesting this is I feel Display is something I want to add when there's a somewhat well-defined string representation of a given type, e.g. something a human would reasonably try to compare with a similarly printed string representing the same object, but output from a different library.

With the blanket impl of ToString for T: Display, I also like to make sure that if a corresponding FromStr impl is ever added to the type, it can round trip the output of Display/ToString.

Code:

#[macro_use]
extern crate ff;

#[derive(PrimeField)]
#[PrimeFieldModulus = "18446744069414584321"]
#[PrimeFieldGenerator = "7"]
#[PrimeFieldReprEndianness = "little"]
struct Fpx([u64; 2]);

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    pub fn test() {
        let val1: Fpx = Fpx([3u64, 0u64]);
        let val2: Fpx = Fpx([7u64, 0u64]);
        let sum_a = val1 + val2;
        let sub_a = val1 - val2;
        let mul_a = val1 * val2;
        assert_eq!(10u64, sum_a.0[0], "Add fails");
        assert_eq!(18446744069414584317u64, sub_a.0[0], "Sub fails");
        assert_eq!(21u64, mul_a.0[0], "Mul fails");
    }
}

Output:
---- tests::test stdout ----
thread 'tests::test' panicked at 'assertion failed: (left == right)
left: 21,
right: 90194313195: Mul fails', src/lib.rs:23:9
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

I noticed that `90194313195` is `21` in Montgomery form. Is there a way to fix it?

This is stable now. We shouldn't export anything that exposes u128 as a type in the API though, which we aren't doing.

Fails to compile for some moduli lesser than 2^64

Minimal example:

#[derive(PrimeField)]
#[PrimeFieldModulus = "103"]
#[PrimeFieldGenerator = "102"]
struct Fp(FpRepr);

Compilation error:

error[E0425]: cannot find value `r0` in this scope
  --> src/main.rs:16:10
   |
16 | #[derive(PrimeField)]
   |          ^^^^^^^^^^ not found in this scope

Using the following does not compile:

ff = { version = "0.11.0", default-features = false, features = ["derive", "alloc"] }

because derive depends on bitvec which is only included with the bits feature enabled.

Compile error, and relevant code snippet:

<...>.cargo/registry/src/github.com-1ecc6299db9ec823/ff-0.11.0/src/lib.rs:269:14
    |
269 |     pub use {bitvec, byteorder, rand_core, subtle};
    |              ^^^^^^ no external crate `bitvec`

ff-0.11.0/src/lib.rs:

/// Functions and re-exported crates used by the [`PrimeField`] derive macro.
#[cfg(feature = "derive")]
#[cfg_attr(docsrs, doc(cfg(feature = "derive")))]
pub mod derive {
    pub use crate::arith_impl::*;
    pub use {bitvec, byteorder, rand_core, subtle};
}

rand_core v0.6 has been released with first-class WASM support via getrandom v0.2.

It'd be great to get a version bump of this dependency in the next breaking release.

The elliptic-curve crate presently has a FromDigest trait which it uses for hashing to a scalar:

https://docs.rs/elliptic-curve/0.6.2/elliptic_curve/trait.FromDigest.html

I think it might make sense to move that trait into this crate (possibly gated on a digest cargo feature) so it can be used for implementing protocols generically which require hash-to-scalar.

This would be a pretty large change, but I'm wondering if it makes sense to build the ff traits around the std::ops traits, instead of having custom methods for every operation.

This could be something like:

pub trait FiniteField
where
    Self: Add<Self, Output = Self>,
    Self: Sub<Self, Output = Self>,
    Self: Mul<Self, Output = Self>,
    Self: AddAssign<Self>,
    Self: SubAssign<Self>,
    Self: Copy + Clone + Sized + Debug + PartialEq + Eq + Neg,
    Self: ConstantTimeEq + ConditionallyAssignable,
{
    fn zero() -> Self;
    fn one() -> Self;
    /// Returns 0 on input 0, or UB
    fn invert(&self) -> Self;
}

impl<F: FiniteField> Default for F {
    fn default() -> Self {
        F::zero()
    }
}

/// Marker trait
pub trait PrimeField: FiniteField {}

pub trait SqrtField: FiniteField {
    /// Computes sqrt(u/v)
    fn sqrt_ratio(u: &Self, v: &Self) -> Self;

    /// Computes 1/sqrt(self)
    fn invsqrt(&self) -> Self {
        Self::sqrt_ratio(&Self::one(), self)
    }

    /// Computes sqrt(self)
    fn sqrt(&self) -> Self {
        Self::sqrt_ratio(self, &Self::one())
    }
}

/// A `FiniteField` that can be encoded in 32 bytes.
///
/// The `TryFrom` should reject non-canonical encodings.
pub trait FieldEncoding32
where
    Self: FiniteField + TryFrom<[u8; 32]> + Into<[u8; 32]>,
    for<'a> Self: TryFrom<&'a [u8; 32]>,
    for<'a> Self: TryFrom<&'a [u8]>,
{
}

/// FieldEncoding48, FieldEncoding56, etc

Similar to the Sum bound on Group, it would be nice to have one on Field as well.

Related issue: RustCrypto/elliptic-curves#685

I come here because we use ff (thanks a lot, BTW!) and when testing builds with cargo update -Z minimal-versions we encounter a problem with its dependencies.

I started looking into it, and got a bit concerned.

First bitvec comes with a chain of dependencies that seems a bit ... vague & unnecessary. I mean they do make sense, but for a staple crate I would cut them just to not have them and minimize dependencies.

Then it occurred to me that they are not in a great shape. First, AFAICT there's not even a single CI testing if the build is even passing, not to mention running unit-tests.

When I looked at wyz it didn't seem like the latest published version is even in the repo: https://github.com/myrrlyn/wyz . The last commit&tag that I can see is for 0.4: myrrlyn/wyz@183b577 so I have no idea where is latest 0.5 release coming from: https://crates.io/crates/wyz .

The problem that I was aiming at fixing does even have a PR open: myrrlyn/wyz#6 . But it wasn't merged for 1.5 year now, which seems very long for an obvious change that adds 4 characters. https://github.com/myrrlyn/wyz/pull/6/files

So... yeah. It doesn't build my confidence. I hope don't come off too negative, as it's not my intention. I know that Open Source maintenance is laborious and often ungrateful, and I appreciate (usually unpaid) effort everyone is putting in making Rust ecosystem so great. But for a crate that will most definitely be used for serious crypto stuff, it is something to address - maybe we could help the maintainer, eliminate the extra deps, etc.

We removed the SqrtField trait in ff 0.7.0, as all fields that we intend the Field trait to apply to support a sqrt operation (ff_derive is able to derive implementations for p = 3 (mod 4) and p = 1 (mod 16)). More precisely, SqrtField was a separate trait because Field was previously implemented on the pairing::bls12_381::{Fq6, Fq12} extension fields of BLS12-381, which didn't have square-root operations; these are not part of the bls12_381 crate's public API.

In #6, @hdevalence had separately suggested adding several sqrt-related operations to the then-existing SqrtField trait:

pub trait SqrtField: FiniteField {
    /// Computes sqrt(u/v)
    fn sqrt_ratio(u: &Self, v: &Self) -> Self;

    /// Computes 1/sqrt(self)
    fn invsqrt(&self) -> Self {
        Self::sqrt_ratio(&Self::one(), self)
    }

    /// Computes sqrt(self)
    fn sqrt(&self) -> Self {
        Self::sqrt_ratio(self, &Self::one())
    }
}

If these would be sufficiently widely-useful, they could be added to the Field trait. If not, we could consider re-introducing the SqrtField trait.

zcash/librustzcash#191 (comment)

We need to do this once the ff refactor changes have been upstreamed here.

When using ff_derive with the base or scalar field modulus of elliptic curves like P-256 or P-384, ff_derive requires one more limb than is strictly necessary.

Example:

use ff::PrimeField;

#[derive(PrimeField)]
#[PrimeFieldModulus = "115792089210356248762697446949407573530086143415290314195533631308867097853951")
#[PrimeFieldGenerator = "6"]
#[PrimeFieldReprEndianness = "big"]
struct P256FieldElement([u64; 4]);

...fails with the following error:

error: The given modulus requires 5 limbs.
 --> src/lib.rs:7:31
  |
7 | struct P256FieldElement([u64; 4]);

The current API is fn invert(&self) -> CtOption<Self>; this is flexible, as it allows the caller to choose to handle the zero-input case manually by mapping it to Field::zero, or treat it as an invalid case. Is this flexibility leveraged in any cryptographic protocols that we support (or want to support), or should we short-circuit this to have a consistent default?

e.g. F::one() << 63 would be equivalent to F::from_u64(1 << 63).

Currently, the following trait methods cannot be used in constant-time code:

• Field::is_zero (returns bool)
  • As of #62 this can now be emulated with f.ct_eq(&F::zero()).
• PrimeField::from_str (returns Option<Self>)
• PrimeField::from_repr (returns Option<Self>)
• PrimeField::is_odd (returns bool)
• PrimeField::is_even (returns bool)

The main problematic one is PrimeField::from_repr which prevents constant-time parsing logic, and can't be implemented in terms of other APIs (which is why we have separate constant-time APIs in the pasta_curves crate's FieldExt trait).

Meanwhile we also have PrimeField::pow_vartime which is explicitly advertised as using variable-time logic internally (even though it is effectively constant-time if using a fixed exponent).

My preference is that in a future breaking release, we change the default APIs to be constant time, and add *_vartime APIs that default to calling the constant-time impls, but that trait implementors can choose to optimise if they wish.

These are missing currently, making it quite hard to work with.

The general operation c = (a_0 * b_0) + (a_1 * b_1) + ... (i.e. an inner product, but "sum of products" is a more obvious name) is used all over the place in cryptography. We can provide a default slow implementation of the function, and then downstream crates can override it with more efficient implementations (e.g. zkcrypto/bls12_381#84).

I'm currently trying to implement Pluto-Eris see: https://github.com/daira/pluto-eris

It turns out, since PrimeField trait requires Default to be implemented for the associated trait Repr, Pluto and Eris can't be implemented as, as today, the Rust language doesn't impl Default for any array larger than 32.

The basic README example

extern crate rand;
#[macro_use]
extern crate ff;

#[derive(PrimeField)]
#[PrimeFieldModulus = "52435875175126190479447740508185965837690552500527637822603658699938581184513"]
#[PrimeFieldGenerator = "7"]
struct Fp(FpRepr);

does not work anymore. Error:

error[E0433]: failed to resolve: use of undeclared type or module PrimeFieldDecodingError
--> src/main.rs:5:10
|
5 | #[derive(PrimeField)]
| ^^^^^^^^^^ use of undeclared type or module PrimeFieldDecodingError

error[E0433]: failed to resolve: could not find rand_core in {{root}}
--> src/main.rs:5:10
|
5 | #[derive(PrimeField)]
| ^^^^^^^^^^ could not find rand_core in {{root}}

error[E0412]: cannot find type PrimeFieldDecodingError in this scope
--> src/main.rs:5:10
|
5 | #[derive(PrimeField)]
| ^^^^^^^^^^ not found in this scope
|
help: possible candidate is found in another module, you can import it into scope
|
6 | use ff::PrimeFieldDecodingError;
|

error: aborting due to 3 previous errors

Some errors have detailed explanations: E0412, E0433.
For more information about an error, try rustc --explain E0412.
error: could not compile ff.

with use ff::PrimeFieldDecodingError; the next error is:

Error:

error[E0433]: failed to resolve: could not find rand_core in {{root}}
--> src/main.rs:7:10
|
7 | #[derive(PrimeField)]
| ^^^^^^^^^^ could not find rand_core in {{root}}

The RngCore::try_fill_bytes method provides fallible random number generation.

We've discussed making our RNG methods in @RustCrypto projects similarly fallible: RustCrypto/meta#19

If a change is made here, making the same change to group would probably make sense.