Blockchain technology has been criticized for low transaction throughput, without which no blockchain implementation can service any mass market product with large numbers of concurrent users. Individuals are accustomed to instantly purchasing a good or a service with cash or credit card; no fully decentralized blockchain implementation currently supports that kind of real time financial transaction. Notable high-throughput networks such as Ripple and IOTA have centralization: privileged nodes which act as masters to the unprivileged public nodes. Those master nodes present a security vulnerability as they can be hacked, or subpoenaed by state actors. This blog reviews a new consensus algorithm, [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV), which serves fully permissioned and fully decentralized blockchain implementations. Such a blockchain is a network without any single points of failure (as there is no centralized control) and all nodes are assumed to be faithfully executing the network protocol correctly; otherwise they would not have been granted permission to join and to remain in the network. [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) is actually the foundation of a family of blockchain consensus algorithms, derived and originally published by an anonymous group calling themselves Team Rocket. Despite its limitation to fully permissioned blockchains, [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) provides the reader with a wealth of insight into decentralized algorithms, and the statistical methods employed to analyze their correctness and their performance. This algorithm will therefore be the subject of the remainder of this blog. Note, however, that Team Rocket has extended this algorithm in three different ways, to create three other blockchain consensus algorithms - for entirely public, and entirely decentralized blockchains. These three extensions [have been empirically shown](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) to attain a throughput of a couple thousand transactions per second, with only a few milliseconds of latency. ## What Is Slush? How Does It Work? Like most blockchain implementations, all nodes store their own copy of the ledger. Unlike most blockchain consensus algorithms, [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) employs an epidemic or gossip style of communication to spread updates throughout the system. Each node in the network faithfully executes the following algorithm to definitively approve or reject any incoming transaction. ![Slush Consensus Algorithm From The Node's Perspective](https://steemitimages.com/DQmPMQVybpTpaDHuiDAYS15zHrTiPrdPd3mszfDKnLnP6Lo/Slush_consensus_algorithm.png) The intuition for this consensus algorithm is found in the general framework of recursion. The recursive base case is when a node has already made a definitive decision regarding this transaction. The recursive step is when a node has not made a definitive decision, and it asks a partition or a subset of remaining nodes what their decision was, then takes the majority vote as its own decision. ***Implementation Detail*** In the flowchart or process chart above, the node which tentatively approves the transaction in absence of a definitive decision only replies with approval upon being queried by other nodes in the blockchain network. It does _not_ reply to the client with this tentative approval. It only replies with tentative approval to other nodes in the blockchain network to prevent an infinite recursion when none of the nodes have any definitive decision on this particular transaction. Once consensus has been reached on the blockchain, the client is certain to have received the correct reply as to whether or not their digitally signed transaction was definitively approved. #### Number Of Communication Requests Required To Achieve Consensus [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) defines consensus the same as all other blockchain consensus algorithms: agreement on the ledger, of which all nodes maintain a local copy. Therefore we are interested in the number of communication requests among nodes required for either all nodes to approve this transaction, or for all nodes to reject this transaction. Most blockchain consensus algorithms require as many communication requests among nodes as the _square_ of the total _N_ nodes in the network. [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) instead achieves consensus in _N log N_ communication requests among the total _N_ nodes in the network. ***Comparison Of This New Consensus Algorithm With Current Algorithms*** Consider the following hypothetical blockchain network sizes, and their respective numbers of communication requests among nodes required to reach consensus. Clearly, higher throughput will be readily achieved with this new and much more scalable consensus algorithm. | total network nodes | current consensus algorithms | [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) consensus algorithm | |--------|----------|----------| | 512 | 262 144 | 4 608| | 1 024 | 1 048 576 | 10 240 | | 2 048| 4 194 304 | 22 528 | | 4 096 | 16 777 216 | 49 152 | But how do we know that [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) is guaranteed to achieve consensus? And how do we know that it does so with _N log N_ communication requests among the total _N_ nodes in the network? It turns out that proving the scalability of the number of communication requests among nodes also proves that the algorithm achieves consensus. ### Why Does Slush Converge? How Fast Does It Converge? This analysis will proceed using a branch of statistics known as [stochastic processes](https://www.quora.com/What-is-a-stochastic-process-in-laymans-terms). Put plainly, a [stochastic process](https://www.quora.com/What-is-a-stochastic-process-in-laymans-terms) is a sequence of random variables where each variable in the sequence is dependent on the observed values of the previous variables. Think of it like [time series analysis](https://www.quora.com/What-is-time-series-analysis-What-are-its-advantages-and-disadvantages) on a person performing physical exercise: their heart rate is not only a function of the intensity of the activity, but is also a function of their heart rate in the past (including periods of inactivity). Within the [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) consensus algorithm, the number of nodes which approve or reject a particular transaction at a particular instant in time _t_ is dependent on the number of approving or rejecting nodes for that transaction at time _t - Δt_. Where _Δt_ can be an arbitrarily small difference in time for a fully decentralized and fully asynchronous algorithm such as [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV). Let us walk through a toy example to study this consensus algorithm in detail. Suppose there are only _9_ nodes in the network. Then a client submits a digitally signed transaction to an arbitrary node in the network. At any instant in time _t_, the number of nodes who have approved this transaction and used it to update their own copy of the ledger is anywhere between _0_ and _9_. And for sufficiently small _Δt_, only one node has received a complete response for its query - due to heterogeneous node hardware, heterogeneous network topology, non-uniform placements of nodes, etc. Then the number of approving nodes can either remain unchanged, or can change by exactly _1_ with every _Δt_. An intuitive diagram of all possible states for the number of nodes approving this transaction is simply ![Number Of Approving Nodes As A Random Walk](https://steemitimages.com/DQmYXXHr9aSmBUpyo4MBTdLCgHHq8FbQon1617tNZexea8e/update_acceptance_as_a_random_walk.png) where each of the gray circles represents state _S_, whose subscript indicates the number of nodes which have approved this transaction and used it to update their internal ledger. Directional lines indicate a transition from one state to another, with _R_ indicating the probability of remaining in the same state. _P_ indicates the probability of transitioning to a state where one additional node has approved this transaction; equivalently, one less node has rejected this transaction. _Q_ indicates the probability of transitioning to a state where one less node has approved this transaction; equivalently, one additional node has rejected this transaction. The consensus algorithm completes once either of all _9_ of the nodes in the network definitively approve this transaction, or once all _9_ nodes in the network definitively reject this transaction. The states at the two end-points of the diagram above are therefore called _absorbing states_, because the number of approving nodes for this transaction can no longer transition once it has entered either of these two absorbing states. With sufficiently small _Δt_ such that only one node in this blockchain network has received a complete response for its query, the number of communication requests among nodes can be analyzed using a fundamental tool of [stochastic processes](https://www.quora.com/What-is-a-stochastic-process-in-laymans-terms) known as [first-step analysis](https://www.quora.com/What-is-first-step-analysis-that-is-used-in-the-Gamblers-Ruin). [First-step analysis](https://www.quora.com/What-is-first-step-analysis-that-is-used-in-the-Gamblers-Ruin) exploits the fact that transitioning from one state to another requires the same _expected_ amount of steps as transitioning from the immediately following state to the desired "other state," plus _1_ to account for the transition that just happened. It is therefore a particular instantiation of the mathematical tool commonly known as [proof by induction](https://www.khanacademy.org/math/algebra-home/alg-series-and-induction/alg-induction/v/proof-by-induction). #### Expected Number Of Communication Requests To Approve Or Reject A Transaction Using the immediately preceding state diagram, let _U_ denote the _expected_ number of steps to reach either of the two _absorbing states_; and note that reaching one precludes ever reaching the other. Let the subscripts on _U_ indicate the current state in the diagram from which we are transitioning to either of the two _absorbing states_. Then the _expected_ number of communication requests to approve or reject a transaction is derived using [first-step analysis](https://www.quora.com/What-is-first-step-analysis-that-is-used-in-the-Gamblers-Ruin) ![Slush Expected Number Of Communication Requests](https://cdn.steemitimages.com/DQmWzksTYz1qE1iAAzXrBc8Te4gZd9fpQuARXqgzyFtWsuT/Slush_expected_communication_rounds.png) which may look daunting but is actually guaranteed to have a solution because there are as many unknowns as there are equations - eight values of _U_ and eight equalities. In general, for a network with _N_ total nodes, there will be _N-1_ unknowns and _N-1_ equalities so there will always be a solution for arbitrary sized blockchain networks. Intuitively, the equations above say that the blockchain network whose consensus is governed by this particular algorithm is guaranteed to reach consensus - because the system of equations has a solution which means the state of the network will eventually be either unanimous approval or unanimous rejection. These equations also say that transitioning from one state to the next costs exactly _k_ communication requests, where _k_ is manually set at the protocol level and its function is detailed in the flowchart diagram of the per node algorithm that must be faithfully executed asynchronously by every node in this network. When dealing with a [stochastic processes](https://www.quora.com/What-is-a-stochastic-process-in-laymans-terms), it is always necessary to question whether the eventuality of reaching an _absorbing state_ will take a finite amount of time or steps. It is a subtle distinction, but guaranteeing that the equations have a solution only guarantees that an _absorbing state_ will be reached within a (possibly infinite) amount of time or number of steps. Team Rocket, the authors of [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) and its three extensions, therefore present proofs that this eventuality does indeed occur in _finite_ time and therefore _finite_ number of steps. ***What are the exact quantities of the transition probabilities?*** In order to understand the proofs of consensus in finite time and finite steps, it is immensely helpful to understand how the transition probabilities are defined. Team Rocket does not explain or derive these transition probabilities. Therefore their proofs can be difficult to reproduce without first stepping back and looking at this core component of all their equations and inequalities. Within a sufficiently small _Δt_ such that only one node in this blockchain network has received a complete response for its query, this single node can switch its rejection of a digitally signed transaction to an approval with probability *P* or it can switch its approval of the same digitally signed transaction to a rejection with probability *Q*, where ![Slush Transition Probability P](https://steemitimages.com/DQmPGXA5KVBFutLKa5FcDC4uyRWh3M9YtUo139F9wVD2k37/Slush_transition_probability_P.png) ![Slush Transition Probability Q](https://steemitimages.com/DQmVrxuxFpjS6v4btdG9H41tFuNiJvMd2wb4GeQQrqUJ1Fj/Slush_transition_probability_Q.png) and the only other option this single node has is to remain with its current decision of approval or rejection with probability *R*, where ![Slush Transition Probability R](https://steemitimages.com/DQmZdNkoCVJjCEZSR94QfCqfBfGP2mNSFv4YNbSB2LhvYa3/Slush_transition_probability_R.png) and where the number of nodes in the network which currently approve this transaction is indicated by the subscript _i_. This is relevant because the probability that this single node is one which rejects the transaction is _(N - i) / N_ whereas the probability that this single node is one which approves the transaction is _i / N_ for a network with _N_ total nodes. This stems from the _a priori_ assumption that any node in the blockchain network is equally likely to be the one which receives a complete response to its query within sufficiently small _Δt_. [Slush](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) consensus algorithm specifies precisely in what conditions peers tell the current node to approve this transaction: when more than half of them have themselves approved this transaction. The transition probabilities are therefore equal to ![Slush Transition Probability P](https://steemitimages.com/DQmXvMecY6h4iuH4DXTou7D5vNiWU9amYLS1YnWZdBoHwLB/Slush_transition_probability_P.png) ![Slush Transition Probability Q](https://steemitimages.com/DQmXxBH73q2aWAidh52PZ1jMRtNaUJHHKVcQ3vqY9vBf7c1/Slush_transition_probability_Q.png) ![Slush Transition Probability R](https://steemitimages.com/DQmTVpK31FGEpWjdWswr6E2bYXzKRxmF8Tz1GjR7eKAD49X/Slush_transition_probability_R.png) where the probability that querying _k_ out of the total _N_ nodes in the network results in _c_ nodes approving this transaction follows a [Hypergeometric distribution](https://en.wikipedia.org/wiki/Hypergeometric_distribution) because at the instant the query is made, no two nodes are identical, and the total number of nodes which have approved this transaction is _i_. The probability that more than half of queried peers approve of this transaction is therefore given by ![Slush Probability Of Peers Approving As Sum Of Hypergeometric Random Variables](https://steemitimages.com/DQmbfQCKVmoA22k8xVfs6ZYhVMowobkH1jukZpmVcahTrhK/Slush_probability_of_peers_approving.png) and the probability that half or less of queried peers approve this transaction is its complement: computed by subtracting the above sum from _1_. With this depth of understanding, the reader is now encouraged to [study the original paper](https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV) by Team Rocket.

Topics