摘要：截止年月號(hào)，比特幣中有個(gè)區(qū)塊，并且這些數(shù)據(jù)占據(jù)了的磁盤空間。每個(gè)比特幣節(jié)點(diǎn)都是路由區(qū)塊鏈數(shù)據(jù)庫(kù)挖礦錢包服務(wù)的功能集合。是比特幣的輕量級(jí)節(jié)點(diǎn)，它不需要下載所有的區(qū)塊鏈數(shù)據(jù)，也不需要驗(yàn)證區(qū)塊和交易數(shù)據(jù)。

最終內(nèi)容請(qǐng)以原文為準(zhǔn)：https://wangwei.one/posts/630...

在這一系列文章的最開始部分，我們提到過區(qū)塊鏈?zhǔn)且粋€(gè)分布式的數(shù)據(jù)庫(kù)。那時(shí)候，我們決定跳過"分布式"這一環(huán)節(jié)，并且聚焦于"數(shù)據(jù)存儲(chǔ)"這一環(huán)節(jié)。到目前為止，我們幾乎實(shí)現(xiàn)了區(qū)塊鏈的所有組成部分。在本篇文章中，我們將會(huì)涉及一些在前面的文章中所忽略的一些機(jī)制，并且在下一篇文章中我們將開始研究區(qū)塊鏈的分布式特性。

前面各個(gè)部分內(nèi)容：

基本原型

工作量證明

持久化 & 命令行

交易（UTXO）

地址（錢包）

在 持久化 & 命令行 這篇文章中，我們研究了比特幣核心存儲(chǔ)區(qū)塊的方式。當(dāng)中我們提到過與區(qū)塊相關(guān)的數(shù)據(jù)存儲(chǔ)在 blocks 這個(gè)數(shù)據(jù)桶中，而交易數(shù)據(jù)則存儲(chǔ)在 chainstate 這個(gè)數(shù)據(jù)桶中，讓我們來回憶一下，chainstate 數(shù)據(jù)桶的數(shù)據(jù)結(jié)構(gòu)：

"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

數(shù)據(jù)庫(kù)所表示的UTXO的區(qū)塊Hash

從那篇文章開始，我們已經(jīng)實(shí)現(xiàn)了比特幣的交易機(jī)制，但是我們還沒有用到 chainstate 數(shù)據(jù)桶去存儲(chǔ)我們的交易輸出。所以，這將是我們現(xiàn)在要去做的事情。

chainstate 不會(huì)去存儲(chǔ)交易數(shù)據(jù)。相反，它存儲(chǔ)的是 UTXO 集，也就是未被花費(fèi)的交易輸出集合。除此之外，它還存儲(chǔ)了"數(shù)據(jù)庫(kù)所表示的UTXO的區(qū)塊Hash"，我們這里先暫且忽略這一點(diǎn)，因?yàn)槲覀冞€沒有用到區(qū)塊高度（這一點(diǎn)我們會(huì)在后面的文章進(jìn)行實(shí)現(xiàn)）。

那么，我們?yōu)槭裁葱枰?UTXO 池呢？

一起來看一下我們前面實(shí)現(xiàn)的 findUnspentTransactions 方法：

   /**
     * 查找錢包地址對(duì)應(yīng)的所有未花費(fèi)的交易
     *
     * @param pubKeyHash 錢包公鑰Hash
     * @return
     */
    private Transaction[] findUnspentTransactions(byte[] pubKeyHash) throws Exception {
        Map allSpentTXOs = this.getAllSpentTXOs(pubKeyHash);
        Transaction[] unspentTxs = {};

        // 再次遍歷所有區(qū)塊中的交易輸出
        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;
    }

該方法是用來查找錢包地址對(duì)應(yīng)的包含未花費(fèi)交易輸出的交易信息。由于交易信息是存儲(chǔ)在區(qū)塊當(dāng)中，所以我們現(xiàn)有的做法是遍歷區(qū)塊鏈中的每個(gè)區(qū)塊，然后遍歷每個(gè)區(qū)塊中的交易信息，再然后遍歷每個(gè)交易中的交易輸出，并檢查交易輸出是否被相應(yīng)的錢包地址所鎖定，效率非常低下。截止2018年3月29號(hào)，比特幣中有 515698 個(gè)區(qū)塊，并且這些數(shù)據(jù)占據(jù)了140+Gb 的磁盤空間。這也就意味著一個(gè)人必須運(yùn)行全節(jié)點(diǎn)（下載所有的區(qū)塊數(shù)據(jù)）才能驗(yàn)證交易信息。此外，驗(yàn)證交易信息需要遍歷所有的區(qū)塊。

