ZK HACK - Ferveo and Plonkup Workshop - Anoma

Transcript

right yes so um so as i said uh joshua will um you know take us all through p lookup later and so um that'll be exciting uh i guess we'll talk a little bit and have a really cool um live demonstration um so we'll start off with it with uh a non-zk related uh cryptography topic um but one that i'm sure will still be of interest to um many of you here um just go over this project that we call furvio um which is in collaboration with osmosis labs um

it's a great collaboration that we've had with them and um uh uh yes just having a little technical issue all right there we go uh you can follow along uh because it's a hack md slides uh you can follow along with this link um and you can uh browse the slides at your own pace um although um the tech most of the technical uh details about fervia will be releasing the technical paper uh relatively soon um that we're currently preparing that will have all of the nice uh math and proofs and other

details that um will be very interesting but for right now uh i want to go through the high level overview of what we're trying to do and some of the design decisions that we've made okay so what is fervium well there's this problem that blockchains have uh have uh encountered especially um as more and more finance applications move on to the blockchain this probable minor extractable value or mev and the idea of minor extrapolable value which is perhaps a little bit of a uh

misnomer because it's not just miners that can um extract value in this way but uh pretty much anyone who has um some kind of advantageous position on the network where they can control in some way how transactions are executed on the network including putting their transactions ahead of other people's in a way that can uh be called front running um censoring transactions reordering transactions to um um be more advantageous to the miner or validator

in many cases uh in fact these entities don't actually have any kind of formal role in the network but uh nevertheless they have uh you know better connections and um are able to monitor the mempool for incoming transactions or that kind of thing and um they're able to uh because of uh whatever advantages they have um be able to uh um change how the transactions are executed um and and uh extract some value and in cases of of like front running um this uh sort of lowers the utility of the

network it makes less useful for other people um because uh if they're if other people are trying to do you know their trades in the network um but they're get keep getting front run uh and extracting some of the value of these trades then there's not as much uh usefulness of this network for those traders so um there's some great articles on this um some technical research but it's flashback bots group and some amazing um articles on the uh the concept of a deep forest which which i encourage you to read but many of you may already be familiar with um and and you know solving this uh issue or or

addressing this issue of minor extractable value is um going to be important for blockchains going forward okay so uh what what can we do about it like um uh blockchains are very public um at least um if we're not in the zero knowledge uh area um transactions come in they're public um they have to be publicly executed so what can you do well the most uh important thing you can possibly do is to at least not reveal the content of the transactions until they're actually included in a block um and the block is committed and the

ordering of the transactions are committed only then do you want to reveal what the content of the transactions actually work because that way when the block is being constructed no one can use their knowledge of the transaction that was submitted to put their transactions in front or sandwich the transactions or in other ways alter the order of how the transactions are executed and so broadly i think people have uh looked at minor extractable value and said okay this uh uh

trying to prevent the content of the transaction from being revealed um is is the important part um however uh the details about how to actually do this are not necessarily so straightforward um and there's actually uh several different kind of theoretical approaches which um people have looked into um one very popular idea of how how to address this is using some kind of time lock encryption um usually but maybe not always based off of something like verifiable delay functions where the idea is that um you lock your

uh transactions in this time lock encryption um and you encrypt your transaction to say well i can only uh i want the these transactions to only be able to be decrypted say one minute from now and the hope being that in that one minute time they will be included in the blockchain and um you know committed to and then once the time lock is opened um the transactions will execute uh in the order that they have appeared in the blockchain and um in some ways this is a good approach um it's certainly um sort of very compatible with the notions

of of how proof-of-work blockchains work um there's some tricky things in terms of how to get the actual timing to work out the way that you want them to um and also uh certainly in some applications uh having a delay and execution is is uh not so convenient as well um you don't you know you want your uh time lock to last long enough to make sure that your transaction gets executed um without being front run but uh you also don't want your transaction locked for too long um otherwise it might become stale or it might not uh

execute um in the way that you want to um it's a different way of of doing it which is the way that we've gone with furvio is to use something called threshold decryption where um um unlike timelock encryption which is uh based off of encrypting um to some future time uh threshold decryption is this idea of decrypting via some committee or some group of entities that are able to decrypt um and there was a great uh talk by uh sunny a couple um weeks ago on these various trade-offs and um these

different approaches that can be used for for preventing minor extractable value um which which uh you can go watch his talk is it's really great um but uh we'll further into the trade-offs here and just describe uh how do we actually accomplish this with phobia so with threshold decryption um if you're familiar with the standard public key cryptography uh where you know a message is get encrypted to a public key and then whoever possesses the private key can decrypt them with the threshold decryption system it works very similar you have a single public key that's available to everyone public

and it's broadcast on the blockchain or or gossiped in some way so everyone has it and uh messages which in this case are essentially transactions um can be encrypted to this single public key but the difference is that no one actually knows the private key uh the private key that's associated with this public key um is not possessed by anyone in the world but instead in different parties own uh what we'll call private key shares with which are we've kind of partitioned up this private key in in some way so that every subset of at

least tea parties can decrypt the message while every subset of it most team minus one parties cannot decrypt the message and um this is related to something called uh shamir secret sharing if you're familiar with with that um the idea of how uh um and parties can share uh a general kind of secret um such that at least um every subs at least tea parties can reconstruct the secret well every subset of always of the most t-minus one parties cannot reconstruct the secret and the basic concept is the same except that instead of uh reconstructing the private key which

would reveal to everyone what the private key was um parties are are not going to reveal the private key they're instead going to decrypt this message and these parameters are are very adjustable so like um so in the threshold description system you can choose these values of t and n where um if you have n different parties and you want um say two thirds of them to be able to decrypt then you can choose t equals um two-thirds of n right so threshold decryption is something that we can build um on top of uh secret sharing um and it's been known for for many many years that you can and

there's been many different constructions for how to build direct uh decryption cryptosystems uh although i'm not sure that there's actually been uh very many applications deployed the actual use threshold description okay so threshold decryption um as a cryptographic concept is well established but one reason why it's um verifiable delay functions are a little bit newer um it sort of came up in the blockchain context first but in the uh um

social cryptography is actually very useful depending on the kind of blockchain that you're uh building it on top of so in a bft byzantine fault tolerant consensus based blockchain such as for example those that are built on tendermint um or the tendermint proof-of-stake protocol um there's actually a very nice natural correspondence between um who owns a stake in the network or who has been delegated the stake in the network and who should own these private key shares so in the tendermint proof of stake system um validators are delegated weight by people who own

that staking token the network and validators can produce blocks by uh voting using the stake and more than two-thirds weight by stake uh when they vote to commit a block that causes the box to get committed and transactions in it um join the blockchain right and so um at least uh sort of qualitatively you have this very very natural correspondence the validators which already have been delegated this uh stake in the network this authority in the network to say okay if some threshold of stake has voted to commit these blocks

um then uh the blocks become finalized and uh you know the blockchain uh progresses forward uh and so it's very very natural now to say that um these validators should also have these private key shares and be able to decrypt these transactions um subject to the same two-thirds weight uh threshold um and so this this makes um using threshold decryption uh in this proof-of-stake world a lot sort of a lot more of a natural choice than maybe using time lock encryption so

here's the basic idea of how we want the transaction model to look like um validators are going to generate a common public key in some way a single public key that everyone uh using the block change in no um this public key gets broadcasted in some way um alice wants to do some kind of transaction so she builds the transaction um in the way that um you know she has her wallet software that builds her transaction for um and the wallet is going to encrypt her transaction um to this public key so she encrypts the transactions that no one can

know what's contained in this transaction but presumably it can be decrypted later at some point so once alice broadcasts her encrypted transaction uh validators are going to get this encrypted transaction in the mempool and validators are going to include uh this encrypted transaction eventually in a block um you know uh validators because they have no idea what's in the uh transaction um are going to have to uh you know use just uh what little information they have to decide um you know when and how to include alice's

transaction so maybe she's included the gas amount and the fees and that sort of thing but otherwise uh no one can actually tell um what her transaction is or what kind of transaction she might be doing and therefore makes it much more difficult to front run or get an ev4 and so validators are going to include alice's encrypted transaction of the block um whoever is constructing the next block because in in the tendermint proof of stake this is very um sort of well described like well specified uh about how blocks are proposed and um

voted on um whoever the block proposer is will scoop up a bunch of transactions from the mempool add it to the block and then um the network will come to consensus on that plot and what we want to happen is that uh when the validators are voting on this block to decide whether to commit to it um they should be uh committing with their uh decryption shares of alice's transaction but all pretty essentially uh the decryption shares of every transaction in this block but the idea is that um we want to make sure that uh um the exact moment when two-thirds uh

of uh stake is voting for this block that uh two-thirds of the um pub private key shares are also voting for this block and therefore um as soon as you reach this two-thirds threshold the block is finalized um and you also have enough decryption shares to actually decrypt alice's trend transaction and execute it so that's the model that we're trying to get to now there's some difficulties that happen when you try and actually implement this the biggest difficulty is that um well

validators have different amounts of stake and in general um you know you might hope that every validator has about the equal amount of weight because that's good for decentralization of the network um and other reasons but um in practice of course this time not how it works um uh val there's gonna be very top-heavy um and a couple of validators tend to have a lot of weight um and so two-thirds by count of validators is not generally going to be equal to two-thirds by stick like even in a really great world where volumes have roughly equal kind of stake um you're not necessarily going to have

this exact uh equality um and so uh if we want to achieve our ideal outcome where the validator can finalize the block if and only if they can decrypt all the transactions in the block well then um you know we need to do some some adjustment there we need to uh know that's the outcome we want to get but we can't just give one uh private key share to each validate so the only really reasonable way to do this is by awaiting the private key shares namely you have more private key shares than you have validators and higher stake validators get more private key shares

um and if you have a hundred validators for example uh you might want to give two thousand or four thousand or even eight thousand key shares out and uh this will let you approximate the uh um amount of stake that all the validators have in the network now uh because we're now making the number of private shares um um private key shares uh in the protocol much much larger you know there's a big difference between say n equals 100 and n equals 8 000.

um the immediate thing that this enforces is that um every uh part of this protocol now must be uh big of n log n in performance in both uh network bandwidth and computation um which uh the otherwise the scaling is just too bad um it has to be at least this kind of quasi-linear scaling and the reason that i point this out as being really important is because it's not necessarily obvious how to achieve this because remember if you have n different parties

um the communication complexity pairwise is n squared so if you're sending a message between every pair of entities in network um and you have an entities then um you have n squared messages right and so this is uh in in general and then if you must do uh if every entity must do some computation um from each uh on the data they receive from every other entity then it very it can very easily become um you know a big of n squared bandwidth and computation and um in fact this is kind of just a general issue with

distributed systems um in general and but it just becomes um kind of even more acute here because um we are sort of uh um the number of validators or a number of entities in the network and the number of private key shares which is now much larger and so uh with everything we do we have to focus on keeping this performance much better so um the first part of this uh of furvio is so we need to have the validators be able to create

this private key where um the private key is distributed around to all the private key shares are distributed around all the validators but no one actually knows what the private key is um is very much like a trusted setup in the zk world um right and so um won't go into the details of how this how we do this there's some really great papers that describe the technical details uh much better but um the basic design decisions that that we've made in furvio um are that we want to use something called a publicly verifiable secret sharing scheme

so uh as i mentioned secret sharing before the idea that um and parties can split the secret among themselves um the verifiable part of verifiable secret sharing is that everyone uh can verify that their own uh private key shares are valid um they haven't been distributed in invalid uh private key share by someone um um you know if say there was a rogue validator uh being part of the protocol well uh you would want that their uh messages can be detected by uh by the person receiving the messages um

