Toward succinct proofs of solvency with Jeremy Clark | a16z research

Transcript

we're really uh glad to have Jeremy Clark here uh today and this week um so just like when I introduced Andrew yesterday i' have been working with Jeremy on uh blockchains for 10 years now our uh first couple of papers that we wrote together came out in 2014 uh it was actually a paper we wrote in 2016 um on proofs of solvency uh that uh Jeremy's going to be telling us more about today so uh I should say Jeremy's a associate professor at Concordia and uh Montreal um and yeah he's going to tell us all about proofs of solvency uh trying to prove that exchanges aren't going to well haven't already disappeared with all of your money

that's a subtle distinction but an important one yeah all right yeah thanks uh it's awesome to be here again and and uh Happy uh to give this talk okay so before I get into the Talk itself I met all the interns last time and most of you I saw last year so instead of having five slides on everything I do I just condense it to one slide so my research interests are broader than crypto so this will be more of a crypto talk uh today uh last year I talked about more of a systems uh kind of talk so I'm interested in systems aspects of ethereum uh empirical uh work work measurements that type of thing and then lots of stuff on uh apply crypto and then lots of fun uh projects that

have nothing to do with anything serious uh in terms of research like how do you start your papers what's the opening sentence you use and who is Satoshi Nakamoto so if you want to know my thoughts on any of those things you can ask me after okay so uh this is uh new work uh with my uh student Barry and uh Master student uh at Concordia and we're going to be talking about uh succinct proofs of solvency there's a toward or it could be a towards in the title and I'll I'll talk about what that means as well briefly uh a proof of solvency is basically a solution to this problem um so you have centralized exchanges so we're not talking Unis swap onchain

stuff we're talking about offchain traditional exchanges uh the way it works is you put your money on the exchange uh so you might have US Dollars you want to buy some ethereum so you'll put your US dollars through a Bank transaction I want I have eth I want to buy cash out for US dollars so I'm going to do an ethereum transaction okay but the point is the central exchange takes custody of both sides of the currency why do they do this uh the the answer is that you might not get executed right away so I might want to sell at a certain price and nobody's available at that particular time I can put my uh bid as a standing bid in the order book and then I go away from my computer someone else comes along is willing to match

that price The Exchange wants to execute that trade for me even though I'm absent okay so that's why they take it under custody is it good to take it under custody for the exchange so normally we think that's bad uh because it's sort of uh you you're limiting your trust you don't have custody of your own crypto anymore but there is an upshot of it which is from a usability perspective it's a lot less intimidating to have a web account with a password that can get reset and your funds sort of sitting there and and the exchange is worrying about them okay so what we see is that a lot of people you would think people will go into the exchange they'll do their trade and get out as quickly as possible but that actually isn't what happens a lot of people just sort of let their money

sit on the exchange they treat it kind of like a bank okay so if someone breaches an exchange and steals uh the cryptocurrency or or the US Dollars uh but it's because US dollars are traceable and reversible it's a lot easier to steal the crypto and not get caught um there could be a lot of money sitting on the exchange so what we seen historically is a lot of exchanges get breached and they lose a lot of money so one of the earliest cases was this exchange called Mount gaau they lost about half a billion dollars what's interesting about this is if you read the fine print of of the news articles is that this theft it wasn't that someone broke in and stole half a

billion dollars what happened is someone broke in when Bitcoin wasn't worth what it was worth by the time this attack was was discovered it sat there unnoticed for like a year or two the price of Bitcoin shot up so the hole that was missing just got bigger and bigger and bigger and then they woke up and discovered it now no one knows the backstory of like was it Insider fraud was it theft or anything like that uh but the point is that they they went on for two years uh having this hole in their balance sheet so the way it works is uh you can think just business like 101 uh you have a bunch of assets which is uh the things that you are supposed to have so I have a bunch of eth uh they belong to my user so I have a liability

to the user because the user can cash out at any time um and I could prove to the user one by one that I'm going to do this computation and this is the balance I'm using for you in my computation okay so I could prove to you that I have this computation and uh you you think that you have 100 eth with me and I'll open up my proof and prove to you that I I'm accounting 100 eth for you my assets are controlled by private keys if they're crypto assets okay um and then usually your assets are slightly bigger than your liabilities uh so this is the leftover is called Equity or Capital depending on on the context what you

could imagine is you could do a big zero knowledge proof where the exchange says I know a bunch of keys you I'm not going to tell you what keys are mine but I I'm going to prove that if you take the balances that are associated with those keys and add them up you get a certain number and I have a bunch of users and user can check the number that I'm throwing in for them and if you add them up you get a certain number and if you subtract these two numbers you get something that's at least zero uh maybe greater than zero okay so that's the basic setup so the prover knows everything they know all their assets they know all their liabilities they want to prove that they're solvent uh and the and they don't want to reveal

anything beyond that fact okay so at the end of the day I don't know how much the assets are that the exchange has I don't know who the users are I don't know how many users are on the exchange and on and on I I forget the other properties but basically it just it just reveals that single fact uh that they're solvent or not okay and the vision for this would be an exchange might do this once a day okay they would just post this it's a direct proof it doesn't supersede like traditional Audits and people coming in and things like that but it's just sort of a daily exercise that an exchange can do so we had this idea we proposed uh a paper back in 2015 today what I'm going to do is basically talk about how to make it faster and like

kind of smaller uh in terms of proof sizes now since that paper came out it didn't solve the problems it's not like exchanges all implemented this and now there's never been a breach of an exchange since quite the opposite there's been lots of high-profile cases of of breaches and there's a real long tale of of smaller uh thefts um and there's no requirement like legal or anything like that that you have to do a crypto proof of solvency exchanges could do it they might not uh they might do it as kind of a trust signal to their users most exchanges I think it's fair to say don't do it but there are some that have done it but even the ones that have done it uh there's often problems with it so here's a recent paper that uh went through a bunch of the different proofs

