DAPPCON 2019: Why zkSnarks Aren't Enough, Taking a Holistic Approach to Privacy - Harry Halpin (Nym)

Transcript

how many people here are working on privacy technology how many okay okay how many people here would like to have some sort of better privacy in their product or code or whatever okay so so how many people here are using some sort of zk star stark ck snark okay just bulletproof something like that okay so a few people so what I'm gonna argue is a bit of a subtle point so I

really am really supportive of ZK snarks and I'm very supportive of hi-tech crypto in general and the wonderful thing about ZK snark says I think even Sergey Brin from Google said he said well it's amazing that Zee cash the cryptocurrency community put together this technology that was very cutting edge research and got it to usable code and a marketable product very quickly but there's been a what I would argue is a slightly unfortunate side effect and so I do agree privacy is a huge market

but the unfortunate side effect is when people want to add privacy to their their code they kind of think that like ZK snarks is sort of a magical privacy box or some magical technique it's a fairly magical technique that they can just kind of throw in and then all of a sudden they have a a private cryptocurrency so for example and what you've seen is if you actually look at how privacy's playing out in the real world it's not as simple as just adding a new cryptographic primitive a new cryptographic protocol that it's what we call a holistic problem it involved like

we have in the world of cryptography we know how to do proofs around well-defined adversaries we can show that something is secure under certain assumptions usually kind of crazy assumptions but assumptions that are probably plausible given what we've been doing for the last 20 or 30 years but if you look at the actual kind of real world hacks you know huge fines on Facebook because of for example password leakage this giant ooofff hack where ooofff bearer tokens a lot of adversaries to access you know a large 10% or 20% of Facebook's accounts which is like you know fairly large

fraction of all sentient life you know 50 to ten you know millions of millions of people and then if privacy is something that we really want if it actually might be a huge market I think we need to start looking at the broader space and not just fetishizing particular techniques or primitives even if they're really good so in the fundamental point that we're trying to make at NIMH technologies and I think the research community the privacy enhancing technology space has made for very long time is that any system there's different levels of abstraction

there's different things going on if I want to do a blockchain transaction I fundamentally need to first do a peer-to-peer transaction using you know some sort of protocol Datagram protocol usually UDP and that this transaction is simply networked peer-to-peer broadcast and that's happening beneath the blockchain so if you're using CK snarks using Z cache you're using monera whatever cool once the new version of a theorem comes out awesome we'll have like fast pairing base Krypton theorem we can do it natively I think as teching these people are doing wonderful work

and I really look forward to see it coming to fruition but beneath your blockchain there's a networking stack and networking stack can leak metadata and then also above your blockchain you're gonna be building gaps right after we are after all at Def Con and all of the problems you can use ZK snarks on your chain but if you're logging in to a system you're authenticating to a system adapt and that dap has a username and password or personal data and it leaks that data then it doesn't really matter if your defended on chain because it

might be keeping that data off chain or even on train in a way which is not safe so the fundamental point we want to make is that privacy is fundamentally a holistic property of the whole system and so on chain privacy it's like it's like the first step and it's a bit of really hard first step and we should congratulate the people Aztecs and people Koda the people at C Cash electric coin company Z cash foundation Manero research all the people are really working very hard to provide all chain privacy but all chain privacy is not enough we need application level prophecy and we lead the network level privacy and there are also kinds of applications like private information

retrieval data normalization techniques k anonymity which we're going to go into today because it would take ages but these things are also useful techniques that people should know about so the way to think of privacy is that we're gonna have a tool box and this tool box for bodies different tools and we want to use the right tool for the job we don't want to just use a bulldozer for every job because the bulldozer is inefficient maybe it's slow maybe we kill some trees we murder some animals whatever we could actually hurt our application by kind of going going too far and using technology which is not necessarily suited but we have at hand so the privacy isn't on I'm going to do

how many people here want to brief zero knowledge explanation before going any further no one some people okay we'll do a brief one so on chain and these are slides I think I got them from maderas versa so I didn't make these wonderful graphics the essentially on Jain issue Allen firms is really hard because the you take so sets you can just kind of hang out on chain you can watch who's sending money to who and you could analyze the ledger and while analyzing Network data is hard it requires someone like the NSA or chain analysis gathering all the network data and then going over it looking at on chain data you can download block

