ZKPodcast: STARKs & StarkWare with Eli and Alessandro

Transcript

[Music] welcome to zero knowledge a podcast where we explore the latest in blockchain technology and the decentralized web the show is hosted by me Anna and in this episode we sit down with Ellie and Alessandra from Starke where to talk about Starks first I want to say thank you to this week's sponsor

Pui network Pio a network has published a threshold cryptography rust library it is used in their implementation of the honey badger BFT consensus algorithm it can generate a set of key pairs such that for example any four key holders can collaborate to sign or decrypt messages but fewer than four wouldn't be able to honey badger BFT uses threshold signatures to encrypt lists of transactions for censorship resistance and to create random values that can be used as a defense against some attacks to learn more about threshold cryptography and how to use it check out the latest poa network medium post at medium comm slash POA - network so thank you again POA network lastly if you want

to support this show or if you want to just get in touch our links as always are in the show notes now here's our interview with Elly and Alessandro this is an episode that we've been very excited about recording for some time Starks first hit our radar when we were doing our research I think around the first zero-knowledge summit and it's come up repeatedly through our zero knowledge series so the episodes that we're doing on zero knowledge topics I would say just for our listeners this is a relatively advanced topic so if you want some background into zero knowledge proof CK snarks and maybe some other zero knowledge systems check out the

series on the noubar at zero knowledge dot F M but now let's start our interview with the guys from Stark where Elie and Alessandro thank you guys for joining us thank you thank you very much for having this yeah so maybe we should start with a quick intro do our normal thing and kicking off talking a little bit about yourselves and how he got into the blockchain space I'm having been sassoon my involvement in the blockchain started many years ago though I didn't know it at the time when I was doing my postdoc around 2001 and MIT and Harvard I started getting interested into something called the PCP theorem

probabilistically checkable proofs and it's a very mathy topic thats related to what later became to be known as Starks and I've been interested in this topic ever since for the past 17 years or something like that and slowly over time what started off as very abstract mathematical theorems and understandings got reduced slowly into code and systems that are very relevant to block chains because they allow one to solve problems like scalability and privacy in block chains did you come to it from a

computer science background or a math background like what was your angle into it good question I was doing theoretical computer science which is sort of somewhere in between it definitely uses very mathematical formal methods but to answer and address questions that are about computers and computation all right Alessandra how about you all right hi I'm Alessandra Casas I'm a faculty member at UC Berkeley and I do research in complexity theory theoretical cryptography and applied cryptography my background was initially first mathematics so that's my I did my undergrad at MIT in mathematics though after that I switched to theoretical

computer science for my PhD and ever since I have done research I been involved in research around the topic of aristocracy actual proofs which le mentioned earlier as well as a cryptographic proofs which use these tools to achieve strong privacy in efficiency properties some of which are again strongly related to two Starks that we'll discuss today so I'm very curious to hear when did you guys meet and how did stark where happen so it was summer of 2010 Alice found I was back then a professor at Technion Alessandro

was I think starting his PhD under Sylvia my colleague at MIT and he came to spend the song at Technion and we work together back then with the Iran formal was from Tel Aviv University and Daniel Jenky who was a student the technique of the time when we two started hacking at it and it's been already eight years since then well there was a very fun date years and that was certainly a very fun summer and also should you keep thanking Ellie for hosting me then did you was it then that you kind of realized that you wanted to do something like stark where I mean we had a much I mean it would be it would

be in an overstatement to say that we had a very fuzzy understanding of applications and we were barely you know getting to the point of okay let's see if we can even sort of run this in a way that it halts on any non-trivial computation like this was sort of things were just too slow but then we didn't know as I mean nowhere near there a number of things we know today about the entire space of applications and possible techniques a lot has changed even though we you know we had a good place to start from but at least from my point of view I had no clue in the world and no hopes whatever that any of that stuff would be even close to practical or interest any

outside of academic circles and even inside academic circles I have no no idea why someone would you know be interested in what we were doing serious amazing it was just it was just this like you guys were just very like there were very few people into this stuff I imagine at the time so it was like oh cool there's other people doing this thing I'm into I don't know what we were thinking when we started to implement its its curiosity the challenge was it was great actually I remember when we submitted a paper about one of our early sort of works on a PCP efficiency and I still remember one of the reviewers from the conference

that sort of commented on our paper as something like laying siege on the problem of PCP efficiency because I hit the paper just gave off this aura of like immense and possibly hopeless work on this problem so yeah like two years or three years after we had you know so much work and we were able to prove a computation that does for operations where each one of the operations is do nothing and it took the prover like 10 hours this was after so much sweat and blood what was the beginning of stark where

when did it start and what is it for what is stark word therefore so yeah let me just say briefly a little bit about the company incorporated exactly one year ago four co-founders asanga myself Michael reactive who's the chief architect liquid oh he's the CEO but now we're about 20 people in the company almost all of them are in engineering and they're steeped deeply in math and writing good code we incorporated to use a starts in order to solve scalability and also privacy that problems in watching we raised 36 million dollars in

