Category: Bitcoin

ScriptPubKey
55 OP_5
93 OP_ADD
59 OP_9
87 OP_EQUAL

ScriptSig
54 OP_4

76 OP_DUP
76 OP_DUP
95 OP_MUL
93 OP_ADD
56 OP_6
87 OP_EQUAL

52

from script import Script
script_pubkey = Script([0x76, 0x76, 0x95, 0x93, 0x56, 0x87])
script_sig = Script([0x52])
combined_script = script_sig + script_pubkey
print(combined_script.evaluate(0))

OP_CODEが異なるような気が…
OP_MULはビットコインネットワークで無効化されている

6e OP_2DUP
87 OP_EQUAL
91 OP_NOT
69 OP_VERIFY
a7 OP_SHA1
7c OP_SWAP
a7 OP_SHA1
87 OP_EQUAL

from script import Script
script_pubkey = Script([0x6e, 0x87, 0x91, 0x69, 0xa7, 0x7c, 0xa7, 0x87])
c1 = '255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f576964746820\
32203020522f4865696768742033203020522f547970652034203020522f537562747970652035\
203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e67\
74682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8\
fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1ff\
fe017f46dc93a6b67e013b029aaa1db2560b45ca67d688c7f84b8c4c791fe02b3df614f86db169\
0901c56b45c1530afedfb76038e972722fe7ad728f0e4904e046c230570fe9d41398abe12ef5bc\
942be33542a4802d98b5d70f2a332ec37fac3514e74ddc0f2cc1a874cd0c78305a215664613097\
89606bd0bf3f98cda8044629a1'
c2 = '255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f576964746820\
32203020522f4865696768742033203020522f547970652034203020522f537562747970652035\
203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e67\
74682038203020522f42697473506572436f6d706f6e656e7420383e3e0a73747265616d0affd8\
fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1ff\
fe017346dc9166b67e118f029ab621b2560ff9ca67cca8c7f85ba84c79030c2b3de218f86db3a9\
0901d5df45c14f26fedfb3dc38e96ac22fe7bd728f0e45bce046d23c570feb141398bb552ef5a0\
a82be331fea48037b8b5d71f0e332edf93ac3500eb4ddc0decc1a864790c782c76215660dd3097\
91d06bd0af3f98cda4bc4629b1'
collision1 = bytes.fromhex(c1)
collision2 = bytes.fromhex(c2)
script_sig = Script([collision1, collision2])
combined_script = script_sig + script_pubkey
print(combined_script.evaluate(0))

secp256k1の公開鍵は圧縮で33バイト、非圧縮で65バイト(130文字)で長い
UTXOセットが大きくなる
ScriptPubKeyフィールドに公開鍵が存在する

### p2pkhで解決
– アドレスが短くなる
– sha256とripemd160
=> hash160と呼ぶ　160ビット
p2pkhは短くて安全性が高い

### ScriptPubKey(output)
76 OP_DUB
a9 OP_HASH160
14 Length of
bc3b…da
88 OP_EQUALVERIFY
ac OC_CHECKSIG

### ScriptSig(input)
48 Length of signature
30..01 signature
21 Length of pubkey
0349…8a pubkey

### 構成
– ScriptPubKey(output)
OP_DUB, OP_HASH160, HASH, OP_EQUALVERIFY, OP_CHECKSIG
– ScriptSig(input)
,

OP_DUPはエレメントの先頭を複製するため、pubkeyが複製される

def op_dup(stack):
    if len(stack) < 1:
        return False
    stack.append(stack[-1])
    return True

OP_HASH160でpubkeyをhash160(sha256, ripemd160)実行、20バイトのハッシュを生成する

def op_hash160(stack):
    if len(stack) < 1:
        return False
    element = stack.pop()
    stack.append(hash160(element))
    return True

OP_EQUALVERIFYで、生成されたhashとhash値が正しいか確認

def op_equalverify(stack):
    return op_equal(stack) and op_verify(stack)

def op_equal(stack):
    if len(stack) < 2:
        return False
    element1 = stack.pop()
    element2 = stack.pop()
    if element1 == element2:
        stack.append(encode_num(1))
    else:
        stack.append(encode_num(0))
    return True

def op_verify(stack):
    if len(stack) < 1:
        return False
    element = stack.pop()
    if decode_num(element) == 0:
        return False
    return True

OP_CHECKSIGはP2PKと同じ