uh systems and I should mention too that uh I'll get there eventually but I might as well mention it now is some of these proofs only prove the liability side they don't prove the asset side uh and I'll talk about why there's there's actually a clear reason for for why that is the case Okay so proofs of solvency they sound great right but they do have some practical limitations that are important to to flag the first is that they rely on human behavior so users have to check that their number is correct if you never check and I'm in exchange and I know you never check I can just zero out your account and now my liability are less and then I can have less assets to cover for those liabilities um you can't prevent a hack okay so this is a detection mechanism

it's not a prevention mechanism exit scams hacks that kind of thing can still occur and you could have exchanges that are insolvent but they have a friend maybe that's also ins solvent or not in exchange just has a bunch of money they kind of pull their assets together just to push the zero knowledge proof through right and then they can decouple their assets again and then later the next day they do the same thing uh so you can't solve that sort of well we have some ideas about how you can maybe do something about it but basically it's hard to to do anything about the collusion problem so now maybe you're on the other side of okay now proofs of solvency don't sound so great right are they are they actually is it just an exercise in crypto is it some crypto problem that we make up that we can

solve or do they actually do something meaningful and so I'm sort of in the middle I don't think they're perfect they're not going to like revolutionize like security but they are material they make a material difference they're worth doing they're meaningful okay the first thing it does is it forces the exchange to actually do the accounting so they have to go in and they have to find their accounts and find the keys that that correspond to the accounts and things like that uh you see with FTX for example there's a lot of assets that just kind of go missing they have them in the end right but just nobody knows where they are at any time and then same with Mount gaau you have this big hole in your balance sheet and it takes a year or two for someone to realize that it's missing okay so at at least what

you do is you get rid of the incompetence and it doesn't necessarily prevent the outright fraud but what you're doing is you're forcing people to to very meaningfully commit fraud okay you can no longer just be like oh we're just incompetent okay now it's like I'm I'm going to commit fraud and I have to find someone to collude with I'm producing these uh the this sort of paper trail of my audits every single day and so later if there's an investigation then they can go look at you know what were the accounts that you were using in these proofs and they can untangle what the fraud was exactly okay so you are you're adding a lot of evidence to an Evidence Trail it makes it a lot of harder to cover up you have

to go and find someone that's going to collude with you that's someone that might tell the authorities about what you're doing um and so it in my mind it meaningfully raises the bar uh for committing fraud uh for an exchange so they're not perfect but they're better than nothing so what is a proof of solvency like kind of on the inside so what we're going to do is we're going to split it into five pieces okay there's going to be two pieces with the asset side there'll be two pieces of the liability side and then there'll be the part where you just subtract your assets from your liabilities okay so on the asset side what you want to do is you want to prove that you know some signing keys that correspond to some currency and then what you want to do is you want

to add them up and get a total liability okay on the asset side you're going to commit or sorry on the liability side you're going to commit to all the liabilities users can check is my liability included correct so that's one component and then what you're going to do is you're going to take all the liabilities and again you're going to add them up to a total liability okay so at the end of 1 2 3 4 I have one number that represents my assets I have one number that represents my liability and then in step five I just want to show that if you subtract them you get a positive number or a non- negative number I should say okay and what we want to do is we want to make each of these proofs uh constant size and constant time for the prover to spend uh

verifying uh and the title says toward because we can't get there okay so we can't actually make it fully succinct but we can make a lot of progress and and I'll go through the details of what's succinct and what's not and if anyone has ideas about how to to to make it fully succinct in all steps that would be great now this room is is is kind of weird because you have you know a bunch of you don't do crypto at all well you do crypto as in cryptocurrency not as in cryptography you work on uh systems or you work on economics Game Theory mechanism design that type of thing there's some people who work on crypto cryptography but maybe not on zero knowledge specifically and then you have one person in the back that wrote

The Textbook on Starks right um so how do I give a talk that's going to appeal to the whole audience uh and the answer is that I'm going to air on the side of simplifying things okay so this is uh since it's an internship program I I going to like try and explain pieces uh in a lot of detail as if you've never seen them before so we're going to pick a model to work with so the model we pick is uh called plun uh this is not the best model OKAY especially in this room I'm not here to tell you that this is the stateof the-art it is not the stateof the-art but it's good enough uh it's pretty flexible and to be honest with you I understand it so I I I felt very comfortable with it and so that's

why we Tred to do it uh in plon and once we lay down the protocol in this setting then we can look at can we use multivariate polinomial or or different things to to to make it better and even more succinct and faster Pro or time and things like that okay um so plun is a general zero knowledge system uh it's based on polinomial uh the polinomial have a single variable so it's called univariate Uh you need a commitment scheme to commit uh to polom and this whole model is called poly IOP so there's other poly iops that you say multivariant pols and then there's other things that aren't based on polinomial at all okay so the world of snarks is big and complicated now at the end of the day what plon actually is is it's

just it's it's kind of like a gadget that says here's a circuit uh the circuit has a bunch of gates there's uh addition Gates and multiplication Gates and I know a way to wire this circuit or like to label all the wires on the circuit such that it evaluates to a certain output okay so uh you can think of of plon as as really just a little Gadget and in order to get there in order to prove to you that I know how to create this circuit I'm going to use a bunch of other little gadgets okay so I have things like I have two polinomial or I want to multiply them together or I want to add them or things like that okay so I I mentioned this to the intern so one thing that we're working on that's very much work in progress but

you can take a peek at it is we're trying to create a sort of encyclopedia or Handbook of all of these different gadgets uh and so you can see like um so what I'm going to do today is actually basically we just use four or five of these things um but but there're simple things like if you want to zero out elements of the array you want to rotate uh you want to add multiply and then a little more complicated things like prove permutations and lookups and ranges and circuits so we have a bunch of gadgets building up to the idea that you could have a gadget for a circuit and then once you have a gadget for a circuit then you can Implement what you want to as a circuit itself okay so you can Implement any function that you can

capture in a circuit so one way of doing a proof of solvency would be to do it at the circuit level so we just we write the circuit we compile it down and uh then we we run it okay that's not what we're going to do today okay what we're going to do today is we're going to use the gadgets that plonc itself uses we're going to use directly okay and it should be intuitive to you that this is going to be a lot faster okay instead of abstracting our function as as a circuit uh and then using a general framework that just evaluates circuits we're going to use the tools that that the circuit evaluation thing uses itself okay um so it's uh we're we're sort of down a layer uh in terms of it and you can always do

