楕円曲線論はじめの一歩 (3)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は「足し算」とは何か。つまり「群」について語りました。
今回は、「モノの個数」以外にも「群」の条件を満たすものがあるので、
それについて見ていきましょう。

時計の短針、実は群

f:id:y-hoshizuki:20181225191622p:plain

これは 1 時間に 1 つずつ進んでいく時計の時針です。

モノの個数ではないですが、これも実は群の条件を満たしています。
1 つずつ確認してみましょう。

演算に対して閉じている

1 時から 1 時間経つと 2 時。
3 時から 4 時間経つと 7 時。
8 時から 6 時間経つと 14 時...かと思いきや 2 時。

ちゃんと演算に対して閉じていますね。

結合法則

1 時から 2 時間経って、さらに 3 時間経つと 6 時。
2 時間と 3 時間、あわせて 5 時間が 1 時から経過すると 6 時。

ちゃんと成り立ちますね。

単位元

0 時から n 時間経てば n 時。
n 時から 0 時間経っても n 時。

間違いなく単位元です。

逆元

3 時の 3 時間前は 0 時。
5 時の 5 時間前も 0 時。

逆元はきちんと存在しています。

記号の世界の言葉で説明してみる

今の短針の位置、つまり 0 時からの経過時間を x、追加する経過時間を y としましょう。
この時計の短針の位置は (x + y) \bmod 12 で計算できます。
mod は剰余、つまり「あまり」のことで、x と y を足して、12 で割ったあまりが、
新しい短針の位置になります。

このように、ぐるっと回って元に戻る構造をしている群のことを「巡回群」と呼び、
特に「巡回群」の要素となっている元の個数が有限であるもののことを「有限巡回群」と呼びます。

数学の世界では、12 個の要素からなっている有限巡回群\mathbb{Z}/12\mathbb{Z} と書いたりします。

まとめ

モノの個数以外にも、群の条件を満たすものがあり、
その一例を見てみました。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

楕円曲線論はじめの一歩 (2)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は「1+1」を題材に、「1ってそもそも何?」「抽象的な考え方」について
語りました。お気づきの方はいると思いますが、途中で投げかけた質問、
「+ ってどういう意味?」についてはスルーしていました。
今回はそこから語ろうと思います。

「足し算」と呼んでもいい条件

+ も 1 と同じく単なる記号で、「足し算」であることを示しています。
じゃぁ、「足し算」って何でしょう?

これについては、過去の偉い人たちが散々検討を重ねた結果、
「最低限、4 つの条件を満たせば『足し算』と呼んでも差し支えないのではないか」
という結論を得ました

その 4 つを順に見ていきましょう。

「りんごの個数」と「りんごの個数」を足したら「りんごの個数」

当たり前といえば当たり前です。
これを満たさないものは足し算ではありません。

例えば、「りんごの個数」と「小麦粉の量」を足して「アップルパイの個数」
なんてものは足し算とは呼べません。

これを専門用語で「演算に対して『閉じている』」と表現します。
答えがアップルパイになってしまったら「閉じていません」。

(1+2)+3 = 1+(2+3)

足し算がいくつか並んでる場合、どの順で計算しても結果が変わらない、ということです。

1+2 に 3 を足しても、1 に 2+3 を足しても結果は同じ。

モノの個数で考えているうちは当然のことですが、
いずれ「個数」じゃないものを扱い始めると実は重要な条件です。

小学校でも習ったと思います、「結合法則」というやつです。

0 がある

0 に何を足しても答えは変わらず(0+?=?)。何に 0 を足しても答えは変わらず(?+0=?)。
そんな性質を持つ「記号」が必ず 1 つあることです。

これを専門用語で「単位元」と呼びます。

ちなみに単位元は 2 つ以上存在できません。
証明は省略します。

マイナスの数がある

ちょっとややこしいですが、
要するに引き算のことも同じに扱うことで、
足し算について考えるだけにしたいんです。