def op_checksig(stack, z):
    if len(stack) < 1:
        return False
    sec_pubkey = stack.pop()
    der_signature = stack.pop()[:-1]
    try:
        point = S256Point.parse(sec_pubkey)
        sig = Signature.parse(der_signature)
    except (ValueError, SyntaxError) as e:
        return False
    if point.verify(z, sig):
        stack.append(encode_num(1))
    else:
        stack.append(encode_num(0))
    return True

### P2PKH
– ScriptPubKeyが短くなる
– ripemd160,sha256も計算する

OP_CHECKSIG
The entire transaction’s outputs, inputs, and script (from the most recently-executed OP_CODESEPARATOR to the end) are hashed. The signature used by OP_CHECKSIG must be a valid signature for this hash and public key. If it is, 1 is returned, 0 otherwise.

from ecc import (
    S256Point,
    Signature,
)

def op_checksig(stack, z):
    if len(stack) < 1:
        return False
    sec_pubkey = stack.pop()
    der_signature = stack.pop()[:-1]
    try:
        point = S256Point.parse(sec_pubkey)
        sig = Signature.parse(der_signature)
    except (ValueError, SyntaxError) as e:
        return False
    if point.verify(z, sig):
        stack.append(encode_num(1))
    else:
        stack.append(encode_num(0))
    return True

class S256Point(Point):

    @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)

class Signature:

   @classmethod
    def parse(cls, signature_bin):
        s = BytesIO(signature_bin)
        compound = s.read(1)[0]
        if compound != 0x30:
            raise SyntaxError("Bad Signature")
        length = s.read(1)[0]
        if length + 2 != len(signature_bin):
            raise SyntaxError("Bad Signature Length")
        marker = s.read(1)[0]
        if marker != 0x02:
            raise SyntaxError("Bad Signature")
        rlength = s.read(1)[0]
        r = int.from_bytes(s.read(rlength), 'big')
        marker = s.read(1)[0]
        if marker != 0x02:
            raise SyntaxError("Bad Signature")
        slength = s.read(1)[0]
        s = int.from_bytes(s.read(slength), 'big')
        if len(signature_bin) != 6 + rlength + slength:
            raise SyntaxError("Signature too long")
        return cls(r, s)

class S256Point(Point):
    def verify(self, z, sig):
        s_inv = pow(sig.s, N - 2, N)
        u = z * s_inv % N 
        v = sig.r * s_inv % N
        total = u * G + v * self
        return total.x.num == sig.r

bitcoinの署名をシリアライズする標準をDERフォーマット(Distinguished Encoding rules)と呼ぶ

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

30 – Marker
45 – Length of Sig
02 – Marker for r value
21 – r value length
00ed…8f – r value
02 – Marker for s value
20 – s value length
7a98..ed – s value

    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

署名ハッシュz
s = (z + r(Temporary PrivateKey * Gのx座標)*G)/Temporary PrivateKey mod P

署名は、署名ハッシュと kの値が決まれば、k*Gのx軸座標であるrと、(z + r*e)/k の sが決まる。

def encode_num(num):
    if num == 0:
        return b''
    abs_num = abs(num)
    negative = num < 0
    result = bytearray()
    while abs_num:
        result.append(abs_num & 0xff)
        abs_num >>= 8
    if result[-1] & 0x80:
        if negative:
            result.append(0x80)
        else:
            result.append(0)
    elif negative:
        result[-1] != 0x80
    return bytes(result)

def decode_num(element):
    if element == b'':
        return 0
    big_endian = element[::-1]
    if big_endian[0] & 0x80:
        negative = True
        result = big_endian[0] & 0x7f
    else:
        negative = False
        result = big_endian[0]
    for c in big_endian[1:]:
        result <<= 8
        result += c
    if negative:
        return -result
    else:
        return result

def op_0(stack):
    stack.append(encode_num(0))
    return True

evaluateにより、script_sigとscript_pubkeyの検証を行いたい
Scriptの第二引数である0xac(172)はOP_CHECKSIG

from script import Script
z = 0x7c076ff316692a3d7eb3c3bb0f8b1488cf72e1afcd929e29307032997a838a3d
sec = bytes.fromhex('04887387e452b8eacc4acfde10d9aaf7f6d9a0f975aabb10d006e\
4da568744d06c61de6d95231cd89026e286df3b6ae4a894a3378e393e93a0f45b666329a0ae34')
sig = bytes.fromhex('3045022000eff69ef2b1bd93a66ed5219add4fb51e11a840f4048\
76325a1e8ffe0529a2c022100c7207fee197d27c618aea621406f6bf5ef6fca38681d82b2f06fd\
dbdce6feab601')
script_pubkey = Script([sec, 0xac])
script_sig = Script([sig])
combined_script = script_sig + script_pubkey
print(combined_script.evaluate(z))

    def evaluate(self, z):
        cmds = self.cmds[:]
        stack = []
        altstack = []
        while len(cmds) > 0:
            cmd = cmds.pop(0)
            if type(cmd) == int:
                operation = OP_CODE_FUNCTIONS[cmd]
                if cmd in (99, 100):
                    if not operation(stack, cmds):
                        LOGGER.info('bad op: {}'.format(OP_CODE_NAMES[cmd]))
                        return False
                elif cmd in (107, 108):
                    if not operation(stack, altstack):
                        LOGGER.info('bad op: {}'.format(OP_CODE_NAMES[cmd]))
                        return False
                elif cmd in (172, 173, 174, 175):
                    if not operation(stack, z):
                        LOGGER.info('bad op: {}'.format(OP_CODE_NAMES[cmd]))
                        return False
                else:
                    if not operation(stack):
                        LOGGER.info('bad op: {}'.format(OP_CODE_NAMES[cmd]))
                        return False
            else:
                stack.append(cmd)
        if len(stack) == 0:
            return False
        if statck.pop() == b'':
            return False
        return True

99: op_if,
100: op_notif,

op_if: If the top stack value is not False, the statements are executed. The top stack value is removed.

def op_if(stack, items):
    if len(stack) < 1:
        return False
    true_items = []
    false_itmes = []
    current_array = true_items
    found = False
    num_endifs_needed = 1
    while len(items) > 0:
        item = items.pop(0)
        if item in (99, 100):
            num_endifs_needed += 1
            current_array.append(item)
        elif num_endifs_needed == 1 and item == 103:
            current_array = false_items
        elif item == 104:
            if num_endifs_needed == 1:
                found = True
                break
            else:
                num_endifs_neede -= 1
                current_array.append(item)
        else:
            current_array.append(item)
    if not found:
        return False
    element = stack.pop()
    if decode_num(element) == 0:
        items[:0] = false_items
    else:
        items[:0] = true_items
    return True

op_notif: If the top stack value is False, the statements are executed. The top stack value is removed.

def op_notif(stack, items):
    if len(stack) < 1:
        return False
    true_items = []
    false_items = []
    current_array = true_items
    found = False
    num_endifs_needed = 1
    while len(items) > 0:
        item = items.pop(0)
        if item in (99, 100):
            num_endifs_needed += 1
            current_array.append(item)
        elif num_endifs_needed == 1 and item == 103:
            current_array = false_items
        elif item == 104:
            if num_endifs_needed == 1:
                found = True
                break
            else:
                num_endifs_needed -= 1
                current_array.append(item)
        else:
            current_array.append(item)
    if not found:
        return False
    element = stack.pop()
    if decode_num(element) == 0:
        items[:0] = true_items
    else:
        items[:0] = false_items
    return True

—–
107: op_toaltstack,
108: op_fromaltstack,

op_toaltstack:

def op_toaltstack(stack, altstack):
    if len(stack) < 1:
        return False
    altstack.append(stack.pop())
    return True

op_fromaltstack

def op_fromaltstack(stack, altstack):
    if len(altstack) < 1:
        return False
    stack.append(alstack.pop())
    return True

172: op_checksig,
173: op_checksigverify,
174: op_checkmultisig,
175: op_checkmultisigverify,

0xac(172)のOP_CHECKSIGが非常に重要

eは秘密鍵、pは公開鍵
eG = P

ランダムな256ビットの数字k
k * G = R (x座標をr)

uG + vP = kG
kはランダムに選ばれる数字で、u, vは署名者が選ぶ

vP = (k – u)G
P = ((k-u)/v)G

eG = ((k-u)/v)G のため、 e = (k – v) / u
つまり、秘密鍵 e = (k – v) / u を満たす(u, v)の組み合わせであればどれでも良い
eは秘密鍵を知っている人のみわかる

目的は署名ハッシュと呼ぶ。署名ハッシュはzで表す。
uG + vPに当てはめると、 u = z/s, v = z/s

uG + vP = R(目的) = kG
uG + veP = kG
u + ve = k
z/s + re/s = k
(z + re)/s = k
s = (z + re)/k

k は256ビットを保証するためhash256を2回繰り返す

1. 署名(r, s)、署名対象のハッシュをz, 公開鍵をPとする
2. u = z/s, v = r/sを計算する
3. uG + vP = Rを計算する
4. Rのx座標がrと同じであれば署名は有効

