A table¶
A game's state is not all a table needs. It also needs the moves made so far, the events each player may read, the players' names and the keys that open each seat. None of that belongs to any game's rules, so the engine keeps it, once, for every game, in a session.
The session¶
structure Session (σ : Type) where
config : Json
state : σ
/-- Accepted actions as `{actor, action}`, in order. -/
log : Array Json := #[]
/-- Events emitted by accepted actions, in order, with their audience. -/
events : Array (Audience × Json) := #[]
/-- Which game this is at the table: 1, then 2 after a rematch, and so on. -/
games : Nat := 1
/-- The table's keys, once locked (`lock`). Until then no request opens it. -/
keys : Option Keys := none
/-- What the players are called, seat by seat (from the config's "names"). -/
names : List String := []
deriving Inhabited
Session σ is a session of the game whose state is σ: Session
Games.Snap.State is a Snap table, Session Games.Alba.State an Alba one.
Around the game's state it keeps:
config, the JSON the table was started from, andlog, every accepted move with who made it. With the two, the whole game can be replayed, because the deal comes from the config's seed.events, every event so far, each tagged with itsAudience: who may see it.keys, once the table is locked, andnames, the players' names.
Array is like List, but stored in one block of memory, so adding to the
end and reading by position are fast. #[] is the empty array.
A session is started from a config. The engine asks the game to init, and
checks the names itself: one per seat, none empty, all different.
/-- A config: the seed for the deal, and the players' names. -/
def config : Json := .obj #[("seed", 3), ("names", .arr #["Ada", "Brian"])]
/-- A Snap table, started from that config. -/
def table : Session Games.Snap.State :=
match Session.start config with
| .ok s => s
| .error _ => default
/-- info: ["Ada", "Brian"] -/
#guard_msgs in
#eval table.names
/-- info: "config 'names': every name must be different" -/
#guard_msgs in
#eval match Session.start (σ := Games.Snap.State) (.obj #[("names", .arr #["Ada", "Ada"])]) with
| .ok _ => "started"
| .error e => e
The match handles a failed start; this one can't fail, so it never
reaches default (a session with every field at its default, which
deriving Inhabited provides).
nameOf turns the list of names into a Names function, falling back to
seatName for a seat with no name:
/-- What seat `i`'s player is called. -/
def nameOf (s : Session σ) : Names := fun i => s.names.getD i (seatName i)
s.names.getD i (seatName i) reads position i of the list, or gives the
default if there is none.
What a player is sent¶
/-- What `v` sees: the same shape for every game. Refused for a seat that
does not exist. -/
def view (s : Session σ) (v : Viewer) : Except String Json :=
if !s.admits v then .error s!"no such seat (the game has {Game.seats s.state})" else
.ok <| .obj #[
("game", Game.name σ),
("seats", Json.ofNat (Game.seats s.state)),
("names", Json.ofList Json.str s.names),
("you", match v with | .player i => Json.ofNat i | .debug => .null),
("phase", (Game.phase s.nameOf s.state).toJson),
("waitingFor", Json.ofList Json.ofNat (Game.waitingFor s.state)),
("catalogue", Game.catalogue s.state),
("observation", Game.observe s.state v),
("actions", .arr (Game.actions s.nameOf s.state v |>.map ActionSpec.toJson).toArray),
("events", .arr (visible s.events v)),
("outcome", (s.outcome.map Outcome.toJson).getD .null)]
Apart from the replies to their own moves, this is all a player is ever
sent about a game, and it has the same shape for every game. Each part is the game's answer to one of the
class's questions, asked with the table's names: the phase, who is awaited,
the catalogue, the observation for this viewer, the moves offered to them,
the events they may see and the outcome. visible keeps only the events
whose audience admits the viewer.
A view for a seat the game doesn't have is refused:
/-- info: {"id":"playing","title":"Play","text":"Ada to flip. Call snap whenever the two face-up cards match."} -/
#guard_msgs in
#eval match table.view (.player 0) with
| .ok j => IO.println ((j.get? "phase").getD .null)
| .error e => IO.println e
/-- info: no such seat (the game has 2) -/
#guard_msgs in
#eval match table.view (.player 2) with
| .ok j => IO.println j
| .error e => IO.println e
IO.println prints a value as text: for Json, the JSON the browser would
receive.
Making a move¶
/-- Apply one client action. On rejection the session is returned unchanged. -/
def submit (s : Session σ) (actor : Nat) (action : Json) : Session σ × Json :=
if actor ≥ Game.seats s.state then (s, refusal "seat" "no such seat") else
match (Game.decodeAction (σ := σ) action) with
| .error e => (s, refusal "malformed" s!"malformed action: {e}")
| .ok a =>
match Game.step s.state actor a with
| .error r => (s, refusal "illegal" r.reason)
| .ok (state', evs) =>
let evs := (evs.zipIdx.map fun (e, k) =>
(Game.audience (σ := σ) e, eventJson (σ := σ) s.nameOf (s.events.size + k) e)).toArray
let mine := visible evs (.player actor)
({ s with state := state'
log := s.log.push (.obj #[("actor", Json.ofNat actor), ("action", action)])
events := s.events ++ evs },
.obj #[("ok", true), ("events", .arr mine)])
A move arrives as JSON from a seat number. submit checks, in order:
- that the seat exists (code
seat), - that the JSON is a move of this game, using the game's
decodeAction(codemalformed), - that the rules allow it, using the game's
step(codeillegal).
Only then does it build the new session, with { s with … }: the new
state, the move added to the log, and the new events added to the history.
Each event is numbered (seq), given its plain-words text, and tagged with
its audience. The reply to the mover contains only the new events they may
see.
def flipMove : Json := .obj #[("id", "flip")]
/-- info: {"ok":false,"code":"seat","reason":"no such seat"} -/
#guard_msgs in
#eval IO.println (table.submit 7 flipMove).2
/-- info: {"ok":false,"code":"malformed","reason":"malformed action: unknown action 'jump'"} -/
#guard_msgs in
#eval IO.println (table.submit 0 (.obj #[("id", "jump")])).2
/-- info: {"ok":false,"code":"illegal","reason":"not your turn"} -/
#guard_msgs in
#eval IO.println (table.submit 1 flipMove).2
/-- info: {"ok":true,"events":[{"seq":0,"text":"Ada turned A♥","type":"flipped","player":0,"card":{"rank":1,"suit":"H","label":"A♥","red":true}}]} -/
#guard_msgs in
#eval IO.println (table.submit 0 flipMove).2
/-- info: #[{"actor":0,"action":{"id":"flip"}}] -/
#guard_msgs in
#eval IO.println (table.submit 0 flipMove).1.log
Rejection changes nothing¶
Look at the three refusals in submit: each gives back s, the session it
was given. The engine proves that, for every game:
/-- **A rejected action changes nothing.**
If the action decodes but the game's rules refuse it, the session is returned
exactly as it was: no state change, no log entry, no events. -/
theorem rejected_action_changes_nothing (s : Session σ) (actor : Nat) (sent : Json)
{act : Game.Action σ} {why : Rejection}
(decoded : Game.decodeAction (σ := σ) sent = .ok act)
(refused : Game.step s.state actor act = .error why) :
(s.submit actor sent).1 = s := by
-- The rules' refusal is passed straight back with the original session.
simp only [Session.submit, decoded, refused]
split <;> rfl
Game.decodeAction (σ := σ) sent = .ok act names the hypothesis that the
move decodes, and refused the hypothesis that the rules refuse it. The
conclusion, (s.submit actor sent).1 = s, is about the whole session: not
only the state, but the log, the events and the keys. .1 is the first
half of the pair submit returns. The proof unfolds submit, rewrites
with the two hypotheses, and what is left is s = s in every branch.
Its companions say the same for a malformed move and for a seat that doesn't exist:
/-- **A malformed action changes nothing.**
If the engine cannot even decode what a client sent, the session is returned
exactly as it was. -/
theorem malformed_action_changes_nothing (s : Session σ) (actor : Nat) (sent : Json) {why : String}
(malformed : Game.decodeAction (σ := σ) sent = .error why) :
(s.submit actor sent).1 = s := by
-- `submit` checks the seat and decodes first, and rejects before touching the session.
simp only [Session.submit, malformed]
split <;> rfl
These theorems know nothing about any game: σ could be any type with a
Game instance. So each game gets them for nothing. A game's own theorems
say when its rules refuse a move; the engine's say what a refusal does to
the table. Put together, they say something about one game's tables, as the
exercises show.
Names are only labels¶
Rename the players and make the same move. The words differ:
/-- The same table, with its players called something else. -/
def renamed : Session Games.Snap.State := { table with names := ["Cat", "Dan"] }
/-- info: {"ok":true,"events":[{"seq":0,"text":"Cat turned A♥","type":"flipped","player":0,"card":{"rank":1,"suit":"H","label":"A♥","red":true}}]} -/
#guard_msgs in
#eval IO.println (renamed.submit 0 flipMove).2
#guard toString (renamed.submit 0 flipMove).1.log == toString (table.submit 0 flipMove).1.log
but the #guard shows the log is the same. The engine proves this for every
move, at every table, of every game:
/-- **Names are only labels: renaming the players changes nothing in the game.**
A move has the same effect on the game, and is logged the same, whatever the
players are called; only the words of the events differ. -/
theorem names_change_nothing_in_the_game (s : Session σ) (ns : List String) (actor : Nat) (sent : Json) :
({ s with names := ns }.submit actor sent).1.state = (s.submit actor sent).1.state ∧
({ s with names := ns }.submit actor sent).1.log = (s.submit actor sent).1.log := by
unfold Session.submit
dsimp only
split
· exact ⟨rfl, rfl⟩
· split
· exact ⟨rfl, rfl⟩
· split
· exact ⟨rfl, rfl⟩
· exact ⟨rfl, rfl⟩
{ s with names := ns } is the same session with other names. The proof
unfolds submit and follows each if and match with split; in every
branch the state and the log are built from the same things, so rfl
closes each, and exact ⟨rfl, rfl⟩ proves both halves of the ∧.
(dsimp only makes the small simplifications that need no lemmas, such as
reading the names field of { s with names := ns }.)
Keys¶
Anyone who can reach a server can send it a request. So a table is locked with keys: one secret per seat, and one for the owner, which opens the all-seeing debug view. The hosts make the keys and hand each player only their own.
/-- The secrets that open a table: one per seat, and the owner's (which opens
the all-seeing view). Hosts make them, from a secure random source, and hand
each player only their own; the engine checks every request against them. -/
structure Keys where
seats : List String
owner : String
deriving Inhabited, Repr
/-- Lock a session with its keys: exactly one per seat, none empty, all
different (the owner's too), so no key can open two places. -/
def lock (s : Session σ) (k : Keys) : Except String (Session σ) :=
if k.seats.length ≠ Game.seats s.state then .error "keys: one key per seat is needed"
else if (k.owner :: k.seats).any (·.isEmpty) then .error "keys: a key must not be empty"
else if !(k.owner :: k.seats).Nodup then .error "keys: every key must be different"
else .ok { s with keys := some k }
lock refuses keys that are missing, empty or repeated. Nodup says a
list has no duplicates. opens says whether a key opens a place, and
viewAs and submitAs check it before doing anything:
/-- Does `key` open viewer `v`'s place: a seat with that seat's key, the
all-seeing view with the owner's? An unlocked session opens to no one. -/
def opens (s : Session σ) (v : Viewer) (key : String) : Bool :=
match s.keys, v with
| some k, .player i => k.seats[i]? == some key
| some k, .debug => k.owner == key
| none, _ => false
/-- A move, made only with the actor's own seat's key. -/
def submitAs (s : Session σ) (actor : Nat) (key : String) (action : Json) : Session σ × Json :=
if s.opens (.player actor) key then s.submit actor action
else (s, refusal "key" "this seat's key is needed")
k.seats[i]? reads position i of the list, or none if there is none,
so a seat beyond the end is opened by nothing. Here is a table locked with
keys, and Brian's key tried on Ada's seat:
def keys : Keys := { seats := ["ada-secret", "brian-secret"], owner := "owner-secret" }
def locked : Session Games.Snap.State :=
match table.lock keys with
| .ok s => s
| .error _ => default
/-- info: key: this place's key is needed -/
#guard_msgs in
#eval match locked.viewAs (.player 0) "brian-secret" with
| .ok j => IO.println j
| .error e => IO.println e
/-- info: {"ok":false,"code":"key","reason":"this seat's key is needed"} -/
#guard_msgs in
#eval IO.println (locked.submitAs 0 "brian-secret" flipMove).2
/-- info: keys: every key must be different -/
#guard_msgs in
#eval match table.lock { keys with owner := "ada-secret" } with
| .ok _ => IO.println "locked"
| .error e => IO.println e
The proofs say what this means for every game. Only a seat's own key opens its view:
/-- **A seat's view goes only to whoever holds that seat's key.** -/
theorem only_the_seats_key_opens_its_view (s : Session σ) (i : Nat) (key : String) (j : Json)
(shown : s.viewAs (.player i) key = .ok j) :
∃ k, s.keys = some k ∧ k.seats[i]? = some key := by
unfold Session.viewAs at shown
cases locked : s.keys with
| none => simp [Session.opens, locked] at shown
| some k =>
by_cases opened : s.opens (.player i) key
· simp only [Session.opens, locked, beq_iff_eq] at opened
exact ⟨k, rfl, opened⟩
· simp [opened] at shown
No key opens two seats:
omit [Game σ] in
/-- **No key opens two seats.**
On a locked table every key is different, so whatever opens seat `i` and
seat `j` shows that `i` and `j` are the same seat. -/
theorem no_key_opens_two_seats (s : Session σ) (k : Keys) (locked : s.keys = some k)
(distinct : (k.owner :: k.seats).Nodup) {i j : Nat} {key : String}
(opensI : s.opens (.player i) key) (opensJ : s.opens (.player j) key) : i = j := by
simp only [Session.opens, locked, beq_iff_eq] at opensI opensJ
have nodup : k.seats.Nodup := (List.nodup_cons.mp distinct).2
obtain ⟨hi, -⟩ := List.getElem?_eq_some_iff.mp opensI
exact nodup.eq_of_getElem?_eq hi (opensI.trans opensJ.symm)
omit [Game σ] in tells Lean that this theorem doesn't need the Game
instance that the variable line would otherwise add: keys are the same
whatever the game. The proof takes apart what opens says for each seat,
k.seats[i]? = some key and k.seats[j]? = some key, and uses the fact
that a list with no duplicates has each value at one position only.
And a move without the mover's key changes nothing:
/-- **A move made without the actor's own seat's key changes nothing.** -/
theorem a_move_without_the_key_changes_nothing (s : Session σ) (actor : Nat) (key : String) (sent : Json)
(shut : s.opens (.player actor) key = false) :
(s.submitAs actor key sent).1 = s := by
simp [Session.submitAs, shut]
Secrecy, for every game¶
In Snap's chapter on secrecy, the proof that a view reveals nothing hidden started with a lemma from the engine. Here it is:
/-- A view is built from nothing but its parts: the seat count and the
players' names, the phase, who is awaited, the catalogue, the viewer's
observation and offers, the events they are admitted to, and the outcome. Two
sessions that agree on those (the worded parts for any names) give the viewer
exactly the same view. (Each game's secrecy guarantee uses this to cover
everything a player is sent.) -/
theorem view_is_built_from_its_parts {σ : Type} [Engine.Game σ] {s t : Engine.Session σ} {v : Engine.Viewer}
(seats : Engine.Game.seats s.state = Engine.Game.seats t.state) (names : s.names = t.names)
(phase : ∀ who, Engine.Game.phase who s.state = Engine.Game.phase who t.state)
(waiting : Engine.Game.waitingFor s.state = Engine.Game.waitingFor t.state)
(catalogue : Engine.Game.catalogue s.state = Engine.Game.catalogue t.state)
(observe : Engine.Game.observe s.state v = Engine.Game.observe t.state v)
(actions : ∀ who, Engine.Game.actions who s.state v = Engine.Game.actions who t.state v)
(events : Engine.Session.visible s.events v = Engine.Session.visible t.events v)
(outcome : ∀ who, Engine.Game.outcome who s.state = Engine.Game.outcome who t.state) :
s.view v = t.view v := by
have named : s.nameOf = t.nameOf := by funext i; simp [Engine.Session.nameOf, names]
cases v <;>
simp only [Engine.Session.view, Engine.Session.admits, Engine.Session.outcome, seats, names, named, phase,
waiting, catalogue, observe, actions, events, outcome] <;>
rfl
It says: if two sessions agree on every part view is built from, the
viewer's views of them are equal. It is the one place where the shape of a
view is taken apart, so a game's secrecy proof never needs to look at it.
Each game supplies only its own part: that its phase, its observation, its
offers and its outcome are the same for two games that look the same to the
player. Snap, Lol and Alba each do this for their own secrets, with their
own LookSame.
∀ who in the hypotheses matters. The worded parts must agree for any
names, not only the table's, which is part of why secrecy holds whatever the
players are called.
Exercises¶
- On the locked table above, make Ada's first flip with her own key. What is the reply?
- Prove that a table that hasn't been locked opens to no one, in any game.
(Hint:
simp, told aboutSession.opensand your hypothesis.) - Prove that a finished Snap table ignores every move it can decode, by
putting together Snap's
finished_game_rejects_everythingand the engine'srejected_action_changes_nothing. (Hint:obtainthe reason from the first, thenexactthe second.)
Solution
/-- info: {"ok":true,"events":[{"seq":0,"text":"Ada turned A♥","type":"flipped","player":0,"card":{"rank":1,"suit":"H","label":"A♥","red":true}}]} -/
#guard_msgs in
#eval IO.println (locked.submitAs 0 "ada-secret" flipMove).2
/-- A table that has not been locked opens to no one, in any game. -/
theorem unlocked_opens_to_no_one {σ : Type} [Game σ] (s : Session σ) (v : Viewer) (key : String)
(unlocked : s.keys = none) : s.opens v key = false := by
simp [Session.opens, unlocked]
open Games.Snap in
/-- A finished Snap table ignores every move it can decode. -/
theorem finished_table_changes_nothing (s : Session State) (actor : Nat) (sent : Json) (act : Action)
{w : Option (Fin 2)} (decoded : Game.decodeAction (σ := State) sent = .ok act)
(over : s.state.phase = .finished w) :
(s.submit actor sent).1 = s := by
obtain ⟨why, refused⟩ := Proofs.Snap.finished_game_rejects_everything over actor act
exact Proofs.Engine.rejected_action_changes_nothing s actor sent decoded refused
The third is the pattern for every game: the game proves when its rules
refuse, and the engine proves what refusing does. Lean accepts
refused, a fact about Snap's step, where the engine's theorem wants
one about Game.step, because the instance says step := step, and
Lean sees that the two are the same.