Month: December 2023

圧縮公開鍵の作成

### パラメータファイルの作成
$ openssl ecparam -name secp256k1 -out secp256k1.pem
$ 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
16進数表記で出力
$ openssl ec -in secp256k1-private.pem -outform DER | tail -c +8 | head -c 32 | xxd -p -c 32

### 公開鍵
$ openssl ec -in secp256k1-private.pem -pubout -out secp256k1-public.pem ; cat secp256k1-public.pem
16進数表記で出力
$ openssl ec -in secp256k1-private.pem -pubout -outform DER | tail -c 65 | xxd -p -c 65
$ pubKey=04bf03ed7464908e5ee11ca694d3699cef8f27b51d6bd4294576ac30f7a5ebf84346ec91d2fae812d2d8e9528838bc929d6f5eab143214864e8dc719b976c9bbd1

$ prefix=`echo $pubKey | cut -c1-2` ; echo “prefix = $prefix”
prefix = 04
$ x=`echo $pubKey | cut -c3-66` ; echo “x=$x”
x=bf03ed7464908e5ee11ca694d3699cef8f27b51d6bd4294576ac30f7a5ebf843
$ y=`echo $pubKey | cut -c67-130` ; echo “y = $y”
y = 46ec91d2fae812d2d8e9528838bc929d6f5eab143214864e8dc719b976c9bbd1

$ pubKeyHash=`echo $pubKey | hash160` ; echo $pubKeyHash
$ checksum=`echo 00${pubKeyHash} | sha256d | cut -c1-8` ; echo $checksum
$ echo 00${pubKeyHash}${checksum} | b58e

opensslのrmd160がうまくいかん…

Base58 decode

Base58decodeはBase58encodeの逆の処理を行う

import sys
import re

matrix=list('123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz')

pattern=r"^1*"

for line in sys.stdin:
    target=line.strip('\n')
    match=re.match(pattern, target)
    ones=match.group()
    target=target.lstrip(ones)
    targetChars=list(target)
    q=0
    for c in targetChars:
        q=q*58+matrix.index(c)
    decodedHex=str(hex(q)).lstrip('0x')
    decodedHex=ones.replace('1','00') + decodedHex
    hexlen=len(decodedHex)
    if hexlen % 2 == 1:
        print('0'+decodedHex)
    else:
        print(decodedHex)

$ echo 18N | python3 base58decode.py
0001ab

Base58 encode

1. 対象データの先頭に0が続く場合、0以外になるまでそのバイトを除外(e.g. 最初の3バイトが全て0の場合は、先頭の3バイトを除外)
2. 1の結果を58で割る
3. 剰余をBase58に変換
4. 変換された剰余を連結し、1で除外した0の数だけ先頭に1を連結

import sys
import re

matrix = list('123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz')

pattern=r"^(00)*"

for line in sys.stdin:
    target = line.rstrip('\n')
    match = re.match(pattern, target)
    zeros=match.group()
    target = target.lstrip(zeros)
    q = int(target, 16)
    r = 0
    b58str = ''
    while q > 0:
        q, r = divmod(q, 58)
        b58str = matrix[r] + b58str

    print(zeros.replace('00', '1') + b58str)

$ echo 0001ab | python3 base58encode.py
18N

C++ 入門の入門1

わざとエラーを発生させる

#include <iostream>
using namespace std;

int main(){
    cout << "hello world\n"
}

void main(){
    cout << "hello world\n";
}

### コンパイルオプション
オブジェクトファイル　-c
実行ファイル -o
静的ライブラリをリンク　-L
ヘッダを追加 -l
警告 -W, -wall
機能有効 -std=c++11
最適化 -O

#### 変数

int main(){
    int a = 12345;
    int b = 98765;
    cout << a + b << endl;
    cout << a - b << endl;
}

intは32bit

#include <iostream>
#include <limits>
using namespace std;

int main(){
    cout << numeric_limits<int>::lowest() << ", " << numeric_limits<int>::max() << endl;
}

floatが32ビットだがdoubleは64bit

int main(){
    double a = 1.23;
    double b = 5.43;
    cout << a * b << endl;
    cout << a / b << endl;
}

SRM453 MazeMaker