ScriptPubKeyの形式がp2pkであるトランザクションアウトプット
ECDSAの署名を検証するには、メッセージz, 公開鍵P, 署名r, sが必要
p2pkでは、ビットコインは公開鍵に送られ、秘密鍵の所有者は署名を作成することによりビットコインをアンロックできる。
ScriptPubKeyはビットコインを秘密鍵の所有者の管理下に置く。
P は公開鍵(x,y) 256bit
e は秘密鍵

e.g.
ScriptPubKey
41 – length of pubkey
0411…a3 pubkey
ac – OP_CHECKSIG

ScriptSig
47 – length of signature
3044 .. 01 – signature

OP_CHECKSIG, pubkey + signature のコマンドセットにする
スタックの先頭エレメントがゼロ以外のときは、有効なscript sigとみなされる

stackにpubkey, signatureをpushし、OP_CHECKSIGで有効であればstackに1をpush, 有効でなければ0をpushする
0以外であれば処理を終了する
0の場合は、スクリプトは無効となり、トランザクション自体が無効になる
秘密鍵を知っている人だけが有効なScriptSigを作り出すことができる

各コマンドがオプコードかスタックにプッシュされるオプコードかを判定する
1~77まではエレメントでそれ以上(78以上)がオプコードとみなす

class Script:

    def __init__(self, cmds=None):
        if cmds is None:
            self.cmds = []
        else:
            self.cmds = cmds
    
    // omission

    @classmethod
    def parse(cls, s):
        length = read_varint(s)
        cmds = []
        count = 0
        while count < length:
            current = s.read(1)
            count += 1
            current_byte = current[0]
            if current_byte >= 1 and current_byte <= 75:
                n = current_byte
                cmds.append(s.read(n))
                count += n
            elif current_byte == 76:
                data_length = little_endian_to_int(s.read(1))
                count += data_length + 1
            elif current_byte == 77:
                data_length = little_endian_to_int(s.read(2))
                cmds.append(s.read(data_length))
                count += data_length + 2
            else:
                op_code = current_byte
                cmds.append(op_code)
        if count != length:
            raise SyntaxError('parsing script failed')
        return cls(cmds)

### シリアライズ
整数の場合はオプコード、それ以外はエレメント

class Script:

    // 

    def raw_serialize(self):
        result = b''
        for cmd in self.cmds:
            if type(cmd) == int:
                result += into_to_little_endian(cmd, 1)
            else:
                length = len(cmd)
                if length < 75:
                    result += int_to_little_endian(length, 1)
                elif length > 75 and length < 0x100:
                    result += int_to_little_endian(76, 1)
                    result += int_to_little_endian(length, 1)
                elif length >= 0x100 and length <= 520:
                    result += int_to_little_endian(77, 1)
                    result += int_to_little_endian(length, 2)
                else:
                    raise ValueError('too long an cmd')
                result += cmd
        return result
    
    def serialize(self):
        result = self.raw_serialize()
        total = len(result)
        return encode_varint(total) + result

### Script Fieldの連結
scriptオブジェクトは評価が必要なコマンドのセットを表す
スクリプを評価するにあたり、ロックボックスのScriptPubKey(outputsの2番目)とアンロックするScriptSig(inputsの3番目)のフィールドを連結する必要がある。
ScriptPubKeyはPrevious Transaction, ScriptSigはCurrent Transaction
ScriptSigがScriptPubKeyをunlockする
ScriptSigからのコマンドはScriptPubKeyのコマンドの上に配置し、処理するコマンドがなくなるまで1つづつ処理される

class Script:
    def __add__(self, other):
        
        return Script(self.cmds + other.cmds)

標準スクリプト(Base58, Bech32)
p2pk, p2pkh, p2sh, p2wpkh, p2wsh

ウォレットは様々なタイプを解釈する方法を知っており、適切なScriptPubKeyを作成する

ScriptPubKeyとScriptSigはどちらも同じ方法でパースされる
バイトが0x01から0x4b(10進数の75)の間の場合(nと呼ぶ)、次のnバイトを1つのエレメントとして読み取る。その範囲の値ではないときは、そのバイトはオペレーションを表している

0x00 – OP_0
0x51 – OP_1
0x60 – OP_16
0x76 – OP_DUP
0x93 – OP_ADD
0xa9 – OP_HASH160
0xac – OP_CHECHSIG

0x4bより長いエレメントの場合は、特別なオプコードOP_PUSHDATA1(76-255), OP_PUSHDATA2(256-520), OP_PUSHDATA4がある。