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>
Abstract
This LIP defines how to generalize the LiskBFT consensus protocol to allow for different finality weights of the participating validators. A finality weight defines the amount with which the corresponding validator contributes to finalizing blocks. Additionally, we allow these weights as well as the weight threshold for considering a block final to change over time.
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 finality weights of the active validators, i.e., different weights with which the validators contribute to finalizing blocks. 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 ProofofAuthority LIP where validators can be added and removed or their weights changed with a simple transaction and without a hard fork.
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
.  finality weight: The weight with which a validator contributes to finalizing a block.
 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 finality weights of all validators casting a prevote for this block has to be at least the prevote threshold.
 precommit threshold: For considering a block final, the sum of finality weights of all validators casting a precommit for this block has to be at least the precommit threshold.
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, the changes introduced in this LIP are limited to the following aspects of the LiskBFT consensus protocol:
 Instead of a finality weight of
1
, the finality weight of a validator can be anyuint64
value.  Instead of having a fixed finality weight, the finality weight of validators can change per round.
 The prevote threshold is always computed from the sum of finality weights of all validators. Therefore, the prevote threshold can change per round if the sum of finality weights changes.
 Instead of having a fixed precommit threshold, the precommit threshold can change per round within a range depending on the sum of finality weights of all validators.
 We introduce a variable
