Proposal: BLS serialization tests

[hwwhww]

BLS serialization tests

Background

• The latest IETF BLS standard draft (04) uses ZCash's point representations as the serialization format.
• We used to have an old https://github.com/ethereum/eth2.0-specs/blob/v0.9.0/specs/bls_signature.md#point-representations doc as the explainer of the Zcash docs. But it was deleted since we expected the IETF BLS standard would define it more formally.
• Here is a good summary of the different cases of 3 MSBs of byte 0 in compressed format (see the "ZCash semantics" column): proposal: serialization format for BLS12-381 points pairingwg/bls_standard#16.
• We currently don't have a test suite for BLS compression/decompression tests.

Proposed new test suite

The input and output of our BLS APIs are all in minimal-pubkey-size form (compressed 48-byte pubkey and 96-byte signature). So the functions to test would be:

def compress_G1(decompressed_pubkey: bytes96) -> bytes48

• input:
  • decompressed_pubkey: bytes96
• output:
  • compressed_pubkey: (i) bytes48 or (ii) empty for the invalid cases.

def decompress_G1(compressed_pubkey: bytes48) -> bytes96

• input:
  • compressed_pubkey: bytes48
• output:
  • decompressed_pubkey: (i) bytes96 (ii) empty for the invalid cases.

def compress_G2(decompressed_signature: bytes192) -> bytes96

• input:
  • decompressed_signature: bytes192
• output:
  • compressed_signature: (i) bytes96 (ii) empty for the invalid cases.

def decompress_G2(compressed_signature: bytes96) -> bytes192

• input:
  • compressed_signature: bytes96
• output:
  • decompressed_signature: (i) bytes192 (ii) empty for the invalid cases.

Discussions

1. Are the APIs available?

• 1.1. I naively assumed that the BLST binding does provide these APIs for all supported languages. Could the client teams help check if it's true? /cc @kirk-baird @michaelsproul @benjaminion @mratsim @nisdas and @dot-asm
• 1.2. Do your compression and decompression APIs include subgroup membership checking?

2. Did the fuzzing already cover the 3-MSBs edge cases of BLS tests?

/cc @zedt3ster

3. Do you think it would help to reduce the consensus error risks?

/cc @JustinDrake @CarlBeek

[nisdas]

@hwwhww For testing compressing/decompressing of G1/G2 points, the Go API in BLST does have support for this so its not an issue on our end. Serialization test format looks good to me 👍

On 1.2 , BLST has removed subgroup checks when decompressing points as of v3 , this was just merged into Prysm here.
prysmaticlabs/prysm#7971 . I imagine it would be the same for the other language bindings too.

[dot-asm]

• 1.1. I naively assumed that the BLST binding does provide these APIs for all supported languages.

The group check is an expensive operation, and it's argued that application is entitled for a choice when to perform it. Primarily because there are situations when it's possible to perform multiple checks in parallel. In other words blst deserialization/uncompression subroutines don't perform group checks, and it's application's responsibility to either make explicit in-group-check call right after deserialization, or pass perform-group-checks-as-you-go flags to higher level procedures and utilize parallelism whenever possible.

Speaking of serialization format in more general terms. As data is deserialized and converted into internal representation format, it implicitly gets modulo reduced. In other words deserialization procedure can handle non-reduced input seamlessly. But it's only natural to assume that if input is not reduced, then somebody is trying to mess with you. For this reason first thing the [blst] deserialaztion procedure does is to ensure that input is fully reduced. However, this is not actually specified, and a formal concern can be and even was raised. In other words, while we are at it, it would be only appropriate to explicitly specify that input is expected to be fully reduced and provide corresponding test vector.

[mratsim]

1.1 The C API that we use has support for the decompression/uncompression from Zcash
1.2 We do infinity checks and subgroup checks after decompression and skip those at verification because we do a lot of verification with the same public key so no need to pay an expensive subgroup check every time.

[kirk-baird]

These APIs are all available in Apache Milagro Rust and could trivially be added to milagro_bls.

With respect to the subgroup checking in lighthouse we do that for PublicKeys at serialization time and Signatures at verification time. So it may not be on by default for lighthouse but can easily be added to tests. So happy eitherway if we are to include or not include the subgroup checks.

[zedt3ster]

From a fuzzing perspective, the existing BLS work (available here) included the 3 MSBs but was only aimed at the compressed version (i.e. MSB0 = 1)

[mratsim]

Here is a case from November 2019 where there was an infinity bit set and we didn't check properly that the rest of the bits were 0: status-im/nimbus-eth2#555

This was before we skipped the Ethereum signature for testing so it's from one of the old test vectors.

[mratsim]

Close?

https://github.com/ethereum/bls12-381-tests includes decompression tests (cc @asanso). Compression can be done by clients via round-trip tests to confirm internal consistency.