[Music]
okay all right hi everyone
so yeah I'm Andrew Miller I'm a
professor at the University of Illinois
at urbana-champaign
I'm also a member of the research
initiative ic3 the initiative for
cryptocurrencies and contracts I'm also
a board member of the Z cash Foundation
and enterprise aetherium Alliance I'm
also a technical adviser to a bunch of
aetherium related projects for example
chain-linked which I know was talked
about earlier and what I want to tell
you about today is basically a
culmination of the last couple of years
of research into smart contract
programming that I've been doing I've
been doing research and cryptocurrencies
since prior to aetherium back in the
Bitcoin times and have been trying to
include etherium smart contract
programming in things like assignments
at the University of Maryland and like
computer security courses since as early
back as 2014 like before aetherium was
even released and what i want to talk
about is basically how we evaluate the
languages that we use to write smart
contracts in so you all know the story
that we now think about crypto
currencies as not just on a place where
money goes and you can transfer money
from one person to another we think more
generally about writing programs that
run on the blockchain and we need smart
contract programming languages to define
these now you probably all know that
there's two main paradigms for writing
smart contracts to run on a blockchain
crypto currency you've got your Bitcoin
style programming language which is not
turing-complete all right and you've got
your aetherium style programming
languages which are turing-complete ins
so you probably you know at least seen
this kind of idea this is the main
difference between these two programming
styles on the right you've got more
complicated control flow maybe these are
going to be more difficult to analyze
and maybe the simplified Bitcoin scripts
more rigid less expressive hopefully
easier to analyze now there's a version
of this talk
I give that um really just drives in on
this point this really isn't the right
way to think about the differences
between smart contract programming
languages turing completeness is really
a red herring it's just not uh it's not
the real point you know the compressed
version of this I'll just list the the
kind of summaries of this all right it's
not really the case that aetherium is
Turing complete all of the things about
halting problem in infinite loops being
undecidable they don't apply because of
the gasps limit that effectively makes
etherion programming not Turing complete
you know how long something's going to
run at most all right and it's not the
case that you'd ever need Turing
completeness so it's not necessarily the
most important thing that you want
anyway and if you have a Turing complete
language it doesn't necessarily mean you
can do everything you want to in it all
right it's not just what you can compute
that matters but um how input and output
are handled concurrency things like that
all right and uh something that I hear a
lot but it's not you know it's just not
true it's not the case that Turing
complete languages are not possible to
apply formal validation to it's really
awesome that the etherium community's
moving full ahead and caring about
formal methods and it's the case that
formal methods can also apply to you
know programs written in a
turing-complete language as well maybe
it's not decidable maybe you can't do
all analysis for all programs but you
can still have very effective formal
verification methods alright so if you
buy this premise and you say ok turing
completeness is a red herring how else
should we go about evaluating the
difference between smart contract
programming languages and what do we
want from one so the approach that i've
been taking in my research i should also
say what i'm gonna talk about a couple
of different research projects that are
joint work with some collaborators of my
anudo benta of Ranjit Kumar asan and
Patrick McCrory who you would have heard
talked earlier and uh one of the
breakout sessions and the approach that
we've been taking is basically to come
up with interesting applications and try
to refine them over time to get them as
efficient or as effective as we can in
some kind of quantitative way and to see
how far we can go by implementing these
applications in the different smart
contract programming languages now
there's a common theme that you all this
aetherium audience might find heartening
that this common theme runs through all
of these applications that we've tried
which is that
there's some quantitative reason where
we can do a better job of implementing
these applications in aetherium than we
can in the Bitcoin style programming
language alright and that's what I'm
gonna try to explain just to give a
quick preview of these three things I'll
tell you a little bit about lottery
applications in aetherium and to do a
coin flip lottery in aetherium you can
do quite simply and quite efficiently
whereas to try to do the same thing in
Bitcoin you require this kind of
trade-off of either an exponential
amount of computation in the number of
parties that are playing or else you
have to lock up a bunch of extra money
as security deposits that you don't have
to in the etherium case and then I'll
tell you a little bit later about
payment channels and things like the
lightning or rated Network and there's
an optimization that you can make in
etherium that reduces the amount of
money that you have to have locked up
for a certain amount of time in these
payment channels that we can't figure
out how to get this benefit in in
Bitcoin this trick only works in
aetherium all right and then finally all
and by telling you a little bit about a
poker protocol that we worked on where
there's really two properties that you
would want and you can't get both of
them at the same time with Bitcoin
whereas you can do that in aetherium
all right so let me start by just
introducing this lottery application and
let me explain to you how this goes so
you all know the lottery application
it's perfectly simple you have n players
they each put in one coin all right and
then some random selection process
happens and then one of them walks away
with all n of the coins now I'm gonna
say that the the condition that I want
you would probably think of using the
block hash for this let's just say
that's out of bounds what we care about
is the fair cryptographic on committin
reveal kind of lotteries so not relying
on a block hash which miners might be
able to influence alright so the way
that this works the coin flip lottery
you've probably seen this in some kind
of form it's similar to what um theory
emmm name services bidding does all of
the parties are going to pick some
random value and they're going to before
some time limit they're going to place
the hash of this random value on the
blockchain and then they have up to some
time limit after all of the The
Commitments are in to reveal what those
random values were that they committed
to right and then the random winner is
some you know decided somehow by
adding up all of these secret values
that are revealed and then hashing them
and that picks one of the winners right
now this is simple in order to make it
secure though you want to have this or
that it's a fair lottery so that even if
n minus one of the parties are bad they
can't get they can't cheat against the
one remaining honest party and where the
problem ends up happening that you need
a technical solution to is what happens
if one of these players just doesn't
show up and doesn't reveal their secret
value that they committed to in the
earlier round all right you have to have
some way of handling this case maybe the
first thing that you would think of is
just to take a security deposit like you
have an extra coin that each party has
to put in and if they don't reveal their
value then they lose that coin all right
so this makes sense but it doesn't
actually solve the problem because if
there are more than one player that
collude against you know even the one
remaining honest party then just doing
this
still penalize --is the honest parties
that are remaining all right the simple
solution doesn't give you a fair lottery
now this idea of a coin flip lottery has
been an interesting test case it was one
of the first smart contracts examples
that people tried to work out how to do
in Bitcoin and what I'm gonna describe
is that the version that you can do in
Bitcoin still has this trade off like I
mentioned you either have to collect
really big security deposits or you have
to do a kind of ridiculous amount of
extra computation whereas in aetherium
there's a way of doing a lottery quite
simply that doesn't require any of this
extra collateral so to start let me
explain how this works in Bitcoin again
this has been an important test case for
smart contract programming since even
prior to aetherium the main tool that we
have at our disposal is this idea of a
claim or refund gadget it's denoted by
this little arrow which has some
parameters like an amount of money Q a
hash H and some deadlines T and what
what this arrow is saying is that Alice
is promising to Bob that she's going to
reveal the preimage of this hash value
by some deadline T and if she fails to
reveal that preimage then Bob gets the Q
dollars okay so that's what's meant by
this claim a refund gadget
you know to implement the claim a refund
gadget in Bitcoin
I won't go all the way through this it's
something you can do with the the
Bitcoin scripting language it's
especially easier now it used to be
possible but a lot harder before I check
lock time verify it's a lot simpler now
with the check lock time verify opcode
it's like you make a UT x 0 that has a
piece of you know script pub key Bitcoin
script in it that says this can be
claimed
you know before a deadline if you you
know reveal the preimage of this hash
then then alice can spend it it comes
with a signature from alice and the pre
image or if time t1 elapses then Bob can
take the coin just with his signature he
doesn't have to reveal anything but he
can only do this after this deadline
alright so there's two ways to spend
this there's the refund transaction
which has to come along with X all right
and so Alice can make this by revealing
X before the deadline or else a claimed
transaction means Alice forfeited it she
didn't reveal her pre image in time so
Bob gets the coins instead all right so
um it actually turned out that a lottery
that implemented this was one of the
contributions of a really interesting
paper that actually won the best paper
award in 2014 at the Oakland conference
this is the the most prestigious
computer security conference and the
academic computer security research
community and they came up with a way of
they didn't express it in terms of the
claimed refund that little abstraction
came later from Ito and Ranjith but um
it uses this basic technique but the
catch is that it requires this really
large amount of collateral the idea is
that every party deposits enough
security collateral that if they get
caught failing to reveal their committed
value they compensate every other party
for the total amount that any of the
parties could have won so it's like
whatever is the total amount of the
lottery times the number of parties
there are that's what each party has to
put up as a security deposit and the way
that this is implemented is kind of um a
monstrosity this isn't even the full
transaction graph of all the parts that
are needed it's um this is actually kind
of the plain case basically what happens
is all of the parties make these claim
or refund commitments to each other all
right and then they'll all get settled
at once but it requires collecting this
large amount of security to deposit up
front and so each party has to put in N
squared coin
and so it's n cubed in total is the
amount of collateral that's required in
addition to the bet now you know and
Ranjit came up with a way to improve on
this which is also extremely clever and
yet you also get the feeling it's kind
of complicated I won't be able to you
know to even describe it in a way that I
think you'll totally be comfortable with
it
you could think of it like this it
involves proceeding in sequential rounds
where in each round the parties make a
claim or refund to the next party in
line all right and then there's like a
separate unwinding phase where they also
make commitments they make these claim
or refunds with that where you have to
reveal multiple preimages and each one
of them one more preimage than the last
it's really hard to describe it but it
requires now like a linear number of
rounds like you have to do this one at a
time the timeouts get larger and larger
each time it's kind of like if I'm you
know if any party fails to reveal their
preimage then the next party in line has
enough money to compensate them plus
everyone else after this
all right the net result is it reduces
the total amount of extra security
deposits you need to collect down from n
cubed in total to merely N squared in
total all right but it also comes at a
trade-off which is that this ends up
stretching out over and rounds like the
lottery takes longer the more parties
that you have participating whereas the
original one took more collateral but
you know finished in a constant number
of rounds and it still has this quality
that I think it's a little bit hard to
wrap your head around so I'm not going
to try to explain it any more clearly
than that the techniques really clever
though now you might start to wonder you
know is there a simpler way of doing
this and so I should say again all of
these were done in in Bitcoin prior to
aetherium being so widely appreciated
anyway we started to look at how you
could do a lottery in aetherium and it
just immediately was simple oh you can
do something a lot easier than this what
you can do is have a tournament bracket
where you always have two parties just
playing a flip game against each other
all right and at each time you like lay
them out like a tournament bracket after
the first two parties play then whoever
wins that lottery goes on to the next
round all right and then you finally you
keep doing this like a tournament until
you get to the final of the tournament
and then whoever's there wins and now
the rule is that the way
you handle aborts is that since you're
always just playing with an opponent if
you fail to reveal your secret in time
then the other party wins it's like you
forfeit the other party immediately goes
on to the next level and this is really
easy to do in aetherium because you can
keep track of who was the winner at each
bracket it's really easy to do this with
um lots of contracts like one contract
for each match and then the contracts
talk to each other it's also easy just
to unfold it and write one big contract
that keeps an array keeping track of all
of the different stages of the
tournaments it's really quickly pretty
simple at something you could implement
in solidity we started to look then at
okay so you can do this simple
tournament bracket and etherium I should
say also that um you know this
tournament doesn't require any extra
collateral because you don't have to
take a security deposit from someone if
they forfeit you just you know that the
other person goes on to the next level
so we looked at to try to see if we
could emulate this tournament structure
rather than this linear structure or one
round expensive structure in Bitcoin and
we came up with something that's a
little bit unsatisfying but it is still
technically a tournament structure we
came up with this extension of the
claimer refund gadget that's really like
a two-way claim a refund gadget it
involves a sequence of two transaction
scripts rather than just one it's like
Alice has a turn to commit bob has a
turn Alice has a turn to reveal bob has
a turn to reveal you know the net of it
is that there are everyone has two all
of these transactions have to be signed
by all of the parties involved ahead of
time like all of the parties in the
tournament have to sign all of these
transactions everything except for the
the hash preimages is the only thing
that's left out of the signature all
right and you know no matter what there
will be like at least this transaction
on the blockchain and then you know
there's some case where you can go
straight to one of these outcomes
basically there's three possible
transactions that can be the outcomes of
this like two of the transactions
involve Bob winning one of the the
possible output transactions involves
Alice winning it's a little bit tricky
to explain but it's basically the same
kind of thing you're encoding this
condition of you know reveal a pre-image
before sometime you can do that in
Bitcoin script the
and chaining these things together by
having multiple transactions pre signs
that all refer to each other and this
structure you can actually combine into
a tournament bracket just like the
etherium example but with a catch all
right so that catches that because in
Bitcoin transaction script even making
use of Segway even making use of the
most modern op codes when you have a
transaction that receives inputs you
have to expressly indicate the
transaction ID of the transaction whose
input you know whose outputs you're
spending as an input so what that means
is that if one of the matches in this
first round has three possible output
transactions alright then to make the
next round of the tournament that
depends on it it has to have you know
you have to have one pre-signed
transaction for each of those possible
inputs and so if you have it the the
next round of transactions has two
possible matches two possible matches it
has two like the winner from each of
these two matches goes on to the next
round you end up having to have three
times three different contracts each for
each combination of the ways that that
could end and then it gets worse from
there because now this you know stack of
transactions has 27 possible outcomes
all right and so the next layer has to
have 27 times 27 of those and it goes on
by the time you get to the end you
you've got this tournament bracket that
worked but you end up having an
exponential number of transactions that
everyone has to sign up front only one
of them will end up getting put on the
blockchain but you have to sign them all
up front and so that's where this
exponential amount of computation comes
in it's kind of unsatisfying it's a
little bit awkward it's kind of like
having one hot encoding where the the
the one hot is which of these
transactions you sign up front actually
gets placed on the blockchain and you
have one of these you know transactions
for every possible combination of all
the different ways the tournament could
have gone up to that point all right is
this a bit of a convoluted structure the
lesson that we get here immediately is a
qualitative one which is that things
that are pretty simple to express an
ethereal are sometimes really
complicated to express in Bitcoin
sometimes there's a way to do it I'm
surprised at just how often there's
something that I thought there'd be no
way to do and yet we can figure out a
way to do it in Bitcoin script but it's
a little bit on you know unsatisfying
and unnecessary
early convoluted it's a little bit like
trying to build a web browser inside a
ti-83 calculator you can do it but ti-83
basic is not the most friendly language
to be entering and you know button key
presses at a time but really the power
of this is that we have not just that
qualitative statement but this actually
gives us a quantitative statement about
the difference between these two
programming paradigms all right this is
like the scoreboard of how well we can
do a lot of reason these different
environments write in these original
Bitcoin ones you know earlier traded off
this amount of you know collateral that
you had to take for varying amounts of
computation or running time all right
and then this weird one that we figured
out how to do as this exponential cost
but back down to no extra collateral
right whereas the one that we get in
etherium is pretty efficient in the
number of rounds and it doesn't require
any extra collateral or any unusual
amount of computation
all right despite being qualitatively
simpler I want to switch to then talking
about you know the next application
maybe you'll find this one more
interesting because payment channels are
invoked these days and this is a paper
called sprites you can find this paper
online all right and the upshot of it is
that if you have a lightning Network
situation where you have payments that
are going across you know some lengths
in this payment channel graph the amount
of collateral cost that you need is
quadratic all right in in the worst case
as a function of the length of the hops
that you have to go I'll give you some
explanation of that whereas in aetherium
we can do something simpler and we can
reduce this collateral cost from
quadratic down to linear so you all know
what a payment channel is by now it's
where you make a smart contract where
you deposit some money for two parties
and then after doing that initial
deposit you can do off chain payments to
each other really rapidly all right and
then what's really especially cool about
them is that if you have a chain of
payment channels from one party to
another like you have Alice and Bob here
Alice wants to pay Bob she doesn't
already have a payment channel to Bob
but she has a sequence you know she has
some intermediaries to whom she does
have payment channels and there's some
path of payment channels from her to Bob
you can do this linked payment where
each party pays the next person down in
the chain and you do this in a way where
there's like an atom isset II guarantee
which means that these parties in the
middle they're not losing any money like
they're getting X from there and
channel they're paying Exxon they're out
coming channel they net out alright and
there's no risk of them actually losing
their money now the fun of this right
this is this idea of the Lightning
Network that we can have with a
relatively small number of payment
channels we can build paths connecting
any two parties with fairly low path
length between them while still each one
only is pretty small degree like no one
person has to have too many payment
channels now what you care about in this
case is the collateral cost which is you
should think of as like the dollar hours
or the money times time that your
money's tied up because the payments in
a payment channel don't necessarily
happen instantaneously especially if one
of the parties goes offline so when one
of these payments begins it doesn't just
happen immediately it's in a pending
state for a while until it settles and
so this guy is outgoing payment is also
in a pending state and if you know
something happens and someone doesn't
send you know immediately what they
should this pending state might last for
a while meanwhile this intermediary node
is asking when's you gonna get the money
back how long is his extra dollar tied
up and that's this money times time
collateral cost now the way that
lightning and also Radin go is that when
you establish these linked payments it's
like you set up conditional payments
from one party to the next and these are
you know similar to that claim a refund
thing they have a dollar amount they
have a pre-image and they have a
deadline and what happens is that each
deadline has to be a little bit larger
than the next it happens in the typical
case is that right that this party on
the right end has the preimage ex and he
waits until he gets his incoming payment
and then he goes ahead and reveals it
you know anyone who's listening in the
typical case it just completes
immediately after that it's pretty quick
right an entirely off chain but the
reason why you need that extra delay is
because right what can happen is that if
say these two orange colored parties are
bad they actually hold on to that
preimage ex they don't just send it to
everyone when they get their incoming
conditional payments made it may be that
this guy right here this blue one only
finds out about the preimage X because
this orange guy was Petty which I mean
he waits till the very last possible
moment and then actually puts X on the
blockchain and gets his payment so when
this happens this guy gets it in right
at his deadline t plus one this blue guy
here has to turn around and then
put that Exxon on the blockchain himself
in order to get this payment from the
other guy all right so as a result he
needs to have some extra amount of time
he has to wait to see this transaction
on the blockchain and then be able to
get his transaction in before his
timeout goes that's why each party has
to have a longer timeout than the party
to their right all right so as a result
if you have a length L chain of payments
that you want to make then you have to
have L times whatever's an appropriate
amount of time for this guy to you know
in the worst case have to have his money
locked up and this means that the total
collateral cost in the worst case when
you know people other people in the
chain are delaying in this way is you
may have to have l squared you know in
total among all of these parties it
could be up to L squared times X in
dollar hours right this collateral cost
now here's what we can do in aetherium
this is the idea of sprites it's an
optimization we actually come up with a
way that you can have chained payments
it works really similar to this except
the lock times the deadlines for each
one of these conditional payments is
exactly the same and the way it works is
that the rules for settling this payment
make use of a global condition not just
a local condition the way that you do it
and lightning in and Radin we have a
single contract we call the global
preimage manager and the idea is that
rather than requiring each value to be
sent on each payment channel the rules
for settling this payment channels say
go to the global preimage manager
contract and check whether a value was
published there in time all right what
it looks like in the worst case is that
if some party goes and puts their value
at the last possible moment it's like it
sets an on blockchain event that then
guarantees that all of the channels if
they go to this dispute handling case
are going to close in exactly the same
way these other parties upstream in the
payment channel no longer have a burden
of responding and a certain deadline
they know that whenever they get around
to it the channels are gonna settle in a
consistent atomic way which will
guarantee that known of the
intermediaries lose any money which is
what we want all right the key to this
is making use of this global pretty
image manager contract which is
something that's straightforward to do
in aetherium before which there's no
real way to do it in Bitcoin
I'm just gonna really briefly mention
this last application of poker I'm not
going to go into very details about it
although there's a paper online that you
can read to see it right online poker is
one of these holy grails of
cryptographic applications it's really
exciting because people like playing
poker and it's an interesting exercise
of your cryptography because you have
private cards that you need to deal and
need to keep secret and you know the
basic structure of handling the
housekeeping of keeping track of like
whose turn it is and whether anyone
forfeited a turn and therefore needs to
be punished that can be handled by the
state channel generalization of this
payment channels idea so without going
into any of the cryptography that's
there I just want to point out that
there that we've had the sequence of
works mostly just a Ramsey de niro I
only hoped in this on last one there's
really like two parties that you had to
two properties that you would like from
a good poker application one is that you
would like it to be off chain only in
the typical case so you can play many
rounds of poker without having to make a
non chain transaction in pay fees and
you would also like the poker game not
just to end up telling you who the
winner is but to actually like give you
the amount of money that you want back
okay my screen went out okay so um well
I think you got the gist of that end of
it the only thing that the only way to
get both of these properties combined is
to have to make use of the the
flexibility and the etherium smart
contract model we couldn't find any way
of being able to get both of these
desired properties both having off train
in the usual case and actually being
able to do a payment out oh this just
drop okay
no it's a weirdly next thing I have to
open up
Hudson James and everyone okay all right
yeah the only point I wanted to make
yours we want to have both of these
qualities like these ones here that say
no cash distribution what it means is
that you learn who the winner was but it
doesn't actually make any money change
hands at the end right you want to play
poker for some kind of stakes in order
to get both of these qualities where you
can actually settle for money on chain
when you have to but it's off train only
in the typical case all right we weren't
able to figure out how to do that in
Bitcoin whereas all of these one
desirable property the other we figured
out some way of doing it in Bitcoin but
to get both seems to rely on the ability
of having like references to dynamic
transactions rather than having like a
fixed transaction input which is what
your is constrained to do in the u TXO
model alright so I just want to wrap up
in here by saying you know more about
what I think is the the lesson that
we've learned from this so first of all
I think this is a way to go about
evaluating the expressiveness of smart
contract languages I think that if
someone proposes a new smart contract
language one of the first things you
should try to do is to see can you
implement the the high score on the
scoreboard for all of these applications
if you get stuck there's a sign that
there's something you know useful that
you would like to be able to do in smart
contract programming that this language
isn't affording all right there are
other like trade-offs and so maybe
there's you know some justification like
that so for example the the you TXO
model in Bitcoin supports benign reorg
Slyke if there is a reorg than all of
the transactions will be shortly played
right after all right and there's some
trade-off involving privacy um with
sprites so I'm not saying that you
absolutely need to have this benefit I
think it's the case that doing on you
TXO prototyping first actually slows
down research by obscuring the main idea
behind a smart contract application all
right and a sort of obscuring the key
ideas and I think that the fact that
Radin was designed the way that it is
was because it was mimicking the the
design and bitcoin which was only
necessary because of bitcoins limited
script so even the Radin you know clone
of the Lightning design fails to make
use of a theorems full power even though
it's in in the etherium language so you
know my suggestion is that you should
use a language like aetherium to
prototype your new application even if
it's something that
you're eventually going to eventually
try to port to Bitcoin or to other
applications so I'll stop there Thanks
[Music]