Description

The Tendermint X TendermintVerify verify_skip_distance function is implemented as follows:

fn verify_skip_distance(
    &mut self,
    skip_max: usize,
    trusted_block: &U64Variable,
    target_block: &U64Variable,
) {
    let one = self.one();
    let trusted_block_plus_one = self.add(*trusted_block, one);
    // Verify target block > trusted block.
    self.gt(*target_block, trusted_block_plus_one);

    let skip_max_var = self.constant::<U64Variable>(skip_max as u64);
    let max_block = self.add(*trusted_block, skip_max_var);
    // Verify target block <= trusted block + skip_max.
    self.lte(*target_block, max_block);
}

This function is intended to check that target_block > trusted_block and target_block <= trusted_block + skip_max. However, self.gt(*target_block, trusted_block_plus_one); only allocates a Boolean circuit variable and assigns it True if and only if the *target_block > trusted_block_plus_one. This Boolean variable is, however, not constrained to be True, so the inequality is not constrained to hold. This is analogous for the second inequality.

Impact

As Tendermint X was out of scope for this audit, we have not evaluated the impact for Tendermint X. With regards to in-scope parts of Blobstream X, this bug, depending on behavior of the Tendermint X skip function called as follows,

let target_header_hash = builder.skip::<MAX_VALIDATOR_SET_SIZE, CHAIN_ID_SIZE_BYTES>(
    C::CHAIN_ID_BYTES,
    C::SKIP_MAX,
    trusted_block,
    trusted_header_hash,
    target_block,
);

could allow an attacker to generate a CombinedSkipCircuit proof in which target_block < trusted_block.

In this case, the check (seen below) done in prove_subchain to check the last header hash against a trusted hash will never be carried out, allowing an attacker to use a chain of arbitrary header hashes of their choosing (note that prove_data_commitment never does any checks involving start_header_hash, the root of trust for the header hashes is purely the check on end_header_hash done in prove_subchain).

// If this is the last valid block, verify the last_block_id_proof_root (header hash of block curr_idx+1) is equal to the global_end_header_hash.
// This is the final step in the verification that global_start_block -> global_end_block is linked.
let root_matches_end_header =
    self.is_equal(last_block_id_proof_root, *global_end_header_hash);
let end_header_check = self.or(is_not_last_block, root_matches_end_header);
self.assert_is_equal(end_header_check, true_bool);

All batches in prove_data_commitment would be disabled, so the reduction steps will always choose the left subchains' data Merkle root. Thus, the data-commitment Merkle root ultimately returned would be the one from the very first batch, where a full batch worth of committed data would be returned, with the data hashes thus choosable by the attacker. See also the description of Finding ref↗.

Recommendations

As CombinedSkipCircuit exposes trusted_block and target_block publicly, the check that target_block > trusted_block can also be carried out outside the circuit. In this case, the circuit is intended to be used together with an EVM smart contract BlobstreamX.sol, which contains the following check in the commitHeaderRange function that appears to prevent providing a proof with target_block < trusted_block.

if (_targetBlock <= latestBlock || _targetBlock - latestBlock > DATA_COMMITMENT_MAX) {
    revert TargetBlockNotInRange();
}

As long as such checks are made by the verifier wherever the proofs of the CombinedSkipCircuit circuit are used, it is not necessary to make in-circuit changes to prevent impact on CombinedSkipCircuit.

As the ineffective inequality checks in Tendermint X's verify_skip_distance function were intended to be enforced, we recommend constraining the two Boolean variables returned by self.gt and self.lte to be True.

Remediation

This issue has been acknowledged by Succinct, and a fix was implemented in the following commit: