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

Question

我正在尝试用 Java 编写一个非常简单的 merkle-tree 实现。我使用比特币区块链上第170 个区块中的 txid 值作为参考，所以我可以看到正确的结果应该是什么。该区块对应的txid如下：b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16据我了解，比特币的 merkle-tree 实现方式如下：将区块中的交易拆分成对字节交换 txid连接 txid对连接的对进行双重哈希需要注意的是：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 {

    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代码将byte转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;

    }