針對(duì)這個(gè)問題的解決辦法是需要有一個(gè)存儲(chǔ)了所有UTXOs（未花費(fèi)交易輸出）的索引，這就是 UTXOs 池所要做的事情：UTXOs池其實(shí)是一個(gè)緩存空間，它所緩存的數(shù)據(jù)需要從構(gòu)建區(qū)塊鏈中所有的交易數(shù)據(jù)中獲得（通過遍歷所有的區(qū)塊鏈，不過這個(gè)構(gòu)建操作只需要執(zhí)行一次即可），并且它后續(xù)還會(huì)用于錢包余額的計(jì)算以及新的交易數(shù)據(jù)的驗(yàn)證。截止到2017年9月，UTXOs池大約為 2.7Gb。

好了，讓我們來想一下，為了實(shí)現(xiàn) UTXOs 池我們需要做哪些事情。當(dāng)前，有下列方法被用于查找交易信息：

Blockchain.getAllSpentTXOs —— 查詢所有已被花費(fèi)的交易輸出。它需要遍歷區(qū)塊鏈中所有區(qū)塊中交易信息。

Blockchain.findUnspentTransactions —— 查詢包含未被花費(fèi)的交易輸出的交易信息。它也需要遍歷區(qū)塊鏈中所有區(qū)塊中交易信息。

Blockchain.findSpendableOutputs —— 該方法用于新的交易創(chuàng)建之時(shí)。它需要找到足夠多的交易輸出，以滿足所需支付的金額。需要調(diào)用 Blockchain.findUnspentTransactions 方法。

Blockchain.findUTXO —— 查詢錢包地址所對(duì)應(yīng)的所有未花費(fèi)交易輸出，然后用于計(jì)算錢包余額。需要調(diào)用

Blockchain.findUnspentTransactions 方法。

Blockchain.findTransaction —— 通過交易ID查詢交易信息。它需要遍歷所有的區(qū)塊直到找到交易信息為止。

如你所見，上面這些方法都需要去遍歷數(shù)據(jù)庫(kù)中的所有區(qū)塊。由于UTXOs池只存儲(chǔ)未被花費(fèi)的交易輸出，而不會(huì)存儲(chǔ)所有的交易信息，因此我們不會(huì)對(duì)有 Blockchain.findTransaction 進(jìn)行優(yōu)化。

那么，我們需要下列這些方法：

Blockchain.findUTXO —— 通過遍歷所有的區(qū)塊來找到所有未被花費(fèi)的交易輸出.

UTXOSet.reindex —— 調(diào)用上面 findUTXO 方法，然后將查詢結(jié)果存儲(chǔ)在數(shù)據(jù)庫(kù)中。也即需要進(jìn)行緩存的地方。

UTXOSet.findSpendableOutputs —— 與 Blockchain.findSpendableOutputs 類似，區(qū)別在于會(huì)使用 UTXO 池。

UTXOSet.findUTXO —— 與Blockchain.findUTXO 類似，區(qū)別在于會(huì)使用 UTXO 池。

Blockchain.findTransaction —— 邏輯保持不變。

這樣，兩個(gè)使用最頻繁的方法將從現(xiàn)在開始使用緩存！讓我們開始編碼吧！

定義 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 allUTXOs = blockchain.findAllUTXOs();
        for (Map.Entry entry : allUTXOs.entrySet()) {
            RocksDBUtils.getInstance().putUTXOs(entry.getKey(), entry.getValue());
        }
        log.info("ReIndex UTXO set finished ! ");
    }
    
    ...
}    

此方法用于初始化 UTXOSet。首先，需要清空 chainstate 數(shù)據(jù)桶，然后查詢所有未被花費(fèi)的交易輸出，并將它們保存到 chainstate 數(shù)據(jù)桶中。

實(shí)現(xiàn) findSpendableOutputs 方法，供 Transation.newUTXOTransaction 調(diào)用

public class UTXOSet {
 
   ... 
 
   /**
     * 尋找能夠花費(fèi)的交易
     *
     * @param pubKeyHash 錢包公鑰Hash
     * @param amount     花費(fèi)金額
     */
    public SpendableOutputResult findSpendableOutputs(byte[] pubKeyHash, int amount) {
        Map unspentOuts = Maps.newHashMap();
        int accumulated = 0;
        Map chainstateBucket = RocksDBUtils.getInstance().getChainstateBucket();
        for (Map.Entry 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);
    }
    
