Celestia Q2 2025 High-Throughput Recovery Audit Report Final v2

Security Audit Report

CELESTIA Q2 2025: HIGH THROUGHPUT RECOVERY

Authors: Last Revised Martin Hutle, Sergio Mena, Tatjana 2025/06/24 Kirda, Marius Poke Celestia Q2 2025 High Throughput Recovery

Contents Audit overview 3 The Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Scope of this report . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Audit plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Audit Dashboard 5 Target Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Engagement Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Severity Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

System Overview 6

Threat Model 8 Threat model for pull-based broadcast tree recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Basic type definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Data flow definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Algorithm description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Threats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Threat model for catchup mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Protocol Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Threats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Findings 36 Stale currentHeight in the propagation reactor causes catchup to skip blocks . . . . . . . . . . . . . . . . . . 39 The CompactBlock validation doesn’t check whether the proposal is for the right height and round . . . . 40 AddCommitment doesn’t update the PartSetHeader for cached heights and rounds . . . . . . . . . . . . . . 41 The requests made in a step of catchup are incorrectly updated . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Not validating last part length of CompactBlock leads to a panic while decoding . . . . . . . . . . . . . . . . 43 Calling SetHave and SetWant method could trigger a panic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Block parts can become unavailable due to silent failure in the TrySendEnvelopeShim function . . . . . . 45 Race condition in HaveParts processing during height transitions . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Race condition in syncData causes a runtime panic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 TrySendEnvelopeShim can silently fail in handleWants function . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 When clearing wants the node sends parts without proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Unresolvable wants in PeerState . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 The parts retrieved from mempool are not being validated . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 if !blockProp.started.Load() check missing from the handleCompactBock function . . . . . . . . . . . . . . . 52 The specified disconnection rules were not implemented . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Propagation reactor adds peers without verifying PBBT support . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Incorrectly sized maxRequests BitArray allows unlimited requests for parity parts . . . . . . . . . . . . . . . . 55 ClearWants might fail due to pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 The concurrent request limit might be computed inaccurately . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 The check for complete CombinedPartSet during catchup is incorrect . . . . . . . . . . . . . . . . . . . . . . . 58 Catchup on cached proposals is delayed until next reactor tick . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Proofs are verified for received parts that the node already has . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 HaveParts broadcast despite the failed WantParts send . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 TrySendEnvelopeShim can silently fail in broadcastCompactBlock function . . . . . . . . . . . . . . . . . . . 62 TrySendEnvelopeShim can silently fail in broadcastHaves function . . . . . . . . . . . . . . . . . . . . . . . . . 63 GetPart returning nil causes a runtime panic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Discrepancy between the implementation and specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 TxMetaData cannot be validated before block is complete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Nodes don’t drop duplicate WantParts message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Nodes don’t drop RecoveryPart message if they were not requested . . . . . . . . . . . . . . . . . . . . . . . . 68 Miscellaneous code findings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Appendix: Vulnerability classification 70

Disclaimer 73

Audit overview The Project In April and May 2025, Celestia engaged Informal Systems ↗ to work on a partnership and conduct a security audit of the following items:

Repository celestia-core, branch feature/recovery ● celestia-core/consensus/propagation ↗
Repository celestia-app, branch evan/spec-PBBT ● Vacuum! Part I: High Throughput Recovery specification

Relevant code commits The audited code was from:

● Branch feature/recovery – commit hash 139bad235a379599670f30d5e28c637dde4bb17a ↗ ● Vacuum! Part I: High Throughput Recovery specification – commit hash a0369f750aed5129f37d93f0f65c234ee1f10d12 ↗

Scope of this report The primary focus of this audit was the High Throughput Recovery algorithm, which is built on top of CometBFT as a new reactor to enhance block propagation. As part of this inspection, the data types and algorithm defined within the propagation reactor were examined in detail. The code review also covered the integration points of the propagation reactor with the consensus code. The scope of this audit did not include a review of the existing CometBFT logic or the test code. Furthermore, it did not cover the mempool, end-to-end tests, or cryptographic components.

Audit plan The audit was conducted between April 28th, 2025, and May 30th, 2025 by the following personnel:

● Martin Hutle ● Marius Poke ● Sergio Mena

● Tatjana Kirda

Conclusions The audit was conducted while the code was still in development. Consequently, prior to the audit, the clients shared several known issues with the current implementation. The full mesh overlay has not yet been implemented, leaving the system vulnerable to determined attackers. Additionally, the compact block lacks signature verification,

making it susceptible to forgery attacks. The calculation of the PerPeerConcurrentRequestLimit assumes that voting power is evenly distributed among validators. The specification also envisions an ideal protocol without per-peer bandwidth restrictions. During the audit, we identified thirty-one findings, including three of critical severity, three of high severity, seven of medium severity, twelve of low severity, and six informational. Full details of these issues can be found on the Findings page.

