zkSummit6: Beating the Flash Boys with Fully Homomorphic Encryption + ZKPs Ravital Solomon NuCypher

Transcript

[Music] so next up we're going to hear from ravital salman and beating the flash boys with fully homomorphic encryption and ckps so today we'll be looking at front running on exchanges and the title of this talk is beating the flash boys with fully homomorphic encryption and zero knowledge proofs for those of you who don't know flash voice as a reference to a michael lewis book dealing with high frequency trading this is a joint work with gada who was previously at new cipher and is now an assistant professor at uconn so we're going to first look at front

running in traditional markets many financial applications involve buying and selling goods maybe the most popular example is the stock market in an auction potential buyers submit bids and in its simplest form a bid consists of two values n the number of items the buyer wishes to purchase and p the price per item that the buyer is willing to pay in front running some malicious actor sees a concrete transactions details before it's been processed and then reacts before the transaction from this innocent user is executed usually for some sort of financial gain the traditional solution to front running is either sealed bids

in which you hide the bid value itself or dark pools which can be thought of as private exchanges additionally front running is actually illegal for most securities so you can of course threaten people with lawsuits there are a couple different types of front running but for the purpose of this talk we are going to focus on insertion attacks so we assume eve has already front run alice's order meaning that she's seen in order alice is submitted and reacted before alice's order has been finalized so in insertion we really require alice to still want to run

the same function for this to be an insertion attack so an example of this might be ticket scalping where alice wants to buy some concert ticket eve sees this buys the concert ticket first and then sells it back to alice at a higher price thereby making some sort of profit so here eve really needs alice to want to still purchase the concert ticket for this attack to be successful however there are a couple different types of front-running attacks that we will not be concerned with in this talk so what does front-running look like in blockchain well the first thing to note is that front-running is primarily a problem for the account based model not so much

for utxos so if your solution to front running is just to ditch the account based model it's probably no value in listening to the rest of this talk the interesting thing to note is that since we're not in securities markets we don't have the same regulations for front running in blockchain and we cannot threaten people with lawsuits necessarily and additionally dark pools don't really work because we do want some kind of decentralization so we don't want some trusted party to maintain the order book on the right is an image and caption from eskandari at all's sok on front running from previous year at financial crypto that i

highly recommend you can see here that this is in the ethereum network a user submits some order say to buy a thousand shares of some stock along with a gas price the front runner sees the user's order and then submits his own order for the same number of shares but with a higher gas price thereby bribing the miners to work on his order over this innocent user's order so what are potential solutions for front running in blockchain so we have three major categories that solutions could fall into the first of which is trying to enforce some sort of transaction order that this

can be quite tricky and opens up a whole can of worms another potential solution is redesigning the market itself maybe to disincentivize front running but this falls more under economics which is not my specialty and then the final potential solution is trying to offer some sort of privacy that way malicious users can't see the bid in the first place this might fall under creating a private blockchain which could potentially hide the inputs and outputs of transactions and functions it could potentially hide the function itself and even the identity of users or we could have some sort of still

sealed bid auction but it's important to note that we have to have some sort of way to prevent early aborts that way users can't just submit bids that they have no intention of acting on so we're going to look at how can we design a cryptocurrency scheme that offers privacy and protects against front-running attacks blockchain designs offering privacy are definitely not new and there's quite a few previous designs these are some particularly popular and potentially well-known ones the interesting thing to note is that a lot of them use trusted setups or some sort of trusted party

for efficiency which we see as sexy zk and hawk in this case the construction either will use an encryption scheme with zero knowledge proofs or some sort of commitments with zero knowledge proofs they have different issues so while zether does not use any sort of trusted setup or trusted party it has limited functionality sexy on the other hand has quite a bit of functionality offers a large amount of privacy but it's pretty expensive for the user to implement and a trusted setup is needed for each application zk has a similar issue in the sense that there are expensive computations that the user has

