Category: Blockchain

secp256k1は
a=0, b=7 すなわち　y**2 = x **3 + 7
p(※有限体の素数prime) = 2**256 – 2**32 – 977
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
n(※群位) = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
すなわち2*256は32バイトで記憶することができ、秘密鍵の記憶が比較的簡単にできるという特徴を持つ

gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
p = 2**256 – 2**32 – 977
print(gy**2 % p == (gx**3 + 7) % p)
$ python3 test.py
True

gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
p = 2**256 - 2**32 - 977
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
x = FieldElement(gx, p)
y = FieldElement(gy, p)
seven = FieldElement(7, p)
zero = FieldElement(0, p)
G = Point(x, y, zero, seven)
print(n*G)

256ビットの数を常に64文字で表示する。

P = 2**256 - 2**32 - 977

class S256Field(FieldElement):

    def __init__(self, num, prime=None):
        super().__init(num=num, prime=P)
    
    def __repr__(self):
        return '{:x}'.format(self.num).zfill(64)

a, bの初期化

class S256Point(Point):

    def __init__(self, x, y, a=None, b=None)
        a, b = S256Field(A), S256Field(B)
        if type(x) == int:
            super().__init__(x=S256Field(x), y=S256Field(y), a=a, b=b)
        else:
            super().__init__(x=x, y=y, a=a, b=b)

群の位数

N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

class S256Point(Point):
    def __rmul__(self, coefficient):
        coef = coefficient % N
        return super().__rmul__(coef)

x, yも定数として定義Gしておく

G = S256Point(
    0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
    0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
)

from ecc import G, N
print(vars(N*G))
$ python3 main.py
{‘a’: 0000000000000000000000000000000000000000000000000000000000000000, ‘b’: 0000000000000000000000000000000000000000000000000000000000000007, ‘x’: None, ‘y’: None}

群とは
-> ある二項演算とその対象となる集合とを合わせて見たときに結合性を伴い単位元と逆元を備えるものをいう。
-> 演算が一つ入った集合で、「結合法則」、「単位元の存在」、「逆元の存在」の３つの条件を満たすものを群という

(a + b)G = ((a + b)%n)G

y**2 = x**3 +7 で(15, 86)

from ecc import FieldElement, Point
 
prime = 223
a = FieldElement(num=0, prime=prime)
b = FieldElement(num=7, prime=prime)
x = FieldElement(num=15, prime=prime)
y = FieldElement(num=86, prime=prime)
p = Point(x, y, a, b)
inf = Point(None, None, a, b)
product = p
count = 1 
while product != inf:
    product += p 
    count += 1
print(count)

どこまで加算すれば無限遠点になるかを計算すれば良いんですね。

from ecc import FieldElement, Point
 
prime = 223
a = FieldElement(num=0, prime=prime)
b = FieldElement(num=7, prime=prime)
x = FieldElement(num=192, prime=prime)
y = FieldElement(num=105, prime=prime)
p = Point(x, y, a, b)
print(vars(p+p))

$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(49), ‘y’: FieldElement_223(71)}

p * p や 2*pとすると、以下のようなエラーとなってしまう。
$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(49), ‘y’: FieldElement_223(71)}
Traceback (most recent call last):
File “/home/vagrant/dev/blockchain/main.py”, line 10, in
print(vars(p*p))
TypeError: unsupported operand type(s) for *: ‘Point’ and ‘Point’

Traceback (most recent call last):
File “/home/vagrant/dev/blockchain/test.py”, line 9, in
print(p+p)
File “/home/vagrant/dev/blockchain/ecc.py”, line 89, in __add__
if self == other and self.y == 0 * self.x:
TypeError: unsupported operand type(s) for *: ‘int’ and ‘FieldElement’

他のパターン
x = FieldElement(num=143, prime=prime)
y = FieldElement(num=98, prime=prime)
$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(64), ‘y’: FieldElement_223(168)}

x = FieldElement(num=47, prime=prime)
y = FieldElement(num=71, prime=prime)
$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(36), ‘y’: FieldElement_223(111)}

4 * (47, 71) の場合
$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(194), ‘y’: FieldElement_223(51)}

