A Technical Q&A on Network Partition Attacks

Cryptocurrencies are prone to many different types of attack. As Bitcoin is over 11 years on the track, we know and were facing many different attempts on breaking its security. One of them is network partition attack.

Cryptocurrency protocols implemented as a top layer of TCP/IP stack in the so-called application layer. It can be said that cryptocurrencies directly use the entire TCP/IP infrastructure. If someone has control power over this
infrastructure, they can hurt all application protocols. This is a general
threat of all cryptocurrencies.

A few weeks ago, after I started my path as an Algorand ambassador, I had an opportunity to interview the leaders of Algorand foundation, Silvio Micali and Massimo Morini.

I asked them different kinds of questions including some more technical ones about network partition attacks, which interest me. Then I decided to go deeper into this topic.

In my eyes, Algorand stands right in the middle of the blockchain trilemma triangle, when the scalability and security are not taking anything from a decentralization degree. Later on, in the article I try to compare Algorand's solution with another blockchain project, which seems to be very far with their development, Cardano. But my first look will go to Bitcoin and its approach to the protection from network attacks.

What is a network attack?

So, what the typical network attack is?

Any decentralized system is susceptible to a network attack in which an adversary targets the communication links between users, making it difficult or impossible for users to interact. An adversary could partition the network into isolated pieces, so that members of one piece can only communicate with each other but not with members of other pieces. During a network partition, the network is completely asynchronous and the adversary has total control over who receives which messages and when. If the partition lasts long enough and the underlying blockchain didn't take this into consideration in its design, then the adversary may be able to convince different groups of users to accept different blocks at the same height in the blockchain. As a result, contradicting transactions will be accepted by different users, allowing the adversary to double-spend their money.

Source: https://www.algorand.com/what-we-do/technology/security

Bitcoin and network attacks

Let’s firstly look upon Bitcoin and its solution on network attacks.

At a high-level, Bitcoin is a randomly-established peer-to-peer network composed of thousands of nodes and tens of thousands of connections which rely on flooding to propagate transactions. As an attacker, being able to prevent the spread of information in such a network seems unrealistic, if not impossible. Bitcoin is surprisingly centralized from an Internet routing perspective: 20% of the Bitcoin nodes are hosted in less than 100 IP prefixes. To put this in perspective, there are close to 600,000 IP prefixes advertised in the Internet today. At the same time, few well-established ISPs (e.g. Hurricane Electric) naturally see a large fraction of the Bitcoin traffic. Together, these two characteristics make large-scale routing attacks surprisingly practical.

Because of its centralization, partitioning the Bitcoin network and isolate 50% of its mining power only requires a small routing attack, one which is orders of magnitude smaller than the attacks routinely seen in the Internet today. Any malicious ISP with access to the Internet routing infrastructure can perform this attack which starts to be effective after only few minutes (according to our own measurements on the live network). Any ISP transiting Bitcoin traffic can delay the propagation of mined blocks (for up to 20 minutes), in a stealth way, even if she sees one direction of the traffic.

Source: https://hackingdistributed.com/2017/05/01/bgp-attacks-on-btc/

Partitioning attacks

With partitioning attacks, an attacker aims at splitting the Bitcoin network into (at least) two disjoint components such that no information (e.g. transaction) can be exchanged between them. To partition the network into two components, a network attacker intercepts all the traffic destined to all the Bitcoin nodes contained within one of the component and drops any connection to the other component. To intercept traffic, a network attacker relies on vulnerabilities in the Border Gateway Protocol (BGP), the only Internet routing protocol used today, which does not validate the origin of routing announcements. These attacks, commonly referred to as BGP hijacks, involve getting a router to falsely announce that it has a better route to some IP prefix. By hijacking all the IP prefixes pertaining to the nodes in one component, the attacker can effectively intercept all the traffic exchanged between the two components. Once on path, the attacker can sever all these connections effectively disconnecting the two components. An animation of the attacks can be found on our website.

Illustration of how an AS-level adversary (AS8) can intercept Bitcoin traffic by hijacking prefixes to isolate the set of nodes P = (A, B, C, D, E). Source: https://hackingdistributed.com/2017/05/01/bgp-attacks-on-btc/

The extreme centralization of Bitcoin from an Internet viewpoint makes partition attacks particularly effective as few IP prefixes need to be hijacked. Indeed, our measurements show that 50% of Bitcoin mining power is hosted in only 39 prefixes (i.e., in 0.007% of all Internet prefixes). This allows an attacker to isolate ~50% of the mining power by hijacking only these 39 prefixes. Much larger BGP hijacks (involving orders of magnitude more IP prefixes) are routinely seen in the Internet today.

By partitioning the network, the attacker forces the creation of two parallel blockchains. After the attack, all the blocks mined by the side with the shorter chain will be discarded together with all included transactions and the corresponding miners’ revenues. Moreover, discarded transactions will be irrecoverably canceled if there exist other transactions in the prevailing branch of the chain which spent the exact same Bitcoins (conflicting transactions).