a sort of hybrid approach too so if there's certain problems that you can't solve because you don't have enough gadgets uh then you could do a circuit for that piece and then glue it to to doing things directly with gadgets but for pra solvy they they I don't want to undersell it but it is kind of relatively easy it's a lot of additions and range proofs and things like that and so we have enough gadgets to cover every aspect of the proof almost there's one piece that we have to glue uh something to that that gets a little awkward but I'll I'll get there in a second okay so what's the sort of related work uh in terms of proof of solvency so we have Provisions uh and Provisions is a full proof it does everything but it's not succinct at all okay and this isn't just a theoretical

thing where it's like oh it's it's technically not succinct but you know whatever it it it's it's good enough it actually is like practically infeasible so uh prover time is in the hours uh and the proof size like say you have a million customers it's going to be like gigabytes that people have to download okay by contrast at the end of the day we'll we'll get to somewhere where it takes a couple seconds uh and it's like kilobytes in terms of size okay so this is a concrete Improvement it's not just a theoretical thing exercise to make it succinct bulletproof is a way to speed up Provisions particularly uh for the range proofs okay so that helps you a lot on the liabilities it helps you a little bit on the solves uh it doesn't

really help you on the asset side it more or less inherits the properties of Provisions itself but it again if you layer Bulletproof on top of Provisions it's an 0 protocol okay it does everything then there's a bunch of papers uh like two ccs papers and one post from vitalic that only deal with the liability side so they say hey we can do it succinctly uh but we're not touching the asset side okay we're just going to create a number that's the liability you can check that you're in that number but then you need a trusted auditor or someone like that that's going to go in look at that number and compare it to the books of the exchange to make sure that that number is correct okay and so here you can use things like accumulator schemes um or uh vitalic

thing is is in the same model as ours it's like a a polinomial based uh commitment protocol on the asset side there was almost no work except for at FC this year at a workshop there's a really nice paper uh called uh instant uh proof of reserves some people call these proof of reserves by the way uh so you you'll hear that terminology and then for my purposes proof of solvency proof of Reserve are exactly the same um and so what they did is they just did the asset side um and they mainly concentrated on ADD the assets up but when it came time to prove that oh that key belongs to me or that key doesn't belong to me they resorted to to doing it at the circuit level okay so they don't have a direct protocol uh for doing it they just Implement a generic

circuit and then compile it down uh using snarks Okay so we're going to try and do something a little different in this paper okay so this is where we're going to get to uh first off we're going to have a complete protocol so we're going to cover all aspects of the of assets and for everything that we do we're going to be better than provisions and bulletproofspeaking.com Theory but when

you pick a specific elliptic curve to implement your crypto on you run out of space and so what you have to do is you have to kind of split things up and so we don't we get something that's succinct in the number of users it's constant it doesn't matter how many users you have but there's a different parameter that that it is linear in that parameter but I'll cover these details when we get there so if you look at this whole chart you might say you know there's a lot of stuff on the liabilities the solvency column unless if you have both assets and liabilities you're not going to get that column anyway okay so this looks more sparse on the asset side and it looks really really sparse here I mean there's basically sense Provisions other than than oh you can Implement anything in a

circuit there's there's zero progress okay so like Provisions is still the state-ofthe-art for that particular column okay so why is that that seems like kind of weird like there's not a lot of activity there okay and so I call this the SE P issue so the issue here is that if you want to do a proof of solvency for Bitcoin or for ethereum you have a bunch of eth that's tied to a key and the key is uh like a normal ecdsa signature and that's implemented in a certain kind of elliptic curve okay this elliptic curve does not have pairings okay if you want to do something succinct right you more most

okay let me put it a different way if you want to do it in the model that we want to do it in so the poly IOP model with kzg commitments and univariate polinomial you need parents okay so that's the problem so if if we just if everyone use BLS then we could just do it directly okay so what we need to do is we need to sort of glue something in SEC p and we want to kind of map it into a pairing friendly group and once we get in the pairing friendly group then we can do the rest of the protocol more or less succinctly okay so that's kind of the challenge and then this is sort of just sort of showing the same thing so supports eth or BTC means that it supports like secp keys and then e people are either liabilities or

assets and there's not a lot of people in the middle that are also succinct and support everything by the way why does bulletproof work bulletproof doesn't need pairings okay so bulletproof is great uh for that reason but but they don't they don't actually innovate on that protocol itself um so they they just sort of inherit what what Provisions it so how do we deal with this problem how have other people dealt with this problem so there's a bunch of solutions so one is you can use Sigma protocols okay that's what we did in Provisions Sigma Protocols are like the generation of zero knowledge before snarks okay they're slower they're still like pretty fast but but when you have millions of users and millions of of accounts and things like that uh then it can get too heavy to use bulletproof uses inner product it's a lot faster

than Sigma protocols but it's not going to be as fast as as something like plunk um and uh you can just do the liabilities ignore assets then you don't face this problem so there's a bunch of papers that do that um you could just say we don't have privacy over our assets we'll just publish them okay or we'll tell you what all our keys are so so so no zero knowledge so there's some protocols that do that uh you can do it at the circuit level um so you can just Implement a a circuit so you're implementing secp math in the circuit K that's going to run on a like a BLS curve or something like that okay um so that's why it gets expensive um and we have some numbers in the paper I don't

have them in my slides but comparing what it means at a circuit level and what we actually do now if ethereum just used pairing based signatures then everything would be great they are starting to use it on the proof of stake side um but but for just normal assets it's not being used um now there could be future blockchains that use it and then Pro of solvency will be very easy for those ones but we want to do one for Bitcoin or E today as it exists uh and so we're we're not going to punt on that issue and then the the third idea is well what if we can kind of map uh numbers from sep into a pairing friendly group then maybe we can make some uh progress on it so that's going

