ZKMPCML: From Memes to Reality

Transcript

hello okay cool uh hi everyone I'm Aira you might know me as bad crypto bch on Twitter I post a lot of memes not recently but over the past months I've been posting a lot of memes um just following the z g in cryto Twitter um and uh yeah today I'm going to be talking about some work that we did as a result of an Aztec grant that we got recently um in terms of making it more practical to actually like get to MPC ZK MPC ml um so I'm pretty sure most of you who follow like Twitter or Discord are like just what's going on in the space you might have seen some combination of these acronyms before and like at first it kind of it just sounds ridiculous

right like who would actually type this I mean I did for the slides but like in general like when you see this on Twitter you're just like it's some guy in front of his oh wait it's not well you'll see him soon yes so guy like this tweeting you know kind of like meditating to make it a reality but he has like no expertise in ZK NPC nor ML and you're kind of just like proplex as to like why is there some guy in CT like this um for some context if you don't know this is Rick ruin he's like a famous producer um if you listen to like Jay-Z Kanye he's like known for being their producer he has like no formal music expertise he kind of just like is there for the vibe check

he knows what people like like to listen to um except like he's actually successful but like the people on CT are not not really successful um but yeah it's like a good representation of like what the state of the kmpc ml feels like um and even when you do see somebody who might seem like they know what they're doing right they look all imposing they have like raised tons of money they have a website and when you go on their website you try to figure out more what it actually looks like is this right there's nothing in the back end um you don't really see anything uh there's no code it's just like acronyms everywhere I guess for for hype um but uh in this talk we've actually tried to make it like a reality

or at least like towards making it more of a reality um so quickly we'll talk about like what we actually worked on um how we did it so this is like the most in-depth in-depth part um some quick results and then some final conclusions for for the future so what did we actually work on so it's part of uh nor research Grant uh so Aztec has these like um rfps for Grants on different topics um we've managed to combine NPC ZK using nor um and using a tool called Conor uh that you guys will hear more about later um in in the day um so you combine these tools together um in order to sort of take a stab at ckm

pcml so specifically what we did is we implemented the building blocks for training and inference uh of logistic regression um and logistic regression is like a foundational model for other ml models that people care about um it has like sigmoids stuff like this um specifically we focus more on the training because that's typically the harder part um and that's the part that people care more about um and sort of like where the alpha is where companies sort of um care most about privacy um the data sets how you do the training those are typically the things that um large companies care about so we just focus on that um and then once you get that inference is a rather straightforward um so basically we focused specifically on how we represent

numbers um this is like a big issue in ml like keeping position um and the accuracy of like your calculations um so we'll go into depth about fixed Point numbers and then we implemented some key algorithms um that people heavily rely on in ml specific stochastic grade in descent um and sigo function um specifically the logistic sigo function um but then there's once you have this you can sort of implement other kinds of sigo functions so quickly what's uh logistic progression uh you might have seen this in like your high school or like university courses um it's a model that lets you classify um data based off some given features um and then the S mod is sort

of like what you're um what you're Computing to actually get the the uh the the classes right um so you you're given a set of data um you train it and then you want to say like oh is this and a is this like a bear or a cat or something else uh based off the get the given INF sample um and then how do you find like the betas here well you basically run um you basically run this optimization problem um any you calculate how well your optimization problem has done um against like the regular data set which is the log loss here um so basically that's what we we worked

on uh so like a visualization of this is um basically we have an NPC Network these three nodes um one of them is like malicious um you want to compute logistic regression um and then you want to compute that like the result of the logistic regression competition was done properly so that's the proof part um and specifically what nor allows is uh public auditability so you can post you know your proof on chain and get like a verifier um we didn't do any like onchain stuff for for this project but um it's totally possible with uh the tool set so how did we actually go about doing this um by implementing this uh it looks simple but it's a lot of work um so you

basically implemented this um in npcn C specifically just in nor um the nice thing about K is it lets you reuse um your noral circuits for NPC as well so basically um the way this algorithm works is you have this update function um these beta t+ ones um and you just like iterate until you converge um on the error um between like instances of the betas um so basically whenever you hear like MPC defined it's usually like you compute some public function over some private input and get like a public output um so the public function is this um itative solution uh the public result is the the

final beta not the it of betas um and then the private inputs are X and Y which are from the training data set so in ml we care a lot about like how we represent and miniplate decimal numbers um so there's two main options for that so the first option is floating Point uh which is very common um and it's represented in this format you have some Precision you have some bias um and you want to like represent like as accurate as possible the floating points um and then the other option is fix points which is a little bit less accurate um but is like

more more transportable across architectures and it's simpler to Define so the criteria that we sort of use to um determine what direction we should go in is based heavily based on like Noir um you want to be able to compute negative numbers uh we want to be able to handle relatively large numbers and we care a lot about performance within circuits um and that's like the key part here and so we settled on fixo numbers um floting Point numbers the operations over them can be slow um since we're operating over uh in Noir um it just made more sense to focus on

something that has more determinism um filling points are like better if you have like an FPU we don't have that here um and it can Yi different results which is not really worth it uh whereas like fix points it's faster to do like a lot of operations with them uh consistent results across executions and you can like control um loss due to errors and stuff like this um so that's why we focus on fix point uh so fix Point uh so there's a specific strategy that we uh implemented uh from Katrina SAA it's a relatively old paper but it's very relevant it's implemented in quite a few like NPC libraries um and the goal is to encode a decimal number and field of integers mod a prime so in

Noir um field elements are 254 bits um so the strategy is to take the first 127 bits um and have that be a positive value um and then if you want to represent negative values then you can use the last 127 bits um however in Noir there's this decompose uh functionality that can either decompose uh an element into 128 bits or 126 bits um so we decided just do the 126 bits based off the slide here and so we don't use the middle middle bits um and yeah as mentioned before we're operating over field elements and

not decimal numbers so you need a way to map you know fixo numbers into uh field elements um and this process known as quantization it's very common um so you use it mainly to save space um and so basically what we did is we scale um all the numbers from like a regular data set um into this format so if you have just an integer you just m M by 2 to the 16 um if you have a decimal you multiply by 2 to 16 you truncate um and this is this SAA um paper goes over like how to do a deterministic and probabilistic uh tration so in code this is what it looks

like um so now we just have like one element to represent one large number as opposed to two um so oftentimes you might see like a fix Point U representing like two uh field elements uh we reduced it to one so we save quite a bit of space and then operations over these elements are rather straightforward um add and subtraction are pretty straightforward um however for multiplication it's not as straightforward um because you need to be careful with handling the Precision and the error right so if you naively multiply two quantitized numbers um you end up with a large factor of 22 to 32 and now you need to divide it to get it back to like the right size

um so visually this is what that that looks like for positive numbers um pretty straightforward um CES from the previous slide uh divide it by 2 to the 16 and now you have this like number what that's within um the correct size um but then for negative numbers it's not so easy um you might divide and you might get some garbage um so the way to fix that is by flipping the sign and then um flip it back once you've done the calculation but we're not done quite yet um this this issue of do you actually end up with the right uh size elements after doing this operation right so for

multiplication both operant should be maximum 63 bits for addition subtraction and most they should be 125 bits um but when you do this go back yeah if if you do this you may not end up with something that's of the right size right so um there's a concrete example here we have this multiplication um we get a * B * 2 to 32 you've divided you've scaled it down um but you may end up over overflowing here because this final number may still be larger than um 63 bits or 125 bits um so yeah this is this was done by like enforcing it directly

in the circuit um unfortunately adds more gates um but it's necessary to make sure that um we don't get into like these numbers and that um all the numbers that we get at the end is accurate so we kind of handle how to we've gone over how to handle decimals in circuits um but we haven't like talked about how to handle uh the sigmoid function quite yet um and this is pretty important otherwise you can't do logistic regression so quickly what this looks like um so you have this like e to the X Factor you have a division um ideally you really don't want to implement this in a circuit right um so there's ways to approximate this um and specifically

there's a construction from hung at all from this paper in 2020 uh that gives a specific sigmo function that works well for secure computation um so this is what we ended up implementing in the circuits it's a PE wise NE function uh which looks much nicer than um ETD X in a division um and yeah there are results which I think is what people care most about so we implemented this on a single machine um and simulated the three parties on a single machine um we we ran an honest majority semi-honest adversary NPC protocol provided by too um and we benchmarked um the multi uh the training specifically multi

training across two uh common data sets um the iris data set and the wine data set um and so concretely what this look like um for Noir by itself this is just a proving um the numbers are actually quite promising um with relatively like small instances um but for for kir as you can tell that the numb is are a bit like larger but this is to be expected especially for training that's the part that takes the most time um so for 10 Epoch and and 30 training samples um it takes about 30 minutes um and then for 20 Epoch 30 uh training samples it takes about like twice that so about an hour um and then when we do the same thing on

the wi data set for cono um once we got like over 30 training samples the machine we had kind of like froze and would killed the process so we just have like that text there um and this is contrasted with just like normal um if you're just using like psyit learn there like no fancy cryptography um over the same things then it runs like really quickly and you can run it on your own Machine by yourself um so that sounds kind of like pessimistic right on a single machine um using you know regular uh ml libraries it's really fast but using fancy cryptography takes quite a bit of time um however U as part of our

conclusions we're pretty optimistic about this um once you sort of start applying like Hardware improvements uh to see will be obviously working really hard on kir um you can get like a sizable Improvement in these benchmarks um really it's only like up from here um or I guess down because we're trying to get the numbers down um but up in terms that it should be faster um so we're like very optimistic about this um so yeah uh what's next we have code you can play with it uh we have a full report with like way more details the stuff about optimization the stuff about Noir um

that it didn't get time to go over um yeah and uh please use it um yeah we're trying to get people to like use this for things that they might find interesting um even if you don't use the ml portions the stuff around like fix points matricies still very useful um so yeah if you have like a project that you're aiming to build um you know come see me after after the talk um and if you want to learn more details you can get the report um I want to thank everyone at the hash team so I'm the one who gave the talk but everybody else did the work uh sir Hanan and Elena are are cryptography Engineers um they did all the heavy lifting uh Teresa is are project manager to make sure that

everything is scheduled uh on time and get resources done uh Savio who's the uh product manager of nor Aztec um was the one who helped us like get this grant by like introducing it to us and answering all of our questions um and to se they were like very helpful throughout this entire process um we kept on asking them a bunch of like random questions and like finding bugs and they were able to like Rectify and fix it in a very timely manner so you know without them I wouldn't be able to do this project and uh yeah Special thanks to them uh so yeah keep up with us follow the hash Engineers on Twitter very smart people um highly recommend them and uh follow hash on Twitter we'll be tweeting more

about this uh in the coming weeks so uh yeah that's it and then the final [Applause] slide have some time for questions thanks for the talk I think the memes are amazing so uh when you when you uh when you ran it against the psychic learn and you saw that the psychic learn on your laptop is like lot more optimal than doing all this cryptography did you

kind of um even before you start working on that did you do so um the question I have is when I look at your performance slide I think the result you're presenting is that the cryptographic way of uh doing the model training takes more time than psychic learn right right so uh but uh did you go deeper into what part of the training is taking the most time and then benchmarking that to the psychic learn because I feel like um when I I'm new to this cryptographic math but I kind of feel like there could be certain aspects with the Jacobian or the inversion of the Matrix where actually the cryptography may not be optimal so it probably like just was

wondering that if you kind of went a little deeper into like what really takes the time uh we haven't really done that um but before we started the project we did Benchmark um training on Psychic learn just to get a sense of like how like how worse can this be cuz we obviously knew that adding the cryptography would make it slower but we didn't have a sense of like how much slower and now we do um but yeah that's actually something that's worthwhile we do have um a section in the report about optimizations um but it's not against the questions that you asked oh yeah I was wondering like

um so um there's like different provs that you could use right um I was wondering like what is like the most performing provs like ZK provs that is compatible for this no um M MPC ml thing so we just used what was available in Noir um I know the Noir team is like working on integrating other provs um but we just use what's available not just in Noir but in cor specifically so kir specifically has like their own um grass 16 prover um and that's what we used oh okay it's like a distributed like NPC gross improver okay for sure yeah away um in terms of

comparing you know this versus like status quo of Psych learn right um so you showed the performance differences in terms of speed were were you able to look into like what the perform like the effectiveness difference was like like the accuracy yeah yeah it was exactly the same oh okay so the quantization stuff you're having to do doesn't actually affect at least for a smaller scale training setup yeah which is actually pretty optimistic um so yeah like I mentioned there only like up from here can only get faster um yeah cool question

I could actually you probably already answered this just now but do you ever see a full 754 implementation actually adding any value to this like in the distant future whenever they're actually F Sor full a floating Point 754 I um it's it's possible yeah um but I think this would be much faster than that okay yeah yeah it's always going to be performance if if it doesn't have any you know loss of accuracy yeah yeah I mean there are NPC algorithms for floating point we just didn't Implement them for for this project um so it's totally possible I would just expect them to be solar okay well thank you

[Applause]