ZK Whiteboard Sessions – Module Eight: Achieving Decentralised Private Computation

Transcript

[Music] hello everyone uh i'm bobbin from polygon and i'm here today with pratush for malio and we're going to be talking about how to achieve the centralized private computations and how the zkp's tie into that have you been fantastic to be here um yes i'm pratyush and i'll be talking about first i guess you know what privacy actually means in the context of blockchains and uh when computation is involved and then we'll see how to actually how existing systems fall short and then how we can uh use zero knowledge proofs as bobbin said to actually improve the state of

the art with respect to strong privacy okay so i guess a real starting point should be how existing blockchain systems work and where they fall short in terms of the privacy guarantees they provide so if i take a you know existing system like ethereum or something right so let me just make sure this works so what happens there is that there you know there are some minors of validators which maintain this list of blocks which is the blockchain and um let's just call these entities m1 m2 whatever right and they're responsible for appending a new block to the blockchain

whenever you know at some regular period of time right so what does this new block actually consist of so let's say i'm a user and i want to publish a new transaction to the network what i will do is i will send my transaction to the network to the miners right and then they will check that this transaction is valid before they append it into the sort of 2b block or the the new block that is being going to be added right now what does this transaction validation actually look like so in the context of the smart contract blockchain such as ethereum um what these miners need to do is they need to re-execute the computation that

is occurring or is claimed to be occurring inside the the transaction so whatever smart contract is specified at this transaction they need to execute the code of that smart contract on whatever data is specified inside the transaction and make sure that the transaction is authorized by uh you know the correct parties whoever is supposed to were supposed to authorize the transaction um so yeah so this this re-execution happens with all the nodes in the network and then if i want to check the history of the chain i have to again do the re-execution of every transaction in every block from the beginning till the present right that seems to be problematic in some ways yeah so you know re-execution it's

a very nice and simple strategy which is why everybody uses it every blockchain that i know of uses it uh to check that the transaction is valid but it actually causes two kinds of problems first from a scalability perspective the issue is that um you know in this transaction the code in there has to be re-executed by every node in your network right and then if if your network contains nodes with different computing power so say a super computer a desktop computer and then maybe just a phone which has a very small computational ability then if your computation if your transaction is heavy then maybe only the trend the supercomputer and the full

desktop node can check the transaction um in time right and this is a problem when we have many transactions in the network which we do want because we want to scale up our chains right so there's like many transactions coming in every given second and what will most likely happen is that our computationally weak node will not be able to keep up with the um uh with the rate of transactions that are coming through right so we will sort of we're limiting the kinds of nodes that can participate in checking the integrity uh of our of our blockchain and this is you know not something we want especially when you claim to be a

decentralized network okay so that's from a scalability perspective from a privacy perspective the issue is that each transaction it reveals at least three kinds of data first to re-execute you need to know which program you you're executing right you need to figure out okay i'm executing say a payment smart contract or something erc20 so you need to execute the code for that then you need to know what data is being is being provided as input to this program right so this is information like sender recipient value in erc20 so on and so forth right and finally you need to know the identity of the person who's authorizing or like sort of participating in the transaction right

so you reveal information about the participants of the of of this transaction in particular right and this information sort of is encoded in this transaction and once this transaction goes to the to the blockchain and is uh enshrined there it sort of lives on the blockchain forever forever for everyone to see and indeed it needs to live there because if i want to check the history of the chain i need the transaction to to execute to make sure that the data the state was updated correctly right i think in regards to like so these are clear in regards to anonymity i think even the original bitcoin paper at least the claim was that you can separate the because we we don't

actually know the participants we only know their keys so maybe there is some degree of anonymity there yeah so that's a good question right so maybe you know it's clear that what why we want to hide the data that is being provided as input into the transaction but if we for example um yeah this participant is actually not like say you know pratyush mishra here it's public key 0x59 whatever like some random looking string right so it doesn't actually reveal directly my identity but the problem is um this sort of guarantees what's only called is called pseudonymity right so just a different name for for my identity and the problem is that say if

i reuse the public key that i use in transaction one in another transaction then anybody can see that these two transactions were executed or authorized by the same person right so then they can see exactly that um uh i'm you know using this public key to the same person is using the same public key to pay for coffee at starbucks and then participate in some complex g5 protocol and then like this can cause all kinds of problems right so if they know that this public key uh is owned by a whale and that whale goes and shops at a particular starbucks then maybe you could have some you know you can stock that veil or basically pseudonymity doesn't really lead to uh any sort of strong anonymity guarantees

because you can piece together the pieces of information and then build a profile of the person that uh is behind that public key yeah and i i think even in everyday transactions uh you know let's say you're receiving your salary payments in some account you don't want to necessarily exactly transfer money from that account to your friends because you don't necessarily want all your friends to know how much money you're making and you know all of that stuff yeah and like you know if you're going to the doctor and for a particular treatment you don't want the world to know that you have you know you're going to cancer specialist so yeah the sort of lack of uh privacy on that perspective all this anonymity uh really impacts every aspect of um you know a person's life because finance interacts with every aspect of a

