最近打算用 java 實(shí)現(xiàn) bitcoin 協(xié)議, 于是就有了實(shí)現(xiàn)了一個(gè) 梅克爾樹 的算法, 網(wǎng)上的有個(gè) Github 的不方便復(fù)制黏貼, 所以就自己寫了一個(gè), 實(shí)現(xiàn)很不 java, 主要來源于 bitcion-core的 merkle.cpp ComputeMerkleRoot, 最早實(shí)現(xiàn)了個(gè)java 的, 后來重寫了, 現(xiàn)在的代碼可讀性差了點(diǎn).
梅克爾樹
網(wǎng)上都有介紹這里就不啰嗦了, 最終是個(gè) 完全二叉樹 ,只說一個(gè)細(xì)節(jié), 如果是奇數(shù)的時(shí)候會(huì)用最后一個(gè)數(shù)填充
例如:
1, 2, 3, 4, 5, 6, 7, 8, 9, 0, A
11個(gè)數(shù)(數(shù)據(jù)是允許重復(fù), 為了說明簡單, 設(shè)置為不相同), 經(jīng)過多次填充后與下面的列表計(jì)算結(jié)果是一致的
1, 2, 3, 4, 5, 6, 7, 8, 9, 0, A, A, 9, 0, A, A
(共16個(gè)數(shù), 剛好平分, 真實(shí)算法不需要填充, 直接復(fù)制結(jié)果就行)
- 第一輪
11是奇數(shù)添加一個(gè)A湊夠偶數(shù)11 + 1 - 第二輪
6是偶數(shù)不需要湊 - 第三輪
3是奇數(shù), 將最后一位湊上 剛好是第一輪9, 0, A, A的計(jì)算結(jié)果, 最終湊為3 + 1 - 第四輪
2是偶數(shù) - 第五輪
1只有一個(gè)結(jié)果了 即是梅克爾樹的根
java 核心代碼
/**
* @param <U> 元數(shù)據(jù)類型
* @param <T> hash 后的數(shù)據(jù)類型
* @param list 原始數(shù)據(jù)
*/
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");
}
/**
* 算法說明:
* 將原數(shù)據(jù) 封裝為 MerkleTree 并添加到列表(trees),
* len 存儲(chǔ)長度, 每次盡可能多(len + 1) / 2)的折半,
* 遍歷, 如果下一個(gè)(next = i+1)超出(即len為奇數(shù)), 則復(fù)制最后一個(gè)(next = i)
* 將計(jì)算好的結(jié)果組裝為新 node, 并添加到 列表(trees) 的前半部分
* 每次循環(huán)都折半, 直到只有一個(gè) len == 1 時(shí)候, 即是樹根
*
* 重復(fù)使用 trees 數(shù)組, 是根據(jù) bitcoin 源碼clone而來, 新建一個(gè)數(shù)組也是可以的.
*/
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) { // 超長復(fù)制最后一個(gè)
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);
}
注意:
- 大部分區(qū)塊鏈瀏覽器的 交易hash都是小端的, 這個(gè)不是指字節(jié)的大端小端, 而是C++ 中使用 uint_256 來存儲(chǔ)導(dǎo)致的問題
- 塊鏈里的交易列表 不是 按照交易在區(qū)塊中的順序來排序的, 這個(gè)問題花了我一天時(shí)間去排查
詳細(xì)源碼
在碼云 gitee MerkleTree.java 上
使用
本著復(fù)制粘貼方便的目的, 沒有添加任何外部依賴, 但使用了java8的函數(shù)接口
- 第一個(gè)參數(shù)是要建樹的數(shù)據(jù)
- 第二個(gè)參數(shù)將列表中的值轉(zhuǎn)為 需要 hash 的值
- 第三個(gè)參數(shù)對 兩個(gè)需要 hash 的值合并為一個(gè)值
一般形式如下, 將一個(gè)字節(jié)數(shù)組 hash 為 另一個(gè)字節(jié)數(shù)組 ( 實(shí)例中bitcoin需要兩次 sha256 )
List<byte[]> list = ....
MerkleTree<byte[], byte[]> tree = MerkleTree
.merkleTree(
list,
e -> e,
(e1, e2) -> ByteUtil.sha256sha256(ByteUtil.concat(e1, e2))
);
下載源碼包 MerkleTreeTest 有詳細(xì)的測試用例
(完)