Mike Mazemeister has recently built a large maze in his backyard. The j-th character of the i-th element of maze is ‘X’ if the square is an impassable bush; otherwise, it is a ‘.’. Mike wants his friend, Jumping Jim, to solve the maze. Jim will start in row startRow in column startCol.

Unlike typical maze solvers, Jim has the ability to jump through the maze, rather than simply walking. Jim’s possible moves are described in moveRow and moveCol. The i-th element corresponds to a move Jim can make in which his current row is changed by moveRow[i], and his current column is changed by moveCol[i]. For example, if moveRow = {1, 0, -1} and moveCol = {3, -2, 5}, Jim’s legal moves are (1,3), (0, -2), and (-1, 5). However, Jim cannot move outside the boundary of the maze, and he cannot land on an impassable bush.

Mike wants to make the maze impossible for Jim to exit, and can place the exit in any cell containing a ‘.’ in the maze. If this turns out to be impossible, then Mike wants to make Jim’s trip take as long as possible. Jim is smart, and he will always exit the maze in the minimum number of jumps that he can. Return the maximum number of jumps that Jim will make to exit the maze; if it is impossible for him to exit the maze, return -1 instead.

#include <string>
#include <vector>
#include <queue>
using namespace std;

class MazeMaker {
    public:
        int longestPath(vector <string> maze, int startRow, int startCol,
                        vector <int> moveRow, vector <int> moveCol)
    {
        int max = 0;
        int width = maze[0].size(),
            height = maze.size();
        int boad[50][50];

        for(int i = 0; i < height; i++)
            for (int j = 0; j < width; j++)
                board[i][j] = -1;
        
        board[startRow][startCol] = 0;
        queue<int> queueX;
        queue<int> queueY;
        queueX.push(startCol);
        queueY.push(startRow);

        while(queueX.size() > 0){
            int x = queueX.front(),
                y = queueY.front();
            queueX.pop(); queueY.pop();
            for(int i = 0; i < moveRow.size(); i++){
                int nextX = x + moveCol[i],
                    nextY = y + moveRow[i];
                
                if ( 0 <= nextX && nextX < width 
                    && 0 <= nextY && nextY < height
                    && board[nextY][nextX] == -1
                    && maze[nextY].substr(nextX,1) == '.'){
                        board[nextY][nextX] = board[y][x] + 1;
                        queueX.push(nextX);
                        queueY.push(nextY);
                    }
            }
        }
        for (int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if (maze[i].substr(j, 1) == "." && board[i][j] == -1)
                    return -1;
                max = std::max(max,board[i][j]);
            }
        }
        return max;
    }
}

[bitcoin] p2sh-p2wsh

p2sh-p2wshは、p2sh-p2wpkhと同様にp2wshに後方互換性を持たせる方法

BIP0141以前
01000000 – version
01 – # of inputs
7082…54 – previous tx hash
00000000 – previous tx index
2322…4c – ScriptSig
ffffffff – sequence
01 – # of outputs
603e…00 – output amount
1600…22 ScriptPubKey
00000000 – locktime

BIP0141以降
01000000 – version
00 – Segwit marker
01 – Segwit flag
01 – # of inputs
7082…54 – previous tx hash
01000000 – previous tx index
2322…4c – ScriptSig
ffffffff – sequence
01 – # of outputs
603e…00 – output amount
1600…22 ScriptPubKey
0400…ae – witness
00000000 – locktime

OP_0, 32-byte hash
WitnessScriptはスクリプトコマンドとして解釈されコマンドセットに配置される
OP_0, signature1, signature2, OP_2, pubkey1, pubkey2, pubkey3, OP_3, OP_CHECKMULTISIG

[bitcoin] Pay-to-witness-script-hash(p2wsh)

BIP0141以前
01000000 – version
01 – # of inputs
593a…98 – previous tx hash
00000000 – previous tx index
00 – ScriptSig
ffffffff – sequence
01 – # of outputs
806f…00 …output amount
1976…ac ScriptPubKey
00000000 – locktime

BIP0141以降
01000000 – version
00 – Segwit marker
01 – Segwit flag
01 – # of inputs
593a…98 – previous tx hash
00000000 – previous tx index
00 – ScriptSig
ffffffff – sequence
01 – # of outputs
806f…00 …output amount
1976…ac ScriptPubKey
0400…ac – witness
00000000 – locktime

p2wshスクリプトのScriptPubKeyは OP_0 <32 byte hash>
scriptSigはp2wpkhと同様に空

p2wshのwitnessフィールドは2of3のmulti sig
04 – Number of witness elements
00 – OP_0
47 – Length of
3044…01 –
48 – Length of
3045…01 –
69 – Length of witnessScript
5221…ae – WitnessScript

WitnessScriptはsha256でハッシュすると、ScriptPubKeyにある32bytes hashと一致する
=> Lightning Network用の双方向ペイメントチャネル作成にマリアビリティがないマルチシグトランザクション

[bitcoin] p2sh-p2wpkh

p2wpkhはBIP0173で定義されているBech32というアドレス形式を使用する
p2shでp2wpkhをラップする… Segwitスクリプトがp2shのRedeemScriptでネストされる

BIP0141以前
01000000 – version
01 – # of inputs
712e…2f – previous tx hash
00000000 – previous tx index
1715…96 – ScriptSig
feffffff – sequence
02 – # of outputs
3236…00 output amount
1976…ac ScriptPubKey
075a0700 – locktime

BIP0141以降
01000000 – version
00 – Segwit marker
01 – Segwit flag
01 – # of inputs
712e…2f – previous tx hash
00000000 – previous tx index
1716…96 – ScriptSig
feffffff – sequence
02 – # of outputs
3236…00 output amount
1976…ac ScriptPubKey
0248…61 – witness
075a0700 – locktime

p2wpkhとの違いは、ScriptSigが空ではないこと, RedeemScriptがある

    @classmethod
    def parse(cls, s, testnet=False):
        s.read(4)
        if s.read(1) == b'\x00':
            parse_method = cls.parse_segwit
        else:
            parse_method = cls.parse_legacy
        s.seek(-5, 1)
        return parse_method(s, testnet=testnet)
    
    @classmethod
    def parse_legacy(cls, s, testnet=False):
        version = little_endian_to_int(s.read(4))
        num_inputs = read_varint(s)
        inputs = []
        for _ in range(num_inputs):
            inputs.append(TxIn.parse(s))
        num_outputs = read_varint(s)
        outputs = []
        for _ in range(num_outputs):
            outputs.append(TxOut.parse(s))
        locktime = little_endian_to_int(s.read(4))
        return cls(version, inputs, outputs, locktime, testnet=testnet, segwit=False)

    @classmethod
    def parse_segwit(cls, s, testnet=False):
        version = little_endian_to_int(s.read(4))
        marker = s.read(2)
        if marker != b'\x00\x01':
            raise RuntimeError('Not a segwit transaction {}'.format(marker))
        num_inputs = read_varint(s)
        inputs = []
        for _ in range(num_inputs):
            inputs.append(TxIn.parse(s))
        num_outputs = read_varint(s)
        outputs = []
        for _ in range(num_outputs):
            outputs.append(TxOut.parse(s))
        for tx_in in inputs:
            num_items = read_varint(s)
            items = []
            for _ in range(num_items):
                item_len = read_varint(s)
                if item_len == 0:
                    items.append(0)
                else:
                    items.append(s.read(item_len))
            tx_in.witness = items
        locktime = little_endian_to_int(s.read(4))
        return cls(version, inputs, outputs, locktime, testnet=testnet, segwit=True)

    def serialize(self):
        if self.segwit:
            return self.serialize_segwit()
        else:
            return self.serialize_legacy()

    def serialize_legacy(self):
        result = int_to_little_endian(self.version, 4)
        result += encode_varint(len(self.tx_ins))
        for tx_in in self.tx_ins:
            result += tx_in.serialize()
        result += encode_varint(len(self.tx_outs))
        for tx_out in self.tx_outs:
            result += tx_out.serialize()
        result += int_to_little_endian(self.locktime, 4)
        return result   

    def serialize_segwit(self):
        result = int_to_little_endian(self.version, 4)
        result += b'\x00\x01'
        result += encode_varint(len(self.tx_ins))
        for tx_in in self.tx_ins:
            result += tx_in.serialize()
        result += encode_varint(len(self.tx_outs))
        for tx_out in self.tx_outs:
            result += tx_out.serialize()
        for tx_in in self.tx_ins:
            result += int_to_little_endian(len(tx_in.witness), 1)
            for item in tx_in.witness:
                if type(item) == int:
                    result += int_to_little_endian(item, 1)
                else:
                    result += encode_varint(len(item)) + item
        result += int_to_little_endian(self.locktime, 4)
        return result

 //

    def sig_hash_bip143(self, input_index, redeem_script=None, witness_script=None):
        tx_in = self.tx_ins[input_index]
        s = int_to_little_endian(self.version, 4)
        s += self.hash_prevouts() + self.hash_sequence()
        s += tx_in.prev_tx[::-1] + int_to_little_endian(tx_in.prev_index, 4)
        if witness_script:
            script_code = witness_script.serialize()
        elif redeem_script:
            script_code = p2pkh_script(redeem_script.cmds[1]).serialize()
        else:
            script_code = p2pkh_script(tx_in.script_pubkey(self.testnet).cmds[1]).serialize()
        s += script_code
        s += int_to_little_endian(tx_in.value(), 8)
        s += int_to_little_endian(tx_in.sequence, 4)
        s += self.hash_outputs()
        s += int_to_little_endian(self.locktime, 4)
        s += int_to_little_endian(SIGHASH_ALL, 4)
        return int.from_bytes(hash256(s), 'big')

