1 00:00:02,174 --> 00:00:05,600 We're going to start by talking about ASIC-resistant mining puzzles. 2 00:00:05,600 --> 00:00:06,390 These are, far and away, 3 00:00:06,390 --> 00:00:09,740 the most widely discussed and sought-after alternative mining puzzles. 4 00:00:11,560 --> 00:00:15,860 There are several reasons why we might want an ASIC-resistant mining puzzle. 5 00:00:15,860 --> 00:00:18,260 If you recall from previous lectures, 6 00:00:18,260 --> 00:00:22,529 Bitcoin mining used to be done using ordinary computers like CPUs and GPUs. 7 00:00:23,630 --> 00:00:27,460 Then eventually move towards customized FPGA devices. 8 00:00:27,460 --> 00:00:32,600 And now mining is mostly conducted using very powerful optimized ASIC chips. 9 00:00:32,600 --> 00:00:36,760 Which are so vastly more effective than general purpose computing equipment 10 00:00:36,760 --> 00:00:39,890 that it doesn't even pay off to use an ordinary computer or 11 00:00:39,890 --> 00:00:42,630 a very old generation of mining equipment. 12 00:00:42,630 --> 00:00:43,810 But this is too bad, in a way. 13 00:00:43,810 --> 00:00:48,160 Because it used to be very appealing that ordinary users could use 14 00:00:48,160 --> 00:00:51,740 Mind Bit coins out of midair just by leaving their computers on overnight. 15 00:00:51,740 --> 00:00:52,980 A computer that they already had. 16 00:00:54,310 --> 00:00:55,140 This was really good for 17 00:00:55,140 --> 00:00:58,370 a low barrier to entry because it gave a compelling reason for 18 00:00:58,370 --> 00:01:02,110 ordinary users around the world to joining the Bit Coin network and participate. 19 00:01:03,680 --> 00:01:06,760 So wouldn't it be nice if we could go back to the good old days when it was 20 00:01:06,760 --> 00:01:11,370 possible to mine Bitcoins using ordinary, general-purpose computing equipment? 21 00:01:11,370 --> 00:01:15,810 So the approach to go back to this is to come up with a puzzle that reduces the gap 22 00:01:15,810 --> 00:01:19,645 between the most the most cost-effective customized hardware and 23 00:01:19,645 --> 00:01:22,430 general-purpose equipment that ordinary people already have. 24 00:01:23,460 --> 00:01:25,920 A separate goal is to try to prevent 25 00:01:25,920 --> 00:01:30,160 the very large ASIC manufactures from dominating the bitcoin mining game. 26 00:01:31,250 --> 00:01:33,850 There are only a few companies that are able to produce 27 00:01:33,850 --> 00:01:38,270 large semi-conductor fabrication, in order to actually produce the ASICs. 28 00:01:38,270 --> 00:01:40,550 So this represents a sort of consolidation of power. 29 00:01:40,550 --> 00:01:44,350 Now, a lot of customers of bitcoin mining ASICs 30 00:01:44,350 --> 00:01:48,440 have this concern that the manufacturers are going to delay the shipment of their 31 00:01:48,440 --> 00:01:51,490 mining devices in order for them, the manufacturers, 32 00:01:51,490 --> 00:01:54,960 to use the mining devices themselves in order to use them for 33 00:01:54,960 --> 00:01:58,360 their own benefit to get their own rewards at the expense of their customers. 34 00:01:59,490 --> 00:02:02,610 Another concern is that if there is some breakthrough and 35 00:02:02,610 --> 00:02:05,240 there is a vastly more efficient ASIC design, 36 00:02:05,240 --> 00:02:09,320 whoever comes up with that design might keep it a trade secret to themselves and 37 00:02:09,320 --> 00:02:13,350 use it to build their own very powerful industrial mining center. 38 00:02:13,350 --> 00:02:14,970 Then they would be able to dominate the network. 39 00:02:16,260 --> 00:02:19,140 So the approach here might be to build a puzzle that 40 00:02:19,140 --> 00:02:23,054 reduces the gap between potential future hardware ASIC designs and 41 00:02:23,054 --> 00:02:27,377 the ASICs that we already have which are largely distributed to ASIC mining 42 00:02:27,377 --> 00:02:34,289 customers We're going to start by talking 43 00:02:34,289 --> 00:02:38,600 about the most widely used approach towards having an ASIC resistant puzzle. 44 00:02:38,600 --> 00:02:41,060 This is called a memory hard puzzle. 45 00:02:41,060 --> 00:02:42,610 Now the premise here is fairly simple, 46 00:02:42,610 --> 00:02:46,430 and it's based on a well known phenomena since the 80s about 47 00:02:46,430 --> 00:02:49,840 the change in the performance of computing equipment over time. 48 00:02:52,380 --> 00:02:53,320 Since the 80s, 49 00:02:53,320 --> 00:02:57,970 the performance of processing has increased at an exponential rate. 50 00:02:57,970 --> 00:03:00,070 You've probably heard of this referred to as Moore's Law. 51 00:03:00,070 --> 00:03:02,780 Now the performance of memory and 52 00:03:02,780 --> 00:03:05,040 storage have also increased at an exponential rate. 53 00:03:05,040 --> 00:03:09,890 But this rate is much slower, much lower rate than that for processors. 54 00:03:09,890 --> 00:03:13,000 There's a performance gap between the mos efficient processors and 55 00:03:13,000 --> 00:03:14,940 the most efficient memory and storage. 56 00:03:14,940 --> 00:03:17,470 And this gap actually grows over time. 57 00:03:17,470 --> 00:03:21,620 This means that if we had a puzzle that requires lots of memory to compute, 58 00:03:21,620 --> 00:03:24,990 rather than just processing circuits, 59 00:03:24,990 --> 00:03:29,250 then the potential improvement from next generation's optimized hardware and 60 00:03:29,250 --> 00:03:31,990 the current generation of optimized hardware, or even general purpose 61 00:03:31,990 --> 00:03:34,990 computing equipment would be much lower and that's what we want. 62 00:03:37,430 --> 00:03:42,250 So, we're going to talk now about the most popular instance of a memory hard puzzle. 63 00:03:43,450 --> 00:03:44,410 This is called scrypt. 64 00:03:45,505 --> 00:03:48,048 Scrypt's actually a memory hard hash function. 65 00:03:48,048 --> 00:03:51,580 And an scrypt based mining puzzle is the same as the BitCoin mining puzzle, 66 00:03:51,580 --> 00:03:54,450 just replacing the SHA2 hash with the scrypt hash. 67 00:03:56,780 --> 00:04:01,040 Scrypt is memory hard in that it has a constant time memory tradeoff. 68 00:04:01,040 --> 00:04:05,050 This means that the hash can be computed using a fixed amount of memory. 69 00:04:05,050 --> 00:04:07,520 It's possible to compute it using less memory, but doing so 70 00:04:07,520 --> 00:04:09,759 increases the amount of time that it takes to compute. 71 00:04:11,430 --> 00:04:14,110 Now as I mentioned, this puzzle is actually widely used in Bitcoin 72 00:04:14,110 --> 00:04:18,790 alternatives, including the second most popular crypto currency, 73 00:04:18,790 --> 00:04:20,800 Litecoin, and a variety of others. 74 00:04:22,310 --> 00:04:26,200 One thing that is to scrypt's advantage is that this hash function is also used in 75 00:04:26,200 --> 00:04:29,720 other places in security, especially password hashing. 76 00:04:29,720 --> 00:04:33,050 Which has similar goals to ASIC resistance in Bitcoin mining. 77 00:04:33,050 --> 00:04:35,850 This gives extra confidence that if there are security problems with 78 00:04:35,850 --> 00:04:36,710 the hash function. 79 00:04:36,710 --> 00:04:38,730 then other people are looking at them and might find them. 80 00:04:40,470 --> 00:04:43,220 Now the basic way that scrypt works goes in two steps. 81 00:04:43,220 --> 00:04:46,740 The first step involves filling a large block of random access memory with 82 00:04:46,740 --> 00:04:48,010 random values. 83 00:04:48,010 --> 00:04:51,600 And the second step involves reading from this memory in a random order. 84 00:04:51,600 --> 00:04:54,110 Now I'm going to give a detailed illustration of just how 85 00:04:54,110 --> 00:04:56,580 the scrypt hash function works. 86 00:04:56,580 --> 00:04:59,710 Now the goal here is going to be to compute the scrypt hash function of 87 00:04:59,710 --> 00:05:00,970 an input string x. 88 00:05:02,010 --> 00:05:03,700 Now this going to be the first step and 89 00:05:03,700 --> 00:05:08,510 the goal is to fill a block of memory containing n cells. 90 00:05:08,510 --> 00:05:09,490 With random values. 91 00:05:10,530 --> 00:05:11,120 Here N is 36. 92 00:05:11,120 --> 00:05:16,480 Now these values are going to be filled in, in sequential order. 93 00:05:16,480 --> 00:05:21,320 The first value, V1, is simply the hash of the input 94 00:05:21,320 --> 00:05:25,440 string x where the hash function H is an ordinary hash function like SHA2. 95 00:05:26,540 --> 00:05:34,790 Now the second value of v2 is the hasha 2 of the previous value, v1. 96 00:05:34,790 --> 00:05:39,770 This is the same as the hash function applied to the input string x twice. 97 00:05:41,540 --> 00:05:46,650 And so on, the third value of v3 is the hash function applied to the input value. 98 00:05:46,650 --> 00:05:47,430 X three times. 99 00:05:49,910 --> 00:05:51,870 And so on, after n iterations, 100 00:05:51,870 --> 00:05:54,860 all n memory cells are filled up with pseudo random values. 101 00:05:54,860 --> 00:05:59,460 And the last value is the same as the hash function H applied to x, n times. 102 00:06:03,590 --> 00:06:07,699 Now in the next step, we're going to read back the values of memory in random order. 103 00:06:09,120 --> 00:06:13,180 Now we're going to begin by having an accumulator value, A, which involves 104 00:06:13,180 --> 00:06:16,180 computing the hash function, H, one more time on the last value. 105 00:06:18,080 --> 00:06:22,120 Now for n iterations we're going to use the current value of the accumulator, 106 00:06:22,120 --> 00:06:28,210 A, to pick an index, I, out of these n potential memory cells. 107 00:06:28,210 --> 00:06:34,110 They're going to read that value of memory xor with the current accumulator value A. 108 00:06:34,110 --> 00:06:36,240 Take the hash h once more of this value, 109 00:06:36,240 --> 00:06:39,180 and replace the accumulator's value with this updated value. 110 00:06:41,540 --> 00:06:43,210 Now after, n iterations, 111 00:06:43,210 --> 00:06:46,880 the final value of the accumulator a is the output of this function. 112 00:06:51,201 --> 00:06:55,200 Now let me explain the intuition for why this scrypt hash function is memory hard. 113 00:06:56,500 --> 00:07:00,930 Now you can compute this by using the N memory cells as described just before. 114 00:07:00,930 --> 00:07:05,280 It's also possible to compute the scrypt hash value using less memory. 115 00:07:05,280 --> 00:07:08,049 Suppose you wanted to cut down the amount of memory you needed by half. 116 00:07:09,100 --> 00:07:12,680 You could do, do this by only storing every other value V in the table. 117 00:07:13,680 --> 00:07:16,190 Only the odd values in this case. 118 00:07:16,190 --> 00:07:20,790 So, what happens if you need to access one of the even numbered values of v which you 119 00:07:20,790 --> 00:07:21,690 aren't storing, 120 00:07:21,690 --> 00:07:25,280 well you need to compute it from the values of v that you are storing. 121 00:07:25,280 --> 00:07:29,020 Now, you can always compute v i. 122 00:07:29,020 --> 00:07:32,400 By computing the hash H of VI minus one. 123 00:07:33,690 --> 00:07:34,490 Now this works and 124 00:07:34,490 --> 00:07:37,860 you got away with using less memory, but you had to compute an extra value for H. 125 00:07:39,560 --> 00:07:41,570 Now this intuition holds up. 126 00:07:41,570 --> 00:07:45,050 On average if you wanted to reduce the amount of memory by half, you would 127 00:07:45,050 --> 00:07:49,780 have to reduce the amount of computation cycles you need by one and a half. 128 00:07:49,780 --> 00:07:50,310 And so on. 129 00:07:53,496 --> 00:07:56,361 Now to talk a little bit about scrypt use in practice, 130 00:07:56,361 --> 00:07:59,310 there are a couple of disadvantages. 131 00:07:59,310 --> 00:08:02,360 One is that even though it has this disadvantage of being memory hard to 132 00:08:02,360 --> 00:08:08,060 compute, the scrypt-based mining puzzle also requires an amount of memory and 133 00:08:08,060 --> 00:08:11,120 end cycles in order to check a proof of work puzzle solution. 134 00:08:12,430 --> 00:08:15,400 This puts a constraint on how large you can set N, in other words, 135 00:08:15,400 --> 00:08:16,730 how memory hard you can make. 136 00:08:18,160 --> 00:08:21,790 Now, a good question is, is this memory puzzle actually ASIC resistant? 137 00:08:23,290 --> 00:08:24,470 And there's some uncertainty here. 138 00:08:25,540 --> 00:08:28,989 A script ASICs are already available, at least the first generation of these. 139 00:08:30,040 --> 00:08:33,010 And they are at least somewhat faster than what you can do with general purpose 140 00:08:33,010 --> 00:08:35,120 computing equipment like CPUs and GPUs. 141 00:08:35,120 --> 00:08:40,120 There are several companies competing to make faster scrypt ASIC's and 142 00:08:40,120 --> 00:08:43,950 it's unclear how much better this performance gap will be able to get. 143 00:08:43,950 --> 00:08:48,900 There's some concern that in the alt coins that currently use that scrypt base mining 144 00:08:48,900 --> 00:08:51,500 puzzles that the parameter N hasn't been set correctly and 145 00:08:51,500 --> 00:08:55,000 this is one of the factors Leading to ASIC's arriving. 146 00:08:57,140 --> 00:09:00,960 Now this general approach of having a memory hard hash function is good because, 147 00:09:00,960 --> 00:09:04,930 as I mentioned, a scrypt is used in other applications like password hashing. 148 00:09:04,930 --> 00:09:09,170 And so if there's any future improvements in password hashing, then memory hard 149 00:09:09,170 --> 00:09:12,900 mining puzzles would be able to use these new password hashing functions and 150 00:09:12,900 --> 00:09:14,679 be able to achieve the desired effect. 151 00:09:17,250 --> 00:09:20,560 now I'm going to talk about another approach to having a memory hard 152 00:09:20,560 --> 00:09:21,700 proof of work mining puzzle. 153 00:09:23,530 --> 00:09:25,890 This puzzle is called cuckoo has cycles. 154 00:09:25,890 --> 00:09:28,990 And the main advantage this has over scrypt is that it doesn't require any 155 00:09:28,990 --> 00:09:31,210 random access memory to check a puzzle solution. 156 00:09:33,300 --> 00:09:35,970 Now, we're going to look at how this works, which involves, for 157 00:09:35,970 --> 00:09:39,360 every mining attempt, we're going to start with a potential solution x, 158 00:09:39,360 --> 00:09:40,890 which you can think of as a random string. 159 00:09:40,890 --> 00:09:44,270 And we're going to use the following procedure to determine whether or 160 00:09:44,270 --> 00:09:46,630 not x is a puzzle solution. 161 00:09:46,630 --> 00:09:51,160 For the first step, we're going to select the e pseudo-random edges in this graph. 162 00:09:52,540 --> 00:09:56,560 Now, for each edge, we're going to pick a random 163 00:09:56,560 --> 00:10:01,750 node from the top set of nodes and a random node from the bottom set of nodes. 164 00:10:01,750 --> 00:10:05,780 Now, we do this by computing hash values using, again, the underlying hash value H, 165 00:10:05,780 --> 00:10:07,850 which can just be an ordinary hash function. 166 00:10:09,970 --> 00:10:12,850 Now, the edges are filled in. 167 00:10:12,850 --> 00:10:14,340 In the graph as illustrated below. 168 00:10:21,510 --> 00:10:24,699 Once the graph's completed, we want to determine whether or 169 00:10:24,699 --> 00:10:26,920 not there's a cycle in the graph of size K. 170 00:10:27,960 --> 00:10:32,290 Now a cycle is a set of edges such that if you align the edges tip to tip. 171 00:10:32,290 --> 00:10:34,840 where tip to end then they form a complete cycle. 172 00:10:36,120 --> 00:10:39,320 So here's what a cycle of size 4 would look like in this illustrated graph. 173 00:10:41,580 --> 00:10:43,690 Now K is another parameter of the puzzle. 174 00:10:45,030 --> 00:10:49,710 If the graph determined by input X has a cycle of size K then 175 00:10:49,710 --> 00:10:54,150 we say that this has a solution and we just output the input value X 176 00:10:54,150 --> 00:10:58,020 as well as the evidence that there was a cycle, so the K indexes of the edges. 177 00:10:59,400 --> 00:11:02,120 Now, it's not as intuitive why this is a memory hard function. 178 00:11:03,833 --> 00:11:07,368 But the explanation is that finding cycles in graphs is a fairly well 179 00:11:07,368 --> 00:11:10,097 studied problem, and the best known algorithms for 180 00:11:10,097 --> 00:11:12,590 doing this do require a large amount of memory. 181 00:11:13,920 --> 00:11:17,730 Now what is really clear to see is that this puzzle is very easy to check. 182 00:11:17,730 --> 00:11:20,888 The only thing you need to do in order to check the puzzle solution is to 183 00:11:20,888 --> 00:11:24,020 re-compute what the edge end points would be for 184 00:11:24,020 --> 00:11:27,710 each of the K edges provided, using the input value X. 185 00:11:27,710 --> 00:11:31,580 You only have to compute K hash functions and no random access memory is required. 186 00:11:32,790 --> 00:11:36,120 Now, there are even more approaches towards building ASIC-resistant 187 00:11:36,120 --> 00:11:37,320 mining puzzles. 188 00:11:37,320 --> 00:11:40,460 I'm only going to describe these really briefly. 189 00:11:40,460 --> 00:11:44,040 One is to simply build much more complicated functions than the ones that 190 00:11:44,040 --> 00:11:46,020 we've talked about so far. 191 00:11:46,020 --> 00:11:50,300 One example is the mining puzzle based on the X11 hash function, 192 00:11:50,300 --> 00:11:53,829 which is simply 11 well known hash functions strung together in a sequence. 193 00:11:55,950 --> 00:11:59,830 Another approach is to have a mining puzzle that's a moving target. 194 00:11:59,830 --> 00:12:02,950 Here you would have a mining puzzle that actually changes all together, 195 00:12:02,950 --> 00:12:04,510 every so often. 196 00:12:04,510 --> 00:12:09,230 This means that optimized mining hardware for one puzzle probably wouldn't be good 197 00:12:09,230 --> 00:12:12,370 at solving all of the puzzles, even after the puzzle changes. 198 00:12:12,370 --> 00:12:15,220 And customize mining hardware that's only good at solving 199 00:12:15,220 --> 00:12:19,400 one instance of the puzzle, won't be very useful once the puzzle does change. 200 00:12:19,400 --> 00:12:23,680 You know it's unclear exactly how we would change the puzzle every so 201 00:12:23,680 --> 00:12:27,860 often in order to maintain the security requirements that we need. 202 00:12:27,860 --> 00:12:31,310 Now there's a counter argument that says that there's really no point in trying to 203 00:12:31,310 --> 00:12:32,840 make an ASIC resistant puzzle, 204 00:12:32,840 --> 00:12:36,620 because the SHA2 based mining puzzle that we already have is already good enough. 205 00:12:37,760 --> 00:12:40,640 Now, the SHA2 circuit is pretty well understood. 206 00:12:40,640 --> 00:12:44,160 We have a good idea of what's the optimal way of computing SHA2. 207 00:12:45,240 --> 00:12:48,020 As a result Bitcoin mining ASICs aren't changing very much and 208 00:12:48,020 --> 00:12:51,710 it seems unlikely that there's going to be a breakthrough in computing these 209 00:12:51,710 --> 00:12:53,510 proof of work solutions any faster. 210 00:12:54,760 --> 00:12:56,000 Now, even as it is today, 211 00:12:57,640 --> 00:13:02,320 mining ASICs consists of multiple copies of the same basic SHA2 circuit. 212 00:13:02,320 --> 00:13:05,980 And the only difference between the largest ASICs and the smallest- or 213 00:13:05,980 --> 00:13:10,560 cheapest- ASICs, is that they have more copies of the same, essential circuit. 214 00:13:10,560 --> 00:13:13,910 This means that even the biggest mining ASICs are only a little bit 215 00:13:13,910 --> 00:13:17,460 more cost effective than the smaller ASICs. 216 00:13:17,460 --> 00:13:20,632 They compute puzzle solutions faster, but they're also more expensive.