    ...
    
}    

實(shí)現(xiàn) findUTXOs 接口，供 CLI.getBalance 調(diào)用：

public class UTXOSet {
 
   ... 
 
   /**
     * 查找錢包地址對(duì)應(yīng)的所有UTXO
     *
     * @param pubKeyHash 錢包公鑰Hash
     * @return
     */
    public TXOutput[] findUTXOs(byte[] pubKeyHash) {
        TXOutput[] utxos = {};
        Map 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 中相應(yīng)方法的微調(diào)版，先前的方法將不再使用。

有了UTXO池之后，意味著我們的交易數(shù)據(jù)分開存儲(chǔ)到了兩個(gè)不同的數(shù)據(jù)桶中：交易數(shù)據(jù)存儲(chǔ)到了 block 數(shù)據(jù)桶中，而UTXO存儲(chǔ)到了 chainstate 數(shù)據(jù)桶中。這就需要一種同步機(jī)制來保證每當(dāng)一個(gè)新的區(qū)塊產(chǎn)生時(shí)，UTXO池能夠及時(shí)同步最新區(qū)塊中的交易數(shù)據(jù)，畢竟我們不想頻地進(jìn)行 reIndex 。因此，我們需要如下方法：

更新UTXO池：

public class UTXOSet {
 
   ... 

   /**
     * 更新UTXO池
     * 

     * 當(dāng)一個(gè)新的區(qū)塊產(chǎn)生時(shí)，需要去做兩件事情：
     * 1）從UTXO池中移除花費(fèi)掉了的交易輸出；
     * 2）保存新的未花費(fèi)交易輸出；
     *
     * @param tipBlock 最新的區(qū)塊
     */
    @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()) {

            // 根據(jù)交易輸入排查出剩余未被使用的交易輸出
            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 {

   ...

   /**
     * 創(chuàng)建區(qū)塊鏈
     *
     * @param address
     */
    private void createBlockchain(String address) {
        Blockchain blockchain = Blockchain.createBlockchain(address);
        UTXOSet utxoSet = new UTXOSet(blockchain);
        utxoSet.reIndex();
        log.info("Done ! ");
    }
    
    ...
    
}    

當(dāng)創(chuàng)建一個(gè)新的區(qū)塊鏈?zhǔn)牵覀冃枰亟?UTXO 池索引。截止目前，這是唯一一處用到 reIndex 的地方，盡管看起有些多余，因?yàn)樵趨^(qū)塊鏈創(chuàng)建之初僅僅只有一個(gè)區(qū)塊和一筆交易。

修改 CLI.send 接口：

public class CLI {
    
    ...

   /**
     * 轉(zhuǎn)賬
     *
     * @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);
        
        ...
    }
    
    ...
    
}    

當(dāng)一個(gè)新的區(qū)塊產(chǎn)生后，需要去更新 UTXO 池?cái)?shù)據(jù)。

讓我們來檢查一下它們的運(yùn)行情況：

$ 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

前面的章節(jié)中我們省略了礦工挖礦的獎(jiǎng)勵(lì)機(jī)制。時(shí)機(jī)已經(jīng)成熟，該實(shí)現(xiàn)它了。

礦工獎(jiǎng)勵(lì)其實(shí)是一個(gè) coinbase 交易（創(chuàng)幣交易）。當(dāng)一個(gè)礦工節(jié)點(diǎn)開始去生產(chǎn)一個(gè)新的區(qū)塊時(shí)，他會(huì)從隊(duì)列中取出一些交易數(shù)據(jù)，并且為它們預(yù)制一個(gè) coinbase 交易。這筆 coinbase 交易中僅有的交易輸出包含了礦工的公鑰hash。

只需要更新 send 命令接口，我們就可以輕松實(shí)現(xiàn)礦工的獎(jiǎng)勵(lì)機(jī)制：

public class CLI {
    
    ...

   /**
     * 轉(zhuǎn)賬
     *
     * @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);
        // 獎(jiǎng)勵(lì)
        Transaction rewardTx = Transaction.newCoinbaseTX(from, "");
        Block newBlock = blockchain.mineBlock(new Transaction[]{transaction, rewardTx});
        new UTXOSet(blockchain).update(newBlock);
        
        ...
    }
    
    ...
        
} 

還需要修改交易驗(yàn)證方法，coinbase 交易直接驗(yàn)證通過：

public class Blockchain {
    
  /**
     * 交易簽名驗(yàn)證
     *
     * @param tx
     */
    private boolean verifyTransactions(Transaction tx) {
        if (tx.isCoinbase()) {
            return true;
        }
    
        ...
    }
    
    ...
    
}    

在我們的實(shí)現(xiàn)邏輯中，代幣的發(fā)送也是區(qū)塊的生產(chǎn)者，因此，獎(jiǎng)勵(lì)也歸他所有。

讓我們來驗(yàn)證一下獎(jiǎng)勵(lì)機(jī)制：

$ 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 這個(gè)地址一共收到了三份獎(jiǎng)勵(lì)：

第一次是開采創(chuàng)世區(qū)塊；

第二次是開采區(qū)塊：00005fd36a2609b43fd940577f93b8622e88e854f5ccfd70e113f763b6df69f7

第三次是開采區(qū)塊：00009fd7c59b830b60ec21ade7672921d2fb0962a1b06a42c245450e47582a13

Merkle Tree（默克爾樹） 是這篇文章中我們需要重點(diǎn)討論的一個(gè)機(jī)制。

正如我前面提到的那樣，整個(gè)比特幣的數(shù)據(jù)庫(kù)占到了大約140G的磁盤空間。由于比特幣的分布式特性，網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)必須是獨(dú)立且自給自足的。每個(gè)比特幣節(jié)點(diǎn)都是路由、區(qū)塊鏈數(shù)據(jù)庫(kù)、挖礦、錢包服務(wù)的功能集合。每個(gè)節(jié)點(diǎn)都參與全網(wǎng)絡(luò)的路由功能，同時(shí)也可能包含其他功能。每個(gè)節(jié)點(diǎn)都參與驗(yàn)證并傳播交易及區(qū)塊信息，發(fā)現(xiàn)并維持與對(duì)等節(jié)點(diǎn)的連接。一個(gè)全節(jié)點(diǎn)（full node）包括以下四個(gè)功能：

隨著越來越多的人開始使用比特幣，這條規(guī)則開始變得越來越難以遵循：讓每一個(gè)人都去運(yùn)行一個(gè)完整的節(jié)點(diǎn)不太現(xiàn)實(shí)。在中本聰發(fā)布的 比特幣白皮書 中，針對(duì)這個(gè)問題提出了一個(gè)解決方案：Simplified Payment Verification (SPV)（簡(jiǎn)易支付驗(yàn)證）。SPV是比特幣的輕量級(jí)節(jié)點(diǎn)，它不需要下載所有的區(qū)塊鏈數(shù)據(jù)，也不需要驗(yàn)證區(qū)塊和交易數(shù)據(jù)。相反，當(dāng)SPV想要驗(yàn)證一筆交易的有效性時(shí)，它會(huì)從它所連接的全節(jié)點(diǎn)上檢索所需要的一些數(shù)據(jù)。這種機(jī)制保證了在只有一個(gè)全節(jié)點(diǎn)的情況，可以運(yùn)行多個(gè)SPV輕錢包節(jié)點(diǎn)。

更多有關(guān)SPV的介紹，請(qǐng)查看：《精通比特幣（第二版）》第八章

為了使SPV成為可能，就需要有一種方法在沒有全量下載區(qū)塊數(shù)據(jù)的情況下，來檢查一個(gè)區(qū)塊是否包含了某筆交易。這就是 Merkle Tree 發(fā)揮作用的地方了。

比特幣中所使用的Merkle Tree是為了獲得交易的Hash值，隨后這個(gè)已經(jīng)被Pow（工作量證明）系統(tǒng)認(rèn)可了的Hash值會(huì)被保存到區(qū)塊頭中。到目前為止，我們只是簡(jiǎn)單地計(jì)算了一個(gè)區(qū)塊中每筆交易的Hash值，然后在準(zhǔn)備Pow數(shù)據(jù)時(shí)，再對(duì)這些交易進(jìn)行 SHA-256 計(jì)算。雖然這是一個(gè)用于獲取區(qū)塊交易唯一表示的一個(gè)不錯(cuò)的途徑，但是它不具有到 Merkle Tree的優(yōu)點(diǎn)。

來看一下Merkle Tree的結(jié)構(gòu)：

