Add weights to Lisk-BFT consensus protocol

Consensus
1

Hello everyone,

I want to propose a first LIP for the roadmap objective “Update Lisk-BFT for interoperability”. The LIP generalizes the Lisk-BFT consensus protocol specified in LIP 0014 by introducing finality weights, which are weights with which validators contribute to finalizing blocks.

I’m looking forward to your feedback.

Here is the complete LIP draft:

LIP: <LIP number>
Title: Add weights to Lisk-BFT consensus protocol
Author: Jan Hackfeld <jan.hackfeld@lightcurve.io>
Type: Standards Track
Created: <YYYY-MM-DD>
Updated: <YYYY-MM-DD>
Requires: Introduce the BFT module LIP

Abstract

This LIP defines how to generalize the Lisk-BFT consensus protocol to allow for different BFT weights of the participating validators, which may also change over time. The BFT weight is the weight attributed to the prevotes and precommits cast by a validator and therefore determines to what extent the validator contributes to finalizing blocks. We specify this generalized computation of consensus votes and associated properties using the new state structure defined in the BFT module.

Copyright

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

Motivation

The Lisk-BFT consensus protocol introduced in LIP 0014 was specified for the Lisk mainchain and sidechains that use Delegated Proof-of-Stake with fixed configuration parameters that only change in rare cases as part of a hard fork. In these blockchains, there is a fixed number of active delegates, i.e., those delegates participating in finalizing blocks, and all of them have equal weight. One exception to that is the bootstrap period introduced as part of the new genesis block format in LIP 0034. During the bootstrap period none of the bootstrap delegates contributes to finalizing blocks, so that blocks can only be finalized after the bootstrap period is over.

For more flexibility and to also support other validator selection mechanisms, we want to allow for different BFT weights of the active validators, i.e., different weights attributed to the prevotes and precommits cast by a validator. These weights and the threshold for finalizing a block should also not be constant, but should be allowed to change over time. This is, in particular, required in conjunction with the Proof-of-Authority validator selection mechanism introduced in the [PoA][module] where validators can be added and removed or their weights changed with a simple transaction and without a hard fork.

Additionally, as part of the new state architecture, the consensus votes are stored as part of the state as described in the BFT module LIP. In this LIP, we therefore describe how the consensus votes and associated properties need to be updated as part of the block processing, using the notation and state structure introduced in the BFT module LIP.

Rationale

Terminology

In this section, we briefly define the main terms used throughout this LIP. For more background information see the Lisk-BFT paper.

  • active validators: The active validators at height h are all validators that can contribute to finalizing a block at that height by casting consensus votes for a block at height h.
  • BFT weight: The weight attributed to the prevotes and precommits cast by a validator. We further use the notation aggregateBFTWeight(h) to denote the sum of BFT weights of all active validators at height h.
  • prevote: A consensus vote that is implied by the information in the block proposed by a validator. Validators are only allowed to prevote for one block at every height.
  • precommit: A consensus vote that is implied by the information in the blocks proposed by a validator. A precommit requires a previous prevote for a block.
  • 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. We use the notation prevoteThreshold(h) to denote the prevote threshold valid for the block at height h.
  • 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. We use the notation precommitThreshold(h) to denote the prevote threshold valid for the block at height h.

Changes Compared to LIP 0014

The general goal of the update of the Lisk-BFT consensus protocol specified in this LIP is to allow more flexibility while keeping as much of the specification in LIP 0014 as possible. Therefore, many part of the Lisk-BFT protocol, such as the fork choice rule, the fast chain switching mechanism or the block synchronization mechanism stay unchanged.

The generalization of the Lisk-BFT consensus protocol to allow for different BFT weights of the participating validators implies the following changes:

  • Instead of a BFT weight of 1, the BFT weight of a validator can be any uint64 value.
  • Instead of having a fixed BFT weight, the BFT weight of validators can change over time. The BFT module LIP defines how the BFT weights can be changed. For instance, the DPoS module or PoA module can call the BFT module in case of validator changes and adjust the BFT weights accordingly.
  • The prevote threshold is always computed from the sum of BFT weights of all validators. Therefore, the prevote threshold can change if the sum of BFT weights changes.
  • Instead of having a fixed precommit threshold, the precommit threshold can change within a range depending on the sum of BFT weights of all validators. The BFT module LIP defines how the precommit threshold can be changed.

