Recently, I realized that I was stuck in a rabbit hole for educational work with blockchains. I was interested in this topic, because I have always been concerned about the guarantees of security and performance of blockchain protocols.
In the end, even though these protocols are relatively easy to describe and implement, it seems that they have much more attack vectors than standard distributed systems, including distributed databases and file systems. Moreover, the probabilistic nature of the blockchain implies that there may be a deeper phenomenon that underlies the empirical success and stability of Bitcoin and Ethereum.
Since blockchains combine probability, game theory, cryptography and distributed systems, it is natural that the probabilistic asks questions about phase transitions, stable Nash equilibrium, and random walks on miner graphs. For example, someone might ask: “Does the law of length of a Bitcoin chain obey Golton-Watson's process? How far is it from the critical level? ”Answers to such questions are likely to reveal some secrets about security, transaction processing speed and quality of service of blockchains and help us create more complex distributed data block structures.
In this series of publications, I will focus on the following issues:
- What is the relationship between the security analysis of the blockchain and the traditional analysis of distributed systems?
- How do blockchain security settings control transaction processing speed, quality of service, and other practical indicators of distributed algorithms?
- How is centralization determined, considering all the different attack vectors for the blockchain?
- Can we associate the similarity of grinding attacks in systems with evidence of the share of ownership with a traditional probabilistic object (for example, the mixing time in a Markov chain)?
I want to use a combination of academic literature about blockchains and the theory of discrete random walks as a starting point for developing the relationship between probability and blockchains. This post focuses on the first question and contains less technical information. The following posts will contain technical details and probabilistic assumptions about blockchains. I want to note that initially I wrote one long post containing the answers to all these questions, but I soon realized that I had too much information for one publication!
Warning: we are far from the level of such work as Probability on Trees and Networks of Russell Lyons and Yuval Perez. I just want to share with you my thoughts on some issues.
The Galton-Watson tree is almost a critical case: the color represents the distance from the root
The key innovation of Bitcoin, which allowed this to happen, was the introduction of concepts from game theory - the incentive system into a standard distributed transaction database. To be more precise, Bitcoin suggested such a concept for developing incentives, in which the possibility that the owner of a database node will have a hostile and destructive influence on the network security or an element of trust in the database results is small or even negligible. This means that even if someone tries to conduct a hostile attack on the Bitcoin network, then, according to statistics, they will most likely fail.
This guarantee is based on the fact that the rest of the network has no incentive to cooperate with the enemy, as this may reduce their chance of minting new Bitcoins. Comparing this situation with a modern financial system — there is a large amount of trust based on identification data — this is both a “know your customer” rule and a credit rating created over many years of interaction between consumers and financial institutions. Moreover, banks have many of their own incentives to prevent fraud and malicious activity associated with the violation of various laws, as well as relations with central banks. But what is the Bitcoin incentive system and how does it provide trust, similar to a bank trust? Why this trust can be considered reliable, even if one institution has a large part of the mining forces or if there is a large number of miners and a lot of time is needed to confirm the transaction?
The most obvious vulnerability of Bitcoin is associated with the famous attack of 51%. Suppose there is a miner who controls more than 50% of all mining forces, which means that he receives a reward for confirming more than 50% of the blocks (for example, packets of verifiable transactions) received by the network. If any organization had such power, then it could create a bitcoin transfer transaction from any address to its own with a greater chance of its confirmation, because this organization controls most of the confirmation mechanism.
In the Bitcoin protocol, there is a system in which miners compete for transaction confirmation. If the miner first successfully confirms the transaction, he informs all participants in the network about it. The percentage of mining forces for one object correlates with the probability that it will confirm the transaction: the more mining forces you have, the more transactions you confirm. In addition, if you have more than 50% of the mining power, then you can also prevent other people from confirming transactions.
In the banking sector, it would look like Citi has more than 50% of US consumer deposits, which means the bank can say, “Hey, we need a billion dollars, let's confirm the transaction from Morgan Stanley in favor of Citi, because they probably won't be able to stop!". When Morgan Stanley attempts to block this transaction, Citi will ensure that all its mining forces accept it. In the modern financial system, this cannot happen because central banks manage large interbank transfers and are trusted third-party intermediaries who will not allow such transactions. However, if someone has a large part of the Bitcoin mining forces, this object is statistically equivalent to the central bank, which to a certain extent has the right to have the last word in the confirmation of the transaction.
In the abstract example, where Bitcoin is the dominant payment method, all miners are rational and extremely selfish, there is a miner with 51% of forces - such an attack is simply inevitable. However, in the past, Bitcoin's network had situations when mining pools gained more than 50% of the mining capacity of the network, and the double waste attack was never made. This means that the security of the blockchain is more complex, and only due to the concentration of the mining forces in one object does not hack it.
Another way to interact with security and competition in Bitcoin is the transaction confirmation method, which uses a random voting system and selects a “leader” to mine the block. According to these rules, miners constantly throw asymmetrical coins until someone throws a tails. The asymmetry of the coin of each miner or the likelihood that tails will fall out depends on the performance or share of the miner’s ownership. In other words, if you have the largest percentage of the mining forces of the network, then, most likely, it will be you who will have the tails in almost every case. The first miner, who falls tails, is the “chosen leader” who creates the block and receives the reward.
Please note that miners, unlike ordinary voting, do not have to identify themselves. In order for the network to recognize the new miner, he only needs to take part in one transaction or silence the block. Moreover, the number of miners can vary greatly and the exact number of election participants is not disclosed. From this point of view, blockchains refer only to attachable databases, which provide security thanks to multiple random selections without identification.
Thus, an attack of 51% can be made with more than 50% of the votes in most elections. In this case, you can do double waste by creating a transaction with someone else, excluding the past transaction from the block or adding a transaction that cancels the original transaction. I always think that the analogy with the vote also makes it possible to understand that all miners and network participants do not need to have the same copy of the chain and / or agree with each transaction. This is a big step away from traditional distributed databases, where attempts are being made to find solutions to such problems as the task of the Byzantine generals Leslie Lamport, where there are attempts to find the line between a clear consensus and the inability to reach a consensus.
Usually, the analysis of distributed systems focuses on security using an uncompromising method and implies that each node agrees with the identification data, the order of transactions and their confirmation, that is, an unambiguous consensus is reached. In these systems, the participant also chooses a leader - the algorithm of the Byzantine generals performs a recursive algorithm for choosing a leader - but usually there is one non-random choice, which assumes that all personalities are known at the beginning of the choice [0].
In the case of blockchains, we do not know the number of dishonest miners and the identification data of those who will also participate in the “vote”. This is similar to human-made systems, such as currencies, which are often governed by a probabilistic approach, since society can agree and follow rules with which a significant (but not clearly established) part disagrees. In this case, we see that the voting-based Bitcoin security component can be calculated as the maximum size of a disagreeing group with which the network can continue to accept transactions, even if this group does not agree with the rest of the network and creates fraudulent transactions (which can be called falsification of voting ).
The use of the new incentive system in Bitcoin led to an explosion in the academic analysis of the problems of game theory related to voting. However, other security issues with traditional distributed databases still pose problems. One of the biggest problems in maintaining the same state of distributed databases is network latency and asynchrony — the nodes need time to receive transactions that may arrive in a different order. In the database world, we usually try to create systems that do not depend on the order of receipt of transactions. However, in the blockchain world, the exact order of the blocks is the main factor of security and stability. Most blockchains and peer-to-peer protocols provide a message through the gossip protocols — you tell your neighbors about the new block, they tell their neighbors, and so on.
What happens if two people create the same transaction block at the same time? In Bitcoin, a fork will be formed and one chain forms a tree with the last two blocks. Since the blocks pass through the network, the miners choose the block that they receive first. In theory, a blockchain could constantly fork and look like a random Galton-Watson tree in the picture above. However, it would be awful - blockchains that look like trees would eventually spend more computational power on constantly re-confirming transactions in the branches that are ending.
Satoshi Nakamoto's analysis shows that the probability that both branches will have the same height decreases exponentially with the number of blocks assigned by the network [1]. In order to overcome the fork, you must wait until one of the branches grows significantly and becomes the longest chain for all the miners. This time penalty is related to how much confidence the user needs to believe that his transaction has been accepted by the network. For example, in Bitcoin’s original whitepaper, Satoshi assumes that in order to make sure that the transaction is accepted by the network, you need to wait until six more blocks are created after the transaction block. On average, one Bitcoin block appears every 10 minutes, we would have to wait a full hour to make sure the transaction was confirmed! Such a compromise at the security level (in this case, a parameter of six blocks was chosen to ensure it) and time assumes that network latency can affect not only security. Here are some more examples of problems:
- Quality of service. Even if the waiting time until the transaction is accepted by the network by the majority of the network is small, changes in transaction processing speed can be critical. In IPFS, which is also called “Dropbox on the blockchain,” the block is associated with a set of files. If there is a large variation in bandwidth between the blocks, the process of loading a folder with a large number of files may be delayed [2]. This situation may be unacceptable for users who are accustomed to centralized systems such as Dropbox, which have small variations in speed and low latency.
- Transaction cost Distributed exchanges seek to eliminate centralized market makers, using the mining award to motivate miners (who play the role of market makers) to keep the order books intact. For example, miners receive liquidity rewards to level the bid book [3]. Nevertheless, it can be very profitable for market makers to leave an order book unsynchronized (for example, as in this article), so you need to develop a system of incentives, thanks to which market makers do not want to collect a mining award at the same time and create a big difference between courses for asynchrony.
- The effects of "rich all richer." Many blockchains use gossip algorithms with distributed hash tables, for example, Kademlia. In these algorithms, nodes monitor their “nearest neighbors” on the basis of who sends them the largest number of blocks upon request. A miner with a high proportion and / or power can use such algorithms to always be the “nearest” neighbor to most of the other miners. Thus, he can make sure that his blocks get into the network before the blocks of other miners, and gradually gain a steady advantage over miners with the same capacities. We will look at this problem in one of the following articles about routing attacks.
Network signal delay and asynchrony are the cost of communication in this decentralized system. We give a more illustrative example and look at how much the time of searching for a single file in Dropbox and IPFS can differ. Suppose we are in an ideal world, where Dropbox is one server and there is one route from your computer to Dropbox. In this case, the difference in search time depends only on the properties of this one path. However, in IPFS there are nodes N and K on which copies of your file are stored. In this situation, we have two additional sources of oscillation:
- Path selection / routing. Since the gossip protocols try to create expanders, most likely there is no unique way (especially if K ~ N / 2) [4].
- Node operation time If the node is turned off, and we are trying to download a file from it, then we will have to repeat our request, which increases the search time.
Moreover, note that these additional sources are scaled with N and K, and one-way oscillations do not depend on N or K. From this idealized example, we see that the blockchain systems have decreased service quality, which means that any protected and productive system must have some centralization. Can we relate this observation to the theory of traditional databases and find a way to analyze this trade-off?
It is interesting that Shostak, Pis and Lamport consider a compromise between centralization and quality of service in their original article “The Task of the Byzantine Generals”. In the last section, they analyze a d-regular bond graph [5]. At a high level, this property is due to the fact that the nodes v and w have no pairs, and all the paths from v to k pass either through w or through any neighbor w. They show that you can remain resistant to Byzantine enemies, but you have to pay a fine proportional to the diameter of the connection graph. So, if someone can create a random version of this property [6], then we can use it for security analysis of the blockchain.
Such an analysis is carried out in random binary Byzantine protocols [7] and most likely will be useful for a probabilistic person working with blockchains. Moreover, studying the behavior of random walks in graphs of distributed hash tables in the least favorable case is likely to help provide guarantees for standard distributed systems for blockchains, albeit with a spectral space and a penalty associated with the diameter.
I hope this article showed how about forty years of work on distributed systems can be successfully used in a formal probabilistic analysis of blockchains. Even considering that most of the analysis of Byzantine errors in distributed systems is deterministic, much can be used in the probabilistic world through careful observation of the phenomenon of concentration and random walks on graphs. In the next article, we will discuss how different authors in the cryptography world perform probabilistic analysis of various simplified blockchain models with idealized enemies. In the next article, I will also try to illustrate (by example) how random versions of deterministic algorithms can help avoid such seemingly insurmountable problems as the Arrow theorem.
Thanks to Uthsavu Chitra, Jayanta Garlapati and Yi Sun for comments and suggestions.
[0] For example, if we know that there are m dishonest miners in the deterministic Byzantine scheme, then Lamport's algorithm proposes an Ω (m) algorithm for fair voting, assuming that we can determine the identity of all voters.
[1] This analysis was not accurate, since the exact graph describing the network is important for calculating this probability. In one of the following articles in this series, we take a closer look at an example of this type of calculation and how it is influenced by the choice of an algorithm using the example of the Ethereum network.
[2] Please note that not only blockchains have this property - such distributed file systems as NFS and Amazon S3 also have problems with a large number of files. Nevertheless, these systems control network topologies and can solve most of the problems of random routing of blockchain networks.
[3] It is interesting that the US securities market to some extent uses this through the regulation of the national market system.
[4] It is not proven that the graphs created by algorithms such as Kademlia are expanders. They often have properties that determine the constant diameter of the graph Ω (log N).
[5] This differs from the standard definition of regularity in graph theory, where a graph is d-regular if each vertex has d edges!
[6] The first attempt at a random version. Suppose we have two nodes v and k, and ε> 0. For each node w∊ ∂v, and any pair of paths?,? with maximum length εN, which starts with w and ends with k, Pr [|? ∩? |> 2] = O (f (N, ε)) for the rapidly decreasing function f.
[7] See Ben-Or, Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols and Mikali, Byzantine Agreement, Made Trivial