two rounds of equity from a bunch notable entities paradigm that our second round we also got the size of all grant from the theory foundation and our first move is going to be to deploy at the end of q1 a solution for scaling Dex's by putting a verifier on chain and the prover node being off chained and later on we would like to offer Starks for scalability later on for privacy as well across multiple block chains and then as many use cases as we can afford to put them on are you looking into other like it Starks gonna be the center

of all of these systems or are you also doing research on other zero knowledge systems our focuses Tom starts when were of course the deeply steeped into Z cake Starks and Z cache and we're fully aware of other beautiful developments and our area bulletproof and recurse and snarks and other things because we I think try to explain we think there are some core attributes of Starks you know the transparent nature post quantum securely the efficiency of the approver and verifier that makes them a really good kind of technology for solving scalability and privacy on long chains so that's gonna be our main

focus in your future I have a question sort of for both of you what got you originally into blockchain technology or when did that start to really come into your purview okay I mean it was around 2013 2014 and the culmination of that was zero cash paper the point was that if you try yeah we were already deeply building I mean both of us together were working since 2010 on implementing various kinds of proof systems snarks and what later became starts and if you go around trying to look for examples where this makes sense and then can use in the

conventional world of banks health care institutions and so on they are occupied by big trusted parties and their it doesn't make that much sense to add this new technology as it does for block chains and in block chains it makes much more sense or to put it more starkly that forgive the pun if you go to people in the conventional world and tell them oh we have this new thing you know it's your knowledge pulse and so on someone can prove something to others then they will start asking wait who's gonna prove what to whom is the bank gonna prove to you that they're okay or

the other way around and if you go and talk to people in the blockchain space the last you where's the code you know what do you use it here are five things we need to do with it I guess the space is just like a perfect trial ground for all of this stuff that's cool yeah I would second that in that I mean earlier on the theoretical value of these notions of sort of proofs that certified long computations there are themselves you know very short and easy to verify a third legal value was very clear and so the potential use cases could in principle be many but obviously you want to try to figure out which ones are actually most compelling and clearest to the public that maybe could have you

know more impact in this case an application to money was rather a convenient because it is a notion that everybody understands so I don't you know it's always hard to look back and and rationalize the way sort of things go but I think it was maybe not not too surprising that the first is a real application which was the zero cash protocol which both Ellie and I co-authored with our other great colleagues was something that not only was I think academically interesting protocol it was the first time you could realize fully almost peer-to-peer payments but also it was a that many other people found interesting and

eventually sort of something that was was born purely as an academic paper eventually became a startup that was both of us co-founded also a few years ago and eventually turned into something real and here you're talking about you're talking about Z cash right I mean the use of so highly efficient and in this case also private a a cryptographic proves to do something useful in this case was protecting gas or user privacy because it has to do with a notion that is everybody understands money then it is a great sort of a place to start experimenting with this technology as opposed to some I don't know potentially arcane notion of compliance between banks and governments I mean like who cares right I mean it is important of course but it

is much less of a easy story to communicate I guess you also don't have to worry about all the stakeholders and the politics so you'd have to play in order to get those other agencies on board what you're talking about here is Z cash and the zero cash paper that you guys co-authored about two months ago we had Zuko on the podcast as well and he told the story coming much more he was definitely coming from like decentralized storage and it was this zero coin paper that was his first turning point that led to this did the zero coin paper also crossed your path that this was this something that also kind of brought you into the space so it definitely crossed their paths and the

zero cash paper is you know in early talks I often described it as the team of zero coin our team which was doing back then ZK snart's and but we didn't wait for Bitcoin or for the zero point paper you know as is often the case in science there are many different efforts that don't necessarily know of each other when they start so for instance I mean Alessandro and I on our co-authors have been working on on our stuff since 2010 and around 2013 which was before the zero cash paper we sort of were trying

to find places to you know market our let's call them ZK engines right then dawned on us that you know decentralized cryptocurrency is back then it was pretty much only a Bitcoin or an ideal place to sort of market this kind of technology in science because the lack of trusted parties there really demands you know powerful cryptographic tools and then we did here of the zero point paper and we you know and I guess they also heard of us and we immediately sort of approached each other they knew much more about you know how Bitcoin works for us it was sort of a bit newer we had

this shiny new engine that you know we've been studying the theory of implementing the ZK snarks and sort of you know was a match made in heaven but particular you know why should acknowledges your cash paper was you know certainly I mean each of each paper on its own is a contribution and then zero cash may not have been possible without both the the expertise and contributions of prior lines of work one of them on anonymous a digital digital cash that includes both 0 car zero coin and and other papers that came before it as well as on the other and the others line of work all this work on ZK snarks

