The original link

An overview of the

Through “Bitcoin those things (1) — Introduction” and “Bitcoin those things (2) — Transaction” two articles, we have a basic understanding of bitcoin. In this article, we explore the core of what bitcoin does: the blockchain.

Block chain

A blockchain, as its name suggests, is a linked list of data structures called blocks. A large amount of transaction information is recorded in each block. All nodes in the Bitcoin system maintain a global blockchain, with full nodes owning a complete copy.

Since blockchain is a series of blocks, is there any relationship between the blocks? In fact, each block contains information about the previous block. When a new block is created, the block header of the previous block is SHA256 encrypted to generate a hash value. The hash value is then referenced in the parent block hash field in the block header of the new block so that each block header contains its parent block hash value. The result is a blockchain that can be traced back to the first block (Trands).

Blockchains can be stored as Flat files or stored in databases. The bitcoin core client uses Google’s LevelDB database to store blockchain metadata.

block

A block is essentially a container data structure that serves transaction information. Let’s look at a Swift open source library called BitcoinKit to see how it describes bitcoin’s block structure.

public struct BlockMessage {
    /* Block header */
    /// Block version information (note, this is signed)
    public let version: Int32
    /// The hash value of the previous block this particular block references
    public let prevBlock: Data
    /// The reference to a Merkle tree collection which is a hash of all transactions related to this block
    public let merkleRoot: Data
    /// A Unix timestamp recording when this block was created (Currently limited to dates before the year 2106!)
    public let timestamp: UInt32
    /// The calculated difficulty target being used for this block
    public let bits: UInt32
    // The nonce used to generate this block... to allow variations of the header and compute different hashes
    public let nonce: UInt32
    
    /* Number of transactions */
    /// Number of transaction entries
    public let transactionCount: VarInt
    
    /* Trade list */
    /// Block transactions, in format of "tx" command
    public let transactions: [Transaction]}Copy the code

Based on the above code, we can actually divide the block structure into three parts:

  • Block Header: A Block Header consisting of multiple fields
  • Transaction Count: Records the number of transactions recorded in the block
  • Transactions: List of blocks recorded in this block

Let’s take a look at each part in turn.

Block head

As you can see from the sample code above, the block header contains six fields:

  • Version: indicates the Version number of the block
  • Previous Block Hash: Block header Hash of the parent Block
  • Merkle Root: The Root value of the Merkle Tree composed of transactions in this block
  • Timestamp: The creation time of the block
  • Difficulty Target: The Target value of a proof of effort
  • Nonce: the proof-of-work value calculated for this block

Nonce, Difficulty Target and Timestamp are used in the mining process.

Merkle Tree

As mentioned above, each block contains a Merkle Root field to record the Root of the Merkle tree. So what is a Merkle tree? Why was this tree built?

Merkle tree is a kind of hash binary tree, which is mainly used for fast induction and verification of large-scale data integrity data structure.

In the Bitcoin system, merkle trees are used to summarize all transactions in a block, generate a digital fingerprint of the block’s set of transactions, and provide an efficient way to verify the presence of a transaction in the block.

Merkle trees are built from the bottom up. The merkle tree is built by recursively hashing a pair of nodes and inserting the newly generated hash node into the merkle tree until only one hash node remains, the root of the merkle tree.

The following figure shows an example of constructing merkle tree for transactions A, B, C and D.

The build process

First, an encrypted hash (double-sha256) is performed on each transaction to produce a leaf node.

Then, the parent node is obtained by the cryptographic hash operation after the leaf nodes are connected in tandem.

Continue with similar operations until only one top node, the Merkle Root, remains.

Since merkle is a binary tree, it requires an even number of leaf nodes. If only an odd number of transactions need to be summarized, the last transaction is copied to form an even number of leaf nodes. As shown in the figure below, the C node is replicated.

Because the result of an encrypted hash is always 32 bits long, the root of the Merkle tree is always 32 bits in size no matter how many transactions are used to build it.

Transaction to verify

To prove the existence of a transaction in a block, a node simply computs log2(N) hashes to form an authentication path (also known as merkle path) from the transaction to the root. This method can reduce the time complexity of verification from O(N) to log2(N). As the number of transactions increases, the efficiency advantage of this verification method becomes more obvious.

Take merkle tree as shown in the figure below as an example to verify whether there is transaction K in the block. In order to verify whether transaction K exists, we need to provide the child nodes of the nodes on the authentication path, namely the nodes marked in blue, including:

Then, the transaction K is used to combine these nodes, and the encrypted hash operation is carried out in turn in the way of constructing Merkle tree to obtain:

The last node calculated is Merkle Root, and if it matches the Merkle Root value recorded in the block, it indicates that there is a transaction K in the block.

Some problems may arise:

  • Don’t all the nodes in the Bitcoin system have a copy of the global blockchain? Isn’t it possible to verify that a transaction exists by simply traversing the blockchain?
  • When verifying a transaction through a Merkle tree, where do the nodes that assist verification come from?

In fact, not all nodes in the Bitcoin system keep a complete copy of the global blockchain. Because the current global blockchain data volume of Bitcoin has been very large, it is unrealistic for ordinary clients, especially mobile clients, to keep a complete copy of the blockchain.

Therefore, nodes in a Bitcoin system can be divided into two types depending on whether a complete global copy of the blockchain is kept:

  • Full Node: Keeps a complete copy of the blockchain and can independently verify all transactions.
  • Light node (also known as SPV node) : only retains part of the blockchain, relies on the whole node to provide validation data, and verifies transactions through simple payment verification.

In fact, the merkel-based method of verifying transactions is called simple payment verification, which is mainly used for light nodes.

Simple Payment verification

Light nodes do not hold a full copy of the blockchain, only the block header. They use authentication paths to verify that a transaction exists in a block, rather than having to download all the transactions in the block.

Consider a scenario where an SPV node wants to know if a transaction related to an address has been completed in its wallet.

To complete this verification process, the SPV nodes first establish Bloom filters on the communication links between the nodes, limiting the acceptance of only transactions containing the target address. When the docking full node detects that a transaction fits the Bloom filter, it sends the block as a Merkle Message.

Merkle messages contain block headers and an authentication path that connects the target transaction to merkle roots.

The SPV node uses the authentication path in the Merkle message and the target transaction to get the merkle root value. The merkel-root value of the block header in the Merkel-message is then verified to determine whether the transaction exists in the corresponding block. This can prove whether the transaction exists in the blockchain, that is, whether the transaction is completed.

Transaction number

The transaction count records how many transactions the block contains.

Transaction list

A transaction list records a series of transactions. Let’s look at how transactions are described in the open source library.

public struct Transaction {
    /// Transaction data format version (note, this is signed)
    public let version: UInt32
    
    /// A list of 1 or more transaction inputs or sources for coins
    public let inputs: [TransactionInput]
    
    /// A list of 1 or more transaction outputs or destinations for coins
    public let outputs: [TransactionOutput]
    
    /// A list of witnesses, one for each input; omitted if flag is omitted above
    // public let witnesses: [TransactionWitness] // A list of witnesses, one for each input; omitted if flag is omitted above
    /// The block number or timestamp at which this transaction is unlocked:
    public let lockTime: UInt32
}
Copy the code

Comparing the members of Transaction type with the structure of transactions described in Bitcoin (2) — Transactions, the two are basically the same. Therefore, this paper will not be repeated.

reference

  1. Master Bitcoin
  2. Blockchain Development Guide
  3. Introduction to BlockChain and Ethereum
  4. BitcoinKit