_images/share.png

Consensus

_images/topology.png

Network Topology

Decentralization refers to the practice of maintaining database which is replicated (in whole or in parts) across many parties who participate in a consensus process to keep it synchronized and append new data to it.

Centralization refers to the practice of maintaining a database in which one party maintains the integrity of the database, orders transactions, verify transactions, and manages visibility and permissions. This intermediary manages a database centrally, provides accounts to all of the parties, and ensures that all operations are permitted according to a known set of rules. In many cases, especially financial, every party still maintains its own copy of the data, so everyone spends a lot of time checking that their databases agree. The trusted intermediary is often a single legal entity that is legally bound to it’s client to preserve privacy and integrity.

While centralization has the property of maintaining confidentiality and high throughput, it eliminates the key motivation of a blockchain solution and has no advantage over existing traditional databases and messaging platforms.

Federated Consensus

Consensus is the state of a distributed system where reads and writes yield consistent state to all observers. A state change in the system is called a transaction and the fundamental role of the consensus algorithm is to derive an immutable ordering of transactions. A transaction represents a single, atomic modification to the distributed ledger (database), and blocks in the network are collections of transactions; i.e. blocks contains immutably ordered atomic modifications to the database that are either accepted or rejected as a whole. Every time a block is accepted and its transactions are applied to the database, Uplink ensures that the database’s rules are followed. If any transaction in the block violates one of these rules, the entire block will be rejected with a corresponding error.

The main role of the consensus algorithm is to facilitate the agreement of what the next block in the blockchain should be. For a consensus algorithm to be useful, it must ensure that agreement is reached quickly and certainly, with the majority of the network always in agreement such that the generation and acceptance of new blocks (i.e. continual modification of the database) continues.

There are three forms of consistency of consensus algorithms:

  1. Weak Consistency: All accesses to synchronization variables are seen by all processes (or nodes, processors) in the same order (sequentially) - these are synchronization operations. But all other accesses may be seen in different order on different processes (or nodes, processors).
  2. Eventual Consistency: A is a specific form of weak consistency where the transaction engine guarantees that if no new updates are made to the state, eventually all accesses will return the last updated value. If no failures occur, the maximum size of the inconsistency window can be determined based on factors such as communication delays, the load on the system, and the number of replicas involved in the replication scheme.
  3. Strong Consistency: All accesses are seen by all parallel processes (or nodes, processors, etc.) in the same order (sequentially).

The two properties discussed when choosing a consensus algorithm to order transactions are:

  1. Byzantine Fault Tolerance: The property that consensus must hold in the presence of many faulty, malicious or badly connected nodes in the network.
  2. Sybil Attacks: The property that consensus must hold even in a network with many nodes with faked or forged identities.

Transaction Speed

The current implementation of the Uplink federated consensus algorithm is capable of achieving end-to-end throughput of 42000 transactions per second in standard network configurations with sub-second latency.

Federated Consensus

_images/consensus.png

Federated consensus is a simple consensus algorithm where specific nodes, denoted validating nodes (or validators), are designated to generate and sign new blocks given certain validation predicates defined by configurable consensus parameters hold. All transactions in the network are submitted to the validators and all blocks generated in the network originate from a validating node. However, before a block is broadcast to the entire network, the node that generated the block must first broadcast the block to all the validating nodes such that the block can be signed by a configurable threshold number of validating nodes before the network will accept the block as valid.

Since signing blocks is a computationally cheap operation in comparison to Proof of Work, blocks can be created at a high rate. Thus, a configurable block-period between two blocks is specified such that validators only attempt to generate a block when this specified amount of time has elapsed since the last block generated.

Overview:

Adjoint’s federated consensus algorithm is implemented with a simple, comprehensive, and resilient protocol that allows Uplink to achieve consensus about new blocks and distributed ledger state quickly and safely. This allows the network high transaction throughput without compromising important security elements that are necessarily enforced during the lifetime of a private distributed ledger.

Designed with network and data security as priorities, Uplinks federated consensus algorithm was influenced by surveying modern consensus research and other popular consensus algorithms and protocols used in the blockchain space. After extensive research, Uplink’s consensus algorithm has been implemented to adhere to the distinct needs of the private distributed ledger space, specifically for the financial domain of structured products trading supplemented by a powerful smart contract engine.

An high level specification of the consensus algorithm follows below.


Consensus Parameters:

The consensus algorithm parameters are configurable and determine the behavior of the validator nodes with respect to block generation, and also determine how blocks should be assessed for validity in the network. These parameters are stored in the block header, thus the latest block in the chain determines the parameters with which the validity of the next block should be validated.

Validator Set:
A list of addresses of validating nodes in the network
Block Period:
The elapsed time specifying how long a validating node will wait inbetween attempting to generate a new block
Block Generation Limit:
The number of consecutive blocks in which a validating node can generate a block
Block Signing Limit:
The number of consecutive blocks in which a validating node can sign a block
Threshold:
The number of validator signatures a block must receive
Mininum Transactions:
The minimum number of transactions a block must contain

Consensus State:

The ConsensusState is a data structure all validating nodes store to reduce competition between validators when generating and signing blocks, and to limit redundant generation of blocks. The state contains two fields:

Previous Signed Block Index:
If a validator has already signed a block with the same index as another validator is requesting it to sign, it will not sign the block. This prevents multiple blocks of the same index racing to collect the threshold number of signatures.
Previous Generated Block Index:
If a validator has already generated a block and broadcast it to the other validators, it will not attempt to generate a new block of the same index. If the previously generated block was rejected by the other validators or did not receive enough signatures, the validator is effectively banned from attempting to generate a block with the same index.

Protocol:

Messages:

SignBlockMsg:
When a validating node receives a SignBlockMsg containing the block a fellow validating node is requesting signatures of, it validates the block with respect to chain rules, world state, and consensus protocol parameters.
BlockSigMsg:
When a validating node receives a BlockSigMsg containing a signature of the block it requested to be signed, the validator verifies the signature and adds the signature to the list of block signatures if it is valid.

Design:

There are two distinct processes running during the execution of Uplink’s consensus protocol (running on all validator nodes); The block generation process, and the block signing process.

Block Generation Process:
The validator attempts to generate a block with the current transactions in it’s mempool, after checking that the poa-state and previous block’s poa parameter predicates are satisfied. This process broadcasts potentially valid blocks to the set of validators using SignBlockMsg and waits for other validators to respond with a BlockSigMsg.
Block Signing Process:
The validator verifies the received block is valid, and signs it’s header if the poa-state and previous block’s poa parameter predicates are satisfied. This process receives a SignBlockMsg and responds to the send with a BlockSigMsg if the block is valid.

Validation:

In order for blocks to be considered valid, they must satisfy many predicates, determined by the consensus protocol parameters, the chain rules (consensus agnostic datastructure validation rules), and the world state. This section will give an overview of validation predicates enforced by the consensus protocol. All of the predicates listed below originate from fields in the last accepted block’s poa parameters.

Origin:
The block origin must be a valid address existing in the validatorSet field.
Number of Signatures:
The block must contain a number of signatures of the block header equal to or greater than the threshold field.
Signature Integrity:
The set of block signatures must not contain a signature from a validating node that has signed a block in the past (blockSignLimit - 1) blocks.
Transactions:
The block must contain a minimum number of transactions specified in the minTxs field.
Timestamp:
The block timestamp must be equal to or greater than the previous block’s timestamp, plus blockPeriod milliseconds.
Validator Address (Origin):
The block must not be generated by a validator that has generated a block in the past (blockGenLimit - 1) blocks.

Security

Many consensus protocols come with a well-known assumption which stipulates that at least 3f + 1 nodes are necessary to reach consensus in the presence of up to f Byzantine faulty nodes. In practice, this number is determined by the parameters of the consensus algorithm outlined above.

There are two canonical properties of distributed systems consensus algorithms that are important to maintain throughout the lifetime of a private distributed ledger network: safety and liveness.

Safety:

The property of a blockchain protocol such that there is no dispute to which block is the correct block at a particular index. Each node in the network can verify and validate, without question, the integrity of a given block and whether or not it is the next valid block in the chain. This property also asserts that states in which consensus is not achievable do not occur given certain network invariants; i.e. the algorithm does not get “stuck”.

Furthermore, Uplink’s consensus algorithm has additional guarantees of safety resulting from the blockGenLimit and blockSignLimit parameters of the algorithm; The former limiting the number of blocks validating nodes can generate, and the latter limiting the number of blocks validating nodes can sign.

Liveness:
The property of a blockchain protocol such that eventually new blocks will be generated. Like safety, the liveness property is only guaranteed given certain network invariants (outlined below).

Let \(s\) be the signer limit or the number of consecutive blocks out of which a validator may sign one block.

Let \(g\) be the generator limit or the number of consecutive blocks out of which a validator may generate one block.

