Now we're going to talk about another possible desired quality for puzzles, which is for them to have some sort of socially beneficial, intrinsic use. Now, there's a sense in which it seems like Bitcoin mining is extremely wasteful. And if you recall from previous lectures, we think that Bitcoin mining consumes about 150 to 900 megawatts of power in total. And this is comparable to the power output of a really small hydroelectric power plant for example. Now this mining work is put towards computing the SHA-2 mining puzzles, which don't serve any purpose outside the Bitcoin mining system. So this raises a very natural question. Is there some way that we could have a puzzle, where computing the puzzle solution actually provides some sort of useful benefit to society, while still solving the, satisfying the basic things that Bitcoin puzzles need? This would amount to something like recycling and it would advantages such as, lowering the overall cost of the Bitcoin system and potentially reducing Bitcoin's environmental impact. Now, there are a bunch of natural candidates for this that seem like they might work. The general structure of these possible candidates are problems that are involve finding a solution in a potentially very large solution space. Where the good solutions that you're looking for are very sparse within this space. This is like finding a needle in a hay stack. Problems of this sort include protein folding, where the goal is to find a 3D configuration of a molecule that has a very low potential energy. We're searching for aliens and signals from radio signals in space and looking for anomalous patterns that might indicate extraterrestrial life. Now for the same reason these seem like they might work as a Bitcoin mining puzzle, these have been successfully used in the past as crowdsourced distributed computing projects, such as folding at home and SETI at home. Now there are a bunch of challenges that would have to be solved in order to use a problem like this in Bitcoin. In the cases that I just described at home, like folding at home and SETI at home, there's a trusted administrator of the distributed computing project that's able to choose which instances of problems all of the participants in the network are supposed to be working on. Now in Bitcoin, there is no trusted administrator to choose the problems, so instead instances of the problem have to be generated pseudorandomly from public information, such as the hash of the last block that was found. Now, in order for these to be useful, randomly generated puzzle instances of the sort would have to still be useful. And also randomly generated puzzle solutions have to be hard. Now it's not known how to turn any of these problems into such a puzzle scheme. Now there is one example that seems to work and has already been implemented and is somewhat used in practice, which is called Primecoin. Now the goal here is to have a mining puzzle where finding a puzzle solution involves finding a chain of very large prime numbers. In particular, to find a puzzle solution in Primecoin, you have to find a Cunningham chain. Now a Cunningham chain consists of a sequence of prime numbers p, where each of the ps is of the form 2 to the power of some number times a constant a plus 1. Now each p in the sequence has to be a large probable prime where, whether or not it's a probable prime, uses a probabilistic prime checking algorithm. And also, the first instance of the prime number p has to be a multiple of the hash function of the metadata for the blocks, such as the hash for the previous block, the mrkl_root of the transaction and a random nonce value that minors get to choose. Now this has been used in an alt coin called Primecoin, and it's actually paid off in some sense. Many of the largest known Cunningham chains have come from miners in the Primecoin network. This is interesting, because there have been distributing projects such as PrimeGrid which have also tried to find prime number chains of this sort. This also adds some confidence that this is truly a hard problem because a lot of other people are also interested in finding solutions to this sort of problem. So is this actually useful? Well possibly. There is at least one known use of Cunningham prime numbered chains, but the kind of Cunningham chains that are found by Primecoin miners actually entirely overkill for this application. Now, there's another approach towards having a proof of useful work which is rather than focusing on the amount of power or workout put of the network, we might instead focus on the effect investment in Bitcoin mining infrastructure. Now just as an estimate, a lot more than $100 million dollars have been spent on customized Bitcoin mining hardware overall. This includes designing new Bitcoin mining equipment, as well as actually manufacturing it. Now this Bitcoin mining equipment is very good at computing SHA-2 hashes, but this improvement in technology is only useful for the Bitcoin network, it has no other use otherwise. So the idea is what if we could design a puzzle where the investment in newer and better Bitcoin mining hardware would itself be useful. Even if the work that's done and the power output is still listed. Now, here's one example of a proposal that has this quality. It's called Permacoin, and the idea is to replace Bitcoin mining rigs, which compute SHA-2 hash functions, with storage devices such as hard drives and memory. Now, the side effect of Bitcoin miners investing in better mining equipment would be a side effect of having a massively distributed, replicated backup storage system. The way that Permacoin works, it begins by assuming we have a large file F, which everyone knows about. And the goal of the network is going to be to store this file. For simplicity, imagine that F is chosen globally by a trusted dealer at the beginning. Each user is going to store a random subset of this file. Now Permacoin is based on a alternative puzzle that uses storage. Now assume that you have the file F broken up into several blocks. The first part of Permacoin involves building a Merkel hash tree over each of the blocks of the file Now every user is going to generate a key pair in order to mine, which is going to include a public key, PK. And they're going to use their public PK to pseudo-randomly select a subset of these file segments F that they're now responsible for storing. Now for each mining attempt, the miner is going to select a random nonce value and their going to compute a hash function h1 that includes the previous block hash, the Merkel rate of transactions, their public key, PK, and the nonce value that they chose. Now rather than checking if this is a puzzle solution immediately, they first have to fetch K psuedo-randomly chosen file segments from the subset that they are storing, which is determined from that hash value h1. Now they compute a second hash value, h2, which includes all of the data used to compute the first has as well as the actually contents of the file blocks, F. Now from the second hash value, h2, it's compared to a target in order to see if the puzzle solution is actually a valid solution. So the idea here is that the only way to make attempts at finding a puzzle solution, and determine if an attempt is a valid puzzle solution, requires you to store the random subset of files blocks that you were supposed to based on your public key. Here's one application of the Permacoin storage puzzle. And this involves kind of a subtle point about Bitcoin's incentives. And there is a cost to being an honest miner in Bitcoin, remember honest miners are supposed to validate every Bitcoin transaction that's included in a block. However validating every transaction involves storing the unspent transaction database, which at the current time requires about 200 MB of storage. Now maintaining this unspent transaction output database, doesn't help you find puzzle solutions any faster. It's a little bit like unpaid overtime. So the idea would be to use the Permacoin storage space puzzle in order to reward miners for actually storing copies of the unspent transaction output database. This would reduce the marginal cost of being honest versus just mining for the sake of getting all of the rewards. So, to summarize this section, having a proof of useful work is a very natural goal. But the challenge is to have this secondary side effect while still maintaining the central security requirements. There's an argument that any benefit would have to be a pure public good because if there were a way for an individual miner to get the benefit of the useful work they were doing, then this benefit would also benefit an attacker. So it would make attacks on the network subsidized tO the same amount that it would add any secondary improvement to society. Now, potentially viable approaches to this include storage and finding large trains of prime numbers. But other potential approaches could be possible as well. So even though some of these useful proofs of work have been implemented in practice, arguably the benefit to society so far from these Is pretty minimal.