science obstetrics it's actually really easy you can do it at home even and there's been lots of techniques for the last few years people you know hung out on a Bitcoin Tolkein ah maybe we should like use mixers I think people use helix now I'm not really sure fresh addresses stealth addresses and these seem seem to cover your tracks intuitively but they don't really do it these digital traces remain in the UT Exocet and these can lead to Deanna Lamas ation attacks using traffic analysis and machine learning and what zk c cache as he case stark says they say in general is this

transaction valid and you provide you won't provide it you don't want to give some of the whole transaction to audit you just want to give a proof that there is a valid transaction that you didn't for example send a negative amount money or that all the account balances add up you haven't minted new cryptocurrency money these are the sort of things you need to prove and we're a little bit of confusion how many people here have heard of Schnoor signatures okay excellent so our store searchers hopefully maybe added a Bitcoin now I'm not a hundred percent sure but the way to think about zero knowledge proof is there it's amazing technique talk to Sylvia McCauley he invented it was Shafi and

other folks he's here somewhere from Al Gore and but the fundamental techniques are actually quite old so this is a paper from 1989 by Klaus Peters nor which essentially was called efficient identification centuries for smart car and this is the technique which anyone can code up although probably wouldn't recommend unless you're really bored but it's kind of worth the exercise and it provides the basis because I snore for Sigma protocols and Sigma protocols essentially are the building block for all zero knowledge proof based system so the way to think about it is that the CK Starks and CK Starks

and bulletproof so whatever new system they're gonna make up next year or these very advanced techniques but the very basic techniques have been around for a long time since the 1989 and that the technique which we can actually all understand is that I have approver and of a verifier the prover gives you a proof to say they did something like oh I sent you some money the verify says yep I don't know how much you sin I don't know you owned this key but you've verified I can verify that it's true without knowing the exact value or key or whatever data you're trying to hide and that's the zero knowledge property so it's pretty easy let's just use very simple you know

diffie-hellman whatever algum all keys a private key which is X public key G to the X the prover once the create was called a witness this witness basically they get a random number from the same everyone shares the same group they send it over and there's a challenge and everyone cons does the same thing which is sent back and their response from the prover if you look at step three here they don't reveal their X they don't reveal their key but they take their witness they mask their private key what's the challenge over of course the

fine the model define I feel at least in their response and that response it can then be checked using her public key which Rimmer and then basically they can check that the witness is valid and that the private key of the own the key the key that the private key is indeed knowledge apart key exists by Bob because Alice has this public key and can use a challenge response witness pattern to basically compute that yes yes is key and that's a very simple signature scheme there's really not too much going on it's three steps and there are some patents on it so when they were

creating for example ECDSA they change it a bit and what they really want what people really want is they don't want to have this many rounds so you see there's lots of back-and-forth together since witness there's a challenge as a response wouldn't be great if I just sit you one thing just a single thing and you could verify it and that's the signature and you do this pretty simply actually so you have the same setup and again it's very important everyone's very scared of Z caches trusted set up ok the ceremony seemed a little bit wanky I'll put it that way but like I I mean I was just odd and they do need this common reference string I I know

why they did it but trusted setups are used in more or less not all but a lot of common cryptography it's important member if when you have these like public parameters like a group or if you know RSA you need like an N and a Q you know these public parameters in general or chosen often from NIST standards or you know whatever someone gave you hard-coded in your crypto library which is often wrong and that these public parameters are effectively a trusted set up as well they're just a trusted set for RSA and not a trust and set up for zk snark so again even store not magic and it's a trusted set up because you're going to all have the same groups so there's a public key random witness but

step two is the real trick to make it a non-interactive where you basically just hash the public key and the witness and the message is everyone a little signature here and then you send that back with the response and the challenge which is again a hash not sent by ours but a hash that the prover can generate and you kind of concatenate it all you have message challenge response and then they could check it because everyone has the same hash function she can do a hash function over the public key the witness the message boom gets the seeds you can check them to see that sees that that C is valid so that's it that's a what it's

a very famous paper it's call I actually it's actually readable unlike many modern crypto papers by Fiat and Adi Shamir and it's how to prove yourself practical solutions for identification signature problems and you can apply this to storage as the snore Sigma protocol and you can get a snore signature and that's a pretty awesome thing so what's going on the Bitcoin very simple protocol everyone can understand it and I personally III like I'm really impressed by CK CK snarks but I also kind of like my cryptid be readable something I can feel like I can understand and code up myself okay there we go and so again what zero-knowledge juice is summarized it's