person's life also from a fungibility perspective from i guess from the integrity of the currency perspective you want each coin to be equal to every other coin right so like if i give you a dollar you shouldn't you know say okay this dollar is only worth actually 80 cents you wanted every dollar to be worth the same but with bitcoin for example i can go and ethereum i can go and see okay this bitcoin was used in this transaction which is part of like some criminal activity right so actually i don't want to transact with that or if i transact with it i'll only you know value it at like point eight bitcoins or something like that right so now you've lost this fundamental property of the currency which is that every unit is exchangeable for every other unit

now we talked about ethereum and bitcoin and but the models are there are slightly different right ethereum is account based and bitcoin is utxo based so yeah um mine like basically there might be a claim that utxob systems are better than account based system so i'm curious how how you think about it yeah so maybe let's take a quick look at uh the difference right so the utxo model basically what happens is that there's a list of accounts right and then when you make a transaction you update the state of this account which is you know saying the sender's account and update the state of this account so i'll subtract the value of the transaction from this account and up add the value of the transaction to this

account right now privacy for for this is quite difficult because you need to hide which entry in this list is being updated for every transaction and while we have some crypto techniques for that and they're not very efficient and like probably in the context of blockchains the most efficient thing would be to somehow like update every uh entry in the sort of list of accounts some with dummy entries if they're not participating in the transaction and others with actual entries if they are participating with actual updates if they are participating in the transaction so in the in the account model you know we have uh you know

it's very difficult to achieve any sort of anonymity so that's why existing work on achieving private payments and private computation actually focuses on what's called the utxo model which underlies uh bitcoin right so maybe let's quickly just go over what the utxo model looks like so basically in a utxo model transaction um what you have is you have some input coins right and some output coins i'll just say one input and two outputs for now right um and the idea is that these sort of split you're sort of in some sense consuming your input coin and

creating two new output coins right and so basically you maintain in some sense a set of you know active coins or whatever right unspent coins maybe so in bitcoin parallax this would be like utxos right so when i construct a transaction i consume or i take some utx so it was the output of some previous transactions so this came from some you know tx prime or something right and then i produce and then i mark that utxo as spent now right so it becomes like i said stxo and then i produce two new coins right uh c2 and c3 which are then appended into the list of

active unspent coins right so these are now the new utxos in the uh in in our uh in our set of active coins and what are key properties do we do we want to check when we execute this transaction we probably want to make sure that we didn't create any new money or something exactly right so let's okay so this is what the transaction looks like but what does a validator need to do to check a transaction is valid before appending it to uh to the blockchain right so maybe i'll write it here just to keep it separate from things you might erase in the future so the first thing you want to do is you want to check that the

utxo that you're spending that the spent coin is that uh i guess exists it's active still or something yeah is active right or was active before the transaction right um and you need to check that you know that it is authorized right so basically i'm not spending somebody else's ut right only the person who owns this utxo is able to uh consume that utxo or spend that utxo or that or that coin right so that's one the second property is you want to check

that value balances are preserved right so check that value is conserved and what this just means is that the sum of the input and output values is is equal right so c the value of c2 plus the value of c3 should be equal in this case to the value of c1 and because of this you basically lose data privacy and because of this um you lose the anonymity right and i guess if there is like if it's not just simple checking uh of um you know uh if it authorized but like if there is a complex program that that is there that's where you will lose the functional privacy as well yeah so so this is yeah so you know we're talking about these

changes about general computation bitcoin is a chain which just supports one computation which is transferring money and in that case the value the computation is checking that the value is conserved right um so yeah so coming to your point of data privacy versus anonymity and so on right so yeah you're completely right that these two steps or these two properties are the ones which harm the anonymity of users because if i need to check that that you know that the c1 that i'm spending in this transaction was not spent in a prior transaction i need to have you know some unique identifier for this c1 which i can then refer to in the list of active coins and check that okay c1 the identifier of c1 actually lives

inside this list of active coins right and then i could subsequently cancel off that identifier once i've spent c1 and then append the identifiers for c2 and c3 right but now because this identifier is unique it allows me to link c1 to the transaction that created it right so then i'm able to build this transaction graph going backwards off you know every ancestor of c1 in some sense um this you know completely harms privacy and then finally also when i if i need to check that the spender is authorized to spend this utxo you know the simple way to do it is to you know include a signature over the transaction but the signature has to validate against some public key and

whichever public key that signature validates against in this case it would be the signature of c1 for the public key of associated with c1 right um yeah that public key again reveals uh the pseudo-nimitz identity of the person who is uh sending the transaction right so how do we bring zkp's uh to help with this yeah okay so that's a fantastic question we'll start with what is the easier property which is first you know showing how we can enforce that value is conserved without um uh yeah while hiding what value is actually

uh participating in the transaction right what is the sender value recipient value and so on yeah okay so maybe let's see how we can do uh this one first okay so what we will do is if we actually open up this thingy a little bit so there's c1 and there's some you know abstractly there's some value associated with the coin that you're spending and there is some public key associated with the coin that you are spending right which you know specifies which address or is the owner of this coin okay so what we can do first is we want to hide this information we want to hide the value is conservative with the public key

maybe we'll just focus on hiding the value first and we'll come to the public key later so what we'll do is instead of including the value in the clear we will actually hide the value let me put this away under some sort of cryptographic hiding mechanism in this case we'll use what's called a commitment so i'll just put a box around values that are committed right so there's a uh commitment to the value here uh commitment similar commitment to the value here and a similar commitment to the value here and just to clarify the commitment doesn't reveal anything about the value but it doesn't allow anybody to change the underlying value right yeah

fantastic so yes yeah quick overview of commitments and basically cryptographic uh primitives which allow you to uh sort of you can think of them as lock boxes which allow you to uh you know commit to some message in this case the value um while hiding on information about what the message is but you can't sort of open the same commitment to do different uh values uh or two different messages if i'm the minor like how do i now check that um because i don't know what the actual values are how do i achieve that right so if it's preserved yeah so the hiding property of the commitments ensures that okay now this coins they don't reveal any information about what value is inside them right but they also make it impossible for the for the minor

validator to check that the value is conserved so how do we do that and this is where we introduced our first use of zkp's right so uh so we'll include inside the transaction also some proof pi right [Music] and what we'll enforce inside this zero knowledge proof is first we'll sort of you know open up we'll take as input all these commitments so we'll take uh i'll just call this c1 maybe cm1 cm2 and cm3 right so we'll take cm1 cm2 cm3 as input inside the as public input

to the zero knowledge proof um and then we will open these right so we'll open all of these and then check that v1 is equal to v2 plus v3 right so we'll just sort of just move the maybe i'll write it somewhere here and because we'll have some other stuff which will come in the middle so we check that v1 is equal to v2 plus v3 so instead of having the miner perform this check we just have the transaction constructor provide a proof that enforces this check right so uh we've moved the competition away from the miner into the uh into the proof itself right and

there's the zero knowledge property of the proof system ensures that even though we're opening these commitments inside the the proof they reveal no information about the contents of the commitment so no no intimidation is revealed by this pie about v1 v2 v3 right so this allows us to get our prop our value conservation check right so we're good on that one okay so this gets us data hiding um but now we still want to achieve anonymity right so how do we actually go about doing that and there's basically you know these two

steps that we need to to do correctly let's maybe tackle the second one because it's a bit easier so what we'll do is right now there is this public key that is living inside the ut exos right so there's the value which is inside the commitment but also this public key abstractly which is living here so what we'll do is we will move the public key also inside the commitment for this coin right so now the public key also or the address also lives inside the commitment so we'll open this up and then instead of checking whatever signature we were checking in plane we will now just check the signature inside the zero knowledge proof also

okay so this allows us to move this is authorized check again inside the zero knowledge proof right so the proof itself almost becomes like a signature or it validates the signature in some sense in some cases exactly yeah in some sense um actually yeah if you look at how the first work to actually achieve this private payments in in the space and did it they didn't have a signature they used some other mechanism like proving knowledge of the public key in some sense insight is your knowledge proof so that's how they did they did it right okay so now we've we're almost there we've achieved the data hiding and then partially anonymity but we need to check that the coin that we're spending is active without revealing which coin

that we're checking which coin it is that we're spending right so we need to provide a way for the validator to check that the coin is is the spent coin is actually you know the correct coin but while hiding completely what uh what that coin is so the approach taken by uh zero cash which is as i said this first work for private payments in in the blockchain space what they did was they said okay instead of having this list of active coins which is updated and uh and as transactions come in in and out we will just have this ever growing list of commitments right

so we will have a list of commitments right and as new transactions come in we will append the output commitments to this so right so if uh we have some list then the dot when this transaction comes in we will append like say c2 and c3 at the end of the list additionally we will build a merkle tree over this list of commitments we can call this the commitment tree and then the main i guess one of the key innovations of zerocash was instead of

providing the commitment of the utxo identifier in the clear inside the transaction we just have the transaction constructor prove that the commitment actually exists right so this allows us to ensure that the commitment was created in some past transactions it is the output of some valid transaction that happened in the past right so what we will do is we will check that cm1 oops let's check that cm1 it belongs in the commitment merkel tree and we can do this via some standard mercury authentication path checks right then merkle tree also

becomes the input exactly so you will need to provide additionally the root of the merkle tree and then the validator can check that you know this claimed root that we're providing as input is actually the root of some historical like the root of the merkle tree at some point in the past right and i guess how do you make sure that as the same transaction doesn't spend the same like we used to mark which ones are active or not here there is no information which one has been spent or not exactly right so now we've sort of in some sense gotten rid of this coin entirely from the from the transaction right which is you know what we want for privacy but uh and okay so now we know we're spending some coin from this list of coins but how do we know that it's not

already been been spent right how do we know that the cm1 was not used also in a different transaction so to do that you can think of this as the set of you know set of all coins so what we need to do additionally is to make a set of spent coins right so to do this um we want some set of uh i mean set of spent coins also so i'm just dividing this off okay and how uh maybe i'll just draw the c1 in dotted lines to indicate that it is maybe in in

green to indicate that it is hidden right so this c1 actually does exist in the transaction it's just completely hidden so c1 is here and there is a commitment which has the value and the public key right okay so now how do we maintain this list of spent coins without sort of linking the entries in this set with the entries in the set of all coins right so we want to be able to check that the c1 is not in the set of spent coins but how do we do that without checking it against this list okay so the mechanism that is used in

