signatures.go 17 KB
Newer Older
1
package types
2

3 4 5 6 7 8
// 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'.

9
import (
10
	"bytes"
11 12
	"errors"

13 14
	"gitlab.com/NebulousLabs/Sia/crypto"
	"gitlab.com/NebulousLabs/Sia/encoding"
15 16
)

17
var (
18 19 20 21 22 23 24 25 26 27 28
	// 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
29
	ErrInvalidUnlockHashChecksum = errors.New("provided unlock hash has an invalid checksum")
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
	// 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
45
	ErrWholeTransactionViolation = errors.New("covered fields violation")
46

47 48 49 50
	// 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}
51 52 53 54 55

	// 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.
56 57

	// SignatureEd25519 is a specifier for Ed22519
58
	SignatureEd25519 = Specifier{'e', 'd', '2', '5', '5', '1', '9'}
59
	// SignatureEntropy is a specifier for entropy
60
	SignatureEntropy = Specifier{'e', 'n', 't', 'r', 'o', 'p', 'y'}
61 62 63
)

type (
64 65 66 67 68 69 70 71 72 73 74 75
	// 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 {
David Vorick's avatar
David Vorick committed
76 77 78 79 80 81 82 83 84 85 86
		WholeTransaction      bool     `json:"wholetransaction"`
		SiacoinInputs         []uint64 `json:"siacoininputs"`
		SiacoinOutputs        []uint64 `json:"siacoinoutputs"`
		FileContracts         []uint64 `json:"filecontracts"`
		FileContractRevisions []uint64 `json:"filecontractrevisions"`
		StorageProofs         []uint64 `json:"storageproofs"`
		SiafundInputs         []uint64 `json:"siafundinputs"`
		SiafundOutputs        []uint64 `json:"siafundoutputs"`
		MinerFees             []uint64 `json:"minerfees"`
		ArbitraryData         []uint64 `json:"arbitrarydata"`
		TransactionSignatures []uint64 `json:"transactionsignatures"`
87
	}
88

89 90 91 92 93
	// 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 {
David Vorick's avatar
David Vorick committed
94 95
		Algorithm Specifier `json:"algorithm"`
		Key       []byte    `json:"key"`
96
	}
97

98 99 100 101 102 103 104 105 106 107 108 109
	// 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 three types that use UnlockConditions: SiacoinInputs, SiafundInputs,
	// 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 {
David Vorick's avatar
David Vorick committed
110 111 112
		ParentID       crypto.Hash   `json:"parentid"`
		PublicKeyIndex uint64        `json:"publickeyindex"`
		Timelock       BlockHeight   `json:"timelock"`
113
		CoveredFields  CoveredFields `json:"coveredfields"`
David Vorick's avatar
David Vorick committed
114
		Signature      []byte        `json:"signature"`
115
	}
116

117 118 119 120 121 122 123 124
	// 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
125
	// UnlockConditions; of these, at least 'SignaturesRequired' unique keys must sign
126 127 128
	// the transaction. The keys that do not need to use the same cryptographic
	// algorithm.
	//
129 130
	// If 'SignaturesRequired' == 0, the UnlockConditions are effectively "anyone can
	// unlock." If 'SignaturesRequired' > len('PublicKeys'), then the UnlockConditions
131 132
	// cannot be fulfilled under any circumstances.
	UnlockConditions struct {
David Vorick's avatar
David Vorick committed
133 134 135
		Timelock           BlockHeight    `json:"timelock"`
		PublicKeys         []SiaPublicKey `json:"publickeys"`
		SignaturesRequired uint64         `json:"signaturesrequired"`
136 137 138 139 140 141 142 143 144 145 146 147
	}

	// 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
	}
)
148

149 150 151 152 153 154 155 156 157
// Ed25519PublicKey returns pk as a SiaPublicKey, denoting its algorithm as
// Ed25519.
func Ed25519PublicKey(pk crypto.PublicKey) SiaPublicKey {
	return SiaPublicKey{
		Algorithm: SignatureEd25519,
		Key:       pk[:],
	}
}

158 159 160 161
// 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
162
// Timelock and SignaturesRequired are both low entropy fields; they can be
163 164
// protected by having random public keys next to them.
func (uc UnlockConditions) UnlockHash() UnlockHash {
165
	var buf bytes.Buffer
166
	e := encoding.NewEncoder(&buf)
167
	tree := crypto.NewTree()
168 169 170 171 172 173 174
	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()
175
	}
176 177
	e.WriteUint64(uc.SignaturesRequired)
	tree.Push(buf.Bytes())
178 179 180 181 182
	return UnlockHash(tree.Root())
}

