MerkleTree - 梅克尔树

最近打算用 java 实现 bitcoin 协议, 于是就有了实现了一个 梅克尔树 的算法, 网上的有个 Github 的不方便复制黏贴, 所以就自己写了一个, 实现很不 java, 主要来源于 bitcion-core的 merkle.cpp ComputeMerkleRoot, 最早实现了个java 的, 后来重写了, 现在的代码可读性差了点.

梅克尔树

网上都有介绍这里就不啰嗦了, 最终是个 完全二叉树 ,只说一个细节, 如果是奇数的时候会用最后一个数填充

例如:

1, 2, 3, 4, 5, 6, 7, 8, 9, 0, A
11个数(数据是允许重复, 为了说明简单, 设置为不相同), 经过多次填充后与下面的列表计算结果是一致的
1, 2, 3, 4, 5, 6, 7, 8, 9, 0, A, A, 9, 0, A, A
(共16个数, 刚好平分, 真实算法不需要填充, 直接复制结果就行)

1. 第一轮11是奇数添加一个A 凑够偶数 11 + 1
2. 第二轮 6 是偶数不需要凑
3. 第三轮 3 是奇数, 将最后一位凑上 刚好是第一轮 9, 0, A, A 的计算结果, 最终凑为 3 + 1
4. 第四轮 2 是偶数
5. 第五轮 1 只有一个结果了 即是梅克尔树的根

java 核心代码

    /**
     * @param <U>     元数据类型
     * @param <T>     hash 后的数据类型
     * @param list    原始数据
     */
    public static <U, T> MerkleTree merkleTree(List<U> list, Function<U, T> mapper, BiFunction<T, T, T> reducer) {
        if (list.isEmpty()) {
            throw new IllegalArgumentException("NOT EMPTY");
        }
        /**
         * 算法说明:
         * 将原数据 封装为 MerkleTree 并添加到列表(trees),
         * len 存储长度, 每次尽可能多(len + 1) / 2)的折半,
         * 遍历, 如果下一个(next = i+1)超出(即len为奇数), 则复制最后一个(next = i)
         * 将计算好的结果组装为新 node, 并添加到 列表(trees) 的前半部分
         * 每次循环都折半, 直到只有一个 len == 1 时候, 即是树根
         *
         * 重复使用 trees 数组, 是根据 bitcoin 源码clone而来, 新建一个数组也是可以的.
         */
        List<MerkleTree<U, T>> trees = list.stream().map(u -> {
            T hash = mapper.apply(u);
            return new MerkleTree<U, T>().setHash(hash).setData(u);
        }).collect(Collectors.toList());
        int len = trees.size();
        while (len > 1) {
            for (int i = 0; i < len; i += 2) {
                int next = i + 1;
                if (next >= len) { // 超长复制最后一个
                    next = i;
                }
                MerkleTree<U, T> node = new MerkleTree();
                node.left = trees.get(i);
                node.right = trees.get(next);
                node.hash = reducer.apply(node.left.hash, node.right.hash);
                trees.set(i / 2, node);
            }
            len = (len + 1) / 2;
        }
        return trees.get(0);
    }

注意:

1. 大部分区块链浏览器的 交易hash都是小端的, 这个不是指字节的大端小端, 而是C++ 中使用 uint_256 来存储导致的问题
2. 块链里的交易列表 不是 按照交易在区块中的顺序来排序的, 这个问题花了我一天时间去排查

详细源码

在码云 gitee MerkleTree.java 上

使用

本着复制粘贴方便的目的, 没有添加任何外部依赖, 但使用了java8的函数接口

1. 第一个参数是要建树的数据
2. 第二个参数将列表中的值转为 需要 hash 的值
3. 第三个参数对 两个需要 hash 的值合并为一个值

一般形式如下, 将一个字节数组 hash 为 另一个字节数组 ( 实例中bitcoin需要两次 sha256 )

    List<byte[]> list = ....
    MerkleTree<byte[], byte[]> tree = MerkleTree
        .merkleTree(
            list,
            e -> e,
            (e1, e2) -> ByteUtil.sha256sha256(ByteUtil.concat(e1, e2))
        );

下载源码包 MerkleTreeTest 有详细的测试用例

(完)