Articles

New Developments in Cryptocurrencies and Blockchain Technologies

November 29, 2019


Now, I would like to introduce to you our featured presenter Dan Boneh. Professor Boneh heads the applied cryptography group and co-directs the computer security lab here at Stanford. Professor Boneh’s research focuses on applications of cryptography to computer security. His work includes crypto systems with novel properties, web security, security for mobile devices and crypto analysis. He is the author of over 100 publications in the field and as a Packard and Alfred P Sloan Fellow. He is a recipient of the 2014 ACM prize and a 2013 Gardel Prize. In 2011, Dan Boneh, received the Ishii award for industry education innovation. Professor Boneh received his PhD from Princeton University and joined Stanford in 1997. Now, I’d like to turn the floor over to Dan. Great. Thanks Joe. So, excited to be here. welcome everyone, and I wanna tell you a little about, a little bit about our work on cryptocurrencies and blockchain technologies and everything that, we’re doing in this space here. So, I’m looking forward to this webinar and you know, if you have any questions please type them in and we will answer questions in the Q&A session. So, this is meant for you. If I say anything it’s not clear please feel free to ask and we will answer the question right away. All right. So, let’s get started. As Joe said, I’m Dan Boneh, I’m a professor here I work on cryptography, computer security, and I’ve been doing a lot of work on blockchain over the last couple of years. That’s a fantastic area, a lot of fun to work in this, in this space and I wanna tell you a little bit about our work and particularly what excites me about this area. before we get started, I wanted to mention that in Computer Science, we have a very active computer security lab, which covers lots of areas within computer security which intersect very strongly with blockchain. So, let me just quickly explain kind of what we do. So, I work on crypto, blockchains, and things like that. we have a security works on measuring notions of security, material works on big data and security. we have folks doing static analysis which is actually quite relevant to smart contracts, you wanna make sure that the contract actually does what it’s supposed to do, and so we have a number of people working on verification of software in particular and smart contracts as well David Mazieres works on operating systems and consensus protocols. In fact, the Stellar consensus protocol. Stellar is one of the largest cryptocurrencies out there that consensus protocols was designed by David Mazieres We have folks also working on IoT security. John Mitchell works on various aspects of protocol design and programming languages. Programming languages are also a big component of blockchains. Again, the question is, in what language do we write smart contracts that are then executed on a blockchain and that’s a fantastic area that’s growing quite rapidly, and then Mendel works on VMs. So, there’s a very active security lab, but in this webinar I’m gonna focus specifically on our work on blockchains and what we’ve been doing in the space. So, what I’d like to tell you a little bit about today is basically a couple of things we’ve done. One thing I’ll tell you about is something called confidential transactions using a system called bulletproofs that we developed, and we’ll talk about all the applications of that and where that came from. And then I wanna tell you a bit about what are called proof of solvency which is how to prove that a cryptocurrency exchange is actually solvent and can cover all of its obligations. Then we’re gonna switch gears and talk about an application that’s actually not directly motivated by blockchains, but is relevant as well. I’ll tell you about a system called Prio which is used for privately aggregating statistics. Everything I say here is work that’s available in papers that are published in public. I’ll have links if you wanna read more about the work you are very welcome to you and as I said if you wanna use any of this, this is all public domain and would be happy to answer any questions you have about deploying any of these techniques. Okay. Good. So, let’s start with bulletproofs and confidential transactions. This is joint work with my student Benedict Bunz as well as our collaborator Jonathan Bootle, Andrew Poelstra, Pieter Wulle and Greg Maxwell. Andrew, Pieter and Greg are in a company called Blox Stream, and they’re actually also one of the core, some of the core bitcoin developers. Okay, so, this is work that appeared, earlier this year. I have a link here to the paper in case you wanna learn more about how bulletproofs work, but let’s get right to it. So, I guess before I tell you about bulletproofs, I wanna talk a little bit more broadly about blockchains and cryptocurrencies in general. It’s an area that from my point of view is a fantastic area to be working is, to be working in. The interesting, this area though, it kinda suffers as you may know, A little bit from overhype but nevertheless there are real scientific problems here. And just to give you and that’s kind of what attracts me to the area kind of the hard, scientific, questions that need to be answered. I can tell you that literally every project that I talk to in the blockchain space I walk away with three new research problems to work on. So, there are really lots and lots and lots of open questions which is kind of great for a researcher like me. So, just to tell you kind of the the things that attracts us to this area. So, you know there is need for a new consensus protocols, we’ll talk about consensus protocols in just a bit and this is generally a kind of work in distributed systems. So, yeah. So, developing new consensus protocols I already mentioned, there’s a lot of demand for new programming languages for programming smart contracts and along with programming languages for smart contracts is also need for verification tools. So, how do we verify that the contract does what it’s supposed to do. So, we don’t end up with a situation like the Tao where because of a programming bug, a lot of money was stolen or like other exeunt like other famous contracts where because of a bug, a lot of money was locked up so no one could actually access those funds. So, verification is becoming quite a central area of smart contracts and as I said, there’s a fair amount of work about that here. There’s obviously a need for new cryptography, that’s kind of my bread and butter, that’s where I live and that’s where I’m gonna talk to you about and then there is also really beautiful work in what’s called Mechanism Design or more generally, this area called algorithmic game theory which is essentially how to distribute rewards and how to divide, how to design incentive compatible mechanisms that encourage players to act honestly and contribute well to the system. So, all of these are kind of wonderful areas where the blockchain introduces new research problems. So, there’s really a lot of new science that’s being created here. In my opinion of course this area is like I said a wonderful area to work in. It’s not a fad. It’s an area that’s here to stay and it’s gonna be with us for a long time. As I said, in this talk I’m gonna focus on some of my work which is basically kind of new cryptography that’s needed for for cryptocurrencies. Yes, I hope this will all be clear and exciting to you and like I said I’d be happy to answer any questions that you have at the end of the talk, end of the talk. It’s okay. So, let’s get to it. Although I do wanna say that because of all this, kind of scientific interest, it turns out there were many people working on blockchains around the University of Stanford here. And so what we did is we created this new center for blockchain research, it’s called CBR, the Center for Blockchain research. If you wanna learn more about the CBR, please go to cbr.stanford.edu. There’s a lot of information there about what we do. In particular, this is a research focused effort, but in addition to our research, we run a lot of outreach activities and including courses and moocs and books and seminars. So there are a lot of activities. All our activities are open to the public and we want people to come and kind of join our activities here on campus. So, you know, please go to cbr.stanford.edu to learn about our outreach activities. Particularly, if you go to the seminar page, there are instructions there on how to add yourself to the mailing list just to learn about activities that the center runs. I promise it’s a very low volume mailing list. All you will get is just e-mails about events that are open to the public that you are all welcome to come and participate in. In particular in January we’re running our third Stanford Blockchain conference. If you wanna submit a paper to that, if you wanna present some of your work, there are instructions on how to submit papers. If you just wanna come and learn, you’re very welcome to. As I said this is in January, open to the public, and anyone can come and participate in the conference. If you come to one of these events you kind of realize there’s so much energy in the blockchain space. Even though it’s a technical conference it’s really fascinating to hear all the conversations, the talks and the conversations in the hallway. And again I can tell you that a lot of our brightest students now are going into the space and with so much talent in the blockchain area. You know, it’s almost guaranteed that good things are gonna come out of it. So, I do wanna mention that our Center for Blockchain Research is, is sponsored by sort of top project in the space, the Ethereum Foundation, Protocol Labs, Interchain Foundation, OmiseGo, Dfinity and Polychain Capital. So, it’s been great to work with them and as I said we’re always always looking for more folks to work with. If you have any questions about our project that you’re interested in you know, please reach out and we would love to talk. Okay. So, with that let’s get started with, the technical part of the presentation. And I guess I’ll start by taking on a challenge that someone asked me recently which is to define a blockchain in 10 words or less. So, what is a blockchain? Well, let me try to define it in 10 words or less and then we’ll kind of dig into the words. So, a blockchain really is a data structure that has a number of critical properties, right? So the properties are basically liveness, which means that anyone can write to the blockchain and there’s no way to prevent you from writing to the blockchain. Right, we call that liveness. When you write to the Blockchain obviously sometimes there’s a transaction fee associated with that but if you’re willing to pay the transaction fee, you cannot be prevented from writing to the blockchain. So that’s liveness. Persistence means that once the data is written to the blockchain, it can never be removed. And typically, the way we achieve persistence is by replicating the blockchain. This data structure replicating in many times all over the world. So that if you’re gonna remove something from the blockchain you have to remove it from all the replicas or a majority of the replicas. So that’s persistence and you notice there’s a little star there because typically persistence is achieved under certain assumptions basically say the adversary has less than 51% of the computing power in the network or there are other ideas that are coming up about less than a certain amount of the stake of the funds in the network less than a certain amount of the space that the network uses and so on and so forth. But persistence typically is achieved under certain assumptions. And once you have liveness and persistence, the other important property that’s implied by that is what’s called consensus, which essentially means that anyone that’s using the blockchain agrees on the current state of the blockchain. That is, we all agree on what data currently, resides on the blockchain. Okay, good. So, those are kind of the three properties that blockchains provide to us. But fundamentally, I want you to remember it is just a data structure for managing data and it just happens to provide these properties. Now, these properties enable a tremendous number of applications. The most– the simplest one is something is in the cryptocurrency, right? If you have liveness and persistence, essentially this means that if somebody sends you money, there is no, you know, a crypto token say there is no way to take to undo that transaction because of the persistence properties or rather I should be more precise, there’s no way to remove the transaction from the blockchain because of the persistence property. Of course you can, if you want to you can send the money back and undo the transaction but there’ll be a log of the fact that money was sent to you and then money was sent back. So, persistence is kind of necessary for a cryptocurrency application. The liveness property means that no one can prevent you from spending your funds once you actually decide that you want to spend them. Okay. So that’s why currency is a very natural application for a blockchain data structure. But it also enables a whole bunch of other applications like what’s enabled by smart contracts, it enables crypto asset managements. So once I own a particular physical entity, I can record that in the blockchain and that can never be taken away until I actually transfer ownership to somebody else. You can also talk about crypto asset management for digital goods and I have to mention there is a game called Cryptokitties which is where people trade digital kitties for fun and it’s actually a pretty, pretty, pretty amazing game. I encourage you to check it out. It’s a really really well designed game where people can buy kitties and then trade them later on, breed them with the kitties and trade them and so on. That’s a wonderful example of of digital asset that manage on the blockchain. Essentially who owns which kitty is recorded. In this data structure and once you own a kitty, no one can take it away from you even if the company that runs the CryptoKitties game goes out of business. Yeah, so you will always, always always own this kitty and no one can take it away from you and that’s kind of the power of, of the blockchain. Okay, good. Ah, so, Crypto Asset Management is another application. I have to say that there’s a lot of interest where, in the Stanford Registrar’s office in putting Stanford transcripts on the blockchain and there are a lot of benefits to that. So, for example, you can always if you, if you present your, your transcript to an employer, the employer can always test, can always tell that it’s looking at the latest version of the transcript because the latest version is recorded on the blockchain. So, there are a lot of benefits to putting contracts on the blockchain just for the purpose of freshness. So, you know you’re looking at the latest version of the documents. And again even if, you know, the unthinkable happens and for some reason, you know, Stanford is no longer around, your transcript would still be on the blockchain and you can still prove that you are a Stanford graduate. So, again the persistence is what is such a such a powerful mechanism and that makes the data structure so useful. Of course everything is transparent of blockchain, all the data on the blockchain is public, the whole world can see it. So, there are a lot of applications that require transparency and blockchains are are a wonderful data structure for those. Just to give you one example. If you wanna run a lottery, for example, if you want the lottery to be transparent, so that you are guaranteed that the randomness that went into the lottery really is unbiased readiness then again, a transparent data structure like a blockchain is a very good data structure to use. Yes, so, I kind of walk through a number of a number of applications, there are many many others. But this is why there’s so much excitement about the space and that there is this, like I said there’s this data structure that is now available out there. It enables us to do things we couldn’t do before. And again that’s why so many people are building new applications and why so much talent is going into the space. All right. So, with that, let’s kind of drill down a little bit. And I guess what I wanted to do even though there are lots and lots and lots of blockchains out there with very different characteristics and very different designs. I wanted to just pick on one, and drill down a little bit more just to show you how it works. So, you know, the one that I just chose is the Bitcoin and blockchain maybe that’s the most well-known. But again I want you to remember Bitcoin is just one example of a blockchain. In fact, we consider just the generation one blockchain in that it’s very limited in its capabilities, generation two blockchains are things that, are things like Ethereum that include smart contracts and other capabilities and generation three blockchains are the ones that are being developed and deployed now. Those are ones that kind of avoid the expensive proof of work that’s needed to make blockchains work and we’ll talk about that a little bit later. Okay. So, let’s talk about the Bitcoin blockchain just so that we start at the beginning. All right. So the Bitcoin blockchain basically is, you know, as the name implies, it’s basically a sequence of blocks. Yeah. So,you can add blocks to the blockchain at will. In fact, every 10 minutes, a new block is created and these blocks basically form this very very long chain. Yeah, it’s basically, from the beginning of time, you know, since 2009, these blocks have been added every 10 minutes. So there are many many many of these blocks. And the reason they form a chain is because you notice, when I looking at block number N minus one, that’s the block header contains in it a bunch of transactions, you can see there’s a whole transaction tree that’s embedded in the block in the block header. This is what’s called– this tree here– is what’s called a Mercal tree, which means that essentially all of these transactions that represent the block and we’ll talk about transactions in just a minute, essentially they’re sort of committed to in the block header. Yeah, so this value here is a hash value that commits to all the transactions that are embedded in this particular block. There is what’s called a non switch, is related to the proof of work, I won’t talk about that here. There’s a time stamp but the important field in the block header is what’s called a hash. So what is this hash? Basically, every block is in every block what you do is you hash the block header. Yes, you compute some sort of a compressed function of the block header and then you write the resulting hash value into the hash field of the next block. And this is what forms the chain structure. Yes, so you can see here again block number n contains a hash of block number n minus one, block number n plus one will contain a hash of block number n and so we get this very very long chain structure where this hash operation induces sequence among blocks and that’s why we call it a chain. As I said, this is only generation one of blocked, of the block chain structure. There are many new ideas being considered now. In particular rather than using a chain, people are talking about using more complicated graphs. But here let’s just keep it simple and just talk about the Bitcoin blockchain. Okay. So, that’s what the blocks are. Now you notice that all these transactions here, so every block has a number of transactions typically there are between several hundred to several thousand transactions in a particular block. So let’s talk about what these transactions are. And a transaction again just to give you a sense of how they work. I’m not gonna talk about the specifics of the transaction format, just to give you a sense of what they are, essentially every transaction corresponds to a transfer of potentially a transfer of funds between addresses in the Bitcoin network. Yeah. So, what happens is in a transaction we have these inputs to the transaction. These are kind of the addresses that provide funds into the transaction. So in this case there are two transaction inputs and then the transaction output which are basically where the funds are going. So, every transaction output basically has a value which is how much money is being transferred to this particular address and then it has the address which is where the funds are actually going. All right. Transaction outputs contain value and address. And in this case there are two transaction outputs, we call these things UTXOs. UTXO stands for unspent transaction outputs. So, here we have UTXO on number one and UTXO on number two. So, what happened here, is this transaction basically created two new UTXOs. These UTXOs belong to this address number one and address number two, and each one has a certain value associated with it. Now, later on, if you want to spend money from a particular address, you actually don’t spend money from an address, you actually spend money from a UTXO. Okay. So, there are no accounts in bitcoin, no accounts. Funds are actually held by these UTXOs, and what this means is that when you want to spend the money from a UTXO, essentially you create a new transaction. Here we have one transaction input going in. This transaction input essentially points to the UTXO that`s being spent. Okay. So, the value that’s going into this transaction, is the value associated with the UTXO. And then there is a signature by the owner of the address that says, “Yes, I’m authorizing the spending of this UTXO.” Right? So, remember that you have a secret key that’ll essentially allows you to spend the UTXO and only you can cause a UTXO to be spent, or rather, only whoever owns the secret key that’s able to create the signature is capable of spending a particular UTXO. So, it’s kind of cool in that no one can take your funds away from you other than by taking your secret key. So, if you keep your secret key safe, no one can ever spend your funds. And by the way, I should say that there’s a whole industry forming around custodial services for holding secret keys for cryptocurrencies. So, if you happen to own a bunch of cryptocurrencies maybe as an investment, maybe because you’re an enthusiast, or maybe because you want to use the cryptocurrencies for something, the question is always where do you store the corresponding secret keys that enable you to spend those funds? You can store them at your home if you want, but if something happens and I don’t know maybe there’s a burglary, maybe your home, maybe something happens to your house, maybe you lose the secret keys, in some way those funds can then be spent on your behalf. And so, there’s a whole industry of custodial services where you can give them the secret key, and they will manage and store it for you. So, yes. So, keep in mind that it’s probably a good idea not to store a cryptocurrency secret keys yourself. It is probably a good idea to give it to a custodial service and this is their business to keep those secret keys safe and make sure that they’re never lost. Okay. So, regardless though, we have these transaction inputs that basically authorize the spending of the UTXO. And here we have the two new UTXOs that are being created. So, for example, here you see a UTXO number three was created. And the interesting thing about the UTXO model is it’s not account-based. So, funds are held in these UTXOs, which means that after you spend the UTXO, that UTXO dies. Okay. So, no one can spend funds from that UTXO anymore and it’s as if it never existed. Okay. So, this will be called a spent transaction output as opposed to an unspent transaction output and no one can ever spend funds from that UTXO again. So, that’s how funds are basically are held on the block chain, and that’s how they’re being transferred from address to address, they’re held in UTXOs and a transfer means creating another UTXO. Okay. So, that’s the UTXO model. So, that’s how the bitcoin network works. It’s a pretty interesting model, although I have to say other block chains actually use an account model where funds are actually held in accounts, and if you wanted to see how much money you have, you basically check how much money is in your account. In bitcoin, if you wanted to see how much money you have, you have to sum up all UTXO, that all the UTXOs that belong to your address, and that will tell you how much money you have. So, it’s a little harder to tell what your balance is, but at the same time this model is actually quite clever and that makes it quite easy to manage what’s live on the block chain and what’s not live on the block chain. Okay. So, that’s the UTXO model. Let’s dig in a little bit and look at a particular transaction. So, here I just listed one random transaction from the Bitcoin network. And the thing that I want to point out here which is quite interesting is, again, you can see the addresses here, you can see the exact addresses that provide the funds. Okay. So, this is one address that provided the funds, here’s another address that provided the funds. And here’s how much money was being transferred in. So, in this case it’s 0.5 Bitcoins, and then the other address provided 1.47 Bitcoins. Okay. So, you can see exactly how much money came in and then you can see where it went. Right. So, it went to this address, you know 0.01 went to this address, and then two bitcoins went to this address. So, you can see exactly which addresses contributed funds and which addresses received those funds. And I can tell you that there’s a lot of work out there that shows that in fact it’s not difficult to map addresses to physical entities. So, there’s no anonymity in these addresses. It’s actually not that hard to figure out who these addresses belong to. So, literally, you can tell who transferred funds to who and how much. Yes, so the amounts are all public. So, and you remember these transactions all go on the bitcoin block chain, which is in replicated all over the world. It is public for anyone to see, and it’s important that everyone can see the block chain, so they can verify that all the transactions are legitimate. We’ll talk about what legitimacy means in just a minute. Okay. Good. So, the problem with this is that the fact that all these amounts are public is somewhat contradictory to business needs. Right. So, for example, because everybody can see who the payer is, who the payee is and what the amounts were, this is problematic for business need. Right? So, for example, if Stanford wanted to be my salary in cryptocurrencies, effectively, in a bitcoin cryptocurrency say, effectively, everyone could see what my salary is. Yes. So, the salary would be public. So, that’s kind of, you know, contrary to, what a lot of businesses need. And, even worse, like for example if you wanted to supply manufacturer wanted to pay its supplier in cryptocurrencies, or in Bitcoin in particular, every one will be able to see how much the supply the manufacturer pays for the good. So, Ford, for example, would have to reveal how much it pays for tires, just as an example. So, again, this is kinda counter to how to business needs. Generally, this information needs to be kept secret. And so, the question is what to do. So, can we adapt these existing cryptocurrencies, so that maybe it’s okay to reveal who the payer and the payee is, but it’s not okay to reveal what the value is, right? So, it’s okay to say that, “Stanford pays me my salary.” Everybody knows that I’m a Stanford professor. What’s not okay is to reveal what my salary is. Just as one example. Yeah. So that’s our goal. So, can we kind of hide what the amounts are in the transactions and this is what’s called confidential transactions. Yeah. So, confidential transactions is basically the idea of instead of having the amounts to be available in the clear, like you see here, the amounts are actually in the clear, the idea is to actually hide what the amounts and yet make it possible for everyone to verify the transaction. Okay. So, what are we gonna do? Well, instead of writing the actual amounts in the clear, like we do here, we’re gonna, we’re gonna write something else onto the blockchain. Instead, we’re gonna write what’s called the commitments. So what is a commitment? So here. I have to do a little bit of math here. I cannot give a talk without doing some math. So, let me explain what this means. So, if you look at the amounts here, you see it says, 0.533 Bitcoins. Instead of writing the numbers 0.533 in the clear, instead, what we’re gonna write is the number 533 in the exponent of some base. Yes, we’re gonna write G to the power of 533, multiplied by some sort of a random value that hides what the value is. Okay? So, this is what’s called the commitments. Yeah. So, I’m committing to the number 533, which was the amount that’s being transferred, but anyone who’s looking at the blockchain, has no idea what the number is that I committed to 533 because this number has been blinded by this random number here, by this H to the R1 where R1 is a totally random number. And they do the same thing, you can see this is a transfer of 1.478. Well, I’m gonna write G to the power of 1478, right? So, I’m committing to a number 1478, but nobody can tell that that’s the number that I committed to, and the same thing on the outputs. And one thing that’s interesting is actually that the fees are still gonna be- you noticed this– let me kind of jump here. The fees are still available in the clear, so everybody can know what the miners were receiving, but everything else is hidden. Okay. So, let me just say, say a few more words about this commitment. This commitment is what’s called a Pedersen commitment. It’s a very basic mechanism used in cryptography, and when you wanna commit to a particular value V, again, like I said, you put V in the exponent and then you blind it with some random number, H to the R. Okay? So, by looking at the number, by looking at the commitment, you learn nothing about V, but whoever committed cannot change the value of the number V. That’s the idea. Okay. So now, we get this private, privacy, more privacy preserving blockchain in that no one can tell what amounts were actually transferred. So again, Stanford can pay my salary, no one can tell, what my salary is. But now, we run into an immediate problem which is well, if since the amounts are hidden, how do you validate the transactions? In particular, what does that mean to validate a transaction? What you have to check is that the sum of the inputs going into the transaction, right? The sum of the funds going into this transaction, should be equal to the sum of the funds going out of the transaction plus the transaction fee, right? That’s kind of a fundamental equality that has to be held, has to be true for every single transaction. When the amounts were available in the clear, everyone could just look in the blockchain and verify that all the transactions are valid. If the transaction was not valid, the whole block would get rejected and thrown out of the blockchain, but now that the amounts are commitments, they’re not actually available in the clear, you can no longer verify that this property holds. So we have kind of a fundamental problem and the question is what do we do? Okay. So this is kind of where the beauty of cryptography comes in. And so, what we’re gonna do is we’re gonna use, a little bit of crypto magic and the crypto magic we’re gonna use is what’s called a zero knowledge proof. Okay? Zero knowledge proof. So, what is a zero knowledge proof? A zero knowledge proof is something that allows me to prove to you that a certain fact is true without revealing anything else about that fact. So, you learn you have confidence that the fact is actually true, but you have no idea, about anything else. Yeah, that’s kind of the magic of zero knowledge proof and let me explain what we do here. So, again, even though the public doesn’t know what the amounts are, whoever creates that transaction can convince the public that this equality actually holds without actually revealing what the input and output values are. So that’s one thing. So you have to convince the public that this equality star actually holds. It turns out there’s another problem you have to prove, which is that in fact, it’s not just about the equality, the other problem you have to prove is that all the values are actually positive. Yeah. So it’s not just the sums are equal, you wanna make sure that none of the output values are negative. Let me explain quickly why that’s so important. Imagine I had a transaction that had three inputs going in. So there’s a UTXO worth three bitcoins going in and then one UTXO on the output was equal to seven, and the other UTXO on the output was equal to negative four. Right? So, we had three going in, seven and negative four going out. Well, three is equal to seven plus negative four, yes? So, star is satisfied. However, now we have a UTXO that’s worth seven bitcoins which anyone can then spend as if they had seven bitcoins. Yeah. So, money was all of a sudden created out of thin air and of course they’re gonna ignore them. The negative four output. They’re just gonna use the seven bitcoin output and sort of all of a sudden, money was created out of thin air. So, in fact proving that all the outputs are positive is kind of crucial to prevent money from being created, and so we have to do that as well. The odd thing is that proving that star holds is quite easy, proving that an equality like this is actually quite easy, this should just follows from the rules of exponentiation. Yeah, if I have, well, let me kind of convince you that that’s true. If I have a commitment you can see G to the 533 and G to the 1478, if I multiply these two together, I get G to the 533 plus 1478. Yeah, and I can compare that to the sum, to the product of these two outputs. Yeah, so in fact, checking that a sum hold is actually quite easy, checking that a value is positive, that turns out to be kind of tricky. Why did I write 2 to the 52 minus 1 one here? Well, it turns out that’s the denomination of bitcoin. Yeah, so a bitcoin can go up to basically the bitcoin has 52 bits of precision for a particular amounts. So, the amounts can be specified as a 52 bit string and we have to argue that that 52 bit string is a positive output. Okay, that’s the hard part. All right. So what do we do? So, our work basically which we call bulletproofs is a very efficient, zero knowledge proof system for proving that a commitment to a value V is positive. Yeah, the value that was committed to, in fact, is positive. And it builds on some earlier work. Again, beautiful, beautiful work of Bootle-Cerulli-Chaidos-Groth and Petit from 2016. We basically improved that somewhat and experimented with it for this particular application. And so, what we can do, is essentially, if you have an n-bit proof. So, you have a commitment to an n-bit number and you wanna prove that number is positive, this is what’s called a range proof. It turns out again, I have to write a little bit of math here It turns out our proof size effectively is logarithmic in the number of bits. Okay? So, even if your number is, you know, a thousand bits, the proof will only contain 10-10 elements in it. Yeah. So, it’s a very short proof whereas previously, the proofs were much, much, much longer, they basically were linear in the size of the value. Yeah. So, we kind of went from linear size proofs to logarithmic size proofs. Logarithms is, of course, grow much slower, but even more importantly, if you have to do D proofs, like if you have to prove multiple ranges in a given remember every block has like a thousand transactions in it and so, you have to do like a thousand of these arranged proofs in every block. Before, the size of these proofs would just add up. So, if you do have to do a thousand proofs the proof would be a thousand times bigger than a single proof. In our case, using bullet proofs, no. You just basically, if you have to do a thousand proofs, all you do is you add like 10 additional elements and that’s it and then nothing else changes. And of course, there is no trusted-setup which I don’t want to talk about here. Okay. So these bulletproofs are kind of extremely well-suited for confidential transactions and then just to give you an example, essentially, if you wanted to implement confidential transactions using the previous best zero knowledge system, if you had one transaction, the the data that would have to go on the blockchain would be around four kilobytes, whereas with bulletproofs, it’s only 600 bytes. So, even for a single transaction, we save a lot of space on the blockchain. if you wanted to do proofs for like two transactions, before, everything would scale linearly. For us, things scale much, much better, so instead of, you know, 7,000 bytes, we only need 700 bytes. If you wanna do 10 proofs, you know, here, before, you would need 40,000 bytes, we only need 900 bytes. Okay? So, again, the amount of data that goes on the blockchain, all these proofs have to go on a blockchain to convince the public, the amount of data using bulletproofs is much, much, much shorter than what was possible before in the case of no trusted-setup And as a result, this makes confidential transactions much, much more practical, and easier to deploy in the real world without blowing up the size of a blockchain. Good. So, as I said, this is the bulletproofs, so, like a very good match for confidential transactions, just to be concrete. If you wanted to implement confidential transactions without bulletproofs, blockchain would be like 160 gigabytes, with us, it kind of drops to like 17 gigabytes, so, you know, significant savings. And I want you to remember the blockchain is replicated all over the world, all over the world. Right? So, everyone would have to store 160 gigabytes, here, we are providing quite a bit of savings in the amount of storage. The other thing that bulletproofs are good for, is proving what’s called solving the solvency problem. And I’ll explain this is a paper that we wrote, in 2015 and how to prove that an exchange solvent, and I’ll talk about that more in just a minute, but I can tell you that, in our first results, the proof of solvency that the exchange actually can support all of its obligations, that proof was 18 gigabytes, every day would have to be produced, with bulletproofs, the proof goes down dramatically, to something like 60 megabytes which is much, much, much, easier to do in practice and it turns out bulletproofs can also be used for providing other anonymity mechanisms which I won’t talk about here. Okay. So, let’s talk about a solvency problem. So, that’s kind of a really fascinating area in its own right, so let me explain what the solvency problem is. So, I hope many of you have heard of Mt. Gox. So, Mt. Gox is a bitcoin exchange, that essentially held a lot of people’s funds, so instead of holding the funds yourself, you would give the funds to Mt. Gox and they presumably would store them for you. Well, unfortunately, through a sequence of mishaps, they basically lost all the funds that were given to them. I just wanted you to understand something like $450 million were lost as a result of the Mt. Gox compromise. This was a big deal in the bitcoin world. It caused the crash in the prices of bitcoin. Now this is kind of a very traumatic event for cryptocurrencies, for bitcoin in particular. But it turns out Mt. Gox was nothing special in that many other exchanges have failed to, basically, people gave them their funds to hold, and then the exchange basically lost those funds, and a lot of people lost, their cryptocurrency savings. And again, this is why you want to use custodial services because this is their business. They will not lose or presumably, that they’re built to not lose your keys. So, don’t hold the keys yourself, give them to a custodial service, that’s the probably the safest thing to do. Okay. So, the question is what can we do about these solvency problems? The fact that exchanges, so many exchanges, have, lost the funds given to them. So, the question is what to do? And so again, we can use the fact that we’re dealing with digital goods to provide what’s called a proof of solvency. So, what is a proof of solvency? Well, let’s see. So, every exchange has a bunch of obligations to its customers. This is how much money they owe their customers. And then they have a bunch of assets that they hold. Right? So, these are basically cryptocurrencies, crypto funds that exchange owns. And the goal is to prove that the amount of assets is at least as big as the amount of obligations. In fact if you wanted to support reserve currencies where maybe the assets are only one-tenth of the obligations, you can do that too. But let’s stick to the simple case where just assets are bigger than obligations. Okay. This is what solvency means. In the physical world, the way a bank proved that, proved that it is solvent, is it brings in auditors once a year and these auditors certify that a bank is solvent. That is not a transparent process, not transparent. Right. Nobody, in the public knows what these auditors do, they just certify, but there is no transparency to that process. And the beauty of a cryptocurrency is you can actually transparently prove to the entire world, that you’re solvent because everything is stored as crypto. What they would like to do though is prove that the exchange is solvent without revealing secret information, you know, internal information that’s private to the exchange. Well, this again takes us to the world of zero knowledge proofs where you’d like to prove in zero knowledge that you’re solvent without revealing anything about your internal business. Okay, so again, that was a beautiful problem for us that we worked on and as I said, we developed an efficiency of zero-knowledge protocol for this problem. It’s kind of remarkable that literally the exchange can run this protocol every day. Yeah, every day, it would produce, you don’t have to do this once a year like in the physical world. Every morning, it would produce a zero knowledge proof that says, yes, my assets are bigger than my obligations. Nothing would be revealed about its obligations and nothing would be revealed about its assets and yet the public now has confidence that they are solvent. Yeah, so that’s what you can do with these proofs of solvency, zero knowledge proofs of solvency. And as I said, bulletproofs makes this very efficient. It’s quite interesting actually if Mt. Gox had run these proofs like on a daily basis, their trouble would have been detected many, many months before they actually had to declare that they’re bankrupt. Yeah. In fact, they would have discovered themselves that they cannot run the proof of solvency, and they would have realized that there’s a problem much earlier on than when the problem was actually made public. Yeah. So, I have to say that, bulletproofs have been adopted by a number of projects, and they’re actually put in use, somehow, somehow proof of solvency have not yet been adopted by the industry. So if you know, and if you run an exchange, or if you know an exchange that it’s interested in deploying a proof of solvency, please get in touch with us. You know, I think this is a useful thing to deploy. I think once exchange does it, all the other exchanges would have to kind of deploy it as well. And, you know, it would give us more faith in how these exchanges run. And so generally, this is kind of a nice thing to do. And as I said, we can do it so, we might as well. So again, if you are interested in actually deploying and using this, please get in touch with us. All the research that we do is available in the public domain to support ecosystem. And in fact we’d be happy to help you deploy this. Okay. So that’s kind of what I wanted to say about, proofs of solvency. And I have to say, I literally only touched the tip of the iceberg when it comes to cryptocurrencies. It’s a huge and fascinating area. All I told you about is just one project that we did this year. We have many, many, many other projects that we do at the CBR and you know, lots and lots of forward looking, looking research that we do. If you wanna learn more about the work that we do as I said, go to cbr.stanford.edu, and check out our research page. And then in addition, we’re also running a class on Cryptocurrencies and Blockchain Technologies. This will be the third time we run this class. We’ve been doing it for three years now. The class is called CS251. It’s actually a televised class, so anyone can sign up to this class via scpd.stanford.edu, anywhere in the world. You’re welcome, very welcome to come take the class either if you’re local, you know, come to our lectures and listen in, if you’re remote, you can watch it on the web. The class is gonna go through a lot of the issues that surround cryptocurrencies. How the crypto works, how the consensus protocols work, how to write smart contracts, what are the upcoming technologies in cryptocurrencies and blockchains? It’s a lot of fun to teach this class, obviously the students are, are quite interested in this, and as I said, we’ll cover a lot more than I was able to cover here today. So, I look forward to seeing you there. Now, I think we’re actually running kind of, just took a little bit longer than I expected. I hope it was all clear. I was hoping to tell you about another project which maybe I’ll just summarize in 30 seconds and then stop, which is a a way to privately aggregate statistics. And again, I put up a link to this project if you wanna learn more about what it does, but maybe I can just walk through in 30 seconds and explain what this project does. It’s kind of an interesting, interesting, topic in its own right. So, I just want you to be aware that this technology exists, and if it’s applicable to you, you know, please use it, or get in touch with us, and we’d be happy to help you deploy it. So, the problem is basically, how do we, how does a company learn about its users? Aggregate statistics about it’s user in a privacy preserving manner. Okay? So, today, suppose, let’s take a simple application. Suppose you’re on Twitter. You wanna measure, oh sorry. Suppose you’re an application that measures, I don’t know, people’s blood pressure. And you wanna measure, how does blood pressure correlate to how many minutes a day you use Twitter? Yeah, so, every point here corresponds to one user, right? So, this user uses Twitter this much, and his blood pressure is this much, right? So, if you wanted to kind of build a model for how Twitter uses correlates to blood pressure- this is just a comical application, nobody actually does this, but, if you wanted to build sort of a model for what the correlation is, the way you do that today is, basically, every user sends the data to the application, to the application developer, and then the application developer runs regression to figure out what the model is. Yeah, that’s kind of how we do things today. This is highly non-private in the sense that you have to send all your data to the application developer, even though all the application developer cares about is aggregate statistics. So, this is very non-private, and the question is, can we do better? And it turns out we can do better. Basically, what you can do is you can split your data and share, and send a share of the data to the Stress tracker, which actually reveals nothing to the application developer. You can send another share of the data to, say, Google, which again, on their own, they learn nothing about your data. So, this is called secret sharing, where each, where, by themselves, they absolutely learn nothing about the individual data, and yet, they can actually, together, they can figure out what the model is. Yeah, so, this is great. Yeah, this is great, it allows the developer to learn what the model is without learning anything about, private data, however, there is a problem. The problem is that someone can come in and send you bogus data. You can see they sent a point that’s way, way, way, way, way up here, and that causes the whole model to skew. That one point is so off the charts that it causes the whole model to skew. And so, what our system can make it, what our system makes it possible to do is, basically, you know, learn the results, do it with privacy, but also make sure that all of the submissions, actually, lie within a legitimate bound, a valid bound. So, you cannot have one submission that will skew up all the results. All right, so, that’s what the Prio system does. If you have a need for private aggregation, I guess I’m not gonna say much more about this. If you have a need for private aggregation, you know, I would encourage you to go check out this project. This is something that we did again this, earlier this year. Everything is available online including codes and paper that explains how the system works. If you’d like to use it, as I said, please get in touch with us and we’d be happy to help you do that. All right. So, I’m gonna stop here, and I will open it up for questions. So, Joe, take it away. Great. Well, thank you so much Dan for joining us and giving us such a wonderful presentation. Now, we’ll shoot some questions over to Dan for the end of this presentation. So, one of the first questions that came up, and I think that, you know, it definitely stands out is, why are machines being used to generate bitcoin hash so highly power hungry? Yes, that’s a great question. Right, right, right. So, you’re asking about the proof of work. So, I guess this is related to the consensus part which we didn’t quite talk about here. So, let’s see. So, bitcoin uses this proof of work mechanism, so that the more power you invest as a miner, the more likely you are to be minting the next block. And I should say that whoever mints the block, gets what’s called a block reward, the Coinbase which is you know essentially, an amount of bitcoin, that then you as a miner own. Yeah, so the reason for this proof of work mechanism is actually very very simple to understand in that, effectively, it’s a way to randomly choose a miner from the set of all miners in the system. Yeah. So, you know, everybody invests a certain amount of energy in trying to solve a particular puzzle. whoever solves the puzzle, he’s gonna kind of, wins the lottery and gets to mint the next block, which then pays back to that miner. Okay, s o, effectively, a proof of work is what we have come to call a randomness beacon. Yeah, you have like, say, 1,000 miners, then the proof of work is basically, a way to choose at random, from this set of 1,000 miners, in a way that no one can bias. Right? So, you know, everybody tries to solve the challenge that was you know, embedded in the block, and whoever solves it is the one that actually gets the block reward. So basically, proof of work is a one way to implement a randomness beacon that chooses a miner at random, but now there have been many proposals for other randomness beacons that actually are not that power hungry that don’t require burning so much energy. So in fact, this is kind of, as I said, generation one blockchains require proof of work, the third generation blockchains are actually starting to move away from proof of work. And just to give you some examples there’s a lot of, there are many experiments with proof of stake. So, rather tha generating randomness by solving a hard challenge, we can generate randomness by, basically, requiring everybody to prove some stake, and if they misbehave, they lose that stake. So, there are several experiments with that. There’s a beautiful, there’s beautiful work on using proof of space instead of proof of work. So, a company called a project called Chiha is doing that. Proof of space means that rather than proving that you own a lot of CPUs, you prove that you own a lot of disks, and disks so you have a lot of storage. And disks themselves actually don’t consume that much power, so it’s gonna be much more eco friendly. It’s gonna be a much more eco friendly way to generate randomness to sort of choose a miner at random, in fact, Chiha calls it farming instead of mining because it’s so much more eco friendly. And so, we’re actually gonna be moving away, eventually, from proof of work, and these, this mining process is not gonna take that much energy. But again, to answer your question, yeah, in one sentence, essentially, it’s the proof of work is a way to choose a random miner that will then mints the next block. Great. Thank you for that. Another question and this came up a few times. If the block chain info can’t be deleted, how was, Mt. Gox crypto disappear? Like, how did it get stolen? Yes, yes, yes. Well, the information is still on the blockchain. We can still see that it was stolen. So, it’s not that the data was deleted from the blockchain. What happened was essentially, there were a couple of things that happened. Essentially, people were- so Mt. Gox- so people sent their money to their cryptocurrencies to Mt. Gox. Mt. Gox consolidated it into their own assets, and then, unfortunately, due to bugs in the system, an attacker was able to withdraw more money than the attacker deposited. So, even though all the money was pooled together, Mt. Gox paid out more than it was supposed to, the particular attackers. And as a result, it’s all recorded on the blockchain. They basically lost the funds that were given to them. Essentially, the funds were transferred to other, to another malicious user. So, yeah. So, the data was not removed from the blockchain, it’s just that the funds moved where they were not supposed to move. And in follow up to that, if the ledger is, is always there and you could see the transaction, how are they not able to identify who the attacker was? Well, that’s a good question too, right? So, if the attacker moves the funds to different addresses, you can definitely follow the money and see where the addresses are, but you know, the attacker might actually just leave the funds in, on the blockchain and never actually translate them to a physical entity. So, you’re right, that could still- and then if there’s no interaction with the physical world, you’re not gonna figure out who the, what the physical entity is associated with a particular address. Right? So, you know, the funds are just sitting there, maybe in a couple of decades, someone will withdraw them. But right now, they’re just there, and we have no idea who they belong to. Great. Yeah. Great questions. Yeah. This last question might be a very timely question. So, by definition there is no privacy, how does this play into privacy laws? Oh, my God. Okay. So, let’s just be precise here. It’s not quite, you’re saying there’s no privacy in the blockchain. That’s not quite true. That’s not quite true. So, in the bitcoin system, as is, yes, when you put data on the blockchain, the whole world can see it. When you make transactions, the whole world can see the transactions. The work that I described here, basically, allows you to protect the amounts. Yeah, so, still you would know who paid who, but the amounts will be hidden. There are other blockchains like Zcash, like Monero that actually protect everything. Yeah, they’re completely private. So, in Zcash, for example, you have no idea who’s paying who, what the amounts are, just nothing is hidden. All you can do is you can verify the transactions are valid, but you have no idea what’s in the transaction. So, Zcash actually is a very, very good for fit for business needs if you wanted to transact with your supplier and not even reveal who your supplier is, you know, Zcash is a good way to do it. So, to say that there is no privacy is just not true. Yeah, there are blockchains that do provide a very strong notion of privacy, it’s just that the most widely used ones, bitcoin, ethereum, and so on, at the fundamental area, they don’t provide privacy, but again, you can build things on top of them that will provide privacy as well. So, yeah. So, let’s just make sure we’re precise and accurate there. Great. Well, thank you so much, for your time today, Dan. We hope you all enjoyed this presentation about crypto and blockchains. And if you have further questions, please reach out to our client services team. Have a great rest of your day. Yeah, thanks everyone. This was a lot of fun. And feel free to send us more questions.

You Might Also Like

2 Comments

  • Reply Dixing Xu August 22, 2018 at 5:21 pm

    Hi! I wonder is the ppt available online? Thanks!

  • Reply Beason Curd August 23, 2018 at 4:03 pm

    Blockchain technology is used to store and secure the entire life cycle of an aeronautical parts.

  • Leave a Reply