BIP 0037 - Revision history

934: Update BIP text with latest version from https://github.com/bitcoin/bips/blob/b5723035e23896d0/bip-0037.mediawiki

2019-09-24T18:00:24Z

Update BIP text with latest version from https://github.com/bitcoin/bips/blob/b5723035e23896d0/bip-0037.mediawiki

Belcher: Add link to BIP37 privacy problems page

2019-02-15T20:33:18Z

Add link to BIP37 privacy problems page

← Older revision		Revision as of 20:33, 15 February 2019
Line 11:		Line 11:

	{{BipMoved\|bip-0037.mediawiki}}		{{BipMoved\|bip-0037.mediawiki}}

			== See Also ==
			* [[BIP37 privacy problems]]

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

934: Removing redundant parameter.

2015-12-29T13:46:19Z

Removing redundant parameter.

← Older revision		Revision as of 13:46, 29 December 2015
Line 10:		Line 10:
	</pre>		</pre>

	{{BipMoved\|bip-0037.mediawiki~~\|BIP 0037~~}}		{{BipMoved\|bip-0037.mediawiki}}

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

Wumpus: Github move

2013-12-06T08:03:30Z

Github move

Show changes

Mike: Update to the latest version of the protocol.

2013-02-20T12:43:46Z

Update to the latest version of the protocol.

← Older revision		Revision as of 12:43, 20 February 2013
Line 5:		Line 5:
	Title: Connection Bloom filtering		Title: Connection Bloom filtering
	Author: Mike Hearn <hearn@google.com>, Matt Corallo <bip@bluematt.me>		Author: Mike Hearn <hearn@google.com>, Matt Corallo <bip@bluematt.me>
	Status: ~~Draft~~		Status: Accepted
	Type: Standards Track		Type: Standards Track
	Created: 24-10-2012		Created: 24-10-2012
Line 51:		Line 51:
	\|-		\|-
	\| 4 \|\| nTweak \|\| uint32_t \|\| A random value to add to the seed value in the hash function used by the bloom filter.		\| 4 \|\| nTweak \|\| uint32_t \|\| A random value to add to the seed value in the hash function used by the bloom filter.
			\|-
			\| 1 \|\| nFlags \|\| uint8_t \|\| A set of flags that control how matched items are added to the filter.
	\|}		\|}

	See below for a description of the Bloom filter algorithm and how to select nHashFuncs and filter size for a desired false positive rate.		See below for a description of the Bloom filter algorithm and how to select nHashFuncs and filter size for a desired false positive rate.

	Upon receiving a <code>filterload</code> command, the remote peer will immediately restrict the broadcast transactions it announces (in inv packets) to transactions matching the filter, where the matching algorithm is specified below.		Upon receiving a <code>filterload</code> command, the remote peer will immediately restrict the broadcast transactions it announces (in inv packets) to transactions matching the filter, where the matching algorithm is specified below. The flags control the update behaviour of the matching algorithm.

	The <code>filteradd</code> command is defined as follows:		The <code>filteradd</code> command is defined as follows:
Line 111:		Line 113:
	SPV clients that wish to use Bloom filtering would normally set fRelay to false in the version message, then set a filter based on their wallet (or a subset of it, if they are overlapping different peers). Being able to opt-out of inv messages until the filter is set prevents a client being flooded with traffic in the brief window of time between finishing version handshaking and setting the filter.		SPV clients that wish to use Bloom filtering would normally set fRelay to false in the version message, then set a filter based on their wallet (or a subset of it, if they are overlapping different peers). Being able to opt-out of inv messages until the filter is set prevents a client being flooded with traffic in the brief window of time between finishing version handshaking and setting the filter.

	The <code>getdata</code> command is extended to allow a new type in the <code>inv</code> submessage. The type field can now be <code>MSG_FILTERED_BLOCK (== 3)</code> rather than <code>MSG_BLOCK</code>. If no filter has been set on the connection, a request for filtered blocks is ignored. If a filter has been set, a <code>merkleblock</code> message is returned for the requested block hash. In addition, because a <code>merkleblock</code> message contains only a list of transaction hashes, transactions matching the filter should also be sent in separate tx messages. This avoids a slow roundtrip that would otherwise be required (receive hashes, didn't see some of these transactions yet, ask for them). Note that because there is currently no way to request transactions which are already in a block from a node (aside from requesting the full block), the set of matching transactions that the requesting node hasn't either received or announced with an inv must be sent and any additional transactions which match the filter may also be sent. This allows for clients (such as the reference client) to limit the number of invs it must remember a given node to have announced while still providing nodes with, at a minimum, all the transactions it needs.		The <code>getdata</code> command is extended to allow a new type in the <code>inv</code> submessage. The type field can now be <code>MSG_FILTERED_BLOCK (== 3)</code> rather than <code>MSG_BLOCK</code>. If no filter has been set on the connection, a request for filtered blocks is ignored. If a filter has been set, a <code>merkleblock</code> message is returned for the requested block hash. In addition, because a <code>merkleblock</code> message contains only a list of transaction hashes, transactions matching the filter should also be sent in separate tx messages after the merkleblock is sent. This avoids a slow roundtrip that would otherwise be required (receive hashes, didn't see some of these transactions yet, ask for them). Note that because there is currently no way to request transactions which are already in a block from a node (aside from requesting the full block), the set of matching transactions that the requesting node hasn't either received or announced with an inv must be sent and any additional transactions which match the filter may also be sent. This allows for clients (such as the reference client) to limit the number of invs it must remember a given node to have announced while still providing nodes with, at a minimum, all the transactions it needs.

	===Filter matching algorithm===		===Filter matching algorithm===
Line 117:		Line 119:
	The filter can be tested against arbitrary pieces of data, to see if that data was inserted by the client. Therefore the question arises of what pieces of data should be inserted/tested.		The filter can be tested against arbitrary pieces of data, to see if that data was inserted by the client. Therefore the question arises of what pieces of data should be inserted/tested.

	To determine if a transaction matches the filter, the following algorithm ~~MUST be~~ used. Once a match is found the algorithm aborts.		To determine if a transaction matches the filter, the following algorithm is used. Once a match is found the algorithm aborts.

	# Test the hash of the transaction itself.		# Test the hash of the transaction itself.
	# For each output, test each data element of the output script. This means each hash and key in the output script is tested independently. '''Important:''' if an output matches whilst testing a transaction, the node ~~MUST~~ update the filter by inserting the serialized COutPoint structure. See below for more details.		# For each output, test each data element of the output script. This means each hash and key in the output script is tested independently. '''Important:''' if an output matches whilst testing a transaction, the node might need to update the filter by inserting the serialized COutPoint structure. See below for more details.
	# For each input, test the serialized COutPoint structure.		# For each input, test the serialized COutPoint structure.
	# For each input, test each data element of the input script (note: input scripts only ever contain data elements).		# For each input, test each data element of the input script (note: input scripts only ever contain data elements).
Line 134:		Line 136:

	By updating the bloom filter atomically in step 2 with the discovered outpoint, the filter will match against TX 2 in step 3 and the client will learn about all relevant transactions, despite that there is no pause between the node processing the first and second blocks.		By updating the bloom filter atomically in step 2 with the discovered outpoint, the filter will match against TX 2 in step 3 and the client will learn about all relevant transactions, despite that there is no pause between the node processing the first and second blocks.

			The nFlags field of the filter controls the nodes precise update behaviour and is a bit field.

			* <code>BLOOM_UPDATE_NONE (0)</code> means the filter is not adjusted when a match is found.
			* <code>BLOOM_UPDATE_ALL (1)</code> means if the filter matches any data element in a scriptPubKey the outpoint is serialized and inserted into the filter.
			* <code>BLOOM_UPDATE_P2PUBKEY_ONLY (2)</code> means the outpoint is inserted into the filter only if a data element in the scriptPubKey is matched, and that script is of the standard "pay to pubkey" or "pay to multisig" forms.

			These distinctions are useful to avoid too-rapid degradation of the filter due to an increasing false positive rate. We can observe that a wallet which expects to receive only payments of the standard pay-to-address form doesn't need automatic filter updates because any transaction that spends one of its own outputs has a predictable data element in the input (the pubkey that hashes to the address). If a wallet might receive pay-to-address outputs and also pay-to-pubkey or pay-to-multisig outputs then BLOOM_UPDATE_P2PUBKEY_ONLY is appropriate, as it avoids unnecessary expansions of the filter for the most common types of output but still ensures correct behaviour with payments that explicitly specify keys.

			Obviously, nFlags == 1 or nFlags == 2 mean that the filter will get dirtier as more of the chain is scanned. Clients should monitor the observed false positive rate and periodically refresh the filter with a clean one.

	===Partial Merkle branch format===		===Partial Merkle branch format===

BlueMatt: Tweak PMT description

2012-12-17T21:11:18Z

Tweak PMT description

← Older revision		Revision as of 21:11, 17 December 2012
Line 90:		Line 90:
	\| 4 \|\| total_transactions \|\| uint32_t \|\| Number of transactions in the block (including unmatched ones)		\| 4 \|\| total_transactions \|\| uint32_t \|\| Number of transactions in the block (including unmatched ones)
	\|-		\|-
	\| ? \|\| ~~number_of_hashes~~ \|\| ~~varint~~ \|\| ~~Number of~~ hashes		\| ? \|\| hashes \|\| uint256[] \|\| hashes in depth-first order (including standard varint size prefix)
	\|-		\|-
	~~\| ? \|\| hashes \|\| uint256[] \|\| hashes in depth-first order (<= 32*N bytes)~~		\| ? \|\| flags \|\| byte[] \|\| flag bits, packed per 8 in a byte, least significant bit first (including standard varint size prefix)
	\|-
	~~\| ? \|\| bytes_of_flags \|\| varint \|\| number of bytes of flag bits (1-3 bytes)~~
	\|-
	\| ? \|\| flags \|\| byte[] \|\| flag bits, packed per 8 in a byte, least significant bit first (~~<= 2*N-1 bits~~)
	\|}		\|}

BlueMatt: Add nTweak

2012-12-17T21:08:15Z

Add nTweak

← Older revision		Revision as of 21:08, 17 December 2012
Line 49:		Line 49:
	\|-		\|-
	\| 4 \|\| nHashFuncs \|\| uint32_t \|\| The number of hash functions to use in this filter. The maximum value allowed in this field is 50.		\| 4 \|\| nHashFuncs \|\| uint32_t \|\| The number of hash functions to use in this filter. The maximum value allowed in this field is 50.
			\|-
			\| 4 \|\| nTweak \|\| uint32_t \|\| A random value to add to the seed value in the hash function used by the bloom filter.
	\|}		\|}

Line 147:		Line 149:
	A Bloom filter is a bit-field in which bits are set based on feeding the data element to a set of different hash functions. The number of hash functions used is a parameter of the filter. In Bitcoin we use version 3 of the 32-bit Murmur hash function. To get N "different" hash functions we simply initialize the Murmur algorithm with the following formula:		A Bloom filter is a bit-field in which bits are set based on feeding the data element to a set of different hash functions. The number of hash functions used is a parameter of the filter. In Bitcoin we use version 3 of the 32-bit Murmur hash function. To get N "different" hash functions we simply initialize the Murmur algorithm with the following formula:

	<code>nHashNum * ~~(MAX_UINT32 / (nHashFuncs - 1))~~</code>		<code>nHashNum * 0xFBA4C795 + nTweak</code>

	i.e. if the filter is initialized with 4 hash functions, when the second function is needed h1 would be equal to ~~1431655765~~.		i.e. if the filter is initialized with 4 hash functions and a tweak of 0x00000005, when the second function (index 1) is needed h1 would be equal to 4221880218.

	When loading a filter with the <code>filterload</code> command, there are two parameters that can be chosen. One is the size of the filter in bytes. The other is the number of hash functions to use. To select the parameters you can use the following formulas:		When loading a filter with the <code>filterload</code> command, there are two parameters that can be chosen. One is the size of the filter in bytes. The other is the number of hash functions to use. To select the parameters you can use the following formulas:
Line 155:		Line 157:
	Let N be the number of elements you wish to insert into the set and P be the probability of a false positive, where 1.0 is "match everything" and zero is unachievable.		Let N be the number of elements you wish to insert into the set and P be the probability of a false positive, where 1.0 is "match everything" and zero is unachievable.

	The size S of the filter in bytes is given by <code>(-1 / pow(log(2), 2) * N * log(P)) / 8</code>. Of course you must ensure it does not go over the maximum size (36,000).		The size S of the filter in bytes is given by <code>(-1 / pow(log(2), 2) * N * log(P)) / 8</code>. Of course you must ensure it does not go over the maximum size (36,000: selected as it represents a filter of 20,000 items with false positive rate of < 0.1% or 10,000 items and a false positive rate of < 0.0001%).

	The number of hash functions required is given by <code>S * 8 / N * log(2)</code>.		The number of hash functions required is given by <code>S * 8 / N * log(2)</code>.

BlueMatt: re add


2012-12-17T20:59:39Z
re add <code>

				
				
				
				
				
				← Older revision
				Revision as of 20:59, 17 December 2012
				
Line 65:
Line 65:
The data field must be smaller than or equal to 520 bytes in size (the maximum size of any potentially matched object). The data field must be smaller than or equal to 520 bytes in size (the maximum size of any potentially matched object).



The given data element will be added to the Bloom filter. A filter must have been previously provided using filterload. This command is useful if a new key or script is added to a clients wallet whilst it has connections to the network open, it avoids the need to re-calculate and send an entirely new filter to every peer (though doing so is usually advisable to maintain anonymity). The given data element will be added to the Bloom filter. A filter must have been previously provided using <code>filterload</code>. This command is useful if a new key or script is added to a clients wallet whilst it has connections to the network open, it avoids the need to re-calculate and send an entirely new filter to every peer (though doing so is usually advisable to maintain anonymity).



The <code>filterclear</code> command has no arguments at all. The <code>filterclear</code> command has no arguments at all.



BlueMatt: Require a previous filter before filteradd
2012-12-17T20:56:22Z
Require a previous filter before filteradd

				
				
				
				
				
				← Older revision
				Revision as of 20:56, 17 December 2012
				
Line 65:
Line 65:
The data field must be smaller than or equal to 520 bytes in size (the maximum size of any potentially matched object). The data field must be smaller than or equal to 520 bytes in size (the maximum size of any potentially matched object).



The given data element will be added to the Bloom filter. If no filter has been previously provided using <code>filterload</code>, a new one will be initialized that would have a false positive rate of, at a minimum, 0.1% with 1000 inserted elements. This command is useful if a new key or script is added to a clients wallet whilst it has connections to the network open, it avoids the need to re-calculate and send an entirely new filter to every peer. The given data element will be added to the Bloom filter. A filter must have been previously provided using filterload. This command is useful if a new key or script is added to a clients wallet whilst it has connections to the network open, it avoids the need to re-calculate and send an entirely new filter to every peer (though doing so is usually advisable to maintain anonymity).



The <code>filterclear</code> command has no arguments at all. The <code>filterclear</code> command has no arguments at all.



BlueMatt: Update for PMT
2012-12-15T00:23:30Z
Update for PMT

				
				
				
				
				
				← Older revision
				Revision as of 00:23, 15 December 2012
				
