What players can't see¶
In a card game, what you can't see matters as much as what you can. In Snap, nobody may know the order of the face-down cards, or the face-up cards buried under the top one. This chapter shows how the project proves that the engine never tells them.
What a player is sent¶
The engine never sends a player the state of the game. It sends a view, built for that player. Here is how Snap shows a hand:
def handJson (h : Hand) (reveal : Bool) : Json :=
let base := #[("down", Json.ofNat h.down.length), ("up", Json.ofNat h.up.length),
("top", (h.up.head?.map Card.toJson).getD .null)]
if reveal then
.obj (base ++ #[("downCards", Json.ofList Card.toJson h.down),
("upCards", Json.ofList Card.toJson h.up)])
else .obj base
Json is the engine's own type for JSON data, the format browsers read.
Unless reveal is set, a hand shows only how many cards are in each pile,
and the top face-up card. The observation of the whole table uses it:
def observe (s : State) (v : Viewer) : Json :=
.obj #[
("hands", .arr #[handJson s.hand0 (v == .debug), handJson s.hand1 (v == .debug)]),
("turn", finToJson s.turn),
("flips", Json.ofNat s.flips),
("maxFlips", Json.ofNat s.maxFlips)]
Only the debug viewer, the all-seeing view used for testing, gets the hidden
cards. Here are two games that differ only in the order of the second
player's face-down cards. Player 0's view of them is identical, and only the
debug view tells them apart:
/-- Two games that differ only in the order of player 1's face-down cards. -/
def gameA : State :=
{ hand0 := { down := [⟨3, 0⟩], up := [⟨9, 1⟩] }, hand1 := { down := [⟨1, 0⟩, ⟨13, 3⟩] }, maxFlips := 10 }
def gameB : State :=
{ gameA with hand1 := { down := [⟨13, 3⟩, ⟨1, 0⟩] } }
/-- info: {"hands":[{"down":1,"up":1,"top":{"rank":9,"suit":"H","label":"9♥","red":true}},{"down":2,"up":0,"top":null}],"turn":0,"flips":0,"maxFlips":10} -/
#guard_msgs in
#eval IO.println (observe gameA (.player 0))
#guard toString (observe gameA (.player 0)) == toString (observe gameB (.player 0))
#guard toString (observe gameA .debug) != toString (observe gameB .debug)
Saying "reveals nothing"¶
How do you state that a view reveals nothing hidden? Not by listing what's in it: that's easy to get wrong, and says nothing about the events, the offered moves, or the words on screen. Instead, the project states it as indistinguishability: if two games differ only in hidden things, the player gets exactly the same view of both. Then nothing the player is sent can depend on the hidden things, because changing them changes nothing.
First, what a player may see of a hand:
/-- What a player may see of a hand: how many cards are face down and face
up, and the top face-up card. -/
def HandLooksSame (h k : Hand) : Prop :=
h.down.length = k.down.length ∧ h.up.length = k.up.length ∧ h.up.head? = k.up.head?
and of a whole game:
/-- Two games look the same to the players when they agree on everything
public: what can be seen of each hand, whose turn it is, the flips made and
allowed, and whether the game is over. They may differ in the order of the
face-down cards and in the face-up cards below the top. -/
def LookSame (s t : State) : Prop :=
HandLooksSame s.hand0 t.hand0 ∧ HandLooksSame s.hand1 t.hand1 ∧ s.turn = t.turn ∧ s.flips = t.flips ∧
s.maxFlips = t.maxFlips ∧ s.phase = t.phase
∧ is and. Two games "look the same" when every public fact agrees. The
two games above do, and the proof is a list of rfls, one for each public
fact:
example : Proofs.Snap.LookSame gameA gameB := by
refine ⟨⟨rfl, rfl, rfl⟩, ⟨rfl, rfl, rfl⟩, rfl, rfl, rfl, rfl⟩
refine gives the shape of the proof, with the anonymous-constructor
brackets matching the ∧s, and fills every piece.
The guarantee¶
/-- **Nothing a player is sent reveals a face-down card.**
Everything in a player's view (the observation, the moves offered, what is
happening, who is awaited, the rules, the outcome, and the events) is the
same in any two games at the same table (the same players' names) that differ
only in the order of face-down cards (and the face-up cards beneath the top). -/
theorem whole_views_reveal_nothing_hidden {i : Nat} {s t : Engine.Session State} (same : LookSame s.state t.state)
(names : s.names = t.names)
(events : Engine.Session.visible s.events (.player i) = Engine.Session.visible t.events (.player i)) :
s.view (.player i) = t.view (.player i) := by
obtain ⟨⟨d0, u0, top0⟩, ⟨d1, u1, top1⟩, turn, flips, cap, ph⟩ := same
have hands : ∀ (h k : Hand), h.down.length = k.down.length → h.up.length = k.up.length →
h.up.head? = k.up.head? → handJson h false = handJson k false := by
intro h k d u top; simp [handJson, d, u, top]
have ends : ∀ who, outcome who s.state = outcome who t.state := by
intro who; unfold outcome; rw [ph]; split <;> simp [cap]
apply Proofs.view_is_built_from_its_parts (s := s) (t := t) (show (2 : Nat) = 2 from rfl) names
· intro who
show phase who s.state = phase who t.state
unfold phase; rw [ph, ends]; simp [turn]
· show waitingFor s.state = waitingFor t.state
unfold waitingFor; rw [ph, turn]
· show catalogue s.state = catalogue t.state
simp [catalogue, cap]
· show observe s.state (.player i) = observe t.state (.player i)
have notDebug : (Engine.Viewer.player i == Engine.Viewer.debug) = false := rfl
simp [observe, notDebug, hands _ _ d0 u0 top0, hands _ _ d1 u1 top1, turn, flips, cap]
· intro _
show actions s.state (.player i) = actions t.state (.player i)
simp [actions, ph, turn]
· exact events
· exact ends
It covers the whole view: everything the engine sends, not only the
observation. It says: take two sessions (a game, with its players' names and
its history of events) whose games look the same, with the same names, and
whose events visible to player i are the same. Then player i's complete
views of them are equal.
The proof uses a lemma from the engine, view_is_built_from_its_parts, which
says a view is built only from its parts: the phase, who the table is waiting
for, the catalogue, the observation, the offered moves, the events and the
outcome. Each · then shows that one part is the same in both games, mostly
by unfolding its definition and using the matching piece of LookSame.
This is how the project handles secrecy for every game. Lol and Alba each
have their own LookSame, with their own secrets, and the same kind of proof.
Why this kind of proof is worth having¶
A test can check that a view doesn't contain a particular card. It can't check that the view doesn't depend on the card in some indirect way: a count that changes, a word that differs, an event that's missing. The indistinguishability proof rules all of those out at once, because it is about the whole view, and about every pair of games.
Exercise¶
Find out what the guarantee really protects. In Games/Snap/Game.lean, make
observe leak something: for example, give player views the downCards
too, by passing true to handJson for both hands. Run make proofs. Which
part of the proof of whole_views_reveal_nothing_hidden fails? Then put it
back.
Answer
The bullet that shows the observations are equal fails: with the face-down cards in the view, two games that look the same to a player can now give different views, so the statement is false and no proof could succeed. The engine's views and the proof are tied together: changing what a player is sent means changing what the proof promises.