Plug-and-Play Long-Range Defense

In three numbers

What the defense buys

All figures come from the paper's Ethereum-based estimates in §6. They are estimates from concrete parameters, not measurements of a deployment.

Protection window

>10 years

Up from 189 days, if an adversary evaluates the VDF at most 5% faster than an honest server. At 1% faster it is more than 51 years (Theorem 2).

Worst-case proof after 10 years

≈20 KB

vs. ≈337 MB for graph-labeling PoSW (SNACKs), per the §6 text. Fig. 7 plots ≈7.9 KB for this point; see the provenance note.

Trust assumption

1 honest server

Out of however many the client contacts. The PoS consensus protocol is unchanged, so no fork is needed to deploy it.

The problem

Old keys can rewrite old history

In a proof-of-stake chain, validators sign blocks with keys backed by stake. Once validators exit and withdraw, their old signing keys can no longer be slashed, but they still verify for the epochs where they held stake. An attacker who buys enough exited keys can sign a competing history from some past epoch onward. Every rule a new client checks (valid transactions, valid consensus signatures) passes on both chains, so the client cannot tell which is real. That opens the door to double-spending. This is the long-range attack.

Today's remedy is checkpoints published on bulletin boards and block explorers, which a new client must trust. That is centralisation and a single point of failure. Key rotation needs a hard fork, and it assumes validators delete old keys they could instead sell. Lewis-Pye and Roughgarden proved that PoS cannot avoid long-range attacks without a time-dependent primitive such as a VDF or ephemeral keys.

This paper adds that time-dependent primitive outside the chain. Independent servers timestamp each finalized checkpoint as it is emitted, using a new primitive called Insertable Proof of Sequential Work ($\mathsf{InPoSW}$). An attacker who forks the past later cannot produce an older timestamp for the fork than the honest server already holds. To win, the attacker would have had to start timestamping around the moment the authentic checkpoint appeared, and at that point they did not yet have the keys.

Interactive · Figures 3–5 of the paper

Inside $\mathsf{InPoSW}$: VDFs arranged like a skip list

A single VDF only accepts data when it starts, so timestamping each checkpoint with its own VDF costs work linear in the number of checkpoints. Graph-labeling PoSW (SNACKs) accepts data mid-run, but its proofs grow linearly with elapsed time. $\mathsf{InPoSW}$ runs VDFs of length $\Delta_T\cdot 2^i$ side by side. At each step $N$ it starts a new level-$i$ VDF for every $i$ with $2^i \mid N$, and each new VDF takes a vector commitment of the outputs that just finished together with the new data. To prove that data $x_t$ went in at step $t$, the prover sends only the VDFs on the shortest chain from $t$ to now.

Steps elapsed $N$ (each step is $\Delta_T$) 27

Checkpoint $x_t$ inserted at step $t$ 5

finished VDF
still running
on the proof path
inserted checkpoint $x_t$

VDF proofs sent

–

shortest chain from $t$ to $N$

Bound, Fig. 5

–

$\le 2\log_2 N$ VDF proofs

Sequential work proven

–

$x_t$ was inserted $(N-t)\cdot\Delta_T$ ago

Level-$i$ VDFs start at every multiple of $2^i$, as in the paper's evaluation algorithm (Fig. 4). The highlighted chain splits $[t, N]$ into the fewest aligned intervals. That is the "shortest path" in the Fig. 3 caption. With §6's parameters ($\Delta_T \approx 3.6$ minutes), ten years is $10 \cdot 365.25 \cdot 24 \cdot 60 / 3.6 \approx 1.46$ million steps by our arithmetic, and the paper says $\approx 20$ VDF instances then run in parallel.

A note on Fig. 5 as typeset. The verifier loop in Fig. 5 sets $z = 2^{\lfloor\log_2 t\rfloor}$ and takes the lowest set bit of $j$ while $j > z$. Run literally, that loop can step past $t$. For example, with $N = 2$ and $t = 1$ it picks the level-1 VDF covering $[0,2]$, which starts before $x_1$ was inserted. This widget draws the aligned shortest path that the Fig. 3 caption and the completeness proof describe. The $\le 2\log_2 N$ bound holds for it. By our own exhaustive check (not in the paper), it never needs more than 18 proofs for any $N \le 1024$.

Interactive · Theorem 2 and §6

How long the past stays safe