Line 86:
Line 86:
| 4 || nonce || uint32_t || The nonce used to generate this block… to allow variations of the header and compute different hashes | 4 || nonce || uint32_t || The nonce used to generate this block… to allow variations of the header and compute different hashes
|- |-
| 1 || txn_count || uint32_t || Number of transactions that matched the filter | 4 || total_transactions || uint32_t || Number of transactions in the block (including unmatched ones)
|- |-
| ? || transactions || merkle_tx[] || A series of merkle_tx messages, defined below, for each transaction in the block that matched the filter. | ? || number_of_hashes || varint || Number of hashes
|} 
  
The <code>merkle_tx</code> message is defined below: 
  
{|class="wikitable" 
! Field Size !! Description !! Data type !! Comments 
|- |-
| 4 || index || uint32_t || The index in the original block that the transaction appeared at. | ? || hashes || uint256[] || hashes in depth-first order (<= 32*N bytes)
|- |-
| 32 || hash || uint256_t || The hash of the matching transaction. | ? || bytes_of_flags || varint || number of bytes of flag bits (1-3 bytes)
|- |-
| ? || merkle_branch || uint256_t[] || A vector of hashes defining the Merkle branch linking this transaction to the merkle root in the block header | ? || flags || byte[] || flag bits, packed per 8 in a byte, least significant bit first (<= 2*N-1 bits)
|} |}



See below for the format of the merkle branch. See below for the format of the partial merkle tree hashes and flags.



As you can see a <code>merkleblock</code> message is a block header, plus identifying information for transactions that matched the filter, plus the Merkle branch which can be used to prove that the matching transaction data really did appear in the solved block. Clients can use this data to be sure that the remote node is not feeding them fake transactions that never appeared in a real block, although lying through omission is still possible. Thus, a <code>merkleblock</code> message is a block header, plus a part of a merkle tree which can be used to extract identifying information for transactions that matched the filter and prove that the matching transaction data really did appear in the solved block. Clients can use this data to be sure that the remote node is not feeding them fake transactions that never appeared in a real block, although lying through omission is still possible.



===Extensions to existing messages=== ===Extensions to existing messages===
Line 143:
Line 137:
By updating the bloom filter atomically in step 2 with the discovered outpoint, the filter will match against TX 2 in step 3 and the client will learn about all relevant transactions, despite that there is no pause between the node processing the first and second blocks. By updating the bloom filter atomically in step 2 with the discovered outpoint, the filter will match against TX 2 in step 3 and the client will learn about all relevant transactions, despite that there is no pause between the node processing the first and second blocks.



===Merkle branch format=== ===Partial Merkle branch format===



A ''Merkle tree'' is a way of arranging a set of items as leaf nodes of tree in which the interior nodes are hashes of the concatenations of their child hashes. The root node is called the ''Merkle root''. Every Bitcoin block contains a Merkle root of the tree formed from the blocks transactions. By providing some elements of the trees interior nodes (called a ''Merkle branch'') a proof is formed that the given transaction was indeed in the block when it was being mined, but the size of the proof is much smaller than the size of the original block. A ''Merkle tree'' is a way of arranging a set of items as leaf nodes of tree in which the interior nodes are hashes of the concatenations of their child hashes. The root node is called the ''Merkle root''. Every Bitcoin block contains a Merkle root of the tree formed from the blocks transactions. By providing some elements of the trees interior nodes (called a ''Merkle branch'') a proof is formed that the given transaction was indeed in the block when it was being mined, but the size of the proof is much smaller than the size of the original block.



The branch is a list of hashes that can be used with the following algorithm. The encoding works as follows: we traverse the tree in depth-first order, storing a bit for each traversed node, signifying whether the node is the parent of at least one matched leaf txid (or a matched txid itself). In case we are at the leaf level, or this bit is 0, its merkle node hash is stored, and its children are not explored further. Otherwise, no hash is stored, but we recurse into both (or the only) child branch. During decoding, the same depth-first traversal is performed, consuming bits and hashes as they written during encoding.
  