// SigHash returns the hash of the fields in a transaction covered by a given
// signature. See CoveredFields for more details.
Luke Champine's avatar
Luke Champine committed
183
func (t Transaction) SigHash(i int, height BlockHeight) (hash crypto.Hash) {
Luke Champine's avatar
Luke Champine committed
184 185 186 187 188 189 190 191 192 193
	sig := t.TransactionSignatures[i]
	if sig.CoveredFields.WholeTransaction {
		return t.wholeSigHash(sig, height)
	}
	return t.partialSigHash(sig.CoveredFields, height)
}

// wholeSigHash calculates the hash for a signature that specifies
// WholeTransaction = true.
func (t *Transaction) wholeSigHash(sig TransactionSignature, height BlockHeight) (hash crypto.Hash) {
194
	h := crypto.NewHash()
Luke Champine's avatar
Luke Champine committed
195 196 197 198
	e := encoding.NewEncoder(h)

	e.WriteInt(len((t.SiacoinInputs)))
	for i := range t.SiacoinInputs {
David Vorick's avatar
David Vorick committed
199 200 201
		if height >= ASICHardforkHeight {
			e.Write(ASICHardforkReplayProtectionPrefix)
		}
Luke Champine's avatar
Luke Champine committed
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221
		t.SiacoinInputs[i].MarshalSia(e)
	}
	e.WriteInt(len((t.SiacoinOutputs)))
	for i := range t.SiacoinOutputs {
		t.SiacoinOutputs[i].MarshalSia(e)
	}
	e.WriteInt(len((t.FileContracts)))
	for i := range t.FileContracts {
		t.FileContracts[i].MarshalSia(e)
	}
	e.WriteInt(len((t.FileContractRevisions)))
	for i := range t.FileContractRevisions {
		t.FileContractRevisions[i].MarshalSia(e)
	}
	e.WriteInt(len((t.StorageProofs)))
	for i := range t.StorageProofs {
		t.StorageProofs[i].MarshalSia(e)
	}
	e.WriteInt(len((t.SiafundInputs)))
	for i := range t.SiafundInputs {
David Vorick's avatar
David Vorick committed
222 223 224
		if height >= ASICHardforkHeight {
			e.Write(ASICHardforkReplayProtectionPrefix)
		}
Luke Champine's avatar
Luke Champine committed
225 226 227 228 229 230 231 232 233
		t.SiafundInputs[i].MarshalSia(e)
	}
	e.WriteInt(len((t.SiafundOutputs)))
	for i := range t.SiafundOutputs {
		t.SiafundOutputs[i].MarshalSia(e)
	}
	e.WriteInt(len((t.MinerFees)))
	for i := range t.MinerFees {
		t.MinerFees[i].MarshalSia(e)
234
	}
Luke Champine's avatar
Luke Champine committed
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
	e.WriteInt(len((t.ArbitraryData)))
	for i := range t.ArbitraryData {
		e.WritePrefixedBytes(t.ArbitraryData[i])
	}

	h.Write(sig.ParentID[:])
	encoding.WriteUint64(h, sig.PublicKeyIndex)
	encoding.WriteUint64(h, uint64(sig.Timelock))

	for _, i := range sig.CoveredFields.TransactionSignatures {
		t.TransactionSignatures[i].MarshalSia(h)
	}

	h.Sum(hash[:0])
	return
}

