https://crypto.stanford.edu/pbc/

I was under impression pairings would take roughly 30 milliseconds according to the link above.

But my test shows otherwise:

$ time cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/hello_world`
PT0.321907197S seconds for whatever you did.

real	0m0.840s
user	0m0.792s
sys	0m0.012s

My test code:

extern crate bn;
extern crate rand;
extern crate time;
use bn::{Group, Fr, G1, G2, pairing};
use time::PreciseTime;

fn main() {
	let rng = &mut rand::thread_rng();

	// Generate private keys
	let bob_sk = Fr::random(rng);
	let carol_sk = Fr::random(rng);

	// Generate public keys in G1 and G2
	let (bob_pk1, bob_pk2) = (G1::one() * bob_sk, G2::one() * bob_sk);
	let (carol_pk1, carol_pk2) = (G1::one() * carol_sk, G2::one() * carol_sk);

	// Time the pairing
	let start = PreciseTime::now();
	let alice_ss = pairing(bob_pk1, carol_pk2);
	let end = PreciseTime::now();
	
	println!("{} seconds for whatever you did.", start.to(end));
}

@chronusz

The y coordinate shouldn't be negated if it's zero. Since z = 0, this doesn't break any library invariants.

I pushed 4e2096bedd67d77370985b5ee92f4ab241c25430 to master on accident, so please review that as well. [Edit by @daira: link to commit.]

See also https://github.com/scipr-lab/libsnark/issues/60.

This also bumps the crate version.

Currently, Fq2 elements (c1*q + c0) are serializing c1 || c0, this changes the serialization to match the IEEE 1363 standard format, which we use in Zcash.

Since we're adding divrem anyway for the standard, I changed Fp randomness to sample a random U512 and modulo the field char for a uniform distribution. (This was recommended by @daira.) This also allows me to add Fr interpretation to the API, which is useful for signature schemes.

https://github.com/paritytech/bn/blob/master/src/groups/mod.rs#L108 The check is here. I have seen no the same checks in bellman_ce, go-ethereum, and ethereumj. But parity-ethereum (openethereum) is still using this costly check.

Obviously, we should not check the subgroup for G1 at the prime order curve. What about checking G2 subgroup before pairing?

This adds a new normalize method to Group that can be used to speed up serialization in parallel. The jacobian-to-affine conversion will handle the trivial case of z=1, speeding up serialization significantly in some cases. In the future, I would rather elevate this stuff to the type system, but this works for now.

Also, cleaned up the benchmarks.

test fq12_exponentiation         ... bench:   5,969,704 ns/iter (+/- 410,626)
test fq12_scalar_multiplication  ... bench:      19,286 ns/iter (+/- 756)
test fr_addition                 ... bench:          22 ns/iter (+/- 5)
test fr_inverses                 ... bench:      10,260 ns/iter (+/- 206)
test fr_multiplication           ... bench:         146 ns/iter (+/- 47)
test fr_subtraction              ... bench:          22 ns/iter (+/- 6)
test g1_addition                 ... bench:       2,597 ns/iter (+/- 200)
test g1_deserialization          ... bench:       1,229 ns/iter (+/- 118)
test g1_scalar_multiplication    ... bench:     633,965 ns/iter (+/- 12,880)
test g1_serialization            ... bench:      11,888 ns/iter (+/- 261)
test g1_serialization_normalized ... bench:         687 ns/iter (+/- 169)
test g1_subtraction              ... bench:       2,606 ns/iter (+/- 152)
test g2_addition                 ... bench:      11,340 ns/iter (+/- 475)
test g2_deserialization          ... bench:       9,407 ns/iter (+/- 273)
test g2_scalar_multiplication    ... bench:   2,728,459 ns/iter (+/- 336,310)
test g2_serialization            ... bench:      15,467 ns/iter (+/- 257)
test g2_serialization_normalized ... bench:       1,353 ns/iter (+/- 146)
test g2_subtraction              ... bench:      11,382 ns/iter (+/- 238)
test perform_pairing             ... bench:   6,992,153 ns/iter (+/- 788,769)

on my system:

test g1_deserialization ... bench: 1,264 ns/iter (+/- 35) test g2_deserialization ... bench: 3,650 ns/iter (+/- 143)

• [x] New Fp/Fp2 implementations
• [x] New G1/G2 implementations
• [x] New Fp6/Fp12 implementations
• [x] New pairing implementations
• [x] Test vectors, benchmarks, travis tests

seems like a lot of people fork and add bits but don't PR back to the main lib?

wondering if there's some way that maybe co-ordination could be improved? I wonder why they don't contribute back...

Hi,

We needed Gt to be serializabe. This approach might not be the cleanest solution as I am still a rust newbie, but it does the job for us currently.

OTOH, you might want to replace serialisation with serde soon anyway...

BR Martin

I'm designing a new "core" for the cryptography in this library, mostly in the interest of performance and flexibility.

Features include:

• The library will support multiple BN curve implementations all behind this abstract API. In particular, I plan to integrate a stronger curve construction which should be more secure and more useful for zk-SNARKs.
• The user can perform miller loops (with any number of point tuples) manually if they want to avoid unnecessary final exponentiations or redundant ate loops. The Ethereum folks will need to expose all of this functionality in their precompiles if they want to give users maximum performance and flexibility, especially if you need to use newer zk-SNARK schemes or do batch/probablistic verification of proofs.
• The user can perform G2 precomputation for the miller loop manually.
• Support for mixed addition.
• Support for curve point compression (the same way that Zcash compresses proofs).

API preview:

pub trait Field<E: Engine>: Sized +
                            Eq +
                            PartialEq +
                            Copy +
                            Clone +
                            Send +
                            Sync +
                            Debug +
                            'static
{
    fn zero() -> Self;
    fn one(&E) -> Self;
    fn random<R: rand::Rng>(&E, &mut R) -> Self;

    fn is_zero(&self) -> bool;
    
    fn square(&mut self, &E);
    fn double(&mut self, &E);
    fn negate(&mut self, &E);
    fn add_assign(&mut self, &E, other: &Self);
    fn sub_assign(&mut self, &E, other: &Self);
    fn mul_assign(&mut self, &E, other: &Self);
    fn inverse(&self, &E) -> Option<Self>;
    fn sqrt(&self, &E) -> Option<Self>;
    fn powi<I: IntoIterator<Item=u64>>(&self, engine: &E, exp: I) -> Self;
    fn powb<I: IntoIterator<Item=bool>>(&self, engine: &E, exp: I) -> Self;
}

pub trait PrimeField<E: Engine>: Field<E>
{
    type Repr: AsRef<[u64]>;

    fn from_str(&E, s: &str) -> Result<Self, ()>;
    fn from_repr(&E, Self::Repr) -> Result<Self, ()>;
    fn into_repr(&self, &E) -> Self::Repr;
}

/// A representation of a group element that can be serialized and deserialized,
/// but is not guaranteed to be a point on the curve.
pub trait GroupRepresentation<E: Engine, F: Field<E>, G: Group<E, F>>: Copy +
                                                                       Clone +
                                                                       Sized +
                                                                       Send +
                                                                       Sync +
                                                                       Debug +
                                                                       'static
{
    /// Attempt to parse the representation as an element on
    /// the curve in the affine.
    fn to_affine(&self, &E) -> Option<G::Affine>;

    /// This is like `to_affine` except the caller is
    /// responsible for ensuring the point is on the curve.
    /// If it isn't, this function is allowed to panic,
    /// but not guaranteed to.
    fn to_affine_unchecked(&self, &E) -> G::Affine;
}

pub trait GroupAffine<E: Engine, F: Field<E>, G: Group<E, F>>: Copy +
                                                               Clone +
                                                               Sized +
                                                               Send +
                                                               Sync +
                                                               Debug +
                                                               PartialEq +
                                                               Eq +
                                                               'static
{
    fn to_jacobian(&self, &E) -> G;
    fn to_compressed(&self, &E) -> G::Compressed;
    fn to_uncompressed(&self, &E) -> G::Uncompressed;
}

pub trait Group<E: Engine, F: Field<E>>: Sized +
                                         Eq +
                                         PartialEq +
                                         Copy +
                                         Clone +
                                         Send +
                                         Sync +
                                         Debug +
                                         'static
{
    type Affine: GroupAffine<E, F, Self>;
    type Compressed: GroupRepresentation<E, F, Self>;
    type Uncompressed: GroupRepresentation<E, F, Self>;
    type Prepared: Clone + 'static;

    fn zero(&E) -> Self;
    fn one(&E) -> Self;
    fn random<R: rand::Rng>(&E, &mut R) -> Self;

    fn is_zero(&E) -> Self;

    fn to_affine(&self, &E) -> Self::Affine;
    fn prepare(&self, &E) -> Self::Prepared;

    fn double(&mut self, &E);
    fn negate(&mut self, engine: &E);
    fn add_assign(&mut self, &E, other: &Self);
    fn add_assign_mixed(&mut self, &E, other: &Self::Affine);
    fn mul_assign(&mut self, &E, other: &E::Fr);
}

pub trait Engine: Sized {
    type Fq: PrimeField<Self>;
    type Fr: PrimeField<Self>;
    type Fqe: Field<Self>;
    type Fqk: Field<Self>;
    type G1: Group<Self, Self::Fq>;
    type G2: Group<Self, Self::Fqe>;

    fn new() -> Self;

    fn miller_loop<'a, I>(&self, I) -> Self::Fqk
        where I: IntoIterator<Item=&'a (
                                    &'a <Self::G1 as Group<Self, Self::Fq>>::Prepared,
                                    &'a <Self::G2 as Group<Self, Self::Fqe>>::Prepared
                               )>;

    fn final_exponentiation(&self, &Self::Fqk) -> Self::Fqk;

    fn pairing(&self, p: &Self::G1, q: &Self::G2) -> Self::Fqk
    {
        self.final_exponentiation(&self.miller_loop(
            [(&p.prepare(self), &q.prepare(self))].into_iter()
        ))
    }
}

This PR implements the Boneh Franklin "BasicIdent" IBE scheme with BN curves. I'll update the PR with the FullIdent scheme once I write it.

From what I've read, the original scheme works on bilinear pairings, but with G1 x G2 -> Gt, it only requires that CDH holds in G1 and G2, and DDH holds in Gt, so it should work on BN curves (could anyone confirm this?).

This PR uses the two previous ones, the first to fix compilation, the second to reuse the sighash module. I'll rebase when those are merged.

What I currently need to move this forward, is a way to serialize a point in compressed form, to generate a hash from it. The way I do it for this test is very ugly: using format! and the Debug implementation for g_idto generate a string, and hashing it with sha256.

A way to serialize and deserialize arbitrary points from G1, G2 and Gt would be useful as well, to transport ciphertexts or signatures.

The hash derived from the shared g_id point is used to generate a Chacha20 key instead of XOR-ing it directly with the plaintext. I think it is ok, assuming that Chacha20 is a PRF, but I have not verified it yet. It keeps the malleability from the original scheme, but it would not be hard to derive more data, to do a Chacha20+Poly1305 authenticated encryption (or any other algorithm combination).