Merged mining specification - Revision history

Phelix: Clarifications

2015-08-08T12:31:19Z

Clarifications

← Older revision		Revision as of 12:31, 8 August 2015
Line 78:		Line 78:
	\| ? \|\| branch_hash[] \|\| char[32] \|\| Individual hash in the branch; repeated <tt>branch_length</tt> number of times		\| ? \|\| branch_hash[] \|\| char[32] \|\| Individual hash in the branch; repeated <tt>branch_length</tt> number of times
	\|-		\|-
	\| 4 \|\| branch_side_mask \|\| int32_t \|\| Bitmask of which side of the merkle hash function the <tt>branch_hash</tt> element should go on. Zero means it goes on the right, One means on the left.		\| 4 \|\| branch_side_mask \|\| int32_t \|\| Bitmask of which side of the merkle hash function the <tt>branch_hash</tt> element should go on. Zero means it goes on the right, One means on the left. It is equal to the index of the starting hash within the widest level of the merkle tree for this merkle branch.
	\|}		\|}

	The first <tt>branch_hash</tt> is used first, and the least-significant bit of the <tt>branch_side_mask</tt> determines its hash position. Then the second <tt>branch_hash</tt> is applied with the second-least-significant bit of the <tt>branch_side_mask</tt>, etc. So for Alice's example, <tt>branch_length</tt> would be 3, the hashes would be given in the order #9, #3, then #2, and the <tt>branch_side_mask</tt> would be <tt>0b011</tt> = 3.		The first <tt>branch_hash</tt> is used first, and the least-significant bit of the <tt>branch_side_mask</tt> determines its hash position. Then the second <tt>branch_hash</tt> is applied with the second-least-significant bit of the <tt>branch_side_mask</tt>, etc. So for Alice's example, <tt>branch_length</tt> would be 3, the hashes would be given in the order #9, #3, then #2, and the <tt>branch_side_mask</tt> would be <tt>0b011</tt> = 3 (equal to the index of #10 in the widest level of the merkle tree).

	== Merged mining coinbase ==		== Merged mining coinbase ==
Line 91:		Line 91:
	\| 4 \|\| magic \|\| char[4] \|\| <tt>0xfa</tt>, <tt>0xbe</tt>, 'm', 'm' '''(only required if over 20 bytes past the start of the script; optional otherwise)'''		\| 4 \|\| magic \|\| char[4] \|\| <tt>0xfa</tt>, <tt>0xbe</tt>, 'm', 'm' '''(only required if over 20 bytes past the start of the script; optional otherwise)'''
	\|-		\|-
	\| 32 \|\| block_hash \|\| char[32] \|\| Hash of the AuxPOW block header		\| 32 \|\| block_hash \|\| char[32] \|\| Hash of the AuxPOW block header / root of the chain merkle branch
	\|-		\|-
	\| 4 \|\| merkle_size \|\| int32_t \|\| Number of entries in aux work merkle tree. '''(Must be a power of 2)'''		\| 4 \|\| merkle_size \|\| int32_t \|\| Number of entries in aux work merkle tree. '''(Must be a power of 2)'''

XertroV: 'thus', not 'thusly'

2013-06-21T07:38:15Z

'thus', not 'thusly'