it was like a really great collaboration that led to greater efficiency and greater privacy actually so for example before zero cash it was not known how to fully hide everything about a payment but that's something that we did we did manage to design for zero cash one ask if you were ever part of the Z cash company yeah we're co-founders and we we took an active role in technology transfer at the very beginning obviously you know we you know we're also researchers and so we don't we didn't participate in our day to day basis but you know at the conception and when you start a company there is a quite a bit of work that goes into then you try to

set it up in such a way that it can be successful through the abilities of early employees which it hasn't you know we sort of there's a wonderful team working at Z cash now both the zero queen and zero cash papers this is all about snarks which is where you guys were working I guess that was what you were working on at the time how did you get from snarks to Starks and I'm really curious about this like at what point did you decide actually let's put snarks kind of on the shelf and let's like focus more on these Starks which was like an older and older concept maybe we can also talk about the history of Starks in that yeah so he it may seem from the outside that you know we were first working on snarks

and deploying them in Z cash and then moved on to starts but that's actually not the you know this is what maybe the public sees from the outside from the inside was if anything the other way around and also you know it's a more complicated story so Starks go back to what's called PCP techniques and you know both Alessandra and I have been working on them actually even prior to working on on Starks and we never gave up on them and we never gave up on you know start research either what happened is that you know smart technology matured earlier and was deployed in Z

cash and start technology you know has fewer cryptographic assumptions and hence is a little bit harder to actually deploy in practice to a longer time yeah you know I would also comment and zero cash as a protocol doesn't particularly care what cryptographic proof system you use to instantiate it what matters is that you use something as efficient as possible so it just so happens that when it was written and when the wait when the company started sort of the a a most sort of a suitable a primitive on the shelf was the case narcs but you know we love all this to give it really proof systems and we try to improve all of

them because they are so far they they they have slightly different trade-offs any already alluded to the fact that hysterics make parsimonious use of cryptography and so we'll discuss this later how it relates to maybe post quantum security and other advantages but because in Ziggy snarks you kind of make a have your user cryptography you could go farther earlier in terms of efficiency and that's why they were kind of ready to go earlier you know we still work and so all these technologies and yeah right now maybe there's an emphasis on starix I should add that at least my case I certainly felt greater personal motivation to make progress and research

starix after the experience with Zee cache because it highlighted the difficulties of dealing with trusted set up in the real world just to remind the listeners for in Z cache because it uses ZK snarks there's a need for a trusted party to conduct an operation at the beginning of time to generate system parameters to be used for proving and verifying and this trusted party if corrupted you know could generate valid looking proofs for false statements and this is the reason why in the real world you get around this problem using real world cryptographic ceremonies will distribute the responsibility of generating the system

parameters to a collection of parties in such a way that only if all of them are simultaneously colluding this will happen but if at least one participating parties is honest than this the set up is secure in Starks there is no such thing okay you can just agree on a hash function which is the only cryptography that reduces and and deploy the system so it was very compelling the the prospect of a getting to the point where we have as efficient cryptography proof system that we can just go and use without any of this mess I certainly felt you know a great personal motivation to try to go after this goal that we were anyways pursuing already but you know probably there was some sort of time dependency there in terms of emphasis I want to know very before we dive in even deeper into Starks where

does where does Starks come from we've talked about zero knowledge proof sand we've talked about the origin of snarks but we've never actually talked about the origin of Stark's so yeah so I mean starts go back to works in the early 1990s pretty much you know some famous works of but by researcher a brilliant researcher from Chicago and levine sega t fort now from the early 1990s already pretty much said that you know using these new techniques that that are called you know the PCP theorem and things related to that you could already reach amazing scalability in which once approver writes down a

proof the verifier can check it exponentially faster in this holes actually for any reasonable conceivable computation I mean formally for any language and non-deterministic exponential time sorry for the math that terminology it but it means for any for any reasonable and conceivable computation you could speed up the process of verifying it without any trust assumptions by an exponential factor and this was completely mind-blowing at the time so this was already in you know 1991-92 short parentheses sorry only if you pull up the paper and you can there are

certain sentences there that are a very visionary so he here's one this state already in the abstract a single reliable PC can monitor the operation of a herd of supercomputers working with possibly extremely powerful but unreliable software and untested hardware this is hinting at this exponential speed-up where you have a single PC that by virtue running a verifier is able to check the correct computation of you know a herd of supercomputers Michigan are supercomputers there they have many more resources so already back in the mid-1990s it was known how to speed up the verification process exponentially right but what took another what is it

twenty years or so to reach was how to speed up the process of generating the proof so that the verifier could enjoy an exponential speed-up in checking and this took a pretty long while and a lot of uh you know breakthroughs were needed along the way and all of this you know culminated in the end in code base and systems that are what we call starts so again thirty years ago already the exponential speed-up and verification was understood but generating the proofs was a big challenge it still is this challenge but by now you know we've made enough progress to

