Modern Merge-mining
The Bitcoin community welcomes Bitcoin sidechains because they are increasing Bitcoin’s utility now and probably they will do even more in the future. The RSK sidechain was specially designed to provide incentives aligned with the Bitcoin community. It incentivizes the participation of bitcoiners, the Bitcoin wallets, and specially Bitcoin miners by using a consensus protocol based on merge-mining. Merge-mining is a technique to re-utilize proof-of-work from one blockchain to secure another. The way it works is simple: miners add the hash of a new block of another chain to Bitcoin blocks, and then they start trying to find the proof of work that matches the difficulty established by the Bitcoin network. However, if while searching they find a Bitcoin block with proof of work that matches the difficulty of the merge-mined chain, then that Bitcoin block header becomes a valid proof of work of the merge-mined block and both the Bitcoin header and merge-mined block are sent to the merge-mined chain network to be included in its blockchain. Merge-mining allows the creation of blocks at a higher rate than the primary chain block rate. This has several benefits such as reducing the reward payout variability and providing faster transaction confirmations. For all existing ecosystems that accept merge-mining, one of the blockchains is the primary chain, which is the chain whose block header possesses the proof of work in its block header hash. The others are secondary blockchains, whose blocks are linked from primary chain blocks. The only requirement to re-utilize proof of work when mining a primary block is that the link to the secondary blockchain block is unambiguous, to avoid that the same amount of work is used to supply proof of work for two different blocks of the same blockchain.
Merge-mining, or merged-mining, is almost as old as Bitcoin: the cryptocurrency namecoin began merge-mining with Bitcoin in 2011 to achieve stronger security. Later other blockchains followed. Merge-mined consensus has been formally analyzed and criticized. However, most researchers and users reason about merge-mining based on the outdated consensus model introduced by namecoin. The launch of the RSK Bitcoin sidechain, a smart-contract platform that is secured by merge-mining with Bitcoin, revived the research of more secure merge-mining protocols. The result was a new wave of theoretical and practical developments on merge-mining, which have now become fundamental to understand the potential of this technology. The new models disprove some common misconceptions about merge-mining security. For example, it is generally believed that a merge-mined sidechain can’t be secure against double-spends even when the merge-mining hashrate or its block rewards are low. Here we’ll discuss how it can be secure.
The Namecoin Merged-mining Design
The way namecoin merge-mines with Bitcoin is simple. At the end of the coinbase field of the generation transaction the miner writes 4 bytes that indicate that an AuxPow record follows. These 4 bytes are called magic bytes and are used to find the AuxPow record easily. Next we find the AuxPow record where the miners must store the root hash digest of a Merkle tree containing the block hashes of the different blockchains that are being merge-mined. Then the treeSize field follows, which specifies the number of merge-mined blocks of distinct blockchains included in the tree, and a treeNonce field that is supposed to help avoid collisions of chain ids, but the design is flawed and this value is unused. The following diagram depicts a Bitcoin block carrying an AuxPow record linking to 4 blocks (W,X,Y, and Z) from 4 different merge-mined blockchains:
To allow namecoin nodes to verify the proof of work of a namecoin block, the namecoin block must include a Merkle path to find the Coinbase transaction in the Bitcoin transaction tree, then the coinbase transaction itself, and finally a Merkle path to find the namecoin block hash in the AuxPow tree. Apart from the design of AuxPow data structure, there is an underlying Namecoin consensus model which is simply to verify the proof of work of the Bitcoin header and ignore all other fields.
Primary Chain Distinction
From a game theory perspective, there is no primary blockchain. We distinguish a “primary” blockchain from all merge-mined “secondary” blockchains only because a secondary blockchain block needs an additional Merkle proof to allow the verification of the proof-of-work. In fact, a merge-mined blockchain can grab proof of work from more than one primary chain, as is the case of RSK. While most of the RSK hashrate comes from Bitcoin miners, there were times where a small portion of the hashrate came from Bitcoin Cash. This cannot be avoided, as from RSK consensus perspective Bitcoin and Bitcoin Cash block headers look identical. The existence of a primary chain is a purely syntactic distinction. During the 2011–2013 period there were several proposals published in forum bitcointalk.org about Bitcoin hard-forks to abstract out the Bitcoin proof of work in a separate “master” header-chain, and make all merge-mined blockchains’ blocks (including Bitcoin’s) derive from this master headerchain as part of a Merkle Tree. Still, something not previously considered is the fact that the master header does not need to be part of a chain at all. The header can only specify a Merkle tree root of chain blocks and the nonce, although having a timestamp field in it could improve the security of all merge-mined chains, as we’ll see later. This imaginary structure is depicted in the following figure where X and Y refer to some other merge-mined blockchains:
If this data structure had been adopted, there wouldn’t be any primary blockchain. When we analyze the incentives for miners to secure more than one blockchain with the same proof of work, we must analyze all of them as secondary chains, or we can call them simply merge-mined chains. To analyze merge-mining incentives we should think about SHA256D miners (the actual hash function used) instead of Bitcoin miners. We must analyze all merge-mined blockchains and the incentives that blockchains provide to miners. The fact that SHA256D miners care about Bitcoin and RSK is the result of the shared incentives and shared communities, not the other way around.
Cross-chain Cryptoeconomic Consensus Rules
One of the possibilities not considered by the namecoin consensus model is adding to one of the merge-mined blockchains consensus rules based on data extracted from the block headers (or the block contents) of other merge-mined blockchains. Therefore one chain can influence or benefit from what happens in the other. When we have such rules, we call the first blockchain, source blockchain, and the rule, the source cryptoeconomic rule. Reciprocally, there is a target blockchain and target cryptoeconomic rule. For example, imagine a merge-mined chain X that shares 90% of the hashrate with Bitcoin, and the merge-mined chain mandates that the Bitcoin block must pay 0.1 BTC to a random output address created in the prior Bitcoin block, as in a raffle. The following figure depicts a possible state of the involved blockchains:
In the figure, the miner of X block 27 has opted to discard its merge-mined Bitcoin block, to avoid paying the raffle. The eventual miner of the Bitcoin block 102 opted not to merge-mine the chain X, and did not have to pay the raffle.
This is an example of a source rule that highly conflicts with the primary chain’s natural incentives: the new rule may lead Bitcoin miners to exclude any transaction with a fee lower than 10k satoshis/kilobyte. They would instead prefer to fill the remaining block space with a self-paying transaction containing the maximum number of outputs. A seemingly innocent source rule induces a target rule that has undesired effects. The Bitcoin community must always analyze cross-chain consensus rules carefully, as the source rules are defined in other blockchains.
RSK’s Timestamp Linking Consensus Rule
RSK will soon activate one powerful cross-chain consensus rule that is incentive neutral to honest Bitcoin miners. The Iris network upgrade adds a rule which mandates that the RSK block timestamp must not be too distant from the Bitcoin block timestamp for the RSK block to be valid. This source rule improves RSK security and creates a cryptoeconomic target rule that incentivizes increasing Bitcoin timestamp accuracy. However, RSK does it without harming Bitcoin. The Bitcoin protocol does not need precise time synchronization and RSK avoids introducing a new requirement by being very lax regarding the maximum time difference between RSK and Bitcoin timestamps.
A Vigilant Community
A cross-chain source rule is always intrinsic and explicit, while a target rule is extrinsic and implicit. Both of them are cryptoeconomic because the miner can always lie about a target blockchain block, in order to verify the source rule or avoid merge-mining not to comply with the source rule, but doing any of these has the cost of being unable to claim block rewards in the other blockchain. We’ve prefer to speak about “cryptoeconomic rules” and not just “mining incentives”. There is a thin line that separates them. If the majority of miners modify the code that creates a block template in response to an external incentive that is provided fairly to all miners, and that incentive is substancial, then the practical effect is no different than if the cryptocurrency consensus code would have included the incentive as a explicit rule and paid an extra fee for miners that obey the rule.
What is important to highlight is that Merge-mining is not needed (not even a sidechain is needed!) to create a cryptoeconomic rule that affects Bitcoin miners. A bribing attack to incentivize the Bitcoin miners to adopt a specific soft-fork can be created in any smart contract in a random blockchain. An Ethereum contract could do it, with the help of a stateful Bitcoin block relay, such as the once active btcrelay or currently active tBTC relay. This possibility was identified and documented together with a family of attacks known as cross-chain briberies, introduced in several papers. These attacks only require a Turing-complete smart contract platform. The great power that the Bitcoin community has to prevent any malicious incentives operating on Bitcoin miners is the threat of a User Activated Soft Fork (UASF). A UASF can easily ban blocks following any malicious extrinsic consensus rule. The Bitcoin community realized the power of the UASF threat in 2017: now miners attempting to maliciously soft-fork Bitcoin fear retaliation.
Bitcoiners need to be critically vigilant about new Bitcoin miner incentives coming from any blockchain in existence.
Existent Incentives to Secure Merge-Mining
There are various reasons why namecoin has resisted 51% attacks from Bitcoin miners even during the times namecoin was secured by a small amount of Bitcoin hashrate. The first is that namecoin was not considered to compete with Bitcoin. One of the oldest bitcointalk.org users described namecoin in 2011 in the following way to justify merge-mining:
“Namecoin is somewhat unique because it is established, has some value, provides a useful non-competing function, and has decent liquidity. Attributes all “scamcoins” lack.“ — DeathAndTaxes, https://bitcointalk.org/index.php?topic=47898.0
Non-competing with Bitcoin was the main reason namecoin was not attacked by Bitcoin miners and the Bitcoin community. The opposite did happen: the competing blockchain CoiledCoin was attacked by the Eligius mining pool in 2012 without pangs of conscience.
There are two other incentives that protect Bitcoin mining and merge-mining that have seldom been discussed in the context of proof-of-work:
- Proof of work may incentivize Covert Adversaries but not arbitrary malicious parties.
- Proof of Work provides attack preannouncement
Paraphrasing the linked paper, covert adversaries have the property that they may deviate arbitrarily from the protocol specification in an attempt to cheat, but do not wish to be “caught” doing so. If there is a high probability of being caught, they won’t attempt to cheat. While covert adversaries can be considered rational actors, rational behaviour is generally analyzed limited to short-term consequences, and the disincentive to attack due to retaliation is seldom considered. However, if any Bitcoin mining pool operator or Bitcoin miners were malicious, it would be a covert adversary and not an overt one: mining pools operators’ identities are known in the ecosystem, and they can be tracked and prosecuted, their accounts in online exchanges can be blocked. Mining activity requires so much space and consumes so much electricity that it’s very hard for miners to hide their real-world identity from authorities when operating large mining facilities. The difficulty to anonymously acquire 51% of Bitcoin’s hashrate operates in Bitcoin’s favour.
The second property seldom discussed is attack preannouncement: either the attacker acquires enough ASICs at once to surpass all the existent hashrate (which is impossible due to ASIC production bottlenecks) or the attacker must buy, redirect or control 51% of the existing hashrate and put it to work on a hidden reorg. This would be immediately noticed by the Bitcoin community, who can perform several preventive actions, such as increasing the transaction confirmation blocks to hundreds, and contacting the missing mining pools to find out the reason the hashrate is missing. Therefore, any attempt to double-spend a large amount can be detected before the attack materializes. This is a strong deterrent that can only be provided by proof-of-work, and not by proof-of-stake consensus systems.
Anyway, we’ll see in the following sections that there are new merge-mining variants that provide blockchain reorg protection for long reorganizations, elevating the security of the sidechain to the security of Bitcoin.
Fork-Aware Merge Mining
In the namecoin consensus model, a merge-mined chain block hash is hidden in a Merkle tree (originally called AuxPow). Therefore, users watching Bitcoin AuxPow blocks do not know which other chain blocks are being merge-mined. Nor can they compute how much hashrate is merge-mining a specific chain. This model lacks an important property that Bitcoin already offers that I call Cryptoeconomic Merge-Mining Data Availability (CMMDA). CMMDA allows users to retrieve per-chain merge-mining information, and establishes a base cost miners must pay if they want to hide it. Adding CMMDA to merge-mining is simple, yet compressing the highest amount of information in the smallest space is not. We start with the simple approach: we remove the AuxPow tree altogether and we flatten the block hash data. The last coinbase transaction output will contain in its script an OP_RETURN opcode followed by an array of block hashes, each one preceded by a chain identifier. The following figure depicts this new design:
The data which comprise the merge-mining information is called the merge-mining tag. To simplify the following examples, we also assume that the Bitcoin difficulty is higher or equal than any merge-mined chain difficulty. By looking at the tags, anyone can compute the hashrate participating in merge-mining a chain X. They can also compute the hashrate of the honest chain of X by running a full node of X, which should not be higher than the estimated hashrate from the Bitcoin chain. With this information, they can compute the hashrate difference, which is a cryptoeconomic bound on the hashrate participating in the merge-mining of a competing fork of X. The exact Bitcoin blocks that are merge-mining a malicious fork of X can be identified by taking all the merge-mining tags whose block hashes do not belong to the honest chain of X. We call them “hidden” blocks of X.
With the proposed data structure, we can’t be sure if the hidden blocks are linked in a chain or they are sparse orphaned siblings for distinct parents. They could even be random hashes added by some miners just to confuse the users of X. However, we can assume the worst-case scenario and raise the awareness of the community when the hashrate accumulated by hidden blocks is higher (or better, close to) the hashrate of the honest chain of X. Why not strictly higher? Because the evidence collected through CMMDA is cryptoeconomic, which means that the attacker may discard some Bitcoin blocks (and lose their reward) to hide his actual hashrate. Nevertheless, for this same reason, for each amount of hidden hashrate detected we can also establish a minimum bound for the cost to attack X. The higher the hidden hashrate, the lower the additional cost to perform a double-spend attack.
Assuming both X and Bitcoin have the same block difficulty, we don’t really need to inspect block hashes published in the Bitcoin coinbase transaction, as we know that any block in the honest chain of X should have an associated Bitcoin block, then any Bitcoin block referencing a block hash in X that has not been referenced back by the honest chain of X, must be counted as malicious. Therefore, if we cap the number of merge-mined chains to, for example, 64, then we can keep the AuxPow Merkle tree, and only add a 64-bit bitmap where we signal if a certain chain is present or not in the tree (a rule that the corresponding bit in the bitmap must be set should be verified by a consensus rule of the merge-mined chain). This new design is depicted in the following diagram:
One of the nice properties of CMMDA is that any user running both Bitcoin and a network node of X user can build a stateless cryptoeconomic (also probabilistic) proof of an ongoing attack to X and distribute it over the X network, and X nodes could halt transaction confirmation and enter a safe mode to avoid double-spends until the threat disappears. Informally, we can say we sacrifice some of the sidechain liveness (the property that states that transactions will eventually confirm), and we highly improve soundness (the property that states that transactions will not be double-spent).
However, a block hash of a hidden block of X is not enough to distinguish between the following scenarios:
- A miner’s node connection to the network is slow, and therefore the connection latency forces the miner to create an excessive amount of orphan blocks.
- A miner’s node does not correctly synchronize with the tip of the honest chain, and therefore it is mining a fork from an old point in time.
- A miner is creating a malicious concurrent fork of the honest chain.
The first two scenarios may be common, and it’s not ideal to penalize the network by freezing transaction confirmations if a mining pool malfunctions. The approach taken by RSK to distinguish between these scenarios is to add additional information to the merge-mining tag. It adds cryptoeconomic pointers to equally spaced ancestor blocks, therefore by looking at two merge-mining tags we can detect how far is the closest forked point or establish that both blocks are part of the same fork with high probability. This is specified in RSKIP110, and the design rationale can be found here. The RSK community also created a fork monitoring system called Armadillo.
Still Armadillo wouldn’t be as powerful as it can be without Timestamp linking. Timestamp linking is an RSK source consensus rule that prevents merge-miners from backdating a block timestamp. If a minority of Bitcoin miners try to backdate an RSK block, they need to also backdate a Bitcoin block. Backdating Bitcoin blocks with minority hashrate is limited to, on average, at most one hour, due to a Bitcoin consensus rule on timestamps (a block timestamp must be higher than the mean of the last 11 blocks).
We can split double-spent attacks to Nakamoto consensus in two classes: Revert After Confirmation (or RAC) and Revert During Confirmation (or RDC). The first starts after the victim has accepted the first spend of a double-spend, and the second starts before the first spend is accepted. If a RAC attack is attempted to RSK after activating the timestamp linking consensus rule, minority miners cannot backdate blocks anymore, which means that the only option to the attacker is to create a fork of the blockchain at an old block number, but use correct timestamps, creating a timestamp gap. This attack can be prevented by adding a consensus rule to RSK that penalizes forks with large timestamp gaps. One promising penalization strategy is to construct a transfer function from block PoW to cumulative difficulty that decreases as the block timestamp variance increases. However any penalization strategy only increases the hashrate threshold that the attacker requires to finally revert the blockchain and succeed to double-spend, but will not prevent the double-spend. Later we’ll see a new sidechain technology called Syncchains that fully prevents this attack. In the following figure, each block label represents the timestamp put on the block (not the time it was mined):
In the diagram, orange blocks are the blocks created by the attacker, and blue blocks are blocks created by the remaining honest miners. The green block is also an honest block but represents the moment the victim accepts the first spend (for example, an exchange confirms a deposit).
If miners cannot backdate the RSK blocks of a malicious fork and cannot easily continue an old fork, then a double-spend attack must be concurrent to the period the potential victim is waiting for the confirmation of the first spend (the Revert During Confirmation attack). The following figure depicts the RDC attack:
The benefit of preventing RACs is that RDCs can be deterred with alerts raised by the presence of hidden blocks in merge-mining tags. The potential victim can listen to such alerts and avoid confirming the first spend, therefore preventing the double-spend. On alerts, nodes can enter a safe mode where they keep accepting and broadcasting blocks and transactions, but they stop providing transaction confirmations to the user or to connected applications (i.e., communication over the node RPC interface is suspended). The following diagram depicts how Armadillo alerts prevent RDCs:
While this does not eliminate all incentives for blockchain reorganizations, it does prevent double-spends, eliminating the strongest incentives to reorganize the chain (MEV-related and fee sniping incentives to reorganize the blockchain will still subsist).
We coined the term Fork-aware merge mining to the combination of Merge-mining Data Availability, a Fork detection system, the timestamp linking rule, and nodes being able to respond to fork alerts by automatically entering a safe mode where transactions are not confirmed. However, we can do better! Welcome to Inclusive Fork-Aware Merge-Mining.
Inclusive Fork-Aware Merge-Mining
If a merge-mined chain does not provide enough value to miners, there will be miners who ignore merge-mining and mine only the primary chain. The miners that mine only the primary chain are considered neutral from the perspective of the merge-mined chain: as they don’t care about the chain’s consensus rules, somehow they are confirming with their blocks whatever merge-mined block was last linked by the merge-miners, be it honest or malicious.
This means that provided there is no ongoing hidden attack on a merge-mined chain, the neutral miners’ blocks are confirming the honest merge-mined chain. The neutral blocks can be picked by the merge-mined chain and used as confirmation hashrate just like uncle blocks in RSK. This means that a merge-mined chain X having only 1% of the total hashrate can “borrow” the remaining 99% of the hashrate as long as that 99% is neutral. The consensus rules of the merge-mined chain X will accept confirmation blocks only if they do not have a merge-mining tag related to X. This figure depicts how neutral blocks are currently wasted:
The following diagram shows how the neutral blocks can be assigned to a sidechain fork, as confirmation hashrate:
To prove that a block N is confirming a merge-mined block B and no other block, it is necessary to prove that N is neutral and N’s parent is either also neutral or it is B. Proving that a block is neutral involves showing that it doesn’t contain any block hash for the merge-mined blockchain of B. We call this a chain exclusion proof. The AuxPow bitmap provides an easy way to support chain exclusion proofs. When a sidechain is excluded from AuxPow the corresponding bit in this map should be unset. The end result is that while there is no attack (most of the time) a secondary merge-mined chain can inherit 100% of the Bitcoin hashrate (in practice it can inherit more hashrate than Bitcoin, as it can merge the hashrates of Bitcoin and other Bitcoin forks!). Implementing this technique seems simple, but the devil is in the details: some precautions must be taken not to increase the selfish mining incentives when the sidechain block difficulty is much lower than the mainchain difficulty. For RSK there is a fully specified proposal to adopt Inclusive Fork-Aware Merge-mining that may one day be activated.
The most interesting and still unexplored feature of Inclusive Fork-Aware Merge-mining is that it can be performed simultaneously with several proof-of-work blockchains (i.e. odd blocks have bitcoin PoW and even blocks have ZCash PoW). If the PoW functions are not efficiently mined by the same hardware, then the end result is that the resulting sidechain’s thermodynamic security is equal to the sum of the merge-mined chains!
Bootstrapping a New Sidechain
We have shown that a sidechain can be bootstrapped even starting with a low merge-mining hashrate if Inclusive Fork-Aware Merge-mining is used. But we also showed that the Revert-After-Confirmation Attack without backdating can still revert the sidechain if the attacker’s hashrate is high enough. Therefore, for bootstrapping new sidechains we propose to implement them as Syncchains. Syncchains are a new kind of Bitcoin sidechains that are synchronous with Bitcoin, which means that to perform a long reorganization of the sidechain, an attacker needs to also reorganize the Bitcoin blocks. Merge-mined Syncchains have one huge benefit compared to the standard merge-mined sidechains: they inherently provide a federated peg-in and peg-out mechanism that is fast and immune against double-spends. It’s also possible to start a sidechain as a Syncchain, and then turn it into a standalone sidechain, by adding a Bitcoin relay as a sidechain smart contract. Is much easier to do the opposite if the sidechain already has a BTC relay, by forwarding the Bitcoin headers and the Bitcoin peg-in transactions from Bitcoin to the Bitcoin relay contract as part of consensus (and disabling these method calls from sidechain users and contracts).
Summary
In this post we’ve described the namecoin merge-mining design, and we’ve shown a more generic design to illustrate that merge-mining can be blockchain neutral in terms of data structures and algorithms used, but it will never be neutral in economical terms: competing blockchains do not incentivize shared merge-mining. We also presented a new type of cross-chain consensus rules that are powerful, yet they should be designed carefully not to disturb Bitcoin mining incentives. We described the Inclusive Fork-aware merge-mining variant that makes merge-mining highly secure even with low hashrate engaged. This technique comprises several complementary sidechain consensus rules, including a cross-chain rule on block timestamps. We also presented the Syncchain protocol that can be used by new sidechain builders to bootstrap new merge-mined sidechains securely.
Thanks to all IOV Labs researchers that provided valuable suggestions to improve this article! Visit https://innovation.iovlabs.org/
