EB116 – Eli Ben-Sasson: Zero Knowledge Proofs

Transcript

[Music] this episode of epicenter Bitcoin has brought you by high. me protect yourself against hackers and Safeguard your identity online with a first class VPN go to high. me/ epicenter and sign up for a free account today hello and welcome to EP a Bitcoin the show which talks about the Technologies projects and startups driving decentralization and the global cryptocurrency Revolution my name is Brian faan Crane and I'm me Roy today we have got a very special episode for all of the

crypto nerds out there um when I started with Bitcoin I was reminded of Arthur C Clark's statement that any sufficiently advanced technology is essentially indistinguishable from Magic I saw Bitcoin and I thought this is technology that fits that bill it's a huge organization without an hierarchy it's a it's a Global Financial system and it's an immutable Ledger that was something very special that I found in Bitcoin when I started uh about a year into my journey in understanding Bitcoin I came across this other technology that which I also for which I also had the feeling that this is sufficiently Advanced that is

indistinguishable from Magic and that was the technology of ZK snarks now you might have heard of this name it is uh the upcoming currency Z cach or zeroc cach is based on this and it's it's going to be a currency that preserves fungibility by being uh completely private private and Anonymous so today we are joined by Professor Eli Ben Sasson from uh from techon he's a professor there and we are going to talk about some of the basic principles of zero knowledge proofs and crypto cryptography that allows zero cach to be built so we are going to talk about the fundamental constructs today followed by an episode on zeroc in the future but before we get

started let's first have an introduction from you uh Eli could you give us your introduction yes so hello my name is Ellie benon I'm a professor at techon Israel Institute of Technology at hia Israel um and and I do my research there mostly on math and the um theory of computation and um I also try to apply it in the context of various proof systems um such as um ZK snarks so H how did you become interested in in this area and what is

the the kind of importance of of ZK snarks okay so uh proof systems in general um are well known within the theoretical computer science Community to be as Mel just described it some of the most amazing magic that that came about in the past um 30 or 40 years in computer science and like many other colleagues of mine I got attracted to this field and wanted to understand the mathematics and you know the implications and how do you build these things how you analyze them and what are their you know attributes and limitations that's how I got into it uh some 15 years ago so what is a proof

system okay so uh a mathematical proof as you might learn it in a course in mathematical logic is just a string of bits that describes a proof um a little bit just like a computer program is a string of bits that describes a computation now the amazing um discovery that started in the late 1980s um called interactive proofs is that you can get almost the same mathematical rigor in a much more efficient way if instead of asking for a full you know proof as in a textbook in mathematics you are willing to undergo um the sort of proof um mechanism that

we see in courts of law where you know there's a defendant or approver in this case that wants to prove a statement and there's a verifier that you could think of him as the counselor or what's it called the The Advocate that tries to query and question the prover um and the goal is to find out whether the statement is true so in an interactive proof there is back and forth between prover and verifier and it's all in the purpose of proving or checking whether a statement is true and the amazing thing is that you can get proofs of any statements in a very efficient manner

that's much shorter than the classical mathematical way in the sort of courtroom style interactive proof system okay that that's very interesting so so normally one would have to provide a lot of data for example so to to prove that a certain thing computation was executed for example whereas with an interactive proof you you you could have someone question you and does does that mean it's like probabilistic does that mean like I'm going to ask you know a random set of questions and you know I'm going to get it right 99.9% of the time or or do you get the same kind of certainty as if the other party gives you the entire proof great question so

you don't have absolute mathematical certainty with an interactive proof that's something you have to um you know uh throw away so you don't have absolute certainty you only have probabilistic certainty but you could get that probability to be as close as you want to um to one and you do use Randomness in order to um facilitate this whole process and also it's very important that there's interaction between the two parties um so those are the three ingredients you use Randomness you have some probability of error it's not a 100% proof uh you know um mathematical proof

but it's as high probability as you you know are willing to accept and um you need to use um yeah Randomness interaction and there is probability of error what you gain is is amazing efficiency so uh so for our for our listeners um like right here when we when we use the word proof Pro um what you can think of mentally is kind of some of the proofs that you used to do when you were in school which are mathematical proofs but you must also remember that a lot of um Financial lot of financial transactions or financial U data can be also written in the form of proofs for example uh

what what just bear this in mind that the word proof is is is a very broad thing I think here and it could include something like proof of owning 100 Bitcoins for example that is also a proof right Professor yes whenever a computation is executed and reaches a result any computation any computer program that you run that got an input ran ran ran and then produced an output you could think of it as a statement the statement is from the input I ran this computer program and got that output that is a mathematical statement it's a very general mathematical statement and one that captures many many things you

know these computations could be any computer program and each one of them forms a statement and now we can prove these statements um about any computer program being executed correctly um exactly so you can apply it to financial statements you can apply it to statements about um healthc care you can uh apply it to statements or computations that are related to law enforcement uh you name it anything that a computer executes you could get a statement out of it that you can now prove uh using all kinds of um cryptographic proof systems so in in this case um to to verify a proof does that mean

