okay so last year around January no Iran
December the year before yeah around
December last year I started to work
with snacks and thanks are applicable to
two major things for privacy and for
scalability so today I'm gonna talk
about two applications to privacy and
one application to scalability so the
privacy projects are called Maximus in
semaphore so makes a mess is uh is that
is a generic either an e or C 20 token
mixer where you can deposit money thir
and later you can withdraw one either
and there's no way to connect the
deposit to the withdrawal and Saima four
is if all it is very similar
architecture and we use that to do to do
general reputation mixing yeah so so you
can you can become part of a group and
you can signal things about your
thoughts or beliefs or other things and
no one can connect all people will know
is that you're a member of that group
and then we also have some rate limiting
things there as well so that we can do
like cooler public systems and then
we'll talk about snacks with scalability
it's okay you can come in and we'll talk
about we'll talk about snacks with
scalability so so basically we'll we'll
build an elliptic curve inside the snark
and we'll use that to make signatures
and we'll use that also to Patterson
commitments and then we then we sort of
join that all together to make something
called roll-up where and how what
roll-up is is roll-up aggregates
transactions together in order to it
aggregates transaction validation so
instead of having to verify 10,000
signatures inside the EVM you have to
verify a single snag proof you can come
in it's okay oh yeah who said that
okay so yeah so then so that's that's
what we use we use that's what roll up
it's yeah it's just it's a scalability
solution okay
so first what is a snack okay so a snake
is a snake is a way of proving that you
did a computation without proving out
proving that you did a computation
correctly yeah so the verification of a
snark is succinct oh wait I'll say that
later so given given some inputs and
some code that we predefined before
we'll get some outputs yeah that's what
that's what a snack proves yeah prove
that we run the code with the inputs and
got the outputs yeah but then we can do
cool things right we can sort of hide
some of the inputs and some of the
outputs yeah and that's this is where we
get our privacy properties right because
we can start to hide things so or we can
hide everything but that doesn't really
make much that that kind of makes sense
but not in not in a lot of applications
okay so so for the rest of the talk
we'll just talk about this code yeah so
in the center box inside the snake we
have this code that defines what we're
verifying so we'd use that to verify
that yeah so so that's the central
problem that we're trying to solve yeah
that it's difficult to make this code
that verifies that yeah so it's
difficult to define the computation that
you're verifying you did correctly so so
that's what we're gonna talk about later
or that's like that's like the main
theme of this talk yeah that will go
through that and we'll see how it
applies to three different solutions
okay oh yeah okay so how does this
relate to aetherium so so we can
validate thanks inside the EBM although
it's a little bit expensive it costs
about five hundred thousand gasp at
optimal to do that right now
but there's the there is scope to reduce
those costs so and this means we can
have privacy and scalability yeah we can
have privacy by just hiding the inputs
that we have and we can add scalability
because the
the ballot the verification of a proof
is succinct it takes the same amount of
time no matter how complicated the the
code that you are verifying is yeah so
for the rest of the talk we're gonna
define the code that we saw in the
previous figure here yeah
we're just going to define the code that
defines the snack okay so a lot of the
time in boxing we talk about a lot of
the time in boxing we talk about Merkle
trees right because Merkle trees are a
good aggregator of information so this
is how a Merkle tree works so basically
you have ABC and D and those are the
members of our group and we want to
aggregate those together to a single
root yeah so what we do is we hash A and
B together we have C and D together and
then we hash a and B C and D together
and that gives us the root yeah
so so sorry so we hash the hash of a and
B and the hash of C and D together and
we get the root so and then we can make
something called mirco proof and prove
that we remember and we can prove that
we're a member of that set okay but so
let's go forward okay so let's let's
think about this now so so we can move
we can move that Merkle proof inside a
snack yeah and this lets us do some
really cool things okay yeah okay so but
but in order in order to so we can do
cool things here but but it's there's
nobody has any permissions here right
because ABC and D are all public and
that means anyone can prove that a B and
C in the ABC or D are a member of our
group but that doesn't really that
doesn't really help us we want to we
want to have a way that that people have
some private information and they can
use that private information to signal
about to we want it we want to limit
what people are able to do inside our
system so the way that we do that is
this that we come up with this really
kind of naive we come up with this
really naive kind of public key private
key scheme yeah and the public key is
defined as the hash of of two inputs one
called it's not a fire one called a
secret and another fire in the secret I
just random numbers we just regenerate
these random numbers and we hash them
together to create our public key and we
and we give our public and then we do
something else with the public key so
anyone who knows the private key of the
public key is able to make a C
but this is a little bit naive because
if if people are able to make the
signatures then they can always then as
soon as you make a signature someone
else can copy your signature because
when you make the signature you reveal
your private key so it doesn't really
work but what we can do is we can put
this inside the snack yes and if we put
it inside the snack we can hide the
notifier in the secret and that means
that our signature scheme becomes kind
of yeah that I signature seam now makes
sense okay people can make signatures
and it doesn't reveal what their private
key so we can do this repeatedly yeah
okay
so but but now this doesn't really make
sense as I said before right because we
have we just people can prove that
they're a member of this group the
miracle that's defined by the root
people can people can prove that they're
a member but that doesn't really make
sense because we don't reveal anything
and if you give that proof to somebody
else they don't even know what itwhat is
talking about I mean they just know that
you don't they just know that you're a
member of song Merkle root and that
doesn't that doesn't really make sense
so what so what we need to do is reveal
the merkel root yeah and now it starts
to make sense
yeah and that now the Merkel root is
public to the verifier and when they
verify it they can see that oh this
person must know the private key of a
member of this of this group okay oh
wait what does it say is there some way
for me to know the time okay I can I can
see okay okay so so now we can use it
okay so this is already enough to do
some cool things okay this is already
enough to do to make a mixer okay so
this is what it makes me smart
contractors first of all a user deposit
and either into the contract and I and
then the contract will allow them to add
a leaf to our group yeah
then a user can use a snack to prove
that they know the secret information of
a leaf in our in our group and users who
prove this can withdraw coin and this
this work and because the only thing
that we reveal in the previous because
the only thing we reveal is the merkel
root there is no way for anyone to know
which leaf LED to which withdrawal but
there's a problem with this
so does anybody know what the problem is
yes sorry okay yeah that's also a
problem but that's not the one that's
not the one that I contrived to talk
about next
so yeah that's definitely a problem but
the way that we solve that is that we
limit it to one ether per deposit and
one ether Patrol and yeah so it is a
problem and there's wasted six atom and
we can talk about those in a while but
has anyone another a problem yes yes
exactly you can do a double spend right
because nobody because you just proved
you're part of the Merkel route yeah and
people can people and just take out
coins again and again as long as you're
a single member you can repeatedly take
money out because there's no there's no
sort of there's nothing to prevent you
from from double spending yeah it's the
double spend problem because you just
don't have information about about who
was withdrawn previously so okay how do
we fix this problem does anyone have any
ideas
yes sorry I didn't hear what he said
yeah that would kind that would kind of
work but if people because everyone uses
the same balance it doesn't really it
doesn't I could just deposit the same
balance as somebody else and just take I
could take all let's say one either is a
popular amount I could just take one
either is out a bunch of times but yeah
probably to nullify exactly so so we
kind of contrived to have this nullifier
here previously as part of the public
key and that's why I didn't just call a
private key so so what we do is we we
publish the nullifier yeah we make that
public and then in our smart contract we
remember that whenever someone uses a
certain nullifier we remember it and
then we prevent people from withdrawing
with the same nullifier twice and so
this actually introduces another problem
that we need to think about but it's
kind of outside the scope of the talk
but but the problem is that that there's
like a griefing attack here that's
someone could someone could see that I'm
trying to withdraw a nullifier X and
quickly deposit deposit nullifier X
again and then withdraw that and then my
would role would fail but this is a
griefing attack and it's like $1 for $1
I mean it's very expensive to hurt
people with it but yeah it's definitely
problem but but yeah there's ways to fix
it but it's kind of outside the scope
what we only talked about okay so now we
can check yeah so now every time we
withdraw we make sure that that coin
hasn't been withdrawn already okay so
that's how makes much worse I mean
that's that's that's that's exactly what
we have currently in the github okay so
we have some problems with that and I'm
one of the major problems is is who pays
for the gas right so the thinking is
that if I deposit one ether and then
later I deposit another either I need to
have gas in that account in order to pay
for the transaction fee of the
withdrawal and because I can't do that
yeah because now you have a chicken and
egg situation it's like I had this
anonymous money but I need non-anonymous
money to take it out so that becomes a
problem so so there's a way to solve
that I don't know if I talked about that
in the next slide or not no so the way
the way that we saw that is we do like
layer two transaction abstraction which
is oh it's actually called meta
transactions that's the new name for it
so what we do is a meta transaction
where people get a fee for broadcasting
these proofs and the fee is like a
portion of the amount of money that you
deposited okay so then problem number
two is that people can analyze the
inputs and the outputs to track the
users yeah and so this is more like a
temporal attack and you can use these
heuristics to let's say that let's say
that I deposit one either into the smart
contract and then I would throw that one
either in the next block I mean it's
very obvious that it's kind of obvious
who deposited yeah I mean you can't
connect them cryptographically but you
can come up with these sort of clever
heuristics about about how much you can
how much you can take in and take out
and that's part of the reason why I
prevented the having multiple amounts
because because if you have multiple
amounts the amount that you would draw
is also an indicator of who deposited
yeah and let's say that I've deposited
one point one five six seven either and
then someone later withdrew one point
five six seven either it's a good bet
that it was me it was my withdrawal I
mean what we want to do is maximize our
privacy set so yeah so that's that's
know there's some thoughts on that so we
have a proposal for the layer two
transaction abstraction and hopefully
we'll be able to sort of merge it with
with someone else's
but anyone that's kind of future work
that needs to be known okay so can we
allow multiple deposited sizes and
that's kind of that's kind of whatever
address and yeah it's also trivial to to
allow here C 2012 in deposits and
withdrawals but we need to be careful
about the privacy set again if these
tokens have sort of low volume then it's
unlikely that people will be able to get
these if these these transactions have
low value but it'll be unlikely that
people yeah I mean people might think
that this is really super private annum
and it might not be I mean it's just
something to be aware of when when about
these things because yeah okay and then
there's like other kind of further
research questions about how can we can
we increase the size of our privacy set
by being able to trade from one currency
to another privately and that would that
would be kind of cool I mean that would
that would sort of marriage are
separated here see 20 tokens into a way
that that we could into something that
makes a little bit that has stronger
anonymity properties but that that seems
that seems to be a difficult thing to do
but we can see that that sort of future
future work okay so so basically so
that's the end of mix Emes okay so so
that's that's that's all I really have
to say about mix mix for now so it's a
general token mixer that you can use to
mix your ether or your tokens so this is
this is this is like cool it's nice work
but it's a little bit it's not really
very it's very similar to see caches
work and I mean it's similar to things
that already exist I mean they don't
exist in material but it's like work
that's been done before and it's cool
but I would sort of search for other
ways to use snacks to do other things so
the thing that I'm actually more
interested in is is something called
semaphore which is which is very very
similar to to mix mess so so instead of
instead of depositing one either and
being allowed to join the tree we come
up with some other rule that lets people
join the tree yeah we could have like a
sign-in with github button and people
who sign in with github are able to are
able to join this Merkel tree and
and then they can make proofs about
things yeah and if they don't sign in
with and we sort of limit the amount of
members in the group so this this tree
becomes like a proof of github
yeah and anyone with github is able to
is able to make signals about things so
how do we do this how do we make like a
generic signaling application and the
way that we do it is so so basically we
have a lot of what we need already yeah
that's very similar to make suppose we
have the same public keys and private
key I should do the air quotes when I
say public key private key we have the
same setup and then we have a Merkel
tree where we aggregate all of these
together and then we put that inside the
snark and we add you see here you see
here in the we we've added the idea of a
signal so this signal is just like 32
bytes and it says it's the hash of
something that you want to say I mean it
could be the hash of a tweet or it could
be the hash of of a vote or it could be
a hash of something else yeah so we
include that yeah so yeah so we include
the signal but we still have another
problem and what is the problem
does anybody know yeah anybody else
so think think about the difference
between what we do it makes it makes a
mess like makes a mess is we only want
to use maximus one time but this we want
to use multiple times does anyone have
any ideas so the problem is oh yeah
sorry exactly yeah so the answer is that
you you you you if you reuse you we
force you to reuse the same nullifier
here and when we force you to do that
you can link different signals together
yeah so if I say if I do one tweet and
one vote the nullifier will be the same
and I will I will be able to link those
two things together and it still has
like it's still anonymous ish but
because you can connect them together
it's it's not really great because I
mean because we don't really want to do
that I mean we
to be able to tweet and vote and do a
bunch of other things and have them
disconnected from each other
yeah so the another pilot so how can we
fix this does anyone have any ideas
sorry
how should we the counter yeah that's
right
yeah so we are so we had this idea of an
external nullifier yeah
so we hashed the nola part with the
external nullifier inside the snark and
I mean this gets a little bit a little
bit messy but but yeah that works so we
have this external nullifier and we hash
the two together so now our expert are
our our new nullifier will be unique
because as long as the external
nullifier is different then each signal
is unique and we can limit people from
making multiple signals about the same
thing but we can't connect to say two
different signals about two different
topics together okay
okay so now I have two examples let me
see what time it is okay so this is this
is looking good so we can we can talk
about at least this example it may be
another so so like this is this is this
starts to get a little bit complicated
so let's do an example to make it to
make it a little bit clearer so so let's
do first-past-the-post voting yeah and
let's just think about that so
first-past-the-post voting is just where
everybody votes and then you count the
votes and whoever has the most votes at
the end of the count wins uh maybe
that's not exactly what yeah that's
that's what that's what I'm talking
about anyway I'm not sure if that's the
technical definition of
first-past-the-post voting but yeah okay
so so let's say that everyone in this
room comes up and we vote for some
decision yeah weather weather zero or
one
weather weather people thought to have
come was good or people thought that one
was bad good okay so we have this binary
decision and we and we come up with some
framework so we say that okay we all
agree on the same signal yeah and the
signal is wait yeah so we all we all
agree on the same signal and the signal
is that DEFCON is bad
we have another signal and that signal
is DEFCON is boo good yeah and people
can vote and we'll count up all of them
together and at the end we'll we'll
we'll see who thought how many people
thought everything was good and how many
people thought they was bad and then
finally we need to think about their
external nullifier so who thinks that we
should use the same external nullifier
four four four bolt signals okay and who
thinks we shouldn't use the same
external notify for both signals okay
okay so if we don't use the same
external nullifier for both signals then
then people would be able to vote I
think that one was good and I think that
one was bad and we'll have no way to
detect them so we need to vote we need
to have the same nullifier external
nullifier for bolt ok and this way you
can you you can link the votes together
which kind of sucks but you also limit
people from voting twice which is
definitely a good idea okay so now we
can let's talk about something a little
bit more complicated so we can also do
like proportional representation and
proportional representation is another
form of voting where when instead of
voting like having a binary choice you
can you can choose among multiple
multiple different choices so the idea
so that's that's a spanner or a previous
example where we had oh I think that
program was good I think that wasn't bad
and now we can add a third one I and say
that I think that one was okay but I
think I think we can do better next year
so that people can people can choose oh
actually that doesn't really make sense
I think I think I think it makes more
sense for like leadership elections so
let's say that we vote between an
elephant giraffe and a kangaroo to be
our to be our leaders okay and we want
it so okay so different people like
different animals more yeah
oh let's change one of them to a lion so
an elephant a kangaroo and a lion yeah
because this makes more sense okay
okay so okay so we're voting between a
elephant kangaroo no line right and we
want to pick yeah so some people really
some people really don't want to vote
for the lion so oh wait I'm explaining
the the benefits of proportional
representation and I shouldn't do that
because on topic okay okay so okay so
yeah so so basically we can do the same
thing but for the elephant the lion and
the kangaroo they each have a different
signal but the external no the fire
always stays the same okay yeah
so that really makes sense from it's
very similar it's a previous example
okay okay so let's just keep going I
mean here's the current problems with
with with some before so chemists so can
we build a proportional representation
where you can't link the votes together
because I mean in the previous example
it's clear that we have to use the same
external nullifier I have for each
signal and that kind of lets us that's
us link that oh I voted first for the
kangaroo and then for the giraffe and
then for the lion and that's that and
that will reveal information about the
electorate in general and maybe we want
to stop doing maybe we want we don't
want to do that yeah so that's one thing
but that's really complicated and can we
do quadratic voting like this that's
another interesting question there's
like a bunch of application for some
before that that haven't really been
explored again how do we pay the gas
that is if you do this if you do this on
chain but I don't we change stuff with
this but in general it makes more sense
to have it as an option of chain
scalability solution Ono obtained
signaling solution I mean it just works
a lot better because you have to pay
five hundred thousand guys for every
vote which is which it doesn't really
work very well okay and then can we make
deniable signatures so this is this is
more to do with like anti coercion
voting oh no bribery resistant folding
or coercion resistant folding where
where someone can force someone to
either through physical force or through
money to or they can pay them to vote a
certain way and this is about dayum we
all agree it's about thing and we should
think about how to solve it
and there's and there's some ways that
we can do it but they're kind of outside
the scope of what we're talking about
here but if anyone's interested to talk
about that we can talk about it later
okay so now now some more limitations of
the snark work that we've done so far
so the proofing time is is is quite long
for Maximus in semaphore it takes about
I have some numbers here oh wait no I'll
talk about that in a minute
okay so then there's okay so this is so
so now we've talked about makes a mess
and we talked about semaphore and we see
that we see that in that we have some
cool some cool things that we can do
with these so there's a point and
there's a bunch of like open
opportunities to continue this work and
to do other cool stuff with it for
example we could have a yeah so example
we could have we could we could build
this kind of group I mean we don't
really have any groups in semaphore yet
and it would be nice to have a group of
people who could signal about something
together and then we can expand it so
one way to do that is to have a like we
have to have a way to limit the amount
of people who can join a group otherwise
you can just join the group and and
signal about whatever you want yeah I do
sock puppet attacks and things like that
which we know soft but it's a puppet
attack is where it's where like you see
this really interesting discourse on
some social media platform but it turns
out it's just one person with many
accounts talking to themselves and it's
a way to sort of propagate your ideas
and force the discourse on the topic in
a certain direction and in general I
think this is bad and this is bad and we
should we should find a way to stop it
so one way the way to stop it is to
limit the amount of people who can join
the conversation but we also want
everyone to be able to join the
conversation we just don't we just want
everyone to be able to join once so
there's a bunch of ways to think about
how we limit people from joining them
and one of the and one of the ways is
although it's really it's really it's
not very strong it's very weak is to
have like a github based Merkle tree
joining and we have some other and then
there's some other ways to do it and I
can talk about those later okay so then
the next idea is to is to build on top
of some sort of membership requirement
to build on top of that and to make some
sort of social media platform so this
would be a little bit different than the
ones that were used to that instead of
having like a person who tweets about
something we could have a
it's a very impersonal tweet about
something we could have a group yeah you
would join a group and your group would
engage in discourse internally and
externally so you could see a group of
people discussing something and some of
the people believe something and other
people believe something else and I
think that if we remove like the idea of
the self from this I think we remove the
idea of this self from this then we can
I think it will lead to like more open
discourse so so this is like sort of a
philosophical tangent that I'm gonna go
on but this is this is what I this is
this is my sort of reasoning for this
it's not like in general in life it's
normally it's easy for people to
coordinate inside a group it's easy for
people to say oh listen I think this and
I think this and people have this sort
of healthy discourse and then they agree
or disagree and this is this is very
good for everybody but but sometimes
this is not possible sometimes like for
an example sometimes a minority inside a
group can be oppressed by the majority
and the majority can impose some sort of
costs on the minority when they try to
coordinate and it comes and and this
will lead to a point where with the
minority are unable to sort of even
admit that they're part of the minority
because they're afraid of oppression or
something like that or they're afraid of
some sort of consequence for this for
this admission and there's been a bunch
of rights movements that I've been
around that have standard around people
saying that oh I'm part of this group
and and revealing that and paying this
kind of high social costs but that's
like not very good for everybody I mean
there should be a way for people to
coordinate without having to pay this
high cost and one of the ways for people
to coordinate and not pay this high cost
is to make these like anonymous
signalling groups yeah and people can
say it can can anonymously say oh I'm
part of this group without revealing
which part of which member of the group
they are so they they they can't be they
can't be the victim of some kind of
oppression because they didn't they or
it's more difficult for them to be a
victim of some kind of oppression and
they're also free to sort of express
this belief and this I think is a
healthy thing for society in general
because people should be free to sort of
coordinate with each other and express
their beliefs and I think that when yeah
yeah okay so that's that's like the end
of the philosophical tangent but that's
that's that's that's why we need to have
these sort of anonymity system or
systems with strong anonymity properties
so I'm very interested in people are in
people who are interested in working on
this in billing things with time before
and please talk to me afterwards if you
are there's a bunch of but there's a few
people working on this and we're happy
for other people to join and there's a
lot of open opportunities so so then so
then we can have anonymous credential
systems and this is where you can just
sign into something without revealing
who you are and we can and that's a
whole other use case that we can have
then we can have reputation systems and
it's in fact we found a way to build a
reputation peace system where where you
can kind of exclude someone from the
group if they if they if they if they
break some rules so let's say that I
have like a VPN server and I'm like I
let everybody use my PP on server who's
in this it was in this room I at the end
of the thing I just go around and I
collect everyone's private key and I say
ok everyone's allowed to join but then
or some someone sites to use this VPN
all the time and they use too much of
the bandwidth and I have to remove them
from the system so there's this kind of
talks that this post here talks about
how we can do that and what we can do
yeah so this this post is each research
post talks about how we can do that and
and other things about that and yeah so
it's sort of the limits and trade-offs
and whether it is useful or not no this
is definition that we can go in with
some four seven four okay so there's a
bunch more stuff we can build with some
four and I kind of think that like not
enough people are working on this so I'm
happy to sort of talk with people
afterwards or during the question answer
session about this and yeah hopefully we
can sort of do some work together okay
okay so then also I want to promote this
ethnics so as Eric said SMX is this
theorem snark project that's funded by
the ATM foundation that are moving
forward with some of the the lower-level
equip the graphic primitives that we
need and they're doing a bunch of good
stuff and if anyone has some C++
experience or wants to learn a little
bit about snacks that this would be a
good place to sort of contribute
there's also Socrates and circum I I
think I have circum later but I'm sorry
Socrates it's also a cool project I
maybe had them later so so we also use a
or C 20 tokens
oh yeah so this is other things we can
fix with Maximus so we could make a pull
request to include ear see 20 tokens
ethics have re-implemented it being a
much more efficient way and it'd be nice
to sort of port their work to the
original repository yeah and then it
would be good to merge mix in seven four
together because they're so similar it
would just be good to have a single a
single repository okay and then then
this other work to do we can replace the
hash function which I'll talk about in a
while and then there's also a bunch more
some before use cases that that'll be
nice to explore and talk about okay so
let's talk about some of some of the
figures of what we have so so okay so so
the hash function so we need in order to
make a Merkle tree in order to make a
Merkle tree we need to have a hash
function and a hash function that we use
right now is a a 256 and char 256
it's very expensive to do inside inside
the snark because it's based upon binary
operations and I'm gonna talk about that
in a minute so improving time in seven
four is about seven minutes and the
Merkle tree the depth of the Markel tree
is 29 which means there's like 29 hashes
so that's yeah so it's quite expensive
but that a the tree is very big it's
enough for like 500 million people to
join so on my laptop it takes about
seven minutes and it needs a lot of
problems it's impossible to run it on a
smartphone and this is a problem so it's
about 50 K constraints per hash which is
which leads to 1.5 million constraints
altogether and this makes the proof this
is the reason why the proving time is so
so so we want to minimize the we want to
minimize the proving time so we want to
meet early so we want to reduce the
number of constraints so let's talk
about how we can do this okay so inside
of snark we can do a time we can we can
do this we can sort of check these
assertions
yeah we can check to sight Chinese and
sign kinds of assertions we can say that
a multiplied by B equals C and we can
check that we can check multiplications
and additions so we can also replace a
and B with a bunch of additions of
something else yeah where it can be the
sums of things yeah so then we can
already do cool things with this I mean
we can already implement every company
computation with this right because we
and the way that we the way that we end
up the end of doing it is okay for
example can can anyone think about how
to do how to design an xor gate with
this I mean maybe this is probably not a
good interactive question but this is a
good sort of learning experience to make
an xor gate at the start and just see
how you can make these constraints also
I have a list of these problems that are
kind of interesting to approach you at
the start so if anyone's interested in
that please let me know yeah so sha-256
is binary operator it has a bunch of
binary operations one of them is an XOR
and then there's like Sigma shifting
yourself and a whole other bunch of
stuff so what we do is or what other
people have done well the lipsmack
people have done it they've implemented
sha-256
they've implemented it in in lipstick
and and they've just built all the basic
gadgets and plug them all together so we
can we can we can already do this but it
turns out it's really expensive because
we just turn everything in a binary and
inside the binary we use we can just do
zero on one where we have we can
actually do a lot more expressive things
inside the snark so how can we can how
can we improve this so let's talk about
what we can do inside a snack so we can
do this a times a times B equals C where
a and B and C are all these items and we
can also but we have to be careful
because we have to we have an overflow
so snacks work over this prime field and
if we get to this number which is about
253 bits which is 253 bits we will
overflow I mean if we add one more will
overflow and so we wrap around at this
other number down here which is about
200 to 250 bits so a turn so that means
that we do all our arithmetic modulo P
yeah where P is where P is a prime
number so does anyone know how this can
be how we can use this anyone have any
ideas how we can use this to build like
an interesting interesting things this
is it this is a difficult question yeah
okay so it turns out and we kind of use
this to build elliptic curves yeah
because okay so if we take a look if we
take an example of psychic it's like P
256 K 1 which is about where P is to 256
bits all operations occur
so it turns out that we could we could
build a comparative elliptic curve
inside the snark and do and have all our
reason to take modulo P done for free so
so we just do regular multiplications
and additions inside this now I kind of
would turn out that that would be that
those those operations were done modulo
P so so why don't we do this with Zack P
256 K 1 the reason that we don't do it
with this curve is because they have
edge cases that the when you when you
try and double points okay so if people
are like strolling to follow that's okay
I mean this is this is this is kind of a
little bit difficult stuff and it's
gonna get easier in a little bit it's
just I'm just talking about how to build
these krypter krypter graphic primitives
for like two more minutes and then we're
gonna get back to the regular kind of
okay now we put this here and now we put
this here and how do we build things
with this okay okay so so the reason why
we don't use the reason why we pay so we
use it twisted Edwards curve yeah we use
it twisted Edwards curve down these are
the formulas neither point additions
Ouisa twisted Edwards curve because it
doesn't have edge cases when you when
you double the identity or you yeah when
you double the identity or you are their
identity to something else so in general
in science we don't want to have it if
we had an edge case we'd have to have if
we had an edge case we'd have to have an
if loop and if we have an if loop that's
that's not very good
inside the snark it's just really
expensive to do in a loop because we
have to do everything a times B equals C
which which is really okay there's
another example how do you make an if
loop with a times B equals C it's
totally possible but it's it turns out
that it's it's prohibitively expensive
when you do it a bunch of times okay so
this is the curve due to these are the
point multiple
so then okay so inside the curve we need
so we need to be able to do two things
to do a little cryptography the first
thing is to do point additions which is
easy we can use these formulas here and
we can implement implement those inside
the snack easily the second is to do
point a to point multiplicative
multiplication and we can do that too
it's just a little bit more complicated
and we just do a bunch of doublets
actually scalar multiplication just
degrades to to just additions well yeah
we can figure that out too and you yeah
we can figure out a 2 and we can use
window exponentiation
we could switch to window exponentiation
which will save us a lot of constraints
and add snags have done that already
there there now we come in the canonical
implementation although circum have a
competing one and Socrates are gonna
make their own implementation soon so
we're gonna have a bunch of these
implementations that people can use to
do electric art stuff I hope it's okay
that I said that okay okay so then these
are some links that will teach you about
elliptic curve operations and how to do
that and just a general background yeah
because this is I mean the last couple
of slides were generally difficult off
and it's okay that if you didn't
understand them I'm and now we're gonna
get back to that oh yeah so I just had
some future work about this so and then
we're gonna get back to the regular
stuff so I'm not sure that link is right
but you guys you folks can find it okay
so so future work so the first thing is
that this this this work should be
treated yeah this work hasn't been
reviewed and I don't think that anybody
should use this in production until it's
been reviewed a lot this is like the
rule in crypto waste or the rule in
crypto currencies is don't roll your own
crypto and I did okay so so please be
very careful about this also if you have
crypto cryptography expertise it would
be I'd be very interested to talk to you
about sort of reviewing some of this
work and so more people can use it but
at least we should say that it's
possible to do this kind of
cryptographic stuff inside a snark this
is yeah this is at least an example of
how that's possible so it's for pedestal
hashes and signature scheme which I'll
talk about in a second yeah so okay so
we'll be good to get some review and
here's where you can review it and then
there's possibility that we could build
bowler proofs in the same way and embed
them inside the snack and that's a nice
interesting that's interesting like a
research problem and then there is also
it would be cool if we could do like
recursive snacks or at least requires
one layer
and then we can do something like the
sea paper there was this paper recently
about using recursive snacks to do like
private smart contracts so that would
that's an also an interesting sort of
future future direction okay okay I know
also I want to say thanks to Dario
Hopwood and and for for help and advice
about this as well as the Z cash team
who had done who III who had done very
similar work before me and really lit
away from me when I was doing this it
specifically this issue you can see it's
so cool they just describe everything or
every single step of their
decision-making and then they also have
a blog post about about how to do so and
actually they're using it now in the
wild so they just had a couple of days
ago another they're using Patterson
commitments oh yeah so I should have
talked about that oh sorry okay so so
what can we actually use this to do like
what is the what is elliptic curve
inside it's not useful for and the
answer is as you said as you asked
Patterson commitments and and signature
scheme so on top of this on top of this
we built a I built a Patterson
commitments and signature scheme and
ethnics have also implemented it so and
zk are now using this in the world
they've had a daughter did although
their work is is a little bit different
than ours because they use the different
they do use a different curve and that
means that they're yeah so their their
work is not directly trans transferable
but it's still like a proof of concept
that this is possible okay so a big nice
alignment congratulations that I'm on
their recent hired Fork it's cool okay
so next we're gonna talk about we're
gonna talk about scalability so 20
minutes cool okay so next we're gonna
talk about scalability so so far we've
done so far yeah so so far we've just
talked about using using snacks for
privacy and now we're gonna talk about
using snacks for scalability so we can
so so the thing that we were missing was
a signature scheme before before that we
weren't able to really use it for
for privacy but now we can or for
scalability but now we can so here's
here's what we do we take the we take we
make this new form as opposed to before
where we had we just had the private key
be just this simple two images that are
2 2 this is just secret key that we hash
together we got the public the public
key we replaced this now with with this
new construction this is for this is for
a generic database yeah a permission
database so in the tree we have a B and
C and each a B and C has a public key
associated with it as well as an object
so the public key tells says it says who
is allowed to update this object yeah
and the object can be whatever you want
it to be it can be like a list of tweets
it can be your token balance it can be a
bunch of other things as well so this is
like a generic scalability solution
where you can update these leaves in the
Merkle tree in batches so myself yeah
okay so the way that this works is that
we have a single prover yeah and we have
a bunch of users and what the users do
is they aggregate signatures together
and know what the users do is they make
signatures and they pass it to the
prover and the prover aggregates these
signatures together and use and makes a
ZK start to prove that they updated the
Merkle tree correctly so let's see how
that looks
yeah so this is what they do they have
the old Merkel route then they have a
snark where they prove that everything
was done correctly that they did where
they validate a bunch of signatures and
then they have the new Merkel route yeah
and this proof is proof that they have
possession of these but that's so so
they so for example they can't update
the tree they can update and take
someone's money unless they have a
signature to send it somewhere so what
the user does if they want to send if
they want to update the leaf is that
they sign a E and B yeah and then I
stack those the following things ok this
Naik check that the signature match is
the public key pop key here and B oh
yeah
yeah checks that this signature matches
pop key generates the leaf B by hashing
with the object that that's that's that
the user probably also provided check
start that leaf is in the tree and then
replaces that leaf B with the new leaf e
okay so you see what happens you see
what happens you can go like this yeah
okay and what we do is we have a snack
that proves that before we had we had
root and now we have updated root so the
so we use a smart contract to verify
each transition and now the operator now
we now we know we have a smart contract
that validates each transition and now
and now we have a system where the we're
sorry now yeah so this is just a general
scalability system so we know and so now
the operator isn't able to isn't able to
update the tree on that's the users
allow them to unless the user gives them
a signature and says ok I'll take my
Leafs
a - a - yeah so that makes that make
sense I mean but this is this really
doesn't work as it is right because this
really doesn't work as it is because it
costs 500 thousand gasp to validate the
snark right and it costs like less than
ten thousand gasp to validate signature
inside the snack inside the EBM so why
would we use this does anyone have any
ideas okay so so patch yes patch them up
because the verification of a snack is
succinct
we can include as many as we want inside
the snack yeah so basically instead of
instead of using this for one signal
transaction we use this for like ten
thousand transactions yeah so we can
aggregate together ten thousand
transactions and we can and we can use
this to update the merkel route so this
is where we get our scalability benefit
yeah so now it takes five to five
hundred thousand got five hundred
thousand guys to validate ten thousand
transactions which is great I mean it's
great we're moving things are getting
cheaper okay so so now
just to summarize to link the
cryptographic so to cryptography stuff
to here so what we did before when we
define this twisted edwards curve that
we were using is that we we wanted to
make a signature scheme and we need to
make a signature scheme so the users
could sign something in the and and the
operand the prover wasn't able to just
sort of steal people's money and move
things around so we made this signature
scheme and now we just validate a bunch
of signature schemes inside the snark
and we update our route yeah old road
new route perfect so we do that okay so
we do that a bunch of times inside the
snack we have like a for loop and we end
up with just a single proof that we had
transition a to be correctly new routes
to new route correctly okay so what are
some problems with this okay so some
problems with this is is the proving
time so the proving time is quite quite
high I think you can prove on unlike
regular hard way to 220 million
constraints and that's about enough for
maybe twelve twelve transactions but but
that's not our limiting factor here so
because it turns out that we can use the
AWS Amazon Web Services to do two boxes
or another cluster yeah just an e
cluster to pass these transactions
together and to make the proofs but this
cost money but it doesn't cost a lot of
money it costs like $1200 for a proof
which is totally which is totally fine
if you if you doing $1,200 for 10,000
transactions that works out really cheap
yeah okay so and we can use Paris and
commitments it's difficult to have a
hash function that's efficient inside
the snack inside the VM but I should
talk about that in a while
okay so now our only problem becomes
this our only problem is now the data
availability problem yeah that we know
that the operator can't steal people's
money but we thought the operator is
able to be able to block people from
getting their money and does anybody
know how they do this yeah okay yeah
they refuse to publish it yeah they
refuse to put so so someone does a
Merkle tree update yeah
and then they refuse to update publish
to people the merkel leaves that they
need to make the proof yeah and when you
refuse to do that nobody is able to move
their money anymore
so now let's talk
about sort of solutions to this oh I'm
almost done
okay so so one of it one of the ideas is
is is this thing called roll up and roll
back
yeah so with roll up what you do is the
the prover continues to update the
miracle tree they do these transitions
and then Annie and then and then we have
this we have what we what it's called
yeah so it's similar it is similar to
pass my exists and we can we cannot let
merge and split leaves it's just like
it's just like plasma or cache I think
where you have like these independent
leaves and you can't join them together
but you can send them to other people
[Music]
okay so that's so one solution is roll
up yeah which I'll talk about in the
next slide and the other solution is to
is to pass all the data from the EBM
into the stack yeah and I suppose about
this and I'll talk about this so so how
this roll up roll back work and roll up
roll up roll back is actually called
nazma roll up roll back is the old name
so so we have a priority queue okay so
so listen we have so the operator
aggregate severence transactions and
they and they go block at a time block
at a time
moving forward with the chain and then
at some point in the future let's
imagine that our operator becomes
malicious and they refuse to publish the
the the Merkle path or the merkel leaves
that you need in order to exit your
coins so what do we do so we have this
thing called a priority queue a priority
exit queue and basically anyone who
enters the priority execute is able to
is anyone who enters that queue the
operator must serve that key within a
timeout that we define like a week two
weeks something like that and if the
operator doesn't it doesn't doesn't
fulfill that request what we do is we
slash the operator and we say that okay
data is now unavailable yeah and what we
do is we start to we do two things now
yes and we start the world back
mechanism so roll back okay so here's
the current his let me set the stage so
we have the operator has been running
for a while for five states yeah we
started at s1 where the one person
deposited one coin yeah and we know that
data is completely available then then
we move then we we started to move
forward the operator makes nag proofs
and validated them on chain and we ended
up at say five yeah
and I'd stay five the operator refuses
to share the data so I'd stay five we
enter the priority queue and the
operator refuses to refuse it to exit us
so what we do is we stash the operator
and we have this kind of option for a
new operator yeah someone else to take
over the chain um when you bid in this
option what you have to do is you say
you say the state that you want to begin
from the state that you want to take
over from so you don't have to continue
from state five you can continue from
any previous state so you say the state
that you want to continue from and you
say you say the state that you want to
continue from and you say how much you
want to put as your deposit yeah we have
liked this idea of a limited deposit and
something something like that that's
fine so so we finish the auction and we
select the the bidder who selected the
newest state with the highest the
highest bid yeah and then what we do
let's say that the new operator yeah so
the idea is that the new operator will
never will never ask to continue from a
state where they have all the data
available to them from the state where
they don't have all the data available
because they will be trivially slashed
immediately yeah and they'll lose all
their their whole deposit so then let's
say that their of the new operator comes
and they say okay I'm gonna take over at
say three so what we what we do we have
this transition from state 5 to say 3 so
what we do is we say that ok anyone who
has an implied transaction between state
in state 4 or state 5 is able to exit
yeah and we have another period where we
have this kind of plasmus dialogues that
where people come forward and say ok I
want to go I want to leave and that
works out fine so so then we roll back
to state 3 and the new opera continues
yeah and if no so if no operator comes
forward and says listen I want to
continue we just go all the way back to
state zero and that's just basically a
plasma exit it's more ordered though
yeah yeah ok
that kind of works but it's it's there's
a bunch of problems with that and one of
the major problems is that you can enjoy
and leave together for a reason that I
can discuss afterwards that people have
questions about it and another problem
with that is another problem with that
is like this idea of finality that you
you don't know that you you're not
guaranteed that your state is not gonna
chain rule back but we can have this
kind of weaker for now the assumptions
and you can say that listen if I have
all the data for a single for a single
state I know that if there's a I know
that someone will come forward to take
over from another state or I can come
forward and take over from that state so
people will know that okay we only roll
back a little bit okay so that's that's
kind of that's kind of how roll up roll
backs nazma that's how stance my works
okay okay so now the other option is to
do that availability inside the chain
and what we do is we just pass all the
variables from the EVM to the snark and
we verify we bear and this way no one is
able to no one is able to yeah this way
the data is definitely available we rely
on the theory availability guarantees
yeah about this this is kind of this is
not great for two reasons for some
reasons it's it costs a lot of gas per
transaction which sort of limits our
scaling not at the amount of proofs that
we can make or the size of proofs that
we can make but at the cost per
transaction so we limited by gas inside
the VM because we have to pay gas every
transaction that we include yeah yeah so
I talked about compressing here but I
all sort of leave out the new ones of
that but yeah we have to compress the
data to inside a bimbo compressing is
just hash together so that works that
works too and this is kind of the
approach that we've sort of moving
forward with at the moment so these
comparisons with plasma which I already
did okay and then I have two examples so
this is like alright let's finish the I
won't do the examples because because we
only have like five minutes a minute
left yeah okay so let's just talk about
yeah these two exams quickly so one is
you can if T and this this was done at a
hackathon in Berlin by a bunch of people
and I would say their names what I'm not
sure they want me to say their name so I
won't yeah
okay so yeah so basically they did and
not non-functional token with roll-up
ana works pretty well and we also are me
and a few people are working on making
some sort of generic token with this we
can just patch talking transpose
together yeah and if we were gonna use
that available in chain as I said before
and each each leaf has a variable amount
you can trade tokens for to each other
but not spit oh oh no users can split
two tokens that's not right that side
and users connected leap what the leaf
is no wait that's not this light is
wrong okay so let's talk about roller
problems really quickly and then then
we'll have some questions okay so so one
that one problem is that the proving
time is quite big and we need to
outsource this is quite long it takes
okay so it takes about it takes one hour
and a half to prove on AWS and it costs
like $1500 a little bit less than that
and we want to reduce this and we think
that we can reduce it but it will get
more expensive and then there's other
way to reduce it to instead of using the
cluster we can use GPUs FPGAs and Asics
and those are all open open areas of
research that or implementations that
I'm interested in to talking to people
about if people are interested in doing
that that's cool come and we can talk
about it
can we add strong anonymity properties
to this system that's another research
question because everything ok
everything is completely transparent
here just because we used to start to
aggregate the data it doesn't mean that
doesn't mean that we still have the
anonymity properties that we had before
so is it possible to add those anonymity
properties back that's another
interesting question so we have
optimizations yeah so it's it's
interesting it's this add snarks project
have done a lot of work with with these
these optimizations this is move forward
quite quite well also ID ID entry have
another implementation at sites are
working on implementation I need three
are working on implementation two
[Music]
yeah and we're gonna replace you are 256
with pedals and commitments in some
places good
so future work yeah so we want to
implement both approaches yeah so if so
many if there's if someone who's
implement interests in implementing the
other approach the it's not as my
approach would be interested in that too
and so we're interested in hearing about
generic other use cases other than just
scaling and tokens or tokens and stuff
like that I'd be interested to hear all
the use cases that we can use it to
aggregate transactions together and
aggregated like bolts and things
together I know that comes with a bunch
of problems still oh yeah we could do
that too non fundable token maybe we can
make an exchange with this request so
this is like a request so if we good to
have the guards cost reduced in the EVM
newarker for more security would be nice
so we use I'll be I'm 128 right now
would be nice to move to be LS the one
that seeker uses and that means we could
reuse a bunch of they're a bunch of
their signature schemes and stuff like
that and a bunch of their tools and we
can all just be working on the same
curve that would be great and it would
be good to have a hash function
pre-compile that that's efficient inside
the snark something like Patterson
commitments that'll be cool ok that's it
ok
[Applause]
okay so um do we have time for questions
yeah we have time for maybe one or two
questions okay if people want to ask me
more questions I'll just hang out
outside for a little while and we can
talk okay
okay so who has any questions yeah you
mentioned one possible use case is
quadratic voting and I'm wondering if
you have any like tight design ideas
about how you can ensure that someone
doesn't have create multiple identities
in order to skew quadratic voting okay
so there's like there's like some ideas
about this one thing we could do is and
it's a bit creepy as we could use like
we could use biometrics in order to
limit the amount of people who are able
to join our group but this is this has
problems too because people can just
make fake biometrics yeah so we'd have
to have some kind of real-world
biometric testing station and that's not
really very I don't know that has some
problems it's game of all the other
thing is that we can have a we can have
this kind of these kind of parties where
everyone comes and you everywhere every
attendee is able to join the group but
but that kind of limits us because every
attendee you could just get your friends
to come and take their take their keys
or take their position in the group
another thing that we could do is we
could have this like really high barrier
to entry and say that you have to have
accomplished X Y inside in order to join
but that's not very good either because
I mean sort of limits the amount of
people that can join and can be sort of
commit to it so yeah I I mean it's sort
of it's a difficult problem I think and
it's but it's one that's important to
sort of figure out and solve so I think
a good approach would be to do like some
sort of trusted Hardware with with some
sort of biometric database or something
like that I mean it's it's not very it's
not very nice but if we need to do
something like that we could do that
yeah the white t-shirt he asked first
and then is the stuff that stock wear is
working on could that potentially
improve the efficiency of this there's a
completely different right so they would
improve they would
they're proving time but I they would
prove improve the pooping time but
currently the proves are a little bit
big on it still I mean I'm totally
interested in and seeing what they have
when when they sort of when they're
ready for that but it's still it's still
moving forward I guess it would be good
to talk to you who's here he sort of has
some more more ideas about that yeah
okay cool sorry that's my time if anyone
wants to talk I'll be outside
yeah pour like the next
you