to be our approach so it was actually here last year so I talked to uh some of you and Lena uh introduced me to this paper and so this is a paper that uh is exactly it looks exactly like what we need okay it's basically I have G to the X in SEC P I have G to the X in BLS and I can prove that the the x value in those two things are exactly the same so let's go forward with that and see if we can we can s of squeeze out a protocol using that paper okay so what we have just from looking at the blockchain is you have a bunch of public keys that are in secp and then just in PL Tex you have a bunch of balances and anyone can see this this is on the blockchain so I can

come along and I can say I'm an exchange I own secret key to and these two keys are mine I will note a caveat with our protocol it also is in Provisions is we can only deal with ethereum addresses where you know the full public key so normally when you first receive money eth you the only thing that gets recorded on the blockchain is a hash of the public key and then when you send money you have to sign then you have to reveal your full public key okay so this only is going to involve accounts uh that that uh have done at least one transaction outgoing transaction okay so that's a limitation uh that we have okay so what we're going to do is we're going

to take all the addresses I don't want to reveal which ones are mine yeah is that a fundamental limitation or you just don't want to do the hashing and circuit so if you want to do it at the gadget level you can't you can't compute the pre-image with those gadgets alone if you want to drop down to the Circuit level then you can do it or you could do something intermediary where you have a circuit just to to know the pre-image and then yeah that makes sense well it seems like yeah you could have a gadget that's like knowing the hash pre image and then plus the quality with the you know with a public key right yeah exactly yeah yeah so it and it also gets complicated because you can't write down what the public key is right cuz if as soon as

you write down what the public key is then I know that you know that's your key cuz otherwise you wouldn't know the pre-image to the hash so we'd have to hide that public key as well so anyways it it it there's no theoretical limitation for sure but it it's complicated to think about okay so what I do is I pull in the two addresses I own I pull in either all the other addresses on ethereum or I can just build an anonymity set so if I want to be a little smaller and save some time that's fine I can pick a thousand keys or addresses at random and and have them be part of my anonymity set okay um okay so what we can do is we can use that paper and we can uh map uh the

secret key uh to the a public key in BLS okay or in any pairing friendly curve I'm just picking that one because it's sort of what ethereum uses now for proof of stick okay so the statement that I'm proving basically is I know a value here and it's the same as this value here but I'm not telling you this value because it's my secret key I'm just telling you this value which is the public key so this seemed promising but then what we realized is uh oh yeah and then you can just copy the bounces since they're in plain text anyway you can just put them directly in the group any verifier can check that you encoded them uh correctly into the group what we realize is that when you do this proof

you're essentially proving knowledge of the secret key like you can't do the proof If you don't know what the secret key is itself okay so it it acts as a proof of knowledge and once you've proven knowledge of it uh it doesn't really matter if we have that value if we actually have this value sitting in BLS or not we we're not going to do anything with we're not going to actually do something with this value okay the only thing we want to know is that that the person knew it okay uh if anything what we're going to do is uh also I I sort of skipped over it but you you need to fill in the other stuff you have to fill in the rest of the column with with something okay because if you

leave these blank then uh then everyone knows which keys are yours because it's the only ones with value sitting there okay so you could just drop a zero in okay so the only thing that we're going to do is we're going to basically say I'm not using this balance because there's a zero sitting here I'm allowed to use this balance because I have a proof sitting here that proves that I know this secret key okay and so anyway so the the main Insight that we had is that instead of actually mapping the keys into BLS what we could do is we could just map whether we could prove knowledge of them or not into BLS so what we could have instead is kind of like a selector Vector where it just has

a one if we were able to prove knowledge of this and it has a zero if we were not able to prove knowledge of this okay so it sounds confusing because I'm saying it so let me put it on the screen so you can look at it uh and and then it might make a little more clear but before we go there if I can get this selector Vector then I can basically just you know multiply each of these together add them up and then I'm going to have the balance of of the eth that belongs to me as opposed to someone else so that that's why we're we're going with this I'll also mention before I get to the proof itself um this is pre-computation so so your keys probably don't change that much on a day-to-day basis the

balances change every day okay so you're going to have to what we wanted to do with the selector Vector is we wanted you to do it once and then if your Che Keys change you can redo it but if the balances just change it doesn't matter we're not going to touch the balances until a later step in the protocol okay um so yeah and then you also if you prove on a daily basis you also have a day for like say new Bitcoin comes in let's say have a new user what I'm going to do is I'm going to create a fresh account for them to deposit at so I know that it belongs to them as opposed to someone else but then I have the rest of the day to move that to my hot wallet or to my cold wallet okay so as long as I

get everything moved around before I issue this proof then I can actually have a small set of keys uh and uh I don't have to change my keys even if I'm generating new keys I just got to move the money uh to an old key now the paper I mentioned at the FC Workshop uh it's much better in this regard uh so what they do is they allow you to precompute keys that you might own in the future and since keys are deterministically generated you can commit to a whole bunch of keys uh that that you're going to use in the future and then they're already sort of part of your proof um and they do a totally different approach using lookup arguments it's awkward to glue our protocol to theirs otherwise we would explore that but that's sort of something we'll we'll look at in future

work so let's go back to the proof so the proof says um I'm writing a zero here and I can do that for any row I want okay I can always write a zero okay but if I want to write a one I have to know the secret key uh that corresponds to the public key here okay and nobody knows which like the proof is witness hiding meaning that when I issue the proof it looks the same whether I'm in the top or the bottom okay it's just it looks exactly the same so how do we do this proof the answer is we can actually just go back to 1990s zero knowledge we can do a sigma protocol and so what we're going to do is if this is a zero

you can think of these as commitments so every column has a commitment like a Peterson commitment to either a zero or one and I'm going to prove to you that um either this Peterson commitment is to a zero or it's in to a one and I happen to know the secret key that course respon to this public key which is the schnor uh zero knowledge protocol okay so all three of these are Sigma protocols this is just a proof of what a Peterson commitment is which is called proof of representation this is a proof of knowledge of of a discret log which is schnore they're like the the the most basic Sigma protocols the logic to link them the ORS and the ANS um is also standard in Sigma

