Private Information Retrieval on Blockchains with Chris Beck

hi I'm here to talk to you about private information retrieval and blockchain um yes so let's uh let's get started since we started a little late okay so the topics I'd like to cover today I'd like to try to explain to everybody what is private information retrieval I'd like to talk about how can this technology help the ethereum project and its Community I'd like to talk about why should we care about this philosophically I want to give an overview of known techniques I want to give some examples of practical deployments I want to sketch how this could be used for ethereum and I think we might cut the future directions because I don't know if we're gonna have time but we'll see um okay so private information retrieval often written PIR so in private information retrieval the idea is that there's a client and there's a server that has a large data set and the client would like to search that data set for a particular key but they don't want the service operator to learn what key they're searching for because it might be very sensitive for some reason um and so PIR generally means trustless cryptographic protocols that accomplish this task um so to try to connect this to ethereum folks I want to try to talk about uh controversy having to do with metamask which happened last year so in November 22 the maker of metamask informed users that when you use infuro which is the default RPC provider in metamask it will collect your IP address and your ethereum wallet address whenever you make a transaction and uh some people were unhappy about this because they felt like this is not what should be happening in like a web 3 technology uh and so the options that we have now are users can use alternative RPC providers but nothing prevents those providers from collecting the same data um some users may run an ethereum full node themselves for privacy but unfortunately that's not practical for like the vast majority of users so in principle private information retrieval is a way that users could have that privacy without running a full node so that that's what brings me here today to talk about this um and I want to sort of talk about sort of how this connects to web3 philosophy right so web3 means different things to different people right it's a social movement um web 2 has largely become associated with giants like Facebook and Google that own large parts of the internet and harvest all the data in a model that's now called surveillance capitalism uh and so I've been coming to East Denver for many years I live in this area and uh when you ask people what web3 means you invariably get lots of different answers but one of the common denominators that I often hear is that web3 means you own your own data now I believe that you cannot meaningfully own your own data if you do not have privacy around that data and that is what I believe motivates a lot of privacy activists to contribute to blockchain projects um so I want to try to give an example of private information retrieval in practice because if you're an engineer you may never have heard of private information retrieval before it's not commonly used in real web Technologies because it's actually really hard um but there are a few examples that I want to talk about so 10 years ago signal messenger ran up against a very difficult private information retrieval problem so the problem is that signal users need to be able to discover if their contacts are using signal and get their public keys in order to send them messages uh however signal does not want to learn your contact list they don't want to be able to in see or infer uh what phone numbers you're querying they don't want to learn everybody's contact list in the whole world that that feels like a bad thing that they don't want to have access to and uh a lot of there are a lot of obvious approaches they thought about like what if we just hash all the phone numbers but it turns out that that doesn't actually do anything from a cryptographic perspective because phone numbers are actually pretty small there's not a lot of data there and you can probably Brute Force the hash so they wrote a blog post in 2014 about this issue because they were still thinking about and they weren't sure what to do and then they researched it for about three years uh which I think is pretty interesting um so uh a lot of private information retrieval research there's a lot of academic literature on this topic and most academic papers on this topic fall into one or two buckets it's either computational PIR or information theoretic PIR this has to do with sort of the the security model for the system in computational PR PIR papers generally to handle a query the server has to load every data item into memory and then do public key cryptography with it which is very expensive and unfortunately these approaches generally just don't scale to having a service that millions of people are using in a large data set um in information theoretic PIR they sort of change the model so there's not one server anymore but there's K servers and when you the user want to make a private query you're going to send a special message to K different servers and then those servers are each going to think about it and give you back a response and then you're gonna like do something with all the responses together and you're gonna get your answer but the servers aren't supposed to learn what happened the problem is that this model assumes that these servers are not communicating and there's no way for you as a verify as like as a user to verify that the servers are not colluding so like uh sort of putting this in context like in my experience a lot of people in the ethereum community are pretty good at Game Theory so there are a lot of blockchain Technologies where uh you assume that the majority of the validator nodes are honest and then that makes the consensus service have uh has liveness and have good properties going forward uh and we know that in principle all the validators could collude and get together and start rolling back blocks and rolling back time or tampering with the blockchain in bad ways but we also know that if they did that it would be immediately apparent to everybody who's sinking the chain they would not be able to conceal the fact that this happened so we can trust them but we're also in a position to verify that they didn't do that um whereas with this information theoretic PIR stuff it's like if all the nodes decided to collude and and start sharing messages to try to see what your query was they know that you would have no way of ever finding out that they did that so that that makes the game theory around this very bad so I don't expect K server PIR to actually be used in practice um signal sort of looked at all this stuff and what they ultimately decided to do they created the signal contact Discovery service and they decided the best approach was to create an Intel sgx Enclave and so that's that's that's so much surprising right it involves trusted Hardware so it's a complicated solution uh but the shape of signal kind of Discovery is roughly like this the the data set is stored in the enclave's encrypted memory which the node operator is not able to access without penetrating sgx protections uh and when users connect to this service they create a secure connection to The Enclave using remote attestation then The Enclave scans across the entire data set all the phone numbers and all the public keys in constant time in order to resolve queries but many queries are actually batched together for many users to try to amortize the cost of this slow scan and then several minutes later all the encrypted responses are returned to all of the users so that's a pretty remarkable thing uh and to connect it back to web 3 philosophy to my knowledge this is the first private information retrieval service that was ever deployed to serve millions of users in real life like not as an academic paper and I think it's really cool that signal was not content just to promise we won't log your data they want to use cryptography to prove that they are technically incapable of harvesting your data and eliminate the need for blind Trust I believe that that is a social Norm worth building towards to counter surveillance capitalism generally and I also think it's cool that like in my view this aligns with a lot of web 3 privacy projects even though Signal's not a web 3 company and they're like in some ways a lot older than web3 um so the next thing I want to talk about is oblivious rain which is sort of another iteration of this so signal contact Discovery was great but the algorithm they used is pretty rudimentary uh it still requires touching every data item in charge in order to support a query it's not really appropriate for a low latency service a lot of blockchain stuff a lot of payments applications you need to be able to respond in seconds not minutes the signal was okay with having contact Discovery be like it takes five minutes to find your contacts because it was an adequate user experience for their needs most people don't immediately need to find their contacts as long as academic eventually in the background then it's fine um but we were sort of interested in trying to figure out how we can make this better and so we turn towards a technology called oblivious Ram so oblivious Ram is a data structure with a cryptographic security property it does not require touching all the data in order to serve a request instead what happens is data is continuously shuffled over time in a way that providely obscures the flow of data across all queries and together with the secure Enclave approach this can be used to build a low latency private information retrieval service so I want to try to talk about the history of this idea because it's pretty it's pretty cool so oblivious Ram was invented by ODed goldrick in 1987. it's actually before I was born uh it was significantly improved by goldrick and his student of stravsky in 1996 path Oram was a major breakthrough in 2013 that was due to Emile stefanov Elaine she Christopher Fletcher and like four others uh this was one of the first oblivious random data structures that had good theoretical worst case performance uh and then a few years later zero Trace was a landmark paper of sajan sassy Christopher Fletcher and Sergey garbanov which first implemented path Oram in an Intel sgx Enclave they had this idea that this might work it might be good the security model makes sense and they decided to try it and do benchmarks and they reported promising performance performance measurements on real Hardware so that was a really exciting paper uh of the three people pictured here I would imagine that more people in the audience will recommend the third person Sergey gorbanov because he went on to be a co-founder of algorand and later axillar uh so I want to give a shout out to Sergey um so this is where mobile coin enters the picture go to my my story Touches under the thread um mobile coin launched an oblivious service called mobile coin fog in February 2021 to support mobile clients like signal and Moby in a privacy preserving manner so that they can check their balances against the blockchain without revealing to us which transactions are theirs we actually load the entire mobile coin blockchain into oblivious Ram and we support all the mobile users balance checks in real time uh this is the first time that oblivious Ram technology was shipped in production to millions of users we built on the ideas of zero trace and we implemented a number of performance optimizations to make it practical with only a few actual machines all of our machines are serving about 100 requests a second uh against the whole blockchain loaded into this diesel ramps uh and so at this point I want to give a shout out to all the engineers that I've worked with because there's really been a lot of people that have made this a possibility so I designed in prototyped fog I implemented our Oram in 2019 a large team of people has worked together over years to productionize and scale this into the future so I want to give a specific shout out to my colleagues Iran runstein James Cape Joe Kottke Joe Yandel Farah drakeley Hall Sam Daly William Juan Jason greathouse Andrew Riggle and Emily cutlip as well as some other people not pictured here including Nick Santana and Ramon mechas thank thank you all of you I'm extremely proud of what we've built um so now I want to talk about how oblivious Ram could help ethereum so the ethereum blockchain is quite large however I believe that it could be like shared across a reasonable number of oblivious Ram machines I believe that we could load significant chunks if not all of the ethereum blockchain into oblivious Ram um the goal of this project would be to create a new eth RPC endpoint that you could use in metamask and the idea would be that it would use Oram to serve the types of requests made by metamask while preserving the privacy of the users the idea would be that this would be like a public good that helps users of metamask to protect their privacy without having to do really complicated things like run a full node uh now in order for this to work we would have to modify the RBC protocol a little bit we would have to allow for remote attestation to take place before the client sends an encrypted request to The Enclave this is not just like a drop-in change but I think it shouldn't be too difficult to do that modification um much of the infrastructure that we use for mobile coin fog could be reused for this purpose uh it's mostly agnostic as to your structure of your blockchain and all this stuff is open source you can look at the mobile coin Foundation GitHub uh we have the mobile coin repo and the MC oblivious repo in the longer term I think it's possible to support the more complicated RPC requests like East called but there might be a path to do that we'd have to talk about it if you are interested in contributing to such a project or supporting such a project please reach out to us we'd be super stoked about trying to support the ethereum community um the last thing I want to say is that uh I want to I want to make another final note so it's helped people keep all these Technologies straight oblivious Ram is not the same as your knowledge proofs it's not directly related at all actually uh there is enormous interest in research effort towards using zero knowledge proofs in ethereum and layer twos however zero knowledge proofs actually do nothing to solve private information retrieval privacy problems it's like completely orthogonal uh yet zero knowledge proving attracts most of the attention so in the long term I want to sort of encourage us all to think holistically about privacy um how am I doing in time I guess I have a few minutes so I'm actually going to do the talk about future directions so the last thing I want to talk about which is kind of cool um so in a recent blog post vitalik buterin on the on the ethereum research blog talked about stealth addresses what they are what they mean try to introduce the concept and he even proposed that they could be added to ethereum in the future which is really cool um so stealth addresses are the idea that when you receive a payment this is sort of a high level explanation your address is going to be perturbed randomly by the sender in sort of a special way and this random address is what appears Unchained to any onlookers the idea is to establish unlinkability between your payments so that instead of having your address on every single payment you have these different stealth addresses on all of your payments and then it may seem bad that your address is different but it turns out that if you do the math correctly later you can use your private keys to account for the perturbation and you can still produce a correct signature to spend the stealth address funds so that's a really cool idea uh I believe this idea originated in Monero research Labs uh mobilecoin uses it D cash has sort of an equivalent idea they don't exactly call it stealth addresses but it's similar um so one of the main issues about stealth addresses in my mind is that stealth addresses create scalability problems so the reason they do is that um the randomness for your stealth address is being chosen by the sender and it's not known to the recipient in advance so what it sort of means is that the users are forced to do trial decryption in order to identify their transactions like if you send me a payment I have no idea what the stealth address will be that it's coming on so I have to look at all the payments and try to match my private Keys against them uh and this is a really bad thing for small clients like metamask or mobile phones that's why we were really focused on a mobile coin uh so I invented a concept that I call sequential stealth addresses which are a really key part of Mobile coin fog and in this variation of the idea it's like your payments come along a sequence of pseudorandom addresses that are predictable by you but nobody else and so then you can search for your next payment using a PIR query and you don't have to do trial decryption so that is sort of what makes fog able to do things in real time for people you know we don't stream the entire blockchain to the phones because that would work we use the sequential stealth addresses and PIR together to have uh privacy and scalability at the same time so uh I don't have time to fully properly explain that but if you are interested uh please come up and talk to me after or somebody else at mobile coin uh or you can look at the fog white paper which also explains all these ideas in great detail uh that's all I plan to talk about I think we might have a minute or two for questions uh thank you all for listening to my talk [Applause] you mentioned there were two approaches tpir one of which involves uh putting everything into RAM basically and that that doesn't scale but it sounds like the approaches you've used here also involve that for the whole blockchain like is the idea then to scale that across machines and use the random multiple machines and if so can you know how to correlate like which machine are you querying to find out what part of the data you're querying that's a great question so uh the way the system is designed actually is that uh as you scale up to the highest degree what I think we're supposed to do in the end is you store the Oram Pages you actually move them out of The Enclave encrypt it again and you store them on an SSD and if you have a performance SSD then that's actually not the bottleneck um so usually you're going to be having like you know terabyte of data on each machine that's doing this I think it's like where the scaling rig works out to and then when you're serving requests on the blockchain across several machines what you actually do is you have like a router that handles the incoming request and it dispatches to any possibly relevant Enclave so all the machines May potentially do work for your query but usually when somebody's like checking their balance again having checked it like yesterday they don't have to scan all previous blocks for their most recent payment instead they just searched the most recent blocks for their most recent payment and uh that improves the scalability system a lot oh yeah thanks for that question it's a great question are there any other questions that I can or do you have any further questions okay thanks all right I think that's a wrap oh do you want your question are you familiar with Nim a gentleman yesterday gave a presentation on a library to kind of like oh sorry are you familiar with Nim okay yeah so can you use the two together so like Nim kind of like uses tour routing to like obscure your metamask transactions um like like sent them and how it's received could you use that together with yeah so the question is basically like can you use mixed Nets Torah type routing or what what Nim does to try to improve your privacy as well and try to avoid linking your IP to the queries that you're making and the answer is yes you can stack all these Technologies together with increasing benefits uh but yeah it's like if you're using mixed Nets what you're trying to do is you're revealing to the server which transaction you're querying but you're trying to dissociate your IP from that um where's our thing we're trying to make it so the server learns nothing but they might learn your IP so yeah so if you use both together their server should really have no idea what's going on cool I think we are out of time but uh thanks everybody uh yeah and thanks East Denver