Repository: celestiaorg/celestia-node
Pull request #1777 (2023-02-18 14:30:30)

refactor(libhead): unify VerifyAdjacent and VerifyNonAdjacent into Verify
Last beautification for read-only header interface. We didn't do it previously with @tzdybal, as the syncing logic depended on adjacency through ErrNotNotAdjacent, which VerifyAdjacent returned. The solution is to keep returning this error but from Append.                                                                                                                                                                                                                                                                   

Additionally, this solves an edge case found by @gupadhyaya, where when Syncer starts and instantly requests and fails to apply a new network header due to adjacency.       

Wondertan: I also moved /headertest from root to /header. It shouldn't be in the root
vgonkivs: conflicts
Wondertan: Lint is borken
Wondertan: Merge over GH didn't go well, so rebasing locally

Patch:
diff --git a/core/exchange.go b/core/exchange.go
index 29d32216..49e5074c 100644
--- a/core/exchange.go
+++ b/core/exchange.go
@@ -64,7 +64,7 @@ func (ce *Exchange) GetVerifiedRange(
 	}
 
 	for _, h := range headers {
-		err := from.VerifyAdjacent(h)
+		err := from.Verify(h)
 		if err != nil {
 			return nil, err
 		}
diff --git a/header/verify.go b/header/verify.go
index e9a12e2a..eebb39c0 100644
--- a/header/verify.go
+++ b/header/verify.go
@@ -10,53 +10,47 @@ import (
 	libhead "github.com/celestiaorg/celestia-node/libs/header"
 )
 
-// TODO(@Wondertan): We should request TrustingPeriod from the network's state params or
-//  listen for network params changes to always have a topical value.
-
-// VerifyNonAdjacent validates non-adjacent untrusted header against trusted 'eh'.
-func (eh *ExtendedHeader) VerifyNonAdjacent(untrusted libhead.Header) error {
+// Verify validates given untrusted Header against trusted ExtendedHeader.
+func (eh *ExtendedHeader) Verify(untrusted libhead.Header) error {
 	untrst, ok := untrusted.(*ExtendedHeader)
 	if !ok {
-		return &libhead.VerifyError{Reason: fmt.Errorf("invalid header type: expected %T, got %T", eh, untrusted)}
-	}
-	if err := eh.verify(untrst); err != nil {
-		return &libhead.VerifyError{Reason: err}
+		// if the header of the type was given, something very wrong happens
+		panic(fmt.Sprintf("invalid header type: expected %T, got %T", eh, untrusted))
 	}
 
-	// Ensure that untrusted commit has enough of trusted commit's power.
-	err := eh.ValidatorSet.VerifyCommitLightTrusting(eh.ChainID(), untrst.Commit, light.DefaultTrustLevel)
-	if err != nil {
+	if err := eh.verify(untrst); err != nil {
 		return &libhead.VerifyError{Reason: err}
 	}
 
-	return nil
-}
+	isAdjacent := eh.Height()+1 == untrst.Height()
+	if isAdjacent {
+		// Optimized verification for adjacent headers
+		// Check the validator hashes are the same
+		if !bytes.Equal(untrst.ValidatorsHash, eh.NextValidatorsHash) {
+			return &libhead.VerifyError{
+				Reason: fmt.Errorf("expected old header next validators (%X) to match those from new header (%X)",
+					eh.NextValidatorsHash,
+					untrst.ValidatorsHash,
+				),
+			}
+		}
 
-// VerifyAdjacent validates adjacent untrusted header against trusted 'eh'.
-func (eh *ExtendedHeader) VerifyAdjacent(untrusted libhead.Header) error {
-	untrst, ok := untrusted.(*ExtendedHeader)
-	if !ok {
-		return &libhead.VerifyError{Reason: fmt.Errorf("invalid header type: expected %T, got %T", eh, untrusted)}
-	}
-	if untrst.Height() != eh.Height()+1 {
-		return &libhead.ErrNonAdjacent{
-			Head:      eh.Height(),
-			Attempted: untrst.Height(),
+		if !bytes.Equal(untrst.LastHeader(), eh.Hash()) {
+			return &libhead.VerifyError{
+				Reason: fmt.Errorf("expected new header to point to last header hash (%X), but got %X)",
+					eh.Hash(),
+					untrst.LastHeader(),
+				),
+			}
 		}
-	}
 
-	if err := eh.verify(untrst); err != nil {
-		return &libhead.VerifyError{Reason: err}
+		return nil
 	}
 
-	// Check the validator hashes are the same
-	if !bytes.Equal(untrst.ValidatorsHash, eh.NextValidatorsHash) {
-		return &libhead.VerifyError{
-			Reason: fmt.Errorf("expected old header next validators (%X) to match those from new header (%X)",
-				eh.NextValidatorsHash,
-				untrst.ValidatorsHash,
-			),
-		}
+	// Ensure that untrusted commit has enough of trusted commit's power.
+	err := eh.ValidatorSet.VerifyCommitLightTrusting(eh.ChainID(), untrst.Commit, light.DefaultTrustLevel)
+	if err != nil {
+		return &libhead.VerifyError{Reason: err}
 	}
 
 	return nil
@@ -67,13 +61,17 @@ func (eh *ExtendedHeader) VerifyAdjacent(untrusted libhead.Header) error {
 var clockDrift = 10 * time.Second
 
 // verify performs basic verification of untrusted header.
-func (eh *ExtendedHeader) verify(untrst *ExtendedHeader) error {
+func (eh *ExtendedHeader) verify(untrst libhead.Header) error {
+	if untrst.Height() <= eh.Height() {
+		return fmt.Errorf("untrusted header height(%d) <= current trusted header(%d)", untrst.Height(), eh.Height())
+	}
+
 	if untrst.ChainID() != eh.ChainID() {
-		return fmt.Errorf("new untrusted header has different chain %s, not %s", untrst.ChainID(), eh.ChainID())
+		return fmt.Errorf("untrusted header has different chain %s, not %s", untrst.ChainID(), eh.ChainID())
 	}
 
 	if !untrst.Time().After(eh.Time()) {
-		return fmt.Errorf("expected new untrusted header time %v to be after old header time %v", untrst.Time(), eh.Time())
+		return fmt.Errorf("untrusted header time(%v) must be after current trusted header(%v)", untrst.Time(), eh.Time())
 	}
 
 	now := time.Now()
diff --git a/libs/header/errors.go b/libs/header/errors.go
index 6f00876a..8a04f6b6 100644
--- a/libs/header/errors.go
+++ b/libs/header/errors.go
@@ -2,7 +2,7 @@ package header
 
 import "fmt"
 
-// VerifyError is thrown on during VerifyAdjacent and VerifyNonAdjacent if verification fails.
+// VerifyError is thrown on during Verify if it fails.
 type VerifyError struct {
 	Reason error
 }
diff --git a/libs/header/header.go b/libs/header/header.go
index 72d1698f..cdf27db4 100644
--- a/libs/header/header.go
+++ b/libs/header/header.go
@@ -21,10 +21,8 @@ type Header interface {
 	LastHeader() Hash
 	// Time returns time when header was created.
 	Time() time.Time
-	// VerifyAdjacent validates adjacent untrusted header against trusted header.
-	VerifyAdjacent(Header) error
-	// VerifyNonAdjacent validates non-adjacent untrusted header against trusted header.
-	VerifyNonAdjacent(Header) error
+	// Verify validates given untrusted Header against trusted Header.
+	Verify(Header) error
 	// Validate performs basic validation to check for missed/incorrect fields.
 	Validate() error
 
diff --git a/libs/header/p2p/session.go b/libs/header/p2p/session.go
index d637acd9..b00ac57a 100644
--- a/libs/header/p2p/session.go
+++ b/libs/header/p2p/session.go
@@ -3,6 +3,7 @@ package p2p
 import (
 	"context"
 	"errors"
+	"fmt"
 	"sort"
 	"time"
 
@@ -160,6 +161,7 @@ func (s *session[H]) doRequest(
 		case <-s.ctx.Done():
 		case s.reqCh <- req:
 		}
+		log.Errorw("processing response", "err", err)
 		return
 	}
 	log.Debugw("request headers from peer succeeded", "peer", stat.peerID, "amount", req.Amount)
@@ -201,23 +203,18 @@ func (s *session[H]) validate(headers []H) error {
 		return nil
 	}
 
-	// verify that the first header in range is valid against the trusted header.
-	err := s.from.VerifyNonAdjacent(headers[0])
-	if err != nil {
-		return nil
-	}
-
-	if len(headers) == 1 {
-		return nil
-	}
-
-	trusted := headers[0]
+	trusted := s.from
 	// verify that the whole range is valid.
-	for i := 1; i < len(headers); i++ {
-		err = trusted.VerifyAdjacent(headers[i])
+	for i := 0; i < len(headers); i++ {
+		err := trusted.Verify(headers[i])
 		if err != nil {
 			return err
 		}
+		if trusted.Height()+1 != headers[i].Height() {
+			// Exchange requires requested ranges to always consist of adjacent headers
+			return fmt.Errorf("peer sent valid but non-adjacent header")
+		}
+
 		trusted = headers[i]
 	}
 	return nil
diff --git a/libs/header/store/store.go b/libs/header/store/store.go
index 1f36fa83..7daad912 100644
--- a/libs/header/store/store.go
+++ b/libs/header/store/store.go
@@ -262,7 +262,7 @@ func (s *Store[H]) GetVerifiedRange(
 	}
 
 	for _, h := range headers {
-		err := from.VerifyAdjacent(h)
+		err := from.Verify(h)
 		if err != nil {
 			return nil, err
 		}
@@ -309,7 +309,16 @@ func (s *Store[H]) Append(ctx context.Context, headers ...H) (int, error) {
 	// collect valid headers
 	verified := make([]H, 0, lh)
 	for i, h := range headers {
-		err = head.VerifyAdjacent(h)
+		// currently store requires all headers to be appended sequentially and adjacently
+		// TODO(@Wondertan): Further pruning friendly Store design should reevaluate this requirement
+		if h.Height() != head.Height()+1 {
+			return 0, &header.ErrNonAdjacent{
+				Head:      head.Height(),
+				Attempted: h.Height(),
+			}
+		}
+
+		err = head.Verify(h)
 		if err != nil {
 			var verErr *header.VerifyError
 			if errors.As(err, &verErr) {
diff --git a/libs/header/sync/sync_head.go b/libs/header/sync/sync_head.go
index c6a007ab..6ff04691 100644
--- a/libs/header/sync/sync_head.go
+++ b/libs/header/sync/sync_head.go
@@ -118,7 +118,7 @@ func (s *Syncer[H]) incomingNetHead(ctx context.Context, netHead H) pubsub.Valid
 	var nonAdj *header.ErrNonAdjacent
 	if errors.As(err, &nonAdj) {
 		// not adjacent, maybe we've missed a few headers or its from the past
-		log.Debugw("attempted to append non-adjacent header", "store head",
+		log.Debugw("attempted to append gossiped non-adjacent header", "store head",
 			nonAdj.Head, "attempted", nonAdj.Attempted)
 	} else {
 		var verErr *header.VerifyError
@@ -168,7 +168,7 @@ func (s *Syncer[H]) validate(ctx context.Context, new H) pubsub.ValidationResult
 		return pubsub.ValidationIgnore
 	}
 	// perform verification
-	err = sbjHead.VerifyNonAdjacent(new)
+	err = sbjHead.Verify(new)
 	var verErr *header.VerifyError
 	if errors.As(err, &verErr) {
 		log.Errorw("invalid network header",
@@ -183,6 +183,9 @@ func (s *Syncer[H]) validate(ctx context.Context, new H) pubsub.ValidationResult
 	return pubsub.ValidationAccept
 }
 
+// TODO(@Wondertan): We should request TrustingPeriod from the network's state params or
+//  listen for network params changes to always have a topical value.
+
 // isExpired checks if header is expired against trusting period.
 func isExpired(header header.Header, period time.Duration) bool {
 	expirationTime := header.Time().Add(period)


Test patch:
diff --git a/core/header_test.go b/core/header_test.go
index 17337405..4d156dfd 100644
--- a/core/header_test.go
+++ b/core/header_test.go
@@ -8,8 +8,9 @@ import (
 	"github.com/stretchr/testify/require"
 	"github.com/tendermint/tendermint/libs/rand"
 
+	"github.com/celestiaorg/celestia-node/header/headertest"
+
 	"github.com/celestiaorg/celestia-node/header"
-	"github.com/celestiaorg/celestia-node/headertest"
 )
 
 func TestMakeExtendedHeaderForEmptyBlock(t *testing.T) {
diff --git a/das/daser_test.go b/das/daser_test.go
index 8d0a33e0..4de53315 100644
--- a/das/daser_test.go
+++ b/das/daser_test.go
@@ -16,9 +16,10 @@ import (
 	"github.com/stretchr/testify/require"
 	"github.com/tendermint/tendermint/types"
 
+	"github.com/celestiaorg/celestia-node/header/headertest"
+
 	"github.com/celestiaorg/celestia-node/fraud"
 	"github.com/celestiaorg/celestia-node/header"
-	"github.com/celestiaorg/celestia-node/headertest"
 	libhead "github.com/celestiaorg/celestia-node/libs/header"
 	"github.com/celestiaorg/celestia-node/share"
 	"github.com/celestiaorg/celestia-node/share/availability/full"
diff --git a/fraud/testing.go b/fraud/testing.go
index 355d0440..feb11044 100644
--- a/fraud/testing.go
+++ b/fraud/testing.go
@@ -14,8 +14,9 @@ import (
 	mocknet "github.com/libp2p/go-libp2p/p2p/net/mock"
 	"github.com/stretchr/testify/require"
 
+	"github.com/celestiaorg/celestia-node/header/headertest"
+
 	"github.com/celestiaorg/celestia-node/header"
-	"github.com/celestiaorg/celestia-node/headertest"
 )
 
 type DummyService struct {
diff --git a/headertest/serde_test.go b/header/headertest/serde_test.go
similarity index 100%
rename from headertest/serde_test.go
rename to header/headertest/serde_test.go
diff --git a/headertest/testing.go b/header/headertest/testing.go
similarity index 100%
rename from headertest/testing.go
rename to header/headertest/testing.go
diff --git a/header/headertest/verify_test.go b/header/headertest/verify_test.go
new file mode 100644
index 00000000..9a338b8f
--- /dev/null
+++ b/header/headertest/verify_test.go
@@ -0,0 +1,96 @@
+package headertest
+
+import (
+	"strconv"
+	"testing"
+	"time"
+
+	"github.com/stretchr/testify/assert"
+
+	libhead "github.com/celestiaorg/celestia-node/libs/header"
+
+	tmrand "github.com/tendermint/tendermint/libs/rand"
+)
+
+func TestVerify(t *testing.T) {
+	h := NewTestSuite(t, 2).GenExtendedHeaders(3)
+	trusted, untrustedAdj, untrustedNonAdj := h[0], h[1], h[2]
+	tests := []struct {
+		prepare func() libhead.Header
+		err     bool
+	}{
+		{
+			prepare: func() libhead.Header { return untrustedAdj },
+			err:     false,
+		},
+		{
+			prepare: func() libhead.Header {
+				return untrustedNonAdj
+			},
+			err: false,
+		},
+		{
+			prepare: func() libhead.Header {
+				untrusted := *untrustedAdj
+				untrusted.ValidatorsHash = tmrand.Bytes(32)
+				return &untrusted
+			},
+			err: true,
+		},
+		{
+			prepare: func() libhead.Header {
+				untrusted := *untrustedNonAdj
+				untrusted.Commit = NewTestSuite(t, 2).Commit(RandRawHeader(t))
+				return &untrusted
+			},
+			err: true,
+		},
+		{
+			prepare: func() libhead.Header {
+				untrusted := *untrustedAdj
+				untrusted.RawHeader.LastBlockID.Hash = tmrand.Bytes(32)
+				return &untrusted
+			},
+			err: true,
+		},
+		{
+			prepare: func() libhead.Header {
+				untrustedAdj.RawHeader.Time = untrustedAdj.RawHeader.Time.Add(time.Minute)
+				return untrustedAdj
+			},
+			err: true,
+		},
+		{
+			prepare: func() libhead.Header {
+				untrustedAdj.RawHeader.Time = untrustedAdj.RawHeader.Time.Truncate(time.Hour)
+				return untrustedAdj
+			},
+			err: true,
+		},
+		{
+			prepare: func() libhead.Header {
+				untrustedAdj.RawHeader.ChainID = "toaster"
+				return untrustedAdj
+			},
+			err: true,
+		},
+		{
+			prepare: func() libhead.Header {
+				untrustedAdj.RawHeader.Height++
+				return untrustedAdj
+			},
+			err: true,
+		},
+	}
+
+	for i, test := range tests {
+		t.Run(strconv.Itoa(i), func(t *testing.T) {
+			err := trusted.Verify(test.prepare())
+			if test.err {
+				assert.Error(t, err)
+			} else {
+				assert.NoError(t, err)
+			}
+		})
+	}
+}
diff --git a/headertest/verify_test.go b/headertest/verify_test.go
deleted file mode 100644
index 03aab15b..00000000
--- a/headertest/verify_test.go
+++ /dev/null
@@ -1,67 +0,0 @@
-package headertest
-
-import (
-	"strconv"
-	"testing"
-	"time"
-
-	"github.com/stretchr/testify/assert"
-
-	tmrand "github.com/tendermint/tendermint/libs/rand"
-)
-
-func TestVerifyAdjacent(t *testing.T) {
-	h := NewTestSuite(t, 2).GenExtendedHeaders(2)
-	trusted, untrusted := h[0], h[1]
-	tests := []struct {
-		prepare func()
-		err     bool
-	}{
-		{
-			prepare: func() {},
-			err:     false,
-		},
-		{
-			prepare: func() {
-				untrusted.ValidatorsHash = tmrand.Bytes(32)
-			},
-			err: true,
-		},
-		{
-			prepare: func() {
-				untrusted.RawHeader.Time = untrusted.RawHeader.Time.Add(time.Minute)
-			},
-			err: true,
-		},
-		{
-			prepare: func() {
-				untrusted.RawHeader.Time = untrusted.RawHeader.Time.Truncate(time.Hour)
-			},
-			err: true,
-		},
-		{
-			prepare: func() {
-				untrusted.RawHeader.ChainID = "toaster"
-			},
-			err: true,
-		},
-		{
-			prepare: func() {
-				untrusted.RawHeader.Height++
-			},
-			err: true,
-		},
-	}
-
-	for i, test := range tests {
-		t.Run(strconv.Itoa(i), func(t *testing.T) {
-			test.prepare()
-			err := trusted.VerifyAdjacent(untrusted)
-			if test.err {
-				assert.Error(t, err)
-			} else {
-				assert.NoError(t, err)
-			}
-		})
-	}
-}
diff --git a/libs/header/p2p/exchange_test.go b/libs/header/p2p/exchange_test.go
index 7d6175d2..c9a24141 100644
--- a/libs/header/p2p/exchange_test.go
+++ b/libs/header/p2p/exchange_test.go
@@ -79,7 +79,7 @@ func TestExchange_RequestVerifiedHeadersFails(t *testing.T) {
 	ctx, cancel := context.WithTimeout(context.Background(), time.Millisecond*500)
 	t.Cleanup(cancel)
 	_, err := exchg.GetVerifiedRange(ctx, h, 3)
-	require.Error(t, err)
+	assert.Error(t, err)
 
 	// ensure that peer was added to the blacklist
 	peers := exchg.peerTracker.connGater.ListBlockedPeers()
diff --git a/libs/header/sync/sync_test.go b/libs/header/sync/sync_test.go
index 89d3e9eb..44dd0179 100644
--- a/libs/header/sync/sync_test.go
+++ b/libs/header/sync/sync_test.go
@@ -288,7 +288,7 @@ func TestSyncer_FindHeadersReturnsCorrectRange(t *testing.T) {
 	require.Equal(t, h[len(h)-1].Height(), int64(21))
 	header := h[0]
 	for i := 1; i < len(h); i++ {
-		require.NoError(t, header.VerifyAdjacent(h[i]))
+		require.NoError(t, header.Verify(h[i]))
 		header = h[i]
 	}
 }
diff --git a/libs/header/test/testing.go b/libs/header/test/testing.go
index b1c9016a..5f0a3d4c 100644
--- a/libs/header/test/testing.go
+++ b/libs/header/test/testing.go
@@ -6,7 +6,6 @@ import (
 	"crypto/rand"
 	"encoding/binary"
 	"encoding/gob"
-	"errors"
 	"fmt"
 	"math"
 	"testing"
@@ -84,35 +83,18 @@ func (d *DummyHeader) IsExpired(period time.Duration) bool {
 	return expirationTime.Before(time.Now())
 }
 
-func (d *DummyHeader) VerifyAdjacent(other header.Header) error {
-	if other.Height() != d.Height()+1 {
-		return fmt.Errorf("invalid Height, expected: %d, got: %d", d.Height()+1, other.Height())
-	}
-
-	if err := d.verify(other); err != nil {
-		return err
-	}
-
-	return nil
-}
-
-func (d *DummyHeader) VerifyNonAdjacent(other header.Header) error {
-	return d.verify(other)
-}
-
-func (d *DummyHeader) verify(header header.Header) error {
-	// wee1
+func (d *DummyHeader) Verify(header header.Header) error {
 	epsilon := 10 * time.Second
 	if header.Time().After(time.Now().Add(epsilon)) {
-		return errors.New("header Time too far in the future")
+		return fmt.Errorf("header Time too far in the future")
 	}
 
 	if header.Height() <= d.Height() {
-		return errors.New("expected new header Height to be larger than old header Time")
+		return fmt.Errorf("expected new header Height to be larger than old header Time")
 	}
 
 	if header.Time().Before(d.Time()) {
-		return errors.New("expected new header Time to be after old header Time")
+		return fmt.Errorf("expected new header Time to be after old header Time")
 	}
 
 	return nil
diff --git a/nodebuilder/testing.go b/nodebuilder/testing.go
index ccbb9f3a..78063254 100644
--- a/nodebuilder/testing.go
+++ b/nodebuilder/testing.go
@@ -12,7 +12,7 @@ import (
 
 	"github.com/celestiaorg/celestia-node/core"
 	coreheader "github.com/celestiaorg/celestia-node/header"
-	"github.com/celestiaorg/celestia-node/headertest"
+	"github.com/celestiaorg/celestia-node/header/headertest"
 	"github.com/celestiaorg/celestia-node/libs/fxutil"
 	"github.com/celestiaorg/celestia-node/libs/header/mocks"
 	"github.com/celestiaorg/celestia-node/nodebuilder/header"
diff --git a/nodebuilder/tests/fraud_test.go b/nodebuilder/tests/fraud_test.go
index ba065a25..ac25106f 100644
--- a/nodebuilder/tests/fraud_test.go
+++ b/nodebuilder/tests/fraud_test.go
@@ -10,8 +10,9 @@ import (
 	"github.com/libp2p/go-libp2p/core/peer"
 	"github.com/stretchr/testify/require"
 
+	"github.com/celestiaorg/celestia-node/header/headertest"
+
 	"github.com/celestiaorg/celestia-node/fraud"
-	"github.com/celestiaorg/celestia-node/headertest"
 	"github.com/celestiaorg/celestia-node/nodebuilder"
 	"github.com/celestiaorg/celestia-node/nodebuilder/core"
 	"github.com/celestiaorg/celestia-node/nodebuilder/node"
diff --git a/share/eds/retriever_test.go b/share/eds/retriever_test.go
index cc398890..182d5720 100644
--- a/share/eds/retriever_test.go
+++ b/share/eds/retriever_test.go
@@ -12,6 +12,8 @@ import (
 	"github.com/stretchr/testify/assert"
 	"github.com/stretchr/testify/require"
 
+	"github.com/celestiaorg/celestia-node/header/headertest"
+
 	"github.com/celestiaorg/celestia-app/pkg/da"
 	"github.com/celestiaorg/celestia-app/pkg/wrapper"
 	"github.com/celestiaorg/nmt"
@@ -19,7 +21,6 @@ import (
 
 	"github.com/celestiaorg/celestia-node/fraud"
 	"github.com/celestiaorg/celestia-node/header"
-	"github.com/celestiaorg/celestia-node/headertest"
 	"github.com/celestiaorg/celestia-node/share"
 	"github.com/celestiaorg/celestia-node/share/eds/byzantine"
 	"github.com/celestiaorg/celestia-node/share/ipld"