These are my notes of the seventh lecture from Coursera’s Bitcoin and Cryptocurrency Technologies during Dec 2016 – Feb 2017. This was a great lecture in that it started more from fundamentals to explain how decentralization has been done in bitcoin.
Questions answered in this Post:
- Define consensus and distributed consensus.
- What is a distributed consensys protocol?
- What does consensus mean in Bitcoin
- How does consensus work in bitcoin?
- With all the pessimism with distributed consensus, what enables bitcoin/makes it less at risk for these shortfalls?
Before we can started talking about distributed consensus and consensus for bitcoin, what on earth is consensus? According to the Merriam-Webster dictionary…
Consensus:
general agreement about something; an idea or opinion that is shared by all people in a group
Great, now what is distributed consensus?
Well, when related to computer science, how can multiple main computer nodes agree on a single idea/piece of data if they are receiving different inputs. Then a consensus protocol is the answer to the question on “How” these nodes can come into agreement. If one is interested then please google “distributed systems protocols” to learn about these. Or just look at things like distributed hash tables or Paxos.
Distributed Consensus Protocol
Def
fixed number of nodes, n
each nodes have some input value
- each nodes have some input value
- protocol terminates and all correct nodes decide on the same value
- this value must have been proposed by some correct node
- in this scenario there are bad, faulty, and malicious nodes as well as the correct nodes.
Consensus in Bitcoin
Bitcoin is a peer to peer system. When Alice wants to pay Bob, she broadcasts the transaction to all Bitcoin nodes that comprise the peer-to-peer network. Also, Alice and Bob are not the only individuals broadcasting out transactions.
signed by Alice
pay to pk_Bob: H()
contains Hash of the coins history
Bob is not on the system he needs to be a bitcoin node to hear it
Consensus in bitcoin means if all these people are broadcasting their transactions and all these nodes are hearing them, how do you determine which transactions were broadcast, which were valid, and in what order. By the end, there should be a single, global ledger that is maintained by all. However, it also means that nodes will also have transactions they have that may not be on the block yet. These are called outstanding transactions.
How consensus could work in Bitcoin?
at any given time:
- All nodes have a sequence of blocks of transactions they’ve reached consensus on
- Each node has a set of outstanding transaction they’ve heard about (these have not reached consensus
Scrooge Coin: transactions were put into blocks
Why is bitcoin blockchain consensus hard?
- Nodes may crash
- Nodes may by malicious (put invalid transactions in blocks)
- Network is imperfect
- Not all pairs of nodes connected
- Faults in network (poor network connectivity)
- Latency since these nodes are all over the internet
With high latency, this also means that there is no notion of global time. The ordering agreed upon does not indicate time. All we know is that one node was put one the block chain prior not which transactions actually was broadcasted and heard first. Because of this constraint, many consensus protocols in literature tend to be pessimistic. You get these impossibility results.
Impossibility Result Examples
Byzantine Generals Problem which resulted in if a third or more of the generals (nodes) were traitors when it was impossible to achieve consensus.
Fischer-Lynch-Paterson (deterministic nodes)
which proved that consensus impossible with a single faulty node
Paxos – never produces inconsistent result
protocol can get stuck and never make any progress
These pessimistic models tend to shed light on the idea that bitcoin is the same problem as resolving a distributed database and thus can make concessions that the others were unable to.
Consensus in bitcoin: theory versus practice
While theory may sound pessimistic, practice seems to work better. This may be due to special features of bitcoin. Also, bitcoin contains the idea of incentives because it’s a currency. Second, bitcoin embraces randomness where as proper distributed systems hate it. Actually the consensus algorithm relies on randomness. So while you can never by 100% confident, you can be extremely confident when a block has entered the ledger. Also, the latency is fine since at this point, it’s one every ten minutes.