but we go a little further than um just a verifiable secret sharing scheme uh we want to use a publicly verifiable secret sharing scheme in a publicly verifiable secret sharing scheme uh the validity of every step of the dkg can be checked by every other validator in the network so um this means that um validators are going to engage in this key generation protocol and they're going to share messages with each other um um it's not just the recipient of each message that can verify um that the the message was constructed properly but

in fact um every validator or even people are not validators in the network uh can check each step of the dkg check each message and make sure that it's valid and the reason that this is important in the blockchain context is that there's no issues if a validator goes offline so the reason for this is that if the scheme was not publicly verifiable um then a validator that could send a you know rogue or invalid message um might not be detected um because if the validator that's receiving that

message has gone offline for some reason um either on purpose or uh you know if they were if there was like a denial of service or something or if there's just any issue that caused them to go offline um this invalid message might not be detected and so um uh the distributed key generation gets much more complex um when you have to have additional rounds of communication where a validator has to be online and file a dispute if if a different validator is acting um in a malicious or byzantine way okay and so uh our primary objective here is that we're

going to avoid that we want to avoid that as much as possible we want to use a publicly verifiable secret sharing scheme where um if a validator goes offline then they know that all the messages that they would have received their online um are uh are are still good uh let's see we have a question uh would it be possible to use a hierarchical uh secret sharing scheme to account for the weights of each validator and thus reduce the number of shares needed um that's a good question and it's one that we we struggled with for for quite a while ourselves um um trying to figure this out and reading

all the literature about secret sharing um so the answer the the the the short answer to this is that um you can but you don't necessarily gain very much and the reason for this is that um is actually kind of quite deep uh um secret sharing is an information theoretic um construct uh it's actually based off of polynomials and interpolation right uh if you're if you're familiar with secret sharing um is not actually based on like a cryptographic construction necessarily and so the problem with information theoretic schemes is that um you you

don't actually get many opportunities to um to do like compression or aggregation or anything like that and so um if you have a secret sharing scheme which um you want to have you know uh the parties have different weight in them um then very often times um uh the um the size of the private keyshare um is going to be uh um is going to grow uh with the weight rather than um anything else a growing year only with the weight and so um if you adopted a different uh kind of

secret sharing scheme um for example there's secret sharing schemes they're not based off of polynomials they're based off of chinese remainder theorem um there's actually many different secret sharing schemes that people have proposed of a common thread among amongst them is that unfortunately when you actually try and implement them it's very very difficult to sort of beat the uh the simplest secret sharing scheme of sharing a polynomial uh evaluations of a polynomial um which uh that's not to say you can't beat that but uh uh certainly a simple scheme is very

much more straightforward to implement and optimize um but sort of as as we found um uh we were able to get the secret sharing scheme to to be uh very performant it's just a mostly a matter of um dealing with the high amount of bandwidth required uh because of the high number of private key shares and um also making sure that our implementations are all um very fast computational algorithmically fast um this big o of n log n algorithmic complexity

okay um so the other important property of our distributed key generation um is that we actually use a synchronous on-chain message passing protocol and uh this is actually quite a bit different than most of the uh academic literature on distributed key generation um a lot of the interesting work in recent years has been on in the asynchronous model that is or maybe i should say partially asynchronous model where um entities are passing messages between each other perhaps using a gossip protocol

and um there it becomes much much more difficult to achieve like a big o of n log n uh overall complexity um um and and also um uh maintain the synchrony of the network you know uh synchronizing things in general is just a very very difficult thing to do uh i mean that's why blockchains are interesting um but uh since we uh have uh control of the underlying chain um it's uh actually much much simpler if you uh use the existing uh bft consensus mechanism um to uh to synchronize your distributed key generation protocol and

it's just much simpler when the blockchain and bft consensus are already there and you can assume that when a message is posted to the blockchain that it can be received that it actually is received by everyone um and that there's not some kind of byzantine fault in the network um now this of course means that there's a lot of on-chain data but uh we find that's not a problem because this data is actually prunable later and so we're not carrying this data forever so so we're going to run our distributed key generation protocol on the chain and and we have uh this nice um it's based

on this nice publicly verifiable secret sharing scheme um there's a technical issue which which tripped us up for for for quite a while namely that um a publicly verifiable secret sharing uh based dkg uh generates private key shares that are elliptic curve points and not scalars so if you're familiar with how private keys work usually uh you don't know what the curve cryptography private key shares are scalars and public key shares uh public keys are with the curve points uh however um in the dkg that we constructed um the private key shares are also with the curve points

um formally speaking um um this dkg works over a pairing based pairing friendly curve and the public key points are public keys are g1 points and the private keys are g2 points the private key shares are g2 points as well um and and this is a problem uh because you uh it becomes very difficult to use like existing um uh threshold uh decryption schemes um which are not written with this assumption in mind they're written with uh perhaps other assumptions um and so our solution this is uh we've developed a new pairing based uh uh

encryption scheme that supports threshold decryption with these publicly verifiable secret sharing generated keys now uh just uh one aside um there was a nice paper this year by groth uh the same groth as in broth 16 who described a uh pvss based distributed key generator uh which actually does generate private key shares that are scalars however um the scheme that we're using is quite good enough um quite high performance and um simple enough that um we can we can

continue using the um pvss scheme that has this uh private key share uh property okay so uh so what what are the optimizations and features that are are really interesting and perhaps unique uh to to fervia um first is that everything is being done using fast um big o of n log n algebra operations so uh if you're familiar with um or secret sharing in general um or perhaps uh just inferring things from what i've said so far um secret sharing involves a lot of polynomial operations um you know multiplying adding uh