actually work with subsystems that have a lot of other good benefits they're plausibly post quantum secure they have pretty efficient proving and verification time they have no trusted setup and very minimal cryptographic assumptions and they're you know the parts in them that are proven mathematically to be correct or rather a large portion of them so they're very little or very few assumptions and the assumptions are kind of pretty well understood I remember when I think it was when Z cash was launched I started digging into it trying to understand how it worked what it was and I was watching

several talks I watched one talk on Starks I can't remember if it was you Ellie or else under giving the talk but anyway it was a breakdown of sort of experiments with Starks and their performance characteristics and kind of going over how they work and the examples were you know it was like oh well yeah I can see why this is not reasonable right now where it was like Oh to do the simple computation you needed a hundred and thirty gigabytes of RAM or something like that and you know it was just like not tractable whereas whereas snarks on the other and was completely reasonable to compute but had

this sort of toxic wastes thing has Starks moved on from there like I know that we're not really talking about E in that range anymore I mean it's already much better as far as I understand and compared to I don't know how long ago this talk was let's say three years ago or like what are the boundaries right now for Starks maybe two one high level point there is that something that has changed quite dramatically since maybe let's say 2014 2015 which is around when a Zika started is that alien eye on our colleagues have

introduced new models for realizing start so while in the 90s you would build Starks from this PCP is that that a Lee mentioned today the way you do it you would rather do you would rather instead the design an interactive PCP or a multi round PCP essentially it's a it's a more flexible model within which you can achieve your exponential speed ups and within which it is much much easier to in relative terms to make it so that the prover can generate this proofs for the verifier and so while a few years ago yes we did have this prototype systems that would take hundreds of gigabytes of memory that is a cell extent not the

case anymore we have much better constructions and it's not just because more time has passed and we've written more papers but also something qualitative has happened it wasn't even an inflection point around 2016 where we introduced this notion which we call interactive Oracle troops denoting the fact that there is an interaction within the proving the verifier it's just a model okay heywhere these proofs are generated and then this interaction gets compiled into like a shortener interactive proof and producing the the information for this interaction is much easier than it is for PCP is so the numbers we would have today we we don't know how to achieve with PCP is alone so this was something new that happened from the 90s it's not just perfecting

90s technology it is moving sort of beyond that yes it's important for me to add and stress that I mean only you know this interview perhaps it's only me and under sandal but there you know we have many very important co-authors going with long way back I mean specifically I wanna highlight and mention you know the involvement and contribution of her or co-founder Michael E octave who is a PhD under me at Technion and you know there are many other co-authors that and of course we're you know as they say Dwarfs on the when the shoulders of giants and you know this goes back a very long way

so I just don't want the listeners to get the impression that only those speaking honest you know podcast yeah far from it also should highlight it's a my Michael is a student was a student of Elliot at me also highlight where my students an explainer who also you know played a major role in in some of these works so we've started to talk about Starks in comparison to snarks and some of the sort of new features of Starks just in terms of its usability but can we I'd love to use some time to just dive into Starks you have gone on stages explaining Starks you I can just imagine you have to do a lot of

education and communication around this so that people understand what it is how would you explain Starks on a podcast with no whiteboard this challenge so I'd say first of all a stark is a special kind of very proof so first of all maybe what's what's the proof so a proof I mean imagine you're going out of the grocery store and you're holding you know the receipt and you're looking at it and maybe summing up the you know the items and checking if the some that you were asked to pay is correct what you're essentially doing is verifying a

proof the proof is the receipt and it is a proof of computational integrity it's sort of asserts and and proves to you that the some you were asked to pay correct so how do you verify you're summing up the items and you're really just really executing the computation okay but it's a proof now for our listeners who probably know about blockchains let's jump to an analogy you know the block chaining world you are you know you want to verify that I mean someone told you that over the past ten blocks you know she earned she has gotten hold of ten coins right so what would a receipt or a proof look for that it

would probably be something that has all of the transactions in the last ten blocks and then some of them are highlighted you know with with like a marker those are the transactions that account for her funds and then she would also probably need to prove to you that she controls the keys that hold those funds so it's a very you know it's a very long kind of receipt and would be very hard to check and it would also compromise her privacy and you know you now you know a lot whole lot about her coins so okay Starks give you a way of generating a receipt for you know holding ten coins in the last you know

ten blocks without showing you first of all which coins they are and without giving you all the information and the transactions that went there but still you get the same assurance that it is correct so it's sort of a very succinct received very short but shorter than the computation you would need to do to find those coins and still it has the same level of assurance that everything is correct and has computational integrity so this is a good sort of high-level overview and explanation of zero knowledge proves how they apply to these systems but I'm curious to dig into more detail on what the difference is between

