Простая реализация дерева меркла в Java - PullRequest
Новая
       26

Простая реализация дерева меркла в Java

1 голос
/ 31 мая 2019

Я пытаюсь написать очень простую реализацию дерева меркле в Java.

Я использую значения txids в блоке 170 в биткойнахблокчейн для справки, так что я могу видеть, каким должен быть правильный результат.

txids, соответствующие этому блоку, выглядят следующим образом: 

b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082

f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16

Насколько я понимаю, этот биткойн merkleРеализация -дерева работает следующим образом:

  1. разбивает транзакции в блоке на пары
  2. байт-своп txids
  3. объединяет txids
  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();
    }

Ожидаемый результат для корня merkle этих двухtxid это: 

7dac2c5666815c17a3b36427de37bb9d2e2c5ccec3f8633eb91a4205cb4c10ff

Какрезультат, который я получаю в итоге: 

3b40cab1157838cc41b08e27641f65d245957ab07b3504d94bc2d355abaed06c

Не получаю ли я ожидаемого результата, потому что я обманываю, когда делаю байт-своп, потому что я пропускаю шаг или потому что яесть ошибка в моем коде (или какая-то их комбинация)?Любая помощь будет оценена!

1 Ответ

1 голос
/ 31 мая 2019

Вы не понимаете, что такое байт [] в Java.Строки в вашем примере являются "шестнадцатеричными" представлениями байта [].См. Как инициализировать байтовый массив в 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;
    }
...