/
signatures.go
389 lines (354 loc) · 14.1 KB
/
signatures.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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
package types
// signatures.go contains all of the types and functions related to creating
// and verifying transaction signatures. There are a lot of rules surrounding
// the correct use of signatures. Signatures can cover part or all of a
// transaction, can be multiple different algorithms, and must satify a field
// called 'UnlockConditions'.
import (
"bytes"
"errors"
"github.com/HyperspaceApp/Hyperspace/crypto"
"github.com/HyperspaceApp/Hyperspace/encoding"
)
var (
// ErrEntropyKey is the error when a transaction tries to sign an entropy
// public key
ErrEntropyKey = errors.New("transaction tries to sign an entropy public key")
// ErrFrivolousSignature is the error when a transaction contains a frivolous
// signature
ErrFrivolousSignature = errors.New("transaction contains a frivolous signature")
// ErrInvalidPubKeyIndex is the error when a transaction contains a signature
// that points to a nonexistent public key
ErrInvalidPubKeyIndex = errors.New("transaction contains a signature that points to a nonexistent public key")
// ErrInvalidUnlockHashChecksum is the error when the provided unlock hash has
// an invalid checksum
ErrInvalidUnlockHashChecksum = errors.New("provided unlock hash has an invalid checksum")
// ErrMissingSignatures is the error when a transaction has inputs with missing
// signatures
ErrMissingSignatures = errors.New("transaction has inputs with missing signatures")
// ErrPrematureSignature is the error when the timelock on signature has not
// expired
ErrPrematureSignature = errors.New("timelock on signature has not expired")
// ErrPublicKeyOveruse is the error when public key was used multiple times while
// signing transaction
ErrPublicKeyOveruse = errors.New("public key was used multiple times while signing transaction")
// ErrSortedUniqueViolation is the error when a sorted unique violation occurs
ErrSortedUniqueViolation = errors.New("sorted unique violation")
// ErrUnlockHashWrongLen is the error when a marshalled unlock hash is the wrong
// length
ErrUnlockHashWrongLen = errors.New("marshalled unlock hash is the wrong length")
// ErrWholeTransactionViolation is the error when there's a covered fields violation
ErrWholeTransactionViolation = errors.New("covered fields violation")
// FullCoveredFields is a covered fileds object where the
// 'WholeTransaction' field has been set to true. The primary purpose of
// this variable is syntactic sugar.
FullCoveredFields = CoveredFields{WholeTransaction: true}
// These Specifiers enumerate the types of signatures that are recognized
// by this implementation. If a signature's type is unrecognized, the
// signature is treated as valid. Signatures using the special "entropy"
// type are always treated as invalid; see Consensus.md for more details.
// SignatureEd25519 is a specifier for Ed22519
SignatureEd25519 = Specifier{'e', 'd', '2', '5', '5', '1', '9'}
// SignatureEntropy is a specifier for entropy
SignatureEntropy = Specifier{'e', 'n', 't', 'r', 'o', 'p', 'y'}
)
type (
// CoveredFields indicates which fields in a transaction have been covered by
// the signature. (Note that the signature does not sign the fields
// themselves, but rather their combined hash; see SigHash.) Each slice
// corresponds to a slice in the Transaction type, indicating which indices of
// the slice have been signed. The indices must be valid, i.e. within the
// bounds of the slice. In addition, they must be sorted and unique.
//
// As a convenience, a signature of the entire transaction can be indicated by
// the 'WholeTransaction' field. If 'WholeTransaction' == true, all other
// fields must be empty (except for the Signatures field, since a signature
// cannot sign itself).
CoveredFields struct {
WholeTransaction bool `json:"wholetransaction"`
SiacoinInputs []uint64 `json:"siacoininputs"`
SiacoinOutputs []uint64 `json:"siacoinoutputs"`
FileContracts []uint64 `json:"filecontracts"`
FileContractRevisions []uint64 `json:"filecontractrevisions"`
StorageProofs []uint64 `json:"storageproofs"`
MinerFees []uint64 `json:"minerfees"`
ArbitraryData []uint64 `json:"arbitrarydata"`
TransactionSignatures []uint64 `json:"transactionsignatures"`
}
// A SiaPublicKey is a public key prefixed by a Specifier. The Specifier
// indicates the algorithm used for signing and verification. Unrecognized
// algorithms will always verify, which allows new algorithms to be added to
// the protocol via a soft-fork.
SiaPublicKey struct {
Algorithm Specifier `json:"algorithm"`
Key []byte `json:"key"`
}
// A TransactionSignature is a signature that is included in the transaction.
// The signature should correspond to a public key in one of the
// UnlockConditions of the transaction. This key is specified first by
// 'ParentID', which specifies the UnlockConditions, and then
// 'PublicKeyIndex', which indicates the key in the UnlockConditions. There
// are two types that use UnlockConditions: SiacoinInputs
// and FileContractTerminations. Each of these types also references a
// ParentID, and this is the hash that 'ParentID' must match. The 'Timelock'
// prevents the signature from being used until a certain height.
// 'CoveredFields' indicates which parts of the transaction are being signed;
// see CoveredFields.
TransactionSignature struct {
ParentID crypto.Hash `json:"parentid"`
PublicKeyIndex uint64 `json:"publickeyindex"`
Timelock BlockHeight `json:"timelock"`
CoveredFields CoveredFields `json:"coveredfields"`
Signature []byte `json:"signature"`
}
// UnlockConditions are a set of conditions which must be met to execute
// certain actions, such as spending a SiacoinOutput or terminating a
// FileContract.
//
// The simplest requirement is that the block containing the UnlockConditions
// must have a height >= 'Timelock'.
//
// 'PublicKeys' specifies the set of keys that can be used to satisfy the
// UnlockConditions; of these, at least 'SignaturesRequired' unique keys must sign
// the transaction. The keys that do not need to use the same cryptographic
// algorithm.
//
// If 'SignaturesRequired' == 0, the UnlockConditions are effectively "anyone can
// unlock." If 'SignaturesRequired' > len('PublicKeys'), then the UnlockConditions
// cannot be fulfilled under any circumstances.
UnlockConditions struct {
Timelock BlockHeight `json:"timelock"`
PublicKeys []SiaPublicKey `json:"publickeys"`
SignaturesRequired uint64 `json:"signaturesrequired"`
}
// Each input has a list of public keys and a required number of signatures.
// inputSignatures keeps track of which public keys have been used and how many
// more signatures are needed.
inputSignatures struct {
remainingSignatures uint64
possibleKeys []SiaPublicKey
usedKeys map[uint64]struct{}
index int
}
)
// Ed25519PublicKey returns pk as a SiaPublicKey, denoting its algorithm as
// Ed25519.
func Ed25519PublicKey(pk crypto.PublicKey) SiaPublicKey {
return SiaPublicKey{
Algorithm: SignatureEd25519,
Key: pk[:],
}
}
// UnlockHash calculates the root hash of a Merkle tree of the
// UnlockConditions object. The leaves of this tree are formed by taking the
// hash of the timelock, the hash of the public keys (one leaf each), and the
// hash of the number of signatures. The keys are put in the middle because
// Timelock and SignaturesRequired are both low entropy fields; they can be
// protected by having random public keys next to them.
func (uc UnlockConditions) UnlockHash() UnlockHash {
var buf bytes.Buffer
e := encoding.NewEncoder(&buf)
tree := crypto.NewTree()
e.WriteUint64(uint64(uc.Timelock))
tree.Push(buf.Bytes())
buf.Reset()
for _, key := range uc.PublicKeys {
key.MarshalSia(e)
tree.Push(buf.Bytes())
buf.Reset()
}
e.WriteUint64(uc.SignaturesRequired)
tree.Push(buf.Bytes())
return UnlockHash(tree.Root())
}
// SigHash returns the hash of the fields in a transaction covered by a given
// signature. See CoveredFields for more details.
func (t Transaction) SigHash(i int) (hash crypto.Hash) {
cf := t.TransactionSignatures[i].CoveredFields
h := crypto.NewHash()
if cf.WholeTransaction {
t.marshalSiaNoSignatures(h)
h.Write(t.TransactionSignatures[i].ParentID[:])
encoding.WriteUint64(h, t.TransactionSignatures[i].PublicKeyIndex)
encoding.WriteUint64(h, uint64(t.TransactionSignatures[i].Timelock))
} else {
for _, input := range cf.SiacoinInputs {
t.SiacoinInputs[input].MarshalSia(h)
}
for _, output := range cf.SiacoinOutputs {
t.SiacoinOutputs[output].MarshalSia(h)
}
for _, contract := range cf.FileContracts {
t.FileContracts[contract].MarshalSia(h)
}
for _, revision := range cf.FileContractRevisions {
t.FileContractRevisions[revision].MarshalSia(h)
}
for _, storageProof := range cf.StorageProofs {
t.StorageProofs[storageProof].MarshalSia(h)
}
for _, minerFee := range cf.MinerFees {
t.MinerFees[minerFee].MarshalSia(h)
}
for _, arbData := range cf.ArbitraryData {
encoding.WritePrefixedBytes(h, t.ArbitraryData[arbData])
}
}
for _, sig := range cf.TransactionSignatures {
t.TransactionSignatures[sig].MarshalSia(h)
}
h.Sum(hash[:0])
return
}
// sortedUnique checks that 'elems' is sorted, contains no repeats, and that no
// element is larger than or equal to 'max'.
func sortedUnique(elems []uint64, max int) bool {
if len(elems) == 0 {
return true
}
biggest := elems[0]
for _, elem := range elems[1:] {
if elem <= biggest {
return false
}
biggest = elem
}
if biggest >= uint64(max) {
return false
}
return true
}
// validCoveredFields makes sure that all covered fields objects in the
// signatures follow the rules. This means that if 'WholeTransaction' is set to
// true, all fields except for 'Signatures' must be empty. All fields must be
// sorted numerically, and there can be no repeats.
func (t Transaction) validCoveredFields() error {
for _, sig := range t.TransactionSignatures {
// convenience variables
cf := sig.CoveredFields
fieldMaxs := []struct {
field []uint64
max int
}{
{cf.SiacoinInputs, len(t.SiacoinInputs)},
{cf.SiacoinOutputs, len(t.SiacoinOutputs)},
{cf.FileContracts, len(t.FileContracts)},
{cf.FileContractRevisions, len(t.FileContractRevisions)},
{cf.StorageProofs, len(t.StorageProofs)},
{cf.MinerFees, len(t.MinerFees)},
{cf.ArbitraryData, len(t.ArbitraryData)},
{cf.TransactionSignatures, len(t.TransactionSignatures)},
}
// Check that all fields are empty if 'WholeTransaction' is set, except
// for the Signatures field which isn't affected.
if cf.WholeTransaction {
// 'WholeTransaction' does not check signatures.
for _, fieldMax := range fieldMaxs[:len(fieldMaxs)-1] {
if len(fieldMax.field) != 0 {
return ErrWholeTransactionViolation
}
}
}
// Check that all fields are sorted, and without repeat values, and
// that all elements point to objects that exists within the
// transaction. If there are repeats, it means a transaction is trying
// to sign the same object twice. This is unncecessary, and opens up a
// DoS vector where the transaction asks the verifier to verify many GB
// of data.
for _, fieldMax := range fieldMaxs {
if !sortedUnique(fieldMax.field, fieldMax.max) {
return ErrSortedUniqueViolation
}
}
}
return nil
}
// validSignatures checks the validaty of all signatures in a transaction.
func (t *Transaction) validSignatures(currentHeight BlockHeight) error {
// Check that all covered fields objects follow the rules.
err := t.validCoveredFields()
if err != nil {
return err
}
// Create the inputSignatures object for each input.
sigMap := make(map[crypto.Hash]*inputSignatures)
for i, input := range t.SiacoinInputs {
id := crypto.Hash(input.ParentID)
_, exists := sigMap[id]
if exists {
return ErrDoubleSpend
}
sigMap[id] = &inputSignatures{
remainingSignatures: input.UnlockConditions.SignaturesRequired,
possibleKeys: input.UnlockConditions.PublicKeys,
usedKeys: make(map[uint64]struct{}),
index: i,
}
}
for i, revision := range t.FileContractRevisions {
id := crypto.Hash(revision.ParentID)
_, exists := sigMap[id]
if exists {
return ErrDoubleSpend
}
sigMap[id] = &inputSignatures{
remainingSignatures: revision.UnlockConditions.SignaturesRequired,
possibleKeys: revision.UnlockConditions.PublicKeys,
usedKeys: make(map[uint64]struct{}),
index: i,
}
}
// Check all of the signatures for validity.
for i, sig := range t.TransactionSignatures {
// Check that sig corresponds to an entry in sigMap.
inSig, exists := sigMap[crypto.Hash(sig.ParentID)]
if !exists || inSig.remainingSignatures == 0 {
return ErrFrivolousSignature
}
// Check that sig's key hasn't already been used.
_, exists = inSig.usedKeys[sig.PublicKeyIndex]
if exists {
return ErrPublicKeyOveruse
}
// Check that the public key index refers to an existing public key.
if sig.PublicKeyIndex >= uint64(len(inSig.possibleKeys)) {
return ErrInvalidPubKeyIndex
}
// Check that the timelock has expired.
if sig.Timelock > currentHeight {
return ErrPrematureSignature
}
// Check that the signature verifies. Multiple signature schemes are
// supported.
publicKey := inSig.possibleKeys[sig.PublicKeyIndex]
switch publicKey.Algorithm {
case SignatureEntropy:
// Entropy cannot ever be used to sign a transaction.
return ErrEntropyKey
case SignatureEd25519:
// Decode the public key and signature.
var edPK crypto.PublicKey
copy(edPK[:], publicKey.Key)
var edSig crypto.Signature
copy(edSig[:], sig.Signature)
sigHash := t.SigHash(i)
err = crypto.VerifyHash(sigHash, edPK, edSig)
if err != nil {
return err
}
default:
// If the identifier is not recognized, assume that the signature
// is valid. This allows more signature types to be added via soft
// forking.
}
inSig.usedKeys[sig.PublicKeyIndex] = struct{}{}
inSig.remainingSignatures--
}
// Check that all inputs have been sufficiently signed.
for _, reqSigs := range sigMap {
if reqSigs.remainingSignatures != 0 {
return ErrMissingSignatures
}
}
return nil
}