八月中秋白露，路上行人凄涼。
小橋明月桂花香纷闺，日夜千思萬想刨仑。
心中萬般寧靜涵防，青春好讀文章。
十年苦讀在書房，方見才學(xué)益廣。

最近要自己實現(xiàn)一個區(qū)塊鏈园欣，其中區(qū)塊體用到MerkleTree，找了好久終于找到了一個可以看懂的實現(xiàn)—_—

簡單來說就是每筆交易的hash都兩兩結(jié)合最后生成跟(root)hash休蟹，結(jié)構(gòu)圖如下：

image.png

話不多說懂的懂沸枯，不懂的看代碼也會懂，如果跟作者一樣沒有天分赂弓，那就復(fù)制代碼打斷點運(yùn)行一步一步看也會懂

package cn.cnic.chain.merkle;

import org.springframework.util.CollectionUtils;

import java.security.MessageDigest;
import java.util.ArrayList;
import java.util.List;

/**
 * java實現(xiàn)默克爾樹
 */
public class MerkleTrees {

    // MerkleRoot
    private String root;

    // 交易集合
    private List<String> txList;

    /**
     * 構(gòu)造方法
     * 初始化所有txid , root設(shè)置成""
     */
    public MerkleTrees(List<String> txList) {
        this.txList = txList;
        root = "";
    }

    /**
     * 根據(jù)txid動態(tài)求出root
     */
    public void merkle_tree() {

        if (CollectionUtils.isEmpty(txList)){
            return;
        }

        List<String> tempTxList = new ArrayList<>();

//        for (int i = 0; i < this.txList.size(); i++) {
//            tempTxList.add(this.txList.get(i));
//        }
        tempTxList.addAll(txList);

        //不是是否可以直接把參數(shù)設(shè)置為 txList
        List<String> newTxList = getNewTxList(tempTxList);

        //執(zhí)行循環(huán)绑榴，直到只剩下一個hash值
        while (newTxList.size() != 1) {
            newTxList = getNewTxList(newTxList);
        }

        this.root = newTxList.get(0);
    }

    /**
     * 求出上一層所有節(jié)點hash
     *
     * @param tempTxList
     * @return
     */
    private List<String> getNewTxList(List<String> tempTxList) {

        List<String> newTxList = new ArrayList<>();
        int index = 0;
        while (index < tempTxList.size()) {
            // left
            String left = tempTxList.get(index);
            index++;
            // right
            String right = "";
            if (index != tempTxList.size()) {
                right = tempTxList.get(index);
            }
            // parent = left + right
            String sha2HexValue = getSHA2HexValue(left + right);
            newTxList.add(sha2HexValue);
            index++;

        }
        return newTxList;
    }

    /**
     * left 、right 求出具體的父類節(jié)點hash
     *
     * @param str
     * @return
     */
    public String getSHA2HexValue(String str) {
        byte[] cipher_byte;
        try{
            MessageDigest md = MessageDigest.getInstance("SHA-256");
            md.update(str.getBytes());
            cipher_byte = md.digest();
            StringBuilder sb = new StringBuilder(2 * cipher_byte.length);
            for(byte b: cipher_byte) {
                sb.append(String.format("%02x", b&0xff) );
            }
            return sb.toString();
        } catch (Exception e) {
            e.printStackTrace();
        }

        return "";
    }

    /**
     * 獲取跟節(jié)點hash
     * @return
     */
    public String getRoot() {
        return this.root;
    }
}

測試方法如下：

package cn.cnic.chain.merkle;

import java.util.ArrayList;
import java.util.List;

/**
 * 構(gòu)建MerkleTree測試類
 */
public class App {
    public static void main(String[] args) {
        List<String> tempTxList = new ArrayList<>();
        tempTxList.add("a");
        tempTxList.add("b");
        tempTxList.add("c");
        tempTxList.add("d");
        tempTxList.add("e");

        MerkleTrees merkleTrees = new MerkleTrees(tempTxList);
        merkleTrees.merkle_tree();

        System.out.println("root : " + merkleTrees.getRoot());

    }
}