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, 260 insertions, 50 deletions

diff --git a/les/odr_requests.go b/les/odr_requests.go
index 1f853b341..937a4f1d9 100644
--- a/les/odr_requests.go
+++ b/les/odr_requests.go
@@ -36,13 +36,15 @@ import (
 
 var (
 	errInvalidMessageType  = errors.New("invalid message type")
-	errMultipleEntries     = errors.New("multiple response entries")
+	errInvalidEntryCount   = errors.New("invalid number of response entries")
 	errHeaderUnavailable   = errors.New("header unavailable")
 	errTxHashMismatch      = errors.New("transaction hash mismatch")
 	errUncleHashMismatch   = errors.New("uncle hash mismatch")
 	errReceiptHashMismatch = errors.New("receipt hash mismatch")
 	errDataHashMismatch    = errors.New("data hash mismatch")
 	errCHTHashMismatch     = errors.New("cht hash mismatch")
+	errCHTNumberMismatch   = errors.New("cht number mismatch")
+	errUselessNodes        = errors.New("useless nodes in merkle proof nodeset")
 )
 
 type LesOdrRequest interface {
@@ -64,6 +66,8 @@ func LesRequest(req light.OdrRequest) LesOdrRequest {
 		return (*CodeRequest)(r)
 	case *light.ChtRequest:
 		return (*ChtRequest)(r)
+	case *light.BloomRequest:
+		return (*BloomRequest)(r)
 	default:
 		return nil
 	}
@@ -101,7 +105,7 @@ func (r *BlockRequest) Validate(db ethdb.Database, msg *Msg) error {
 	}
 	bodies := msg.Obj.([]*types.Body)
 	if len(bodies) != 1 {
-		return errMultipleEntries
+		return errInvalidEntryCount
 	}
 	body := bodies[0]
 
@@ -157,7 +161,7 @@ func (r *ReceiptsRequest) Validate(db ethdb.Database, msg *Msg) error {
 	}
 	receipts := msg.Obj.([]types.Receipts)
 	if len(receipts) != 1 {
-		return errMultipleEntries
+		return errInvalidEntryCount
 	}
 	receipt := receipts[0]
 
@@ -186,7 +190,14 @@ type TrieRequest light.TrieRequest
 // GetCost returns the cost of the given ODR request according to the serving
 // peer's cost table (implementation of LesOdrRequest)
 func (r *TrieRequest) GetCost(peer *peer) uint64 {
-	return peer.GetRequestCost(GetProofsMsg, 1)
+	switch peer.version {
+	case lpv1:
+		return peer.GetRequestCost(GetProofsV1Msg, 1)
+	case lpv2:
+		return peer.GetRequestCost(GetProofsV2Msg, 1)
+	default:
+		panic(nil)
+	}
 }
 
 // CanSend tells if a certain peer is suitable for serving the given request
@@ -197,12 +208,12 @@ func (r *TrieRequest) CanSend(peer *peer) bool {
 // Request sends an ODR request to the LES network (implementation of LesOdrRequest)
 func (r *TrieRequest) Request(reqID uint64, peer *peer) error {
 	peer.Log().Debug("Requesting trie proof", "root", r.Id.Root, "key", r.Key)
-	req := &ProofReq{
+	req := ProofReq{
 		BHash:  r.Id.BlockHash,
 		AccKey: r.Id.AccKey,
 		Key:    r.Key,
 	}
-	return peer.RequestProofs(reqID, r.GetCost(peer), []*ProofReq{req})
+	return peer.RequestProofs(reqID, r.GetCost(peer), []ProofReq{req})
 }
 
 // Valid processes an ODR request reply message from the LES network
@@ -211,20 +222,38 @@ func (r *TrieRequest) Request(reqID uint64, peer *peer) error {
 func (r *TrieRequest) Validate(db ethdb.Database, msg *Msg) error {
 	log.Debug("Validating trie proof", "root", r.Id.Root, "key", r.Key)
 
-	// Ensure we have a correct message with a single proof
-	if msg.MsgType != MsgProofs {
+	switch msg.MsgType {
+	case MsgProofsV1:
+		proofs := msg.Obj.([]light.NodeList)
+		if len(proofs) != 1 {
+			return errInvalidEntryCount
+		}
+		nodeSet := proofs[0].NodeSet()
+		// Verify the proof and store if checks out
+		if _, err, _ := trie.VerifyProof(r.Id.Root, r.Key, nodeSet); err != nil {
+			return fmt.Errorf("merkle proof verification failed: %v", err)
+		}
+		r.Proof = nodeSet
+		return nil
+
+	case MsgProofsV2:
+		proofs := msg.Obj.(light.NodeList)
+		// Verify the proof and store if checks out
+		nodeSet := proofs.NodeSet()
+		reads := &readTraceDB{db: nodeSet}
+		if _, err, _ := trie.VerifyProof(r.Id.Root, r.Key, reads); err != nil {
+			return fmt.Errorf("merkle proof verification failed: %v", err)
+		}
+		// check if all nodes have been read by VerifyProof
+		if len(reads.reads) != nodeSet.KeyCount() {
+			return errUselessNodes
+		}
+		r.Proof = nodeSet
+		return nil
+
+	default:
 		return errInvalidMessageType
 	}
-	proofs := msg.Obj.([][]rlp.RawValue)
-	if len(proofs) != 1 {
-		return errMultipleEntries
-	}
-	// Verify the proof and store if checks out
-	if _, err := trie.VerifyProof(r.Id.Root, r.Key, proofs[0]); err != nil {
-		return fmt.Errorf("merkle proof verification failed: %v", err)
-	}
-	r.Proof = proofs[0]
-	return nil
 }
 
 type CodeReq struct {
@@ -249,11 +278,11 @@ func (r *CodeRequest) CanSend(peer *peer) bool {
 // Request sends an ODR request to the LES network (implementation of LesOdrRequest)
 func (r *CodeRequest) Request(reqID uint64, peer *peer) error {
 	peer.Log().Debug("Requesting code data", "hash", r.Hash)
-	req := &CodeReq{
+	req := CodeReq{
 		BHash:  r.Id.BlockHash,
 		AccKey: r.Id.AccKey,
 	}
-	return peer.RequestCode(reqID, r.GetCost(peer), []*CodeReq{req})
+	return peer.RequestCode(reqID, r.GetCost(peer), []CodeReq{req})
 }
 
 // Valid processes an ODR request reply message from the LES network
@@ -268,7 +297,7 @@ func (r *CodeRequest) Validate(db ethdb.Database, msg *Msg) error {
 	}
 	reply := msg.Obj.([][]byte)
 	if len(reply) != 1 {
-		return errMultipleEntries
+		return errInvalidEntryCount
 	}
 	data := reply[0]
 
@@ -280,10 +309,36 @@ func (r *CodeRequest) Validate(db ethdb.Database, msg *Msg) error {
 	return nil
 }
 
+const (
+	// helper trie type constants
+	htCanonical = iota // Canonical hash trie
+	htBloomBits        // BloomBits trie
+
+	// applicable for all helper trie requests
+	auxRoot = 1
+	// applicable for htCanonical
+	auxHeader = 2
+)
+
+type HelperTrieReq struct {
+	HelperTrieType    uint
+	TrieIdx           uint64
+	Key               []byte
+	FromLevel, AuxReq uint
+}
+
+type HelperTrieResps struct { // describes all responses, not just a single one
+	Proofs  light.NodeList
+	AuxData [][]byte
+}
+
+// legacy LES/1
 type ChtReq struct {
-	ChtNum, BlockNum, FromLevel uint64
+	ChtNum, BlockNum uint64
+	FromLevel        uint
 }
 
+// legacy LES/1
 type ChtResp struct {
 	Header *types.Header
 	Proof  []rlp.RawValue
@@ -295,7 +350,14 @@ type ChtRequest light.ChtRequest
 // GetCost returns the cost of the given ODR request according to the serving
 // peer's cost table (implementation of LesOdrRequest)
 func (r *ChtRequest) GetCost(peer *peer) uint64 {
-	return peer.GetRequestCost(GetHeaderProofsMsg, 1)
+	switch peer.version {
+	case lpv1:
+		return peer.GetRequestCost(GetHeaderProofsMsg, 1)
+	case lpv2:
+		return peer.GetRequestCost(GetHelperTrieProofsMsg, 1)
+	default:
+		panic(nil)
+	}
 }
 
 // CanSend tells if a certain peer is suitable for serving the given request
@@ -303,17 +365,21 @@ func (r *ChtRequest) CanSend(peer *peer) bool {
 	peer.lock.RLock()
 	defer peer.lock.RUnlock()
 
-	return r.ChtNum <= (peer.headInfo.Number-light.ChtConfirmations)/light.ChtFrequency
+	return peer.headInfo.Number >= light.HelperTrieConfirmations && r.ChtNum <= (peer.headInfo.Number-light.HelperTrieConfirmations)/light.ChtFrequency
 }
 
 // Request sends an ODR request to the LES network (implementation of LesOdrRequest)
 func (r *ChtRequest) Request(reqID uint64, peer *peer) error {
 	peer.Log().Debug("Requesting CHT", "cht", r.ChtNum, "block", r.BlockNum)
-	req := &ChtReq{
-		ChtNum:   r.ChtNum,
-		BlockNum: r.BlockNum,
+	var encNum [8]byte
+	binary.BigEndian.PutUint64(encNum[:], r.BlockNum)
+	req := HelperTrieReq{
+		HelperTrieType: htCanonical,
+		TrieIdx:        r.ChtNum,
+		Key:            encNum[:],
+		AuxReq:         auxHeader,
 	}
-	return peer.RequestHeaderProofs(reqID, r.GetCost(peer), []*ChtReq{req})
+	return peer.RequestHelperTrieProofs(reqID, r.GetCost(peer), []HelperTrieReq{req})
 }
 
 // Valid processes an ODR request reply message from the LES network
@@ -322,35 +388,179 @@ func (r *ChtRequest) Request(reqID uint64, peer *peer) error {
 func (r *ChtRequest) Validate(db ethdb.Database, msg *Msg) error {
 	log.Debug("Validating CHT", "cht", r.ChtNum, "block", r.BlockNum)
 
-	// Ensure we have a correct message with a single proof element
-	if msg.MsgType != MsgHeaderProofs {
+	switch msg.MsgType {
+	case MsgHeaderProofs: // LES/1 backwards compatibility
+		proofs := msg.Obj.([]ChtResp)
+		if len(proofs) != 1 {
+			return errInvalidEntryCount
+		}
+		proof := proofs[0]
+
+		// Verify the CHT
+		var encNumber [8]byte
+		binary.BigEndian.PutUint64(encNumber[:], r.BlockNum)
+
+		value, err, _ := trie.VerifyProof(r.ChtRoot, encNumber[:], light.NodeList(proof.Proof).NodeSet())
+		if err != nil {
+			return err
+		}
+		var node light.ChtNode
+		if err := rlp.DecodeBytes(value, &node); err != nil {
+			return err
+		}
+		if node.Hash != proof.Header.Hash() {
+			return errCHTHashMismatch
+		}
+		// Verifications passed, store and return
+		r.Header = proof.Header
+		r.Proof = light.NodeList(proof.Proof).NodeSet()
+		r.Td = node.Td
+	case MsgHelperTrieProofs:
+		resp := msg.Obj.(HelperTrieResps)
+		if len(resp.AuxData) != 1 {
+			return errInvalidEntryCount
+		}
+		nodeSet := resp.Proofs.NodeSet()
+		headerEnc := resp.AuxData[0]
+		if len(headerEnc) == 0 {
+			return errHeaderUnavailable
+		}
+		header := new(types.Header)
+		if err := rlp.DecodeBytes(headerEnc, header); err != nil {
+			return errHeaderUnavailable
+		}
+
+		// Verify the CHT
+		var encNumber [8]byte
+		binary.BigEndian.PutUint64(encNumber[:], r.BlockNum)
+
+		reads := &readTraceDB{db: nodeSet}
+		value, err, _ := trie.VerifyProof(r.ChtRoot, encNumber[:], reads)
+		if err != nil {
+			return fmt.Errorf("merkle proof verification failed: %v", err)
+		}
+		if len(reads.reads) != nodeSet.KeyCount() {
+			return errUselessNodes
+		}
+
+		var node light.ChtNode
+		if err := rlp.DecodeBytes(value, &node); err != nil {
+			return err
+		}
+		if node.Hash != header.Hash() {
+			return errCHTHashMismatch
+		}
+		if r.BlockNum != header.Number.Uint64() {
+			return errCHTNumberMismatch
+		}
+		// Verifications passed, store and return
+		r.Header = header
+		r.Proof = nodeSet
+		r.Td = node.Td
+	default:
 		return errInvalidMessageType
 	}
-	proofs := msg.Obj.([]ChtResp)
-	if len(proofs) != 1 {
-		return errMultipleEntries
-	}
-	proof := proofs[0]
+	return nil
+}
 
-	// Verify the CHT
-	var encNumber [8]byte
-	binary.BigEndian.PutUint64(encNumber[:], r.BlockNum)
+type BloomReq struct {
+	BloomTrieNum, BitIdx, SectionIdx, FromLevel uint64
+}
 
-	value, err := trie.VerifyProof(r.ChtRoot, encNumber[:], proof.Proof)
-	if err != nil {
-		return err
+// ODR request type for requesting headers by Canonical Hash Trie, see LesOdrRequest interface
+type BloomRequest light.BloomRequest
+
+// GetCost returns the cost of the given ODR request according to the serving
+// peer's cost table (implementation of LesOdrRequest)
+func (r *BloomRequest) GetCost(peer *peer) uint64 {
+	return peer.GetRequestCost(GetHelperTrieProofsMsg, len(r.SectionIdxList))
+}
+
+// CanSend tells if a certain peer is suitable for serving the given request
+func (r *BloomRequest) CanSend(peer *peer) bool {
+	peer.lock.RLock()
+	defer peer.lock.RUnlock()
+
+	if peer.version < lpv2 {
+		return false
 	}
-	var node light.ChtNode
-	if err := rlp.DecodeBytes(value, &node); err != nil {
-		return err
+	return peer.headInfo.Number >= light.HelperTrieConfirmations && r.BloomTrieNum <= (peer.headInfo.Number-light.HelperTrieConfirmations)/light.BloomTrieFrequency
+}
+
+// Request sends an ODR request to the LES network (implementation of LesOdrRequest)
+func (r *BloomRequest) Request(reqID uint64, peer *peer) error {
+	peer.Log().Debug("Requesting BloomBits", "bloomTrie", r.BloomTrieNum, "bitIdx", r.BitIdx, "sections", r.SectionIdxList)
+	reqs := make([]HelperTrieReq, len(r.SectionIdxList))
+
+	var encNumber [10]byte
+	binary.BigEndian.PutUint16(encNumber[0:2], uint16(r.BitIdx))
+
+	for i, sectionIdx := range r.SectionIdxList {
+		binary.BigEndian.PutUint64(encNumber[2:10], sectionIdx)
+		reqs[i] = HelperTrieReq{
+			HelperTrieType: htBloomBits,
+			TrieIdx:        r.BloomTrieNum,
+			Key:            common.CopyBytes(encNumber[:]),
+		}
 	}
-	if node.Hash != proof.Header.Hash() {
-		return errCHTHashMismatch
+	return peer.RequestHelperTrieProofs(reqID, r.GetCost(peer), reqs)
+}
+
+// Valid processes an ODR request reply message from the LES network
+// returns true and stores results in memory if the message was a valid reply
+// to the request (implementation of LesOdrRequest)
+func (r *BloomRequest) Validate(db ethdb.Database, msg *Msg) error {
+	log.Debug("Validating BloomBits", "bloomTrie", r.BloomTrieNum, "bitIdx", r.BitIdx, "sections", r.SectionIdxList)
+
+	// Ensure we have a correct message with a single proof element
+	if msg.MsgType != MsgHelperTrieProofs {
+		return errInvalidMessageType
+	}
+	resps := msg.Obj.(HelperTrieResps)
+	proofs := resps.Proofs
+	nodeSet := proofs.NodeSet()
+	reads := &readTraceDB{db: nodeSet}
+
+	r.BloomBits = make([][]byte, len(r.SectionIdxList))
+
+	// Verify the proofs
+	var encNumber [10]byte
+	binary.BigEndian.PutUint16(encNumber[0:2], uint16(r.BitIdx))
+
+	for i, idx := range r.SectionIdxList {
+		binary.BigEndian.PutUint64(encNumber[2:10], idx)
+		value, err, _ := trie.VerifyProof(r.BloomTrieRoot, encNumber[:], reads)
+		if err != nil {
+			return err
+		}
+		r.BloomBits[i] = value
 	}
-	// Verifications passed, store and return
-	r.Header = proof.Header
-	r.Proof = proof.Proof
-	r.Td = node.Td
 
+	if len(reads.reads) != nodeSet.KeyCount() {
+		return errUselessNodes
+	}
+	r.Proofs = nodeSet
 	return nil
 }
+
+// readTraceDB stores the keys of database reads. We use this to check that received node
+// sets contain only the trie nodes necessary to make proofs pass.
+type readTraceDB struct {
+	db    trie.DatabaseReader
+	reads map[string]struct{}
+}
+
+// Get returns a stored node
+func (db *readTraceDB) Get(k []byte) ([]byte, error) {
+	if db.reads == nil {
+		db.reads = make(map[string]struct{})
+	}
+	db.reads[string(k)] = struct{}{}
+	return db.db.Get(k)
+}
+
+// Has returns true if the node set contains the given key
+func (db *readTraceDB) Has(key []byte) (bool, error) {
+	_, err := db.Get(key)
+	return err == nil, nil
+}