转载

基于Java语言构建区块链（六）—— 交易（Merkle Tree）

文章的主要思想和内容均来自 https://jeiwan.cc/posts/building-blockchain-in-go-part-6/

引言

在这一系列文章的最开始部分，我们提到过区块链是一个分布式的数据库。那时候，我们决定跳过”分布式”这一环节，并且聚焦于”数据存储”这一环节。到目前为止，我们几乎实现了区块链的所有组成部分。在本篇文章中，我们将会涉及一些在前面的文章中所忽略的一些机制，并且在下一篇文章中我们将开始研究区块链的分布式特性。

前面各个部分内容：

基本原型
工作量证明
持久化 & 命令行
交易（UTXO）
地址（钱包）

UTXO池

在持久化 & 命令行这篇文章中，我们研究了比特币核心存储区块的方式。当中我们提到过与区块相关的数据存储在 blocks 这个数据桶中，而交易数据则存储在 chainstate 这个数据桶中，让我们来回忆一下， chainstate 数据桶的数据结构：

‘c’ + 32-byte transaction hash -> unspent transaction output record for that transaction

某笔交易的UTXO记录

‘B’ -> 32-byte block hash: the block hash up to which the database represents the unspent transaction outputs

数据库所表示的UTXO的区块Hash

从那篇文章开始，我们已经实现了比特币的交易机制，但是我们还没有用到 chainstate 数据桶去存储我们的交易输出。所以，这将是我们现在要去做的事情。

chainstate不会去存储交易数据。相反，它存储的是 UTXO 集，也就是未被花费的交易输出集合。除此之外，它还存储了”数据库所表示的UTXO的区块Hash”，我们这里先暂且忽略这一点，因为我们还没有用到区块高度（这一点我们会在后面的文章进行实现）。

那么，我们为什么需要 UTXO 池呢？

一起来看一下我们前面实现的 findUnspentTransactions 方法：

/**
  * 查找钱包地址对应的所有未花费的交易
  *
  * @param pubKeyHash 钱包公钥Hash
  * @return
  */
 private Transaction[] findUnspentTransactions(byte[] pubKeyHash) throws Exception {
     Map<String, int[]> allSpentTXOs = this.getAllSpentTXOs(pubKeyHash);
     Transaction[] unspentTxs = {};

     // 再次遍历所有区块中的交易输出
     for (BlockchainIterator blockchainIterator = this.getBlockchainIterator(); blockchainIterator.hashNext(); ) {
         Block block = blockchainIterator.next();
         for (Transaction transaction : block.getTransactions()) {

             String txId = Hex.encodeHexString(transaction.getTxId());

             int[] spentOutIndexArray = allSpentTXOs.get(txId);

             for (int outIndex = 0; outIndex < transaction.getOutputs().length; outIndex++) {
                 if (spentOutIndexArray != null && ArrayUtils.contains(spentOutIndexArray, outIndex)) {
                     continue;
                 }

                 // 保存不存在 allSpentTXOs 中的交易
                 if (transaction.getOutputs()[outIndex].isLockedWithKey(pubKeyHash)) {
                     unspentTxs = ArrayUtils.add(unspentTxs, transaction);
                 }
             }
         }
     }
     return unspentTxs;
 }

该方法是用来查找钱包地址对应的包含未花费交易输出的交易信息。由于交易信息是存储在区块当中，所以我们现有的做法是遍历区块链中的每个区块，然后遍历每个区块中的交易信息，再然后遍历每个交易中的交易输出，并检查交易输出是否被相应的钱包地址所锁定，效率非常低下。截止2018年3月29号，比特币中有 515698 个区块，并且这些数据占据了140+Gb 的磁盘空间。这也就意味着一个人必须运行全节点（下载所有的区块数据）才能验证交易信息。此外，验证交易信息需要遍历所有的区块。

针对这个问题的解决办法是需要有一个存储了所有UTXOs（未花费交易输出）的索引，这就是 UTXOs 池所要做的事情：UTXOs池其实是一个缓存空间，它所缓存的数据需要从构建区块链中所有的交易数据中获得（通过遍历所有的区块链，不过这个构建操作只需要执行一次即可），并且它后续还会用于钱包余额的计算以及新的交易数据的验证。截止到2017年9月，UTXOs池大约为 2.7Gb。

