Examining PoW Blockchains

Zain Admani
Nov 12, 2018 · 7 min read

Now that we have set up the basics of how blockchains work (The Basics) and outlined the main foundation of distributed computing (The Origin of Blockchains), we can now examine blockchains as distributed systems. The main goal is to see what are the EXACT guarantees that blockchains provide and what assumptions they make to achieve these guarantees. For this analysis, I will be focusing on Bitcoin for simplicity and history, but other similar PoW chains, like Ethereum, will also fall into this analysis.

Overview

Famously, Bitcoin-like PoW blockchains boast a tolerance to bad actors that have <50% of the hash rate of the entire network. Notably, this is different than most historical distributed computing research which described security simply as a percentage of nodes that were failing. This re-framing of the problem of security is one of the reasons Satoshi was able to create a whole new way of reaching probabilistic consensus leveraging PoW.

More technically Bitcoin is tolerant to Byzantine failures where the failure nodes have less than 50% of the available hashing ability of the whole network. All important messages are signed so that nodes cannot lie about other nodes’ messages. Blockchains also rely on synchronous networks in order to work properly since they need all nodes to move in lockstep (block updates) and require a partially synchronized clock (timestamps in each block must not drift by a reasonable amount of time).

Consistency/Availability Trade Off

In regards to the Consistency/Availability trade off, blockchains strongly prefer Availability over Consistency which can be seen in the concept of a fork. If 2 valid blocks are mined simultaneously, a fork is formed. What this means is that the network itself is not consistent since some miners accept one chain while others accept another. Miners will accept any valid transactions and try to produce blocks at the expense of possibly causing a fork. And forks can happen in completely normal operation with no malicious actors just by random chance. This is how blockchains rank Availability over Consistency.

Security Guarantees

Another aspect of blockchains that may surprise people is it’s protection against >1/3 of Byzantine malicious nodes in the network that is shown to be impossible by the Lamport/Pease Result. The way it gets around this is by not actually solving consensus but rather solving probabilistic consensus with an additional condition. The additional condition is that no malicious actor can have >50% of the hash rate of the entire network regardless of the number of nodes they control. If this additional condition is broken in Bitcoin then the network is at mercy of the attacker since all transactions can now be changed or halted. Practically, this means Bitcoin comes to a halt and new transactions will not commit.

Another important aspect of Bitcoin is that it technically only solves probabilistic consensus. What this means is that the blocks never reach finality, reaching a state where they can never be changed in normal operations. In Bitcoin, this is because a longer fork can form randomly sometime by lucky miners which can cause the blocks in the shorter chain to become orphans. This is quite important because it means that no transactions in a blockchain are technically guaranteed safe. More clearly, if a merchant was to use a blockchain transaction to sell an item, they would never reach a point where they can trust a transaction will be guaranteed to not change in the future.

Blockchains offer probabilistic finality such that the deeper a block is in the chain, the lower the probability that it will be changed randomly. This probability quickly approaches 0% but never actually reaches it (mathematically speaking). Satoshi estimated the probability that a given transaction will get undone given the number of confirmations and the percent of the network that is owned by an attacker. The attacker’s probability of success can be modeled by a Poisson distribution. I have plotted the probability that a transaction will be reversed given the number of confirmations and different percents of the network owned by an attacker.

Probability that a transaction sent to the Bitcoin network will be reverted. The many lines show the probability changing given different percentages owned by the attacker. It is clear that given a reasonably small attack percentage, very few confirmations can basically give 99%+ safety.

As you can see, this probability quickly approaches 0% when the percent the attacker owns is low. On occasions where the attacker owns less than 10% of the network, even 3 confirmations gets you very close to 0%. It should also be noted that if the attacker controls even close to 50% of the network, the network security guarantees are quickly eroded and at 50% all guarantees are gone.

It should be noted that I am not saying blockchain transactions are insecure, they are just technically not guaranteed to be secure. The probabilistic finality may not be an absolute guarantee, but in real world use it seems to be good enough for users in practice. Users can actually wait for any number of confirmations until they are comfortable with the probabilistic security they are being offered which can actually be seen as a feature.

Network Assumptions

Bitcoin-like blockchains all have strong network assumptions and rely on a synchronous network. This can clearly be seen in the design of the protocol in the way miners add a timestamp in the block header. If a miner’s block timestamp is sufficiently off then the block is not counted as valid. This makes all nodes share a global clock that can’t drift too far.

