zkSummit: plookup: Speeding up the PLONK prover - Zac Williamson & Ariel Gabizon

Transcript

I don't know if you want to maybe just introduce what you're about to speak about well we're getting Muriel set up yeah say a few words so yes so what we like to kind of present is some new research and that we've been working on over the past couple of two to three months called a P lookup I think I think I might have been careful you're calling the original name effect essentially what this is is is it's a scheme to that implement that implements efficient look-up tables via polynomial commitments and so and the idea is that it can be integrated it's quite easily into a a stock proving system that uses

polynomial commitment schemes like plunk what it does is it the the goal of is basically to make us not come from the algorithms friendly a bit more friendly by replacing computation with with lookups because you know computation is hard and why bother doing work when you can just refer to someone else computation instead so the idea is to basically implement key value mappings over precomputed tables that can be used to create extremely efficient circus so for example things like exclusive or operations on binary on binary like values doing things like 16-bit range checks and even things like looking up a looker point so nobody can be disabled

for pairs of Nash's these operations become extremely efficient because the lookup is effectively constant time constant of like stages as one gate into the circuit so it can increase the efficiency of clear instances like trunk by a tree over an order of magnitude as we know snarks are easy prey in a world of nasty binary function what what that means is is that for example say we want to do we have three field elements and we want to show that the third is the bit

why's soar of the first two when thinking of them of their binary decomposition when thinking of them is a bit strings so the way we're used to doing this in snarks is basically we write we explicitly write the binary decomposition of a B and C and then prove that bitwise really prove these binary decompositions are correct and then prove that you know the bitwise XOR holds for each bit bit so basically this

would take you 25 to 32 constraints say in our one CS the the difference between 25 and 32 is if you insist on also checking the binary decomposition of C or just inferring it right so the basic problem at a high level is that we need to represent our operations in native field operations so we had and ok 25 32 is not a big number are not big numbers but the reason it's painful is this is a multiplicative factor we pay basically

say we write sha-256 as a sequence of 8-bit operations right we have the rotates the bitwise and the bitwise soars so each such operation we're going to pay this this multiplicative factor and for this problem that has become is getting a lot of attention in the last few years is to not let our snarks out into the cruel world of arbitrary

bitwise operations grab them keep them in in friendly neighborhoods of new hash functions that are being designed that are based solely or almost solely are not I confess I'm not a big expert on these these new functions but basically that consists of native field operations like Q being square roots inverses and this this approach is is getting a lot of attention and has a lot of you know has advantages right so maybe to answer dara'a question I guess

I was thinking it's 25 because it's like 16 for the binary decompositions of a and B then another eight for the bitwise Wars and I was thinking there's another one there for checking I guess for the checking that these are really the binary decompositions I didn't count it carefully maybe you can do 24 there is more of an expert than me on this so basically an alternative approach to this that was used in in the Aria system for example is let's do let's do something else

let's not explicitly represent the logic of these bitwise up non native operations let's for example just pre compute a table of all the legal input output tuples so all let's pre compute a table of all a B and C in the field such that if you look at their binary decomposition you'll all three of them will be 8-bit strings and C will be really the the sort of a and B right so the idea here is instead of

trying you know working hard to represent efficiently the the logic of this non-native operation let's just try to somehow check that this tupple ABC is in our precomputed table and the the point is that if you do enough lookups then like there's going to be some costs for this table and

enabling this operation of checking that things are in the table but if you do enough lookups this is going to be have an amortized cost of sort of one constraint per per such operation all right so how does this protocol of proving that values are in the table work so a slightly awkward but also nice thing that happened was that while preparing the slides we actually came up

with a protocol that's simpler than the one in the paper it still doesn't be when you really count the counts to constants it's it seems to be not as good as the one in the paper but for explaining how to do such a thing it's much cleaner and simpler so that's what I'm going to try to show you now yeah so the basic tool here is a multiset check so we're given say we're giving to like set or multi sets of values there can be repetitions

and we on a check that like the A's and B's are equal is multi sets so they contain the same elements even counting repetitions but maybe in different order so this is a basic tool and here's here's how how you can do it so you choose some random gamma in your field so right so think like the A's and B's even though even if they're different it could be that if we take the product of all the B's and all the A's will get the same thing right