protocols okay the only thing that's weird about this this statement is that the first two things are in one group and the second thing is in a different group okay other than that it it's it's very very standard so is that a problem are you allowed to do that can you do a sort of conjunction and disjunction of some Sigma protocols in one group and other ones that are in another group and the answer is that the logic is only based on challenge values so basically for the the the side that you're not doing you kind of learn what the challenge value is ahead of time can pick it and for the side that you are doing you don't know what the challenge is so as long as the challenge value can be the same in both of these groups then you can glue it together can

the challenge value be the same okay and the answer is yes you can actually the challenge is a bit string and it can be any length Okay so you'll take the smaller exponent group uh between the two and you'll just make sure that your bit length is a little bit less than that and if it can be any length then why don't you make it one or two like why why use a big Challenge and the answer is it relates to soundness so the soundness of the protocol as T gets bigger it gets exponentially more sound okay so you want the biggest T possible but you know you can do a 250 bit Challenge and that's like plenty sound uh and it will fit in the exponent groups of both BLS and secp because they're both around 256 bits uh

each okay so I didn't go through Sigma protocols so I you might be lost at this stage but but uh later when we we switch to the plon side I'm I'm going to go a little slower and and try and explain uh step by step I just didn't cover this because it um uh is is a little more standard and so there's a chance that you've been exposed to it okay so let's sort of uh recap so what we have is I have a set of individual commitments to this selector Vector okay and I proven to you that I've only put a one there if I know the key and there's a zero there if I don't know the key or if I just choose not to to to to put a zero there whatever okay what I want now is I want to represent this Vector as a single

value I now we're ready to make this succinct okay so what I want to do is I want to hold I have uh a whole bunch of Peterson commitments and then I have another value and this is a single value that represents the exact same vector and I'm going to prove to you that they're the same so what's encoded in the single value is the same that's encoded across all these individual commitments and once I done that then I can move forward through the rest of the protocol with just that single value okay so the rest of the protocol we can we can uh uh have be succinct so how do we get a single number that represents like a full array or column or row of of values so the model that we use the poly IOP model says okay you start with an

array there's a bunch of operations you can do on your arrays you're going to represent the arrays as pols and you're going to commit to the polinomial and the Pol is going to be like if you have a thousand or well a million elements your array is going to be a million elements your polinomial is going to be a million degrees but the commitment to the polinomial is going to be succinct okay so the succinctness is really only going to come from this step to this step how do we take an array and encode it into a polinomial there's three ways of doing it uh a protocol like plon uses all three at some point in the protocol so the easiest way is you can just drop it into the coefficients of the polinomial the second thing you can do

is you can say I want a polinomial that's going to be zero at three it's going to be zero at one it's going to be have another zero at one it's going to have a zero at seven so I'm going to set that to the roots of the polinomial and then I'll spit out uh the polinomial or what I can do is I can pick what's called a domain say 0 1 2 3 and then I can encode my uh data as points on the polinomial at these X values and then I just interpolate by drawing a line through it and then that's my polom okay so all three of them work they have different properties the short end is basically this coefficients are very fast you you get it you get the polinomial directly but it's really hard to show that the third element in the

array is a one okay that's it's hard to do uh from a math so usually we only do coefficient mapping when all the everything's supposed to be zero then we map it into a polinomial and then the polinomial will be a zero polinomial because all the coefficients are zero but we generally don't use it otherwise uh Roots have a weird property which is let's say I switch the seven and the one I have a different array now but when I encode it into Roots I'll get the same polom okay is that a good feature or a bad feature well it depends on what you're trying to do so normally we care about order right you shouldn't go switch the array but sometimes you don't care about order sometimes like for

example I want to prove that one thing's a permutation of another then this is really handy because I can encode the two things as roots and then just show that they're the same polinomial and then now they um you know and it's order and variant okay so root encodings generally only use when you want to prove permutations otherwise you don't use it and then evaluation points is what we're going to use more or less except for some optimizations we'll we'll use this but I'm not covering them in the slides or in the paper um so we're going to do this it's a little slower because you have to do the interpolation um but then it's very flexible so if you have two polinomial encoded this way you add them together all of it's like you're adding all the elements in the array same with

multiplication you if you want to multiply all the elements in the array you just multiply the polinomial uh if you want to open it at the third point you can uh kzg will will give you a protocol to do that um you know and I can go on and on but but but anyways this is a very flexible uh way of of doing the encoding now the next question is is it it should we actually just encode it at 012 3 or can we do better than that okay and so the answer is we can certainly we can just encode it at 0 1 2 3 4 uh and we can use what's called Gan interpolation uh it's n squ uh complexity but what we can do as an efficiency aspect is what we can do is we can pick X values so that normally if

I if I move from one x value to the next I just add one so to go from here I add one to go here I add one when I hit four and I add one then I drop out of the array okay so I'm no longer in the array but the polinomial is defined at all points so there is something sitting at index 5 I just don't know what it is okay um so what we like to have is we like to Define what's called a multiplicative subgroup so that to go through the array what we do is we multiply instead of adding so I pick a w a a a number like three and so 1 * 3 is 3 3 * 3 is 9 9 * 3 is 27 27 * 3 mod

whatever this is uh is 19 and then if I multiply 19 by 3 again I go back to one okay so it's closed under multiplication so then I never I never leave the domain okay I stay in the domain okay this is going to be helpful later when we want to prove that like certain properties hold for all of the values across uh the array it's also useful when you want to interpolate through it you can use a faster algorithm to do the interpolation if you have this property what we say is is just that Omega has multiplicative order K in Q uh and then what that means is that the capath root of one is Omega and so we we say that Omega is a k root

of one or Unity Cu uh one and unity are the same in this group so you'll see the term root of unity a lot in the and that's all it means it's actually something that's maybe a little simpler than than what it sounds like okay now the question is okay where does this uh Kappa value come from can I set it to be anything I want so can I get an array of size six if I want it can I get an array of seven eight like can I just choose that value freely and the answer is no uh it's set by the elliptic curve so the elliptic curve has an exponent group it has a certain size which is q and the only roots of unity that you have are going to be some divisor of Q minus one so whoever picked that Q value they've

