Skip to content
This repository has been archived by the owner on Jun 11, 2024. It is now read-only.

Latest commit

 

History

History
845 lines (646 loc) · 45.2 KB

lip-0058.md

File metadata and controls

845 lines (646 loc) · 45.2 KB
LIP: 0058
Title: Define BFT store and block processing logic
Author: Jan Hackfeld <jan.hackfeld@lightcurve.io>
        Mitsuaki Uchimoto <mitsuaki.uchimoto@lightcurve.io>
Discussions-To: https://research.lisk.com/t/introduce-bft-module/321
Status: Active
Type: Standards Track
Created: 2021-09-07
Updated: 2024-01-04
Requires: 0055, 0056, 0061

Abstract

This LIP defines the BFT store and the block processing logic related to the Lisk-BFT consensus protocol. The BFT store is responsible for maintaining the consensus participants, their BFT weights and all information related to the consensus votes that have been cast as part of the block headers. In this LIP, we specify how this information is serialized and stored as well as updated as part of the block processing.

Copyright

This LIP is licensed under the Creative Commons Zero 1.0 Universal.

Motivation

The Lisk-BFT consensus protocol introduced in LIP 0014 specifies two block properties, maxHeightGenerated (renamed from maxHeightPreviouslyForged) and maxHeightPrevoted, which are validated as part of the block processing. As part of the new state architecture and stricter separation into network domain, consensus domain and application domain, the majority of the block processing now happens in the application domain and is logically separated into separate modules. The consensus-related logic and verification of the block header properties are performed in the consensus domain, however. That is why the consensus participants, their BFT weights, keys and the current state of consensus votes are also maintained as part of the consensus domain. In this LIP, we therefore define the BFT store for this purpose and specify how this information is updated as part of the block processing. Additionally, we define the concept of block slots and the logic for determining which validator is assigned to a specific block slot. Further, we specify how the new block header properties impliesMaxPrevotes, validatorsHash and aggregateCommit are validated as part of the block processing in the consensus domain.

Rationale

The main purpose of the BFT protocol is to compute the following three properties:

  • maxHeightPrevoted: The maximum height of a block for which the weight of prevotes is at least a certain threshold value, see LIP 0056 for details. This value is important for the block verification and fork choice rule.
  • maxHeightPrecommitted: The maximum height of a block for which the weight of precommits is at least a certain threshold value, see LIP 0056 for details. This value is important for knowing up to which height the chain is finalized.
  • maxHeightCertified: The maximum height of a block for which a certificate has been generated and included in the chain, see LIP 0061. This value is important for validating aggregate commits and for the unlock transaction in PoS.

For computing the three values above, the following inputs are required:

  • Prevote threshold: This threshold value is required for correctly updating the property maxHeightPrevoted. This threshold can be computed from the sum of BFT weights of the active validators, see LIP 0056 for details.
  • Precommit threshold: This threshold value is required for correctly updating the property maxHeightPrecommitted, see LIP 0056 for details.
  • Certificate threshold: This threshold value is important for validating aggregate commits included in blocks and then updating the value of maxHeightCertified, see LIP 0061.
  • BFT weights of consensus participants: For computing the prevote and precommit weight of a block, the BFT weight of the active validators at that block height is required.
  • Block headers information: A subset of the properties of the recent block headers in the current chain is required to update the prevote and precommits weights. The reason is that validators cast prevotes and precommits as part of their block header, see LIP 0056 for details.

We call the first four inputs above the BFT parameters. We assume that these BFT parameters are forwarded from the application domain to the consensus domain whenever the setValidatorParams function in the Validators module is called. For a PoS chain, the PoS module would need to call the setValidatorParams function with the correct parameters. Similarly, for a PoA chain, it is the responsibility of the PoA module to provide the correct parameters as input to the setValidatorParams function.

All the input parameters above, except the block headers, are stored in the BFT Parameters substore. The block header information is always available in the processing context within the consensus domain. We use the height at which the parameters are first valid as key. This means that if h1 and h2 are two keys in the BFT Parameters substore with h1 < h2 and there is no key between h1 and h2, then the BFT parameters for the key h1 are valid at heights h1, ..., h2-1. The BFT substore is therefore agnostic of the concept of rounds and the frequency at which these parameters are updated.

The output of the computations is stored in the BFT Votes substore and is updated as part of processing a block. In that store, the current values of maxHeightPrevoted, maxHeightPrecommitted and maxHeightCertified are stored. Additionally, the substore contains the relevant properties of the MAX_LENGTH_BLOCK_BFT_INFOS most recent block headers (if these exist) together with their current prevote weight and precommit weight. Note that the constant MAX_LENGTH_BLOCK_BFT_INFOS is defined in the table at the beginning of the specifications.