interpolating polynomials evaluating polynomials there's a lot of these polynomial operations which which um happen uh in the secret sharing process and the threshold decryption process and they're sometimes but not always optimizable using um like fft techniques um it turns out that uh uh there's actually a quite general field of uh um fast polynomial operations um uh fast polynomial algorithms which which allow you to do all these um operations in the required and log in speed

and so uh where we've had to we've implemented all these operations and um you know integrated them into into our distributed key generation and threshold description um implementation and so that that's going to allow us to uh scale up the number of private key shares um to the level that we want without uh destroying the performance completely some optimizations um that that we've done on the decryption share side um we have uh in our implementation a one decryption share per transaction per validator um not per transaction per private key share so this is a very very

nice optimization which our very own dk hack host kobe helped point out um and this is this is very important because any time that you can do something on a per validator basis instead of a per private key share basis um you're automatically going to get an enormous speed up because you're going from like i said 4 000 or 8 000 private key shares down to uh you know 100 validators um uh our threshold inc our encryption and threshold decryption scheme has to be um something called key committing uh namely uh we want to be able to say that either a transaction

is guaranteed to be decryptable or it's detectable that it's invalid or another way of saying this is that all valid transactions um can be decrypted um using uh verifiably decrypted using the key that we derive and uh the reason it's important is to prevent uh the censorship of transactions that so you don't want validators decrypting a transaction and then discovering oh no no i didn't like this one i want to censor it um in some way uh the important property we get from key committing is that if a transaction is validly constructed and encrypted then um the decryption shares will become available and it must

become decrypted uh because everyone else can can verify that um if it actually was an invalid transaction that um that fact is verifiable to everyone so uh before i hand this off to joshua part which i know that everyone was going to be interested in was the actual concrete performance of this of furvio both in terms of the bandwidth and the compute time so the amount of data that goes on chain um

is uh is for the distributed key generator is actually quite large it's 138 megabytes per epic so if you uh refresh your key say once per day um you're putting this large amount data on the chain however the trade-off is that it's actually printable so it's more of an issue for uh gossiping all of this data around it's it's not very efficient uh to gossip data while um the dkg is running um however um in terms of your long-term storage costs it's actually not important because once the dkg is done and the epic is passed and the key

has expired uh you can just prune all of this data from from your blockchain and uh if you do if you you know have the ability to build your blockchain in a way where it's printable um then you uh you maybe don't care so much that that your gkg uses so much on chain data um and then the uh um actual data that sort of is important um on chain the decryption share and the ciphertext overhead is going to be quite minimal um your decryption shares are very a very small amount you know basically 48 bytes per transaction per validator um and so um maybe if you have a lot of

validators um this can add up per transaction but uh as a general rule it's actually very very small it's it's much better than if it was uh again um 48 bytes per transaction per private key share and then the ciphertext overhead um uh from from encrypting to this public key a couple hundred bytes uh this is also mostly unavoidable performance wise a rough single core measurements on on my laptop and so i should be much much better on on actual um like validator hardware um we managed to uh push most of the

compute into a per block compute um so it takes about four seconds of compute per block to do um to to sort of uh do all the prep work for for doing threshold decryption for that block and then a really insignificant 16 milliseconds extra compute per transaction um the the cost has been uh so if you have many transactions you're actually amortizing its four second cost of over the many transactions um in that block um and so uh even for a very high number of transactions like 100 transactions per block um you still don't actually have that uh very much total compute time and um you know if you parallelize this

uh over many cores if you have 32 or 64 cores uh this should um make this quite feasible for validators to do uh over um um you know over all of their blocks right um uh you know the some validators might have to upgrade their hardware but that's an acceptable trade-off against you know running a proof-of-work uh miner or something right um it's not that significant um to to add some more cores okay um let's see you can check out all of our work in progress uh the public repository certainly uh appreciate any uh comments

or feedback or uh other insights that you might have any uh any interest any questions let's see share papers related to dkg or pbss yes a dkg in the wild is a great one um um there's uh one that in fact um that put us in contact with uh you know kobe about this in the first place um um on aggregate aggregateable dkg um

uh in fact uh our dkg is very very much closely related to uh this aggregateable dkg um except of course the um the aggregateable dkg is more interesting overall in the asynchronous context um where they they get this uh big of n log n performance um asynchronously uh um which is which is a much bigger achievement um the fact that we're doing everything synchronously makes things um makes the the full aggregateable dkg unnecessary but uh in in every other respect our dkg is very very similar to the agriculture

um maybe i'll oh i'll share one more paper um this is the the groth 21 uh dkg um uh it's a very very interesting piece of work uh that uh yeah i i i encourage you to at least read the abstract and and and maybe uh understand uh why it's an interesting piece of work but um certainly uh uh it's uh it's also quite complex both in concept and implementation

okay um yeah i think josh like thank you so much for this talk um i guess if there's any other questions joe do you want to just kind of stick around in the chat if people wanted to ask more yeah absolutely perfect and joshua do you want to maybe jump in here joe i think you're going to have to turn off your screen for him for joshua perfect cool and i think when you're not speaking maybe just mute to to avoid any sort of background perfect cool okay see can i make this big

all right so uh yeah i'm going to present on plunk up a a protocol which combines uh both planck and p lookup protocols uh into one um this uh well let me just find where i'm at here uh so what is plunk up um it's a method for unifying the plonk and pluck pluck-up proving schemes uh plonk uh came up first look up came out a bit later there was nothing in uh in the the pickup

paper saying exactly how these two things could or should be combined uh plookup was kind of its own singular thing and so we we went ahead and tried to combine these and ended up with uh with plonk up uh plonk up has the advantages of planck which are uh relatively small proofs uh fast verification and uh universal setup uh with the additional power of lookups to reduce circuit sizes if you have an unfriendly a circuit unfriendly function like uh bitwise operations um most most hash functions have some bitwise

