/
ecmh.go
152 lines (133 loc) · 4.61 KB
/
ecmh.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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
package btcec
import (
"crypto/sha256"
"encoding/binary"
"math/big"
"github.com/daglabs/btcd/util/daghash"
)
// Multiset tracks the state of a multiset as used to calculate the ECMH
// (elliptic curve multiset hash) hash of an unordered set. The state is
// a point on the curve. New elements are hashed onto a point on the curve
// and then added to the current state. Hence elements can be added in any
// order and we can also remove elements to return to a prior hash.
type Multiset struct {
curve *KoblitzCurve
x *big.Int
y *big.Int
}
// NewMultiset returns an empty multiset. The hash of an empty set
// is the 32 byte value of zero.
func NewMultiset(curve *KoblitzCurve) *Multiset {
return &Multiset{curve: curve, x: big.NewInt(0), y: big.NewInt(0)}
}
// NewMultisetFromPoint initializes a new multiset with the given x, y
// coordinate.
func NewMultisetFromPoint(curve *KoblitzCurve, x, y *big.Int) *Multiset {
var copyX, copyY big.Int
if x != nil {
copyX.Set(x)
}
if y != nil {
copyY.Set(y)
}
return &Multiset{curve: curve, x: ©X, y: ©Y}
}
// NewMultisetFromDataSlice gets a curve and a slice of byte
// slices, creates an empty multiset, hashes each data and
// add it to the multiset, and return the resulting multiset.
func NewMultisetFromDataSlice(curve *KoblitzCurve, datas [][]byte) *Multiset {
ms := NewMultiset(curve)
for _, data := range datas {
x, y := hashToPoint(curve, data)
ms.addPoint(x, y)
}
return ms
}
// Clone returns a clone of this multiset.
func (ms *Multiset) Clone() *Multiset {
return NewMultisetFromPoint(ms.curve, ms.x, ms.y)
}
// Add hashes the data onto the curve and returns
// a multiset with the new resulting point.
func (ms *Multiset) Add(data []byte) *Multiset {
newMs := ms.Clone()
x, y := hashToPoint(ms.curve, data)
newMs.addPoint(x, y)
return newMs
}
func (ms *Multiset) addPoint(x, y *big.Int) {
ms.x, ms.y = ms.curve.Add(ms.x, ms.y, x, y)
}
// Remove hashes the data onto the curve, subtracts
// the point from the existing multiset, and returns
// a multiset with the new point. This function
// will execute regardless of whether or not the passed
// data was previously added to the set. Hence if you
// remove an element that was never added and also remove
// all the elements that were added, you will not get
// back to the point at infinity (empty set).
func (ms *Multiset) Remove(data []byte) *Multiset {
newMs := ms.Clone()
x, y := hashToPoint(ms.curve, data)
newMs.removePoint(x, y)
return newMs
}
func (ms *Multiset) removePoint(x, y *big.Int) {
y.Neg(y).Mod(y, ms.curve.P)
ms.x, ms.y = ms.curve.Add(ms.x, ms.y, x, y)
}
// Union will add the point of the passed multiset instance to the point
// of this multiset and will return a multiset with the resulting point.
func (ms *Multiset) Union(otherMultiset *Multiset) *Multiset {
newMs := ms.Clone()
otherMsCopy := otherMultiset.Clone()
newMs.addPoint(otherMsCopy.x, otherMsCopy.y)
return newMs
}
// Subtract will remove the point of the passed multiset instance from the point
// of this multiset and will return a multiset with the resulting point.
func (ms *Multiset) Subtract(otherMultiset *Multiset) *Multiset {
newMs := ms.Clone()
otherMsCopy := otherMultiset.Clone()
newMs.removePoint(otherMsCopy.x, otherMsCopy.y)
return newMs
}
// Hash serializes and returns the hash of the multiset. The hash of an empty
// set is the 32 byte value of zero. The hash of a non-empty multiset is the
// sha256 hash of the 32 byte x value concatenated with the 32 byte y value.
func (ms *Multiset) Hash() *daghash.Hash {
if ms.x.Sign() == 0 && ms.y.Sign() == 0 {
return &daghash.Hash{}
}
hash := sha256.Sum256(append(ms.x.Bytes(), ms.y.Bytes()...))
castHash := daghash.Hash(hash)
return &castHash
}
// Point returns a copy of the x and y coordinates of the current multiset state.
func (ms *Multiset) Point() (x *big.Int, y *big.Int) {
var copyX, copyY big.Int
copyX.Set(ms.x)
copyY.Set(ms.y)
return ©X, ©Y
}
// hashToPoint hashes the passed data into a point on the curve. The x value
// is sha256(n, sha256(data)) where n starts at zero. If the resulting x value
// is not in the field or x^3+7 is not quadratic residue then n is incremented
// and we try again. There is a 50% chance of success for any given iteration.
func hashToPoint(curve *KoblitzCurve, data []byte) (x *big.Int, y *big.Int) {
i := uint64(0)
var err error
h := sha256.Sum256(data)
n := make([]byte, 8)
for {
binary.LittleEndian.PutUint64(n, i)
h2 := sha256.Sum256(append(n, h[:]...))
x = new(big.Int).SetBytes(h2[:])
y, err = decompressPoint(curve, x, false)
if err == nil && x.Cmp(curve.N) < 0 {
break
}
i++
}
return x, y
}