「3 を引く」のは「-3 を足す」のと同じ、というわけです。
わざわざ引き算の概念を作らなくても、マイナスがあれば、
足し算の概念だけですべて片付きます。

つまり、本質的には足し算も引き算も同じものである、と言いたいわけですね。

マイナスのことを専門用語で「逆元」と呼びます。
何が逆なのか?「3」の逆が「-3」というイメージです。

ある記号と、その逆元を足したら 0 になる。という条件です。

4 つの条件を満たしたら「足し算」と呼ぶ

ここまでで並べた 4 つの条件こそが、「モノの個数の足し算」から
具体的な要素を極限までそぎ落とした、いわば「足し算の本質」です。

この足し算の本質を満たす計算と、その計算ができる記号(今回は数字ですね)、この 2 つを
セットにして「群」と呼んでいます。

そして、「群」の要素となっている記号のことを「元」と呼びます。

まとめ

今回は、足し算というものの本質、群についてお話しました。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

楕円曲線論はじめの一歩 (1)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

今回は、暗号通貨で電子署名に使われている、楕円曲線暗号について語ろう...
と思ったのですが、楕円曲線暗号の実装方法や簡単な説明は、イマドキありふれているので、
ここはもう少し踏み込んで、楕円曲線論について語ろうと思います。

このあたりの話になってくると、難しい言葉や難しそうな数式がたくさん出てくる説明なら
WikipediaGoogle で探せば見当たりますが、数学に造詣がないと読み解くのは困難だと思います。
なので、証明や厳密な定義などはそちらにおまかせする方向で、
概念の生まれた背景や考え方のような、ストーリー性に重点を置いて語っていければと思います。

すべてのはじまり、1+1 は?

初っ端から「バカにしてるのか?」と思われそうなタイトルですが、
いたって大真面目です。もちろん、小学一年生でもわかるような 2 という話でも
ないですし、「田んぼの田」みたいななぞなぞでもありません。

注目したいのは以下の点です。

  1. そもそも 1 ってなに?
  2. + ってどういう意味?

どうでしょう?小学校で天下り式に教わった数式ですが、
実はちゃんと説明できる人は多くないのではないでしょうか?

小学校ではどう教わった?

イマドキの学習指導要領でどうなってるかは知りませんが、
私のころは、りんごやおはじきで習いました。

f:id:y-hoshizuki:20181225190936p:plain

りんご1個とりんご1個、あわせるとりんごが2個。

ここで重要な事実が1つ、みんな当たり前に受け入れてきたことですが、
「実はりんごじゃなくてバナナでも同様なことが言える」のです。

つまり、りんごにこだわる必要は特になくて、
りんごとかバナナとか、梨とかみかんが、1個あることを
数式の中では「1」と表記しているのです。

言い方を変えれば、「1」というのは「何か」を示す「ただの記号」でしかなくて、
実は「#」とか好きな文字であっても良かったんです。
ここが混乱の元となるのですが、本文中で「1個」というときの1と、
数式の中で出てくる「1」は意味が違うのです。

f:id:y-hoshizuki:20181225191013p:plain

本文中で「りんごが1個」と言っているの「1」は「具体例の世界」の話、
「1+1」と数式で書いているときの「1」は「記号の世界」の話。

こんな風に、具体例から一旦記号に置き換えて、「計算」と呼ばれる作業をしてから
元の具体例の世界に戻ってくる。
...ということをやっていたのが、小学一年生で習った算数なのです。

どうでしょう?実は意外に複雑なことをやっていましたね?

どうしてそんな面倒な手順を踏むのか?

「記号の世界」つまり「数式の世界」であれば、これまで発明された
いろいろな公式がそのまま使えて便利だから、に他なりません。

言い方を変えれば、記号の世界で考案された公式の方が、より「汎用的」であるわけです。

また、記号の世界には具体的な概念がほとんど登場しなくなります。
これは具体例の要素を可能な限りそぎ落として、本質だけを捉えて扱うということです。

このように、記号の世界に一旦変換して物事を考えることを「抽象化」と呼び、
抽象化して「本質について」だけを考えることこそ、
「数学」という学問の真髄とも言えると思います。

