java中一个简单的merkle-Tree实现

Question

我正试图用Java编写一个非常简单的merkle树实现。

我使用比特币区块链上方框170中的TXID值作为参考，因此我可以看到正确的结果。

与该块对应的TXID如下所示：

b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082

f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16

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

1. 将块中的事务拆分为成对的事务

有一个警告是：

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

我的代码在一个开关语句中，它看起来像这样：

case "test merkle root": {
    // txid A
    String A = "b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082";

    // txid A byte-swapped
    String A_little = MainChain.swapEndianness(A);

    // txid B
    String B = "f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16";

    // txid B byte-swapped
    String B_little = MainChain.swapEndianness(B);

    // txid A + B concatenated
    String AB_little = A_little + B_little;

    // double hash of byte-swapped concatenated A+B
    String ABdoubleHash =  SHA256.generateSHA256Hash(SHA256.generateSHA256Hash(AB_little));

    // double hash concatenated with itself
    String ABAB_little = ABdoubleHash + ABdoubleHash;

    // double hash of self-concatenated double-hashed txid
    String merkleRootLittleEndian = SHA256.generateSHA256Hash(SHA256.generateSHA256Hash(ABAB_little));

    // print result byte-swapped back to big-endian
    System.out.println("Merkle root: " + MainChain.swapEndianness(merkleRootLittleEndian));
}

我编写的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();
    }

这两种TXD的merkle根的预期结果为：

7dac2c5666815c17a3b36427de37bb9d2e2c5ccec3f8633eb91a4205cb4c10ff

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

3b40cab1157838cc41b08e27641f65d245957ab07b3504d94bc2d355abaed06c

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

Answer 1

您不了解Java中的byte[]是什么。示例中的字符串是字节[]的十六进制表示。请参见如何在Java中初始化字节数组？

public class MerkleTree {
    static MessageDigest digest;
    public static void main(String[] args) throws NoSuchAlgorithmException {
        digest = MessageDigest.getInstance("SHA-256");
        new MerkleTree().run();
    }
    private void run() {
        // txid A
        byte[] A = hexStringToByteArray("b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082");
        System.out.println(Arrays.toString(A));
        // txid A byte-swapped
        byte[] A_little = swapEndianness(A);
        System.out.println(Arrays.toString(A_little));

        // txid B
        byte[] B = hexStringToByteArray("f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16");
        System.out.println(Arrays.toString(B));

        // txid B byte-swapped
        byte[] B_little = swapEndianness(B);
        System.out.println(Arrays.toString(B_little));

        // txid A + B concatenated
        byte[] AB_little = Arrays.copyOf(A_little, A_little.length + B_little.length);
        System.arraycopy(B_little, 0, AB_little, A_little.length, B_little.length);
        System.out.println(Arrays.toString(AB_little));

        // double hash of byte-swapped concatenated A+B
        byte[] ABdoubleHash = SHA256(SHA256(AB_little));
        System.out.println(Arrays.toString(ABdoubleHash));

        // print result byte-swapped back to big-endian
        byte[] result = swapEndianness(ABdoubleHash);
        System.out.println(Arrays.toString(result));
        System.out.println(getHex(result));         
    }
    byte[] swapEndianness(byte[] hash) {
        byte[] result = new byte[hash.length];
        for (int i = 0; i < hash.length; i++) {
            result[i] = hash[hash.length-i-1];
        }
        return result;
    }
    byte[] SHA256(byte[] obytes) {
        return digest.digest(obytes);
    }
    byte[] hexStringToByteArray(String s) {
        int len = s.length();
        byte[] data = new byte[len / 2];
        for (int i = 0; i < len; i += 2) {
            data[i / 2] = (byte) ((Character.digit(s.charAt(i), 16) << 4)
                                 + Character.digit(s.charAt(i+1), 16));
        }
        return data;
    }
    private static final String    HEXES    = "0123456789abcdef";
    String getHex(byte[] raw) {
        final StringBuilder hex = new StringBuilder(2 * raw.length);
        for (final byte b : raw) {
            hex.append(HEXES.charAt((b & 0xF0) >> 4)).append(HEXES.charAt((b & 0x0F)));
        }
        return hex.toString();
    }
} 

最后，参考Java代码将字节转换为十六进制

编辑：这将是一个更好的资源，因为你经常想做这类事情很多。

    // txid A byte-swapped
    byte[] A = swapEndianness(
            hexStringToByteArray("b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082")
        );
    // txid B byte-swapped
    byte[] B = swapEndianness(
            hexStringToByteArray("f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16")
        );
    // txid A + B concatenated
    byte[] AB = Arrays.copyOf(A, A.length + B.length);
    System.arraycopy(B, 0, AB, A.length, B.length);

    // print result byte-swapped back to big-endian
    String result = getHex(swapEndianness(SHA256(SHA256(AB))));
    System.out.println(result);         
    }
    byte[] swapEndianness(byte[] hash) {
        for (int i = 0; i < hash.length/2; i++) {
            byte t = hash[hash.length-i-1];
            hash[hash.length-i-1] = hash[i]; 
            hash[i] = t; 
        }
        return hash;
    }