chainMaxHeightPrecommited
, which denotes the largest heighth
such that the finality 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. This is in contrast to the value ofchainMaxHeightFinalized
, which is the maximum value ofchainMaxHeightPrecommited
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 ofchainMaxHeightPrecommited
, but different values ofchainMaxHeightFinalized
due to a different history of reverted blocks. The variablechainMaxHeightPrecommited
is introduced as it will be important for certificate generation.
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 finality weights and thresholds in this LIP are integers. For simplicity of exposition, the paper assumes that the finality weights are scaled such that the sum of finality 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 finality weights and thresholds in this LIP to the finality weights and thresholds used in the paper is done by dividing all finality weights and thresholds at height h
by the sum of finality 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 ρ
. For the definition of the constants and variables names used in this LIP, such as prevoteThreshold(h)
, precommitThreshold(h)
and aggregateFinalityWeight(h)
, see the table of constants and table of variables and functions at the beginning of the specification section. 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) / aggregateFinalityWeight(h) > 1/3
).
Similarly, we choose prevoteThreshold(h)
such that prevoteThreshold(h) / aggregateFinalityWeight(h) > 2/3
.
The parameter ρ
, which determines how many blocks in the past a block can imply prevotes for, is given by LSK_BFT_VOTE_RANGE+1
in the specifications in this LIP, as also in LIP 0014. 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
introduced below. We have ρ=LSK_BFT_VOTE_RANGE+1
by Definition 4.1 in the LiskBFT paper and the definition of LSK_BFT_VOTE_RANGE
in the specifications below. Further, we have LSK_BFT_VOTE_RANGE+1 = 3*LSK_BFT_BATCH_SIZE
as defined below. This means ρ = 3*LSK_BFT_BATCH_SIZE
holds, which ensures that ρ
is at least 3
times the maximum number of active validators by the choice of LSK_BFT_BATCH_SIZE
, 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 finality 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 finality 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(⅔*aggregateFinalityWeight(h)) + 1
and there are no Byzantine validators. Then it is safe to change validators with overall finality weight of at most ceil(1/3*aggregateFinalityWeight(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 finality weight is 1
. For instance, doubling the finality weights of all validators actually means that after rescaling no weight changed.
Specification
Constants
Name  Value  Description 

LSK_BFT_BATCH_SIZE 
configurable per chain  This is a constant that should be never smaller than the round length of the chain, see also LIP 0014. 
LSK_BFT_VOTE_RANGE 
3*LSK_BFT_BATCH_SIZE1 
A block at height h can imply prevotes and precommits from height hLSK_BFT_VOTE_RANGE up to height h . We use this constant for more concise notation in the following specifications. See also LIP 0014. 
Basic Variables and Functions
In the following table, we provide the variable and function names used in these specifications together with a brief description.
Name  Type  Description 

blockheaders(h) 
block header object  For a height h as input, the function returns the block header object in the current chain at height h . 
validatorFinalityWeight(h,v) 
uint64 
For a height h and a validator address v as input, the function returns the finality weight of the validator with address v at height h . For nonactive validators this value is 0 . 
aggregateFinalityWeight(h) 
uint64 
For a height h , the function returns the sum of finality weights of all active validators at height h . The validator finality weights have to be set be so that this sum is at most the maximum uint64 value. 
blockPrevoteWeights[h] 
uint64 
For a height h , blockPrevoteWeights[h] contains the aggregate weight of prevotes for the block at height h , considering all prevotes implied by blocks in the current chain. 
blockPrecommitWeights[h] 
uint64 
For a height h , blockPrecommitWeights[h] contains the aggregate weight of precommits for the block at height h , considering all precommits implied by blocks in the current chain. 
prevoteThreshold(h) 
uint64 
For a height h as input, the function returns the prevote weight threshold at height h . This threshold of prevotes is required for casting precommits for the block at height h . This value has to be equal to floor(2/3*aggregateFinalityWeight(h))+1 . 
precommitThreshold(h) 
uint64 
For a height h as input, the function returns the precommit weight threshold at height h . For every height h the following has to hold: floor(1/3*aggregateFinalityWeight(h))+1 <= precommitThreshold(h) <= aggregateFinalityWeight(h) . 
chainMaxHeightPrevoted 
uint32 
The maximum height h such that the following holds: blockPrevoteWeights[h]>=prevoteThreshold(h) . 
chainMaxHeightPrecommited 
uint32 
The maximum height h such that the following holds: blockPrecommitWeights[h]>=precommitThreshold(h) . 
chainMaxHeightFinalized 
uint32 
The maximum height until which the current chain is considered final and will not be reverted. It is the maximum value of chainMaxHeightPrecommited computed so far. 
The weights of active validators and the thresholds for being able to precommit for a block or consider a block final can change per round. This requires to store the following values for every round that is not finalized:

validatorFinalityWeight(h, v)
for every active validatorv
, 
aggregateFinalityWeight(h)
, 
prevoteThreshold(h)
, 
precommitThreshold(h)
.
Note that these functions are defined for every height for ease of use in the specifications below, but it is sufficient to store these values per round as these cannot change within one round. For Lisk DPoS, the return values of these functions, except for validatorFinalityWeight(h, v)
, are constant and thus it is sufficient to store these constants.
Lisk DPoS configuration
This section gives the specific values for the constants, variables and functions for Lisk DPoS.
Name  Value  Description 

NUM_ACTIVE_DELEGATES 
configurable per chain Lisk Mainnet: 101 
The number of active delegates in a Lisk DPoS chain. 
NUM_STANDBY_DELEGATES 
configurable per chain Lisk Mainnet: 2 
The number of standby delegates in a Lisk DPoS chain. 
LSK_BFT_BATCH_SIZE 
NUM_ACTIVE_DELEGATES+NUM_STANDBY_DELEGATES 
This value equals the fixed length of a round in a Lisk DPoS chain. 
validatorFinalityWeight(h,v) 
If the block at height h is part of the bootstrap phase: * 0 for all delegates If the block at height h is after the bootstrap phase: * 1 for all active delegates * 0 for all other delegates 
See above. 
aggregateFinalityWeight(h) 
If the block at height h is part of the bootstrap phase: * 0 If the block at height h is after the bootstrap phase: * NUM_ACTIVE_DELEGATES 
See above. 
prevoteThreshold(h) 
floor(2/3*NUM_ACTIVE_DELEGATES)+1 
See above. 
precommitThreshold(h) 
floor(2/3*NUM_ACTIVE_DELEGATES)+1 
See above. 
Note that during the bootstrap period, the equality for prevoteThreshold(h)
and inequality for precommitThreshold(h)
do not hold. This is because all bootstrap delegates have finality weight 0
so that blocks are not finalized during the bootstrap period as specified in LIP 0034.
Lisk PoA configuration
This section gives the specific values for the constants, variables and functions for Lisk PoA.
The ProofofAuthority LIP specifies a chain property object that stores the current validators, their weights and a threshold both used as precommit threshold for LiskBFT as well as required threshold for updating the authorities. For a height h
, we let chainProp[h]
denote the associated chain property object at height h
, that is, if height h
is part of round r
, then chainProp[h]
is the chain property object at the beginning of round r2
. Note that in particular, the validator addresses in the chainProp object are those validators forging in round r
due to the delay of 2
rounds specified in ProofofAuthority LIP.
Name  Value  Description 

MAX_NUM_VALIDATORS 
See ProofofAuthority LIP.  Maximum possible number of active validators as defined in the ProofofAuthority LIP. 
LSK_BFT_BATCH_SIZE 
MAX_NUM_VALIDATORS 
This is the maximum round length that is possible in a PoA chain. 
validatorFinalityWeight(h,v) 
* For a height h and validator address v with v==chainProp.validatorAddresses[i] , the value is chainProp[h].weights[i] . * For a height h and any validator address v not contained in chainProp[h].validatorAddresses , the value is 0 . 
See above. 
aggregateFinalityWeight(h) 
For a height h , this is the sum of all entries in the array chainProp[h].weights . 
See above. 
prevoteThreshold(h) 
floor(2/3*aggregateFinalityWeight(h))+1 
See above. 
precommitThreshold(h) 
chainProp[h].threshold 
See above. 
Computing Prevotes and Precommits with Weights
As the weights of active validators and thresholds can change per round, we need to generalize the computation of the weight of prevotes and precommits for blocks as described here. This section is an update of the specifications in the section “Computing Prevotes and Precommits” in LIP 0014, i.e., the computation of prevotes, precommits, the values of chainMaxHeightPrevoted
and chainMaxHeightFinalized
have to be changed as described below and the computation of chainMaxHeightPrecommited
is added. The specifications here also use the same three functions getHeightNotPrevoted()
, applyPrevotesPrecommits()
and computeChainMaxHeightPrevoted()
with the same input parameters. Compared to LIP 0014, the following changed:
 The map
prevoteCounts
is renamed toblockPrevoteWeights
andprecommitCounts
toblockPrecommitWeights.
 The maps
blockPrecommitWeights
andblockPrevoteWeights
are incremented by a dynamic validator weight instead of the constant1
.  The check
prevoteCounts[h]>=LSK_BFT_PREVOTE_THRESHOLD
is replaced byblockPrevoteWeights[h] >= prevoteThreshold(h)
which uses a dynamic threshold.  The check
prevoteCounts[h]>=LSK_BFT_PRECOMMIT_THRESHOLD
is replaced byblockPrevoteWeights[h] >= precommitThreshold(h)
which uses a dynamic threshold.  The code for
getHeightNotPrevoted()
is simplified.  A new function
computeChainMaxHeightPrecommitted()
is introduced to compute the updated value ofchainMaxHeightPrecommited
.  The function
computeChainMaxHeightFinalized()
has different input parameters as it uses the value ofchainMaxHeightPrecommited
.  The code in this section takes into account the new block schema.
Let newBlockheader
be the block header added to the current chain and further newBlockheader.asset.maxHeightPreviouslyForged < newBlockheader.height
. Then the following function computes the largest height of an ancestor block in the range {newBlockheader.heightLSK_BFT_VOTE_RANGE1, ..., newBlockheader.asset.maxHeightPreviouslyForged}
for which the chain does not contain an implied prevote by the validator forging newBlockheader
(or newBlockheader.heightLSK_BFT_VOTE_RANGE1
if none exists). If heightNotPrevoted
is the return value of this function, then the validator can only precommit in the range {heightNotPrevoted+1, ..., newBlockheader.asset.maxHeightPreviouslyForged}
ensuring that is has cast a prevote for all blocks for which it precommits. Using the notation from the transformation in Definition 4.1 of the LiskBFT paper and assuming newBlockheader
is the header of block B_l
, the function computes the value max{j_2,newBlockheader.heightLSK_BFT_VOTE_RANGE1}
. 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 forged by the validator (as the validator forged a block at height h 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 forged by the same validator and we therefore check that block beforehand.  Case 3: In this case, the validator cast a prevote for all blocks at heights
{newBlockheader.height  LSK_BFT_VOTE_RANGE,...,newBlockheader.height}
and we therefore returnnewBlockheader.heightLSK_BFT_VOTE_RANGE1.
getHeightNotPrevoted(newBlockheader) {
let heightPreviousBlock = newBlockheader.asset.maxHeightPreviouslyForged;
const minPrevoteHeight = newBlockheader.heightLSK_BFT_VOTE_RANGE
while (heightPreviousBlock>=minPrevoteHeight) {
if (blockheaders[heightPreviousBlock].generatorPublicKey!=newBlockheader.generatorPublicKey 
blockheaders[heightPreviousBlock].asset.maxHeightPreviouslyForged>=heightPreviousBlock) {
// Case 1
return heightPreviousBlock;
} else {
// Case 2
heightPreviousBlock=blockheaders[heightPreviousBlock].asset.maxHeightPreviouslyForged;
}
}
// Case 3
return minPrevoteHeight1;
}
Given the new block newBlockheader
added to the current chain as input, this function updates the maps blockPrevoteWeights
and blockPrecommitWeights
taking into account all prevotes and precommits implied by newBlockheader
.
applyPrevotesPrecommits(newBlockheader) {
// a block header only implies votes if maxHeightPreviouslyForged<height
if (newBlockheader.asset.maxHeightPreviouslyForged >= newBlockheader.height) {
return;
}
const addressCurrentValidator = address of the validator given by newBlockheader.generatorPublicKey
const validatorMinHeightActive = height of first block of round since when the validator
given by addressCurrentValidator has been continuously active
const largestHeightPrecommit = largest height of a precommit of the validator given
by addressCurrentValidator
const heightNotPrevoted = getHeightNotPrevoted(newBlockheader)
// add implied precommits by newBlockheader
const minPrecommitHeight = max(validatorMinHeightActive,
heightNotPrevoted+1,
largestHeightPrecommit+1)
const maxPrecommitHeight = newBlockheader.height1;
for (let h=minPrecommitHeight; h <= maxPrecommitHeight;h++) {
// Add precommit if threshold is reached
if (blockPrevoteWeights[h] >= prevoteThreshold(j)) {
blockPrecommitWeights[h] += validatorFinalityWeight(h, addressCurrentValidator);
}
}
// add implied prevotes by newBlockheader
const minPrevoteHeight = max(newBlockheader.asset.maxHeightPreviouslyForged+1,
validatorMinHeightActive,
newBlockheader.heightLSK_BFT_VOTE_RANGE);
const maxPrevoteHeight = newBlockheader.height;
for (let h = minPrevoteHeight; h <= maxPrevoteHeight; h++) {
blockPrevoteWeights[h] += validatorFinalityWeight(h, addressCurrentValidator);
}
}
Given currentHeight
, the height of the new block header added to the chain, as input, the function below returns the new value of chainMaxHeightPrevoted
.
computeChainMaxHeightPrevoted(currentHeight){
let maxHeightPrevoted = blockheaders[currentHeight].maxHeightPrevoted;
const minHeightCheck = max(maxHeightPrevoted+1,
currentHeightLSK_BFT_VOTE_RANGE);
for (let h=currentHeight; h >= minHeightCheck; h) {
if (blockPrevoteWeights[h] >= prevoteThreshold(h)) {
return h;
}
}
return maxHeightPrevoted;
}
Given currentHeight
, the height of the new block header added to the chain, and the current value of chainMaxHeightPrecommited
as input, the following function computes the new value of chainMaxHeightPrecommited
.
computeChainMaxHeightPrecommited(currentHeight, currentChainMaxHeightPrecommited){
const minHeightCheck = max(currentChainMaxHeightPrecommited+1,
currentHeightLSK_BFT_VOTE_RANGE)`
for (let h = currentHeight; h >= minHeightCheck; h) {
if (blockPrecommitWeights[h] >= precommitThreshold(h)) {
return h;
}
}
return currentChainMaxHeightPrecommited;
}
Given the current value of chainMaxHeightFinalized
and the updated value of chainMaxHeightPrecommited
computed above as input, the following function computes the new value of chainMaxHeightFinalized
.
computeChainMaxHeightFinalized(currentChainMaxHeightFinalized, updatedChainMaxHeightPrecommited) {
return max(updatedChainMaxHeightPrecommited, currentChainMaxHeightFinalized);
}
Backwards Compatibility
For Lisk Mainnet, the weights and threshold are the same as specified in LIP 0014 and this LIP therefore does not specify a protocol change for Lisk Mainnet. The LIP only allows more flexibility for new chains to customize the LiskBFT consensus protocol, in particular, in conjunction with the ProofofAuthority validator selection mechanism specified in the ProofofAuthority LIP.