a key building block for privacy integrity you could do it interactively but you can also use tricks like the Fiat Shamir transform do it not interactively and that's really useful for signatures and you can only just do signatures you can use that trick to do hold transcripts all sorts of things and they compose well you can basically do sorts of tricks where you say oh I have send the different witnesses different responses I can do equality I can prove that to things that's that someone knows or equal I can prove linear relationships between these things and that's the sort of magic that gets you all the work of yen's growth and all the work of ZK Starks we can sort of say I can take kind of anything I can even take an

entire C computer program and I can compile it down to a NAND gate and I can use your knowledge to prove the results of that program and a NAND gate now and that's where things get tricky right so you can make that's the paper I'm sorry I forgot the reference it's the lib snarks paper by Eli Benz a scene of stark ware and other folks so you can do these during all she's saying non-interactive arguments and knowledge will you take that really basic setup that you know sure did back in 1989 with another trick from the 80s and you can basically say I can transform anything anything and to NAND gates and these circuits I can produce

proofs and that's amazing and that is actually magic almost I mean you could go through the paper it definitely works but the problem is with this approach is that sometimes it's overkill sometimes you may not actually need to do a full ZK start so for example often for example what we're doing in NIMH technologies is we want to do something very simple we want to say I want to prove that you just own a key I want to prove that you have an age I reprove you have a name and then I could do something a bit simpler so these are called anonymous with indication

credentials it's a whole field of research also going back more or less to the 90s mostly pushed forward by Jana common ish now add affinity for reasons I would love to know why but I assume they're cooking up something in a space essentially you have identity provider subjects relying party and you want to convince someone again it's a proof or verifier game that you hold a credential with attributes that satisfy some boolean formula for example that I'm over the age of 18 I live in Cambridge Massachusetts the proofer can't lie the verifier can't infer anything outside the formula and even if they collude it's anonymous so this is kind of kind of protocol flow the prover gets a

certified credential they the certify credential embeds whatever properties people have you show the protocol the verifier can then check with the issuer and say yep that's a valid that's a valid protocol that's sorry valid credential and this is a work where there's been tons of work that's happening in parallel to some of the very few people have I think followed this work up within the larger cryptocurrency aetherium space I think it's really worth looking at because you know tons of people don't wonderful work here the early work which was embedded into what was called Microsoft passport I think a sort of failed identity

initiative was basically single show credentials by brands and of course David Chomp where you basically blind some credential you show the credential but in the problems if you try to show the credential more than once you're you lose you're an M&E you lose your privacy so people kept working on it and using more advanced crypto this is the combination license kiyo work basically assumes ciel signatures to make simple orders say you can prove you know the signature over particular ciphertext and so you can't because you're sort of like there's no showing of the attributes and the clear you can't link multiple shows of the credential you can always ran

demise that ciphertext and it so you have a sort of blinded showing procedure that's really awesome to be even later work which I was working on up until fairly recently into 2016 called algebraic message authentication codes where you have an issuer you have an issue in the verifier are the same and you can blind a proof of Lady to Mac and it's very fast very simple speedy stuff but it's centralized and I think the main waiting about algebraic max is it's a Mac so it doesn't you the reasons fast it doesn't use asymmetric crypto uses symmetric crypto with some nice private e privacy properties and so what we're trying to Adam and some other folks are saying well rather than we would like to see a world where people don't use Facebook Connect but they don't log in

with Facebook using this ooofff base flow which reveals all the identity but they use a blinded token hamsa negation control which we can verify within you know milliseconds which holds attributes and is ideally more scalable and faster than standard ZK Starks and we're actually not doing a huge breakthrough if you're actually saying well do we really need to use CK Sark's this use case I just want to prove some attributes I can use much simpler math and kind of go back to these very simple non interactive schemes and we don't we don't have to go all the way to sort of

compiling things down to nand circuits I think that's a pretty pretty awesome thing and what we've developed is we've been working building off of the cocoanut signature scheme which was the Sanitary scheme that was done by george aneesa's and friends and then their startup was acquired by Facebook but the code and the papers all open sourced and patent free is that we essentially you know we want users to be able to use these credentials to authenticate without password to embed whatever tech what they want into it we want to restrict against replay attacks and everything else but unlike the traditional work anonymous invitation schemes it's decentralized so essentially we have different validators