operations so implementing them in a circuit is a little um inefficient uh but with lookups you can you can increase the efficiency a lot uh the reinforced concrete hash is an example of a new hash function that exploits lookups and arithmetic in a circuit so to express the reinforced concrete hash in a circuit you need something that can do both plonk up this is our solution for doing both we've uh taken

um we've been following the convention of uh using the term plonkish to refer to uh family of protocols that descended from planck um if you just say plonk no one knows what you're talking about because there's there's so many different kinds so uh if we're referring to the family of protocols we just call them plonk-ish so that people know we're we're talking about a whole uh whole group of protocols that have some similarities i think it was some folks at ecc that started using plonkish as in this way so some examples of plonkish protocols are planck the original turboplonk and ultra plank which i always get confused which one is

which but one is referring to custom gates one is referring to uh look up gates and possibly also custom gates uh like i said i forget what's what um pluck up uh which is for lookups only plonk up which is our uh our version of lookups and arithmetic halo 2 which uses uh planck with a different polynomial commitment scheme and faflop which just came out and also this first time i'm ever pronouncing that out loud um and uh i don't know maybe your plunk here someday uh it's there's so many

different plonks uh everyone should try and make their own plonk i think it's a good exercise okay so uh what characterizes a plunkish protocol um they can't be characterized by their polynomial commitment scheme or their gate structure because you can change those you can swap out the polynomial commitment scheme you can use you can use kzg or kate commitments uh halo 2 uses an inner product argument like bulletproof style commitment scheme but you can theoretically swap it out and use

something like fry turning plonk into a kind of start so you can't really uh call something plonkish just by its polynomial commitment scheme or the gate structure because uh you can use custom gates um so uh which can be basically anything so uh what does characterize a plunkish protocol uh you have fixed width gates uh which could be custom you have a universal setup so you can run one trusted setup that works for any circuit below a particular size uh

plonkish protocols usually exploit a lagrange basis in order to gain some efficiency there so uh in a lagrange basis you you represent your values by points or evaluations on polynomials rather than coefficients or some other thing um and they have a grand product argument the original planck uses a grand product argument to to show that there's a permutation of variables that shows their quality

plookup has a different product argument planck up combines those uh i just see a question here what's uh fixed with gates uh with uh with plonk you don't get uh unbounded fan in um like you do with rank one constraint system with r1cs you can do basically unbounded additions in a single gate with uh the planck or plunkish protocols you [Music] uh you don't get to do unbounded edition you could you could make your gate have

many editions if you wanted you could make it have eight editions but it's it's fixed so i like to view plunkish protocols like a switchboard uh so what i have here is is kind of my my mental image of what's going on with plonk i've got three different uh types of gates here we have addition in green multiplication in blue and look up in orange for a b

c and d a 1 b 1 c 1 d 1 to be a part of this this green row means that they have to satisfy a particular constraint in this case an addition constraint so i decided to make it a plus b equals c plus d multiplication uh a times b equals c plus b and for lookups uh then you just look up the the tuple a b c d and check to see if it's in the table all right so uh rows are associated with these

these gates they need to satisfy these gate constraints all right then what you can do is uh connect them together i hastily drew these uh wires on an airplane so but uh you could uh plug a kind of patch cable in and connect two variables so here i've got c1 and a2 connected which means they need to take on the same value that's how you can connect variables from one gate to another gate so here i've got a multiplication gate

where one of the factors in the multiplication b4 also needs to be a part of this this lookup so it's going to be the first element in this lookup row so c1 equals a2 b4 equals a5 uh before i get too far i just wanted to give some terminology so you know what i'm what i'm talking about uh wires are columns of the provers private inputs to the circuit and they're vectors of length n so if i scroll back up here i'll try not to do too much

scrolling but if i scroll back up here you'll see i've got a b c and d columns so we have four wires the a y or b y or c or d one and the length of those wires is six okay gates talked about a little bit but a gate is just a relationship that a row of the private provers private inputs must satisfy and uh plock up supports arithmetic gates and look up gates sometimes these are also called constraints sometimes if i'm really being bad i might call it a row but it's not really a row so

but you might hear that selectors are vectors uh also of length n that turn gates on and off for example a one index k of the lookup selector turns the lookup requirement on for row k a selector can also contribute an auxiliary scalar to a geek constraint in some cases like i said they're vectors of length n finally we have copy constraints i've already mentioned these these are like those uh those patch cables that you can plug into the switchboard that force two variables to take on the same value

um so these are used to build a permutation which swaps each variable with another that is supposed to be equal to it so essentially we run through the same kind of product twice one with the original value and one with the permuted value and if those products are equal then the original value and the permuted value must be the same we also have a circuit description this is uh all the stuff selectors circuit length and the permutation encoding the copy constraints and the lookup table from the circuit description this is uh this is public stuff that

you need to to prove and verify circuit okay what our lookup table will look like uh the lookup table has columns equal to the number of wires in the circuit so i had four wires earlier so i made a table with four columns and we will take those values of wires in a lookup gate and see if those same four values appear in as a row in this table i'm gonna do a lookup

okay uh there's i i made a lot of slides i made way more slides than i needed so i'm not going to go through all of these um or not all of them in depth so you can you can see these slides you can take a look at them later if you want to look at more of these arguments but i will stop here for the grand product argument this is what i was talking about before where we we check these copy constraints so what we have is four wires a b c and d and we

multiply up all these terms into a big product and if you look at the numerator and denominator of these terms they're they're similar but not quite the same uh up top you have can i highlight that part that way right here you have like i beta i stands for the index of the original uh value um so uh the we index these like basically the first wire a gets one through n b gets uh n plus one to

two n right um and so on so we have uh we have all these indices from one to four n uh that's what i is here and uh in the denominator we have almost the exact same thing except we now use the permutation on the index instead of the original index um so if these uh if the product in the numerator equals the product in the denominator they should all cancel out you get one if you try to mess with any of the values of the wires it's not going to cancel out you won't get one if you try to mess with the indexes

