les, light: LES/2 protocol version (#14970)

This PR implements the new LES protocol version extensions:

* new and more efficient Merkle proofs reply format (when replying to
  a multiple Merkle proofs request, we just send a single set of trie
  nodes containing all necessary nodes)
* BBT (BloomBitsTrie) works similarly to the existing CHT and contains
  the bloombits search data to speed up log searches
* GetTxStatusMsg returns the inclusion position or the
  pending/queued/unknown state of a transaction referenced by hash
* an optional signature of new block data (number/hash/td) can be
  included in AnnounceMsg to provide an option for "very light
  clients" (mobile/embedded devices) to skip expensive Ethash check
  and accept multiple signatures of somewhat trusted servers (still a
  lot better than trusting a single server completely and retrieving
  everything through RPC). The new client mode is not implemented in
  this PR, just the protocol extension.

1 files changed, 295 insertions, 0 deletions

diff --git a/light/postprocess.go b/light/postprocess.go
new file mode 100644
index 000000000..e7e513880
--- /dev/null
+++ b/light/postprocess.go
@@ -0,0 +1,295 @@
+// Copyright 2016 The go-ethereum Authors
+// This file is part of the go-ethereum library.
+//
+// The go-ethereum library is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Lesser General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// The go-ethereum library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
+
+package light
+
+import (
+	"encoding/binary"
+	"errors"
+	"fmt"
+	"math/big"
+	"time"
+
+	"github.com/ethereum/go-ethereum/common"
+	"github.com/ethereum/go-ethereum/common/bitutil"
+	"github.com/ethereum/go-ethereum/core"
+	"github.com/ethereum/go-ethereum/core/types"
+	"github.com/ethereum/go-ethereum/ethdb"
+	"github.com/ethereum/go-ethereum/log"
+	"github.com/ethereum/go-ethereum/params"
+	"github.com/ethereum/go-ethereum/rlp"
+	"github.com/ethereum/go-ethereum/trie"
+)
+
+const (
+	ChtFrequency                   = 32768
+	ChtV1Frequency                 = 4096 // as long as we want to retain LES/1 compatibility, servers generate CHTs with the old, higher frequency
+	HelperTrieConfirmations        = 2048 // number of confirmations before a server is expected to have the given HelperTrie available
+	HelperTrieProcessConfirmations = 256  // number of confirmations before a HelperTrie is generated
+)
+
+// trustedCheckpoint represents a set of post-processed trie roots (CHT and BloomTrie) associated with
+// the appropriate section index and head hash. It is used to start light syncing from this checkpoint
+// and avoid downloading the entire header chain while still being able to securely access old headers/logs.
+type trustedCheckpoint struct {
+	name                                string
+	sectionIdx                          uint64
+	sectionHead, chtRoot, bloomTrieRoot common.Hash
+}
+
+var (
+	mainnetCheckpoint = trustedCheckpoint{
+		name:          "ETH mainnet",
+		sectionIdx:    129,
+		sectionHead:   common.HexToHash("64100587c8ec9a76870056d07cb0f58622552d16de6253a59cac4b580c899501"),
+		chtRoot:       common.HexToHash("bb4fb4076cbe6923c8a8ce8f158452bbe19564959313466989fda095a60884ca"),
+		bloomTrieRoot: common.HexToHash("0db524b2c4a2a9520a42fd842b02d2e8fb58ff37c75cf57bd0eb82daeace6716"),
+	}
+
+	ropstenCheckpoint = trustedCheckpoint{
+		name:          "Ropsten testnet",
+		sectionIdx:    50,
+		sectionHead:   common.HexToHash("00bd65923a1aa67f85e6b4ae67835784dd54be165c37f056691723c55bf016bd"),
+		chtRoot:       common.HexToHash("6f56dc61936752cc1f8c84b4addabdbe6a1c19693de3f21cb818362df2117f03"),
+		bloomTrieRoot: common.HexToHash("aca7d7c504d22737242effc3fdc604a762a0af9ced898036b5986c3a15220208"),
+	}
+)
+
+// trustedCheckpoints associates each known checkpoint with the genesis hash of the chain it belongs to
+var trustedCheckpoints = map[common.Hash]trustedCheckpoint{
+	params.MainnetGenesisHash: mainnetCheckpoint,
+	params.TestnetGenesisHash: ropstenCheckpoint,
+}
+
+var (
+	ErrNoTrustedCht       = errors.New("No trusted canonical hash trie")
+	ErrNoTrustedBloomTrie = errors.New("No trusted bloom trie")
+	ErrNoHeader           = errors.New("Header not found")
+	chtPrefix             = []byte("chtRoot-") // chtPrefix + chtNum (uint64 big endian) -> trie root hash
+	ChtTablePrefix        = "cht-"
+)
+
+// ChtNode structures are stored in the Canonical Hash Trie in an RLP encoded format
+type ChtNode struct {
+	Hash common.Hash
+	Td   *big.Int
+}
+
+// GetChtRoot reads the CHT root assoctiated to the given section from the database
+// Note that sectionIdx is specified according to LES/1 CHT section size
+func GetChtRoot(db ethdb.Database, sectionIdx uint64, sectionHead common.Hash) common.Hash {
+	var encNumber [8]byte
+	binary.BigEndian.PutUint64(encNumber[:], sectionIdx)
+	data, _ := db.Get(append(append(chtPrefix, encNumber[:]...), sectionHead.Bytes()...))
+	return common.BytesToHash(data)
+}
+
+// GetChtV2Root reads the CHT root assoctiated to the given section from the database
+// Note that sectionIdx is specified according to LES/2 CHT section size
+func GetChtV2Root(db ethdb.Database, sectionIdx uint64, sectionHead common.Hash) common.Hash {
+	return GetChtRoot(db, (sectionIdx+1)*(ChtFrequency/ChtV1Frequency)-1, sectionHead)
+}
+
+// StoreChtRoot writes the CHT root assoctiated to the given section into the database
+// Note that sectionIdx is specified according to LES/1 CHT section size
+func StoreChtRoot(db ethdb.Database, sectionIdx uint64, sectionHead, root common.Hash) {
+	var encNumber [8]byte
+	binary.BigEndian.PutUint64(encNumber[:], sectionIdx)
+	db.Put(append(append(chtPrefix, encNumber[:]...), sectionHead.Bytes()...), root.Bytes())
+}
+
+// ChtIndexerBackend implements core.ChainIndexerBackend
+type ChtIndexerBackend struct {
+	db, cdb              ethdb.Database
+	section, sectionSize uint64
+	lastHash             common.Hash
+	trie                 *trie.Trie
+}
+
+// NewBloomTrieIndexer creates a BloomTrie chain indexer
+func NewChtIndexer(db ethdb.Database, clientMode bool) *core.ChainIndexer {
+	cdb := ethdb.NewTable(db, ChtTablePrefix)
+	idb := ethdb.NewTable(db, "chtIndex-")
+	var sectionSize, confirmReq uint64
+	if clientMode {
+		sectionSize = ChtFrequency
+		confirmReq = HelperTrieConfirmations
+	} else {
+		sectionSize = ChtV1Frequency
+		confirmReq = HelperTrieProcessConfirmations
+	}
+	return core.NewChainIndexer(db, idb, &ChtIndexerBackend{db: db, cdb: cdb, sectionSize: sectionSize}, sectionSize, confirmReq, time.Millisecond*100, "cht")
+}
+
+// Reset implements core.ChainIndexerBackend
+func (c *ChtIndexerBackend) Reset(section uint64, lastSectionHead common.Hash) error {
+	var root common.Hash
+	if section > 0 {
+		root = GetChtRoot(c.db, section-1, lastSectionHead)
+	}
+	var err error
+	c.trie, err = trie.New(root, c.cdb)
+	c.section = section
+	return err
+}
+
+// Process implements core.ChainIndexerBackend
+func (c *ChtIndexerBackend) Process(header *types.Header) {
+	hash, num := header.Hash(), header.Number.Uint64()
+	c.lastHash = hash
+
+	td := core.GetTd(c.db, hash, num)
+	if td == nil {
+		panic(nil)
+	}
+	var encNumber [8]byte
+	binary.BigEndian.PutUint64(encNumber[:], num)
+	data, _ := rlp.EncodeToBytes(ChtNode{hash, td})
+	c.trie.Update(encNumber[:], data)
+}
+
+// Commit implements core.ChainIndexerBackend
+func (c *ChtIndexerBackend) Commit() error {
+	batch := c.cdb.NewBatch()
+	root, err := c.trie.CommitTo(batch)
+	if err != nil {
+		return err
+	} else {
+		batch.Write()
+		if ((c.section+1)*c.sectionSize)%ChtFrequency == 0 {
+			log.Info("Storing CHT", "idx", c.section*c.sectionSize/ChtFrequency, "sectionHead", fmt.Sprintf("%064x", c.lastHash), "root", fmt.Sprintf("%064x", root))
+		}
+		StoreChtRoot(c.db, c.section, c.lastHash, root)
+	}
+	return nil
+}
+
+const (
+	BloomTrieFrequency        = 32768
+	ethBloomBitsSection       = 4096
+	ethBloomBitsConfirmations = 256
+)
+
+var (
+	bloomTriePrefix      = []byte("bltRoot-") // bloomTriePrefix + bloomTrieNum (uint64 big endian) -> trie root hash
+	BloomTrieTablePrefix = "blt-"
+)
+
+// GetBloomTrieRoot reads the BloomTrie root assoctiated to the given section from the database
+func GetBloomTrieRoot(db ethdb.Database, sectionIdx uint64, sectionHead common.Hash) common.Hash {
+	var encNumber [8]byte
+	binary.BigEndian.PutUint64(encNumber[:], sectionIdx)
+	data, _ := db.Get(append(append(bloomTriePrefix, encNumber[:]...), sectionHead.Bytes()...))
+	return common.BytesToHash(data)
+}
+
+// StoreBloomTrieRoot writes the BloomTrie root assoctiated to the given section into the database
+func StoreBloomTrieRoot(db ethdb.Database, sectionIdx uint64, sectionHead, root common.Hash) {
+	var encNumber [8]byte
+	binary.BigEndian.PutUint64(encNumber[:], sectionIdx)
+	db.Put(append(append(bloomTriePrefix, encNumber[:]...), sectionHead.Bytes()...), root.Bytes())
+}
+
+// BloomTrieIndexerBackend implements core.ChainIndexerBackend
+type BloomTrieIndexerBackend struct {
+	db, cdb                                    ethdb.Database
+	section, parentSectionSize, bloomTrieRatio uint64
+	trie                                       *trie.Trie
+	sectionHeads                               []common.Hash
+}
+
+// NewBloomTrieIndexer creates a BloomTrie chain indexer
+func NewBloomTrieIndexer(db ethdb.Database, clientMode bool) *core.ChainIndexer {
+	cdb := ethdb.NewTable(db, BloomTrieTablePrefix)
+	idb := ethdb.NewTable(db, "bltIndex-")
+	backend := &BloomTrieIndexerBackend{db: db, cdb: cdb}
+	var confirmReq uint64
+	if clientMode {
+		backend.parentSectionSize = BloomTrieFrequency
+		confirmReq = HelperTrieConfirmations
+	} else {
+		backend.parentSectionSize = ethBloomBitsSection
+		confirmReq = HelperTrieProcessConfirmations
+	}
+	backend.bloomTrieRatio = BloomTrieFrequency / backend.parentSectionSize
+	backend.sectionHeads = make([]common.Hash, backend.bloomTrieRatio)
+	return core.NewChainIndexer(db, idb, backend, BloomTrieFrequency, confirmReq-ethBloomBitsConfirmations, time.Millisecond*100, "bloomtrie")
+}
+
+// Reset implements core.ChainIndexerBackend
+func (b *BloomTrieIndexerBackend) Reset(section uint64, lastSectionHead common.Hash) error {
+	var root common.Hash
+	if section > 0 {
+		root = GetBloomTrieRoot(b.db, section-1, lastSectionHead)
+	}
+	var err error
+	b.trie, err = trie.New(root, b.cdb)
+	b.section = section
+	return err
+}
+
+// Process implements core.ChainIndexerBackend
+func (b *BloomTrieIndexerBackend) Process(header *types.Header) {
+	num := header.Number.Uint64() - b.section*BloomTrieFrequency
+	if (num+1)%b.parentSectionSize == 0 {
+		b.sectionHeads[num/b.parentSectionSize] = header.Hash()
+	}
+}
+
+// Commit implements core.ChainIndexerBackend
+func (b *BloomTrieIndexerBackend) Commit() error {
+	var compSize, decompSize uint64
+
+	for i := uint(0); i < types.BloomBitLength; i++ {
+		var encKey [10]byte
+		binary.BigEndian.PutUint16(encKey[0:2], uint16(i))
+		binary.BigEndian.PutUint64(encKey[2:10], b.section)
+		var decomp []byte
+		for j := uint64(0); j < b.bloomTrieRatio; j++ {
+			data, err := core.GetBloomBits(b.db, i, b.section*b.bloomTrieRatio+j, b.sectionHeads[j])
+			if err != nil {
+				return err
+			}
+			decompData, err2 := bitutil.DecompressBytes(data, int(b.parentSectionSize/8))
+			if err2 != nil {
+				return err2
+			}
+			decomp = append(decomp, decompData...)
+		}
+		comp := bitutil.CompressBytes(decomp)
+
+		decompSize += uint64(len(decomp))
+		compSize += uint64(len(comp))
+		if len(comp) > 0 {
+			b.trie.Update(encKey[:], comp)
+		} else {
+			b.trie.Delete(encKey[:])
+		}
+	}
+
+	batch := b.cdb.NewBatch()
+	root, err := b.trie.CommitTo(batch)
+	if err != nil {
+		return err
+	} else {
+		batch.Write()
+		sectionHead := b.sectionHeads[b.bloomTrieRatio-1]
+		log.Info("Storing BloomTrie", "section", b.section, "sectionHead", fmt.Sprintf("%064x", sectionHead), "root", fmt.Sprintf("%064x", root), "compression ratio", float64(compSize)/float64(decompSize))
+		StoreBloomTrieRoot(b.db, b.section, sectionHead, root)
+	}
+
+	return nil
+}