is anyone here going to a chaos computer camp probably not one or two people okay anyway so if you really want me to I'm gonna give a whole talk on this at chaos computer camp but unfortunately I don't have time to give it here so I'm gonna speed up but effectively we what we do the trick we do I'll just go straight to the trick if you're a crypto person we basically use the same sort of hash trick the Fiat Shamir was also used identity based encryption but then we use the threshold signature so if you use threshold signatures you can sort of take a centralized thing and make it distributed and that's the trick that we use to kind of take the centralized anonymous authentication schemes and make them decentralized and we have this sort of complex scheme where you can sort of show that get some tokens you

can embed in tribute and the issuing authorities attributes sign them off multiple issuing authorities can sign them using some sort of threshold signature and you can see that everything over on this side is not honest but because you can reran demise getting this multiple ciphertext point that we made earlier you can show the service providers and they become anonymized the service provider can then the final step verify if they're true or not so we think that's kind of cool so sometimes I guess the the moral of this part part of the story is that z case snarks are great but sometimes you can actually use simpler crypto if what you're doing is something simpler such

as attributes so tons of crypto has been used so don't don't immediately assume you have a new privacy problem that z KS dark serve the answer you want to use the right tool but there's this whole other thing which was gonna mention very briefly because we're gonna run out of time otherwise which is this a bit of advertisement so Claude ideas and the audience somewhere there she is so she's getting to talk on the network level which I mentioned very beginning a talk and the the the network level is of course these UDP packets these TCP IP packets and what you could do on these kind of packets is you can do traffic

analysis you can watch the packets coming in for example if appear to a system and the packets going out and then you can use correlations between those packets to defeat privacy properties on higher levels of the system so like I said I'm using Z cache and I watch all the packets being shipped out by Z cache full nodes i watch what gets right into the blockchain and i use the timing and the IP addresses in these sort of things to try to dnr my z cache and a lot of people know about this z cache definitely knows about it if you read this e cache paper they say assume an anonymous authentication channel like you know a mixed edit or but actually assuming an opposite vacation channel

it's a completely fine and normal thing to do an academic paper but it's not enough for a real-world system folks like Manero have realized this they try to deploy Kover e which was essentially a branch of i2 p8 or like system didn't really I don't think it's worked out quite yet Bitcoin trying to use dandelion which is a even simpler I would say more VPN style system but all of these different crypto currencies are having to kind of think now that we have some idea of how to do all chain privacy we need to think a bit more about the network level and a brief preview of Claudia's talk at 4:45 it should go really deep into all this stuff okay so essentially that the lesson is encryption only protects the

content of a message but metadata is who is talking to who and when and there's a whole giant field of network analysis like signal intelligence traffic analysis machine learning ai which is very was very good at this point a Dean on amaizing metadata and at this point because there is no sort tor doesn't really disrupt the order of packets even systems like tor can be Dean Onam eyes using these techniques because if you think about tor for a second the first hop in the Tor unless you're running you know doing something with a hidden service is often

unencrypted like encrypted just with TLS at best and last hop out is also can be unencrypted or encrypted TLS and TLS does not provide really padding so all the you know TS TLS and tcp/ip fried streams these streams have patterns in them there's order of packets there's a timing of packets and you can use this data to look at the beginning of tor the entry knows the exit nodes and do traffic analysis attacks the dnr mice tor and so that's why this diagram the ESF is is clearly wrong because the NSA won't be looking at your at inside tour

itself they'll be looking where should the NSA beat NSA be in this diagram just someone tell me should it be we're should be yes you really as i said you'll be at the start you'll be at the stop and that's what it lets the NSA won't go from the middle it's gonna pointless unless they're doing some sketchy thing with CMU to Diamont analyze a hidden service so yeah so that's so you could actually because you have these fixed guards traffic's on the same circuit for ten minutes there's no delay there's no cover traffic these sort of concepts that claudia will talk about you can use that to DNR my store and there are solutions to this makes networking is the one that we're

