G-clock — Clock

G-clock (Clock) is part of Idealized Setup and Resources in the UC functionality encyclopedia. Status: an idealized setup assumption or shared resource.

A shared monotone counter modeling round synchrony, introduced by Katz–Maurer–Tackmann–Zikas and recast as a shared global setup by Badertscher–Maurer–Tschudi–Zikas. It has become the canonical timekeeping functionality behind composable analyses of Bitcoin and its successors: global (one instance, reachable from every session), readable by anyone it serves, and advanced only once every honest party currently in the round structure has asked it to.

Functionality

Reading the box: \(\mathcal{A}^{!}(\cdot)\) is a responsive call on the adversary slot — the answer comes back before anything else runs, and here it is discarded outright, the call being a notification; \(\mathbf{C}\) is the set of corrupted parties; \(A\) and \(Z\) are the adversary’s and environment’s name components, so the first test of each mutator asks whether an outsider is calling on an honest party’s behalf. The process id is pinned to a constant and \(\mathbf{N}\) admits every standard, adversarial and environment id — that is what makes the clock global.

Functionality \(\mathcal{G}_{\mathsf{Clock}}\)
\(\mathit{pid} := (\mathsf{GClock},0,0)\),   \(\mathbf{P}\),   \(\mathbf{N} := \mathbf{Std} \cup \mathbf{A} \cup \mathbf{Z}\),   \(\mathbf{U} := \{(\mathcal{A},\mathsf{serves})\}\),   \(\mathit{par} := \bot\)
Initialize():
  1. \(\mathtt{now} \gets 0\)
  2. \(\mathtt{reg},\, \mathtt{tick} : \mathcal{G}_{\mathsf{Clock}}.\mathbf{P} \to \{0,1\}\)
  3. \(\mathtt{reg}[*] \gets 0\);  \(\mathtt{tick}[*] \gets 0\)
id.Register()from id′
  1. \(\textbf{if}\ \mathit{id}'.F \in \{A,Z\} \ \wedge\ \mathit{id}.P \notin \mathbf{C}\ \textbf{then}\)
  2. \(\textbf{return}\ \mathtt{now}\)
  3. \(\mathtt{reg}[\mathit{id}.P] \gets 1\);  \(\mathtt{tick}[\mathit{id}.P] \gets 0\)// a fresh member owes a tick
  4. \(\textbf{return}\ \mathtt{now}\)
id.Deregister()from id′
  1. \(\textbf{if}\ \mathit{id}'.F \in \{A,Z\} \ \wedge\ \mathit{id}.P \notin \mathbf{C}\ \textbf{then}\)
  2. \(\textbf{return}\ \mathtt{now}\)
  3. \(\mathtt{reg}[\mathit{id}.P] \gets 0\)
  4. \(\textbf{return}\ \mathtt{now}\)
id.Update()from id′
  1. \(\textbf{if}\ \mathit{id}'.F \in \{A,Z\} \ \wedge\ \mathit{id}.P \notin \mathbf{C}\ \textbf{then}\)
  2. \(\textbf{return}\ \mathtt{now}\)// reading, not ticking
  3. \(\textbf{if}\ \mathtt{reg}[\mathit{id}.P] = 0\ \textbf{then}\)
  4. \(\textbf{return}\ \mathtt{now}\)// not in the round structure
  5. \(\mathtt{tick}[\mathit{id}.P] \gets 1\)
  6. \(\textbf{if}\ \forall\, P \in \mathcal{G}_{\mathsf{Clock}}.\mathbf{P} \setminus \mathbf{C} \, : \, \mathtt{reg}[P] = 1 \Rightarrow \mathtt{tick}[P] = 1\ \textbf{then}\)
  7. \(\mathtt{now} \gets \mathtt{now} + 1\)
  8. \(\mathtt{tick}[*] \gets 0\)// the round is over
  9. \(\mathcal{A}^{!}\bigl(\mathit{id}.\mathsf{Update},\ \mathtt{now}\bigr)\)// notify; the answer is discarded
  10. \(\textbf{return}\ \mathtt{now}\)
id.Read()from id′
  1. \(\textbf{return}\ \mathtt{now}\)
id.Leak()from id′
  1. \(\textbf{return}\ (\mathtt{now},\ \mathtt{reg},\ \mathtt{tick})\)

The box is transcribed from UC for Gamers (§17.1, p. 159), line numbering and all. Every operation returns \(\mathtt{now}\), reads and mutators alike, and always as it stands on return — so a caller that closed a round sees the counter it just advanced, not the one it entered on.

Register and Deregister are the same operation up to which flags they set: a freshly registered party has its tick cleared (line 6) and so owes a fresh tick, while a departing one is simply dropped from the round structure and leaves no obligation behind. Both open with the outsider test (lines 4 and 8), which downgrades the call to a read.

The round closes in Update, and lines 17–19 are the whole of it. A tick is recorded (line 16); if every currently-honest registered party’s tick is now in, the counter advances by one and every tick clears at once. Two things follow from how line 17 quantifies. Corrupt parties neither hold a round open nor help close one — the test ranges over \(\mathbf{P} \setminus \mathbf{C}\), so their ticks are the adversary’s to give or withhold and count for nothing either way. And until the first honest party registers the test is vacuously true, so time is effectively the adversary’s to spend.

The notification at line 20 fires on every Update that gets that far, not only on the ones that advanced the counter, and its answer is discarded — the clock is telling the adversary something and asking nothing. That it is responsive means the adversary cannot use the notification to run other machinery mid-tick.

Known realizations

A global setup assumption, not itself realized by a lower-level protocol in this framework — it stands in directly for whatever round-synchronization mechanism (network-level timeouts, a blockchain’s own block schedule, etc.) a deployment actually has.

Properties

Both proven with probability exactly \(0\) against every occupant of the adversary slot:

  • Steadiness. The counter only ever moves forward by exactly one, and only at a genuine tick — no read, registration, or departure ever sees it jump, stall backward, or advance on its own.
  • Unanimity. The counter cannot pass a time \(t\) while some honest, still-registered party that joined by \(t\) has not ticked for round \(t\) — a round cannot close early by leaving an honest party behind.

The per-tick adversary notification costs something real: transferring these two properties from the ideal clock to a system built over it needs an argument made directly (the usual “any adversary reduces to a canonical one” shortcut doesn’t apply to a functionality that notifies the slot on every call), which is the price of the clock telling the adversary anything at all.

Formal artifacts

No machine-checked formalization yet.

References: