实验 1

关键在理解伪代码，怎么弄

写一个merkle tree

实验要求：

1. 生成一个2^n个元素的集合，要求里面没有重复元素

2. 要求用数组存构建这棵树（这样简单一些）

3. hash函数选取一个，如md5或sha256、sha1

   用库，千万不要自己实现

节点三类：清节点（记录区块的头和与自己有关的节点）

证明存在

返回证据（以及他们所在左右）

自下而上构建

证明不存在

证明相邻两个存在（序号差1）

生成树的时候排好序，对输入的数组

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class MerkleTree {
    private String[] transactions;
    private String[] tree;

    public MerkleTree(String[] transactions) {
        this.transactions = transactions;
        this.tree = new String[4 * transactions.length];
        buildMerkleTree(0, 0, transactions.length - 1);
    }

    private void buildMerkleTree(int node, int start, int end) {
        if (start == end) {
            tree[node] = transactions[start];
        } else {
            int mid = (start + end) / 2;
            buildMerkleTree(2 * node + 1, start, mid);
            buildMerkleTree(2 * node + 2, mid + 1, end);
            tree[node] = hash(tree[2 * node + 1] + tree[2 * node + 2]);
        }
    }

    public boolean verifyTransaction(String transaction) {
        return verifyTransaction(transaction, 0, 0, transactions.length - 1);
    }

    private boolean verifyTransaction(String transaction, int node, int start, int end) {
        if (start == end) {
            return tree[node].equals(transaction);
        } else {
            int mid = (start + end) / 2;
            if (verifyTransaction(transaction, 2 * node + 1, start, mid)) {
                return true;
            }
            if (verifyTransaction(transaction, 2 * node + 2, mid + 1, end)) {
                return true;
            }
            return false;
        }
    }

    private String hash(String input) {
        try {
            MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
            byte[] hash = messageDigest.digest(input.getBytes());
            StringBuilder hexString = new StringBuilder();
            for (byte b : hash) {
                String hex = Integer.toHexString(0xff & b);
                if (hex.length() == 1) hexString.append('0');
                hexString.append(hex);
            }
            return hexString.toString();
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
    }
}