to do finally hawk is a very recent work reason it's a very old work in this area and probably one of the first looking at private smart contracts but it requires a trusted manager so our design will not use any sort of trusted setup or trusted party our construction differs from the previous ones in that we are going to use a fully homomorphic encryption scheme along with zero knowledge proofs the main issue with our construction is efficiency especially with regards to space as there is an issue of ciphertex expansion for fhe and finally we're only going to offer input and output privacy for our

solution which suffices for sealed bid auctions and front running there here we just have kind of graphical representation of how the solutions really compare or like buckets you can put the solutions into on the left we see that most of them require some sort of trust assumptions either a trusted setup trusted hardware trusted party and here we've also included ekkaden and arvidtrum we have zether which has limited functionality but no trusted setup and hours which probably has the largest efficiency loss with regards to space but does not have any sort of trusted setup hardware party and has much more functionality than zether

there's no one solution fits all here it really depends on what's most important to you we're going to look at some of the design assumptions and our solution so we are going to build on top of ethereum's design even though our scheme is not immediately compatible with ethereum by that we mean we are going to take some of their design principles we are going to assume that we have an account based model we have a nonce associated with each account some sort of signature scheme we can support smart contracts every operation is associated with some cost and there are fees attached to each transaction at that effect priority

our scheme is going to assume the use of a public account with this key pair unencrypted balance and some nonce but additionally add private accounts in which we have an fhe key set and this fhe key set is going to be used to maintain an encrypted balance that way the balance is hidden from other users we will also have a nonce associated with this account that will be incremented with each transaction the private accounts will be used to support private transactions which will allow us to send currency between public and private accounts we will introduce a locking mechanism to prevent conflicts between concurrency and private operations

and additionally we note that fully homomorphic encryption can be used to create smart contracts providing input output privacy since we can operate on ciphertext so for those of us that don't know or need a refresher in fully homomorphic encryption there are two main ideas behind fully homomorphic encryption the first is that the scheme is additively homomorphic meaning that adding the encryption of a and b together is the same as having added a and b in the plaintext space and having encrypted that and additionally the scheme is multiplicatively homomorphic an interesting thing to note about fully homomorphic encryption

is that it's lattice-based so it's naturally post-quantum fully homomorphic encryption schemes fall in three major categories depending on how it models computation it could be either boolean circuits arithmetic circuits or floating point arithmetic we are going to be using a fully homomorphic encryption scheme using arithmetic circuits and below is just a diagram illustrating how fhe works you feed it some encrypted inputs you can perform computations on these inputs and you get encrypted outputs so what are the challenges with using fhe the number one challenge is that fully

homomorphic encryption is incredibly expensive however this is not huge problem in our scheme because we note that basic transactions between users don't really require the full power of fully homomorphic encryption we only need the simpler ring lwe encryption scheme from braygave additionally for using homomorphic multiplications we can outsource these more expensive computations to the miners to perform for us another issue with fully homomorphic encryption is how do we ensure that these homomorphic computations were even performed correctly without checking it ourself

this will not be a problem in our design since we assume an honest majority of miners another potential issue is that fhe is single key meaning that it only supports computations on ciphertext encrypted under a single key how might we perform operations on inputs coming from different users this will require a bit of ingenuity in our part in design and there may be additional logic needed in smart contracts another problem is that fhe uses lattice-based cryptography lattice-based cryptography and the zero-knowledge proofs for lattice-based cryptography are not very efficient so what zero-knowledge proof can we use

that's relatively efficient and by that we mean producing proofs less than 100 kilobytes in size on average so the interesting thing here is that there is a pretty recent construction called short discrete log proofs and it allows us to prove lattice-based relations using patterson commitments so we'll make use of this scheme in our construction just to recap the cryptographic tools we're going to use is a fully homomorphic encryption scheme using arithmetic circuits this would narrow us down to the bgv and bfb scheme and it's important to note that for simple transactions we don't need the full power of fully homomorphic

