Proof-of-Authority validator selection mechanism

Hello everyone,

I would like to propose another LIP for the roadmap objective “Introduce alternative validator selection mechanism for sidechains”. This LIP specifies the Proof of Authority mechanism in particular.

I’m looking forward to your feedback.

Here is the complete LIP draft:

LIP:
Title: Proof-of-Authority validator selection mechanism
Author: Iker Alustiza <iker@lightcurve.io>
Type: Standards Track
Created: <YYYY-MM-DD>
Updated: <YYYY-MM-DD>
Requires: BLS signatures LIP

Abstract

This LIP introduces the Lisk Proof-of-Authority (PoA) mechanism for the selection of validators, known as authorities in this context, to generate blocks. In particular, this document specifies the PoA module which contains the schemas and the logic for transactions, blocks and accounts that defines the PoA mechanism for the Lisk protocol.

Copyright

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

Motivation

In Proof-of-Authority (PoA) blockchains only a pre-defined set of validators, called the authorities, can propose blocks and they are selected based on off-chain information such as their reputation or identity. It trades the decentralization of the network (arbitrarily selected authorities) for efficiency and performance. This mechanism was first proposed by Gavin Wood in 2015.

A PoA blockchain is especially attractive for small projects or blockchain applications where the project owners are expected to run the network nodes. Due to the simplicity of its validator selection algorithm, it is also suitable for applications where a high transaction per second throughput is important. That is why a self-contained PoA module seems to be a very useful feature to be added as one of the modules available for sidechain developers in the Lisk SDK.

Rationale

This LIP specifies the PoA module which contains the schemas and logic for transactions, blocks and accounts that defines the PoA mechanism for the Lisk protocol. Sidechain developers creating a sidechain with the Lisk SDK will have the out-of-the-box choice between this module or the DPoS module as the mechanism for validator selection in their sidechain.

As mentioned, the Lisk PoA module only sets the mechanism for the selection of the validators, which implies that the underlying algorithm to reach consensus for blocks of the chain is assumed to be given by the Lisk-BFT consensus algorithm. The PoA module also assumes the same round system as currently specified for the Lisk Mainchain. That is, the assignment of block forging slots is done in batches of consecutive blocks called rounds.

Typically, PoA systems do not define any reward system (blockHeader.reward = 0). However, sidechain developers may choose to have a reward system in the chain native token to incentivize the authorities. This reward system can be defined in the same way and with similar rules as it is done for the DPoS case.

Moreover, the banning mechanism (as defined in LIP 0023) and the punishment of BFT violations (as defined in LIP 0024 for the Lisk-BFT protocol) are not necessary for a functional PoA blockchain.
Hence, in this LIP they are not included in the specifications.

Updating the Set of Authorities

The current active authorities, i.e., those authorities eligible to forge blocks and participate in the Lisk-BFT consensus, are stored in the chain property store of the PoA module together with their associated weight. The chain property store further contains a threshold property. The weights and threshold are used in the Lisk-BFT consensus algorithm and for the validity of the authority update transaction. This transaction is specific to the PoA module and allows to update the mentioned paramaters. In particular, the authority update transaction allows PoA chains to increase (or decrease) the number of active authorities, to change their associated weight and the threshold. This is a particularly interesting feature for blockchain applications that start with a small set of validators and nodes in the network (for example, the sidechain developers themselves). With the success and maturity of the application, there may be an interest in opening the project to a bigger and more decentralized set of participants. The transaction is only valid if a threshold of active authorities approve it by adding their signature (to be aggregated) to the transaction asset.

This transaction can set a maximum of 199 active authorities which is the maximum number of active validators in any chain built with the Lisk SDK.

Migration from PoA to DPoS