Source: https://hackingdistributed.com/2017/05/01/bgp-attacks-on-btc/

Proof-of-Work blockchains are vulnerable to network attacks. If an adversary is capable of partitioning the communication network for a couple hours, due to the basic rule where the longest chain wins, he is able to double-spend coins, because the messages sent by set of users A to set of users B is disrupted. So, the adversary is able to construct the longest chain at this point.

This is because blockchain is a communication protocol, which is executed over an underlying communication network. Adversary can then attack the communication network itself by obstructing routers or cables, or even the protocol by sending divergent messages through the network.

If the gains from double-spend attack are exceeding the cost of that attack, this kind of attack definitely should not be ignored.

How can Bitcoin be prevented from network attacks?

In the same article, you can find also the solution, how to prevent network attack for Bitcoin

Fortunately, there are both short- and long-term countermeasures against network attacks. First, peer selections could be made routing-aware. Bitcoin nodes could, for example, aim at maximizing the diversity of the Internet paths seen by their connections to minimize the risk that an attacker can intercept all of them. Moreover, nodes could monitor the behavior of their connections to detect events like abrupt disconnections from multiple peers or unusual delays in block delivery. These events could serve as an early indicator of a routing attack and could, for instance, trigger the establishment of extra randomly-selected connections.

Finally, solutions like end-to-end encryption would also help (especially against delay attacks). Yet, encryption alone would not be sufficient to protect against partitioning attacks as an attacker can still drop encrypted Bitcoin connections.

Source: https://hackingdistributed.com/2017/05/01/bgp-attacks-on-btc/

Let’s consider an attack when an adversary prevents only block propagation and the delegation of hash-rate to pools is not affected. Block propagation is critical mainly for pools since they need to have the latest block(s) in order to maintain the longest chain. If part of pools gets separated from the rest of the network by the attack then from a certain block there will be two groups of pools that maintain their own blockchain and do not know about the competitive chain. Once the attack is gone both groups will be exposed to the competitive chain. Naturally, the longest chain wins. PoW prefers liveness over security. In the ideal case, there is always one block producer and many validators.

There is no measure that would detect the attack and stop the blockchain progression. The rules are simple. Every valid block is a candidate for a permanent addition to the blockchain. In the case of the fork, the rule regarding the longest chain is applied. Thus, the risk of the double spend attack is always present if the network gets split. The routing attack prevention might not be necessarily implemented on the consensus level. It could be prevented on the networking level.

Algorand approach on consensus

Algorand is a decentralized blockchain platform for smart contracts with its native coin called Algo. It uses Pure Proof of Stake (PPoS) to conclude network consensus. Founder Silvio Micali called Algorand “Byzantine Agreement Protocol on Steriods” due its approach to security, scalability and level of decentralization. Algorand can tolerate malicious users as long as the supermajority of stakeholders are non-malicious. The protocol itself is very fast with finality of transactions within 5 seconds and requires minimal computational power per node.

Verifiable Random Functions

The main functional concept used by Algorand is Verifiable Random Function (VRF) for selecting the block proposer and the voting committee members. Verifiable Random Function is a cryptographic primitive similar to lottery that maps inputs to verifiable pseudorandom outputs.

VRFs were introduced by Algorand founder Silvio Micali, Michael Rabin and Salil Vadhan in 1999. VRF is used in Cardano Ouroboros Proof of Stake consensus as well.

Participation and ephemeral keys

For participation in the consensus, users don’t use their spending keys, but for certain number of rounds generates a participation key. Besides the participation key, also collection of ephemeral keys is generated for each round. Those ephemeral keys are signed by the participation key and then the participation key is deleted. With one ephemeral key, the account signs a message for one corresponding round and that key is then deleted and can’t be used anymore.

So, by using participation keys instead of spending keys, ALGO tokens of the user are secured even when the participation node is compromised. And deleting both participation key and ephemeral key after they are used prevents the blockchain from double-using the old keys.

Algorand Consensus Protocol / Block proposal

Algorand's approach is unique in that the block creation and validation are
random due to Verifiable Random Functions (VRF). The Algorand consensus process takes three separate phases.

1. Proposal phase

One ALGO account is randomly selected to propose a new block to the
network. All the nodes of the network then start looping through online
accounts with valid participation keys. The VRF, similar to a weighted lottery, determines if the account is selected to propose the next block or not. So, the accounts with more Algos have a higher probability to be selected.

Once selected, the VRF output of the node proves that this particular
account is a valid proposer of the next block.

Block proposal in Algorand

2. Soft vote phase

In this phase, the number of proposals is cut to one account, who got a
chance to propose the new block. In this process, nodes are verifying the
signed messages and validating the selection by using VRF proof. The account with the lowest VRF hash is set to propose the next block. This is happening within the fixed amount of time so once done, the only account is selected.

Soft vote - 1st part

In the second part of the soft vote phase, nodes run VRF for every participating account to check, if they were validated to participate in the soft vote committee. Chosen accounts will have a weighted vote based on the numbers of ALGOs in the account and those votes will be then propagated to the network. The votes with the lowest VRF block proposal calculated at the timeout will be then sent out to other nodes with their VRF Proof. For each step in the process new committee is selected.

Soft vote - 2nd part

3. Certify vote phase

A committee of 1000 verifiers is pseudo randomly selected to receive information about the new block. Then they verify its validity; they can mark the block as valid or invalid due to the potential problems with double-spending, overspending etc. If the majority agrees up on it, the block is added to the blockchain and this process lasting less than 5 seconds is repeated. In Algorand consensus is enough when a super majority of the verifiers are honest participants, then the block is to be certified.

When the quorum is reached, the node is prompted to create a certificate
for the new block and to write it to the Algorand blockchain. After that, a new round is initiated so the process starts again from the proposal phase of a new block.

But if the quorum isn’t reached in a certifying committee vote by a certain timeout, then the network will enter the recovery mode.

Certify vote phase

Algorand Security

Security is a must in Algorand blockchain, because without security,
there couldn’t be a trust from participants to hold and transact assets with
high value. The network agreement in Algorand is designed to withstand a
long-lasting partition and quick recovery from it. Algorand prefers safety over liveness of the blockchain.

In Algorand, an account participating on consensus protocol must be online. But by not using spending keys for the consensus participation, it is safe to be part of the consensus. So even if those participation keys are corrupted, the user’s funds remain safe.

Algorand resilient against network partition attacks

During a network partition attack on Algorand blockchain, the attacker
isn’t able to persuade two honest nodes to accept two different blocks in the same round. Even when partition may last for a long and indefinite amount of time, this premise remains valid. Due to protocol settings, only one block can be certified and then written into the blockchain in a given round. Besides that, the transactions are then final immediately after writing into the blockchain and stays there forever. So, the subsequent confirmation like in the Bitcoin network is not necessary.

Even though no blockchain can guarantee, that blocks are written to the blockchain during a network partition, Algorand is capable of recovering shortly after the partition is resolved. Then it also guarantees, that the new blocks will be generated at the same speed as before the network partition.

Partition recovery mode in Algorand

When the group of nodes see no progress for a while, the nodes then enter partition recovery mode. In partition recovery mode, the nodes are still continuing the consensus protocol. But besides that, they are periodically sending out recovery messages.

During a network partition, these recovery messages are not propagated
properly.

However, recovery messages are again propagated rapidly as soon as the
partition is healed. When the desired message threshold accumulates, the node states are reconstructed and the blockchain continues to move forward again. Algorand is then recovered almost instantly from network partition, which makes economically expensive to stall Algorand blockchain for the adversary.

Algorand is non-forkable blockchain

One more safety advantage to the network partition attack is, that the Algorand blockchain forking is virtually impossible due to protocol settings. So, the attacker of the network is not able to make a fork of the blockchain and try to propagate it somehow. The balances of the users remain safe all the time.

Weaknesses of Algorand

I can see one weakness as well in Algorand solution, or maybe better to say in this present situation. The token allocation of ALGO tokens in the first years is highly advantageous on behalf of the Algorand Inc. and the Algorand Foundation.

While the attacker could somehow track those tokens or nodes, they might be vulnerable to the communication noise at some level. This is not the critical issue, but until the allocation of ALGO tokens would be more spread around the globe to their users, this is still a valid point of some kind of attack, but not necessarily a network partition attack. This problem should be solved with time and with the diversity of ALGO token allocation.

Cardano approach to network partition attacks

At the end of this article, let me give a look into Cardano network.

Time is split into an epoch in the Cardano network and each epoch into slots. In every slot a randomly selected slot leader gets the right to produce a block. Nobody can deduce in advance who will be assigned to produce a block.

The possibility of committing the routing attack is about the ability of the network to propagate a block. In the case that an adversary is able to split the network and prevent the propagation of blocks then naturally there will be maintained two blockchains in the two separate parts of the networks. If a slot leader fails to produce a block for any reason then the slot remains empty. It will happen during the routing attack.

In every part some nodes will produce blocks and some not. Blockchain progression will be slowed down. After the routing attack the longest chain will win. As far as I know there is no special period when the network would recognize the attack and switch to a kind of recovery mode.

Cardano network works similarly as PoW in the sense of block propagation. There is only one block producer in a given slot and all other full nodes are validators. There is nothing like a special committee that would validate a newly created block. However, there is a special relay network layer that is, hopefully, sufficiently robust to prevent the routing attack.

Sources:

https://www.algorand.com/Algorand%20Protocol.pdf

https://www.algorand.com/resources/blog/algorands-core-technology-in-a-nutshell

https://www.algorand.com/what-we-do/technology/security/

https://hackingdistributed.com/2017/05/01/bgp-attacks-on-btc/

https://cryptodiffer.com/news/code-review-of-algorand-by-incodewetrust-team/

https://pixabay.com/