say the A's are all ones and the B's are like half 1 & 2 so we can't just compare the product of the A's and B's but say we after you've fixed the A's and B's we choose some random gamma and now we compare again the product but where everything is shifted by this this random gamma so obviously right if the A's and B's are the same just maybe not in the same order then these products will will be the same and what you can show from the Schwarz epilim of pretty

easily is that if they're not the same then with high very high probability over gamma the product will be different so so right with a simple randomization we've reduced this multi set track to just one product check and so a big part of plunk is saying that okay when how am i given these A's and B's so if I'm giving the A's and B's as like values of polynomials that I have commitments to then there is a

extremely efficient grand product protocol that it then enables you've just given sort of the commitments to the A's and the B's to to do this check all right so so we have this basic tool tool the multiset check and now another small element so so now I'm let's say the witness is these values fi and the table is these values TI's so we want to prove that the FS now not as multisets

just as sort of sets the eff that all the values in the FS are contained in in T so one thing that may confuse you right we had tuples before and now we just have these single elements both in the witness in the table but it's sort of an easy exercise that with randomness you can reduce from the temple case to this single element case okay so so let so here's how the this the simplified protocol we came up with

two days ago works and I'll just I'll give it just on a specific example so say our witness is the multiset 3-1-1 and our table is one three four so right so the claim is true all the values of F appear in T and now approver wants to convince you of this you have you have just the commitment to F polynomial commitment to that so here's what you do the prover will commit to a sorted

version of F Union T here I hope it's not confusing I'm sort of shifting between talking about sets and multi sets but here I mean sort of a union as a multi set is even an ordered I guess multi set so so right so s is s is right is the vector 1 1 1 3 3 4 right if you take all the values in that all the values of T you take their multi set Union you write them you sort them this is this is the S you're you're going to get all right and now the prover is going to

show that so the provers commits you know sends this commitment to s and now using this multi set check protocol the prover is going to show that is multi sets s and F Union T are the same and you know a minor technical point is that using sort of the long grande product if you have commitments to F and T then doing the grande product over F Union T is not it's not a big deal you

all right so so right at this stage we know that s is equal weight living at this stage we know that s is equal to the union of F and T but you know that doesn't it could be still at this point that there are things in F and you know it shows so far that whatever is in is in F is is either whatever is in s is either an effort T but still at this point there could be things in F that are not in in T at this point we don't know that yet otherwise right so so now what we'll do is we'll look at the

difference multi set of s call that s Prime what do I mean by difference Multi said very simple right we look at the the elements of s and and we just take we just take the difference of each two adjacent elements so right we're going to get a vector or a multi set of size 1 less than than s just and right we're just going to get you just do the computation 1 minus 1 0 again 0 then 2 0 1 right basically every time there's a repetition where it's

going to give us a 0 right the repetitions here are the or what makes it sort of non-trivial if F was allowed to use just each value of t just once then we could just do a divisibility check between sort of the polynomial whose roots are F and was root 30 but the multiplicities here are the in are the potential problem that maybe f uses something from t many times like like is happening here with one right so this is the difference multiset you're basically going to get a zero for each repetition cool and and and also we'll compute this difference multiset of of T so call it t

prime so right it's 3 minus 1 we're going to get to 4 minus 3 we have 1 so we have this S Prime and T Prime and and now what we're going to show is basically that the non zero differences in s prime are exactly the non zero differences in or the non zero differences in s are exactly the non zero differences of of T and why can we do this at this point with just a multiset checker because we know that we

already know that s is f Union T and we know that well we sort we know that the the difference is coming from F and not from T from the repetitions in a sense are just going to contribute zeros how many zeros like the size of that so basically the prover checks that s Prime you is T Prime Union as many zeros as the size of F so so this is the this is the simplified protocol so I think I'll I'll basically I'll give you maybe a minute

to process it and see if there are questions and and and if not I'll hand over to Zack you you actually even while you're while people are thinking about questions I'm wondering if Zack could potentially continue only because we're currently running a little bit over time into the break and yeah although I get it I think area you want to keep that slide up in a way right oh can you hear me I turned on my volume now okay so yeah I think you

want people to continue to be able to see that slide right yeah but I think yeah yeah I wonder I wonder how we could do this I might actually if I bounce out I wonder if Zack you could share your screen in my place yeah happy to try that yeah then you could actually keep this although actually then I'm not I mean that might distract from Zacks presentation so I'll stop sharing and I'll put it back on after Zacks time for the Q&A maybe what I'm gonna do it just so you know is in the next like right

