-
Notifications
You must be signed in to change notification settings - Fork 8
/
Copy pathzero_knowledge.html
166 lines (134 loc) · 19.1 KB
/
zero_knowledge.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="">
<title>
Zerocoin Project
</title>
<meta name="description" content="">
<meta name="author" content="">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<!--[if lt IE 9]>
<script src="http://html5shim.googlecode.com/svn/trunk/html5.js"></script>
<![endif]-->
<link href="/media/css/bootstrap.min.css" rel="stylesheet">
<link href="/media/css/bootstrap-responsive.min.css" rel="stylesheet">
<link href="/media/css/style.css" rel="stylesheet">
<link href="/media/css/stickyfooter.css" rel="stylesheet">
<link href="/media/css/nav.css" rel="stylesheet">
<link href="/media/css/typography.css" rel="stylesheet">
<link rel="shortcut icon" href="/media/images/favicon.png">
<link rel="apple-touch-icon" href="/media/images/apple-touch-icon.png">
<link rel="apple-touch-icon" sizes="72x72" href="/media/images/appleimgim-touch-icon-72x72.png">
<link rel="apple-touch-icon" sizes="114x114" href="/media/images/apple-touch-icon-114x114.png">
<script>
var _gaq = [['_setAccount', 'UA-40085231-1'], ['_trackPageview']];
(function(d, t) {
var g = d.createElement(t),
s = d.getElementsByTagName(t)[0];
g.src = '//www.google-analytics.com/ga.js';
s.parentNode.insertBefore(g, s);
}(document, 'script'));
</script>
</head>
<body class="zero_knowledge">
<div id="wrap"> <!-- Wrap for sticky footer -->
<div class="row-fluid">
<div class="span7 offset3">
<div class="navbar">
<a class="btn btn-navbar collapsed" data-align="left" data-toggle="collapse" data-target="#foobar">
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</a>
<div class="nav-collapse" id="foobar">
<ul class="nav">
<li><a href="index">Home</a></li><li><a href="people">People</a></li><li><a href="q_and_a">Q and A</a></li><li><a href="talks_and_press">Papers, Press, etc</a></li></ul>
<div class="pull-right twitter-div" >
<a href="https://twitter.com/zerocoinproject" class="twitter-follow-button" data-show-count="false" data-show-screen-name="false">Follow @zerocoinproject</a>
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0],p=/^http:/.test(d.location)?'http':'https';if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src=p+'://platform.twitter.com/widgets.js';fjs.parentNode.insertBefore(js,fjs);}}(document, 'script', 'twitter-wjs');</script>
</div>
</div>
</div>
</div>
</div>
<div class="row-fluid banner">
<div class="span6 offset3" />
<h1>
<a class="brand" href="index.html">
<img src="/media/images/zq_bw_72.png"/>erocoin Project
</a>
</h1>
</div>
</div>
<div class="row-fluid">
<div class="span6 offset3">
<h1 id="zero-knowledge-proofs">Zero-knowledge proofs</h1>
<p>The core of Zerocoin is a zero-knowledge proof-of-knowledge that a serial number (e.g. 16309) comes from some coin in the block chain. Because the proof reveals nothing but the previously unseen serial number, the mint/ withdrawal of a coin is completely unlinkable to the spending of a coin. This is why the system
is anonymous.</p>
<p>Think of zerocoins as little safes each with a different combination and containing a different coin serial number. The proof of knowledge part means we are proving that we know the serial number inside one of the safes which also entails knowing the safe it’s in and its combination – otherwise we couldn’t possibly show serial number was actually in a safe. The zero-knowledge part means we don’t reveal the last two things. If we revealed which safe the serial number was in, someone could figure out who originally put it in the safe and we’d loose our anonymity. Similarly, if we revealed the combination, we might as well reveal the safe because someone can try the combination on every the safe until they find the one it opens Thus we need to reveal the serial number and prove it actually came from some safe, but keep everything else secret. This seems impossible.</p>
<p>Luckily for us, it actually is possible to prove you know something with out revealing it. For example, you might prove you know a way to visit all the major cities in the United States for some low cost without actually revealing the route. This is due to some very fundamental work by people at the Massachusetts Institute of Technology that won them computer science’s highest honor – the Turing Award. In general, large parts of cryptography involve making the impossible possible and this is no exception. The following example should at least convince you zero-knowledge proofs are possible.</p>
<h2 id="coke-v-pepsi">Coke v Pepsi.</h2>
<h3 id="the-pepsi-challenge">The Pepsi Challenge</h3>
<p>Suppose Alice wants to prove to her friend Bob that she can tell the difference between Pepsi and Coke. The way normal people do this (if they do it at all) is with a bind taste test: Bob gives Alice two identical cups containing Coke and Pepsi. Alice then tastes both of them and tells Bob which is which. If Alice can tell the difference between Coke and Pepsi, see will pass the challenge. Technically this property is called <em>completeness</em> and in Zerocoin it insures that if you have a coin, you can always spend it (a rather important feature of money we think).</p>
<p>If all of this sounds slightly familiar, it should. In fact, the Pepsi Challenge ads from the 70’s did almost exactly this: instead of seeing if people could tell the difference, they gave people two unmarked cups and asked which one people preferred. The experiment is, of course, laughably bad even if your goal is merely to establish a consumer’s preference. One test is not enough to measure preference of or insure accurate differentiability. But 1980’s broadcast television commercials are perhaps not the best medium to ask for statistically significant experimental results (let alone <a href="http://cowbirdsinlove.com/46" title="mad engineer">control groups</a>).</p>
<h3 id="the-iterated-pepsi-challenge">The iterated Pepsi Challenge.</h3>
<p>The problem is Alice’s answer could be a fluke: she could have just gotten lucky and guessed which cup had Pepsi in it. Alice’s proof is not really confidence inspiring. To fix this, Bob makes Alice repeat the experiment many times. In fact, Bob is paranoid and – possibly as a result of owning stock in both Coke and the local gym – makes Alice repeat the experiment 80 times. At that point, Alice’s odds of “getting lucky” are 1 in 2^80 as she’d have to guess correctly each of the 80 times: she stands a better chance of simultaneously winning the lottery and being struck be lighting. Thus Alice can only convince Bob she can tell the difference between Coke and Pepsi if she really can. Technically, this property is called <em>soundness</em> and it’s important in Zerocoin: without it, no one would have any faith that the coins they were receiving were genuine. </p>
<h3 id="the-coke-zero-challenge">The Coke Zero Challenge</h3>
<p>Least you have not realized it yet, Alice and Bob are not actually normal people. In fact, they are cryptographers, an occasionally prickly and paranoid bunch who can do some very useful things but whom you probably don’t want to split your <a href="http://en.wikipedia.org/wiki/Dining_cryptographers_problem" title="dinning cryptographers problem">dinner check</a> with with. Because of her paranoia, Alice wants to make sure all she shows Bob is that she can differentiate between Coke and Pepsi.</p>
<p>In particular, Alice is worried that Bob doesn’t actually know which glass has Coke in it and which has Pepsi – perhaps he lost his sense of taste in an unfortunate <a href="http://en.wikipedia.org/wiki/Patty_and_Selma#Selma_Bouvier">bottle rocket accident</a> – and is using this absurd Pepsi challenge to figure it out. While this may seem harmless, Alice has a vindicative streak and doesn’t want to help Bob out – in part because she suspects Bob’s is making her drink 160 sodas just to make her fat. </p>
<p>To alleviate her concerns, Alice is going to use a Zero-Knowledge proof. Specifically, Alice is going to have Bob secretly flip a coin and either fill both cups with the same soda or one with Pepsi and one with Coke. He will then give these to Alice, who, after tasting both, will tell Bob if the cups contain the same drink or different ones. Again, if Alice can’t tell the difference between Coke and Pepsi, she will have at most a 50/50 chance of getting the answer correct and since Bob makes her do this repeatedly, she can’t easily fake it. This time though, Bob doesn’t learn anything he doesn’t already know since he knows whether the cups contained the same thing or not. Formally, this is the <em>Zero-knowledge</em> property and it is what makes Zerocoin anonymous and gives it it’s name.</p>
<p>What precisely makes it Zero-knowledge gives you some insight into how strange cryptographers are. We(Cryptographers) know this is Zero knowledge because Alice need not know anything about Coke or Pepsi to conduct the proof. Instead, she can simply give Bob a weighted coin and, thus knowing only how Bob fills the cups,Alice can give him the correct answer. The protocol can’t reveal what neither party knows and so it’s zero-knowledge. We call such a thing a <em>simulator</em> and its existence ensures the proof reveals nothing(the fact that Bob will never use a weighted coin ensures this only works in theory, but theory is good enough in this bizarro world).</p>
<p>Strictly speaking, the Coke-Zero-Challenge is what cryptographers call an honest verifier proof, since Bob could do a number of things to deviate from the protocol and learn something. For example, he could swap out the two cups he just poured with ones he found on the side of the road and thus learn if they both contain the same soda or not. However, in this case, Alice better hope Bob follows the protocol since Bob could also swap one of the cups out with potassium cyanide (or Crystal Light). Don’t worry, due to some clever mathematics and the use of hash functions, Zerocoin does not have this problem.</p>
<h2 id="semantic-sugar-free">(Semantic) Sugar Free.</h2>
<p>Note, for those of you who are allergic to complex mathematics, its probably best to stay with the above explanation.</p>
<p>So the above example should convince you that the seemingly impossible – proving something without revealing it – is possible. So how do you do it for real? </p>
<h3 id="graphs">Graphs</h3>
<p>Consider a road map of the United states which simply has all the interstate connections between cities on it (but not the distances or their names). This is a odd map, but it does tell you if you can get from one city to another by going through a third. One might be curious how easy it is to tell if two such maps are actually the same (i.e. all the same cities are connected to-each other, but maybe in different locations and have different names). Clearly, if we leave out a city, people will probably notice (though not the Apple Maps quality control team), but if we move say L.A. to the East Coast, change its name to Gotham, and change all the other city names, it’s actually somewhat hard to tell if it’s the same map (It is the same map here,all the same cities are connected and so you can still get from San Fransisco to San Diego via L.A. Remember, we don’t care about the increase in distances) </p>
<p>Formally, we call these maps <a href="http://en.wikipedia.org/wiki/Graph_(mathematics)">graphs</a>, the cities vertices, and the freeways edges. Telling if two graphs(maps) are the same is the <a href="http://en.wikipedia.org/wiki/Graph_isomorphism">graph isomorphism</a> problem. We call graphs that are the same isomorphic and the mapping between the vertices(cities) in one graph and the verticies in the other graph the isomorphism(In our toy example L.A. -> Gotham). </p>
<table class="wikitable" style="margin: 1em auto 1em auto">
<tbody><tr>
<th>Graph G</th>
<th>Graph H</th>
<th>An isomorphism<br>
between G and H</th>
</tr>
<tr>
<td style="padding-left:2em;padding-right:2em;"><a href="/wiki/File:Graph_isomorphism_a.svg" class="image"><img alt="Graph isomorphism a.svg" src="http://upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Graph_isomorphism_a.svg/100px-Graph_isomorphism_a.svg.png" width="100" height="213" srcset="http://upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Graph_isomorphism_a.svg/150px-Graph_isomorphism_a.svg.png 1.5x, http://upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Graph_isomorphism_a.svg/200px-Graph_isomorphism_a.svg.png 2x"></a></td>
<td style="padding-left:1em;padding-right:1em;"><a href="/wiki/File:Graph_isomorphism_b.svg" class="image"><img alt="Graph isomorphism b.svg" src="http://upload.wikimedia.org/wikipedia/commons/thumb/8/84/Graph_isomorphism_b.svg/210px-Graph_isomorphism_b.svg.png" width="210" height="210" srcset="http://upload.wikimedia.org/wikipedia/commons/thumb/8/84/Graph_isomorphism_b.svg/315px-Graph_isomorphism_b.svg.png 1.5x, http://upload.wikimedia.org/wikipedia/commons/thumb/8/84/Graph_isomorphism_b.svg/420px-Graph_isomorphism_b.svg.png 2x"></a></td>
<td align="center" style="background-color:white;"><i>f</i>(<i>a</i>) = 1
<p><i>f</i>(<i>b</i>) = 6</p>
<p><i>f</i>(<i>c</i>) = 8</p>
<p><i>f</i>(<i>d</i>) = 3</p>
<p><i>f</i>(<i>g</i>) = 5</p>
<p><i>f</i>(<i>h</i>) = 2</p>
<p><i>f</i>(<i>i</i>) = 4</p>
<p><i>f</i>(<i>j</i>) = 7</p>
</td>
</tr>
</tbody></table>
<p>Note, it’s really easy to generate isomorphic graphs, since you can move the cities( known as vertices) around and then you know isomorphism between the two graphs. If we are not the one who scrambled the graph, it is hard to tell if there is such a mapping. This is the mathematical equivalent not of telling the difference between Coke or Pepsi(rather easy), but of telling the difference between Bud Light or Miller Light(or <a href="http://en.wikipedia.org/wiki/Oxbow_(horse)">Oxbow’s</a> last drug test).</p>
<p>Indeed, there is an analogous proof to the Coke-Zero proof: instead of using cups with either the same or different soda, Bob gives Alice random graphs that either are or are not isomorphic to eachother and Alice tells him the answer.</p>
<p>A related problem is proving that you know an isomorphism between two graphs. So lets say Alice wants to convince Bob she knows an isomorphism between two graphs G1 and G2. Alice could tell Bob the mapping (e.g. by pointing out that all we did was rename L.A. to Gotham and move it to the East Coast), but that reveals more than Alice wants to. Instead, Alice will generate a third graph G3 that is isomorphic to either G1 or G2 and sends it to Bob. Bob then flips a coin and asks Alice to reveal the mapping from G1 to G3(e.g. L.A -> Metropolis) or G2 to G3(e.g. Gotham -> Metropolis). Since finding the other mapping is hard, Bob never learns the relation between the vertices in G1 and G2, but he does, after doing this repeatedly (with a new and differently labeled G3 each time), become assured Alice knows both the relation between G1 and G3 and between G3 and G2. If Alice didn’t know both mappings, she’d have to have guessed which one Bob would ask for before generating G3.</p>
<p>Unlike the Coke-Zero challenge, this is a proof of knowledge, since we are showing Alice knows an isomorphism. Formally, this requires an <em>extractor</em>: a fictive all powerful thing that can actually extract what Alice knows from the protocol. In this case, we can imagine the extractor as a rubber mallet: after asking the relation between G3 and G2, Bob whacks Alice over the head with the mallet introducing temporary amnesia. He then asks for the relation between G1 and G3. Even if Alice somehow participated in the proof protocol without knowing the answer, Bob now actually has the answer since he can compose L.A -> Metropolis and Metropolis -> Gotham to get L.A -> Gotham. Thus, we can be sure that the mallet-free version of the protocol Alice either knows or could trivially figure out the answer.</p>
<p>It turns out another hard problem is figuring out if, using only three colors, you can color the vertices on a graph (e.g. cities) so that adjacent ones (e.g cities connected by an interstate segment) don’t have the same color. This is called the three color problem. It turns out Alice can prove she know such a coloring in Zero-Knowledge by randomly picking the three colors she will use and then, after painting the graph with them, telling Bob which colors she used and allowing him to see the color of two connected vertices of his choice. Repeating this assures Bob that 1) only three colors were used and 2) adjacent nodes don’t have the same color. Yet,because fresh colors are used each time, Bob never learns how to color the graph himself. There is a cool demo of this <a href="http://web.mit.edu/~ezyang/Public/graph/svg.html">here</a>. </p>
<p>For reasons we will not go into, it turns out we can use the 3-color Zero
Knowedlge Proof to prove anything we are interested in( see <a href="http://en.wikipedia.org/wiki/NP-complete%20"Non-deterministic%20Polynomial%20time%20Complete%20problems"%20for%20an%20explanation">NP Complete </a>). Proofs that use that trick are only practical to the type of people who spend 20 minutes flipping coins to make sure the NSA isn’t paying for their dinner (yep, cryptographers again). In reality, there are about as useful as an interstate map with no names or distances on it. Thankfully, there are better ideas.</p>
</div>
</div>
<div id="push"></div> <!-- for sticky footer-->
</div> <!-- / sticky footer wrap -->
<div id ="footer" class="row-fluid footer">
<div class="span6 offset3">
<p>Created by <a href="http://hms.isi.jhu.edu/index.php/people/11.html">Ian Miers</a> <a href="https://twitter.com/imichaelmiers">@imichaelmiers</a></p>
</div>
</div>
<script src="//ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<script>window.jQuery || document.write('<script src="/media/js/libs/jquery-1.9.1.min.js">\x3C/script>')</script>
<script src="http://netdna.bootstrapcdn.com/twitter-bootstrap/2.3.2/js/bootstrap.min.js"></script>
<!--[if lt IE 7 ]>
<script src="/media/js/libs/dd_belatedpng.js"></script>
<script>DD_belatedPNG.fix('img, .png_bg'); // Fix any <img> or .png_bg bg-images. Also, please read goo.gl/mZiyb </script>
<![endif]-->
</body>
</html>