bls_verify_multiple: signature accepted wrongly

[mratsim]

For the invalid_sig_2 test case in process_attester_slashing - https://github.com/ethereum/eth2.0-spec-tests/tree/ae6dd9011df05fab8c7e651c09cf9c940973bf81/tests/minimal/phase0/operations/attester_slashing/pyspec_tests/invalid_sig_2

we accept an invalid signature for the second attestation.

Nim logs after instrumentation:

[Suite] Official - Operations - Attester slashing  [Preset: minimal]
msg1: {"data":{"beacon_block_root":"36ADD8F44BB1D56D274DEE7719A7BFA0B711D0FD16405DF73744B516FB48B5BC","source":{"epoch":0,"root":"0000000000000000000000000000000000000000000000000000000000000000"},"target":{"epoch":0,"root":"36ADD8F44BB1D56D274DEE7719A7BFA0B711D0FD16405DF73744B516FB48B5BC"},"crosslink":{"shard":0,"parent_root":"C78009FDF07FC56A11F122370658A353AAA542ED63E44C4BC15FF4CD105AB33C","start_epoch":0,"end_epoch":0,"data_root":"0000000000000000000000000000000000000000000000000000000000000000"}},"custody_bit":false}
msg2: {"data":{"beacon_block_root":"36ADD8F44BB1D56D274DEE7719A7BFA0B711D0FD16405DF73744B516FB48B5BC","source":{"epoch":0,"root":"0000000000000000000000000000000000000000000000000000000000000000"},"target":{"epoch":0,"root":"36ADD8F44BB1D56D274DEE7719A7BFA0B711D0FD16405DF73744B516FB48B5BC"},"crosslink":{"shard":0,"parent_root":"C78009FDF07FC56A11F122370658A353AAA542ED63E44C4BC15FF4CD105AB33C","start_epoch":0,"end_epoch":0,"data_root":"0000000000000000000000000000000000000000000000000000000000000000"}},"custody_bit":true}

pubkeys: @[a49f744d9bbfbcdd106592646040a3322fbe36e628be501a13f5272ad545a149f06f59bd417df9ae1a38d08c5a2108fe, c00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]
message_hashes: [265DA027BB78DABB68A53A51BE155F311F1657AD8B7DB463DC04799A068B07F2, 310D5D275E383A5039220D5E7B850D7B6529351550B8FDEB48FD92EBB98D7DDC]
signature: b55ba5d791ef0a8cdcde372890b4f544b2ff850f5c61e511c7d65c0a12f9afda4e77f96695811265f6da57d3ea1f48e80bc8d1e105021f010f6f50e490e6f7033ab1ce182b9e025434d066d90c569240a913e11c8c34bfa4795dab642a1725c9
domain: 2
WRN 2019-09-10 14:10:08-04:00 Received empty public key, skipping verification. tid=396218
WRN 2019-09-10 14:10:08-04:00 Received empty public key, skipping verification. tid=396218
msg1: {"data":{"beacon_block_root":"36ADD8F44BB1D56D274DEE7719A7BFA0B711D0FD16405DF73744B516FB48B5BC","source":{"epoch":0,"root":"0000000000000000000000000000000000000000000000000000000000000000"},"target":{"epoch":0,"root":"0101010101010101010101010101010101010101010101010101010101010101"},"crosslink":{"shard":0,"parent_root":"C78009FDF07FC56A11F122370658A353AAA542ED63E44C4BC15FF4CD105AB33C","start_epoch":0,"end_epoch":0,"data_root":"0000000000000000000000000000000000000000000000000000000000000000"}},"custody_bit":false}
msg2: {"data":{"beacon_block_root":"36ADD8F44BB1D56D274DEE7719A7BFA0B711D0FD16405DF73744B516FB48B5BC","source":{"epoch":0,"root":"0000000000000000000000000000000000000000000000000000000000000000"},"target":{"epoch":0,"root":"0101010101010101010101010101010101010101010101010101010101010101"},"crosslink":{"shard":0,"parent_root":"C78009FDF07FC56A11F122370658A353AAA542ED63E44C4BC15FF4CD105AB33C","start_epoch":0,"end_epoch":0,"data_root":"0000000000000000000000000000000000000000000000000000000000000000"}},"custody_bit":true}