8 * (47, 71) の場合
$ python3 main.py
{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(116), ‘y’: FieldElement_223(55)}

from ecc import FieldElement, Point

prime = 223
a = FieldElement(num=0, prime=prime)
b = FieldElement(num=7, prime=prime)
x1 = FieldElement(num=192, prime=prime)
y1 = FieldElement(num=105, prime=prime)
x2 = FieldElement(num=17, prime=prime)
y2 = FieldElement(num=56, prime=prime)
p1 = Point(x1, y1, a, b)
p2 = Point(x2, y2, a, b)
print(p1+p2)
print(vars(p1+p2))

$ python3 main.py

{‘a’: FieldElement_223(0), ‘b’: FieldElement_223(7), ‘x’: FieldElement_223(170), ‘y’: FieldElement_223(142)}

vars()とすることで、オブジェクトの中身を表示します。ここでは、x:170, y:142になります。

(170,142) + (60, 139) = (220, 181)
(47,71) + (17,56) = (215,68)
(143,98) + (76,66) = (47,71)

これをpythonのunittestで記述する

    def test_add(self):
        prime = 223
        a = FieldElement(0, prime)
        b = FieldElement(7, prime)  
        point1 = ((170,142),(47,71),(143,98))
        point2 = ((60,139),(17,56),(76,66))
        result = ((220, 181),(215,68),(47,71))
        for i in range(0, 3):
            x1 = FieldElement(num=point1[i][0], prime=prime)
            y1 = FieldElement(num=point1[i][1], prime=prime)
            x2 = FieldElement(num=point2[i][0], prime=prime)
            y2 = FieldElement(num=point2[i][1], prime=prime)
            x3 = FieldElement(num=result[i][0], prime=prime)
            y3 = FieldElement(num=result[i][1], prime=prime)
            p1 = Point(x1, y1, a, b)
            p2 = Point(x2, y2, a, b)
            p3 = Point(x3, y3, a, b)
            self.assertEqual(p3, (p1+p2))

x1, y1, x2, y2, x3, y3をtuppleにしてforeachでも良かった。

d = {192:105, 17:56, 200:119, 1:193, 42:99}
prime = 223
for x, y in d.items():
    a = (x**3 + 7)%prime
    b = (y**2)%prime
    if a == b:
        print('{}, {} is on the curve'.format(x, y))
    else:
        print('sorry {}, {} is not on the curve'.format(x, y))

$ python3 test.py
192, 105 is on the curve
17, 56 is on the curve
sorry 200, 119 is not on the curve
1, 193 is on the curve
sorry 42, 99 is not on the curve

こうとも書ける

from ecc import FieldElement, Point

a = FieldElement(num=0, prime=223)
b = FieldElement(num=7, prime=223)
x = FieldElement(num=192, prime=223)
y = FieldElement(num=105, prime=223)
p1 = Point(x, y, a, b)
print(p1)

y^2 = x^3 + ax + b

-> yが2乗となっているため、x軸に対して対象となる。
-> ビットコインは y^2 = x^3 + 7 で表されている(secp256k1)

2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 -1を 有限体上で定義された楕円曲線

曲線 y^2 = x^3 + ax + bをclassで表現すると

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
        
from ecc import Point

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

楕円曲線上にあるかの判定

d = {2:4, -1:-1, 18:77, 5:7}
for x, y in d.items():
    try:
        Point(x, y, 5, 7)
        print(x, y)
    except ValueError:
        pass

$ python3 main.py
-1 -1
18 77

### 点の加算
2つの点を演算して、同じ曲線上に3つ目の点を得ることを加算と呼ぶ
垂直、接線の場合は、直線が2点で交差する

無限遠点とは、限りなく遠いところ（無限遠）にある点のこと
点Aに換算すると点Aになる　A + I = A
Pythonでは無限遠点をNoneで表現する
from ecc import Point

p1 = Point(-1, -1, 5, 7)
p2 = Point(-1, 1, 5, 7)
inf = Point(None, None, 5, 7)

print(p1 + inf)
print(inf + p2)
print(p1 + p2)

__init__を修正してaddをoverloadする