zero cash is basically you include inside your commitment an additional entry or additional piece of data called the serial number or nullifier now this is a unique identifier for the coin right similar to the commitment it's completely unique there's one per per coin essentially and the idea is that when i'm spending the coin i reveal as part of the transaction the serial number also so this is not hidden anymore this is the actual serial number for the input coin right do you reveal the serial number or the hash of serial number for example

yeah so i'm hiding some details here you actually how you actually compute it is that you have some some secret thingy in here right and then you hash that along with your private key that is associated with this public key right um you hash all both of those together the secret key and the serial number nonce or whatever and then you output the result of that hash um but for uppers i think it's fine to just as assume i think the important property is that the serial number is in no way can be linked to the original coin that was to the commitment yeah so from this commitment i have no idea what the serial number for this cm2 is that is completely hidden we have no way of figuring out like if later on i spend c2

there's no way to link sn2 with this cm2 at any point in time okay so basically i have this list of serial numbers uh so let's say sn one level up to like sn n or whatever right and what the validator does is when they see the transaction they check that this serial number that is input in this uh that is provided as part of the transaction is not in the list of spent coins and uh the zero knowledge proof asserts that you also provide instead of providing cm1 you provide sn1 as input right and then you check that sn1 is the serial number for

cm 1. so in this um to check the validity of the uh but that the coin actually exists we use a merkle tree why can't we use a miracle tree for serial numbers why why don't we instead of outputting a serial number just include the check for serial number in the proof yeah so that's a good question right so a priory we just have this set of spent coins which keeps growing as you spend more and more coins over the lifetime of your system right so if i have two to the 30 payments then i will have at least two to the 30 entries in this uh in this list right and this is going to hurt the scalability of our system one way to work around that is instead of

having the validator or miner check that the serial number is not in this list we can have the proof itself assert that right so we'll build as you said another merkle tree this is the serial number or nullifier merkle tree and then we we can add another line here which asserts that you know check that sn1 does not belong in this merkle tree for example right but what what would be a challenge was that i mean um as far as i know like zcash doesn't do that for example right yeah so the main reason to avoid that is from the perspective of the user right they always need to use the latest merkle tree route at every time step right because

otherwise what ends up happening is so let's say i use the serial number merkle tree from 10 blocks ago right i could have spent the serial number in those intervening 10 blocks and then nobody would be this the the proof would still be valid because according to the route which i gave it which is the 10 blocks old route uh the non-membership proof would go through right but in the meanwhile in the last 10 blocks i spent the that coin and so now i've double spent the coin so basically from from that that's the reason why we need to so you could now you could ask the user to always maintain the latest you know latest uh non-membership proof for their coins right but this means that if i go

offline come online then i need to sync with uh the network right and yeah but proof could become stale if like it didn't get through the network fast enough yeah so yeah so if it didn't get in block one then i have to make like if i if my transaction didn't make it into this block then i would have to wait another block as you said exactly right and then i would have to make another proof for that new block and so on and so forth so this is a lot of pain from a user ergonomics perspective so it's much easier for the miner to check this but um that probably creates another problem because this list of nullifiers is ever growing right you can't ever get rid of them yeah so what you can do for example is say you know i'm going to have an epoch

of maybe three years or something like that right and then all the coins within that three years so i'll maintain like a serial number list for those three years right and then if i want to so then let's say that three-year period gets over then in the next three year period i can enforce the policy that okay if you're trying to spend a coin which is from three years ago right from the last epoch then you have to provide the non-membership proof right uh but for coins in this epoch you that are that were created in this epoch then you will just check the serial number so basically this maybe gets around the problem that your proof becomes stale because it's not like you know i'm

asking you to prove non-membership like the three-year-old epoch is always going to be a three-year-old epoch always so it's not like the merkle tree for that epoch is going to change so we don't have that problem so you could yeah so that this way you could this does harm your anonymity because it reveals oh is it from uh is the coin that is being spent from this epoch or from you know some past epoch and that sort of partitions you had an empty set a little bit um but you know if your system has you know the sort of scale where the list of nullifiers growing is a scalability problem then your anonymity set is in practice going to be large enough like in three years you're going to see enough transactions that your

anonymity set is big enough yeah i think for like if you're dealing with like 10 transactions per second you're probably never realistically going to face this issue but if you're dealing with thousands transactions per second then yeah i mean exactly and in that case as you said you know an animated set is big enough over a course of a year or you know maybe even less than that who knows exactly yeah okay so yeah this sort of basically is the high level overview of how so this checks this off right exactly right so now we have this is basically the construction of zero cache which is uh shows how to achieve these private payments right so this is how you would get a private payment system on top of a decentralized ledger okay so so one issue with that is that this is like a fixed dkp you're

proving a specific circuit so like you don't get the smart contracts or whatever else capabilities so it is nice you have private payments but it's you know limited in functionality yeah exactly yeah so this is yeah so this is already i mean this is a big step for um you know we didn't undo private payments and now we know how to do private payments uh completely private payments but you know people have moved on from just doing simple payments with bitcoin and now the excitement is all in doing you know all kinds of heavy computations or interesting competitions with smart contracts right and this you can this is also one computation the competition is checking the value is conserved right but we might want to do something more complex than that right and maybe you want to do a