pubkeys: @[a49f744d9bbfbcdd106592646040a3322fbe36e628be501a13f5272ad545a149f06f59bd417df9ae1a38d08c5a2108fe, c00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]
message_hashes: [C95B0E9B54380B3456DCE5884F25FFCC6C5A85CFEABC824B39FE9BF908CAAA55, F91D9E2C071FD4D8A9F5DE7B004A5642038B0CA50668C4CC42A339C9448A580E]
signature: b55ba5d791ef0a8cdcde372890b4f544b2ff850f5c61e511c7d65c0a12f9afda4e77f96695811265f6da57d3ea1f48e80bc8d1e105021f010f6f50e490e6f7033ab1ce182b9e025434d066d90c569240a913e11c8c34bfa4795dab642a1725c9
domain: 2
WRN 2019-09-10 14:10:08-04:00 Received empty public key, skipping verification. tid=396218
WRN 2019-09-10 14:10:08-04:00 Received empty public key, skipping verification. tid=396218
./nim-beacon-chain/tests/official/test_fixture_operations_attester_slashings.nim(72) test_fixture_operations_attester_slashings
./nim-beacon-chain/tests/official/test_fixture_operations_attester_slashings.nim(57) testImpl_operations_attester_slashing_invalid_sig_2
./.choosenim/toolchains/nim-0.19.6/lib/system.nim(3879) failedAssertImpl
./.choosenim/toolchains/nim-0.19.6/lib/system.nim(3872) raiseAssert
./.choosenim/toolchains/nim-0.19.6/lib/system.nim(2918) sysFatal

    Unhandled exception: ./nim-beacon-chain/tests/official/test_fixture_operations_attester_slashings.nim(57, 18) `done3656088 == false` We didn't expect this invalid attester slashing to be processed. [AssertionError]
  [FAILED] [Invalid] invalid_sig_2

Pyspec logs after similar instrumentation

eth2spec/test/phase_0/block_processing/test_process_attester_slashing.py
>>> Attestation 1 <<<
^^^^^^^^^^^^^^^^^^^^^
Phase0 - Serialized msg1: 36add8f44bb1d56d274dee7719a7bfa0b711d0fd16405df73744b516fb48b5bc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000036add8f44bb1d56d274dee7719a7bfa0b711d0fd16405df73744b516fb48b5bc0000000000000000c78009fdf07fc56a11f122370658a353aaa542ed63e44c4bc15ff4cd105ab33c00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Phase0 - Serialized msg2: 36add8f44bb1d56d274dee7719a7bfa0b711d0fd16405df73744b516fb48b5bc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000036add8f44bb1d56d274dee7719a7bfa0b711d0fd16405df73744b516fb48b5bc0000000000000000c78009fdf07fc56a11f122370658a353aaa542ed63e44c4bc15ff4cd105ab33c00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

######  bls_verify_multiple  #######
#############################################
pubkeys: ['a49f744d9bbfbcdd106592646040a3322fbe36e628be501a13f5272ad545a149f06f59bd417df9ae1a38d08c5a2108fe', 'c00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000']
message_hashes: ['265da027bb78dabb68a53a51be155f311f1657ad8b7db463dc04799a068b07f2', '310d5d275e383a5039220d5e7b850d7b6529351550b8fdeb48fd92ebb98d7ddc']
signature: b55ba5d791ef0a8cdcde372890b4f544b2ff850f5c61e511c7d65c0a12f9afda4e77f96695811265f6da57d3ea1f48e80bc8d1e105021f010f6f50e490e6f7033ab1ce182b9e025434d066d90c569240a913e11c8c34bfa4795dab642a1725c9
domain: 0200000000000000
bls verified: True

index_att - bls_verified: True
valid att

>>> Attestation 2 <<<
^^^^^^^^^^^^^^^^^^^^^
Phase0 - Serialized msg1: 36add8f44bb1d56d274dee7719a7bfa0b711d0fd16405df73744b516fb48b5bc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010101010101010101010101010101010101010101010101010101010101010000000000000000c78009fdf07fc56a11f122370658a353aaa542ed63e44c4bc15ff4cd105ab33c00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Phase0 - Serialized msg2: 36add8f44bb1d56d274dee7719a7bfa0b711d0fd16405df73744b516fb48b5bc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010101010101010101010101010101010101010101010101010101010101010000000000000000c78009fdf07fc56a11f122370658a353aaa542ed63e44c4bc15ff4cd105ab33c00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

