-
Notifications
You must be signed in to change notification settings - Fork 0
/
add.go
84 lines (70 loc) · 2.31 KB
/
add.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
package mmr
import (
"hash"
)
type NodeAppender interface {
Get(i uint64) ([]byte, error)
Append(value []byte) (uint64, error)
}
// AddHashedLeaf adds a single leaf to the mmr and back fills any interior nodes
// 'above and to the left'
//
// Returns the size of the mmr after addition of the leaf. This is also the
// position of the next leaf.
func AddHashedLeaf(store NodeAppender, hasher hash.Hash, hashedLeaf []byte) (uint64, error) {
var err error
var i uint64
hasher.Reset()
height := uint64(0) // leaf height is always zero
if i, err = store.Append(hashedLeaf); err != nil {
return 0, err
}
// This loop checks to see if we can back fill any new mountains. Because of
// the MMR structure, for any node we add, if the next node after that would
// be higher in the tree, then the node we just added lets us create at
// least one new peak.
//
// Here, we add the second item, and it lets us add the first peak at 2
//
// 0 1 <- we add '1'
//
// 2 <- so we get to append '2' as well, because the iNext would be higher
// / \
// 0 1
//
// This tactic works no matter how many peaks exist already, as each
// backfilled 'peak' is always at the 'next' position relative to the node
// that was just added. Hence we get away with this deceptively simple
// looking iterative approach.
//
// Note that i is at 'next' every time we call IndexHeight
for IndexHeight(i) > height {
iLeft := i - (2 << height)
// XXX: TODO: I believe iRight is always just i - 1
// because i - (2 << height ) + SiblingOffset(height)
// => i - (2 << height ) + (2 << height) - 1
// => i - 1
// And, intuitively, the 'next' i is always last i + 1, and that is
// always going to be RHS when we are adding
iRight := iLeft + SiblingOffset(height)
hasher.Reset()
// For interior nodes, commit to the position to provide for non
// equivocal proof of position see: ref:
// https://github.com/proofchains/python-proofmarshal/blob/master/proofmarshal/mmr.py#L142
HashWriteUint64(hasher, i+1)
var value []byte
if value, err = store.Get(iLeft); err != nil {
return 0, err
}
hasher.Write(value)
if value, err = store.Get(iRight); err != nil {
return 0, err
}
hasher.Write(value)
if i, err = store.Append(hasher.Sum(nil)); err != nil {
return 0, err
}
height += 1
}
return i, nil
}