/
merkle_tree.go
93 lines (81 loc) · 1.92 KB
/
merkle_tree.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 internal
import (
"bytes"
"crypto/sha512"
"errors"
"fmt"
"github.com/AutoRoute/node/types"
)
func CreateMerkleReceipt(key PrivateKey, packets []types.PacketHash) PacketReceipt {
old := make([]merklenode, 0)
for _, h := range packets {
old = append(old, merklenode{h, nil, nil})
}
for {
if len(old) <= 1 {
break
}
cur := make([]merklenode, 0)
for i, _ := range old {
if i%2 == 1 {
cur = append(cur, merklenode{"", &old[i], &old[i-1]})
}
}
if len(old)%2 == 1 {
cur = append(cur, merklenode{"", &old[len(old)-1], nil})
}
old = cur
}
return PacketReceipt{old[0], key.Sign(old[0].Hash())}
}
type PacketReceipt struct {
Tree merklenode
Signature Signature
}
func (m PacketReceipt) Verify() error {
if !bytes.Equal(m.Signature.Signed(), m.Tree.Hash()) {
return errors.New("Signature does not match contents")
}
return m.Signature.Verify()
}
func (m PacketReceipt) Source() types.NodeAddress {
return m.Signature.Key().Hash()
}
func (m PacketReceipt) ListPackets() []types.PacketHash {
return m.Tree.ListLeafs()
}
type merklenode struct {
LeafHash types.PacketHash
Left *merklenode
Right *merklenode
}
func (m merklenode) ListLeafs() []types.PacketHash {
if len(m.LeafHash) != 0 {
return []types.PacketHash{m.LeafHash}
}
if m.Right == nil {
return m.Left.ListLeafs()
}
return append(m.Left.ListLeafs(), m.Right.ListLeafs()...)
}
func (m merklenode) Hash() []byte {
if len(m.LeafHash) != 0 {
s := sha512.Sum512([]byte(m.LeafHash))
return s[0:sha512.Size]
}
if m.Right == nil {
s := sha512.Sum512(append(m.Left.Hash()))
return s[0:sha512.Size]
}
s := sha512.Sum512(append(m.Left.Hash(), m.Right.Hash()...))
return s[0:sha512.Size]
}
func (m merklenode) String() string {
if len(m.LeafHash) > 0 {
return fmt.Sprintf("{%x}", m.LeafHash)
}
if m.Right == nil {
return fmt.Sprintf("{%v nil}", *m.Left)
}
return fmt.Sprintf("{%v %v}", *m.Left, *m.Right)
}