1
00:00:03,621 --> 00:00:08,330
Now we're going to talk about another
possible desired quality for puzzles.

2
00:00:08,330 --> 00:00:12,030
Which is for them to have some sort
of socially beneficial intrinsic use.

3
00:00:14,720 --> 00:00:19,150
Now there's a sense in which it seems like
Bitcoin mining is extremely wasteful.

4
00:00:19,150 --> 00:00:23,490
If you recall from previous lectures, we
think that BitCoin mining consumes about

5
00:00:23,490 --> 00:00:27,050
150 to 900 megawatts of power in total.

6
00:00:27,050 --> 00:00:30,980
And this is comparable to
the power output of a really small

7
00:00:30,980 --> 00:00:32,970
hydroelectric power plant, for example.

8
00:00:34,160 --> 00:00:38,760
Now, this mining work is put towards
computing these SHA2 mining puzzles

9
00:00:38,760 --> 00:00:41,570
which don't serve any purpose
outside the BitCoin mining system.

10
00:00:42,640 --> 00:00:46,850
So this raises a very natural question,
is there some way that we could have

11
00:00:46,850 --> 00:00:49,840
a puzzle where computing
the puzzle solution actually

12
00:00:49,840 --> 00:00:54,400
provides some sort of useful benefit
to society while still solving the,

13
00:00:54,400 --> 00:00:57,290
satisfying the basic things
that BitCoin puzzles need.

14
00:00:58,850 --> 00:01:00,970
This would amount to
something like recycling, and

15
00:01:00,970 --> 00:01:05,570
it would have advantages such as lowering
the overall cost of the Bitcoin system,

16
00:01:05,570 --> 00:01:08,150
and potentially reducing
Bitcoin's environmental impact.

17
00:01:11,998 --> 00:01:14,313
Now there are a bunch of
natural candidates for

18
00:01:14,313 --> 00:01:17,090
this that seem like they might work.

19
00:01:17,090 --> 00:01:21,330
The general structure of these
possible candidates are problems that

20
00:01:21,330 --> 00:01:25,090
involve finding a solution in
a potentially very large solution space.

21
00:01:25,090 --> 00:01:26,860
Where the good solutions
that you're looking for

22
00:01:26,860 --> 00:01:29,000
are very sparse within this space.

23
00:01:29,000 --> 00:01:30,750
This is like finding
a needle in a haystack.

24
00:01:31,750 --> 00:01:35,430
Problems of this sort include protein
folding, where the goal is to find

25
00:01:35,430 --> 00:01:39,079
a 3D configuration of a molecule that
has a very low potential energy.

26
00:01:40,365 --> 00:01:45,360
Or searching for aliens and signals from
radio signals in space and looking for

27
00:01:45,360 --> 00:01:48,110
anomalous patterns that might
indicate extraterrestrial life.

28
00:01:49,180 --> 00:01:52,230
Now, for the same reason these seem
like they might work as a BitCoin mining

29
00:01:52,230 --> 00:01:57,084
puzzle, these have been successfully used
in the past as crowd source distributed

30
00:01:57,084 --> 00:02:00,361
computing projects such as,
folding at home and at home.

31
00:02:01,740 --> 00:02:04,420
Now, there are a bunch of challenges
that would have to be solved in order to

32
00:02:04,420 --> 00:02:06,480
use a problem like this in Bitcoin.

33
00:02:07,950 --> 00:02:09,699
In the cases that I
just described at home,

34
00:02:09,699 --> 00:02:13,620
like folding at home and at home,
there's a trusted administrator

35
00:02:13,620 --> 00:02:17,060
of the distributed computing project
that's able to choose which instances of

36
00:02:17,060 --> 00:02:21,330
problems all of the participants in
the network are supposed to be working on.

37
00:02:21,330 --> 00:02:25,160
Now in Bitcoin, there is no trusted
administrator to choose the problems.

38
00:02:25,160 --> 00:02:29,260
So instead, instances of the problem
have to be generated pseudo randomly

39
00:02:29,260 --> 00:02:33,050
from public information, such as the hash
of the last block that was found.

40
00:02:34,800 --> 00:02:36,500
Now, in order for these to be useful,

41
00:02:36,500 --> 00:02:41,080
randomly generated puzzle instances of
this sort would have to still be useful.

42
00:02:41,080 --> 00:02:44,560
And also a randomly generated
puzzle solutions have to be hard.

43
00:02:44,560 --> 00:02:47,910
Now it's not known how to turn any of
these problems into such a puzzle scheme.

44
00:02:49,450 --> 00:02:52,930
Now there is one example that seems to
work and has already been implemented and

45
00:02:52,930 --> 00:02:55,250
is somewhat used in practice
which is called Primecoin.

46
00:02:56,380 --> 00:02:59,680
Now the goal here is to have a mining
puzzle where finding a puzzle solution

47
00:02:59,680 --> 00:03:04,550
involves finding a chain of
very large prime numbers.

48
00:03:04,550 --> 00:03:05,150
In particular,

49
00:03:05,150 --> 00:03:09,640
to find a puzzle solution in Primecoin,
you have to find a Cunningham chain.

