Category: Bitcoin

### 楕円曲線 定義
y^2 = x^3 + ax + b

class Point:

	def __init__(self, x, y, a, b):
		self.a = a
		self.b = b
		self.x = x
		self.y = y
		if self.y**2 != self.x**3 + a * x + b:
			raise ValueError('({},{}) is not on the curve'.format(x, y))

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y \
			and self.a == other.a and self.b == other.b

	def __ne__(self, other):
		return not (self == other)

p1 = Point(-1, -1, 5, 7)
p1 = Point(-1, -2, 5, 7)

一次方程式
y = ax^2 + bx + c

二次方程式
y = ax^3 + bx^2 + cx + d

楕円曲線は左辺がy^2となっている　
x軸に対して対称のグラフ

ビットコインに用いられる楕円曲線はsecp256k1と呼ばれる
y^2 = x^3 + 7

def on_curve(x, y):
	return y**2 == x**3 + 5*x + 7

print(on_curve(2,4))
print(on_curve(-1,-1))
print(on_curve(18,77))
print(on_curve(5,7))

### 点の加算
曲線上の二つの点を演算して、三つ目の点を得る
第三の点をx軸に対して対称にした点が点の加算の解になる
　L 点の加算は容易に予測できない(同一性、可換性、結合性、可逆性)

なるほど、こういうことをやっとるんか

四則演算(加算、減算、乗算、除算)について閉じている有限体を作るために利用できる道具がモジュロ演算
モジュロ演算：1つの数を別の数で割った余りの数を求めること
(3 – 16) % 12 = 11
(12 + 843) % 60 = 15
(23 + 97) % 60 = 0

pythonのモジュロ演算

print(7 % 3)
print(-27 % 13) 

$ python3 app.py
1
12

有限体上の加算が閉じていることを確認する必要がある
F19 = {0, 1, 2…18}

F57

prime = 57
print((44+33)%prime)
print((9-29)%prime)
print((17+42+49)%prime)
print((52-30-38)%prime)

### 加算と減算

// 省略
	def __add__(self, other):
		if self.prime != other.prime:
			raise TypeError('Cannot add two numbers in different Fields')
		num = (self.num + other.num) % self.prime
		return self.__class__(num, self.prime)

	def __sub__(self, other):
		if self.prime != other.prime:
			raise TypeError('Cannot subtract two numbers in different Fields')
		num = (self.num - other.num) % self.prime
		return self.__class__(num, self.prime)		

a = FieldElement(7, 13)
b = FieldElement(12, 13)
c = FieldElement(6, 13)
print(a+b==c)

### 乗算とべき乗
べき乗は乗算を繰り返し

prime = 97
print(95*45*31 % prime)
print(17*13*19*44 % prime)
print(17**7 * 77**49 % prime)

乗算

	def __mul__(self, other):
		if self.prime != other.prime:
			raise TypeError('Cannot multiply two numbers in different Fields')
		num = (self.num * other.num) % self.prime
		return self.__class__(num, self.prime)

a = FieldElement(3, 13)
b = FieldElement(12, 13)
c = FieldElement(10, 13)
print(a*b==c)

べき乗

	def __pow__(self, exponent):
		num = (self.num ** exponent) % self.prime
		return self.__class__(num, self.prime)

a = FieldElement(3, 13)
b = FieldElement(1, 13)
print(a**3==b)

for prime in (7, 11, 17, 31):
	print([pow(i, prime-1, prime) for i in range(1, prime)])

### 有限体上の除算

prime = 31
print(3*pow(24, prime-2, prime) % prime)
print(pow(17, prime-4, prime))
print(pow(4, prime-5, prime)*11 % prime)

	def __truediv__(self, other):
		if self.prime != other.prime:
			raise TypeError('Cannot divide two numbers in different Fields')
		num = self.num * pow(other.num, self.prime - 2, self.prime) % self.prime
		return self.__class__(num, self.prime)

いきなり難しいな

$ sudo apt install python3-virtualenv
$ virtualenv -p python3 .venv
$ .venv/vin/activate
$ . .venv/bin/activate
$ pip3 install -r requirements.txt

// vagrant上でjupyter notebookを起動する
$ jupyter notebook –no-browser –ip=0.0.0.0

ビットコインは相互に依存するコンポーネントが多数存在する
楕円曲線暗号(ECC)が基礎となる
L 署名アルゴリズム、検証アルゴリズム　… トランザクションの仕組みの中心
　　L シェノア署名、秘匿トランザクションなどの技術

### 有限体
有限の個数からなる集合と演算
集合が閉じている、加法単位元、乗法単位元、加法逆元、乗法逆元

### 有限集合
Fp = {0,1,2,…p-1}
体の位数は素数のべき乗となる

class FieldElement:

	def __init__(self, num, prime):
		if num >= prime or num < 0:
			error = 'Num {} not in field range 0 to {}'.format(
				num, prime - 1)
			raise ValueError(error)
		self.num = num
		self.prime = prime

	def __repr__(self):
		return 'FieldElement_{}({})'.format(self.prime, self.num)

	def __eq__(self, other):
		if other is None:
			return False
		return self.num == other.num and self.prime == other.prime

a = FieldElement(7, 13)
b = FieldElement(6, 13)
print(a==b)
print(a==a)

$ python3 app.py
False
True