Merged mining specification

NOTE: This standard is used by Namecoin, but new merged mining data should likely propose a new BIP to supercede it with something based on p2pool's merged mining.

Terminology

Auxiliary Proof-of-Work (POW)

a.k.a "AuxPOW". This is the way that merged mining can exist; it is the relationship between two blockchains for one to trust the other's work as their own and accept AuxPOW blocks.

Merged Mining

The act of using work done on one blockchain on more than one chain, using Auxiliary POW.

Auxiliary Blockchain

The altcoin that is accepting work done on alternate chains as valid on its own chain. Client applications have to be modified to accept Auxiliary POW.

Parent Blockchain

The blockchain where the actual mining work is taking place. This chain does not need to be aware of the Auxiliary POW logic, as AuxPOW blocks submitted to this chain are still valid blocks.

Parent Block

Not to be confused with the "previous block". This is a block that is structured for the parent blockchain (i.e. the prev_block hash points to the prior block on the parent blockchain). The header of this block is part of the AuxPOW Block in the auxiliary blockchain.

AuxPOW Block

This is a new type of block that is similar to a standard blockchain block, with two important differences. Firstly, the hash of the block header does NOT meet the difficulty level of the blockchain (so, if interpreted by a naive client, will be thrown out as not meeting the difficulty level). Secondly, it has additional data elements that show that the miner who created this block actually did mining activity (hashing) on the parent blockchain, and that work meets the difficulty level of the auxiliary blockchain, which is why this block should be accepted.

Aux proof-of-work

This is used to prove work on the auxiliary blockchain. In vinced's original implementation it's generated by calling the getworkaux RPC method on the parent blockchain client (bitcoind) and then the work is then submitted by passing it to the auxiliary chain client (namecoind) as the second parameter to getauxblock.

When receiving an Aux proof-of-work block in a "block" network message, the data received is a standard block, but the below extra data is inserted between the nonce and txn_count elements:

Field Size	Description	Data type	Comments
?	coinbase_txn	txn	Coinbase transaction linking the AuxPOW block to its parent block
32	block_hash	char[32]	Hash of the parent block header
?	coinbase_branch	merkle_branch	The merkle branch linking the coinbase_txn to the parent block's merkle_root
?	blockchain_branch	merkle_branch	The merkle branch linking this auxiliary blockchain to the others, when used in a merged mining setup with multiple auxiliary chains
80	parent_block	block header	Parent block header

For the coinbase_branch merkle branch, because the coinbase transaction is the first transaction in the block (if using Bitcoin as a parent chain, i.e. hash #7 in the example given below), the branch_side_mask is always going to be all zeroes, because the branch hashes will always be "on the right" of the working hash.

When only working on one auxiliary blockchain, the blockchain_branch link is not needed, and is nulled-out by being presented as 5 bytes of zeros (interpreted as a one-byte var_int indicating a branch_length of zero, and a 32-bit (4 byte) branch_side_mask of all zeroes.

Merkle Branch

Say Alice created a Merkle tree, and it's root element is publicly available. For example:

             merkleRoot (0)
              /        \
             /          \
            1            2
           / \          / \
          /   \        /   \
         3     4      5     6
        / \   / \    / \   / \
       7   8 9  10  11 12 13 14

Now she wants to prove to Bob that a given hash (#10) was part of that tree, but Bob doesn't have the full tree (only the public root; hash #0). Alice can send Bob all the hashes she used to make the tree in the first place (hashes #7-#14, total of 7 extra hashes), so Bob can build the whole tree to verify the root is the same, but that's rather data-intensive. Instead, she could give Bob hashes #9, #3, and #2 (one from each level of the tree, working #10 back to the root). Without Bob knowing the structure of the tree, Alice also has to tell Bob what order to apply the hashes in (since hash(#9, #10) == #4, but hash(#10, #9) != #4). So Alice tells Bob "left, left, right" to indicate which operand #9, #3, and #2 are, respectively. That can be encoded as a bitmask and take up very little data to transmit. So, instead of transmitting 7 hashes to Bob, Alice transmits 3 hashes and a bitmask. The data savings get even more pronounced if the merkle tree gets even bigger.

That is the overall premise, and specifically for the AuxPOW protocol, it's been termed a "merkle branch" (since it's one pathway of a merkle tree), and is transmitted thusly:

Field Size	Description	Data type	Comments
?	branch_length	var_int	The number of hashes making up the branch
?	branch_hash[]	char[32]	Individual hash in the branch; repeated branch_length number of times
4	branch_side_mask	int32_t	Bitmask of which side of the merkle hash function the branch_hash element should go on. Zero means it goes on the right, One means on the left.

The first branch_hash is used first, and the least-significant bit of the branch_side_mask determines its hash position. Then the second branch_hash is applied with the second-least-significant bit of the branch_side_mask, etc. So for Alice's example, branch_length would be 3, the hashes would be given in the order #9, #3, then #2, and the mask would be 0b011 = 3.

Merged mining coinbase

Insert exactly one of these headers into the scriptSig of the coinbase transaction in the parent block.

Field Size	Description	Data type	Comments
4	magic	char[4]	0xfa, 0xbe, 'm', 'm' (required iff over 20 bytes prior to aux merkle root in coinbase)
32	block_hash	char[32]	Hash of the AuxPOW block header
4	merkle_size	int32_t	Number of entries in aux work merkle tree. Must be a power of 2.
4	merkle_nonce	int32_t	Nonce used to calculate indexes into aux work merkle tree; you may as well leave this at zero

That string of 44 bytes being part of the coinbase script means that the miner constructed the AuxPOW Block before creating the coinbase.

Aux work merkle tree

If you're just mining a single auxiliary chain and using getauxblock, you don't have to worry about this - just set the merkle tree hash in the coinbase to the aux chain block's hash as given by getauxblock, the merkle size to 1, and the merkle nonce to 0. If you're mining more than one, this is a bit broken. It uses the following algorithm to convert the chain ID to a slot at the base of the merkle tree in which that chain's block hash must slot:

unsigned int rand = merkle_nonce;
rand = rand * 1103515245 + 12345;
rand += chain_id;
rand = rand * 1103515245 + 12345;
slot_num = rand % merkle_size

The idea is that you can increment merkle_nonce until the chains you're mining don't clash for the same slot. The trouble is that this doesn't work; because it just adds a number derived from the merkle_nonce to the chain_id, if two chains clash for one nonce they'll still clash for all possible nonces. New implementers: please pick your chain_id so that not clashing with existing chains requires as small a value of merkle_size as possible, or use a better algorithm to calculate the slot id for your chain.

Once you know where in the merkle tree the different chains go, reverse the bytes of each chain's block hash as given you by getauxblock (so the byte at the start moves to the end, etc) and insert into the appropriate slot, filling the unused ones with arbitrary data. Now build up the merkle tree as usual by taking each pair of values in the initial row and double SHA-256 hashing them to give a new row of hashes, repeating this until you only have a single hash. This last hash is the merkle root. You need to reverse the bytes of this again before inserting it into the coinbase. If you're not using getauxblock to get the block hash, you can skip the first reversal but still need to reverse the final merkle root when adding it to the coinbase.

The aux proof-of-work also needs a merkle branch, which is built as follows: find the location of the block's hash in the merkle tree, and add the other value that you hashed it with in building the merkle tree. Now add the value you hashed that result with. Keep doing this until you reach the root. The merkle root itself is never included in the merkle branch. If you just have a single aux chain, this can be left entirely empty. (It also appears you don't need to reverse these hashes.)