Practical Security: The Mafia game¶
Let’s look a bit deeper at Monte, working up to an implementation of the Mafia party game.
Objects¶
Monte has a simpler approach to object composition and inheritance than many other object-based and object-oriented languages.
A Singleton Object¶
We will start our exploration of objects with a simple singleton
object. Methods can be attached to objects with the to
keyword:
>>> object origin:
... to getX():
... return 0
... to getY():
... return 0
... # Now invoke the methods
... origin.getY()
0
Unlike Java or Python, Monte objects are not constructed from classes. Unlike JavaScript, Monte objects are not constructed from prototypes. As a result, it might not be obvious at first how to build multiple objects which are similar in behavior.
Functions are objects too¶
Functions are simply objects with a run
method. There is no
difference between this function:
>>> def square(x):
... return x * x
... square.run(4)
16
... and this object:
>>> object square:
... to run(x):
... return x * x
... square(4)
16
Warning
Python programmers beware, methods are not functions. Methods are just the public hooks to the object that receive messages; functions are standalone objects.
Todo
document docstrings
Todo
document named args, defaults
Object constructors and encapsulation¶
Monte has a very simple idiom for class-like constructs:
>>> def makeCounter(var value :Int):
... return object counter:
... to increment() :Int:
... return value += 1
... to makeOffsetCounter(delta :Int):
... return makeCounter(value + delta)
...
... def c1 := makeCounter(1)
... c1.increment()
... def c2 := c1.makeOffsetCounter(10)
... c1.increment()
... c2.increment()
... [c1.increment(), c2.increment()]
[4, 14]
And that’s it. No declarations of object contents or special
references to this
or self
.
Inside the function makeCounter
, we simply define an object called
counter
and return it. Each time we call makeCounter()
, we get
a new counter object. As demonstrated by the makeOffsetCounter
method, the function (makeCounter
) can be referenced from within
its own body. (Similarly, our counter object could refer to itself in
any of its methods as counter
.)
The lack of a this
or self
keyword may be
surprising. But this straightforward use of lexical scoping saves us
the often tedious business in python or Java of copying the arguments
from the parameter list into instance variables: value
is already
an instance variable.
The value
passed into the function is not an ephemeral parameter
that goes out of existence when the function exits. Rather, it is a
true variable, and it persists as long as any of the objects that uses
it persist. Since the counter uses this variable, value
will exist
as long as the counter exists.
A natural result is the complete encapsulation required for object
capability discipline: value
is not visible outside of
makeCounter()
; this means that no other object can directly observe nor
modify it. Monte objects have no public attributes or fields or even a notion
of public and private. Instead, all names are private: if a name is not
visible (i.e. in scope), there is no way to use it.
We refer to an object-making function such as makeCounter
as a
“Maker”. As a more serious example, let’s make a sketch of our game:
>>> def makeMafia(var players :Set):
... def mafiosoCount :Int := players.size() // 3
... var mafiosos :Set := players.slice(0, mafiosoCount)
... var innocents :Set := players.slice(mafiosoCount)
...
... return object mafia:
... to getWinner():
... if (mafiosos.size() == 0):
... return "village"
... if (mafiosos.size() >= innocents.size()):
... return "mafia"
... return null
...
... to lynch(victim):
... players without= (victim)
... mafiosos without= (victim)
... innocents without= (victim)
...
... def game1 := makeMafia(["Alice", "Bob", "Charlie"].asSet())
... game1.lynch("Bob")
... game1.lynch("Charlie")
... game1.getWinner()
"mafia"
Traditional Datatypes and Operators¶
Monte includes basic data types such as Int
,
Double
, Str
, Char
, and Bool
. All integer arithmetic is
unlimited precision, like in Python.
The operators +
, -
, and *
have their traditional meanings
for Int
and Double
. The normal division operator /
always
gives you a Double
result. The floor divide operator //
always
gives you an Int
, truncated towards negative infinity. So:
>>> -3.5 // 1
-4
Strings are enclosed in double quotes. Characters are enclosed in single quotes.
The function traceln
sends diagnostic output to the console. The if
and while
constructs look much like their Python equivalents, as do lists
such as [4, 14]
.
Operator precedence is generally the same as in Java, Python, or C. In a few cases, Monte will throw a syntax error and require the use of parentheses.
With that, let’s set aside our game sketch and look at a more complete
rendition, mafia.mt
:
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | # An implementation of the Mafia party game state machine.
import "lib/enum" =~ [=> makeEnum]
exports (makeMafia, DAY, NIGHT)
def [MafiaState :DeepFrozen,
DAY :DeepFrozen,
NIGHT :DeepFrozen] := makeEnum(["day", "night"])
def makeMafia(var players :Set, rng) as DeepFrozen:
# Intial mafioso count.
def mafiosoCount :Int := players.size() // 3
def sample(population :List, k :(Int <= population.size())) :List:
def n := population.size()
def ixs := [].diverge()
while (ixs.size() < k):
if (!ixs.contains(def ix := rng.nextInt(n))):
ixs.push(ix)
return [for ix in (ixs) population[ix]]
var mafiosos :Set := sample(players.asList(), mafiosoCount).asSet()
var innocents :Set := players - mafiosos
var state :MafiaState := NIGHT
var day := 0
var votes :Map := [].asMap()
object mafia:
to _printOn(out) :Void:
def mafiaSize :Int := mafiosos.size()
def playerSize :Int := players.size()
out.print(`<Mafia: $playerSize players, `)
def winner := mafia.getWinner()
if (winner == null):
out.print(`$state $day>`)
else:
out.print(`winner $winner>`)
to getState() :MafiaState:
return state
to getQuorum() :Int:
return switch (state) {
match ==DAY { (mafiosos.size() + innocents.size() + 1) // 2}
match ==NIGHT {mafiosos.size()}
}
to getMafiaCount() :Int:
return mafiosoCount
to getWinner():
if (mafiosos.size() == 0):
return "village"
if (mafiosos.size() >= innocents.size()):
return "mafia"
return null
to advance() :Str:
if (mafia.getWinner() =~ outcome ? (outcome != null)):
return outcome
if ([state, day] == [NIGHT, 0]) {
state := DAY
day += 1
return "It's morning on the first day."
}
if (mafia.lynch() =~ note ? (note != null)):
state := switch (state) {
match ==DAY {NIGHT}
match ==NIGHT { day += 1; DAY}
}
votes := [].asMap()
return note
return `${votes.size()} votes cast.`
to vote(player ? (players.contains(player)),
choice ? (players.contains(choice))) :Void:
switch (state):
match ==DAY:
votes with= (player, choice)
match ==NIGHT:
if (mafiosos.contains(player)):
votes with= (player, choice)
to lynch() :NullOk[Str]:
def quorum :Int := mafia.getQuorum()
def counter := [].asMap().diverge()
for _ => v in (votes):
if (counter.contains(v)):
counter[v] += 1
else:
counter[v] := 1
traceln(`Counted votes as $counter`)
escape ej:
def [victim] exit ej := [for k => v in (counter) ? (v >= quorum) k]
def count := counter[victim]
def side := mafiosos.contains(victim).pick(
"mafioso", "innocent")
players without= (victim)
mafiosos without= (victim)
innocents without= (victim)
return `With $count votes, $side $victim was killed.`
catch _:
return null
return ["game" => mafia, "mafiosos" => mafiosos]
|
Unit Testing¶
This module also uses Monte’s unit test facilities to capture a simulated game:
18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | import "unittest" =~ [=> unittest]
import "lib/entropy/entropy" =~ [=> makeEntropy :DeepFrozen]
import "lib/entropy/pcg" =~ [=> makePCG :DeepFrozen]
def sim1(assert):
def names := ["Alice", "Bob", "Charlie",
"Doris", "Eileen", "Frank",
"Gary"]
def rng := makeEntropy(makePCG(731, 0))
def randName := fn { names[rng.nextInt(names.size())] }
def [=> game, =>mafiosos] := makeMafia(names.asSet(), rng)
assert.equal(`$game`, "<Mafia: 7 players, night 0>")
assert.equal(mafiosos, ["Eileen", "Frank"].asSet())
def steps := [game.advance()].diverge()
while (game.getWinner() == null):
# Rather than keep track of who is still in the game,
# just catch the guard failure.
try:
game.vote(randName(), randName())
catch _:
continue
def step := game.advance()
if (step !~ `@n votes cast.`):
steps.push(step)
steps.push(`$game`)
assert.equal(steps.snapshot(),
["It's morning on the first day.",
"With 4 votes, innocent Alice was killed.",
"<Mafia: 6 players, night 1>",
"With 2 votes, mafioso Eileen was killed.",
"<Mafia: 5 players, day 2>",
"With 3 votes, mafioso Frank was killed.",
"<Mafia: 4 players, winner village>"])
unittest([sim1])
|
We still cannot import access to a true source of entropy; makePCG
constructs a pseudo-random number generator given an initial seed, and
makeEntropy
makes an object that takes the resulting sequence of bytes and
packages them up conveniently as integers etc. In
Secure Distributed Computing, we will develop the part of the game that
provides a truly random seed. But for unit testing, the seed is an arbitrarily
chosen constant.
Additional flow of control¶
Other traditional structures include:
try{...} catch errorVariable {...} finally {...}
throw(ExceptionExpressionThatCanBeAString)
break
,continue
switch (expression) {match pattern1 {...} match pattern2 {...} ... match _ {defaultAction}}
String Interpolation with quasi-literals¶
Monte’s quasi-literals enable the easy processing
of complex strings as described in detail later;
out.print(`currently $state>`)
is a simple example wherein the
back-ticks denote a quasi-literal, and the dollar sign denotes a
variable whose value is to be embedded in the string.
Dynamic “type checking” with guards¶
Monte guards perform many of the functions usually thought of
as type checking, though they are so flexible that they also work as concise
assertions. Guards can be placed on variables (such as mafiososCount
:Int
), parameters (such as players :Set
), and return values (such as
getState() :MafiaState
).
Guards are not checked during compilation. They are checked during execution and will throw exceptions if the value cannot be coerced to pass the guard.
Monte features strong types; monte values resist automatic coercion. As an example of strong typing in Monte, consider the following statement:
def x := 42 + true
This statement will result in an error, because true
is a boolean value
and cannot be automatically transformed into an integer, float, or other value
which integers will accept for addition.
We can also build guards at runtime. The call to makeEnum
returns
a list where the first item is a new guard and the remaining items are
distinct new objects that pass the guard. No other objects pass the
guard.
Todo
show: Guards play a key role in protecting security properties.
Final, Var, and DeepFrozen¶
Bindings in Monte are immutable by default.
The DeepFrozen guard ensures that an object and everything
it refers to are immutable. The def makeMafia(…) as DeepFrozen
expression
results in this sort of binding as well as patterns such as DAY
:DeepFrozen
.
Using a var
pattern in a definition (such as mafiosos
) or parameter
(such as players
) lets you assign to that variable again later.
There are no (mutable) global variables, however. We cannot import a random
number generator. Rather, the random number generator argument rng
is
passed to the makeMafia
maker function explicitly.
Assignment and Equality¶
Assignment uses the :=
operator, as in Pascal. The single equal
sign =
is never legal in Monte; use :=
for assignment and
==
for testing equality.
==
and !=
are the boolean tests for sameness. For any pair
of refs x and y, “x == y” will tell whether these refs designate
the same object. The sameness test is monotonic, meaning that the
answer it returns will not change for any given pair of objects.
Chars, booleans, integers, and floating point numbers are all
compared by their contents, as are Strings, ConstLists, and ConstMaps.
Other objects only compare same with themselves, unless their
definition declares them:ref:Transparent<selfless>, which lets them
expose their contents and have them compared for sameness.
Data Structures for Game Play¶
Monte has Set
, List
, and Map
data structures that let us
express the rules of the game concisely.
A game of mafia has some finite number of players. They don’t come in
any particular order, though, so we write var players :Set
to
ensure that players
is always bound to a Set
,
though it may be assigned to different sets at different times.
We use .size()
to get the number of players, and once we get the
mafiosos
subset (using a sample
function), the set of innocents
is
the difference of players - mafiosos
.
We initialize votes
to the empty Map
, written [].asMap()
and add to it using votes with= (player, choice)
.
To lynch
, we use counter
as a map from player to votes cast
against that player. We initialize it to an empty mutable map with
[].asMap().diverge()
and then iterate over the votes with for _
=> v in votes:
.
Functional Features (WIP)¶
Monte has support for the various language features required for programming in the so-called “functional” style. Monte supports closing over values (by reference and by binding), and Monte also supports creating new function objects at runtime. This combination of features enables functional programming patterns.
Monte also has several features similar to those found in languages in the Lisp and ML families which are often conflated with the functional style, like strict lexical scoping, immutable builtin value types, comprehension syntax, and currying for message passing.
Comprehensions in Monte are written similarly to Python’s, but in keeping with
Monte’s style, the syntax elements are placed in evaluation order:
[for KEY_PATTERN => VALUE_PATTERN in (ITERABLE) if (FILTER_EXPR) ELEMENT_EXPR]
.
Just as Python has dict comprehensions, Monte provides map comprehensions –
to produce a map, ELEMENT_EXPR
would be replaced with KEY_EXPR => VALUE_EXPR
.
A list of players that got more than a quorum of votes is written
[for k => v in (counter) ? (v >= quorum) k]
. Provided there
is one such player, we remove the player from the
game with players without= (victim)
.
Destructuring with Patterns¶
Pattern matching is used in the following ways in Monte:
The left-hand side of a
def
expression has a pattern.A single name is typical, but the first
def
expression above bindsMafiaState
,DAY
, andNIGHT
to the items frommakeEnum
using a list pattern.If the match fails, an ejector is fired, if provided; otherwise, an exception is raised.
Parameters to methods are patterns which are matched against arguments. Match failure raises an exception.
A final pattern such as
to _printOn(out)
or with a guardto sample(population :List)
should look familiar, but the such-that patterns into vote(player ? (players.contains(player)), ...)
are somewhat novel. The pattern matches only if the expression after the?
evaluates totrue
; at the same time,player
is usable in the such-that expression.Each matcher in a
switch
expression has a pattern.In the
advance
method, ifstate
matches the==DAY
pattern–that is, ifstate == DAY
–thenNIGHT
is assigned tostate
. Likewise for the pattern==NIGHT
and the expressionDAY
.An exception would be raised if neither pattern matched, but that can’t happen because we have
state :MafiaState
.Match-bind comparisons such as
"<p>" =~ `<@tag>`
test the value on the left against the pattern on the right, and return whether the pattern matched or not.Matchers in object expressions provide flexible handlers for message passing.
The [=> makeEnum]
pattern syntax is short for ["makeEnum" =>
makeEnum]
, which picks out the value corresponding to the key
"makeEnum"
. The Module Syntax Expansion section explains how
imports turn out to be a special case of method parameters.