Modeling Resources in Permissionless Longest-chain Total-order Broadcast

The problem

Same protocol, different resource, different attacks

A permissionless blockchain has no membership list, so it cannot count votes. Instead it makes writing rights scarce: you may append a block only if you can prove you hold some resource. Bitcoin uses computation, Ouroboros Praos uses stake, Filecoin uses storage.

Each of these protocols has its own security proof, in its own model, under its own assumptions. That makes them almost impossible to compare — and it leaves the interesting question unanswered. Proof-of-Stake is vulnerable to long-range attacks and Proof-of-Work is not. Is that a fact about Ouroboros, or a fact about stake?

Interactive 1 · Def. 3.3 & Def. 4.1

The allocator is a box — commit into it

The paper's move is to replace “Proof-of-Work” and “Proof-of-Stake” with a single interface. You hand a resource allocator a budget and a chain state; it hands back a commitment $\pi$ or $\bot$. Pick a resource, press Play, and watch what actually travels on the wires — that is the whole of what distinguishes Proof-of-Work from Proof-of-Stake in this model.

Provenance. The four events are Def. 3.2; the resource types are Def. 3.3; the five properties the box enforces are Def. 4.1. The draw inside the box is the allocator's own: Lem. 4.4 describes $\mathsf{RA}_{\mathsf{pow}}$ as running $r$ threads of a “biased coin with probability $\varrho$”, and Def. 4.6 (arXiv Def. 10 for storage) gives leader selection the same shape. This is a walk-through, not a simulation — the sequence is fixed, and it shows one refused commit and one granted one rather than implying any particular rate. What changes between the cells is what the interface carries: whether a budget travels on the wire at all, whether it comes back, and whether the allocator has to reach into the chain to find it. Repeating a commit on a reusable resource returns the same $\pi$, which is the use-once clause of Def. 4.1; the $h_0$ branch is step 2 of §5.1.

Interactive 2 · Equation 1

The one inequality that has to hold

Every secure allocator must satisfy honest-majority assignment: the chance that some Byzantine process wins a slot has to stay under a bound set by the honest chance and the network delay.

$$p_{\mathcal{A}} \;<\; \frac{1}{\Delta - 1 + 1/p_{\mathcal{H}}}$$

$$p_{\mathcal{H}} = 1-(1-\varrho)^{R-R_{\mathcal{A}}} \qquad p_{\mathcal{A}} = 1-(1-\varrho)^{R_{\mathcal{A}}}$$

Provenance. The inequality is Equation 1 in Def. 4.1, attributed there to Gaži et al. (CCS 2020). The closed forms for $p_{\mathcal{H}}$ and $p_{\mathcal{A}}$ are from the Proof-of-Work proof (Lem. 4.4); the Proof-of-Stake proof (Lem. 4.8) gives the same pair, writing $p_{\mathcal{A}} \approx 1-(1-\varrho)^{R_{\mathcal{A}}}$ and noting that an adversary committing to shorter chains could raise it slightly. The storage proof (arXiv Lem. 7) writes $p_{\mathcal{A}} \le 1-(1-\varrho)^{R_{\mathcal{A}}}$, with equality only when Byzantine processes commit their whole budget. Leader selection has the same shape $1-(1-\varrho)^{r_i}$ in all three allocators (Def. 4.6; arXiv Def. 10 for storage). The paper fixes no numeric values for $R$, $R_{\mathcal{A}}$, $\varrho$ or $\Delta$ — the slider settings are illustrative, only the formulas are the paper's.

At $\Delta=1$ the bound collapses to $p_{\mathcal{A}} < p_{\mathcal{H}}$ and the dashed line lies exactly on the blue one.

Interactive 3 · §5.1

The long-range attack, step by step

A long-range attack corrupts processes that used to hold the resource. It works on stake and fails on computation — and the framework says exactly where it fails. Switch the resource and walk the four steps.

Is a virtual-resource-shifting event happening?

Def. 5.1 needs two things at once: a set $\mathcal{P}_{\mathsf{maj}}$ that held the majority at an old height $h_0$, and that holds almost nothing at the current height $h_1$.

Provenance. Steps are the four numbered items of §5.1 (§6.1 in arXiv); the two inequalities are Def. 5.1 (Def. 12 in arXiv); the conclusion is Thm. 5.4 (Thm. 10 in arXiv). $R$ and $R_{\mathcal{A}}$ are taken from the sliders above.

Interactive 4 · Lemma 5.2

Run the race

