Bitcoin and cryptocurrencies, in general, have been revolutionary new technologies in recent times. Over the past few years, people have been growing skeptical not just of governments and central authorities but also of large corporations such as big banks and technology companies. These corporations, in many cases, have cornered a large share of the market and act as de facto central authorities giving them a lot of power.
The reason why cryptocurrencies are so popular is because of their inherent decentralized nature. What it means is that no single entity, group of entities or individuals control the system. The system is, rather, controlled by all the participants together. This, of course, sounds highly messy as it potentially involves millions of people. That is the reason why most systems have one central authority in power, as it makes the functioning of the system smooth.
Importance of consensus protocols
The way cryptocurrencies dealt with this issue was by coming up with protocols that assured a ‘consensus’ among participants. This is by far the most critical component of the entire decentralized system of cryptocurrencies. In fact, in the very first white paper published by Satoshi Nakamoto on Bitcoin in 2008, the conclusion emphasized achieving consensus as seen below.
Snippet from Satoshi Nakamoto’s White Paper on Bitcoin
Now there are a lot of different consensus protocols used across different cryptocurrencies. Bitcoin, for example, uses the ‘proof of work’ protocol. These protocols are ‘byzantine fault-tolerant.’ The objective of Byzantine fault tolerance is to be able to defend against failures of system components that prevent other components of the system from reaching an agreement among them, where such an agreement is needed for the correct operation of the system.
This is really critical to the workability of Blockchain and, hence, cryptocurrencies. Unlike the conventional financial payment systems like Visa, there is no central authority to validate; if the system fails once, it will fail permanently.
In fact, in the very first white paper on bitcoin written by Satoshi Nakamoto, the BFT protocol was critical to creating the proof of work concept. BFT is also used in large and critical systems like airplane engines and even nuclear reactors. Essentially it is a protocol useful wherever the decisions depend on the inputs of a large set of sensors. Several algorithms have been designed solely with the purpose of achieving Byzantine fault tolerance. These algorithms are then extensively used by several cryptocurrencies with further underlying protocols.
The Brooks–Iyengar algorithm is a hybrid algorithm working on distributed control when there is a significant amount of noisy data. The algorithm combines Byzantine agreement with sensor fusion, and in doing so, it bridges the gap between sensor fusion and Byzantine fault tolerance. We already saw above what byzantine fault tolerance represents. Similarly, sensor fusion is the process of combining sensory data or data derived from disparate sources such that the resulting information has less uncertainty than would be possible when these sources were used individually.
The way the algorithm works is by having each node in the array take inputs from the other nodes and then arrive at the expected value based on the average. Let us call these nodes Processing Elements (PE). Each PE will calculate its respective value based on a weighted average of the inputs received from other nodes. At this point, you can eliminate any sensors with high variance or use heuristics to choose reliable nodes. It runs in O(NlogN) time and can handle up to N/3 faulty sensors.
Understanding the Brooks-Iyengar algorithm with an example
As seen below, the example assumes different sensors that meter the energy levels. Now each of these meters is recording values, but it might be the case that one or more than one of these sensors is faulty. So, instead of each sensor individually sending its inputs to the plant, an intermediate step is added. In this step, each sensor also receives the data from the other sensors. This is effectively multi-sensor fusion.
Now, rather than sending their respective meter readings, these sensors arrive at a reading that takes a weighted average of both the values sent by other sensors as well as their limits. These levels are then stored on a blockchain.
Brooks-Iyengar Implementation Schematic for an Energy Blockchain
The algorithm considers N processing elements (PEs), t of which might be faulty and, as a result, can behave in an unwanted manner. The algorithm either takes real values with a certain level of noise (known or unknown) or a real value that has a predetermined level of uncertainty or an interval as inputs.
The algorithm then gives a real value along with an interval of certainty as output. It runs in O (NlogN), where N, as discussed earlier, is the number of PEs. O(logN) complexity is usually achieved via making recursive calls of the same algorithm. So, effectively the algorithm is fairly scalable when it comes to dealing with a large data set. It is possible to modify this algorithm to correspond to Crusader’s Convergence Algorithm (CCA), but that will also increase the bandwidth requirement.
Evolution of various consensus algorithms
The Brooks-Iyengar algorithm was a breakthrough development in the field of consensus protocols. The Byzantine problem was conceived way back in 1982 and was, in turn, made from the modification of the two generals’ problem conceived several years prior to that.
In 1983 and 1985, the approximate and in-exact consensus protocols were conceived, respectively. For more than a decade after that, there was no breakthrough development in the field. This is why the Brooks-Iyengar algorithm is considered to be a seminal work.