let's say snarks and Starks because what you just described can be achieved with either if I understand it yeah good point so maybe one way to clarify the relation is to note that a stark is you know some extent a special case or snark right so it is a snark with extra properties that we like okay what are these extra properties that they make this is a subset of constructions particularly appealing one is that the trusted setup is to some extent trivial okay its public there is no toxic waste you only have sort of public randomness in terms of concrete terms in the real world these public randomness would simply come from agreeing to use a

certain hash function for example chat with the Sikhs or ketchup or Blake you know some hash function that we decide to use as ours to some extent source of public randomness okay so you see this is a special case of trusted setup now because the setup now looks like this then it is very easy to deploy because we don't need to do try ceremonies to agree on a hash function now because this is the only cryptography that astark users you also get the additional benefits one of them is plausible post quantum security I say plausible because of course you know we don't know if and when a new understanding in the efficient quantum algorithm say would

prove otherwise but it is this is normal in cryptography when we talk about post random security for any primitive within plausible post quantum security so why is it the case that using this type of cryptography could suggest post quantum security it is because hash functions such as chat of d6 and Tkaczyk they don't use algebraic structure yeah the most part algebraic structure which is typically what efficient want to algorithms exploit to sort of gain speed ups over classical algorithms so these are two advantages that pop right out from the feature that we're only using sort of this knowledge break hash functions in our construction I mean one way to see a difference between start

and snark is maybe to look at the you know what the acronym means so both of them have Arkin which pretty much has the same meaning the letter n in the snark means non integer active which means that it must be a one-shot proof in a start you don't actually require that you could have it be non interactive but you could also have it be interactive so not all Starks can be snarks that's what it not all snarks can be starts because the letter T stands for transparent which means that you have no trusted setup and basically it only uses what's known as public randomness so there are some settings in which a start can be a snart than a start can be a start but the

differences are very important start requires no trust at setup that's one of its core properties and whereas a snart requires it to be non interactive only a one shot you know message so that's essentially the difference between a start gonna start the most important to the public part is the lack of a trusted setup which is a requirement in stocks when you say that it can be interactive would that mean so we we've done an episode where we talked about the interactive proofs and then the non interactive proofs but if you're saying that Starks could be interactive would that mean then you're having a

conversation back and forth between proven verifier until there's like a probabilistic yes but but probably better it would be to use a blockchain okay the transparency in a start means that all the verifier ever since is basically public randomness or you know as long as we have a source of randomness that you're willing to trust that could be what the verifier does so let's move to a blockchain in the blockchain you actually have this sort of temporal event of you know a new block coming with some block header and something that can be assumed and it's already assumed and you know practically

by all blockchains to be pretty random so in blockchain you could definitely instantiate a start in a setting where there's a first message from the proofer then you wait you know from let's say six blocks to transpire then you get randomness from the latest of these this goes back to the prefer any completes the proof and this actually has a lot of benefits both from the theoretical point of view because it means that actually the systems are a little bit safer the assumptions that you're making when analyzing this are a little bit better and more well understood you only need collision resistant hash functions as opposed to using the random Oracle apophysis and another even more practical implication

is that you could conceivably work with such a start with a lower security parameter so you could work with the probability of error of only let's say 60 bits of security rather than under 20 or 80 bits of security which would be required if you want to make it to one shot you know non interactive setting so there are theoretical benefits to using interaction especially over a blockchain and there are actually also practical implications to using it okay and we already had a number of you know projects that we talked to that you know we're telling us oh we are anyways using interaction and randomness from the

blockchain so why not use it to make things both safer and more efficient and we said yeah you could definitely you could definitely be doing this with the stock there's a lot of people trying to use block headers for randomness and with varying success there are a lot of attack vectors like miners can can choose to manipulate the transactions in such a way that they affect the randomness I'm sure though that you've thought of and I know many others have thought of other ways to achieve randomness on a blockchain that's sort of the the hype right now is how to generate randomness like public randomness and there's a lot of research and effort going into that like what's

called beacon chains and random beacons and BLS signatures so generate randomness and things like yes I would I would maybe you know counter that by saying that if a blockchain is already dealing with the issue of generating randomness and says we you know are generating a beacon of random this one way or another anyways because we need it for all those other things then you could plug that in to a start right and exactly I mean so so even I mean I I'm just sort of in my head seeing all the people crying out about using block headers as randomness because it's it's one of those things that like all the core devs always complain about but we

are I mean they're complaining but we are using them even in Bitcoin right you are using part of the input to the next you know block header is different locator so we are already using this and I think it's pretty unavoidable I mean we don't really know of any good way to completely resolve this but as a practical matter we're all using you know various sources of randomness that we understand that they are not none of them is perfect yeah yeah exactly I mean we we currently don't have anything better and and that's I think that's eyes like this there are better things in the works and you could plug that into this structure I think that's an important note yes you'd mentioned that Starks are post quantum secure are

