Confirm curves to use for aggregate signature and public keys

[mratsim]

Context

Blocking #4 - Implement AggregateSignature

From spec: https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html

BLS signature Scheme

• KeyGen(): choose a random α ← Zq and set h ← g ∈ G1. output pk:=(h) and sk:=(α). (pk public key, sk secret/private key)
• Sign(sk,m): output σ←H0(m)^α ∈ G0. The signature is a single group element.
• Verify(pk,m,σ): if e(g1,σ)=e(pk, H0(m)) output "accept", otherwise output "reject".

In Milagro libraries:

• spec G1 is amcl G the Generator of ECP (see ECP_BLS381_KEY_PAIR_GENERATE)
• G2 is not used for signing

Referring to Zcash spec: https://github.com/zkcrypto/pairing/tree/master/src/bls12_381#bls12-381-instantiation

Fq elements are 48 bytes (ECP in milagro crypto?) Fq2 elements are 96 bytes (ECP2 in milagro crypto?)

Referring to Vitalik's Elliptic Curve Pairing: https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

G1 is on Fq G2 is on Fq12

Note that signatures in Milagro crypto are passed as a tuple (c, d) which seems to match with the real + imaginary complex used for ECP2

Some checks

An check that could be done would be making sure that G1 https://github.com/status-im/nim-milagro-crypto/blob/290f927865f9e575920dca5f415c58b554dbe92e/src/milagro_crypto/generated/rom_curve_BLS381.c#L19-L20

and G2 https://github.com/status-im/nim-milagro-crypto/blob/290f927865f9e575920dca5f415c58b554dbe92e/src/milagro_crypto/generated/rom_curve_BLS381.c#L27-L30

matches with G1

x = 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
y = 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569

and G2

x = 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758*u + 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160
y = 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582*u + 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905

from Zcash https://github.com/zkcrypto/pairing/tree/master/src/bls12_381.

We can see from the hex version de Zcash that the couple few last Zcash hex digits match with the first hex digits of Milagro. 17F1D3A73197D7942695638C4FA9AC0FC3688C4F9774B905A14E3A3F171BAC586C55E83FF97A1AEFFB3AF00ADB22C6BB

However Milagro "Big" representation uses a word excess + base word (see Milagro whitepaper) instead of a standard representation so we can't compare with milagro raw hex.

Other lib using Milagro for aggregate signature

This library https://github.com/lovesh/signature-schemes/blob/master/src/bls/aggr_new.rs is using Milagro Rust as a backend for BLS aggregate signature.

• G1/ECP for signature aggregation
• G2/ECP2 for public key aggregation

which seems strange

[mratsim]

See #8 and the new Wiki article: https://github.com/status-im/nim-milagro-crypto/wiki/Resources-&-TODO.

The verify implementation in Milagro I was checking doesn't use G2 but it's also probably not the deterministic signature verification we should use as there is a CSPRNG parameter in sign.

I.e. we need to implement deterministic signing and verification similar to: https://github.com/lovesh/signature-schemes/blob/63238e935455a03193425f0a6fda928f72754a27/src/bls/simple.rs

impl Signature {
    // Signature = H_0(msg) * sk
    pub fn new(msg: &[u8], sig_key: &SigKey) -> Self {
        let hash_point = hash_on_GroupG1(msg);
        let sig = hash_point.mul(&sig_key.x);
        // This is different from the paper, the other exponentiation happens in aggregation.
        // This avoids the signer to know beforehand of all other participants
        Signature { point: sig }
    }

    pub fn verify(&self, msg: &[u8], ver_key: &VerKey) -> bool {
        // TODO: Check if point exists on curve, maybe use `ECP::new_big` and x cord of verkey
        if self.point.is_infinity() {
            println!("Signature point at infinity");
            return false;
        }
        let msg_hash_point = hash_on_GroupG1(msg);
        let mut lhs = ate_pairing(&GeneratorG2, &self.point);
        let mut rhs = ate_pairing(&ver_key.point, &msg_hash_point);
        /*let mut lhs_bytes: [u8; FP12_SIZE] = [0; FP12_SIZE];
        let mut rhs_bytes: [u8; FP12_SIZE] = [0; FP12_SIZE];
        lhs.tobytes(&mut lhs_bytes);
        rhs.tobytes(&mut rhs_bytes);
        lhs_bytes.to_vec() == rhs_bytes.to_vec()*/
        lhs.equals(&mut rhs)
    }
}

[mratsim]

Closing, implementation done