that the the party that's verifying it have has to have uh you know all the input data that went into that function the answer is yes but you could sometimes have a cryptographic reference to that input data for instance maybe there's a large input file that needs to be you know used by the by the computation but to make things succinct you could run a different program that gets only a hash of that data file and now the execution is relevant to the hash of the file so you could cryptographically compress inputs to make them very succinct um but in at the end of the day um one has to start with a particular um

explicit input and reach an explicit output and then there's all sorts of auxiliary inputs that maybe you want to hide them using things like zero knowledge proofs so you start with some input you reach some output and in the middle you may use all kinds of auxiliary inputs that you don't want to be revealed so revealing inputs and outputs is an option it's not a something that you must do but it depends on the statement for inance Let me Give an example I can prove you know someone owns owns a Bitcoin okay you know I I won't tell you anything about let's say the the um any transaction or any pointer to any uh Bitcoin blockchain I could just prove to you there exists

some some Bitcoin own by someone well okay that's a statement that I can prove but in the context of a financial transaction that probably is something you don't care about what you care is you want to know that I own a Bitcoin that I know of a Bitcoin transaction and when when when you want me to say that to you you want to see what is you know some indicator of that Bitcoin transaction so you would want to see some input so so for example like like let's uh let's let's take this one example and then uh then go through what kinds of proofs there are so the simple example I want to take is uh like in 2014 U bitstamp The Exchange uh dat a proof of

solvency so they wanted to prove to the world that they owned around I don't know what it was around 100,000 Bitcoins or something the way they did that is they called Mike Hearn yes Mike Hearn and Mike Hearn came uh he physically went to bitstamp and um he actually verified that uh what which outputs bitstamp is claiming claiming as their own and he had bitstamp sign messages with private Keys corresponding to those unspent outputs so you know maybe there's like you know 100 outputs in the Bitcoin blockchain Bitcoin was bitstamp was claiming okay I

I own these outputs and I have the private keys so if you imagine me as bitstamp I'm trying to say that and then there's Brian who is like Mye Kar and he comes to me and he says okay if you want to prove that you own these 100,000 Bitcoins these 100 outputs then get those private Keys take this message from me and sign all of sign this message by all of these different private Keys then I go and sign and I send those signatures to Brian and Brian can check those signatures and say okay I agree that you have 100,000 Bitcoins spread over these 100 different outputs right so this was done in 2014 um now for this what's what's what's relevant

is we needed a human like we needed Brian to be there verifying it now what you're saying Professor essentially is this this whole process could be automated by having let's imagining an ideal program what that ideal program does is it takes inputs the private keys that bitstamp has uh goes to the Bitcoin blockchain checks how many Bitcoins corresponding to these outputs it has and then it outputs the value of the total number of Bitcoins controlled by bitstamp so the input is the private Keys there's a program and then the output is how many Bitcoins does the person who gave the input have right now

what you're saying is Bitcoin bitstamp can run this program on their end and generate a proof that somebody else could verify on their side and they doesn't and he doesn't need to be physic Al in with with bitstamp or communicating with bitstamp precisely yes and um these private Keys would would be what we would call in our papers and talks auxiliary inputs or a non-deterministic witness to take a more technical term so the the private keys that are used to sign these various messages are data that you do not want revealed you just want to prove that you know it

its existence so this would be auxiliary input to our computation this non-deterministic witness that proves knowledge of of the keys that control these 100 coins and the statement then is the statement being proved is there exist 100 keys there exists 100 Keys No One Is revealing them such that you know if they are plugged into the signing and uh verification of signatures algorithm all of them you know are correct and the total sum of them is whatever a th000 coins so the statement is someone executed the program and this program

output the value a th000 coins and that program is the one we just described the one that checks signatures and then sums up the amount of of value in the coins perfect yeah that's that's very interesting now just to take a little step back the term snarks uh there so there's the term snarks right there's the term ZK snarks like zero knowledge snarks and then they are there's also the term zero knowledge proofs can you briefly explain like what exactly each of those are and and how they are related yeah um I think there's a an abundance of of terms that talk about

very similar things and um um so zero knowledge there are okay zero knowledge there are a lot of zero knowledge protocols out there okay theoretical and a few are um implemented and there are several different names for them some times some of them are called computationally sound proofs and sometimes it's non-interactive zero knowledge and there's snars and snarks and uh I'm sure there are a few other um proofs of Delegation of computation various different names for things that are somewhat similar um so zero knowledge means that informally

means that the auxilary inputs that are involved in the computation all these keys and stuff that is not explicitly um you know produced as an output of the computer program um all this information is is hidden and kept private that's the informal description there's also a formal definition that is a little bit more involved and I don't want to get into so there are many many different ways to get zero knowledge proofs and then there are many many flavors of zero knowledge proofs according to what cryptographic assumptions are used and what kind of zero zero knowledge comes in several variants there are statistical and computational and perfect and in all

kinds of models and I think that as you go into different models and different setup assumptions for these systems you get various terms that um I'm not sure I mean the distinction between the various flavors is not something that the general public you know would want to go into necessarily okay no no that's that's perfectly fine then that that that's also a good answer so we we can we can sort of all lump them together and and we can you can know what we're talking about yeah non cryptographers I think you know calling them either ZK proofs or um snarks or you know there are other names for them I like to call them skip

sync computational integrity and privacy proofs but you know every there are similar variants of uh the same big phenomena of an interactive proof that is zero knowledge and uh you know proves that a computation executed correctly let's take a short break and talk about hi. me hi. me is a VPN provider and if you don't know yet why you should need a VPN provider let us help you I'm sure you like me and when all the crazy Revelations came out during the Snowden time uh of all the the spying that is being done by the NSA and other government agencies you were

shocked and you said not with me not with my own rights now the way government agencies can spy on you there's many of them but the most easiest way is by simply going to your ISP and getting all your traffic capturing all your traffic and the VPN can protect you from that it can give you a secure tunnel from your computer to any of the exit nodes all over the world so that all your traffic goes to the secure pipe that's encrypted and cannot be intruded on and with high. me you can choose any of their the 30 exit noes all over the world so you can enter the internet in a secure location the best thing about hide.me is that they have a free plan which

includes 2 gbt of unthrottled bandwidth per month so you can go to hide.me epicenter to create your free account and when you use that URL you'll automatically get 35% off if ever you decide to go premium Now the premium plans are really great they include unlimited bandwidth access to all of the 30 exit nodes that high. me provides and you can install it on up to five devices at a time so you can have this running on your phone your tablet your computer at work your personal computer and just be completely protected all the time and of course high. me accepts Bitcoin so we'd like to thank high. me for their support of epicenter Bitcoin so in this case like uh like when you're saying zero knowledge if you map it to the bitstamp example the zero

knowledge part is that when bitstamp is trying to prove that it owns 100,000 coins it has some knowledge the knowledge is basically private keys that unlock these different coins on the Bitcoin Network that is bitstamp's knowledge and then if I am a verifier of bitstamp I want to verify that they actually have this thing then uh it is in bitstamp's interest to not reveal any of these keys to me they want to prove that they own 100,000 coins but they don't want to reveal any of these keys because I can steal those I can steal those funds if I knew the keys so zero knowledge here means that they can send

me a proof that they own 100,000 coins while also not revealing their knowledge which is the private which is the private key so zero knowledge basically uh is is a reflection of that that they can keep their private keys and their knowledge secret but yet prove something to me about what about the nature of the knowledge that they have yeah so um I I I I I try to explain it this way if I make a statement like I own a thousand Bitcoins you're already getting knowledge now you know that I own a thousand Bitcoins okay now we and

you gain some knowledge from that now we start interacting I send you various strings of bits and you ask me certain queries and I send you information back and the question now is at the end of this extra process after you heard the statement what have you learned and in a zero knowledge proof there's a formal way of stating that you learned nothing you learned as much as if you would have asked me you know your questions and I would just answer with h you know 0000000000 z00 like you know some completely random string that's the informal interpretation of a zero knowledge proof where you learn what you learn from the statement but the the whole interactive or non-interactive or everything extra everything appearing in

the proof or in the snark or this extra information is meaningless to you from a cryp cryptographical point of view it's just as as tossing you know a few coins and using that thing what do you learn from that extra about you know do you learn anything if I just toss a few coins and and tell you the answers will you learn something about the keys that control my 100 Bitcoins no so that's the informal explanation of what it means for a proof to be zero knowledge it conveys no information beyond the veracity of the statement so anything you can learn you will have learned from the statement itself not from the proof so if you if you look at the the bit stamp example like there so who are

exactly the Actors and The participants in these things so is there just bit stamp on the one hand that would you know do this proof and then Supply it to some verifier who would then um I guess either run the proof entirely or they would be interacting with them so those would be two different cases or is that right okay so um a lot of work has gone into so we started talking about interactive proofs that there is a back and forth and it's really crucial um to get you know these Savings in in running time and all the amazing properties you really need the interaction but then people you know asked okay can we sort of minimize this

interaction or make it really really simple and and and and the amazing answer is yes you could do various things that will make the interaction very minimal to the point of only needing um a setup phase that is so it's like a thre message protocol or actually just a two message protocol there's a setup phase where some you know queries if you will are um broadcasted and then after that everything is non- interactive so after that there's just a prover um using the information that came from the setup

phase and using it to cook up proofs and you know sending them or broadcasting them outside to the outside world and then anyone can add their Leisure at their Leisure um you know check these proofs so there still is interaction but a very minimal kind of interaction I mean formally there's a very small number of rounds of interaction there's one publishing of um you know setup parameters and then beyond that there's only the proof sending proofs along with the statements being proved so it still is interactive but um you know very minimal

interaction so like uh like in this podcast uh before we jumped into this example you were going through uh this uh you're telling this telling this story about in the 80s you had interactive proofs and now you have these ZK snarks and the key takeaway like i' like to ask if this correct the key takeaway is in in the 80s if if there existed bitstamp and it wanted to prove me this thing in the 80s then we would have to exchange a lot of messages right I send I send him a query replies I send him again replies and maybe after a th rounds I'm convinced that okay this this guy actually has 1,000 Bitcoins what has happened over

the last 25 years is I don't need to keep on sending these queries receiving replies in order to no I can basically the bitstamp can just generate a string send it to me and I can read that string and verify that this is true that is the advance um not exactly so I think it's just it's more that um you know Theory progresses very quickly and there's usually in in advanced science a few decades um go by between an initial idea and even its implications and various improvements on it and you know technology making its way into the real world this happens all the time in

computer science for instance error correcting codes were started to be you know devised in this 40s and you know various other Advanced codes were then devised in in the 60s and it takes really like two to three decades for those things to show up inside actual systems even if um you know the things that show up in the end are pretty much known at the start so now to answer this particular question if you asked a theoretician in the early 90s you know if we wanted to do this um um this computation that you just did do I need a lot of rounds of interaction and so on and so forth the answer would have been theoretically not you know you know you

have very um very very good systems theoretical ones that work really extremely well have an even better setup we'll get to the setup um process later and and you know the trust assumptions um so even better things were known in the 1980s and 1990s but converting them into practice I mean a lot of the initial theoretical um uh constructions were extremely inefficient from a practical point of view so again to sum up in the early 90s there were very good answers that gave already non-interactive zero knowledge proof systems that had asymptotically and theoretically

pretty much the same performance as the snarks that showed up only recently but um the constructions were not efficient enough to be um done in practice now I should say it's not that research is not Advanced I want to um um so so the the the currently published version of snarks that's out there that zerocash uses and others um did benefit from several beautiful recent results that said something like this because uh these early constructions are a little bit too inefficient these constructions based on publicistic checkable proofs let's let's use additively homomorphic

encryption to bypass the problematic parts and additively homomorphic encryption is something that's been around for some time but this idea to use additively homomorphic encryption to speed up um the way you use problemistic C checkable proofs is a relatively new idea it started in 2007 and a work of two of my peers at techon yuali Shai and kushilevitz and uh a researcher from um UCLA Rafael ostrovski and in this beautiful paper um they said you know if we use additively homomorphic encryption we could speed up and circumvent various technicalities in previous um attempts

and this led to a long sequence of works that culminated in a beautiful construction By Gentry Garo um Paro and and rikova uses something that introduced something called quadratic span programs and quadratic arithmetic programs that really became quite efficient and they are the theoretical basis of the currently implemented systems the two I think most adopted ones are Pinocchio and lib snark so again in the90s they knew to do really amazing things theoretically constructions were inefficient 2007 uh marvelous breakthrough said let's use additively homomorphic

encryption to bypass certain technicalities that thing has led to very rapid progress that led to these systems uh that we use today um I should mention that the old school kind of systems are still very much interesting and you know we're still working on getting them off the ground as well perhaps we could we could uh so that's that's a very interesting history that that uh that theoretically it was it was there for 20 years and now only it has started to become practical as an like as an engineering solution to certain problems so we we we'll want to go into um what is the current state of implementation because a lot of our audience say are like programmers who

might you know someday want to use these systems so um they might want to know what's going on right now but before that perhaps we should go into um the setup phase like in your in your scenario you said that there's there's this setup phase that that is needed before in our case like bitstamp can actually generate the proof so what is the setup phase like okay so the setup phase I should say um and this goes back to you know the old systems versus the new systems so in the old systems the old theoretic theoretical systems that have not yet been um reduced to practice um in these old systems the setup phase consisted of picking a very short random

string and posting it so for instance practically speaking you could take the first 256 digits of of Pi and say this is you know this is the system setup and from here on it's non- interactive and everyone uses it okay um but again these systems have not yet been implemented the newer systems that you would use additively homomorphic encryption have a more involved and uh susceptible setup phase that you have to do really carefully in this setup phase um the parties running it are going to use um asymmetric encryption so some forms of public e uh cryptography to take um some

secret and cook up from it various queries remember we talked about an interactive proof where uh The Advocate is going to ask you know the prover various questions so with the use of additively homomorphic encryption um you take those queries that you would want to ask later on and somehow encrypt them in advance in a way that the prover the honest prover can answer them very easily and efficiently but um a prover who wants to prove a false statement will not you know efficiently be able to to answer this question so this setup phase involves some secret that if it is somehow leaked or revealed um you know

can ruin the system in the sense that knowing that secret that trapdoor would allow whoever knows it to you know Forge pseudo proofs of of any statement true or false so in the new systems the ones implemented like lib snark and Pinocchio and and Hawk and zeroc cach the setup phase is a really really critical one really critical phase that has to be carried out right and carried outright means that the party that runs it has to basically you know be unobserved and then destroy the computer or laptop or whatever it used to generate um the

initial um part in the interactive proof okay so so so to rephrase that like let's let's take the the the bit stamp example again and now let's say that mic instead of going by there and looking at their computers and all you know he was going to play that role but using you know zero knowledge proofs so let's say he he was participating in that setup phase uh to to as the the the party interacting with bitstamp do so that means he would have to have some secret you know key for the setup phase but if he you know leaked that to anyone then they could Forge the proof is is

that correct that would work but it's a little bit better so suppose everyone knows the computation for checking uh solvency okay it's a it's a well-defined computation so someone it doesn't have to be my current but someone trusted or some you know someone trusted by by everyone should um run the setup phase on behalf of everyone else and then you know publish to the world this is the key that everyone uses or the set of keys that everyone uses and then that person could you know disappear um now you don't there's no need for Mike Hearn or anyone else I mean everyone knows the computation everyone has the key to

proving and the key to verifying it anyone can run this computation and you know that um this company can run the computation and just generate the output along with the proof right but you still need that trusted party except that there's a different role for The Trusted party you The Trusted party doesn't have to verify the process doesn't have to verify the keys they just have to produce some secret and then not leak it right yeah they have to well they have they consume a certain secret which is you know just some random string and that random string is used to generate a um a key that is revealed to everyone and the important thing is that the random string should be you know just destroyed because if it is leaked uh it

could be used to forge um it doesn't break zero knowledge but it could be used to to forge um statements sorry proofs of any statement I I'm sure I'm sure uh the researchers including you must have developed some kind of Hardware or other systems that kind of give High certainty uh that uh secret has been destroyed for example let's say I I want to be U I want to do the setup phase professionally right like my I want to make my profession just setting up these zero knowledge systems and then destroying their secrets and then that's it and everyone can use it and that's that's what I want to do right now now

the world doesn't trust me obviously because uh to the world I'm just just a single guy in in a in a strange city they don't know of why would they trust me to to to to set set these systems up so uh have have the has the community developed some kinds of methods by which a gen set up a person like me could ensure the world that the way I've set it up is actually right and I've destroyed what needs to be destroyed uh unfortunately to the best of my knowledge no I don't have a good answer for that the best answer I have for that is so um my colleagues and and I in particular uh Professor Matt

Green Alexandro kza uman TR and mad's last year we published a paper showing how you can do multi-party secure multi-party computation to amort amortize this uh this uh harmful secret this trapo among several parties so for instance you know um we could all participate in this protocol and uh what we proved in that paper is that if even one of us is is honest in the sense that we actually do destroy um our computer and don't reveal the secret then even if the rest collude the whole system is still secure but this

isn't uh you know this isn't the ultimate answer that should convince everyone that things are okay because some Central agency maybe could listen could Eaves drop on all our computers or maybe you know maybe we will have a large enough incentive to actually um you know reveal the keep these secrets and and combine them together even if we do this multiparty computation protocol so um from a cryptographic point of view I'm not aware yet of any research that shows how to um in this additively homomorphic encryption system uh make sure that there's no key that can be used now where C you can do this the the good

news is that the good old systems the one that have not been implemented yet don't have this problem at all there is no trusted setup period you you you the first message is practically speaking I already you know can tell it to you it's the first 256 digits of pi or you know pick any other random looking string that's probably good enough for practical purposes and there's nothing that any of us can do that I'm aware of that could break such a system so there is hope Beyond the Horizon it's just not yet uh you know ready for practical use like zero cache okay that's that's interesting because I was going to say before well

with the bit samping example you know if you say like we don't want to trust my K to destroy that thing well maybe what one could do is just run it you know five times right five different people do it and then bitstamp has to prove it for each one but then what you're saying right is the even simpler way would be that sort of the five people together generate that secret and then if you even one of them is honest then bitstamp only has to verify it once and and you have that same sort of security exactly it's yeah so what we proved is that you if the secure multi-party computation protocol that we suggested is used then it's enough that just one party used the

you know destroyed the randomness that it put into the baking of this first message this these parameters that everyone uses afterwards and again ultimately when it comes to systems like zeroc cach or or hawk or whatever other systems are built using um the encryption based snarks you would have to I mean users and customers would have to use their own discretion and decision about whether they trust the party or the process that generated um the keys of the system to be uh trustworthy because there is no cryptography in that flavor of systems that that assures you that the key is okay today's magic word is proof p r o

oof head over to let's talk bitcoin.com to sign in enter the magic word and claim your part of the listener [Music] reward so uh so in this in this world of the The Trusted like let's call it the trusted uh party snark uh what are kind of the performance implications of of of doing something like this like let us go back to the initial definition which is like there's a program there's some input to it and there's some output and I have a computer that's running this program and I get an output and I want to prove to the world that

the output actually matches this input and program so I generate a SN so what what what performance penalty do I get and then if I send you this proof and you want to verify this what performance penalty do you have so the trade-offs uh very roughly speaking are that the approver pays a lot and the verifier pays very little or even uh benefits because um verification you know in the published um snarks is around 9 milliseconds is really really fast for any length of computation so theoretically you could take a computation that would take even without proving it you know a year or something really ridiculously large and cook up um

it's it's snark and still it would take only 9 milliseconds to verify okay um so verifier really really gains a lot um in or saves a lot now Pro pays a lot it's it's it's much more timec consuming to generate a proof uh than just to run a computation but of course you have to pay for um you know being able to prove something and um I I would say that currently you know within a few hours you could get a computation that's roughly something like um let's say up to a million cycles of a simple uh machine that's roughly where

