What each player knows¶
Alba is a game about who knows what. A Thane knows only their own role. The Mirk know each other. The Seer knows who the Mirk are, and must not let it show. And no one ever learns who played which quest card. This chapter shows how the rules give each player their knowledge, and how the project proves that nothing else gets out.
Knowledge by role¶
The rules work out who is on the minions' side:
/-- Seats on the minions' side. -/
def minions (s : State) : List Nat := (List.range s.players).filter fun i => (s.role i).minionSide
It is written inside namespace State in the rules file, so its full name is
State.minions, and you call it with a dot: s.minions. List.range n is
[0, 1, …, n - 1], every seat, and filter keeps those
whose role is on the minions' side. Then each player's knowledge, as a list
of seats they know to be minions:
/-- The seats `i` knows to be on the minions' side: all of them for the
oracle, the others for anyone on that side, none for a servant. -/
def knowledge (s : State) (i : Nat) : List Nat :=
if s.role i = .oracle then s.minions
else if (s.role i).minionSide then s.minions.filter (· != i)
else []
The oracle knows them all. A minion knows the others: (· != i) keeps every
seat that isn't i (!= is not equal, as a Bool). A servant knows no
one. At a table of six:
/-- Six players: the oracle in seat 1, the minion in seat 2, the assassin in seat 3. -/
def six : State := { roles := [.servant, .oracle, .minion, .assassin, .servant, .servant], leader := 0 }
/-- info: [2, 3] -/
#guard_msgs in
#eval six.minions
/-- info: [[], [2, 3], [3], [2], [], []] -/
#guard_msgs in
#eval (List.range 6).map six.knowledge
Two guarantees say the same in general:
/-- **The oracle is shown exactly the minions.** -/
theorem the_oracle_knows_exactly_the_minions {i : Nat} (oracle : s.role i = .oracle) :
s.knowledge i = s.minions := by
simp [State.knowledge, oracle]
/-- **A minion is shown exactly the others on the minions' side.** -/
theorem minions_know_each_other {i : Nat} (minion : (s.role i).minionSide = true) :
s.knowledge i = s.minions.filter (· != i) := by
have notOracle : s.role i ≠ .oracle := by intro h; rw [h] at minion; simp [Role.minionSide] at minion
simp [State.knowledge, notOracle, minion]
In the second, the proof first shows that a minion isn't the oracle
(notOracle), because knowledge asks about the oracle first. intro h
assumes the opposite, rw [h] at minion turns minion into the claim that
the oracle is on the minions' side, and simp sees that it's false.
These say what each player is shown. They don't say that players aren't shown more. That needs a guarantee of a different kind.
What a player is sent¶
A player is sent an observation, built for them:
def observe (s : State) (v : Viewer) : Json :=
let n := s.players
let shared := #[
("players", Json.ofNat n), ("phase", Json.str (phaseName s.phase)),
("leader", Json.ofNat s.leader), ("quest", Json.ofNat s.quest),
("teamSizes", Json.ofList Json.ofNat (teamSizes n)),
("failsNeeded", Json.ofList Json.ofNat ((List.range (teamSizes n).length).map (failsNeeded n))),
("results", Json.ofList Json.bool s.results), ("rejections", Json.ofNat s.rejections),
("team", Json.ofList Json.ofNat s.team), ("ready", Json.ofList Json.ofNat s.ready.reverse),
("voted", Json.ofList Json.ofNat s.voters.reverse),
("played", Json.ofList Json.ofNat s.playedBy.reverse),
("revealed", (s.revealed.map (Json.ofList fun r => Json.str r.id)).getD .null),
("lastVotes", Json.ofList pairJson s.lastVotes)]
match v with
| .player i =>
.obj (shared ++ #[
("role", Json.str (s.role i).id),
("knowsMinions", Json.ofList Json.ofNat (s.knowledge i)),
("yourVote", ((s.votes.lookup i).map Json.bool).getD .null),
("yourCard", ((s.cards.lookup i).map Json.bool).getD .null)])
| .debug =>
.obj (shared ++ #[("roles", Json.ofList (fun r => Json.str r.id) s.roles),
("votes", Json.ofList pairJson s.votes.reverse),
("cards", Json.ofList pairJson s.cards.reverse)])
The shared part is the same for everyone: the phase, the leader, the
results, who has voted and who has played, but not how. Then each player
gets their own role, their knowledge, and their own vote and card. Only the
debug viewer, the all-seeing view used for testing, gets everyone's roles,
votes and cards.
Here is a quest in progress. Seats 1, 2 and 3 are the Band. The assassin and the minion have played, one Fail and one Success, and seat 3 hasn't played yet. In a second game, the two minions played the other way round. Seat 3's view is the same in both; only the debug view tells them apart:
/-- Five players, on the second quest: seats 1, 2 and 3 are the team. The
assassin (seat 1) and the minion (seat 2) have played; seat 3 has not. -/
def questA : State :=
{ roles := [.oracle, .assassin, .minion, .servant, .servant], leader := 1, quest := 1, results := [true],
phase := .questing, team := [1, 2, 3], cards := [(2, true), (1, false)] }
/-- The same, except that the two minions played the other way round. -/
def questB : State := { questA with cards := [(2, false), (1, true)] }
#guard toString (observe questA (.player 3)) == toString (observe questB (.player 3))
#guard toString (observe questA .debug) != toString (observe questB .debug)
Looking the same¶
As with secrecy before, the project states "reveals nothing" as
indistinguishability: two games that differ only in what a player may not
see give that player exactly the same view. What a player may see depends on
who they are, so Alba's LookSame is about one player, i:
/-- Two states agree on everything `i` may see: the public state (including,
once the game is over, every role; whom the assassin named; and the last
revealed votes), `i`'s own
role and knowledge, and `i`'s own vote and card. -/
def LookSame (i : Nat) (s t : State) : Prop :=
s.players = t.players ∧ s.phase = t.phase ∧ s.leader = t.leader ∧ s.quest = t.quest ∧
s.results = t.results ∧ s.rejections = t.rejections ∧ s.team = t.team ∧ s.ready = t.ready ∧
s.voters = t.voters ∧ s.playedBy = t.playedBy ∧ s.revealed = t.revealed ∧ s.accused = t.accused ∧
s.lastVotes = t.lastVotes ∧
s.role i = t.role i ∧ s.knowledge i = t.knowledge i ∧
s.votes.lookup i = t.votes.lookup i ∧ s.cards.lookup i = t.cards.lookup i
The first lines are public: everyone may see them. The last two lines are
i's own: their role, their knowledge, and lookup i, which finds i's
entry in a list of pairs, so their own vote and their own card, if any.
Everything else is missing, and that is what may differ: other players'
roles, how others voted, which cards others played.
The two quests above look the same to seat 3, and not to seat 1, who knows which card they played:
example : Proofs.Alba.LookSame 3 questA questB := by
unfold Proofs.Alba.LookSame; decide
example : ¬ Proofs.Alba.LookSame 1 questA questB := by
unfold Proofs.Alba.LookSame; decide
LookSame is a def, so decide can't see what it says until unfold
replaces it with its body. Then it's a list of facts about two concrete
games, and decide checks them all.
The guarantee¶
/-- **No information leaks: in particular, who played which quest card is never revealed.**
A player's view (their observation and the moves offered to them) depends
only on public information, their own role and what it lets them know, and
their own vote and card. Two games that differ in anything else, such as other
players' roles while the game goes on, how others voted before the reveal, or
which quest cards other team members played, look exactly the same to them. -/
theorem views_reveal_nothing_hidden {i : Nat} {s t : State} (same : LookSame i s t) :
observe s (.player i) = observe t (.player i) ∧ ∀ who, offers who s (.player i) = offers who t (.player i) := by
obtain ⟨players, phase, leader, quest, results, rejections, team, ready, voters, playedBy, revealed, accused,
lastVotes, role, knows, myVote, myCard⟩ := same
constructor
· -- The observation is built from the public fields and the player's own.
simp only [observe, players, phase, leader, quest, results, rejections, team, ready, voters, playedBy,
revealed, lastVotes, role, knows, myVote, myCard]
· -- The offers depend on the same, and on `check`, which does too.
intro who
have checks := check_same ⟨players, phase, leader, quest, results, rejections, team, ready, voters,
playedBy, revealed, accused, lastVotes, role, knows, myVote, myCard⟩
simp only [offers, players, phase, leader, quest, role, checks]
If two games look the same to player i, then i's observation is the
same, and so are the moves offered to them. The proof:
obtaintakessameapart into its facts, one name each.constructorsplits the goal, an∧, into its two halves.simp only [observe, …]unfoldsobserveand rewrites with exactly the facts listed, and no others. Sinceobservereads only those fields, both sides become the same.- The offered moves also depend on
check, so the proof usescheck_same, which sayscheckgives the same answer in two games that look the same:
/-- Whether a move by `i` is legal depends only on what `i` may see. -/
theorem check_same {i : Nat} {s t : State} (same : LookSame i s t) (m : Move) : check s i m = check t i m := by
obtain ⟨players, phase, leader, quest, -, -, team, ready, voters, playedBy, -, -, -, role, -⟩ := same
cases m <;> simp only [check, players, phase, leader, quest, team, ready, voters, playedBy, role]
A theorem is a function, so you can use it on the two quests above. Give it a proof that they look the same to seat 3, and it gives back a proof that seat 3's observations are equal:
theorem seat3_cannot_tell : observe questA (.player 3) = observe questB (.player 3) :=
(Proofs.Alba.views_reveal_nothing_hidden (by unfold Proofs.Alba.LookSame; decide)).1
That covers the observation and the moves. A player is sent more than that, and the whole view is covered too:
/-- **Nothing a player is sent reveals what they may not see.**
Everything in a player's view (the observation, the moves offered, what is
happening, who is awaited, the rules, the outcome, and the events they are
admitted to) is the same in any two games at the same table (the same
players' names) that look the same to them. In particular, while the assassin
chooses, no part of the view says who the assassin is. -/
theorem whole_views_reveal_nothing_hidden {i : Nat} {s t : Engine.Session State}
(same : LookSame i 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 ⟨obs, acts⟩ := views_reveal_nothing_hidden same
exact Proofs.view_is_built_from_its_parts (by simp [Engine.Game.seats, same.1]) names
(fun who => (public_parts_same same who).1) (public_parts_same same Engine.seatName).2.1
(public_parts_same same Engine.seatName).2.2.1 obs acts events (fun who => (public_parts_same same who).2.2.2)
The phase text, who the table is waiting for, the rules and the outcome are
shown to depend only on public facts (public_parts_same). One of them
deserves a look: who the table is waiting for.
/-- Who the table openly waits on. While the assassin chooses, no one is
named: who the assassin is stays secret until they have chosen. -/
def waitingFor (s : State) : List Nat :=
let all := List.range s.players
match s.phase with
| .proposing => [s.leader]
| .discussing | .deliberating => all.filter (· ∉ s.ready)
| .voting => all.filter (· ∉ s.voters)
| .questing => s.team.filter (· ∉ s.playedBy)
| .assassinating | .finished _ => []
While the assassin chooses, the table waits for no one, because naming the
player it waited for would name the assassin. Try changing that line so
the table waits for the assassin's seat while they choose: make test still
passes, but make proofs fails in public_parts_same, the lemma
whole_views_reveal_nothing_hidden is built on. Two games that look the
same to a servant can have their assassins in different seats, so their
views would differ.
Who played which card¶
The guarantee's doc comment singles out quest cards, and for good reason. Without that secret, Alba wouldn't be a game: a Fail would point straight at a Conspirator. Look at what happens to the two quests above when seat 3 plays the last card:
def finishQuest (s : State) : State × List Event :=
match step s 3 (.play true) with
| .ok r => r
| .error _ => (s, [])
/-- info: [Games.Alba.Event.cardPlayed 3, Games.Alba.Event.questDone 1 1 false] -/
#guard_msgs in
#eval (finishQuest questA).2
#guard finishQuest questA == finishQuest questB
The events are the same: seat 3 played, and the quest failed with one Fail.
And the two whole games are now equal: resolveQuest records only the
result, and starting the next proposal empties cards. Once a quest is
over, not even the game remembers who played what.
That is one table. Two guarantees prove it for every table. The first is about the play itself: two plays that leave the same cards on the table, played by the same players, announce exactly the same events, whichever card each player played, including the card being played now.
/-- **Playing a quest card announces that it was played, never which card it was.**
Take two plays by the same player, on two tables that are the same except for
which player played which of the quest cards: the same players have played,
and the same cards are on the table once this one is down, whichever card
this player and each of the others played. If both are accepted, they
announce exactly the same events: that the card was played, and, when it is
the last, the quest's result with only its number of fails. -/
theorem playing_a_quest_card_reveals_no_card (u : State) (cs ct : List (Nat × Bool)) (a : Nat) (b b' : Bool)
(samePlayers : cs.map (·.1) = ct.map (·.1))
(sameCards : (((a, b) :: cs).map (·.2)).Perm (((a, b') :: ct).map (·.2)))
{s t : State} {e f : List Event}
(first : step { u with cards := cs } a (.play b) = .ok (s, e))
(second : step { u with cards := ct } a (.play b') = .ok (t, f)) : e = f := by
-- What each play announces is the same...
have announced := apply_play_events_ignore_which_card u cs ct a b b' samePlayers sameCards
-- ...and an accepted play announces exactly that.
rw [(accepted_step first).2.2.2, (accepted_step second).2.2.2]
exact announced
The second is about every move after it: in two games that differ only in who played which card, any move is accepted or refused alike, and announces the same events.
/-- **Later moves never reveal who played which quest card either.**
In two games that are the same except for which player played which of the
quest cards on the table (the same players have played, and the same cards
are there), every move is accepted or refused alike, and announces exactly the
same events. With `playing_a_quest_card_reveals_no_card` for the plays
themselves, and `views_reveal_nothing_hidden` for the rest of a player's view,
who played which card is never revealed. -/
theorem later_moves_reveal_no_card (u : State) (cs ct : List (Nat × Bool))
(samePlayers : cs.map (·.1) = ct.map (·.1)) (sameCards : (cs.map (·.2)).Perm (ct.map (·.2)))
(a : Nat) (m : Move) :
(step { u with cards := cs } a m).map (·.2) = (step { u with cards := ct } a m).map (·.2) := by
-- Whether the move is allowed never looks at which card anyone played...
have allowed := check_ignores_which_card u samePlayers a m
-- ...and what it announces never does either.
have announced := apply_events_ignore_which_card u cs ct samePlayers sameCards a m
-- Both games are in the same phase, the only other thing `step` looks at.
have samePhase : ({ u with cards := cs } : State).phase = ({ u with cards := ct } : State).phase := rfl
generalize ({ u with cards := cs } : State) = s at *
generalize ({ u with cards := ct } : State) = t at *
-- So both are refused alike, or both are accepted with the same events.
unfold step
rw [samePhase, allowed]
cases t.phase <;> cases check t a m <;> simp [Except.map, announced]
whole_views_reveal_nothing_hidden takes the events as given, and these two
are what make that safe for quest cards. The statements take two lists of
cards, cs and ct, and ask for the same players (samePlayers, the first
of each pair) and the same cards in any order (sameCards, a permutation of
the second of each pair). That is exactly "the same except for who played
which card".
The oracle's secret¶
The assassin's job at the end is to find the oracle. Do the minions' views give the oracle away? Swap the oracle with a servant, and the minions can't tell:
/-- `six` with the oracle and a servant swapped. -/
def sixSwapped : State := { six with roles := [.oracle, .servant, .minion, .assassin, .servant, .servant] }
example : Proofs.Alba.LookSame 2 six sixSwapped := by
unfold Proofs.Alba.LookSame; decide
example : Proofs.Alba.LookSame 3 six sixSwapped := by
unfold Proofs.Alba.LookSame; decide
Their knowledge is the list of minions, which hasn't changed, and the
oracle's role isn't theirs to see. So by views_reveal_nothing_hidden, no
minion's view can tell the oracle from a servant. If the assassin finds the
oracle, it's from how the oracle played, not from anything the engine said.
The reveal¶
When the game is over, everyone turns their card over:
/-- Every role, face up, once the game is over (as at the real table); nothing
while it goes on. -/
def revealed (s : State) : Option (List Role) :=
match s.phase with
| .finished _ => some s.roles
| _ => none
revealed is one of the public facts in LookSame, so once the game is
over, two games that look the same to a player have the same roles. Before
the end, it's none in every game, so it reveals nothing:
/-- **When the game is over, everyone sees every role; until then, no one does.**
Every player's view carries the full list of roles exactly when the game has
finished, as when everyone turns their card over at the end. -/
theorem every_role_is_revealed_at_the_end (s : State) :
(∀ w, s.phase = .finished w → s.revealed = some s.roles) ∧
(∀ p, (∀ w, p ≠ .finished w) → s.phase = p → s.revealed = none) := by
constructor
· intro w finished; simp [State.revealed, finished]
· intro p going current
subst current
unfold State.revealed
split
· rename_i w finished; exact absurd finished (going w)
· rfl
Exercises¶
- At the table
six, swap the minion in seat 2 with the servant in seat 4. Show that the swapped game looks the same to the servant in seat 0, but not to the oracle in seat 1. Why not to the oracle? - Prove that a servant knows no one: if
s.role i = .servant, thens.knowledge i = []. - In
Games/Alba/Game.lean, makeobserveleak the quest cards: add("cards", Json.ofList pairJson s.cards.reverse)to thesharedpart. Runmake proofs. What fails? Then put it back withgit restore Games/Alba/Game.lean.
Solution
-
The oracle's knowledge lists the minions, and the minions have moved, so
knowledge 1differs:/-- `six` with the minion and a servant swapped. The servants can't tell. -/ def sixOtherMinion : State := { six with roles := [.servant, .oracle, .servant, .assassin, .minion, .servant] } example : Proofs.Alba.LookSame 0 six sixOtherMinion := by unfold Proofs.Alba.LookSame; decide example : ¬ Proofs.Alba.LookSame 1 six sixOtherMinion := by unfold Proofs.Alba.LookSame; decide #guard toString (observe six (.player 0)) == toString (observe sixOtherMinion (.player 0)) -
One
simpdoes it:/-- A servant knows no one on the minions' side. -/ theorem servants_know_nothing {s : State} {i : Nat} (servant : s.role i = .servant) : s.knowledge i = [] := by simp [State.knowledge, servant, Role.minionSide]simpunfoldsknowledge, usesservantto work out the role, andRole.minionSideto see that a servant isn't on the minions' side. -
The proof of
views_reveal_nothing_hiddenfails, at thesimp onlyfor the observation:LookSamedoesn't includes.cards, so nothing letssimpshow the two observations are equal. No proof could, since the statement is now false.make teststill passes: no test looks for acardsfield in a player's view, and no test could look for every possible leak. The engine's views and the proof are tied together: changing what a player is sent means changing what the guarantee promises.