now we are kind of going into our break time so I will probably actually jump out of here to get the next speaker ready and you can continue you should keep going as long as there are people in this session and that people want to continue to be part of it so why don't you set up your slides Zack and I'll make them big and then I'll bounce out I can also bounce back sounds good okey so sharing screen okay cool so yeah so that so this is a kind of follow on make me

talk Mario just going over what you can do with these little tables and the efendi the kind of implication is for common are dozens and circuits and one the trade-offs one of the costs and so working title for pluck up funk is something we're working on called ultra Blanc still very much an active work in progress what the with peeler cup what it enables is extremely efficient key value mappings um because there's witnesses say that you're proving are members of this this multi set T F is a canon in in other plant will be kind of a rent a random

linear combination of multiple witnesses um so for example if you want to do an exclusive or operation you can take your kind of your two operands click around and any combination of those and the claimed output of your exclusive or table and that becomes an element of F and similarly and you can do a similar thing to cream struck the elements of tea from pre-computed precomputed polynomials you can also create a simplified version of the lookup table which isn't a paper for scenarios where you don't need work for where basically for range proofs if you just want to prove that something is within a range you can do that very efficiently up to about ranges of like 2 to the 16

extremely practical once you start getting above that the size of the look-up tables going to get quite large which does have a knock-on effect on your the preview tations see the prism it is is you literally get river an order of magnitude efficiency increases relative to our and cs4 common algorithms things like like conventional hash algorithms Pettersen hashes range which constraints so just realize I didn't actually sorry I supposed to add let's add a reference there but um so you can implement the round construction of some the tiny realm architecture very efficiently so you can do things like kind of access an element in a turn

around will turn around my construction in a single gate instead of having to have a like a a logarithmic factor and for practicing your memory and you can implement each number systems via these lookups and by Nisha I am a so you're referring to things like the integers in the world of snacks yeah that anything they're just like kind of not your native Frank your mother's is difficult to work with but you can do things like not just integers but also obviously prime fields that aren't the native circus prime field and even things like binary fields within a prime field based not for things like if you want to do a es encryption the downsides are it does have extra commitments in

the papers three but we very complete we can get that after two when most integrated into plunk the table says cannot people work you might need to add dummy gates into your circuit if your table size is significantly larger than the number of actual constraints in your circuit which does limit the size of these tables particularly if you're doing things like creating small circuits to be for proofs that are designed to be constructed in the web browser um it's also is it's tricky to integrate into sparse snacks like the constructions that Justin was describing earlier I'm sure it's not insurmountable but the one the one of irritating problems is you need to fit this kind of

sorted list where you're completing a set of the differences in your sorted list you do need to kind of access adjacent elements in your list and so if your list is sparseness full of zeros that's more difficult to do and also there's a creeper concept impression of P Lipa written by care that doesn't work just link to it below of anybody wants to have a gander so yeah ultra block is an iterative upgrade from deadlock where several funk was basically talk with custom gates custom constraints to do things like Penniston hashes and binary arithmetic and this is a yeah and so effectively a lot of the infrastructure that we

developed a tiger paw can kind of be replaced by these little tables and the overall effects on kind of the precise and the number of prove amount of people work it's relatively small so ultra pond has gone down up to 13 in g1 scalar multiplications where n is the number of gates in your circuit the original pocket was nine but you can gain the number of can actually gates in your circuits gets reduced back between a factor of 2 mins a hundred depending on the easy hovering you're executing and the pre flank is very small it's still it's a full Andre kilobyte my final slide is basically just some gate counts how many gates does it actually

take to do common algorithms if we if we use ultra block I thought she numbers here one is if you're kind of the tables that you're using or have to you the 12 elements and one for 2 to the 16 so the 2 to the 12 context is a fee if you've got a you know a circuit where the number of gates is about 2 to the 16 you don't want a lot of like look-up tables who themselves others are the size of your circuit because this commitment to s this sort of list kind of requires at least as many entries as you look as as you have in your lookup tables so that can become very costly if the lookup tables have a similar size to a second size but you can see here I'm basically compared to you total pump if LCS look

