當(dāng)前位置：首頁(yè) > 编程语言 > java >内容正文

java

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

發(fā)布時(shí)間：2025/3/21 java 48 豆豆

生活随笔收集整理的這篇文章主要介紹了基于Java语言构建区块链（六）—— 交易（Merkle Tree）小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

基于Java語(yǔ)言構(gòu)建區(qū)塊鏈（六）—— 交易（Merkle Tree）

2018年04月16日 10:21:35?wangwei_hz?閱讀數(shù)：480更多

個(gè)人分類(lèi)：?區(qū)塊鏈比特幣bitcoin

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

引言

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

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

基本原型

工作量證明

持久化 & 命令行

交易（UTXO）

地址（錢(qián)包）

UTXO池

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

從那篇文章開(kāi)始，我們已經(jīng)實(shí)現(xiàn)了比特幣的交易機(jī)制，但是我們還沒(méi)有用到?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)槲覀冞€沒(méi)有用到區(qū)塊高度（這一點(diǎn)我們會(huì)在后面的文章進(jìn)行實(shí)現(xiàn)）。

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

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

/*** 查找錢(qián)包地址對(duì)應(yīng)的所有未花費(fèi)的交易** @param pubKeyHash 錢(qián)包公鑰Hash* @return*/private Transaction[] findUnspentTransactions(byte[] pubKeyHash) throws Exception {Map<String, int[]> 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;}

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

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

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

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

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

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

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

Blockchain.findUnspentTransactions?方法。

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

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

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

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

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

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

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

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

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

定義?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?數(shù)據(jù)桶，然后查詢(xún)所有未被花費(fèi)的交易輸出，并將它們保存到?chainstate?數(shù)據(jù)桶中。

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

public class UTXOSet {... /*** 尋找能夠花費(fèi)的交易** @param pubKeyHash 錢(qián)包公鑰Hash* @param amount 花費(fèi)金額*/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);}...}

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

public class UTXOSet {... /*** 查找錢(qián)包地址對(duì)應(yīng)的所有UTXO** @param pubKeyHash 錢(qián)包公鑰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?中相應(yīng)方法的微調(diào)版，先前的方法將不再使用。

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

更新UTXO池：

public class UTXOSet {... /*** 更新UTXO池* <p>* 當(dāng)一個(gè)新的區(qū)塊產(chǎn)生時(shí)，需要去做兩件事情：* 1）從UTXO池中移除花費(fèi)掉了的交易輸出；* 2）保存新的未花費(fèi)交易輸出；** @param tipBlock 最新的區(qū)塊*/@Synchronizedpublic 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]);}}// 沒(méi)有剩余則刪除，否則更新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)?#xff0c;我們需要重建 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ù)。

讓我們來(lái)檢查一下它們的運(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 1JgppX2xMshr35wHzvNWQBejUAZ3Te5MdfElapsed 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ǎng)勵(lì)機(jī)制

前面的章節(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)開(kāi)始去生產(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)證通過(guò)：

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ì)也歸他所有。

讓我們來(lái)驗(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 1MpdtjTEsDvrkrLWmMswq4K3VPtevXXnUDElapsed 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ì)：

第一次是開(kāi)采創(chuàng)世區(qū)塊；
第二次是開(kāi)采區(qū)塊：00005fd36a2609b43fd940577f93b8622e88e854f5ccfd70e113f763b6df69f7
第三次是開(kāi)采區(qū)塊：00009fd7c59b830b60ec21ade7672921d2fb0962a1b06a42c245450e47582a13

Merkle Tree

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

正如我前面提到的那樣，整個(gè)比特幣的數(shù)據(jù)庫(kù)占到了大約140G的磁盤(pán)空間。由于比特幣的分布式特性，網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)必須是獨(dú)立且自給自足的。每個(gè)比特幣節(jié)點(diǎn)都是路由、區(qū)塊鏈數(shù)據(jù)庫(kù)、挖礦、錢(qián)包服務(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è)功能：

隨著越來(lái)越多的人開(kāi)始使用比特幣，這條規(guī)則開(kāi)始變得越來(lái)越難以遵循：讓每一個(gè)人都去運(yùn)行一個(gè)完整的節(jié)點(diǎn)不太現(xiàn)實(shí)。在中本聰發(fā)布的?比特幣白皮書(shū)?中，針對(duì)這個(gè)問(wèn)題提出了一個(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輕錢(qián)包節(jié)點(diǎn)。

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

為了使SPV成為可能，就需要有一種方法在沒(méi)有全量下載區(qū)塊數(shù)據(jù)的情況下，來(lái)檢查一個(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)。

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

每一個(gè)區(qū)塊都會(huì)構(gòu)建一個(gè)Merkle Tree，它從最底部的葉子節(jié)點(diǎn)開(kāi)始往上構(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 形成新的樹(shù)節(jié)點(diǎn)。這個(gè)過(guò)程不斷地被重復(fù)，直到最后僅剩一個(gè)被稱(chēng)為根節(jié)點(diǎn)的樹(shù)節(jié)點(diǎn)。這個(gè)根節(jié)點(diǎn)的Hash就是區(qū)塊中交易數(shù)據(jù)們的唯一代表，它會(huì)被保存到區(qū)塊頭中，并被用于參與POW系統(tǒng)的計(jì)算。

Merkle樹(shù)的好處是節(jié)點(diǎn)可以在不下載整個(gè)塊的情況下驗(yàn)證某筆交易的合法性。為此，只需要交易Hash，Merkle樹(shù)根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;/*** 默克爾樹(shù)** @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)開(kāi)始往上構(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<Node> 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<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);}// 內(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<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]);// 奇數(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)*/@Datapublic 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é)

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

資料

源碼：https://github.com/wangweiX/blockchain-java/tree/part6-transaction2

The UTXO Set

UTXO set statistics

Merkle Tree

Why every Bitcoin user should understand “SPV security”

Script

“Ultraprune” Bitcoin Core commit

Smart contracts and Bitcoin

總結(jié)

以上是生活随笔為你收集整理的基于Java语言构建区块链（六）—— 交易（Merkle Tree）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇：用java写一个简单的区块链（下）
下一篇：基于Java语言构建区块链（五）—— 地