The Double Spending problem, Consensus mechanisms on distributed networks, and Establishing “trust” in the “trustless” network! The Double Spending problem If Alice has $10 in her wallet, she should be able to buy goods only up to $10. So for example if Alice goes to a store, and there is a lamp for $10 and table for $10, she should be able to spend the $10 only on one of them. The double spend issue does not arise in day to day cash transactions since the exchange of currency for the goods happens together (i.e. it is a centralized system). So Alice gives up the $10 and gets the lamp, and now does not have the $10 any more. However the issue is a little different in distributed systems. In case of distributed systems, the record of the transaction is broadcast to all nodes in the network . (i.e. Alice broadcasts the transaction on the network so that every node on the network is made aware that “Alice has used up $10 to buy a lamp”) Each node records this transaction message and then passes the message onto the next node in the network, and the process continues until all nodes in the network have recorded the message . “Alice has used up $10 to buy a lamp” However as this message propagates through a large network following issues may arise. Messages may take different paths as they propagate through the networks and consequently arrive at different nodes at different times. Due to node failures, some nodes may be unable to forward the message to the next node and the message may be lost. Thus, we are left with a situation where at a given time, certain number of nodes , and certain number of nodes are are aware that Alice has spent the $10 on the lamp not aware that Alice has spent the $10 on the lamp. For the nodes that are not yet aware that Alice has spent the $10, i.e. the message has not yet reached them; they are still under the impression that Alice has $10 in possession to spend on anything else. Thus, it is possible for Alice to broadcast another message to the network that and if this message reaches a node before the first message i.e. , they will now assume that Alice has used up the $10 on the table instead. “Alice has spent $10 on the table ” “Alice has spent $10 on a lamp ” This opens up the possibility of Alice being able to spend the $10 on the table, and the $10 on the lamp; which should not be allowed as Alice only has $10, not $20. same This is the double spend problem. The double spend problem arises in distributed systems since the transaction messages take time to propagate through a large network. Because of differences in propagation time over the network, there is no guarantee that the order in which a transaction message arrives at a node is the order in which they were created. Note: It may be argued that one could include a universal timestamp on the message data, along with the hash to ensure data integrity, and this would easily address the issue of transaction messages arriving at different times at a particular node. However, Alice could easily fake her timestamp before signing the message, and put in an earlier timestamp for the second message, creating a whole deal of confusion on the network. At a deeper level, the network is now left in an inconsistent state where some nodes have validated that and others have validated that . “Alice has spent $10 on the lamp ” “Alice has spent $10 on the table ” In order to resolve this inconsistent state of the network (where few nodes have validated one transaction and others have validated a conflicting transaction), we need some consensus mechanism on the order of the transactions, thereby bringing the network back to a consistent state. Consensus mechanisms in (Distributed Ledger Technologies) DLT and Blockchains “The truth isn’t a thing of fact or reason. It is simply what everyone agrees on.” ― Gregory Maguire, Wicked: The Life and Times of the Wicked Witch of the West There are two ways in which this consensus can be established, where each node on the network is known and each node votes “yay” or “nay” on the validity of the transaction. Consensus is achieved by tallying up the majority votes and endorsement policy (eg. PBFT algorithm). The endorsement policy may dictate that the transaction is valid if 2/3 of the nodes on the network validate “yay” on the transaction. Voting based consensus (as in case of trusted consortium nodes or private distributed network, eg. Hyperledger): where only one member of the network, chosen based on PoW or PoS, is allowed to decide if the transaction is valid or not, and this decision is agreed to by all on the network. In effect whoever wins the competition (wins the lottery) and the network agrees that transactions validated by the winning node are valid. Lottery or Competition based consensus (as in case of public or trustless node network, eg. Ethereum): The “competition” by which the next node is elected may be in the form of solving a cryptographic puzzle eg. PoW, or may be in the form of increased chances based on contribution of investments into the network eg. PoS. Consensus mechanism (either voting or lottery), are a way for the network to determine which of the conflicting transactions are to the be considered valid by the entire network. All the nodes of the network then invalidate the conflicting transaction, and proceed only with the consensus agreed upon validated transaction. It is interesting to note that the validated transaction may not actually be the “correct” transaction out of the conflicting transaction. In our example if the group consensus votes “Alice spends $10 on the table” as the validated transaction, the “correct” transaction i.e. “Alice spends $10 on the lamp” will get invalidated by all the nodes of the network. In fact the purpose of the consensus algorithms is not to ascertain the “truth” as to which was the “correct” transaction between the two transactions. Instead consensus algorithms are merely a mechanism to prevent the double spending problem in distributed networks (i.e. In our example using the consensus mechanism we are ensured that Alice can spend that $10 once and only once); and ensures that only one of the conflicting transaction is agreed upon by the entire network, and the any conflicting transactions are invalidated by the entire network. Establishing “trust” in a “trustless” network Bodhi: “You don’t trust me?”Johnny Utah: “You gotta earn trust.” — Point Break (1991) Proof of Work (PoW) algorithm is a means by which a winner emerges from within the network (based on the solution to a cryptographic puzzle), and that winner decides which of the conflicting transaction in the network are valid and to be a part of the next block in the blockchain. Could not any node be picked at random and designated the next winner (true random lottery), and this node be elected to decided which of the conflicting transactions are valid. However the question begs, why do we need nodes to compete with each other to solve a complex cryptographic puzzle in the first place to select a winner? i.e. Why do we need a complex PoW? The answer to this is as follows, If lottery winners are picked without it being computationally intensive to add blocks (or some token of computationally intensive i.e. PoS), then it becomes easy for anyone to add the next block on the Blockchain. This means that several parties can add their versions of block to the blockchain, and the one with the greatest single computing power will be able to scale up the block chain, and have the longest blockchain. The genius of Satoshi Nakamoto’s solution to the issue of “establishing trust in a trustless network”, is to ensure that it is impossible for an individual, or a even a large group of individuals (as long as the group size is <50%), to computationally outpace the collective network, i.e. to create new blocks to add to the blockchain, and (continuously) maintain the longest chain on the blockchain. Thus, the basic idea is to make it and introduce some mechanism to do this. The most common of these mechanisms is the PoW algorithm. computationally hard to add blocks to the blockchain However there is also Proof of Elapsed Time (PoET), which needs node to computationally “wait” for a period of time, before the next block is added to the blockchain, thereby again artificially making it computationally “hard” to add blocks to the Blockchain. In case of PoS, the escrow of tokens as a mechanism to be chosen as the next member to create a block, again makes it computationally hard for any one individual to invest enough number of tokens to outpace the collective network. 👏 Found this post useful? Hit the button below to show how much you liked it :) Follow me on Medium for the latest updates and posts! Read Next: Making sense of the Blockchain Landscape in 2018 Other Articles by Prashant Ram: BlockChain Demystified: Looking Under the hood of the BlockChain Understanding Digital Signatures in Blockchain and Cryptocurrency The Distributed Autonomous Organization (DAO) and how Blockchain/AI can take over the network — and why you cannot stop it!

Why do we need Proof of Work (PoW) in Blockchain?

Too Long; Didn't Read

People Mentioned

Company Mentioned

@prashantramnyc

RELATED STORIES