Obviously, the synchronous network model is not ideal since the internet is not a reliable synchronous network and offers no guarantees for any of its participants. However, it should be noted that this assumption is not as simple as it seems. Blockchains are not complete networks, meaning all nodes are not connected to all other nodes. This is mainly due to the large number of nodes on the network which makes complete networks impossible due to the large overhead and worldwide distribution of nodes. A complete network requires a N² number of network links where N is the number of nodes. The blockchain network is actually an incomplete graph of nodes communicating with each other thru each other.

Complete Network (Left) vs Incomplete Network (Right)

This type of network means that information just can’t be sent from a node to any other node since they aren’t necessarily connected. So the information is spread through gossip protocols where nodes talk to their peers who talk to their peers and so on until all nodes have most likely heard the information. These protocols offer probabilistic guarantees that all nodes will eventually get the messages from other nodes without a huge overhead in number of messages sent.

This framing of the network as a graph can help see exactly why the synchronous assumption may not be too bad. The most important thing nodes must do is broadcast blocks to their peers. Let’s see what is required to transmit a new block from its miner to the rest of the network. At any given moment the most important transfer of information (for safety) is from nodes that have the new block to nodes that don’t. So as long as links between these peers are sporadically synchronous (arguably a close model to the internet), then the block will make it to the whole network with a probability of 100% after some time. Not only that, there are also a huge number of different routes the data can take in a gossip protocol to get to each node (exponential in the number of peers) which further improves the probability of getting a synchronous period and introduces redundancy. Waiting on network propagation is one reason Satoshi went for longer block times and higher mining difficulty.

One thing to note is that this formulation of the network graph makes analyzing the network security of blockchains very difficult and it is still not fully understood. Guarantees of gossip protocols, especially in the real world, are hard to quantify especially considering we can’t detect exactly if the network is behaving synchronously or not at any given moment. Not only that, the large number of routes and nodes that are entering and leaving make quantifying any guarantees very difficult. One thing Bitcoin-like blockchains have going for them is that they have seemingly worked in real world networks for a long period of times without large faults (at least at the protocol level).

Decentralization

One reason for the fragmented, graph-like network and the usage of gossip protocols instead of just building a huge connected network is decentralization. A connected network is limited in number of nodes by network overhead so a fragmented network can support a lot more nodes which enables decentralization. Decentralization is one of the shining benefits of using Bitcoin-like blockchains since it makes sure the system is resistant to manipulation by a few parties. By designing for fragmentation, blockchains are very robust and enable large numbers of nodes that is better for decentralization.

So while a fully connected network would be easier to understand and would have more clear guarantees, it would make the network completely impractical in a system with thousands of nodes. Smaller networks can also go much faster in terms of transactions per second (TPS) since messages take less time to reach all relevant nodes and communications require a lot fewer messages to reach consensus. This decentralization vs TPS trade off can actually be seen a lot in the cryptocurrency space. Chains such as EOS, NANO, and Bitshares which use DPoS (will get into in another post) have substantially higher TPS at the cost of very few voting nodes ( <100 for many of them ). Bitcoin goes the other route and enables very high decentralization with a rather low TPS which makes it a lot more theoretically secure from manipulation.

The holy grail of decentralized computing would be to find a protocol that could support thousands of distributed nodes and also offer extremely high TPS. On the bright side, there is no proof yet that states that this trade off is absolutely required so some new chains may find a way to achieve the holy grail in the coming future. There is a lot of work to do!

Thank you for Reading!

If you have any questions/comments feel free to ask in the comments.

Please stay tuned for more posts!

Blockchains: An Informal Deep Dive

A blog by Zain Admani that documents my deep dive into the…

Blockchains: An Informal Deep Dive

A blog by Zain Admani that documents my deep dive into the technical working and evolution of blockchain technology and distributed systems in general. The goal is to document my findings in the order to help others understand the technology and how we got to where we are.

Zain Admani

Written by

Software Engineer. Computer Scientist. MS in CS @UTexas

Blockchains: An Informal Deep Dive

A blog by Zain Admani that documents my deep dive into the technical working and evolution of blockchain technology and distributed systems in general. The goal is to document my findings in the order to help others understand the technology and how we got to where we are.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store