As mentioned before, the sidechain developers using the SDK may specify their blockchain application to be deployed on a PoA or DPoS chain (assuming they do not develop a custom mechanism).
Thus, a sidechain will be either a PoA or a DPoS blockchain and both modules cannot co-exist in the same chain. However, there may be an interest for some projects that started as a PoA chain to migrate to DPoS. If this is the case, the developers and the future network validators have two choices:

  1. After launching the project, if there is a need for a more decentralized approach: Hard-fork the chain to include the DPoS module instead of PoA. This can be easened by following a snapshot mechanism similar to the one specified in LIP 0035.
  2. If during the development phase, it is decided that the application should start on a PoA chain and then run on a DPoS chain for the long term: The sidechain developers can define an arbitrarily long bootstrapping period for the DPoS chain in the genesis block as explained in LIP 0034. This bootstrapping period effectively mimics a PoA chain where there is a fixed set of validators given by the public keys in the initDelegates property of the block header asset. This will allow it to first have a preparatory phase of the application so it can mature sufficiently before transferring to a DPoS chain.

Specification

Proof-of-Authority Module

The PoA module defines the constants, the state structure, the generation, validation and processing of blocks, the round system, and the specific transactions in PoA chains.

Constants

Name Type Value
POA_MODULE_ID uint32 TBD
PREFIX_VALIDATOR_STORE bytes 0x8000
PREFIX_USERNAME_STORE bytes 0xc0000
PREFIX_CHAIN_STORE bytes 0x0000
EMPTY_HASH bytes SHA-256("")
MAX_LENGTH_USERNAME uint32 20
MAX_NUM_VALIDATORS uint32 199
MAX_UINT64 uint64 18446744073709551615
POA_MESSAGE_TAG bytes ASCII encoded string “LSK_POA_”

State of the PoA Module

Figure 1: The state store of the PoA module is defined by three parts, one for the validator store, one for the username store, and the third to store the general chain properties. The keys are constructed as the concatenation of POA_MODULE_ID || Storage Prefix || Storage Key.

Validator Store

The validator objects of the registered authorities are stored as distinct key-value entries in the key-value store of the PoA module. For every entry, the key is given by POA_MODULE_ID || PREFIX_VALIDATOR_STORE || hash(address) where address is the address of the user account registered as validator, either in the genesis block or with an authority registration transaction and hash() is the SHA-256 hash function.
The value is the validatorObject object, serialized according to the validatorObjectSchema schema, containing the username property:

  • username: A string representing the validator username, with a minimum length of 1 character and a maximum length of 20 characters.
Validator Object Schema
validatorObjectSchema = {
   "type": "object",
   "properties": {
      "username": {
         "dataType": "string",
         "fieldNumber": 1
      }
   },
   "required": [
      "username"
   ]
}
Username Store

The username store is an auxiliary store used to validate authority registration transactions. The key of this store is given by POA_MODULE_ID || PREFIX_USERNAME_STORE || hash(username) where username, serialized as a utf-8 encoded string, is the username of the validator as given in the genesis block or with an authority registration transaction.
The value is the address of the user account registered as validator serialized according to the validatorAddressSchema schema.

Validator Address Schema
validatorAddressSchema = {
   "type": "object",
   "properties": {
      "address": {
         "dataType": "bytes",
         "fieldNumber": 1
      }
   },
   "required": [
      "address"
   ]
}
Chain Properties

The general chain properties are stored in a single key-value entry. The key is POA_MODULE_ID || PREFIX_CHAIN_STORE || EMPTY_HASH.
The value is a serialized object with the following properties:

  • roundLength: An integer stating the total number of blocks in a round. It has to be less than or equal to MAX_NUM_VALIDATORS.
  • validatorAddresses: An array of pairwise distinct 20-bytes addresses in lexicographical order and of length roundLength.
    It specifies the set of active validators in the chain.
  • weights: An array of positive integers of the same size as the validatorAddresses property where each element is the weight of the corresponding validator in validatorAddresses.
  • threshold: An integer stating the weight threshold for finality in the BFT consensus protocol and the weight threshold needed for authority update transactions.
  • validatorsUpdateNonce: An integer representing the number of times that the validator set has been updated with an authority update transaction.
    It is initialized to 0.
Chain Properties Schema
chainPropSchema = {
   "type": "object",
   "properties": {
      "roundLength": {
         "dataType": "uint32",
         "fieldNumber": 1
      },
      "validatorAddresses": {
         "type": "array",
         "items": {
            "dataType": "bytes"
         },
         "fieldNumber": 2
      },
      "weights": {
         "type": "array",
         "items": {
            "dataType": "uint64"
         },
         "fieldNumber": 3
      },
      "threshold": {
         "dataType": "uint64",
         "fieldNumber": 4
      },
      "validatorsUpdateNonce": {
         "dataType": "uint32",
         "fieldNumber": 5
      }
   },
   "required": [
      "roundLength",
      "validatorAddresses",
      "weights",
      "threshold",
      "validatorsUpdateNonce"
   ]
}

Block Generation, Validation and Processing in PoA Chains

The block schema, generation process, validity rules and processing are defined outside of the PoA module (and the DPoS module) and are therefore not affected by the choice between DPoS and PoA modules. Similarly to the DPoS module, the PoA module will provide a list of forgers of a round to the consensus layer so that the corresponding validation happens there. Below we only list some clarifications in this regard and the particularities in the genesis block of PoA chains.

Genesis Block

The schema and rules of the first block b of a PoA chain will be specified in a future LIP. In particular, it sets an initial chainProp object in its asset as:

  • The roundLength property has to be a positive integer less than or equal to MAX_NUM_VALIDATORS.

  • The validatorAddresses array has to contain pairwise distinct 20-bytes addresses in lexicographical order and must have length roundLength.

  • The weights array is of the same size as the validatorAddresses property and contains positive integers.

  • Let totalWeight be the sum of every element in the weights array. Then totalWeight has to be less than or equal to MAX_UINT64.

  • The threshold property is an integer in the following range:

    • Minimum value: ⌊ ⅓ × totalWeight⌋+ 1
    • Maximum value: totalWeight

    where ⌊⋅⌋ is the floor function.

  • The validatorsUpdateNonce property is set to 0.

Validator Selection and Round System

In the Lisk PoA system, blocks are grouped together into batches of roundLength consecutive blocks, which are referred to as a round. The PoA module provides a list of forging validators, the forger list, for every round to the consensus layer similarly to the DPoS module. Let forgers be the forger list of a round r and chainProp the chain properties object of the PoA module at round r - 2. Then forgers is computed as follows:

  1. Put the address of every element in the chainProp.validatorAddresses array into forgers.addresses and every element in the chainProp.weights array into forgers.weights.
  2. Get the random seed randomSeed1 for height h computed as specified in LIP 0022 but generalized for any value of roundLength instead of 103.
  3. Sort forgers respect to forgers.addresses with randomSeed1 as defined by the shuffling algorithm in LIP 0003.
  4. Call the corresponding reducers from the consensus and block slot validation layers to set the new ordered validators list with their corresponding weights (when needed).

Authority Registration Transaction

This transaction is equivalent to the delegate registration transaction in the DPoS module and has the same schema and similar validity rules. The assetID of this transaction is 0.

Transaction Asset Validity

Let trs be the authority registration transaction to be validated, then:

  • The trs.asset.username property has to contain only characters from the set [a-z0-9!@$&_.], must not be empty and has to be at most MAX_LENGTH_USERNAME characters long.
  • The value of trs.asset.username must not already be registered as a validator username. This is, the store has no entry with storage prefix equal to PREFIX_USERNAME_STORE and storage key equal to hash(trs.asset.username), where trs.asset.username is serialized as a utf-8 encoded string.
Transaction Application

When this transaction is applied, new entries for the validator store and the username store are added to the key-value store of the PoA module as specified above.

Authority Update Transaction

The assetID of this transaction is 1.

Transaction Asset Schema
updateValidatorAsset = {
   "type": "object",
   "properties": {
      "validatorAddresses": {
         "type": "array",
         "items": {
            "dataType": "bytes"
         },
         "fieldNumber": 1
      },
      "weights": {
         "type": "array",
         "items": {
            "dataType": "uint64"
         },
         "fieldNumber": 2
      },
      "threshold": {
         "dataType": "uint64",
         "fieldNumber": 3
      },
      "validatorsUpdateNonce": {
         "dataType": "uint32",
         "fieldNumber": 4
      },
      "signature": {
         "dataType": "bytes",
         "fieldNumber": 5
      },
      "aggregationBits": {
         "dataType": "bytes",
         "fieldNumber": 6
      }
   },
   "required": [
      "validatorAddresses",
      "weights",
      "threshold",
      "validatorsUpdateNonce",
      "signature",
      "aggregationBits"
   ]
}

