immundb has insufficient verification of data authenticity

@@ -0,0 +1,98 @@
+/*
+Copyright 2022 Codenotary Inc. All rights reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+	http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+package schema
+
+import (
+	"context"
+	"crypto/sha256"
+
+	"github.com/codenotary/immudb/embedded/store"
+)
+
+func minUint64(a, b uint64) uint64 {
+	if a < b {
+		return a
+	}
+	return b
+}
+
+func FillMissingLinearAdvanceProof(
+	ctx context.Context,
+	proof *store.DualProof,
+	sourceTxID uint64,
+	targetTxID uint64,
+	imc ImmuServiceClient,
+) error {
+	if proof.LinearAdvanceProof != nil {
+		// The proof is already present, no need to fill it in
+		return nil
+	}
+
+	// Early preconditions that indicate a broken proof anyway
+	if proof == nil ||
+		proof.SourceTxHeader == nil ||
+		proof.TargetTxHeader == nil ||
+		proof.SourceTxHeader.ID != sourceTxID ||
+		proof.TargetTxHeader.ID != targetTxID {
+		return nil
+	}
+
+	// Find the range startTxID / endTxID to fill with linear inclusion proof
+	startTxID := proof.SourceTxHeader.BlTxID
+	endTxID := minUint64(sourceTxID, proof.TargetTxHeader.BlTxID)
+
+	if endTxID <= startTxID+1 {
+		// Linear Advance Proof is not needed
+		return nil
+	}
+
+	lAdvProof := &store.LinearAdvanceProof{
+		InclusionProofs: make([][][sha256.Size]byte, endTxID-startTxID-1),
+	}
+
+	// Fill in inclusion proofs for subsequent transactions
+	for txID := startTxID + 1; txID < endTxID; txID++ {
+		partialProof, err := imc.VerifiableTxById(ctx, &VerifiableTxRequest{
+			Tx:           targetTxID,
+			ProveSinceTx: txID,
+			// Add entries spec to exclude any entries
+			EntriesSpec: &EntriesSpec{KvEntriesSpec: &EntryTypeSpec{Action: EntryTypeAction_EXCLUDE}},
+		})
+		if err != nil {
+			return err
+		}
+		lAdvProof.InclusionProofs[txID-startTxID-1] = DigestsFromProto(partialProof.DualProof.InclusionProof)
+	}
+
+	// Get the linear proof for the whole chain
+	partialProof, err := imc.VerifiableTxById(ctx, &VerifiableTxRequest{
+		Tx:           endTxID,
+		ProveSinceTx: startTxID + 1,
+		// Add entries spec to exclude any entries
+		EntriesSpec: &EntriesSpec{KvEntriesSpec: &EntryTypeSpec{Action: EntryTypeAction_EXCLUDE}},
+	})
+	if err != nil {
+		// Note: We don't check whether the proof returned from the server is correct here.
+		// If there's any inconsistency, the proof validation will fail detecting incorrect
+		// response from the server.
+		return err
+	}
+	lAdvProof.LinearProofTerms = DigestsFromProto(partialProof.DualProof.LinearProof.Terms)
+
+	proof.LinearAdvanceProof = lAdvProof
+	return nil
+}

@@ -308,8 +308,20 @@ func (a *defaultAuditor) audit() error {
 			return noErr
 		}
 
+		dualProof := schema.DualProofFromProto(vtx.DualProof)
+		err = schema.FillMissingLinearAdvanceProof(
+			ctx, dualProof, prevState.TxId, state.TxId, a.serviceClient,
+		)
+		if err != nil {
+			a.logger.Errorf(
+				"error fetching consistency proof for previous state %d: %v",
+				prevState.TxId, err)
+			withError = true
+			return noErr
+		}
+
 		verified = store.VerifyDualProof(
-			schema.DualProofFromProto(vtx.DualProof),
+			dualProof,
 			prevState.TxId,
 			state.TxId,
 			schema.DigestFromProto(prevState.TxHash),

@@ -1051,6 +1051,35 @@ func (c *immuClient) VerifiedGetAtRevision(ctx context.Context, key []byte, rev
 	return c.VerifiedGet(ctx, key, AtRevision(rev))
 }
 
+func (c *immuClient) verifyDualProof(
+	ctx context.Context,
+	dualProof *store.DualProof,
+	sourceID uint64,
+	targetID uint64,
+	sourceAlh [sha256.Size]byte,
+	targetAlh [sha256.Size]byte,
+) error {
+	err := schema.FillMissingLinearAdvanceProof(
+		ctx, dualProof, sourceID, targetID, c.ServiceClient,
+	)
+	if err != nil {
+		return err
+	}
+
+	verifies := store.VerifyDualProof(
+		dualProof,
+		sourceID,
+		targetID,
+		sourceAlh,
+		targetAlh,
+	)
+	if !verifies {
+		return store.ErrCorruptedData
+	}
+
+	return nil
+}
+
 func (c *immuClient) verifiedGet(ctx context.Context, kReq *schema.KeyRequest) (vi *schema.Entry, err error) {
 	err = c.StateService.CacheLock()
 	if err != nil {
@@ -1134,15 +1163,16 @@ func (c *immuClient) verifiedGet(ctx context.Context, kReq *schema.KeyRequest) (
 	}
 
 	if state.TxId > 0 {
-		verifies = store.VerifyDualProof(
+		err := c.verifyDualProof(
+			ctx,
 			dualProof,
 			sourceID,
 			targetID,
 			sourceAlh,
 			targetAlh,
 		)
-		if !verifies {
-			return nil, store.ErrCorruptedData
+		if err != nil {
+			return nil, err
 		}
 	}
 
@@ -1313,16 +1343,17 @@ func (c *immuClient) VerifiedSet(ctx context.Context, key []byte, value []byte)
 	targetAlh = tx.Header().Alh()
 
 	if state.TxId > 0 {
-		verifies = store.VerifyDualProof(
-			schema.DualProofFromProto(verifiableTx.DualProof),
+		dualProof := schema.DualProofFromProto(verifiableTx.DualProof)
+		err := c.verifyDualProof(
+			ctx,
+			dualProof,
 			sourceID,
 			targetID,
 			sourceAlh,
 			targetAlh,
 		)
-
-		if !verifies {
-			return nil, store.ErrCorruptedData
+		if err != nil {
+			return nil, err
 		}
 	}
 
@@ -1509,15 +1540,16 @@ func (c *immuClient) VerifiedTxByID(ctx context.Context, tx uint64) (*schema.Tx,
 	}
 
 	if state.TxId > 0 {
-		verifies := store.VerifyDualProof(
+		err := c.verifyDualProof(
+			ctx,
 			dualProof,
 			sourceID,
 			targetID,
 			sourceAlh,
 			targetAlh,
 		)
-		if !verifies {
-			return nil, store.ErrCorruptedData
+		if err != nil {
+			return nil, err
 		}
 	}
 
@@ -1691,15 +1723,17 @@ func (c *immuClient) VerifiedSetReferenceAt(ctx context.Context, key []byte, ref
 	targetAlh = tx.Header().Alh()
 
 	if state.TxId > 0 {
-		verifies = store.VerifyDualProof(
-			schema.DualProofFromProto(verifiableTx.DualProof),
+		dualProof := schema.DualProofFromProto(verifiableTx.DualProof)
+		err := c.verifyDualProof(
+			ctx,
+			dualProof,
 			sourceID,
 			targetID,
 			sourceAlh,
 			targetAlh,
 		)
-		if !verifies {
-			return nil, store.ErrCorruptedData
+		if err != nil {
+			return nil, err
 		}
 	}
 
@@ -1862,15 +1896,17 @@ func (c *immuClient) VerifiedZAddAt(ctx context.Context, set []byte, score float
 	targetAlh = tx.Header().Alh()
 
 	if state.TxId > 0 {
-		verifies = store.VerifyDualProof(
-			schema.DualProofFromProto(vtx.DualProof),
+		dualProof := schema.DualProofFromProto(vtx.DualProof)
+		err := c.verifyDualProof(
+			ctx,
+			dualProof,
 			sourceID,
 			targetID,
 			sourceAlh,
 			targetAlh,
 		)
-		if !verifies {
-			return nil, store.ErrCorruptedData
+		if err != nil {
+			return nil, err
 		}
 	}
 

@@ -213,15 +213,16 @@ func (c *immuClient) VerifyRow(ctx context.Context, row *schema.Row, table strin
 	}
 
 	if state.TxId > 0 {
-		verifies = store.VerifyDualProof(
+		err := c.verifyDualProof(
+			ctx,
 			dualProof,
 			sourceID,
 			targetID,
 			sourceAlh,
 			targetAlh,
 		)
-		if !verifies {
-			return store.ErrCorruptedData
+		if err != nil {
+			return err
 		}
 	}
 

@@ -246,16 +246,17 @@ func (c *immuClient) _streamVerifiedSet(ctx context.Context, kvs []*stream.KeyVa
 	targetAlh = tx.Header().Alh()
 
 	if state.TxId > 0 {
-		verifies = store.VerifyDualProof(
-			schema.DualProofFromProto(verifiableTx.DualProof),
+		dualProof := schema.DualProofFromProto(verifiableTx.DualProof)
+		err := c.verifyDualProof(
+			ctx,
+			dualProof,
 			sourceID,
 			targetID,
 			sourceAlh,
 			targetAlh,
 		)
-
-		if !verifies {
-			return nil, store.ErrCorruptedData
+		if err != nil {
+			return nil, err
 		}
 	}
 
@@ -360,15 +361,16 @@ func (c *immuClient) _streamVerifiedGet(ctx context.Context, req *schema.Verifia
 	}
 
 	if state.TxId > 0 {
-		verifies = store.VerifyDualProof(
+		err := c.verifyDualProof(
+			ctx,
 			dualProof,
 			sourceID,
 			targetID,
 			sourceAlh,
 			targetAlh,
 		)
-		if !verifies {
-			return nil, store.ErrCorruptedData
+		if err != nil {
+			return nil, err
 		}
 	}
 

@@ -24,10 +24,12 @@ import (
 
 	"github.com/codenotary/immudb/pkg/api/schema"
 	"github.com/codenotary/immudb/pkg/client"
+	"github.com/codenotary/immudb/pkg/client/state"
 	"github.com/codenotary/immudb/pkg/fs"
 	"github.com/codenotary/immudb/pkg/server"
 	"github.com/codenotary/immudb/pkg/server/servertest"
 	"github.com/stretchr/testify/require"
+	"google.golang.org/grpc"
 	"google.golang.org/protobuf/types/known/emptypb"
 )
 
@@ -38,6 +40,8 @@ type stateServiceMock struct {
 	stateHistory map[uint64]*schema.ImmutableState
 }
 
+var _ state.StateService = (*stateServiceMock)(nil)
+
 func newServiceStateMock() *stateServiceMock {
 	return &stateServiceMock{
 		state:        &schema.ImmutableState{TxId: 0},
@@ -71,6 +75,25 @@ func (ssm *stateServiceMock) CacheUnlock() error {
 	return nil
 }
 
+func (ssm *stateServiceMock) SetServerIdentity(identity string) {}
+
+type clientProxyRemovingLinearAdvanceProof struct {
+	schema.ImmuServiceClient
+}
+
+func (mock *clientProxyRemovingLinearAdvanceProof) VerifiableTxById(
+	ctx context.Context, in *schema.VerifiableTxRequest, opts ...grpc.CallOption,
+) (
+	*schema.VerifiableTx, error,
+) {
+	ret, err := mock.ImmuServiceClient.VerifiableTxById(ctx, in)
+	if ret != nil && ret.DualProof != nil {
+		// Cleanup the linear advance proof so that it gets regenerated
+		ret.DualProof.LinearAdvanceProof = nil
+	}
+	return ret, err
+}
+
 func TestLongLinearProofVerification(t *testing.T) {
 	// Start the server with transaction data containing long linear proof
 	dir := t.TempDir()
@@ -151,15 +174,37 @@ func TestLongLinearProofVerification(t *testing.T) {
 	})
 
 	t.Run("Exhaustive consistency proof", func(t *testing.T) {
-		for i := uint64(1); i <= txCount; i++ {
-			for j := i; j <= txCount; j++ {
-				ssm.state = ssm.stateHistory[i]
 
-				_, err = cl.VerifiedTxByID(context.Background(), j)
-				require.NoError(t, err)
-				require.EqualValues(t, j, ssm.state.TxId)
+		t.Run("server-generated linear advance proof", func(t *testing.T) {
+			for i := uint64(1); i <= txCount; i++ {
+				for j := i; j <= txCount; j++ {
+					ssm.state = ssm.stateHistory[i]
+
+					_, err = cl.VerifiedTxByID(context.Background(), j)
+					require.NoError(t, err)
+					require.EqualValues(t, j, ssm.state.TxId)
+				}
 			}
-		}
+		})
+
+		t.Run("client-reconstructed linear advance proof", func(t *testing.T) {
+
+			scl := cl.GetServiceClient()
+			// Mock service client that removes linear advance proofs
+			// that will mimic the behavior of older servers
+			cl.WithServiceClient(&clientProxyRemovingLinearAdvanceProof{ImmuServiceClient: scl})
+
+			for i := uint64(1); i <= txCount; i++ {
+				for j := i + 5; j <= txCount; j++ {
+
+					ssm.state = ssm.stateHistory[i]
+
+					_, err = cl.VerifiedTxByID(context.Background(), j)
+					require.NoError(t, err)
+					require.EqualValues(t, j, ssm.state.TxId)
+				}
+			}
+		})
 	})
 
 }

@@ -417,3 +417,95 @@ func TestVerifyDualProofLongLinearProofWithReplica(t *testing.T) {
 	})
 
 }
+
+func TestGenerateDataWithLongLinearProof(t *testing.T) {
+	const (
+		initialNormalTxCount = 10
+		linearTxCount        = 10
+		finalNormalTxCount   = 10
+	)
+
+	opts := DefaultOptions().WithSynced(false).WithMaxLinearProofLen(100).WithMaxConcurrency(1)
+	dir := t.TempDir()
+	immuStore, err := Open(dir, opts)
+	require.NoError(t, err)
+	defer func() {
+		if immuStore != nil {
+			immustoreClose(t, immuStore)
+		}
+	}()
+
+	t.Run("Prepare initial normal transactions", func(t *testing.T) {
+		for i := 0; i < initialNormalTxCount; i++ {
+			tx, err := immuStore.NewWriteOnlyTx()
+			require.NoError(t, err)
+
+			err = tx.Set([]byte(fmt.Sprintf("step1:key:%d", i)), nil, []byte(fmt.Sprintf("value:%d", i)))
+			require.NoError(t, err)
+
+			txhdr, err := tx.AsyncCommit()
+			require.NoError(t, err)
+			require.EqualValues(t, i+1, txhdr.ID)
+			require.EqualValues(t, i, txhdr.BlTxID)
+
+			immuStore.ahtWHub.WaitFor(txhdr.ID, nil)
+		}
+	})
+
+	t.Run("Add transactions with long linear proof", func(t *testing.T) {
+		// Disable binary linking and restore before we finish this step
+		immuStore.blDone <- struct{}{}
+		defer func() {
+			go immuStore.binaryLinking()
+			immuStore.ahtWHub.WaitFor(initialNormalTxCount+linearTxCount, nil)
+		}()
+
+		for i := 0; i < linearTxCount; i++ {
+			tx, err := immuStore.NewWriteOnlyTx()
+			require.NoError(t, err)
+
+			err = tx.Set([]byte(fmt.Sprintf("step2:key:%d", i)), nil, []byte(fmt.Sprintf("value:%d", i)))
+			require.NoError(t, err)
+
+			txhdr, err := tx.AsyncCommit()
+			require.NoError(t, err)
+			require.EqualValues(t, i+1+initialNormalTxCount, txhdr.ID)
+			require.EqualValues(t, initialNormalTxCount, txhdr.BlTxID)
+		}
+	})
+
+	t.Run("Add normal transactions at the end", func(t *testing.T) {
+		for i := 0; i < finalNormalTxCount; i++ {
+			tx, err := immuStore.NewWriteOnlyTx()
+			require.NoError(t, err)
+
+			err = tx.Set([]byte(fmt.Sprintf("step3:key:%d", i)), nil, []byte(fmt.Sprintf("value:%d", i)))
+			require.NoError(t, err)
+
+			txhdr, err := tx.AsyncCommit()
+			require.NoError(t, err)
+			require.EqualValues(t, i+1+initialNormalTxCount+linearTxCount, txhdr.ID)
+			require.EqualValues(t, i+initialNormalTxCount+linearTxCount, txhdr.BlTxID)
+
+			immuStore.ahtWHub.WaitFor(txhdr.ID, nil)
+		}
+	})
+
+	t.Run("copy database files to test folder", func(t *testing.T) {
+		err := immuStore.Sync()
+		require.NoError(t, err)
+
+		err = immuStore.Close()
+		require.NoError(t, err)
+		immuStore = nil
+
+		destPath := "../../test/data_long_linear_proof"
+		copier := fs.NewStandardCopier()
+
+		err = os.RemoveAll(destPath)
+		require.NoError(t, err)
+
+		err = copier.CopyDir(dir, destPath)
+		require.NoError(t, err)
+	})
+}

@@ -1866,6 +1866,7 @@ type DualProof struct {
 	TargetBlTxAlh      [sha256.Size]byte
 	LastInclusionProof [][sha256.Size]byte
 	LinearProof        *LinearProof
+	LinearAdvanceProof *LinearAdvanceProof
 }
 
 // DualProof combines linear cryptographic linking i.e. transactions include the linear accumulative hash up to the previous one,
@@ -1931,6 +1932,16 @@ func (s *ImmuStore) DualProof(sourceTxHdr, targetTxHdr *TxHeader) (proof *DualPr
 	}
 	proof.LinearProof = lproof
 
+	laproof, err := s.LinearAdvanceProof(
+		sourceTxHdr.BlTxID,
+		minUint64(sourceTxHdr.ID, targetTxHdr.BlTxID),
+		targetTxHdr.BlTxID,
+	)
+	if err != nil {
+		return nil, err
+	}
+	proof.LinearAdvanceProof = laproof
+
 	return
 }
 
@@ -1985,6 +1996,64 @@ func (s *ImmuStore) LinearProof(sourceTxID, targetTxID uint64) (*LinearProof, er
 	}, nil
 }
 
+// LinearAdvanceProof returns additional inclusion proof for part of the old linear proof consumed by
+// the new Merkle Tree
+func (s *ImmuStore) LinearAdvanceProof(sourceTxID, targetTxID uint64, targetBlTxID uint64) (*LinearAdvanceProof, error) {
+	if targetTxID < sourceTxID {
+		return nil, ErrSourceTxNewerThanTargetTx
+	}
+
+	if targetTxID <= sourceTxID+1 {
+		// Additional proof is not needed
+		return nil, nil
+	}
+
+	tx, err := s.fetchAllocTx()
+	if err != nil {
+		return nil, err
+	}
+	defer s.releaseAllocTx(tx)
+
+	r, err := s.NewTxReader(sourceTxID+1, false, tx)
+	if err != nil {
+		return nil, err
+	}
+
+	tx, err = r.Read()
+	if err != nil {
+		return nil, err
+	}
+
+	linearProofTerms := make([][sha256.Size]byte, targetTxID-sourceTxID)
+	linearProofTerms[0] = tx.header.Alh()
+
+	inclusionProofs := make([][][sha256.Size]byte, targetTxID-sourceTxID-1)
+
+	for txID := sourceTxID + 1; txID < targetTxID; txID++ {
+		inclusionProof, err := s.aht.InclusionProof(txID, targetBlTxID)
+		if err != nil {
+			return nil, err
+		}
+		inclusionProofs[txID-sourceTxID-1] = inclusionProof
+
+		tx, err := r.Read()
+		if err != nil {
+			return nil, err
+		}
+		linearProofTerms[txID-sourceTxID] = tx.Header().innerHash()
+	}
+
+	return &LinearAdvanceProof{
+		LinearProofTerms: linearProofTerms,
+		InclusionProofs:  inclusionProofs,
+	}, nil
+}
+
+type LinearAdvanceProof struct {
+	LinearProofTerms [][sha256.Size]byte
+	InclusionProofs  [][][sha256.Size]byte
+}
+
 func (s *ImmuStore) txOffsetAndSize(txID uint64) (int64, int, error) {
 	if txID == 0 {
 		return 0, 0, ErrIllegalArguments
@@ -2772,3 +2841,10 @@ func maxUint64(a, b uint64) uint64 {
 	}
 	return a
 }
+
+func minUint64(a, b uint64) uint64 {
+	if a >= b {
+		return b
+	}
+	return a
+}

@@ -5,7 +5,7 @@ Licensed under the Apache License, Version 2.0 (the "License");
 you may not use this file except in compliance with the License.
 You may obtain a copy of the License at
 
-	http://www.apache.org/licenses/LICENSE-2.0
+    http://www.apache.org/licenses/LICENSE-2.0
 
 Unless required by applicable law or agreed to in writing, software
 distributed under the License is distributed on an "AS IS" BASIS,
@@ -28,6 +28,14 @@ func VerifyInclusion(proof *htree.InclusionProof, entryDigest, root [sha256.Size
 	return htree.VerifyInclusion(proof, entryDigest, root)
 }
 
+func advanceLinearHash(alh [sha256.Size]byte, txID uint64, term [sha256.Size]byte) [sha256.Size]byte {
+	var bs [txIDSize + 2*sha256.Size]byte
+	binary.BigEndian.PutUint64(bs[:], txID)
+	copy(bs[txIDSize:], alh[:])
+	copy(bs[txIDSize+sha256.Size:], term[:]) // innerHash = hash(ts + mdLen + md + nentries + eH + blTxID + blRoot)
+	return sha256.Sum256(bs[:])              // hash(txID + prevAlh + innerHash)
+}
+
 func VerifyLinearProof(proof *LinearProof, sourceTxID, targetTxID uint64, sourceAlh, targetAlh [sha256.Size]byte) bool {
 	if proof == nil || proof.SourceTxID != sourceTxID || proof.TargetTxID != targetTxID {
 		return false
@@ -45,16 +53,77 @@ func VerifyLinearProof(proof *LinearProof, sourceTxID, targetTxID uint64, source
 	calculatedAlh := proof.Terms[0]
 
 	for i := 1; i < len(proof.Terms); i++ {
-		var bs [txIDSize + 2*sha256.Size]byte
-		binary.BigEndian.PutUint64(bs[:], proof.SourceTxID+uint64(i))
-		copy(bs[txIDSize:], calculatedAlh[:])
-		copy(bs[txIDSize+sha256.Size:], proof.Terms[i][:]) // innerHash = hash(ts + mdLen + md + nentries + eH + blTxID + blRoot)
-		calculatedAlh = sha256.Sum256(bs[:])               // hash(txID + prevAlh + innerHash)
+		calculatedAlh = advanceLinearHash(calculatedAlh, proof.SourceTxID+uint64(i), proof.Terms[i])
 	}
 
 	return targetAlh == calculatedAlh
 }
 
+func VerifyLinearAdvanceProof(
+	proof *LinearAdvanceProof,
+	startTxID uint64,
+	endTxID uint64,
+	endAlh [sha256.Size]byte,
+	treeRoot [sha256.Size]byte,
+	treeSize uint64,
+) bool {
+	//
+	//       Old
+	//  \ Merkle Tree
+	//   \
+	//    \
+	//     \              Additional Inclusion proof
+	//      \                  for those nodes
+	//       \                in new Merkle Tree
+	//        \            ......................
+	//         \          /                      \
+	//          \
+	//           \+--+     +--+     +--+     +--+     +--+
+	// -----------|  |-----|  |-----|  |-----|  |-----|  |
+	//            +--+     +--+     +--+     +--+     +--+
+	//
+	//         startTxID                            endTxID
+	//
+
+	if endTxID < startTxID {
+		// This must not happen - that's an invalid proof
+		return false
+	}
+
+	if endTxID <= startTxID+1 {
+		// Linear Advance Proof is not needed
+		return true
+	}
+
+	if proof == nil ||
+		len(proof.LinearProofTerms) != int(endTxID-startTxID) ||
+		len(proof.InclusionProofs) != int(endTxID-startTxID)-1 {
+		// Check more preconditions that would indicate broken proof
+		return false
+	}
+
+	calculatedAlh := proof.LinearProofTerms[0] // alh at startTx+1
+	for txID := startTxID + 1; txID < endTxID; txID++ {
+
+		// Ensure the node in the chain is included in the target Merkle Tree
+		if !ahtree.VerifyInclusion(
+			proof.InclusionProofs[txID-startTxID-1],
+			txID,
+			treeSize,
+			leafFor(calculatedAlh),
+			treeRoot,
+		) {
+			return false
+		}
+
+		// Get the Alh for the next transaction
+		calculatedAlh = advanceLinearHash(calculatedAlh, txID+1, proof.LinearProofTerms[txID-startTxID])
+	}
+
+	// We must end up with the final Alh - that one is also checked for inclusion but in different part of the proof
+	return calculatedAlh == endAlh
+}
+
 func VerifyDualProof(proof *DualProof, sourceTxID, targetTxID uint64, sourceAlh, targetAlh [sha256.Size]byte) bool {
 	if proof == nil ||
 		proof.SourceTxHeader == nil ||
@@ -93,15 +162,15 @@ func VerifyDualProof(proof *DualProof, sourceTxID, targetTxID uint64, sourceAlh,
 	}
 
 	if proof.SourceTxHeader.BlTxID > 0 {
-		verfifies := ahtree.VerifyConsistency(
+		verifies := ahtree.VerifyConsistency(
 			proof.ConsistencyProof,
 			proof.SourceTxHeader.BlTxID,
 			proof.TargetTxHeader.BlTxID,
 			proof.SourceTxHeader.BlRoot,
 			proof.TargetTxHeader.BlRoot,
 		)
 
-		if !verfifies {
+		if !verifies {
 			return false
 		}
 	}
@@ -120,10 +189,49 @@ func VerifyDualProof(proof *DualProof, sourceTxID, targetTxID uint64, sourceAlh,
 	}
 
 	if sourceTxID < proof.TargetTxHeader.BlTxID {
-		return VerifyLinearProof(proof.LinearProof, proof.TargetTxHeader.BlTxID, targetTxID, proof.TargetBlTxAlh, targetAlh)
+		verifies := VerifyLinearProof(proof.LinearProof, proof.TargetTxHeader.BlTxID, targetTxID, proof.TargetBlTxAlh, targetAlh)
+		if !verifies {
+			return false
+		}
+
+		// Verify that the part of the linear proof consumed by the new merkle tree is consistent with that Merkle Tree
+		// In this case, this is the whole chain to the SourceTxID from the previous Merkle Tree.
+		// The sourceTxID consistency is already proven using proof.InclusionProof
+		if !VerifyLinearAdvanceProof(
+			proof.LinearAdvanceProof,
+			proof.SourceTxHeader.BlTxID,
+			sourceTxID,
+			sourceAlh,
+			proof.TargetTxHeader.BlRoot,
+			proof.TargetTxHeader.BlTxID,
+		) {
+			return false
+		}
+
+	} else {
+
+		verifies := VerifyLinearProof(proof.LinearProof, sourceTxID, targetTxID, sourceAlh, targetAlh)
+		if !verifies {
+			return false
+		}
+
+		// Verify that the part of the linear proof consumed by the new merkle tree is consistent with that Merkle Tree
+		// In this case, this is the whole linear chain between the old Merkle Tree and the new Merkle Tree. The last entry
+		// in the new Merkle Tree is already proven through the LastInclusionProof, the remaining part of the liner proof
+		// that goes outside of the target Merkle Tree will be validated in future DualProof validations
+		if !VerifyLinearAdvanceProof(
+			proof.LinearAdvanceProof,
+			proof.SourceTxHeader.BlTxID,
+			proof.TargetTxHeader.BlTxID,
+			proof.TargetBlTxAlh,
+			proof.TargetTxHeader.BlRoot,
+			proof.TargetTxHeader.BlTxID,
+		) {
+			return false
+		}
 	}
 
-	return VerifyLinearProof(proof.LinearProof, sourceTxID, targetTxID, sourceAlh, targetAlh)
+	return true
 }
 
 func leafFor(d [sha256.Size]byte) [sha256.Size]byte {

@@ -19,8 +19,10 @@ package store
 import (
 	"crypto/sha256"
 	"encoding/binary"
+	"path/filepath"
 	"testing"
 
+	"github.com/codenotary/immudb/pkg/fs"
 	"github.com/stretchr/testify/require"
 )
 
@@ -123,3 +125,68 @@ func TestVerifyDualProofEdgeCases(t *testing.T) {
 	}
 
 }
+
+func TestVerifyDualProofWithAdditionalLinearInclusionProof(t *testing.T) {
+	dir := filepath.Join(t.TempDir(), "data")
+	copier := fs.NewStandardCopier()
+	require.NoError(t, copier.CopyDir("../../test/data_long_linear_proof", dir))
+
+	opts := DefaultOptions().WithSynced(false).WithMaxConcurrency(1)
+	immuStore, err := Open(dir, opts)
+	require.NoError(t, err)
+	defer immustoreClose(t, immuStore)
+
+	maxTxID := immuStore.TxCount()
+
+	t.Run("data check", func(t *testing.T) {
+		require.EqualValues(t, 30, maxTxID, "Invalid dataset - expected 30 transactions")
+
+		t.Run("transactions 1-10 do not use linear proof longer than 1", func(t *testing.T) {
+			for txID := uint64(1); txID <= 10; txID++ {
+				hdr, err := immuStore.ReadTxHeader(txID, false)
+				require.NoError(t, err)
+				require.Equal(t, txID-1, hdr.BlTxID)
+			}
+		})
+
+		t.Run("transactions 11-20 use long linear proof", func(t *testing.T) {
+			for txID := uint64(11); txID <= 20; txID++ {
+				hdr, err := immuStore.ReadTxHeader(txID, false)
+				require.NoError(t, err)
+				require.EqualValues(t, 10, hdr.BlTxID)
+			}
+		})
+
+		t.Run("transactions 21-30 do not use linear proof longer than 1", func(t *testing.T) {
+			for txID := uint64(21); txID <= 30; txID++ {
+				hdr, err := immuStore.ReadTxHeader(txID, false)
+				require.NoError(t, err)
+				require.Equal(t, txID-1, hdr.BlTxID)
+			}
+		})
+
+	})
+
+	t.Run("exhaustive consistency proof check", func(t *testing.T) {
+		for sourceTxID := uint64(1); sourceTxID < maxTxID; sourceTxID++ {
+			for targetTxID := sourceTxID; targetTxID < maxTxID; targetTxID++ {
+
+				sourceTx := tempTxHolder(t, immuStore)
+				targetTx := tempTxHolder(t, immuStore)
+
+				err := immuStore.ReadTx(sourceTxID, sourceTx)
+				require.NoError(t, err)
+
+				err = immuStore.ReadTx(targetTxID, targetTx)
+				require.NoError(t, err)
+
+				dproof, err := immuStore.DualProof(sourceTx.Header(), targetTx.Header())
+				require.NoError(t, err)
+
+				verifies := VerifyDualProof(dproof, sourceTxID, targetTxID, sourceTx.header.Alh(), targetTx.header.Alh())
+				require.True(t, verifies)
+			}
+		}
+	})
+
+}

@@ -137,6 +137,7 @@ func DualProofToProto(dualProof *store.DualProof) *DualProof {
 		TargetBlTxAlh:      dualProof.TargetBlTxAlh[:],
 		LastInclusionProof: DigestsToProto(dualProof.LastInclusionProof),
 		LinearProof:        LinearProofToProto(dualProof.LinearProof),
+		LinearAdvanceProof: LinearAdvanceProofToProto(dualProof.LinearAdvanceProof),
 	}
 }
 
@@ -174,6 +175,24 @@ func LinearProofToProto(linearProof *store.LinearProof) *LinearProof {
 	}
 }
 
+func LinearAdvanceProofToProto(proof *store.LinearAdvanceProof) *LinearAdvanceProof {
+	if proof == nil {
+		return nil
+	}
+
+	inclusionProofs := make([]*InclusionProof, len(proof.InclusionProofs))
+	for i, p := range proof.InclusionProofs {
+		inclusionProofs[i] = &InclusionProof{
+			Terms: DigestsToProto(p),
+		}
+	}
+
+	return &LinearAdvanceProof{
+		LinearProofTerms: DigestsToProto(proof.LinearProofTerms),
+		InclusionProofs:  inclusionProofs,
+	}
+}
+
 func DualProofFromProto(dproof *DualProof) *store.DualProof {
 	return &store.DualProof{
 		SourceTxHeader:     TxHeaderFromProto(dproof.SourceTxHeader),
@@ -183,6 +202,7 @@ func DualProofFromProto(dproof *DualProof) *store.DualProof {
 		TargetBlTxAlh:      DigestFromProto(dproof.TargetBlTxAlh),
 		LastInclusionProof: DigestsFromProto(dproof.LastInclusionProof),
 		LinearProof:        LinearProofFromProto(dproof.LinearProof),
+		LinearAdvanceProof: LinearAdvanceProofFromProto(dproof.LinearAdvanceProof),
 	}
 }
 
@@ -216,6 +236,22 @@ func LinearProofFromProto(lproof *LinearProof) *store.LinearProof {
 	}
 }
 
+func LinearAdvanceProofFromProto(laproof *LinearAdvanceProof) *store.LinearAdvanceProof {
+	if laproof == nil {
+		return nil
+	}
+
+	inclusionProofs := make([][][sha256.Size]byte, len(laproof.InclusionProofs))
+	for i, proof := range laproof.InclusionProofs {
+		inclusionProofs[i] = DigestsFromProto(proof.Terms)
+	}
+
+	return &store.LinearAdvanceProof{
+		LinearProofTerms: DigestsFromProto(laproof.LinearProofTerms),
+		InclusionProofs:  inclusionProofs,
+	}
+}
+
 func DigestsToProto(terms [][sha256.Size]byte) [][]byte {
 	slicedTerms := make([][]byte, len(terms))
 

@@ -53,6 +53,7 @@
     - [KeyPrefix](#immudb.schema.KeyPrefix)
     - [KeyRequest](#immudb.schema.KeyRequest)
     - [KeyValue](#immudb.schema.KeyValue)
+    - [LinearAdvanceProof](#immudb.schema.LinearAdvanceProof)
     - [LinearProof](#immudb.schema.LinearProof)
     - [LoadDatabaseRequest](#immudb.schema.LoadDatabaseRequest)
     - [LoadDatabaseResponse](#immudb.schema.LoadDatabaseResponse)
@@ -597,6 +598,7 @@ DualProof contains inclusion and consistency proofs for dual Merkle-Tree + L
 | targetBlTxAlh | [bytes](#bytes) |  | Accumulative hash (Alh) of the last transaction that's part of the target Merkle Tree |
 | lastInclusionProof | [bytes](#bytes) | repeated | Inclusion proof of the targetBlTxAlh in the target Merkle Tree |
 | linearProof | [LinearProof](#immudb.schema.LinearProof) |  | Linear proof starting from targetBlTxAlh to the final state value |
+| LinearAdvanceProof | [LinearAdvanceProof](#immudb.schema.LinearAdvanceProof) |  | Proof of consistency between some part of older linear chain and newer Merkle Tree |
 
 
 
@@ -980,6 +982,23 @@ DualProof contains inclusion and consistency proofs for dual Merkle-Tree + L
 
 
 
+<a name="immudb.schema.LinearAdvanceProof"></a>
+
+### LinearAdvanceProof
+LinearAdvanceProof contains the proof of consistency between the consumed part of the older linear chain
+and the new Merkle Tree
+
+
+| Field | Type | Label | Description |
+| ----- | ---- | ----- | ----------- |
+| linearProofTerms | [bytes](#bytes) | repeated | terms for the linear chain |
+| inclusionProofs | [InclusionProof](#immudb.schema.InclusionProof) | repeated | inclusion proofs for steps on the linear chain |
+
+
+
+
+
+
 <a name="immudb.schema.LinearProof"></a>
 
 ### LinearProof

@@ -379,6 +379,16 @@ message LinearProof {
   repeated bytes terms = 3;
 }
 
+// LinearAdvanceProof contains the proof of consistency between the consumed part of the older linear chain
+// and the new Merkle Tree
+message LinearAdvanceProof {
+  // terms for the linear chain
+  repeated bytes linearProofTerms = 1;
+
+  // inclusion proofs for steps on the linear chain
+  repeated InclusionProof inclusionProofs = 2;
+}
+
 // DualProof contains inclusion and consistency proofs for dual Merkle-Tree + Linear proofs
 message DualProof {
   // Header of the source (earlier) transaction
@@ -401,6 +411,9 @@ message DualProof {
 
   // Linear proof starting from targetBlTxAlh to the final state value
   LinearProof linearProof = 7;
+
+  // Proof of consistency between some part of older linear chain and newer Merkle Tree
+  LinearAdvanceProof LinearAdvanceProof = 8;
 }
 
 message Tx {

@@ -2264,6 +2264,10 @@
         "linearProof": {
           "$ref": "#/definitions/schemaLinearProof",
           "title": "Linear proof starting from targetBlTxAlh to the final state value"
+        },
+        "LinearAdvanceProof": {
+          "$ref": "#/definitions/schemaLinearAdvanceProof",
+          "title": "Proof of consistency between some part of older linear chain and newer Merkle Tree"
         }
       },
       "title": "DualProof contains inclusion and consistency proofs for dual Merkle-Tree + Linear proofs"
@@ -2640,6 +2644,27 @@
         }
       }
     },
+    "schemaLinearAdvanceProof": {
+      "type": "object",
+      "properties": {
+        "linearProofTerms": {
+          "type": "array",
+          "items": {
+            "type": "string",
+            "format": "byte"
+          },
+          "title": "terms for the linear chain"
+        },
+        "inclusionProofs": {
+          "type": "array",
+          "items": {
+            "$ref": "#/definitions/schemaInclusionProof"
+          },
+          "title": "inclusion proofs for steps on the linear chain"
+        }
+      },
+      "title": "LinearAdvanceProof contains the proof of consistency between the consumed part of the older linear chain\nand the new Merkle Tree"
+    },
     "schemaLinearProof": {
       "type": "object",
       "properties": {

@@ -0,0 +1,165 @@
+/*
+Copyright 2022 Codenotary Inc. All rights reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+	http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+package integration
+
+import (
+	"context"
+	"path/filepath"
+	"sync"
+	"testing"
+
+	"github.com/codenotary/immudb/pkg/api/schema"
+	"github.com/codenotary/immudb/pkg/client"
+	"github.com/codenotary/immudb/pkg/fs"
+	"github.com/codenotary/immudb/pkg/server"
+	"github.com/codenotary/immudb/pkg/server/servertest"
+	"github.com/stretchr/testify/require"
+	"google.golang.org/protobuf/types/known/emptypb"
+)
+
+type stateServiceMock struct {
+	cl           sync.Mutex
+	m            sync.RWMutex
+	state        *schema.ImmutableState
+	stateHistory map[uint64]*schema.ImmutableState
+}
+
+func newServiceStateMock() *stateServiceMock {
+	return &stateServiceMock{
+		state:        &schema.ImmutableState{TxId: 0},
+		stateHistory: make(map[uint64]*schema.ImmutableState),
+	}
+}
+
+func (ssm *stateServiceMock) GetState(ctx context.Context, db string) (*schema.ImmutableState, error) {
+	ssm.m.RLock()
+	defer ssm.m.RUnlock()
+
+	return ssm.state, nil
+}
+
+func (ssm *stateServiceMock) SetState(db string, state *schema.ImmutableState) error {
+	ssm.m.Lock()
+	defer ssm.m.Unlock()
+
+	ssm.state = state
+	ssm.stateHistory[state.TxId] = state
+	return nil
+}
+
+func (ssm *stateServiceMock) CacheLock() error {
+	ssm.cl.Lock()
+	return nil
+}
+
+func (ssm *stateServiceMock) CacheUnlock() error {
+	ssm.cl.Unlock()
+	return nil
+}
+
+func TestLongLinearProofVerification(t *testing.T) {
+	// Start the server with transaction data containing long linear proof
+	dir := t.TempDir()
+	copier := fs.NewStandardCopier()
+	require.NoError(t, copier.CopyDir("../../test/data_long_linear_proof", filepath.Join(dir, "defaultdb")))
+
+	options := server.DefaultOptions().WithDir(dir)
+	bs := servertest.NewBufconnServer(options)
+
+	err := bs.Start()
+	require.NoError(t, err)
+	defer bs.Stop()
+
+	cl, err := bs.NewAuthenticatedClient(client.DefaultOptions().WithDir(t.TempDir()))
+	require.NoError(t, err)
+	defer cl.CloseSession(context.Background())
+
+	// Inject our custom state service to have insight into the state values
+	ssm := newServiceStateMock()
+	cl.WithStateService(ssm)
+
+	const txCount = 30
+
+	t.Run("verify server data", func(t *testing.T) {
+		sc := cl.GetServiceClient()
+
+		st, err := sc.CurrentState(context.Background(), &emptypb.Empty{})
+		require.NoError(t, err)
+		require.EqualValues(t, txCount, st.TxId)
+
+		t.Run("transactions 1-10 do not use linear proof longer than 1", func(t *testing.T) {
+			for txID := uint64(1); txID <= 10; txID++ {
+				tx, err := sc.TxById(context.Background(), &schema.TxRequest{
+					Tx: txID,
+					EntriesSpec: &schema.EntriesSpec{
+						KvEntriesSpec: &schema.EntryTypeSpec{Action: schema.EntryTypeAction_EXCLUDE},
+					},
+				})
+				require.NoError(t, err)
+				require.Equal(t, txID-1, tx.Header.BlTxId)
+			}
+		})
+
+		t.Run("transactions 11-20 use long linear proof", func(t *testing.T) {
+			for txID := uint64(11); txID <= 20; txID++ {
+				tx, err := sc.TxById(context.Background(), &schema.TxRequest{
+					Tx: txID,
+					EntriesSpec: &schema.EntriesSpec{
+						KvEntriesSpec: &schema.EntryTypeSpec{Action: schema.EntryTypeAction_EXCLUDE},
+					},
+				})
+				require.NoError(t, err)
+				require.EqualValues(t, 10, tx.Header.BlTxId)
+			}
+		})
+
+		t.Run("transactions 21-30 do not use linear proof longer than 1", func(t *testing.T) {
+			for txID := uint64(21); txID <= txCount; txID++ {
+				tx, err := sc.TxById(context.Background(), &schema.TxRequest{
+					Tx: txID,
+					EntriesSpec: &schema.EntriesSpec{
+						KvEntriesSpec: &schema.EntryTypeSpec{Action: schema.EntryTypeAction_EXCLUDE},
+					},
+				})
+				require.NoError(t, err)
+				require.Equal(t, txID-1, tx.Header.BlTxId)
+			}
+		})
+	})
+
+	t.Run("get all transaction states", func(t *testing.T) {
+		for txID := uint64(1); txID <= txCount; txID++ {
+			_, err = cl.VerifiedTxByID(context.Background(), txID)
+			require.NoError(t, err)
+			require.Contains(t, ssm.stateHistory, txID)
+		}
+		require.Len(t, ssm.stateHistory, txCount)
+	})
+
+	t.Run("Exhaustive consistency proof", func(t *testing.T) {
+		for i := uint64(1); i <= txCount; i++ {
+			for j := i; j <= txCount; j++ {
+				ssm.state = ssm.stateHistory[i]
+
+				_, err = cl.VerifiedTxByID(context.Background(), j)
+				require.NoError(t, err)
+				require.EqualValues(t, j, ssm.state.TxId)
+			}
+		}
+	})
+
+}