we get stuck in terms of ram consumption so roughly a million comp million Cycles or maybe you know 100,000 Cycles some very simple machine that has you know small word size some some early version of an X 286 um I mean that's the kind of systems that we actually built and tested so for instance zero cache which puts our system pretty much uses it to its limit involves something like um you know 128 invocations of sha to 56 plus a little bit of logic so the big thing there is the number of invocations of Sha 56 and it will take you roughly an

hour to produce a proof that you ran you know 128 invocations of sha and did some minimal logic you know integer addition and stuff like that now you I mean I'm sure that our Bitcoin audience viewers know that you can do Shaw 5 Shaw 256 pretty quickly on Modern computers and I'm telling you that to prove that you executed it um with a snark be one hour for you know roughly a 100 sha so that's right what's the uh rate of that it's it's pretty small but you know you get zero knowledge and you get proofs so is isn't that a constraint

like if if I want to spend a zero cash in the future I want to spend a z cash coin does it mean I need to uh generate the proof that I have the coin and I'm spending it correctly for I need one hour to do all of these computations so in the academic paper you know as an academic I would say yes you spend one hour I I know that the you know engineering team is looking at various things like getting this uh you know numbered down and I'm I think that when you'll talk to um Zuko who's the CEO of zcash he'll probably be better suited to answer these kinds of questions but um everyone who knows computers knows that anything that runs

X now in an academic version probably when it gets to production grade and after optimizations is going to be much faster than x so uh so can you walk us through the landscape of uh landscape of systems that are available today and can be used by like very good programmers to experiment with these Technologies like you mentioned Pinocchio and lipn could you explain what else is there and what's the difference so I think the basic systems that I aware of are pretty much these two Pinocchio and lib snark um um there may be differences in the um licensing

strategies which probably matters to a lot of programmers I know I I don't know about pinocchios I you know the license that that that's used there but I'm sure it's it's posted there somewhere ours is an MIT open source you know MIT standard license so it's I think very welcoming to programmers and it's available at lib snar uh the GitHub repository um additionally those interested in playing with with other assistant um could could look at at zcash that has its own GitHub that uses lib snar and also um already has an alpha test net running so and and you know that's another place to use um

to look at code and use it and play with it um I am not aware enough of other basic systems that um other than Pinocchio and lib snar but you know there's Google I know of pinoc lip snark and I know of zcash I'm sure there must be others that already improve or forked or but I'm not the right person to ask we so we we mentioned zero cash right so that that would be one application to make basically something like Bitcoin but you know truly Anonymous what other applications are there for that this kind of technology and then what are the ones that you are

most interested in it's a very good question and it's one that's a little bit hard for me to answer because I'll explain why the things that interest me most are getting these things to be Universal which means it's it's a little bit like building a compiler so whoever builds a compiler if you ask them you know what is the program that you would like most to compile I'm guessing they'll say well you know all of them and you know I just want to build the compiler to be as good as possible so the mindset that that that we have is often more or less like this we first try to build Universal systems that apply to any computer or to a large class of computer programs and then you could look at applications that's actually what happened with with

lib snar first we published a bunch of papers about how you could get arbitrary C programs to compile into zero knowledge snarks and then we optimized it and downscaled the U not I mean downscale the functionality to uh but also optimize the speed and efficiency to uh build uh zero cache so any computer program as long as it's not too many cycles let's say a million cycles of some simple machine is probably where we top out right now is a candidate and I think the first things would be things within the financial domain so smart contracts you know not just proving things about statements but maybe you know that you pay taxes that you

um um you know that you can comply to certain regulations so certainly Financial applications are really really good for that let me say why because they're very simple as a computer program you know this is not loading up boots uh bootstrapping the Linux kernel it's just you know addition and subtraction of of integers right that's what money is about and um these computations are really important they have a lot of an econ a lot of economic incentive to them that's another good thing about them and um yeah so they're really simple and as computations and they're really important I think other domains where it may be interesting is

of course security and cyber security all kinds of things related to you know gateways and entry points to systems improving system Health uh other things would be in the health care area and as I said legal and government areas where you know privacy is really valued and important those are areas but you know when I go to the lab and and talk to my peers what what do we talk about not so much about the applications about getting the systems more efficient new new functionalities and so on so so if you look at this from a higher level would you would you say that zero knowledge proofs so basically always valuable when someone wants to verify

that the process is done in a certain way and that is done correctly without having access to some private data yes that's why I like to call you know that's why we called our Labs Skipper lab succinct proofs are short computational Integrity you want you expect Integrity from your computations you want the output to be correct and and privacy sucin computational integrity and privacy research Skipper lab that's uh yeah that's how I would describe it you want all computations to have their outputs produced with Integrity without cheating correctly okay that's great and so that sort of

ties into some of the the areas you mentioned right so if you talk about Finance or you mentioned that like uh for example let's say some Bank could prove that before every payment they check a certain database and the result they get backck was you know the person is not a terrorist or for example with the tax authorities that they could prove certain things about maybe how the money was spent like some sort of accountability to the public or or auditing function could be interesting right so that defitely so okay yeah and and what about the realities of this I mean do are you seeing adoption yes okay for my seat as a