まとめ

今回は 1+1 の数式から始まり、1 とは何か?抽象化とか何か?
というあたりについて語りました。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

暗号通貨のトランザクションを手作りする (8)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回までで raw トランザクションの作り方は一通り説明し終わりました。
今回はおまけ的な位置づけで、コインアドレスについて説明します。

コインアドレス

コインアドレスは、公開鍵ハッシュと相互に変換可能な文字列なので、
公開鍵ハッシュの代わりにやり取りするときに便利に使えます。

前回、手作りしたトランザクション
TXID 661b7e85f863232aff7344acd268bb9eaab306fc8b806d3e6101244c6d06c373
ですが、その直前のトランザクションとなる
TXID c37ab04631eef5813077fbbaae44e01bf26f9cab86426316ba81f99e2c9e8282
はどうやって作ったと思いますか?

実は、公開鍵ハッシュからコインアドレスを生成して、そこに送金しただけです。

ではコインアドレスの作成方法を見ていきましょう。

公開鍵ハッシュは db2e054bb576dc63283c0060abd46df14057c2de でしたね。
まずは先頭にモナコインのテストネットを表すプレフィックス、6f をつけます。

そして、sha256 を 2 回計算して、チェックサムを作ります。

$ printf "%b" "\x6f\xdb\x2e\x05\x4b\xb5\x76\xdc\x63\x28\x3c\x00\x60\xab\xd4\x6d\xf1\x40\x57\xc2\xde" | openssl sha -sha256 -binary | openssl sha -sha256
(stdin)= 1320a8f11585dd4764f6c8ffe4bd8824585d737b821b4b928a40be5e483e4f36

この先頭 4 Byte の「1320a8f1」がチェックサムです。

プレフィックス、公開鍵ハッシュ、チェックサムの 3 つをつなげると
6fdb2e054bb576dc63283c0060abd46df14057c2de1320a8f1
となります。

これを、Base58 エンコードすればコインアドレスの完成です。
Bass58 エンコードといっても、要はただの 58 進数なので、多倍長整数が扱える言語なら
簡単なコードで変換できます。

例えば python で書いてみましょう。

# util.py

def b58encode( src ):
	mapping = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

	r = ''
	n = long( src, 16 )
	for i in range( 0, 34 ):
		r = mapping[n % 58] + r
		n = n / 58

	return r

実行してみます。

$ python
>>> import util
>>> util.b58encode( '6fdb2e054bb576dc63283c0060abd46df14057c2de1320a8f1' )
'n1VsQdyHFc15HzZMxfGgEC2zRQKWqu4XSQ'

はい、できました。

あとは、このコインアドレスに送金すれば、
TXID c37ab04631eef5813077fbbaae44e01bf26f9cab86426316ba81f99e2c9e8282
が作られます。

今回の連載はこれで終了となります。
みなさん、お付き合いいただき、ありがとうございました。
ご質問、ご意見等ありましたらお気軽にリプライください。

暗号通貨のトランザクションを手作りする (7)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回までで、P2PKH で必要な「電子署名」「公開鍵」「公開鍵のハッシュ値」ができました。
今回は raw トランザクションを完成させてブロックチェーンに取り込んでもらいましょう。

scriptSig の組み立て

P2PKH の scriptSig は以下の形式でした。

PUSH 電子署名
PUSH 公開鍵

これにあわせて scriptSig を組み立てます。
1点注意、openssl dgst で作った電子書名は DER 形式というフォーマットになっているため、
そのまま使えますが、OP_CHECKSIG はその後ろに 01 をつけたものを PUSH する必要があります。

47                        ... 前回作った電子署名の長さ + 1 (PUSH 命令)
30 44 02 20 5C 66 D2 C6 F1 AE 9D 91 D4 10 3F 4F
40 B7 26 CC 9C 27 21 42 B1 A1 7F CE B5 23 74 45
FD BD 95 63 02 20 21 F1 2C 9D A7 7E AC 95 35 31
61 6E E6 73 DC 19 69 A0 48 C3 C1 6A EB 60 22 E0
D2 E8 CA D3 E6 4F         ... 前回作った電子署名
01                        ... 後ろにくっつける

21                        ... 公開鍵の長さ (PUSH 命令)
02 B4 EE A1 4B 61 45 A8 97 F8 75 61 3C 80 FE 3B
3F 50 D4 69 A5 B2 88 6B 50 5F 55 F6 A3 08 B9 E8
74                        ... 第5回で作った公開鍵

本番用 raw トランザクションの組み立て

前回仮組みしたのと同じ構成にする必要があります。
scriptSig は今回は正しく電子署名の入ったものを使います。

02 00 00 00      ... バージョン 2
01               ... 入力は 1 つ

入力データ
 82 82 9E 2C 9E F9 81 BA 16 63 42 86 AB 9C 6F F2
 1B E0 44 AE BA FB 77 30 81 F5 EE 31 46 B0 7A C3
                  ... 前 TXID: c37ab04631eef5813077fbbaae44e01bf26f9cab86426316ba81f99e2c9e8282
 00 00 00 00      ... 前 TX の第0出力を使用する
 6A               ... scriptSig の長さ 106 Byte
 47
 30 44 02 20 5C 66 D2 C6 F1 AE 9D 91 D4 10 3F 4F
 40 B7 26 CC 9C 27 21 42 B1 A1 7F CE B5 23 74 45
 FD BD 95 63 02 20 21 F1 2C 9D A7 7E AC 95 35 31
 61 6E E6 73 DC 19 69 A0 48 C3 C1 6A EB 60 22 E0
 D2 E8 CA D3 E6 4F
 01
 21
 02 B4 EE A1 4B 61 45 A8 97 F8 75 61 3C 80 FE 3B
 3F 50 D4 69 A5 B2 88 6B 50 5F 55 F6 A3 08 B9 E8
 74               ... 正しい scriptSig
 00 00 00 00      ... シーケンス番号はとりあえず 0

01               ... 出力は 1 つ

出力データ
 C0 9E E6 05 00 00 00 00 ... 0.99 tMONA
 19               ... scriptPubKey は 25 Byte
 76 A9 14
 DB 2E 05 4B B5 76 DC 63 28 3C 00 60 AB D4 6D F1 40 57 C2 DE
 88 AC            ... scriptPubKey 本体

00 00 00 00      ... ロックタイムはとりあえず 0

これで P2PKH の raw トランザクションが完成しました。


後はこの16進文字列を、

$ monacoin-cli sendrawtransaction "0200000001...00000000"

とコインノードに送りつければ、ブロードキャストされてブロックチェーンに取り込まれます。

こうしてできたのが、
TXID 661b7e85f863232aff7344acd268bb9eaab306fc8b806d3e6101244c6d06c373
です。

今回はここまで。あと 1 回だけ続きます。
ご質問、ご意見等ありましたらお気軽にリプライください。

暗号通貨のトランザクションを手作りする (6)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は秘密鍵と公開鍵のペアを作って、公開鍵のハッシュ値を求めました。
今回は電子署名を作ってみましょう。

OP_CHECKSIG の仕様

電子署名を作るには、OP_CHECKSIG の仕様を知る必要があります。

...とはいえ、実際に使われているパターンは1つしかないので、
それだけ覚えてもらえれば十分です。

bitcoin wiki の OP_CHECKSIG
ページに図と共に詳細な説明がありますが、もう少し噛み砕いて説明します。

  1. まず、UTXO の scriptPubKey を取り出します。
  2. 新規トランザクションの scriptPubKey を設計します。
  3. 次に、新規トランザクションの scriptSig を全部空っぽ、長さは 0 にしたデータを作ります。
  4. 電子署名を作る対象の入力データだけ、scriptSig の部分に、取り出した scriptPubKey を挿入します。
  5. この状態のデータの SHA256 ハッシュを2度計算して、電子署名を作成します。

具体的には図のように作ります。