As auxiliary information for fast updates of the prevotes and precommits, we additionally store some information regarding the currently active validators, namely the minimum height since when a validator has been active and the largest height for which a validator has already cast a precommit.

Apart from the main responsibility, to correctly compute the three heights mentioned at the beginning, this LIP includes the following additional logic:

  • The logic for computing the validators hash, a hash value authenticating the BLS keys of the currently active validators, their BFT weights and the certificate threshold.
  • Functions that allow to verify the Lisk-BFT related properties in the block header, namely validatorsHash, maxHeightGenerated, maxHeightPrevoted and impliesMaxPrevotes, see also LIP 0055.

Block Slots

In the Lisk protocol, time is divided into intervals of fixed length. These intervals are called block slots and at most one block can be added to the blockchain during each slot. The length of a block slot is a constant called block time. In this LIP we define how to determine which generator is eligible to generate a block in a certain block slot.

Furthermore, the BFT store maintains the generator list, a list of validators that are eligible to generate a block in the given order. Note that a position in the generator list does NOT reflect the position in a round. For example, if a generator list validatorList is provided via the function setBFTParameters, then validatorList[0] does not necessarily represent the first generator of the round. Instead, validatorList[n] does represent the first generator of the round for an integer n with 0 < n < length(validatorList), where n depends on the number of missed block slots in the past. The block slots of a round are then assigned round-robin using [validatorList[n], validatorList[n+1], ..., validatorList[-1], validatorList[0], ..., validatorList[n-1]]. The exact assignment of a generator for a timestamp is defined by the function getGeneratorAtTimestamp.

Specification

Constants

Name Type Value Description
SUBSTORE_PREFIX_BFT_PARAMETERS bytes 0x0000 The substore prefix of the BFT Parameters substore.
SUBSTORE_PREFIX_BFT_VOTES bytes 0x8000 The substore prefix of the BFT Votes substore.
LSK_BFT_BATCH_SIZE uint32 configurable per chain This constant determines the value of MAX_LENGTH_BLOCK_BFT_INFOS and thereby the range of prevotes and precommits. Additionally, it is used in the block synchronization mechanism and fast chain switching mechanism defined in LIP 0014.
MAX_LENGTH_BLOCK_BFT_INFOS uint32 3*LSK_BFT_BATCH_SIZE The maximum length of the array blockBFTInfos in the BFT Votes substore.
BLOCK_TIME uint32 10 (value for the Lisk mainchain) Block time (in seconds) set in the chain configuration.
ADDRESS_LENGTH uint32 20 Length in bytes of an address.
ED25519_PUBLIC_KEY_LENGTH uint32 32 Length in bytes of an Ed25519 public keys.
BLS_PUBLIC_KEY_LENGTH uint32 48 Length in bytes of a BLS public key.
INVALID_BLS_KEY bytes 48 bytes all set to 0 A BLS key used as a placeholder before a valid BLS key is registered, see LIP 0063 for details.

As explained in Section "Comparison to the Lisk-BFT paper" in LIP 0056, the constant LSK_BFT_BATCH_SIZE should never be smaller than the maximum round length of the chain. For a blockchain using the PoS module, it is therefore recommended to use LSK_BFT_BATCH_SIZE = NUMBER_ACTIVE_VALIDATORS + NUMBER_STANDBY_VALIDATORS, where NUMBER_ACTIVE_VALIDATORS and NUMBER_STANDBY_VALIDATORS are constants defined in the PoS module. For a blockchain using the PoA module, a safe choice is LSK_BFT_BATCH_SIZE = MAX_NUM_VALIDATORS, where MAX_NUM_VALIDATORS is a constant defined in the PoA module. If the maximum number of authorities is known to be smaller, it is recommended to use a smaller value for LSK_BFT_BATCH_SIZE for improved efficiency.

Notation and Functions

Name Description
uint32be(x) For an integer x with 0 <= x < 2^32, the function returns 4 bytes representing the big endian unsigned integer serialization of x.
// This symbol represents integer division.

BFT Store

The BFT store is organized in the two substores described below. Note that the BFT store is not part of the state store of the application domain and therefore does not impact the state root. Each substore of the BFT store is a simple key-value store similar to the substores in the application domain.

BFT Parameters

Substore Prefix, Store Key, and Store Value
  • The substore prefix is SUBSTORE_PREFIX_BFT_PARAMETERS.
  • Each store key is uint32be(h) for a height h.
  • Each store value is the serialization of an object following the JSON schema bftParametersSchema defined below.
  • Notation: We let bftParameters(height) denote the object stored in the BFT store for the substore prefix SUBSTORE_PREFIX_BFT_PARAMETERS and store key uint32be(height), deserialized using the bftParametersSchema schema.