professor doing research who before this only did you know only did math improved theorems I see a lot of interest from you know people like you I've never been interviewed about my work on propositional proof complexity and resolution and you know I've never been asked to be interviewed about and you know those are results I'm very happy with so I'm joking here but what I mean is think there is adoption but I'm also not the right person to ask because I'm not really you know a startup entrepreneur I don't really know what the trends are I think that from as a scientist I'm very excited to see that people outside you

know the mathematical theoretical domain of computer scientists is actually interested in talking about this and hearing more so yeah that's a sign of adoption yeah that's that's really a sign of adoption perhaps it's it's it's just just the nature of uh like distributed uh ledgers like you know whether they be Bitcoin or the ledgers that people are building for banks and we kind of see that this whole our whole space like a toz we are going to hit this big wall where uh we none of us have an answer for financial privacy like um like with Bitcoin what happens is uh generally bitcoiners are the people who care enough about having

something independent of government to say okay I'm going to willing I'm willing to potentially sacrifice my financial privacy to have this to transact in this system that's not controlled by a government but I'll be immune to things like the Greek crisis or the Brazilian crisis or whatever right and that's that's kind of the person I am but when when when whenever you try to go and say that okay A Bank should use a system like this then you know you get into a system situation where the banks already have give you Financial privacy and why why should they move to another system which doesn't so this is kind of our this is the reason I think there's a lot of interest into this line

of research because it it seems one thing that can tie untie the guardian knot really and uh allow this tech tech to go mainstream and you know careers to be made et yeah I think that this this hits upon a point that's common to things like like ZK snarks and to bitcoin which is that these are technologies that are very much for decentralization and for you know the little guy out there and anti-establishment whereas a lot of the world and a lot of business is about trying to be that trusted party the portal you know the portal where everyone goes to the hub

the central place that's how business succeeds and now the question is does do business want or need something like this the centralized thing I would say that past experience is the internet you know the internet is something very decentralized very distributed and uh it did spawn a lot of business um good business it is always constantly under these pressures that make it more centralized I'm sure some people would say it is already completely centralized and it's just one big scam I don't know I don't think that's the common view so there are these forces of centralization and decentralization always going on in society and Bitcoin

is I understand undergoing one of those spasms as we speak right you know is it really decentralized anymore is it controlled by mining pools I don't know I'm not a Bitcoin expert um I'm sure similar things can also apply and will apply to systems built on zero knowledge proofs and things like that so uh so a few a few applications uh Perhaps Perhaps you're not the perfect person for this conversation but I'd still want to pose a question anyway uh because I don't know who is to be honest um like I I have this feeling that um zero knowledge proofs could uh could help in scaling up things like Bitcoin

and ethereum like let me let me walk you through my thought process and tell me if it's right or wrong for example in ethereum you have these smart contracts right and uh like if I and Brian do do a smart contract so there's a program in in the middle of us that's mediating our financial relationship that program needs to be checked by all of the nodes on the ethereum network so there might be like 6,000 of them so it's one single computation repeated like 6,000 times across the network now the simple question I kind of get in my mind is this is a technology where computation can be repeated once done once and then checked 6,000 times that you know the result was

correct or not so it naturally seems something that could help like ethereum scale that you could delegate some of your computation to a specialized node and that node does the computation and it generates a proof and then all of the rest of the network just verifies that proof that allows massive scalability would you say this view is right I would say that it's completely right theoretically and now practically it remains to be seen it's very challenging practically because you know taking this ballpark number of roughly we max out at a 128 shot to 56 invocation so if you take just even a single block with thousands of of shatu

56 and you know thousands of uh ecdsa signatures you know we're not up to scale right now with that so theoretically yes it could compress you know again theoretically you could take the whole history of the blockchain from the Genesis till today and have a single 288 bite snark that attests to the fact that the you know you don't need to know anything just that all these transactions till the very latest state is okay theoretically practically um I think we're heading that way but it will be a non-trivial scientific and then engineering challenge to actually comp press um you know practical things that

could help in the scaling problem but yes I'm I'm very optimistic in the midterm and long term in the short term it's challenging scientific work that you know we're we're thinking about so what's midterm but in your definition in your Dictionary what is midterm well you know a few years as opposed to many many years and short short term would be you know a few weeks and then midterm is I don't want to give any you know dates or you know any any prophecies about when something may happen or not it's sometime in the future uh so perhaps like uh before the show me and Brian were talking about this technology and

we were we were having this discussion about how uh about how um like like like with ethereum you see that they have you have Smart contracts and with uh with zero knowledge you could delegate this computation to specialized node but for Bitcoin also we were we were thinking of this other example where um let's say like a miner creates a block and now the other nodes other miners in the network need to download this block verify it and then start building on top of it right and like if if the block is extremely huge like if the block is like 100 MB so let's say a minor in like shinjang Province China generates this block that's 100 MBS now