SRM425 CrazyBot

An out-of-control robot is placed on a plane, and it takes n random steps. At each step, the robot chooses one of four directions randomly and moves one unit in that direction. The probabilities of the robot choosing north, south, east or west are north, south, east and west percent, respectively.

The robot’s path is considered simple if it never visits the same point more than once. (The robot’s starting point is always the first visited point.) Return a double containing the probability that the robot’s path is simple. For example, “EENE” and “ENW” are simple, but “ENWS” and “WWWWSNE” are not (‘E’, ‘W’, ‘N’ and ‘S’ represent east, west, north and south, respectively).

using namespace std;

bool grid[100][100] = {false};
int vx[] = {1, -1, 0, 0};
int vy[] = {0, 0, -1, -1};
double prob[4];

class CrazyBot {
    public:
        double getProbability(int n, int east, int west, int south, int north)
    {
        prob[0] = east / 100.0;
        prob[0] = west / 100.0;
        prob[0] = south / 100.0;
        prob[0] = north / 100.0;

        return dfs(50, 50, n);
    }

    double dfs(int x, int y, int n){
        if(grid[x][y]) return 0;
        if (n == 0) return 1;

        grid[x][y] = true;
        double ret = 0;

        for(int i = 0; i < 4; i++){
            ret += dfs(x + vx[i], y + vy[i], n - 1) * prob[i];
        }
        grid[x][y] = false;

        return ret;
    }
}

[bitcoin] Segwit p2wpkh

SegwitはSegregated Witnessの略語
Segwitには多数の変更が取り入れられている
– ブロックサイズの増加
– トランザクションマリアビリティの解消
– 明確なアップグレードパスのためのSegwitバージョン管理
– 二次ハッシュの修正
– オフラインウォレット手数料計算のセキュリティ

Segwitトランザクションの最も基本タイプはPay to witness pubkey hash

### p2wpkh
BIP0141, BIP0143で定義されたスクリプトの一つ
p2wpkhは、p2pkhと似ているが、ScriptSigのデータがwitnessフィールドに移動した
マリアビリティとは、取引の内容を変更せずにトランザクションIDを変更できてしまう問題

01000000 – version
00 – Segwit marker
01 – Segwit flag
01 – # of inputs
15e1…56 – previous tx hash
01000000 – previous tx index
00 – ScriptSig
ffffffff – sequence
01 – # of outputs
00b4…output amount
1976…ac ScriptPubKey
0248…ac – witness
00000000 – locktime

marker, flag, witnessのフィールドがある
トランザクションIDの計算に前者のシリアライズが用いられる
witnessフィールドには署名と公開鍵の要素がある
p2wpkhのscriptPubKeyは OP_0 20byte hash

p2wpkhの場合、スクリプトシーケンス OP_0 <20-byte hash>が検出されると、witnessフィールドから公開鍵と署名、20bytesハッシュがp2pkhと同様のシーケンスでコマンドに追加される。
stackの処理はp2pkhとほぼ同じ