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
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:- 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.
- 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
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.
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
- 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.