Bitcoin Wiki - User contributions [en]

List of address prefixes

2014-01-24T21:25:35Z

MidnightLightning:

Blockchain-based currencies use addresses, which are a [[Base58Check encoding]] of some hash, typically that of a public key. The encoding includes a version byte, which affects the first character in the address. The following is a list of some prefixes which are in use.

{| class="wikitable"
|-
!Decimal version
!Leading symbol
!Use
!Example
|-
|0
|1
|Bitcoin pubkey hash
|<tt>17VZNX1SN5NtKa8UQFxwQbFeFc3iqRYhem</tt>
|-
|5
|3
|Bitcoin script hash
| <tt>3EktnHQD7RiAE6uzMj2ZifT9YgRrkSgzQX</tt>
|-
|48
|L
|Litecoin pubkey hash
|<tt>LhK2kQwiaAvhjWY799cZvMyYwnQAcxkarr</tt>
|-
|52
|M or N
|Namecoin pubkey hash
|<tt>NATX6zEUNfxfvgVwz8qVnnw3hLhhYXhgQn</tt>
|-
|111
|m or n
|Bitcoin testnet pubkey hash
|<tt>mipcBbFg9gMiCh81Kj8tqqdgoZub1ZJRfn</tt>
|-
|128
|5
|Bitcoin Private key
|<tt>5Hwgr3u458GLafKBgxtssHSPqJnYoGrSzgQsPwLFhLNYskDPyyA</tt>
|-
|196
|2
|Testnet script hash
|
|-
|239
|9
|Testnet Private key
|<tt>92Pg46rUhgTT7romnV7iGW6W1gbGdeezqdbJCzShkCsYNzyyNcc</tt>
|}

The following table shows the leading symbol(s) and address length(s) for 160 bit hashes for each of the possible decimal version values:

{| class="wikitable"
|-
!Decimal version
!Leading symbol
!Address length
|-
|0
|1
|up to 34
|-
|1
|Q-Z, a-k, m-o
|33
|-
|2
|o-z, 2
|33 or 34
|-
|3
|2
|34
|-
|4
|2 or 3
|34
|-
|5-6
|3
|34
|-
|7
|3 or 4
|34
|-
|8
|4
|34
|-
|9
|4 or 5
|34
|-
|10-11
|5
|34
|-
|12
|5 or 6
|34
|-
|13
|6
|34
|-
|14
|6 or 7
|34
|-
|15-16
|7
|34
|-
|17
|7 or 8
|34
|-
|18
|8
|34
|-
|19
|8 or 9
|34
|-
|20-21
|9
|34
|-
|22
|9 or A
|34
|-
|23
|A
|34
|-
|24
|A or B
|34
|-
|25-26
|B
|34
|-
|27
|B or C
|34
|-
|28
|C
|34
|-
|29
|C or D
|34
|-
|30-31
|D
|34
|-
|32
|D or E
|34
|-
|33
|E
|34
|-
|34
|E or F
|34
|-
|35-36
|F
|34
|-
|37
|F or G
|34
|-
|38
|G
|34
|-
|39
|G or H
|34
|-
|40-41
|H
|34
|-
|42
|H or J
|34
|-
|43
|J
|34
|-
|44
|J or K
|34
|-
|45-46
|K
|34
|-
|47
|K or L
|34
|-
|48
|L
|34
|-
|49
|L or M
|34
|-
|50-51
|M
|34
|-
|52
|M or N
|34
|-
|53
|N
|34
|-
|54
|N or P
|34
|-
|55-56
|P
|34
|-
|57
|P or Q
|34
|-
|58
|Q
|34
|-
|59
|Q or R
|34
|-
|60-61
|R
|34
|-
|62
|R or S
|34
|-
|63
|S
|34
|-
|64
|S or T
|34
|-
|65-66
|T
|34
|-
|67
|T or U
|34
|-
|68
|U
|34
|-
|69
|U or V
|34
|-
|70-71
|V
|34
|-
|72
|V or W
|34
|-
|73
|W
|34
|-
|74
|W or X
|34
|-
|75-76
|X
|34
|-
|77
|X or Y
|34
|-
|78
|Y
|34
|-
|79
|Y or Z
|34
|-
|80-81
|Z
|34
|-
|82
|Z or a
|34
|-
|83
|a
|34
|-
|84
|a or b
|34
|-
|85
|b
|34
|-
|86
|b or c
|34
|-
|87-88
|c
|34
|-
|89
|c or d
|34
|-
|90
|d
|34
|-
|91
|d or e
|34
|-
|92-93
|e
|34
|-
|94
|e or f
|34
|-
|95
|f
|34
|-
|96
|f or g
|34
|-
|97-98
|g
|34
|-
|99
|g or h
|34
|-
|100
|h
|34
|-
|101
|h or i
|34
|-
|102-103
|i
|34
|-
|104
|i or j
|34
|-
|105
|j
|34
|-
|106
|j or k
|34
|-
|107-108
|k
|34
|-
|109
|k or m
|34
|-
|110
|m
|34
|-
|111
|m or n
|34
|-
|112-113
|n
|34
|-
|114
|n or o
|34
|-
|115
|o
|34
|-
|116
|o or p
|34
|-
|117-118
|p
|34
|-
|119
|p or q
|34
|-
|120
|q
|34
|-
|121
|q or r
|34
|-
|122-123
|r
|34
|-
|124
|r or s
|34
|-
|125
|s
|34
|-
|126
|s or t
|34
|-
|127-128
|t
|34
|-
|129
|t or u
|34
|-
|130
|u
|34
|-
|131
|u or v
|34
|-
|132-133
|v
|34
|-
|134
|v or w
|34
|-
|135
|w
|34
|-
|136
|w or x
|34
|-
|137-138
|x
|34
|-
|139
|x or y
|34
|-
|140
|y
|34
|-
|141
|y or z
|34
|-
|142-143
|z
|34
|-
|144
|z or 2
|34 or 35
|-
|145-255
|2
|35
|}

Protocol documentation

2014-01-16T16:57:34Z

MidnightLightning: /* Network address */ change presentation of IPv6 address to standard

Sources:
* [[Original Bitcoin client]] source

Type names used in this documentation are from the C99 standard.

For protocol used in mining, see [[Getwork]].

==Common standards==

=== Hashes ===