# Let H = the hash of the transaction being checked for block inclusion. 
# Let I = the index in the original block of the transaction being checked. 
# For each element E in the branch: 
## If I is even, H = SHA256(SHA256(concatenation of E and H)) 
## If I is odd, H = SHA256(SHA256(concatenation of H and E)) 
## Divide I by 2   (right-shift) 
# If H is equal to the merkle root in the block header, the transaction was included 



===Bloom filter format=== ===Bloom filter format===

← Older revision		Revision as of 20:59, 17 December 2012
Line 65:		Line 65:
	The data field must be smaller than or equal to 520 bytes in size (the maximum size of any potentially matched object).		The data field must be smaller than or equal to 520 bytes in size (the maximum size of any potentially matched object).

	The given data element will be added to the Bloom filter. A filter must have been previously provided using filterload. This command is useful if a new key or script is added to a clients wallet whilst it has connections to the network open, it avoids the need to re-calculate and send an entirely new filter to every peer (though doing so is usually advisable to maintain anonymity).		The given data element will be added to the Bloom filter. A filter must have been previously provided using <code>filterload</code>. This command is useful if a new key or script is added to a clients wallet whilst it has connections to the network open, it avoids the need to re-calculate and send an entirely new filter to every peer (though doing so is usually advisable to maintain anonymity).

	The <code>filterclear</code> command has no arguments at all.		The <code>filterclear</code> command has no arguments at all.

← Older revision		Revision as of 20:56, 17 December 2012
Line 65:		Line 65:
	The data field must be smaller than or equal to 520 bytes in size (the maximum size of any potentially matched object).		The data field must be smaller than or equal to 520 bytes in size (the maximum size of any potentially matched object).

	The given data element will be added to the Bloom filter. ~~If no~~ filter ~~has~~ been previously provided using ~~<code>~~filterload~~</code>, a new one will be initialized that would have a false positive rate of, at a minimum, 0.1% with 1000 inserted elements~~. This command is useful if a new key or script is added to a clients wallet whilst it has connections to the network open, it avoids the need to re-calculate and send an entirely new filter to every peer.		The given data element will be added to the Bloom filter. A filter must have been previously provided using filterload. This command is useful if a new key or script is added to a clients wallet whilst it has connections to the network open, it avoids the need to re-calculate and send an entirely new filter to every peer (though doing so is usually advisable to maintain anonymity).

	The <code>filterclear</code> command has no arguments at all.		The <code>filterclear</code> command has no arguments at all.

← Older revision		Revision as of 00:23, 15 December 2012
Line 86:		Line 86:
	\| 4 \|\| nonce \|\| uint32_t \|\| The nonce used to generate this block… to allow variations of the header and compute different hashes		\| 4 \|\| nonce \|\| uint32_t \|\| The nonce used to generate this block… to allow variations of the header and compute different hashes
	\|-		\|-
	\| 1 \|\| ~~txn_count~~ \|\| uint32_t \|\| Number of transactions ~~that matched~~ the ~~filter~~		\| 4 \|\| total_transactions \|\| uint32_t \|\| Number of transactions in the block (including unmatched ones)
	\|-		\|-
	\| ? \|\| ~~transactions~~ \|\| ~~merkle_tx[]~~ \|\| ~~A series~~ of ~~merkle_tx messages, defined below, for each transaction in the block that matched the filter.~~		\| ? \|\| number_of_hashes \|\| varint \|\| Number of hashes
	\|}

	~~The <code>merkle_tx</code> message is defined below:~~

	~~{\|class="wikitable"~~
	~~! Field Size !! Description !! Data type !! Comments~~
	\|-		\|-
	\| 4 \|\| ~~index~~ \|\| ~~uint32_t~~ \|\| ~~The index~~ in ~~the original block that the transaction appeared at.~~		\| ? \|\| hashes \|\| uint256[] \|\| hashes in depth-first order (<= 32*N bytes)
	\|-		\|-
	\| 32 \|\| ~~hash~~ \|\| ~~uint256_t~~ \|\| ~~The hash~~ of ~~the matching transaction.~~		\| ? \|\| bytes_of_flags \|\| varint \|\| number of bytes of flag bits (1-3 bytes)
	\|-		\|-
	\| ? \|\| ~~merkle_branch~~ \|\| ~~uint256_t~~[] \|\| ~~A vector of hashes defining the Merkle branch linking this transaction to the merkle root~~ in ~~the block header~~		\| ? \|\| flags \|\| byte[] \|\| flag bits, packed per 8 in a byte, least significant bit first (<= 2*N-1 bits)
	\|}		\|}

	See below for the format of the merkle ~~branch~~.		See below for the format of the partial merkle tree hashes and flags.

	~~As you can see~~ a <code>merkleblock</code> message is a block header, plus identifying information for transactions that matched the filter~~, plus the Merkle branch which can be used to~~ prove that the matching transaction data really did appear in the solved block. Clients can use this data to be sure that the remote node is not feeding them fake transactions that never appeared in a real block, although lying through omission is still possible.		Thus, a <code>merkleblock</code> message is a block header, plus a part of a merkle tree which can be used to extract identifying information for transactions that matched the filter and prove that the matching transaction data really did appear in the solved block. Clients can use this data to be sure that the remote node is not feeding them fake transactions that never appeared in a real block, although lying through omission is still possible.

	===Extensions to existing messages===		===Extensions to existing messages===
