Photo by BTC Keychain
秋山です。
先日、ブロックチェーンとPoWについて、Pythonコードを交えつつ解説する記事を書きました。
paiza.hatenablog.com
前回は、あくまで一つのプログラム上でブロックチェーンを作って、その中でPoWを行う…という話でした。今回は、複数人が取引を行う際に自分の取引が改ざんされてしまわないよう、自分の取引に署名をするときに扱われている楕円曲線暗号の話をメインに書いてみたいと思います。
■秘密鍵と公開鍵とアドレスについて
皆さんは、Bitcoinのアドレスの形式がどんなものか知っていますか？
Bitcoinのアドレスは、Base58でエンコードされた、最初が1もしくは3で始まる文字列となります。アドレスの生成手順に関しては、以前こちらの記事で書いたので、興味のある方はごらんください。
paiza.hatenablog.com
↑の記事では、アドレス生成の流れを書いているだけで詳しい解説はしていませんが、Bitcoinのアドレスは以下の要素から構成されます。
【秘密鍵】
- ランダム性が保証された値
- 通貨の保持者以外に漏えいしてはならない
【公開鍵】
- 秘密鍵から楕円曲線暗号を使って生成される
- ブロックチェーンの取引データを確認するために必要となる
【アドレス】
- 公開鍵から生成される
- 一般的に、判読の間違いが起こらないように特殊なエンコードが行われる
※Bitcoinの場合、「1」と「l」は判読しづらいため「l」は禁止…などといったルールもあります。
上記の通り、秘密鍵→公開鍵→アドレス…という流れで作られていくわけですが、最初に作られる秘密鍵以降は、すべて一方向性の数学的処理が行われます。たとえば逆順にアドレス→公開鍵→秘密鍵といった感じで逆算することは、ほぼ無理…極めて困難な行為…ということになっています。
前述したアドレス生成の記事では、OpenSSLを使って秘密鍵と公開鍵のペアを生成し、そこからアドレスを生成する処理についてを書きました。公開鍵→アドレスの生成に関しては、ハッシュ化処理と判読性を高めるためにBase58化する…という処理になっています。
今回はOpenSSLでやっている部分を具体的に説明していきます。
秘密鍵と公開鍵のペアの生成について
公開鍵は楕円曲線暗号によって秘密鍵から作られる…と書きましたが、Bitcoinでは secp256k1 と呼ばれる楕円曲線暗号が使われています。実際に使われている楕円曲線の図やパラメーターはこちら（Secp256k1 - Bitcoin Wiki）。
この楕円曲線から公開鍵を求める流れですが、ざっくり文章にすると「Bitcoin上で決められた G から秘密鍵分足し算した楕円曲線上の点を公開鍵とする」ということになります。
前述のwikiを引用すると、Bitcoinで使われている G は
G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
…ということになります。
ちょっとよくわかんないですね。
楕円曲線について
楕円曲線の話をします。楕円曲線が具体的にどんなものかというと、
y^2 = x^3 + ax + b
が一般的な式で、この式を a = 0, b = 7としたものがBitcoinで使われている楕円曲線となります。
式にすると
y^2 = x^3 + 7 Mod p
となります。
pは巨大な素数で、Bitcoinでは p = 2^256-2^32-2^9-2^8-2^7-2^6-2^4-1 とされています。
式だけ見てもよくわかんないので、グラフにしてみるとこんな感じになります。
このグラフ上のGを秘密鍵分足し算するとはどういうことなのか？
楕円曲線上の足し算で A + B を足す…という場合、二点を結んだ直線の接線で x 軸の対称の位置となります。
秘密鍵分の足し算を行うということは…最悪の場合、秘密鍵の範囲の最大値まで足し算しなくてはならず、かなり厳しい話ですよね。そのため、楕円曲線上の倍算は以下のように考えます。
2 * G というのは、楕円曲線上においては G の接線を引いて、楕円曲線上にその接線の交わる点の x 軸の対称の位置にある点です。(今回のGは仮で置いているので、Bitcoinで決められたGとは違う位置です)
図にするとこんな感じですね。
4 * G はこんな感じ。
…こんな感じで、点が移動していきます。ちなみに、対称移動しない場合はマイナス倍したと考えてよいので、 G の接線の公転は -2 *G と捉えてもよいです。
楕円曲線上の離散対数問題を解く準指数関数時間アルゴリズムは今のところ見つかってないため、上記の 4 という数字が 4 * G の値からは逆算できない…つまり一方向性で安全であろう…ということになっています。
これで楕円曲線上での足し算と掛け算を獲得しました。ちなみに引き算は、楕円曲線上では現実的に不可能です(専門家ではないので厳密な表現ではないかもしれませんが…)。
「Bitcoin上で決められた G から秘密鍵分足し算した楕円曲線上の点を公開鍵とする」ということは、単純に考えると秘密鍵回数分足さなくてはなりませんよね。でも、前述のような足し算を繰り返すのは、鍵の総数を考えると現実的ではありません。
ここでは、double-and-addという手法を使います。(Elliptic curve point multiplication - Wikipedia)
簡単に説明すると、2進数にしたときに最も左の桁を除き、1の桁の時は倍算→足し算、0の時は倍算…とすることで、鍵を2進数にした桁数で秘密鍵回足した数値が算出できます。
…ちょっとよくわかんないですね。
適当な数字で考えると、たとえば 11 * 3 = 33 の場合、 11を2進数にすると1011です。最も左の桁を除いて、011を順に倍算、倍算→足し算、倍算→足し算としていくと、((3*2) * 2 + 3) * 2) +3 = 33 となります。
ということで、楕円曲線上の足し算、倍算、double and addによるn回の足し算…この3つの要素を使って楕円曲線上におけるGから秘密鍵分だけ足し算を行い、その楕円曲線上のある点を公開鍵とする…という処理をPythonで書いてみました。
こんな感じで鍵の計算ができるというわけです。
この辺はブロックチェーンやPoWと関係なく、取引データの秘密鍵さえ守っていれば、逆算して取引データを改ざんすることはできないであろう…という話ですね。
この鍵を使って署名をし、ブロックチェーンに追加をすると、公開鍵に対応したBitcoinアドレスにおいて、出力に関する取引が行われた…という記録となります。そして、Aさん→Bさんのような送金は、ブロックチェーンを見ているすべてのユーザーが確認できる状態となるわけです。
■まとめ
ということで、前回の記事とはちょっと方向を変えて、主に暗号に関する話と、Bitcoinで使われている楕円曲線暗号がどんなものなのかを解説してみました。
次回があれば、複数のプログラムが実際にトランザクションを投げ合っているような状態を、PaizaCloudを使ってやってみようかと思います。
ほかにも暗号通貨やPythonや機械学習などに関する記事をいろいろ書いているので、興味のある方は見てみてください。
paiza.hatenablog.com
paiza.hatenablog.com
「プログラミング自体が初心者なので、まずはPythonを使えるようになりたい！」という方は、プログラミングが動画で学べる「paizaラーニング」の「Python入門編」（今年から全編無料になりました）から始めてみてください。
途中でブログパーツとして使ったオンライン実行環境サービス「paiza.IO (パイザ・アイオー)」はこちら
「PaizaCloud」では、環境構築に悩まされることなく、ブラウザだけで簡単にWebサービスやサーバアプリケーションなどの開発・公開ができます。
「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。
詳しくはこちら
そしてpaizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら
