Security Meaning and Risk Model

This document analyzes the security implications of representing transaction references inside a block proposal using a truncated transaction identifier:

$$ \textsf{TxRef}(tx) := \operatorname{Trunc}_b(H(tx)) $$

where H is a cryptographic hash function and Trunc_b denotes keeping the first $b$ bits (equivalently, we can say $L$ bytes where $b=8L$). This truncated value is used only as a compact reference for mempool lookup and block reconstruction.

The relevant notion of “security” in this context is not collision resistance of the block commitment itself, since the block proposal header contains:

• block_root: a Merkle root computed over full transaction hashes

Hence, the truncated reference mechanism does not change the cryptographic binding of the block proposal to the chosen transaction set. Instead, the security concerns relate to availability, reconstruction feasibility, and DoS resistance.

Random Collisions

A truncated reference $\textsf{TxRef}(tx)$ may map to more than one transaction in a validator’s local mempool. In other words, multiple distinct transactions may share the same $b$-bit prefix, creating ambiguity during reconstruction.

This ambiguity is not a consensus-integrity failure, because the commitment in header.block_root still uniquely binds the proposal to a specific ordered set of full transaction hashes. Any reconstruction attempt that selects the wrong candidate transactions will fail to reproduce block_root and will therefore be rejected.

However, random prefix collisions can still have negative operational consequences:

• Reconstruction overhead: validators may need to consider multiple candidates for a single reference, increasing computation and lookup costs.
• Practical rejection / DoS risk: if ambiguity becomes too frequent (or too large per reference), reconstruction may become infeasible within resource limits, causing validators to reject the proposal even when the leader acted honestly.

Therefore, random collisions primarily affect liveness and efficiency, rather than correctness.

Adversarial Prefix Grinding (Targeted DoS)

Unlike random collisions, an adversary may attempt to create collisions intentionally by generating transactions whose hash begins with a chosen prefix value. This is a classic prefix grinding attack.

For a secure hash function modeled as a random oracle, the expected cost to find an input whose hash matches a specific $b$-bit prefix is approximately:

$$ \mathbb{E}[\textsf{work}] \approx 2^b $$

When $b$ is small, this work factor can be low enough that an attacker can cheaply inject transactions designed to collide under truncation. This increases ambiguity for targeted prefixes and can be used to:

• increase reconstruction costs,