Transaction Asset Validity

Let trs be the authority update transaction to be validated and chainProp the chain properties object of the PoA module. Then the validity rules specific to the asset of trs are:

  • Rules for trs.asset.validatorAddresses array:

    • The array must have at least 1 element and at most MAX_NUM_VALIDATORS elements.
    • The array must be ordered lexicographically.
    • Each element is a unique 20-bytes address.
    • The account represented by each address is a registered validator.
  • Rules for trs.asset.weights array:

    • The array must have the same number of elements as trs.asset.validatorAddresses.
    • Each element is a positive integer.
    • Let totalWeight be the sum of every element in the trs.asset.weights array. Then totalWeight has to be less than or equal to MAX_UINT64.

    Note that the elements in this array correspond one to one to the elements in the trs.asset.validatorAddresses array in the same order.

  • Rules for trs.asset.threshold property:

    • The value of trs.asset.threshold is within the following range:

      • Minimum value: ⌊ ⅓ × totalWeight⌋+ 1
      • Maximum value: totalWeight

      where ⌊⋅⌋ is the floor function.

  • Rules for trs.asset.validatorsUpdateNonce property:

    • The value of trs.asset.validatorsUpdateNonce has to be equal to chainProp.validatorsUpdateNonce.
  • Rules for trs.asset.aggregationBits and trs.asset.signature properties:

    • The function verifyWeightedAggSig(keyList, tag, netID, aggregationBits, signature, weights, threshold, message), specified in the BLS signatures LIP, must return VALID where:

      • The keyList argument is an array with the BLS public keys of the current validators of the chain.
      • The tag is equal to POA_MESSAGE_TAG.
      • The netID byte array corresponds to the network ID of the chain.
      • The aggregationBits argument is the byte array given in trs.asset.aggregationBits.
      • The signature argument is the aggregate signature given in trs.asset.signature.
      • The weights argument contains the weights of the current validators of the chain.
      • The threshold argument is the current certificate threshold of the chain.
      • The message argument is the output bytes of the serialization, as specified in LIP 0027, of trs.asset.validatorAddresses, trs.asset.weights, trs.asset.validatorsUpdateNonce, and trs.asset.threshold properties according to the following schema:
      validatorSignatureMessage = {
          "type": "object",
          "properties": {
              "validatorAddresses": {
         	    "type": "array",
                  "items": {
         	        "dataType": "bytes",
                  },
                  "fieldNumber": 1
              },
         	"weights": {
      	    "type": "array",
         	    "items": {
          		 "dataType": "uint64",
          	    },
                  "fieldNumber": 2
       	},
       	"threshold": {
                  "dataType": "uint64",
             	    "fieldNumber": 3
       	},
       	"validatorsUpdateNonce": {
             	    "dataType": "uint32",
            	    "fieldNumber": 4
       	},
          },
          "required": [
              "validatorAddresses",
              "weights",
              "threshold",
              "validatorsUpdateNonce"
          ]
      }
      
Transaction Application

Let trs be the authority update transaction to be processed and chainProp the chain properties object of the PoA module. Then processing trs has the following effect:

  • The chainProp.validatorAddresses array is set to trs.asset.validatorAddresses.
  • The chainProp.weights array is set to trs.asset.weights.
  • The chainProp.validatorsUpdateNonce property is set to trs.asset.validatorsUpdateNonce + 1.
  • The chainProp.roundLength property is set to trs.asset.validatorAddresses.length.
  • The chainProp.threshold property is set to the value of the trs.asset.threshold property of the transaction.

Backwards Compatibility

This LIP introduces a new module for sidechains in the Lisk ecosystem. As such it does not affect any existing chain, hence it does not imply any incompatibilities.

1 Like

I have updated the of the use of the verifyWeightedAggSig function to the new interface as per the specs in BLS signatures LIP