Some attackers on a distributed consensus protocol choose which participants to take over only after watching what those participants send. The most dangerous version, called a strongly adaptive adversary, can also delete a message after seeing it. It watches an honest node vote, takes over that node, and erases the vote before anyone else counts it. Known defenses make this attacker pay heavily. Either communication must grow quadratically with the number of nodes, or every message must be wrapped in a time-lock puzzle, a ciphertext that takes a long, fixed amount of sequential computation to open. The long computation keeps the attacker from reading a vote in time to act on it, which is expensive for the honest nodes too. Neither cost is affordable for battery-powered sensors running 16-bit microcontrollers.
On a shared radio channel, "deleting a message after the fact" has no literal meaning. Once a packet has been fully radiated, every neighbor has received it. The only physical way to erase it is reactive jamming: the attacker hears the start of a packet and transmits noise over the rest. This attack is quiet for two reasons. First, the half-duplex constraint (a radio cannot receive while it transmits on the same band) means the honest sender cannot hear the jamming. Second, the attacker can base its decision on what it has already heard. Our claim is that on a broadcast radio, the attacker's erasure power reduces to "decide whether to jam before the packet ends." It can be made blind to message content with a cheap symmetric-key encoding that reveals nothing until the final symbol arrives, even to an attacker who has just stolen the sender's keys. The time-lock puzzle then shrinks from seconds of modular squaring to one packet's airtime.
Core Claim
The time-lock puzzle in Round-Efficient Byzantine Broadcast Under Strongly Adaptive and Majority Corruptions has one specific job. It keeps a node's vote hidden until that vote has been delivered, so any decision to corrupt the node and erase the vote is made without knowing the vote. On a single-hop radio neighborhood, delivery finishes when the last symbol of the packet has been radiated. Hiding the content until that moment therefore does the same job.
We implement this "airtime seal" with an all-or-nothing transform: a keyless, invertible re-encoding in which no bit of the plaintext can be computed from any proper subset of the output blocks. We build it from a lightweight block cipher, and we randomize which of several slots in a frame carry each packet's copies, following coded slotted ALOHA. Coded slotted ALOHA is a random-access scheme in which each packet is sent several times in random slots, and the receiver removes decoded copies from collided slots to recover more packets.
The keyless property is the ingredient that ordinary link encryption lacks. An adversary that corrupts the sender mid-packet learns all of the sender's keys. With a stream or block cipher, those keys let it read the packet's prefix and jam the tail selectively. With the all-or-nothing transform, the keys do not help, because the missing tail blocks are needed to recover any plaintext bit.
The claim is falsifiable. Against a content-triggered reactive jammer, sealed packets should be erased at a rate independent of their content, and that rate should be bounded by the jammer's energy budget. Unsealed or merely encrypted packets should show strongly content-dependent erasure.
This does not contradict the $\Omega(f^2)$ lower bound of Communication Complexity of Byzantine Agreement, Revisited, which shows that any agreement protocol facing an adversary able to erase messages after the fact needs quadratic communication. That bound is proved in a point-to-point message model, where erasure is free. Our argument is that on a radio the premise of free, content-aware erasure does not hold once packets are sealed. What remains is content-blind erasure paid for in jamming energy. That is closer to the weakly adaptive model of Expected Constant Round Byzantine Broadcast Under Dishonest Majority, where messages already sent cannot be retracted.
Relation to Prior Work
Three lines of work motivate the gap. Round-Efficient Byzantine Broadcast Under Strongly Adaptive and Majority Corruptions defeats strongly adaptive corrupt majorities with time-lock puzzles and committees chosen by verifiable random functions. We reuse its blind-corruption argument but replace the computational delay with airtime. Securing every bit: authenticated broadcast in radio networks shows that radio physics can replace signatures, because an attacker cannot forge silence. However, it assumes simultaneous transmitting and sensing, and its adversary does not adapt. Byzantine Consensus in Wireless Networks cuts forwarding to once per node using aggregate signatures, but it assumes a collision-free channel. Neither of the radio papers considers an attacker who corrupts nodes based on what they transmit.
One paper constrains the design. Probabilistic Handshake in All-to-all Broadcast Coded Slotted ALOHA lets a half-duplex node infer, with no acknowledgment traffic, whether its packet was probably decoded. It does this by simulating a neighbor's interference-cancellation decoding. It catches only about 30% of failures and assumes honest participants. We use it as the sender's jamming detector, and we treat its false-handshake rate as a bound on how much a sender can learn about its own erasures.
The lightweight-hardware literature supplies the cost targets and the key source. The circuits of TV-PUF : A Fast Lightweight Aging-Resistant Threshold Voltage PUF and A Low-Power Hybrid RO PUF With Improved Thermal Stability for Lightweight Applications derive device-unique keys and random values from manufacturing variation at microwatt power. We use such a PUF only to seed each node's private slot-selection randomness; the all-or-nothing transform itself needs no secret key.
Research Program
The first part is modeling. We define a radio-strongly-adaptive adversary. It can corrupt any node at any symbol boundary, learning that node's state and keys. It can transmit noise that destroys any slot it chooses, within a total energy budget $\beta$, the budget notion already used by Alistarh et al. It cannot undo symbols that receivers have already captured. Half-duplex honest nodes hear nothing while they transmit.
We then prove a reduction. For a sealed packet sent as $r$ copies in slots chosen with private randomness, the probability that the adversary erases the packet is the same whatever the plaintext is. That probability is at most the fraction of candidate slot patterns the adversary can afford to jam. The main technical work is handling copies whose early slots have already been captured before the corruption: the adversary may learn the slot pattern of the remaining copies, so we bound how much a partial observation helps it.
The second part is a protocol. We port the committee-voting structure of the time-lock-puzzle protocol to a single-hop radio neighborhood, replacing each puzzle with a sealed, slot-randomized packet. We then extend it across multiple hops by forwarding the sealed packet unchanged. This preserves content-blindness at every hop, because relays learn content only after full receipt, exactly as neighbors do.
The third part is implementation. We will measure the energy and latency of the all-or-nothing transform, in software on a 16-bit microcontroller-class target and in a circuit-level estimate. We will compare these against the sequential squaring that a time-lock puzzle of equivalent protective delay would require.
Baselines
The naive reference point is insecure flooding. It has zero Byzantine resilience, but it sets the speed floor. It will run in the same WSNet simulator topologies, with the same node counts (up to 4,000 nodes, as in Alistarh et al.) and the same channel model.
The strongest existing radio-native method is NeighborWatchRB from Securing every bit: authenticated broadcast in radio networks. That paper reports completing broadcasts 7.7 times slower than naive flooding while delivering the correct message to more than 90% of honest nodes when 25% of devices are malicious. We will re-run it under our half-duplex model, which the original omits, and under our adaptive reactive jammer. Beating it means at least 90% correct delivery under that malicious fraction plus adaptive corruption, at a slowdown no worse than 7.7 times.
The strongest existing method against strongly adaptive corruption is the time-lock-puzzle protocol of Wan et al. No reported empirical result on energy or latency was found on Lacuna for this protocol. We will therefore implement it on the same simulated hardware, with puzzle hardness set to cover one round, and compare energy per delivered bit and end-to-end latency. Beating it means matching its content-blindness guarantee at a lower energy cost.
Two ablations isolate the key ingredient. In the first, packets are encrypted with a standard stream cipher under the sender's key instead of the all-or-nothing transform. In the second, packets are sealed but sent in fixed, predictable slots. All variants share the same slot count, copy count $r$, adversary energy budget, and a fixed tuning budget for the jammer's policy.
Why not just…?
Why not just run the time-lock-puzzle protocol on the sensors? Its protective delay comes from sequential squaring. By construction this cannot be sped up, so it must run for the full round on every honest node. The file's own gap analysis identifies this as a processing bottleneck for low-power devices. We will measure it directly rather than assume it, since the file contains no reported microcontroller figures. If the puzzle's measured energy turns out to be comparable to the airtime seal, the practical case collapses, and we will report that.
Why not just encrypt every packet at the link layer? This is the most serious alternative, and the first ablation tests it. Ordinary encryption hides content from outsiders but not from an adversary that corrupts the sender mid-packet and takes its keys. Such an adversary decrypts the prefix and jams the tail only when the vote is unfavorable. The prediction is that content-dependent erasure under link encryption stays close to the unprotected level, while sealed packets remove it. If link encryption with per-packet ephemeral keys erased from memory before transmission proves equally blind, that simpler design should be adopted, and our contribution narrows to the slot randomization.
Why not just retransmit until acknowledged? Explicit acknowledgments cause signaling storms in dense broadcast settings, as Probabilistic Handshake in All-to-all Broadcast Coded Slotted ALOHA argues. More importantly, once an unsealed packet has been seen, the attacker knows its content and can jam every retransmission. Retries therefore make the attacker spend more energy but do not stop it from choosing which votes to erase.
Why not just rely on radio physics, since signals cannot be recalled? Physics blocks literal recall, but reactive jamming within the packet recovers the same effect, and half-duplex means the sender never notices. The fixed-slot and unsealed conditions measure how much erasure power the attacker keeps when only physics protects the packet.
Proposed Experiments
We will run Monte Carlo channel simulations with 200 slots per frame, matching Ivanov et al., along with multi-hop WSNet scenarios. The honest vote bit is drawn uniformly at random. The adversary jams, and corrupts nodes, according to its best content-triggered policy within the energy budget $\beta$.
The decisive check is the gap in erasure rate between packets carrying the two vote values. It should be near zero for sealed, slot-randomized packets and large for both ablations. Secondary metrics are agreement-failure probability at corrupt fractions from 25% to above one half, the fraction of honest nodes receiving the correct broadcast, latency relative to flooding, and energy per delivered bit against the time-lock baseline. We will also sweep the copy count $r$ to trace erasure probability against jammer budget. Our analysis predicts that erasure probability falls roughly geometrically in $r$ when slots are chosen independently, since each extra copy forces the adversary to guess and jam one more private slot.
References
- Round-Efficient Byzantine Broadcast Under Strongly Adaptive and Majority Corruptions
- Communication complexity of byzantine agreement, revisited
- Expected Constant Round Byzantine Broadcast Under Dishonest Majority
- Securing every bit: authenticated broadcast in radio networks
- Byzantine Consensus in Wireless Networks
- Probabilistic handshake in all-to-all broadcast coded slotted ALOHA
- TV-PUF : A Fast Lightweight Aging-Resistant Threshold Voltage PUF
- A Low-Power Hybrid RO PUF With Improved Thermal Stability for Lightweight Applications