up stuff it just it's it's a profound change in basically what's possible the parent base it's nuts now things like hash it hashes become almost like approximately 10 times or 20 everything Pettersen times more efficient you know you can do an entire 512-bit pedals in fashion and 64 constraints and you can even start to do things like prime field multiplications over a over over that like arbitrary prime fields extremely efficiently so this this number of giving here for these minor field models that's assuming I should have had it added bit more context if that's for

like the 256 bit prime field which whose modulus is not equal to them your native circuit modulus with also plunk with range low-cut is about 32 constraints which is means that things like recursive snap compositions without having to rely on cycles of pairing friendly curves becomes extremely practical and everything if this is also a welcome progress will missingness but we're very confident that we can get the number of constraints to verify a recursive slot down to about two hundred thousand which is that's like two to three seconds at favorite time it's it's yeah yeah so yeah we're very very hopeful this can

this will um make a lot of snack unfriendly algorithms much more feasible internet yeah that's about that's about it we'll have to share yeah there's a question here there's a couple questions and actually people should feel free to add questions in here and vote on the questions that are already in there I don't know if you would like to take one of them do you see the ask a question at the bottom yes I do why does the nominator feel most the kitchen coaster with increase the deficit that's because I made an error and I put I heard for

those in the wrong work wrong or that it should shrink yeah my bad okay listen hash is cheaper than Poseidon an ultra block I think they will become quite similar I'm not sure so my knowledge of Poseidon it's it's it's a little old i I can't remember it Posada could benefit much from precomputed tables it can then then society will have a similar like increasing efficiency but I yeah comic authors of my head they

should be it should be at least more similar than they currently are not in our Macias basic instructions III would guess yes I would guess that they it would be cheaper what kind of recursive priests are we going to implement using P lockup well one of the one of the advantages of basically is brute forcing recursion is that's the verifier runtime is constant depending on use that it's not function at your site sense which means you can verify Alba 3 seconds with arbitrary verification keys for the same cost like

no additional complexity so what we're looking to do with it in the in the immediate term is implement zqz karela on a thinning so that you can do basically last year last November we launched the Aztec loss no sir this January we launched at the us our asset protocol on a theorem for private payments and we want to defer our first plan is basically to add full anonymity into that construction and also reduced significant use the gas costs by willow and all that magnitude by using a zeeky zeeky or not construction we have a rollup that aggregates private transaction smokers but the the the the ramifications are much wider than that

you can start to do things like theoretically if if the implementations can get refined enough implement light clients it's my contracts inside of theory so you could do things like a bit like on like clients buy a stock second for a courser stock circuits so that you can have basically a trustus oracle or if they're in for this object for the state of bitcoin and yeah you go you can all also something we're exploring is using crazy multi-party computation constructions using recursive snacks these are the kind of scope of what you can do is now increase significantly I hope that answered it Justin it's

definitely more remaining a process right now what we're doing right now is would be we're but it so are kind of our long breather verify libraries it's called Breton bag it's it's all it's all open source and right now what we're doing is implementing gadgets on it which explicitly I call these look-up tables I haven't I haven't really making it transpired that takes of battery circuits and figure out the look-up tables it seems like it seems non-trivial yeah I think that okay can you hear me yep oh so I mean yeah maybe to state the obvious I mean the

good thing is for like the common things like you know Shaw it's it's very natural and obvious what what you'll do a lookup table for your look you'll do a lookup table basically for the bitwise Wars and bitwise ants and that pretty much gives you like the speed-up do you want to answer another one of the questions here yeah Deb I wonder could you could you expand a bit on your question like what what kind of yeah I'm not I'm not I'm not

sorry I'm not not what kind of structured operations you do you mind if dev is here and if you're available we could actually bring you onto the screen I don't know if that would be something interesting dev are you around let's see if he's hearing us waiting for him in your charge okay I'm gonna bring came on home I see what you're saying so it's basically if the two of the Chiappa realms are kind of you today we re it's brought that to be honest yeah that

there might be both it's not it's not something that can you hear me yeah yes I can no longer okay can you hear us now okay I mean I think well maybe while he yeah it seems like an interesting idea if we can use the commutativity of bid wise sword to get the table down by half I I didn't think about it it's a it's an interesting thing to think about yeah it yeah if you're if you're willing to represent integers in a bit of a

