core, core/types, miner: fix transaction nonce-price combo sort

2 files changed, 126 insertions, 16 deletions

diff --git a/core/types/transaction.go b/core/types/transaction.go
index 7a6c5e088..4049ae888 100644
--- a/core/types/transaction.go
+++ b/core/types/transaction.go
@@ -17,11 +17,13 @@
 package types
 
 import (
+	"container/heap"
 	"crypto/ecdsa"
 	"errors"
 	"fmt"
 	"io"
 	"math/big"
+	"sort"
 	"sync/atomic"
 
 	"github.com/ethereum/go-ethereum/common"
@@ -302,27 +304,78 @@ func TxDifference(a, b Transactions) (keep Transactions) {
 	return keep
 }
 
-type TxByNonce struct{ Transactions }
+// TxByNonce implements the sort interface to allow sorting a list of transactions
+// by their nonces. This is usually only useful for sorting transactions from a
+// single account, otherwise a nonce comparison doesn't make much sense.
+type TxByNonce Transactions
 
-func (s TxByNonce) Less(i, j int) bool {
-	return s.Transactions[i].data.AccountNonce < s.Transactions[j].data.AccountNonce
-}
+func (s TxByNonce) Len() int           { return len(s) }
+func (s TxByNonce) Less(i, j int) bool { return s[i].data.AccountNonce < s[j].data.AccountNonce }
+func (s TxByNonce) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
+
+// TxByPrice implements both the sort and the heap interface, making it useful
+// for all at once sorting as well as individually adding and removing elements.
+type TxByPrice Transactions
 
-type TxByPrice struct{ Transactions }
+func (s TxByPrice) Len() int           { return len(s) }
+func (s TxByPrice) Less(i, j int) bool { return s[i].data.Price.Cmp(s[j].data.Price) > 0 }
+func (s TxByPrice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
 
-func (s TxByPrice) Less(i, j int) bool {
-	return s.Transactions[i].data.Price.Cmp(s.Transactions[j].data.Price) > 0
+func (s *TxByPrice) Push(x interface{}) {
+	*s = append(*s, x.(*Transaction))
 }
 
-type TxByPriceAndNonce struct{ Transactions }
+func (s *TxByPrice) Pop() interface{} {
+	old := *s
+	n := len(old)
+	x := old[n-1]
+	*s = old[0 : n-1]
+	return x
+}
 
-func (s TxByPriceAndNonce) Less(i, j int) bool {
-	// we can ignore the error here. Sorting shouldn't care about validness
-	ifrom, _ := s.Transactions[i].From()
-	jfrom, _ := s.Transactions[j].From()
-	// favour nonce if they are from the same recipient
-	if ifrom == jfrom {
-		return s.Transactions[i].data.AccountNonce < s.Transactions[j].data.AccountNonce
+// SortByPriceAndNonce sorts the transactions by price in such a way that the
+// nonce orderings within a single account are maintained.
+//
+// Note, this is not as trivial as it seems from the first look as there are three
+// different criteria that need to be taken into account (price, nonce, account
+// match), which cannot be done with any plain sorting method, as certain items
+// cannot be compared without context.
+//
+// This method first sorts the separates the list of transactions into individual
+// sender accounts and sorts them by nonce. After the account nonce ordering is
+// satisfied, the results are merged back together by price, always comparing only
+// the head transaction from each account. This is done via a heap to keep it fast.
+func SortByPriceAndNonce(txs []*Transaction) {
+	// Separate the transactions by account and sort by nonce
+	byNonce := make(map[common.Address][]*Transaction)
+	for _, tx := range txs {
+		acc, _ := tx.From() // we only sort valid txs so this cannot fail
+		byNonce[acc] = append(byNonce[acc], tx)
+	}
+	for _, accTxs := range byNonce {
+		sort.Sort(TxByNonce(accTxs))
+	}
+	// Initialize a price based heap with the head transactions
+	byPrice := make(TxByPrice, 0, len(byNonce))
+	for acc, accTxs := range byNonce {
+		byPrice = append(byPrice, accTxs[0])
+		byNonce[acc] = accTxs[1:]
+	}
+	heap.Init(&byPrice)
+
+	// Merge by replacing the best with the next from the same account
+	txs = txs[:0]
+	for len(byPrice) > 0 {
+		// Retrieve the next best transaction by price
+		best := heap.Pop(&byPrice).(*Transaction)
+
+		// Push in its place the next transaction from the same account
+		acc, _ := best.From() // we only sort valid txs so this cannot fail
+		if accTxs, ok := byNonce[acc]; ok && len(accTxs) > 0 {
+			heap.Push(&byPrice, accTxs[0])
+			byNonce[acc] = accTxs[1:]
+		}
+		// Accumulate the best priced transaction
+		txs = append(txs, best)
 	}
-	return s.Transactions[i].data.Price.Cmp(s.Transactions[j].data.Price) > 0
 }
diff --git a/core/types/transaction_test.go b/core/types/transaction_test.go
index 1c0e27d9a..62420e71f 100644
--- a/core/types/transaction_test.go
+++ b/core/types/transaction_test.go
@@ -117,3 +117,60 @@ func TestRecipientNormal(t *testing.T) {
 		t.Error("derived address doesn't match")
 	}
 }
+
+// Tests that transactions can be correctly sorted according to their price in
+// decreasing order, but at the same time with increasing nonces when issued by
+// the same account.
+func TestTransactionPriceNonceSort(t *testing.T) {
+	// Generate a batch of accounts to start with
+	keys := make([]*ecdsa.PrivateKey, 25)
+	for i := 0; i < len(keys); i++ {
+		keys[i], _ = crypto.GenerateKey()
+	}
+	// Generate a batch of transactions with overlapping values, but shifted nonces
+	txs := []*Transaction{}
+	for start, key := range keys {
+		for i := 0; i < 25; i++ {
+			tx, _ := NewTransaction(uint64(start+i), common.Address{}, big.NewInt(100), big.NewInt(100), big.NewInt(int64(start+i)), nil).SignECDSA(key)
+			txs = append(txs, tx)
+		}
+	}
+	// Sort the transactions and cross check the nonce ordering
+	SortByPriceAndNonce(txs)
+	for i, txi := range txs {
+		fromi, _ := txi.From()
+
+		// Make sure the nonce order is valid
+		for j, txj := range txs[i+1:] {
+			fromj, _ := txj.From()
+
+			if fromi == fromj && txi.Nonce() > txj.Nonce() {
+				t.Errorf("invalid nonce ordering: tx #%d (A=%x N=%v) < tx #%d (A=%x N=%v)", i, fromi[:4], txi.Nonce(), i+j, fromj[:4], txj.Nonce())
+			}
+		}
+		// Find the previous and next nonce of this account
+		prev, next := i-1, i+1
+		for j := i - 1; j >= 0; j-- {
+			if fromj, _ := txs[j].From(); fromi == fromj {
+				prev = j
+				break
+			}
+		}
+		for j := i + 1; j < len(txs); j++ {
+			if fromj, _ := txs[j].From(); fromi == fromj {
+				next = j
+				break
+			}
+		}
+		// Make sure that in between the neighbor nonces, the transaction is correctly positioned price wise
+		for j := prev + 1; j < next; j++ {
+			fromj, _ := txs[j].From()
+			if j < i && txs[j].GasPrice().Cmp(txi.GasPrice()) < 0 {
+				t.Errorf("invalid gasprice ordering: tx #%d (A=%x P=%v) < tx #%d (A=%x P=%v)", j, fromj[:4], txs[j].GasPrice(), i, fromi[:4], txi.GasPrice())
+			}
+			if j > i && txs[j].GasPrice().Cmp(txi.GasPrice()) > 0 {
+				t.Errorf("invalid gasprice ordering: tx #%d (A=%x P=%v) > tx #%d (A=%x P=%v)", j, fromj[:4], txs[j].GasPrice(), i, fromi[:4], txi.GasPrice())
+			}
+		}
+	}
+}