core: lookup txs by block number instead of block hash (#19431)

* core: lookup txs by block number instead of block hash

Transaction hashes now store a reference to their corresponding
block number as opposed to their hash. In benchmarks this was
shown to reduce storage by over 12 GB.

The main limitation of this approach is that transactions on
non-canonical blocks could never be looked up, however that is
currently not supported.

The database version has been upgraded to version 5 and the
transaction lookup process is backwards-compatible with the
prior two transaction lookup formats prexisting in the
database instance. Tests have been added to ensure this.

* core/rawdb: tiny review nit fixes

2 files changed, 93 insertions, 67 deletions

diff --git a/core/rawdb/accessors_indexes.go b/core/rawdb/accessors_indexes.go
index 530989850..423145a76 100644
--- a/core/rawdb/accessors_indexes.go
+++ b/core/rawdb/accessors_indexes.go
@@ -17,6 +17,8 @@
 package rawdb
 
 import (
+	"math/big"
+
 	"github.com/ethereum/go-ethereum/common"
 	"github.com/ethereum/go-ethereum/core/types"
 	"github.com/ethereum/go-ethereum/ethdb"
@@ -27,28 +29,34 @@ import (
 
 // ReadTxLookupEntry retrieves the positional metadata associated with a transaction
 // hash to allow retrieving the transaction or receipt by hash.
-func ReadTxLookupEntry(db ethdb.Reader, hash common.Hash) common.Hash {
+func ReadTxLookupEntry(db ethdb.Reader, hash common.Hash) *uint64 {
 	data, _ := db.Get(txLookupKey(hash))
 	if len(data) == 0 {
-		return common.Hash{}
+		return nil
+	}
+	// Database v6 tx lookup just stores the block number
+	if len(data) < common.HashLength {
+		number := new(big.Int).SetBytes(data).Uint64()
+		return &number
 	}
+	// Database v4-v5 tx lookup format just stores the hash
 	if len(data) == common.HashLength {
-		return common.BytesToHash(data)
+		return ReadHeaderNumber(db, common.BytesToHash(data))
 	}
-	// Probably it's legacy txlookup entry data, try to decode it.
+	// Finally try database v3 tx lookup format
 	var entry LegacyTxLookupEntry
 	if err := rlp.DecodeBytes(data, &entry); err != nil {
 		log.Error("Invalid transaction lookup entry RLP", "hash", hash, "blob", data, "err", err)
-		return common.Hash{}
+		return nil
 	}
-	return entry.BlockHash
+	return &entry.BlockIndex
 }
 
 // WriteTxLookupEntries stores a positional metadata for every transaction from
 // a block, enabling hash based transaction and receipt lookups.
 func WriteTxLookupEntries(db ethdb.Writer, block *types.Block) {
 	for _, tx := range block.Transactions() {
-		if err := db.Put(txLookupKey(tx.Hash()), block.Hash().Bytes()); err != nil {
+		if err := db.Put(txLookupKey(tx.Hash()), block.Number().Bytes()); err != nil {
 			log.Crit("Failed to store transaction lookup entry", "err", err)
 		}
 	}
@@ -62,12 +70,12 @@ func DeleteTxLookupEntry(db ethdb.Writer, hash common.Hash) {
 // ReadTransaction retrieves a specific transaction from the database, along with
 // its added positional metadata.
 func ReadTransaction(db ethdb.Reader, hash common.Hash) (*types.Transaction, common.Hash, uint64, uint64) {
-	blockHash := ReadTxLookupEntry(db, hash)
-	if blockHash == (common.Hash{}) {
+	blockNumber := ReadTxLookupEntry(db, hash)
+	if blockNumber == nil {
 		return nil, common.Hash{}, 0, 0
 	}
-	blockNumber := ReadHeaderNumber(db, blockHash)
-	if blockNumber == nil {
+	blockHash := ReadCanonicalHash(db, *blockNumber)
+	if blockHash == (common.Hash{}) {
 		return nil, common.Hash{}, 0, 0
 	}
 	body := ReadBody(db, blockHash, *blockNumber)
@@ -88,12 +96,12 @@ func ReadTransaction(db ethdb.Reader, hash common.Hash) (*types.Transaction, com
 // its added positional metadata.
 func ReadReceipt(db ethdb.Reader, hash common.Hash, config *params.ChainConfig) (*types.Receipt, common.Hash, uint64, uint64) {
 	// Retrieve the context of the receipt based on the transaction hash
-	blockHash := ReadTxLookupEntry(db, hash)
-	if blockHash == (common.Hash{}) {
+	blockNumber := ReadTxLookupEntry(db, hash)
+	if blockNumber == nil {
 		return nil, common.Hash{}, 0, 0
 	}
-	blockNumber := ReadHeaderNumber(db, blockHash)
-	if blockNumber == nil {
+	blockHash := ReadCanonicalHash(db, *blockNumber)
+	if blockHash == (common.Hash{}) {
 		return nil, common.Hash{}, 0, 0
 	}
 	// Read all the receipts from the block and return the one with the matching hash
diff --git a/core/rawdb/accessors_indexes_test.go b/core/rawdb/accessors_indexes_test.go
index ca74ba6af..c09bff010 100644
--- a/core/rawdb/accessors_indexes_test.go
+++ b/core/rawdb/accessors_indexes_test.go
@@ -22,69 +22,87 @@ import (
 
 	"github.com/ethereum/go-ethereum/common"
 	"github.com/ethereum/go-ethereum/core/types"
+	"github.com/ethereum/go-ethereum/ethdb"
 	"github.com/ethereum/go-ethereum/rlp"
 )
 
 // Tests that positional lookup metadata can be stored and retrieved.
 func TestLookupStorage(t *testing.T) {
-	db := NewMemoryDatabase()
+	tests := []struct {
+		name                 string
+		writeTxLookupEntries func(ethdb.Writer, *types.Block)
+	}{
+		{
+			"DatabaseV6",
+			func(db ethdb.Writer, block *types.Block) {
+				WriteTxLookupEntries(db, block)
+			},
+		},
+		{
+			"DatabaseV4-V5",
+			func(db ethdb.Writer, block *types.Block) {
+				for _, tx := range block.Transactions() {
+					db.Put(txLookupKey(tx.Hash()), block.Hash().Bytes())
+				}
+			},
+		},
+		{
+			"DatabaseV3",
+			func(db ethdb.Writer, block *types.Block) {
+				for index, tx := range block.Transactions() {
+					entry := LegacyTxLookupEntry{
+						BlockHash:  block.Hash(),
+						BlockIndex: block.NumberU64(),
+						Index:      uint64(index),
+					}
+					data, _ := rlp.EncodeToBytes(entry)
+					db.Put(txLookupKey(tx.Hash()), data)
+				}
+			},
+		},
+	}
 
-	tx1 := types.NewTransaction(1, common.BytesToAddress([]byte{0x11}), big.NewInt(111), 1111, big.NewInt(11111), []byte{0x11, 0x11, 0x11})
-	tx2 := types.NewTransaction(2, common.BytesToAddress([]byte{0x22}), big.NewInt(222), 2222, big.NewInt(22222), []byte{0x22, 0x22, 0x22})
-	tx3 := types.NewTransaction(3, common.BytesToAddress([]byte{0x33}), big.NewInt(333), 3333, big.NewInt(33333), []byte{0x33, 0x33, 0x33})
-	txs := []*types.Transaction{tx1, tx2, tx3}
+	for _, tc := range tests {
+		t.Run(tc.name, func(t *testing.T) {
+			db := NewMemoryDatabase()
 
-	block := types.NewBlock(&types.Header{Number: big.NewInt(314)}, txs, nil, nil)
+			tx1 := types.NewTransaction(1, common.BytesToAddress([]byte{0x11}), big.NewInt(111), 1111, big.NewInt(11111), []byte{0x11, 0x11, 0x11})
+			tx2 := types.NewTransaction(2, common.BytesToAddress([]byte{0x22}), big.NewInt(222), 2222, big.NewInt(22222), []byte{0x22, 0x22, 0x22})
+			tx3 := types.NewTransaction(3, common.BytesToAddress([]byte{0x33}), big.NewInt(333), 3333, big.NewInt(33333), []byte{0x33, 0x33, 0x33})
+			txs := []*types.Transaction{tx1, tx2, tx3}
 
-	// Check that no transactions entries are in a pristine database
-	for i, tx := range txs {
-		if txn, _, _, _ := ReadTransaction(db, tx.Hash()); txn != nil {
-			t.Fatalf("tx #%d [%x]: non existent transaction returned: %v", i, tx.Hash(), txn)
-		}
-	}
-	// Insert all the transactions into the database, and verify contents
-	WriteBlock(db, block)
-	WriteTxLookupEntries(db, block)
+			block := types.NewBlock(&types.Header{Number: big.NewInt(314)}, txs, nil, nil)
 
-	for i, tx := range txs {
-		if txn, hash, number, index := ReadTransaction(db, tx.Hash()); txn == nil {
-			t.Fatalf("tx #%d [%x]: transaction not found", i, tx.Hash())
-		} else {
-			if hash != block.Hash() || number != block.NumberU64() || index != uint64(i) {
-				t.Fatalf("tx #%d [%x]: positional metadata mismatch: have %x/%d/%d, want %x/%v/%v", i, tx.Hash(), hash, number, index, block.Hash(), block.NumberU64(), i)
+			// Check that no transactions entries are in a pristine database
+			for i, tx := range txs {
+				if txn, _, _, _ := ReadTransaction(db, tx.Hash()); txn != nil {
+					t.Fatalf("tx #%d [%x]: non existent transaction returned: %v", i, tx.Hash(), txn)
+				}
 			}
-			if tx.Hash() != txn.Hash() {
-				t.Fatalf("tx #%d [%x]: transaction mismatch: have %v, want %v", i, tx.Hash(), txn, tx)
-			}
-		}
-	}
-	// Delete the transactions and check purge
-	for i, tx := range txs {
-		DeleteTxLookupEntry(db, tx.Hash())
-		if txn, _, _, _ := ReadTransaction(db, tx.Hash()); txn != nil {
-			t.Fatalf("tx #%d [%x]: deleted transaction returned: %v", i, tx.Hash(), txn)
-		}
-	}
-	// Insert legacy txlookup and verify the data retrieval
-	for index, tx := range block.Transactions() {
-		entry := LegacyTxLookupEntry{
-			BlockHash:  block.Hash(),
-			BlockIndex: block.NumberU64(),
-			Index:      uint64(index),
-		}
-		data, _ := rlp.EncodeToBytes(entry)
-		db.Put(txLookupKey(tx.Hash()), data)
-	}
-	for i, tx := range txs {
-		if txn, hash, number, index := ReadTransaction(db, tx.Hash()); txn == nil {
-			t.Fatalf("tx #%d [%x]: transaction not found", i, tx.Hash())
-		} else {
-			if hash != block.Hash() || number != block.NumberU64() || index != uint64(i) {
-				t.Fatalf("tx #%d [%x]: positional metadata mismatch: have %x/%d/%d, want %x/%v/%v", i, tx.Hash(), hash, number, index, block.Hash(), block.NumberU64(), i)
+			// Insert all the transactions into the database, and verify contents
+			WriteCanonicalHash(db, block.Hash(), block.NumberU64())
+			WriteBlock(db, block)
+			tc.writeTxLookupEntries(db, block)
+
+			for i, tx := range txs {
+				if txn, hash, number, index := ReadTransaction(db, tx.Hash()); txn == nil {
+					t.Fatalf("tx #%d [%x]: transaction not found", i, tx.Hash())
+				} else {
+					if hash != block.Hash() || number != block.NumberU64() || index != uint64(i) {
+						t.Fatalf("tx #%d [%x]: positional metadata mismatch: have %x/%d/%d, want %x/%v/%v", i, tx.Hash(), hash, number, index, block.Hash(), block.NumberU64(), i)
+					}
+					if tx.Hash() != txn.Hash() {
+						t.Fatalf("tx #%d [%x]: transaction mismatch: have %v, want %v", i, tx.Hash(), txn, tx)
+					}
+				}
 			}
-			if tx.Hash() != txn.Hash() {
-				t.Fatalf("tx #%d [%x]: transaction mismatch: have %v, want %v", i, tx.Hash(), txn, tx)
+			// Delete the transactions and check purge
+			for i, tx := range txs {
+				DeleteTxLookupEntry(db, tx.Hash())
+				if txn, _, _, _ := ReadTransaction(db, tx.Hash()); txn != nil {
+					t.Fatalf("tx #%d [%x]: deleted transaction returned: %v", i, tx.Hash(), txn)
+				}
 			}
-		}
+		})
 	}
 }