Additionally, this LIP uses a different notation and assumes a different way of storing consensus-related information due to the new state structure introduced in the BFT module LIP. In particular, we introduce the following changes to the BFT-related properties:

  • The property chainMaxHeightPrevoted is renamed to maxHeightPrevoted.
  • The property chainMaxHeightFinalized is renamed to maxHeightFinalized.
  • The property maxHeightPreviouslyForged is renamed to maxHeightGenerated.
  • As part of the consensus vote computations, we also update a new property maxHeightPrecommitted which is introduced in the BFT module LIP.
    The property denotes the largest height h such that the BFT weight of precommits for the block at height h in the current chain is above or equal to the precommit threshold. Note that this value is completely determined by the current tip of the chain and can decrease if blocks are reverted. Therefore, the property can also be stored as part of the state. This is in contrast to the value of maxHeightFinalized, which is the maximum value of maxHeightPrecommitted a node has computed for any block at its tip so far. It is important to observe that two nodes may have the same tip of the chain and thus the same current value of maxHeightPrecommitted, but different values of maxHeightFinalized due to a different history of reverted blocks. The variable maxHeightPrecommitted is introduced as it will be important for certificate generation.

Below you find a list of the main functions in LIP 0014 that define the computation of prevotes, precommits and properties maxHeightPrevoted and maxHeightFinalized and the corresponding function in this LIP.

  • The function getHeightNotPrevoted in LIP 0014 is the same in this LIP.
  • The function applyPrevotesPrecommits in LIP 0014 corresponds to the function updatePrevotesPrecommits in this LIP.
  • The function computeChainMaxHeightPrevoted in LIP 0014 corresponds to the function updateMaxHeightPrevoted in this LIP.
  • The function computeChainMaxHeightFinalized in LIP 0014 corresponds to the function updateMaxHeightPrecommitted in this LIP.

The changes in these functions are due to the fact that all prevotes and precommits have an associated weight as described above and to account for the state structure defined in the BFT module LIP.

Comparison to the Lisk-BFT paper

The main technical difference between the Lisk-BFT protocol specified in the paper (Definition 4.1 in the Lisk-BFT paper) and the specification in this LIP is that the BFT weights and thresholds in this LIP are integers. For simplicity of exposition, the paper assumes that the BFT weights are scaled such that the sum of BFT weights is 1 at every height. To avoid any issues with floating point arithmetic and rounding, the LIP, however, uses integral weights instead. A transformation from the BFT weights and thresholds in this LIP to the BFT weights and thresholds used in the paper is done by dividing all BFT weights and thresholds at height h by the sum of BFT weights at height h.

The Lisk-BFT protocol introduced in Definition 4.1 of the Lisk-BFT paper allows to choose two protocol parameters, τ ∈ (1/3, 1] and a natural number ρ. The decision threshold τ in the paper corresponds to the precommit threshold used in this LIP up to rescaling and the subtle difference that the weight of precommits in the paper has to be strictly more than τ but in these specifications it only has to be greater or equal than precommitThreshold(h) (as we restrict the range of precommitThreshold(h) such that precommitThreshold(h) / aggregateBFTWeight(h) > 1/3). Similarly, we choose prevoteThreshold(h) such that prevoteThreshold(h) / aggregateBFTWeight(h) > 2/3.

The parameter ρ, which determines how many blocks a block can imply prevotes for, is given by 3*LSK_BFT_BATCH_SIZE in the specifications in this LIP, as also in LIP 0014. Here LSK_BFT_BATCH_SIZE is a constant given in the specifications below. As the round length in a PoA chain can vary, we require that the maximum possible round length in a PoA chain, given by the constant MAX_NUM_VALIDATORS defined in the Proof-of-Authority LIP, is always at most the constant LSK_BFT_BATCH_SIZE. As we have ρ=3*LSK_BFT_BATCH_SIZE, this ensures that ρ is at least three times the maximum number of active validators, which is required by Definition 4.1 in the Lisk-BFT paper for the liveness of the protocol.

Validator Changes

In order to guarantee the safety property, not too many validators, in terms of BFT weight, can change at one time without intermediate blocks being finalized, as shown in Theorem 4.4 in the Lisk-BFT paper. Note that these are guarantees for the worst case, i.e., a significant number of Byzantine validators and bad network conditions at the time of the validator change. Without bad network conditions or Byzantine validators a large proportion of validators can change without contradicting blocks being finalized. For a chain utilizing Lisk DPoS in practice, the validator set typically is rather stable so that the sufficient conditions for the safety property are generally satisfied. For a PoA chain, it is highly recommended that the validators change the BFT weights and active validator set in a cautious and gradual way so that the sufficient condition for the safety property is satisfied. Assume that the PoA chain uses precommitThreshold(h)=floor(⅔*aggregateBFTWeight(h))+1 and there are no Byzantine validators. Then it is safe to change validators with overall BFT weight of at most ceil(1/3*aggregateBFTWeight(h))-1 and then wait for sufficient time until this change is considered final. In order to compute the weight that is actually changing as defined Theorem 4.4 in the Lisk-BFT paper, it is best to rescale the weights such that sum of BFT weight is 1. For instance, doubling the BFT weights of all validators actually means that after rescaling no weight changed.

Specification

Constants

Name Value Description
LSK_BFT_BATCH_SIZE configurable per chain A constant of the BFT module, see the BFT module LIP for a description.

Notation

In this LIP, we use the following notation that is introduced in the BFT module LIP:

  • bftParameters(height): denotes the deserialized object stored in the BFT Parameters substore with store key equal to uint32be(height), i.e., the big endian unsigned integer serialization of height,
  • bftVotes: denotes the deserialized object stored in the BFT Votes substore with store key equal to empty bytes,

For details regarding the BFT module store and schemas of the stored objects, see the BFT module LIP.

Internal Functions

In this section, we specify some auxiliary functions and the three main functions updatePrevotesPrecommits, updateMaxHeightPrevoted and updateMaxHeightPrecommitted for updating the BFT Votes substore of the BFT module. The BFT module specifies in which order and at what time of the block processing these three functions are called. The three functions completely define how the prevote and precommit weights, the property maxHeightPrevoted and the property maxHeightPrecommitted stored in the BFT Votes substore are updated as part of the block processing.

getBFTWeight

This function allows to obtain the BFT weight of a given validator at a certain height.

Parameters
  • validatorAddress: Address of the validator for which to obtain the BFT weight.
  • height: Height for for which to obtain the BFT weight.
Returns

The BFT weight of the validator with address validatorAddress at height height.

Execution
getBFTWeight(validatorAddress, height):
    bftParameters = getBFTParametersInternal(height)
    validatorInfo = object in bftParameters.validators with
                    address property equal to validatorAddress
    return validatorInfo.bftWeight

Note that the function getBFTParametersInternal is an internal function defined in the BFT module LIP.

setLargestHeightPrecommit

This function allows to update the property largestHeightPrecommit for the validator specified by the address given as input.

Parameters
  • validatorAddress: Address of the validator for which to update the property largestHeightPrecommit.
  • height: The property largestHeightPrecommit is set to this value.
Execution
setLargestHeightPrecommit(validatorAddress, height):
    for validatorInfo in bftVotes.activeValidators:
        if validatorInfo.address == validatorAddress:
            validatorInfo.largestHeightPrecommit = height
            return

getHeightNotPrevoted