######  bls_verify_multiple  #######
#############################################
pubkeys: ['a49f744d9bbfbcdd106592646040a3322fbe36e628be501a13f5272ad545a149f06f59bd417df9ae1a38d08c5a2108fe', 'c00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000']
message_hashes: ['c95b0e9b54380b3456dce5884f25ffcc6c5a85cfeabc824b39fe9bf908caaa55', 'f91d9e2c071fd4d8a9f5de7b004a5642038b0ca50668c4cc42a339c9448a580e']
signature: b55ba5d791ef0a8cdcde372890b4f544b2ff850f5c61e511c7d65c0a12f9afda4e77f96695811265f6da57d3ea1f48e80bc8d1e105021f010f6f50e490e6f7033ab1ce182b9e025434d066d90c569240a913e11c8c34bfa4795dab642a1725c9
domain: 0200000000000000
bls verified: False

index_att - bls_verified: False
invalid att: signature verification
-----------------------------------
-----------------------------------

Differences:

• It could come from the domain issue that we have - [BLS / Interop] Invalid signatures generated for deposit mock start #404
• py_ecc aggregate the pubkeys for multi-verification: https://github.com/ethereum/py_ecc/blob/c74aca90b7905a1ec9dd1454dc992d5c6f4f28b0/py_ecc/bls/api.py#L89-L117
  instead of our one-by-one approach https://github.com/status-im/nim-beacon-chain/blob/d1b1ecf86bd44eb01941f0b23c20add7950217ff/beacon_chain/spec/crypto.nim#L182-L202

Tooling

Zcli also properly reject the second attestation with the command:

$  zcli transition sub op attester_slashing -i pre.ssz -o out_foo.ssz attester_slashing.ssz
failed to process attester slashing
attestation 2 of attester slashing cannot be verified

https://simpleserialize.com/ website confirmed our SSZ serialization/hashing against lodestar implementation.

Instrumentation

Nim

# https://github.com/ethereum/eth2.0-specs/blob/v0.8.3/specs/core/0_beacon-chain.md#is_valid_indexed_attestation
proc is_valid_indexed_attestation*(
    state: BeaconState, indexed_attestation: IndexedAttestation): bool =
  ## Check if ``indexed_attestation`` has valid indices and signature.
  # TODO: this is noSideEffect besides logging
  #       https://github.com/status-im/nim-chronicles/issues/62

  let
    bit_0_indices = indexed_attestation.custody_bit_0_indices.asSeq
    bit_1_indices = indexed_attestation.custody_bit_1_indices.asSeq

  # Verify no index has custody bit equal to 1 [to be removed in phase 1]
  if len(bit_1_indices) != 0:
    notice "indexed attestation: custody_bit equal to 1"
    return false

Python

eth2.0-specs/test_libs/pyspec/eth2spec/phase0/spec.py

from eth2spec.utils.ssz.ssz_impl import serialize

def is_valid_indexed_attestation(state: BeaconState, indexed_attestation: IndexedAttestation) -> bool:
    """
    Check if ``indexed_attestation`` has valid indices and signature.
    """
    bit_0_indices = indexed_attestation.custody_bit_0_indices
    bit_1_indices = indexed_attestation.custody_bit_1_indices

    # Verify no index has custody bit equal to 1 [to be removed in phase 1]
    if not len(bit_1_indices) == 0:
        print('invalid att: custody bit equal to 1')
        return False
    # Verify max number of indices
    if not len(bit_0_indices) + len(bit_1_indices) <= MAX_VALIDATORS_PER_COMMITTEE:
        print('invalid att: max number of indices')
        return False
    # Verify index sets are disjoint
    if not len(set(bit_0_indices).intersection(bit_1_indices)) == 0:
        print('invalid att: index set disjoints')
        return False
    # Verify indices are sorted
    if not (bit_0_indices == sorted(bit_0_indices) and bit_1_indices == sorted(bit_1_indices)):
        print('invalid att: unsorted indices')
        return False

    # Verify aggregate signature
    msg1 = AttestationDataAndCustodyBit(data=indexed_attestation.data, custody_bit=0b0)
    msg2 = AttestationDataAndCustodyBit(data=indexed_attestation.data, custody_bit=0b1)

    print(f'Phase0 - Serialized msg1: {serialize(msg1).hex()}')
    print(f'Phase0 - Serialized msg2: {serialize(msg2).hex()}')


    bls_verified = bls_verify_multiple(
        pubkeys=[
            bls_aggregate_pubkeys([state.validators[i].pubkey for i in bit_0_indices]),
            bls_aggregate_pubkeys([state.validators[i].pubkey for i in bit_1_indices]),
        ],
        message_hashes=[
            hash_tree_root(msg1),
            hash_tree_root(msg2),
        ],
        signature=indexed_attestation.signature,
        domain=get_domain(state, DOMAIN_ATTESTATION, indexed_attestation.data.target.epoch),
    )
    print(f'\nindex_att - bls_verified: {bls_verified}')
    if not bls_verified:
        print('invalid att: signature verification')
        print('-----------------------------------')
        print('-----------------------------------')
        return False
    print('valid att')
    return True