particularly interested in where you basically the clot in the classical model you take messages then you kind of mix them up shuffle them if you want me to think about it and you could even do anonymous responses and serbs and you know you can't build sort of realistic things which are resistant to traffic analysis we use particular techniques rather than mixing we do timing delays but it has essentially the same effect and we think is much more flexible and probably much more faster in the endgame and it's very generic so it works with lots of different kinds of systems it's what we call generic anonymous overlay network but I don't want people to get give up hope there's actually a lot of really good work you can do on the network level and that's what we'll be

discussing at 4-4 or 45 I think and you know and some of these technologies are already part of Bitcoin the Sphynx message format also part of the genius Majoris denise's and in goldberg basically we have ways we know we can do provably encrypted packets that hide the routing hop-by-hop and make all the messages the same size and they use very nice crypto to do that again no trying to explain but essentially it's used in the Lightning Network already so even though the Lightning network isn't a mixed net probably should be a mixed net because the light network has a very exposed to paula g very maybe fragile on that level

they're using a very nice packet format and so as a final I guess the final moral of this story is that you know no none of the cryptos magic even it appears to be magic if you using crypto that you believe is magic should probably use crypto that you understand or you should find people and use their libraries and verify those libraries but if you're having issues with scalability of the issues performance kryptos are very wide spaced and you might go get some of those same properties using other constructions and just like you know not every problem

necessarily needs a blockchain although surprising amount find it very useful not every pro net every protocol needs DK Starks but a lot of protocols do but even if you're using ZK snarks there's other levels in reality that aren't covered by the abstraction that you may be thinking that you maybe think your privacy y'all have privacy also you really want to look at the full stack the whole level all the different levels because any level in your system can produce leaks produce side channels and then clever people can you can attack those leaks attack their side channels and use that to gain information key

material and metadata which is quite easy to get out of most systems which can be used to D naanum eyes and destroy the privacy of your system so I hope that story made sense have you take a few questions and then I think I have to go so anyone getting any response questions concerns you know we're working on mix nets so we have a github repo where were under development and when we get to the point where it's mature we're gonna launch it and it's a generic overlay Network cities like tor you'll just plug in and it will help the UNAM eyes your network levels for the anonymous within occasion credentials which I also talked about briefly those we demoed this

morning in East Berlin that github repo is already available probably need some more work I'm a little bit shaky so there's maybe some bits that could be fleshed out but the basic codes already there anymore happy to fork that code copy that code and look at that crypto could you oops sorry go for it whoever has the mic I don't know I okay okay go for it could you comment on the difference between what you're suggesting here and VOP ahrefs so the what verify verifiable oblivious pseudo-random functions oh yeah so those are used in a privacy pass which is the work so if I want to access to where the

problems you have at or is people say oh you're coming through some like weird anonymous maybe you're a spammer so verifiable oblivia vo vehicle ovens work sorry I remember yes yes okay I forget the exact name of the construction but it's so it's basically very similar it's a kind of enormous of the occasion credential however I think I'm pretty sure it's centralized I don't think they use threshold signatures to determine and so they're unlink Abul so I get a pass a privacy pass and that pass shows that I'm you know like it has certain protections so I can't constantly replay

it dah dah dah I'm a legitimate user by I'm unlink able to other my other usage of the system and I I forget the exact deals but I'm pretty sure that he doesn't use any kind of threshold sensors and therefore I don't think there's a cloud Fair flare is running a decentralized set of validators for use privacy passes I think CloudFlare themselves actually just kind of issues them and they use that construction to basically ensure the product the unlink ability of each privacy pass credential that being said you might bail take that's a very good point actually think about this your mind will take the techniques that are used in coconut or threshold signatures in general with a kind of some hashing ibe kind of tricks to decentralize

privacy pass good idea we should email Nick about that I'm pretty sure they're centralized most of the anomalous indication and credential schemes were not investigated by the cryptocurrency community because they relied on centralized authorities that's kind of main difference between coconut and the Newt and the older schemes and what the way to think about on the broad picture is that there's a trade-off function between like say ZK Starks which I have heavy computation but don't have centralized authorities to some extent and schemes like coconut which assume there's a set of authorities which are

always online is you kind of push them the computation off to them that's also a privacy pass does but then you can speed other things up thank you so they a lot of these things are trade offs or trade offs between computational computation time and availability is one fundamental trade-off we typically make okay thanks a lot I'm around all day hope that was useful