locked in basically what your sizes are and you can't do anything about it now the good thing is that people who design elliptic curves take this into mind okay so they try and give you lots of variations uh in terms of different subgroups that you can have um so BLS for example it will give you uh you can use an array of size any power of two up to 2 to 32 so you can have 2 to the 16 2 the 17 2 the 18 all the way to 2 the 32 and uh so what you do is you think about the array size that you want and then you just sort of Round Up to the nearest power of two and then as long as you don't spill over 2 to 32 everything's good but what what's going to happen for

us later you'll see is that we do spill over that and so we have to do something about it so now we have our polinomial we want to commit to it um so what we do is we uh we use this kzg uh which is a famous uh polinomial commitment scheme uh it has this trusted setup so the people in this room worked on a paper about how to do this uh trusted setup in a distributed way and more or less you you you take your polinomial you take the trusted setup and you're able to basically compute G to the polinomial it's evaluated at a random Point nobody knows what that random point is that's why the setup is trusted and I'm not going to convince you of the math but if I have the polinomial evaluated at a random point I

didn't know what that point was then it locks the polom in completely okay so I can't um it it basically is a binding commitment uh to that polinomial now we're doing things in the zero knowledge space so we're going to use a more complicated version and it's even more complicated than this because there's some structure to the RS but basically we're going to have a randomizer term on the end as well but I'm I'm sort of glossing over that detail so kzg you can commit to a polinomial you can prove that if you evaluate the polinomial at one you'll get the value 122 uh this is what uses the pairing so this is why we work so hard to get into BLS so that we can use this uh commitment scheme and then there's a way to sort of partially open to so if you look at the opening

protocol they first open it to a commitment to the value then they just tell you what the value is and you check whether it matches the commitment to the value but if you want to open it to the commitment and stop you can do that so that's going to be useful uh to us as well so what I'm going to do is I'm just going to uh I'm going to take this column I'm going to put in a polinomial I'm going to commit to it and say here it is and then what I'm going to do is I'm going to open this point this point this point this point and prove that they match those Peterson commitments that prove the knowledge uh of of the private keys so that's how I'm going to glue uh the two things together okay and uh when I open the polinomial I'm not going to

open it to zero or one I'm just going to open it to a commitment to zero or a commitment uh to one okay all right so now we've glued the fact that I know a bunch of SEC P keys to this single Vector that represents which keys I know and which keys I don't now from this point forward we can just we can stay in the pairing base uh model and do the rest of the protocol so this is why the to is in the title is we still have to do a sigma protocol for every key okay but still it's it's not super expensive um so proving time you know is you know it's it's in the seconds uh verification time uh is in the low seconds like tens of seconds and

and we're talking about kilobyte uh proof sizes now what we have is uh we have our selector value okay uh we have the balances uh and so what we do is we just multiply them together and that will give us the multiplication of these two values uh and again we can represent that succinctly as a single value okay how I do the multiplication I'm not going to explain so there is a gadget that lets you multiply two polinomial together and produce a third polinomial or let me phrase it differently I give you this this this so you have three values and I prove to you that this times this equals this okay uh then once I have the multiplication then I want to

add up all the elements that are there and this this is another Gadget but I'm going to um so they add up to 70 and this one I'm going to walk through just so that you see what one of these gadgets look like under the hood and it's the only Gadget I'm going to show you okay and the rest of them you can are kind of like variations on on how this works so you can think of this as a sort of sum check protocol but it's not the sum check protocol it's it's the plon version of it okay so we have this array we want to add them up and we have the number that's supposed to be the total uh which is 70 okay what I'm going to do is I'm going to build a second array a helper array I call it

accumulator but it's not like the accumulators from crypto they're they're something different and so the way this works is for the first value I just copy the number in from the first array for the second value uh what I'll do is I'll take the sum of the same number in the first array and the previous number okay so this is sort of like a running tally as you go through uh this array so the next value will be the sum of 68 and the sum of the previous value which is two and then the next value will be uh the sum of the previous value which is 70 plus I'll add in the zero and then the number that's sitting here at the head of this array should match uh the value

that I'm asserting is the total so what are the constraints of the system so there's three so the first is that I copied this correctly the first value the second is that each update is correct so they it's the sum of the previous value and the same array and the value in the other array at the same index okay so at this index it's the sum of the other array at the same index and the same array at the index uh before that should be a plus apologies the uh last thing is just that the the last value or the first value in this case uh matches uh this value here can we take these constraints and represent them in

polinomial math okay so this has to do with arrays what about pols and the answer is yes it's pretty much a straight translation so we just say that for this particular value the last value in our polinomial uh the values are the same between these two polinomial uh for all the X's working up to the last value so with the exception of the last value then uh the value at every variable is the sum of the same variable in the other array plus the one moved over again how do you move over one uh you just multiply by Omega okay and then uh you can prove that this sum that I'm asserting is the sum uh matches the first element in the array now the next

thing we have to do is we have to do something about these like for xal w k minus1 and for all X we have to do something about that okay so um oh yeah sorry first before I do that I'm just going to push everything so it equals zero so I'm going to pull this over to this side and then set the whole thing equal to zero okay so these this is just rearranged and then I label or I don't even label them so yeah so it's just the same equations just with everything moved to one side so that they equal zero if you want to zero out elements of an array you can do it just with multiplication so what you can do is let's say you have an array and you want to zero all the elements of the array you just multiply it by this polinomial

okay and this you don't have to interpolate this polinomial you can just directly compute it uh if you want to zero out the first element you'll get Randomness in all the other elements but you'll guarantee that there's a zero here uh then you can multiply these this polinomial by this now if your polinomial happens to be zero because of your constraint in all the other places at the end of this multiplication it will be zero everywhere so your constraint will take care of the fact that it should be zero in all of these locations and multiply it by this will Zero out that particular position okay so you can zero the whole polinomial you can zero just the first element you can zero the last element you can zero everything except for the last element you zero everything uh but the first

element what do we want here uh so what we want is we want to zero everything but the last element here we everything is zero except for the last element so we want to just zero the last element and uh here we want to zero everything except for the first element okay so we multiply the pols by the appropriate things just straight out of the chart okay so now what we have is we have a polinomial or yeah polom that's zero at all the elements in our domain okay it's not necessarily zero across the polom but it's zero across the domain of the polinomial so to make it zero across the whole polinomial we take another polinomial called The Vanishing