class Point:

    def __init__(self, x, y, a, b):
        self.a = a
        self.b = b
        self.x = x
        self.y = y
        if self.x is None and self.y is None:
            return
        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)

    def __add__(self, other):
        if self.a != other.a or self.b != other.b:
            raise TypeError('Point {}, {} are not on the same curve'.format(self, other))
        
        if self.x is None:
            return other
        if other.x is None:
            return self

x1 != x2 の時の加算コーディング

        if self.x != other.x:
            s = (other.y - self.y) / (other.x - self.x)
            x = s**2 - self.x - other.x
            y = s(self.x - x) - self.y
            return self.__class__(x, y, self.a, self.b)

P1 = P2(x座標が同じでy座標が異なる時)

    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)

a = 128
print(a.to_bytes(2, 'big'))
print(a.to_bytes(4, 'big'))

print(int.from_bytes(b'\x00\x80', 'big'))
print(int.from_bytes(b'\x00\x00\x00\x80', 'big'))

import hashlib

class Block():
    def __init__(self, data, prev_hash):
        self.index = 0
        self.nonce = 0
        self.prev_hash = prev_hash
        self.data = data

    def blockhash(self):
        blockheader = str(self.index) + str(self.prev_hash) + str(self.data) + str(self.nonce)
        block_hash = hashlib.sha256(blockheader.encode()).hexdigest()
        return block_hash

    def __str__(self):
        return "Block Hash: " + self.blockhash() + "\nPrevious Hash: " + self.prev_hash + "\nindex: " + str(self.index) + "\nData: " + str(self.data) + "\nNonce: " + str(self.nonce) + "\n--------------"

class Hashchain():
    def __init__(self):
        self.chain = ["0000000000000000000000000000000000000000000000000000000000000000"]

    def add(self, hash):
        self.chain.append(hash)

hashchain = Hashchain()
target = 0x777777 * 2**(8*(0x1e - 0x03))

for i in range(30):
    block = Block("Block " + str(i+1), hashchain.chain[-1])
    block.index = block.index + i + 1
    for n in range(4294967296):
        block.nonce = block.nonce + n
        if int(block.blockhash(), 16) < target:
            print(block)
            hashchain.add(block.blockhash())
            break

簡易的なhash計算

import hashlib

input_text = "satoshi"

for nonce in range(20):
    input_data = input_text + str(nonce)
    hash = hashlib.sha256(input_data.encode("UTF-8")).hexdigest()
    print(input_data + " → " + hash)

ブロックヘッダのdifficulty bitsにハッシュ値の条件が書かれている
0x1e777777 のような形式で記述されている。

# difficulty_bits = 0x1e777777
# exponent = 0x1e
# coefficient = 0x777777

target = 0x777777 * 2**(8*(0x1e - 0x03))
print(target)

target_hex = hex(target)[2:].zfill(64)
print(target_hex)

import hashlib

class Block():
    def __init__(self, data, prev_hash):
        self.index = 0
        self.nonce = 0
        self.prev_hash = prev_hash
        self.data = data

    def blockhash(self):
        blockheader = str(self.index) + str(self.prev_hash) + str(self.data) + str(self.nonce)
        block_hash = hashlib.sha256(blockheader.encode()).hexdigest()
        return block_hash

    def __str__(self):
        return "Block Hash: " + self.blockhash() + "\nPrevious Hash: " + self.prev_hash + "\nindex: " + str(self.index) + "\nData: " + str(self.data) + "\nNonce: " + str(self.nonce) + "\n--------------"

class Hashchain():
    def __init__(self):
        self.chain = ["0000000000000000000000000000000000000000000000000000000000000000"]

    def add(self, hash):
        self.chain.append(hash)

hashchain = Hashchain()
target = 0x777777 * 2**(8*(0x1e - 0x03))

for i in range(30):
    block = Block("Block " + str(i+1), hashchain.chain[-1])
    block.index = block.index + i + 1
    for n in range(4294967296):
        block.nonce = block.nonce + n
        if int(block.blockhash(), 16) < target:
            print(block)
            hashchain.add(block.blockhash())
            break