P3 Block Chain Data Structures

Hash Pointers

• A normal pointer in programming saves the target memory location.

编程中的普通指针保存目标内存位置。

• Hash pointer is a pointer saving the target memory location and the target hash，Typically, H is used to represent a hash pointer. It can locate the position of the structure and also detect whether the content has been modified, as it stores its hash value.

Hash 指针是保存目标内存位置和目标 hash 的指针，通常用 来表示一个哈希指针。它可以定位结构的位置，还可以检测内容是否已被修改，因为它存储其哈希值。

Block Chain

+---------------------+         +---------------------+         +---------------------+
|   genesis block     |         |        Block 2      |         |the most recent block| <---- H()
|---------------------|         |---------------------|         |---------------------|
|                     | <-------|--H(previous).       | <-------|--H(previous).       |
+---------------------+         +---------------------+         +---------------------+

• Block Chain is a linked list using hash pointers.

区块链是使用哈希指针的链表。

• The first block of the chain is called genesis block

链的第一个区块称为创世区块(genesis block)

• The last block of the chain is the most recent block.

链的最后一个区块是 最近产生的区块(the most recent block)。

• Each Block has a hash pointing to the previous block, the hash of the most recent block is saved in the block chain system.

每个区块都有一个指向前一个区块的哈希值，最近产生的区块的哈希值保存在区块链系统中。

• The hash of a block is the result of applying a hash function to the entire content of the block.

区块的哈希值是将哈希函数应用于区块的全部内容的结果。

• The hash of a block is the content of the current block and the hash of the previous block. This creates a tamper-evident log. In other words, it is impossible to modify a block within the blockchain. If a block is modified, then all subsequent blocks must also be changed.

一个区块的哈希值是当前区块的内容和前一个区块的哈希值。这将创建一个防篡改日志(tamper-evident log)。换句话说，不可篡改区块链中的区块。如果修改了区块，则还必须更改所有后续区块(才能通过规则的校验)*。

因为篡改能被检测到，所以可以只保存最后一些区块。张三只保存了最后的几个区块，要使用更前面的区块，就问系统中的其他节点去要这个区块。有些节点是有恶意的，不能别人给了就信，所以，获取到别人的区块以后，要计算哈希值来校验是不是合法的。----- 这里的节点说的是终端？

Merkle tree

          +------------------+
          | H(12)      H(34) | <------H(root)
          +--------+---------+
                   |
          +--------+---------+
          |                  |
  +-------+-------+  +-------+-------+
  | H(1)      H(2)|  | H(3)      H(4)|
  +-------+-------+  +-------+-------+
          |                  |
     +----+----+      +------+------+
     |         |      |             |
+----+---+ +--+---+ +----+---+ +---+---+
| Data 1 | |Data 2| | Data 3 | | Data 4|
+--------+ +------+ +--------+ +-------+

Leaf Nodes: Represent the hash values of the original data (e.g., `Data 1`, `Data 2`, etc.). 
叶子节点：最下面的叶子 是数据块。（这里的节点 好像不是说终端设备，只是这颗树的节点）
Intermediate Nodes: Are the combinations of the hash values of their child nodes.
中间节点：两个哈希指针的拼接。 左右两个子节点的 Hash 进行的拼接。
Root Node: Is the hash value of the entire Merkle Tree, representing the hashes of all leaf nodes.
根节点： 整个默克尔树的哈希值。 

• Merkle tree is a binary tree using hash pointers

Merkle 树是使用哈希指针的二叉树

• The advantage of this data structure is that you only need to know the root hash value to detect any modifications to the structure of the tree.

这种数据结构的优点是，您只需要知道根哈希值即可检测对树结构的任何修改。

• The leaf nodes represent the transaction data.

叶节点表示交易数据。（这里的节点 好像不是说终端设备，只是这颗树的节点）

• A single block consists of a block header and a block body.

单个区块由 block header 和 block body 组成。block header中有 根哈希值，没有具体的交易内容； block body 有交易列表的。

• The root hash of the Merkle tree, composed of all the transactions contained in each block, is stored in the block header of that block.

Merkle 树的根哈希，某个区块中包含的所有交易组成的根哈希值，存储在该区块的区block header中。 ------------ 一个区块中可以有很多个交易，这个区块的所有交易数据是Merkle 树的叶子，整个Merkle 树的Root是根哈希值，存储在block header里；交易的信息列表则存储在block body里。

