Last month I published an article on RSK Labs’s blog on how merge-mining works on the RSK sidechain. In this short article, I will deepen[1] the issue of the security of merge-mining RSK, and show how RSK’s security has increased after the last network upgrade. Now RSK merge-mining security could reach a level of security comparable to Bitcoin mining, for users that wait for at least a hundred block confirmations.
Thermodynamic, Game-Theoretic and Cryptographic Security
Nakamoto consensus can be analyzed from three different security angles: thermodynamic[2], game-theoretic, and cryptographic security. Thermodynamic security means that an external attacker who wishes to revert the blockchain must pay a high cost in electricity. Game-theoretic security means that a new non-Bitcoin miner has to invest an enormous amount in hardware and an existing Bitcoin miner that is trying to maximize profit would prefer to stay honest rather than to become malicious (below the selfish-mining threshold). Cryptographic security sometimes means that under some assumptions it is practically infeasible for an attacker to break the protocol, and other times means that some information is perfectly hidden, meaning no computational power will ever uncover it. But Nakamoto Consensus weakest angle is not cryptographic, so we’ll focus on the first two. Merge-mining is not different in this regard. Between 30% and 51% of Bitcoin miners have been merge-mining RSK, which makes RSK the most secure smart-contract platform on the planet in “thermodynamic” security. Still, before the last network upgrade the game-theoretic security of RSK was quite lower. The reason is that RSK, as a native sidechain, lacks coin issuance and therefore depends solely on transaction fees, which are growing but are still low compared to Bitcoin subsidy. This shortcoming would still exist even if 100% of Bitcoin hash rate were mining RSK. RSK relies on the alignment of long term incentives between RSK and Bitcoin: the fact that RSK adds functionality to Bitcoin, and reduces the value of competing cryptocurrencies.
A previous (and probably broken) “solution”
One “solution”, that pops up in forums and blockchain designs[3] over and over again, is to assign a score to the best chain based on the time the blocks were received. The older the chained blocks are, the higher the score. When two branches are compared not only the accumulated PoW is used, but this score is also taken into consideration to decide which one is the “right” best chain. The underlying idea is that when the attacker reveals his hidden branch, even if longer, the network will reject it. But this is not a minor change to Nakamoto Consensus: it changes the consensus protocol completely! Without more assumptions on the network topology and synchronicity, it’s very difficult to prove that this method converges to consensus as it depends on the relative times the blocks are received by individual nodes. In fact, if the attacker is strategically positioned in the network, he or she may be able to cheat a specific node, or even split the network into two disconnected components that will never be in consensus again.
Armadillo
Armadillo is the code-name of a solution to the problem of hidden hashing power in merge-mining, and I designed it specifically for RSK in RSKIP110. A fundamental problem of merge-mining is solved with Armadillo. Before, all merge-mining was subsidized, both honest miners and malicious ones were. After Armadillo is fully implemented, malicious miners will be automatically detected and not subsidized. However, Armadillo has a downside: 51% of malicious miners will be able to prevent the RSK network from confirming transactions. The trade-off is nevertheless very positive.
In a nutshell, the old merge-mining tag is replaced by a new tag that contains some ordered bytes of the Bitcoin block ids related to 7 previous RSK blocks, at fixed RSK block heights that are multiples of 64, in a packed field called Commit to Parents Vector (CPV). We’ll call each of these referenced blocks a “milestone”. Some sample milestones are the blocks at heights 64,128,192,256, etc. Milestones can be reversed as any other block, and they don’t affect how nodes choose the best chain. By checking the existence of overlapping milestones in different tags, an observer can discover blocks that belong to the same branch. More precisely, the shared milestones are detected as overlapping segments in the CPV vector. The following diagram depicts the relation between Bitcoin blocks, RSK merge-mining tags, and RSK blocks (milestones and others) during a double-spend attack that attempts a long reorg.
Figure 1. The timeline of a double-spend attack attempt
Figure 1 represents a period of RSK merge-mining, performed by 50% of the Bitcoin hash rate. The attacker, having 25% of Bitcoin hash rate, will solve, on average, one every 4 Bitcoin blocks. The victim is an RSK Instant Exchange that will exchange RBTC for BTC. Let’s analyze the different events. First, an honest Bitcoin block is mined at height 1000, which refers to an RSK block at height 64, which becomes a milestone. Then, the attacker pays the Instant Exchange 10 RBTC in a transaction T that gets included in RSK block 65 (not shown in the figure). The Instant Exchange is supposed to send the BTC to the attacker after 120 RSK block confirmations (approximately 1 hour later, past the RSK block 185). Right after T gets included in RSK block 65, the attacker tries to build a hidden branch of the RSK blockchain starting from a different RSK block 65 not including the transaction T. While merge-mining, he solves the Bitcoin block 1001, and therefore reveals the RSK merge-mining tag for block 128. The tag doesn’t show a mismatch in milestones because it’s too recent or it represents blocks that are in RSK’s future, but it’s already suspicious because it references a block number (128) that the RSK network has not yet reached. However, the RSK network doesn’t have enough information to signal this as an attack, because it doesn’t reference any non-shared milestone.
In Bitcoin block 1002 there is another merge-mining tag. This time it is a block mined by an honest merge-miner. Since it’s related to RSK block 128, it establishes another milestone. Now the attacker keeps mining his own RSK branch, but, by chance, he doesn’t solve any Bitcoin block. While the attacker is trying to mine a Bitcoin block at height 1003, he mines an RSK milestone at height 192. None of the RSK blocks privately mined between height 65 and height 128 are published. Then the honest merge-miners mine blocks between 129 and 192, including the milestone 192, but none of Bitcoin headers associated with them reach Bitcoin PoW target so they are not included in the Bitcoin blockchain. Now the attacker keeps mining private RSK blocks until block 210. This time the block header (1005) is a valid Bitcoin block. He has the choice to:
- Discard the Bitcoin block and lose the 12.5 BTC (approximately 125K USD at the current rate) in order to keep building a private RSK branch longer than 210 blocks. Keep his RSK private branch.
- Discard the private RSK branch and desist to carry on with the attack.
- Publish the Bitcoin block, hoping that he mines all remaining confirmation blocks required for the attack before nodes are notified about the anomaly exposed by his tags.
The double-spend attack could be profitable if the double-spent amount were greater than 125K USD (setting aside the legal and reputational costs for the Bitcoin miner to be exposed by such attack). Therefore, the Instant Exchange could improve its algorithm to decide how many blocks to wait for confirmation depending on the transacted amount. It could wait for N RSK blocks, plus one additional block per thousand dollars exchanged. Note that this generally works, but it doesn’t take into account composed (simultaneous) attacks, such as concurrent atomic swaps.
In the example, the attacker publishes the Bitcoin block but continues with the attack, hoping that the nodes won’t be notified on time about the anomaly exposed by his tags. But monitoring nodes see the anomaly of two milestones stated in the Block’s CPV field (blocks 128 and 192) that were not shared with the RSK best-chain. This represents a malicious fork of length between 82 and 125 blocks, therefore nodes will stop confirming transactions until the risk dissipates. The attacker will never receive the BTC he originally paid for, so the double-spend attack is neutralized. The anomaly disappears when block 211 is revealed. At RSK block 211, the attacker, who has already outperformed the honest best chain and has mined more than the 120 blocks required by the Instant Exchange, decides to give up, because he doesn’t receive the BTC. He reveals the hidden branch in order to get at least some transaction fees and the RSK network switches to the attacker’s branch, where the transaction T is missing and the RBTC was never sent to the Exchange. During the attack, nodes will be in a “Safe Safe mode” (explained later) and will have paused any economic activity, so they won’t be affected by the reorg.
While the full potential of Armadillo will be reached in following project milestones, the core change to the merge-mining tags that enable the whole system has already been activated. In the future, RSK security could match or even surpass Bitcoin’s security[4]. We must note that Armadillo is not bulletproof: it works well for economic nodes that require a high number of RSK block confirmations (i.e. 120, or about 1 hour), such as two-way pegs and exchanges, but it doesn’t improve security for nodes that accept payments with few confirmations.
New Monitoring Nodes
The full system requires at least a node in the network to be connected to both the RSK network and the Bitcoin network, running a special software module in the RSK node that monitors and detects malicious RSK forks by inspecting the Bitcoin blockchain. The members of the RSK federation are already connected to both networks, so they can easily perform this function cheaply and automatically for the benefit of the network. However, any user can take the role.
To understand what the monitor module does, I’ll first explain the consensus changes that occurred. New data was added to the RSK tag that enables an observer to associate the tags that belong to the same RSK blockchain branch. An attempt to create a parallel chain of RSK blocks can then be detected with high probability by monitoring the tags and reconstructing the graph representing transitive parent-child relations. Even if the RSK blocks mined are never sent to the RSK network, the tags contain enough information to build the probabilistic graph of RSK block parents.
Decentralized Alerts and the “Safe Safe Mode”
A monitoring node recreates the graph of RSK block relations on the arrival of every new Bitcoin block[5]. The first monitoring node to create this graph will be the first to detect a malicious fork, and it will create and broadcast a decentralized alert called Malicious Fork Proof (MFP). An MFP consists of multiple SPV proofs containing interconnected block headers together with the associated RSK tags (via Merkle membership proofs), and additional confirmation headers if needed. All headers serve as proof of work, and set a minimum cost for the creation of fake proofs. This prevents alerts spam. An MFP can prove the existence of a non-best branch consisting of a high number of RSK blocks. Figure 2 shows how an MFP is built by a monitor node. As soon as the node detects a fork, an alert will be broadcast. Also, a new MFP will be distributed every time the attacker mines another Bitcoin block and the fork persists. The Instant Exchange node will remain in Safe Safe Mode and refuse to accept the RBTC deposit (and any other transaction) until the alert automatically clears after the honest best-chain has outpaced the attacker’s branch or otherwise. The following diagram depicts how alerts are propagated.
Figure 2. Alert messages (MFPs) are propagated thought the RSK network
All RSK nodes are able to verify a received MFP and, if it’s correct, forward it to all connected peers, even without being connected to the Bitcoin Network. RSK nodes that receive valid MFPs can extract information about when the attack will take place (block numbers) and enter a Safe Safe Mode during this interval.
Historically, Bitcoin had a “Safe Mode”. A Bitcoin node would enter this mode upon reception of a valid alert message, and in this mode it would not confirm any transactions through the UI nor through the RPC interface. The problem with Bitcoin’s Safe Mode is that it was centralized: alerts were centrally issued and signed by a private key that too many developers had access to. But RSK MFPs are fully decentralized and self-verifiable. They can be produced anywhere and producing a fake proof carries a high cost in PoW. This means that an attacker that wants to hide a selfish RSK branch must renounce to mine Bitcoin during the attack. A back-of-the-envelope calculation yields that a 200 RSK block (1.5 hours) reorg attack costs about 300K USD, for a mining pool having 25% of Bitcoin’s hashrate, while the same attack in Ethereum costs 200K according to crypto51.app.
The New Tag Format
The 32-byte block header hash is replaced by a 32-byte byte array with the following format:
- 20-byte prefix of the hash-for-merge-mining (PREFIX)
- 7-byte Commit-to-Parents-Vector (CPV)
- 1-byte number of uncles in the last 32 blocks (NU), limited by 255.
- 4-byte Block Number (BN)
Figure 3 shows the transformation of the tag.
Figure 3. The old and new merge-mining tags
The four fields must be checked in consensus. The hash of the RSK header is truncated to 20 bytes so that the tag still occupies 32 bytes, therefore maintaining compatibility with poolservers software. The NU value is used to predict the difficulty of the attacker’s branch, because in RSK difficulty depends on the number of uncles per block.
The Security of the New Tag
We’ve set our goal that RSK merge-mining be safe from any rational attacker and also from an irrational attacker with the capability of computing 2^80 hash operations in not less than 30 seconds. We ensure that the rational attacker would prefer to behave honestly and merge-mine an RSK block requiring only about 2^69 operations (the current difficulty of an RSK block) and being fully subsidized by Bitcoin, rather than to carry on the costly attacks. We do not consider the possibility of the composability of this attack with other merge-mined systems (which apart from namecoin, do not yet exist).
An irrational attacker that attempts to perform 2^80 hashing operations would need to invest 2000 times more hardware than the rational miner, and its electricity consumption would not be subsidized. The investment would amount about five trillion dollars (5e12), assuming the attacker uses hardware similar to state-of-the-art Bitcoin ASICs. But things are even worse for the irrational attacker, as it can produce one or more blocks that share the proof of work for the same RSK block height, and we’ll see later that this does not generally provide any monetary gain to the attacker [6]. So that’s five trillion dollars wasted. Therefore the 80-bit-security is well balanced across all components, and there is no component with substantially weaker security that can be a target of attack. To justify this, we’ll shortly and informally review possible targets of attack.
First, RSK compresses the generation transaction with a non-standard cryptographic trick. Instead of providing the full generation transaction, it transmits only the tail. To still be able to produce the right cryptographic hash of this message, it starts hashing from a midstate of the Merkle–Damgård construction, instead of the initial state. This 64-byte midstate is transmitted along the tail.
Figure 4 shows the merge-mining proof. The blue boxes represent the data that is actually included in the proof.
Figure 4. The merge-mining proof (blue) comprising only the tail of the generation (or coinbase) transaction.
Securely using this trick requires assuming a property from SHA256 that is stronger than collision and pre-image resistance, known as “freestart collision” resistance, and we need this to be at least as secure as brute-forcing 80 bits, which is our target security threshold. SHA-1 (an already broken hash function) has a best known free-start attack that requires brute-forcing about 80 bits. No freestart collision has been found in SHA256, and the best results[7] correspond to finding semi-free-start collisions in a reduced-round version of SHA256 (38 of the 64 rounds, at a cost of 2^65 operations), so we can conclude that RSK merge-mining is safe. It must be noted that a supposed free-start attack on SHA256 requiring 2^80 operations would be devastating for SHA256 and would render it useless as a secure standard hash function, and Bitcoin would be in trouble anyway. But if such attack is ever discovered, the RSK platform could be easily protected by a network upgrade not to use this cryptographic trick for merge-mining proof compression, at the expense of a small increase in block size. However, as we stated before, even if the attack would cost less than merge-mining in terms of bit-security, it would not be cost-efficient.
Second, with respect to the truncation of the hash digest activated in the 1.0.0 release, the new scheme provides the equivalent of 80-bit security for tag collisions. However, the attack is theoretically, economically, and computationally irrational. From the computational complexity point of view, an 80-bit collision attack would require the use of an unrealistic amount of memory [8]. Also, the CPU cost of the collision attack is more than 2000 times higher than the cost of solving the RSK PoW puzzle (69 vs 80 bits).
From the theoretical point of view and due to the DECOR+ consensus used in RSK, because the collision can only occur at the same RSK block height, the colliding blocks would share the block reward, so there is no benefit to find new siblings of past blocks if the past block reward is approximately equal to the reward of a new block. The attacker would be mainly competing against himself. For the same reason, there is no benefit to find collisions for new blocks, with the added difficulty that it must be performed within 30 seconds on average, instead of 5 minutes available to reference uncles.
From the economic point of view, an honest merge-miner earns Bitcoin transaction fees, so merge-mining is subsidized by Bitcoin, while the attacker has to pay the full cost of the collision attack. This makes almost any attack on the PoW linkage not cost-efficient. This is valid for both, hash digest collisions on the RSK block hash and the free-start collisions on the coinbase transaction hash.
Therefore we think the tag is secure for the next 10 years, even considering a breakthrough in computing efficiency. However, if computing trends radically change, a future network upgrade could easily expand back the size of the hash to the full 32 bytes and we could also add more block references to the CPV field.
Summary
Almost half of the Bitcoin hashrate is currently merge-mining RSK. However, until the 1.0.0 release, the security of RSK was lower than Bitcoin’s. This is because RSK, as a native sidechain, lacks coin issuance and therefore depends solely on transaction fees. Without block subsidy, the incentives to follow the rules vs to double-spend are lower. With Armadillo, a feature already available, RSK can become as secure as Bitcoin for transactions requiring at least a hundred confirmations, with the only downside of slightly reducing network liveness under active attacks.
References
[1] This article also reproduces some parts of the original article.
[2] Once a transaction is confirmed in a block it can’t be reversed without someone expending a minimum amount of energy to rewrite the chain. This energy is known as the “thermodynamic” security of a PoW-based blockchain.
[3] https://www.horizen.global/assets/files/A-Penalty-System-for-Delayed-Block-Submission-by-Horizen.pdf and https://hal.archives-ouvertes.fr/hal-01310088v1/document
[4] RSK receives hashing power not only from Bitcoin, but also some from Bitcoin Cash! If RSK received all hashing power from Bitcoin plus some from Bitcoin Cash, it would surpass Bitcoin hashing rate.
[5] Note that the Bitcoin blocks processed don’t need to be part of the same branch if they are close to the tip, but due to the low number of orphans in Bitcoin, it makes sense to process only the best chain.
[6] Another interesting attack would be to use tag collisions to create blocks for several competing chains in parallel, all with the same accumulated difficulty, and feed each other miner with a different “best chain” in order to prevent them to work in the same best chain. It requires having direct peer-to-peer connections with the other miners. It could work if the attacker has less hashing power than the remaining miners together but vast more hashing power than the remaining miners separated. Still, this attack would be much more costly than just performing a 51% attack to ignore other miner’s blocks.
[7] https://eprint.iacr.org/2015/350.pdf
[8] The RAM memory required by a simple collision attack is 2^80 hash digests (32 million exabytes). Using the Oorschot/Wiener algorithm, and assuming a single processor can perform 2^40 sequential hash operations in less than 30 seconds, the RAM memory requirement could be reduced to 32 terabytes.
Bitslog 