it also is not going to cancel out uh pluck up also has a product argument uh this i should say is a modified version of the lookup uh product argument um we we've changed this a little bit to uh to make it more um efficient uh this suggestion here um for how to change this was uh luke pearson came up with this uh it really really helped with the the efficiency of our of our plonket protocol

plookup also has this product this is really interesting i think so i i'll i'll try to explain how it works uh you have a um a vector of queries which is f and you have a vector that comes from the public lookup table that's t and you combine those together you concatenate them to form a new vector s which is double the length of either t or f because you're combining them together and then you divide s into two halves which we call h1 and h2

you can see those down here in the denominator h1 are all the odd indexed elements of s h2 are the even indexed elements of s and s is sorted to match the ordering on t okay so uh what happens here is that these denominator factors will run through all of the elements of s and you can actually see here if you look we are not just going through the elements we're kind of pairing up adjacent elements

so that we have we have a first element and we have the next element which is multiplied by delta um so all of the uh the pairs of elements as you go through s are run through with these denominator factors if uh that pair of elements that are adjacent matches a pair of elements from the table then one of these denominator factors is going to cancel with this factor here sometimes the two adjacent values will be the same when they're the same they are the same

because they are a table value and a lookup value which means the excuse me a table value and a query value i should say which means the query is in the table and that's why we see it twice we have a table value and a query value they're the same uh when that happens if if these two like h1i and h2i are equal then you can factor out one plus delta because we also see this one plus delta here the one plus delta can come completely out of this and what you have left is epsilon times the single value

which must be one of the queries which is f so that will cancel out with these factors here so as we run through this uh this concatenated and sorted vector here s it's either going to cancel out with an element of the table or an element of the queries if the vector is formed correctly so this will all cancel out and you get one okay um i'm going to skip past some of this more technical stuff

uh and i'll i'll show you these gate structures before we get on to the live coding part uh with plonk up we have two major kinds of gates we have arithmetic gates and look up gates here's an arithmetic gate what you have are uh the provers private inputs these are a b c and d uh you also have selectors uh q m q l r o uh we couldn't figure out a name for the fourth one so we just called the fourth one q4 and qc is a constant that you can add into a gate so uh if you look here this first term

has qm times a b so if the q selector the qm selector is a 1 then that means we are including a times b in this gate as a part of the constraint um if that selector is zero then you won't have that in there so um if you if you turn on qm with uh with a one you make this a multiplication gate or you can turn it off and make it more of an addition gate uh the rest of the terms we have ql qr times a and b each and also q o times c these stand for left right and

out so these can scale a b and c or they can turn them off completely by making them zero uh we have a fourth one uh for for d um we have a constant also so uh this is more expressive in some ways than a rank one constraint um actually i'd take that back i take that back completely as this is all addition here a rank one constraint can also express this with also even more editions if they want so this is less expressive than a rank one

constraint but it can do multiplication and uh and scalarized addition here so kind of like a linear type constraint with one multiplication a lookup gate is is much simpler it doesn't have to satisfy a formula like this all it needs is that that tuple needs to be an element of the table okay so uh if you want to use planck up uh you can uh you can run a setup with plunk up here we have the code for this um and is the uh

the size of the circuit that you want to use um and so you can generate a setup this way this is your trusted setup you might have heard about uh then we create approver approver can have a kind of tag i'm calling this one workshop prover this initializes a transcript uh so workshop prover is also kind of a diversifier so that different proofs for different purposes will have different tags here and will not be able to they won't verify if you have the wrong tag

all right then the previous private inputs my my circuit here i should have put a slide in this but my circuit here is uh showing a pythagorean relationship between private inputs so there's three private inputs a b and c and my circuit should show that a squared plus b squared equals c squared so here's the approver's private inputs um 5 12 and 13 that should form a pythagorean triple if i remember my geometry correctly and these are out of those inputs and become variables in our constraint system the prover.mute cs is our constraint system

all right once we have variables in we need to put our gates into the circuit uh we have a multiplication gate here and it has a selector value which is one it's two variables a and a so this should uh give one times a times a so a squared and then we save that here in var a squared bar b squared essentially the same just we're using bar b of course for c squared essentially the same we're using var c

um then we need one addition gate to show that a squared plus b squared equals c squared the way we actually do that is show that a squared plus b squared plus c squared equals zero or excuse me minus c squared equals zero so we have our three squares uh we could scale those if we wanted to but we don't want to in this case so we're just using a one and uh for c uh we take the negative so that adds to zero all right once we have our gates uh then

you can prove a circuit uh with a commit key ck uh you just run uh prover.proof and that will create your proof for you and then to verify uh you need a commit key and a verifier key but you just run verifier.verify and uh that takes proof a verifier key and some public information here the public inputs in the lookup table it gives you your result um i think i saw some interesting questions over here uh david what's the point of reordering t in t prime as well

uh from enabling alternative ordering slide uh i will scroll and see if i can find that slide this is one of the slides i skipped um we we have to sort these vectors and uh sorting can be kind of tricky uh they need to be sorted um in order for this uh lookup argument to work but the prover needs to sort their copy of the table the same way the verifier has their copy of the table so

you can use like a relative sorting algorithm or you could also just do this small change to the product argument here the prover uses this t prime instead which is their own ordering it can be whatever order the prover wants it doesn't have to match the proof the the verifiers copy which is t and these extra factors show that the provers ordering is a permutation of the

verifiers ordering so this enables the the prover to choose a sorting algorithm of their choice um if you use a relative sorting algorithm it's um it's a little tricky uh if you take one of uh any any number of efficient sorting algorithms out of the box you can get down to n log n uh pretty easily just by attacking on a few extra elements here we had an issue with the sorting when we first ran through this protocol the sorting was was really destroying our our