decentralized exchange or maybe you want to do some sort of auction there's a unlimited number of things that you could want to do with smart contracts and this doesn't support that okay right so we stopped off here we were talking about uh how we achieve private payments we want to achieve smart competition uh smart contracts inside this same privacy paradigm right so if you actually take a look at this construction the only thing which is really specific to the use case of our application of payments is just this line here right which corresponds to this check right so this is where checking one specific program's correct

execution namely the sort of the payment program or the payment application and the check for that is just checking the value conservation so to generalize this maybe we just get rid of this specific step here right and maybe i'll just rewrite this to put the signature up above so 4 check the check sig against pk okay so these are all the checks which are sort of going to be which are sort of agnostic or completely independent of the application right and then we have one more which is

the application specific execution right so we have some computation that is executing and we want to check that is executed correctly and so then this check now becomes checked that application executed correctly okay now the question is where does this application live what application now we're executing we'll get into that in just a second uh check i guess application execution all right this is the check that we want to do right so okay which application what execution what data all right so let's just take a

look at that so right now we have a handle on um i guess three things right so we have this input coin or something like that let's instead of since we're not talking about payments anymore let's change the terminology from coin or utxo to record which is what we use in this xc paper and it's just some sort of you know entity which holds some data right so your record has some data inside it so we have an input record and two output records in this example so the question is what application are we expecting the correctness of and the answer is in some sense whatever application is specified by this input record right so what we'll do is inside

the commitment we will include uh this is getting a bit crowded uh where did i put my oh the eraser is right here so we just rewrite this a little bit okay so we have our value our pk and the serial number but now we will also have some program id or something like that right so let me call this pid or something like that okay and is that a commitment to a program or is it something else so for the moment i'll leave it abstract um and we'll see we'll fill in the gaps of you know what

how to go from pid to actually the application okay right and so here what we'll do now is you know check that program for pid executed correctly okay right now okay so this is fairly simple extension of where we were before right but this one change actually opens up a whole box of pandora's box of uh of things in terms of that need to be done because okay this is a very innocuous looking line but actually to implement this sufficiently in a

construction like something that you can run in in some decentralized network it's actually quite tricky so let's see what the problems that we encounter are so the first issue is that for all of the efficient zkp proofs uh zk proof systems that we know right they all work uh at least in terms of you know the ones which have the best proof size for example they all work with what's called circuits right and so the circuit is like some description of a computation and they work with so-called fixed circuits right so you do you specify a computation as a circuit and then you make a proof for that circuit right

but this requires knowing ahead of time what that circuit is right and here essentially what we're asking for the zero knowledge proof to do is say hey please maintain an open slot inside yourself for uh something that i can just plug in right so this program which is going to be specified arbitrarily i need to be able to plug in any arbitrary program and then you have to make a proof about that now the techniques we know for do this to do this um there's quite a few right so one technique is what's called a universal circuit so it basically has exactly this like slot where you can plug in the code of any program and then it'll run and execute correctly and you will enforce that the program executed correctly right now the downside for

these universal circuits is that they're quite expensive in in practice um yeah they impose at least like a 10 15 20 x overhead compared to if you just had like one hard-coded program in here okay so that's one uh approach the other approach is instead of checking that the program executed correctly right we can use what's called proof recursion and instead just check that uh a proof for that program executed is is valid right so the proof that the program executed correctly being said check that in here right so let me just rewrite that uh

so let me erase this and we'll just put program proof is valid check program proof for pid right and that's all we so okay so we've done this right why does this help right if you think of it taking a step back there's no reason that this new check is more efficient than the previous check that we had of a universal circuit and the the key idea is here's where we sort of leverage the succinctness property of these uh snarks right uh so the idea is that checking this this proof is going to be

much cheaper than executing the program itself right so this proof you can check it in let's say you know 10 000 or 20 000 r1cs gates whereas the program it might correspond to like you know 1 million r1cs gates right so checking this proof is only going to cost 20 000 gates no matter which program is being executed inside the which corresponds to pid right so by doing this where now we have one step of recursion to uh we just yeah we validate just one proof instead of rerunning the program basically by using recursion you fixed this is a fixed circuit itself exactly and you can provide um the fixed circuit itself knows how to verify

whatever proof but then you can provide proof for any program to it and it will still be exactly right that's that's yeah fantastic way to put it so now we've instead of having this circuit which has this empty slot to plug things in right now we've fixed the circuit the circuit is always doing just these steps it has some zkp verifier uh hard coded in right and then we can provide whatever input proof we want to that um to uh to that uh verifier sub circuit and in practice what we need to do for this is then this pid it actually becomes a hash of uh if you're familiar with terminology there's this verification key which corresponds to the program for many snacks of interest so if you take grout

