ZK10: Authenticating web data via Interactive zero-knowledge proofs - Xiang Xie

Transcript

[Music] yeah my Sean from pabs and yeah it's Jo to work with Kong sh and and yeah we have PL of time so feel free to interact me for any questions okay so let's be casual so yeah uh the the title of this presentation is about uh you know authenticating web data via what new primitive called interactive Bruce so here is a background so uh for example there is a approver in the server or you can see the pro as a client so uh the client can access uh data from the server using you know a secret and to to

to query the server and get the response back so here's question so can we do the following things that the prover convinces a verifier that this m or this incubated m is actually retrieved from the server without any modifications on the server side so if if we could allow the server to change then he just assign the message but in a lot of cases the server do not need to sign the message for example you just retrieve your you like uh your balance from your uh uh back account there's no sign there's a no sign nature so generally can the approver convince the verify approv the

verify that okay this message is actually from the server so a very concrete example is that can I prove to someone else that I have enough eth in combase so just using cryptography not you know uh any other trust so this is the background that we are trying to you know to solve um uh in this scenario we are focusing on this you know transport layer security what callls protocol so protoc is is a standard web have two protocal uh you know uh it offers you know authenticity and confidentiality so why we focusing on TS because you know all the web data are transferred you

know using this protocol for example like htps so everything is on https so it's so gener so General that we can you know to deploy of of aggm to a lot of use cases so we are focusing on this TS so t 1.2 and T 1.3 so this is the the background okay so let's go uh let bit deep into what TS is doing so basically it has two like phrases two phrases phases so first one is handshake so means that the client and server negotiate uh this you know uh a common key so that that that's using

you know a very standard all we call called DH and K uh change something like that uh the client send a random to server the server send him back random together with a you know a g to the X and the certificate and the signature of them then send the Cent send back g g to the Y so the the common key is like G to the X to the Y and has or P run function of the transaction so you in this way the client and the server can negotiate uh with output which is a common py uh for the client and server and is used for the next record phase so record phase is that these two guys using this

common key to uh send incent messages so the client using K KC to in the message and send it to the server so decrypt with KC and the server KS to send the in incp message to the client and the Cent decrypt so so that's that's the rec C face so it's very standard and yeah it's it's used everywhere uh especially when you're using brows using your browsers so it's it's everywhere so this is the the the the a small background of TS and uh yeah let's go back to the problem so we're trying to solve the problem so

there is a first trial uh yeah a very no trivial solution is that given this you know transcript can I just use SNS or the proes to prove that okay I know the suround I know the secret I know the message M that generates generate all these transcripts can do this I think I think this is the is the a very first trial of of previous paper to trying to solve this but unfortunately this cannot be done just using SS uh the reason is is that here is the thing so yeah provs can use valid R secret and you know this valid message

to generate you know a proof but there is one thing because uh the client or the approver he knows all the symmetric key and he can just encrypt another random message M Prim and replace the original s text with this new s text and then he can just prove it and yes he can prove it because he knows all the secret key and he can just encrypt this random M Prime visiting secret key and all this transcript is valid but the problem here is that he cannot make sure that this message is from the server he can just generate it but you cannot make sure or you cannot convince the verifier that

this message is from the server it's valid but it's probably not from the server so that's the key point so yeah and the first try uh I think the first try is fails and uh and uh in a in a in a previous paper that c call is decentralized Oracle proposed by John and other other other cryptographers in like in 2020 yeah they came up a solution so the solution is like this so instead of you know the prover and the server is a a channel by themselves so the verifier

is participating this handshake phase so it's called a thre party computation handshake or three PC handshake which means that uh after this process the server can get the session key but the approver of the client only get half of the session key and the other half is given to the verifier which means that the approver and the verifier together establish a Channel with the server but the Prov himself cannot access to this ACC this this channel so uh in this case if the approver want to send a message to the server he has to run a

two-party computation protocol NPC protocol to generate this kind of s text and then send to him so when the server send back this C C2 okay the Prov just forward this oh sorry the just forward this message to the verifier in this case the verifier can ensure that this C2 uh this C2 is actually from the server it's not generated by the pr himself so it's something like a commitment or is is somehow Sol the problem of the first trial solution which is to make sure that everything sent back to the server is actually from the is actually from

the server because the verifier uh know controls half control the the the the the the channel and the approver cannot you know manipulate this channel so this the this is the uh basic idea of this day Cod solution oh yeah at the end at end at the end uh the verifier we you know send back the his half to the approver because okay and now I already know that C2 is from the from the server so I don't need to control the the the the channel uh I do not need to control the channel so he just send back the half of the session key and then the Prov can decrypt everything but now verify now

knows that C2 is actually from the server so next step is that in this case so the verify knows KV C1 C2 and the okay Pro need to prove that okay okay uh you just not with that I know KP secret M that generate these steps so yeah this this kind of uh uh solution Works actually it works because you know now verifier can make sure that all the message is from the server and the the appr also proved that oh I own this kind of secret I know this kind of message so this is good this is good however there's one thing that's you

know one drawback of this solution which means um one thing is a day paper has to use you know uh a Mist secure two-piece protocol which is very heavy so they're using something like something called authenticated gar circuit so it's it's very costly uh it's like more than 10 times slower than this you know semi Hest converts and there one other thing is that you need SNS so TS has a lot of ciphers like sha like as like multiplications over this kind of you know G field so the pro has to uh use use SN to prove uh the relations under this kind

of you know un unfriendly ciphers which is uh very costly especially for in terms of you know proven time in terms of you know memory consumption so it's very it's it's it's very heavy and as as far as I know um the D Cod uh you know the the de solution is now is is not you know deployed right now and there only a a paper published so so uh our goal is that can we find another way to you know uh you know to uh uh overcome all these uh uh uh barriers so yeah our paper actually yeah propos a new paradigm we called garble

them proof so basically so we can replace this also gar circuit with semon gas then we have 10 times Improvement and then we don't need to use stick knocks because in the first step we already have interaction so you have to you know the prover and verifier have to have has have to do interactions so we can use this kind of Interac knowledge proof and this kind of i k is quite faster than SN so yeah but yeah I I only show you the ideas here but you know the details is very complicated and it's not just a very simple replacement so especially you have to using R to put

kind of you know key duration functions which is a bunch of sh but yeah I think is very efficient to prove sh you know uh statements and yeah as a result the Improvement is something like that like this so actually optimize this kind of kdf to reduce the uh anase you know from you know like 300,000 to like three uh 7 700,000 to like 300,000 which is about uh 3 times Improvement and the the computation uh is almost 10 times faster and uh uh in this case we do not measure

in the SN part if we want to uh measure in the SN part uh we are it could be faster so the communication size is like uh 14 times low lower and the memory yeah our memory consuming is it's very low it's very small so it's like just 100 megabytes so it's it's very low so as a result our improvements allow our product to be deployed withing browsing tensions actually we already developed a product that put everything in the call extension and yeah it's also is is already available right now okay that's the the main uh result of the paper so uh in next SL I will uh

go a little bit you know uh details of of what we have done yeah the first thing is scar I think it's a very it's a very uh beautiful idea or beautiful solution to you know to to S this two PC problems and a lot of cryptographers focus on this kind of area and there's lot of you know amazing optimizations to reduce the uh computation cost and communication cost so here I'm going to show you the basic idea of this gabber circuit so the motivation of gabber circuit is that there's two person what we call gobl or evaluator each one has a private input and they want to uh uh collaboratively

to uh compu the function f XY and get the result so this is stand two piec problem so yes here I I give you example how G works so in in this case uh the uh gabra has two bits input and uh okay evalate has two base input so now they want to uh compete this kind of simple circuit and two anate and one X orate so yeah the yellow wires are for gab and the blue W for evaluate so in this in this case so the gobler first take this kind of

circuit he choose uh two random labels for each wire so for example it's a b c d e f g so for each wire uh each wire and is kind of random random bits is kind of random 128 bits and in this case for each kind of for each gate he do this kind of gobling which we call is G gble gate so for for example let uh for this Nate so the goer using the input wires so he he's using a two key incubation scem using this kind of

two uh labels to encrypt the output label so for example for this gate there is an encryption using a B to encrypt e so the way uh gab uh gab disate is that the index of e is actually the index is actually the end of index A and B so for example this is endgate so uh only the last uh uh you know inici uh is using E1 because one and one is one z z z z and Z is z so one and one is one so this kind of Garber circuit Garber gate is you know corresponding to this kind of uh uh

specific gate so he can do all this gate and then he send this gar circuit sorry he send this kind of G circuit to the evaluate together with you know this kind of output gate out of the label g0 G1 which uh represent zero bit and one bit and together he also send the input label of Gab because if his his input is zero gabra send a zero his the other one is one then he send C1 to the evaluator so there are some kind of label missing so

it's uh B and D so there is a very standard way called the oper transfer so the eight you this kind of bits his input bits at selected bits and he can select the label B and label D according to his input for example now get B1 and D1 and the governor cannot figure out what kind of Labor he's choosing and also the evaluator cannot know other you know B b0 and B d0 so in this case the G the variator now gets a z B1 C1 D1 so for each gate he do the

decription so for example in the first gate uh the evalate can get can decrypt the third C text to get you know e z and then get F1 so using e0 and F1 to decrep the the last gate to get G1 okay G1 stands for one so for B one so he can get the he can get the the output of all the gble circuit so this is a very basic idea of back to like uh 1986 is is is quite ineff it's not efficient so after 40 years it's bling fast so um as there is a very nice property

of garit so you know the security of uh security GC is highly asymmetric means that it's Ure against malicious evaluators yes it's it's it's very it's very nice property but it it's only secure against a semi honest governers so because the governers can you knowjust the Govern a different function f Prime to get information of the eval so this is uh we actually using this kind of asymmetric property of Gab circuit which is which is uh very uh good for us to do optimizations and you know after 40 years now GC is pleasing fast we're using a lot of you know optimizations like ASN I instructions

like using this kind of set of half Gates three halves so in current implementations we can govern like uh 20 million and Gates per second and all these XR gates are for free so that's that's bre fast and I think this is very fast okay so far so good it's about Cate yeah uh yeah I think now is a new uh a new primitive called interactive knowledge proof so is kind of very new to the community I think and uh actually

we're using this kind of V yeah I have to I I have to uh know that uh it's interactive and we cannot use FIA to make it non interactive because is a a private con it's not a public con so in this kind of uh you know uh uh protocol so the verifier we have a global secret C data so here I keep this kind of secret data and um uh these two parties we are using uh a tool called The V Vector obious uh linear evaluation yeah it's kind of a new uh you know particle new to to gener massive types A topos of this random k i

m i b and safies this you know K IAL Mi I plus bi * Delta so k mi I here are you know bits and B is just one bit so it's kind of information theoretical Mac so it's widely used in this is system and U yeah I'm not going to show how V gener this kind of toes is is very complicated but I just show you that yeah we can do that and then we can do it very very efficiently we can like do to generate like uh 10 million typos in just one minute in just one second sorry we can generate

very efficient fast very very very efficient and U yeah so given this kind of TPS we can do Z proof yeah it's very it's very interesting and uh this kind of you know random TS enable us to build very efficient interact Z proofs and you know all these operations here is very cheap it's not like you know SN has to uh you know to to handle fft to handle you know MSM which is very heavy and in ik K everything is very cheap it's just a bits it's just O is just yeah just x o and that's there there uh and you can speed you can can speed the lab using you know uh

instructions like as uh instructions or other kind of you know SSC instructions it's very fast so yeah you know here is a very simple trick that given this kind of Ki mibi for this all kind of random things and uh uh witness W and uh we we uh decompose it as bit so the Prov just send what we call the difference between a wi and bi send these kind of things to verifier and then they get here get a new Ki and this kind of Ki and Mi wi also satisfy this

kind of uh relation this is what we call a Mac a Mac of the winess of the back a Mac of the of the input so using this kind of uh uh very simple way we can handle you know it can prove you know circuit satisfiability for very large circuit and yeah the key point so if you're focusing on ADD uh add gate is very it can be done locally because it's linear everything's linear you can you can you can handle this kind of adgates for free so the major part here is how you handle this uh multiplication gate

so supposed we have you know yeah suppos we have these uh two kind of uh three kind of typos here B1 B2 and B3 you have to prove that B1 equals B2 Prim a times spe2 so yeah here's here's here's a trick that we call yeah I know this is very complicated just you know you just yeah trust me that you can just use this kind computation you can get the result on Bal a0 * A1 time plus A1 * Delta and it can uh these two uh these three typos

can be rewrite in a new way as long as B3 equals B1 * B2 as long as this kind of terms is cancelled so if it's cancelled then uh uh means that uh I'm proving a multiplication gate and uh get the result in this kind of uh uh linear linear relation which is very useful fast proof so what we have to done is to to prove that uh this kind of s topos satisfies this property so this property is very easy to check so how to check but just using you know check with mask then open so we just mask everything and then open these stuffs because we are

masking a z and A1 so so this message is is totally random and we just send it back to verifier and the verifier just check this linear uh equation uh H and which is very fast and then in this way we can um efficiently uh prove to the verifier that these two wires these three wires satisfy this kind of multiplication uh relation which is very fast and also uh as we know uh in a circuit there a lot of multiplication gate so there is s way called you know using random India compilation we can check a lot of multiplication gate just uh in one shot

so just using this kind of you know Rand combination it's very standard way to prove multiple you know multiplication Gates and this is very fast okay so uh I going to show you some uh uh numbers so the reason we say that ik is buing fast is that from our experiment we can prove one trillion anat using just uh $2 which is quite fast and uh uh we can just we can prove you know one trillion M Gates over uh 41 bit field we just using $2.5 us so this is kind of our you

know uh Benchmark on different kind of machine and the Machine is very you know uh it's not powerful it's a very un powerful machine just two wips and one gbyte memory so it's very it's very cheap it's quite cheap and of course in the in a has to you know be are interactive so we has to consider uh this network boundaries so yeah we are using some kind of proper boundaries to do the oper uh to do the experiments and but it's still very fast quite fast and yes we can do a lot of things using is K so in a paper yes last year so we can actually prove repe the

computations for example we can prove you know uh uh in a batching way so I Prov to you that uh for example I Pro proed to you that uh the input and output satisfies a a batch of you know uh relations and in this way we can further reduce the communication size say I can Pro one gate by using just one uh .006 for field Elements which is quite uh low and yeah we can do Z ml I know yeah now people in the community doing Z ml using snugs yeah I know that and the the the benefit using s is that uh you

can uh the result can be verified on CH because it's not intractive if um is not required to be non interactive then we can use is to proof and the power the power of Isa to prove machine learning model is much more powerful than TN actually a paper uh right yes last year is that we can you know Pro very complicated uh models like rest net one one1 means there's over 100 you know layers of the of the comp of the of network and we can do it in less than like 20 minutes and actually the the

benefit of using isk is that um the memory consumption is not a Boton neck we you can just prove uh as long as you want you just prove as long as you want and can you can can Als at the end you finished the proof but yeah uh there's there's no memory limit here and also um new paper this year is just can detecting bias in federal learning using ik and just to improve like 10 times faster and even more so actually we found that igk uh yeah is quite fast and it had a lot of very exciting and interesting applications

andn cannot do but yeah there's uh you know this theage of case that he has to be interactive it has to be interactive yeah that's the that's only you know this Dage here okay let's get back to our problem so yeah we're trying to you know to do this kind of uh proof system so now using our new protocol so it's kind of like this so first of all yeah it's also a two-piece protocol but we're just using Semitic C circuit which is like 10 times faster than malicious secure Gaba circuit yeah it's 10 times faster just faster and then yeah when send message and them using semon g

c and yeah these kind of things is very similar to to to to Deco and as the end we now using i k to proof we are not using know to prove this this stuff because Isaac is very compatible with these booing circuits he can do it very fast so us is has to Pro that like the kdf is computed correctly and uh I know a lot of things I know this kind of winess to generate this you know uh data so yeah this kind of uh just that simple but yeah I I explain it in a simple way but you know if you want to look at our paper is like 60 pages and is is it's very complicated because we spend a lot

you know spend a lot of time to to handle these Corner cases because when we using this kind of new idea or new uh protocol we has to handle a lot of con cases especially in the security proof which is very you know is very subtle so that's our performance comparing to Deco so yeah we do a lot of uh you know uh uh experiments so basically we are like 10 times faster than theyo in in different scenarios yeah and um we also show that our protocol is global scale which means uh we conduct a a series of experiments by

deploying uh the verifier in like 18 cities all over the world so yeah let me explain a little bit so so we actually uh uh approve uh you know coinbase apis and TW apis so the the yellow one is coin based the green one is co is is Twitter so and the time um out the time outside uh the time form is is online time total time which means that we can separate the whole processor into off time and on time which means that uh uh we can do off time before the you know the proof uh starts which is you can be you can do it

any time and um and our appr a verifier so our verifier is deployed in in San Francisco and uh yeah you can show that the the worst case is probably here South Africa and they takes like 10 10 seconds to prove but if but there is a very natural way to optimize it is just by deploying the the verifier very close to this approver because now uh latency uh Network latency and the network uh uh band is the major uh bck but yeah we can still accept this kind of performance because uh it's it's it's also very fast

it's also still uh I know um satisfies a lot of uh requirements in real applications yeah yeah actually as I said before I put everything into a Chrome extension that's our product so in our product is yeah it's called extension our product you can actually access to different kind of centralized exchange and you can prove to P that uh how many assets you are holding in a centralized exchange for example how many uh that the amount of assets are holding in in commas and you can prove to other guys that what

