[bitcoin基礎技術] デジタル署名

<送信者>
– データをハッシュ関数でハッシュ化
– 出力されたハッシュ値を秘密鍵で暗号化し、署名を作成
– データと署名をセットにして受信者に送信

<受信者>
– 受け取ったデータを送信者と同じハッシュ関数でハッシュ化してハッシュ値Aを得る
– 受け取った署名を送信者の公開鍵で復号してハッシュ値Bを得る
– A B比較して一致していることを確認

### デジタル署名の流れ
1. 送信者のメッセージを作成
$ echo secret > message.txt; cat message.txt
secret

2. 秘密鍵でハッシュ値に署名し、message.sigに出力
$ openssl dgst -sha256 -sign secp256k1-private.pem message.txt > message.sig; ls message.sig
message.sig

3. 生成した公開鍵で署名を検証
$ openssl dgst -sha256 -verify secp256k1-public.pem -signature message.sig message.txt
Verified OK

### メッセージの改ざん検出
$ openssl ecparam -genkey -name secp256k1 -out secp256k1-private-evil.pem; ls secp256k1-private-evil.pem
secp256k1-private-evil.pem
$ echo “tampered secret” > tampered_message.txt ; cat tampered_message.txt
tampered secret
$ openssl dgst -sha256 -sign secp256k1-private-evil.pem tampered_message.txt > tampered_message.sig ; ls tampered_message.sig
tampered_message.sig
$ openssl dgst -sha256 -verify secp256k1-public.pem -signature tampered_message.sig tampered_message.txt
Verification failure

[bitcoin基礎技術] 公開鍵暗号

パラメータファイルの生成
$ openssl ecparam -name secp256k1 -out secp256k1.pem

secp256k1.pem

-----BEGIN EC PARAMETERS-----
BgUrgQQACg==
-----END EC PARAMETERS-----

$ openssl ecparam -in secp256k1.pem -text -noout
EC-Parameters: (256 bit)
ASN1 OID: secp256k1

パラメータの確認
$ openssl ecparam -in secp256k1.pem -text -param_enc explicit -noout
EC-Parameters: (256 bit)
Field Type: prime-field
Prime:
00:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:fe:ff:
ff:fc:2f
A: 0
B: 7 (0x7)
Generator (uncompressed):
04:79:be:66:7e:f9:dc:bb:ac:55:a0:62:95:ce:87:
0b:07:02:9b:fc:db:2d:ce:28:d9:59:f2:81:5b:16:
f8:17:98:48:3a:da:77:26:a3:c4:65:5d:a4:fb:fc:
0e:11:08:a8:fd:17:b4:48:a6:85:54:19:9c:47:d0:
8f:fb:10:d4:b8
Order:
00:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
ff:fe:ba:ae:dc:e6:af:48:a0:3b:bf:d2:5e:8c:d0:
36:41:41
Cofactor: 1 (0x1)

秘密鍵を生成
$ openssl ecparam -in secp256k1.pem -genkey -noout -out secp256k1-private.pem
$ cat secp256k1-private.pem
—–BEGIN EC PRIVATE KEY—–
MHQCAQEEIAqV2IN8gUr9qXpsJyhpYA4KQfXioS/oiDMh1dgPcncAoAcGBSuBBAAK
oUQDQgAEeiuKeXTtb0t4F7DzVMbIHOrLIQ5T4JPq3NTU7OC7TWCghk6ALrWLgTGD
zUuuEIWI4GLsYea/829orVMO4Rz/FQ==
—–END EC PRIVATE KEY—–

秘密鍵を16進数表記で出力
$ openssl ec -in secp256k1-private.pem -outform DER | tail -c +8 | head -c 32 | xxd -p -c 32
read EC key
writing EC key
0a95d8837c814afda97a6c272869600e0a41f5e2a12fe8883321d5d80f727700

秘密鍵を変数に格納
$ privKey=0a95d8837c814afda97a6c272869600e0a41f5e2a12fe8883321d5d80f727700

