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 block
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 similar to a standard block, but extra data is inserted between the nonce and txn_count elements. In the below table, the shaded rows are the same as the standard block definition:
| Field Size | Description | Data type | Comments |
|---|---|---|---|
| 4 | version | uint32_t | |
| 32 | prev_block | char[32] | |
| 32 | merkle_root | char[32] | |
| 4 | timestamp | uint32_t | |
| 4 | bits | uint32_t | |
| 4 | nonce | uint32_t | |
| ? | coinbase_txn | txn | Coinbase transaction that is in the parent block, 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 |
| ? | txn_count | var_int | |
| ? | txns | tx[] |
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 branch_side_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.[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.)
Example
This is the AuxPOW block at height 19200 in the Namecoin chain (the first block that allowed AuxPOW authentication). It has a hash of d8a7c3e01e1e95bcee015e6fcc7583a2ca60b79e5a3aa0a171eddd344ada903d, and only has one Namecoin transaction (coinbase sending 50 NMC to the miner's address). The parent block that was used as Proof of Work has a hash less than the difficulty target of Namecoin at the time, but not the Bitcoin target:
0000000000003d47277359fb969c43e3c7e7c0306a17f6444b8e91e19def03a9 -- parent block hash 000000000000b269000000000000000000000000000000000000000000000000 -- Namecoin difficulty target 00000000000009ee5d0000000000000000000000000000000000000000000000 -- Bitcoin difficulty target
Hence, this AuxPOW block was valid in the Namecoin blockchain, but not in the Bitcoin blockchain (you will find no Bitcoin block with the hash starting 3d47277359fb969c. If it were, it would be right after 4a59b7deb5c4e01b, since that's the previous_block hash used)
Block Header: 01 01 01 00 // Version 36 90 9a c0 7a 16 73 da f6 5f a7 d8 28 88 2e 66 c9 e8 9f 85 46 cd d5 0a 9f b1 00 00 00 00 00 00 // Previous block hash 0f 5c 65 49 bc d6 08 ab 7c 4e ac 59 3e 5b d5 a7 3b 2d 43 2e b6 35 18 70 8f 77 8f c7 dc df af 88 // Merkle root 8d 1a 90 4e // Timestamp 69 b2 00 1b // Bits 00 00 00 00 // Nonce Coinbase Transaction: 01 00 00 00 // Version 01 // TxIn Count 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // Previous Out 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ff ff ff ff 35 // Script size 04 5d ee 09 1a 01 4d 52 2c fa be 6d 6d d8 a7 c3 e0 1e 1e 95 bc ee 01 5e 6f cc 75 83 a2 ca 60 b7 // Script 9e 5a 3a a0 a1 71 ed dd 34 4a da 90 3d 01 00 00 00 00 00 00 00 ff ff ff ff // Sequence Number 01 // TxOut Count 60 a0 10 2a 01 00 00 00 // Amount 43 // Script Size 41 04 f8 bb e9 7e d2 ac bc 5b ba 11 c6 8f 6f 1a 03 13 f9 18 f3 d3 c0 e8 47 50 55 e3 51 e3 bf 44 // Script 2f 8c 8d ce e6 82 d2 45 7b dc 53 51 b7 0d d9 e3 40 26 76 6e ba 18 b0 6e ae e2 e1 02 ef d1 ab 63 46 67 ac 00 00 00 00 // Lock Time Coinbase Link: a9 03 ef 9d e1 91 8e 4b 44 f6 17 6a 30 c0 e7 c7 e3 43 9c 96 fb 59 73 27 47 3d 00 00 00 00 00 00 // Hash of parent block header 05 // Number of links in branch 05 0a c4 a1 a1 e1 bc e0 c4 8e 55 5b 1a 9f 93 52 81 96 8c 72 d6 37 9b 24 72 9c a0 42 5a 3f c3 cb // Hash #1 43 3c d3 48 b3 5e a2 28 06 cf 21 c7 b1 46 48 9a ef 69 89 55 1e b5 ad 23 73 ab 61 21 06 0f 30 34 // Hash #2 1d 64 87 57 c0 21 7d 43 e6 6c 57 ea ed 64 fc 18 20 ec 65 d1 57 f3 3b 74 19 65 18 3a 5e 0c 85 06 // Hash #3 ac 26 02 df e2 f5 47 01 2d 1c c7 50 04 d4 8f 97 ab a4 6b d9 93 0f f2 85 c9 f2 76 f5 bd 09 f3 56 // Hash #4 df 19 72 45 79 d6 5e c7 cb 62 bf 97 94 6d fc 6f b0 e3 b2 83 9b 7f da b3 7c db 60 e5 51 22 d3 5b // Hash #5 00 00 00 00 // Branch sides bitmask Aux Blockchain Link: 00 // Number of links in branch 00 00 00 00 // Branch sides bitmask Parent Block: 01 00 00 00 // Version 08 be 13 29 5c 03 e6 7c b7 0d 00 da e8 1e a0 6e 78 b9 01 4e 5c eb 7d 9b a5 04 00 00 00 00 00 00 // Previous block hash e0 fd 42 db 8e f6 d7 83 f0 79 d1 26 be a1 2e 2d 10 c1 04 c0 92 7c d6 8f 95 4d 85 6f 9e 81 11 e5 // Merkle root 9a 23 90 4e // Timestamp 5d ee 09 1a // Bits 1c 65 50 86 // Nonce Transactions: 01 // Tx Count 01 00 00 00 // Version 01 // TxIn Count 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // Previous Out 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ff ff ff ff 08 // Script size 04 69 b2 00 1b 01 01 52 // Script ff ff ff ff // Sequence number 01 // TxOut Count 00 f2 05 2a 01 00 00 00 // Amount 43 // Script size 41 04 89 fe 91 e6 28 47 57 5c 98 de ea b0 20 f6 5f df f1 7a 3a 87 0e bb 05 82 0b 41 4f 3d 80 97 // Script 21 8e c9 a6 5f 1e 0a e0 ac 35 af 72 47 bd 79 ed 1f 2a 24 67 5f ff b5 aa 6f 96 20 e1 92 0a d4 bf 5a a6 ac 00 00 00 00 // Lock Time