Let \(N\) be the number of validating nodes.

Let \(M\) be the number of signatures that denote a valid block.

Safety of Uplink’s Consensus Protocol:

In Uplink’s consensus algorithm, the safety property that two blocks will never be considered “correct” at an arbitrary height of the chain holds if and only if:

  • The number of malicious validating nodes is less than the number of signatures denoting a valid block \(M\). This means that malicious validators cannot coordinate to validate an invalid block by signing an invalid block.
  • The number of malicious validating nodes is less than \(N / g\). I.e. a malicious node cannot dominate the block generation process.

Liveness of Uplink’s Consensus Protocol:

Liveness is the property that the Uplink network will always, eventually progress; In other words, new blocks will always be generated. Liveness of Uplink’s federated consensus protocol is guaranteed if and only if:

  • The number of validators, \(N\), is greater than the number of signatures \(M\) denoting a valid block.
  • The number of validators, \(N\), is greater than the generator limit \(g\). I.e. there will always be a validator that is allowed to generate a block.
  • The number of validators, \(N\), divided by the threshold \(M\), is greater than \(s\), the signer limit. I.e. there will always be enough validators to sign a block

Attack Vectors

At any point during the lifetime of the network one or several validator nodes may be comprised. This can only happen in the event that a private key of a validator node is compromised due to a lapse in security of a counter party. The proprietary version of Uplink’s federated consensus includes a voting mechanism in which set of validator nodes can be modified via a voting mechanism, and will provide even more security for counterparties involved in the network. However, without this mechanism, Uplink’s federated consensus still provides an impressive amount of security.

As mentioned previously, there are several known attack vectors that result unavoidably from the design and construction of consensus algorithm. This section explains these attack vectors and describes how Uplink’s public federated consensus algorithm circumvents these vectors with nuances in the algorithm such that these attack vectors cannot be used to compromise the network, or the guarantees of the consensus algorithm such as safety and liveness.

Let \(m\) be the number of malicious validators in the network.

Let \(p\) be the number of trusted validators in the network.

Let \(s\) be the number of blocks that must come between each block signed by an individual validator.

Let \(k\) be the number of blocks that must come between each block generated by an individual validator.

Spamming Signer:
A malicious signer may sign more blocks than allowed by the \(s\) parameter. In this case, blocks generated by trusted validator nodes at the same block height may concurrently have the number of signatures required and there will be contention (potentially a soft-fork). This is resolved in two ways; First, a randomized wait period is generated by each node and added to the block period such that there is a low probability validator nodes will generate a block at the same height at the same time. In addition to this, if a soft for does happen, there is an addition block-scoring mechanism such that the next block mined at a larger index will override the previous block accepted by nodes on the other side of the fork. Soft forks are guaranteed to be eventually resolved, in practice, within the next 1-2 blocks generated by the network.
Spamming Generator:
A malicious validator node may begin to generate blocks faster than the designated block period. Uncontested, this would allow the malicious generator to starve the rest of the network by generating blocks with transactions that serve on the interest of the malicious validator. This attack is circumvented by only allowing validator nodes to generate 1 block out of every \(k\) blocks. In this case, \(m >= (k - 1)\) would have to hold, i.e. the number of malicious nodes would have to be equal to or greater than the number of blocks a validator must wait to sign a single block.
Malicious Signer:
A malicious validator node may sign invalid blocks. As long as the number of malicious signers \(m\) is less than the number of signatures \(s\) required for a block to be valid \(m < s\), there will be no effect on the network as long as malicious signers also sign valid blocks. Given trusted validators \(p\), as long as \(p >= s\), the number of
Malicious Generator:
A malicious validator node may attempt to generate invalid blocks. In this case, the network will simply reject the invalid blocks, and other validator nodes will not sign the block. This will have no effect on the network as long as \(m < s\).

Quorum Generation

To generate an initial consortium key set, use the key generation utility and specify the number of validators:

$ uplink keys --a 1
Using configuration: config/node.config
Writing account
FdHbo2JbWnjYtHUUgviBCFyoHLa5pPJ1mMCwFM5T95E6
Writing account
Ajf9Ryr86TisQ6PQHwdFWmprqFA4hRCdarBgHkEkAL2m
Writing account
FZXcX2YUFoo8DvtrpSrcH5FFJTWqy1jePVZ8N8sCj7r

The list of validators addresses is then hashed into the genesis block of the chain and provides the entropy seed for the genesis block, thus uniquely identifying the chain and providing a single proof for existence of the validator pool.