polinomial which is also zero across the domain we divide the two and if that evenly divides there's no remainder uh so we can commit to a quotient polinomial it proves that this original polinomial was Zero across the domain otherwise it wouldn't divide evenly okay so just by by being able to produce these Q values I basically prove to you uh that that uh the vanishing polinomial is actually Vanishing and then I can just again rearrange this and push it all over so that it all equals zero and these are truly zero polinomial that should be zero all the way across if these three constraints hold so what do I give to the verifier what I give to

the verifier is just a commitment to my two my original array my helper array and then I'm going to give them a commitment to each of these Q values okay then the the verifier is going to say okay I want to check that these relationships hold okay I'm going to check it at a random point so if um I'm going to pick a random point we call it Lambda and what you're going to do is you're going to open these Q values at Lambda so you open them up you're going to open the original array and the helper array at Lambda as well and then because of this constraint we do we are looking at the element beside the element in the array so what I'm going to do is I'm going to also open uh that

array at the next element uh in the array okay uh and so those are the the values that I open and then what you do is you take these values you plug it into this equation you get these three values and then you take these three values you plug in the Q values you know you can compute these themselves and you better get zero at the end if you you don't get zero then there was something wrong uh with the constraint system okay so that maybe didn't come across as well as I thought but hopefully uh you get the sort of intuition of it so now we have basically we have the sum of the total assets of the exchange I'll I'll go a little bit faster through the liability side but um this stuff is all constant constant time uh for the

verifier uh constant size the only thing the verifier has to do that's not constant time is they have to interpolate these balances into a polom okay they have to check that it was interpolated correctly but there's no crypto operations it's just field operations and so that's what the uh the orange line is there so we did the keys uh we did the total assets we want to give users an individual proof that their liability is included so again we make a big chart we have a bunch of user IDs we have a bunch of balances that we're asserting we're asserting what the total liability is that we own to every user you can show up and say show me my account okay so the you the exchange

will say well I have you in slot four or sorry slot three um and your balance is two and I'll say yeah that's right my balance is two I have two e with you okay now the problem is we have two users that both have a balance of two so what the exchange could do is if Joe has a balance of two and I do uh when we both check it could open up it could tell me I'm the third slot it could also tell Joe that he's the third slot okay that's called a clash attack and then it doesn't have to include the second two in its balance sheet now it it's under representing its liabilities which means it has to have less assets to cover it so you also have to give a unique user ID like a hash of your email address or

something like that so that you know that that slot belongs to you so basically we do a vector commitment polinomial commitment polinomial commitment uh in order to and then we do a polinomial open and the only thing you have to check is that the index that you get in this vector and the index that you get in this are same okay and then the summation I already showed you it's the same protocol as before except for there's okay there's one thing actually sorry um okay so this is basically the same it's the sum of this but there's one problem with this the problem is that the exchange can make up users if it wants to okay they're users that will never check but it can add users to it now why would it do this if it makes up a user and adds a balance of two it has

to have two more eth in its possession in order for the proof to go through so it's basically just shooting itself in the foot if it wants to add users that don't exist okay but what if it does this it has a user with a negative balance okay now these numbers add up to zero and so now it just has to have zero assets and because this is the exchange's fake account it knows that there's not a user out there that's going to check and say oh my negative my balance is negative that's weird okay basically no one will ever check this balance and it's negative and now its total liabilities are zero okay so how do we solve this what we have to do is we have to do a range check on every

single value here and specifically we're looking for a positive integer which is a small integer in modular math okay so we just pick like what's the most eth that someone could own and as long as the number is between zero and the max amount of eth that someone could own then then it's fine the range check I won't go through it works kind of like the sum check it's just a it's a step more complicated but again you're building a sort of helper array so you take your number you encode it in this case we're going least significant bit to most significant bit you make this sort of helper array where you're going to kind of fold the bits in one by one and the relationship is that you take the previous value you multiply it by two and then you add the value that's at

the same factor here and if you stare at it long enough you'll see that that's a binary decomposition of the number 11 and that this will total up uh to 11 um so the constraints that you have are just that this rule is followed that's the middle one uh that the final value matches the value that you're expecting so that's that one and then also that that you start off with either a zero or one okay so you start off binary and then where's the range in these constraints the range is in this value here so if this value is k then you know that uh the number could not be bigger than than two to the K because every number you put in is is binary the most

that you could put in is a whole bunch of ones so You' only get k1s and if you get k1s and you run it through this the maximum value you get is 2 to the K minus one okay so that's that's in 30 seconds how the range proof works then we have some problem where let's say you have a million accounts you only have 12 bits left for your accounts because you have 32 two to the 32 maximum uh root of unity in BLS and so that that could represent balances between $30 and $150,000 but that's obviously not enough you need more bits to represent a lot of balances will be less than that amount or greater than that amount so we basically run out of room so what we do is we make a sort of two-dimensional

array so we take this is the bit decomposition the first bit this is the second bit this is with the third bit folded in this is with the fourth bit this is and then you go all the way up to the final bit and then the final bit this row will be the actual balances themselves okay and we commit to them individually so I give you a commitment to this row to this row to this row to this row to this row and so now instead of having one commitment to everything you have K commitments where K is the number of bits that you're using to represent the balances is that succinct technically not it's linear in the number of bits but it's independent of the number of users okay so the number of users you have are uh the number of

columns that you have and so uh you can have 10 users or a million users or 10 million users and it's always the same size uh the proof uh so yeah so K bit PR Precision gives you K polinomial and therefore K polinomial commitments that you have to check prover time is is is always linear um or n log n but anyways it's constant for the user in terms of the proof size and the verifier time the only exception is that the bit Precision will pick a different constant value across okay so if I'm only using 8 Bits it's going to be faster than if I'm using 64 bits okay but we're still talking milliseconds and we're talking kilobytes for the proof even with 64 bits which is way more than you need