// partialSigHash calculates the hash of the fields of the transaction
// specified in cf.
func (t *Transaction) partialSigHash(cf CoveredFields, height BlockHeight) (hash crypto.Hash) {
	h := crypto.NewHash()
256

Luke Champine's avatar
Luke Champine committed
257
	for _, input := range cf.SiacoinInputs {
David Vorick's avatar
David Vorick committed
258 259 260
		if height >= ASICHardforkHeight {
			h.Write(ASICHardforkReplayProtectionPrefix)
		}
Luke Champine's avatar
Luke Champine committed
261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
		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 _, siafundInput := range cf.SiafundInputs {
David Vorick's avatar
David Vorick committed
276 277 278
		if height >= ASICHardforkHeight {
			h.Write(ASICHardforkReplayProtectionPrefix)
		}
Luke Champine's avatar
Luke Champine committed
279 280 281 282 283 284 285 286 287 288 289
		t.SiafundInputs[siafundInput].MarshalSia(h)
	}
	for _, siafundOutput := range cf.SiafundOutputs {
		t.SiafundOutputs[siafundOutput].MarshalSia(h)
	}
	for _, minerFee := range cf.MinerFees {
		t.MinerFees[minerFee].MarshalSia(h)
	}
	for _, arbData := range cf.ArbitraryData {
		encoding.WritePrefixedBytes(h, t.ArbitraryData[arbData])
	}
290
	for _, sig := range cf.TransactionSignatures {
291
		t.TransactionSignatures[sig].MarshalSia(h)
292 293
	}

294 295
	h.Sum(hash[:0])
	return
296 297
}

Luke Champine's avatar
Luke Champine committed
298
// sortedUnique checks that 'elems' is sorted, contains no repeats, and that no
Luke Champine's avatar
Luke Champine committed
299 300
// element is larger than or equal to 'max'.
func sortedUnique(elems []uint64, max int) bool {
David Vorick's avatar
David Vorick committed
301
	if len(elems) == 0 {
Luke Champine's avatar
Luke Champine committed
302
		return true
David Vorick's avatar
David Vorick committed
303 304
	}

305 306 307
	biggest := elems[0]
	for _, elem := range elems[1:] {
		if elem <= biggest {
Luke Champine's avatar
Luke Champine committed
308
			return false
309
		}
310
		biggest = elem
311
	}
Luke Champine's avatar
Luke Champine committed
312
	if biggest >= uint64(max) {
Luke Champine's avatar
Luke Champine committed
313
		return false
314
	}
Luke Champine's avatar
Luke Champine committed
315
	return true
316 317 318
}

// validCoveredFields makes sure that all covered fields objects in the
Luke Champine's avatar
Luke Champine committed
319 320
// 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
321
// sorted numerically, and there can be no repeats.
Luke Champine's avatar
Luke Champine committed
322
func (t Transaction) validCoveredFields() error {
323
	for _, sig := range t.TransactionSignatures {
Luke Champine's avatar
Luke Champine committed
324
		// convenience variables
325
		cf := sig.CoveredFields
Luke Champine's avatar
Luke Champine committed
326 327 328 329 330
		fieldMaxs := []struct {
			field []uint64
			max   int
		}{
			{cf.SiacoinInputs, len(t.SiacoinInputs)},
331
			{cf.SiacoinOutputs, len(t.SiacoinOutputs)},
Luke Champine's avatar
Luke Champine committed
332
			{cf.FileContracts, len(t.FileContracts)},
333
			{cf.FileContractRevisions, len(t.FileContractRevisions)},
Luke Champine's avatar
Luke Champine committed
334 335 336
			{cf.StorageProofs, len(t.StorageProofs)},
			{cf.SiafundInputs, len(t.SiafundInputs)},
			{cf.SiafundOutputs, len(t.SiafundOutputs)},
337
			{cf.MinerFees, len(t.MinerFees)},
Luke Champine's avatar
Luke Champine committed
338
			{cf.ArbitraryData, len(t.ArbitraryData)},
339
			{cf.TransactionSignatures, len(t.TransactionSignatures)},
Luke Champine's avatar
Luke Champine committed
340 341
		}

342
		if cf.WholeTransaction {
343 344
			// If WholeTransaction is set, all fields must be
			// empty, except TransactionSignatures.
Luke Champine's avatar
Luke Champine committed
345 346
			for _, fieldMax := range fieldMaxs[:len(fieldMaxs)-1] {
				if len(fieldMax.field) != 0 {
347
					return ErrWholeTransactionViolation
Luke Champine's avatar
Luke Champine committed
348
				}
349
			}
350 351 352 353 354 355 356 357 358 359 360 361 362
		} else {
			// If WholeTransaction is not set, at least one field
			// must be non-empty.
			allEmpty := true
			for _, fieldMax := range fieldMaxs {
				if len(fieldMax.field) != 0 {
					allEmpty = false
					break
				}
			}
			if allEmpty {
				return ErrWholeTransactionViolation
			}
363 364 365 366
		}

		// Check that all fields are sorted, and without repeat values, and
		// that all elements point to objects that exists within the
367 368 369 370
		// 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.
Luke Champine's avatar
Luke Champine committed
371 372
		for _, fieldMax := range fieldMaxs {
			if !sortedUnique(fieldMax.field, fieldMax.max) {
373
				return ErrSortedUniqueViolation
Luke Champine's avatar
Luke Champine committed
374
			}
375 376 377
		}
	}

Luke Champine's avatar
Luke Champine committed
378
	return nil
379 380
}

Luke Champine's avatar
Luke Champine committed
381
// validSignatures checks the validaty of all signatures in a transaction.
382
func (t *Transaction) validSignatures(currentHeight BlockHeight) error {
383
	// Check that all covered fields objects follow the rules.
Luke Champine's avatar
Luke Champine committed
384
	err := t.validCoveredFields()
385
	if err != nil {
Luke Champine's avatar
Luke Champine committed
386
		return err
387 388
	}

Luke Champine's avatar
Luke Champine committed
389 390
	// Create the inputSignatures object for each input.
	sigMap := make(map[crypto.Hash]*inputSignatures)
391
	for i, input := range t.SiacoinInputs {
392 393
		id := crypto.Hash(input.ParentID)
		_, exists := sigMap[id]
394
		if exists {
395
			return ErrDoubleSpend
396
		}
397

Luke Champine's avatar
Luke Champine committed
398
		sigMap[id] = &inputSignatures{
399
			remainingSignatures: input.UnlockConditions.SignaturesRequired,
Luke Champine's avatar
Luke Champine committed
400
			possibleKeys:        input.UnlockConditions.PublicKeys,
401
			usedKeys:            make(map[uint64]struct{}),
Luke Champine's avatar
Luke Champine committed
402
			index:               i,
403
		}
404
	}
405 406
	for i, revision := range t.FileContractRevisions {
		id := crypto.Hash(revision.ParentID)
407
		_, exists := sigMap[id]
408
		if exists {
409
			return ErrDoubleSpend
410 411
		}

Luke Champine's avatar
Luke Champine committed
412
		sigMap[id] = &inputSignatures{
413 414
			remainingSignatures: revision.UnlockConditions.SignaturesRequired,
			possibleKeys:        revision.UnlockConditions.PublicKeys,
415
			usedKeys:            make(map[uint64]struct{}),
Luke Champine's avatar
Luke Champine committed
416
			index:               i,
417 418
		}
	}
David Vorick's avatar
David Vorick committed
419
	for i, input := range t.SiafundInputs {
420 421
		id := crypto.Hash(input.ParentID)
		_, exists := sigMap[id]
422
		if exists {
423
			return ErrDoubleSpend
424 425
		}

Luke Champine's avatar
Luke Champine committed
426
		sigMap[id] = &inputSignatures{
427
			remainingSignatures: input.UnlockConditions.SignaturesRequired,
Luke Champine's avatar
Luke Champine committed
428
			possibleKeys:        input.UnlockConditions.PublicKeys,
429
			usedKeys:            make(map[uint64]struct{}),
Luke Champine's avatar
Luke Champine committed
430
			index:               i,
431
		}
432 433 434
	}

	// Check all of the signatures for validity.
435
	for i, sig := range t.TransactionSignatures {
436
		// Check that sig corresponds to an entry in sigMap.
Luke Champine's avatar
Luke Champine committed
437 438
		inSig, exists := sigMap[crypto.Hash(sig.ParentID)]
		if !exists || inSig.remainingSignatures == 0 {
Luke Champine's avatar
Luke Champine committed
439
			return ErrFrivolousSignature
440
		}
441
		// Check that sig's key hasn't already been used.
Luke Champine's avatar
Luke Champine committed
442
		_, exists = inSig.usedKeys[sig.PublicKeyIndex]
443
		if exists {
444
			return ErrPublicKeyOveruse
445
		}
446 447 448 449
		// Check that the public key index refers to an existing public key.
		if sig.PublicKeyIndex >= uint64(len(inSig.possibleKeys)) {
			return ErrInvalidPubKeyIndex
		}
450
		// Check that the timelock has expired.
451
		if sig.Timelock > currentHeight {
452
			return ErrPrematureSignature
453 454
		}

Luke Champine's avatar
Luke Champine committed
455 456 457
		// Check that the signature verifies. Multiple signature schemes are
		// supported.
		publicKey := inSig.possibleKeys[sig.PublicKeyIndex]
458
		switch publicKey.Algorithm {
David Vorick's avatar
David Vorick committed
459
		case SignatureEntropy:
460 461
			// Entropy cannot ever be used to sign a transaction.
			return ErrEntropyKey
Luke Champine's avatar
Luke Champine committed
462

463
		case SignatureEd25519:
David Vorick's avatar
David Vorick committed
464
			// Decode the public key and signature.
Luke Champine's avatar
Luke Champine committed
465
			var edPK crypto.PublicKey
466 467 468
			copy(edPK[:], publicKey.Key)
			var edSig crypto.Signature
			copy(edSig[:], sig.Signature)
469

Luke Champine's avatar
Luke Champine committed
470
			sigHash := t.SigHash(i, currentHeight)
471
			err = crypto.VerifyHash(sigHash, edPK, edSig)
472 473
			if err != nil {
				return err
474
			}
Luke Champine's avatar
Luke Champine committed
475

476
		default:
477
			// If the identifier is not recognized, assume that the signature
Luke Champine's avatar
Luke Champine committed
478 479
			// is valid. This allows more signature types to be added via soft
			// forking.
480 481
		}

482
		inSig.usedKeys[sig.PublicKeyIndex] = struct{}{}
Luke Champine's avatar
Luke Champine committed
483
		inSig.remainingSignatures--
484 485 486 487
	}

	// Check that all inputs have been sufficiently signed.
	for _, reqSigs := range sigMap {
Luke Champine's avatar
Luke Champine committed
488
		if reqSigs.remainingSignatures != 0 {
489
			return ErrMissingSignatures
490 491 492 493 494
		}
	}

	return nil
}