Notions In Distributed Computing And Blockchain Technology
This is a slightly technical article compared to the old ones that I have published thus far. Itry to present here the summary of abstract notions that are relevant to blockchain technology. I start by the classical Consensus and we travel to the Nakamoto consensus that defies the FLP possibility. After that, Ilist terms related to scalability and Security.
Classical Consensus in distributed computing
Consensus among different processes in a distributed network is a fundamental requirement for a wide range of applications. The agreement dictates that the processes coordinate to reach a common understanding and then take certain actions.
Definition: Process failure models
Fail-stop an operative process might fail by stopping the execution. Other processes could acknowledge that failure.
Crash an operative process might fail by stopping the execution. Unlike the fail-stop model, other processes do not learn of this crash.
Byzantine or malicious failure a process may exhibit any arbitrary behavior and no authentication techniques are applicable to verify any claims made.
Definition: Overview of the system
Among the n processes in the system, at most f processes can be faulty. A faulty process can behave in any manner allowed by the failure model assumed. The various failure models, i.e. fail-stop, and Byzantine failures.
Definition: The consensus problem
Each process has an initial value and all the correct processes must agree on a single value, formally:
Validity: If all the non-faulty processes have the same initial value, then the agreed-upon value by all the non-faulty processes must be that same value.
Agreement: All non-faulty processes must agree on the same value.
Termination: Each non-faulty process must eventually decide on a value.
Definition: Synchronous system Vs. Asynchronous system
A synchronous system is a system that has a known bounded: message latency, drift rate for the local clock of each processor and time to execute each process. An asynchronous system is a system in which none of the above three properties of synchronous systems are satisfied
Definition: Impossibility result for the consensus problem in the Asynchronous systems
Fisher, Lynch, and Patterson (FLP) showed the impossibility of reaching agreement in an asynchronous system, even if a single process is allowed to have a crash failure.
Definition: Solving the FLP impossibility result by Randomized consensus
Fault-tolerant randomized distributed algorithms permit to solve the FLP impossibility. The field was created in 1983.
THE NAKAMOTO consensus in distributed computing
The Nakamoto consensus presented the ability for anonymous processes to participate in the consensus protocol via proof-of-work mining. The algorithm was able to solve the diverse parts of the FLP impossibility. A process could be anonymous and diffuse a valid solution to the rest of the network. Such a model open the doors to a new type of “setting described as “permissionless”.
A simplified version of the Nakamoto Consensus based on the Monte Carlo randomized can be considered like the this :
Validity: The output value must be one of the inputs (with non-negligible probability)
·Agreement: All correct processes must agree on the same value, except with negligible probability.
Termination: All correct processes must output a single value after a bounded time
Scalability in Blockchain technology
By definition “Scalability is the capability of a system to handle an increasing amount of work”. It is in fact, the correlation of several parameters and metrics. In the context of Blockchain, we can define scalability as, the ability to achieve a target throughput and latency in the presence of increasing workload while maintaining the decentralization nature. The next section explicit the bottlenecks factors that limit the Blockchain scaling.
Storing: The Blockchain’s log structure states that all state changes are recorded in the blockchain since the Genesis Block. All nodes need to maintain a full copy of the blockchain, limiting the total size to the current hardware capacity.
Network latency: The validation of new blocks is limited by the Blockchain’s write propagation and leader-election protocol.
Bandwidth/Block size: The total number of transactions per block is limited by the block size of the Blockchain.
Transaction Cost: Transaction cost include the amounts associated with bandwidth, storage, fees, and mining.
Energy consumption: The exponential increase in energy consumption to mine new blocks is a major concern.
Infinite Ledger: The public aspect of the Blockchain depends on the ability to retrieve the whole ledger. As it grows, the capability to newly join the network would be more and more time-consuming.
Scalable Blockchain promise to (1) enable services that achieve comparable performance as mainstream technologies, (2) support novel applications and (3) support a large number of users.
Security issues in Blockchain Technology
To understand the inherent security risks in blockchain technology we present different potential attacks.
Sniffing: A passive observation of transactions
Sybil attack: An attacker might be in control of some nodes in the blockchain network.
Time jacking: The ability to slow or speed up the network. It can manipulate a node’s timestamp.
Denial of Service: Spamming a node with excess data may disable a node from making progress. It might reduce its ability or even stop it from processing transactions.
Malicious node code: Any aberration might lead to other clients adopting the same and eventual propagation of erroneous or malicious code.
False forking: An attacker can mine a block and would lead to a false segmentation of the network.
Hash power: The attacker manages to obtain more hash power than all the other nodes in the network combined
References
“distributed Computing Principles, Algorithms, And Systems”, Ajay D. Kshemkalyani And Mukesh Singhal, Cambridge Press March 2011.
“preventing The 51%-attack: A Stochastic Analysis Of Two Phase Proof Of Work In Bitcoin”, Martijn Bastiaan , June 2015.
“blocks And Chains: Introduction To Bitcoin, Cryptocurrencies, And Their Consensus Mechanisms” Aljosha Judmayer , Nicholas Stifter ,katharina Krombholz , Morgan And Claypool, June 2017