16 planck marlin sonic etc right they all produce a short digest or hash off the program which is called the verification key which the verifier can use to to check the proof right so this pid actually becomes the verification key for the we'll call this vk for the program so vkp right and this is again vkp okay and i guess what i didn't mention before that instead of having the value in here we can have any arbitrary data so i'll just call it d but yeah you can put whatever byte string you want in there and then you

will check that this you will check this proof against vkp so you can take the program proof against the pkp and the idea is that this vkp is going to be again very small um and a fixed size no matter what the program is makes sense and then does the uh so in here we had like two outputs being generated does the does the circuit somehow like is it flexible enough to say some uh programs can generate more than one like one output two outputs ten outputs whatever okay so this is a very good question and it ties in to the questions of data privacy and function privacy also right so maybe taking a step back from this construction and going back to our properties of data privacy function

privacy and anonymity right we achieve anonymity just because we didn't change any of the anonymity infrastructure from the zero cache construction data privacy again is preserved because you know they only have opaque commitments in the transaction and function privacy is achieved because if this is zero knowledge right we reveal no information about which verification key is being plugged into the proof right so the zkp hides information about the program so this gets us all three or four properties of that sub properties for privacy okay now the question is what happens if you know i have this is one transaction what

if there's another transaction which has inside it so let's say this tx1 for example it had inside it uh two inputs and two outputs right uh this would result require a different circuit for this zkp right which two which supports two serial numbers two uh two commitments for the outputs and then potentially your proof would also look different right so a priory there is no [Music] reason why we can't just say okay i'm just going to have different circuits for you know transactions with one input and two outputs and transactions and another circuit for a transaction with

uh two inputs and two outputs and another one for five and three out whatever whatever combination you like you just fix it ahead of time and say these are the transactions that i would like to support and you would have the zero knowledge proofs for that right and then you have to make sure that your program that is that you're using actually supports that rit of the inputs and outputs right now so this is a thing that you can do very naturally but it does hurt a little bit are guarantees of function privacy and the reason for this is because if i know for example that program a only works with three inputs and two outputs right

then every transaction which contains three inputs and two outputs is a candidate to be program a and if i know that program b only accepts one input and one output then i know that there's not going to be any overlap between the transactions for program a and program b so then i can use that to maybe figure out okay this transaction is definitely not program b so that's sort of harming and partitioning our anonymity set for our various uh programs right so that's why in this xc paper what we did is we just fixed two and two out so you have two inputs and two outputs no matter what um actually in in yeah in the implementation and the idea is that using this two and two out you can actually construct you know any higher arity that you want

um as long as you also support like dummy inputs and dummy outputs and then um so this is kind of an abstract construction like if we talk start talking about the concrete proving systems um yeah i think uh in sexy original paper you guys use the growth 16 right so like what are the different trade-offs of you know different proving systems here yeah so yeah so yeah there's with you know we have every year sort of new proof systems coming out and it's a very fast moving space so there's obviously different trade-offs so in the sexy paper we we use actually this con this proof system called growth smaller 17 which uh in retrospect you know we didn't need to use that but basically it provides this

property called um simulation extractability which is necessary for for this construction overall but anyway so yeah so uh the problem with this the proof system that we had in that uh at the time of writing the paper is that uh you know if you've heard of zika stocks you know often that they require this trusted setup uh kind of uh to produce the verification and proving keys right now for groth mahler and groth and grout 16 these proof systems they require the trusted setup to be performed once per circuit right so if i perform uh if i have for example you know the one in two out circuit

that will require a different set up from the two and two out circuit right and maybe this is okay you know if you're just talking about a small number of circuits for which do the same functionality but in the context of arbitrary computation that is specified by the user right now the user will have to other the program developer will have to produce a trusted setup for uh every program that they produce right and the user will have to run this or trust this trusted setup was performed correctly for for any arbitrary program right and so we know of like decent techniques to reduce the overhead of doing this such as you know the ceremonies that have happened for zcash and basically you

know everybody has participated probably at one of these mpc ceremonies now but yeah it's a big hassle to ask that this every time you want to deploy a new smart contract you have to run a fresh ceremony with like hundreds of participants right so ideally you don't use rothmother 16 or 17. so what do you want instead what we've done right now in elia which is a version of a deployment of sexy right is we switched out um gros 16 for us marlin which is a proof system which has universal setup it's like planck or sonic and the idea there is that this verification key can be derived just from the program without requiring any trust in the

person who's deriving the verification key right it doesn't require any secrets for the trusted setup it's like a transparent setup once you have some you perform basically the ceremony once and then you take the output of the ceremony and then you can deterministically specialize it to produce this verification key and anybody can check that this was produced correctly and the benefit of this is that now when i'm a developer who wants to deploy the smart contract all i need to do is i need to do the deterministic step of deriving the verification key and then anybody can check that whatever i'm claiming the verification key is is actually the correct verification key for the given program okay now one question i have is could you have kept this as growth 16 but like the verifier inside here would

verify marlin circuits or something like that or is there is there an upside or downside to doing that yeah so you can do exactly that right so you can have because um really the only place where you need this universality is the program proof right because that is the program so there's like many programs with only one this sort of transaction circuit so you could put this as a graph 16 and this as marlin or plonk or whatever is your favorite proof system um in the end in in earlier we just went with mileage just for simplicity so to avoid having two different proof systems in the code base in general what are the other differences between like what you guys had in the original sexy paper versus uh what you guys are doing with everyone now and there's actually quite a few differences um

