Blockchain & Cryptocurrency #7: Distributed consensus

We are a group composed by some Informatics and Mathematics who like to share their IT, Math and Cryptographic knowledge with people. It is possible to find our complete courses on http://learningspot.altervista.org website. Since we think that Steemit is a great opportunity to share knowledge, we are proposing our most interesting lessons here, too.

==================================================

Until now we have talked in a generic manner about centralization and decentralization. Let's now talk about Bitcoin decentralization. The key work of this topic is distributed consensus.

How to build a distributed e-cash system

The key challenge that is necessary to solve to build a distributed e-cash system is the distributed consensus. This is a class of protocols studied for decades in the computer science literature. Intuitively, you can think of it as our goal to decentralize ScroogeCoin, which is the hypothetical currency that we saw in the first week.

Reliability in distributed systems

Imagine the backend systems for companies like Google or Facebook. These companies have thousands, or even millions of servers, which form a massive distributive database. This database records all the actions on the system, such as users' comments, likes, posts and so on.

When a new information comes in, the server needs to make sure that that comment either gets recorded in all copies of the database, or none of them. If the action gets recorded in none of the databases, it's okay: it's enough to notify the problem to the user. On the other hand, if some of the copies of the database saved it and others didn't, then there will be a lot of troubles: the database will be inconsistent.

So this is the key problem that motivated the traditional research on distributed consensus.

Distributed consensus applications

Suppose that we have a distributed consensus protocol and we were able to use it to build a massive distributed key-value store, that maps arbitrary keys or names to arbitrary values. Then we could use it for many applications, for example:

• distributed domain name system: a mapping between human understandable domain names to IP addresses
• public key directory: a mapping between user email addresses to their public keys
• stock trades: the distributed database would keep track of who's transferred goods of which stock to whom

Now that Bitcoin has solved the distributed consensus problem, we can go ahead and try to use it for all these related problems. In fact, there are many Altcoins: systems built on Bitcoin-like principles to achieve slightly different goals. Sometimes they are currency systems, sometimes not.

Technical definition

Imagine that there is a fixed number $$n$$ of nodes or processes and each of them has some input value. Then a consensus protocol run on them has two requirements:

1. the protocol should terminate and all correct nodes should decide on consensus value. We say correct nodes because some of them could be faulty or even malicious.
2. the output value cannot be arbitrary, but must match with one of the input values proposed by at least one of the correct nodes.

Bitcoin transaction

Bitcoin is a peer-to-peer system. So, when Alice wants to pay Bob, she's going to broadcast the transaction to all of the Bitcoin nodes belonging to the peer-to-peer network. The transaction is going to have:

• Alice's signature used by other nodes to check the provenience
• Bob's public key, which also accesses the address at which he wants to receive bitcoins
• a hash of the previous transaction. This is a way for Alice to link this transaction to her receipt of this coin from someone else previously

Alice is going to broadcast the transaction to all of the Bitcoin peer-to-peer nodes. It is not necessary that Bob listens the network to receive the funds. The bitcoins will be his, whether or not he's running a node on the network.

The network nodes wants to reach consensus on which transactions were broadcasted, and the order in which these transactions happened.

How distributed consensus could work in Bitcoin

At any given time:

• All the nodes in the peer-to-peer network would have a sequence of transactions blocks that they've reached consensus on. In fact, for optimization purposes the transactions are organized into blocks and linked together to form a blockchain.
• Each node would have a set of outstanding transactions that it has heard about. The consensus has not happened to them, yet. So each node might have a slightly different version of these outstanding transactions.

Now suppose that there are three nodes in the system, each of whom has an input: the set of outstanding transactions that it heard about. They execute together some consensus protocol, when it succeeds, it is possible to select any valid block and add it to the blockchain, even if it's a block proposed by only one node.

Problems with this kind of system

Taking the traditional theory of distributive consensus and applying that to cryptocurrency, we end up with a system similar to the one described above. This has some similarities wth how Bitcoin works, but it's not exactly the same. In fact, this systems has some hard technical problems, for example:

• Nodes might crash or might be malicious
• The network is highly imperfect: it's a peer-to-peer system and not all pairs of nodes are connected to each other
• There could be faults in the network because of poor Internet connectivity
• There will be a lot of latency in the system, because everything happens over the Internet and there's no single data center. One particular consequence of this high latency, is that there is no notion of global time. This means that not all nodes can agree to a common ordering of events, simply based on observing timestamps.

Constraints in distributed algorithm

Especially the last problem, puts serious constraints on what sorts of algorithms can run into a consensus protocol. A lot of the literature on distributed consensus is somewhat pessimistic. And many impossibility results have been proved, such as:

• Byzantine generals problem: under some conditions, which include the nodes acting in a deterministic manner, consensus is impossible, even with a single faulty process.
• Paxos problem: under certain conditions, even if rare ones, the protocol can get stuck and fail to make any progress

However Bitcoin violates a lot of the assumptions of the previous impossibilities problems. Because of that, consensus in Bitcoin, ironically, works better in practice than in theory:

• Bitcoin introduces the idea of incentives. Because Bitcoin is a currency, it is possible to use it to give incentives to the participants for acting honestly.
• it embraces the notion of randomness: consensus happens over a long period of time, about an hour in the practical system. As time goes on, the probability that a transaction is valid goes up higher and higher. And the probability that you're wrong in making an assumption about a transaction goes down exponentially.

That's why Bitcoin is able to get around these traditional impossibility results on distributed consensus protocols.