备案控制台
探索云世界
开发者社区 数据库 文章 正文

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

2018-04-17 1527
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 最终内容请以原文为准：https://wangwei.one/posts/630e7ae5.html 引言 在这一系列文章的最开始部分，我们提到过区块链是一个分布式的数据库。那时候，我们决定跳过"分布式"这一环节，并且聚焦于"数据存储"这一环节。

最终内容请以原文为准：https://wangwei.one/posts/630e7ae5.html

引言

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

前面各个部分内容：

  1. [基本原型]
  2. [工作量证明]
  3. [持久化 & 命令行]
  4. [交易（UTXO）]
  5. [地址（钱包）]

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 池我们需要做哪些事情。当前，有下列方法被用于查找交易信息：

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

Blockchain.findUnspentTransactions 方法。

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

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

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

  1. Blockchain.findUTXO —— 通过遍历所有的区块来找到所有未被花费的交易输出.
  2. UTXOSet.reindex —— 调用上面 findUTXO 方法，然后将查询结果存储在数据库中。也即需要进行缓存的地方。
  3. UTXOSet.findSpendableOutputs —— 与 Blockchain.findSpendableOutputs 类似，区别在于会使用 UTXO 池。
  4. UTXOSet.findUTXO —— 与Blockchain.findUTXO 类似，区别在于会使用 UTXO 池。
  5. 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）包括以下四个功能：

full node

随着越来越多的人开始使用比特币，这条规则开始变得越来越难以遵循：让每一个人都去运行一个完整的节点不太现实。在中本聪发布的 比特币白皮书 中，针对这个问题提出了一个解决方案：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，它从最底部的叶子节点开始往上构建，每一个交易的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机制。

资料

  1. 源码：https://github.com/wangweiX/blockchain-java/tree/part6-transaction2
  2. The UTXO Set:_Data_Storage#The_UTXO_set_.28chainstate_leveldb.29)
  3. UTXO set statistics
  4. Merkle Tree
  5. Why every Bitcoin user should understand “SPV security”
  6. Script
  7. “Ultraprune” Bitcoin Core commit
  8. Smart contracts and Bitcoin
文章标签：
Java
存储
区块链
数据库
缓存
关键词：
Java语言
Java构建
构建区块链
Java交易
区块链交易
王维_hz
目录
相关文章
游客uul6wusao3sds
|
16天前
|
移动开发 Java Android开发
构建高效Android应用：探究Kotlin与Java的性能差异
【4月更文挑战第3天】在移动开发领域，性能优化一直是开发者关注的焦点。随着Kotlin的兴起，其在Android开发中的地位逐渐上升，但关于其与Java在性能方面的对比，尚无明确共识。本文通过深入分析并结合实际测试数据，探讨了Kotlin与Java在Android平台上的性能表现，揭示了在不同场景下两者的差异及其对应用性能的潜在影响，为开发者在选择编程语言时提供参考依据。
游客uul6wusao3sds
35 4
mrq4nk6ni2neg
|
23天前
|
Java 编译器 Android开发
构建高效Android应用：探究Kotlin与Java的性能差异
在开发高性能的Android应用时，选择合适的编程语言至关重要。近年来，Kotlin因其简洁性和功能性受到开发者的青睐，但其性能是否与传统的Java相比有所不足？本文通过对比分析Kotlin与Java在Android平台上的运行效率，揭示二者在编译速度、运行时性能及资源消耗方面的具体差异，并探讨在实际项目中如何做出最佳选择。
mrq4nk6ni2neg
17 4
无糖可乐嘟嘟
|
24天前
|
数据采集 分布式计算 大数据
Java语言在大数据处理中的应用
传统的大数据处理往往依赖于庞大的数据中心和高性能的服务器，然而随着大数据时代的到来，Java作为一种强大的编程语言正在被广泛应用于大数据处理领域。本文将探讨Java语言在大数据处理中的优势和应用，以及其在分布式计算、数据处理和系统集成等方面的重要作用。
无糖可乐嘟嘟
26 5
一百减一是零
|
1天前
|
前端开发 Java Go
开发语言详解（python、java、Go(Golong)。。。。）
开发语言详解（python、java、Go(Golong)。。。。）
一百减一是零
24 0
源码宝
|
1天前
|
人工智能 前端开发 Java
Java语言开发的AI智慧导诊系统源码springboot+redis 3D互联网智导诊系统源码
智慧导诊解决盲目就诊问题，减轻分诊工作压力。降低挂错号比例，优化就诊流程，有效提高线上线下医疗机构接诊效率。可通过人体画像选择症状部位，了解对应病症信息和推荐就医科室。
源码宝
27 10
桃李春风一杯酒
|
1天前
|
消息中间件 存储 安全
从零开始构建Java消息队列系统
【4月更文挑战第18天】构建一个简单的Java消息队列系统，包括`Message`类、遵循FIFO原则的`MessageQueue`（使用`LinkedList`实现）、`Producer`和`Consumer`类。在多线程环境下，`MessageQueue`的操作通过`synchronized`保证线程安全。测试代码中，生产者发送10条消息，消费者处理这些消息。实际应用中，可能需要考虑持久化、分布式队列和消息确认等高级特性，或者使用成熟的MQ系统如Kafka或RabbitMQ。
桃李春风一杯酒
13 7
桃李春风一杯酒
|
2天前
|
消息中间件 存储 Java
深度探索：使用Apache Kafka构建高效Java消息队列处理系统
【4月更文挑战第17天】本文介绍了在Java环境下使用Apache Kafka进行消息队列处理的方法。Kafka是一个分布式流处理平台，采用发布/订阅模型，支持高效的消息生产和消费。文章详细讲解了Kafka的核心概念，包括主题、生产者和消费者，以及消息的存储和消费流程。此外，还展示了Java代码示例，说明如何创建生产者和消费者。最后，讨论了在高并发场景下的优化策略，如分区、消息压缩和批处理。通过理解和应用这些策略，可以构建高性能的消息系统。
桃李春风一杯酒
9 1
桃李春风一杯酒
|
6天前
|
Java Android开发 C++
Kotlin vs Java：选择最佳语言进行安卓开发
【4月更文挑战第13天】Java曾是安卓开发的主流语言，但Kotlin的崛起改变了这一局面。Google在2017年支持Kotlin，引发两者优劣讨论。Java以其成熟稳定、强大生态和跨平台能力占优，但代码冗长、开发效率低和语言特性过时是短板。Kotlin则以简洁语法、空安全设计和高度兼容Java脱颖而出，但社区和生态系统仍在发展中，可能存在学习曲线和性能问题。选择语言应考虑项目需求、团队熟悉度、维护性、性能和生态系统。无论选择哪种，理解其差异并适应新技术至关重要。
桃李春风一杯酒
17 4
桃李春风一杯酒
|
16天前
|
前端开发 Java API
构建RESTful API：Java中的RESTful服务开发
【4月更文挑战第3天】本文介绍了在Java环境中构建RESTful API的重要性及方法。遵循REST原则，利用HTTP方法处理资源，实现CRUD操作。在Java中，常用框架如Spring MVC简化了RESTful服务开发，包括定义资源、设计表示层、实现CRUD、考虑安全性、文档和测试。通过Spring MVC示例展示了创建RESTful服务的步骤，强调了其在现代Web服务开发中的关键角色，有助于提升互操作性和用户体验。
桃李春风一杯酒
24 2
构建RESTful API：Java中的RESTful服务开发
是阿超
|
17天前
|
Java
Java语言打印九九乘法表(详解)
Java语言打印九九乘法表(详解)
是阿超
15 1
Java语言打印九九乘法表(详解)

热门文章

最新文章

  • 1
    Java中的多线程编程：概念、实现与性能优化
  • 2
    微信小程序上传文件至阿里云OSS直传(java后端签名+前端直传)
  • 3
    推荐一款好用的Java分布式任务调度框架！
  • 4
    java智慧城管源码 AI视频智能分析 可直接上项目
  • 5
    整理Java面试题
  • 6
    Java 学习路线：基础知识、数据类型、条件语句、函数、循环、异常处理、数据结构、面向对象编程、包、文件和 API
  • 7
    Java 并发编程 面试题及答案整理，最新面试题
  • 8
    Java 面试题及答案整理，最新面试题
  • 9
    使用Java代码打印log日志
  • 10
    基于 java + Springboot + vue +mysql 大学生实习管理系统（含源码）
  • 1
    区块链DAPP质押合约代币系统开发|模式方案
    22
  • 2
    前端开发新趋势：Web3、区块链和虚拟现实
    37
  • 3
    构建未来：区块链技术在供应链管理中的应用
    20
  • 4
    智能合约：区块链世界的法则之书
    28
  • 5
    探索区块链技术的核心特性与价值
    33
  • 6
    新一代数据库技术：融合区块链与分布式存储的未来前景
    359
  • 7
    区块链钱包系统开发解决方案/需求设计/功能逻辑/案例详细/源码步骤
    31
  • 8
    区块链3D元宇宙游戏系统开发规则玩法/步骤指南/源码项目
    23
  • 9
    区块链技术在供应链管理中的应用
    39
  • 10
    基于区块链技术的数字身份认证系统设计与实现
    186

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 阿里云平台上进行Java程序的编译与运行
  • 使用Java面向对象编写网络通信程序应用
  • Elasticsearch Java API Client 开发
  • 手动部署Java Web环境（Alibaba Cloud Linux 2）
  • 搭建Java Web开发环境（Anolis OS）
  • RocketMQ中使用Java客户端发送消息和消费的应用
    • 下一篇
    阿里云oss简介和使用流程