好了，让我们来想一下，为了实现 UTXOs 池我们需要做哪些事情。当前，有下列方法被用于查找交易信息：

Blockchain.getAllSpentTXOs—— 查询所有已被花费的交易输出。它需要遍历区块链中所有区块中交易信息。
Blockchain.findUnspentTransactions—— 查询包含未被花费的交易输出的交易信息。它也需要遍历区块链中所有区块中交易信息。
Blockchain.findSpendableOutputs—— 该方法用于新的交易创建之时。它需要找到足够多的交易输出，以满足所需支付的金额。需要调用 Blockchain.findUnspentTransactions 方法。
Blockchain.findUTXO—— 查询钱包地址所对应的所有未花费交易输出，然后用于计算钱包余额。需要调用

Blockchain.findUnspentTransactions 方法。
Blockchain.findTransaction—— 通过交易ID查询交易信息。它需要遍历所有的区块直到找到交易信息为止。

如你所见，上面这些方法都需要去遍历数据库中的所有区块。由于UTXOs池只存储未被花费的交易输出，而不会存储所有的交易信息，因此我们不会对有 Blockchain.findTransaction 进行优化。

那么，我们需要下列这些方法：

Blockchain.findUTXO —— 通过遍历所有的区块来找到所有未被花费的交易输出.
UTXOSet.reindex —— 调用上面 findUTXO 方法，然后将查询结果存储在数据库中。也即需要进行缓存的地方。
UTXOSet.findSpendableOutputs —— 与 Blockchain.findSpendableOutputs 类似，区别在于会使用 UTXO 池。
UTXOSet.findUTXO —— 与 Blockchain.findUTXO 类似，区别在于会使用 UTXO 池。
Blockchain.findTransaction —— 逻辑保持不变。

这样，两个使用最频繁的方法将从现在开始使用缓存！让我们开始编码吧！

定义 UTXOSet：

@NoArgsConstructor
@AllArgsConstructor
@Slf4j
public class UTXOSet {
    private Blockchain blockchain;
}

重建 UTXO 池索引:

public class UTXOSet {
 
   ...
 
  /**
    * 重建 UTXO 池索引
    */
    @Synchronized   
    public void reIndex() {
        log.info("Start to reIndex UTXO set !");
        RocksDBUtils.getInstance().cleanChainStateBucket();
        Map<String, TXOutput[]> allUTXOs = blockchain.findAllUTXOs();
        for (Map.Entry<String, TXOutput[]> entry : allUTXOs.entrySet()) {
            RocksDBUtils.getInstance().putUTXOs(entry.getKey(), entry.getValue());
        }
        log.info("ReIndex UTXO set finished ! ");
    }
    
    ...
}

此方法用于初始化 UTXOSet。首先，需要清空 chainstate 数据桶，然后查询所有未被花费的交易输出，并将它们保存到 chainstate 数据桶中。

实现 findSpendableOutputs 方法，供 Transation.newUTXOTransaction 调用

public class UTXOSet {
 
   ... 
 
   /**
     * 寻找能够花费的交易
     *
     * @param pubKeyHash 钱包公钥Hash
     * @param amount     花费金额
     */
    public SpendableOutputResult findSpendableOutputs(byte[] pubKeyHash, int amount) {
        Map<String, int[]> unspentOuts = Maps.newHashMap();
        int accumulated = 0;
        Map<String, byte[]> chainstateBucket = RocksDBUtils.getInstance().getChainstateBucket();
        for (Map.Entry<String, byte[]> entry : chainstateBucket.entrySet()) {
            String txId = entry.getKey();
            TXOutput[] txOutputs = (TXOutput[]) SerializeUtils.deserialize(entry.getValue());

            for (int outId = 0; outId < txOutputs.length; outId++) {
                TXOutput txOutput = txOutputs[outId];
                if (txOutput.isLockedWithKey(pubKeyHash) && accumulated < amount) {
                    accumulated += txOutput.getValue();

                    int[] outIds = unspentOuts.get(txId);
                    if (outIds == null) {
                        outIds = new int[]{outId};
                    } else {
                        outIds = ArrayUtils.add(outIds, outId);
                    }
                    unspentOuts.put(txId, outIds);
                    if (accumulated >= amount) {
                        break;
                    }
                }
            }
        }
        return new SpendableOutputResult(accumulated, unspentOuts);
    }
    
