Types of Transactions & Pool, Block Header, Node, Bloom Filter
Transactions are propagated through nodes and are verified. Several important verification conditions are as follows:
- Transactions syntax & data structure should be correct
- Transaction size should be smaller than the block’s maximum size
- Input UTXO should not have been used
Double payments can be avoided by identifying the consumption of UTXO already used. - Check if the reference transaction is in the pool or main chain
The transaction was structured to refer to the output value of the previous transaction. But if the transaction to refer to is not confirmed, is it really wrong?
Orphan transaction
Transactions may not be received due to differences in transfer rates on the network. The previous transaction to be referred to is called ‘Parent transaction’ and the subsequent transaction is called ‘Child transaction’. If a child transaction is first received before the parent transaction arrives, the transaction shall be considered an “ Orphan transaction.”
Nodes use UTXO to create transactions or gather transactions to form blocks in a decentralized environment, rather than in the form of looking up from centralized data. Transactions received are added to the transaction pool on the node after the above verification and transferred again to the neighboring node. The pool is filled in such a process. The types of pool are as follows.
Pool
Transaction Pool (Memory Pool)
Nodes contain transactions sent to neighboring nodes. When a miner forms a block, he or she uses his own transaction pool to form the block.
In addition to transaction pools, some nodes form special pools.
Orphan transaction pool
When a transaction is sent, the recipient checks if there is a child transaction and, if any, move both the parent transaction and the child transaction to the transaction pool.
This prevents a valid transaction from being discarded and allows the transaction to be structured validly. The orphan transaction pool limits the number of transactions stored in the corresponding pool to prevent a DoS(Denial of Service) attack.
Both pools are stored in local memory and contain verified but unapproved transactions. In addition, there is a large difference in information between nodes as they are filled directly with messages when starting the node.
UTXO Pool
All UTXO data on the blockchain is stored in UTXO pool and unlike orphanage pool, it is not initially empty but consists of unconsumed outputs (UTXO). In other words, the UTXO pool has fewer differences between nodes because it means the consensus of the network. It is stored in local memory or in permanent storage in the form of a database table and contains approved output values. It also includes the UTXO created in 2009.
Miners store transactions through these pools and use the transaction pools to gather and put them in blocks.
So how does the block hold the transaction, and what structure does the block form?
Blocks are divided into Header and Transaction as shown.
In fact, there is no “Body” field in the block structure. With the block’s configuration, there are also “block size” and “number of transactions ” besides “block headers” and parts that contain “transactions” are usually referred to as “body” and actually make up most of the size.
You might understand why blockchain is said to be ‘chain’ or ‘encrypted’ by looking at the header.
Header’s structure
1. Version
This indicates which version of Bitcoin is being used. This is the version number for tracking software/protocol upgrades.
2. Previous Block Header Hash
This is an important concept that makes blockchain a ‘chain’.
Important thing is that this often referred to as “Block hash,” but it’s actually a “header” which doesn’t include the whole block, so to empathize, I specified it as “Previous(Parent) block header hash” to correct the misunderstanding. “Previous” and “Header” might be included to prevent misunderstanding.
When the node trying to mine the Nth block receives the N-1th block, it directly calculates the ‘header hash’ for the previous block (N-1th block) and puts it in the header (precisely hashing twice). The specific mining process will be explained later.
3. Timestamp
Based on Unix Time (1 January 1970), it will record the time of mining blocks in seconds.
4. Merkle Root
Let’s take a look at the Merkle Tree to find out about Merkle Root. The Merkle Tree is easy to think of as an encryption process that is forming a “tree structure.” The final value at the top is referred to as ‘Root’ and the lower values as ‘Leaf’.
Take the Merkle Tree with 8 transactions as an example. As shown in the figure above, the hash value for the transaction is ‘leaf’ as shown in Hash1 through Hash8, which is then added by tying the two together and proceeding in the same way to obtain the final muckle root. (Hash9 value is the value taken with the “SHA256” hash of ‘Hash1 + Hash2’ twice.)
As shown in the word ‘root’, Merkle Root means one final value as a result which in the figure is the top value.
Looking at the tree, one might ask, ‘What happens if the transaction is odd?’. In this case, the last transaction is copied and used as an even number of transactions. (It is called ‘Balanced Tree’ in these cases)
Also, one might also ask ‘Why is it necessary to use a hash function instead of saving the original copy of the transaction?’. When we think of the usage of a hash function, Merkle Root is very important since it has the advantage of knowing the counterfeit at once. In other words, the effect of the Merkle Root can be clearly seen if it is sure that when one of the 300 data in the block, or the letter of one of the data is changed, the hash will result in a completely different value. (Note that for Ethereum, it uses Merkle-Patricia tree to store the information of the ‘state’.)
The advantages of the Merkle tree go beyond the usage for preventing counterfeit, and also makes it easier to search quickly. If you use a ‘Merkle Path’, the procedure for ‘confirming whether a transaction is contained’ is very easy when you know the Merkle Root. Let’s look at the verification process and what the Merkle Path is.
Example
Alice receives the block header and the Merkle Path from the full-node if it wants to verify that its own transaction ‘Tx1’ is contained in the block. Check whether Tx1 is included in the block header via the Merkle Root and the Merkle Path. What kind of path do you need to know that Tx1 is contained?
With only Hash2, Hash10, and Hash14, the Merkle Root can be calculated and derived directly. That is, by making the Hash1 using Tx1, Alice can add the Hash2 which is included in the Merkle Path and obtain the Hash9. Hash13 can then be obtained by using the hash9 and the Hash10 which is included in the Merkle Path and the Merkle Root can be obtained directly by using the Hash14 included in Merkle Path. If you match this value by comparing it with the ‘Merkle Roots’, you will see that your transaction Tx1 is contained in the block without any change. This also can be confirmed that 3 Merkle Paths(3= log2(8) which 8 is the number of transactions) are included.
This helps Simplified Payment Verification (SPV) nodes find specific transactions easily and quickly.
Node
There are several types of nodes in the Bitcoin P2P network. All nodes have a routing function to validate and propagate transactions and blocks.
Full node
It is a node that holds everything from the Genesis block to the latest data. That is, it can use the blockchain without any help from neighboring nodes. Bitcoin was originally a ‘full node’ for all users. Right now, the role of the Lightweight node has also been created.
Mining node
Mining nodes do not necessarily have to be full nodes. If you want to participate in mining with Lightweight Nodes, you can participate in a mining pool using a pool server.
SPV(Simplified Payment Verification) Node
The SPV node is the same concept as the Lightweight node, which is literally a ‘simple payment verification node’ that can identify a particular transaction without having to store a full blockchain. An important fact commonly misunderstood is that SPV nodes can “confirm” transactions but cannot “directly verify” them. Although the node can perform simple verification (verification that it has been safely stored) by referring to the depth and height of the block containing the transaction, direct verification (whether the transaction itself is appropriate) is not possible because there is no record of all the transactions. UTXO consumption is also not verifiable.
SPV Node will request data to neighboring nodes to verify the payment. However, in this process, SPV nodes naturally expose their privacy. In other words, they must communicate exactly what data they want. To improve this, ‘Bloom Filter’ will be used to maintain privacy while obtaining the desired data.
Bloom Filter
Bloom Filter sets up ‘specific patterns’ to aggregate data that meet conditions. An SPV node, for example, would be like asking for a ‘transaction from someone who ends up ‘ice’’ to find a ‘transaction sent by Alice’. In order to increase accuracy, ‘conditions’ need to be more specified, but also privacy is exposed as much. Bloom Filter, which is made up of various patterns, is defined in BIP37, and the actual method of operation is much more specific and complex, so if you are curious, check the link.
I’ll continue to explain the explanation of ‘Target’ and ‘Nonce’, which are the core of the concept of mining.
References
- Antonopoulos, Andreas M. Mastering Bitcoin: Unlocking Digital Crypto-Currencies. OReilly, 2016.
Dongha Sohn / sohn@skkrypto.io