snart's not post quantum secure the ones that are currently deployed they are definitely not and now there are a fair legal constructions that rely on assumptions that are believed to be a post quantum secure but those are sort of you know so most of theoretical value so far and practical value it may or may not be fulfilled in the future but the ones that are currently deployed most definitely are not a post quantum secure is that because of the randomness or is that because it just even even if you put the trust set up aside it simply has to do with the fact that the cryptographic hardness ultimately relies

on something called the discrete logarithm problem over you know finite abelian groups and quantum computers can actually extract discrete logarithms efficiently while under suitable settings classical algorithms are believed not and so this diff Frances what creates the sort of quantum insecurity yeah I mean to to tether this maybe you know as a good rule of thumb to the listeners any crypto system that relies on things like it's hard to factor a number it's hard to find the discrete log and other things that are have this number theoretic flavor of

things about you know prime numbers and factorization so quantum computers if they ever reach up to scale are known to efficiently break such systems so RSA diffie-hellman key exchange elliptic curve cryptography and this narcs used by easy cash as well as other you know you know more recent suggestions such as the beautiful bullet proof says your knowledge system they rely on such hardness assumptions and they are known to be attackable by quantum computers as we said the Starks make much leaner reliance on cryptography and essentially they only need things like you know hash

functions and we don't know currently of quantum computer attacks that completely break you know the security of hash functions so that's why Starks or plausibly post quantum secure if the post quantum quality something that you think about a lot or is this just one smaller feature of Starks right now what we really benefit from is the the fact that we make a lean use of cryptography we're only using lightweight cryptography this means that overall for example the prover is easier to optimize because you can it is easier to bring the relevant algorithms closer to metal

okay you can optimize them more and more because you're not making use of heavyweight cryptography and so so they're all sort of things a bit faster and you know in the future maybe it's even an easier task to realize these algorithms directly in some sorts of hardware which is something that may happen it would be relatively harder to do that for other things like snarks that make you public-key cryptography for example okay what's going on security I think it's a it's nice you know it's as researchers we take a longer interview of our work so it is a pleasant to know that whatever we design today may you know if efficient enough and interesting enough

withstand the test of time I think that that is wonderful but you know whether it has an immediate impact today that's that's probably that's clear the post quantum part the efficiency part obviously made you mean its impact I wanted to just bring back a little bit and talk a bit more about comparison and how these things are actually constructed so in in all of our previous episodes on snarks and they're not recurring systems we talk about these circuits of logic gates and you know the this particular algorithm is this many gates or whatever and or this system can handle this many gates do you still construct a stark in the same kind of system and if so can you

take the circuit of like let's take the z cache circuits and use a stark instead or are they incompatible how does that compare yeah I think it's a really good question so one of the core challenges in core magical attributes of the start is that the verifier nor no one on behalf of the verifier ever unrolls a circuit so basically the verifier gets a very succinct program that could specify a very long computation and that's all the verifier works with in a snark some one it's called the you know generator

or they you know the entity entrusted with generating the parameters would unroll this computation into a circuit and generate something you know one element per gate and start this does not happen so we had to work much harder in order to allow the verifier to check the very long computation without ever unrolling it and the way this magic happens is you use a a lot of beautiful linear algebra related to succinctly presentation of groups so again I apologize for the math language but that's really the best way I can explain there is succinctness

through structure and the structure is algebraic structure and that's something that is heavily used in this start by the way don't worry don't worry about using math stuff I feel like I think our listeners are gonna love that actually they're gonna even if it's challenging they'll be like I'm going to figure this out the analogy here is whether you expect so you have some statement of interest of computation okay and the way that it is represented in Starks typically not known Starks is you just unroll the computation you literally lay out every gate and every wire and actually what happens during the trusted set up is that trusted part he looks at this layout of the computation and kind

of encodes it this this is basically a system parameters that go in the sky for everybody to use to prove and verify okay but you don't have to do that necessarily right there are computations that are easily specified with much less so think about the difference between the lines of machine code that it takes to specify program okay that's just basically specifying the computation at hand versus the cycles it takes on a machine to execute this program so you could have many more cycles and you have lines in your machine code okay so Starks work with some algebraic analog of machine code okay so the very fire only has in mind this algebraic

machine code even though it is checking the execution of it okay it doesn't have to think about enrolling it this is where the exponential speed-up comes a fraud doesn't have to do this work explicitly it's only all implicitly done using the algebraic structure that Haley mentioned earlier that that's very interesting so you can sort of almost think of it as there's this you know starch assembly language and you have a stark VM and every program you know written in the assembly executed in this VM automatically gets a proof yeah that's exactly you know not not exactly but this is the exact and I sort of a high level analogy or this is at least what I

even think okay in my head so do you have to associate mathematical concepts but this is precisely what's going on it's we have some yeah algebraic computer relative to which you're proving statements without enrolling them so Alessandro I actually saw you speak at he was in San Francisco at an event that the decrypt capital guys were putting on and you had used the term snark instead of snark or stark so what's a snark so snark literally means succinct no interactive argument okay this denotes proofs that are short and easy to verify in a that are written down but not interactively sometimes we

