crypto/merkle: Add error handling (backport celestiaorg#558) (celesti…

…aorg#710) * crypto/merkle: Add error handling (celestiaorg#558) * porting pr * Disallow nil root hashes * linting * making computeRootHash private * Update release notes. * Update .changelog/unreleased/breaking-changes/558-tm10011.md Co-authored-by: Thane Thomson <connect@thanethomson.com> * Wrapping the private function into a public one with the old signature. * update comment * remove dependency on amino * Update .changelog/unreleased/breaking-changes/558-tm10011.md Co-authored-by: Thane Thomson <connect@thanethomson.com> --------- Co-authored-by: Thane Thomson <connect@thanethomson.com> (cherry picked from commit d067b74) # Conflicts: # crypto/merkle/proof.go # crypto/merkle/proof_test.go * fix conflicts --------- Co-authored-by: Lasaro <lasaro@informal.systems>
KYVENetwork · Apr 13, 2023 · 1641d39 · 1641d39
1 parent cf1375e
commit 1641d39
Show file tree

Hide file tree

Showing 4 changed files with 64 additions and 17 deletions.
diff --git a/.changelog/unreleased/breaking-changes/558-tm10011.md b/.changelog/unreleased/breaking-changes/558-tm10011.md
@@ -0,0 +1,2 @@
+- `[crypto/merkle]` Do not allow verification of Merkle Proofs against empty trees (`nil` root). `Proof.ComputeRootHash` now panics when it encounters an error, but `Proof.Verify` does not panic
+  ([\#558](https://github.com/cometbft/cometbft/issues/558))
diff --git a/crypto/merkle/proof.go b/crypto/merkle/proof.go
@@ -50,25 +50,40 @@ func ProofsFromByteSlices(items [][]byte) (rootHash []byte, proofs []*Proof) {
 // Verify that the Proof proves the root hash.
 // Check sp.Index/sp.Total manually if needed
 func (sp *Proof) Verify(rootHash []byte, leaf []byte) error {
-	leafHash := leafHash(leaf)
+	if rootHash == nil {
+		return fmt.Errorf("invalid root hash: cannot be nil")
+	}
 	if sp.Total < 0 {
 		return errors.New("proof total must be positive")
 	}
 	if sp.Index < 0 {
 		return errors.New("proof index cannot be negative")
 	}
+	leafHash := leafHash(leaf)
 	if !bytes.Equal(sp.LeafHash, leafHash) {
 		return fmt.Errorf("invalid leaf hash: wanted %X got %X", leafHash, sp.LeafHash)
 	}
-	computedHash := sp.ComputeRootHash()
+	computedHash, err := sp.computeRootHash()
+	if err != nil {
+		return fmt.Errorf("compute root hash: %w", err)
+	}
 	if !bytes.Equal(computedHash, rootHash) {
 		return fmt.Errorf("invalid root hash: wanted %X got %X", rootHash, computedHash)
 	}
 	return nil
 }
 
-// Compute the root hash given a leaf hash.  Does not verify the result.
+// Compute the root hash given a leaf hash.  Panics in case of errors.
 func (sp *Proof) ComputeRootHash() []byte {
+	computedHash, err := sp.computeRootHash()
+	if err != nil {
+		panic(fmt.Errorf("ComputeRootHash errored %w", err))
+	}
+	return computedHash
+}
+
+// Compute the root hash given a leaf hash.
+func (sp *Proof) computeRootHash() ([]byte, error) {
 	return computeHashFromAunts(
 		sp.Index,
 		sp.Total,
@@ -148,35 +163,36 @@ func ProofFromProto(pb *cmtcrypto.Proof) (*Proof, error) {
 // Use the leafHash and innerHashes to get the root merkle hash.
 // If the length of the innerHashes slice isn't exactly correct, the result is nil.
 // Recursive impl.
-func computeHashFromAunts(index, total int64, leafHash []byte, innerHashes [][]byte) []byte {
+func computeHashFromAunts(index, total int64, leafHash []byte, innerHashes [][]byte) ([]byte, error) {
 	if index >= total || index < 0 || total <= 0 {
-		return nil
+		return nil, fmt.Errorf("invalid index %d and/or total %d", index, total)
 	}
 	switch total {
 	case 0:
 		panic("Cannot call computeHashFromAunts() with 0 total")
 	case 1:
 		if len(innerHashes) != 0 {
-			return nil
+			return nil, fmt.Errorf("unexpected inner hashes")
 		}
-		return leafHash
+		return leafHash, nil
 	default:
 		if len(innerHashes) == 0 {
-			return nil
+			return nil, fmt.Errorf("expected at least one inner hash")
 		}
 		numLeft := getSplitPoint(total)
 		if index < numLeft {
-			leftHash := computeHashFromAunts(index, numLeft, leafHash, innerHashes[:len(innerHashes)-1])
-			if leftHash == nil {
-				return nil
+			leftHash, err := computeHashFromAunts(index, numLeft, leafHash, innerHashes[:len(innerHashes)-1])
+			if err != nil {
+				return nil, err
 			}
-			return innerHash(leftHash, innerHashes[len(innerHashes)-1])
+
+			return innerHash(leftHash, innerHashes[len(innerHashes)-1]), nil
 		}
-		rightHash := computeHashFromAunts(index-numLeft, total-numLeft, leafHash, innerHashes[:len(innerHashes)-1])
-		if rightHash == nil {
-			return nil
+		rightHash, err := computeHashFromAunts(index-numLeft, total-numLeft, leafHash, innerHashes[:len(innerHashes)-1])
+		if err != nil {
+			return nil, err
 		}
-		return innerHash(innerHashes[len(innerHashes)-1], rightHash)
+		return innerHash(innerHashes[len(innerHashes)-1], rightHash), nil
 	}
 }
 

diff --git a/crypto/merkle/proof_test.go b/crypto/merkle/proof_test.go
@@ -1,13 +1,15 @@
 package merkle
 
 import (
+	"bytes"
 	"errors"
 	"fmt"
 	"testing"
 
 	"github.com/stretchr/testify/assert"
 	"github.com/stretchr/testify/require"
 
+	"github.com/tendermint/tendermint/crypto/tmhash"
 	cmtcrypto "github.com/tendermint/tendermint/proto/tendermint/crypto"
 )
 
@@ -198,3 +200,26 @@ func TestVoteProtobuf(t *testing.T) {
 		}
 	}
 }
+
+// TestVsa2022_100 verifies https://blog.verichains.io/p/vsa-2022-100-tendermint-forging-membership-proof
+func TestVsa2022_100(t *testing.T) {
+	// a fake key-value pair and its hash
+	key := []byte{0x13}
+	value := []byte{0x37}
+	vhash := tmhash.Sum(value)
+	bz := new(bytes.Buffer)
+	_ = encodeByteSlice(bz, key)
+	_ = encodeByteSlice(bz, vhash)
+	kvhash := tmhash.Sum(append([]byte{0}, bz.Bytes()...))
+
+	// the malicious `op`
+	op := NewValueOp(
+		key,
+		&Proof{LeafHash: kvhash},
+	)
+
+	// the nil root
+	var root []byte
+
+	assert.NotNil(t, ProofOperators{op}.Verify(root, "/"+string(key), [][]byte{value}))
+}
diff --git a/crypto/merkle/proof_value.go b/crypto/merkle/proof_value.go
@@ -93,8 +93,12 @@ func (op ValueOp) Run(args [][]byte) ([][]byte, error) {
 		return nil, fmt.Errorf("leaf hash mismatch: want %X got %X", op.Proof.LeafHash, kvhash)
 	}
 
+	rootHash, err := op.Proof.computeRootHash()
+	if err != nil {
+		return nil, err
+	}
 	return [][]byte{
-		op.Proof.ComputeRootHash(),
+		rootHash,
 	}, nil
 }
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,2 @@
		- `[crypto/merkle]` Do not allow verification of Merkle Proofs against empty trees (`nil` root). `Proof.ComputeRootHash` now panics when it encounters an error, but `Proof.Verify` does not panic
		([\#558](https://github.com/cometbft/cometbft/issues/558))