Once the shifting event has happened, the adversary rebuilding from $h_0$ holds what $\mathcal{P}_{\mathsf{maj}}$ held back then — strictly more than the honest processes hold now. The honest chain starts ahead by the fork depth. Press Run and watch the two chains extend, one block at a time, each at its own probability per time step.

Using R = 100, R_A = 30, ϱ = 0.0100 from the threshold panel — change them there and the race resets.

Provenance. Each time step is a Poisson trial with $\Pr[X_i=1]=p_{\mathcal{H}}$ on the honest chain and $p_{\mathcal{A}^*}$ on the adversarial one — the trials the proof of Lem. 5.2 sums. The race is simulated: the blocks you see are real draws against those two probabilities, so the run has variance and the overtake time moves. The dashed marks are the deterministic $p_{\mathcal{H}}t$ and $p_{\mathcal{A}^*}t$ and the band edges $(1-\epsilon)p_{\mathcal{H}}t$, $(1+\epsilon)p_{\mathcal{A}^*}t$, whose failure probabilities the proof gives as $\exp(-p_{\mathcal{H}}t\epsilon^2/2)$ and $\exp(-p_{\mathcal{A}^*}t\epsilon^2/3)$. The expected crossing time $t^\star = (h_1-h_0)/(p_{\mathcal{A}^*}-p_{\mathcal{H}})$ is arithmetic on those two rates; the paper itself only says “eventually”. The slider's lower stop, $R_{\mathsf{maj}} = R - R_{\mathcal{A}} + 1$, is the smallest integer budget that satisfies Def. 5.1's strict majority; it starts above that stop only so the two rates are far enough apart to see.

Interactive 5 · Def. 5.5 & Prop. 5.6

Extending a chain costs nothing if the resource comes back

A burnable resource is spent every step you mine; a reusable one is not. Over a window of $t_2-t_1+1$ steps the first accumulates and the second does not — which is the whole reason a private attack or a nothing-at-stake attack is cheap on stake and expensive on hashing.

$$\mathrm{Cost}_{\mathsf{burn}}(p_i,t_1,t_2) = \sum_{t=t_1}^{t_2}\mathsf{Alloc}(p_i,t)$$

$$\mathrm{Cost}_{\mathsf{reuse}}(p_i,t_1,t_2) \;\le\; \max_{t\in[t_1,\dots,t_2]}\mathsf{Alloc}(p_i,t)$$

Provenance. Both expressions are Def. 5.5 verbatim. The reusable side is an upper bound in the paper, not an equality, and is drawn and labelled as a bound. Prop. 5.6 asserts strictness only for $t_2 > t_1$; at a one-step window the two coincide, and the chart shows that rather than hiding it. The budget profiles are illustrative — the paper leaves $\mathsf{Alloc}$ an arbitrary function.

Properties

What a secure resource allocator has to provide

Satisfy all five and the generic algorithm inherits safety and liveness, hence total-order broadcast (Lem. 4.2, Thm. 4.3). Each column is the corresponding security proof.

The use-once row is the load-bearing one: it is the single place where burnable gets for free what reusable has to build, and every difference further down the page traces back to it.

Consequences

Which resource each attack needs

Storage sits in the awkward middle: external, so long-range attacks fail against it, but reusable, so the cost-based attacks stay cheap — though on an external resource they are far easier to spot, because the adversarial chain visibly carries less committed power.

Cite

BibTeX

@inproceedings{AzouviCLVZ22,
  author    = {Sarah Azouvi and Christian Cachin and Duc V. Le and
               Marko Vukoli\'{c} and Luca Zanolini},
  title     = {Modeling Resources in Permissionless Longest-chain
               Total-order Broadcast},
  booktitle = {26th International Conference on Principles of
               Distributed Systems (OPODIS 2022)},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume    = {253},
  pages     = {16:1--16:23},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f\"{u}r Informatik},
  year      = {2022},
  doi       = {10.4230/LIPIcs.OPODIS.2022.16}
}

Code and data

The paper declares no supplementary material — its \supplement field is empty and it reports no implementation, dataset or measurement. There is nothing to link, and every number on this page is computed in the browser from the formulas cited beside it.

Which version you are reading

Section, definition and theorem numbers on this page are the OPODIS proceedings numbers, with the linked PDF's numbers in parentheses where they differ. The linked PDF is the full arXiv version (arXiv:2211.12050v1), which inserts the Proof-of-Storage allocator as its Section 5 — so everything from the security analysis onward shifts by one section, and its definitions and theorems are numbered in single running sequences rather than per section.