The function getHeightNotPrevoted is used to compute the largest height in the current chain for which a validator did not prevote. If newBlockHeader is the block header of the block at the tip of the chain and heightNotPrevoted is the return value of this function, then the validator can only precommit in the range {heightNotPrevoted+1, ..., newBlockHeader.height}. This ensures that that the validator has cast a prevote for a block before casting a precommit.

Using the notation from the transformation in Definition 4.1 of the Lisk-BFT paper, assuming newBlockHeader is the header of block B_l and letting genesisHeight denote the height of the genesis block, the function computes the value max(j_2, newBlockHeader.height-3*LSK_BFT_BATCH_SIZE, genesisHeight).

The three cases marked in the code below are the following:

  • Case 1: This case means that either the block B at height heightPreviousBlock was not generated by the validator (as the validator generated a block at height heightPreviousBlock on a different chain) or B does not imply any prevote.
    In both cases, the validator did not prevote for B and we therefore return the height of B.
  • Case 2: This case means that the block at height heightPreviousBlock was generated by the same validator and we therefore check the blocks beforehand.
  • Case 3: In this case, the validator cast a prevote for all blocks referenced in bftVotes.blockBFTInfos and we therefore return bftVotes.blockBFTInfos[-1].height-1. Note that as the length of bftVotes.blockBFTInfos is at most 3*LSK_BFT_BATCH_SIZE and the genesis block header information is not added to bftVotes.blockBFTInfos, we have bftVotes.blockBFTInfos[-1].height-1 = max(bftVotes.blockBFTInfos[0].height-3*LSK_BFT_BATCH_SIZE, genesisHeight). Note that bftVotes().blockBFTInfos[0].height is the current height as the block information of the block at the current tip is stored at the beginning of bftVotes().blockBFTInfos and that bftVotes().blockBFTInfos[-1].height-1 is one less than the height of the last element in bftVotes().blockBFTInfos.

Returns

The function returns the largest height of an ancestor block referenced in bftVotes.blockBFTInfos for which the chain does not contain an implied prevote by the validator forging bftVotes.blockBFTInfos[0] (or bftVotes.blockBFTInfos[-1].height-1 if none exists).

Execution

getHeightNotPrevoted():
    newBlockBFTInfo = bftVotes.blockBFTInfos[0]
    currentHeight = newBlockBFTInfo.height
    heightPreviousBlock = newBlockBFTInfo.maxHeightGenerated

    # iterate over blockBFTInfo objects in decreasing order by height
    while currentHeight - heightPreviousBlock < length(bftVotes.blockBFTInfos):
        blockBFTInfo = bftVotes.blockBFTInfos[currentHeight - heightPreviousBlock]
        if (blockBFTInfo.generatorAddress != newBlockBFTInfo.generatorAddress or
            blockBFTInfo.maxHeightGenerated >= heightPreviousBlock):
            # Case 1
            return heightPreviousBlock
        else:
            # Case 2
            heightPreviousBlock=blockBFTInfo.maxHeightGenerated
    # Case 3
    # return one less than the height of the blockBFTInfo with smallest height
    return bftVotes.blockBFTInfos[-1].height-1

updatePrevotesPrecommits

This function updates the prevote and precommit weights stored in bftVotes.blockBFTInfos taking into account all prevotes and precommits implied by the block header referenced by bftVotes.blockBFTInfos[0].

Execution
updatePrevotesPrecommits():
    # when processing the genesis block the array is empty and no prevotes or precommits need to be updated
    if length(bftVotes.blockBFTInfos) == 0:
        return
    newBlockBFTInfo = bftVotes.blockBFTInfos[0]
    # a block header only implies votes if maxHeightGenerated < height
    if newBlockBFTInfo.maxHeightGenerated >= newBlockBFTInfo.height:
        return

    validatorInfo = entry in bftVotes.activeValidators with address equal to newBlockBFTInfo.generatorAddress
    heightNotPrevoted = getHeightNotPrevoted()

    # add implied precommits by newBlockheader
    minPrecommitHeight = max(validatorInfo.minActiveHeight,
                             heightNotPrevoted+1,
                             validatorInfo.largestHeightPrecommit+1)
    hasPrecommitted = False
    # iterate over blockBFTInfo objects in decreasing order by height
    for blockBFTInfo in bftVotes.blockBFTInfos:
        if blockBFTInfo.height < minPrecommitHeight:
            break
        # add precommit if threshold is reached
        if blockBFTInfo.prevoteWeight >= getBFTParametersInternal(blockBFTInfo.height).prevoteThreshold:
            blockBFTInfo.precommitWeight += getBFTWeight(newBlockBFTInfo.generatorAddress, blockBFTInfo.height)
            # only update the property largestHeightPrecommit for the largest height of a precomit cast
            if not hasPrecommitted:
                setLargestHeightPrecommit(newBlockBFTInfo.generatorAddress, blockBFTInfo.height)
                hasPrecommitted = True

    # add implied prevotes by newBlockheader
    minPrevoteHeight = max(newBlockBFTInfo.maxHeightGenerated+1,
                           validatorInfo.minActiveHeight)
    # iterate over blockBFTInfo objects in decreasing order by height
    for blockBFTInfo in bftVotes.blockBFTInfos:
        if blockBFTInfo.height < minPrevoteHeight:
            break
        blockBFTInfo.prevoteWeight += getBFTWeight(newBlockBFTInfo.generatorAddress, blockBFTInfo.height)

updateMaxHeightPrevoted

If the prevote and precommit weights have been updated correctly, the following function updates the property bftVotes.maxHeightPrevoted which stores the maximum height of a block with prevote weight at least the prevote threshold value.

Execution
updateMaxHeightPrevoted(){
    # iterate over blockBFTInfo objects in decreasing order by height
    for blockBFTInfo in bftVotes.blockBFTInfos:
        if blockBFTInfo.prevoteWeight >= getBFTParametersInternal(blockBFTInfo.height).prevoteThreshold:
            bftVotes.maxHeightPrevoted = blockBFTInfo.height
            return

updateMaxHeightPrecommitted

If the prevote and precommit weights have been updated correctly, the following function updates the property bftVotes.maxHeightPrecommitted which stores the maximum height of a block with precommit weight at least the precommit threshold value.

Execution
updateMaxHeightPrecommitted(){
    # iterate over blockBFTInfo objects in decreasing order by height
    for blockBFTInfo in bftVotes.blockBFTInfos:
        if blockBFTInfo.precommitWeight >= getBFTParametersInternal(blockBFTInfo.height).precommitThreshold:
            bftVotes.maxHeightPrecommitted = blockBFTInfo.height
            return

Finalized Height

The value of the property maxHeightFinalized, which is the maximum height until the current chain is considered final and should never be reverted, needs to be maintained outside of the state machine. The reason is that it is not uniquely determined by the tip of the chain, but depends on the history of executed and reverted blocks as explained in the rationale at the beginning. The value of maxHeightFinalized can be easily updated as follows:

maxHeightFinalized = max(bftVotes.maxHeightPrecommitted, maxHeightFinalized).

In particular, it only needs to be updated if bftVotes.maxHeightPrecommitted increases.

Backwards Compatibility

This LIP defines a part of the state transition logic of the BFT module introduced in the BFT module LIP. The LIP therefore requires a hard fork as introducing the BFT module implies a hardfork.

2 Likes
2

I updated the proposal significantly due to the changes of the chain architecture and introduction of the BFT module. The main changes are the following:

  • The computation of prevote weights, precommit weights and properties maxHeightPrevoted and maxHeightFinalized is now part of the state transitions of the BFT module. In particular, the notation of the LIP needed to be updated so it describes how the state of the BFT module is changed.
  • The properties chainMaxHeightPrevoted, chainMaxHeightFinalized and maxHeightPreviouslyForged are renamed as described in the proposal.
  • The LIP also specifies how the property largestHeightPrecommit is updated as part of updating the prevote and precommit weights.
3

I created a PR for this proposal on GitHub:

4

The pull request was merged and the LIP has now status Draft: