Difference between revisions of "Merged mining specification"

From Bitcoin Wiki
Jump to: navigation, search
(Aux work merkle tree)
Line 56: Line 56:
 
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.<ref>https://bitcointalk.org/index.php?topic=51069.0</ref> 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.
 
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.<ref>https://bitcointalk.org/index.php?topic=51069.0</ref> 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 hashes 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.
+
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.)
 
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.)

Revision as of 22:07, 7 November 2011

Aux proof-of-work

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

Field Size Description Data type Comments
 ? txns txn Coinbase transaction linking the aux to its parent block
 ? merkle_link mrkllink The merkle path 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] Linking aux merkle branches
4 index int32_t Index of "this" block chain in the aux chain 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 block header
 ? branch_count var_int The number of links to bring the transaction to the block's merkle root
32* branch[] char[32] Linking merkle branches
4 index int32_t Index of this transaction in the merkle tree

Merged mining coinbase

Insert exactly one of these headers into the scriptSig of the coinbase on the parent chain. vinced's code always inserts an OP_2, 0xfa, 0xbe, 'm', 'm' in front of it, but you don't have to.

Field Size Description Data type Comments
32 block_hash char[32] Hash of the aux work merkle tree
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

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.)

Notes