so i didn't explain it quite here but in uh sexy so we didn't actually just have um one program for the entire transaction what we had was each record was associated with a with both the birth predicate and the death predicate so maybe explain those a bit more because i think this is the first time that those came up in this conversation exactly right so that's that's insane let me just maybe i can erase this because we're not going to be touching it anymore okay so what we said in sexy is that you know each record there's two events associated with it it

is created in a transaction or is born in a transaction and then subsequently it is consumed or dies in a in a subsequent transaction right so there's these two events associated with the record so maybe we should allow the user to specify programs that happen at each of these two events right and in practice what we found was actually we do need both of these events to even get simple applications such as uh you know private user-defined payments and so on right it's coming back so we have inside our record so now these are no longer coins these are records right so i'll change all of this later so inside your record you have this commitment and

inside this record commitment we have our data our public key serial number right but we will also have a verification key that corresponds to the program or predicate that you want to execute upon the death or consumption of the record and a program that will be which is is executed when the record is created or is born right so this is the inside the commitment okay and the idea is that so this actually results in a slightly different transaction circuit proof so what we will do is we will for each input record you know check proof

for vk against vkd uh d right so because the input record is being consumed or is dying we check that the user provides a correct proof against the verification key the death the predicate verification key for that uh for that for that record so so if there's multiple input records so there's also like a r2 which is the input then you also check the program proof against that bkd and similarly for each output record right check a proof against vkb right so and what kind of things would

so like that that predicate is more or less clear but what kind of things can you enforce with the birth predicate like why do you need it yeah so it's actually a good good question right so um a priory it's not clear where we you know okay so the record is born and it dies right so you have these two things but you could also have 10 different verification keys are programs which are executed at various points in time right so um so yeah what can you actually put inside this vkd or vkb right so maybe by analogy you can think of this vkd for example as being a version private version of bitcoin script right so in bitcoin script uh there's like the the script you can

associate with the particular utx so uh some script which is executed or is you know is executed when the utxo is spent right so this vkd is somewhat similar to that in that this is requires this predicate is executed or this program is executed when the when that record is is being spent okay in contrast the vkb you can in some sense um i guess think of it as a way to maybe propagate uh or okay how would what we ended up doing in the zexty paper in terms of the application that we designed was

the pattern that emerged or this was that this vkb was more like the application identity for that application right so if i'm doing a payment application right i would set this vkb to be the one which is doing the conservation of value so it'll be the one that's saying the input value is equal to the output value and the idea is that so let's say this c2 and c3 are supposed to be coins of token a right they're these records represent token a coins now i want to ensure that whenever a coin of token a is created it is the case that the value is conserved right so what i will do is i will say a coin

or a record corresponds to a coin of token a if it has birth predicate which is the value conservation predicate for token a right so i'll specify some verification key which is specialized maybe to to token a right and that verification key will enforce that it'll look at all of the records in the transaction check which all have vkb as the as the predicate as the birth predicate right and it'll enforce that the value that is stored inside those records uh the output value equals the input value right so you can think of this in in terms of like the design pattern that emerged as we were writing this xc paper this becomes like the program id or

application id for your application this vkd becomes more like a spin condition so it's like you know this transaction or this coin can be spent in these conditions so it can be like okay if there's a signature from not only the original sender but also maybe some authority um it it yeah it's more like something ad hoc that you can add on afterwards it basically seems like it's imposing restrictions on what the outputs could be or what the rules for creating outputs are it's if the death predicate enforces a rule who can like consuming the the predicate whether you can't uh take it this one says well the shape of the output needs to be uh exactly yeah yeah that complies with whatever is specified

by those yeah exactly so vkd sort of specifies the conditions under which you can sort of under which this record is allowed to be spent and vkb says that whenever a record of this type is created it must satisfy these conditions at the time of creation so yeah this is kind of abstract and uh i guess i'm not sure we have time to actually see how this interacts in an actual application but um yeah that's sort of the high level takeaway but i think without this like you won't be able to do like sophisticated smart contracts and things like that it will be very limited it becomes it becomes quite difficult yeah um yeah without you need i think you really need both of those to actually get any non-trivial interactions what we found

in the paper yeah um yeah that makes sense right so that was one uh let's go back to the question yeah what changed between zack c and elio and like how the uh how things are different yeah so what we actually did in earlier was we moved back to the previous model i had on the p on on the sla on the board i guess which was instead of having these input and output predicates uh the death and birth predicates we just had one program proof which is suppose is responsible for the entire transaction right so um then if this guy has some program vkp then this guy also has that same program vkp and this guy also has

the same program vkp so in some sense we combine both the predicates into into one at a high level and we propagate all of those the same predicate all the time this sort of changes the design pattern that you get when you're actually designing different kinds of applications but i think they're sort of in the end it ends up being um equivalent though yeah so so that's one change so we we go back to the simpler model um at least in the beginning it's probably simpler for people coming from ethereum land to reason about for example just one one program in the in the transitional transaction instead of two different