also discuss snarks with the K at the end and the difference between this is rather important technically though from if I'm a high level perspective it's not not a big deal but let me just at high level mention what is the difference the K at the end it denotes that actually all of these cryptographic proof systems whether we're explicit about it or not are not just proof systems they are so-called proofs of knowledge this essentially means that for example that if approver is proving to you that a certain image of a hash function it has has a pre-image they themselves know the preimage is not a just it exists of

course may be a hash function has a pre-image to a given image that's generally true because hash functions for example compress so sort of almost everything in there in the domain in the range has a pre-image but in cryptography it's important to know that the person generating the proof actually knew the the secret the or the piece of information was trying to assert a knowledge of this is known as proof of knowledge and sometimes in talks because this is a technical notion we just shove it under the carpet even though we use it all over the place it's important to know technically these must be proofs of knowledge to be used in most scenarios but you know it's a rather slippery

concept so just sometimes ignore it so we've talked a lot about Starks we I think we've managed to uncover a little bit of knowledge haha but like we said you know did there's the oldest information about like oh it's you know Starks aren't fast enough eating and snarks are not fast or too big or whatever there's obviously a lot of work has been done it's gotten a lot better since a few years ago because of like actual new research but you as a company in this individual researchers I'm sure you know have huge plans what are the problems right now that you're you're

trying to solve and you know when when are we seeing Starks in use everywhere so completely we're trying to do it start where is you know by the end of q1 2019 so beginning of April we want to deploy on to aetherium a sorry and through the theory of test not the main that yet basically a start verifier four indexes for compressing the you know offering and showing scalability through through Starks so you will have a verifier that will allow a proven ode to prove that it processed many many decks

transactions and you will thus maintain the non custodian part of the decks but you will achieve far greater scalability then you can in current state where everything goes on the maintenance so hopefully the world will be seeing you know real Starks in in the wild within roughly three months and after some testing period we hope this will be a solution that would be integrated to various actual Dex's and help them solve their acute scalability problem that they are faced with right now I

just want to emphasize so even though this is the zero knowledge podcast in this solution we won't be addressing privacy at all we won't be using the zero knowledge aspect of the start we will be using only the scalability attribute of it which is the exponential compression of computation typically we refer to the efficiency property alone as succinct these are sort of proofs of computational integrity a whereby the size of the proof and then the time to verify the proof our cervix currently smaller than sort of naive leery executing the original computation and I imagine you can also use this like we've

had we had a conversation with Eric Tang from live Pierre months ago about off chain computation and how you can do stuff off chain sort of just like check in with various forms of proving systems I don't even know what you'd call these actually like because it can be it doesn't have to be zero knowledge proof but it could be all sorts of different proofs instead of on chain computation you have off chain computation we play and then on the chain you only have the corresponding verifier which is a much cheaper algorithm to run is that what you're talking about here are you using an off chain solution there's this on chain very focuses on Jing ok I just want clarify at the end of q1 it will

only appear on the Testament not on the main that will first tested but the verifier will be sitting always on chain it will be verifying than an exponentially larger computation has occurred correctly off chain and and this is something that you all would like if you want to do often computation you always need some on chain verification aspects and people like life here and many others have so far just kind of said I hope that like that true bit solves this problem and just use their solution and you know maybe that works maybe not but it's the

true bit solution is is it's a game it's like a game theoretic game of playing outs versus various incentive structures to make sure that the computation at the end is is correct but having something like this where it's an actual proof with very high reliability then it changes the story from you know we have to do this kind of back and forth between the chain and off chain and you have this lottery kind of thing too so you know we can actually verify that this was done correctly do you think there are is there sort of a settling on

this being a more plausible scaling solution than those kinds of solutions or is it still debatable that that's a debate that the larger community should hold we strongly believe that this is a very good solution that can help address inability maybe it's not the only sort of main probably it's not the only I mean just like with the internet to reach very large scale and so that we can all you know converse by video chats it's not one thing that solves it right you need fibre optics is that around there isn't a whole bunch of things so it's not that that starix is one component that solves everything but we do believe that it's certainly a very

important complement that should be in the mix of any scalability solution long term I think it I mean obviously something like that true bit system depends on the size of the computation as well and you might have a really really large you know machine learning computation or something done off chain and then you only like you can't necessarily verify everything so it's also like a reliability thing right where if it's something that requires a lot of reliability there's a lot of money hanging on it or something maybe then you want a proper proof if it's just you know like live here compressing an image then it's not that important yeah

between attribute system in something like a start is that in true bit you need someone that is trusted by the verifier someone to act on behalf of the verifier and be non succeed that someone must run a computation that is as long as what the prover does in a stark a verifier doesn't trust anyone else and still spends only an exponentially smaller amount of computation than the proofer so there's an exponential gap between the job of verifying a star true from the job you know someone doing the verification of a true example can Stark computation be non-deterministic of