encryption we can just rely on the basic ring lwe encryption scheme of regave in terms of zero knowledge proofs we're going to use the short discrete log proofs construction and we can use bullet proofs once we have the patterson commitment we will also use a digital signature scheme but that's not particularly interesting so what might a private transaction in our scheme look like well we have the sender with the private account meaning that he has some fhe key pair and he maintains an encrypted balance and the balance is encrypted with respect to this fhe key pair the receiver has a similar setup he has his own fhe

key pair and his own encrypted balance for a private transaction we want to send some amount of currency from the sender who has a private account to the receiver who also has a private account while hiding the transfer amount and the balances of the users involved so what's going to go into a private transaction well the sender's of course going to need to specify who the recipient is he is going to encrypt the transfer amount under his own key with some randomness he is then going to encrypt the transfer amount under the recipient's key using the same randomness and he's gonna need to provide a couple of proofs the first proof is that these two ciphertexts

c and c prime encrypt the same transfer amount using the same randomness he's going to need to also prove that the transfer amount is greater than zero and he's finally going to need to prove that his remaining balance is also greater than zero assuming everything is correct the sender's balance can be updated to his encrypted balance b minus the transfer amount c and the recipient's balance can be updated to his previous encrypted balance b prime plus this transfer amount c prime so what will a seal bid option look like in our scheme well we're going to first go over how a sealed bid auction would work

the seller is going to post some items for auction and then the buyers will submit sealed bids hiding the number of items they're interested in bidding on and the price per item they're willing to pay and then they will reveal their bids at the end of the auction so previously in zether buyers can only bid on a fixed number of shares assuming they want privacy for their entire bid by this we mean that if the seller posts say a hundred shares for sale the buyers or potential buyers have to bid on 100 shares they don't have an option of bidding on a fewer number of shares our scheme will be different in that we

will allow buyers to bid on a variable number of shares so assuming again that the seller is posted up to 100 shares for sale buyers can bid on anywhere between one two hundred shares while hiding their bid price and the number of shares they're interested in buying we are going to need a zero knowledge proof showing that the buyer has enough currency in their account for the total bid value which can be computed as the encryption of n times the encryption of p we'll also need some sort of zero knowledge proof showing that the encryption of p is in the posted range that the seller has offered we will have a locking mechanism

to prevent early abort and here on the right you can see that the first solution is well the first box with hiding p and like pi for the zero knowledge proof details how the scheme might work if you're only interested on bidding on a fixed number of shares and your scheme only supports a homomorphic edition this is precisely the setup of xether in the middle you can see what would be an alternative construction not supported by zether but supported by zexi and zk where you have some sort of encryption or commitment to both the number

of shares you're interested in buying and the price per share since your scheme does not support homomorphic multiplication you would additionally need to post what the total bid would be and encrypt or commit to that value along with the proof showing that this has been done correctly as in the update has been done correctly and it satisfies certain conditions such as being able to afford the bid and p being within the posted range of the seller our scheme will only require posting the encryption of the number of shares you're interested in buying an encryption of the price per share and simpler zero knowledge proof because

the product of the two ciphertexts encrypting nnp can be computed by the miners so here we're just going to look at a comparison of these two approaches where you're interested in hiding both the number of shares and the price per share so one potential construction and this is roughly the construction used in zk and sexy is the user computing the encryption for np and the encryption of the product n times p the user will need to produce a more complex zero knowledge proof showing that this update has been

done correctly the user here will perform the bulk of the computations and the idea is really to rely on a zero knowledge proof to ensure that updates are done correctly our scheme will not require computing all three of these values users only need to compute the encryption of n and the encryption of p miners then can compute the total value which is the product since our scheme supports homomorphic multiplication and the idea here is to rely on fully homomorphic encryption to perform updates that way we can outsource these more expensive computations to the miners to do no one approach is i would say superior to the other it really depends on