for that block if and I'm I'm sitting in Iceland and I'm another minor for that 100 MB block to come to me is going to take 10 minutes or 12 minutes and in that time that minor in shinjang has a has an advantage over me because he knows the block and can build on it but I don't know the block and I don't build on it and I kind of lose out so um so if you if you wanted to scale Bitcoin to a massive block size today uh uh you would have mining centralization like if if Chinese miners are dominating like they would communicate all the blocks to each other and then you know they have an advantage over a minor like me in Iceland now uh now with zik snack what we were thinking was like the minor in

shinjang generates a block and then generates a zik Sak proof that says okay the accounting in this block is correct and he just sends the block header like you know with the with the new Merkel route and the new utx output say has the block header and the proof to me in Iceland and that's just maybe you know 1 MB or 2 MBS so that comes very quickly like in 500 milliseconds and I can also start building on it so uh it allows the minor in Iceland to stay on par with the with the miners in China and then actually Bitcoin can scale the block size using this technology does that make sense again yes I think it does theoretically uh

practically I don't think we're you know we're not yet in the hundreds of megabytes of or hundreds of millions of of uh uh Bitcoin transactions but yes theoretically I think that's you know something we would like to do at some point when the technology is sufficiently efficient for that right the question here I guess would also be how long does it take you to generate that proof right because of course like that also delays how long it takes until you can s send it out to the rest of Network yeah precisely so that's that's actually the only that's the only um um bottleneck because length of proofs is

very small it's going to stay around 300 bytes for for these ZK snarks and verifying them is 9 mill seconds irrespective of these 900 you know uh sorry of this 100 megabyte uh so so it's really the only bottleneck has in always will be on the prover side and right now you can't prove um you know feasibly right within our lifetime a block of 100 million um transactions and then I guess another application could be when you talk about and I guess this this ties a little bit into the Hawk Project I think to have uh smart contracts run offchain right is

could it also be used for that yeah similar it's it's the same thing so you basically um say or for two-way pegging you say you know here's a proof that you know some some sequence of transactions was was conducted offline someplace and you know the all of them verified because the program that you're proving to me is the program that checks transactions and just reports you know final state is that whatever um that side chain now has a partition of coins along you know this small file or approve that Bitcoin will accept it says you can now um redeem a coin back in Bitcoin because something

good happened in a side chain without knowing um what went on yeah so one one other one other interesting thing that I I see in the literature around cryptocurrencies and zero knowledge proofs is um like U many people say that this technology is is something that is too complicated to be implemented by the normal developer right like like there have been like posts across Reddit in ethereum's blog that says that uh it is it is significantly involved and until you get to the point where a normal programmer can just use this thing and not worry about it just like we use our

operating system today and don't think about it uh it's it's hard to kind of spread this do do you see that as as another challenge for the technology not in the long run I mean you just mentioned operating systems we're talking over the Internet with Myriad complexities of you know networking and I mean that's all really complicated I could never W wrap my head around any of these things and yet it works seamlessly right I open up the computer I talk to you guys I have no idea what's going on you know Vision compression you name it so no I don't think um this kind of cryptography is any different it's advanced technology that just is emerging from you know the

science labs and it will take some time but the same thing happened to lasers and Rockets and the internet and computers in general so why would this be different the only thing would be if this is not useful then not enough smart people will try to use it and then yeah will it will rot on the shelves I really really hope that's not going to be the case and then you know you'll have a whole industry and people will use it and it's going to be all over the place that's my hope I I I'd say like if if if we as the blockchain industry survive you will find your use okay so uh yeah I mean the the the use

is is dependent on us what happens to the whole industry that's that's there today yeah no I totally agree I I think it's it seems necessary right if if you look at blockchain you look at smart contracts then it's just like well this this has to be sort of an integral part of of the technology stack in the future right and then it's going to be a challenge too to to because the blockchain stuff on its own is a challenge and then you add that it makes it even more challenging but you I think you're totally right if the incentive is big enough and there's enough at stake and enough interest in it people will make it happen yes I agree so Ellie thanks so much for coming on that was really

enjoyable and super interesting to dive into this topic thank you so much for having me I really enjoyed it and I'm glad I'm glad your field is uh you've chosen a field that is is generating such enormous interest it chose me okay so so for those who want to dive a little bit deeper into it of course we'll Link in the show notes to alie's papers there's a paper on snarks and also one on zerocash and I think we'll also be doing a podcast episode on zerocash in the near future with Zuko um and there's also some links to I think a talk he gave at a Bitcoin event

and we'll have some other the links in there also to his website where you can find the rest of his research papers so with that uh thanks so much for listening so we're part of the L of Bitcoin Network so you can you can check out lots of great podcasts about cryptocurrencies blockchain Etc on leof bitcoin.com and of course you can get uh enter Bitcoin on any podcast application or you can watch the videos on youtube.com/ enter Bitcoin and if you're a loyal listener if you want to participate we have this t-shirt contest if you leave us an iTunes review you can send us an email at show at EPs bitcoin.com and we can send you a t-shirt so thanks so much and we look

forward to being back next week [Music] n