-
Notifications
You must be signed in to change notification settings - Fork 1
/
main.go
93 lines (78 loc) · 2 KB
/
main.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
package main
import (
"crypto/sha1"
"encoding/hex"
"fmt"
"strings"
)
func main() {
fmt.Print("Tree 1:\n")
printTree(buildTree([]Hashable{Block("a"), Block("b"), Block("c"), Block("d")})[0].(Node))
fmt.Print("Tree 2 (added 1 element):\n")
printTree(buildTree([]Hashable{Block("a"), Block("b"), Block("c"), Block("d"), Block("e")})[0].(Node))
}
// buildTree recursively builds the merkle tree, bottom-first. It makes a nodelist for each level until it results in
// 1 node, meaning we reached the root node.
func buildTree(parts []Hashable) []Hashable {
var nodes []Hashable
var i int
for i = 0; i < len(parts); i += 2 {
if i + 1 < len(parts) {
nodes = append(nodes, Node{left: parts[i], right: parts[i+1]})
} else {
nodes = append(nodes, Node{left: parts[i], right: EmptyBlock{}})
}
}
if len(nodes) == 1 {
return nodes
} else if len(nodes) > 1 {
return buildTree(nodes)
} else {
panic("huh?!")
}
}
type Hashable interface {
hash() Hash
}
type Hash [20]byte
func (h Hash) String() string {
return hex.EncodeToString(h[:])
}
type Block string
func (b Block) hash() Hash {
return hash([]byte(b)[:])
}
type EmptyBlock struct {
}
func (_ EmptyBlock) hash() Hash {
return [20]byte{}
}
type Node struct {
left Hashable
right Hashable
}
func (n Node) hash() Hash {
var l, r [sha1.Size]byte
l = n.left.hash()
r = n.right.hash()
return hash(append(l[:], r[:]...))
}
func hash(data []byte) Hash {
return sha1.Sum(data)
}
func printTree(node Node) {
printNode(node, 0)
}
func printNode(node Node, level int) {
fmt.Printf("(%d) %s %s\n", level, strings.Repeat(" ", level), node.hash())
if l, ok := node.left.(Node); ok {
printNode(l, level+1)
} else if l, ok := node.left.(Block); ok {
fmt.Printf("(%d) %s %s (data: %s)\n", level + 1, strings.Repeat(" ", level + 1), l.hash(), l)
}
if r, ok := node.right.(Node); ok {
printNode(r, level+1)
} else if r, ok := node.right.(Block); ok {
fmt.Printf("(%d) %s %s (data: %s)\n", level + 1, strings.Repeat(" ", level + 1), r.hash(), r)
}
}