410 lines
13 KiB
HTML
410 lines
13 KiB
HTML
<!doctype html>
|
|
<html>
|
|
<head>
|
|
<meta charset="utf-8">
|
|
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">
|
|
|
|
<title>reveal.js</title>
|
|
|
|
<link rel="stylesheet" href="dist/reset.css">
|
|
<link rel="stylesheet" href="dist/reveal.css">
|
|
<link rel="stylesheet" href="dist/theme/solarized.css">
|
|
|
|
<!-- Theme used for syntax highlighted code -->
|
|
<link rel="stylesheet" href="plugin/highlight/monokai.css">
|
|
<style>
|
|
.container{
|
|
display: flex;
|
|
}
|
|
.col{
|
|
flex: 1;
|
|
}
|
|
</style>
|
|
</head>
|
|
<body>
|
|
<div class="reveal">
|
|
<div class="slides">
|
|
<section data-markdown>
|
|
<textarea data-template>
|
|
|
|
# Agenda
|
|
* Class Schedule <!-- .element: class="fragment" -->
|
|
* Ice Breaker <!-- .element: class="fragment" -->
|
|
* What you can expect <!-- .element: class="fragment" -->
|
|
* How to get the most out of this <!-- .element: class="fragment" -->
|
|
* Foundational Math <!-- .element: class="fragment" -->
|
|
</textarea>
|
|
</section>
|
|
<section>
|
|
<h2> Class Schedule </h2>
|
|
<div class="container">
|
|
<div class="col">
|
|
<h3 class="fragment">Day 1</h2>
|
|
<ul>
|
|
<li class="fragment">Foundational Math</li>
|
|
<li class="fragment">Elliptic Curve Cryptography</li>
|
|
<li class="fragment">Transaction Parsing</li>
|
|
<li class="fragment">Script</li>
|
|
</ul>
|
|
</div>
|
|
<div class="col">
|
|
<h3 class="fragment">Day 2</h2>
|
|
<ul>
|
|
<li class="fragment">Transaction Construction</li>
|
|
<li class="fragment">Blocks</li>
|
|
<li class="fragment">Simplified Payment Verification</li>
|
|
<li class="fragment">Networking and Segwit</li>
|
|
</ul>
|
|
</div>
|
|
</section>
|
|
<section>
|
|
<h1>Ice Breaker</h1>
|
|
<p class="fragment">How did you get into Bitcoin?</p>
|
|
</section>
|
|
<section>
|
|
<section>
|
|
<h1>What to expect</h1>
|
|
</section>
|
|
<section>
|
|
<h2>Cover Some Material</h2>
|
|
\[
|
|
y^2 = x^3 + ax + b \\
|
|
(x_3, y_3) = (x_1, y_1) + (x_2, y_2) \\
|
|
s = \frac{y_2-y_1}{x_2-x_1} \\
|
|
x_3 = s^2 - x_1 - x_2 \\
|
|
y_3 = s(x_1-x_3) - y_1
|
|
\]
|
|
</section>
|
|
<section>
|
|
<h2>Show an Example</h2>
|
|
What is $(73, 128)+(46, 22)$ in $ y^2 = x^3+7:F_{137}$ ?
|
|
\[s = \frac{y_2-y_1}{x_2-x_1} = \frac{106}{27} = 9 \pmod{137} \\
|
|
x_3 = s^2-x_1-x_2 = 81-73-46 = 99 \pmod {137} \\
|
|
y_3 = s(x_1-x_3)-y_1 = 49 \pmod{137} \\
|
|
(73, 128) + (46, 22) = (99, 49)
|
|
\]
|
|
</section>
|
|
<section>
|
|
<h2>Describe an exercise</h2>
|
|
In the elliptic curve $ y^2 = x^3 + 7:F_{223}$
|
|
<ol>
|
|
<li>Solve the following equations:
|
|
<ul>
|
|
<li> $(192,105) + (17,56)$ </li>
|
|
<li> $(47, 71) + (117,141)$ </li>
|
|
<li> $(143, 98) + (76, 66)$ </li>
|
|
</ul>
|
|
</li>
|
|
<li>Write a unit test for the <code>__add__</code> method</li>
|
|
</ol>
|
|
</section>
|
|
<section>
|
|
<h2>Use Jupyter to Solve</h2>
|
|
<img src="assets/s1-browser.PNG"/>
|
|
</section>
|
|
<section>
|
|
<h1>Do this <a href="#/3/1">again</a></h1>
|
|
</section>
|
|
</section>
|
|
<section>
|
|
<h2> How to get the most out of this seminar </h2>
|
|
<ul>
|
|
<li class="fragment"> <h3>Ask Questions</h3> </li>
|
|
<li class="fragment"> <h3>Ask For Help</h3> </li>
|
|
<li class="fragment"> <h3>Help Your Neighbor</h3> </li>
|
|
<li class="fragment"> <h3>Review Afterwards</h3> </li>
|
|
</ul>
|
|
</section>
|
|
<section>
|
|
<h1>Foundational Math</h1>
|
|
</section>
|
|
<section>
|
|
<h2>Session 1 Objectives</h2>
|
|
<ul>
|
|
<li class="fragment"><strong>Get you comfortable with the math associated with Cryptography</strong>
|
|
<li class="fragment"><strong>Learn Finite Fields</strong>
|
|
<li class="fragment"><strong>Learn Elliptic Curves</strong></li>
|
|
</ul>
|
|
</section>
|
|
<section>
|
|
<section>
|
|
<h2>Finite Fields </h2>
|
|
<ul>
|
|
<li class="fragment"><strong>Finite set of numbers</strong></li>
|
|
<li class="fragment"><strong> Closed under $+, -, \times, \div$ except division by 0</strong></li>
|
|
<li class="fragment"><strong>Used with Elliptic Curves for Cryptography</strong></li>
|
|
<li class="fragment"><strong>Prime fields are the most interesting</strong></li>
|
|
</ul>
|
|
</section>
|
|
<section>
|
|
<h2>Example</h2>
|
|
\[ F_{19} = \{0, 1, 2, ..., 18\} \\
|
|
F_{97} = \{0, 1, 2, ..., 96\} \\
|
|
F_{48947} = \{0, 1, 2, ..., 48946\} \\
|
|
\]
|
|
</section>
|
|
</section>
|
|
<section>
|
|
<section>
|
|
<h2>Addition and Subtraction</h2>
|
|
<p class="fragment"> $F_{19}$ </p>
|
|
<p class="fragment"> $11 + 6 = 17 \pmod{19}$ </p>
|
|
<p class="fragment"> $17 - 6 = 11 \pmod{19}$ </p>
|
|
<p class="fragment"> $18 + 14 = 3 \pmod{19}$ </p>
|
|
<p class="fragment"> $4 - 12 = 11 \pmod{19}$ </p>
|
|
</section>
|
|
<section>
|
|
<h2>Example</h2>
|
|
<p class="fragment"> <code>print((11 + 6) % 19) # 17</code> </p>
|
|
<p class="fragment"> <code>print((17 - 6) % 19) # 11</code> </p>
|
|
<p class="fragment"> <code>print((18 + 14) % 19) # 3</code> </p>
|
|
<p class="fragment"> <code>print((4 - 12) % 19) # 11</code> </p>
|
|
</section>
|
|
<section>
|
|
<h2>Exercise 1, 2 and 3</h2>
|
|
<ol>
|
|
<li> Solve these equations in $F_{31}$ </li>
|
|
<ul>
|
|
<li>$2 + 15 = ?$
|
|
<li>$17 + 21 = ?$
|
|
<li>$29 - 4 = ?$
|
|
<li>$15 - 30 = ?$
|
|
</ul>
|
|
<li> Write the <code>__add__</code> method
|
|
<li> Write the <code>__sub__</code> method
|
|
</ol>
|
|
</section>
|
|
</section>
|
|
<section>
|
|
<section>
|
|
<h2>Multiplication and Exponentiation</h2>
|
|
<p class="fragment"> $F_{19}$ </p>
|
|
<p class="fragment"> $2 \times 4 = 8 \pmod{19}$ </p>
|
|
<p class="fragment"> $7 \times 3 = 2 \pmod{19}$ </p>
|
|
<p class="fragment"> $11^{3} = 1 \pmod{19}$ </p>
|
|
</section>
|
|
<section>
|
|
<h2>Example</h2>
|
|
<p class="fragment"> <code>print(2 * 4 % 19) # 8</code> </p>
|
|
<p class="fragment"> <code>print(7 * 3 % 19) # 2</code> </p>
|
|
<p class="fragment"> <code>print(11 ** 3 % 19) # 1</code> </p>
|
|
<p class="fragment"> <code>print(pow(11, 3, 19)) # 1</code> </p>
|
|
</section>
|
|
<section>
|
|
<h2>Exercise 4, 5, 6, 7 and 8</h2>
|
|
<ol start="4">
|
|
<li> Solve these equations in $F_{31}$ </li>
|
|
<ul>
|
|
<li>$24 \times 19 = ?$
|
|
<li>$17^{3} = ?$
|
|
<li>$5^{5} \times 18 = ?$
|
|
</ul>
|
|
<li> Write a program to calculate $\{0 \cdot k, 1 \cdot k, 2 \cdot k, ..., 30 \cdot k\}$ in $F_{31}$ for some $k$. Notice anything?
|
|
<li> Write the <code>__mul__</code> method
|
|
<li> Write the <code>__pow__</code> method
|
|
<li> Bonus: Write a program to calculate $i^{30}$ in $F_{31}$ for all $i > 0$. Notice anything?
|
|
</ol>
|
|
</section>
|
|
</section>
|
|
<section>
|
|
<section>
|
|
<h2>Division</h2>
|
|
<p class="fragment"> Defined as the inverse of multiplication </p>
|
|
<p class="fragment"> $2 \times 4 = 8 \pmod{19} \implies \frac{8}{2} = 4 \pmod{19}$ </p>
|
|
<p class="fragment"> $7 \times 3 = 2 \pmod{19} \implies \frac{2}{3} = 7 \pmod{19}$ </p>
|
|
<p class="fragment"> $15 \times 4 = 3 \pmod{19} \implies \frac{3}{4} = 15 \pmod{19}$ </p>
|
|
<p class="fragment"> $11 \times 11 = 7 \pmod{19} \implies \frac{7}{11} = 11 \pmod{19}$ </p>
|
|
</section>
|
|
<section>
|
|
<h2>Fermat's Little Theorem</h2>
|
|
<p class="fragment"> $n^{p-1} = 1 \pmod{p}$ for all $n$ if $p$ is prime </p>
|
|
<p class="fragment"> This means we can do division: </p>
|
|
<p class="fragment"> $1/n = n^{-1} = n^{-1} \cdot 1 = n^{-1} \cdot n^{p-1} = n^{p-2} \pmod{p}$</p>
|
|
<p class="fragment"> or $1/n = n^{p-2} \pmod{p}$ </p>
|
|
</section>
|
|
<section>
|
|
<h2>Division</h2>
|
|
<p class="fragment"> $F_{19}$ </p>
|
|
<p class="fragment"> $1/n = n^{p-2} \pmod{p}$ </p>
|
|
<p class="fragment"> $2/3 = 2 \cdot 1/3 = 2 \cdot 3^{19-2} = 7 \pmod{19}$ </p>
|
|
<p class="fragment"> $3/15 = 3 \cdot 1/15 = 3 \cdot 15^{19-2} = 4 \pmod{19}$ </p>
|
|
</section>
|
|
<section>
|
|
<h2>Example</h2>
|
|
<p class="fragment"> <code>print(2 * 3**17 % 19) # 7</code> </p>
|
|
<p class="fragment"> <code>print(2 * pow(3, 17, 19) % 19) # 7</code> </p>
|
|
<p class="fragment"> <code>print(3 * 15**17 % 19) # 4</code> </p>
|
|
<p class="fragment"> <code>print(3 * pow(15, -1, 19) % 19) # 4</code> </p>
|
|
</section>
|
|
<section>
|
|
<h2>Exercise 9 and 10</h2>
|
|
<ol start="9">
|
|
<li> Solve these equations in $F_{31}$ </li>
|
|
<ul>
|
|
<li>$3 / 24 = ?$
|
|
<li>$17^{-3} = ?$
|
|
<li>$4^{-4} \cdot 11 = ?$
|
|
</ul>
|
|
<li> Write the <code>__truediv__</code> method
|
|
</ol>
|
|
</section>
|
|
</section>
|
|
<section>
|
|
<section>
|
|
<h2>Elliptic Curves </h2>
|
|
<ul>
|
|
<li class="fragment"><strong>Equation</strong></li>
|
|
<li class="fragment"><strong>Plotted over some set of numbers</strong></li>
|
|
<li class="fragment"><strong>Useful because of something called <em> point addition</em></strong></li>
|
|
</ul>
|
|
</section>
|
|
<section>
|
|
<div class="container">
|
|
<div class="col fragment">
|
|
Linear $y=mx+b$
|
|
<img src="assets/s1-linear.PNG"/>
|
|
</div>
|
|
<div class="col fragment">
|
|
Quadratic $\scriptsize{y=ax^2+bx+c}$
|
|
<img src="assets/s1-quadratic.PNG"/>
|
|
</div>
|
|
<div class="col fragment">
|
|
Cubic $\tiny{y=ax^3+bx^2+cx+d}$
|
|
<img src="assets/s1-cubic.PNG"/>
|
|
</div>
|
|
</div>
|
|
<div class="container">
|
|
<div class="col fragment">
|
|
Elliptic
|
|
<img src="assets/s1-elliptic-1.PNG"/>
|
|
</div>
|
|
<div class="col fragment">
|
|
$\small{y^2=x^3+ax+b}$
|
|
<img src="assets/s1-elliptic-2.PNG"/>
|
|
</div>
|
|
<div class="col fragment">
|
|
secp256k1 $\scriptsize{y^2=x^3+7}$
|
|
<img src="assets/s1-secp.PNG"/>
|
|
</div>
|
|
</div>
|
|
</section>
|
|
<section>
|
|
<h2>Example</h2>
|
|
Show that $(-1, -1)$ is on the curve $y^2=x^3+5x+7$
|
|
\[ (-1)^2 = (-1)^3 + 5(-1) + 7 = 1
|
|
\]
|
|
<pre>
|
|
<code>
|
|
x, y = -1, -1
|
|
print(y**2 == x**3 + 5 * x + 7) # True
|
|
</code>
|
|
</pre>
|
|
</section>
|
|
<section>
|
|
<h2>Exercise 11 and 12</h2>
|
|
<ol start="11">
|
|
<li> Which of these points are on the curve $y^2=x^3+5x+7$? </li>
|
|
$(-2,4)$, $(3,7)$, $(18,77)$
|
|
<li> Update the <code>__init__</code> method to check that x and y are valid.
|
|
</ol>
|
|
</section>
|
|
<section>
|
|
<h2>Point Addition</h2>
|
|
<img class="r-stretch" src="assets/s1-pointaddition.PNG">
|
|
</section>
|
|
<section>
|
|
<h2>Vertical</h2>
|
|
<img class="r-stretch" src="assets/s1-vertical.PNG">
|
|
</section>
|
|
<section>
|
|
<h2>Group Law for the point at $\infty$</h2>
|
|
<p class="fragment">$y^2=x^3+ax+b$</p>
|
|
<p class="fragment">$(x_1,y_1) = (x_1, y_1) + (\infty, \infty)$</p>
|
|
<p class="fragment">$(x_1,y_1) + (x_1, -y_1) = (\infty, \infty)$</p>
|
|
<p class="fragment">$(\infty, \infty)$ is zero in point addition</p>
|
|
</section>
|
|
<section>
|
|
<h2>Exercise 13</h2>
|
|
<ol start="13">
|
|
<li> Update the <code>__init__</code> and <code>__add__</code> methods to handle $(\infty, \infty)$. (use <code>x=None, y=None</code> to represent the point)</li>
|
|
</ol>
|
|
</section>
|
|
<section>
|
|
<h2>Group Law for when $x_1 \neq x_2$</h2>
|
|
<p class="fragment">$y^2=x^3+ax+b$</p>
|
|
<p class="fragment">$(x_3,y_3) = (x_1, y_1) + (x_2, y_2)$</p>
|
|
<p class="fragment">$s = \frac{y_2-y_1}{x_2-x_1}$</p>
|
|
<p class="fragment">$x_3 = s^2 - x_1 - x_2$ </p>
|
|
<p class="fragment">$y_3 = s(x_1-x_3) - y_1$</p>
|
|
</section>
|
|
<section>
|
|
<h2>Example</h2>
|
|
<p class="fragment">$y^2=x^3+5x+7$</p>
|
|
<p class="fragment">What is $(2,5)+(3,7)$?</p>
|
|
<p class="fragment">$s = \frac{y_2-y_1}{x_2-x_1} = (7-5)/(3-2) = 2$</p>
|
|
<p class="fragment">$x_3 = s^2 - x_1 - x_2 = 4 - 2 - 3 = -1$ </p>
|
|
<p class="fragment">$y_3 = s(x_1-x_3) - y_1 = 2(2-(-1)) - 5 = 1$</p>
|
|
<p class="fragment">$(2,5)+(3,7)=(-1,1)$</p>
|
|
</section>
|
|
<section>
|
|
<h2>Exercise 14 and 15</h2>
|
|
<ol start="14">
|
|
<li> For the curve $y^2=x^3+5x+7$, what is $(2,5) + (-1,-1)$?</li>
|
|
<li> Update the <code>__add__</code> method to handle when $x_1 \neq x_2$</li>
|
|
</ol>
|
|
</section>
|
|
<section>
|
|
<h2>Tangent</h2>
|
|
<img class="r-stretch" src="assets/s1-tangent.PNG">
|
|
</section>
|
|
<section>
|
|
<h2>Group Law for when $P_1 = P_2$</h2>
|
|
<p class="fragment">$y^2=x^3+ax+b$</p>
|
|
<p class="fragment">$(x_3,y_3) = (x_1, y_1) + (x_2, y_2)$</p>
|
|
<p class="fragment">$s = \frac{3x_1^2+a}{2y_1}$</p>
|
|
<p class="fragment">$x_3 = s^2 - 2x_1$ </p>
|
|
<p class="fragment">$y_3 = s(x_1-x_3) - y_1$</p>
|
|
</section>
|
|
<section>
|
|
<h2>Example</h2>
|
|
<p class="fragment">$y^2=x^3+5x+7$</p>
|
|
<p class="fragment">What is $(2,5)+(2,5)$?</p>
|
|
<p class="fragment">$s = \frac{3x_1^2+a}{2y_1} = (3 \cdot 2^2 + 5)/(2 \cdot 5) = 1.7$</p>
|
|
<p class="fragment">$x_3 = s^2 - 2x_1 = 1.72 - 2 \cdot 2 = -1.11$ </p>
|
|
<p class="fragment">$y_3 = s(x_1-x_3) - y_1 = 1.7 \cdot (2+1.11) - 5 = 0.287$</p>
|
|
<p class="fragment">$(2,5)+(2,5)=(-1.11,0.287)$</p>
|
|
</section>
|
|
<section>
|
|
<h2>Exercise 16 and 17</h2>
|
|
<ol start="16">
|
|
<li> For the curve $y^2=x^3+5x+7$, what is $(-1,-1) + (-1,-1)$?</li>
|
|
<li> Update the <code>__add__</code> method to handle when $P_1 = P_2$</li>
|
|
</ol>
|
|
</section>
|
|
</section>
|
|
</div>
|
|
</div>
|
|
|
|
<script src="dist/reveal.js"></script>
|
|
<script src="plugin/notes/notes.js"></script>
|
|
<script src="plugin/markdown/markdown.js"></script>
|
|
<script src="plugin/highlight/highlight.js"></script>
|
|
<script src="plugin/math/math.js"></script>
|
|
<script>
|
|
// More info about initialization & config:
|
|
// - https://revealjs.com/initialization/
|
|
// - https://revealjs.com/config/
|
|
Reveal.initialize({
|
|
hash: true,
|
|
|
|
// Learn about plugins: https://revealjs.com/plugins/
|
|
plugins: [ RevealMarkdown, RevealHighlight, RevealNotes, RevealMath ]
|
|
});
|
|
MathJax.Hub.Config({
|
|
jax: ["input/TeX","output/HTML-CSS"],
|
|
displayAlign: "left"
|
|
});
|
|
</script>
|
|
</body>
|
|
</html>
|