    ...
    
}

实现 findUTXOs 接口，供 CLI.getBalance 调用：

public class UTXOSet {
 
   ... 
 
   /**
     * 查找钱包地址对应的所有UTXO
     *
     * @param pubKeyHash 钱包公钥Hash
     * @return
     */
    public TXOutput[] findUTXOs(byte[] pubKeyHash) {
        TXOutput[] utxos = {};
        Map<String, byte[]> chainstateBucket = RocksDBUtils.getInstance().getChainstateBucket();
        if (chainstateBucket.isEmpty()) {
            return utxos;
        }
        for (byte[] value : chainstateBucket.values()) {
            TXOutput[] txOutputs = (TXOutput[]) SerializeUtils.deserialize(value);
            for (TXOutput txOutput : txOutputs) {
                if (txOutput.isLockedWithKey(pubKeyHash)) {
                    utxos = ArrayUtils.add(utxos, txOutput);
                }
            }
        }
        return utxos;
    }
    
    ...
    
}

以上这些方法都是先前 Blockchain 中相应方法的微调版，先前的方法将不再使用。

有了UTXO池之后，意味着我们的交易数据分开存储到了两个不同的数据桶中：交易数据存储到了 block 数据桶中，而UTXO存储到了 chainstate 数据桶中。这就需要一种同步机制来保证每当一个新的区块产生时，UTXO池能够及时同步最新区块中的交易数据，毕竟我们不想频地进行 reIndex 。因此，我们需要如下方法：

更新UTXO池：

public class UTXOSet {
 
   ... 

   /**
     * 更新UTXO池
     * <p>
     * 当一个新的区块产生时，需要去做两件事情：
     * 1）从UTXO池中移除花费掉了的交易输出；
     * 2）保存新的未花费交易输出；
     *
     * @param tipBlock 最新的区块
     */
    @Synchronized
    public void update(Block tipBlock) {
        if (tipBlock == null) {
            log.error("Fail to update UTXO set ! tipBlock is null !");
            throw new RuntimeException("Fail to update UTXO set ! ");
        }
        for (Transaction transaction : tipBlock.getTransactions()) {

            // 根据交易输入排查出剩余未被使用的交易输出
            if (!transaction.isCoinbase()) {
                for (TXInput txInput : transaction.getInputs()) {
                    // 余下未被使用的交易输出
                    TXOutput[] remainderUTXOs = {};
                    String txId = Hex.encodeHexString(txInput.getTxId());
                    TXOutput[] txOutputs = RocksDBUtils.getInstance().getUTXOs(txId);

                    if (txOutputs == null) {
                        continue;
                    }

                    for (int outIndex = 0; outIndex < txOutputs.length; outIndex++) {
                        if (outIndex != txInput.getTxOutputIndex()) {
                            remainderUTXOs = ArrayUtils.add(remainderUTXOs, txOutputs[outIndex]);
                        }
                    }

                    // 没有剩余则删除，否则更新
                    if (remainderUTXOs.length == 0) {
                        RocksDBUtils.getInstance().deleteUTXOs(txId);
                    } else {
                        RocksDBUtils.getInstance().putUTXOs(txId, remainderUTXOs);
                    }
                }
            }

            // 新的交易输出保存到DB中
            TXOutput[] txOutputs = transaction.getOutputs();
            String txId = Hex.encodeHexString(transaction.getTxId());
            RocksDBUtils.getInstance().putUTXOs(txId, txOutputs);
        }

    }
    
    ...
    
}

让我们将 UTXOSet 用到它们所需之处去：

public class CLI {

   ...

   /**
     * 创建区块链
     *
     * @param address
     */
    private void createBlockchain(String address) {
        Blockchain blockchain = Blockchain.createBlockchain(address);
        UTXOSet utxoSet = new UTXOSet(blockchain);
        utxoSet.reIndex();
        log.info("Done ! ");
    }
    
    ...
    
}

当创建一个新的区块链是，我们需要重建 UTXO 池索引。截止目前，这是唯一一处用到 reIndex 的地方，尽管看起有些多余，因为在区块链创建之初仅仅只有一个区块和一笔交易。

修改 CLI.send 接口：

public class CLI {
	
	...

   /**
     * 转账
     *
     * @param from
     * @param to
     * @param amount
     */
    private void send(String from, String to, int amount) throws Exception {
        
        ...
        
        Blockchain blockchain = Blockchain.createBlockchain(from);
        Transaction transaction = Transaction.newUTXOTransaction(from, to, amount, blockchain);
        Block newBlock = blockchain.mineBlock(new Transaction[]{transaction});
        new UTXOSet(blockchain).update(newBlock);
		
        ...
    }
    
    ...
    
}

当一个新的区块产生后，需要去更新 UTXO 池数据。

让我们来检查一下它们的运行情况：

$ java -jar blockchain-java-jar-with-dependencies.jar  createwallet
wallet address : 1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf

$ java -jar blockchain-java-jar-with-dependencies.jar  createwallet
wallet address : 1HX7bWwCjvxkjq65GUgAVRFfTZy6yKWkoG

$ java -jar blockchain-java-jar-with-dependencies.jar  createwallet
wallet address : 1L1RoFgyjCrNPCPHmSEBtNiV3h2wiF9mZV

$ java -jar blockchain-java-jar-with-dependencies.jar  createblockchain -address 1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf

Elapsed Time: 164.961 seconds 
correct hash Hex: 00225493862611bc517cb6b3610e99d26d98a6b52484c9fa745df6ceff93f445 

Done ! 

$ java -jar blockchain-java-jar-with-dependencies.jar  getbalance -address 1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf
Balance of '1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf': 10

$ java -jar blockchain-java-jar-with-dependencies.jar  send -from 1HX7bWwCjvxkjq65GUgAVRFfTZy6yKWkoG -to  1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf -amount 5
java.lang.Exception: ERROR: Not enough funds

$ java -jar blockchain-java-jar-with-dependencies.jar  send -from 1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf -to 1HX7bWwCjvxkjq65GUgAVRFfTZy6yKWkoG -amount 2
Elapsed Time: 54.92 seconds 
correct hash Hex: 0001ab21f71ff2d6d532bf3b3388db790c2b03e28d7bd27bd669c5f6380a4e5b 

Success!

$ java -jar blockchain-java-jar-with-dependencies.jar  send -from 1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf -to 1L1RoFgyjCrNPCPHmSEBtNiV3h2wiF9mZV -amount 2
Elapsed Time: 54.92 seconds 
correct hash Hex: 0009b925cc94e3db8bab2958b1fc2d1764aa15531e20756d92c3a93065c920f0 

Success!

$ java -jar blockchain-java-jar-with-dependencies.jar  getbalance -address 1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf
Balance of '1JgppX2xMshr35wHzvNWQBejUAZ3Te5Mdf': 6

$ java -jar blockchain-java-jar-with-dependencies.jar  getbalance -address 1HX7bWwCjvxkjq65GUgAVRFfTZy6yKWkoG
Balance of '1HX7bWwCjvxkjq65GUgAVRFfTZy6yKWkoG': 2

$ java -jar blockchain-java-jar-with-dependencies.jar  getbalance -address 1L1RoFgyjCrNPCPHmSEBtNiV3h2wiF9mZV
Balance of '1L1RoFgyjCrNPCPHmSEBtNiV3h2wiF9mZV': 2

奖励机制

前面的章节中我们省略了矿工挖矿的奖励机制。时机已经成熟，该实现它了。

矿工奖励其实是一个 coinbase 交易（创币交易）。当一个矿工节点开始去生产一个新的区块时，他会从队列中取出一些交易数据，并且为它们预制一个 coinbase 交易。这笔 coinbase 交易中仅有的交易输出包含了矿工的公钥hash。

只需要更新 send 命令接口，我们就可以轻松实现矿工的奖励机制：

public class CLI {
	
	...

   /**
     * 转账
     *
     * @param from
     * @param to
     * @param amount
     */
    private void send(String from, String to, int amount) throws Exception {
        
        ...
        
        Blockchain blockchain = Blockchain.createBlockchain(from);
        // 新交易
        Transaction transaction = Transaction.newUTXOTransaction(from, to, amount, blockchain);
        // 奖励
        Transaction rewardTx = Transaction.newCoinbaseTX(from, "");
        Block newBlock = blockchain.mineBlock(new Transaction[]{transaction, rewardTx});
        new UTXOSet(blockchain).update(newBlock);
		
        ...
    }
    
    ...
 	   
}

还需要修改交易验证方法，coinbase 交易直接验证通过：

public class Blockchain {
	
  /**
     * 交易签名验证
     *
     * @param tx
     */
    private boolean verifyTransactions(Transaction tx) {
        if (tx.isCoinbase()) {
            return true;
        }
    
        ...
    }
    
    ...
    
}

在我们的实现逻辑中，代币的发送也是区块的生产者，因此，奖励也归他所有。

让我们来验证一下奖励机制：

$ java -jar blockchain-java-jar-with-dependencies.jar  createwallet 
wallet address : 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD

$ java -jar blockchain-java-jar-with-dependencies.jar  createwallet 
wallet address : 17crpQoWy7TEkY9UPjZ3Qt9Fc2rWPUt8KX

$ java -jar blockchain-java-jar-with-dependencies.jar  createwallet 
wallet address : 12L868QZW1ySYzf2oT5ha9py9M5JrSRhvT

$ java -jar blockchain-java-jar-with-dependencies.jar  createblockchain -address 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD

Elapsed Time: 17.973 seconds
correct hash Hex: 0000defe83a851a5db3803d5013bbc20c6234f176b2c52ae36fdb53d28b33d93 

Done ! 

$ java -jar blockchain-java-jar-with-dependencies.jar  send -from 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD -to 17crpQoWy7TEkY9UPjZ3Qt9Fc2rWPUt8KX -amount 6
Elapsed Time: 30.887 seconds
correct hash Hex: 00005fd36a2609b43fd940577f93b8622e88e854f5ccfd70e113f763b6df69f7 

Success!


$ java -jar blockchain-java-jar-with-dependencies.jar  send -from 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD -to 12L868QZW1ySYzf2oT5ha9py9M5JrSRhvT -amount 3
Elapsed Time: 45.267 seconds
correct hash Hex: 00009fd7c59b830b60ec21ade7672921d2fb0962a1b06a42c245450e47582a13 

Success!

$ java -jar blockchain-java-jar-with-dependencies.jar  getbalance -address 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD
Balance of '1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD': 21

$ java -jar blockchain-java-jar-with-dependencies.jar  getbalance -address 17crpQoWy7TEkY9UPjZ3Qt9Fc2rWPUt8KX
Balance of '17crpQoWy7TEkY9UPjZ3Qt9Fc2rWPUt8KX': 6

$ java -jar blockchain-java-jar-with-dependencies.jar  getbalance -address 12L868QZW1ySYzf2oT5ha9py9M5JrSRhvT
Balance of '12L868QZW1ySYzf2oT5ha9py9M5JrSRhvT': 3

1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUD这个地址一共收到了三份奖励：

第一次是开采创世区块；
第二次是开采区块：00005fd36a2609b43fd940577f93b8622e88e854f5ccfd70e113f763b6df69f7
第三次是开采区块：00009fd7c59b830b60ec21ade7672921d2fb0962a1b06a42c245450e47582a13

Merkle Tree

Merkle Tree（默克尔树）是这篇文章中我们需要重点讨论的一个机制。

正如我前面提到的那样，整个比特币的数据库占到了大约140G的磁盘空间。由于比特币的分布式特性，网络中的每一个节点必须是独立且自给自足的。每个比特币节点都是路由、区块链数据库、挖矿、钱包服务的功能集合。每个节点都参与全网络的路由功能，同时也可能包含其他功能。每个节点都参与验证并传播交易及区块信息，发现并维持与对等节点的连接。一个全节点（full node）包括以下四个功能：

基于Java语言构建区块链（六）—— 交易（Merkle Tree）

随着越来越多的人开始使用比特币，这条规则开始变得越来越难以遵循：让每一个人都去运行一个完整的节点不太现实。在中本聪发布的比特币白皮书中，针对这个问题提出了一个解决方案：Simplified Payment Verification (SPV)（简易支付验证）。SPV是比特币的轻量级节点，它不需要下载所有的区块链数据，也 不需要验证区块和交易数据 。相反，当SPV想要验证一笔交易的有效性时，它会从它所连接的全节点上检索所需要的一些数据。这种机制保证了在只有一个全节点的情况，可以运行多个SPV轻钱包节点。

更多有关SPV的介绍，请查看：《精通比特币（第二版）》第八章

为了使SPV成为可能，就需要有一种方法在没有全量下载区块数据的情况下，来检查一个区块是否包含了某笔交易。这就是 Merkle Tree 发挥作用的地方了。

比特币中所使用的Merkle Tree是为了获得交易的Hash值，随后这个已经被Pow（工作量证明）系统认可了的Hash值会被保存到区块头中。到目前为止，我们只是简单地计算了一个区块中每笔交易的Hash值，然后在准备Pow数据时，再对这些交易进行 SHA-256 计算。虽然这是一个用于获取区块交易唯一表示的一个不错的方式，但是这种方式不具备 Merkle Tree 的优点。

更多有关Merkle Tree的介绍，请查看：《精通比特币（第二版）》第九章

来看一下Merkle Tree的结构：

基于Java语言构建区块链（六）—— 交易（Merkle Tree）

每一个区块都会构建一个Merkle Tree，它从最底部的叶子节点开始往上构建，每一个交易的Hash就是一个叶子节点（比特币中用的双SHA256算法）。叶子节点的数量必须是偶数个，但是并不是每一个区块都能包含偶数笔交易数据。如果存在奇数笔交易数据，那么最后一笔交易数据将会被复制一份（这仅仅发生在Merkle Tree中，而不是区块中）。

从下往上移动，叶子节点成对分组，它们的Hash值被连接到一起，并且在此基础上再次计算出新的Hash值。新的Hash 形成新的树节点。这个过程不断地被重复，直到最后仅剩一个被称为根节点的树节点。这个根节点的Hash就是区块中交易数据们的唯一代表，它会被保存到区块头中，并被用于参与POW系统的计算。

Merkle树的好处是节点可以在不下载整个块的情况下验证某笔交易的合法性。为此，只需要交易Hash，Merkle树根Hash和Merkle路径。

Merkle Tree代码实现如下：

package one.wangwei.blockchain.transaction;

import com.google.common.collect.Lists;
import lombok.Data;
import one.wangwei.blockchain.util.ByteUtils;
import org.apache.commons.codec.digest.DigestUtils;

import java.util.List;

/**
 * 默克尔树
 *
 * @author wangwei
 * @date 2018/04/15
 */
@Data
public class MerkleTree {

    /**
     * 根节点
     */
    private Node root;
    /**
     * 叶子节点Hash
     */
    private byte[][] leafHashes;

    public MerkleTree(byte[][] leafHashes) {
        constructTree(leafHashes);
    }

    /**
     * 从底部叶子节点开始往上构建整个Merkle Tree
     *
     * @param leafHashes
     */
    private void constructTree(byte[][] leafHashes) {
        if (leafHashes == null || leafHashes.length < 1) {
            throw new RuntimeException("ERROR:Fail to construct merkle tree ! leafHashes data invalid ! ");
        }
        this.leafHashes = leafHashes;
        List<Node> parents = bottomLevel(leafHashes);
        while (parents.size() > 1) {
            parents = internalLevel(parents);
        }
        root = parents.get(0);
    }

    /**
     * 构建一个层级节点
     *
     * @param children
     * @return
     */
    private List<Node> internalLevel(List<Node> children) {
        List<Node> parents = Lists.newArrayListWithCapacity(children.size() / 2);
        for (int i = 0; i < children.size() - 1; i += 2) {
            Node child1 = children.get(i);
            Node child2 = children.get(i + 1);

            Node parent = constructInternalNode(child1, child2);
            parents.add(parent);
        }

        // 内部节点奇数个，只对left节点进行计算
        if (children.size() % 2 != 0) {
            Node child = children.get(children.size() - 1);
            Node parent = constructInternalNode(child, null);
            parents.add(parent);
        }

        return parents;
    }

    /**
     * 底部节点构建
     *
     * @param hashes
     * @return
     */
    private List<Node> bottomLevel(byte[][] hashes) {
        List<Node> parents = Lists.newArrayListWithCapacity(hashes.length / 2);

        for (int i = 0; i < hashes.length - 1; i += 2) {
            Node leaf1 = constructLeafNode(hashes[i]);
            Node leaf2 = constructLeafNode(hashes[i + 1]);

            Node parent = constructInternalNode(leaf1, leaf2);
            parents.add(parent);
        }

        if (hashes.length % 2 != 0) {
            Node leaf = constructLeafNode(hashes[hashes.length - 1]);
            // 奇数个节点的情况，复制最后一个节点
            Node parent = constructInternalNode(leaf, leaf);
            parents.add(parent);
        }

        return parents;
    }

    /**
     * 构建叶子节点
     *
     * @param hash
     * @return
     */
    private static Node constructLeafNode(byte[] hash) {
        Node leaf = new Node();
        leaf.hash = hash;
        return leaf;
    }

    /**
     * 构建内部节点
     *
     * @param leftChild
     * @param rightChild
     * @return
     */
    private Node constructInternalNode(Node leftChild, Node rightChild) {
        Node parent = new Node();
        if (rightChild == null) {
            parent.hash = leftChild.hash;
        } else {
            parent.hash = internalHash(leftChild.hash, rightChild.hash);
        }
        parent.left = leftChild;
        parent.right = rightChild;
        return parent;
    }

    /**
     * 计算内部节点Hash
     *
     * @param leftChildHash
     * @param rightChildHash
     * @return
     */
    private byte[] internalHash(byte[] leftChildHash, byte[] rightChildHash) {
        byte[] mergedBytes = ByteUtils.merge(leftChildHash, rightChildHash);
        return DigestUtils.sha256(mergedBytes);
    }

    /**
     * Merkle Tree节点
     */
    @Data
    public static class Node {
        private byte[] hash;
        private Node left;
        private Node right;
    }

}

然后修改 Block.hashTransaction 接口：

public class Block {
    
   ... 

   /**
     * 对区块中的交易信息进行Hash计算
     *
     * @return
     */
    public byte[] hashTransaction() {
        byte[][] txIdArrays = new byte[this.getTransactions().length][];
        for (int i = 0; i < this.getTransactions().length; i++) {
            txIdArrays[i] = this.getTransactions()[i].hash();
        }
        return new MerkleTree(txIdArrays).getRoot().getHash();
    }
    
    ...
	
}

MerkleTree的根节点的Hash值，就是区块中交易信息的唯一代表。

小结

这一节我们主要是对前面的交易机制做了进一步的优化，加入UTXO池和Merkle Tree机制。

下一讲，我们来介绍一下比特币的交易脚本相关的内容。

资料

源码： https://github.com/wangweiX/blockchain-java/tree/part6-transaction2
《精通比特币（第二版）》
The UTXO Set :_Data_Storage#The_UTXO set .28chainstate_leveldb.29)
UTXO set statistics
Merkle Tree
Why every Bitcoin user should understand “SPV security”
Script
“Ultraprune” Bitcoin Core commit
Smart contracts and Bitcoin

基于Java语言构建区块链（六）—— 交易（Merkle Tree）

https://press.one/file/v?s=26e600c30e75eaa13e96be514125b88979ee8ec589372b3f60eb5e3d6884f3e35992f70a44875916b4efc8d87f3021bbf4dea9c23253a8496120b75cc47a6cb30&h=5da52a1d62de45729187a3eed46039f776095760c0848e670140ced8c3c0c32a&a=23fe9bfd7ceef4b44c2ce44dcac8e4a49caf8026&f=P1&v=2

原文 https://wangwei.one/posts/630e7ae5.html

正文到此结束