← Older revision		Revision as of 07:38, 21 June 2013
Line 69:		Line 69:
	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 <tt>hash(#9, #10) == #4</tt>, but <tt>hash(#10, #9) != #4</tt>). 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.		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 <tt>hash(#9, #10) == #4</tt>, but <tt>hash(#10, #9) != #4</tt>). 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~~:		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 thus:

	{\|class="wikitable"		{\|class="wikitable"

XertroV: Added to Technical and Developer categories

2013-06-20T09:00:28Z

Added to Technical and Developer categories

← Older revision		Revision as of 09:00, 20 June 2013
Line 202:		Line 202:
	==Notes==		==Notes==
	<references />		<references />

			[[Category:Technical]]
			[[Category:Developer]]

MidnightLightning: /* Aux proof-of-work block */

2013-06-07T18:09:51Z

Aux proof-of-work block

← Older revision		Revision as of 18:09, 7 June 2013
Line 33:		Line 33:
	\| ? \|\| coinbase_txn \|\| [[Protocol specification#tx\|txn]] \|\| Coinbase transaction that is in the parent block, [[#Merged mining coinbase\|linking]] the AuxPOW block to its parent block		\| ? \|\| coinbase_txn \|\| [[Protocol specification#tx\|txn]] \|\| Coinbase transaction that is in the parent block, [[#Merged mining coinbase\|linking]] the AuxPOW block to its parent block
	\|-		\|-
	\| 32 \|\| block_hash \|\| char[32] \|\| Hash of the ~~parent block~~ header		\| 32 \|\| block_hash \|\| char[32] \|\| Hash of the <tt>parent_block</tt> header
	\|-		\|-
	\| ? \|\| coinbase_branch \|\| [[#Merkle Branch\|Merkle branch]] \|\| The merkle branch linking the <tt>coinbase_txn</tt> to the parent block's <tt>merkle_root</tt>		\| ? \|\| coinbase_branch \|\| [[#Merkle Branch\|Merkle branch]] \|\| The merkle branch linking the <tt>coinbase_txn</tt> to the parent block's <tt>merkle_root</tt>
Line 49:		Line 49:

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

			Note that the <tt>block_hash</tt> element is not needed as you have the full <tt>parent_block</tt> header element and can calculate the hash from that. The current Namecoin client doesn't check this field for validity, and as such some AuxPOW blocks have it little-endian, and some have it big-endian.

	== Merkle Branch ==		== Merkle Branch ==

MidnightLightning: /* Merged mining coinbase */

2013-06-04T19:37:40Z

Merged mining coinbase

← Older revision		Revision as of 19:37, 4 June 2013
Line 87:		Line 87:
	! Field Size !! Description !! Data type !! Comments		! Field Size !! Description !! Data type !! Comments
	\|-		\|-
	\| 4 \|\| magic \|\| char[4] \|\| <tt>0xfa</tt>, <tt>0xbe</tt>, 'm', 'm' '''(required ~~iff~~ over 20 bytes ~~prior to aux merkle root in coinbase~~)'''		\| 4 \|\| magic \|\| char[4] \|\| <tt>0xfa</tt>, <tt>0xbe</tt>, 'm', 'm' '''(only required if over 20 bytes past the start of the script; optional otherwise)'''
	\|-		\|-
	\| 32 \|\| block_hash \|\| char[32] \|\| Hash of the AuxPOW block header		\| 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_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		\| 4 \|\| merkle_nonce \|\| int32_t \|\| Nonce used to calculate indexes into aux work merkle tree; you may as well leave this at zero

MidnightLightning: /* Example */

2013-05-23T20:45:00Z

Example

← Older revision		Revision as of 20:45, 23 May 2013
Line 132:		Line 132:
	00 00 00 00 // Nonce		00 00 00 00 // Nonce

	Coinbase Transaction:		Parent Block Coinbase Transaction:
	01 00 00 00 // Version		01 00 00 00 // Version
	01 // TxIn Count		01 // TxIn Count
Line 168:		Line 168:
	00 00 00 00 // Branch sides bitmask		00 00 00 00 // Branch sides bitmask

	Parent Block:		Parent Block Header:
	01 00 00 00 // Version		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		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

MidnightLightning: /* Example */

2013-05-23T20:44:18Z

Example

← Older revision		Revision as of 20:44, 23 May 2013
Line 121:		Line 121:
	</pre>		</pre>

	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 <tt>3d47277359fb969c</tt>. If it were, it would be right after [https://blockchain.info/block-index/163650/00000000000004a59b7deb5c4e01b9786ea01ee8da000db77ce6035c2913be08 <tt>4a59b7deb5c4e01b</tt>], since that's the ~~previous block~~ hash used)		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 <tt>3d47277359fb969c</tt>. If it were, it would be right after [https://blockchain.info/block-index/163650/00000000000004a59b7deb5c4e01b9786ea01ee8da000db77ce6035c2913be08 <tt>4a59b7deb5c4e01b</tt>], since that's the <tt>previous_block</tt> hash used)

	<pre>		<pre>

MidnightLightning: /* Merged mining coinbase */

2013-05-23T20:43:04Z

Merged mining coinbase

← Older revision		Revision as of 20:43, 23 May 2013
Line 82:		Line 82:

	== Merged mining coinbase ==		== Merged mining coinbase ==
	Insert exactly one of these headers into the scriptSig of the coinbase transaction in the parent block.		Insert exactly one of these headers into the <tt>scriptSig</tt> of the coinbase transaction in the parent block.

	{\|class="wikitable"		{\|class="wikitable"

MidnightLightning: /* Aux proof-of-work block */

2013-05-23T20:39:57Z

Aux proof-of-work block

← Older revision		Revision as of 20:39, 23 May 2013
Line 31:		Line 31:
	\| 4 \|\| nonce \|\| uint32_t \|\|		\| 4 \|\| nonce \|\| uint32_t \|\|
	\|-		\|-
	\| ? \|\| coinbase_txn \|\| [[Protocol specification#tx\|txn]] \|\| Coinbase transaction [[#Merged mining coinbase\|linking]] the AuxPOW block to its parent block		\| ? \|\| coinbase_txn \|\| [[Protocol specification#tx\|txn]] \|\| Coinbase transaction that is in the parent block, [[#Merged mining coinbase\|linking]] the AuxPOW block to its parent block
	\|-		\|-
	\| 32 \|\| block_hash \|\| char[32] \|\| Hash of the parent block header		\| 32 \|\| block_hash \|\| char[32] \|\| Hash of the parent block header

MidnightLightning: /* Example */

2013-05-23T20:32:54Z

Example

← Older revision		Revision as of 20:32, 23 May 2013
Line 121:		Line 121:
	</pre>		</pre>

	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 <tt>3d47277359fb969c</tt>)		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 <tt>3d47277359fb969c</tt>. If it were, it would be right after [https://blockchain.info/block-index/163650/00000000000004a59b7deb5c4e01b9786ea01ee8da000db77ce6035c2913be08 <tt>4a59b7deb5c4e01b</tt>], since that's the previous block hash used)

	<pre>		<pre>