Proof of solvency for CEXes using zkSNARKs

Transcript

foreign and today I'm gonna walk you through proof of solvency for centralized exchanges using snar so firstly I want to speak about the nature of Suma so Suma belongs to privacy and scaling Opera exploration PSC which is a branch of the ethereum foundation that is focused on cryptography and decay but actually Summa belongs to the open source community so as every project that has been built within the tirum foundation is basically a public good for the whole ecosystem and we have like

a an open source license so everyone that wants to use it for any commercial purpose is allowed to do that centralized exchange can freely use that even startups that are building solutions for centralized exchange can leverage our own backend so this is like kind of a disclaimer of the nature of of the project so I want to start with these two figures so maybe you know the one on the right you might not know the one on the left so the guy on the left is uh called Luca pacholi and he's a Franciscan priest they used to live in Italy during the Renaissance and he was kind of friend with Leonardo da Vinci Piero de la Francesca and he's famous I mean a

bit famous because he invented the concept of Double Entry bookkeeping he wrote a book called The Suma the arithmetica which is the reason why we chose this name where introduced the principle of Double Entry bookkeeping so you know like assets on one side liabilities asset must match liabilities and the problem is that this system is basically has some flaws in that and there are people like SPF that leverage this flow to basically fraud people and the problem is that like this same system has been used since Luca pacholi until today and that's how this book authentication mechanism work like you

have at the at the left you have like one party which is the company they build their own book and then they pass it to an auditor that says okay yeah it looks good it's everything is okay and then people like user customer must be must trust this auditor that they perform their job correctly so there are actually two big points of failure in this system one is on the company side so they might cook the books so they might present books that are just wrong and the second point of failure is on the auditor side so they might be corrupted or just I don't know not good enough to understand that

something is wrong so there are like this two big point of failure that are kind of by Design included in this model that is used today okay so that was like kind of the introduction now we'll go into proof of solvency as a general concept not not specific what we are building so profession means generating a cryptographic proof that are centralized exchanges solvent at a specific moment in time and when I say solvent I mean that the assets are greater than the liabilities it's like the default definition of solvent the liabilities from the point of view of a centralized exchange are the deposits of the user so they might be

denominated in every possible cryptocurrency but the important thing to note here is that they do not live on chain it's just kind of some entry in the database in the server of the centralized Exchange and ideally there on the other side there should be asset so the actual eat Bitcoin that are controlled by the exchange that are controlled by some wallets owned by The Exchange these assets are the actual ones that live on chain and the by definition they should map one to one the deposit of the user so for every Bitcoin that is kind of deposit in a centralization The Exchange should

control a wallet with one Bitcoin on that so if a centralized exchange is able to prove that they are solvent users are confident they can safely withdraw at any time so even in the case of like a bank run they can withdraw that was proof of solvency now get to ZK a bit generally what CK means it's like a mental model that I think can work you can help you understand CK so I think the first big priority of ZK is the computational Integrity guarantee so given a computation which rules are known by anyone approver can prove that

this computation was run correctly leveraging this proof so this is a very simple program in this case the rectangle in the middle is the program you have the input on the left and on the right you get the output so the pi that you see on the right is like the the xenoid proof and just by getting the zero Knight proof one we can call it the verifier can verify that this whole computation was run correctly and the second cool part of CK proof which is the ZK part I mean there are also other cool Parts but for this purpose there's the Privacy part that like the prover can selectively decide like kind of tune which part of this computation which

signal inside this computation to keep public and private so for example we can decide okay the input X and Y we can keep them private and to the verifier we can only give Pi the sum the verify will also know the rules of this program so they will be able to tell that I generated a valid sum starting from some inputs X and Y without having to know which are the inputs so this is a very toy example but we'll basically reuse this same model later in the explanation of the proof of solids so now we have ZK proof of solvency we get to ZK proof of solvency with Suma okay so you remember like the first

like um let's say traditional book authentication Approach at a lot of flows we want to move to a ZK based authentication approach and in this case you see there's no longer the auditor in the middle of the diagram but you have this Pro Pi that is able to tell the users and everyone actually in the world that the book were were basically accounted for correctly and that we use we leverage the two properties of Decay that we just mentioned so one is that the data of the company and and like indirectly of the users remain private and the second is that is trustless so we no longer have the this

point of failure that we had before in the previous system we'll go through that more in depth now how does it work that is the object of the presentation the short explanation of how it works is that the The Exchange will basically build this proof of solvency and then they will ask the user to verify that their balances was added correctly to the proof of services so you know that your balance on binance should be 58 The Exchange will generate a proof of solvency and then tell you hey can you check that your balance was correct so this is in short proof of solvency now let's go more in depth into

the old flow of the proof of solvency these are like the four main steps if as you can see the centralized exchange is at the middle there's some interaction with smart contracts and there's also some interaction with the user so everything that you see on the user side will be run let's say everything that you see on the Alice and the sex side will be run locally everything that you see on the smart contract or for of course would be publicly available to to everyone the first thing is that the centralized exchange will build the snapshot so the snapshot is like the it's like a an object like a container of all the data that needs to be used to

perform the proof of solvency and the main part of the snapshot is the Merkel sum tree so this is like the a core data structure of this whole proof of solvency thing is like a Merkel tree but it has an added property which is every time that you go one level up so every time you perform an ashing between two child nodes you also carry the sum together to the parent node so as you can see you get to the top to the root of the Merkel sum tree where you have an ash which is like a commitment to the entire state of the tree and the sum which is the sum of all the entries in the merkelson tree so this is like a

data structure that exists outside of proof of solvency but for the specific goal of proposal we see we use that to we use as entries or the user data so if you can see on the bottom left username Bob and balance 50 we can use them as the entries for the for the miracle some tree the this gets built by the centralized exchange stored off chain and only the root Ash will be public so nothing else will be public available to to the the people the second thing is the proof of account ownership this is not a ZK proof is something very technically simple so the centralized exchange will just collect

all their public keys and perform a signature of a message they will just submit it to the smart contract that will verify the signature and basically register the accounts owned by the centralized Exchange it's not private yet but this is something that we want to add to the system very soon the third part and here we are getting into the more specific implementation detail we have the proof of solvency so this has to be generated only once verified by the smart contract and this basically will tell that the assets of the centralized exchange according to the previous step are greater than the sum of liabilities as built in the

merkelson tree so this is going back to the this mental model of how ZK proof work you see that we have a we have a circuit this is how we call the CK programs the inputs are like the penultimate level ashes and penultimate level sums of the Merkel sum tree so if we go here it's like the penultimate level we just compute the last level of the mercosum tree to get the rush the the root and the root balances and the the further thing that we control is that that the root balances must be less than the asset sum which are like the the actual balances owned by The Exchange as

demonstrated in the previous step so of course this is not enough because I mean we are basically relying at this point we are relying on the exchange to build the Merkel sum tree properly they can just enter whatever they want like all zeros and they will pass the proof of solvency easily so we need to add a further step to the to the problem which is the proof of inclusion so here is when the exchange will generate a proof for each individual user so it's like a different proof to each user this has to be verified locally by the user and this proof will tell Alice in this case that she has been accounted for

correctly in the miracle summary as committed in the previous step like as the miracle Sentry was committed to with the root in the previous step so this is like a very simple zero knowledge proof is a like a it's a very similar to a Merkel tree inclusion proof the only difference is that we also have the sums together in the ashing process and there's also a very subtle detail I will sell I will say that the as you know like the circuits Works in a finite field Prime so if the this aggregated sum overflow the prime the basically the sum will get back to

zero and we'll end up with some liabilities that are way less than the actual liability so we also need to perform some rain check in order to avoid this overflow on the sums okay so at the end of this point like the Alice will get the proof we'll have to verify that the input are actually matching error around balance on the exchange and if this verifies Alice is able to tell that she was included correctly in the proof of solvency I mean the main issue in all the proof of solvency protocols is that is is dependent on the user verification so more are the user that verify the proof

they verified their correct inclusion more safe and more trusted will be the exchange and there are like plenty of uh I would say incentive mechanism that can be applied on top of this protocol to actually incentivize the user to verify their their proof of inclusion and therefore basically creating a more resistant proof of solvency in general so these are like a few benchmarks of our our system we use rust and especially a lo2 library for the proof generation so we achieve a good performance on the proof generation side and also an important thing to notice is

that since we are using a Planck based proving system we don't rely on a circuit specific trusted setup but we can leverage an existing setup which for example we use the one from Hermes in our case which was kind of let's consider secure from the ecosystem okay I will do a demon eye now so it's always you know it was working until five minutes ago wow so the the reaper that I've been using for this demo is this Suma playground and uh if you go inside sumada the main repo that we use to for all our libraries is called Suma solvency this