每一個(gè)區(qū)塊都會(huì)構(gòu)建一個(gè)Merkle Tree，它從最底部的葉子節(jié)點(diǎn)開始往上構(gòu)建，每一個(gè)交易的Hash就是一個(gè)葉子節(jié)點(diǎn)（比特幣中用的雙SHA256算法）。葉子節(jié)點(diǎn)的數(shù)量必須是偶數(shù)個(gè)，但是并不是每一個(gè)區(qū)塊都能包含偶數(shù)筆交易數(shù)據(jù)。如果存在奇數(shù)筆交易數(shù)據(jù)，那么最后一筆交易數(shù)據(jù)將會(huì)被復(fù)制一份（這僅僅發(fā)生在Merkle Tree中，而不是區(qū)塊中）。

從下往上移動(dòng)，葉子節(jié)點(diǎn)成對(duì)分組，它們的Hash值被連接到一起，并且在此基礎(chǔ)上再次計(jì)算出新的Hash值。新的Hash 形成新的樹節(jié)點(diǎn)。這個(gè)過程不斷地被重復(fù)，直到最后僅剩一個(gè)被稱為根節(jié)點(diǎn)的樹節(jié)點(diǎn)。這個(gè)根節(jié)點(diǎn)的Hash就是區(qū)塊中交易數(shù)據(jù)們的唯一代表，它會(huì)被保存到區(qū)塊頭中，并被用于參與POW系統(tǒng)的計(jì)算。

Merkle樹的好處是節(jié)點(diǎn)可以在不下載整個(gè)塊的情況下驗(yàn)證某筆交易的合法性。 為此，只需要交易Hash，Merkle樹根Hash和Merkle路徑。

Merkle Tree代碼實(shí)現(xiàn)如下：

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 {

    /**
     * 根節(jié)點(diǎn)
     */
    private Node root;
    /**
     * 葉子節(jié)點(diǎn)Hash
     */
    private byte[][] leafHashes;

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

    /**
     * 從底部葉子節(jié)點(diǎn)開始往上構(gòu)建整個(gè)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 parents = bottomLevel(leafHashes);
        while (parents.size() > 1) {
            parents = internalLevel(parents);
        }
        root = parents.get(0);
    }

    /**
     * 構(gòu)建一個(gè)層級(jí)節(jié)點(diǎn)
     *
     * @param children
     * @return
     */
    private List internalLevel(List children) {
        List 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);
        }

        // 內(nèi)部節(jié)點(diǎn)奇數(shù)個(gè)，只對(duì)left節(jié)點(diǎn)進(jìn)行計(jì)算
        if (children.size() % 2 != 0) {
            Node child = children.get(children.size() - 1);
            Node parent = constructInternalNode(child, null);
            parents.add(parent);
        }

        return parents;
    }

    /**
     * 底部節(jié)點(diǎn)構(gòu)建
     *
     * @param hashes
     * @return
     */
    private List bottomLevel(byte[][] hashes) {
        List 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]);
            // 奇數(shù)個(gè)節(jié)點(diǎn)的情況，復(fù)制最后一個(gè)節(jié)點(diǎn)
            Node parent = constructInternalNode(leaf, leaf);
            parents.add(parent);
        }

        return parents;
    }

    /**
     * 構(gòu)建葉子節(jié)點(diǎn)
     *
     * @param hash
     * @return
     */
    private static Node constructLeafNode(byte[] hash) {
        Node leaf = new Node();
        leaf.hash = hash;
        return leaf;
    }

    /**
     * 構(gòu)建內(nèi)部節(jié)點(diǎn)
     *
     * @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;
    }

    /**
     * 計(jì)算內(nèi)部節(jié)點(diǎn)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節(jié)點(diǎn)
     */
    @Data
    public static class Node {
        private byte[] hash;
        private Node left;
        private Node right;
    }

}

然后修改 Block.hashTransaction 接口：

public class Block {
    
   ... 

   /**
     * 對(duì)區(qū)塊中的交易信息進(jìn)行Hash計(jì)算
     *
     * @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的根節(jié)點(diǎn)的Hash值，就是區(qū)塊中交易信息的唯一代表。

這一節(jié)我們主要是對(duì)前面的交易機(jī)制做了進(jìn)一步的優(yōu)化，加入U(xiǎn)TXO池和Merkle Tree機(jī)制。

源碼：https://github.com/wangweiX/b...

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