比特币中的节点分 两类： 1. 全节点，保存整个区块的内容block header+block body。 2. 轻节点，只保存block header，比如手机上的比特币钱包。 问题：如何向轻节点证明，某个交易，写入了区块链里面了？就需要用到 Merkle Proof。

Merkle Proof ： 验证交易数据是否确实存在于 Merkle 树中

• In Bitcoin, nodes are categorized into full nodes and light nodes (or lightweight nodes).

在比特币中，节点分为全节点和轻节点（或轻量级节点）。

• Full nodes contain the entire block information, including the block header, block body, and transaction data.

全节点包含完整的区块信息，包括区块header、区块body和交易数据。

• Bitcoin wallets function as light nodes, storing only the block headers.

比特币钱包充当轻节点，仅存储区块header。

• The Merkle tree root of all transactions in a block is stored in the block header.

一个区块中所有交易的 Merkle 树根 存储在此区块header中。

• The purpose of a Merkle proof is to verify that a transaction indeed exists in a Merkle tree.

Merkle Proof的作用是验证交易是否确实存在于 Merkle 树中。

Example

How can we prove that Transaction 3 (tx3) exists? We only have the Merkle Root (R) and the tx3 data.

我们怎么证明 交易 tx3 存在？我们已知的只有 Merkle Root （R） 和 tx3 数据。

具体描述：用一个稍浅一层 的树举例

----------+         +---------------------+         +---------------------+
 block n  |         |        Block n+1    |         |the most recent block| <---- H()
----------|         |---------------------|         |---------------------|
          | <-------|--H(previous).       | <-------|--H(previous).       |
          |.        |      Merkle Root    |         |       Merkle Root   |
----------+         +---------------------+         +---------------------+
                                   |
                                   | 
                                   |
          +------------------+     |
          | H(12)      H(34) | <---
          +--------+---------+
                   |
          +--------+---------+
          |                  |
  +-------+-------+  +-------+-------+
  | H(1)      H(2)|  | H(3)      H(4)|
  +-------+-------+  +-------+-------+
          |                  |
     +----+----+      +------+------+
     |         |      |             |
+----+---+ +--+---+ +----+---+ +---+---+
|   tx1  | | tx2  | |   tx3  | |  tx4  |
+--------+ +------+ +--------+ +-------+

1. Compute the hash for tx3.

1. 本地计算tx3的哈希值。

2. Query the full node for the hash value .

2. 向全节点查询 哈希值

3. Compute from and .

3. 本地计算 哈希值

4. Query the full node for the hash value .

4. 向全节点查询 哈希值

5. Compute the Merkle Root value R' from and .

5 本地计算 R' 。也就是 默克尔树根。

6. Check the equation R' and R. If R' equals R, then tx3 exists; otherwise, it does not.

6. 对比 本地计算得出的 R' 与 存储在 Block Header中的 R。如果一致，则 tx3存在。否则其不存在于Merkle树里。

The Time Complexity of Merkle Proof

• Proof of membership(inclusion)
  • In the context of Merkle trees, the time complexity for verifying a Merkle proof is O(log n), where n is the number of leaf nodes (transactions) in the tree. This is because you only need to traverse up the tree using the hash values provided in the proof, which involves a logarithmic number of steps relative to the total number of transactions.

在 Merkle 树的上下文中，验证 全节点提供的一条 Merkle Proof 的时间复杂度为 O(log n)，其中 n 是树中叶节点（交易）的数量。

• Proof of non-membership
  • We need to query all the transactions from the full nodes and check it's non-existence.

我们需要从全节点查询所有交易并检查它 不存在（它可能出现在任何叶子位置，需尽数排除）。所以复杂度是 O(n)。

• Sorted Merkle tree which sorted by transactio hash is similar to the binary search tree. We can use a Merkle tree to prove the non-existence of a transaction for O(log(n)) time complexity, although this structure is not used in Bitcoin.

如果依据树的叶子的哈希大小做排序重排树，排序 Merkle 树 类似于二叉搜索树。我们能以 的时间复杂度 来证明 交易不存在(Proof of non-membership)。尽管这种结构在比特币中没有使用。比特币 没有 “不存在证明” 的需求。