2

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

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

该区块对应的 txid 如下：

b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082

f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16

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

  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

我的代码在一个 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 方法不是真正的“字节级”交换，而是只是改变了字符串的顺序，它看起来像这样：

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 的 merkle 根的预期结果是：

7dac2c5666815c17a3b36427de37bb9d2e2c5ccec3f8633eb91a4205cb4c10ff

但是，我最终得到的结果是：

3b40cab1157838cc41b08e27641f65d245957ab07b3504d94bc2d355abaed06c

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

4

1 回答 1

2

您不了解 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;
    }
于 2019-05-31T00:11:03.977 回答