benchmarks um and this uh this allows you to kind of step around that issue there's a couple of ways to do it okay i think if are there any questions over the slides before i switch over to the live coding part i don't see any new questions in q a uh i'll go ahead and uh and switch over

now to the the live um live coding i kind of gave you a preview in uh in some of the later slides uh the syntax is going to be slightly different because i'm using a slightly different uh version of our of our library um let's see here here we go okay so what i'd like to do here for the live coding portion is show you how to use plonk up to

make an x or table xor is a you know it's a pretty common operation in hash functions it's also not that easy to do with regular arithmetic gates uh the main reason is that you have to to break up the xor into a bunch of little pieces often just bits so if you have a 256 bit element and you want to xor that with some other bit element well you have to break that into into bits

you can strain each bit so that you know it's a bit so you end up with 512 constraints then you have to use a constraint for each xor and then you need to collect all of those back together into the your output so because uh you're working bit by bit um you end up with you end up using a ton of constraints uh if you use a lookup table you can work more easily with multiple bits and what i'm going to do here is

make a four bit lookup table so each input is going to be four bits um and that'll that'll save a lot of constraints uh we're just going to do an xor between two bytes i wanted to make sure this was not too too complicated i also i'll be making too many mistakes on screen here so we're going to take a a left value left byte a right byte xor them together with their table produce an out bite sorry

i azide i don't have a repo for you okay so let me explain the different parts here you've seen some of this already in the slides uh here's our main um n is the uh the size of the circuit uh actually it's bigger than the size of the circuit it's the next power of two larger than a circuit uh this size needs to be a power of two in order to make the ffts more efficient so uh once we have the size of the circuit we can generate parameters

this is your your trusted setup here so this will generate enough uh elements in the setup to handle a circuit of size 512. next we have the the provers viewpoint here in this uh in this closure uh the prover is going to generate uh random bytes here um three random bytes uh or two random bytes as opposed the last one is the xor between the the left and the right these are going to serve as the inputs to the prover circuit um

then the prover can create their their approver struct i've got it tagged as zeke hack workshop next we will create the lookup table uh with this function we're going to fill in that function which was just above next we add the gates to the circuit we're also going to fill that in in a function that's above um we create a commit key which we need to do a proof we do some pre-processing on the circuit usually pre-processing is done once per circuit

here we're just going to do it on the fly then we also want to make sure that the the verifier gets the same public inputs and the same lookup table so we're going to to grab these from the provers constraint system and pass that along to the verifier later and then we'll create our proof all right once we have the proof created uh if you look at the beginning of this closure uh this will spit out a proof the public inputs and the lookup table these two are public

and well all this is public um and uh the verifier will use these this information to uh to verify so the verifier also creates their own verifier this verifier needs to have the same exact tag here zika hack workshop the verifier appends the lookup table attaches their circuit this is going to be the same circuit using the same function if you notice here these are the verifiers inputs to the circuit they can be anything i just picked some random numbers

uh i don't think that seven x or two is one but i don't i didn't really check i just picked some things uh those don't matter actually um so then uh we compute the commitment verifier key uh and verifier does their own pre-processing uh and then we can run this verification here okay uh and then we'll we'll see at the end if the verifier accepts

so what we really need to do is uh fill in these two functions um generate xor lookup table 4-bit and example circuit both approver and verifier use both of these to create the circuit okay uh let's see here i have my cheap guide uh okay so to generate the table uh we'll just use some for loops uh

these are gonna run through all four bits so it's just gonna go from zero to sixteen uh i is going to be the the values in our first column j will be the value in our column and we'll have our composer this is passed into this function the standard composer handles uh creating the circuit so the composer has a lookup table attached to it i'd look up table is just a uh a wrapper around a vector

so to get to that vector i'm using the dot zero here and uh we will push a row the values so our row of values is a row of scalars we'll use bls scalar and hi here uh we need to pass a u-64 so we'll cast that to 364.

second value is j your value is x or y and j uh this uh this version of uh the library basically defaults to a a table that has four columns we're only using three columns uh so in the last column we'll just um just give it zero okay uh and that should do it

uh this lookup table could be generated by anyone it could be generated by the approver it can be generated by the verifier it can be published somewhere downloaded whatever as long as prover and verifier agree what the table is supposed to be xor then they can generate this table okay so there's our our code that generates our lookup table um let's continue now we need our circuit so here we will put in the gates and any

any computations that we need to do in order to fill those gates so one thing we need to do is uh is take our left right and out inputs and uh split them into uh four bit chunks uh as our lookup table is uh is based on four bit jumps so this is just a bit of arithmetic um this will split in each piece into a high and low part and create a scalar

for the for the high bits we'll just take the left uh input and do an integer division by 16. and then we need to cast that as u 64. so yeah it's under your division that'll get you the the four high bits if you want the four low bits you do almost the same thing except you uh switch this to mod so uh there we get our high bits and our

low bits and uh this converts them into a scalar so we'll do this with all three out so now our three byte

inputs are split into uh scalars that correspond to their upper and lower bits okay now we're going to to include these as variables into our circuit so we take our composer and uh um

this will take the the scalar and turn it into a variable i want to be able to refer to the variable later so i should probably so uh our scalar input will turn into a variable in the composer and we need to do this with all six pieces be absurd that i'm

typing in front of a bunch of people i failed typing in school okay oh wait a second oh these need to be changed too okay all right looks good uh there's one more variable we need

which is um after we do these uh these xors we're going to have the out uh bits and the the out high bits and the out low bits we want to combine those back together into um the out variable here so we'll also include yeah out to u8 so we'll we will need to convert that into a

scalar okay there's all the variables we're using next we can add the gates okay all right we're going to use two lookup gates one for the high parts one for the low parts xor is really nice for this because you can do xor in uh you can divide things up into pieces and do x1 on all pieces and then compose

them later okay so we pick our composer and uh do a flick of gate uh are there high variables so um as i said uh

