so like we said we're gonna talk about
why all your smart contracts are
vulnerable to bribery and what to do
about it and this is joint work with a
number of excellent co-authors like all
good research remember no research is
ever an island so let's start by talking
about why we're all here and actually
one of the interesting reasons we're all
here is because of a Polish economist
from the 1970s named John Harsanyi who
laid the groundwork for this field of
study we call mechanism design what is
mechanism design it's a field of
economics and game theory that takes an
engineering based approach to trying to
get users to behave a certain way using
economic incentives assuming the players
in this game will act rationally and in
their own self-interest so the field
started in the 60s and 70s and consists
of several basic components one of them
is a mechanism which is a game that has
rules a game environment and that
players send messages to that game has
an outcome and that outcome has what's
called a social choice function or
social utility function that says how
good that outcome is for all the players
in the game and therefore for society at
large so what you want to do is
implement some mechanism that implements
some social choice function you find
desirable and the hope is that because
people act rationally they'll sort of
converge on this social choice function
you've chosen so what's an example of
this well before Devcon I actually found
myself pretty hungry and I wanted some
toast but I actually couldn't decide
whether I wanted regular toast or toast
with an image of Jesus on it like you
may have seen being popular on on
various auction sites obviously I went
with the Jesus toast because who
wouldn't
and so I headed over to ebay and found
some auctions on this sort of toast and
you can see here this one has a few days
left in the auction and it's currently
bidding at 1 cent so I was like this is
great I put in my bid for 2 cents and
I'm gonna win this Jesus toast and sort
of fill my hunger the Pens sort of at
the last second someone comes in and
puts a bid for over $9,000 because they
really wanted that piece of toast and
I'm sort of left hungry and not knowing
what's going on so this sort of
highlights a general problem with
auctions which is that in auctions you
need to play strategically you need to
consider how other people are going to
act when you choose how you're going to
act yourself and the games you sort of
play with them like people play on eBay
become very complex
so one of the early things the field of
mechanism design has looked at
traditionally is can we improve things
like auctions and in terms of the social
choice function what our high-level
goals are for that function for the
seller their goal is to maximize their
profit from selling the item of course
and for the buyers they don't want to
overpay over what they think the item is
worth or the minimum they could be
paying they don't want to have to think
about complex strategies like when
should I place my bid do I have to wait
until the last second what are other
people gonna do in this auction and how
can I get this item more cheaply and the
buyers also want to win the item if they
value it more than any other buyer in
the system we also assume the existence
of some auctioneer who's this sort of
trustworthy third party that runs the
mechanism which is sort of a classic
assumption in mechanism design that you
have this third party that everyone who
trusts that's actually running this game
that we talked about so can we improve
the eBay auction one of the proposals
from sort of mechanism designers
classically was what's called a VC G
auction or Vickery Clarke's Groves
auction and the way this works is that
all the buyers send a bid in a sealed
envelope to the auctioneer and at the
end of the auction the auctioneer opens
it and the the winner of the item is the
highest bidder but he pays the second
highest price for the item this model is
used very commonly in things like ad
sales and you can actually
mathematically prove that given a bunch
of private valuations on the buyer the
best strategy for any buyer in this game
is to bid what the item is really worth
for them if they over bid in many cases
they will lose money over bidding their
real valuation and similarly if they
under bid they'll lose money so that's
great right that's what's called a
dominant strategy truthful mechanism in
the classic field of mechanism design
meaning that a buyers dominance or best
strategy is always to tell the truth and
traditionally we've wanted to build
mechanisms that rdst because they
minimize cognitive load and overhead for
sort of the players in your system and
just make things simpler to think about
in reason about and cryptocurrency has
sort of continued this broad tradition
of mechanism design again by some party
or principle using incentives to drive
outcomes so this is an example from the
Bitcoin white paper
satoshi nakamoto who talks about how the
incentives in Bitcoin may help nodes to
behave honestly in the system and smart
contracts have similar overlaps and
continuations of this field of study
that's been going on since the 70s
for example there's this idea that you
can take any mechanism that we've been
studying for decades and just make it a
smart contract get rid of your trusted
third party get rid of your auctioneer
put it on chain and then we don't have
to choose who to trust to play that role
we can just sort of converge on this
code instead otherwise if you want to
build something that no one's ever built
before you can use these same techniques
that people have been using for decades
to sort of analyze your mechanism and
give users the properties they want
unfortunately there's some challenges in
doing this that make smart contracts
very different from traditional
mechanisms so again in traditional
mechanisms you have this trusted third
party where as in block chains you're
replacing it with the blockchain which
has its own sort of set of gotchas
including things like how the
peer-to-peer network works or how miners
choose transactions or sensor
transactions also in traditional
mechanisms you often assume a permission
set of players a known fixed set of
players when you analyze your games for
example eBay knows all of the accounts
that are eligible to participate in a
given action and they have permission
control over this set so does Google
when they're auctioning off ads and
because of that you can do things like
leveraging identity and there is some
trust involved there unlike in smart
contracts and cryptographic systems
where all you might see is someone's
private key and signatures and you might
not be able to leverage this shared
trust so smart contract mechanism design
poses new challenges and chief among
these challenges and what we're going to
talk about today is the ease of
coordinating bribery so last year I
wrote a blog post called the dart Dow
which if you have in read I highly
encourage you to check out and it
described a sort of nightmare scenario
where people can build bribery systems
for smart contracts that operate
completely in the dark so no one can
tell exactly what players are being
bribed to do how many players are being
bribed or or or if the attack is even
succeeding at all not only that but
users are guaranteed that the person
that's bribing them is not going to get
control of their money so the entire
thing is sort of a trustless bribing
infrastructure right and the dark Dow is
actually a mechanism for bribing other
mechanism just
and what I'm gonna do today is introduce
this new term for you guys that we call
anti mechanisms which are all mechanisms
that are intended to disrupt other
mechanisms so the dark Dao is a
particular type of anti mechanism it's
called the dark Dao because it's dark or
invisible no one can tell exactly what's
going on inside it but you could also
have a public bribery contract or other
form of anti mechanism and what anti
mechanisms look like is basically this
so on the left you have what what it
looks like when users are playing a
regular mechanism they're sending
messages to this mechanism and the
mechanism is coming up with some outputs
of the game you can see this mechanism
as a smart contract on etherium private
keys there on the left sending
transactions to the mechanism and some
outputs occurring in the state of the
system an anti mechanism happens when
you have another mechanism that users
can play through instead potentially one
that can interact with the original
mechanism so you can see that they're
shown on the right and prime here is an
anti mechanism and two users in this
case are playing em through em Prime so
why does that matter it matters because
the existence of these anti mechanisms
erode a mechanisms ability to faithfully
implement it's social choice function so
in terms of optimizing for those goals
that we talked about earlier that
mechanism design loves to optimize for
those goals are highly harmed by the
existence of these anti mechanisms not
only that but we can actually quantify
the security of a given mechanism as the
smallest budget anti mechanism that
disrupts the properties we design the
original mechanism for so I would
encourage you guys to stop thinking
about anti mechanisms or sorry stop
thinking only about mechanisms when you
design your smart contracts and your
protocols and started thinking about
what anti mechanisms could be possible
in your system and what the sort of
lowest cost of disruption is as a result
so for the VCG auction the second price
auction we mentioned earlier here's a
very simple anti mechanism M Prime
all M prime does is it collects bids
from its users and it forwards only the
top bid to the original mechanism M so
why is is playing through M prime always
better than playing through M well if
the highest bidder plays through M
doesn't matter the outcome is the exact
same as before so no one's worse off on
the other hand if the highest bidder
happens to play through M prime then
either the second bidder plays to R M
Prime
which case their bid is never forwarded
and the highest bidder ends up paying
less or the second bidder plays through
em and you get sort of the same outcome
again so what we say is that M Prime
composed with M or playing M through m
Prime in this case dominates in this
case weakly dominates playing M directly
it's always better for players to play
through M Prime and it disrupts what we
talked about earlier which is the
dominant strategy truthful nature of BCG
auctions because the auction is no
longer receiving the true valuations
from the buyers so in this case VCG in
terms of a dominant strategy
truthfulness has zero security against
bribery and bribery is a huge deal in
all these systems we're building a huge
deal in smart contracts so if you're
building an Oracle you can bribe people
to provide certain responses you can
bribe them to go offline you can bribe
them to choose which point in a
continuous time series of data they
sample and send into the blockchain if
you're running a voter a governance
system you can buy people's votes you
can pay them to not vote you can
otherwise influence governance if you're
building an identity system you can
build an ting mechanisms that lease
people's identities or partition out
certain capabilities of the identities
as separate from others and for all
mechanisms you can bribe players to take
certain strategies and even to collude
with each other or not participate so
the conclusion is basically this at
least for now so what are we gonna do
about it well first let's talk about the
core problem here which is that this
Dark Tower these private smart contracts
that we're talking about remove a user's
free will in the system they do that by
restraining the actions a user can take
in this cryptographic system and
basically shackling them to a certain
set of strategies or shackling them to a
certain collusive set and we want to get
back to sort of a state where users have
free will where we know that if they're
signing a message they could have signed
any other message in the system as well
and they're not artificially shackled by
some other piece of technology or some
anti mechanism so here we define free
will as the ability for a user to use
their information in this case their
keys in aetherium without any external
restrictions and in this case we're
specifically talking about remote
parties people who are trying to bribe
or otherwise influence users over a
network
because that's most of what we're trying
to secure against so this problem
actually goes beyond crypto currencies
this is not only a crypto currency
problem these two papers have pointed
out similar problems in traditional
cryptographic systems so one thing you
can do is you can use s jacks or MPC to
take a deniable communication protocol
where the property is that I can't
generate a transcript of the protocol
and you can actually generate a
transcript that's provable right so I
lose all my deniability I can't tell you
that no I didn't say this because now
the MPC or SGX process is gonna stamp
for me that yes I actually did say this
or you can use it to do things like
bribe people to act a certain way on
Facebook or buy their votes in like sort
of traditional and voting systems and
things like that which is what that
paper on the Left deals with so how do
we get back to free will well our core
task is ensuring that a user has
unlimited knowledge or access to their
private information such as their keys
and that those private information or
that private information can't be stored
in a secured environment that's somehow
shackling the user and our second task
is that we want to use this to make a
signature scheme that's usable in things
like smart contracts so we know that
when a user signs the message they
actually control their key so we more
generally defined free will as the
ability of a user to learn their own
secrets and we achieve free will by
requiring that whenever a user sends a
message that involves secret data for
example a private key
someone can eavesdrop on that message
and because the user won't let anyone
else eavesdrop on their message that
would for example compromise their funds
that means that essentially the user is
able to eavesdrop on their own data so
what we're gonna be doing is sort of
designing a scheme we call complete
knowledge and users are gonna provide
these complete knowledge proofs to the
system to prove that they actually know
their own secrets and that some human
knows this secret and it's not somehow
shared across multiple parties or
otherwise constrained so I'm gonna flash
a bunch of cryptography at you these
slides are gonna be on my Twitter if you
want to read this in more depth but the
only important thing on this slide is
sort of these last two bullet points
which is that we consider to computation
environments
one being sort of an untrusted
computation environment and another one
being an eavesdrop environment and we
want to make sure that a user has to
send their private data through this
environment that they can also eavesdrop
on and therefore it can learn their own
private data and the way we generate
these proofs is we require some proof
scheme that matches these two
cryptographic definitions the two
important properties here are number
three and four
the first one is unforgeable ax t that
means i can't prove to you that i know
some secret data that i actually don't
know right and the second one is secret
eavesdropping which says that i have the
ability to eavesdrop on my own data and
nobody else in the network can tell
whether or not i actually did this
eavesdropping or not if they could tell
whether i actually did the eavesdropping
or not they could simply require me not
to do the eavesdropping when they bribe
me so it's very critical that the data
is able to be eavesdropped on but sort
of in the dark and in secret and the
basic solutions we use for this are
actually quite surprising so there's two
possible schemes here one of which is
based on Bitcoin Asics and another one
of which is based on SG X or trusted
hardware so the Bitcoin ASIC solution is
to basically do a proof-of-work
on your secret key as well as some
challenge and then generate a snark that
some ASIC has done this proof on a
secret key that the snort keep secret
that corresponds to a public key that
the snark makes public so when the snark
is submitted to the network you know
that at some point someone put that
secret key into an ASIC to generate the
pal the SGX solution similarly forces
you to send the secret key as input or
the secret data as input raw unencrypted
input into an SG X chip so on the left
this allows users to eavesdrop on their
own data because Asics are not secured
you don't know what firmware someone
else is running on their own ASIC and
whether it lets them eavesdrop on their
data or not on the right SG X achieves
this because as G X enclaves have to be
communicated with through an unsecured
OS and nobody is sort of in the broader
network can tell if the OS that was
communicating with the Enclave did or
did not need to drop on its secrets so
I'm not gonna go through these but check
them out later if you're interested in
sort of the formal
the graphic definitions of both of those
schemes what we're actually implementing
is a little bit different so the problem
with the schemes that I just mentioned
is they're a little bit heavy handed and
inefficient generating the snark
actually takes quite some time so
there's this cute little trick you can
do for the proof-of-work version where
you restrict the non-space of the ASIC
and requires someone to try multiple
times to sort of generate a proof such
that if they try more than once they can
recover their own key and with high
probability then they'll be able to sort
of eavesdrop on themselves so basically
the math here works so let's talk about
the proof of work version the proof of
work version fails in one of several
cases so the proof of work version will
fail if you can use a CPU to generate
the proof of work then SGX can just
directly make this proof even though the
secret data is never known to the user
it also fails if the ASIC fails to find
a proof then a user that actually knows
their own secret data won't be able to
prove that to the network
fortunately Bitcoin Asics are much much
much faster than CPUs so a hundred
thousand times faster than
state-of-the-art CPUs at this sort of
work and you can see that given even if
they're only a hundred times faster the
probability that an ASIC will find a
solution before a CPU is basically won
right so there's sort of a broad range
of parameters here for which it's highly
likely that an ASIC will be able to find
this proof of work but a CPU will not
and therefore no sort of SGX process or
multi-party computation can also solve
this proof of work so these are the
marginal CDF's of sort of the times to
solve blue you see the probability that
an ASIC has solved the puzzle and read
the probability that a CPU has solved
the puzzle and you can see the ASIC
slope is just much steeper so you can
sort of parameterize your system to make
sure that an ASIC can always give you
this proof but a CPU can never give you
this proof and therefore no constrained
or shackled computing environment can
never give you this proof so what we're
gonna be doing is releasing this sort of
system on aetherium using this kind of
an architecture so all you're gonna need
to do in your voting contract or
anti-bribery mechanism is called a
single function on our registry when ck
which will tell you the last time that a
complete knowledge proof was generated
on some key
the last time some user proved to the
system that they actually are able to
learn their key right and users can
choose like several backends to do this
if they prefer to do it through SGX they
can do it through SGX if they prefer to
do it through a Bitcoin ASIC they can do
that and interestingly enough this also
gives us an opportunity to recycle old
Bitcoin Asics because even old Asics
that are no longer profitable for mining
on the network are still much much
faster than state-of-the-art CPUs and
can still be used kind of to generate
these proofs so I recommend to you that
if you're designing a system where
bribery is a big deal you should use
this technique to make sure users
actually know their data and they're not
being bribed by some sort of shackling
mechanism some anti mechanism like we
described earlier
not that CK is enough by itself though
so you need to actually follow this more
complex recipe you need to also provide
the classical notion of coercion
resistance which basically says that a
user can secretly change their mind
whenever they want so if a user can
secretly change their mind whenever they
want there's no point in bribing the
user because you don't know if they're
just gonna go and change their mind
later you can't tell if they did that or
not right
and because you're using CK you know
that there's no sort of shackles on the
user that prevent them from changing
their mind in this way and for stake
based systems we want to require this on
the state key so we know that whoever
signed the message actually has skin in
the game and actually has funds at risk
sort of using the generation of this
message so the high-level takeaway here
I guess is that if you don't use this
system your protocol is vulnerable to
bribery period no exceptions so please
don't DM me on Twitter and ask me like
are we vulnerable to bribery in
collusion if you haven't sort of studied
this kind of infrastructure and read
this background material because you
100% are and if you're interested in
learning more about the technical
details or you want to sort of use this
in your anti-bribery systems please feel
free to reach out to me and I'm happy to
chat more it's a very complex sort of
topic I only had 20 minutes to describe
it I know I sort of flew through it but
hopefully you got some takeaways that we
can sort of make sure users own their
own data in these systems and that's
very important to making sure that
they're not being bribed all right if
you'd like to contact me or learn
anything further here's my information
as well as funding and a big thanks to
all our IC 3 partners and
Tyrian community for their support in
this research thank you
[Applause]
you