freaky way by using multi linear subject so you have like roots of unity or a subject criticizes like 2 to the 8th then then you might yeah you might be able to yeah yeah something really worth exploring I know something that I think something ever library's gonna huge much I'm thinking about yeah I mean what one thing to say is this right this thing we I mentioned about compressing couples to like ABC to a single thing that usually you do it with some random combination that ruins like all the structure you had in the original table but yeah it's something to think about definitely yeah

um all the way down sizes you can see here open thermos no no no chill easy cash hmm it's good question but there are some pros and cons the downsize would be you kind of you have to play by the rules of the block when you're working on we have to use the moments being chief I thought as all-time friendly elliptic curve because implementing any other kind of the curve without pretty passive orders would be hideously expensive whereas obviously running your own chain then you can just you can whatever you want you also because you're obviously sharing a blockchain with everybody else in the world the data the cost of data can become

quite can become a bottleneck for example you with is accusing key role of you want to do digitally ability and chain then there's a cost of that which obviously you're running around Cheney could probably mitigate that that the the upsides obviously these are much much larger user the user base you have to quite at the traction if you're and chain you don't have to create your own consensus network which if I approve of work right now would be would be very difficult in the modern worlds just in us used a relatively different algorithm but people could use existing like Essex or GPS on and also obviously but the the what we really like about we're building

my theory is we can get we can focus on what on adding value the way the word like in the best way that we can we can focus on a cryptography on the implementation you don't need to have the overheads of running around chained up facility but is a very mix back I say what does the over had to include lookup tables in the circuit the overhead is the prover well it we split things out to be even verify advance the verify overheads are approximately I think is going to it's gonna end up and with about six or seven extra elliptic a

scalar multiplications the verify has to do which it's not it's not it's mind it's not insignificant but like relative to the tuple any pairings that you live ever ever guess to compute like the marginal increase in verified complexity it's not it's not that large compared to existing time for the prover you obviously you need to commit to the sorted list of Lucas which is at least one kind of extra polynomials commitments in the papers to but we effectively you can leverage the fact that in a plug circuit you're not every gate is going to

contain a lookup which basically you can you can probably yeah Zach I think that's maybe a little too so I think great the simple at a simple level you pay you need to add to your witness yeah like this sorted you need to pay with this sorted witness where you pay basically the size of the table once and you pay for for each thing you want to check in the table you pay for it like you pay for another field element so basically all these things you want to look up you you need to write them twice like once in the original witness and once in the sordid witness yet as you can see here open construction is going

to be very very heavily its kind it's gonna follow in the footsteps of Z cash using the concept of nullifiers to achieve to break the transaction graph and see for currency what is Aztecs open stock research problem I'm sorry okay so the one that the well I think is the big big one for us right now is if you look at the kind of lumped element ultra pond you look at what the prove is committing to the majority of the polynomials are committing to the kind of the evaluations of these polynomials on the subject mostly the circuit we use their values basically reinforcing Trifield because there's a

lot of random is injected into them so with ultra plunk there's going to be 13 pollinate equipments and only four of those the evaluations on age of these polynomials will reflect witness values this is a this is a this is like it's irritating because generally in a stock circuit a lot of your witnesses are going to be quite small for example if you're doing binary boolean logic your witness values are going to be the one zeroes short integers and this if you pre process your comp your structure reference string this has a direct correlation with

creepy time but because if you're doing scalar multiplication and your scales are short that's faster than if you're scalar multiple if you're skilled at scalar multiply its range across the entire field and for plunk nine out of the 13 polynomials discrete the skin and off supplies do range across each eye field and I guess the the upper research problem is can we can we reduce that somehow can we make these gear these these commitments either have like lower degree or have values that are more controllable more directly related to the witnesses similarly I think another at the research problem maybe these things that combined of it is the Fourier transforms that you have to do

you to construct concrete I'll quite relatively large and it's a yeah so really releasing those the cost of there's the number of them all that the complexity is another big open problem I don't get me any other scenario so I I think the the the specific case of range proof where the lookup table is just 0 to M I think that can be improved probably significantly from the lookup paper so I think that's a great thing to for people to think about just I just

want to give you a heads up I'm actually gonna be heading over to the break section but I want to keep you guys going here so this is I know I announced tit earlier but I stuck around but now I'm actually gonna head over there so keep going if there's more questions or come join me at the break session shortly cool so I think I think that's all the questions on the lists answered if anybody is young I was happy to they were happy to to continue otherwise medieval we should we should jump into the break room