what you're looking for and whether or not you're really interested in hiding the price per share one reason you might be interested in hiding both the number of items and the price per share is if you're bidding on a very large number of items and your bid could potentially affect the market itself otherwise you might not need to even worry about hiding the number of shares so just some numbers to end on for the basic ring lwe encryption scheme which is used for all the transactions you can see that encryption and decryption are pretty fast and it's on a very reasonable machine for the short discrete log proofs construction the

performance is dependent on the elliptic curve chosen we just do an application of verifiable encryption here and the proof sizes are approximately 1.3 kilobytes and you can see that for six threads the prover time is under 10 seconds and the verifier times around five seconds for curve two five five one nine so we don't have numbers fully for fhe yet which would be interesting to see to get a better sense of how competitive our scheme is and that's it thank you for listening so thank you for this talk and thanks for those who've left some questions i want to recommend

that if anyone has any questions to put them in the chat now so that we can actually talk about habitel's presentation um i know that like one of the questions i had right off the bat you showed the three different categories of like ways to actually prevent from front running do you think given the work you've done that private like using privacy is the strongest or do you think it's just a way i don't know if it's the strongest solution specifically for front running but i think private blockchains offer so many advantages if you can additionally solve front fronting right cool mccara had a question here

what does the implementation of this construction look like what components are off chain and what components are on chain that question is a bit difficult to answer since we haven't fully implemented it much less even fully benchmarked the scheme that's something in progress so hopefully i'll have news to share in a month or two on that but not right now i'm curious like where did the work come from like what inspired it what was the why like especially in the context of new ciphers specifically like what inspired it within that work i think it was our interest in fully homomorphic encryption and originally i was supposed to look more at like

proofs of correctness for fully homomorphic encryption but i instead became interested in the private smart contract space and then i noticed that like all of them not maybe not all of them but they mostly rely on like additively homomorphic encryption so it was just kind of a what if like could this be done oh oh no am i back yeah okay i cut um i i'm trying to think if i had anything else here so it sounds like this was more to do with like using out using fhe does it have like does the new cypher system as it

exists right now will it do you think it'll tie together do you think it'll be used in tandem somehow i don't think there's any way to implement the work as it is here with like the new cypher network it would really require a different blockchain and a different construction entirely do you do you plan on implementing it though anyway like is this something that you're working on that's really hard to like answer just because we don't have the numbers so like trying to compare it against like sexy is a question i saw like replacing sexy with like the untrusted universal setup understanding like how the numbers compare does this make sense that's necessary first before understanding whether we

should put it into production or deploy it got it and does that also uh refer to dara's question here do you have an order of magnitude estimate for the performance i guess you don't yet yeah i think the the most concerning parts of course like the fhe and the ciphertext expansion i don't think the zero knowledge proofs are too bad i mean i guess it depends what it means by too bad we're talking about like very efficient zero knowledge proofs and you know this workshop so people want like single-digit kilobytes which we may or may not have but we're definitely under 100 kilobytes for proofs i didn't actually because i was listening to your talk on a different screen i didn't actually hear that much about the type of zero-knowledge proof that you're using

what so since fhe uses lattices there's a little bit of a challenge in finding a good proof system to prove things about lattice-based relations so we used a paper called short discrete log proofs and it was from public key cryptography 19 and it allows you to use patterson commitments to prove lattice-based relations so that's the main proof system we relied on but once you have those patterson commitments you can use standard bulletproofs to prove additional relations cool well i don't know if there's any other questions i'm not seeing anything i'm going to assume that everyone understands i guess my the last question

that i have is where can people find out more where can they maybe get involved that is not yet done where the paper has just been submitted to a conference so okay about and then we'll probably post it like on eprint and then also put up a link on you cipher's website cool so we have to we we should look out for a link then yes i'll look up her paper cool very good thanks everybody and we'll see you the next the next talk will be in i think 30 minutes and it's going to be the lightning talks on this stage see you soon