Add weights to Lisk-BFT consensus protocol

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>

Abstract

This LIP defines how to generalize the Lisk-BFT 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 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 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 Proof-of-Authority validator selection mechanism introduced in the Proof-of-Authority 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 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.
  • 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 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, the changes introduced in this LIP are limited to the following aspects of the Lisk-BFT consensus protocol:

  • Instead of a finality weight of 1, the finality weight of a validator can be any uint64 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 height h such that the finality 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. This is in contrast to the value of chainMaxHeightFinalized, which is the maximum value of chainMaxHeightPrecommited 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 chainMaxHeightPrecommited, but different values of chainMaxHeightFinalized due to a different history of reverted blocks. The variable chainMaxHeightPrecommited is introduced as it will be important for certificate generation.

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 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 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 ρ. 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 Proof-of-Authority 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 Lisk-BFT 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 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 finality 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 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 Lisk-BFT 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_SIZE-1 A block at height h can imply prevotes and precommits from height h-LSK_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 non-active 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 validator v,
  • 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 Proof-of-Authority LIP specifies a chain property object that stores the current validators, their weights and a threshold both used as precommit threshold for Lisk-BFT 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 r-2. 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 Proof-of-Authority LIP.

Name Value Description
MAX_NUM_VALIDATORS See Proof-of-Authority LIP. Maximum possible number of active validators as defined in the Proof-of-Authority 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 to blockPrevoteWeights and precommitCounts to blockPrecommitWeights.
  • The maps blockPrecommitWeights andblockPrevoteWeightsare incremented by a dynamic validator weight instead of the constant 1.
  • The check prevoteCounts[h]>=LSK_BFT_PREVOTE_THRESHOLD is replaced by blockPrevoteWeights[h] >= prevoteThreshold(h) which uses a dynamic threshold.
  • The check prevoteCounts[h]>=LSK_BFT_PRECOMMIT_THRESHOLD is replaced by blockPrevoteWeights[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 of chainMaxHeightPrecommited.
  • The function computeChainMaxHeightFinalized() has different input parameters as it uses the value of chainMaxHeightPrecommited.
  • 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.height-LSK_BFT_VOTE_RANGE-1, ..., newBlockheader.asset.maxHeightPreviouslyForged} for which the chain does not contain an implied prevote by the validator forging newBlockheader (or newBlockheader.height-LSK_BFT_VOTE_RANGE-1 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 Lisk-BFT paper and assuming newBlockheader is the header of block B_l, the function computes the value max{j_2,newBlockheader.height-LSK_BFT_VOTE_RANGE-1}. 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 forged by the validator (as the validator forged a block at height h 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 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 return newBlockheader.height-LSK_BFT_VOTE_RANGE-1.
getHeightNotPrevoted(newBlockheader) {
  let heightPreviousBlock = newBlockheader.asset.maxHeightPreviouslyForged;
  const minPrevoteHeight = newBlockheader.height-LSK_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 minPrevoteHeight-1;
}

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.height-1;
  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.height-LSK_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,
                             currentHeight-LSK_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,
                             currentHeight-LSK_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 Lisk-BFT consensus protocol, in particular, in conjunction with the Proof-of-Authority validator selection mechanism specified in the Proof-of-Authority LIP.

2 Likes