F-RO — Local random oracle

F-RO (Local random oracle) is part of Idealized Setup and Resources in the UC functionality encyclopedia. Status: an idealized setup assumption or shared resource.

A lazily-sampled table with a registered party set in front of it. What makes the entry worth having is not the table — every treatment writes the same three lines — but the choice the table is not: this is the local random oracle, one instance per session, against the shared G-RO next to it. The source transcribed here is unusual in arguing that choice out loud rather than assuming it.

Functionality

Reading the box: $\mathbf{A}$ is the adversary’s role in a caller’s id, so $\mathit{id}'.F \neq \mathbf{A}$ says the caller is not the adversary; $\mathbf{C}$ is the corrupted set; $\square$ marks a point of the table never drawn; require refuses the call, and the framework answers $\textsf{rej}$, so no return is written for it; $\kappa$, the parameter on the header line, is the output length. $\mathbf{U} := \varnothing$: this functionality calls nothing, and in particular never calls the adversary.

Functionality $\mathcal{F}_{\mathsf{RO}}$

$\mathit{pid}$, $\mathbf{P}$, $\mathbf{N}$, $\mathbf{U} := \varnothing$, $\mathit{par} := \kappa$

Initialize():

$\mathtt{Reg} \gets \varnothing$// the party set, empty until parties ask
$\mathtt{H}[*] \gets \square$// the table, drawn lazily

id.Register()from id′

$\textbf{require}\ \mathit{id}'.F \neq \mathbf{A} \ \vee\ \mathit{id}.P \in \mathbf{C}$// the adversary may act only for a corrupt party
$\mathtt{Reg} \gets \mathtt{Reg} \cup \{\mathit{id}.P\}$
$\textbf{return}\ \mathit{id}.P$

id.Deregister()from id′