kind of token you're holding yeah you can take it as you know um a private Oracle that uh I can prove off gen data to a sub party and this kind of data can be you know uh transferred to onchain and for onchain applications so yeah that there's one trick is that when we move to uh coin tensions uh you know the power of con extension is much more less than you know a laptop because in in the Chrome we cannot use this uh uh you know as and I instructions which yeah is like it's like 10 times more more slower but yes still we can do the proof in in less

than 10 seconds to to for for all this kind of proof and uh I think this is the first product that can uh uh integrate uh you know this kind of uh privacy preserving all things into CHR exensions and next step is to move it to you know mobile and which will be much FAS because we can use you know ASI and other stuffs to speed up so yeah this is the this is what we have done uh uh uh in a product yeah okay that's basically uh my presentation and yeah our paper is now available and you can

also download our extensions and uh yeah you can yeah yeah yeah add our uh twitterers yeah you happy to you know to talk about anything at details of of a product or protocols yeah that's that's that's all yeah thank you so any questions yeah any questions gu yeah here is I'm not a tech uh so I um help I digest all this information with our tech department but what would you choose to take this route instead of this n route and you know usual that everyone is kind of building up is it in

terms of just speed or just what is the like yeah that's very good question so so basically yeah we are thinking about the thing this way so uh our mission is actually we want to bring you know web two data to to know to to a Smart contract so we want to bring every internet data to Smart contract so there is um a gap now so currently smart contract can access you know uh you know current data or historical onchain data or maybe public data using Oracle but there's one thing missing is the Smart contract cannot access you know off CH prate data right now this is a big Miss

uh you know big gap between know especially if you want to make smallart contract more smarter much more smarter to handle these kind of data driven applications there is that we have to to find a way to you know to bring all this internet private data to Smart contract this is our motivation and in this case yeah I I I think SN can yeah theoretically SN can do that but it's not fast because in this case um there's a lot of end users it's not it's not like layer 2 you can uh you know deploy a very powerful machine to generate proof no in this case there is no machine you just have a laptop you just have a CO stations I'm a user and just I

can only terate like 10 seconds yeah if it's one minute okay down I don't want to do anything so performance now is uh uh performance now matters here so we are choosing this kind of new algorithm or new you know Primitives to uh make good uh you know user experience to enable you know privacy preserving applications using thek yeah something like that thank you yeah coin yeah who own the DAT no not me not me reading data the client they use Arena data in coin for example any other

company has structur this dat they maybe don't like that this data is going to thir part oh very good question so yeah in this case it's maybe not too sensitive but in other use cases I can imagine that companies with companies don't want to have their data stol away or by users because model kind of yeah but yeah this is a good question but there is you have to imagine there is a uh imagine that there is no such question there is no such solution so there has to be a way that I have have a way to access my data because yeah this is my balance account you you have to show me the balance of of my background back uh bank account right so there is

that has to W be a way and the you know most common ways that I can access my data using webs you know uh so if you're using uh browsers then you're using htps if I using https then we can use this kind of protocol so yeah but yeah I I think in the future it's my right to access my data right this put dat to some company the company let's say enhance the data by using whatever algorithm they have then they display you this enhan dat oh well that hand to this data or not I think coinbase has a very interesting terms of condition for that

data different from other exchanges so I think that they make Yes actually yeah actually all these kind of centralized exchange already off you know apis for you to access your data right comp May easy but if you're thinking about Facebook or but yeah but yeah if you company your data company you has to provide a way for you to access you know something right yeah you have a passport and you have a username to access kind of kind of data Maybe it belongs to you maybe it's just public data but there is there is a way to do that right otherwise there's no business for this kind of data company right so that's that has to

be a way for you for their you know know business model for their you know commercial uh you know motivations for to do that so um yeah we assume that there is there has to be a way you have you can access at least part of your own data yeah this kind of assumption but we think that this kind of assumption is very valid yeah thank you yeah um I'm wondering why a browser extension instead of aname is there something that needs to be hidden from like certain processes or just made sense to like was there reason for op for extension instead of was there reason for opting for a

browser extension instead of iame uh no yeah using con extension is that you know in in the R Street Community everybody is very you know comfortable with con stations but yeah it's not the best choice actually if the users want to use you know a mobile phone then we can put everything to a mobile phone and it could be much faster because yeah we has to you know you know to kind of satisfy the requirements of the clients now in the community so everybody using know using car extensions right yeah that's that's the reason we are using this extension here got it yeah okay thank

you okay that's all thank you