Suppose the chain has $T_\Pi$-uncorrupted finality: nobody can gather enough keys to fork a checkpoint until $T_\Pi$ after it is emitted. On Ethereum, §6 puts this at at least 189 days, the estimated time for $\ge 33\%$ of validators to withdraw. The attacker therefore starts at least $T_\Pi$ behind the honest server. The VDF has $(1-\epsilon)$-sequentiality, meaning an adversary evaluates it at most a fraction $\epsilon$ faster. Under that assumption the attacker never catches up until time $T_\Pi\cdot(1/\epsilon).$

Adversary's VDF speed-up $\epsilon$ 5%

Paper's values

Without the defense

189 days

$T_\Pi$ for Ethereum, §6

With InPoSW timestamps

–

$T_\Pi\cdot(1/\epsilon)$

The paper states two cases: $\epsilon = 5\%$ gives $189\cdot 20$ days, "${>}10$ years", and $\epsilon = 1\%$ gives "${>}51$ years". The 5% case is motivated by the VDF Alliance FPGA competition, where the winner and the runner-up differed by ${<}4.5\%$. Other slider values apply the same Theorem 2 formula; the paper does not discuss them.

Interactive · Figures 6 and 7 of the paper

Prover storage and proof size over ten years

These are the paper's estimates for graph-labeling PoSW (SNACKs, instantiated with RandomX) and $\mathsf{InPoSW}$ (instantiated with Wesolowski's VDF), using the parameters in the results table. Drag the slider or hover over the chart. The y-axis is log-scale, and each gridline is a factor of ten.

Metric

Elapsed time 10.0 years

Graph-labeling PoSW (SNACKs)
$\mathsf{InPoSW}$ (this work)
value stated in the §6 text (10 years)

SNACKs

–

InPoSW

–

Reduction (plotted curves)

–

Show the numbers as a table

The figure and the text disagree for $\mathsf{InPoSW}$. At 10 years the plotted $\mathsf{InPoSW}$ curves end at ≈240 GB of storage and ≈7.9 KB of proof. The §6 text says ≈546 GB and ≈20 KB, and its "${>}22\times$" and "${>}17969\times$" reductions follow from the text's values. The SNACKs curves agree with the text (≈12 TB, ≈337 MB). This page plots both sources and does not pick one. Curve values were read from the vector source of Figs. 6–7 (100 points per series, 4 significant figures); see provenance.

Guarantees · Table 2 of the paper

How it compares with other long-range defenses

	Winkle	Solana	SNACK	Babylon / Pikachu	Minotaur	ETH's Finality Gadgets	PoSAT	This work

Reproduced cell by cell from Table 2, including its N/A entries. ✓ = yes, ✗ = no.

What the construction is proven to give

Property	Statement in the paper
Complete, sound, succinct	Theorem 1: the $\mathsf{InPoSW}$ construction of Figs. 4–5 is complete, sound and succinct (proof in the appendix).
Extended finality	Theorem 2: a chain with $T_\Pi$-uncorrupted finality, combined with the bootstrap protocol using a VDF with $(1-\epsilon)\cdot T$-sequentiality, achieves $T_\Pi\cdot(1/\epsilon)$-extended finality against long-range attacks.
Honest-minority servers	The client is protected as long as at least one server it contacts is honest.
Consensus-agnostic	Works with any PoS chain that emits finalized checkpoints, independent of the block-selection rule (e.g. GHOST, Ouroboros).
Non-interactive proofs	$\mathsf{InPoSW}.\mathsf{Ver}$ is non-interactive, so the bootstrap protocol is non-interactive if the bisection game is.
Consistent with the impossibility result	The VDF is the time-dependent primitive that Lewis-Pye and Roughgarden show is necessary.
Easy server maintenance	At a step $2^i$ the server can migrate hardware by moving one succinct vector commitment. Graph-labeling PoSW would need the whole graph moved.

Estimated, not measured

Cost analysis

The paper estimates costs analytically, with Ethereum as the reference chain. There is no implementation benchmark.

Asymptotic cost (Table 1)

