Auxpow Merged Mining: How Dogecoin Borrowed Litecoin's Hashrate.

A previous post explored src/dogecoin.cpp and ended at a cliffhanger: CheckAuxPowProofOfWork accepts a block whose proof-of-work was done on another chain entirely, as long as block.auxpow->check(...) passes. This post follows that call into src/auxpow.cpp and src/auxpow.h to see what a merged-mining proof actually is.

Since block 371,337 in September 2014, most Dogecoin blocks have been mined this way. For example, a Litecoin miner commits to a Dogecoin block inside the Litecoin block they’re already working on. If the hash they find is good enough for Dogecoin’s difficulty, it counts for Dogecoin too, whether or not it was good enough for Litecoin. The miner does no extra hashing. Dogecoin gets Litecoin-scale security. It’s one of the best trades in the history of the coin.

Now this doesn’t have to be Litecoin as the parent, as the protocol so happens to work, but the original implementation and deployment of merge mining was between Litecoin and Dogecoin, so I’ll use that explanation as a shorthand through the rest of this post.

The code that makes this trustworthy is short, and none of it involves talking to a Litecoin node. Let me re-emphasize and re-state that directly: a Dogecoin node verifies a Litecoin miner’s work using nothing but the data attached to the Dogecoin block itself.

Let’s also offer credit where it’s due: the file header names Vince Durham, who invented merged mining for Namecoin in 2011, and Daniel Kraft, who maintains Namecoin and whose auxpow implementation Dogecoin adopted. This code is older than Dogecoin, and it now secures Pepecoin and other Scrypt family chains too. Hard lessons, once encoded and implemented, travel widely.

What travels with the block

An auxpow block header carries a CAuxPow object. Look at its shape in auxpow.h:

class CAuxPow : public CMerkleTx
{
public:
  /** The merkle branch connecting the aux block to our coinbase.  */
  std::vector<uint256> vChainMerkleBranch;

  /** Merkle tree index of the aux block header in the coinbase.  */
  int nChainIndex;

  /** Parent block header (on which the real PoW is done).  */
  CPureBlockHeader parentBlock;
};

These three pieces, plus what it inherits from CMerkleTx (the parent chain’s coinbase transaction and a merkle branch), together form a chain of custody with two links:

1. The parent block header is where the real proof-of-work lives. CheckAuxPowProofOfWork tests its scrypt hash against Dogecoin’s difficulty, as I explained last time.
2. The parent block’s coinbase transaction, plus a merkle branch proving that coinbase really is in the parent block, plus a commitment inside that coinbase proves that the parent block was built on top of our Dogecoin block hash.

If both links hold, the Litecoin miner must have known the submitted Dogecoin block before they started hashing. The work was done “on top of” a Dogecoin block just as if the miner had mined a Dogecoin block directly.

The check, line by line

CAuxPow::check in auxpow.cpp verifies that custody chain. It starts with correctness checks:

if (nIndex != 0)
    return error("AuxPow is not a generate");

if (params.fStrictChainId && parentBlock.GetChainId () == nChainId)
    return error("Aux POW parent has our chain ID");

The first line insists the committed transaction is at index 0 in the parent block, which is where a coinbase must sit (I can’t explain what “a generate” means; I think it may be a typo, but I’m not sure). The second prevents a Dogecoin block being used as the parent for another Dogecoin block. Without it, one unit of work could be laundered into two Dogecoin blocks.

Every chain in the merged-mining family has a chain ID, and a parent is only acceptable if it belongs to a different chain. Dogecoin’s is 0x62, which is 98 in decimal. The comment next to it in chainparams.cpp just says “Josh Wise!”, a nod to the 2014 community fundraiser that put the Dogecoin logo on a NASCAR. Consensus code and Doge history, one line apart.

Then the two merkle proofs:

// Check that the chain merkle root is in the coinbase
const uint256 nRootHash
  = CheckMerkleBranch(hashAuxBlock, vChainMerkleBranch, nChainIndex);

// Check that we are in the parent block merkle tree
if (CheckMerkleBranch(GetHash(), vMerkleBranch, nIndex)
      != parentBlock.hashMerkleRoot)
    return error("Aux POW merkle root incorrect");