course I mean okay it depends I think one should understand what what non determinism means so a non-deterministic computation of a good way to describe it to the listeners is a computation that requires also extra auxiliary information things like passwords you know my medical or financial data there is I mean there is no real you know non-deterministic machine as it was conceived or defined in the 40s or 50s as a machine that actually you know guesses we do have that today though we're executing the exact same computation on x64 does yield different

results sometimes so I believe this is a Miss these are this is the same word referring to the finishings so in computational complexity in non determinism refers to a very specific feature that actually with to leverage quite a lot not just in this proof system but in my across many pub systems and then a sort of I guess you're referring to the fact that real world computer architectures are under specified and you know different realizations of the same architecture on different sort of hardware ships that might behave somewhat people early maybe one way to resolve it is that we use non

determinism in the computational complexity but not in the computer architecture sense in a sense that it is important in fact this proof system is designed in such a way that a correct computation can only have a single correct output and that that's the only thing that the verifier checks if there could be multiple outputs then somehow the security proof system wouldn't really hold mmm right because what does it mean to check you out yeah I mean so so that's something that you know a lot of these off chain solutions struggle with taking live periods an example again they want to run their what they want to compress video 2x to 64 and that's what I would call a non-deterministic

algorithm because it depends on how much Machine time is spent on each frame and that depends on which cpu and watch what speed and like how real-time you want things to be and what bits per second you wanna use yeah but they're using like real architectures remember we are using an algebraic computer that we desire so on this algebraic computer everything is fully specified like every operation has a specific effect on the computation and we have designed it to be so notice also that our algebraic computer is incredibly simpler than real-world architectures and and so is the efficiency also these alternative solutions I mean they are much faster because they're running native

computation on actual computers we are sort of running cryptography it's a much slower process so I think we're getting close to the end of this episode but I'd really love to hear where do you see general zero-knowledge research going like what do you see coming down the pipeline that's really exciting maybe things that you can incorporate into the work that start where is doing or just like generally out there personally I hope that there will be a greater variety of you knowledge proofs that achieve post quantum security I think that is a an important long-term goal so that's something that there's certainly there isn't as much of as I would like to see and I hope the future brings more of that right now we do have Starks but

it's just one approach potentially out of many - yet to be realized in the future and so I'm curious to see what those could be I add to that that you know two specific things so zero knowledge is just the first layer of a bigger theme called secure multi-party computation where there are several parties that each one of them has you know some private information and they which to jointly compute some function so think of you know an auction where everyone wants to put in a bid and you only want the result to be known to the winner something like that so that's one area that could could be deployed later on and a little sound or maybe talk about

recursion per semester thank you yeah the other one is recursion so the moment you have any succinctly steam we're checking a computation takes less time and then running it you can do sort of a sort of crazy idea which is to recursively invoke the proof system on itself where you start running proofs of proofs of proofs of proofs this is no this is something called recursive proof composition we understand how this works for snarks also in practice together with a li and other great colleagues run around where mothers will come on strategy for the first time practical

recursion of snarks which is actually today used in the coder protocol for example and in principle it is also possible for Starks but if you want to try to make the practical that probably requires some new ideas and so this is something that we're actually working on and I at least think that it will lead to even more applications that weren't possible with only single-shot Starks so this is I think it's a very exciting direction that again may Ellie and I have been together it like two weeks ago and then we spent almost all our so free time together talking about this topic so it's something very very fun and but also challenging problem I wanna maybe just just add that in general I think Alice Sango and I in or you know many

colleagues and you know co-workers also at its start where or having a lot of not just fun but meaningful interaction on pushing forward both the implementation the engineering the product size but also the very core science and math of it forever and it's tremendously beneficial and fun thing that I'm not sure we anticipated would actually happen it's it's very science Ian matthean that's a lot of fun do you write all of your code in C++ and what part of it are are you planning to open source so the verifier for the verifier for the contract that you know

that will work with Dex's is currently being written in solidity so our programmers are some of them are writing verifier code in solidity as we speak and making terrific progress on it and that part will be a smart contract that will be you know deployed open-source the prover node will you know there must be a single entity at first that operates it otherwise you run into further problems of consensus improvers and that will not be open-source at first but we will plan to blow our intentions regarding how we're going to

distribute code in a blog post in the very near future but the perverse written in c++ them or something else yeah provers written in c++ and other things people definitely are excited about Stark's I think you guys maybe know this our listeners may or may not know this but we started a little Stark's learning group about a month or two ago and it was supposed to be like eight people talking about this topic and it's turned into like 75 strong and people really got very excited about this um if anyone wants to join the group I'll put the link to the telegram group in the show notes but definitely you see a lot of excitement around this we just want to say yeah thank you for being on

the podcast thank you very much thank you for that thank you thank you for the work that you're doing keep it up and to our listeners thanks for listening thanks for listening [Music]