-
Notifications
You must be signed in to change notification settings - Fork 10
/
merkle.cpp
52 lines (39 loc) · 1.31 KB
/
merkle.cpp
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
#include <eosio/chain/merkle.hpp>
#include <fc/io/raw.hpp>
namespace eosio { namespace chain {
/**
* in order to keep proofs concise, before hashing we set the first bit
* of the previous hashes to 0 or 1 to indicate the side it is on
*
* this relieves our proofs from having to indicate left vs right contactenation
* as the node values will imply it
*/
digest_type make_canonical_left(const digest_type& val) {
digest_type canonical_l = val;
canonical_l._hash[0] &= 0xFFFFFFFFFFFFFF7FULL;
return canonical_l;
}
digest_type make_canonical_right(const digest_type& val) {
digest_type canonical_r = val;
canonical_r._hash[0] |= 0x0000000000000080ULL;
return canonical_r;
}
bool is_canonical_left(const digest_type& val) {
return (val._hash[0] & 0x0000000000000080ULL) == 0;
}
bool is_canonical_right(const digest_type& val) {
return (val._hash[0] & 0x0000000000000080ULL) != 0;
}
digest_type merkle(vector<digest_type> ids) {
if( 0 == ids.size() ) { return digest_type(); }
while( ids.size() > 1 ) {
if( ids.size() % 2 )
ids.push_back(ids.back());
for (int i = 0; i < ids.size() / 2; i++) {
ids[i] = digest_type::hash(make_canonical_pair(ids[2 * i], ids[(2 * i) + 1]));
}
ids.resize(ids.size() / 2);
}
return ids.front();
}
} } // eosio::chain