JSON Schema
bftParametersSchema = {
    "type": "object",
    "required": [
        "prevoteThreshold",
        "precommitThreshold",
        "certificateThreshold",
        "validators",
        "validatorsHash"
    ],
    "properties": {
        "prevoteThreshold": {
            "dataType": "uint64",
            "fieldNumber": 1
        },
        "precommitThreshold": {
            "dataType": "uint64",
            "fieldNumber": 2
        },
        "certificateThreshold": {
            "dataType": "uint64",
            "fieldNumber": 3
        },
        "validators": {
            "type": "array",
            "fieldNumber": 4,
            "items": {
                ...validatorSchema
            }
        },
        "validatorsHash": {
            "dataType": "bytes",
            "fieldNumber": 5
        }
    }
}


validatorSchema = {
    "type": "object",
    "required": ["address", "bftWeight", "generatorKey", "blsKey"],
    "properties": {
        "address": {
            "dataType": "bytes",
            "length": ADDRESS_LENGTH,
            "fieldNumber": 1
        },
        "bftWeight": {
            "dataType": "uint64",
            "fieldNumber": 2
        },
        "generatorKey": {
            "dataType": "bytes",
            "length": ED25519_PUBLIC_KEY_LENGTH,
            "fieldNumber": 3
        },
        "blsKey": {
            "dataType": "bytes",
            "length": BLS_PUBLIC_KEY_LENGTH,
            "fieldNumber": 4
        }
    }
}
Properties