公開鍵を生成
$ openssl ec -in secp256k1-private.pem -pubout -out secp256k1-public.pem; cat secp256k1-public.pem
read EC key
writing EC key
—–BEGIN PUBLIC KEY—–
MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEeiuKeXTtb0t4F7DzVMbIHOrLIQ5T4JPq
3NTU7OC7TWCghk6ALrWLgTGDzUuuEIWI4GLsYea/829orVMO4Rz/FQ==

公開鍵を16進数で出力
$ openssl ec -in secp256k1-private.pem -pubout -outform DER | tail -c 65 | xxd -p -c 65
read EC key
writing EC key
047a2b8a7974ed6f4b7817b0f354c6c81ceacb210e53e093eadcd4d4ece0bb4d60a0864e802eb58b813183cd4bae108588e062ec61e6bff36f68ad530ee11cff15

秘密鍵はスカラーですが、公開鍵は座標x, y
$ pubKey=047a2b8a7974ed6f4b7817b0f354c6c81ceacb210e53e093eadcd4d4ece0bb4d60a0864e802eb58b813183cd4bae108588e062ec61e6bff36f68ad530ee11cff15
$ prefix=`echo $pubKey | cut -c1-2`; echo “prefix= $prefix”
prefix= 04
$ x=`echo $pubKey | cut -c3-66` ; echo “x = $x”
x = 7a2b8a7974ed6f4b7817b0f354c6c81ceacb210e53e093eadcd4d4ece0bb4d60
$ y=`echo $pubKey | cut -c67-130`; echo “y= $y”
y= a0864e802eb58b813183cd4bae108588e062ec61e6bff36f68ad530ee11cff15

[C++ basic] 出力, 文字数字

#include <iostream>
using namespace std;

int main() {
    cout << "ようこそC++!\n";
    cout << "lets start c++!\n";

    return 0;
}

coutはstandard outputと結び付けられ、 は表示を意味する
iostreamは画面出力の機能などを表す
coutは本来、using namespace stdでstc.coutと書くが、省略もできる。

int main() {
    cout << 1 << 2 << 3 << '\n' << 4 << 5 << '\n';

    return 0;
}

c++では文字、数字の表記をリテラルと呼ぶ。リテラルの他に、キーワード、識別子、演算子、区切り子などがある。
リテラルは”で囲む

#include <iostream>
using namespace std;

int main() {
    cout << 'A' << '\n';
    cout << "welcome to C++!\n";
    cout << 123 << '\n';

    return 0;
}

エスケープシーケンス

int main() {

    cout << "円記号を表示する:" << '\\' << '\n';
    cout << "アポストロフィを表示する:" << '\'' << '\n';

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
円記号を表示する:\
アポストロフィを表示する:’

文字コード

int main() {

    cout << "8進数101の文字コードを持つ文字は" << '\101' << "です\n";
    cout << "16進数61の文字コードを持つ文字は" << '\x61' << "です\n";

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
8進数101の文字コードを持つ文字はAです
16進数61の文字コードを持つ文字はaです

文字リテラルは”でくくる。
数値には整数と浮動小数点があり、それぞれinteger literal, floating literalと呼ぶ

int main() {

    cout << "10進数の10は" << 10 << "です\n";
    cout << "8進数の10は" << 010 << "です\n";
    cout << "16進数の10は" << 0x10 << "です\n";
    cout << "16進数のFは" << 0xF << "です\n";

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
10進数の10は10です
8進数の10は8です
16進数の10は16です
16進数のFは15です

int main() {

    cout <<  123 << '\n';
    cout << "\\" << "100もらった\n";
    cout << "また明日\n";

    return 0;
}

8進数と16進数

#include <iostream>
using namespace std;

int main() {

    // 8進数
    cout <<  06 << '\n';
    cout <<  024 << '\n';
    cout <<  015 << '\n';

    // 16進数
    cout <<  0x6 << '\n';
    cout <<  0x14 << '\n';
    cout <<  0xd << '\n';
}

16進数はビットコインで基本となってますね。

coding practice SRM494

Mr. White is a very versatile person – absolutely everything is interesting to him. Perhaps this is why he has many friends. Quite unfortunately, however, none of his friends are versatile at all. Each of them is interested only in two topics and refuses to talk about anything else. Therefore, each time Mr. White organizes a party, it’s a big problem for him to decide whom to invite so that the party is interesting to everybody. Now that Mr. White has a lot of experience in organizing parties, he knows for sure that a party will be interesting if and only if there’s a topic interesting to each of the invited friends.

#include <vector>
#include <string>
using namespacee std;

class InterestingParty {
    public:
        int bestInvitation(vector <string> first, vector <string> second) {
            int i, j;
            int ans = 0;

            for(i=0; i<first.size(); i++){
                int f=0;
                int s=0;
                for(j=0; j<first.size(); j++){
                    if(first[i] == first[j]) f++;
                    if(first[i] == second[j]) f++;
                    if(second[i] == first[j]) s++;
                    if(second[i] == second[j]) s++;
                }
                ans = max(f, ans);
                ans = max(s, ans);
            }
            return ans;
        }
}

連想配列を使う場合

#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespacee std;

class InterestingParty {
    public:
        int bestInvitation(vector <string> first, vector <string> second) {
            map <string, int> dic;

            for(int i=0; i<first.size(); i++){
                dic[first[i]] = 0;
                dic[second[i]] = 0;
            }

            for(int i=0; i<first.size; i++){
                dic[first[i]]++;
                dic[second[i]]++;
            }
            int ans = 0;
            map <string, int>::iterator it;
            for(it=dic.begin(); it!=dic.end(); it++){
                ans = max(ans, it->second);
            }
            return ans;
        }
}

[bitcoin基礎技術] sha256, ripemd160, HMAC-SHA512, PBKDF2

### SHA-256
常に32bytesで出力される
$ echo -n abcdefghijklmn | openssl dgst -sha256
SHA2-256(stdin)= 0653c7e992d7aad40cb2635738b870e4c154afb346340d02c797d490dd52d5f9
-n は改行出力を抑止
$ echo -n a | openssl dgst -sha256
SHA2-256(stdin)= ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb

### RIPEMD-160
160bit 20bytes
$ echo -n a | openssl dgst -rmd160
Error setting digest
2070E0ADFFFF0000:error:0308010C:digital envelope routines:inner_evp_generic_fetch:unsupported:../crypto/evp/evp_fetch.c:349:Global default library context, Algorithm (RIPEMD160 : 99), Properties ()
2070E0ADFFFF0000:error:03000086:digital envelope routines:evp_md_init_internal:initialization error:../crypto/evp/digest.c:254:

$ apt list openssl
Listing… Done
openssl/jammy-updates,jammy-security,now 3.0.2-0ubuntu1.12 arm64 [installed,automatic]

ubuntu22.04でopenssl3.0.2だと ripemd160が使えないらしい

### ダブルハッシュ
$ echo -n a | xxd -r -p | openssl dgst -sha256 | openssl dgst -rmd160
xxd -r -pでバイナリデータに変換する
$ echo -n a | xxd -r -p | openssl dgst -sha256 | openssl dgst -sha256
SHA2-256(stdin)= e877d81a8f216a6aebe39b3ca7b350ad38db6d8ea6ad7e3fe581a8a1ab09eeee

### HMAC-SHA512
HMAC-SHA512とはキーとデータのペアを入力してハッシュ化する処理のこと
SHA-512を使用する
$ echo -n “what do ya want for nothing?” | openssl dgst -sha512 -hmac “Jefe”
SHA2-512(stdin)= 164b7a7bfcf819e2e395fbe73b56e0a387bd64222e831fd610270cd7ea2505549758bf75c05a994a6d034f65f8f0e6fdcaeab1a34d4a6b4b636e070a38bce737
キーを16進数で指定する場合は以下の通り
$ echo -n “what do ya want for nothing?” | openssl dgst -sha512 -mac HMAC -macopt hexkey:4a656665
SHA2-512(stdin)= 164b7a7bfcf819e2e395fbe73b56e0a387bd64222e831fd610270cd7ea2505549758bf75c05a994a6d034f65f8f0e6fdcaeab1a34d4a6b4b636e070a38bce737

ワンライナーで表示
$ echo -n “what do ya want for nothing?” | openssl dgst -sha512 -mac HMAC -macopt hexkey:`echo -n Jefe | xxd -p`
$ echo -n “what do ya want for nothing?” | openssl dgst -sha512 -mac HMAC -macopt hexkey:$(echo -n Jefe | xxd -p)
hmac=`echo -n “what do ya want for nothing?” | openssl dgst -sha512 -mac HMAC -macopt hexkey:$(echo -n Jefe | xxd -p)`; echo $hmac

### PBKDF2
一般的にパスワードのハッシュ化に利用される
ビットコインではニモニックコードからシードを生成する際に利用される。
PBKDF2ではキーとデータを入力し、使用するハッシュ関数とストレッチングの回数を決めておく

import hashlib, binascii
hashFunc="sha512"
password=b"passw0rd"
salt=b"bitcoin"
iteCnt=100
encPass=hashlib.pbkdf2_hmac(hashFunc, password, salt, iteCnt)
print(binascii.hexlify(encPass))

$ python3 main.py
b’65252733b1f1d6e5abd4474d696989641125bedb34be2c7789eef454abac6e718180666c73e0ec44ed529291e3b6e5b22d4222b263c259aa0128ad9f5e1cd2c2′

Ubuntu22.04でc++の実行環境を作る

$ sudo apt install build-essential
$ gcc –version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ g++ –version
g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

#include <iostream>
using namespace std;

int main() {
    cout << "ようこそC++!\n";

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
ようこそC++!

sig_hashとverify_input

txをシリアライズする際に、redeem_script=None としてp2pkh か p2shかを分ける

    def sig_hash(self, input_index, redeem_script=None):
        s = int_to_little_endian(self.version, 4)
        s += encode_varint(len(self.tx_ins))
        for i, tx_in in enumerate(self.tx_ins):
            if i == input_index:
                if redeem_script:
                    script_sig = redeem_script
                else:
                    script_sig = tx_in.script_pubkey(self.testnet)
            else:
                script_sig = None    
            s += TxIn(
                prev_tx = tx_in.prev_tx,
                prev_index = tx_in.prev_index,
                script_sig = tx_in.script_pubkey(self.testnet),
                sequence = tx_in.sequence,
            ).serialize()
        s += encode_varint(len(self.tx_outs))
        for tx_out in self.tx_outs:
            s += tx_out.serialize()
        s += int_to_little_endian(self.locktime, 4)
        s += int_to_little_endian(SIGHASH_ALL, 4)
        h256 = hash256(s)
        return int.from_bytes(h256, 'big')

    def verify_input(self, input_index):
        tx_in = self.tx_ins[input_index]
        script_pubkey = tx_in.script_pubkey(testnet=self.testnet)
        if script_pubkey.is_p2sh_script_pubkey():
            cmd = tx_in.script_sig.cmds[-1]
            raw_redeem = encode_varint(len(cmd)) + cmd
            redeem_script = Script.parse(BytesIO(raw_redeem))
        else:
            redeem_script = None
        z = self.sig_hash(input_index, redeem_script)
        combined = tx_in.script_sig + script_pubkey
        return combined.evaluate(z)
    def is_p2pkh_script_pubkey(self):
        return len(self.cmds) == 5 and self.cmds[0] == 0x76 \
            and self.cmds[1] == 0xa9 \
            and type(self.cmds[2]) == bytes and len(self.cmds[2]) == 20 \
            and self.cmds[3] == 0x88 and self.cmds[4] == 0xac

    def is_p2sh_script_pubkey(self):
        return len(self.cmds) == 3 and self.cmds[0] == 0xa9 \
            and type(self.cmds[1]) == bytes and len(self.cmds[1]) == 20 \
            adn self.cmds[2] == 0x87

p2shの署名検証

p2pkhは1つの署名と1つの公開鍵のみだが、p2shは幾つかの公開鍵(RedeemScript内のSECフォーマット)と、それ以下の数の署名(ScriptSig内、DERフォーマット)がある。署名は公開鍵と同じ順番である必要がある。
特定の署名と公開鍵を取得したら、署名が有効かを判断するために必要なのは署名ハッシュ、すなわちzのみである。

### 署名ハッシュの取得方法
1. 全てのScriptSig(output)を空にする => 00
2. 署名対象となるp2shのインプットのScriptSigをRedeemScriptに置き換える
 L RedeemScriptを空のScriptSigの場所に配置する。※ScriptPubKeyでないことがp2pkhと異なる
3. 4バイトのハッシュタイプを末尾に追加する。p2pkhと同じ。SIGHASH_ALLに対応する整数は1であり、4バイトのリトルエンディアンでエンコードする必要がある
4. SEC公開鍵、DER署名はScriptSig(output)から

from ecc import S256Point, Signature
from helper import hash256
modified_tx = bytes.fromhex('0100000001868278ed6ddfb6c1ed3ad5f8181eb0c7a38\
5aa0836f01d5e4789e6bd304d87221a000000475221022626e955ea6ea6d98850c994f9107b036\
b1334f18ca8830bfff1295d21cfdb702103b287eaf122eea69030a0e9feed096bed8045c8b98be\
c453e1ffac7fbdbd4bb7152aeffffffff04d3b11400000000001976a914904a49878c0adfc3aa0\
5de7afad2cc15f483a56a88ac7f400900000000001976a914418327e3f3dda4cf5b9089325a4b9\
5abdfa0334088ac722c0c00000000001976a914ba35042cfe9fc66fd35ac2224eebdafd1028ad2\
788acdc4ace020000000017a91474d691da1574e6b3c192ecfb52cc8984ee7b6c5687000000000\
1000000')
h256 = hash256(modified_tx)
z = int.from_bytes(h256, 'big')
sec = bytes.fromhex('022626e955ea6ea6d98850c994f9107b036b1334f18ca8830bfff\
1295d21cfdb70')
der = bytes.fromhex('3045022100dc92655fe37036f47756db8102e0d7d5e28b3beb83a\
8fef4f5dc0559bddfb94e02205a36d4e4e6c7fcd16658c50783e00c341609977aed3ad00937bf4\
ee942a89937')
point = S256Point.parse(sec)
sig = Signature.parse(der)
print(point.verify(z, sig))

$ python3 test.py
True

from io import BytesIO
from ecc import S256Point, Signature
from helper import hash256, int_to_little_endian, encode_varint
from script import Script
from tx import Tx, TxIn, SIGHASH_ALL
hex_tx = '0100000001868278ed6ddfb6c1ed3ad5f8181eb0c7a385aa0836f01d5e4789e6\
bd304d87221a000000db00483045022100dc92655fe37036f47756db8102e0d7d5e28b3beb83a8\
fef4f5dc0559bddfb94e02205a36d4e4e6c7fcd16658c50783e00c341609977aed3ad00937bf4e\
e942a8993701483045022100da6bee3c93766232079a01639d07fa869598749729ae323eab8eef\
53577d611b02207bef15429dcadce2121ea07f233115c6f09034c0be68db99980b9a6c5e754022\
01475221022626e955ea6ea6d98850c994f9107b036b1334f18ca8830bfff1295d21cfdb702103\
b287eaf122eea69030a0e9feed096bed8045c8b98bec453e1ffac7fbdbd4bb7152aeffffffff04\
d3b11400000000001976a914904a49878c0adfc3aa05de7afad2cc15f483a56a88ac7f40090000\
0000001976a914418327e3f3dda4cf5b9089325a4b95abdfa0334088ac722c0c00000000001976\
a914ba35042cfe9fc66fd35ac2224eebdafd1028ad2788acdc4ace020000000017a91474d691da\
1574e6b3c192ecfb52cc8984ee7b6c568700000000'
hex_sec = '03b287eaf122eea69030a0e9feed096bed8045c8b98bec453e1ffac7fbdbd4b\
b71'
hex_der = '3045022100da6bee3c93766232079a01639d07fa869598749729ae323eab8ee\
f53577d611b02207bef15429dcadce2121ea07f233115c6f09034c0be68db99980b9a6c5e75402\
2'
hex_redeem_script = '475221022626e955ea6ea6d98850c994f9107b036b1334f18ca88\
30bfff1295d21cfdb702103b287eaf122eea69030a0e9feed096bed8045c8b98bec453e1ffac7f\
bdbd4bb7152ae'
sec = bytes.fromhex(hex_sec)
der = bytes.fromhex(hex_der)
redeem_script = Script.parse(BytesIO(bytes.fromhex(hex_redeem_script)))
stream = BytesIO(bytes.fromhex(hex_tx))
tx_obj = Tx.parse(stream)
s = int_to_little_endian(tx_obj.version, 4)
s += encode_varint(len(tx_obj.tx_ins))
i = tx_obj.tx_ins[0]
s += TxIn(i.prev_tx, i.prev_index, redeem_script, i.sequence).serialize()
s += encode_varint(len(tx_obj.tx_outs))
for tx_out in tx_obj.tx_outs:
    s += tx_out.serialize()
s += int_to_little_endian(tx_obj.locktime, 4)
s += int_to_little_endian(SIGHASH_ALL, 4)
z = int.from_bytes(hash256(s), 'big')
point = S256Point.parse(sec)
sig = Signature.parse(der)
print(point.verify(z, sig))

$ python3 test.py
True

p2shのコーディング

OP_HASH160, hash160, OP_EQUALの処理を追加する

            else:
                stack.append(cmd)
                if len(cmds) == 3 and cmds[0] == 0xa9 \
                    and type(cmds[1]) == bytes and len(cmds[1]) == 20 \
                    and cmds[2] == 0x87:
                    cmds.pop()
                    if not op_hash160(stack):
                        return False
                    stack.append(h160)
                    if not op_equal(stack):
                        return False
                    if not op_verify(stack):
                        LOGGER.info('bad p2sh h160')
                        return False
                    redeem_script = encode_varint(len(cmd)) + cmd
                    stream = ByteIO(redeem_script)
                    cmds.extend(Script.parse(stream).cmds)

p2shの特徴は、RedeemScriptが長くともOP_PUSHDATA2の最大長520byteである点
複雑なロジックを定義するスクリプトにすることができる。

### p2shのアドレス
p2shアドレスを計算するには、p2pkhアドレスの計算方法と類似したプロセスを用いる
hash160の前にプレフィックスバイトを、末尾にチェックサムを追加する
メインネットのp2shはプレフィックスバイトに0x05、Base58のアドレスは3から始まる
テストネットのp2shのプレフィックスバイトに0xc4を使用するため、アドレスは2から始まる

from helper import encode_base58_checksum
h160 = bytes.fromhex('74d691da1574e6b3c192ecfb52cc8984ee7b6c56')
print(encode_base58_checksum(b'\x05' + h160))

$ python3 test.py
3CLoMMyuoDQTPRD3XYZtCvgvkadrAdvdXh

p2pkhとp2shのアドレス

def h160_to_p2pkh_address(h160, testnet=False):
    if testnet:
        prefix = b'\x6f'
    else:
        prefix = b'\x00'
    return encode_base58_checksum(prefix + h160)

def h160_to_p2sh_address(h160, testnet=False):
    if testnet:
        prefix = b'\xc4'
    else:
        prefix = b'\x05'
    return encode_base58_checksum(prefix + h160)

p2sh(pay to script hash)

マルチシグ、複数署名の解法
複数の秘密鍵から単一の集約署名であるシェノア署名が一般的になると思われる

### ベアマルチシグ
オプコードのOP_CHECKMULTISIG (0xae)を理解する必要がある。
OP_CHECKMULTISIGは、スタックから多数の要素をポップし、必要な数の署名がトランザクションインプットに対して有効か否かを返す
トランザクションアウトプットは長いScriptPubKeyのまま

ベアマルチシグのScriptPubKey
51 OP_1
41 Length of pubkey
04fc..3d pubkey1
21 Length of pubkey2
0202..00 pubkey2
52 OP_2
ae OP_CHECKMULTISIG

ベアマルチシグのScriptSig
00 OP_0
48 Length of signature1
3045…01 signature1

pubkeyやsignatureの数が多くなればなるほどバイト数が多くなる
pubkey, signatureのm, nは1~20の数値を指定できる

### SCRIPTの例
OP_0, signature1, signature2, …, signature m, OP_m, pubkey1, … pubkey n, OP_n, OP_CHECKMULTISIG
OP_CHECKMULTISIGは、m + n + 3個の要素をポップし、n個の公開鍵のリストのうち、m個の署名が有効である場合は1をスタックにプッシュ、有効でない場合は0
OP_CHECKMULTISIGは m + n + 2この要素をプップするはずが、m + n + 3でポップしているため、OP_0が追加されている。

def op_checkmultisig(stack, z):
    if len(stack) < 1:
        return False
    n = decode_num(stack.pop())
    if len(stack) < n + 1:
        return False
    sec_pubkeys = []
    for _ in range(n):
        sec_pubkeys.append(stack.pop())
    m = decode_num(stack.pop())
    if len(stack) < m + 1:
        return False
    der_signatures = []
    for _ in range(m):
        der_signatures.append(stack.pop()[:-1])
    stack.pop()
    try:
        points = [S256Point.parse(sec) for sec in sec_pubkeys]
        sigs = [Signature.parse(der) for der in der_signatures]
        for sig in sigs:
            if len(points) == 0:
                LOGGER.info("signatures no good or not in right order")
                return False
            success = False
            while points:
                point = points.pop(0)
                if point.verify(z, sig):
                    success = True
                    break
                if not success:
                    return False
        stack.append(encode_num(1))
    except (ValueError, SyntaxError):
        return False
    return True

### ベアマルチシグの問題
m of nの署名を要求して単一障害を回避するが、問題がある
– ScriptPubKeyが長くなる
– outputsが通常のp2pkhアウトプットの5~20倍になる
これらの問題を軽減するためにPay to script hash(p2sh)が誕生している
L Scriptコマンドのハッシュを取得し、後でハッシュ化する前のScriptコマンドを明らかにする

### 特別なルールを実行するPay-to-script-hash
RedeemScript, OH_HASH160, hash, OP_EQUAL
スタックが1で終わる場合、RedeemScriptがパースされ、Scriptコマンドセットに追加 BIP160で導入された
2-of-2マルチシグのScriptPubKeyがあるとする これをp2shに変換する作業をスクリプトのハッシュを取得してスクリプトを引き換えたいときに利用しやすいように保持する
52 OP_2
21 Length of pubkey1
02…db70 pubkey1
21 Length of pubkey2
03…bb71 pubkey2
52 OP_2
ae OP_CHECKMULTISIG

Pay to script hash(p2sh)のScriptPubKey
a9 OP_HASH160
14 Length of Hash
74d6…56 hash
87 OP_EQUAL

これまでのScriptPubKeyに相当するもののhash160 アンロック時に明らかにしなければならないRedeemScriptのハッシュに資金をロックする
RedeemScriptは公開だけでなくアンロックにも必要で、ブロックチェーン上にはないため、p2shアドレスの作成者が保管しておかなければならない

2-of-2マルチシグのScriptSig
00 OP_0
48 Length of signature1
3045…3701 signature1
48 Length of signature2
3045…2201 signature
47 Length of RedeemScript
5221…ae RedeemScript

### 連結のScript
ScriptPubKey: OP_HASH160, hash, OP_EQUAL
ScriptSig: OP_0, signature1, signature2, RedeemScript
Script: OP_0, signature1, signature2, RedeemScript, OP_HASH160, hash, OP_EQUAL

特別なルールを実行するp2shのパターン: RedeemScript, OP_HASH160, hash, OP_EQUAL
RedeemScriptはScriptコマンドにセット
h160した結果がScriptPubKeyにあるh160の値と等しくなるRedeemScriptを明らかにすると、RedeemScriptはScriptPubKeyの代わりとして機能する
資金をロックするスクリプトをハッシュして、スクリプト自体の代わりにブロックチェーンに入れる

OP_0, signature1, signature2, RedeemScript, OP_HASH160, hash, OP_EQUAL
OP_HASH160でRedeemScriptをhashにするので、
OP_0, signature1, signature2, hash, OP_EQUALとなる。
hashが等しい場合は結果は有効とみなされる

52 OP_2
21 Length of pubkey1
02…db70 pubkey1
21 Length of pubkey2
03…bb71 pubkey2
52 OP_2
ae OP_CHECKMULTISIG