Category: Blockchain

https://cryptobook.nakov.com/mac-and-key-derivation/scrypt

Scrypt (RFC 7914) is a strong cryptographic key-derivation function (KDF). It is memory-intensive, designed to prevent GPU, ASIC and FPGA attacks (highly efficient password cracking hardware).

key = Scrypt(password, salt, N, r, p, derived-key-len)

### Script Parameters
N – iterations count (affects memory and CPU usage), e.g. 16384 or 2048
r – block size (affects memory and CPU usage), e.g. 8
p – parallelism factor (threads to run in parallel – affects the memory, CPU usage), usually 1
password– the input password (8-10 chars minimal length is recommended)
salt – securely-generated random bytes (64 bits minimum, 128 bits recommended)
derived-key-length – how many bytes to generate as output, e.g. 32 bytes (256 bits)

The memory in Scrypt is accessed in strongly dependent order at each step, so the memory access speed is the algorithm’s bottleneck. The memory required to compute Scrypt key derivation is calculated as follows:

Memory required = 128 * N * r * p bytes

Choosing parameters depends on how much you want to wait and what level of security (password cracking resistance) do you want to achieve:

Script hash generator
https://8gwifi.org/scrypt.jsp

$ sudo apt-get install python-dev-is-python3
$ pip3 install scrypt

import pyscript

salt = b'aa1f2d3f4d23ac44e9c5a6c3d8f9ee8c'
passwd = b'p@$Sw0rD~7'
key = pyscript.hash(passwd, salt, 2048, 8, 1, 32)
print("Derived key:", key.hex())

### Litecoin
2011年にリリースされた通貨
scryptをproof of workのアルゴリズムとして使用している

– ブロック生成時間 2.5分
– 通貨総発行量: 2140年までに8400万litecoin
– コンセンサスアルゴリズム: Scrypt proof of work
– 開発者はチャーリーリー
https://github.com/litecoin-project/litecoin

Scrypt proof of workは基本的なハッシュ関数としてscryptを使用しているHashcash証明の証明

### Dogecoin
2013年12月にリリースされたもので、Litecoinのフォークに基づくもの。
支払いやチップの利用を促すもので、通貨発行のスピードを速くしている
– ブロック生成時間 60分
– 通貨総発行量: 2015年までに1000億doge
– コンセンサスアルゴリズム: Scrypt proof of work
– Billy MarkusとJackson Palmerが開発者
https://github.com/dogecoin/dogecoin

トランザクションのコンポーネント
1. バージョン(追加機能)
2. インプット(どのビットコインを使用するか)
3. アウトプット(どのビットコインを移動するか)
4. ロックタイム(トランザクションが有効になるか)

from helper import (
    hash256,
)

class Tx:

    def __init__(self, version, tx_ins, tx_outs, locktime, testnet=False):
        self.version = version
        self.tx_ins = tx_ins 
        self.tx_outs = tx_outs 
        self.locktime = locktime
        self.testnet = testnet

    def __repr__(self):
        tx_ins = ''
        for tx_in in self.tx_ins:
            tx_ins += tx_in.__repr__() + '\n'
        tx_outs = ''
        for tx_out in self.tx_outs:
            tx_outs += tx_out.__repr__() + '\n'
        return 'tx: {}\nversion: {}\ntx_ins:\n{}tx_outs:\nlocktime: {}'.format(
            self.id(),
            self.version,
            tx_ins,
            tx_outs,
            self.locktime,
        )
    
    def id(self):
        return self.hash().hex()

    def hash(self):
        return hash256(self.serialize())[::-1]

idはトランザクションを見つける際にブロックエクスプローラが用いる。リトルエンディアンで返す16進数のhash256

トランザクションのパース

    @classmethod
    def parse(cls, serialization):
        version = serialization[0:4]

変数serializationはバイト配列

↓ ストリームを使用し、readメソッドを使う
read(4)なので、4文字を読み込むという意味

    @classmethod
    def parse(cls, stream):
        serialized_version = stream.read(4)

def encode_base58(s):
    count = 0
    for s in s:
        if c == 0:
            count += 1
        else:
            break
    num = int.from_bytes(s, 'big')
    prefix = '1' * count
    result = ''
    while num > 0:
        num, mod = divmod(num, 58)
        result = BASE58_ALPHABET[mod] + result
    return prefix + result

16進数をバイトに変換し、それをBase58に変換

from ecc import Signature
import helper

s = '7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d'
print(helper.encode_base58(bytes.fromhex(s)))

$ python3 main.py
9MA8fRQrT4u8Zj8ZRd6MAiiyaxb2Y1CMpvVkHQu5hVM6

署名をシリアライズする場合、署名のr, sをエンコードする必要がある。しかし、pointのように圧縮はできない
署名をシリアライズする標準をDERフォーマット(Distinguished Encoding Rules)と呼ぶ。

### DER署名
1. 0x30バイトで開始
2. 署名の残りの長さをエンコード(0x44または0x45)して追加
3. マーカーバイト0x02を追加
4. rをビッグエンディアン整数としてエンコード　ただしrの先頭バイトが0x80以上の時は0x00を付与、長さをrの先頭に追加
5. マーカーバイト0x02を追加
6. sをビッグエンディアン整数としてエンコード　ただしsの先頭バイトが0x80以上の時は0x00を付与、長さをsの先頭に追加

先頭ビットが1の場合は負の数。DERは負のエンコードを許容する。

    def der(self):
        rbin = self.r.to_bytes(32, byteorder='big')
        rbin = rbin.lstrip(b'\x00')
        if rbin[0] & 0x80:
            rbin = b'\x00' + rbin 
        result = bytes([2, len(rbin)]) + rbin
        sbin = self.s.to_bytes(32, byteorder='big')
        sbin = sbin.lstrip(b'\x00')
        if sbin[0] & 0x80:
            sbin = b'\x00' + sbin
        result += bytes([2, len(sbin)]) + sbin
        return bytes([0x30, len(result)]) + result

r, sが定まれば、DERフォーマットが求められる。

from ecc import Signature

r = 0x37206a0610995c58074999cb9767b87af4c4978db68c06e8e6e81d282047a7c6
s = 0x8ca63759c1157ebeaec0d03cecca119fc9a75bf8e6d0fa65c841c8e2738cdaec

sig = Signature(r, s)
print(sig.der().hex())

$ python3 main.py
3045022037206a0610995c58074999cb9767b87af4c4978db68c06e8e6e81d282047a7c60221008ca63759c1157ebeaec0d03cecca119fc9a75bf8e6d0fa65c841c8e2738cdaec

    @classmethod
    def parse(self, sec_bin):
        if sec_bin[0] == 4:
            x = int.from_bytes(sec_bin[1:33], 'big')
            y = int.from_bytes(sec_bin[33:65], 'big')
            return S256Point(x=x, y=y)
        is_even = sec_bin[0] == 2
        x = S256Field(int.from_bytes(sec_bin[1:], 'big'))
        alpha = x**3 + S256Field(B)
        beta = alpha.sqrt()
        if beta.num % 2 == 0:
            even_beta = beta 
            odd_beta = S256Field(P - beta.num)
        else:
            even_beta = S256Field(P - beta.num)
            odd_beta = beta
        if is_even:
            return S256Point(x, even_beta)
        else:
            return S256Point(x, odd_beta)

公開鍵が04, 03, 02かで秘密鍵の点を戻す

SEC圧縮フォーマットは以下の通り

from ecc import S256Point, PrivateKey

p = PrivateKey(5001)
print(p.point.sec(compressed=True).hex())

楕円曲線暗号の公開鍵は(x, y)形式の一つの座標
ECDSA公開鍵をシリアライズする方法はSECフォーマット(Standards for Efficient Cryptography)と呼ばれる

1. プレフィックスバイトは0x04
2. 32バイトのビッグエンディアン整数としてx座標を追加
3. 32バイトのビッグエンディアン整数としてy座標を追加

圧縮SECフォーマットの場合、yが偶数の場合は0x02とし、奇数の場合は0x03とする。

    def sec(self, compressed=True):
        if compressed:
            if self.y.num % 2 == 0:
                return b'\x02' + self.x.num.to_bytes(32, 'big')
            else:
                return b'\x03' + self.x.num.to_bytes(32, 'big')
        else:
            return b'\x04' + self.x.num.to_bytes(32, 'big') + self.y.num.to_bytes(32, 'big')

from ecc import S256Point, PrivateKey

pkey = PrivateKey(5000)
p = pkey.point.sec(compressed=False).hex()
print(p)

$ python3 main.py
04ffe558e388852f0120e46af2d1b370f85854a8eb0841811ece0e3e03d282d57c315dc72890a4f10a1481c031b03b351b0dc79901ca18a00cf009dbdb157a1d10

シリアライズとは、複数の要素を一列に並べる操作や処理のこと。単にシリアライズといった場合には、プログラムの実行状態や複雑なデータ構造などを一つの文字列やバイト列で表現する「直列化」を指すことが多い。

class PrivateKey:

    def __init__(self, secret):
        self.secret = secret 
        self.point = secret * G

    def hex(self):
        return '{:x}'.format(self.secret).zifll(64)

class PrivateKey:

    def __init__(self, secret):
        self.secret = secret 
        self.point = secret * G

    def hex(self):
        return '{:x}'.format(self.secret).zifll(64)

    def sign(self, z):
        k = randint(0, N-1)
        r = (k*G).x.num
        k_inv = pow(k, N-1, N)
        s = (z + r*self.secret) * k_inv % N
        if s > N/2
            s = N - s
        return(r, s)

kがrandintではなく、一意であるようにする。

    def sign(self, z):
        k = self.deterministic_k(z)
        r = (k*G).x.num
        k_inv = pow(k, N-1, N)
        s = (z + r*self.secret) * k_inv % N
        if s > N/2
            s = N - s
        return(r, s)

    def deterministic_k(self, k):
        k = b'\x00' * 32
        v = b'\x01' * 32
        if z > N:
            z -= N
        z_bytes = z.to_bytes(32, 'big')
        secret_bytes = self.secret.to_bytes(32, 'big')
        s256 = hashlib.sha256 
        k = hmac.new(k, v + b'\x00' + secret_bytes + z_bytes, s256).giest()
        v = hmac.new(k, v, s256).digest()
        k = hmac.new(k, v + b'\x01' + secret_bytes + z_bytes, s256).giest()
        v = hmac.new(k, v, s256).digest()
        while True:
            v = hmac.new(k, v, s256).digest()
            candidate = int.from_bytes(v, 'big')
            if candidate >= 1 and candidate < N:
                return candidate 
            k = hmac.new(k, v + b'\x00', s256).giest()
            v = hmac.new(k, v, s256).digest()