Arthur Gervais (ETH Zurich) & Co were also present at the last CCS 2016 – the 23rd ACM Conference on Computer and Communications Security (Hofburg Palace Vienna, Austria / October 24-28, 2016). They presented one other interesting talk with a supporting paper, and The Information Age liked it and wanted to further share and review.
Theirs was a talk with paper on the security and performance of the Proof of Work (PoW) protocol underlying 90% of current cryptocurrencies and major developments deploying blockchain protocols. It dwelled on a so-called blockchain simulator instead of a real deployment, but made claims, with reasonable assumptions, about it being helpful in addressing the scalability issues of the main cryptocurrencies in existence. The paper is an enjoyable read and not very heavy on the mathematical side of these protocols. Nevertheless the argumentation is neat and nimble, round and obviously qualified.
The interesting part from my point of view, the new and novelty of this paper, was the part associated with the concept of a stale network and how the authors used it to argument and determine the relevant aspects of the issues about security and performance of PoW protocols within blockchains.
Arthur Gervais et al.
Stale blocks refer to blocks that are not included in the longest chain, e.g., due to concurrency, conflicts. Stale blocks are detrimental to the blockchain’s security and performance because they trigger chain forks—an inconsistent state which slows down the growth of the main chain and results in significant performance and security implications. On the one hand, stale blocks increase the advantage of the adversary in the network (e.g., double-spending). On the other hand, stale blocks result in additional bandwidth overhead and are typically not awarded mining rewards (except in Ethereum).
An obvious instance of what is a cost and detriment may be of help finding improvements. And differing stale block rates differentiates the diverse cryptocurrencies in terms of performance and security, as can be checked by the table and figures below:
Our results (cf. Table 1) suggest that the stale block rate indeed largely depends on the block interval and the block sizes. For instance, unlike Dogecoin and Litecoin, Bitcoin features larger block sizes due to a higher transaction load (of up to 1MB which results in a higher stale block rate (0.41% vs. 0.273%)—although the block interval of Bitcoin is 4 times longer than that of Litecoin. Moreover, the stale block rate differences between Litecoin and Dogecoin are mainly due to the difference in the block interval (2.5 minutes vs. 1 minute), since their average block sizes are comparable (6.11KB and 8KB). Given a confirmation time reduction of 60%, the stale block rate increased by 127% from Litecoin to Dogecoin.
Notice that in Ethereum, uncle blocks correspond to stale blocks that are referenced in the main chain. The uncle block rate in Ethereum is almost 6.8%, compared to a stale block rate of 0.41% in Bitcoin. In Section 3, we study the impact of the stale block rate on the security of PoW blockchains.
Proof of Work Security Model
Another important concept in the paper pertaining to the security of PoW protocols is that of selfish mining, whereby an adversary performs an attack with the intention of increasing its relative mining in a particular blockchain, and is closely related with the double-spending problem with cryptocurrencies, which a fully honest well performing blockchain completely solves. But there is a trade-off and threshold, the crossing of results in a rational incentive to take an attack. The simulation proposed in this paper demonstrate that it is possible of avert this inconvenience, at the expense of a fully synchronized blockchain network, though… Going a bit against the grain of yesterday’s post here about the Honey Badger proposal:
PoW’s security relies on the principle that no entity should gather more than 50% of the processing power because such an entity can effectively control the system by sustaining the longest chain. We now briefly outline known attacks on existing PoW-based blockchains.
First, an adversary can attempt to double-spend by using the same coin(s) to issue two (or more) transactions—thus effectively spending more coins than he possesses. Recent studies have shown that accepting transactions without requiring blockchain confirmations is insecure . The more confirmations a transaction obtains, the less likely this transaction will be reversed in the future.
Second, miners might attempt to perform selfish mining  attacks in order to increase their relative mining share in the blockchain, by selectively withholding mined blocks and only gradually publishing them [14, 31]. Recent studies show that, as a result of these attacks, a selfish miner equipped with originally 33% mining power can effectively earn 50% of the mining power.
Double-spending attacks and selfish mining can be alleviated if all nodes in the blockchain system are tightly synchronised. Note that, in addition to network latency, synchronisation delays can be aggravated due to eclipse attacks [16,17] where an adversary creates a logical partition in the network, i.e., provides contradicting block and transaction information to different blockchain network nodes.
Interestingly the security model proposed is based on Markov Decision Processes (MDP), of reinforcement learning and machine learning noteworthy fame, here applied within the context of optimally determining adversarial strategies:
Our model extends the Markov Decision Process (MDP) of  to determine optimal adversarial strategies, and captures:
- Stale block rate The stale block rate rs allows us to account for different block sizes, block intervals, network delays, information propagation mechanisms and network configuration (e.g., number of nodes).
- Mining power α is the fraction of the total mining power of the adversary (the rest is controlled by the honest network).
- Mining costs The adversarial mining costs cm ∈ [0, α] correspond to the expected mining costs of the adversary (i.e., total mining costs such as hardware, electricity, man-power) and are expressed in terms of block rewards. For example, if cm = α, the mining costs of the adversary are equivalent to its mining power times the block reward, i.e., the mining costs are covered exactly by the earned block revenue in honest mining.
- The number of block confirmations k This corresponds to the number of blocks needed to confirm a transaction, such that a merchant accepts the transaction.
- The impact of eclipse attacks – Our model accounts for eclipse attacks. Here, we assume that the miners of the honest network are affected by the stale block rate, while the adversary and the colluding eclipsed victims do not mine stale blocks. This is due to the fact that the adversary can use any mined blocks for an attack and effectively only has a small chance of mining a stale block after adopting the honest chain. Therefore, in practice, the adversary exhibits a significantly lower real stale block rate than the honest network. The honest network features propagation and validation delays—hence it will witness a higher stale block rate. Note that the blocks found by the eclipsed victim can also count towards the private chain of the adversary.
The next section in the paper delves into more detailed mathematical analysis, even though not much harder that high-school or undergraduate mathematics. I will follow the common lemma in this blog and encourage the interested folks to not skip it. The following pseudocode briefly describes the MDP restricted binary search algorithm used by the authors:
Our goal is to find the optimal adversarial strategy for selfish mining. Recall that the objective of the adversary in selfish mining is not to optimise the absolute reward, but to increase the share of blocks that are included in the chain accepted by the network. We capture this by optimising the relative revenue r(rel) defined in Equation 1, where r(ai) and r(hi) are the rewards in step i for the adversary and the honest network, respectively:
Note that the MDP process implemented in this paper is modified to account for the non-linear characteristics of the reward function – the details of which is for the reader (and myself) to further analyze if he/she so wishes:
Since an adversary aims to increase his relative reward rrel (Equation 1) in selfish mining, as opposed to the absolute reward, the single-player decision problem cannot be modelled directly as an MDP, because the reward function is non-linear. In order to transform the problem into a family of MDPs, we apply the technique of Sapirshtein et al.’s , which we describe below…
The Blockchain simulator
As the title of the post mentioned this paper introduces a novelty within these computing ecosystems – that of a blockchain simulator. I found it to be immediately enticing, since simulation often proves to be useful indeed in many diverse settings and fields. Think for instance that the aviation and aerospace security requirements industries rely heavily on simulated studies, with simulation being a completely autonomous industry there. And there is also the automotive example, and not to even mention to the emergent virtual reality industry, which in actuality a simulation industry. Here the ambitions are obviously more modest, but the relevance isn’t that smaller:
In this section, we evaluate the performance (and security) of various blockchain instantiations by leveraging our model in Section 3. To this end, we constructed a Bitcoin blockchain simulator in order to evaluate different blockchain instances from a performance perspective. Relying on simulations emerges as the only workable alternative to realistically capture the blockchain performance under different parameters since neither formal modeling, nor the deployment of a thousands of peers (e.g., currently there are 6000 reachable nodes in Bitcoin) would be practical.
By leveraging our simulator, we evaluate different blockchain parameters, such as the block interval, the block size, the propagation mechanisms by measuring the resulting stale block rate, throughput and block propagation times. This also allows us to connect our blockchain simulator to our MDP model in a unified framework. Namely, we feed the stale block rate output by the simulator into our MDP model in order to assess the security (under selfish mining and double-spending) of the resulting blockchain instance.
The video of the talk and conclusion
To summarize here it is the video of the talk delivered by Arthur Gervais at the CCS 2016. Below are the main conclusions and remarks that the paper draws.
In this work, we introduced a novel quantitative framework to objectively compare PoW blockchains given real world network impacts and blockchain parameters. Our framework enables us to evaluate the impact of network-layer parameters on the security of PoW-based blockchain. By doing so, we show how to objectively compare the security provisions of different PoW blockchain instances. Namely, our framework allows us to push the boundaries of PoW powered blockchains in terms of throughput in transactions per second, while observing the impact on the security provisions of the blockchain in terms of optimal selfish mining and double spending strategies.
Our results indirectly suggest that Bitcoin’s blockchain offers more security than Ethereum’s blockchain which rewards miners with uncle rewards and performs uniform tie breaking for blockchain fork resolutions. Our results additionally indicate that existing PoW blockchains can achieve a throughput of 60 transactions per second—without significantly affecting the blockchain’s security. To the best of our knowledge, this is the first contribution that quantitatively evaluates the impact of the stale block rate on optimal double-spending and selfish mining resistance of a PoW blockchain (cf. Figure 7 and Figure 3). By doing so, our results quantitatively capture the security of transactions based on their values, and on the block confirmations—effectively quantifying the level of security achieved by the famous required six block confirmations in Bitcoin.
Our insights do not only allow merchants to take into account the security provisions when accepting transactions and to assess their respective risk of double-spending, but also help miners in quantifying a PoW blockchain’s resilience against selfish mining.
featured image: On the Security and Performance of Proof of Work Blockchains