Audit Dashboard Target Summary ● Type: Protocol and Implementation ● Platform: Go ● Artifacts:

– High Throughput Recovery algorithm implementation, branch feature/recovery ↗ ➞ celestia-core/consensus/propagation ↗ – Vacuum! Part I: High Throughput Recovery specification ↗

Engagement Summary ● Dates: 28.04.2025 - 30.05.2025. ● Method: Manual code review, protocol analysis

Severity Summary

Finding Severity Number

Critical 3 High 3 Medium 7 Low 12 Informational 6 Total 31

System Overview High-Level Algorithm Description High Throughput Recovery activates after the initial dissemination of transactions. The proposer node broadcasts a compact block — a summary, or TOC, of the proposed block — to all other nodes in the network. This compact block enables other nodes to reconstruct the full block using various techniques, without requiring full transmission. Block reconstruction relies on the block parts mechanism defined in CometBFT, and employs the following methods:

● Local Mempool Reconstruction: The propagation reactor queries the mempool reactor. For every transaction in the proposed block, the compact block includes the transaction’s hash, and its start and end offsets in the serialised block. If enough transactions are found locally, nodes can reconstruct one or more block parts from them.

● Parity-Based Recovery: The proposer generates parity parts using the reedsolomon library. With a suitable combination of block parts and parity parts, missing parts can be reconstructed through erasure coding.

● Pull-Based Retrieval: A tree-based pull mechanism — the core of High Throughput Recovery — enables nodes to fetch missing parts from peers.

The algorithm also includes a load balancing strategy to avoid congestion at the proposer node, which acts as the root of the retrieval tree. The data structures involved include mechanisms for verifying messages and block parts. These are in scope for the audit.

Catchup protocol The catchup protocol is triggered for all heights h smaller than the current local height of the consensus protocol. If there is a block part bp[h][r] missing for the last round r of that height, request this part from a peer from which is has not been requested before (WantParts). Once a block part is received, it is handled as in the normal case protocol, except that only normal parts (and not the parity parts) are requested and used to reconstruct the block. The protocol is triggered at the following places:

● Every RetryTime ticks ● When consensus enters the precommit phase for height h and round r ● When consensus enters the commit phase for height h and round r

● When consensus adopts a new valid block for height h in round r (2f+1 prevotes)

Assumptions and Scope The algorithm assumes a stable network topology during the processing and dissemination of each proposed block. This means the node availability and communication links are fixed during that period. If dynamic changes occur mid-block (e.g., connection to a peer shuts down), the algorithm does not account for them explicitly. This

modeling choice keeps the threat model more concise and focused, and reflects the absence of topology-adaptive logic in the provided specification. A general understanding of CometBFT is assumed. Concepts such as validators, block proposals, consensus rounds, and message propagation are not reintroduced here. Readers unfamiliar with these should consult the CometBFT documentation.

Notation and Conventions The threat model uses standard notation, formal logic terminology, and first order logic expressions. It is structured as a set of properties that correct nodes must follow at all times (also called invariants). A list of threats are derived from the properties, which guide our security analysis. The following conventions apply:

● “iff” (if and only if) is used in two ways: – In definitions: “A iff B” means A and B can be used interchangeably. – In properties: “A iff B” means “A if B and B if A”. ● “Previously” is a tricky concept in a distributed system, and is interpreted according to context: – For events on the same node, it refers to real-time order. – For events on different nodes, it implies a causal link via message passing. ● Indices in arrays or lists are zero-based. ● Familiarity with first-order logic and partially synchronous distributed systems is assumed.

Threat Model Threat model for pull-based broadcast tree recovery This report presents a threat model for High Throughput Recovery, an algorithm added to CometBFT as a new reactor to enhance block propagation. The threat model focuses on the behaviour of correct nodes; unless otherwise specified, the term node refers exclusively to a correct node. When we refer to a Byzantine or malicious node, it is stated explicitly.

Properties This section outlines the threat model: a set of definitions, rules, and properties that specify how the system should behave on honest nodes. The threat model serves as a basis for deriving the list of threats, presented in section ‘Threats’, which was used to guide our audit of the code in our search for issues. The threat model and its associated threats enable a methodical and comprehensive analysis, as opposed to simply reviewing the code without a concrete roadmap. This section is organised as follows. Firstly, we introduce several type definitions to enhance the readability of the remainder of the section. The remainder is then divided into two parts: in the first part, we explicitly state the properties that govern the data structures utilised by High Throughput Recovery; in the second part, we set out the properties that the algorithm itself must satisfy. Each part is preceded by a subsection containing definitions that contribute to a clearer organisation of the text.

