Hello everyone,
I want to propose a first LIP for the roadmap objective “Update LiskBFT for interoperability”. The LIP generalizes the LiskBFT 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 LiskBFT consensus protocol
Author: Jan Hackfeld <jan.hackfeld@lightcurve.io>
Type: Standards Track
Created: <YYYYMMDD>
Updated: <YYYYMMDD>
Requires: Introduce the BFT module LIP
Abstract
This LIP defines how to generalize the LiskBFT 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 LiskBFT consensus protocol introduced in LIP 0014 was specified for the Lisk mainchain and sidechains that use Delegated ProofofStake 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 ProofofAuthority 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 LiskBFT 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
.
Changes Compared to LIP 0014
The general goal of the update of the LiskBFT 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 LiskBFT protocol, such as the fork choice rule, the fast chain switching mechanism or the block synchronization mechanism stay unchanged.
The generalization of the LiskBFT 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. 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 consensusrelated information due to the new state structure introduced in the BFT module LIP. In particular, we introduce the following changes to the BFTrelated 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 the BFT module LIP.
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 state structure defined in the BFT module LIP.
Comparison to the LiskBFT paper
The main technical difference between the LiskBFT protocol specified in the paper (Definition 4.1 in the LiskBFT 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 LiskBFT protocol introduced in Definition 4.1 of the LiskBFT 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 ProofofAuthority 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 LiskBFT 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 LiskBFT 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 LiskBFT 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 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 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 propertylargestHeightPrecommit
. 
height
: The propertylargestHeightPrecommit
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 LiskBFT 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.height3*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].height1
. 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].height1 = max(bftVotes.blockBFTInfos[0].height3*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].height1
is one less than the height of the last element inbftVotes().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].height1
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].height1
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.