Line 143:		Line 137:
	By updating the bloom filter atomically in step 2 with the discovered outpoint, the filter will match against TX 2 in step 3 and the client will learn about all relevant transactions, despite that there is no pause between the node processing the first and second blocks.		By updating the bloom filter atomically in step 2 with the discovered outpoint, the filter will match against TX 2 in step 3 and the client will learn about all relevant transactions, despite that there is no pause between the node processing the first and second blocks.

	===Merkle branch format===		===Partial Merkle branch format===

	A ''Merkle tree'' is a way of arranging a set of items as leaf nodes of tree in which the interior nodes are hashes of the concatenations of their child hashes. The root node is called the ''Merkle root''. Every Bitcoin block contains a Merkle root of the tree formed from the blocks transactions. By providing some elements of the trees interior nodes (called a ''Merkle branch'') a proof is formed that the given transaction was indeed in the block when it was being mined, but the size of the proof is much smaller than the size of the original block.		A ''Merkle tree'' is a way of arranging a set of items as leaf nodes of tree in which the interior nodes are hashes of the concatenations of their child hashes. The root node is called the ''Merkle root''. Every Bitcoin block contains a Merkle root of the tree formed from the blocks transactions. By providing some elements of the trees interior nodes (called a ''Merkle branch'') a proof is formed that the given transaction was indeed in the block when it was being mined, but the size of the proof is much smaller than the size of the original block.

	The ~~branch is~~ a ~~list of hashes that can be used with the following algorithm.~~		The encoding works as follows: we traverse the tree in depth-first order, storing a bit for each traversed node, signifying whether the node is the parent of at least one matched leaf txid (or a matched txid itself). In case we are at the leaf level, or this bit is 0, its merkle node hash is stored, and its children are not explored further. Otherwise, no hash is stored, but we recurse into both (or the only) child branch. During decoding, the same depth-first traversal is performed, consuming bits and hashes as they written during encoding.

	~~# Let H = the hash of the transaction being checked~~ for ~~block inclusion.~~
	~~# Let I =~~ the ~~index in~~ the ~~original block~~ of ~~the transaction being checked~~.
	~~# For each element E in~~ the ~~branch:~~
	~~## If I~~ is ~~even~~, ~~H = SHA256(SHA256(concatenation of E~~ and ~~H))~~
	~~## If I~~ is ~~odd~~, ~~H = SHA256~~(~~SHA256(concatenation of H and E~~))
	~~## Divide I by 2 (right~~-~~shift)~~
	~~# If H~~ is ~~equal to the merkle root in the block header~~, ~~the transaction was included~~

	===Bloom filter format===		===Bloom filter format===