-
Notifications
You must be signed in to change notification settings - Fork 175
/
hash.go
118 lines (100 loc) · 4.01 KB
/
hash.go
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
package common
import (
"os"
"github.com/rs/zerolog"
"github.com/onflow/flow-go/crypto/hash"
"github.com/onflow/flow-go/ledger"
"github.com/onflow/flow-go/ledger/common/utils"
)
// default value and default hash value for a default node
var defaultLeafHash []byte
const defaultHashLen = 257
// HashLen is the default output hash length in bytes
const HashLen = 32
// we are currently supporting paths of a size up to 32 bytes. I.e. path length from the rootNode of a fully expanded tree to the leaf node is 256. A path of length k is comprised of k+1 vertices. Hence, we need 257 default hashes.
var defaultHashes [defaultHashLen][]byte
// TODO: remove once the hashing with 32-bytes input is tested
var log zerolog.Logger
func init() {
log = zerolog.New(os.Stderr)
hasher := hash.NewSHA3_256()
defaultLeafHash = hasher.ComputeHash([]byte("default:"))
// Creates the Default hashes from base to level height
defaultHashes[0] = defaultLeafHash
for i := 1; i < defaultHashLen; i++ {
defaultHashes[i] = HashInterNode(defaultHashes[i-1], defaultHashes[i-1])
}
}
// GetDefaultHashes returns the default hashes of the SMT.
//
// For each tree level N, there is a default hash equal to the chained
// hashing of the default value N times.
func GetDefaultHashes() [defaultHashLen][]byte {
return defaultHashes
}
// GetDefaultHashForHeight returns the default hashes of the SMT at a specified height.
//
// For each tree level N, there is a default hash equal to the chained
// hashing of the default value N times.
func GetDefaultHashForHeight(height int) []byte {
return defaultHashes[height]
}
// HashLeaf generates hash value for leaf nodes (SHA3-256).
//
// path must be a 32 byte slice.
// note that we don't include the keys here as they are already included in the path
func HashLeaf(path []byte, value []byte) []byte {
// TODO: this is a sanity check and should be removed soon
if len(path) != HashLen {
log.Warn().Msgf("HashLeaf path input should be 32 bytes, got %d", len(path))
hasher := hash.NewSHA3_256()
_, _ = hasher.Write(path)
_, _ = hasher.Write(value)
return hasher.SumHash()
}
var out [HashLen]byte
hasher := new256()
hasher.hash256Plus(&out, path, value) // path is always 256 bits
return out[:]
}
// HashInterNode generates hash value for intermediate nodes (SHA3-256).
//
// hash1 and hash2 must each be a 32 byte slice.
func HashInterNode(hash1 []byte, hash2 []byte) []byte {
// TODO: this is a sanity check and should be removed soon
if len(hash1) != HashLen || len(hash2) != HashLen {
log.Warn().Msgf("HashInterNode inputs should be 32 bytes, got %d and %d",
len(hash1), len(hash2))
hasher := hash.NewSHA3_256()
_, _ = hasher.Write(hash1)
_, _ = hasher.Write(hash2)
return hasher.SumHash()
}
var out [HashLen]byte
hasher := new256()
hasher.hash256plus256(&out, hash1, hash2) // hash1 and hash2 are 256 bits
return out[:]
}
// ComputeCompactValue computes the value for the node considering the sub tree to only include this value and default values.
func ComputeCompactValue(path []byte, payload *ledger.Payload, nodeHeight int) []byte {
// if register is unallocated: return default hash
if len(payload.Value) == 0 {
return GetDefaultHashForHeight(nodeHeight)
}
// register is allocated
treeHeight := 8 * len(path)
// TODO Change this later to include the key as well
// for now is just the value to make it compatible with previous code
computedHash := HashLeaf(path, payload.Value) // we first compute the hash of the fully-expanded leaf
for h := 1; h <= nodeHeight; h++ { // then, we hash our way upwards towards the root until we hit the specified nodeHeight
// h is the height of the node, whose hash we are computing in this iteration.
// The hash is computed from the node's children at height h-1.
bit := utils.Bit(path, treeHeight-h)
if bit == 1 { // right branching
computedHash = HashInterNode(GetDefaultHashForHeight(h-1), computedHash)
} else { // left branching
computedHash = HashInterNode(computedHash, GetDefaultHashForHeight(h-1))
}
}
return computedHash
}