All properties below are valid starting from the height given as key:

  • prevoteThreshold: This property stores the prevote threshold. For casting a precommit for a block, the sum of BFT weights of all validators casting a prevote for this block has to be at least the prevote threshold. If aggregateBFTWeight is the sum of BFT weights of all validators stored, then the property value must be ((2 * aggregateBFTWeight(h)) // 3) + 1.
  • precommitThreshold: This property stores the precommit threshold. For considering a block final, the sum of BFT weights of all validators casting a precommit for this block has to be at least the precommit threshold. If aggregateBFTWeight is the sum of BFT weights of all validators stored, then the value of this property must satisfy (aggregateBFTWeight // 3) + 1 <= precommitThreshold <= aggregateBFTWeight.
  • certificateThreshold: This property stores the certificate threshold. For considering a certificate or aggregate commit for a valid block, the sum of BFT weights of all validators signing the certificate has to be at least the certificate threshold. If aggregateBFTWeight is the sum of BFT weights of all validators stored, then the value of this property must satisfy (aggregateBFTWeight // 3) + 1 <= certificateThreshold <= aggregateBFTWeight.
  • validators: Each element in the array validators corresponds to a validator and stores its address, generator key, BLS key and BFT weight property. The order in the array determines the block generation order.
  • validatorsHash: A 32-byte value authenticating the BLS keys and BFT weights of the validators and the certificate threshold of the same store entry.

BFT Votes

Substore Prefix, Store Key, and Store Value
  • The substore prefix is SUBSTORE_PREFIX_BFT_VOTES.
  • The store key is empty bytes.
  • The store value is the serialization of an object following the JSON schema bftVotesSchema defined below.
  • Notation: We let bftVotes denote the object stored in the BFT store for the substore prefix SUBSTORE_PREFIX_BFT_VOTES and store key equal to empty bytes, deserialized using the bftVotesSchema schema.
JSON Schema
bftVotesSchema = {
    "type": "object",
    "required": [
        "maxHeightPrevoted",
        "maxHeightPrecommitted",
        "maxHeightCertified",
        "blockBFTInfos",
        "activeValidatorsVoteInfo"
    ],
    "properties": {
        "maxHeightPrevoted": {
            "dataType": "uint32",
            "fieldNumber": 1
        },
        "maxHeightPrecommitted": {
            "dataType": "uint32",
            "fieldNumber": 2
        },
        "maxHeightCertified": {
            "dataType": "uint32",
            "fieldNumber": 3
        },
        "blockBFTInfos": {
            "type": "array",
            "fieldNumber": 4,
            "items": {
                "type": "object",
                "required": [
                    "height",
                    "generatorAddress",
                    "maxHeightGenerated",
                    "maxHeightPrevoted",
                    "prevoteWeight",
                    "precommitWeight"
                ],
                "properties": {
                    "height": {
                        "dataType": "uint32",
                        "fieldNumber": 1
                    },
                    "generatorAddress": {
                        "dataType": "bytes",
                        "fieldNumber": 2
                    },
                    "maxHeightGenerated": {
                        "dataType": "uint32",
                        "fieldNumber": 3
                    },
                    "maxHeightPrevoted": {
                        "dataType": "uint32",
                        "fieldNumber": 4
                    },
                    "prevoteWeight": {
                        "dataType": "uint64",
                        "fieldNumber": 5
                    },
                    "precommitWeight": {
                        "dataType": "uint64",
                        "fieldNumber": 6
                    }
                }
            }
        },
        "activeValidatorsVoteInfo": {
            "type": "array",
            "fieldNumber": 5,
            "items": {
                "type": "object",
                "required": [
                    "address",
                    "minActiveHeight",
                    "largestHeightPrecommit"
                ],
                "properties": {
                    "address": {
                        "dataType": "bytes",
                        "fieldNumber": 1
                    },
                    "minActiveHeight": {
                        "dataType": "uint32",
                        "fieldNumber": 2
                    },
                    "largestHeightPrecommit": {
                        "dataType": "uint32",
                        "fieldNumber": 3
                    }
                }
            }
        }
    }
}
Properties
  • maxHeightPrevoted: This property stores the largest height h such that the aggregate BFT weight of validators prevoting for the block at height h is at least the prevote threshold.
  • maxHeightPrecommitted: This property stores the largest height h such that the aggregate BFT weight of validators precommitting for the block at height h is at least the precommit threshold.
  • maxHeightCertified: This property stores the largest height for which the current chain contains an aggregate commit and therefore a certificate.
  • blockBFTInfos: This property stores an array of length at most MAX_LENGTH_BLOCK_BFT_INFOS. Each element references a block in the current chain and contains all block properties relevant for the Lisk-BFT consensus protocol. If currentHeight is the current height of the chain, genesisHeight is the height of the genesis block, then blockBFTInfos contains on object for each block at heights {currentHeight, currentHeight-1, …, max(genesisHeight + 1, currentHeight - MAX_LENGTH_BLOCK_BFT_INFOS+1)} in descending order of height. In particular, it holds that blockBFTInfos[0].height == currentHeight.
    • prevoteWeight: This property stores the aggregate weight of prevotes for the block, considering all prevotes implied by blocks in the current chain.
    • precommitWeight: This property stores the aggregate weight of precommits for the block, considering all precommits implied by blocks in the current chain.
  • activeValidators: This property stores an array of objects, one for each currently active validator. The array is sorted lexicographically by the address property of each object. Every object contains the following three properties:
    • address: The 20-byte address of the validator.
    • minActiveHeight: The height from which the validator has been continuously active.
    • largestHeightPrecommit: The largest height for which a block generated by the validator implied a precommit.

Internal Functions

For convenience of the specifications below, we define the following internal functions.

areDistinctHeadersContradicting

This function allows to check whether two distinct block headers are contradicting and, in particular, imply a violation of the Lisk-BFT protocol.

Parameters
  • blockHeaderInfo1: An object corresponding to a block header with the properties height, maxHeightGenerated, maxHeightPrevoted and generatorAddress.
  • blockHeaderInfo2: An object corresponding to a block header with the properties height, maxHeightGenerated, maxHeightPrevoted and generatorAddress. This object must correspond to a different block header than blockHeaderInfo1.
Returns

The function returns True if the two objects provided as input correspond to contradicting block headers and False otherwise.

Execution
def areDistinctHeadersContradicting(blockHeaderInfo1, blockHeaderInfo2):
    # Order the two block headers such that b1 must be forged first.
    b1 = blockHeaderInfo1
    b2 = blockHeaderInfo2
    if b1.maxHeightGenerated > b2.maxHeightGenerated
       or (b1.maxHeightGenerated == b2.maxHeightGenerated
           and b1.maxHeightPrevoted > b2.maxHeightPrevoted)
       or (b1.maxHeightGenerated == b2.maxHeightGenerated
           and b1.maxHeightPrevoted == b2.maxHeightPrevoted
           and b1.height > b2.height):
        b1 = blockHeaderInfo2
        b2 = blockHeaderInfo1

    # The order of cases is essential here.
    if b1.generatorAddress != b2.generatorAddress:
        # Blocks by different validators are never contradicting.
        return False
    elif b1.maxHeightPrevoted == b2.maxHeightPrevoted and b1.height >= b2.height:
        # Violation of the fork choice rule as validator moved to different chain
        # without strictly larger maxHeightPrevoted or larger height as justification.
        # This in particular happens if a validator is double forging.
        return True
    elif b1.height > b2.maxHeightGenerated:
        # Violates disjointness condition.
        return True
    elif b1.maxHeightPrevoted > b2.maxHeightPrevoted:
        # Violates that validator chooses branch with largest maxHeightPrevoted.
        return True
    else:
  	    # No contradiction between block headers.
  	    return False

Note that the function above corresponds to the function checkHeadersContradicting defined in LIP 0014, except for not checking whether the two objects blockHeaderInfo1 and blockHeaderInfo2 correspond to the same block. Additionally, the block header property names are updated according to LIP 0055.

computeValidatorsHashInternal

The following function computes the validators hash value from the provided input parameters. The validators hash is a 32-byte value authenticating the BLS keys and BFT weights of the validators and the certificate threshold.

Parameters
  • validators: An array of objects, each with a property blsKey of type bytes and a property bftWeight, which is an unsigned 64-bit integer. The elements in the array must be sorted lexicographically by the blsKey property.
  • certificateThreshold: An unsigned 64-bit integer.
Returns

The value of the validators hash corresponding to the validator information and the certificate threshold given as input.

Execution

We define JSON schema for validator's BLS key and BFT weight:

blsKeyAndBftWeightSchema = {
    "type": "object",
    "required": ["blsKey", "bftWeight"],
    "properties": {
        "blsKey": {
            "dataType": "bytes",
            "length": BLS_PUBLIC_KEY_LENGTH,
            "fieldNumber": 1
        },
        "bftWeight": {
            "dataType": "uint64",
            "fieldNumber": 2
        }
    }
}

We then use the following JSON schema for the computation of the validators hash.

validatorsHashInputSchema = {
    "type": "object",
    "required": ["validators", "certificateThreshold"],
    "properties": {
        "validators": {
            "type": "array",
            "minItems": 1,
            "maxItems": MAX_NUM_VALIDATORS,
            "fieldNumber": 1,
            "items": { ...blsKeyAndBftWeightSchema }
        },
        "certificateThreshold": {
            "dataType": "uint64",
            "fieldNumber": 2
        }
    }
}

The following function uses the schema above to compute the validators hash from the input parameters.

def computeValidatorsHashInternal(validators, certificateThreshold):
    inputObject = object following validatorsHashInputSchema
    inputObject.validators = validators
    inputObject.certificateThreshold = certificateThreshold
    input = serialization of inputObject according to LIP 0027
    return SHA-256(input)

getBFTParametersInternal

This function is a convenience function for obtaining the BFT parameters at a given height.

Parameters
  • h: Height for which to obtain the BFT parameters. Note that for h <= bftVotes.maxHeightCertified the function may fail as among all key-value pairs in the BFT Parameters substore with key less or equal to bftVotes.maxHeightCertified+1 only the one with largest key is kept and all others are pruned.
Returns

The BFT parameters valid at the height h.

Execution
def getBFTParametersInternal(h):
    for key, value in BFT Parameters substore ordered
        decreasing by key:
        if key <= h:
            return deserialized value
    # In this case no BFT parameters are stored for the height h.
    raise Exception("No BFT parameters stored for given height.")

getBlockBFTProperties

This function creates a blockBFTInfo object with a subset of the block properties that are required for the BFT store.

Parameters
  • blockHeader: A block header object.
Returns

Object following the schema of the objects in the array bftVotes.blockBFTInfos.

Execution
def getBlockBFTProperties(blockHeader):
    blockBFTInfo = object following schema of objects in bftVotes.blockBFTInfos
    blockBFTInfo.generatorAddress = blockHeader.generatorAddress
    blockBFTInfo.height = blockHeader.height
    blockBFTInfo.maxHeightGenerated = blockHeader.maxHeightGenerated
    blockBFTInfo.maxHeightPrevoted = blockHeader.maxHeightPrevoted
    blockBFTInfo.prevoteWeight = 0
    blockBFTInfo.precommitWeight = 0
    return blockBFTInfo

getCurrentHeight

The function returns the height of the block at the current tip of the chain.

def getCurrentHeight():
    if length(bftVotes.blockBFTInfos) > 0:
        return bftVotes.blockBFTInfos[0].height
    else:
        # Only directly after processing the genesis block we have length(bftVotes.blockBFTInfos) == 0. 
        # In that case, bftVotes.maxHeightPrevoted is equal to the genesis height.
        return bftVotes.maxHeightPrevoted

setBFTParameters

This function allows to set the thresholds, validators and associated BFT weights to be used from the next height onward and updates the BFT store accordingly. The function is called in the after application processing stage of the genesis block processing and general block processing as defined below.

Parameters
  • precommitThreshold: The precommit threshold value to be used from the next height onward. The value must be a 64-bit unsigned integer.
  • certificateThreshold: The certificate threshold value to be used from the next height onward. The value must be a 64-bit unsigned integer.
  • validatorList: The validators, their associated BFT weight, BLS key and generator key to be used from the next height onward. The value must be an array of objects with an address property containing the 20-byte address of the validator, a bftWeight property containing the BFT weight of the validator as 64-bit unsigned positive integer, a generatorKey property of type bytes and a blsKey property of type bytes. Note that this function fails if the number of provided validators is more than LSK_BFT_BATCH_SIZE.
Execution
def setBFTParameters(precommitThreshold, certificateThreshold, validatorList):
    if length(validatorList) > LSK_BFT_BATCH_SIZE:
        raise Exception("Given list of validators is larger than the maximum allowed value.")
    if len(validatorList) != len(set([validator.address for validator in validatorList])):
        raise Exception("Provided validator addresses are not unique.")
    validBlsKeys = [validator.blsKey for validator in validatorList if validator.blsKey != INVALID_BLS_KEY]
    if len(validBlsKeys) != len(set(validBlsKeys)):
        raise Exception("Provided valid validator BLS keys are not unique.")

    aggregateBFTWeight = 0
    for validator in validatorList:
        aggregateBFTWeight += validator.bftWeight
    if (aggregateBFTWeight // 3)+1 > precommitThreshold or precommitThreshold > aggregateBFTWeight:
        raise Exception("Given precommit threshold is outside the allowed range.")
    if (aggregateBFTWeight // 3)+1 > certificateThreshold or certificateThreshold > aggregateBFTWeight:
        raise Exception("Given certificate threshold is outside the allowed range.")
    bftParams = object following bftParametersSchema
    bftParams.prevoteThreshold = ((2 * aggregateBFTWeight) // 3) + 1
    bftParams.precommitThreshold = precommitThreshold
    bftParams.certificateThreshold = certificateThreshold
    bftParams.validators = validatorList

    # Compute the validators hash.
    activeValidators = []
    for validator in validatorList:
        if validator.bftWeight > 0:
            activeValidator = object with property bftWeight and blsKey
            activeValidator.bftWeight = validator.bftWeight
            activeValidator.blsKey =  validator.blsKey
            add activeValidator to activeValidators
    sort elements in activeValidators lexicographically by blsKey property
    bftParams.validatorsHash = computeValidatorsHashInternal(activeValidators, certificateThreshold)

    # Set the BFT parameters for the correct next height.
    nextHeight = getCurrentHeight() + 1
    bftParameters(nextHeight) = bftParams

    # Update bftVotes.updateActiveValidatorsVoteInfo.
    newActiveValidatorsVoteInfo = []
    for each validator in validatorList:
        if validator.address appears in bftVotes.activeValidatorsVoteInfo:
            validatorVoteInfo = object in bftVotes.activeValidatorsVoteInfo
                                with address equal to validator.address
        else:
            validatorVoteInfo = object following schema of elements
                                in bftVotes.activeValidatorsVoteInfo
            validatorVoteInfo.address = validator.address
            validatorVoteInfo.minHeightActive = nextHeight
            validatorVoteInfo.largestHeightPrecommit = nextHeight-1
        add validatorVoteInfo to newActiveValidatorsVoteInfo
    sort newActiveValidatorsVoteInfo lexicographically by address
    bftVotes.activeValidatorsVoteInfo = newActiveValidatorsVoteInfo

Public Functions

areHeadersContradicting

This function checks whether the block headers objects given as input are contradicting and, in particular, imply a violation of the Lisk-BFT protocol.

Parameters
  • blockHeader1: A block header object.
  • blockHeader2: A block header object.
Returns

The function returns True if the two block headers provided as input are contradicting and False otherwise.

Execution
def areHeadersContradicting(blockHeader1, blockHeader2):
    if  blockHeader1.blockID == blockHeader2.blockID:
        # No contradiction, as block headers are the same.
        return False
    return areDistinctHeadersContradicting(blockHeader1, blockHeader2)

computeValidatorsHash

For the function description, parameters and return value see the corresponding internal function computeValidatorsHashInternal.

Execution
def computeValidatorsHash(validators, certificateThreshold):
    return computeValidatorsHashInternal(validators, certificateThreshold)

existBFTParameters

This function allows to check whether for a certain height there is an entry in the BFT Parameters substore. This function is needed for validating aggregate commits in blocks and checking that there is always an aggregate commit authenticating the BFT weights and certificate threshold for every BFT Parameters substore entry.

Parameters
  • h: Height for which to check whether there is an entry in the BFT Parameters substore.
Returns

The function returns True if and only if there is an entry in the BFT Parameters store with key h.

Execution
def existBFTParameters(h):
    if exists entry in BFT Parameters store with key uint32be(h):
        return True
    return False

impliesMaximalPrevotes

The function returns whether the block header given as input implies the maximal number of prevotes which shows that the block generator is constructively contributing in the Lisk-BFT protocol. This function needs to be called before the execution of the block with the block header blockHeader given as input, as it requires blockHeader.height to be one larger than the maximum height stored in bftVotes.blockBFTInfos.

Parameters
  • blockHeader: A block header that is being verified and supposed to be added to the current tip of the chain.
Returns

The function returns True if the block header implies the maximal number of prevotes and False otherwise.

Execution
def impliesMaximalPrevotes(blockHeader):
    # This condition is only satisfied for the first block after the genesis block.
    if len(bftVotes.blockBFTInfos) == 0:
        if blockHeader.height > blockHeader.maxHeightGenerated:
            return True
        else:
            return False
    heightCurrentTip = bftVotes.blockBFTInfos[0].height
    if blockHeader.height != heightCurrentTip + 1:
        raise Exception("Given block header must have height one larger than the height of the current tip.")
    previousHeight = blockHeader.maxHeightGenerated

    # If the condition below is satisfied, the block does not imply any prevotes.
    if previousHeight >= blockHeader.height:
        return False

    # If the condition below is satisfied, there is no block information stored
    # for height previousHeight and blockHeader implies the maximal number of prevotes.
    offset = heightCurrentTip-previousHeight
    if offset >= length(bftVotes.blockBFTInfos):
        return True

    # If the condition below is satisfied, the block at height previousHeight is
    # generated by a different validator and and b does not imply the maximal number of prevotes.
    if bftVotes.blockBFTInfos[offset].generatorAddress != blockHeader.generatorAddress:
        return False
    return True

isHeaderContradictingChain

This function checks whether the block header provided as input contradicts a recent block in the current chain, i.e., one of the MAX_LENGTH_BLOCK_BFT_INFOS most recent blocks in the current chain contradicts the block header that is supposed to be added. This check should be done before the block given as input is processed and the respective properties are added to bftVotes.blockBFTInfos.

Parameters
  • blockHeader: The block header of a block that is supposed to be added to the current chain.
Returns

The function returns True if the block header blockHeader provided as input contradicts the current chain and should be rejected.

Execution
def isHeaderContradictingChain(blockHeader):
    for blockBFTInfo in bftVotes.blockBFTInfos:
        if blockBFTInfo.generatorAddress == blockHeader.generatorAddress:
            return areDistinctHeadersContradicting(blockBFTInfo, blockHeader)
    return False

Note that the function above is the update of the function checkHeaderContradictingChain defined in LIP 0014 to the new store structure.

getBFTHeights

The function returns the current values of the property maxHeightPrevoted, maxHeightPrecommitted and maxHeightCertified in the BFT Votes substore.

Returns
  • The value of the property maxHeightPrevoted as unsigned 32-bit integer.
  • The value of the property maxHeightPrecommitted as unsigned 32-bit integer.
  • The value of the property maxHeightCertified as unsigned 32-bit integer.
Execution
def getBFTHeights():
    return {
        "maxHeightPrevoted": bftVotes.maxHeightPrevoted,
        "maxHeightPrecommitted": bftVotes.maxHeightPrecommitted,
        "maxHeightCertified": bftVotes.maxHeightCertified
    }

getBFTParameters

This function allows to obtain the BFT parameters valid at the height given as input.

Parameters
  • h: Height for which to obtain the BFT parameters. Note that for h <= bftVotes.maxHeightCertified the function may fail as among all key-value pairs in the BFT Parameters substore with key less or equal to bftVotes.maxHeightCertified+1 only the one with largest key is kept and all others are pruned.
Returns

The BFT parameters valid at the height h.

Execution
def getBFTParameters(h):
    return getBFTParametersInternal(h)

getBFTParametersActiveValidators

This function has the same functionality as getBFTParameters with the only difference that it provides information only for validators with positive BFT weight. This is particularly useful for certificates used for interoperability.

Execution
def getBFTParametersActiveValidators(h):
    bftParams = getBFTParameters(h)
    bftParams.validators = [validator for validator in bftParams.validators if validator.bftWeight > 0]
    return bftParams

getGeneratorAtTimestamp

This function returns the address of the generator active at the timestamp timestamp for the block at height currentHeight + 1 where timestamp and currentHeight are given as input. Notice that if the input timestamp corresponds to a time slot before or after the current round, this function may not return the correct generator address.

def getGeneratorAtTimestamp(timestamp, currentHeight):
    nextHeight = currentHeight + 1
    currentValidatorList = getBFTParametersInternal(nextHeight).validators
    slotIndex = getSlotNumber(timestamp) % len(currentValidatorList)
    return currentValidatorList[slotIndex]

getNextHeightBFTParameters

The function allows to obtain the next larger key in the BFT Parameters substore given a height as input. This function is needed for validating aggregate commits in blocks and checking that there is always an aggregate commit authenticating the BFT weights and certificate threshold for every BFT Parameters substore entry.

Parameters
  • h: Height value which serves as lower bound for iteration over the keys in the BFT Parameters substore.
Returns

For a height h as input, the function returns the smallest height h1 > h with an entry in the BFT Parameters substore with key h1, if such height exists. Otherwise, it fails.

getSlotNumber

This function returns the slot number corresponding to the input timestamp. Note that slots are counted from the UNIX epoch onwards and are independent of the timestamp of the genesis block.

def getSlotNumber(timestamp):
    return timestamp // BLOCK_TIME

Genesis Block Processing

The following two steps are executed as part of the genesis block processing, see LIP 0060 for details.

Before Application Processing

In the before application processing stage of a genesis block b, the BFT store is initialized as follows:

  • The BFT Parameters substore is empty.
  • The BFT Votes substore is initialized as follows:
    • bftVotes.maxHeightPrevoted = b.header.height,
    • bftVotes.maxHeightPrecommitted = b.header.height,
    • bftVotes.maxHeightCertified = b.header.height,
    • bftVotes.blockBFTInfos is an empty array,
    • bftVotes.activeValidatorsVoteInfo is an empty array.

After Application Processing

The function setBFTParameters is called with the BFT parameters forwarded from the application domain as input. If the call of setBFTParameters results in an exception as the parameters are invalid, the genesis block is invalid and discarded. Note that as part of the block processing within the application domain, the function setValidatorParams of the Validators module has to be called (by the PoA module or PoS module) as the blockchain cannot continue after the genesis block without BFT parameters.

Block Processing

The following steps are executed as part of the (non-genesis) block processing, see LIP 0055 for details.

Before Application Processing

In the before application processing stage of a block b, the BFT store is updated according to the logic below. These steps should be executed only after the "before application processing" steps defined in LIP 0055 are executed.

  1. The object getBlockBFTProperties(b.header) is added to the beginning of the array bftVotes.blockBFTInfos.
  2. If bftVotes.blockBFTInfos[MAX_LENGTH_BLOCK_BFT_INFOS] exists, then the corresponding value is removed from the array.
  3. The function updatePrevotesPrecommits from LIP 0056 is executed to update the prevote and precommit weights.
  4. The value of bftVotes.maxHeightPrevoted is updated by calling the function updateMaxHeightPrevoted specified in LIP 0056.
  5. The value of bftVotes.maxHeightPrecommitted is updated by calling the function updateMaxHeightPrecommitted specified in LIP 0056.
  6. Let m be the aggregate commit included in block b. If m.aggregationBits is empty bytes and m.signature is empty bytes, do nothing. Otherwise, set bftVotes.maxHeightCertified to m.height.
  7. Let h be the largest integer such that h <= min(getMaxRemovalHeight(), bftVotes.blockBFTInfos[-1].height) and there is an entry in the BFT Parameters store with key h. Then remove any key-value pair from BFT Parameters with a key strictly smaller than h. Note that the function getMaxRemovalHeight() is defined in LIP 0061.

After Application Processing

In the after application processing stage of a block b,the BFT store is updated according to the logic below:

  • Whenever new BFT parameters are forwarded from the application domain to the consensus domain (this happens whenever the function setValidatorParams of the Validators module is called by the PoA module or PoS module), the function setBFTParameters is called in this stage with the respective parameters as input to update the BFT parameters store. If the call of setBFTParameters results in an exception as the parameters are invalid, the block is invalid and discarded.

Block Creation

The following steps are executed as part of the block generation, see LIP 0055 for details. The logic for the "Before application processing" and "After application processing" stages is the same as defined for the block processing above.

Header Initialization

During the header initialization phase, the properties maxHeightPrevoted, maxHeightGenerated, impliesMaxPrevotes and aggregateCommit in the block header have to be set as follows:

  • The value of maxHeightPrevoted is set during the header initialization phase by calling getBFTHeights().maxHeightPrevoted. This ensures that this happens before executing any logic defined in the section "Block Processing" above.
  • The value of maxHeightGenerated must come from outside the consensus domain layer and is also set during the header initialization phase. As defined in LIP 0014, this value must be the maximum height at which the respective validator previously has generated a block, which is stored as private information for every validator.
  • The value of impliesMaxPrevotes can be obtained by calling impliesMaximalPrevotes(blockHeader) where blockHeader is the block header with the properties maxHeightPrevoted and maxHeightGenerated already initialized.
  • The value of aggregateCommit is obtained by calling the function selectAggregateCommit defined in LIP 0061.

Header Finalization

During the header finalization phase, the property validatorsHash in the block header has to be set as follows:

  • The value of validatorsHash is obtained by calling getBFTParameters().validatorsHash.

Backwards Compatibility

This LIP changes how a block is processed and therefore introduces a hardfork.

Reference Implementation

Introduce BFT module