Merkle tree là gì?
Theo wiki: Trong mật mã và khoa học máy tính, Merkle tree là cây trong đó hash của các nút cha là hash tổng hợp từ các nút con. Ví dụ:
hash (cha) = hash (hash(con1) + hash(con2))
Sử dụng array list để lưu Merkle tree sẽ kiểu thế này:
List tree = new ArrayList();
tree.add("1");
tree.add("2");
tree.add("3");
tree.add("4");
tree.add("5");
tree.add("6");
int j = 0;
for (int nSize = tree.size(); nSize > 1; nSize = (nSize + 1) / 2) {
for (int i = 0; i < nSize; i += 2) {
int i2 = Math.min(i+1, nSize-1);
tree.add(tree.get(j+i) + tree.get(j+i2));
}
j += nSize;
}
System.out.println(tree);
Bitcoin cũng đang dùng Merkle tree để giảm thiểu dung lượng của 1 block, thay vì phải lưu mọi hash của mọi giao dịch, thì giờ nó chỉ cần lưu nút cha nhất của Merkle tree mà thôi