f:id:y-hoshizuki:20181022130426p:plain

電子署名は scriptSig ごとに作る必要があるため、
入力が複数ある場合はこのようになります。

f:id:y-hoshizuki:20181022130435p:plain

さて、それでは実際に作ってみましょう。
今回は monacoin のテストネットで実験してみます。
自分から自分に送る単純なトランザクションです。

UTXO の scriptPubKey

P2PKH を使っているなら以下の形式で固定です。

76   ... OP_DUP
A9   ... OP_HASH160
14   ... 公開鍵のハッシュの長さ (PUSH 命令)
DB 2E 05 4B B5 76 DC 63 28 3C 00 60 AB D4 6D F1 40 57 C2 DE ... 公開鍵のハッシュ
88   ... OP_EQUALVERIFY
AC   ... OP_CHECKSIG

長さは 25Byte です。

新規トランザクションの scriptPubKey

P2PKH で出力するなら先ほどと同じです。

76   ... OP_DUP
A9   ... OP_HASH160
14   ... 公開鍵のハッシュの長さ (PUSH 命令)
DB 2E 05 4B B5 76 DC 63 28 3C 00 60 AB D4 6D F1 40 57 C2 DE ... 公開鍵のハッシュ
88   ... OP_EQUALVERIFY
AC   ... OP_CHECKSIG

長さも同じく 25Byte です。

新規トランザクションの準備

第3回で説明した通りに scriptSig を空っぽの状態で raw トランザクションを作ります。

02 00 00 00      ... バージョン 2
01               ... 入力は 1 つ

入力データ
 82 82 9E 2C 9E F9 81 BA 16 63 42 86 AB 9C 6F F2
 1B E0 44 AE BA FB 77 30 81 F5 EE 31 46 B0 7A C3
                  ... 前 TXID: c37ab04631eef5813077fbbaae44e01bf26f9cab86426316ba81f99e2c9e8282
 00 00 00 00      ... 前 TX の第0出力を使用する
 00               ... scriptSig は 0 Byte
 00 00 00 00      ... シーケンス番号はとりあえず 0

01               ... 出力は 1 つ

出力データ
 C0 9E E6 05 00 00 00 00 ... 0.99 tMONA
 19               ... scriptPubKey は 25 Byte
 76 A9 14
 DB 2E 05 4B B5 76 DC 63 28 3C 00 60 AB D4 6D F1 40 57 C2 DE
 88 AC            ... scriptPubKey 本体

00 00 00 00      ... ロックタイムはとりあえず 0

電子署名対象となる入力だけ、scriptSig を埋める

同じなので区別がつきづらいですが、
トランザクションから抽出した scriptPubKey を、
scriptSig を埋めるべき場所に配置します。

そして末尾に 01 00 00 00 をくっつけます。

02 00 00 00      ... バージョン 2
01               ... 入力は 1 つ

入力データ
 82 82 9E 2C 9E F9 81 BA 16 63 42 86 AB 9C 6F F2
 1B E0 44 AE BA FB 77 30 81 F5 EE 31 46 B0 7A C3
                  ... 前 TXID: c37ab04631eef5813077fbbaae44e01bf26f9cab86426316ba81f99e2c9e8282
 00 00 00 00      ... 前 TX の第0出力を使用する
 19               ... scriptSig ではなく前トランザクションの scriptPubKey の長さは 25 Byte
 76 A9 14
 DB 2E 05 4B B5 76 DC 63 28 3C 00 60 AB D4 6D F1 40 57 C2 DE
 88 AC            ... 前トランザクションの scriptPubKey 本体
 00 00 00 00      ... シーケンス番号はとりあえず 0

01               ... 出力は 1 つ

出力データ
 C0 9E E6 05 00 00 00 00 ... 0.99 tMONA
 19               ... scriptPubKey は 25 Byte
 76 A9 14
 DB 2E 05 4B B5 76 DC 63 28 3C 00 60 AB D4 6D F1 40 57 C2 DE
 88 AC            ... scriptPubKey 本体