programs right that's one thing and then the other thing was we found in practice for many applications function privacy is sort of ends up being compromised anyway the moment you have interactions with multiple um between multiple applications for example or with public state or with you know we going back to the earlier use case you know some applications only need one and three out some need five and two out and in practice you want to support those applications with the maximum efficiency so it becomes a case of yeah it doesn't actually make too much sense to have keep around function privacy because it gets compromised anyway

because you reveal these tiny clues which leak which application it is so what we did was we sort of moved these this program check outside the uh the so we don't have any zero knowledge proof recursion anymore so we sort of this is one proof and then we include along in the transaction additionally the program proof right and this is the one which asserts that the proof is uh yeah that the program executed correctly and do you guys have a distinction between like a private state versus public state or is it all public or private or how does it work

yeah so again another thing was in sexy we were trying to really go for like stretch the limit of okay what is what are the kinds of computations and what is the model for these computations that you can uh do when you want to have the maximum privacy right so this is why the strong focus on function and data privacy right but in practice it ends up being the case that uh you know we also the function privacy ends up being compromised anyways right and for many applications you do need some interaction with some public state right so then you have to maybe uh leak some privacy from that aspect anyways

so zexi is extremely one one was exploring one extreme of the spectrum and but an alias was to support uh i guess more normal applications we do support like public state also so you know you can reveal whatever's inside this commitment in the clear if it's needed or if it's like a uh some global state which must be interacted by multiple users at the same time right uh then i guess to be i can explain what the problem with global status and quickly yeah yeah i think i would be very interested uh in understanding because yeah i think public versus private state as you said like if if there is like more than two people like three four i mean maybe it's

manageable but as soon as the number is more than a few you can't really do anything useful yeah exactly right so yeah the problem at a high level is okay so let's say i have uh i'm interacting for example with unit swap right you know swap at a high level the there's like some balance for the various currencies that are stored in the contract and some exchange rates that are that are associated with the result of the balances all right yeah so the problem with global state is that so again with uniswap we were looking at the example of uniswap so um the idea is that whenever a user transacts with the unit swap sort of contract and updates their balances of

you know taking uh some token a and putting in token b right it changes the exchange rate for everybody subsequent uh who wants to interact with unit swap subsequent to that right so this means that but this is a problem in our application because uh okay so what happens in ethereum right now is that somebody just you know pushes the code to to the network and the miners execute that code right and then they update so they they and like let's say there's 10 transactions wanting to interact with uniswap in the same block the miners will perform some serialization uh some linearization of these of these transactions and say okay this

transaction comes first then this transaction then this transaction then they will execute this transaction sequentially and then they will know that okay this is how the state updates of the use of contract as we flow through the sequence of transactions now the problem with doing that in this utxo based approach is that um i am a user right i have run the the proof like i'm consuming okay the state of the unit swap rec uh contract is stored in some record right i am running writing a proof which proves the correct execution of my exchange with unit swap at the

particular claimed exchange rate against the unit swap record at time t right uh and then look at this transaction is valid but let's say there's another user who's trying to uh execute a unisop transaction at the same time in the same block right they will also try to consume this this uniswap record right but they won't be able to because the serial number for this one uh will already be in the list of serial numbers right so then basically you have to do one unisop transaction per block which severely harms the uh throughput of the of these chains and this is like i think a problem that's being faced for example by cardano right now um

[Music] so one solution to this is to say okay we're not actually going to put the uniswap transaction information or the the contact information inside a record it'll just be public state right and instead of having the user provide this this zero knowledge proof of the correct execution we will just let the uh we will just do this in on chain like we do with uh like ethereum theorem exactly right so ethereum will the network will execute the uniswap information against whatever the user provides and then this basically now becomes a public

computation in sort of a private computation now there are some steps that you can take between this you can i think the yeah there's been some excellent blog posts that i've uh that i've seen which sort of proposed a different idea where you uh have the you could have for example instead of having the network be the one responsible for managing the state and updating the contract you could have some other party like uniform runs somebody uh runs some server and the idea is that users send their incomplete transactions to the server the server sort of serializes and sequence sequentially executes them and then produces zero knowledge proofs and only publishes those sequential zero knowledge proofs which are now valid because

this record one is consumed here and then the the next transaction consumes the updated record as which is the output of this uniform transaction so on and so forth now was this you still kind of like was a global state with a public state and uh you know you know what contract is being executed you lose some privacy but you still can retain some aspects of anonymity right uh yeah so it depends on how you structure it for the particular application you have in mind but yeah so if you just reveal what data is being executed then the commitments will still hide what public key and you know where the input data is coming from for example so it depends on how you structure it we're sort of still working through the

full programming model in elio how what we want it to end up looking like um but yeah it's not like you completely give up all privacy to get public state there's probably like some spectrum of of leakage that uh that you go through depending on how you design your application like a union swap contract that you said it knows which records it consumes but those records are not linked to anything that was existing before exactly and then it maybe can enforce which records get generated but again somebody you know later consuming those records doesn't need to reveal which records exactly exactly okay um i think this concludes our session thank you so much pratush thank you so much for the awesome session and i hope everyone enjoys it thanks a lot everyone thank you bye

[Music] you