Basic type definitions In order to improve readability, we use the following terms in this document:

● hash, a fixed-size byte array in the code ● height, a blockchain height, int64 in the code ● round, a Tendermint consensus round, int32 in the code

● offset, an offset in a byte array, uint32 in the code

● length, the length, or an index, of an array, uint32 in the code

● bitmask, an array of bits

● merkle proof , a data structure containing the aunts that prove inclusion of an element into a tree

● block id, a structure containing

– total, the number of block parts of a serialised block – hash, a hash containing the root hash of the parts

Data flow definitions We define ProposedBlock as a structure composed of:

● height, a height ● round, a round ● txs, an array of arrays of bytes

● (all other fields are not relevant for this threat model)

We define Proposal — unchanged from the original CometBFT/Tendermint Core — as a structure composed of:

● type (not relevant for this threat model) ● height, a height ● round, a round

● pol_round (not relevant for this threat model)

● block_id, a block id

● timestamp (not relevant for this threat model)

● signature, an array of bytes

We define TxMetaData as a structure composed of:

● hash, a hash ● start, an offset

● end, an offset

We define RecoveryPart as a structure composed of:

● height, a height ● round, a round ● index, a uint32

● data, a byte array

● proof, a merkle proof

We define CompactBlock as a structure composed of:

● bp_hash, a hash ● blobs, an array of TxMetaData ● proposal, a Proposal

● last_length, a length

● parts_hashes, an array of hashes

● signature, a signature

Given a CompactBlock instance cb, we define the function signBytes(cb), which returns a fixed-size byte array containing the cryptographic signature covering the following fields:

● cb.bp_hash, cb.blobs, cb.last_length, cb.parts_hashes ● notice that cb.proposal is excluded as it is itself signed

We define PartMetaData as a structure composed of:

● index, a length ● hash, a hash

We define HaveParts as a structure composed of:

● height, a height ● round, a round ● parts, an array of PartMetaData

We define WantParts as a structure composed of:

● height, a height ● round, a round ● parts, a bitmask

● prove, a boolean

Data Flow 1: ProposedBlock and Proposal as input Inputs => Outputs:

● Proposed block, Proposal => CompactBlock ● Proposed block, CompactBlock => RecoveryPart

DF1a. A ProposedBlock (or proposed block) b can be serialised into an array of bytes, denoted as serialised(b):

● The serialisation follows ProtoBuf rules. ● During the serialisation process, we record the start and end byte offsets for each element of b.txs. For any

transaction b.txs[i]: – we denote start(b, i) as the offset of b.txs[i]’s first byte in serialised(b) – we denote end(b, i) as the offset of b.txs[i]’s last byte in serialised(b)

DF1b. Proposed block b can be used as input to create an array tms of TxMetaData:

● tms[i].hash is the hash of b.txs[i] ● tms[i].start is start(b, i) ● tms[i].end is end(b, i)

DF1c. A serialised proposed block serialised(b) can be divided into a list of n parts, denoted as parts(serialised(b)):

● Each part is a byte array ● BlockPartSizeBytes is a constant that defines the length in bytes of each part, except for the last part, which

may be shorter

DF1d. The parts of a serialised proposed block, parts(serialised(b)), can be extended into redundant parts par- ity(serialised(b)):

● We pad the last part of b to size BlockPartSizeBytes ● We use the reedsolomon library to produce as many parts of parity(serialised(b)) as len(parts(serialised(b))) ● All parts of the redundant block have size BlockPartSizeBytes

DF1e. Let p be parts(serialised(b)). Proposed block b and Proposal (or signed proposal) prp can be used as input to create a CompactBlock instance (or compact block) cb:

● cb.blobs is an array of TxMetaData populated from b as described in DF1b ● cb.proposal is prp ● cb.last_length is the length of the last part, i.e., len(p[len(parts(serialised(b)))-1])

● cb.parts_hashes

– has length 2 len(parts(serialised(b)))* – cb.parts_hashes[i] the hash of p[i], if i < len(parts(serialised(b))) – cb.parts_hashes[i] is the hash of pp[i-len(parts(serialised(b)))], if i >= len(parts(serialised(b))), where pp is parity(serialised(b)) ● cb.signature contains the return value of signBytes(cb2), where – cb2’s fields contain the same values as cb’s fields except cb2.signature which is set to nil – notice that it is not necessary to include cb2.proposal in the signature, as it is already signed by the same validator ● cb.bp_hash is the root of the merkle tree of the second half of cb.parts_hashes[i] – the second half is the indexes i, such that len(parts(serialised(b))) <= i < 2 len(parts(serialised(b)))*

– these are holding the

Excerpt (19998 of 160904 characters). Read the whole page on informalsystems/audits ↗

← Back to Documentation