LIP: 0056
Title: Add weights to Lisk-BFT consensus protocol
Author: Jan Hackfeld <[email protected]>
Discussions-To: https://research.lisk.com/t/add-weights-to-lisk-bft-consensus-protocol/289
Status: Active
Type: Standards Track
Created: 2021-05-06
Updated: 2024-01-04
Requires: 0058
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 BFT store defined in LIP 0058.
This LIP is licensed under the Creative Commons Zero 1.0 Universal.
The Lisk-BFT consensus protocol introduced in LIP 0014 was specified for the Lisk mainchain and sidechains that use 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 validators, i.e., those validators 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 validators 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 BFT store as described in LIP 0058. 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 store structure introduced in LIP 0058.
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 heighth
. - 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 heighth
. - 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 heighth
. - 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 heighth
.
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 parts 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 anyuint64
value. - Instead of having a fixed BFT weight, the BFT weight of validators can change over time. In LIP 0058 we define how the BFT weights can be changed.
- 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. LIP 0058 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 as introduced in LIP 0058. In particular, we introduce the following changes to the BFT-related properties:
- The property
chainMaxHeightPrevoted
is renamed tomaxHeightPrevoted
. - The property
chainMaxHeightFinalized
is renamed tomaxHeightFinalized
. - The property
maxHeightPreviouslyForged
is renamed tomaxHeightGenerated
. - As part of the consensus vote computations, we also update a new property
maxHeightPrecommitted
which is introduced in LIP 0058. The property denotes the largest heighth
such that the BFT weight of precommits for the block at heighth
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 ofmaxHeightFinalized
, which is the maximum value ofmaxHeightPrecommitted
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 ofmaxHeightPrecommitted
, but different values ofmaxHeightFinalized
due to a different history of reverted blocks. The variablemaxHeightPrecommitted
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 functionupdatePrevotesPrecommits
in this LIP. - The function
computeChainMaxHeightPrevoted
in LIP 0014 corresponds to the functionupdateMaxHeightPrevoted
in this LIP. - The function
computeChainMaxHeightFinalized
in LIP 0014 corresponds to the functionupdateMaxHeightPrecommitted
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 store structure defined in LIP 0058.
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 defined in LIP 0058. 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 PoA module, 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. Additionally, we need to assume that the block proposal is done in a round-robin fashion so that the condition in Definition 4.1 in the Lisk-BFT paper is satisfied. In the Lisk SDK the Validators module is responsible for the block slot assignment. It assigns block slots round-robin and therefore satisfies this requirement.
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 PoS 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.
In this LIP, we use the following notation that is introduced in LIP 0058:
LSK_BFT_BATCH_SIZE
: a BFT protocol constant that was already introduced in LIP 0014,bftParameters(height)
: denotes the deserialized object stored in the BFT Parameters substore with store key equal touint32be(height)
, i.e., the big endian unsigned integer serialization ofheight
,bftVotes
: denotes the deserialized object stored in the BFT Votes substore with store key equal to empty bytes,
For details regarding the BFT store and schemas of the stored objects, see LIP 0058.
In this section, we specify some auxiliary functions and the three main functions updatePrevotesPrecommits
, updateMaxHeightPrevoted
and updateMaxHeightPrecommitted
for updating the BFT Votes substore introduced in LIP 0058. LIP 0058 further 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.
This function allows to obtain the BFT weight of a given validator at a certain height.
validatorAddress
: Address of the validator for which to obtain the BFT weight.height
: Height for for which to obtain the BFT weight.
The BFT weight of the validator with address validatorAddress
at height height
.
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 LIP 0058.
This function allows to update the property largestHeightPrecommit
for the validator specified by the address given as input.
validatorAddress
: Address of the validator for which to update the propertylargestHeightPrecommit
.height
: The propertylargestHeightPrecommit
is set to this value.
setLargestHeightPrecommit(validatorAddress, height):
for validatorVoteInfo in bftVotes.activeValidatorsVoteInfo:
if validatorVoteInfo.address == validatorAddress:
validatorVoteInfo.largestHeightPrecommit = height
return
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 heightheightPreviousBlock
was not generated by the validator (as the validator generated a block at heightheightPreviousBlock
on a different chain) orB
does not imply any prevote. In both cases, the validator did not prevote forB
and we therefore return the height ofB
. - 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 returnbftVotes.blockBFTInfos[-1].height-1.
Note that as the length ofbftVotes.blockBFTInfos
is at most3*LSK_BFT_BATCH_SIZE
and the genesis block header information is not added tobftVotes.blockBFTInfos
, we havebftVotes.blockBFTInfos[-1].height-1 = max(bftVotes.blockBFTInfos[0].height-3*LSK_BFT_BATCH_SIZE, genesisHeight)
. Note thatbftVotes().blockBFTInfos[0].height
is the current height as the block information of the block at the current tip is stored at the beginning ofbftVotes().blockBFTInfos
and thatbftVotes().blockBFTInfos[-1].height-1
is one less than the height of the last element inbftVotes().blockBFTInfos
.
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).
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
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]
.
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
voteInfos = bftVotes.activeValidatorsVoteInfo
# If the block generator is not BFT participant (i.e., has BFT weight 0) the block
# does not imply prevotes or precommits. This happens for standby validators, for instance.
if there is no entry in voteInfos with address equal to newBlockBFTInfo.generatorAddress:
return
validatorVoteInfo = entry in voteInfos with address equal to newBlockBFTInfo.generatorAddress
heightNotPrevoted = getHeightNotPrevoted()
# Add implied precommits by newBlockheader.
minPrecommitHeight = max(validatorVoteInfo.minActiveHeight,
heightNotPrevoted+1,
validatorVoteInfo.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,
validatorVoteInfo.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)
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.
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
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.
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
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 application domain. 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.
This LIP together with LIP 0058 changes how a block is processed and therefore introduces a hardfork.