proposal: serialization format for BLS12-381 points #16
Comments
|
note: updated the above proposal to avoid redundancy in the encoding that could potentially require additional consistency checks |
This impl follows the proposal
pairingwg/bls_standard#16
|
when deciding on serialization format, it occurs that we should also decide whether to require serialized points to be in the prime-order subgroup or not. This makes deserialization more expensive (need to check that the point has the correct order). If strongly unforgeable signatures are required, then probably the signature has to be checked for subgroup membership (otherwise---I think---one can obtain a new signature by adding a point of small order to an existing signature). But I have to admit I don't remember whether this is true (I suppose checking is easy...), and I just plain don't know whether strong unforgeability is a requirement here. Probably there's also some attack that involves adding a point of small order to an existing public key. But intuitively it seems like proof of possession should help. Again, I need to think more carefully about this. In any case, all of this thinking should happen before deciding on whether or not to require serialized points to be in the prime-order subgroup :) |
|
Someone asked in the last meeting whether this can be made backwards compatible with the ZCash format, and the answer is approximately "yes." The short-short-short version is, given a serialized point in the ZCash format, as long as its length is known a priori (which is already a requirement for deserializing such points, because that's the only way to tell a G1 from a G2 point), it's very simple to distinguish it from a point in the format described above, and thereby unambiguously decode it. In more detail, here's how "compatible decoding" would work. Rows in the following table correspond to the 3 MSBs of the serialized point, and columns correspond to an optional
Decoding according to the above table simultaneously supports both the ZCash and the extended serialization format. Note that it's not obvious to me that this should be done; the point is only to establish that it can be done :) |
|
My current position leans toward "don't change the serialization" mainly because not only has the existing format been deployed in Zcash, but it has also been deployed in protocols for public resource like Powers of Tau. I'm not sure it's worth it really. |
|
Probably we won't specify serialization formats in this draft, which essentially moots this proposal. Beyond that, @hoeteck and @sergeynog point out (out-of-band) that the ciphersuite will be necessary when validating signatures, and knowing the ciphersuite is sufficient to disambiguate the serialized point (because csuite will encode which curve sigs live on). This means we can live with the low-level ambiguity. So: closing this. |
Here's what zcash uses for BLS12-381 point serialization (see the issue where this was decided).
Reproducing here:
The above works, but suffers from a potential issue: it does not differentiate between points on G1 and points on G2.
Admittedly, this might not matter, because it may be that the group is unambiguously determined by the context. For example, if the ciphersuite byte is part of a serialized signature, that suffices to indicate whether the expected point is in G1 or G2.
On the other hand, encoding the group in the serialization format may be more convenient, because it means that the encoding unambiguously indicates the size in bytes of the serialized point. In contrast, the ZCash approach relies on either knowing the group a priori or using the size of the encoding to distinguish between points on G1 and G2. This means that messages encoding points may in some cases require a higher-level preamble or header indicating message length.
Conveniently, it turns out that there are enough spare bits in the above encoding to differentiate between points on G1 and points on G2 in a way that allows the first byte of an encoded point to fully specify the length of the encoding. The reason is that elements of G2 are encoded as
c1 || c0(per the above) with the 3 header bits squirreled away in the 3 MSBs of the encoding ofc1; and this leaves 3 MSBs of c0 with which to encode more information.Here's my concrete proposal.
When the 3 MSBs are
011or111, this is a point on G2, so its serialized length is 192 or 96 bytes, respectively. Otherwise,0xxis 96 bytes and1xxis 48 bytes. Thus, the first byte of the serialized point lets you know exactly how many more bytes are to come.When the point is on G2, the most significant bit of byte 48 should be 1, and the remaining two bits are determined by the table below. Note that compressed/uncompressed is determined in byte 0, so it is not redundantly encoded here.
The 3 MSBs of the encoding of all other residues mod p in any encoded point must be
000. This means that byte 48 of uncompressed points on G1 and bytes 96 and 144 of uncompressed points on G2 must begin000.There's one thing about the above that is slightly annoying: why bother sending (at least) 47 null bytes when encoding a point at infinity? Not only does this waste space on the wire, it means (at least in the ZCash spec) that user code must check that those bytes are actually 0 (see above, "the remaining bits ... should be set to zero") and reject malformed points of this sort.
One argument in favor of keeping "long" encodings of the point at infinity is that it means that all encoded points are some multiple of 48 bytes, and thus user code doesn't have to read one byte, figure out how many more to read, and then read that many more. And arguably it's not worthwhile to make things complex just to shorten the encoding of a point that will only very rarely be encoded in the first place!
Perhaps it would be worthwhile to make
001in the MSBits of byte 0 mean "point at infinity on G2, next 47 bytes must be null," and get rid of the other point at infinity representations for G2. In this case I'd also argue that the "uncompressed point at infinity on G1" encoding should be illegal. But I don't think these are crucial.The text was updated successfully, but these errors were encountered: