一个简单的 merkle-tree 在 java 中的实现

Question

我正在尝试用 Java 编写一个非常简单的 merkle-tree 实现。

我使用比特币区块链上第170 个区块中的 txid 值作为参考，所以我可以看到正确的结果应该是什么。

该区块对应的txid如下：

b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082

f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16

据我了解，比特币的 merkle-tree 实现方式如下：

1. 将区块中的交易拆分成对

2. 字节交换 txid

3. 连接 txid

4. 对连接的对进行双重哈希

需要注意的是：

If there's no additional pairs of txids, concatenate the result of the first pair after double hashing with itself and repeat

我写的 swapEndianness 方法不是真正的“字节级”交换，而只是改变了字符串的顺序，它看起来像这样：

public static String swapEndianness(String hash) {

        char[] hashAsCharArray = hash.toCharArray();

        StringBuilder sb = new StringBuilder();

        for (int i = hash.length() - 1; i > 0; i-=2) {

            sb.append(hashAsCharArray[i - 1]);

            sb.append(hashAsCharArray[i]);

        }

        return sb.toString();

    }

这两个 txid 的默克尔根的预期结果是：

7dac2c5666815c17a3b36427de37bb9d2e2c5ccec3f8633eb91a4205cb4c10ff

然而，我最终得到的结果是：

3b40cab1157838cc41b08e27641f65d245957ab07b3504d94bc2d355abaed06c

我没有得到我期望的结果是因为我在进行字节交换时作弊，因为我错过了一个步骤，还是因为我的代码有错误（或这些错误的某种组合）？任何帮助，将不胜感激！

Answer 1

您不了解 Java 中的 byte[] 是什么。您示例中的字符串是 byte[] 的“十六进制”表示形式。请参阅如何在 Java 中初始化字节数组？public class MerkleTree {&nbsp; &nbsp; static MessageDigest digest;&nbsp; &nbsp; public static void main(String[] args) throws NoSuchAlgorithmException {&nbsp; &nbsp; &nbsp; &nbsp; digest = MessageDigest.getInstance("SHA-256");&nbsp; &nbsp; &nbsp; &nbsp; new MerkleTree().run();&nbsp; &nbsp; }&nbsp; &nbsp; private void run() {&nbsp; &nbsp; &nbsp; &nbsp; // txid A&nbsp; &nbsp; &nbsp; &nbsp; byte[] A = hexStringToByteArray("b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082");&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(A));&nbsp; &nbsp; &nbsp; &nbsp; // txid A byte-swapped&nbsp; &nbsp; &nbsp; &nbsp; byte[] A_little = swapEndianness(A);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(A_little));&nbsp; &nbsp; &nbsp; &nbsp; // txid B&nbsp; &nbsp; &nbsp; &nbsp; byte[] B = hexStringToByteArray("f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16");&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(B));&nbsp; &nbsp; &nbsp; &nbsp; // txid B byte-swapped&nbsp; &nbsp; &nbsp; &nbsp; byte[] B_little = swapEndianness(B);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(B_little));&nbsp; &nbsp; &nbsp; &nbsp; // txid A + B concatenated&nbsp; &nbsp; &nbsp; &nbsp; byte[] AB_little = Arrays.copyOf(A_little, A_little.length + B_little.length);&nbsp; &nbsp; &nbsp; &nbsp; System.arraycopy(B_little, 0, AB_little, A_little.length, B_little.length);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(AB_little));&nbsp; &nbsp; &nbsp; &nbsp; // double hash of byte-swapped concatenated A+B&nbsp; &nbsp; &nbsp; &nbsp; byte[] ABdoubleHash = SHA256(SHA256(AB_little));&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(ABdoubleHash));&nbsp; &nbsp; &nbsp; &nbsp; // print result byte-swapped back to big-endian&nbsp; &nbsp; &nbsp; &nbsp; byte[] result = swapEndianness(ABdoubleHash);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(Arrays.toString(result));&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(getHex(result));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; }&nbsp; &nbsp; byte[] swapEndianness(byte[] hash) {&nbsp; &nbsp; &nbsp; &nbsp; byte[] result = new byte[hash.length];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < hash.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result[i] = hash[hash.length-i-1];&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return result;&nbsp; &nbsp; }&nbsp; &nbsp; byte[] SHA256(byte[] obytes) {&nbsp; &nbsp; &nbsp; &nbsp; return digest.digest(obytes);&nbsp; &nbsp; }&nbsp; &nbsp; byte[] hexStringToByteArray(String s) {&nbsp; &nbsp; &nbsp; &nbsp; int len = s.length();&nbsp; &nbsp; &nbsp; &nbsp; byte[] data = new byte[len / 2];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < len; i += 2) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; data[i / 2] = (byte) ((Character.digit(s.charAt(i), 16) << 4)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+ Character.digit(s.charAt(i+1), 16));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return data;&nbsp; &nbsp; }&nbsp; &nbsp; private static final String&nbsp; &nbsp; HEXES&nbsp; &nbsp; = "0123456789abcdef";&nbsp; &nbsp; String getHex(byte[] raw) {&nbsp; &nbsp; &nbsp; &nbsp; final StringBuilder hex = new StringBuilder(2 * raw.length);&nbsp; &nbsp; &nbsp; &nbsp; for (final byte b : raw) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hex.append(HEXES.charAt((b & 0xF0) >> 4)).append(HEXES.charAt((b & 0x0F)));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return hex.toString();&nbsp; &nbsp; }}&nbsp;最后参考Java代码将byte转Hexadecimal编辑：这在资源上会好一些，因为您经常想做很多这类事情。&nbsp; &nbsp; // txid A byte-swapped&nbsp; &nbsp; byte[] A = swapEndianness(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hexStringToByteArray("b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082")&nbsp; &nbsp; &nbsp; &nbsp; );&nbsp; &nbsp; // txid B byte-swapped&nbsp; &nbsp; byte[] B = swapEndianness(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hexStringToByteArray("f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16")&nbsp; &nbsp; &nbsp; &nbsp; );&nbsp; &nbsp; // txid A + B concatenated&nbsp; &nbsp; byte[] AB = Arrays.copyOf(A, A.length + B.length);&nbsp; &nbsp; System.arraycopy(B, 0, AB, A.length, B.length);&nbsp; &nbsp; // print result byte-swapped back to big-endian&nbsp; &nbsp; String result = getHex(swapEndianness(SHA256(SHA256(AB))));&nbsp; &nbsp; System.out.println(result);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; }&nbsp; &nbsp; byte[] swapEndianness(byte[] hash) {&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < hash.length/2; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; byte t = hash[hash.length-i-1];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hash[hash.length-i-1] = hash[i];&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hash[i] = t;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return hash;&nbsp; &nbsp; }