50
00:03:09,640 --> 00:03:13,230
A Cunningham chain consists of
a sequence of prime numbers.

51
00:03:13,230 --> 00:03:18,070
P, where each of the P's is
of the form two to the power

52
00:03:18,070 --> 00:03:22,417
of some number times
a constant A plus one.

53
00:03:22,417 --> 00:03:28,060
Now each P in the sequence has to be
a large probable prime, where whether or

54
00:03:28,060 --> 00:03:31,740
not it's a probable prime uses
a probabilistic prime checking algorithm.

55
00:03:31,740 --> 00:03:36,310
And also,
the first instance of the prime number P

56
00:03:36,310 --> 00:03:41,100
has to be a multiple of the hash
function of the metadata for the block,

57
00:03:41,100 --> 00:03:45,150
such as the hash of the previous block,
the Merkle root of the transaction, and

58
00:03:45,150 --> 00:03:47,300
a random nonce value that
miners get to choose.

59
00:03:50,764 --> 00:03:54,133
Now this has been used in
an Altcoin called Primecoin, and

60
00:03:54,133 --> 00:03:56,870
it's actually paid off in some sense.

61
00:03:56,870 --> 00:04:00,410
Many of the largest known
Cunningham chains have come from

62
00:04:00,410 --> 00:04:01,770
miners in the Primecoin network.

63
00:04:01,770 --> 00:04:05,880
Now this is interesting because there
have been distributed computing projects,

64
00:04:05,880 --> 00:04:11,170
such as Primegrid, which have also tried
to find prime number chains of this sort.

65
00:04:11,170 --> 00:04:14,610
This also adds some confidence that this
is truly a hard problem, because a lot of

66
00:04:14,610 --> 00:04:19,120
other people are also interested in
finding solutions to this sort of problem.

67
00:04:19,120 --> 00:04:21,000
So, is this actually useful?

68
00:04:21,000 --> 00:04:22,440
Well, possibly.

69
00:04:22,440 --> 00:04:26,180
There is at least one known use of
Cunningham prime number chains, but

70
00:04:26,180 --> 00:04:29,530
the kind of Cunningham chains that
are found by Primecoin miners are actually

71
00:04:29,530 --> 00:04:31,460
entirely overkill for this application.

72
00:04:31,460 --> 00:04:36,400
Now, there's another approach towards
having a proof of useful work, which

73
00:04:36,400 --> 00:04:40,639
is rather than focusing on the amount of
power, or work output of the network.

74
00:04:41,680 --> 00:04:45,760
We might instead focus on the effect
of investment in Bitcoin mining

75
00:04:45,760 --> 00:04:47,340
infrastructure.

76
00:04:47,340 --> 00:04:51,520
Now just as an estimate, a lot more
than $100 million have been spent on

77
00:04:51,520 --> 00:04:54,570
customized Bitcoin
mining hardware overall.

78
00:04:54,570 --> 00:04:57,590
This includes designing new
Bitcoin mining equipment,

79
00:04:57,590 --> 00:04:59,189
as well as actually manufacturing it.

80
00:05:00,370 --> 00:05:04,510
Now this Bitcoin mining equipment is
very good at computing SHA2 hashes, but

81
00:05:04,510 --> 00:05:07,790
this improvement in technology is
only useful for the Bitcoin network.

82
00:05:07,790 --> 00:05:10,210
It has no other use otherwise.

83
00:05:10,210 --> 00:05:14,640
So the idea is, what if we could design
a puzzle where the investment in newer and

84
00:05:14,640 --> 00:05:18,220
better Bitcoin mining hardware
would itself be useful,

85
00:05:18,220 --> 00:05:21,719
even if the work that's done in the power
output of the network is still wasted?

86
00:05:24,050 --> 00:05:28,110
Now here's one example of
a proposal that has this quality.

87
00:05:28,110 --> 00:05:32,765
It's called Permacoin, and the idea is to
replace Bitcoin mining rigs, which compute

88
00:05:32,765 --> 00:05:37,560
SHA2 hash functions, with storage devices,
such as hard drives and memory.

89
00:05:37,560 --> 00:05:41,450
Now the side effect of Bitcoin miners
investing in better mining equipment

90
00:05:41,450 --> 00:05:45,020
would be a side effect of
having a massively distributed

91
00:05:45,020 --> 00:05:46,790
replicated backup storage system.

92
00:05:49,039 --> 00:05:53,076
Now the way that Permacoin works begins by
assuming that we have a large file F which

93
00:05:53,076 --> 00:05:58,050
everyone knows about, and the goal of the
network is going to be to store this file.

94
00:05:58,050 --> 00:05:59,240
Now for simplicity,

95
00:05:59,240 --> 00:06:03,359
imagine that F is chosen globally by
a trusted dealer at the beginning.

96
00:06:05,340 --> 00:06:08,070
Each user is going to store
a random subset of this file.

97
00:06:10,780 --> 00:06:15,330
A Permacoin is based on an alternative
puzzle that uses storage.

98
00:06:17,400 --> 00:06:21,680
Now, assume that you have the file,
F, broken up into several blocks.