00 00 00 00      ... ロックタイムはとりあえず 0

01 00 00 00      ... くっつける

SHA256 ハッシュを2度計算して電子署名を作成する

うまく整形してバイナリ形式で openssl に流し込みます。
openssl dgst で1回 sha256 を計算するので、先に一度 sha256 を計算しておく必要があることに注意してください。

$ printf "%b" "\x02\x00\x00\x00\x01\x82\x82\x9E\x2C\x9E\xF9\x81\xBA\x16\x63\x42\x86\xAB\x9C\x6F\xF2\x1B\xE0\x44\xAE\xBA\xFB\x77\x30\x81\xF5\xEE\x31\x46\xB0\x7A\xC3\x00\x00\x00\x00\x19\x76\xA9\x14\xDB\x2E\x05\x4B\xB5\x76\xDC\x63\x28\x3C\x00\x60\xAB\xD4\x6D\xF1\x40\x57\xC2\xDE\x88\xAC\x00\x00\x00\x00\x01\xC0\x9E\xE6\x05\x00\x00\x00\x00\x19\x76\xA9\x14\xDB\x2E\x05\x4B\xB5\x76\xDC\x63\x28\x3C\x00\x60\xAB\xD4\x6D\xF1\x40\x57\xC2\xDE\x88\xAC\x00\x00\x00\x00\x01\x00\x00\x00" | openssl sha -sha256 -binary | openssl dgst -sha256 -sign wallet.pem -hex
(stdin)= 304402205c66d2c6f1ae9d91d4103f4f40b726cc9c272142b1a17fceb5237445fdbd9563022021f12c9da77eac953531616ee673dc1969a048c3c16aeb6022e0d2e8cad3e64f

これで、電子署名は完成です。

電子署名は乱数を使用するため毎回異なる署名が出力されます。
今は詳しく説明しませんが、正規化ルールの都合があるので、
何度か実行して 3044 から始まるものを選んでください。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

暗号通貨のトランザクションを手作りする (5)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は P2PKH の動作原理について解説しました。
それでは実際にテンプレートを埋める方法について説明していきます。

各要素とコインアドレスの関係

まずは各要素の関係について確認しておきましょう。

f:id:y-hoshizuki:20181022130337p:plain

基本的に一方通行ですが、コインアドレスと公開鍵のハッシュだけ、
相互に変換可能なところに注意してください。

秘密鍵と公開鍵のペアを作成する

openssl を使うと簡単に作れます。
secp256k1 という名前の曲線を使いますが、比較的新しいバージョンの openssl でないと
使えないので注意してください。

$ openssl ecparam -genkey -name secp256k1 -out wallet.pem
$ openssl ec -in wallet.pem -conv_form compressed -text
Private-Key: (256 bit)
priv:
    00:8d:6a:af:b3:37:d6:e3:dd:5a:96:c1:54:95:c6:
    cd:4b:65:1e:52:d0:82:e3:e2:a7:89:28:35:bb:94:
    9c:e1:07
pub:
    02:b4:ee:a1:4b:61:45:a8:97:f8:75:61:3c:80:fe:
    3b:3f:50:d4:69:a5:b2:88:6b:50:5f:55:f6:a3:08:
    b9:e8:74

priv が秘密鍵 256bit、pub が compressed 形式の公開鍵です。

公開鍵のハッシュを求める

次は公開鍵のハッシュを求めます。
公開鍵の : を \x に置換して繋げてから、
openssl で sha256, ripemd160 の順でハッシュを計算します。

$ printf "%b" "\x02\xb4\xee\xa1\x4b\x61\x45\xa8\x97\xf8\x75\x61\x3c\x80\xfe\x3b\x3f\x50\xd4\x69\xa5\xb2\x88\x6b\x50\x5f\x55\xf6\xa3\x08\xb9\xe8\x74" | openssl sha -sha256 -binary | openssl sha -ripemd160
(stdin)= db2e054bb576dc63283c0060abd46df14057c2de

これが公開鍵のハッシュです。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。