is like just a simple application for this for this event okay so let's start the first thing that I that I need to do is is like to to run a a blockchain in local so we are basically spinning up a blockchain and deploying a our own contracts there okay this is maybe okay it's working no

I guess this is the Wi-Fi let's try again okay I'm connected to HCC foreign usually Wi-Fi has internet okay hmm that's very

bad maybe I can use my I think I didn't I didn't pull before or give me a second what not working right okay no worries okay

okay so now we are basically launching our blockchain in local nothing uh nothing fancy okay so let's maybe can you see that yeah it's we'll be now deploying a few contracts okay so now we'll we'll deploy our main contracts is like one contract that is

called Zuma that is one performing all the all the verification of the proof and then that's the verifier that is like the auto generated verifier for our specific zero knowledge proof and we'll also meet some erc20 for the for the signer that is the one that is basically are like in this simulation the addresses of the exchange okay so we have the blockchain running now we have to [Music] um to run the CLI to work the old the old thing so I want to show you before what are the input files that we use to to this CLI so this is this is like basically a CSV file

representing the database of the exchange so you see username and balance is a lot and on this side we have like the signatures so these are like the fake addresses of the exchange and their signature of a message so we start the CLI entering the CSV path this signature CSV path the powersoft Tau that we use for the the The Trusted setup this is the private key of the signer which is simply the one that is interacting with the blockchain this is the local provider so now we will go through the whole flow of action the first one is the maybe I can split it

okay and I don't want to over complicate things the the first thing is that we will generate and submit the proof of wallet ownership so you see the the this proof is sent to the smart contract wallet to the to the wallet sorry to the smart contract and these are like the attested addresses of the centralized exchange now we'll generate the proof of solvency so this is actually a zero noise proof sent to the contract you see now the contract only at this time the contract will actually fetch the balances of the exchange at this block and compare it to the sum as according to the miracle sum

tree so this is the proof that I think yeah now is fetching the balances from the erc20 contracts and now we'll will work will work yeah as you see like the proof is very fast like the the the time is actually more about fetching balances from other contracts so the submit proof of solvency was called and uh and verified so now we have the only the all on chain

part is finished and we go through the proof of inclusion so the part where the exchange rate approved for each individual user so now the exchange will basically need to enter an index which is the identifier of the user in the CSV file we choose zero we'll create the proof we'll save the proof to a file and then that's the verification parcel in the let's say we generate this proof we pass it to a user and then this user has to verify it so first of all we need to okay input the file name then the root us because this is a public input of the proof that we need to verify against we need to make sure

that this root task is matching the one that is published committed committed in the smart contract and then we need to enter the username so we set this user 0 this is the username this is the balance the balance of because we are doing this for two assets but actually we can support any number of Assets in the proof of solvency in any type of asset actually and yeah basically the proof has been validated so you can run this demo with any CSV file any type of number of assets any number of signature and this will work so I think we have yeah I just want to

finish very quick and then pass to if you have some question the next steps as we want to add privacy we want to add instant finality but maybe we can speak about this in a separate place I want to thank my teammates Jean and Alex that are working with me at this project I didn't have a photo of them unfortunately and the last thing I want to leave you to this link on the left you see all of our repo and on the right a Discord Channel well it's not our Discord channel it's actually a general proof of solvency Discord Channel where research and anything happen so question so the off chance snapshot has a

different timestamp with your own chain queries yeah wouldn't that be a problem yeah yeah so actually yeah it's a very good point like the the proof of concept that we deploy right now is is basically there's like some latency between the two of them and the the idea that we want to implement is basically allow the smart contract to access historic data and we are working on an implementation with Axiom on that that can actually allow us to access data on some previous blocks so you can prove that you control some balance at I don't know one year ago basically but yeah it's a good good point could you tell us more about the

incentives for the user when they are asked to ask for the proof of inclusion yeah yeah good one so for the way we designed the protocol we don't want to be the ones enforcing the incentives mechanism it's I think it's more on the centralized exchange site to be the one deciding for these incentives but I think there are like some natural incentives that if you have a lot of money in an exchange you will be incentivized to verify but there may be some incentive mechanisms such as some lotteries or some some just like some price that you give to anyone that perform this solvency verification

yourself thanks anyone else thank you very much thank you