this version defaults to a width for table but the the fourth element may or may not be there so um we need to wrap it in a sun and this needs to be a zero so there is a zero variable that comes up along with the composer that you can use in this case but it's really just an empty column so put a zero in there and there's one more input that we need uh this is a a public input which we're not going to use so uh we'll just

so uh let me label these so we are looking up this tuple in the table and then this last one here is public input you may in some cases use a public input to specify a particular table that you'd like to use we only have one so we don't need them okay so this is going to check the xor relationship between the high variables

we have to give the out high variable uh so we have to compute this ourselves and uh and put it in here and this this gate checks the relationship between them um in this case it doesn't compute the output for you although you do have some some arithmetic gates that do work like that all right we'll do the same thing with the low side um zero that's still going to be zero so i think that's good

for our look-up gates so this checks that um the high bits actually xor up to out high and the low bits actually xor up to out low but then we need to combine those back together and check them against our uh out here which is also encapsulated in this variable outbar so we need one more gate uh this is just going to be an addition gate um we're going to kind of reverse the uh this decomposition that we did up here

where we split things into upper and lower so all we're going to do is take the the upper bits for out out high bar and multiply them by 16. and uh that'll give us uh four zeros in the lower bits and then we just add out of our low or out low bar to get back to 8 bits so this is an add gate and we're taking the out

high bar out low bar the out far as inputs we want to make sure that our constraint has that 16 times the high var plus the low var equals the amplifier um this is going to be our multiplier on the high bar i'll label all these later just like i did these this would be our coefficient multiplier

on low var to be our coefficient multiplier on the out bar it needs to be one but because we're trying to constrain these to be equal to one another uh or all add up to zero rather we need to make it negative then we have two more scalars that we can put in but we're not using these really so just and uh yeah let me label these for you

so you can move you can see and then these are selectors this is the ql selector that modifies a q r selector which modifies b it's not very much modifying because it's one then we have the ql selector now i already did that q o selector this is a constant

you see most of our gates you can add in a constant as well and this is public input uh david asks what's the d here uh this particular style of gate uh is written to uh to just have three inputs so it just automatically puts in zeros for d we have multiple versions of these arithmetic gates some are some allow you to set every single variable and that

that long constraint some are more focused so where if you only need uh three inputs you can just use the three input version yeah d is the fourth one um okay uh let's see um will that do it i think that'll do it so we just have three gates in our circuit two lookup gates which compute the xor and one addition gate which re-packs those those four that chomps back

together into an eight-bit uh bite okay so uh if i've done this right and i haven't made any mistakes we should be able to run this um we'll see oh let's see so uh we're going to see the plunk up um cargo on release and uh hey can you see that yeah it worked

so uh goes through the the steps generating parameters that's the trusted setup pre-processing uh then creates the proof uh the verifier does their own pre-processing verified as their verification and proof is accepted so uh the proof was accepted because our inputs really did correspond to um xors and the gates here here's where we got our inputs left and rights were random but then we we did the xor between left and right together out and um so uh it should work and it did

but what if i mess this up a little bit even xor and just add a plus one um then this should not verify and i actually will see what happens um okay now oh make sure save it first before you compile okay uh so what happened here is uh we had a panic we tried to unwrap error value i said element is not indexed

this happened while we were creating the proof so what happened here is the prover uh in our implementation approver checks as they're creating the proof that their their lookup queries are well-formed and uh and actually exist in the table um so this is the prover saying that they're not going to create a proof they're going to quit because they know it's not possible because one of these one of these values was not in the table it is theoretically possible for approver to uh to ignore this

try to create a proof anyway um if that were if that would have happened uh instead of getting an error value here we would have the proof would just have failed to verify so this stopped actually before that verification actually took place um another way i could mess this up is uh mess with these scalars here so if i put two instead of one and save our our inputs should not satisfy this gate the xors will be done correctly

but when um packing them back together to make uh the out bite it shouldn't work because the the lower bytes are going to be multiplied by two uh so this should not verify let's check it out so now you can see the proof was rejected um [Music] because our inputs did not satisfy this last gate all right in the interest of time i kind

of skipped past some things that you probably would want to do if you were actually designing a circuit uh i only ever checked that the out the out byte is formed from those upper and lower bits here with this last add gate the inputs left and right were never checked um so this decomposition where they're split into high and low uh this is never checked in this circuit

uh if you were really doing this you probably would want to uh to constrain those or check that that that the the left inputs actually correspond to the high and low that we say they do here this computation is not done in the circuit this is just the prover zone like private computations they can do however they want so there's nothing forcing them to actually decompose these inputs correctly only the outputs are constrained with that landscape but this actually kind of corresponds to a lot of normal use cases because

often you have inputs to a circuit or a portion of a circuit that are outputs from early parts and so they might be constrained in earlier sections so i kind of was thinking of that scenario when i was was practicing this example circuit but it wouldn't be too hard i'm not going to do it now but it wouldn't be too hard to add checks on left and right the same way that we have them here for out uh just by copying and pasting this uh all i'd have to do is change the out to the document it should work okay uh that's it uh are there any questions over um

any of this this live coding part any questions about the gates or questions about why i did certain things um joseph says great demo thanks you welcome a little bit more for questions in case someone is uh thinking hard and

typing a question i'll uh just say some uh more remarks on this uh this repo the one that i'm using for this exhibit uh is a little bit out of date it was the easiest just to get up and running for for this um this exhibit uh but our uh our best version of this is uh is located at uh uh it's called arc planck ark dash planck uh and it uses the artworks back end um if you've been doing some of the zk hacks uh you've probably already seen artworks and know a little bit about it i think there was a presentation on it

uh so yeah we're reporting this library over to uh to arc plonk and um let i'll just uh uh rust zkp arc plunk the library is not complete yet we're working on it but it's uh it's actually a little nicer than this one that i'm using here very cool