021.md

Obedient Wool Canary

High

InclusionProof has no size limit for the proof bytes, so adversary could flood and overload nodes by submitting large invalid proofs

Summary

InclusionProof does not limit the size of the merkle nodes proof, which allows for adversary to halt the chain by overloading the nodes.

Root cause

Each Merkle proof consists of log₂(N) hashes, where N is the number of transactions in the Bitcoin block. Each hash (Merkle node) is 32 bytes. Usually Bitcoin blocks contain up to 4,000 transactions in high-volume conditions. So it would be around log₂(4000) ≈ 12 (Merkle nodes needed) for such a block, which is 384 bytes.

In the current logic however, this is not limited at all, meaning that an adversary can submit a very resource-expensive transaction.

The following function is used when dispatching separate inclusion proof tx / bgtdelegation tx: https://github.com/babylonlabs-io/babylon/blob/6dcb0b5df0493615ac251ac6e329a0e0c6952125/x/btccheckpoint/types/btcutils.go#L193

func VerifyInclusionProof(
	tx *btcutil.Tx,
	merkleRoot *chainhash.Hash,
	intermediateNodes []byte,
	index uint32) bool {
	return verify(tx, merkleRoot, intermediateNodes, index)
}
func verify(tx *btcutil.Tx, merkleRoot *chainhash.Hash, intermediateNodes []byte, index uint32) bool {
	txHash := tx.Hash()

	// Shortcut the empty-block case
	if txHash.IsEqual(merkleRoot) && index == 0 && len(intermediateNodes) == 0 {
		return true
	}

	proof := []byte{}
	proof = append(proof, txHash[:]...)
	proof = append(proof, intermediateNodes...)
	proof = append(proof, merkleRoot[:]...)

	var current chainhash.Hash

	idx := index

	proofLength := len(proof)

@>> //@audit proof size is not limited. resources can be exhausted with fake proof
	if proofLength%32 != 0 {
		return false
	}

	if proofLength == 64 {
		return false
	}

	root := proof[proofLength-32:]
	cur := proof[:32:32]
	copy(current[:], cur)
	numSteps := (proofLength / 32) - 1
	for i := 1; i < numSteps; i++ {
		start := i * 32
		end := i*32 + 32
		next := proof[start:end:end]
		if idx%2 == 1 {
@>>		current = hashConcat(next, current[:])
		} else {
@>>		current = hashConcat(current[:], next)
		}
		idx >>= 1
	}
	return bytes.Equal(current[:], root)
}

Ref to double-hashing algo:

// Concatenates and double hashes two provided inputs
func hashConcat(a []byte, b []byte) chainhash.Hash {
	c := []byte{}
	c = append(c, a...)
	c = append(c, b...)
	return chainhash.DoubleHashH(c)
}

Attack Path

1. Adversary submits inclusionProof with only valid hash and index, but invalid merkle node proofs. The merkle node proofs that are submitted are very oversized.
2. This results in very excessive calculation and overloading as we do double sha256 hashing for each merkle node, so with just a few MB attacker could achieve millions of sha256 operations. Since there is no limit for the proofs, adversary can force nodes to do unnecessary operations and overload them.
3. This will slow the whole network down and could lead to chain halt.

Impact

This will slow the whole network down and could lead to chain halt. Such operations should always be limited to the theoretical maximum of possible iterations for node infrastructures, to avoid DDoS attacks which could exhaust the resources of the chain.

Recommendation

Apply a reasonable limit for the max size of the merkle proof.