def process_attester_slashing(state: BeaconState, attester_slashing: AttesterSlashing) -> None:
    attestation_1 = attester_slashing.attestation_1
    attestation_2 = attester_slashing.attestation_2
    assert is_slashable_attestation_data(attestation_1.data, attestation_2.data)
    print("\n>>> Attestation 1 <<<")
    print("^^^^^^^^^^^^^^^^^^^^^")
    assert is_valid_indexed_attestation(state, attestation_1)
    print("\n>>> Attestation 2 <<<")
    print("^^^^^^^^^^^^^^^^^^^^^")
    assert is_valid_indexed_attestation(state, attestation_2)

    slashed_any = False
    attesting_indices_1 = attestation_1.custody_bit_0_indices + attestation_1.custody_bit_1_indices
    attesting_indices_2 = attestation_2.custody_bit_0_indices + attestation_2.custody_bit_1_indices
    for index in sorted(set(attesting_indices_1).intersection(attesting_indices_2)):
        if is_slashable_validator(state.validators[index], get_current_epoch(state)):
            slash_validator(state, index)
            slashed_any = True
    assert slashed_any

eth2.0-specs/test_libs/pyspec/eth2spec/utils/bls.py

# bls.py
@only_with_bls(alt_return=True)
def bls_verify_multiple(pubkeys, message_hashes, signature, domain):
    print("\n######  bls_verify_multiple  #######")
    print("#############################################")
    print(f"pubkeys: {[pk.hex() for pk in pubkeys]}")
    print(f"message_hashes: {[msg.hex() for msg in message_hashes]}")
    print(f"signature: {signature.hex()}")
    print(f"domain: {domain.hex()}")

    result = bls.verify_multiple(pubkeys=pubkeys, message_hashes=message_hashes,
                               signature=signature, domain=domain)
    print(f"bls verified: {result}")
    return result

  # Verify max number of indices
  let combined_len = len(bit_0_indices) + len(bit_1_indices)
  if not (combined_len <= MAX_VALIDATORS_PER_COMMITTEE):
    notice "indexed attestation: validator index beyond max validators per committee"
    return false

  # Verify index sets are disjoint
  if len(intersection(bit_0_indices.toSet, bit_1_indices.toSet)) != 0:
    notice "indexed attestation: indices set not disjoint"
    return false

  # Verify indices are sorted
  if bit_0_indices != sorted(bit_0_indices, system.cmp):
    notice "indexed attestation: indices 0 not sorted"
    return false

  if bit_1_indices != sorted(bit_1_indices, system.cmp):
    notice "indexed attestation: indices 0 not sorted"
    return false

  # Verify aggregate signature
  let
    pubkeys = @[
      bls_aggregate_pubkeys(mapIt(bit_0_indices, state.validators[it.int].pubkey)),
      bls_aggregate_pubkeys(mapIt(bit_1_indices, state.validators[it.int].pubkey)),
    ]
    msg1 = AttestationDataAndCustodyBit(
        data: indexed_attestation.data, custody_bit: false)
    msg2 = AttestationDataAndCustodyBit(
        data: indexed_attestation.data, custody_bit: true)
    message_hashes = [
      hash_tree_root(msg1),
      hash_tree_root(msg2),
    ]
    domain = get_domain(state, DOMAIN_ATTESTATION, indexed_attestation.data.target.epoch)

  debugEcho "msg1: ", Json.encode(msg1)
  debugEcho "msg2: ", Json.encode(msg2)
  debugEcho " "

  debugEcho "pubkeys: ", pubkeys
  debugEcho "message_hashes: ", message_hashes
  debugEcho "signature: ", indexed_attestation.signature
  debugEcho "domain: ", domain

  result = bls_verify_multiple(
    pubkeys,
    message_hashes,
    indexed_attestation.signature,
    domain,
  )
  if not result:
    notice "indexed attestation: signature verification failure"

[tersec]

0.9.1 removes this function: https://github.com/ethereum/eth2.0-specs/releases/tag/v0.9.1

[tersec]

0.9.1 might have removed the function, the same issue still manifests.

[tersec]

It looks like the last instances of this are fixed by #717