java 中的简单 merkle-tree 实现

Question

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

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

该区块对应的txid如下：

b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082

f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16

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

将区块中的交易拆分成对
字节交换 txids
连接 txid
对连接的对进行双重哈希处理

需要注意的是：

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

我的代码在 switch 语句中，如下所示：

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 方法不是真正的 'byte level' 交换，而只是改变了字符串的顺序，它看起来像这样：

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[] 是什么。您示例中的字符串是字节 [] 的 "hex" 表示形式。参见 How do I initialize a byte array in 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 code To convert byte to Hexadecimal

编辑：这在资源上会好一些，因为您经常想做很多这类事情。

    // 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;
    }

java 中的简单 merkle-tree 实现

A simple merkle-tree implementation in java

java

merkle-tree