PoSW scheme	Prover storage	Proof size
GL-PoSW (SNACKs)	$O(N\cdot\Delta_T\cdot\lambda_H)$	$O(N\cdot\log^2(N\cdot\Delta_T)\cdot\lambda_H)$
$\mathsf{InPoSW}$, black-box VDF	$O(N\cdot(\Delta_T\cdot\lambda_{\mathsf{VDF}}\cdot\log N + \mathrm{poly}(\lambda_{\mathsf{VDF}},\log N\Delta_T)))$	$O(\log N\cdot(\mathrm{poly}(\lambda_{\mathsf{VDF}},\log N\Delta_T)+\lambda_H\cdot\log\log N))$
$\mathsf{InPoSW}$, Wesolowski VDF	$O(\log N\cdot(N\cdot(\lambda_{\mathsf{VDF}}+\lambda_H)+\sqrt{N\cdot\Delta_T}\cdot\lambda_{\mathsf{VDF}}))$	$O(\log N\cdot(\lambda_{\mathsf{VDF}}+\lambda_H\cdot\log\log N))$

$N$ is the number of evaluations, $\Delta_T$ the interval between insertions, and $\lambda_H,\lambda_{\mathsf{VDF}}$ the security parameters of the hash and the VDF. Verification computation roughly tracks proof size.

Concrete parameters (§6)

Parameter	Value	Why
Insertion interval $\Delta_T$	≈ 3.6 min	Estimated time for $2^{33}$ squarings (best VDF Alliance FPGA figures). Ethereum emits a finality checkpoint about every 6 minutes.
$\lambda_{\mathsf{VDF}}$	2048	As suggested for Wesolowski's VDF
$\lambda_H$	256	As in most blockchain systems
SNACKs hash	RandomX	ASIC-resistant, with a low hash rate (≈1300 sequential hashes/s on the best-known CPU), which favours SNACKs
SNACKs soundness $\epsilon$	$2^{-40}$
Uncorrupted finality $T_\Pi$	≥ 189 days	Estimated time for $\ge 33\%$ of Ethereum validators to withdraw

After ten years of operation

Quantity	§6 text	Figs. 6–7 curve
SNACKs prover storage	≈ 12 TB	≈ 12,570 GB
$\mathsf{InPoSW}$ prover storage	≈ 546 GB	≈ 240.0 GB
Storage reduction	${>}22\times$	≈ 52×
SNACKs worst-case proof	≈ 337 MB	≈ 344,900 KB
$\mathsf{InPoSW}$ worst-case proof	≈ 20 KB	≈ 7.875 KB
Proof-size reduction	${>}17969\times$ (text) · ${>}17900\times$ (caption)	≈ 43,797×
Parallel VDF instances	≈ 20	–

Curve-derived ratios are the ratio of the plotted values and appear nowhere in the paper. The paper says the ≈20 VDF proofs verify "with a mobile device in a few seconds", and that ≈20 processors for evaluation are "well within the reach of GPUs or FPGA".

Provenance and disagreements

Figs. 6–7 vs. §6 text ($\mathsf{InPoSW}$). The curves end at ≈240 GB and ≈7.875 KB. The text states ≈546 GB and ≈20 KB. The text's reductions (${>}22\times$, ${>}17969\times$) match its own values against the SNACKs endpoints. The SNACKs curves agree with the text. No plotting notebook is in the paper's source, so the curves were read from the matplotlib vector output that the PDF embeds, and the page shows both.
${>}17900\times$ vs. ${>}17969\times$. Fig. 7's caption and §6's body text give different proof-size reductions.
Fig. 7 axis label. The y-axis reads "Prover Size (KB)", but the caption and text describe the worst-case proof size.
${>}22\times$ from rounded values. $12\,\text{TB}/546\,\text{GB} = 21.98$ if the rounded numbers are divided directly. The claim relies on the unrounded SNACKs value (≈12,570 GB on the curve).
Fig. 5 loop. See the note under the skip-list widget.

Reference

Cite this work

@inproceedings{ng2024plug,
  title     = {A Plug-and-Play Long-Range Defense System for
               Proof-of-Stake Blockchains},
  author    = {Ng, Lucien K. L. and Chatzigiannis, Panagiotis and Le, Duc V. and
               Minaei, Mohsen and Kumaresan, Ranjit and Zamani, Mahdi},
  booktitle = {European Symposium on Research in Computer Security (ESORICS)},
  year      = {2024}
}

Code. The paper has no code or data availability statement and links no implementation. Its results are analytical estimates. The linked PDF is the full version of the ESORICS 2024 paper.

What the defense buys

Old keys can rewrite old history

Walk a long-range attack

Inside $\mathsf{InPoSW}$: VDFs arranged like a skip list

How long the past stays safe

Prover storage and proof size over ten years

How it compares with other long-range defenses

What the construction is proven to give

Cost analysis

Asymptotic cost (Table 1)

Concrete parameters (§6)

After ten years of operation

Provenance and disagreements

Cite this work