CheckMerkleBranch is the classic Bitcoin merkle walk: start from a leaf hash, repeatedly combine with sibling hashes, arrive at a root. The second call proves the coinbase is in the parent block. The first computes the root of something more interesting: a chain merkle tree, a little merkle tree whose leaves are the block hashes of every chain this miner is merge-mining at once. A big mining operation doesn’t commit to Dogecoin alone; it commits to the root of a tree containing Dogecoin, Pepecoin, Luckycoin, Bellscoin, Namecoin, Shibacoin, and whichever other merge-mined Scrypt coins else, all in one 32-byte commitment.

That root must then appear in the parent coinbase script, marked by four magic bytes defined at the top of auxpow.h:

/** Header for merge-mining data in the coinbase.  */
static const unsigned char pchMergedMiningHeader[] = { 0xfa, 0xbe, 'm', 'm' };

0xfabe6d6d: fabe then mm for merged mining. If you’ve ever seen this string in the coinbase in a block explorer, now you know what it means. The check searches the coinbase script for the header and requires the chain merkle root to sit immediately after it, and requires the header to appear exactly once:

if (script.end() != std::search(pcHead + 1, script.end(),
        UBEGIN(pchMergedMiningHeader), UEND(pchMergedMiningHeader)))
    return error("Multiple merged mining headers in coinbase");

Why so strict? Imagine a coinbase with two merged-mining commitments to two different Dogecoin blocks. A miner could mine once and submit both. The one-header rule, together with the chain-ID rule, closes off every “one unit of work, two blocks” trick the developers could think of. There’s also a backward-compatibility branch for ancient blocks whose coinbases had no header at all; there the root must appear within the first 20 bytes of the script. Old blocks must validate forever.

I’ll repeat that: old blocks must validate forever.

The slot machine that isn’t random

After the root, the coinbase encodes the size of the chain merkle tree and a nonce, and the code verifies that Dogecoin sits at exactly the slot it’s supposed to:

if (nChainIndex != getExpectedIndex (nNonce, nChainId, merkleHeight))
    return error("Aux POW wrong index");

The getExpectedIndex calculation is:

uint32_t rand = nNonce;
rand = rand * 1103515245 + 12345;
rand += nChainId;
rand = rand * 1103515245 + 12345;

return rand % (1 << h);

Those constants, 1103515245 and 12345, are lifted straight from the ANSI C rand() linear congruential generator. The previous post disussed a Mersenne Twister in the block subsidy; this code is a famously bad PRNG doing consensus work.

Here the “randomness” is not really random, and that’s okay. The slot is a fixed function of the nonce and chain ID. A miner can’t put Dogecoin at slot 3 in one submission and slot 5 in another and reuse the same tree for two different Dogecoin blocks. Each chain gets pseudo-randomly scattered to reduce collisions between chains, but the PRNG deterministically pins slots to prevent double-submission.

Even a bad PRNG like this has value in consensus code: it is deterministic and cheap.

The chain merkle branch has a cap at 30 levels, so a single parent block can commit to about 1.07 billion chains at once. Nobody merge-mines a billion chains (at least until the token generators figure out how to make L1 tokens and make a billion rugpulls), but someone thought about the limit anyway. Consensus code needs checked bounds.

What this bought Dogecoin

Before AuxPoW, Dogecoin’s security depended on Scrypt miners choosing Doge over Litecoin, and Digishield could only soften the whiplash as they came and went. After AuxPoW, the economic choice for miners became screechingly obvious: mine Litecoin, get Dogecoin for free.

As you’d expect from ten seconds of economic reasoning, hashrate jumped, and the profit-chasing exodus problem largely dissolved.

The cost is a kind of dependence: Dogecoin’s security budget is now entangled with the economics of merge mining. Whether that’s a vulnerability or a symbiosis is worth thinking about carefully, but every time I think about it, I keep coming back to this indelible point: the 10,000 DOGE per block reward pays miners who were mining anyway, and both Litecoin and Dogecoin were immediately stronger for it on auxpow adoption. The same is true today.

Pepecoin reached the same conclusion a decade later, adopting merged mining after living through its own difficulty swings. If you’re designing a small proof-of-work chain, this file is arguably the most important prior art you can read.

A small chain doesn’t have to buy its own security if it can rent someone else’s.

Code references are to the Dogecoin Core master branch, src/auxpow.cpp and src/auxpow.h. Corrections welcome.