'Beating the Flash Boys with Fully Homomorphic Encryption' - Ravital Solomon

so we have new cypher ravital coming in and she will be talking about how fully homo homomorphic encryption can help handle front running on exchanges so thank you so much for joining us revital um feel free to take over with your talk great one second so we'll be looking at front running on exchanges as we just heard this was a joint work with gada so to motivate the problem what does front running look like in traditional markets well a lot of financial applications involve buying and selling goods the example you might already be familiar with is the stock market in auctions potential buyers submit their bids where a bid consists of at least two pieces of information you need to know the number of items someone's interested in purchasing and the price per item they're willing to pay so what is front running front running consists of some malicious actor seeing a transaction's details and this malicious actor reacts before this transaction is executed so how is front running dealt with in traditional markets well there's dark pools which you can think of as private exchanges there's sealed bids which simply hide the bid and more generally front running is actually illegal for most securities so you can threaten people with legal action what are the different types of front running well to start we're going to imagine there's alice which is some innocent user submitting some order and there's eve the attacker for the purpose of this talk we're going to be primarily interested in a type of attack called insertion so in an insertion attack alice needs to still run the original function for this attack to be successful so an example might be ticket scalping where alice is interested in buying some concert ticket eve sees this goes and buys the ticket first and then sells it back to alice for a profit so in this case we really need alice to still want the concert ticket for the attack to be successful and for eve to have gotten some money off of this there are other types of front-running attacks such as displacement attacks and suppression attacks but we won't be looking at those today so what does front running look like on blockchain well we're going to look at the image on the right hand side so you can imagine some user submits some transaction and they are interested in buying we'll just say a thousand shares of something they have some gas price associated with their transaction a front runner who in this case is a full node in the network so they can see transactions before they're confirmed notices this order and then submits a new order to buy the same amount of shares but with a higher gas price thereby bribing the miners to prioritize his transaction over the initial transaction so as you might guess this is more of a problem in the account based bottle so that's what we'll be focusing on why don't the traditional solutions work for front running in blockchain well first of all these aren't necessarily securities so we don't necessarily have the same regulations as securities markets and additionally you might be interested in decentralized solutions where you don't want some trusted party maintaining the order book what are the different categories of solutions to this problem then if we're looking at blockchain there are three major categories and these categories are taken from an sok from eskendari at all about front running the first you might look at is could you enforce order in some way for these transactions but this introduces some other problems and doesn't necessarily solve front running in alternative category of solution you could look at is redesigning the entire market itself so maybe you could try economically disincentivizing front running the final category of solution could be adding privacy that way these malicious users can't even see the bid in the first place so we can look at private blockchains where we might be interested in hiding the inputs and outputs we might be interested in hiding the functions themselves and we might be even interested in hiding the identity of the users involved additionally we can also look at sealed bid options but it's important to note that if you're taking this approach you need some way to prevent early aborts and by that i mean some way to prevent people from submitting sealed bids that they have no intention of acting on so since i'm a cryptographer we're going to look at category number three and that is can we design some cryptocurrency scheme that offers privacy at the very least input output privacy and maybe this scheme can also protect against front-running attacks there are some designs out there that offer privacy the main four we're going to look at just because all of them use zero knowledge proofs are zether zexi zk and hawk all of them offer at the very least input output privacy which is necessary for this problem they have various issues none of them are perfect so starting with zether it has very limited functionality in the sense that you cannot get privacy for any function privacy is limited to functions that can be expressed via addition sexy and zk have similar issues they use trusted setups for the zero knowledge proof but arguably you're not committed to using zero knowledge proofs with trusted setups these can be replaced with transparent zero knowledge proofs however these constructions regardless are very expensive for the user we will look at that in a little bit more detail in a second and finally hawk has a semi-trusted manager so not something we would probably want in this kind of solution we are proposing a new design that offers privacy our design is called smart fhe it will have no trusted setups no trusted parties involved it's going to differ in construction from the previous four and that it will use zero knowledge proofs but instead of using partially homomorphic encryption or commitments it is going to use fully homomorphic encryption it will offer input output privacy as needed and the primary issue with our construction is also that it's expensive but it's expensive in a different way the primary problem is space particularly ciphertext growth with fully homomorphic encryption so what is fully homomorphic encryption for those people who don't know you can think of it as a special type of public key encryption scheme that offers two additional properties namely that it's additively homomorphic so that adding a and b in the plaintext space and then encrypting that is the same as having encrypted a and b first and adding that in a ciphertext space a similar relation will hold for multiplication something special about fully homomorphic encryption is that it uses lattice-based cryptography which is different from all the other constructions and another thing to note is that there are three different categories of philly homomorphic encryption depending on how they model computation you have boolean you have arithmetic and you have floating point and we will be looking at arithmetic on the bottom is just a diagram kind of illustrating how fhe works you have some encrypted inputs you can perform computation directly on these encrypted inputs and get encrypted outputs so why might we want to use fhe let's take a step back and kind of look at the different approaches in private smart contracts and private computation for blockchain so on the left is an illustration of how zk and sexy work more generally the idea is that the user wants to run some function and they want privacy input output privacy so what are they going to do they are going to run the function on the plain text inputs and they're going to get some plain text outputs but they obviously don't want to share this plain text information with everyone else on the network so what they're going to do is they're going to encrypt their inputs encrypt their outputs and they need to produce zero knowledge proof showing that this offline computation that they did on their own was done correctly what do the miners do in this kind of paradigm well they just show up and they check the zero knowledge proof the zero knowledge proof is good everything's fine so in this case you can imagine the user's doing a lot of work it is lightweight in the sense that all of this works being done sort of offline except for the zero knowledge proof part being produced so it prioritizes space our approach is going to differ in that we want the miners to do a bit more work and we don't want the user to have to do quite so much work to do private computation so instead the user is going to provide encrypted inputs these inputs will be encrypted with respect to a fully homomorphic encryption scheme and they need to provide some zero-knowledge proof showing that some conditions dependent on the application have been satisfied for their encrypted inputs then the miner comes along they're going to check that the zero knowledge proof is good if so great they can run a function directly on these encrypted inputs thanks to fhe so kind of balancing the work between the users and the miners and in some sense you can think of it as prioritizing the user's time that all sounds great but there are quite a few challenges with using fully homomorphic encryption especially in the blockchain settings so we're gonna look at the three main challenges the first challenge is that fhe is very expensive this is sort of true the time complexity actually isn't that bad and we have some numbers that we ran to show that there is a bigger challenge with ciphertex growth in the sense that the ciphertext grow quite quickly and they're quite large for fhe but there are other avenues that you can explore to potentially solve this problem challenge number two is that unlike the other constructions fhe uses lattice-based cryptography we need a zero-knowledge proof that works with lattice-based relations and allows us to prove lattice-based relations but a lot of the lattice-based zero-knowledge proofs themselves are very expensive so we need to ask what kind of efficient zero-knowledge proof can we use thankfully there's a pretty good construction short discrete log proofs construction that uses patterson commitments and produces decent sized zero-knowledge proofs for lattice-based relations and finally three so if you're familiar with fully homomorphic encryption you probably already know that you can only perform computations on ciphertext encrypted under the same key how are we going to perform operations on inputs especially encrypted inputs that belong to different users and therefore are encrypted under different keys this is going to require some additional logic in the smart contract but it's certainly possible there is a different variant of fully homomorphic encryption called multi-key fully homomorphic encryption and it allows for truly arbitrary computation on inputs that are encrypted with respect to different users and different keys but we're not going to look at this for now so what are the cryptographic tools we'll need for the smart fhe construction we need a fully homomorphic encryption scheme as mentioned earlier we want one using arithmetic circuits this kind of narrows us down to bgv and bfb for basic transactions we don't need the full power of fully homomorphic encryption you only need additive homomorphisms we'll need a zero-knowledge proof that helps us prove lattice relations we're going to use the short discrete logs proof construction and then additionally once we have the patterson commitment we can use bulletproofs for other relations and finally we'll need a digital signatu digital signature scheme or some way of signing transactions but that's not a problem just a quick look at fhe numbers we ran some benchmarks of the bfb scheme from microsoft seal we ran it on pretty basic machine we have the smallest and largest parameters that are supported by default for bfb and you can see on the right that like the numbers are pretty good the only thing that's a bit expensive is key generation for the largest parameters but everything else is like under a second there is like as we noted before an issue with ciphertex size so just getting a sense of how do the ciphertext grow and how large are they after you perform a homomorphic multiplication operation for the smallest default parameter supported by seals bfb it's about 13 kilobytes so decently large these are some numbers to give you an idea of the short discrete logs proof construction the performance is dependent on the elliptic curve you choose we did curve two five five one nine the proof size is pretty small less than one and a half kilobyte and using multiple threads it's decently fast so how is our construction actually going to work well we're going to look on building on ethereum's model so the idea is that we're going to build on top of a smart contract enabled cryptocurrency like ethereum that supports public transactions and public operations so we're going to have an account based model we're going to imagine that there is still signature scheme associated with the public account you still have a nonce that's incremented with each transaction and you support smart contracts every operation is still associated with some cost and there are fees attached to each transaction that affect the priority what new is going to be added to this construction well in addition to this public account we're going to imagine we now also have a private account and the private account has an fhe key set associated with it and this fhe key set is going to be used to encrypt the balance that way a user maintains an encrypted or secret balance similar to the public account we also need a nonce that is unique to the private account and will be incremented with each transaction and the idea is that we're going to use these private accounts to perform private transactions and private smart contracts there are some issues when we're looking at accounts with privacy and concurrency so we're going to introduce some sort of locking mechanism to prevent conflicts so what does a private transaction look like in smart fhe well we have the sender and receiver both of them have their own fully homomorphic encryption key pairs they both have their own encrypted balances imagine the senders as b and the receivers as b prime for a private transaction our goal at the minimum is to hide the transfer amount and the balances of the users involved so what would go into a private transaction we need to know who the recipient is we're going to encrypt the amount we're interested in sending under the sender and receivers public keys with respect to the same randomness so we'll need to publish the randomness and then we need some proofs we need a proof that these two ciphertexts actually encrypt the same transfer amount and they use the same randomness we need a proof that we've sent a non-zero transfer amount to somebody we're not sending somebody a negative amount of currency and we need a proof that the sender actually has enough money or currency in their account to perform this transaction and as we stated earlier you don't need the full power of fully homomorphic encryption to actually do this you can simply use the additively homomorphic aspects to encrypt the senders and receivers balance because they're addition operations so again more generally how does smart fhe work the idea is that the user provides some inputs if the inputs are public or unencrypted a smart contract just proceeds in the same way as it normally would or a transaction proceeds in the normal way as it might in ethereum if the inputs are instead encrypted and in this case encrypted with respect fully homomorphic encryption the user probably needs to provide some sort of zero knowledge proof proving some relations on these encrypted inputs that are application dependent the miners can come along they then check the zero knowledge proof and if everything's good they can perform a computation directly on the user's encrypted inputs thanks to fhe back to our original problem what is going to happen for sealed bid auctions so the idea is that a seller will post some items for auction say that the seller has up to 100 items to sell a potential buyer comes along and the idea is that the buyer can bid on a variable number of shares so anywhere between one to 100 shares one to 100 items that the seller has and they will submit a sealed bid and then reveal their bid at the end of the auction this isn't anything new sealed bid options have been around for a while so in this case we'll need a zero knowledge proof showing that buyers have enough currency in their account for the total bid value and possibly depending on how you want to write this you could also have conditions that show the number of items or within the posted range the prices within some specific range as mentioned earlier we're going to need a locking mechanism to prevent parties from submitting bids and then just running away with no intention on actually acting on them and on the right here you can just kind of see a diagram showing what a bid consists of as we stated earlier a number of shares price per share and different ways of bidding whether you're bidding on a fixed number of shares in which case you need fewer pieces of information or if you're interested in bidding on a variable number of shares and how that might work depending on if you have fully homomorphic encryption or not so back to the kind of comparison of approaches we were looking at previously the zero knowledge proof-based approach taken by zk and sexy for example and then the fully homomorphic encryption-based approach that we're suggesting and proposing here so in a zero-knowledge proof-based approach a user will need to compute a couple different values they will need to have the commitment or encryption to the number of items the price per item and then the total bid value which is n times p they are going to need to produce a more complex urinary proof showing that they've done this update on the encrypted or committed values correctly because there is no like multiplicative relation between the ciphertext and the idea is that the user performs all computations so as we stated earlier the idea is we want to rely on zero knowledge proofs to ensure that updates were in fact done correctly so on the bottom left you can get a snapshot of all the pieces of information that a user might need to provide to participate in a sealed bid auction on the right we have a fully homomorphic encryption-based approach as would be in smart fhe and you can see on the right that there are fewer pieces of information that a user might need to provide and the zero-knowledge proof is a bit simpler so it's an easier transaction or easier computation for the users more generally how do these solutions map out and what do they look like it's difficult to say one solution is superior to the other it really depends on what's most important to you there are a lot of trade-offs the main ones being are you okay with additional trust assumptions like trusted setup semi-trusted managers does efficiency matter to you and if so what kind of efficiency do you prioritize time or do you prioritize space and then finally do you need full functionality are you okay with for example zether where you can only do private computations on certain kinds of functions and finally just some last considerations is front running best solved by cryptography i will not offer an opinion on that there are plenty of different solutions you could be okay with dark pools maybe economic disincentives make better sense more generally should we combine cryptographic solutions with other non-cryptographic solutions and as we suggested before if you choose to take a cryptographic approach what's more important to you time or space and that's it thank you so much aritel that was super interesting um let me see like anyone on the chat please uh post your questions if you have anything while i ask uh one of the questions um as we have a few minutes maybe if you can uh clarify how much of this is a proposal versus implementation um that has been worked on uh so it is a full paper that's currently being submitted to the conference there is benchmark numbers to get a sense of the feasibility compared to the other approaches but there isn't a full working implementation quite yet awesome um second question that we have is what does the zero knowledge ecosystem needs to do to bring this to reality i know it's right it's like putting on the spine here you can't take it the way you want um are you like if you if you you or your team is doing this maybe you know we're not working on this actively but i think like the the prover times and the verification times just need to be improved significantly i think the fact is with like whatever papers are kind of currently being written they all use trusted setups for a reason and it's because that's what's offering practical efficiency so until we have like transparent zero knowledge proofs with good efficiency that don't have ridiculous hardware requirements i i think we have a problem do you think that any of this can be done on ethereum i mean kind of goes with your question i'm optimistic about it but i can't say for sure yet thank you i mean you know we have a lot of smart mind on this space and it's great to have you go through it and i hope it inspires others to break their head around this problem great thank you thank you for joining us today