The blockchain concept forms the backbone of a new wave technology that promises to be deployed extensively in a wide variety of industrial and societal applications. In this article, we present the scientific foundations and technical strengths of this technology. Our emphasis is on blockchains that go beyond the original application to digital currencies such as bitcoin. We focus on the blockchain data structure and its characteristics; distributed consensus and mining; and different types of blockchain architectures. We conclude with a section on applications in industrial and societal settings, elaborating upon a few applications such as land registry ledger, tamper-proof academic transcripts, crowdfunding, and a supply chain B2B platform. We discuss what we believe are the important challenges in deploying the blockchain technology successfully in real-world settings.
Blockchain technology is promising to herald a new revolution in a rich variety of industrial and societal settings. In the timeline 2012-2015, the term blockchain was more of a buzzword; not any longer. Many important global businesses are trying to embrace the blockchain technology to find solutions to their difficult problems. Governments, financial institutions, banks, industrial supply chains, service companies, and even educational institutions and hospitals are investing substantial sums of money in the hope of improving business efficiency and operational robustness. Currently there are several hundreds of startups all over the world; India certainly has a few dozens of startups in the blockchain space. There are hundreds of whitepapers and well compiled technical reports available on the web and these documents provide the multidimensional impact and promise of the technology. Multiple books have been written; the one by Don Tapscott and Alex Tapscott [32] is one of the more prominent ones. The book by Antonopoulos [1], and, the book by Narayanan, Bonneau, Felten, Miller, and Goldfeder [25] provide an excellent, rigorous, and comprehensive introduction to cryptocurrency technologies.
Let us look at an enticing example, that of property titles in popular cities. For instance, the city of Bengaluru in India, popularly referred to as the Silicon Valley of India, is one of India’s most sought after cities to live in, and predictably, real estate prices have been skyrocketing at a furious pace. It is known that a good percentage of property titles may not be trustworthy, in fact, could even be fake. Further, titles and documents have often been fabricated or manipulated. There are many prominent layouts in trouble because of this problem and in many cases, the unsuspecting citizens go through hardships due to this problem. Imagine how socially good it would be if the land records were immutable, safely and securely stored in a distributed public ledger, and new data is allowed to be included only after consensus is reached among all stakeholders. If such a shared ledger were maintained, real estate related fraud could be eliminated. In fact, in the nations of Honduras, Ghana, and Republic of Georgia, startups have helped the Governments there to place all land titles in a secure ledger to ensure that property owners feel secure and assured about their landed properties.
Under the pseudonym Satoshi Nakamoto, an anonymous person or a group of persons wrote a brilliant paper [23] in 2008 in which the bitcoin digital currency was introduced. This paper introduced a simple but powerful data structure which Satoshi Nakamoto called the blockchain. Using this data structure which uses hashing to achieve immutability of data and through an intelligent design of incentives, the bitcoin revolution got launched with this paper. The bitcoin is now a household topic. In this paper, however, our interest is not on bitcoin but on the blockchain data structure which has characteristics that make it perfectly applicable to a rich set of possibilities beyond bitcoin. We explore these exciting possibilities that blockchains offer to numerous usecases in industrial and societal settings.
The objective of this paper is to gain a sound understanding of the various building blocks and foundational principles underlying blockchain technology. The trajectory we follow in this paper is as below.
This is a companion paper to the article “Cryptocurrencies: Science and Socio-Economics” by Veni Madhavan and Kumar Swamy [21] .
Disclaimer. In this article, we have included only a subset of essential references that we are aware of. There are hundreds of webpages, blogs, research papers, and whitepapers on blockchain technology, and numerous textbooks as well. We regret any important omissions.
A blockchain network is typically a peer-to-peer network where each node has computing resources and a data repository. The data repoitory at each node contains an an up-to-date copy of the blockchain.Figure 1 shows a picture of a blockchain network.
Figure 1: A Blockchain network
2.1 Blockchain Data Structure
The blockchain data structure is a structured collection or shared ledger of blocks. Figure 2 depicts a part of a typical blockchain. In this subsection, we describe the data structure that is used in the bitcoin blockchain, to bring out all essential features of a blockchain. A blockchain may contain any number of blocks. For example, the bitcoin blockchain (as of January 2018) contains more than 210000 blocks.
Figure 2: A Blockchain
As a data structure, a blockchain is a doubly linked list of the blocks. Thus, each block has a pointer to the next block as well as a pointer to the previous block. Each block contains the following:
- Data corresponding to a number of transactions. Each transaction may involve a small subset of nodes and is represented in some digital form. A block may contain any number of transactions. For example, a block in the bitcoin blockchain could contain hundreds of transactions.
- A hash value corresponding to the current block.
- A hash value corresponding to the previous block.
Each hash value above is also called proof-of-work for that block. Proof-of-work for a block is computed by solving a difficult cryptographic puzzle: this puzzle takes as input the transaction data of that block and produces a final hash value, after a very large number of hash computations, such that the final value that satisfies a certain criterion that is difficult to achieve (for example, the hash value should start with a string of four zeros, etc.). Because of the intensive nature of this computation and the massive amount of computational work involved in producing this final hash value, the latter is aptly called proof-of-work.
Since every block contains proof of work for the current block and proof-of-work for the previous block, the blockchain becomes virtually immutable. This is because, in order to modify a block, not only do you have to modify the current block but also all successive blocks.
Cryptographic Hash Functions
|
The data corresponding to each block is organized as a Merkle tree (shown in Figure 3). Merkle tree is a binary tree data structure where hashing is used to facilitate efficient verification of the contents of the tree (See Figure 3). The leaf nodes contain the hash values of individual transaction data. Each internal node contains only a hash value that is computed using the hash values contained in its children. The root node will thus contain a hash value which is called the root hash value. Given a Merkle tree, in order to verify that a given a set of transactions is precisely the same as the transactions stored in the Merkle tree, we only have to compute the hash value from the given transaction data and verify that the hash value is the same that of the root hash value in the given Merkle tree.
A new block is included into the blockchain using a process called mining which is described in the next section. Once a new block gets included, the updated blockchain becomes available at all the nodes. The manner in which the blockchain data structure is organized, updated, and
Figure 3: Merkle Tree
replicated ensures that the blockchain is a shared, synchronized, immutable, distributed ledger created through distributed consensus; all nodes have access to the ledger and can verify the truth. Simply speaking, the blockchain elegantly implements tamper-proof record keeping. The blockchain protocol is decentralized and eliminates the need for intermediation by trusted third parties. Blockchain technology thus represents a deep one that combines cryptography, data structuring, and distributed consensus in a brilliant way.
Distributed Consensus in Blockchains and the Byzantine Generals Problem
|
Blockchain technology provides a way to implement a distributed, shared ledger without the need for a central trusted entity or trusted third parties. Theere are other ways to implement a distributed, shared ledger but blockchain technology is superior to the existing approaches because of the above features.
2.2 Mining of Blocks
The addition of a new block to a blockchain is based on inverting a hash function, whose computational complexity is believed to grow exponentially in the length of the input. This process is known as mining (the word validation is also used but we prefer to use the word mining in this article). Mining secures the blockchain system from fraudulent transactions. Mining could be done by any node in the blockchain (in a public blockchain). The task of a miner is two fold : (1) to validate the data in the block and (2) to append the valid block to the already existing blockchain. Note that the success of the blockchain is attributed to the way mining is done i.e. how the verification of data is done in a decentralized, anonymous fashion. In the next two subsections, we present how this is achieved via the standarad process called proof-of-work and a modified process called proof-of-stake.
This section assumes a bitcoin type of (public) blockchain. However, the principles are relevant for other types of blockchains as well. For a detailed treatment of this topic, the reader is referred to [21], [25].
2.2.1 Proof-of-Work
The key idea behind proof-of-work is to make the selection of a miner in a way that nobody can monopolize the system by creating fake nodes. This is ensured in proof-of-work by making the nodes to compete to mine the block using their computation power. This would imply that no single node can monopolize the blockchain protocol as buying that much computation power would be next to impossible.
The proof-of-work is based on inverting a hash function where the hardness of the computation can be controlled. For example, in the bitcoin network, the parameters for proof-of-work are set in
a way that one block is mined in a certain time duration. This cryptographic computation is a hash function based computation where each miner is required to find a random numeric value nonce such that the cryptographic hash function of the nonce when combined with the data and the hash value of the previous block results in a hash value that is less then a specific target value. More specifically,
The hardness of this hash computation can be increased or decreased by adjusting the targetvalue appropriately. This targetvalue is adjusted automatically between the nodes in the blockchain so as to maintain the difficulty of mining to be a certain time duration (in the case of bitcoin blockchain, 10 minutes per mining a block is usually chosen). Note that given a value of nonce and the block, it is easy to verify that the hash function of this block is in fact less than the targetvalue. Thus, once a miner broadcasts a mined block, every other node can verify that the mined block is valid and thus will append this block to its own blockchain.
Proof-of-work described above prevents a serious problem called double-spend. Suppose Alice tries to send the same bitcoin to Bob and Carol. The transactions are not completed unless both the transactions are recorded on the blockchain. If an honest node tries to mine these transactions, it will immediately invalidate one of the transactions as the money is already spent. Another possibility is Alice herself tries to mine the block. In this case, if both the transactions are in one block, then other honest nodes will refuse to accept this block as a valid node. Thus, the only possibility for Alice is that the two transactions should be included in two different blocks. In this case if one of the transactions (say from Alice to Bob) has already appeared in the blockchain, then the other transaction will be invalidated by the honest nodes. The other possibility is that both the blocks are mined at the same time thus creating a fork in the blockchain. When such a fork appears, the blockchain chosen by a majority of the nodes is considered as legal. The trasaction that appears in this legal blockchain will be considered as valid and the other transaction will be invalidated. For other types of attacks, the readers are referred to [26].
A disadvantage of proof-of-work is that it needs a massive amount of computation power (hence, energy) to validate a single block. “The ever-expanding racks of processors used by miners already consume as much electricity as a small city” [10]. Another problem is that mining has become rather proprietary hardware centric which leads to centralization issues as people who are manufacturing such hardware can control the blockchain system. Therefore, people are shifting to other mining techniques like proof-of-stake which is discussed in the next subsection.
2.2.2 Proof-of-Stake
In proof-of-stake, nodes are selected for mining in proportion to the blockchain currency each node is holding as opposed to the computation power in proof-of-work. In proof-of-stake protocol, any node which holds blockchain based currency can become a miner by depositing its currency to the blockchain. Selecting the validator can be done in several ways, such as:
Randomized block selection: Here, the algorithm randomly selects the miner from the set of miners who have deposited their currency. This miner bears the sole responsibility of creating a new block and providing a pointer to some previous block which is typically the last block of the longest chain.
Coin age-based selection: In this protocol, the selection takes into account not only the quantum of currency held but also the duration for which the currency is held. Once these currencies are used for validating the block, the age of the currency is reset to 0. The proof-of-stake protocol is significantly more efficient over proof-of-work protocol in terms of energy consumption, however, this protocol suffers from other disadvantages like nothing at stakeand long range attacks which are briefly described below.
Nothing at stake: Since in proof-of-stake, the miners are not spending any computational effort, it is in best interest of the miner to mine on every competitive chain. This ensures that no matter which chain wins in the future, the miners will be rewarded for sure. Thus, if all miners behave in a rational way, then even if there are no attackers there will be no consensus at all
Long range attacks: In proof-of-stake, a miner can create a fork many blocks back as opposed to proof-of-work. This is because, in order to compete with the longest chain, a miner in proof-of-work will need to do lot of computation work whereas in proof-of-stake, only holding of currency needs to be shown.
2.2.3 Mining Pools
As we have already seen, mining with a proof-of-work protocol needs tremendous amount of energy and computation hardware. Consequently, mining is expensive and even requires one to constantly update hardware (due to the fact that the mining difficulty is always increasing) along with paying off the electricity bills. Even if a miner were to invest such a large amount of money, it is not guaranteed that the miner will actually be successful in mining the block. The mining process results are highly uncertain, as the likelihood of mining a block as compared to the cost of hardware and the cost of electricity is quite low.
Let us consider the probability of successfully mining the block. Since block generation time is fixed and is independent of whether the miner successfully mined the block or not, the distribution is well approximated using the Poisson distribution. To understand this, consider coming up with a nonce value as an independent random trial and the probability with which this nonce will in fact result in successful mining of the block is given by \lambda/N where N tends to infinity indicating the number of nonces to be tried by the miners and \lambda depends on the hardness parameter of the puzzle. Thus, if one computes the probability of not being able to mine any block in a limited time period (say a year), it could be quite high, leaving no earnings. However, a miner may still be doing okay in expectation (for example, by mining more than two blocks in the next year), but the uncertainty could be frustrating for the miner.
To overcome this problem, more and more miners are joining mining pools. Pool mining acts as the insurance to the miners, i.e., even though the miners do not get the full reward of mining a block (quite high but high variance), they get lower rewards (but with certainty) for attempting to mine a block (low reward but low variance). In pool mining, each miner connects mining equipment with a pool server after creating an account on the server. This server synchronizes the efforts put in by the miners so as to share their efforts. Thus, pool server can ensure that the two miners are trying out distinct values of nonces so that the effort of no miner gets wasted.
Even though pool mining seems to be a good option, there are many research questions that arise on the implementability of pool mining. One fundamental question is how to distribute the mining reward amongst the miners associated with the pool. There should be some measure to automatically compute how much effort each miner has put in to find the valid block. Constant reward scheme will not work as it will promote free riding and the performance of overall pool will only reduce.
The unique value proposition of blockchains is that they enable the creation of digital solutions with built in economics. This capability traces its roots to the first applications of blockchains: bitcoins as a digital currency. A necessary condition for a digital currency is the existence of a trusted ledger which can maintain the balances of the account holders. No-one except the account owner should be able to reduce the account balance; not even the entity responsible for maintaining the ledger.
3.1 Asset Ledger
At its very core, this is what a blockchain is – a trusted ledger. As we explained in the previous section, the technological innovation of blockchains is that the trust in the ledger is ensured using a combination of cryptography and distributed consensus.
It turns out that this simple idea of a trusted ledger has multiple economic applications. First and foremost, a shared, trusted ledger enables everyone involved to agree on a single version of the truth. Let us take an asset like land. As economists have argued, land serves the dual purpose in any economy. At the physical layer, land is an asset which can be used for building a house, growing crops, or building a workplace. However, many assets lead a second life beyond the physical world: as collaterals in the financial world. Land and property are the most common assets used as collateral to secure a loan.
A critical requirement to enable land to be used as a collateral is a trusted ledger which acts as a shared registry across the financial system recording details about different properties. In the absence of such a registry, there is no way for a loan issuing agency to verify whether or not a particular asset is owned by the loan application, or for example, whether or not the same property has already been used as a collateral for a previous loan. Today, the financial system relies on manual processes and paper-based documentation to verify these details. This makes the system slow and liable for manipulation. Several financial frauds exploit exactly these limitations: by exploiting the lack of a shared, trusted asset registry, a fraudster is potentially able to “doublespend” the same asset as a collateral.
One interesting question in creating a blockchain based asset registry relates to privacy. The true value of an asset registry is realized when it is shared among every participating agent in the system – does this infringe on individual privacy? Does storing asset ownership on a public registry imply that everyone knows who owns what? Public blockchains like Ethereum and Bitcoin blockchains solve this system by using pseudo-anonymity. Every agent in the system is recognized by its account address (public key) but the blockchain does not store a mapping between this account address and the real-world identity of the agent. With these blockchains, thus, the mapping of assets to account addresses is common knowledge but the mapping between the account address and real-world identity may be kept private (known only to the individual agent). In the context of blockchains being used as an asset registry for crypto-currencies, it is this pseudo-anonymity property which poses challenges to governments and law enforcement agencies worldwide.
With permissioned blockchains (more about these in Section 4), the issue is less pronounced but still exists. With permissioned blockchains who all can become a part of the blockchain network is controlled by an administrator, so information sharing (of the asset registry) is within a group. Often, however, there may be cases where two (or more) agents in the network may want to undertake a transaction privately. Here again is the requirement for privacy. Interesting solutions to this challenge continue to be explored: cryptographic techniques like zero-knowledge proofs, ring signatures, and hash functions can be combined in interesting ways to achieve privacy while still ensuring trust in the underlying ledger.
3.2 Token Ledger
A second class of economic applications enabled by blockchain is closer to its original use – the ability to create new currencies a.k.a. tokens or coins. If we think about currency as yet another asset, then the big picture begins to emerge. Fundamentally, blockchains are
