LIP 0053: Fix verifyValidatorsUpdate function

[gkoumout]

Motivation

In CCU params there is the field activeValidatorsUpdate which is an object containing 3 items:

• blsKeysUpdate: An array containing the BLS keys of the new active validators (ordered in lexicographic order)
• bftWeightsUpdate: An array containing all new BFT weights. This includes the BFT weights of the new validators and the BFT weights of old validators whose weight changed since the last certicificate. If a validator is excluded from the active validator set, then assume their new bft weight is 0.
• bftWeightsUpdateBitmap: This bitmap encodes the correspondence between the BFT weights contained in the bftWeightsUpdate array and the actual validator (identified by their BLS keys) that each weight corresponds to.

The correspondence works as follows (specified in getActiveValidatorsUpdate function). Let

• newBLSKeys be the keys of the new validators (i.e., the keys of the blsKeysUpdate array).
• oldBLSKeys be the keys of the validators known in the chain until the last certificate.
• allBLSKeys = newBLSKeys U oldBLSKeys, i.e., all BLS keys of previous and current validators, sorted in lexicographic order.

Then we have that the bftWeightsUpdateBitmap contains |allBLSKeys| bits where the ith bit (from right to left) corresponds to the ith entry of allBLSKeys; if the ith bit is set to 1 it means that the BFT weight of validator with BLS key allBLSKeys[i] is included in the BFT weights update array. Therefore the number of 1s in the bitmap should be equal to the size of bftWeightsUpdate array.

Validation. Two of the checks performed in verifyValidatorsUpdate function (part of CCU transaction verification) is that for all new validators:

1. The corresponding bitmap value is always set to 1
2. The bft weight is positive.

Current Specifications

In the current specifications, the 2 aforementioned checks are performed in the following loop

    # All new keys must have a positive BFT weight.
    for idx, blsKey in enumerate(allBLSKeys):
        if blsKey in blsKeysUpdate:
            # Get digit of bitmap at index idx (starting from the right).
            digit = (int.from_bytes(bftWeightsUpdateBitmap, 'big') >> idx) & 1
            if digit != 1:
                raise Exception("New validators must have a BFT weight update.")
            if bftWeightsUpdate[idx] == 0:
                raise Exception("New validators must have a positive BFT weight.")

Check (1) is done correctly. Check (2) is not. The reason is that we check bftWeightsUpdate[idx], where idx is the index of blsKey in allBLSKeys array. So we are mixing up indices of two different arrays. Note that in principle the size of allKeys might be quite larger than the size of bftWeightUpdate, in which case even checking bftWeightsUpdate[idx] would give an error.

Proposed Specifications

We should be able to answer the following question: Which indices of bftWeightsUpdate array correspond to newBLSkeys? Then for each of those indices i, we should check that bftWeightsUpdate[i] > 0 .

Here is a proposed way to do that (assuming that check (1) has been already performed successfully):

newValitatorsIndices = []                 // indices of bftWeightsUpdate array corresponding to new validators
index = 0
for idx,  blsKey in enumerate(allBLSKeys):
    # Get digit of bitmap at index idx (starting from the right).
    digit = (int.from_bytes(bftWeightsUpdateBitmap, 'big') >> idx) & 1
    if digit == 1:
        if blsKey in newBLSKeys:
            newValitatorsIndices.append(index)
        index+=1

for i in newValidatorsIndices:
    if bftWeightsUpdate[i] == 0:
        raise Exception('New validators must have a positive BFT weight.')

It would be also possible to merge this check with check (1) (but it would make it a bit harder to parse), as follows:

newValitatorsIndices = []                 // indices of bftWeightsUpdate array corresponding to new validators
index = 0
for idx,  blsKey in enumerate(allBLSKeys):
    # Get digit of bitmap at index idx (starting from the right).
    digit = (int.from_bytes(bftWeightsUpdateBitmap, 'big') >> idx) & 1
    if blsKey in newBLSKeys:
        if digit != 1:
            raise Exception("New validators must have a BFT weight update.")
        newValitatorsIndices.append(index)
    if digit == 1:
        index+=1

for i in newValidatorsIndices:
    if bftWeightsUpdate[i] == 0:
        raise Exception('New validators must have a positive BFT weight.')

Affected LIPs