okay so it's again it's towards the synness but it's very very practical and very fast and then the last bit is just that you you because of the previous protocols you have your total assets your liabilities you can throw in amount that's the leftover and you can do a range proof on it and it should add up to zero so it's assets minus liabilities minus my Capital uh equals zero the idea that you prove which Keys belong to you is linear basically everything else is either constant it's always constant in the number of users and one little sub protocol is linear in the number of bits that you use to represent the accounts but other than that everything is succinct okay uh our protocol is full meaning like we don't just do

liabilities or just do assets we do everything it all works together it's all glued together um and uh it's certainly fast enough you could do it at a faster frequency than once a day uh but I think once of a day is nice I I don't know that you get much benefit from doing it once an hour or once every 10 minutes and it also gives the exchange time to like kind of move their their uh money into their wallets their cold wallets and hot wallets uh everything's implemented uh in Rust and for future uh work we're looking at switching to multivariate polinomial and uh we're also looking at uh ways uh particularly to merge with this other paper that uses lookup arguments and it makes things even faster for reasons

that I won't explain but uh those are are two promisa in future directions okay so that's it and I'll take any questions uh you mentioned one of the gadgets is a lookup argument right like that you built in the in the plon model um how is that how does that relate to merging with the other work that kind of like uses lookup Arguments for range proofs I guess so uh so the question is how does we already have a lookup argument gadget for plunc which is true we do have it so can we just drop it in and do exactly what they do and I'll I can sort of explain uh very I can show you visually like what um what the issue is with just directly doing it

so the output of our I know these these accounts belong to me is a selector Vector that's what our output is of that protocol what that other protocol call expects as an output of this phase is a lookup table with the values actually it would be the the public key values uh or it could even be addresses hashes of addresses but it's basically a lookup table of all the addresses that belong to you okay nothing else and then once you have that lookup table every time new transactions come through you just check them against the lookup table and then they also have a way of like if it's not in the table it will return a zero and if it's in the table it will return a one so their lookups are also they're not standard lookups they're

slightly more complicated um and yeah yeah so that that's basically it so anyways we can't glue them together cleanly without changing the output format and it just it require some thought like how to do it I think we could get there but I just don't know how to do it standing here today yeah quick question so going a little bit back to the bigger picture of how this exchange manages users assets uh so the the reason you want the secret keys to be sick p256 is because you still want to preserve them like to be native accounts is there another model where you can Envision like the exchange creating its own data structure just for proof of solvency and

just keeping a single account on chain for all of the user assets and then you know then you can use maybe BLS signatures nature I see I see yeah so it's uh yeah so so you're right about our motivation so we want to do it in a way that's the most flexible for exchanges they don't have to do anything special to prove solvency they can just take their accounting system as it exists and and then just run it through our protocol so that was the motivation now if you could put the onus on the exchanges to change how like where what addresses they are in and things like that so the simplest case would be if they pulled everything into one address right uh and then you could maybe prove something just about that one address without touching the rest I think it

would greatly simplify uh the protocol but yeah do you have a an attaction on the industry side that people interested in implementing something like that yeah so I didn't really pursue it personally I know some other people on our Provisions paper I think did a bit they talked and they didn't get a lot of traction and then I've talked to other people like kasas and and people that that do it and I think it's sort of the same story but uh if he breaks their scheme then they'll respond and fix it but uh in terms of getting them to implement a proof of solvy I don't know but the the one thing that I think would be helpful is a standard so there is this like ZK working group or something where they're trying to standardize a

bunch of things so if you just said here's a proof of solvency it's good enough uh it covers everything um and you can just implement it here's the code for it and all that type of stuff I I think that would go a long ways uh to to helping yeah the other thing I sort of gloss over too is an exchange has you know they have 10,000 different coins they don't just have eth and Bitcoin they have erc20 tokens and all sorts of things and so you sort of have to rerun this protocol for each of them um but anyways our our thing is adaptable to any erc20 anything where you can have a public list of who what accounts own what what amounts you can feed into our protocol so just to follow up I mean I haven't totally followed every detail we

did go Dan and I went talk to coinbase in like 2016 uh and they were like yeah they were very like enthusiastic but they were kind of like H you know we have other things to uh to look at in the short term and I'm not sure they ever really got there I think like Kraken has been doing something for a while I think it's just proof of reserves um I think that's right I think there's a couple others like I think even binance was doing something I think that they called proof of Reser um but I'm not sure it was actually a proof uh like I think yeah exch I mean I guess it's a

good sign that people are at least thinking about it but like various exchanges have said they're doing proof of reserves and it's just like oh an auditor looked at our books and you know said that we actually have a lot of reserves uh but yeah I don't know anyone who's actually done the full proof of liability as well which is usually the harder part yeah exactly yeah yeah so a lot of exchanges in practice will only do the one side of the proof and not the other um so actually what they do is they they tend to do these two like Steps three and four and then they they punt on one and two and just to just to clarify the uh the problem of non- sux synness comes from the first step right yeah yeah yeah

so it's just that you have to walk through the keys one by one um and and map them into BLS at least in our approach so there might be like a completely off equilibria way of doing it and you need to and that is the the reason for that is because you do a sigma protocol to map each one of them exactly so you um yeah so the reason it's not succinct is you treat them one by one you have a sigma protocol that does the mapping between the two even if you go back to the cops paper it's still um it's still a sigma protocol based proof yeah it's the fact that you have to do it one by one really that does it there are ways also where you can play with Sigma protocols if you want to do a lot of proofs and a lot of verification

they have the structure there are some optimizations that you can do that we did not explore at all like batch verification for them and things like that um but at the end of the day that's the bottleneck for us yeah and what do you what do you think would be the benefit of kind of like uh reporting this to the multivariant setting I'm thinking that the prover time would go down that seems like the main uh benefit of it um maybe proof size a bit and verifier size but they're already constant time and they're small so like it's not really really about squeezing the verifier more it's more about squeezing the sort of some of the structures that we have look like they would just fit cleanly um like the uh like when we do the two-dimensional kind

of Matrix that looks like something that that you could do uh in a multivariant setting a little more cleanly another thing too is I'll just mention is this this gadget book that we built I would love to do a multivariant version of it as well so what's the gadget book for multivariate polinomial look like [Applause]