Usually, when a hash is computed within bitcoin, it is computed twice. Most of the time [http://en.wikipedia.org/wiki/SHA-2 SHA-256] hashes are used, however [http://en.wikipedia.org/wiki/RIPEMD RIPEMD-160] is also used when a shorter hash is desirable (for example when creating a bitcoin address).

Example of double-SHA-256 encoding of string "hello":

hello
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 (first round of sha-256)
9595c9df90075148eb06860365df33584b75bff782a510c6cd4883a419833d50 (second round of sha-256)

For bitcoin addresses (RIPEMD-160) this would give:

hello
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 (first round is sha-256)
b6a9c8c230722b7c748331a8b450f05566dc7d0f (with ripemd-160)

=== Merkle Trees ===

Merkle trees are binary trees of hashes. Merkle trees in bitcoin use a '''double''' SHA-256, the SHA-256 hash of the SHA-256 hash of something.

If, when forming a row in the tree (other than the root of the tree), it would have an odd number of elements, the final double-hash is duplicated to ensure that the row has an even number of hashes.

First form the bottom row of the tree with the ordered double-SHA-256 hashes of the byte streams of the transactions in the block.

Then the row above it consists of half that number of hashes. Each entry is the double-SHA-256 of the 64-byte concatenation of the corresponding two hashes below it in the tree.

This procedure repeats recursively until we reach a row consisting of just a single double-hash. This is the '''merkle root''' of the tree.

For example, imagine a block with three transactions ''a'', ''b'' and ''c''. The merkle tree is:

d1 = dhash(a)
d2 = dhash(b)
d3 = dhash(c)
d4 = dhash(c) # a, b, c are 3. that's an odd number, so we take the c twice

d5 = dhash(d1 concat d2)
d6 = dhash(d3 concat d4)

d7 = dhash(d5 concat d6)

where

dhash(a) = sha256(sha256(a))

''d7'' is the merkle root of the 3 transactions in this block.

Note: Hashes in Merkle Tree displayed in the [[Block Explorer]] are of little-endian notation. For some implementations and [http://www.fileformat.info/tool/hash.htm calculations], the bits need to be reversed before they are hashed, and again after the hashing operation.

=== Signatures ===

Bitcoin uses [http://en.wikipedia.org/wiki/Elliptic_curve_cryptography Elliptic Curve] [http://en.wikipedia.org/wiki/Digital_Signature_Algorithm Digital Signature Algorithm] ([http://en.wikipedia.org/wiki/Elliptic_Curve_DSA ECDSA]) to sign transactions.

For ECDSA the secp256k1 curve from http://www.secg.org/collateral/sec2_final.pdf is used.

Public keys (in scripts) are given as 04 <x> <y> where ''x'' and ''y'' are 32 byte big-endian integers representing the coordinates of a point on the curve or in compressed form given as <sign> <x> where <sign> is 0x02 if ''y'' is even and 0x03 if ''y'' is odd.

Signatures use [http://en.wikipedia.org/wiki/Distinguished_Encoding_Rules DER encoding] to pack the ''r'' and ''s'' components into a single byte stream (this is also what OpenSSL produces by default).

=== Transaction Verification ===
Transactions are cryptographically signed records that reassign ownership of Bitcoins to new addresses. Transactions have ''inputs'' - records which reference the funds from other previous transactions - and ''outputs'' - records which determine the new owner of the transferred Bitcoins, and which will be referenced as inputs in future transactions as those funds are respent.

Each ''input'' must have a cryptographic digital signature that unlocks the funds from the prior transaction. Only the person possessing the appropriate [[private key]] is able to create a satisfactory signature; this in effect ensures that funds can only be spent by their owners.

Each ''output'' determines which Bitcoin address (or other criteria, see [[Scripting]]) is the recipient of the funds.

In a transaction, the sum of all inputs must be equal to or greater than the sum of all outputs. If the inputs exceed the outputs, the difference is considered a [[transaction fee]], and is redeemable by whoever first includes the transaction into the block chain.

A special kind of transaction, called a [[coinbase transaction]], has no inputs. It is created by [[miners]], and there is one coinbase transaction per block. Because each block comes with a reward of newly created Bitcoins (e.g. 50 BTC for the first 210,000 blocks), the first transaction of a block is, with few exceptions, the transaction that grants those coins to their recipient (the miner). In addition to the newly created Bitcoins, the coinbase transaction is also used for assigning the recipient of any transaction fees that were paid within the other transactions being included in the same block. The coinbase transaction can assign the entire reward to a single Bitcoin address, or split it in portions among multiple addresses, just like any other transaction. Coinbase transactions always contain outputs totaling the sum of the block reward plus all transaction fees collected from the other transactions in the same block.

The [[coinbase transaction]] in block zero cannot be spent. This is due to a quirk of the reference client implementation that would open the potential for a block chain fork if some nodes accepted the spend and others did not<ref>[http://bitcointalk.org/index.php?topic=119645.msg1288552#msg1288552 Block 0 Network Fork]</ref>.

Most Bitcoin outputs encumber the newly transferred coins with a single ECDSA private key. The actual record saved with inputs and outputs isn't necessarily a key, but a ''script''. Bitcoin uses an interpreted scripting system to determine whether an output's criteria have been satisfied, with which more complex operations are possible, such as outputs that require two ECDSA signatures, or two-of-three-signature schemes. An output that references a single Bitcoin address is a ''typical'' output; an output actually contains this information in the form of a script that requires a single ECDSA signature (see [[OP_CHECKSIG]]). The output script specifies what must be provided to unlock the funds later, and when the time comes in the future to spend the transaction in another input, that input must provide all of the thing(s) that satisfy the requirements defined by the original output script.

=== Addresses ===

A bitcoin address is in fact the hash of a ECDSA public key, computed this way:

Version = 1 byte of 0 (zero); on the test network, this is 1 byte of 111
Key hash = Version concatenated with RIPEMD-160(SHA-256(public key))
Checksum = 1st 4 bytes of SHA-256(SHA-256(Key hash))
Bitcoin Address = Base58Encode(Key hash concatenated with Checksum)

The Base58 encoding used is home made, and has some differences. Especially, leading zeroes are kept as single zeroes when conversion happens.

== Common structures ==

Almost all integers are encoded in little endian. Only IP or port number are encoded big endian.

=== Message structure ===

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || magic || uint32_t || Magic value indicating message origin network, and used to seek to next message when stream state is unknown
|-
| 12 || command || char[12] || ASCII string identifying the packet content, NULL padded (non-NULL padding results in packet rejected)
|-
| 4 || length || uint32_t || Length of payload in number of bytes
|-
| 4 || checksum || uint32_t || First 4 bytes of sha256(sha256(payload))
|-
| ? || payload || uchar[] || The actual data
|}

Known magic values:

{|class="wikitable"
! Network !! Magic value !! Sent over wire as
|-
| main || 0xD9B4BEF9 || F9 BE B4 D9
|-
| testnet || 0xDAB5BFFA || FA BF B5 DA
|-
| testnet3 || 0x0709110B || 0B 11 09 07
|-
| namecoin || 0xFEB4BEF9 || F9 BE B4 FE
|}

=== Variable length integer ===

Integer can be encoded depending on the represented value to save space.
Variable length integers always precede an array/vector of a type of data that may vary in length.
Longer numbers are encoded in little endian.

{|class="wikitable"
! Value !! Storage length !! Format
|-
| < 0xfd || 1 || uint8_t
|-
| <= 0xffff || 3 || 0xfd followed by the length as uint16_t
|-
| <= 0xffffffff || 5 || 0xfe followed by the length as uint32_t
|-
| - || 9 || 0xff followed by the length as uint64_t
|}

If you're reading the Satoshi client code (BitcoinQT) it refers to this as a "CompactSize". Modern BitcoinQT has also CVarInt class which implements even more compact integer for the purpose of local storage (which is incompatible with "CompactSize" described here). CVarInt is not a part of the protocol.

=== Variable length string ===

Variable length string can be stored using a variable length integer followed by the string itself.

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || length || [[Protocol_specification#Variable_length_integer|var_int]] || Length of the string
|-
| ? || string || char[] || The string itself (can be empty)
|}

=== Network address ===

When a network address is needed somewhere, this structure is used. This protocol and structure supports IPv6, '''but note that the original client currently only supports IPv4 networking'''. Network addresses are not prefixed with a timestamp in the version message.

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || time || uint32 || the Time (version >= 31402)
|-
| 8 || services || uint64_t || same service(s) listed in [[#version|version]]
|-
| 16 || IPv6/4 || char[16] || IPv6 address. Network byte order. The original client only supports IPv4 and only reads the last 4 bytes to get the IPv4 address. However, the IPv4 address is written into the message as a 16 byte [http://en.wikipedia.org/wiki/IPv6#IPv4-mapped_IPv6_addresses IPv4-mapped IPv6 address]
(12 bytes ''00 00 00 00 00 00 00 00 00 00 FF FF'', followed by the 4 bytes of the IPv4 address).
|-
| 2 || port || uint16_t || port number, network byte order
|}

Hexdump example of Network address structure

<pre>
0000 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
0010 00 00 FF FF 0A 00 00 01 20 8D ........ .

Network address:
01 00 00 00 00 00 00 00 - 1 (NODE_NETWORK: see services listed under version command)
00 00 00 00 00 00 00 00 00 00 FF FF 0A 00 00 01 - IPv6: ::ffff:a00:1 or IPv4: 10.0.0.1
20 8D - Port 8333
</pre>

=== Inventory Vectors ===

Inventory vectors are used for notifying other nodes about objects they have or data which is being requested.

Inventory vectors consist of the following data format:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || type || uint32_t || Identifies the object type linked to this inventory
|-
| 32 || hash || char[32] || Hash of the object
|}

The object type is currently defined as one of the following possibilities:

{|class="wikitable"
! Value !! Name !! Description
|-
| 0 || ERROR || Any data of with this number may be ignored
|-
| 1 || MSG_TX || Hash is related to a transaction
|-
| 2 || MSG_BLOCK || Hash is related to a data block
|}

Other Data Type values are considered reserved for future implementations.

=== Block Headers ===

Block headers are sent in a headers packet in response to a getheaders message.

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || version || uint32_t || Block version information, based upon the software version creating this block
|-
| 32 || prev_block || char[32] || The hash value of the previous block this particular block references
|-
| 32 || merkle_root || char[32] || The reference to a Merkle tree collection which is a hash of all transactions related to this block
|-
| 4 || timestamp || uint32_t || A timestamp recording when this block was created (Will overflow in 2106<ref>http://en.wikipedia.org/wiki/Unix_time#Notable.C2.A0events.C2.A0in.C2.A0Unix.C2.A0time</ref>)
|-
| 4 || bits || uint32_t || The calculated difficulty target being used for this block
|-
| 4 || nonce || uint32_t || The nonce used to generate this block… to allow variations of the header and compute different hashes
|-
| 1 || txn_count || [[Protocol_specification#Variable_length_integer|var_int]] || Number of transaction entries, this value is always 0
|}

== Message types ==

=== version ===

When a node creates an outgoing connection, it will immediately [[Version Handshake|advertise]] its version. The remote node will respond with its version. No futher communication is possible until both peers have exchanged their version.

Payload:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || version || int32_t || Identifies protocol version being used by the node
|-
| 8 || services || uint64_t || bitfield of features to be enabled for this connection
|-
| 8 || timestamp || int64_t || standard UNIX timestamp in seconds
|-
| 26 || addr_recv || net_addr || The network address of the node receiving this message
|-
|colspan="4"| version >= 106
|-
| 26 || addr_from || net_addr || The network address of the node emitting this message
|-
| 8 || nonce || uint64_t || Node random nonce, randomly generated every time a version packet is sent. This nonce is used to detect connections to self.
|-
| ? || user_agent || [[#Variable length string|var_str]] || [[BIP_0014|User Agent]] (0x00 if string is 0 bytes long)
|-
| 4 || start_height || int32_t || The last block received by the emitting node
|-
| 1 || relay || bool || Whether the remote peer should announce relayed transactions or not, see [[BIP 0037]], since version >= 70001
|}

A "verack" packet shall be sent if the version packet was accepted.

The following services are currently assigned:

{|class="wikitable"
! Value !! Name !! Description
|-
| 1 || NODE_NETWORK || This node can be asked for full blocks instead of just headers.
|}

Hexdump example of version message (OBSOLETE EXAMPLE. This example lacks a checksum and user-agent):
<pre>
0000 F9 BE B4 D9 76 65 72 73 69 6F 6E 00 00 00 00 00 ....version.....
0010 55 00 00 00 9C 7C 00 00 01 00 00 00 00 00 00 00 U....|..........
0020 E6 15 10 4D 00 00 00 00 01 00 00 00 00 00 00 00 ...M............
0030 00 00 00 00 00 00 00 00 00 00 FF FF 0A 00 00 01 ................
0040 20 8D 01 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
0050 00 00 00 00 FF FF 0A 00 00 02 20 8D DD 9D 20 2C .......... ... ,
0060 3A B4 57 13 00 55 81 01 00 :.W..U...

Message header:
F9 BE B4 D9 - Main network magic bytes
76 65 72 73 69 6F 6E 00 00 00 00 00 - "version" command
55 00 00 00 - Payload is 85 bytes long
- No checksum in version message until 20 February 2012. See https://bitcointalk.org/index.php?topic=55852.0
Version message:
9C 7C 00 00 - 31900 (version 0.3.19)
01 00 00 00 00 00 00 00 - 1 (NODE_NETWORK services)
E6 15 10 4D 00 00 00 00 - Mon Dec 20 21:50:14 EST 2010
01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 FF FF 0A 00 00 01 20 8D - Recipient address info - see Network Address
01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 FF FF 0A 00 00 02 20 8D - Sender address info - see Network Address
DD 9D 20 2C 3A B4 57 13 - Node random unique ID
00 - "" sub-version string (string is 0 bytes long)
55 81 01 00 - Last block sending node has is block #98645
</pre>

And here's a modern (60002) protocol version client advertising itself to a local peer...

Newer protocol includes the checksum now, this is from a mainline (satoshi) client during
an outgoing connection to another local client, notice that it does not fill out the
address information at all when the source or destination is "unroutable".

<pre>

0000 f9 be b4 d9 76 65 72 73 69 6f 6e 00 00 00 00 00 ....version.....
0010 64 00 00 00 35 8d 49 32 62 ea 00 00 01 00 00 00 d...5.I2b.......
0020 00 00 00 00 11 b2 d0 50 00 00 00 00 01 00 00 00 .......P........
0030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ff ff ................
0040 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
0050 00 00 00 00 00 00 00 00 ff ff 00 00 00 00 00 00 ................
0060 3b 2e b3 5d 8c e6 17 65 0f 2f 53 61 74 6f 73 68 ;..]...e./Satosh
0070 69 3a 30 2e 37 2e 32 2f c0 3e 03 00 i:0.7.2/.>..

Message Header:
F9 BE B4 D9 - Main network magic bytes
76 65 72 73 69 6F 6E 00 00 00 00 00 - "version" command
64 00 00 00 - Payload is 100 bytes long
3B 64 8D 5A - payload checksum

Version message:
62 EA 00 00 - 60002 (protocol version 60002)
01 00 00 00 00 00 00 00 - 1 (NODE_NETWORK services)
11 B2 D0 50 00 00 00 00 - Tue Dec 18 10:12:33 PST 2012
01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 FF FF 00 00 00 00 00 00 - Recipient address info - see Network Address
01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 FF FF 00 00 00 00 00 00 - Sender address info - see Network Address
3B 2E B3 5D 8C E6 17 65 - Node ID
0F 2F 53 61 74 6F 73 68 69 3A 30 2E 37 2E 32 2F - "/Satoshi:0.7.2/" sub-version string (string is 15 bytes long)
C0 3E 03 00 - Last block sending node has is block #212672
</pre>

=== verack ===

The ''verack'' message is sent in reply to ''version''. This message consists of only a [[#Message structure|message header]] with the command string "verack".

Hexdump of the verack message:

<pre>
0000 F9 BE B4 D9 76 65 72 61 63 6B 00 00 00 00 00 00 ....verack......
0010 00 00 00 00 5D F6 E0 E2 ........

Message header:
F9 BE B4 D9 - Main network magic bytes
76 65 72 61 63 6B 00 00 00 00 00 00 - "verack" command
00 00 00 00 - Payload is 0 bytes long
5D F6 E0 E2 - Checksum
</pre>

=== addr ===

Provide information on known nodes of the network. Non-advertised nodes should be forgotten after typically 3 hours

Payload:
{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 1+ || count || [[Protocol_specification#Variable_length_integer|var_int]] || Number of address entries (max: 1000)
|-
| 30x? || addr_list || (uint32_t + net_addr)[] || Address of other nodes on the network. version < 209 will only read the first one. The uint32_t is a timestamp (see note below).
|}

'''Note''': Starting version 31402, addresses are prefixed with a timestamp. If no timestamp is present, the addresses should not be relayed to other peers, unless it is indeed confirmed they are up.

Hexdump example of ''addr'' message:
<pre>
0000 F9 BE B4 D9 61 64 64 72 00 00 00 00 00 00 00 00 ....addr........
0010 1F 00 00 00 ED 52 39 9B 01 E2 15 10 4D 01 00 00 .....R9.....M...
0020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 FF ................
0030 FF 0A 00 00 01 20 8D ..... .

Message Header:
F9 BE B4 D9 - Main network magic bytes
61 64 64 72 00 00 00 00 00 00 00 00 - "addr"
1F 00 00 00 - payload is 31 bytes long
ED 52 39 9B - checksum of payload

Payload:
01 - 1 address in this message

Address:
E2 15 10 4D - Mon Dec 20 21:50:10 EST 2010 (only when version is >= 31402)
01 00 00 00 00 00 00 00 - 1 (NODE_NETWORK service - see version message)
00 00 00 00 00 00 00 00 00 00 FF FF 0A 00 00 01 - IPv4: 10.0.0.1, IPv6: ::ffff:10.0.0.1 (IPv4-mapped IPv6 address)
20 8D - port 8333
</pre>

=== inv ===

Allows a node to advertise its knowledge of one or more objects. It can be received unsolicited, or in reply to ''getblocks''.

Payload (maximum payload length: 1.8 Megabytes or 50000 entries):

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || count || [[Protocol_specification#Variable_length_integer|var_int]] || Number of inventory entries
|-
| 36x? || inventory || [[Protocol specification#Inventory Vectors|inv_vect]][] || Inventory vectors
|}

=== getdata ===

getdata is used in response to inv, to retrieve the content of a specific object, and is usually sent after receiving an ''inv'' packet, after filtering known elements. It can be used to retrieve transactions, but only if they are in the memory pool or relay set - arbitrary access to transactions in the chain is not allowed to avoid having clients start to depend on nodes having full transaction indexes (which modern nodes do not).

Payload (maximum payload length: 1.8 Megabytes or 50000 entries):

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || count || [[Protocol_specification#Variable_length_integer|var_int]] || Number of inventory entries
|-
| 36x? || inventory || [[Protocol specification#Inventory Vectors|inv_vect]][] || Inventory vectors
|}

=== notfound ===

notfound is a response to a getdata, sent if any requested data items could not be relayed, for example, because the requested transaction was not in the memory pool or relay set.

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || count || [[Protocol_specification#Variable_length_integer|var_int]] || Number of inventory entries
|-
| 36x? || inventory || [[Protocol specification#Inventory Vectors|inv_vect]][] || Inventory vectors
|}

=== getblocks ===

Return an ''inv'' packet containing the list of blocks starting right after the last known hash in the block locator object, up to hash_stop or 500 blocks, whichever comes first.

The locator hashes are processed by a node in the order as they appear in the message. If a block hash if found in the node's main chain, the list of it's children is returned back via the ''inv'' message and the remaining locators are ignored, no matter if the requested limit was reached, or not.

To receive the next blocks hashes, one needs to issue getblocks again with a new block locator object. Keep in mind that some clients (specifically the Satoshi client) will gladly provide blocks which are invalid if the block locator object contains a hash on the invalid branch.

Payload:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || version || uint32_t || the protocol version
|-
| 1+ || hash count || [[Protocol_specification#Variable_length_integer|var_int]] || number of block locator hash entries
|-
| 32+ || block locator hashes || char[32] || block locator object; newest back to genesis block (dense to start, but then sparse)
|-
| 32 || hash_stop || char[32] || hash of the last desired block; set to zero to get as many blocks as possible (500)
|}

To create the block locator hashes, keep pushing hashes until you go back to the genesis block. After pushing 10 hashes back, the step backwards doubles every loop:

<pre>
// From libbitcoin which is under AGPL
std::vector<size_t> block_locator_indices(int top_depth)
{
// Start at max_depth
std::vector<size_t> indices;
// Push last 10 indices first
size_t step = 1, start = 0;
for (int i = top_depth; i > 0; i -= step, ++start)
{
if (start >= 10)
step *= 2;
indices.push_back(i);
}
indices.push_back(0);
return indices;
}
</pre>

Note that it is allowed to send in fewer known hashes down to a minimum of just one hash. However, the purpose of the block locator object is to detect a wrong branch in the caller's main chain. If the peer detects that you are off the main chain, it will send in block hashes which are earlier than your last known block. So if you just send in your last known hash and it is off the main chain, the peer starts over at block #1.

=== getheaders ===

Return a ''headers'' packet containing the headers of blocks starting right after the last known hash in the block locator object, up to hash_stop or 2000 blocks, whichever comes first. To receive the next block headers, one needs to issue getheaders again with a new block locator object. The ''getheaders'' command is used by thin clients to quickly download the blockchain where the contents of the transactions would be irrelevant (because they are not ours). Keep in mind that some clients (specifically the Satoshi client) will gladly provide headers of blocks which are invalid if the block locator object contains a hash on the invalid branch.

Payload:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || version || uint32_t || the protocol version
|-
| 1+ || hash count || [[Protocol_specification#Variable_length_integer|var_int]] || number of block locator hash entries
|-
| 32+ || block locator hashes || char[32] || block locator object; newest back to genesis block (dense to start, but then sparse)
|-
| 32 || hash_stop || char[32] || hash of the last desired block header; set to zero to get as many blocks as possible (2000)
|}

For the block locator object in this packet, the same rules apply as for the [[Protocol_specification#getblocks|getblocks]] packet.

=== tx ===

''tx'' describes a bitcoin transaction, in reply to ''getdata''

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || version || uint32_t || Transaction data format version
|-
| 1+ || tx_in count || [[Protocol_specification#Variable_length_integer|var_int]] || Number of Transaction inputs
|-
| 41+ || tx_in || tx_in[] || A list of 1 or more transaction inputs or sources for coins
|-
| 1+ || tx_out count || [[Protocol_specification#Variable_length_integer|var_int]] || Number of Transaction outputs
|-
| 9+ || tx_out || tx_out[] || A list of 1 or more transaction outputs or destinations for coins
|-
| 4 || lock_time || uint32_t || The block number or timestamp at which this transaction is locked:
{|class="wikitable"
! Value !! Description
|-
| 0 || Always locked
|-
| < 500000000 || Block number at which this transaction is locked
|-
| >= 500000000 || UNIX timestamp at which this transaction is locked
|}
If all TxIn inputs have final (0xffffffff) sequence numbers then lock_time is irrelevant. Otherwise, the transaction may not be added to a block until after lock_time (see [[NLockTime]]).

|}

TxIn consists of the following fields:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 36 || previous_output || outpoint || The previous output transaction reference, as an OutPoint structure
|-
| 1+ || script length || [[Protocol_specification#Variable_length_integer|var_int]] || The length of the signature script
|-
| ? || signature script || uchar[] || Computational Script for confirming transaction authorization
|-
| 4 || [http://bitcoin.stackexchange.com/q/2025/323 sequence] || uint32_t || Transaction version as defined by the sender. Intended for "replacement" of transactions when information is updated before inclusion into a block.
|}

The OutPoint structure consists of the following fields:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 32 || hash || char[32] || The hash of the referenced transaction.
|-
| 4 || index || uint32_t || The index of the specific output in the transaction. The first output is 0, etc.
|}

The Script structure consists of a series of pieces of information and operations related to the value of the transaction.

(Structure to be expanded in the future… see script.h and script.cpp and [[Script]] for more information)

The TxOut structure consists of the following fields:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 8 || value || int64_t || Transaction Value
|-
| 1+ || pk_script length || [[Protocol_specification#Variable_length_integer|var_int]] || Length of the pk_script
|-
| ? || pk_script || uchar[] || Usually contains the public key as a Bitcoin script setting up conditions to claim this output.
|}

Example ''tx'' message:
<pre>
000000 F9 BE B4 D9 74 78 00 00 00 00 00 00 00 00 00 00 ....tx..........
000010 02 01 00 00 E2 93 CD BE 01 00 00 00 01 6D BD DB .............m..
000020 08 5B 1D 8A F7 51 84 F0 BC 01 FA D5 8D 12 66 E9 .[...Q........f.
000030 B6 3B 50 88 19 90 E4 B4 0D 6A EE 36 29 00 00 00 .;P......j.6)...
000040 00 8B 48 30 45 02 21 00 F3 58 1E 19 72 AE 8A C7 ..H0E.!..X..r...
000050 C7 36 7A 7A 25 3B C1 13 52 23 AD B9 A4 68 BB 3A .6zz%;..R#...h.:
000060 59 23 3F 45 BC 57 83 80 02 20 59 AF 01 CA 17 D0 Y#?E.W... Y.....
000070 0E 41 83 7A 1D 58 E9 7A A3 1B AE 58 4E DE C2 8D .A.z.X.z...XN...
000080 35 BD 96 92 36 90 91 3B AE 9A 01 41 04 9C 02 BF 5...6..;...A....
000090 C9 7E F2 36 CE 6D 8F E5 D9 40 13 C7 21 E9 15 98 .~.6.m...@..!...
0000A0 2A CD 2B 12 B6 5D 9B 7D 59 E2 0A 84 20 05 F8 FC *.+..].}Y... ...
0000B0 4E 02 53 2E 87 3D 37 B9 6F 09 D6 D4 51 1A DA 8F N.S..=7.o...Q...
0000C0 14 04 2F 46 61 4A 4C 70 C0 F1 4B EF F5 FF FF FF ../FaJLp..K.....
0000D0 FF 02 40 4B 4C 00 00 00 00 00 19 76 A9 14 1A A0 ..@KL......v....
0000E0 CD 1C BE A6 E7 45 8A 7A BA D5 12 A9 D9 EA 1A FB .....E.z........
0000F0 22 5E 88 AC 80 FA E9 C7 00 00 00 00 19 76 A9 14 "^...........v..
000100 0E AB 5B EA 43 6A 04 84 CF AB 12 48 5E FD A0 B7 ..[.Cj.....H^...
000110 8B 4E CC 52 88 AC 00 00 00 00 .N.R......

Message header:
F9 BE B4 D9 - main network magic bytes
74 78 00 00 00 00 00 00 00 00 00 00 - "tx" command
02 01 00 00 - payload is 258 bytes long
E2 93 CD BE - checksum of payload

Transaction:
01 00 00 00 - version

Inputs:
01 - number of transaction inputs

Input 1:
6D BD DB 08 5B 1D 8A F7 51 84 F0 BC 01 FA D5 8D - previous output (outpoint)
12 66 E9 B6 3B 50 88 19 90 E4 B4 0D 6A EE 36 29
00 00 00 00

8B - script is 139 bytes long

48 30 45 02 21 00 F3 58 1E 19 72 AE 8A C7 C7 36 - signature script (scriptSig)
7A 7A 25 3B C1 13 52 23 AD B9 A4 68 BB 3A 59 23
3F 45 BC 57 83 80 02 20 59 AF 01 CA 17 D0 0E 41
83 7A 1D 58 E9 7A A3 1B AE 58 4E DE C2 8D 35 BD
96 92 36 90 91 3B AE 9A 01 41 04 9C 02 BF C9 7E
F2 36 CE 6D 8F E5 D9 40 13 C7 21 E9 15 98 2A CD
2B 12 B6 5D 9B 7D 59 E2 0A 84 20 05 F8 FC 4E 02
53 2E 87 3D 37 B9 6F 09 D6 D4 51 1A DA 8F 14 04
2F 46 61 4A 4C 70 C0 F1 4B EF F5

FF FF FF FF - sequence

Outputs:
02 - 2 Output Transactions

Output 1:
40 4B 4C 00 00 00 00 00 - 0.05 BTC (5000000)
19 - pk_script is 25 bytes long

76 A9 14 1A A0 CD 1C BE A6 E7 45 8A 7A BA D5 12 - pk_script
A9 D9 EA 1A FB 22 5E 88 AC

Output 2:
80 FA E9 C7 00 00 00 00 - 33.54 BTC (3354000000)
19 - pk_script is 25 bytes long

76 A9 14 0E AB 5B EA 43 6A 04 84 CF AB 12 48 5E - pk_script
FD A0 B7 8B 4E CC 52 88 AC

Locktime:
00 00 00 00 - lock time
</pre>

=== block ===

The '''block''' message is sent in response to a getdata message which requests transaction information from a block hash.

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || version || uint32_t || Block version information, based upon the software version creating this block
|-
| 32 || prev_block || char[32] || The hash value of the previous block this particular block references
|-
| 32 || merkle_root || char[32] || The reference to a Merkle tree collection which is a hash of all transactions related to this block
|-
| 4 || timestamp || uint32_t || A unix timestamp recording when this block was created (Currently limited to dates before the year 2106!)
|-
| 4 || bits || uint32_t || The calculated [[Difficulty|difficulty target]] being used for this block
|-
| 4 || nonce || uint32_t || The nonce used to generate this block… to allow variations of the header and compute different hashes
|-
| ? || txn_count || [[Protocol_specification#Variable_length_integer|var_int]] || Number of transaction entries
|-
| ? || txns || tx[] || Block transactions, in format of "tx" command
|}

The SHA256 hash that identifies each block (and which must have a run of 0 bits) is calculated from the first 6 fields of this structure (version, prev_block, merkle_root, timestamp, bits, nonce, and standard SHA256 padding, making two 64-byte chunks in all) and ''not'' from the complete block. To calculate the hash, only two chunks need to be processed by the SHA256 algorithm. Since the ''nonce'' field is in the second chunk, the first chunk stays constant during mining and therefore only the second chunk needs to be processed. However, a Bitcoin hash is the hash of the hash, so two SHA256 rounds are needed for each mining iteration.
See [[Block hashing algorithm]] for details and an example.

=== headers ===

The ''headers'' packet returns block headers in response to a ''getheaders'' packet.

Payload:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || count || [[Protocol_specification#Variable_length_integer|var_int]] || Number of block headers
|-
| 81x? || headers || [[Protocol_specification#Block_Headers|block_header]][] || [[Protocol_specification#Block_Headers|Block headers]]
|}

Note that the block headers in this packet include a transaction count (a var_int, so there can be more than 81 bytes per header) as opposed to the block headers which are sent to miners.

=== getaddr ===

The getaddr message sends a request to a node asking for information about known active peers to help with identifying potential nodes in the network. The response to receiving this message is to transmit an addr message with one or more peers from a database of known active peers. The typical presumption is that a node is likely to be active if it has been sending a message within the last three hours.

No additional data is transmitted with this message.

=== mempool ===

The mempool message sends a request to a node asking for information about transactions it has verified but which have not yet confirmed. The response to receiving this message is an inv message containing the transaction hashes for all the transactions in the node's mempool.

No additional data is transmitted with this message.

It is specified in [[BIP_0035|BIP 35]]. Since [[BIP_0037|BIP 37]], only transactions matching the filter are replied.

=== checkorder ===

This message is used for [[IP Transactions]], to ask the peer if it accepts such transactions and allow it to look at the content of the order.

It contains a CWalletTx object

Payload:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
|colspan="4"| Fields from CMerkleTx
|-
| ? || hashBlock
|-
| ? || vMerkleBranch
|-
| ? || nIndex
|-
|colspan="4"| Fields from CWalletTx
|-
| ? || vtxPrev
|-
| ? || mapValue
|-
| ? || vOrderForm
|-
| ? || fTimeReceivedIsTxTime
|-
| ? || nTimeReceived
|-
| ? || fFromMe
|-
| ? || fSpent
|}

=== submitorder ===

Confirms an order has been submitted.

Payload:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 32 || hash || char[32] || Hash of the transaction
|-
| ? || wallet_entry || CWalletTx || Same payload as checkorder
|}

=== reply ===

Generic reply for [[IP Transactions]]

Payload:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || reply || uint32_t || reply code
|}

Possible values:

{|class="wikitable"
! Value !! Name !! Description
|-
| 0 || SUCCESS || The IP Transaction can proceed (''checkorder''), or has been accepted (''submitorder'')
|-
| 1 || WALLET_ERROR || AcceptWalletTransaction() failed
|-
| 2 || DENIED || IP Transactions are not accepted by this node
|}

=== ping ===

The ''ping'' message is sent primarily to confirm that the TCP/IP connection is still valid. An error in transmission is presumed to be a closed connection and the address is removed as a current peer.

Payload:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 8 || nonce || uint64_t || random nonce
|}

=== pong ===

The ''pong'' message is sent in response to a ''ping'' message. In modern protocol versions, a ''pong'' response is generated using a nonce included in the ping.

Payload:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 8 || nonce || uint64_t || nonce from ping
|}

=== filterload, filteradd, filterclear, merkleblock ===

These messages are related to Bloom filtering of connections and are defined in [[BIP 0037]].

=== alert ===

An '''alert''' is sent between nodes to send a general notification message throughout the network. If the alert can be confirmed with the signature as having come from the the core development group of the Bitcoin software, the message is suggested to be displayed for end-users. Attempts to perform transactions, particularly automated transactions through the client, are suggested to be halted. The text in the Message string should be relayed to log files and any user interfaces.

Alert format:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || payload || var_str || Serialized alert payload
|-
| ? || signature || var_str || An ECDSA signature of the message
|}

The developers of Satoshi's client use this public key for signing alerts:
04fc9702847840aaf195de8442ebecedf5b095cdbb9bc716bda9110971b28a49e0ead8564ff0db22209e0374782c093bb899692d524e9d6a6956e7c5ecbcd68284
(hash) 1AGRxqDa5WjUKBwHB9XYEjmkv1ucoUUy1s

The payload is serialized into a var_str to ensure that versions using incompatible alert formats can still relay alerts among one another. The current alert payload format is:
{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 4 || Version || int32_t || Alert format version
|-
| 8 || RelayUntil || int64_t || The timestamp beyond which nodes should stop relaying this alert
|-
| 8 || Expiration || int64_t || The timestamp beyond which this alert is no longer in effect and should be ignored
|-
| 4 || ID || int32_t || A unique ID number for this alert
|-
| 4 || Cancel || int32_t || All alerts with an ID number less than or equal to this number should be canceled: deleted and not accepted in the future
|-
| ? || setCancel || set<int> || All alert IDs contained in this set should be canceled as above
|-
| 4 || MinVer || int32_t || This alert only applies to versions greater than or equal to this version. Other versions should still relay it.
|-
| 4 || MaxVer || int32_t || This alert only applies to versions less than or equal to this version. Other versions should still relay it.
|-
| ? || setSubVer || set<string> || If this set contains any elements, then only nodes that have their subVer contained in this set are affected by the alert. Other versions should still relay it.
|-
| 4 || Priority || int32_t || Relative priority compared to other alerts
|-
| ? || Comment || string || A comment on the alert that is not displayed
|-
| ? || StatusBar || string || The alert message that is displayed to the user
|-
| ? || Reserved || string || Reserved
|}

Sample alert (no message header):
73010000003766404f00000000b305434f00000000f2030000f1030000001027000048ee0000
0064000000004653656520626974636f696e2e6f72672f666562323020696620796f75206861
76652074726f75626c6520636f6e6e656374696e672061667465722032302046656272756172
79004730450221008389df45f0703f39ec8c1cc42c13810ffcae14995bb648340219e353b63b
53eb022009ec65e1c1aaeec1fd334c6b684bde2b3f573060d5b70c3a46723326e4e8a4f1

Version: 1
RelayUntil: 1329620535
Expiration: 1329792435
ID: 1010
Cancel: 1009
setCancel: <empty>
MinVer: 10000
MaxVer: 61000
setSubVer: <empty>
Priority: 100
Comment: <empty>
StatusBar: "See bitcoin.org/feb20 if you have trouble connecting after 20 February"
Reserved: <empty>

== Scripting ==

See [[script]].

== Wireshark dissector ==
A dissector for wireshark is being developed at https://github.com/blueCommand/bitcoin-dissector

==See Also==

* [[Network]]
* [[Protocol rules]]
* [[Hardfork Wishlist]]

==References==
<references />

[[zh-cn:协议说明]]
[[Category:Technical]]
[[Category:Developer]]

Mini private key format

2013-12-04T18:41:13Z

MidnightLightning: /* Example with SHA256 */ Add command-line verification command, and formatting

[[Image:QR-privkeys-sidebyside.png|thumb|right|QR codes of the same private key, in mini versus regular private key format. Both codes have the same dot density and error correction level, but the mini key is 57% of the full code's size.]]
The '''mini private key format''' is a method of encoding a Bitcoin private key in as few as 30 characters so that it can be embedded in a small space. This private key format was first used in Casascius physical bitcoins, and is also favorable for use in QR codes. The fewer characters encoded in a QR code, the lower dot density can be used, as well as more dots allocated to error correction in the same space, significantly improving readability and resistance to damage. The mini private key format offers its own built-in check code as a small margin of protection against typos.

An example key using this encoding is '''S6c56bnXQiBjk9mqSYE7ykVQ7NzrRy'''.

==Usage on a physical bitcoin==
The way it might appear within a physical bitcoin is on a round card printed as follows:

Side of discs showing mini private key: (from [[Casascius physical bitcoins]]) 
[[Image:Miniprivkeys.jpg|300px]]

Side of discs showing prefix of bitcoin address (printed on the opposite side): 
[[Image:Minipubkeys.jpg|300px]]

The examples in this article use the private key and Bitcoin address of the leftmost circle in the above two photos.

==Usage in bar codes==
The mini private key is suitable for use in QR codes. The recommended settings for maximizing readability are: QR version 3, error correction level Q (near highest, 25% possible lost codeword recovery). This results in a 29x29 grid. A minikey QR code can also fit in a 25x25 grid with QR version 2, error correction level L (lowest, 7% possible lost codeword recovery).

The sample private minikey encoded as a QR code on a 29x29 grid looks like this:

[[Image:Private_minikey_in_2D_barcode.gif]]

The mini private key is small enough to fit in a one-dimensional barcode while still remaining practical. Among the most popular one-dimensional barcode symbologies, the one known as "Code 128" is best suited for encoding a minikey due to its favorable data density and support for mixed case strings. The variant known as "Code 128-B" produces the shortest code for strings containing lowercase characters.

The sample private minikey encoded with Code 128-B looks like this:

[[Image:Private_minikey_in_1D_barcode.gif]]

==Import==
Mini private keys can be imported through the following clients/services:

===Applications===
* [[Armory]]

The current mainline ("Satoshi") client cannot currently be used to import minikeys.

===Mobile===

* Mt. Gox Mobile can redeem a private key scanned from a QR Code or is entered using the keyboard. Upon importing, Mt. Gox sweeps the funds to a secondary address, and then a user must wait for six confirmations before the funds will appear in the Mt. Gox account.

===Web===

* [[BlockChain.info]]
** Private keys can be imported into a Blockchain.info wallet and bitcoins can be sent to another address immediately upon import without needing to wait for any confirmations. Even after import, funds remain associated with the private key until they are actually spent to a different address.
* [[StrongCoin]]
* [[Mt. Gox]]
** Importing minikeys is done through the deposit screen using the "Import Private Key" deposit method. Upon importing, Mt. Gox sweeps the funds to a secondary address, and then a user must wait for six confirmations before the funds will appear in the Mt. Gox account. Removing the imported bitcoins from the Mt. Gox account is treated as a bitcoin withdrawal and counts against daily/monthly limits.
** Mt. Gox also permanently remembers any imported private key and automatically sweeps any future funds sent to it into the user's Mt. Gox account.
** Mt. Gox's import screen doesn't properly detect or reject typos. If you make a mistake, Mt. Gox will treat it as a valid entry and report that a private key with a balance of 0.00 BTC from a bitcoin address you won't recognize was "successfully" imported.

==Decoding==
The private key encoding consists of 30 alphanumeric characters from the [[base58]] alphabet used in Bitcoin. The first of the characters is always the uppercase letter S.

To determine whether the minikey is valid:

# Add a question mark to the end of the mini private key string.
# Take the SHA256 hash of the entire string. However, we will only look at the first byte of the result.
# If the first byte is 00, the string is a well-formed minikey. If the first byte is not 00, the string should be rejected as a minikey.

===Example with SHA256===
Here is an example with the sample private key <tt>S6c56bnXQiBjk9mqSYE7ykVQ7NzrRy</tt>.

The string "<tt>S6c56bnXQiBjk9mqSYE7ykVQ7NzrRy?</tt>" has a SHA256 value that begins with 00, so it is well-formed.

To obtain the full 256-bit private key, simply take the SHA256 hash of the entire string. There is no encoding for line breaks in the string, even if the key is broken into multiple lines for printing. The SHA256 should be taken of exactly thirty bytes.

SHA256("S6c56bnXQiBjk9mqSYE7ykVQ7NzrRy") = 4C7A9640C72DC2099F23715D0C8A0D8A35F8906E3CAB61DD3F78B67BF887C9AB

This sample key in [[wallet export format]] is <tt>5JPy8Zg7z4P7RSLsiqcqyeAF1935zjNUdMxcDeVrtU1oarrgnB7</tt>, and the corresponding [[Bitcoin address]] is <tt>1CciesT23BNionJeXrbxmjc7ywfiyM4oLW</tt>.

==== Command line verification ====
To calculate SHA256 from the command line on OSX or Linux devices:

echo -n "S6c56bnXQiBjk9mqSYE7ykVQ7NzrRy?" | shasum -a 256

That should output a line of text like "<tt>000f2453798ad4f951eecced2242eaef3e1cbc8a7c813c203ac7ffe57060355d -</tt>". Since the first two characters are <tt>00</tt> the verification passes for the mini key <tt>S6c56bnXQiBjk9mqSYE7ykVQ7NzrRy</tt>

==Check code==
The mini private key format offers a simple typo check code. Mini private keys must be generated in a "brute force" fashion, keeping only keys that conform to the format's rules. If a key is well-formed (30 Base58 characters starting with S), but fails the hash check, then it probably contains a typo.

If the SHA256 hash of the string followed by '?' doesn't result in something that begins with 0x00, the string is not a valid mini private key.

==Creating mini private keys==
Creating mini private keys is relatively simple. One program which can create such keys is [[Casascius Bitcoin Utility]].

Mini private keys must be created "from scratch", as the conversion from mini private key to full-size private key is one-way. In other words, there is no way to convert an existing full-size private key into a mini private key.

To create mini private keys, simply create random strings that satisfy the well-formedness requirement, and then eliminate the ones that do not pass the typo check. (This means eliminating more than 99% of the candidates.) Then use the appropriate algorithm to compute the corresponding private key, and in turn, the matching Bitcoin address. The Bitcoin address can always be computed from just the private key.

It is strongly advisable to avoid using the digit "1" in minikeys unless it is being printed in such a way where a user is unlikely to mistake it for the lowercase letter "l". Few clients and redemption tools are prepared to tell the user that their entry containing the letter "l" should actually be the number "1" - rather, they will simply reject the code and may leave the user confused.

In all cases, you '''must''' use a secure cryptographic random number generator to eliminate risks of predictability of the random strings.

==Casascius Series 1 coins==

Casascius Series 1 Physical Bitcoins use a 22-character variant of the minikey format, instead of 30 characters. Everything is the same other than the length. To properly implement minikey redemption, services and clients MUST support the 30-character format, but MAY support the 22-character format as well. Use of the 22-character format for future applications is discouraged due to security considerations.

==Python Code==
The following code produces sample 30-character SHA256-based mini private keys in Python. For real-world use, ''random'' must be replaced with a better source of entropy, as the Python documentation for ''random'' states the function ''"is completely unsuitable for cryptographic purposes"''.

<source lang="python">
import random
import hashlib

BASE58 = '23456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'

def Candidate():
"""
Generate a random, well-formed mini private key.
"""
return('%s%s' % ('S', ''.join(
[BASE58[ random.randrange(0,len(BASE58)) ] for i in range(29)])))

def GenerateKeys(numKeys = 10):
"""
Generate mini private keys and output the mini key as well as the full
private key. numKeys is The number of keys to generate, and
"""
keysGenerated = 0
totalCandidates = 0
while keysGenerated < numKeys:
try:
cand = Candidate()
# Do typo check
t = '%s?' % cand
# Take one round of SHA256
candHash = hashlib.sha256(t).digest()
# Check if the first eight bits of the hash are 0
if candHash[0] == '\x00':
privateKey = GetPrivateKey(cand)
print('\n%s\nSHA256( ): %s\nsha256(?): %s' %
(cand, privateKey, candHash.encode('hex_codec')))
if CheckShortKey(cand):
print('Validated.')
else:
print('Invalid!')
keysGenerated += 1
totalCandidates += 1
except KeyboardInterrupt:
break
print('\n%s: %i\n%s: %i\n%s: %.1f' %
('Keys Generated', keysGenerated,
'Total Candidates', totalCandidates,
'Reject Percentage',
100*(1.0-keysGenerated/float(totalCandidates))))

def GetPrivateKey(shortKey):
"""
Returns the hexadecimal representation of the private key corresponding
to the given short key.
"""
if CheckShortKey(shortKey):
return hashlib.sha256(shortKey).hexdigest()
else:
print('Typo detected in private key!')
return None

def CheckShortKey(shortKey):
"""
Checks for typos in the short key.
"""
if len(shortKey) != 30:
return False
t = '%s?' % shortKey
tHash = hashlib.sha256(t).digest()
# Check to see that first byte is \x00
if tHash[0] == '\x00':
return True
return False
</source>

Electrum/Documentation

2013-11-28T01:53:25Z

MidnightLightning: /* What is the "Seed" of a Deterministic Wallet in Electrum? */ Comparison number of atoms was off by an order of magnitude

==Documentation of Electrum Bitcoin Client (Focus on the GUI)==
This page tries to document certain aspects of the [[Electrum|Electrum]] Bitcoin Client. The focus is on explaining certain aspects of its GUI, such that it gets easier for the user to understand its use.

More documentation, especially with regard to command line parameters, can be found at the parent page of this Wiki, i.e. [[Electrum|here]].

===Version Info===
Unless stated otherwise in particular sub-sections, the present state of this documentation is based on
* '''Electrum version 0.58'''
As this documentation gets updated, this "version info" can be updated, too!

Later versions of Electrum may add new features or deviate from this description to some extend.

===Open/Unclear Points===

Discussions about unclear points should take place on the [[Talk:Electrum/Documentation|Discussion page.]]

==What is a "Wallet" and a "Bitcoin Address"?==
* (General, not specific to Electrum)

Your wallet is a list of Bitcoin addresses (more precisely: a list of privat/public key pairs). Each address "contains" (or is associated with) a certain amount of Bitcoins at a given time.

Your wallet's balance is the sum of all Bitcoins of all your wallet's Bitcoin addresses.

Your wallet consists of both [[#Normal Addresses|normal addresses]] and [[#Change Addresses|change addresses]]. Although they are fully equivalent from the Bitcoin protocol's point of view, they are different in how they are used by Bitcoin clients like Electrum.

===Normal Addresses===
* (More or less general, not too specific to Electrum)
====How are New "Normal Addresses" Created for my Wallet?====
A Bitcoin client allows you to trigger the generation of a new Bitcoin address either manually, or it generates new addresses automatically upon certain conditions. The latter applies to Electrum: Depending on the "[[#What is the "Gap Limit"?|gap limit]]" setting in Electrum's program preferences, there will always be a certain number of unused addresses showing up in your list of receive addresses (=your own wallet's addresses), and as these addresses get used, new ones will show up automatically.

Typically you want to use a new address for receiving Bitcoins from somebody, instead of using any of your wallet's present addresses that have already been used for earlier transactions. This is to protect your privacy, because all Bitcoins transfers are published in the blockchain and can be read by anyone.

Another way of adding addresses to your wallet is to [[#Imported Addresses|import]] private keys (with their addresses of course), using Electrum's [[Electrum|command line options]]. See section about [[#Imported Addresses|imported addresses]] for more details.

===Change Addresses===
* (More or less general, not too specific to Electrum)
====What is a "Change Address", and why is it useful?====
The concept of change addresses is a feature not of the Bitcoin protocol, but of a Bitcoin client. It is implemented not only in Electrum but in most Bitcoin clients, including the original "Satoshi" Bitcoin client.

'''How it works:'''

Whenever your Bitcoin client (e.g. Electrum) sends Bitcoins from your wallet's address "A" to a foreing address "B", a new change address "C" is created by Electrum and added to your wallet.

Example: Address "A" has 20 BTC. Electrum sends 9 BTC from "A" to "B". The change (20-9 = 11 BTC) is sent to the "change address" "C". For this purpose, address "C" is created by Electrum at this moment and added to your wallet.

Exception: If all the Bitcoins of "A" are sent to "B", there is no need for creating a change address "C".

Actually, Bitcoin clients can also work without change addresses. In this case, the change would be sent back to "A" instead of the new address "C".

'''Why the concept of "change addresses" is useful:'''

* Using a new change address makes it more difficult for other people (by analyzing the blockchain) to track how many Bitcoins you have or where you're spending them.
* It also conceals which output is the "spend" and which is the "change".

===Imported Addresses===
Instead of generating new addresses in the default way from the wallet's [[#Seed|seed]], Electrum also allows you to import addresses (and their private keys of course) from external sources, e.g. from another Bitcoin client's wallet. For this, use Electrum's [[Electrum|command line]] options. Note that imported addresses cannot be recovered from your wallet's [[#Seed|seed]] and therefore need to be secured separately for a complete backup of your wallet.

Imported addresses can be used like any other [[#Normal Addresses|normal]] receive address with Electrum for transmission or reception of Bitcoins, and can also be (un)tagged as [[#What does it mean to "Prioritize" or "Freeze" Addresses in Electrum?|"prioritized" or "frozen"]].

===Deterministic Wallet===
====What is a "Deterministic Wallet" in Electrum?====
Traditionally, all new addresses (incl. the private keys of course) added to the wallet ([[#Normal Addresses|normal addresses]] or [[#Change Addresses|change addresses]]) are generated randomly. This is the case e.g. for the original "Satoshi Bitcoin Client" (at least as of today, version 0.6.2).

Contrary to that, a Bitcoin client with a "Deterministic Wallet" will generate all new addresses accoding to a pre-defined (i.e. "deterministic") algorithm as a function of a wallet-specific [[#Seed|seed]], which is a 128 bit number. This means, if the seed is known, all new addresses that Electrum will ever create for this wallet are known, because Electrum's algorithm is known (and open source).
This is a big advantage when it comes to making wallet backups:
* ''Traditionally'', a wallet backup just contains the bitcoin addresses (and private keys of course) that have been created by the client by the time the backup was made. If the user performs transactions after the backup, new addresses ([[#Normal Addresses|normal]] or [[#Change Addresses|change]] addresses) will be generated and added to the wallet. These are not included in the backup yet. If the wallet in use gets lost, all the Bitcoins that are associated with the new addresses will also be lost. To avoid the risk of a too high loss, regular wallet backups are important.
* ''With a Deterministic Wallet'' (like with Electrum), the wallet backup only needs to contain the seed, and all new addresses generated in the future are already secured by the initial backup. Hence, regular new backups are not required!

===Seed===
====What is the "Seed" of a Deterministic Wallet in Electrum?====
The Seed of a [[#Deterministic Wallet|deterministic wallet]] is a series of 128 random bits in Electrum.
For convenience, a seed can also be expressed by a sequence of 12 words in Electrum, and it also supports generation of a QR code to facilitate the backup of the seed.

So there are 2128 possible seeds for a deterministic wallet in Electrum.
For comparison, the total number of Bitcoin addresses is 2160, and the number of atoms in the universe is 2166 ([http://en.wikipedia.org/wiki/Observable_universe#Matter_content_-_number_of_atoms ~1080]).
So there exists one Bitcoin address per 64 atoms in the universe, and there exists one seed of Electrum wallets per 4.3 Billion Bitcoin addresses.

===What is the "Gap Limit"?===

The gap limit is the maximal number of contiguous unused addresses in your deterministic sequence of addresses.

If you recover your wallet from seed, you will notice that the gap limit is asked by the recovery dialog.
It is used in order to decide when to stop the recovery procedure.

If you need to have more receiving addresses in your wallet, you may increase your gap limit (expert mode).
This, however, means that you will need to remember the new limit in order to be able to recover your wallet from seed.

==More on the Electrum GUI==

===Send tab and completions===

The "pay to" input line does not only accept bitcoin addresses. You may type a label from your list of contacts, or an alias.

Completions are available based on the labels of your addressbook. Example:

[[Image:Electrum completion 0.png|450px]]
[[Image:Electrum completion 1.png|450px]]

===What does it mean to "Prioritize" or "Freeze" Addresses in Electrum?===
When sending Bitcoins to a foreign address, Electrum will by default use a built-in method to select the address(es) of the wallet used for sending these Bitcoins.

* When you ''prioritize'' some of your wallet's addresses, these addresses will be used with preference. Other addresses will not be used until the prioritized addresses contain no more Bitcoins.
* When you ''freeze'' some of your wallet's addresses, these addresses will not be used for sending bitcoins. Instead, other addresses will be used. Sending Bitcoins is not possible if the non-frozen addresses of your wallet do not contain enough funds.

The user can (de)prioritize or (un)freeze both [[#Normal Addresses|normal]] and [[#Change Addresses|change]] addresses.

Note: Clearly, an address can not be "prioritized" and "frozen" at the same time.

===What does the "Tx" column mean in Electrum?===
* Expert Mode only
* Applies to "Receive" tab (own wallet's addresses) and "Contacts" tab (foreing addresses).

Tx stands for "Transaction"

The Tx column in Electrum displays a number for each Bitcoin address in the address list, both for own addresses ("Receive" tab) and for foreing addresses ("Contacts" tab).

'''In the "Receive" tab (own addresses):'''

The number in the Tx column indicates the total number of _incoming_ Bitcoin transactions that have ever been sent to this address.

'''In the "Contacts" tab (foreign addresses):'''

The number in the Tx column indicates the total number of Bitcoin transactions that have ever been carried out from addresses of the current wallet towards this contact address

===What does the "Balance" column mean in Electrum?===
* Expert Mode only
* Applies to "Receive" tab only (i.e. own wallet's addresses).

The balance column indicates the amount of Bitcoins belonging to the given address.
The individual balances add up to the total balance of your wallet.

===What does the "Flag" column mean in Electrum?===
* Expert Mode only
* Applies to "Receive" tab only (i.e. own wallet's addresses).

This column indicates certain properties of the different addresses:
* C = [[#Change Addresses|Change address]] (without a "C" it means it is a [[#Normal Addresses|normal address]])
* P = Prioritized address
* F = Frozen address
* I = [[#Imported Addresses|Imported address]]

Note: P and F flags can be applied to both [[#Normal Addresses|normal]] and [[#Change Addresses|change]] addresses, and also to [[#Imported Addresses|imported addresses]].

===What do colors mean?===
In the Receive tab:
*green = prioritized
*blue = frozen
In the Contacts tab:
*gray = alias

==Troubleshooting==

=== 'transaction rejected by memorypool' errors ===

When you send a transaction, there is a delay before the Electrum client displays the transaction in its history.
This is because the server polls bitcoind's memorypool every 10 seconds.

If you create another transaction during this interval, during which the first tx is not displayed,
then your client will pick the same coins again, and the transaction will be rejected as a [[Double-spending|double spend]].

=== Using Electrum through a HTTP proxy ===

When you are behind a firewall you can use a HTTP proxy to connect to an Electrum server with some limitations¹.

On Linux (and other POSIX-like systems) set the ''http_proxy'' variable and start the Electrum client, e.g.
<pre>
$ export http_proxy="http://<proxyname>:<proxyport>/"
$ ./electrum
</pre>
Once the client comes up you need to change your server connection to 'http' and to adjust the port, afterwards your Electrum client should work as usual.

¹ Limitations:
* Electrum server selection won't work; you must manually enter the connection data (server, port & protocol)
* Exchange rates cannot be fetched/displayed.

==External Links==
* [http://electrum.org Electrum] project website
* [https://github.com/spesmilo/electrum Electrum] project source (github)
* [https://bitcointalk.org/index.php?topic=50936.msg950497#msg950497 Electrum Forum] - here this documentation was started
* [https://github.com/spesmilo/electrum/blob/master/docs Electrum Docs] updated documentation

BIP 0032

2013-10-30T00:13:20Z

MidnightLightning: Use monospace font for functions and variable names to make lower-case variables stand out, and upper-case 'i' and lower case 'L' more distinguishable

{{bip}}

RECENT CHANGES:
* [16 Apr 2013] Added private derivation for <tt>i >= 0x80000000</tt> (less risk of parent private key leakage)
* [30 Apr 2013] Switched from multiplication by <tt>IL</tt> to addition of <tt>IL</tt> (faster, easier implementation)
* [25 May 2013] Added test vectors

<pre>
BIP: 32
Title: Hierarchical Deterministic Wallets
Author: Pieter Wuille
Status: Accepted
Type: Informational
Created: 11-02-2012
</pre>

==Abstract==

This document describes [[Deterministic Wallet|hierarchical determinstic wallets]] (or "HD Wallets"): wallets which can be shared partially or entirely with different systems, each with or without the ability to spend coins.

The specification is intended to set a standard for deterministic wallets that can be interchanged between different clients. Although the wallets described here have many features, not all are required by supporting clients.

The specification consists of two parts. In a first part, a system for deriving a tree of keypairs from a single seed is presented. The second part demonstrates how to build a wallet structure on top of such a tree.

==Motivation==

The Bitcoin reference client uses randomly generated keys. In order to avoid the necessity for a backup after every transaction, (by default) 100 keys are cached in a pool of reserve keys. Still, these wallets are not intended to be shared and used on several systems simultaneously. They support hiding their private keys by using the wallet encrypt feature and not sharing the password, but such "neutered" wallets lose the power to generate public keys as well.

Deterministic wallets do not require such frequent backups, and elliptic curve mathematics permit schemes where one can calculate the public keys without revealing the private keys. This permits for example a webshop business to let its webserver generate fresh addresses (public key hashes) for each order or for each customer, without giving the webserver access to the corresponding private keys (which are required for spending the received funds).

However, deterministic wallets typically consist of a single "chain" of keypairs. The fact that there is only one chain means that sharing a wallet happens on an all-or-nothing basis. However, in some cases one only wants some (public) keys to be shared and recoverable. In the example of a webshop, the webserver does not need access to all public keys of the merchant's wallet; only to those addresses which are used to receive customer's payments, and not for example the change addresses that are generated when the merchant spends money. Hierarchical deterministic wallets allow such selective sharing by supporting multiple keypair chains, derived from a single root.

==Specification: Key derivation==

===Conventions===

In the rest of this text we will assume the public key cryptography used in Bitcoin, namely elliptic curve cryptography using the field and curve parameters defined by secp256k1 (http://www.secg.org/index.php?action=secg,docs_secg). Variables below are either:
* integers modulo the order of the curve (referred to as n), serialized as 32 bytes, most significant byte first.
* coordinates of points on the curve, serialized as specified in SEC1 in compressed form: [0x02 or 0x03] + 32 byte x coordinate), where the header byte depends on the parity of the omitted y coordinate.
* byte sequences

We shall denote the compressed form of point <tt>P</tt> by <tt>χ(P)</tt>, which for secp256k1 will always be 33 bytes long.

Addition (+) of two coordinates is defined as application of the EC group operation. Multiplication (*) of an integer and a coordinate is defined as repeated application of the EC group operation. The generator element of the curve is called <tt>G</tt>. The public key <tt>K</tt> corresponding to the private key <tt>k</tt> is calculated as <tt>k*G</tt>. We do not distinguish between numbers or coordinates and their serialization as byte sequences.

===Extended keys===

In what follows, we will define a function that derives a number of child keys from a parent key. In order to prevent these from depending solely on the key itself, we extend both private and public keys first with an extra 256 bits of entropy. This extension, called the chain code, is identical for corresponding private and public keys, and consists of 32 bytes.

We represent an extended private key as <tt>(k, c)</tt>, with <tt>k</tt> the normal private key, and <tt>c</tt> the chain code. An extended public key is represented as <tt>(K, c)</tt>, with <tt>K = k*G</tt> and <tt>c</tt> the chain code.

===Child key derivation functions===

We allow for two different types of derivation: private and public.
* Private derivation: knowledge of the private key <tt>kpar</tt> and <tt>cpar</tt> is required to compute both <tt>ki</tt> and <tt>Ki</tt>.
* Public derivation: knowledge of the public key <tt>Kpar</tt> and <tt>cpar</tt> suffices to compute <tt>Ki</tt> (but not <tt>ki</tt>).

We define the private and public child key derivation functions:
* <tt>CKD((kpar, cpar), i) → (ki, ci)</tt>, defined for both private and public derivation.
* <tt>CKD′((Kpar, cpar), i) → (Ki, ci)</tt>, defined only for public derivation.

We use the most significant bit of <tt>i</tt> to specify which type of derivation to use. <tt>i</tt> is encoded as a 32 bit unsigned integer, most significant byte first; '||' represents concatenation.

====Private child key derivation====

To define <tt>CKD((kpar, cpar), i) → (ki, ci)</tt>:
* Check whether the highest bit (<tt>0x80000000</tt>) of <tt>i</tt> is set:
** If 1, private derivation is used: let <tt>I = HMAC-SHA512(Key = cpar, Data = 0x00 || kpar || i)</tt> [Note: The 0x00 pads the private key to make it 33 bytes long.]
** If 0, public derivation is used: let <tt>I = HMAC-SHA512(Key = cpar, Data = χ(kpar*G) || i)</tt>
* Split <tt>I = IL || IR</tt> into two 32-byte sequences, <tt>IL</tt> and <tt>IR</tt>.
* <tt>ki = IL + kpar (mod n)</tt>.
* <tt>ci = IR</tt>.
In case <tt>IL ≥ n</tt> or <tt>ki = 0</tt>, the resulting key is invalid, and one should proceed with the next value for <tt>i</tt>.
[Note: this has probability lower than 1 in 2127.]

====Public child key derivation====

To define <tt>CKD′((Kpar, cpar), i) → (Ki, ci)</tt>:
* Check whether the highest bit (<tt>0x80000000</tt>) of <tt>i</tt> is set:
** If 1, return error
** If 0, let <tt>I = HMAC-SHA512(Key = cpar, Data = χ(Kpar) || i)</tt>
* Split <tt>I = IL || IR</tt> into two 32-byte sequences, <tt>IL</tt> and <tt>IR</tt>.
* <tt>Ki = (IL + kpar)*G = IL*G + Kpar</tt>
* <tt>ci = IR</tt>.
In case <tt>IL ≥ n</tt> or <tt>Ki</tt> is the point at infinity, the resulting key is invalid, and one should proceed with the next value for <tt>i</tt>.

Note that the extended public key corresponding to the evaluation of <tt>CKD(kext, i)</tt> with public derivation (so with <tt>i < 0x80000000</tt>) is identical to the evaluation of <tt>CKD′(Kext, i)</tt>, with <tt>Kext</tt> the extended public key corresponding to <tt>kext</tt>. Symbolically, <tt>CKD((k, c), i)*G = CKD'((k*G, c), i)</tt>. This implies that <tt>CKD'</tt> can be used to derive all public keys corresponding to the private keys that <tt>CKD</tt> would find. It cannot be used to retrieve the private keys, however.

The HMAC-SHA512 function is specified in [http://tools.ietf.org/html/rfc4231 RFC 4231].

===The key tree===

The next step is cascading several <tt>CKD</tt> constructions to build a tree. We start with one root, the master extended key <tt>m</tt>. By evaluating <tt>CKD(m,i)</tt> for several values of <tt>i</tt>, we get a number of first-degree derivative nodes. As each of these is again an extended key, <tt>CKD</tt> can be applied to those as well. To shorten notation, we will write <tt>CKD(CKD(CKD(m,0x8000003),0x2),0x5)</tt> as <tt>m/3′/2/5</tt> now.

Each leaf node in the tree corresponds to an actual keypair, while the internal nodes correspond to the collection of keypairs that descends from them. The chain codes of the leaf nodes are ignored, and only their embedded private or public key is used. Because of this construction, knowing an extended private key allows reconstruction of all descendant private keys and public keys, and knowing an extended public keys allows reconstruction of all descendant public keys derived using public derivation.

===Key identifiers===

Extended keys can be identified by the Hash160 (RIPEMD160 after SHA256) of the serialized public key, ignoring the chain code. This corresponds exactly to the data used in traditional Bitcoin addresses. It is not advised to represent this data in base58 format though, as it may be interpreted as an address that way (and wallet software is not required to accept payment to the chain key itself).

The first 32 bits of the identifier are called the fingerprint.

===Serialization format===

Extended public and private keys are serialized as follows:
* 4 byte: version bytes (mainnet: <tt>0x0488B21E</tt> public, <tt>0x0488ADE4</tt> private; testnet: <tt>0x043587CF</tt> public, <tt>0x04358394</tt> private)
* 1 byte: depth: <tt>0x00</tt> for master nodes, <tt>0x01</tt> for level-1 descendants, ....
* 4 bytes: the fingerprint of the parent's key (<tt>0x00000000</tt> if master key)
* 4 bytes: child number. This is the number <tt>i</tt> in <tt>xi = xpar/i</tt>, with <tt>xi</tt> the key being serialized. This is encoded in MSB order. (<tt>0x00000000</tt> if master key)
* 32 bytes: the chain code
* 33 bytes: the public key or private key data (<tt>0x02 + X</tt> or <tt>0x03 + X</tt> for public keys, <tt>0x00 + k</tt> for private keys)

This 78 byte structure can be encoded like other Bitcoin data in Base58, by first adding 32 checksum bits (derived from the double SHA-256 checksum), and then converting to the Base58 representation. This results in a Base58-encoded string of up to 112 characters. Because of the choice of the version bytes, the Base58 representation will start with "xprv" or "xpub" on mainnet, "tprv" or "tpub" on testnet.

Note that the fingerprint of the parent only serves as a fast way to detect parent and child nodes in software, and software must be willing to deal with collisions. Internally, the full 160-bit identifier could be used.

When importing a serialized extended public key, implementations must verify whether the X coordinate in the public key data corresponds to a point on the curve. If not, the extended public key is invalid.

===Master key generation===

The total number of possible extended keypairs is almost 2512, but the produced keys are only 256 bits long, and offer about half of that in terms of security. Therefore, master keys are not generated directly, but instead from a potentially short seed value.

* Generate a seed S of a chosen length (at least 128 bits, but 256 is advised) from a (P)RNG.
* Calculate <tt>I = HMAC-SHA512(key="Bitcoin seed", msg=S)</tt>
* Split <tt>I</tt> into two 32-byte sequences, <tt>IL</tt> and <tt>IR</tt>.
* Use <tt>IL</tt> as master secret key, and <tt>IR</tt> as master chain code.
In case <tt>IL</tt> is 0 or <tt>>=n</tt>, the master key is invalid.

[[File:BIP32-derivation.png]]

==Specification: Wallet structure==

The previous sections specified key trees and their nodes. The next step is imposing a wallet structure on this tree. The layout defined in this section is a default only, though clients are encouraged to mimick it for compatibility, even if not all features are supported.

An HDW is organized as several 'accounts'. Accounts are numbered, the default account ("") being number 0. Clients are not required to support more than one account - if not, they only use the default account.

Each account is composed of two keypair chains: an internal and an external one. The external [[keychain]] is used to generate new public addresses, while the internal keychain is used for all other operations (change addresses, generation addresses, ..., anything that doesn't need to be communicated). Clients that do not support separate keychains for these should use the external one for everything.

* <tt>m/i′/0/k</tt> corresponds to the <tt>k</tt>'th keypair of the external chain of account number <tt>i</tt> of the HDW derived from master m.
* <tt>m/i′/1/k</tt> corresponds to the <tt>k</tt>'th keypair of the internal chain of account number <tt>i</tt> of the HDW derived from master m.

===Use cases===

====Full wallet sharing: <tt>m</tt>====

In cases where two systems need to access a single shared wallet, and both need to be able to perform spendings, one needs to share the master private extended key. Nodes can keep a pool of <tt>N</tt> look-ahead keys cached for external chains, to watch for incoming payments. The look-ahead for internal chains can be very small, as no gaps are to be expected here. An extra look-ahead could be active for the first unused account's chains - triggering the creation of a new account when used. Note that the name of the account will still need to be entered manually and cannot be synchronized via the block chain.

====Audits: <tt>M</tt>====

In case an auditor needs full access to the list of incoming and outgoing payments, one can share the master public extended key. This will allow the auditor to see all transactions from and to the wallet, in all accounts, but not a single secret key.

====Per-office balances: <tt>m/i′</tt>====

When a business has several independent offices, they can all use wallets derived from a single master. This will allow the headquarters to maintain a super-wallet that sees all incoming and outgoing transactions of all offices, and even permit moving money between the offices.

====Recurrent business-to-business transactions: <tt>M/i′/0</tt>====

In case two business partners often transfer money, one can use the extended public key for the external chain of a specific account (<tt>M/i′/0</tt>) as a sort of "super address", allowing frequent transactions that cannot (easily) be associated, but without needing to request a new address for each payment.
Such a mechanism could also be used by mining pool operators as variable payout address.

====Unsecure money receiver: <tt>M/i′/0</tt>====

When an unsecure webserver is used to run an e-commerce site, it needs to know public addresses that be used to receive payments. The webserver only needs to know the public extended key of the external chain of a single account. This means someone illegally obtaining access to the webserver can at most see all incoming payments, but will not (trivially) be able to distinguish outgoing transactions, nor see payments received by other webservers if there are several ones.

==Compatibility==

To comply with this standard, a client must at least be able to import an extended public or private key, to give access to its direct descendants as wallet keys. The wallet structure (master/account/chain/subchain) presented in the second part of the specification is advisory only, but is suggested as a minimal structure for easy compatibility - even when no separate accounts or distinction between internal and external chains is made. However, implementations may deviate from it for specific needs; more complex applications may call for a more complex tree structure.

==Security==

In addition to the expectations from the EC public-key cryptography itself:
* Given a public key <tt>K</tt>, an attacker cannot find the corresponding private key more efficiently than by solving the EC discrete logarithm problem (assumed to require 2128 group operations).
the intended security properties of this standard are:
* Given a child extended private key <tt>(ki,ci)</tt> and the integer <tt>i</tt>, an attacker cannot find the parent private key <tt>kpar</tt> more efficiently than a 2256 brute force of HMAC-SHA512.
* Given any number (<tt>2 <= N <= 232-1</tt>) of (index, extended private key) tuples (<tt>ij,(pj,cj)</tt>), with distinct <tt>ij</tt>'s, determining whether they are derived from a common parent extended private key (i.e., whether there exists a <tt>(ppar,cpar)</tt> such that for each <tt>j</tt> in <tt>[0..N-1] CKD((ppar,cpar),ij)=(pj,cj))</tt>, cannot be done more efficiently than a 2256 brute force of HMAC-SHA512.
Note however that the following properties does not exist:
* Given a parent extended public key <tt>(Kpar,cpar)</tt> and a child public key <tt>(Ki)</tt>, it is hard to find <tt>i</tt>.
* Given a parent extended public key <tt>(Kpar,cpar)</tt> and a child private key <tt>(ki)</tt> using public derivation, it is hard to find <tt>kpar</tt>.

Private and public keys must be kept safe as usual. Leaking a private key means access to coins - leaking a public key can mean loss of privacy.

Somewhat more care must be taken regarding extended keys, as these correspond to an entire (sub)tree of keys. One weakness that may not be immediately obvious, is that knowledge of the extended public key + a private key descending from it is equivalent to knowing the extended private key (i.e., every private and public key) in case public derivation is used. This means that extended public keys must be treated more carefully than regular public keys. This is the reason why accounts at the first level of the default wallet layout use private derivation, so a leak of account-specific (or below) private key never risks compromising the master.

==Test Vectors==

For more detailed information about these (such as intermediate values and other representations), see [[BIP_0032_TestVectors]]

Test vector 1

Master (hex): 000102030405060708090a0b0c0d0e0f
* [Chain m]
* ext pub: xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8NqtwybGhePY2gZ29ESFjqJoCu1Rupje8YtGqsefD265TMg7usUDFdp6W1EGMcet8
* ext prv: xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6LnF5kejMRNNU3TGtRBeJgk33yuGBxrMPHi
* [Chain m/0']
* ext pub: xpub68Gmy5EdvgibQVfPdqkBBCHxA5htiqg55crXYuXoQRKfDBFA1WEjWgP6LHhwBZeNK1VTsfTFUHCdrfp1bgwQ9xv5ski8PX9rL2dZXvgGDnw
* ext prv: xprv9uHRZZhk6KAJC1avXpDAp4MDc3sQKNxDiPvvkX8Br5ngLNv1TxvUxt4cV1rGL5hj6KCesnDYUhd7oWgT11eZG7XnxHrnYeSvkzY7d2bhkJ7
* [Chain m/0'/1]
* ext pub: xpub6ASuArnXKPbfEwhqN6e3mwBcDTgzisQN1wXN9BJcM47sSikHjJf3UFHKkNAWbWMiGj7Wf5uMash7SyYq527Hqck2AxYysAA7xmALppuCkwQ
* ext prv: xprv9wTYmMFdV23N2TdNG573QoEsfRrWKQgWeibmLntzniatZvR9BmLnvSxqu53Kw1UmYPxLgboyZQaXwTCg8MSY3H2EU4pWcQDnRnrVA1xe8fs
* [Chain m/0'/1/2']
* ext pub: xpub6D4BDPcP2GT577Vvch3R8wDkScZWzQzMMUm3PWbmWvVJrZwQY4VUNgqFJPMM3No2dFDFGTsxxpG5uJh7n7epu4trkrX7x7DogT5Uv6fcLW5
* ext prv: xprv9z4pot5VBttmtdRTWfWQmoH1taj2axGVzFqSb8C9xaxKymcFzXBDptWmT7FwuEzG3ryjH4ktypQSAewRiNMjANTtpgP4mLTj34bhnZX7UiM
* [Chain m/0'/1/2'/2]
* ext pub: xpub6FHa3pjLCk84BayeJxFW2SP4XRrFd1JYnxeLeU8EqN3vDfZmbqBqaGJAyiLjTAwm6ZLRQUMv1ZACTj37sR62cfN7fe5JnJ7dh8zL4fiyLHV
* ext prv: xprvA2JDeKCSNNZky6uBCviVfJSKyQ1mDYahRjijr5idH2WwLsEd4Hsb2Tyh8RfQMuPh7f7RtyzTtdrbdqqsunu5Mm3wDvUAKRHSC34sJ7in334
* [Chain m/0'/1/2'/2/1000000000]
* ext pub: xpub6H1LXWLaKsWFhvm6RVpEL9P4KfRZSW7abD2ttkWP3SSQvnyA8FSVqNTEcYFgJS2UaFcxupHiYkro49S8yGasTvXEYBVPamhGW6cFJodrTHy
* ext prv: xprvA41z7zogVVwxVSgdKUHDy1SKmdb533PjDz7J6N6mV6uS3ze1ai8FHa8kmHScGpWmj4WggLyQjgPie1rFSruoUihUZREPSL39UNdE3BBDu76

Test vector 2

Master (hex): fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8a8784817e7b7875726f6c696663605d5a5754514e4b484542
* [Chain m]
* ext pub: xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB
* ext prv: xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U
* [Chain m/0]
* ext pub: xpub69H7F5d8KSRgmmdJg2KhpAK8SR3DjMwAdkxj3ZuxV27CprR9LgpeyGmXUbC6wb7ERfvrnKZjXoUmmDznezpbZb7ap6r1D3tgFxHmwMkQTPH
* ext prv: xprv9vHkqa6EV4sPZHYqZznhT2NPtPCjKuDKGY38FBWLvgaDx45zo9WQRUT3dKYnjwih2yJD9mkrocEZXo1ex8G81dwSM1fwqWpWkeS3v86pgKt
* [Chain m/0/2147483647']
* ext pub: xpub6ASAVgeehLbnwdqV6UKMHVzgqAG8Gr6riv3Fxxpj8ksbH9ebxaEyBLZ85ySDhKiLDBrQSARLq1uNRts8RuJiHjaDMBU4Zn9h8LZNnBC5y4a
* ext prv: xprv9wSp6B7kry3Vj9m1zSnLvN3xH8RdsPP1Mh7fAaR7aRLcQMKTR2vidYEeEg2mUCTAwCd6vnxVrcjfy2kRgVsFawNzmjuHc2YmYRmagcEPdU9
* [Chain m/0/2147483647'/1]
* ext pub: xpub6DF8uhdarytz3FWdA8TvFSvvAh8dP3283MY7p2V4SeE2wyWmG5mg5EwVvmdMVCQcoNJxGoWaU9DCWh89LojfZ537wTfunKau47EL2dhHKon
* ext prv: xprv9zFnWC6h2cLgpmSA46vutJzBcfJ8yaJGg8cX1e5StJh45BBciYTRXSd25UEPVuesF9yog62tGAQtHjXajPPdbRCHuWS6T8XA2ECKADdw4Ef
* [Chain m/0/2147483647'/1/2147483646']
* ext pub: xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL
* ext prv: xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc
* [Chain m/0/2147483647'/1/2147483646'/2]
* ext pub: xpub6FnCn6nSzZAw5Tw7cgR9bi15UV96gLZhjDstkXXxvCLsUXBGXPdSnLFbdpq8p9HmGsApME5hQTZ3emM2rnY5agb9rXpVGyy3bdW6EEgAtqt
* ext prv: xprvA2nrNbFZABcdryreWet9Ea4LvTJcGsqrMzxHx98MMrotbir7yrKCEXw7nadnHM8Dq38EGfSh6dqA9QWTyefMLEcBYJUuekgW4BYPJcr9E7j

==Implementations==

A Python implementation is available at https://github.com/richardkiss/pycoin

A Java implementation is available at https://github.com/bitsofproof/supernode/blob/1.1/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java

A C++ implementation is available at https://github.com/CodeShark/CoinClasses/tree/master/tests/hdwallets

A Ruby implementation is available at https://github.com/wink/money-tree

==Acknowledgements==

* Gregory Maxwell for the original idea of type-2 deterministic wallets, and many discussions about it.
* Alan Reiner for the implementation of this scheme in Armory, and the suggestions that followed from that.
* Mike Caldwell for the version bytes to obtain human-recognizable Base58 strings.

Merged mining specification

2013-06-07T18:09:51Z

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

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 <tt>prev_block</tt> 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 <tt>getworkaux</tt> RPC method on the parent blockchain client (<tt>bitcoind</tt>) and then the work is then submitted by passing it to the auxiliary chain client (<tt>namecoind</tt>) as the second parameter to <tt>getauxblock</tt>.

When receiving an Aux proof-of-work block in a [[Protocol specification#block|"<tt>block</tt>" network message]], the data received is similar to a standard block, but extra data is inserted between the <tt>nonce</tt> and <tt>txn_count</tt> elements. In the below table, the shaded rows are the same as the standard block definition:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|- style="background-color:#DDD; color:#999;"
| 4 || version || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 32 || prev_block || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 32 || merkle_root || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 4 || timestamp || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || bits || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || nonce || uint32_t ||
|-
| ? || 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 <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>
|-
| ? || blockchain_branch || [[#Merkle 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 || [[Protocol specification#block|Block header]] || Parent block header
|- style="background-color:#DDD; color:#999;"
| ? || txn_count || var_int ||
|- style="background-color:#DDD; color:#999;"
| ? || txns || tx[] ||
|}

For the <tt>coinbase_branch</tt> 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 [[#Merkle Branch|below]]), the <tt>branch_side_mask</tt> 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 <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 ==
Say Alice created a Merkle tree, and it's root element is publicly available. For example:

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

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:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || branch_length || [[Protocol_specification#Variable_length_integer|var_int]] || The number of hashes making up the branch
|-
| ? || 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.
|}

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.

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

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 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
|-
| 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:

<pre>unsigned int rand = merkle_nonce;
rand = rand * 1103515245 + 12345;
rand += chain_id;
rand = rand * 1103515245 + 12345;
slot_num = rand % merkle_size</pre>

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 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 [http://explorer.dot-bit.org/b/19200 height 19200] in the Namecoin chain (the first block that allowed AuxPOW authentication). It has a hash of <tt>d8a7c3e01e1e95bcee015e6fcc7583a2ca60b79e5a3aa0a171eddd344ada903d</tt>, 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:
<pre>
0000000000003d47277359fb969c43e3c7e7c0306a17f6444b8e91e19def03a9 -- parent block hash
000000000000b269000000000000000000000000000000000000000000000000 -- Namecoin difficulty target
00000000000009ee5d0000000000000000000000000000000000000000000000 -- Bitcoin difficulty target
</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 <tt>previous_block</tt> hash used)

<pre>
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

Parent Block 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 Header:
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
</pre>

==Notes==
<references />

Merged mining specification

2013-06-04T19:37:40Z

MidnightLightning: /* Merged mining coinbase */

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 <tt>prev_block</tt> 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 <tt>getworkaux</tt> RPC method on the parent blockchain client (<tt>bitcoind</tt>) and then the work is then submitted by passing it to the auxiliary chain client (<tt>namecoind</tt>) as the second parameter to <tt>getauxblock</tt>.

When receiving an Aux proof-of-work block in a [[Protocol specification#block|"<tt>block</tt>" network message]], the data received is similar to a standard block, but extra data is inserted between the <tt>nonce</tt> and <tt>txn_count</tt> elements. In the below table, the shaded rows are the same as the standard block definition:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|- style="background-color:#DDD; color:#999;"
| 4 || version || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 32 || prev_block || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 32 || merkle_root || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 4 || timestamp || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || bits || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || nonce || uint32_t ||
|-
| ? || 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
|-
| ? || coinbase_branch || [[#Merkle Branch|Merkle branch]] || The merkle branch linking the <tt>coinbase_txn</tt> to the parent block's <tt>merkle_root</tt>
|-
| ? || blockchain_branch || [[#Merkle 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 || [[Protocol specification#block|Block header]] || Parent block header
|- style="background-color:#DDD; color:#999;"
| ? || txn_count || var_int ||
|- style="background-color:#DDD; color:#999;"
| ? || txns || tx[] ||
|}

For the <tt>coinbase_branch</tt> 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 [[#Merkle Branch|below]]), the <tt>branch_side_mask</tt> 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 <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).

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

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

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:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || branch_length || [[Protocol_specification#Variable_length_integer|var_int]] || The number of hashes making up the branch
|-
| ? || 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.
|}

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.

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

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| 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
|-
| 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:

<pre>unsigned int rand = merkle_nonce;
rand = rand * 1103515245 + 12345;
rand += chain_id;
rand = rand * 1103515245 + 12345;
slot_num = rand % merkle_size</pre>

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 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 [http://explorer.dot-bit.org/b/19200 height 19200] in the Namecoin chain (the first block that allowed AuxPOW authentication). It has a hash of <tt>d8a7c3e01e1e95bcee015e6fcc7583a2ca60b79e5a3aa0a171eddd344ada903d</tt>, 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:
<pre>
0000000000003d47277359fb969c43e3c7e7c0306a17f6444b8e91e19def03a9 -- parent block hash
000000000000b269000000000000000000000000000000000000000000000000 -- Namecoin difficulty target
00000000000009ee5d0000000000000000000000000000000000000000000000 -- Bitcoin difficulty target
</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 <tt>previous_block</tt> hash used)

<pre>
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

Parent Block 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 Header:
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
</pre>

==Notes==
<references />

Merged mining specification

2013-05-23T20:45:00Z

MidnightLightning: /* Example */

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 <tt>prev_block</tt> 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 <tt>getworkaux</tt> RPC method on the parent blockchain client (<tt>bitcoind</tt>) and then the work is then submitted by passing it to the auxiliary chain client (<tt>namecoind</tt>) as the second parameter to <tt>getauxblock</tt>.

When receiving an Aux proof-of-work block in a [[Protocol specification#block|"<tt>block</tt>" network message]], the data received is similar to a standard block, but extra data is inserted between the <tt>nonce</tt> and <tt>txn_count</tt> elements. In the below table, the shaded rows are the same as the standard block definition:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|- style="background-color:#DDD; color:#999;"
| 4 || version || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 32 || prev_block || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 32 || merkle_root || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 4 || timestamp || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || bits || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || nonce || uint32_t ||
|-
| ? || 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
|-
| ? || coinbase_branch || [[#Merkle Branch|Merkle branch]] || The merkle branch linking the <tt>coinbase_txn</tt> to the parent block's <tt>merkle_root</tt>
|-
| ? || blockchain_branch || [[#Merkle 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 || [[Protocol specification#block|Block header]] || Parent block header
|- style="background-color:#DDD; color:#999;"
| ? || txn_count || var_int ||
|- style="background-color:#DDD; color:#999;"
| ? || txns || tx[] ||
|}

For the <tt>coinbase_branch</tt> 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 [[#Merkle Branch|below]]), the <tt>branch_side_mask</tt> 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 <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).

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

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

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:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || branch_length || [[Protocol_specification#Variable_length_integer|var_int]] || The number of hashes making up the branch
|-
| ? || 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.
|}

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.

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

{|class="wikitable"
! 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)'''
|-
| 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:

<pre>unsigned int rand = merkle_nonce;
rand = rand * 1103515245 + 12345;
rand += chain_id;
rand = rand * 1103515245 + 12345;
slot_num = rand % merkle_size</pre>

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 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 [http://explorer.dot-bit.org/b/19200 height 19200] in the Namecoin chain (the first block that allowed AuxPOW authentication). It has a hash of <tt>d8a7c3e01e1e95bcee015e6fcc7583a2ca60b79e5a3aa0a171eddd344ada903d</tt>, 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:
<pre>
0000000000003d47277359fb969c43e3c7e7c0306a17f6444b8e91e19def03a9 -- parent block hash
000000000000b269000000000000000000000000000000000000000000000000 -- Namecoin difficulty target
00000000000009ee5d0000000000000000000000000000000000000000000000 -- Bitcoin difficulty target
</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 <tt>previous_block</tt> hash used)

<pre>
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

Parent Block 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 Header:
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
</pre>

==Notes==
<references />

Merged mining specification

2013-05-23T20:44:18Z

MidnightLightning: /* Example */

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 <tt>prev_block</tt> 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 <tt>getworkaux</tt> RPC method on the parent blockchain client (<tt>bitcoind</tt>) and then the work is then submitted by passing it to the auxiliary chain client (<tt>namecoind</tt>) as the second parameter to <tt>getauxblock</tt>.

When receiving an Aux proof-of-work block in a [[Protocol specification#block|"<tt>block</tt>" network message]], the data received is similar to a standard block, but extra data is inserted between the <tt>nonce</tt> and <tt>txn_count</tt> elements. In the below table, the shaded rows are the same as the standard block definition:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|- style="background-color:#DDD; color:#999;"
| 4 || version || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 32 || prev_block || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 32 || merkle_root || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 4 || timestamp || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || bits || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || nonce || uint32_t ||
|-
| ? || 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
|-
| ? || coinbase_branch || [[#Merkle Branch|Merkle branch]] || The merkle branch linking the <tt>coinbase_txn</tt> to the parent block's <tt>merkle_root</tt>
|-
| ? || blockchain_branch || [[#Merkle 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 || [[Protocol specification#block|Block header]] || Parent block header
|- style="background-color:#DDD; color:#999;"
| ? || txn_count || var_int ||
|- style="background-color:#DDD; color:#999;"
| ? || txns || tx[] ||
|}

For the <tt>coinbase_branch</tt> 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 [[#Merkle Branch|below]]), the <tt>branch_side_mask</tt> 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 <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).

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

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

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:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || branch_length || [[Protocol_specification#Variable_length_integer|var_int]] || The number of hashes making up the branch
|-
| ? || 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.
|}

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.

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

{|class="wikitable"
! 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)'''
|-
| 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:

<pre>unsigned int rand = merkle_nonce;
rand = rand * 1103515245 + 12345;
rand += chain_id;
rand = rand * 1103515245 + 12345;
slot_num = rand % merkle_size</pre>

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 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 [http://explorer.dot-bit.org/b/19200 height 19200] in the Namecoin chain (the first block that allowed AuxPOW authentication). It has a hash of <tt>d8a7c3e01e1e95bcee015e6fcc7583a2ca60b79e5a3aa0a171eddd344ada903d</tt>, 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:
<pre>
0000000000003d47277359fb969c43e3c7e7c0306a17f6444b8e91e19def03a9 -- parent block hash
000000000000b269000000000000000000000000000000000000000000000000 -- Namecoin difficulty target
00000000000009ee5d0000000000000000000000000000000000000000000000 -- Bitcoin difficulty target
</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 <tt>previous_block</tt> hash used)

<pre>
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
</pre>

==Notes==
<references />

Merged mining specification

2013-05-23T20:43:04Z

MidnightLightning: /* Merged mining coinbase */

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 <tt>prev_block</tt> 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 <tt>getworkaux</tt> RPC method on the parent blockchain client (<tt>bitcoind</tt>) and then the work is then submitted by passing it to the auxiliary chain client (<tt>namecoind</tt>) as the second parameter to <tt>getauxblock</tt>.

When receiving an Aux proof-of-work block in a [[Protocol specification#block|"<tt>block</tt>" network message]], the data received is similar to a standard block, but extra data is inserted between the <tt>nonce</tt> and <tt>txn_count</tt> elements. In the below table, the shaded rows are the same as the standard block definition:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|- style="background-color:#DDD; color:#999;"
| 4 || version || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 32 || prev_block || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 32 || merkle_root || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 4 || timestamp || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || bits || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || nonce || uint32_t ||
|-
| ? || 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
|-
| ? || coinbase_branch || [[#Merkle Branch|Merkle branch]] || The merkle branch linking the <tt>coinbase_txn</tt> to the parent block's <tt>merkle_root</tt>
|-
| ? || blockchain_branch || [[#Merkle 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 || [[Protocol specification#block|Block header]] || Parent block header
|- style="background-color:#DDD; color:#999;"
| ? || txn_count || var_int ||
|- style="background-color:#DDD; color:#999;"
| ? || txns || tx[] ||
|}

For the <tt>coinbase_branch</tt> 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 [[#Merkle Branch|below]]), the <tt>branch_side_mask</tt> 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 <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).

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

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

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:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || branch_length || [[Protocol_specification#Variable_length_integer|var_int]] || The number of hashes making up the branch
|-
| ? || 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.
|}

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.

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

{|class="wikitable"
! 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)'''
|-
| 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:

<pre>unsigned int rand = merkle_nonce;
rand = rand * 1103515245 + 12345;
rand += chain_id;
rand = rand * 1103515245 + 12345;
slot_num = rand % merkle_size</pre>

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 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 [http://explorer.dot-bit.org/b/19200 height 19200] in the Namecoin chain (the first block that allowed AuxPOW authentication). It has a hash of <tt>d8a7c3e01e1e95bcee015e6fcc7583a2ca60b79e5a3aa0a171eddd344ada903d</tt>, 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:
<pre>
0000000000003d47277359fb969c43e3c7e7c0306a17f6444b8e91e19def03a9 -- parent block hash
000000000000b269000000000000000000000000000000000000000000000000 -- Namecoin difficulty target
00000000000009ee5d0000000000000000000000000000000000000000000000 -- Bitcoin difficulty target
</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)

<pre>
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
</pre>

==Notes==
<references />

Merged mining specification

2013-05-23T20:39:57Z

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

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 <tt>prev_block</tt> 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 <tt>getworkaux</tt> RPC method on the parent blockchain client (<tt>bitcoind</tt>) and then the work is then submitted by passing it to the auxiliary chain client (<tt>namecoind</tt>) as the second parameter to <tt>getauxblock</tt>.

When receiving an Aux proof-of-work block in a [[Protocol specification#block|"<tt>block</tt>" network message]], the data received is similar to a standard block, but extra data is inserted between the <tt>nonce</tt> and <tt>txn_count</tt> elements. In the below table, the shaded rows are the same as the standard block definition:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|- style="background-color:#DDD; color:#999;"
| 4 || version || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 32 || prev_block || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 32 || merkle_root || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 4 || timestamp || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || bits || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || nonce || uint32_t ||
|-
| ? || 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
|-
| ? || coinbase_branch || [[#Merkle Branch|Merkle branch]] || The merkle branch linking the <tt>coinbase_txn</tt> to the parent block's <tt>merkle_root</tt>
|-
| ? || blockchain_branch || [[#Merkle 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 || [[Protocol specification#block|Block header]] || Parent block header
|- style="background-color:#DDD; color:#999;"
| ? || txn_count || var_int ||
|- style="background-color:#DDD; color:#999;"
| ? || txns || tx[] ||
|}

For the <tt>coinbase_branch</tt> 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 [[#Merkle Branch|below]]), the <tt>branch_side_mask</tt> 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 <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).

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

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

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:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || branch_length || [[Protocol_specification#Variable_length_integer|var_int]] || The number of hashes making up the branch
|-
| ? || 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.
|}

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.

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

{|class="wikitable"
! 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)'''
|-
| 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:

<pre>unsigned int rand = merkle_nonce;
rand = rand * 1103515245 + 12345;
rand += chain_id;
rand = rand * 1103515245 + 12345;
slot_num = rand % merkle_size</pre>

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 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 [http://explorer.dot-bit.org/b/19200 height 19200] in the Namecoin chain (the first block that allowed AuxPOW authentication). It has a hash of <tt>d8a7c3e01e1e95bcee015e6fcc7583a2ca60b79e5a3aa0a171eddd344ada903d</tt>, 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:
<pre>
0000000000003d47277359fb969c43e3c7e7c0306a17f6444b8e91e19def03a9 -- parent block hash
000000000000b269000000000000000000000000000000000000000000000000 -- Namecoin difficulty target
00000000000009ee5d0000000000000000000000000000000000000000000000 -- Bitcoin difficulty target
</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)

<pre>
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
</pre>

==Notes==
<references />

Merged mining specification

2013-05-23T20:32:54Z

MidnightLightning: /* Example */

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 <tt>prev_block</tt> 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 <tt>getworkaux</tt> RPC method on the parent blockchain client (<tt>bitcoind</tt>) and then the work is then submitted by passing it to the auxiliary chain client (<tt>namecoind</tt>) as the second parameter to <tt>getauxblock</tt>.

When receiving an Aux proof-of-work block in a [[Protocol specification#block|"<tt>block</tt>" network message]], the data received is similar to a standard block, but extra data is inserted between the <tt>nonce</tt> and <tt>txn_count</tt> elements. In the below table, the shaded rows are the same as the standard block definition:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|- style="background-color:#DDD; color:#999;"
| 4 || version || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 32 || prev_block || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 32 || merkle_root || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 4 || timestamp || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || bits || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || nonce || uint32_t ||
|-
| ? || coinbase_txn || [[Protocol specification#tx|txn]] || Coinbase transaction [[#Merged mining coinbase|linking]] the AuxPOW block to its parent block
|-
| 32 || block_hash || char[32] || Hash of the parent block 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>
|-
| ? || blockchain_branch || [[#Merkle 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 || [[Protocol specification#block|Block header]] || Parent block header
|- style="background-color:#DDD; color:#999;"
| ? || txn_count || var_int ||
|- style="background-color:#DDD; color:#999;"
| ? || txns || tx[] ||
|}

For the <tt>coinbase_branch</tt> 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 [[#Merkle Branch|below]]), the <tt>branch_side_mask</tt> 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 <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).

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

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

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:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || branch_length || [[Protocol_specification#Variable_length_integer|var_int]] || The number of hashes making up the branch
|-
| ? || 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.
|}

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.

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

{|class="wikitable"
! 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)'''
|-
| 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:

<pre>unsigned int rand = merkle_nonce;
rand = rand * 1103515245 + 12345;
rand += chain_id;
rand = rand * 1103515245 + 12345;
slot_num = rand % merkle_size</pre>

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 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 [http://explorer.dot-bit.org/b/19200 height 19200] in the Namecoin chain (the first block that allowed AuxPOW authentication). It has a hash of <tt>d8a7c3e01e1e95bcee015e6fcc7583a2ca60b79e5a3aa0a171eddd344ada903d</tt>, 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:
<pre>
0000000000003d47277359fb969c43e3c7e7c0306a17f6444b8e91e19def03a9 -- parent block hash
000000000000b269000000000000000000000000000000000000000000000000 -- Namecoin difficulty target
00000000000009ee5d0000000000000000000000000000000000000000000000 -- Bitcoin difficulty target
</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)

<pre>
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
</pre>

==Notes==
<references />

Merged mining specification

2013-05-23T20:29:53Z

MidnightLightning: /* Example */ Reformat to not be so tall

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 <tt>prev_block</tt> 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 <tt>getworkaux</tt> RPC method on the parent blockchain client (<tt>bitcoind</tt>) and then the work is then submitted by passing it to the auxiliary chain client (<tt>namecoind</tt>) as the second parameter to <tt>getauxblock</tt>.

When receiving an Aux proof-of-work block in a [[Protocol specification#block|"<tt>block</tt>" network message]], the data received is similar to a standard block, but extra data is inserted between the <tt>nonce</tt> and <tt>txn_count</tt> elements. In the below table, the shaded rows are the same as the standard block definition:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|- style="background-color:#DDD; color:#999;"
| 4 || version || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 32 || prev_block || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 32 || merkle_root || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 4 || timestamp || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || bits || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || nonce || uint32_t ||
|-
| ? || coinbase_txn || [[Protocol specification#tx|txn]] || Coinbase transaction [[#Merged mining coinbase|linking]] the AuxPOW block to its parent block
|-
| 32 || block_hash || char[32] || Hash of the parent block 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>
|-
| ? || blockchain_branch || [[#Merkle 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 || [[Protocol specification#block|Block header]] || Parent block header
|- style="background-color:#DDD; color:#999;"
| ? || txn_count || var_int ||
|- style="background-color:#DDD; color:#999;"
| ? || txns || tx[] ||
|}

For the <tt>coinbase_branch</tt> 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 [[#Merkle Branch|below]]), the <tt>branch_side_mask</tt> 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 <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).

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

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

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:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || branch_length || [[Protocol_specification#Variable_length_integer|var_int]] || The number of hashes making up the branch
|-
| ? || 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.
|}

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.

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

{|class="wikitable"
! 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)'''
|-
| 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:

<pre>unsigned int rand = merkle_nonce;
rand = rand * 1103515245 + 12345;
rand += chain_id;
rand = rand * 1103515245 + 12345;
slot_num = rand % merkle_size</pre>

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 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 [http://explorer.dot-bit.org/b/19200 height 19200] in the Namecoin chain (the first block that allowed AuxPOW authentication). It has a hash of <tt>d8a7c3e01e1e95bcee015e6fcc7583a2ca60b79e5a3aa0a171eddd344ada903d</tt>, 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:
<pre>
0000000000003d47277359fb969c43e3c7e7c0306a17f6444b8e91e19def03a9 -- parent block hash
000000000000b269000000000000000000000000000000000000000000000000 -- Namecoin difficulty target
00000000000009ee5d0000000000000000000000000000000000000000000000 -- Bitcoin difficulty target
</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>)

<pre>
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
</pre>

==Notes==
<references />

Merged mining specification

2013-05-23T20:21:29Z

MidnightLightning: Add example block

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 <tt>prev_block</tt> 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 <tt>getworkaux</tt> RPC method on the parent blockchain client (<tt>bitcoind</tt>) and then the work is then submitted by passing it to the auxiliary chain client (<tt>namecoind</tt>) as the second parameter to <tt>getauxblock</tt>.

When receiving an Aux proof-of-work block in a [[Protocol specification#block|"<tt>block</tt>" network message]], the data received is similar to a standard block, but extra data is inserted between the <tt>nonce</tt> and <tt>txn_count</tt> elements. In the below table, the shaded rows are the same as the standard block definition:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|- style="background-color:#DDD; color:#999;"
| 4 || version || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 32 || prev_block || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 32 || merkle_root || char[32] ||
|- style="background-color:#DDD; color:#999;"
| 4 || timestamp || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || bits || uint32_t ||
|- style="background-color:#DDD; color:#999;"
| 4 || nonce || uint32_t ||
|-
| ? || coinbase_txn || [[Protocol specification#tx|txn]] || Coinbase transaction [[#Merged mining coinbase|linking]] the AuxPOW block to its parent block
|-
| 32 || block_hash || char[32] || Hash of the parent block 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>
|-
| ? || blockchain_branch || [[#Merkle 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 || [[Protocol specification#block|Block header]] || Parent block header
|- style="background-color:#DDD; color:#999;"
| ? || txn_count || var_int ||
|- style="background-color:#DDD; color:#999;"
| ? || txns || tx[] ||
|}

For the <tt>coinbase_branch</tt> 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 [[#Merkle Branch|below]]), the <tt>branch_side_mask</tt> 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 <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).

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

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

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:

{|class="wikitable"
! Field Size !! Description !! Data type !! Comments
|-
| ? || branch_length || [[Protocol_specification#Variable_length_integer|var_int]] || The number of hashes making up the branch
|-
| ? || 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.
|}

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.

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

{|class="wikitable"
! 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)'''
|-
| 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:

<pre>unsigned int rand = merkle_nonce;
rand = rand * 1103515245 + 12345;
rand += chain_id;
rand = rand * 1103515245 + 12345;
slot_num = rand % merkle_size</pre>

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 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 [http://explorer.dot-bit.org/b/19200 height 19200] in the Namecoin chain (the first block that allowed AuxPOW authentication). It has a hash of <tt>d8a7c3e01e1e95bcee015e6fcc7583a2ca60b79e5a3aa0a171eddd344ada903d</tt>, 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:
<pre>
0000000000003d47277359fb969c43e3c7e7c0306a17f6444b8e91e19def03a9 -- parent block hash
000000000000b269000000000000000000000000000000000000000000000000 -- Namecoin difficulty target
00000000000009ee5d0000000000000000000000000000000000000000000000 -- Bitcoin difficulty target
</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>)

<pre>
Block Header:
01 01 01 00 // Version

36 90 9a c0 7a 16 73 da f6 5f a7 d8 28 88 2e 66 // Previous block hash
c9 e8 9f 85 46 cd d5 0a 9f b1 00 00 00 00 00 00

0f 5c 65 49 bc d6 08 ab 7c 4e ac 59 3e 5b d5 a7 // Merkle root
3b 2d 43 2e b6 35 18 70 8f 77 8f c7 dc df af 88

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 // Script
e0 1e 1e 95 bc ee 01 5e 6f cc 75 83 a2 ca 60 b7
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 // Script
03 13 f9 18 f3 d3 c0 e8 47 50 55 e3 51 e3 bf 44
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 // Hash of parent block header
e3 43 9c 96 fb 59 73 27 47 3d 00 00 00 00 00 00

05 // Number of links in branch

05 0a c4 a1 a1 e1 bc e0 c4 8e 55 5b 1a 9f 93 52 // Hash #1
81 96 8c 72 d6 37 9b 24 72 9c a0 42 5a 3f c3 cb

43 3c d3 48 b3 5e a2 28 06 cf 21 c7 b1 46 48 9a // Hash #2
ef 69 89 55 1e b5 ad 23 73 ab 61 21 06 0f 30 34

1d 64 87 57 c0 21 7d 43 e6 6c 57 ea ed 64 fc 18 // Hash #3
20 ec 65 d1 57 f3 3b 74 19 65 18 3a 5e 0c 85 06

ac 26 02 df e2 f5 47 01 2d 1c c7 50 04 d4 8f 97 // Hash #4
ab a4 6b d9 93 0f f2 85 c9 f2 76 f5 bd 09 f3 56

df 19 72 45 79 d6 5e c7 cb 62 bf 97 94 6d fc 6f // Hash #5
b0 e3 b2 83 9b 7f da b3 7c db 60 e5 51 22 d3 5b

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 // Previous block hash
78 b9 01 4e 5c eb 7d 9b a5 04 00 00 00 00 00 00

e0 fd 42 db 8e f6 d7 83 f0 79 d1 26 be a1 2e 2d // Merkle root
10 c1 04 c0 92 7c d6 8f 95 4d 85 6f 9e 81 11 e5

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 // Script
5f df f1 7a 3a 87 0e bb 05 82 0b 41 4f 3d 80 97
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
</pre>

==Notes==
<references />

BIP 0021

2013-05-23T18:45:40Z

MidnightLightning: /* Appendix */

{{bip}}

<pre>
BIP: 21
Title: URI Scheme
Author: Nils Schneider <nils.schneider@gmail.com>
Matt Corallo <bip21@bluematt.me>
Status: Accepted
Type: Standards Track
Created: 29-01-2012
</pre>

This BIP is a modification of an earlier [[BIP 0020]] by Luke Dashjr. BIP 0020 was based off an earlier document by Nils Schneider. The alternative payment amounts in BIP 0020 have been removed.

==Abstract==
This BIP proposes a URI scheme for making Bitcoin payments.

==Motivation==
The purpose of this URI scheme is to enable users to easily make payments by simply clicking links on webpages or scanning QR Codes.

==Specification==

=== General rules for handling (important!) ===

Bitcoin clients MUST NOT act on URIs without getting the user's authorization.
They SHOULD require the user to manually approve each payment individually, though in some cases they MAY allow the user to automatically make this decision.

=== Operating system integration ===
Graphical bitcoin clients SHOULD register themselves as the handler for the "bitcoin:" URI scheme by default, if no other handler is already registered. If there is already a registered handler, they MAY prompt the user to change it once when they first run the client.

=== BNF grammar ===

(See also [[#Simpler syntax|a simpler representation of syntax]])

bitcoinurn = "bitcoin:" bitcoinaddress [ "?" bitcoinparams ]
bitcoinaddress = base58 *base58
bitcoinparams = *bitcoinparam
bitcoinparam = amountparam | labelparam | messageparam | otherparam | reqparam
amountparam = "amount=" *digit [ "." *digit ]
labelparam = "label=" *pchar
messageparam = "message=" *pchar
otherparam = pchar *pchar "=" *pchar
reqparam = "req-" pchar *pchar "=" *pchar

=== Query Keys ===

*label: Label for that address (e.g. name of receiver)
*address: bitcoin address
*message: message that describes the transaction to the user ([[#Examples|see examples below]])
*size: amount of base bitcoin units ([[#Transfer amount/size|see below]])
*(others): optional, for future extensions

==== Transfer amount/size ====

If an amount is provided, it MUST be specified in decimal BTC.
All amounts MUST contain no commas and use a period (.) as the separating character to separate whole numbers and decimal fractions.
I.e. amount=50.00 or amount=50 is treated as 50 BTC, and amount=50,000.00 is invalid.

Bitcoin clients MAY display the amount in any format that is not intended to deceive the user.
They SHOULD choose a format that is foremost least confusing, and only after that most reasonable given the amount requested.
For example, so long as the majority of users work in BTC units, values should always be displayed in BTC by default, even if mBTC or TBC would otherwise be a more logical interpretation of the amount.
== Rationale ==

===Payment identifiers, not person identifiers===
Current best practices are that a unique address should be used for every transaction.
Therefore, a URI scheme should not represent an exchange of personal information, but a one-time payment.

===Accessibility (URI scheme name)===
Should someone from the outside happen to see such a URI, the URI scheme name already gives a description.
A quick search should then do the rest to help them find the resources needed to make their payment.
Other proposed names sound much more cryptic; the chance that someone googles that out of curiosity are much slimmer.
Also, very likely, what he will find are mostly technical specifications - not the best introduction to bitcoin.

==Forward compatibility==
Variables which are prefixed with a req- are considered required. If a client does not implement any variables which are prefixed with req-, it MUST consider the entire URI invalid. Any other variables which are not implemented, but which are not prefixed with a req-, can be safely ignored.

==Backward compatibility==
As this BIP is written, several clients already implement a bitcoin: URI scheme similar to this one, however usually without the additional "req-" prefix requirement. Thus, it is recommended that additional variables prefixed with req- not be used in a mission-critical way until a grace period of 6 months from the finalization of this BIP has passed in order to allow client developers to release new versions, and users of old clients to upgrade.

== Appendix ==

=== Simpler syntax ===

This section is non-normative and does not cover all possible syntax.
Please see the [[#BNF grammar|BNF grammar]] above for the normative syntax.

[foo] means optional, <bar> are placeholders

<nowiki>bitcoin:<address>[?amount=<amount>][?label=<label>][?message=<message>]</nowiki>

=== Examples ===

Just the address:
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W

Address with name:
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?label=Luke-Jr

Request 20.30 BTC to "Luke-Jr":
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?amount=20.3&label=Luke-Jr

Request 50 BTC with message:
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?amount=50&label=Luke-Jr&message=Donation%20for%20project%20xyz

Some future version that has variables which are (currently) not understood and required and thus invalid:
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?req-somethingyoudontunderstand=50&req-somethingelseyoudontget=999

Some future version that has variables which are (currently) not understood but not required and thus valid:
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?somethingyoudontunderstand=50&somethingelseyoudontget=999

Characters must be URI encoded properly.

== Reference Implementations ==
=== Bitcoin clients ===
* [[Bitcoin-Qt]] supports the old version of Bitcoin URIs (ie without the req- prefix), with Windows and KDE integration as of commit 70f55355e29c8e45b607e782c5d76609d23cc858.

[[Category:Developer]]
[[Category:Technical]]
[[Category:BIP|D]]

Merged mining specification

2013-05-23T18:43:15Z

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

Merged mining specification

2013-05-23T18:42:22Z

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

Merged mining specification

2013-05-23T18:41:55Z

MidnightLightning: /* Aux proof-of-work */ Show the standard block elements as well, for context

Merged mining specification

2013-05-23T18:35:44Z

MidnightLightning: /* Terminology */

Merged mining specification

2013-05-23T18:34:14Z

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

Merged mining specification

2013-05-23T18:33:38Z

MidnightLightning: /* Merkle Branch */

Merged mining specification

2013-05-23T18:31:07Z

MidnightLightning: Better explain a Merkle Branch and how it's used in this context

Merged mining specification

2013-05-22T22:19:41Z

MidnightLightning: Updating with more technical information based on my dissection of vinced's source