99
00:06:21,680 --> 00:06:25,150
The first part of Permacoin involves
building a Merkle hash tree over each of

100
00:06:25,150 --> 00:06:26,099
the blocks of the file.

101
00:06:28,353 --> 00:06:32,016
Now every user is going to generate
a key pair in order to mine,

102
00:06:32,016 --> 00:06:34,630
which is going to include a public key,
pk.

103
00:06:34,630 --> 00:06:39,170
And they're going to use their public pk,
to pseudorandomly select

104
00:06:39,170 --> 00:06:42,520
a subset of these file segments F that
they're now responsible for storing.

105
00:06:47,837 --> 00:06:52,689
Now for each mining attempt, the miner is
going to select a random nonce value, and

106
00:06:52,689 --> 00:06:57,750
they're going to complete a hash function
h1 that includes the previous block hash,

107
00:06:57,750 --> 00:07:00,130
the Merkle root of transactions.

108
00:07:00,130 --> 00:07:04,730
Their public key PK in the nonce
value that they chose.

109
00:07:09,931 --> 00:07:13,610
Now rather than checking if this
is a puzzle solution immediately,

110
00:07:13,610 --> 00:07:18,257
they first have to fetch k pseudo-randomly
chosen file segments from the subset that

111
00:07:18,257 --> 00:07:21,890
they're storing, which is
determined from that hash value h1.

112
00:07:24,060 --> 00:07:27,940
Now, they compute a second hash value h2,
which includes all of the data

113
00:07:27,940 --> 00:07:32,220
used to compute the first hash, as well as
the actual contents of the file blocks F.

114
00:07:33,640 --> 00:07:37,620
Now from the second has value h2,
it's compared to a target,

115
00:07:37,620 --> 00:07:41,139
in order to see if the puzzle solution
is actually a valid solution.

116
00:07:42,550 --> 00:07:46,670
So the idea here is that the only way
to make attempts at finding a puzzle

117
00:07:46,670 --> 00:07:50,120
solution, and determine if
an attempt is a valid solution,

118
00:07:50,120 --> 00:07:53,170
requires you to store
the random subset of files and

119
00:07:53,170 --> 00:07:55,840
blocks that you were supposed
to based on your public key.

120
00:07:58,240 --> 00:08:01,760
Here's one application of
the Permacoin storage puzzle.

121
00:08:01,760 --> 00:08:05,500
And this involves a kind of subtle
point about BitCoin's incentives.

122
00:08:05,500 --> 00:08:08,600
There's a cost to being
an honest miner in BitCoin.

123
00:08:08,600 --> 00:08:12,160
Remember that honest miners are supposed
to validate every BitCoin transaction

124
00:08:12,160 --> 00:08:14,120
that's included in a block.

125
00:08:14,120 --> 00:08:16,710
However validating a transaction requires

126
00:08:16,710 --> 00:08:20,300
storing the unspent
transaction output's database.

127
00:08:20,300 --> 00:08:24,670
Which at the current time requires
about 200 megabytes of storage.

128
00:08:24,670 --> 00:08:27,630
Now maintaining this unspent
transaction output database,

129
00:08:27,630 --> 00:08:30,560
doesn't help you find puzzle
solutions any faster.

130
00:08:30,560 --> 00:08:32,080
It's a little bit like unpaid overtime.

131
00:08:33,690 --> 00:08:38,040
So the idea would be to use the Permacoin
storage space puzzle in order to reward

132
00:08:38,040 --> 00:08:43,420
miners for actually storing copies of
the unspent transaction output database.

133
00:08:43,420 --> 00:08:47,560
This would reduce the marginal cost of
being honest versus just mining for

134
00:08:47,560 --> 00:08:49,135
the sake of getting all of the rewards.

135
00:08:50,310 --> 00:08:54,500
So to summarize this section, having
a proof-of-useful-work is a very natural

136
00:08:54,500 --> 00:08:58,800
goal, but the challenges to have this
secondary side effect while still

137
00:08:58,800 --> 00:09:01,079
maintaining the essential
security requirements.

138
00:09:02,770 --> 00:09:06,190
There's an argument that any benefit
would have to be a pure public good.

139
00:09:06,190 --> 00:09:09,800
Because if there were a way for
an individual miner to get the benefit of

140
00:09:09,800 --> 00:09:14,050
the useful work they were doing, then this
benefit would also benefit an attacker.

141
00:09:14,050 --> 00:09:18,050
So it would make a tax on the network
subsidized to the same amount that it

142
00:09:18,050 --> 00:09:20,630
would add any secondary
improvement to society.

143
00:09:22,050 --> 00:09:25,910
Now potentially viable approaches
to this include storage and

144
00:09:25,910 --> 00:09:28,650
finding large trains of prime numbers.

145
00:09:28,650 --> 00:09:32,270
But other potential approaches
could be possible as well.

146
00:09:32,270 --> 00:09:36,907
So even though some of these useful
proofs of work have been implemented and

147
00:09:36,907 --> 00:09:42,003
practiced, arguably the benefit to society
so far from these is pretty minimal.