BLS12-381: Clarification between G1/G2 and serialisation

[mratsim]

@vbuterin @JustinDrake thank you for the new spec regarding BLS12-381.

Comparison with ethresear.ch post

I've compared it with the mini-spec from https://ethresear.ch/t/pragmatic-signature-aggregation-with-bls/2105/31.

I noticed the following differences:

As of this version of the specs we have G1 48 bytes and G2 96 bytes (like Zcash) while the ethresear.ch post (and Chia Network) is using the G1 96 bytes and G2 48 bytes.

I.e. Are the changes intentional?

Serialization

Internally many libraries are using a custom binary representation for bigint for crypto to avoid dealing with carry, for example in Milagro

4 Handling BIG Numbers
4.1 Representation
One of the major design decisions is how to represent the 256-bit field elements required for the elliptic curve and pairing-based cryptography. Here there are two different approaches.

One is to pack the bits as tightly as possible into computer words. For example on a 64-bit computer 256-bit numbers can be stored in just 4 words. However to manipulate numbers in this form, even for simple addition, requires handling of carry bits if overflow is to be avoided, and a high-level language does not have direct access to carry flags. It is possible to emulate the flags, but this would be inefficient. In fact this approach is only really suitable for an assembly language implementation.

The alternative idea is to use extra words for the representation, and then try to offset the additional cost by taking full advantage of the "spare" bits in every word. This idea follows a "corner of the literature" which has been promoted by Bernstein and his collaborators in several publications.

or BearSSL is using i15/i31 limbs (int16 and int32 with spare bits):

Elliptic Curves
BearSSL includes several implementations of elliptic curves. Some use the same generic big integer functions as RSA (“i15” and “i31” code), and thus inherit their constant-time characteristics; other include specialised code which is made faster by exploiting the special format of the involved field modulus.

Some points are worth mentioning, for the implementations of NIST curves:

• ...

• ECDSA signature verification entails computing aG+bQ where a and b are two integers (modulo the curve order), G is the conventional generator, and Q is the public key. Classic implementations mutualise the doublings in the two double-and-add instances; however, this implies a larger table for window optimisation: if using 2-bit windows, then the aggregate table must have all combinations of G and Q with multipliers up to 3, so we are in for at least 13 extra values (apart from G and Q themselves). Each such point uses 216 bytes (three coordinates large enough for the P-521 curve, over 31-bit words with an extra “bit length” word) so such a window would use up almost 3 kB of stack space. We cannot afford that within BearSSL goals.

So we need to define a canonical serialisation that is used during communication.

If understood correctly the serialisation format is defined by

Specifically, a point in G1 as a 384-bit integer z, which we decompose into:

- x = z % 2**381
- highflag = z // 2**382
- lowflag = (z % 2**382) // 2**381

which is just the natural way to extend uint32 / uint64 to uint384.

Is the following visualisation correct? I assume big endian, so most significant bit on the left.

 384     381            192              0
  +-------+--------------+---------------+
  | 0 0 0 |    high      |      low      |
  +-------+--------------+---------------+

   unused <--------------x--------------->

[JustinDrake]

Please ignore the notation I used in the ethresear.ch post :) The spec is the reference. Having said that, it is intentional to have 48-byte pubkeys and 96-byte signatures. The reason is that the performance of signature verification is improved when adding pubkeys (to form the aggregated pubkey) is fast, i.e. happens on the "small-and-fast" curve.

[hwwhww]

@mratsim can we close this issue?

[JustinDrake]

FWIW, I believe that Chia also has pubkeys on the small-and-fast curve (unlike Zcash).

[JustinDrake]

Please reopen if you still have questions @mratsim :)