Merged mining specification

From Bitcoin Wiki
Revision as of 22:19, 22 May 2013 by MidnightLightning (talk | contribs) (Updating with more technical information based on my dissection of vinced's source)
Jump to: navigation, search

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.


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 aux to its parent block
 ? merkle_link mrkllink The merkle branch linking the coinbase (above) to its block
 ? aux_branch_count var_int Number of merkle branches linking this aux chains to the aux root
32* aux_branch[] char[32] The merkle branch linking all auxiliary blockchains being mined against together
4 index int32_t Index of "this" blockchain in the auxiliary blockchain list
80 parent_block block header Parent block header

Merkle link

Field Size Description Data type Comments
32 block_hash char[32] Hash of the parent block header
 ? branch_count var_int The number of links to bring the coinbase transaction to the parent block's merkle root
32* branch[] char[32] Linking merkle branches
4 mask int32_t Bitmask of which "side" of the merkle tree hashing algorithm the branch elements need to be applied on

Merged mining coinbase

Insert exactly one of these headers into the scriptSig of the coinbase on the parent chain.

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.[1] 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.)