概述
merkletree被广泛的应用在比特币技术中,本文旨在通过代码实现一个简单的merkletree,并计算出merkle tree的 treeroot。
merkle tree 是一种数据结构,用于验证在计算机之间和之间存储,处理和传输的任何类型的数据。
目前,merkle树的主要用途是确保从对等网络中接收的数据块未受损和未改变,和检查其他对等网络没有撒谎发送假数据块。
merkle tree应用举例
比特币
gita
mazon's dynamo
gassandra
比特币中的应用
比特币中每个块中都包含了所有交易的集合签名,这个签名就是用merkle tree实现的,merkle树用于比特币以汇总块中的所有事务,产生整个事务集合的整体数字指纹,提供非常有效的过程来验证事务是否包括在块中。
merkle树一个很重要的用处是检查块中是否包含指定的交易,merkle树是通过递归哈希节点对来构造的,直到只有一个哈希。
merkle tree 代码实现
哈希树的跟节点称为merkle根,merkle树可以仅用log2(n)的时间复杂度检查任何一个数据元素是否包含在树中:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
package test;
import java.security.messagedigest;
import java.util.arraylist;
import java.util.list;
public class merkletrees {
// transaction list
list<string> txlist;
// merkle root
string root;
/**
* constructor
* @param txlist transaction list 交易list
*/
public merkletrees(list<string> txlist) {
this .txlist = txlist;
root = "" ;
}
/**
* execute merkle_tree and set root.
*/
public void merkle_tree() {
list<string> temptxlist = new arraylist<string>();
for ( int i = 0 ; i < this .txlist.size(); i++) {
temptxlist.add( this .txlist.get(i));
}
list<string> newtxlist = getnewtxlist(temptxlist);
while (newtxlist.size() != 1 ) {
newtxlist = getnewtxlist(newtxlist);
}
this .root = newtxlist.get( 0 );
}
/**
* return node hash list.
* @param temptxlist
* @return
*/
private list<string> getnewtxlist(list<string> temptxlist) {
list<string> newtxlist = new arraylist<string>();
int index = 0 ;
while (index < temptxlist.size()) {
// left
string left = temptxlist.get(index);
index++;
// right
string right = "" ;
if (index != temptxlist.size()) {
right = temptxlist.get(index);
}
// sha2 hex value
string sha2hexvalue = getsha2hexvalue(left + right);
newtxlist.add(sha2hexvalue);
index++;
}
return newtxlist;
}
/**
* return hex string
* @param str
* @return
*/
public string getsha2hexvalue(string str) {
byte [] cipher_byte;
try {
messagedigest md = messagedigest.getinstance( "sha-256" );
md.update(str.getbytes());
cipher_byte = md.digest();
stringbuilder sb = new stringbuilder( 2 * cipher_byte.length);
for ( byte b: cipher_byte) {
sb.append(string.format( "%02x" , b& 0xff ) );
}
return sb.tostring();
} catch (exception e) {
e.printstacktrace();
}
return "" ;
}
/**
* get root
* @return
*/
public string getroot() {
return this .root;
}
}
|
数据准备
我们将交易的数据,放入到list中:
1
2
3
4
5
6
|
list<string> temptxlist = new arraylist<string>();
temptxlist.add( "a" );
temptxlist.add( "b" );
temptxlist.add( "c" );
temptxlist.add( "d" );
temptxlist.add( "e" );
|
实现过程
准备交易数据
计算出每个数据的hash值,从左到右逐步组成树的左右节点
执行循环知道最后只剩下一个数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
private list<string> getnewtxlist(list<string> temptxlist) {
list<string> newtxlist = new arraylist<string>();
int index = 0 ;
while (index < temptxlist.size()) {
// left
string left = temptxlist.get(index);
index++;
// right
string right = "" ;
if (index != temptxlist.size()) {
right = temptxlist.get(index);
}
// sha2 hex value
string sha2hexvalue = getsha2hexvalue(left + right);
newtxlist.add(sha2hexvalue);
index++;
}
|
测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
package test;
import java.util.arraylist;
import java.util.list;
public class app {
public static void main(string [] args) {
list<string> temptxlist = new arraylist<string>();
temptxlist.add( "a" );
temptxlist.add( "b" );
temptxlist.add( "c" );
temptxlist.add( "d" );
temptxlist.add( "e" );
merkletrees merkletrees = new merkletrees(temptxlist);
merkletrees.merkle_tree();
system.out.println( "root : " + merkletrees.getroot());
}
}
|
执行结果
本文从简单二叉树的形式实现了简单的merkletree,计算出treeroot,但是实际上的的merkletree不拘谨与二叉树还可能是多叉树。
本文90%来着于翻译,原文地址
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:http://blog.csdn.net/xiangzhihong8/article/details/53931213