$\textbf{require}\ \mathit{id}.P \in \mathtt{Reg} \ \wedge\ (\mathit{id}'.F \neq \mathbf{A} \ \vee\ \mathit{id}.P \in \mathbf{C})$
$\mathtt{Reg} \gets \mathtt{Reg} \setminus \{\mathit{id}.P\}$
$\textbf{return}\ \mathit{id}.P$

id.Eval(x)from id′

$\textbf{require}\ \mathit{id}.P \in \mathtt{Reg} \ \wedge\ (\mathit{id}'.F \neq \mathbf{A} \ \vee\ \mathit{id}.P \in \mathbf{C})$// registration is the whole access control
$\textbf{if}\ \mathtt{H}[x] = \square\ \textbf{then}$
$\mathtt{H}[x] \gets_{\$} \{0,1\}^{\kappa}$
$\textbf{return}\ \mathtt{H}[x]$

id.Leak()from id′

$\textbf{return}\ \mathtt{Reg}$// who is registered, and nothing about $\mathtt{H}$

The box is transcribed from Badertscher, Maurer, Tschudi and Zikas, Bitcoin as a transaction ledger: A composable treatment, ePrint 2017/149, revision 20240405:081352, Figure 3, p. 19 (the PDF’s numbering and the printed numbering agree) — the functionality $\mathcal{F}^{\kappa}_{\mathsf{RO}}$, whose caption records that it “makes no changes to the standard corruption mode”.

Two things in the box are not the random oracle:

Lines 3–8 are a party set, and it is doing real work. Most printed random oracles answer anybody. This one answers only registered parties, and de-registration takes the access away again (line 7). That is what makes $\mathcal{F}_{\mathsf{RO}}$ fit the dynamic-availability model the source needs: a party that has left the protocol stops being able to hash, so the work it can do is bounded by the interval over which it was registered.
Line 3’s clause is the framework’s own convention, not the source’s addition. The source writes each interface as “from some party $P$ (or from $\mathcal{A}$ on behalf of a corrupted $P$)”. Here that is one test: the adversary may drive an operation in a party’s name exactly when that party is corrupt.

The rest is the standard construction, and the one line that matters is line 11: a point is drawn once, uniformly, and then never moves. There is no $\mathsf{Program}$ and no $\mathsf{Observe}$ — the two operations that make the global oracle usable — and their absence is the entire difference between this page and G-RO. A local oracle needs neither: the simulator owns the instance, so it can program by answering, and it sees every query because every query comes to it.

Where the source needed a decision:

Source	Box	Why
`GET-REGISTERED` is an interface, answered to $\mathcal{A}$	Line 13, $\mathsf{Leak}$	The registered set is exactly what a corrupt party’s adversary — or any outsider — is allowed to read off this box, so the source’s adversary-only query is this framework’s leakage interface rather than a fourth operation. Nothing about $\mathtt{H}$ is leaked: line 13 does not mention it, and there is no way to learn an undrawn point except by drawing it.
Registration returns $(\textsf{REGISTER}, \mathit{sid}, P)$	Returns $\mathit{id}.P$	The session identifier lives in the process id here, so the reply is the party name alone.
No adversary interaction at all	$\mathbf{U} := \varnothing$	Unusually for a setup functionality, this one places no calls: it neither notifies the adversary of a query nor asks it anything. That is a claim about the box and it is the source’s, not a simplification — and it is why the query-rate assumption below has to be imposed from outside rather than written into the box.

Known realizations

None, and none is intended: a random oracle is a setup assumption. What the source does instead is restrict it, and the mechanism is worth recording here because it is where the locality argument cashes out.

The standard property-based analyses of Bitcoin assume that in each round the adversary cannot make more random-oracle calls than the honest parties collectively can. The source declines to model that by restricting the class of environments — “restricting the environment is not compliant with a general composition theorem” — and wraps the functionality instead. Figure 4, p. 21 gives the wrapped functionality $\mathcal{W}^{q}(\mathcal{F}^{\kappa}_{\mathsf{RO}})$: in a $\mathcal{G}_{\mathsf{Clock}}$-hybrid world it counts $\mathsf{Eval}$ calls arriving from $\mathcal{A}$ on behalf of each corrupted party, forwards only the first $q$ per clock tick, and relays everything else — including every honest party’s query and all registration traffic — unchanged. The bound therefore falls on corrupt parties only, per party, per tick.

This encyclopedia has no page for the wrapper. It is a distinct construct — a functionality that wraps another rather than one that stands alone — and it should not be confused with F-wrap, which is a hardware token.

Properties

Unpredictability, with probability exactly $2^{-\kappa}$ per fresh point: an undrawn $x$ is answered uniformly, and nothing else in the box is a function of $\mathtt{H}$. Since the box makes no calls at all, the only route to a point is $\mathsf{Eval}$, which requires registration.
Consistency, with probability exactly $1$: line 10 tests before line 11 draws, so two $\mathsf{Eval}$ calls on the same $x$ agree, across parties and across time, for as long as the instance lives.
Not programmable, not observable, and local anyway. The source’s own argument for why that suffices, and why the global alternative is worse here, is at its §3.5: a global oracle would force the simulator to create blocks carrying real work, so it would need a much larger query budget than the real-world adversary — and the simulator’s edge in this proof is that it can program its own oracle. The paper also notes that a programmable global oracle exists in the literature but “does not appear to offer more insights than a local RO”, and that its programmability “comes at the price of a technical condition via which an adversary can always make a protocol abort, which is unrealistic”.
One instance per session, and that is the whole content of “local”. The header line leaves $\mathit{pid}$ a parameter and admits the standard callers — against G-RO, which pins $\mathit{pid}$ to a constant and admits every id. Two sessions of a protocol using this box get two independent tables.

Formal artifacts

No machine-checked formalization yet.

References:

Badertscher, Maurer, Tschudi, and Zikas. Bitcoin as a transaction ledger: A composable treatment. In Advances in Cryptology – CRYPTO 2017, Part I, volume 10401 of LNCS, pages 324–356, 2017. Figure 3, p. 19 of revision 20240405:081352, the definition transcribed above; Figure 4, p. 21 for the query-rate wrapper; §3.5, pp. 19–20 for the argument that this oracle should be local.
Nielsen. Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. In Advances in Cryptology – CRYPTO 2002, pages 111–126, 2002. Read, and it prints no random-oracle functionality: it formulates the RO as a model in which the parties and the environment share access to a random function, and the one ideal functionality it writes down is $\mathcal{F}_{\mathsf{nce}}$ for non-committing encryption. Its result — that no non-interactive protocol in the RO model is adaptively secure — is what makes it the standard citation for the oracle’s limits, and the reason it cannot be the citation for the box above.