[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
SlideShare a Scribd company logo
Bitcoin勉強会(技術編)セッション1
主催:日本ネットワークセキュリティ協会 PKI相互運用WG・電子署名WG
Bitcoinを技術的に理解する (資料公開版)
© 2014 Fuji Xerox Co., Ltd. All rights reserved.
2014年6月2日(月) 15:00-17:00
於:セコムホール(原宿)
漆嶌 賢二
本文中の登録商標および商標はそれぞれの所有者に帰属します。
富士ゼロックス株式会社 SkyDeskサービスセンター 漆嶌賢二
はじめに
ビットコインにおいて、「トランザクションやブロック
がどのように署名されたり、ハッシュ計算をしているの
© 2014 Fuji Xerox Co., Ltd. All rights reserved.
がどのように署名されたり、ハッシュ計算をしているの
か」という良い解説書が無く、困っていたのでいろいろ
調査をして資料を作成してみました。みなさんの参考に
なれば幸いです。
今日のテーマ
2© 2014 Fuji Xerox Co., Ltd. All rights reserved.
•政府や企業が一極発行したものではない
•インターネットで流行りつつある
ビットコインとは?
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 3
•暗号技術を使った
•新しいアイディアの仮想通貨
• ビットコインで使われる暗号
– ハッシュ関数とは
– 楕円曲線公開鍵暗号(ECDSA署名)
• ビットコイン用語の説明(1)
• ビットコイン用語の説明(2)
– コインベーストランザクション
– ブロック
– ブロックマイニング
今日のテーマとアジェンダ(70~80分)
ビットコインの技術的概要は、既にご存知な方も多いでしょうから、簡
単におさらいするとして、どんなデータをどんな風に署名するのか、
ハッシュするか等、技術的に詳しく解説します。
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 4
• ビットコイン用語の説明(1)
– ウォレットとアドレスと鍵ペア
– トランザクション
– ビットコインのお金の正体
• ビットコインは仮想通貨の二重使
用みたいな問題をどのように技術
解決したのか?
• ビットコインの技術課題
– トランザクション展性
ビットコイン技術を理解する
のに必要な暗号技術(1/2)
ハッシュ関数
5© 2014 Fuji Xerox Co., Ltd. All rights reserved.
(セキュア)ハッシュ関数
こ の 夏 は 東 北 に 旅
行 に 行 き ま し た 。
こ の 夏 は 東 北 に 旅
行 に 行 き ま し た !
ハッシュ関数 ハッシュ関数
データの内容を識別するための固定の長さのデータを作る関数。
入力値の僅かな違いでも値は大きく異なり、大きなデータでも同じ固定の長さ
ハッシュ関数
23M
バイト
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 6
5291a4db88dc8f08ff0a
6e821ce1a671f8772e82
69cce7df56415d9d148a
2e7890f715d347606e05
0895eddb8c1e2d53bbcd
2e84fd83d6f918d924cb
入力データに変更や改竄がないか簡単に確認できる
電子署名や暗号通信などにも用いられる
BitCoinではデータのIDなどいろんな用途に使われる
SHA-1, MD5などが有名
一文字違うだけで全く違う値 入力データ長にかかわらず長さは同じ
ビットコインで使われるハッシュ関数
ビットコインでは2種類のハッシュ関数しか使われない
ハッシュ関数 出力長 説明
SHA-256 32バイト 米NSAが2001年に開発した米国家標準関数
RIPEMD-160 20バイト 独、ベルギーで1996年開発、ISO/IEC10118-3
ビットコインでは必ずハッシュ関数を二重にかける2通りの方法でしか使わない
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 7
データ入力 データ入力
SHA256
SHA256
SHA256
RIPEMD160
出力(32バイト) 出力(20バイト)
便宜上
本講演では
sha256d
と呼ぶ
(doubleのd)
便宜上
本講演では
hash160
と呼ぶ
ハッシュ関数の大切な特徴(一方向性関数)
データ入力 ハッシュ値ハッシュ
関数
とても簡単
ほぼ不可能
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 8
ハッシュ値
32ビット全部がゼロ
ハッシュ値
先頭8バイトがゼロ
ほぼ不可能
総当り攻撃で
とても時間がかかる
例えば?
ビットコイン技術を理解する
のに必要な暗号技術(2/2)
楕円曲線公開鍵暗号
9© 2014 Fuji Xerox Co., Ltd. All rights reserved.
楕円曲線公開鍵暗号(1)
楕円曲線は楕円ではない
y2 = x3 + ax + b
を満たす曲線を
「楕円曲線」という
注:楕円じゃない B
C
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 10
(性質)
直線を引くと多くの場合
3つの点A, B, Cで交わる
X軸で線対称
A
D
楕円曲線公開鍵暗号(2)
点の足し算=2つの点から3つ目を見つけること
2つの点A,Bから3つめの
交点Cを見つけ
そのX軸対称の点をDとする
①これを
B
C
A=B
C
A+B=D
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 11
と足し算で表す
A
B
D D
②接点A=Bの場合
A+B=D
A+A=D
③すると
A+A+…=nA
整数と点の掛け算
を定義できる
楕円曲線公開鍵暗号(3)
実数ではなく整数Iを素数pで割った余りでやる
曲線上の点のx、y座標が
「整数Iを素数pで割った余り」
で行う。実数でも余りでも性質は同じ。
4G
素数p p
nG
ある点nGが与えられ
た時、nが大きければ
nGからnを求めるの
は非常に難しい
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 12
G
2G
3G
4G
p
G
nG
n
素数p
基準点
(参考) 例えば素数p=263の場合
点をプロットするとこんな感じ n=1, 2, 3 … と軌跡を追うと
もうぐちゃぐちゃ
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 13
出典: http://www.johannes-bauer.com/compsci/ecc/
y=p/2で点が線対称になるとい
う特徴がある
これをp=256bitの巨大な整数で
やるから、もっとスゴイ事に!
楕円曲線公開鍵暗号(4)
楕円曲線を使った公開鍵暗号
G(x,y)
p
基準点
剰余の素数
曲線定数 a
曲線定数 b
曲線パラメータ
有名な所では
NIST P-256, 384, 521
secp256p1, 521p1等
パラメータは任意で良いの
ではなく、いくつかの団体
で安全なパラメータが
数十程度定義されている
ビットコインでは
secp256k1固定で使う
gx=x79be667ef9dc…
gy=x483ada7726a3…
p=xffffffff…
a=0
b=7
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 14
n nG
秘密鍵 公開鍵
公開鍵nGとパラメータG, p, a, bから秘密鍵nを見つけるのは困難
→ 公開鍵暗号として使える!!
(特徴) データが小さい(256bitの鍵なら、公開鍵65(or33)バイト、
秘密鍵32バイト、パラメータも固定で省略してる。)
楕円曲線公開鍵暗号(5)
ECDSA署名の生成と検証
秘密鍵d、パラメータ(生成点G, 剰余の素数n)があるとし、署名の度に乱数 k
(0≦k≦n)を生成し、Gからk回移動した点Rを定義し(R=kG=(rx, ry))、署名値 r, sを
求める。
)(mod
)(mod
n
nx
k
dre
s
rr
+
=
=
生成








==
y
x
r
r
kGR)(mHASHe =
メッセージハッシュe
Gから乱数k回
移動した点R
署名値 r, s
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 15
検証 公開鍵Q=dG、パラメータ(生成点G, 剰余の素数n)、署名値(r,s)があるとし、
以下の点Pを計算する。
Q
s
r
G
s
e
p
p
P
y
x
+=







=
このとき、px = rx (mod n)ならば署名値は正しい
等しければ検証成功
楕円曲線公開鍵暗号(6)
なぜECDSA署名の検証はこれでよいのか?
署名値rsとメッセージ
ハッシュeと公開鍵Qが
正しければ、
点Pと点Rが等しいので
px = rx であることを示そう。
( )
dG
s
r
G
s
e
Q
s
r
G
s
e
p
p
P
y
x
+=
+=







=
1
点Pの定義より
公開鍵Q=dGなので
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 16
点P=点R が示されたので px = rx となる。
署名の検証はこの等式でできる。
( )
( )
RkG
Grde
rde
k
Grde
s
==
+





+
=
+=
1共通項を括って
署名sの定義より
約分してR定義より
楕円曲線公開鍵暗号(7)
公開鍵データの表現方法(非圧縮/圧縮)
n nG
秘密鍵 公開鍵
公開鍵は二次元座標の点
公開鍵の表現方法は2種類ある
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 17
公開鍵の表現方法は2種類ある
非圧縮フォーマット
04 公開鍵nGのX座標(32バイト) 公開鍵nGのY座標(32バイト)
圧縮フォーマット
02 公開鍵nGのX座標(32バイト)
03 公開鍵nGのX座標(32バイト)
Yが偶数の時
Yが奇数の時
XからYはすぐ計算可能:y2=x3+ax+b
注)例は256bit鍵の場合
ビットコインの用語の説明(1)
① ウォレットとアドレスと鍵
② アドレス② アドレス
③ トランザクション
18© 2014 Fuji Xerox Co., Ltd. All rights reserved.
Bitcoinウォレットと
アドレスと
鍵
19© 2014 Fuji Xerox Co., Ltd. All rights reserved.
Bitcoinウォレット(財布)と
Bitcoinアドレスのイメージ
Bitcoinアドレス(小さな財布)
個々にお金が入る・口座番号(アドレス)を持つ
1abcde…
1zUb3…1hF3a…
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 20
Bitcoinウォレット(大きな財布袋)
直接はお金は入らない
Bitcoinの取引(出入金)のイメージ
Bitcoin P2Pネットワーク
②有償ボランティアで送
金の証拠を作りましょう③ transaction block
(=送金の証拠)
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 21
1abc…
1xyz…
アドレス間の
お金のやりとり
Bitcoinアドレスと秘密鍵/公開鍵
1abcdefgabcdefgabcdefgabcdefgabcdeアドレス
1uvwXyzuvwXyzuvwXyzuvwXyzuvwXyzabcアドレス公開鍵
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 22
ウォレット
アドレスにより
鍵を特定する
秘密鍵
公開鍵
BitCoinアドレス
23© 2014 Fuji Xerox Co., Ltd. All rights reserved.
•アドレス毎の公開鍵から生成することができ、公開鍵を特定す
ることができる。すなわち出金元、送金先を特定するID。
•文字 “1” と33字の英数字でできた文字列(例:1abF3…)
•base58checkエンコーディングを使用している
•base58checkエンコーディングとは公開鍵ハッシュとチェッ
クサムをbase58エンコーディングしたもの
Bitcoinのアドレスの特徴
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 24
クサムをbase58エンコーディングしたもの
•base58とはバイナリを58種の英数文字で表現したもの
(数字10種+大小文字26×2種-紛らわしい文字4種
エルl,アイI,オーO,ゼロ0を除く=10+26x2-4=58)
相手口座の入力ミスを防ぐことができる。
•base58はFlickrの画像のIDとしても使われている。
図説:base58check encodingの
公開鍵からアドレスの生成
40 40 40 40・・・ 40 40 40 40・・・ 40
secp256k1曲線
楕円暗号
公開鍵(65byte)
ヘッダ x座標(32byte) y座標(32byte=256bit)
hash160
c4 c5 98・・・ 27
中間ハッシュ値(20byte)
c4 c5 98・・・ 27
値コピー チェックサム生成
00
ヘッダ
1byte を意味します
scriptPubKey
中のハッシュ値
チェックサム生成
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 25
4a bb 8f ・・・1a
4a bb 8f 1ac4 c5 98・・・ 27
base58エンコード
J w 1・・・ TS S u b h m g 6 i1
ヘッダ
20byte
先頭4byte
1+33byte
Bitcoinアドレス
※:ハッシュ関数を使っているので、一方向性の変換
※:ウォレットの秘密鍵エクスポートでも使われる(WIF形式)
※:X.509 公開鍵証明書の鍵識別子(SKID/AKID)の複雑版と言えなくもない
32byte
sha256d
e2
鍵ハッシュ生成
トランザクション(取引履歴)
あるアドレス(小財布)からアドレスへお金が移った
という証拠データ(署名データ)ですという証拠データ(署名データ)です
26© 2014 Fuji Xerox Co., Ltd. All rights reserved.
トランザクションとは
出力0
Bさんに6BTC
Aさんの
取引記録
入力 出力(送金)
Aの署名
Aの署名
Tx?入力?
出力0
△さんに4BTC
出力1
Aさんに2BTC
入力 出力(送金)
◎の署名
1つの小財布(アドレス)の小銭をかき集めて
複数の小財布へお金の移動させる電子署名つき証拠データ
Tx1出力1
Tx2出力0
Tx1 Tx1の出力1のお金は使っ
ちゃいますよという証明
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 27
入力合算=出力合算+取引手数料
取引手数料= 0.0005BTC
出力1
Cさんに2BTC
入力8.0005BTC 出力8BTC
自分へのトランザクションをかき集めて、
好きに分配することができる
Aの署名
Aの署名
出力0
Aさんに
3.0005BTC
入力 出力(送金)
△の署名
△の署名
出力0
Aさんに3BTC
入力 出力(送金)
×の署名
Tx?入力?
Tx?入力?
Tx?入力?
Tx2出力0
Tx3出力0
Tx2
Tx3
大金の一部を使いたいとき
出力0
Bさんに
0.0004BTC
Aさんの取引記録
入力 出力(送金)
Aの署名
出力0
入力 出力(送金)
Tx1出力0
Tx1
残り(おつり)を自分に送金すればよい
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 28
取引手数料= 0.0001BTC
出力1
Aさんに8BTC
入力8.0005BTC 出力8BTC
出力0
Aさんに
8.0005BTC
×の署名Tx?入力?
おつりは自分
(Aさん)に戻せばよい
•以下の条件を満たせば取引手数料無料
– トランザクションデータが1000バイト未満の場合(一般にそう)
– 1取引中の全ての送金が0.01BTC(約600円)以上
– 取引プライオリティが十分に大きい場合
取引手数料(多分、チップみたいなもの)
https://en.bitcoin.it/wiki/Transaction_fees の定義があるが
実際には
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 29
実際には
•0〜0.001BTCの間で自由に払っているようだ
•0BTCで手数料を払わない人もいる
•0.0001〜0.0005BTC(6〜30円)ぐらいの人が多いようだ
•ウォレットクライアントで自由に設定できるようだ
•まさに、欧米流のチップの感覚なのではないかと思う
トランザクションデータの
構造
30© 2014 Fuji Xerox Co., Ltd. All rights reserved.
トランザクションのデータ構造(1)
0100000001aa02ce4965…
バージョン 01000000
入力数 01
前の出力ハッシュ 484d40…
前の出力インデックス 00000000入
PUSHDATA_47
ASN.1形式のECDSA署名値(R,S)
SIGHASH_ALL (全てを署名対象に)
PUSHDATA_41
トランザクションはバイト列
scriptSig スクリプト
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 31
前の出力インデックス 00000000
スクリプトバイト長 8a
署名スクリプト 473044…
シーケンス終端記号 ffffffff
入
力
①
出力数 01
出金額 626401…
スクリプトバイト長 8a
公開鍵検証スクリプト 8a
出
力
①
ブロックロック時間 00000000
EC公開鍵(x04 + X + Y)
OP_DUP
OP_HASH160
PUSHDATA 14
公開鍵ハッシュ値
OP_EQUALVERIFY
OP_CHECKSIG
scriptPubKey スクリプト
トランザクションと生データ
バージョン<4>
入力数<1>
前の取引ハッシュ<32>
前の出力インデックス<4>
スクリプトバイト長<1>
scriptSig
入
力
①
BさんからCさんへの署名済取引記録Tx1
署名値
01000000
01
b3bf2c8e11766b626d40fab1bd…
01000000
8b
48 304502210089f0ff17ffd33f…
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 32
scriptSig
シーケンス終端記号<4>
①
出力数<1>
出金額(BTC) <8>
scriptPubKey
送金先の参照
出
力
①
ブロックロック時間 <4>
公開鍵 41 04dc47f1c4bf5f98e01aac27…
ffffffff
01
302dfa0200000000
1976a91406f1b6......88ac
00000000
注意点:
数値、ハッシュ値、TXIDなどはリトルエンディアン(=バイト逆順)、
スクリプトの中のデータ(ASN.1署名値、公開鍵など)はビッグエンディアンで表現される。
BさんがCさんに送金する
トランザクションの参照関係
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 8a
scriptSig
B秘密鍵に
よる署名値
入
力
①
バージョン 01000000
入力数 01
前の取引ハッシュ 484d40…
前の出力インデックス 0
スクリプトバイト長 8a入
力
①
AさんがBさんに3BTC送金した取引記録 Tx0 BさんがCさんに2.9995BTC送金した取引記録Tx1
2cfd73…
sha256d(Tx0)
Bの公開鍵
A秘密鍵に
よる署名値
Aの公開鍵 公開鍵
署名値
scriptSig
公開鍵
署名値
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 33
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 3.0
scriptPubKey
送金先の参照
Bさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
取引手数料 0.0005 BTC
Bの公開鍵Aの公開鍵 公開鍵公開鍵
BさんがCさんに送金する
署名済トランザクションの生成 (1/5)
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
入
力
①
BさんからCさんへの署名前の取引記録Tx1tbs
とりあえず、
BからCに送金する
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 34
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
6ab3…秘密鍵
045b3…公開鍵
BさんのECC secp256k1
BからCに送金する
署名されていない枠は作る
BさんがCさんに送金する
署名済トランザクションの生成 (2/5)
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 19入
力
①
BさんからCさんへの署名前の取引記録Tx1tbs
scriptPubKey
送金元の参照
Bさんの
公開鍵
ハッシュ
署名値はまだ
決められないので
Bさんアドの
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 35
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
送金元の参照
ハッシュ
Hash Code Type 01000000
6ab3…秘密鍵
045b3…公開鍵
BさんのECC secp256k1
Bさんアドの
公開鍵ハッシュで仮置き
(=複数入力時の場所識別)
hash160
BさんがCさんに送金する
署名済トランザクションの生成 (3/5)
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 19入
力
①
BさんからCさんへの署名前の取引記録Tx1tbs
scriptPubKey
送金元の参照
Bさんの
公開鍵
ハッシュ
3fde9e…
SHA256^2(Tx1tbs)
二重ハッシュ計算
署名入力
sha256d
仮トランザクション
全体のダブルハッシュ
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 36
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
送金元の参照
ハッシュ
Hash Code Type 01000000
ECDSA
署名器
6ab3…秘密鍵
045b3…公開鍵
BさんのECC secp256k1
BさんがCさんに送金する
署名済トランザクションの生成 (4/5)
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 19入
力
①
BさんからCさんへの署名前の取引記録Tx1tbs
scriptPubKey
送金元の参照
Bさんの
公開鍵
ハッシュ
3fde9e…
SHA256^2(Tx1tbs)
二重ハッシュ計算
署名入力
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 37
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
送金元の参照
ハッシュ
Hash Code Type 01000000
ECDSA
署名器
6ab3…秘密鍵
署名生成
045b3…公開鍵
BさんのECC secp256k1
BさんがCさんに送金する
署名済トランザクションの生成 (5/5)
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 8a
scriptSig
B秘密鍵に
よる署名値
入
力
①
BさんからCさんへの署名済取引記録Tx1
Bの公開鍵公開鍵
署名値
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 19入
力
①
BさんからCさんへの署名前の取引記録Tx1tbs
scriptPubKey
送金元の参照
Bさんの
公開鍵
ハッシュ
3fde9e…
SHA256^2(Tx1tbs)
二重ハッシュ計算
署名入力
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 38
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
Bの公開鍵公開鍵
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
送金元の参照
ハッシュ
Hash Code Type 01000000
ECDSA
署名器
6ab3…秘密鍵
署名生成
045b3…公開鍵
BさんのECC secp256k1 ※ハッシュでなく鍵そのもの
BさんがCさんに送金する
署名済トランザクションの検証(1/4)
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 8a
scriptSig
B秘密鍵に
よる署名値
入
力
①
BさんからCさんへの署名済取引記録Tx1
Bの公開鍵公開鍵
署名値
7dbc…
hash160
①公開鍵を取り出し保存
②公開鍵のダブルハッシュ
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 39
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
Bの公開鍵公開鍵
045b3…公開鍵BさんのECC secp256k1
BさんがCさんに送金する
署名済トランザクションの検証 (2/4)
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 8a
scriptSig
B秘密鍵に
よる署名値
入
力
①
BさんからCさんへの署名済取引記録Tx1
Bの公開鍵公開鍵
署名値
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 19入
力
①
BさんからCさんへの署名前の取引記録Tx1tbs
scriptPubKey
送金元の参照
Bさんの
公開鍵
ハッシュ
7dbc…
RIPEMD160(SHA256(公開鍵B))
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 40
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
Bの公開鍵公開鍵
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
送金元の参照
ハッシュ
Hash Code Type 01000000
045b3…公開鍵BさんのECC secp256k1
RIPEMD160(SHA256(
署名前テンプレの生成
BさんがCさんに送金する
署名済トランザクションの検証 (3/4)
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 8a
scriptSig
B秘密鍵に
よる署名値
入
力
①
BさんからCさんへの署名済取引記録Tx1
Bの公開鍵公開鍵
署名値
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 19入
力
①
BさんからCさんへの署名前の取引記録Tx1tbs
scriptPubKey
送金元の参照
Bさんの
公開鍵
ハッシュ
3fde9e…
SHA256^2(Tx1tbs)
二重ハッシュ計算
7dbc…
RIPEMD160(SHA256(公開鍵B))
sha256d
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 41
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
Bの公開鍵公開鍵
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
送金元の参照
ハッシュ
Hash Code Type 01000000
045b3…公開鍵BさんのECC secp256k1
RIPEMD160(SHA256(
仮テンプレ全体をsha256d
BさんがCさんに送金する
署名済トランザクションの検証 (4/4)
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 8a
scriptSig
B秘密鍵に
よる署名値
入
力
①
BさんからCさんへの署名済取引記録Tx1
Bの公開鍵公開鍵
署名値
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 19入
力
①
BさんからCさんへの署名前の取引記録Tx1tbs
scriptPubKey
送金元の参照
Bさんの
公開鍵
ハッシュ
3fde9e…
SHA256^2(Tx1tbs)
二重ハッシュ計算
署名入力
7dbc…
RIPEMD160(SHA256(公開鍵B))
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 42
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
Bの公開鍵公開鍵
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
送金元の参照
ハッシュ
Hash Code Type 01000000
ECDSA
検証器
署名検証
045b3…公開鍵BさんのECC secp256k1
RIPEMD160(SHA256(
入力が複数ある場合の署名はどうする?
バージョン 01000000
入力数 03
前の取引ハッシュ 2cfd73…
前の出力インデックス 4
シーケンス終端記号 ffffffff
入
力
①
「入力②」に対して署名したいとする
前の取引ハッシュ 5234afbc…
前の出力インデックス 1
入
力
②
スクリプトバイト長 19
scriptPubKey Bさんの
バージョン 01000000
入力数 03
前の取引ハッシュ 2cfd73…
前の出力インデックス 4
シーケンス終端記号 ffffffff
入
力
①
前の取引ハッシュ 5234afbc…
前の出力インデックス 1
入
力
②
署名を
したい
箇所だけ
公開鍵を
仮置き
これ全体の
ハッシュを
計算し
ECDSA
署名する
署名対対象外の入力の所は空
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 43
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵ハッシュ
出
力
①
ブロックロック時間 00000000
Hash Code Type 01000000
シーケンス終端記号 ffffffff
②
前の取引ハッシュ d4210bf8…
前の出力インデックス 0
シーケンス終端記号 ffffffff
入
力
③
scriptPubKey
送金元の参照
Bさんの
公開鍵ハッシュ
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵ハッシュ
出
力
①
ブロックロック時間 00000000
Hash Code Type 01000000
シーケンス終端記号 ffffffff
②
前の取引ハッシュ d4210bf8…
前の出力インデックス 0
シーケンス終端記号 ffffffff
入
力
③
どの場所に
署名したい
のか明確に
するために
公開鍵を
仮置き
署名対対象外の入力の所は空
トランザクションのデータ構造と
X.509公開鍵証明書の関係
tbsCertificate(署名対象)
前の取引ハッシュ 484d40…
前の出力インデックス 0
入
力
①
BitCoinトランザクション
A秘密鍵に
よる署名値
Aの公開鍵
scriptSig
公開鍵
署名値
X.509公開証明書(EE)
証明書シリアル番号
tbsCertificate(署名対象)
証明書シリアル番号
X.509公開証明書(CA)
SubjectPublicKeyInfo
(CAの公開鍵)
署名で保護
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 44
scriptPubKey
送金先の参照
Bさんの
公開鍵
ハッシュ
出
力
①
Aの公開鍵公開鍵
署名アルゴリズム
CAによる署名値
署名アルゴリズム
署名値
SubjectKeyIdentifier
拡張
(CAの公開鍵)
署名で
保護
署名で保護
同じ「色」の箇所が大体同じような機能を持っている
トランザクション入力・出力
で使われるBitCoinスクリプト
とは?
45© 2014 Fuji Xerox Co., Ltd. All rights reserved.
トランザクションの入力・出力
表現にはBitCoin Scriptが使われる
バージョン 01000000
入力数 01
前の出力ハッシュ 484d40…
前の出力インデックス 00000000入
PUSHDATA_47
ASN.1形式のECDSA署名値(R,S)
SIGHASH_ALL (全てを署名対象に)
PUSHDATA_41
EC公開鍵(x04 + X + Y)
scriptSig スクリプト
送金者署名値と送金者公開鍵が
含まれるスクリプト
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 46
前の出力インデックス 00000000
スクリプトバイト長 8a
署名スクリプト 473044…
シーケンス終端記号 ffffffff
入
力
①
出力数 01
出金額 626401…
スクリプトバイト長 19
公開鍵検証スクリプト 76a914…
出
力
①
ブロックロック時間 00000000
EC公開鍵(x04 + X + Y)
OP_DUP
OP_HASH160
PUSHDATA 14
公開鍵ハッシュ値
OP_EQUALVERIFY
OP_CHECKSIG
scriptPubKey スクリプト
受取人公開鍵の参照(hash160)
が含まれるスクリプト
BitCoin Scriptとは
•BitCoinのトランザクションの入出力を表現する
スクリプト言語
•Forthのようなスタック言語
•約90の命令(オペコード)
•文、条件、四則演算、ビット演算、スタック操作、
暗号プリミティブなどの命令がある。
•BitCoinのトランザクションでは極めて限定的な
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 47
•BitCoinのトランザクションでは極めて限定的な
使われ方しかしないので学ぶ必要はあまりない。
•送金の証拠となるトランザクションデータ中にス
クリプトを含めることを可能にし、拡張性を持た
せたという意味でビットコインは世界初の画期的
なサービスとなっている。
•トランザクションではPUSHDATA, DUP,
HASH160, EQUALVERIFY, CHECKSIGの命
令ぐらいしか出てこない。 出典:https://en.bitcoin.it/wiki/Script より
ビットコインの
お金の正体って何なの?
48© 2014 Fuji Xerox Co., Ltd. All rights reserved.
アドレスの取引残高の正体は何か?
アドレスFからAへ5BTC
アドレスFからAへ8BTC
トランザクション出力
使われたお金
tx④
tx③
改竄不能な
トランザクション
改竄不能な
二分木
b④
b③
b(n)
改竄不能な
最長
ブロック
チェーン
取引残高を証明するのは使用
されていないトランザクション出力
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 49
アドレスFからAへ8BTC
その後アドレスAからNへ8BTC
アドレスHからAへ2BTC
5+2=合計7BTC
tx②
tx①
b③
b②
b①
b(0)ビットコインP2Pネットワーク
ここでちょっと質問
7500BTC(約4億円)のビットコイン
(の秘密鍵)の入ったハードディスクを
50© 2014 Fuji Xerox Co., Ltd. All rights reserved.
(の秘密鍵)の入ったハードディスクを
間違って捨てちゃったという事件
出典: http://www.theguardian.com/technology/2013/nov/27/hard-drive-bitcoin-landfill-site
P2Pネットワークで預金残高は保証
されているのに取り戻せないの?
アドレスの秘密鍵をなくすとどうなる?
アドレス
1abc…
秘密鍵が無いと、もう
誰にもお金をあげられない
秘密鍵が無いと、
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 51
ウォレット
秘密鍵が無いと、
もう換金もできない
ビットコインの用語の説明(2)
① ブロックチェイン
② コインベーストランザクション② コインベーストランザクション
③ マイニング(発掘)
52© 2014 Fuji Xerox Co., Ltd. All rights reserved.
ブロックチェインについて
53© 2014 Fuji Xerox Co., Ltd. All rights reserved.
ブロックチェインとは
tx④
tx③
トランザクション
b④
b③
b(30万)
ブロック
チェイン
P2Pネットでトランザ
クションを改竄されない
ようにするための仕組み
約10分に1つブロック
が増える
1ブロックで数百のト
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 54
tx②
tx①
b③
b②
b①
b(0)ビットコインP2Pネットワーク
1ブロックで数百のト
ランザクションを含む
今30万ブロック
年5万ブロック増える
ブロックを作った人に
は賞金(今は25BTC)
なぜブロックチェインが必要なのか?
ビットコインP2Pネットワーク
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 55
Bさんの署名つきトランザクション
Bさんには
7 BTCある
Cさんに
7 BTC渡す
入力 出力
このトランザクションは、ただ署名しただけであって、
ビットコインネットワークではこの取引を認めていない
なぜブロックチェインが必要なのか?
ビットコインP2Pネットワーク
のブロックチェイン
登録
(=Proof Of Work)
(=マイニング)
公開
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 56
Bさんの署名つきトランザクション
Bさんには
7 BTCある
Cさんに
7 BTC渡す
入力 出力
P2Pネットワークに受け入れてもらうことで
取引が全ビットコイン利用者に受理される
登録依頼
ブロックのデータ構造
マジックナンバー(定数) <4> = d9b4bef9
ブロックのデータバイト数 <4>
ブロックヘッダ<80>
ブロックバージョン <4>
直前のブロックヘッダのハッシュ<32>
マークルルートハッシュ値 <32>
現在時刻(Unixオリジンの秒数) <4>
マジックナンバー(定数) <4> = d9b4bef9
ブロックのデータバイト数 <4>
ブロックヘッダ<80>
ブロックバージョン <4>
直前のブロックヘッダのハッシュ<32>
マークルルートハッシュ値 <32>
現在時刻(Unixオリジンの秒数) <4>
sha256d
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 57
ブロックヘッダ
現ターゲット(ハッシュ計算困難度) <4>
発掘で計算されたノンス <4>
トランザクション数 <1-9>
トランザクションデータ 0
トランザクションデータ 1
トランザクションデータ n
:
ブロックヘッダ
現ターゲット(ハッシュ計算困難度) <4>
発掘で計算されたノンス <4>
トランザクション数 <1-9>
トランザクションデータ 0
トランザクションデータ 1
トランザクションデータ n
:
coinbase
発掘報償金25.?BTC
coinbase
発掘報償金25.?BTC
sha256d
merkleroot
コインベーストランザクション
(発掘者への報酬約25BTC)
バージョン<4>
入力数<1>
前の取引ハッシュ<32>
前の出力インデックス<4>
スクリプトバイト長<1>
scriptCoinbase
入
力
①
01000000
01
00000000000000… (全部ゼロ)
ffffffff (全部ff)
8b
03+ブロック高+あと不明
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 58
scriptCoinbase
シーケンス終端記号<4>
①
出力数<1>
出金額(BTC) <8>
scriptPubKey
送金先(発掘者)の参照
出
力
①
ブロックロック時間 <4>
ffffffff
01
xxxxxxxx… 25BTC+手数料になる
1976a91406f1b6......88ac
00000000
全てのお金の源流はコインベーストランザクション
b④
b③
b(30万)
発掘者3へ
発掘者4へ
25BTC
発掘者5へ
25BTC
Aさんへ
0.03BTC
Aさんへ
0.01BTC
Aさんへ
Aさんの
アドレスに
0.07BTC
コインベース
使われていないトランザクション出力=誰かの口座残高
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 59
b③
b②
b①
b(0)発掘者1へ
50BTC
発掘者2へ
50BTC
発掘者3へ
25BTC
25BTCAさんへ
0.03BTC
約10分おきに
発掘者に与えられる
賞金BTC
お金は細かく分かれた
りくっついたりしなが
ら利用者の元へ届く
マークルルートハッシュの計算
ブロックに含まれる全トランザクションデータの
ハッシュ値を木構造で組み合わせてそれをルート値として管理する。
→ 後続ブロックを持った時点でトランザクションを改竄できなくなる
結合関数 fm =sha256d(rev(txida)+rev(txidb)) ※ rev: バイトの逆順
ハッシュ1234 ハッシュ5656
ハッシュ12345656 これがマークルルート
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 60
tx1
AからBへ4BTC
tx2
FからDへ1BTC
tx3
ZからQへ1BTC
tx4
WからYへ3BTC
tx5
PからGへ9BTC
tx6
SからLへ1BTC
ハッシュ1 ハッシュ2 ハッシュ3 ハッシュ4 ハッシュ5 ハッシュ6
txid1 txid2 txid3 txid4 txid5 txid6
ハッシュ12 ハッシュ34 ハッシュ56 ハッシュ56
組む相手が無けれ
ば同じ値で
fm fm fm
fm fm
sha256d sha256d sha256d sha256d sha256d sha256d
マークルルートハッシュのメリット
いらない部分を保管しなくて済む
例えば、tx2が自分の関連するトランザクションだとして、
関係するものだけを残して後で検証したい場合、
下の薄いのは消してもいつでも再検証ができる
ハッシュ1234 ハッシュ5656
ハッシュ12345656
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 61
tx1
AからBへ4BTC
tx2
FからDへ1BTC
tx3
ZからQへ1BTC
tx4
WからYへ3BTC
tx5
PからGへ9BTC
tx6
SからLへ1BTC
ハッシュ1 ハッシュ2 ハッシュ3 ハッシュ4 ハッシュ5 ハッシュ6
txid1 txid2 txid3 txid4 txid5 txid6
ハッシュ12 ハッシュ34 ハッシュ56 ハッシュ56
消してしまってよい
ブロックの発掘
62© 2014 Fuji Xerox Co., Ltd. All rights reserved.
ブロックの発掘とは?
マジックナンバー(定数) <4> = d9b4bef9
ブロックのデータバイト数 <4>
ブロックヘッダ<80>
ブロックバージョン <4>
直前のブロックヘッダのハッシュ<32>
マークルルートハッシュ値 <32>
現在時刻(Unixオリジンの秒数) <4>
sha256d
root ターゲットの値によりブロックヘッダ
ハッシュ値の許容される最大値が得られる
(全P2Pネットワーク上で
発掘が10分程度で終わるように調整)
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 63
ブロックヘッダ
※時間は比較的適当でよい
現ターゲット(ハッシュ計算困難度) <4>
※約半月に1回変更になる
発掘で計算されたノンス <4>
トランザクション数 <1-9>
トランザクションデータ 0
トランザクションデータ n
:
merkleroot
表の出典:Ken Shirriff's blog
Bitcoin mining the hard way: the algorithms, protocols, and bytes
http://www.righto.com/2014/02/bitcoin-mining-hard-way-algorithms.html
先頭が0が16個つくために
85万回ハッシュ計算をした
ブロックのターゲット値の計算は?
現ターゲット(ハッシュ計算困難度) <4>
※約半月に1回変更になる
ブロックヘッダ中の4バイト圧縮表現ターゲット
18 7c 30 537c3053 18
リトルエンディアン
なので逆順に
桁数 値
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 64
7c 30 53 00 00 00 00 0000・・・00 ・・・
全体でx18=24バイトになるように先頭32-24=8バイトがゼロ
16進数32バイト表現のターゲット値(=hash256dの結果長と同じ)
この値「以下」になるように発掘(=ハッシュ計算)を繰り返す
難易度(Difficulty)の推移
当たり前だが、ネット全体での
ハッシュ計算速度と難易度は相関がある
2014年5月下旬、難易度は
4年前の100億倍になった
5ヶ月で10倍
ハッシュ速度
100ペタH/s
難易度
120億
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 65
出典:http://bitcoin.sipa.be/
2014年1月
全ネット20ペタH/s
難易度10億
5ヶ月で10倍
指数関数的に増加
ブロックの発掘って
どれくらい難しいのか
• 先頭1文字だけのゼロなら16進数なので1/16確率でできる。
• 今の(2014年2月)時点の難しさならば1/1019の確率
• 地球上の全部の砂の中から特定の1粒を見つけるより難しい
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 66
出典:Ken Shirriff's blog
Bitcoin mining the hard way: the algorithms, protocols, and bytes
http://www.righto.com/2014/02/bitcoin-mining-hard-way-algorithms.html
プール, ASIC, FPGA, GPU, CPUによる
ブロック発掘の変遷・速度・費用感
費用
AntMiner U2 (USB)
2GH/s 45万円
Monarch (PCI)
600GH/s 22万円
AntMiner S2 (Rack)
1TH/s 27万円
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 67
速度
Minerscube 15 (Box)
15TH/s 65万円
Cpuminer
(on DELL, Linux) 3.5MH/s
2012年
FPGA時代
100-800MH/s
2014年
発掘プール
1-22PetaH/s
2011年
GPU時代
20-70MH/s
2009年
CPU時代
4-8MH/s
2013年
ASIC時代
1G-10TeraH/s
出典・参考:gizmodo:Bitcoinをざくざく掘り出す、モンスター・マシンたち(2013.04.17)
http://www.gizmodo.jp/2013/04/bitcoin_2.html
現時点での発掘者比率
共同発掘
GHash.IO
22 Peta H/s
33%
その他
普通のデルサーバーVMの1CPUでやったとした
ら
3M H/sの速度
10分に一回発掘できるとして速度比較から
BTCguild v.s. 個人のデルサーバVM
2万年に一回しか勝てない
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 68
出典:blockchain.info 過去4日間のハッシュレート分布
https://blockchain.info/pools?timespan=4days
共同発掘
BTCguild
8 Peta H/s
13%
2万年に一回しか勝てない
全ハッシュ v.s. 個人のデルサーバーVM
15万年に一回しか勝てない
発掘プール
(みんなで発掘作業を分担して掘れたら賞金山分け)
Bitcoin P2P
ネットワーク 共同発掘プール
全世界 約24,000人が参加 トータルで10ペタハッシュ/秒
発掘結果
(例)
賞金
(25BTC)
ノンスの計算範囲を各分担者に重ならないように作業依頼
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 69
少し難易度が低いターゲットで何回発掘できたか?がその人の貢献量
(=Share) 作業貢献に応じて発掘できた時に賞金を分配
15回 4回 3回 2回 1回
15BTC 4BTC 3BTC 2BTC 1BTC
本当のターゲット:先頭16文字がゼロ
プール参加者のターゲット:先頭10文字がゼロ
仮想通貨で起きそうな諸問題
のBitCoinならではの解決法
70© 2014 Fuji Xerox Co., Ltd. All rights reserved.
コピー容易なデジタル通貨の
二重利用をどう防ぐのか?
不正利用を防ぐための仕組み(1)
電子署名
太郎さんから花子さんへ5BTCあげます
文書なんで誰でも書き換えられるので「太郎さん」は言い逃れできる
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 71
太郎さんから花子さんへ5BTCあげます
太郎さんの秘密鍵で行った署名は書き換えできず
「太郎さんの意図」がなければ署名できないので言い逃れ不能
不正利用を防ぐための仕組み(2)
シリアル番号
1BTC渡します
1BTC渡します
1か2BTCかわからない。同じお金を2重につかえてしまう。
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 72
1か2BTCかわからない。同じお金を2重につかえてしまう。
1BTC渡します
1BTC渡します
番号が同じなら間違いだとわかる。二重に使えない。
番号:1234
番号:1234
不正利用を防ぐための仕組み(3)
全ての人が参加する
花子に
1BTC渡します
和子に
1BTC渡します
どちらが本物かわからない。同じお金を二重利用
番号:1234
番号:1234
口座は-1or2?
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 73
どちらが本物かわからない。同じお金を二重利用
花子に
1BTC渡します
番号:1234
正当な
取引
和子に
1BTC渡します
番号:1234 全員の前
じゃない
(架空取引)
不正利用を防ぐための仕組み(4)
トランザクション(ブロック)をハッシュの連鎖にする
バラバラだと個別に改竄できてしまう
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 74
ハッシュの連鎖になっているなら
途中の一部を書き換えることは不可能
不正利用を防ぐための仕組み(5)
作業証明(proof of work) (=コインの発掘)
花子に
1BTC渡します
番号:1234
半分以上がグルの悪者だったら、いくらでも騙せる
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 75
①取引の検証の計算コストを高くする
②取引を検証した人には報酬を与える
解決策
花子に
1BTC渡します
番号:1234
計算量が高すぎて多数派工作をすることは不可能
不正利用を防ぐための仕組み(6)
ブロックチェイン最長優先のルール
どちらの枝を信じるかでお金が二重利用可能
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 76
短い方は発掘しても後で無視され徒労に終わるので
みなが最長のチェインにつながるように発掘
Transaction Malleability
トランザクション展性とは?
最大の取引所Mt.Gox社がTransaction Malleability
DoS攻撃によってダウンしたと言っていますが、詳しDoS攻撃によってダウンしたと言っていますが、詳し
く解説しましょう
77© 2014 Fuji Xerox Co., Ltd. All rights reserved.
トランザクション展性
Transaction Malleabilityって知ってます?
出典: http://arxiv.org/pdf/1403.6676v1.pdf
「トランザクション展性を使ったDoS
攻撃により預金が不正に引き出され
Mt.Gox社は破綻した」という噂が
ニュースに流れたが、スイスの研究者
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 78
出典:http://www.pcworld.com/article/2114200/malleability-
attacks-not-to-blame-for-mt-goxs-missing-bitcoins-study-says.html
出典: http://www.cryptocoinsnews.com/news/malleability-bankrupt-
mt-gox/2014/03/27
ニュースに流れたが、スイスの研究者
の論文より、トランザクション展性と
破綻に直接の関係は無くスケープゴー
トに使われたのでは?と言われている
トランザクション展性とは何か?
トランザクションとスクリプトの図(再掲)
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 8b
scriptSig
B秘密鍵に
よる署名値
入
力
①
BさんからCさんへの署名済取引記録Tx1
Bの公開鍵公開鍵
署名値
PUSHDATA 48 (48バイトプッシュ)
ASN.1形式のECDSA署名値(R,S)
SIGHASH_ALL (全てを署名対象に)
scriptSig スクリプト
送金者署名値と送金者公開鍵が
含まれるスクリプト
48
30450221…
01
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 79
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
Bの公開鍵公開鍵 SIGHASH_ALL (全てを署名対象に)
PUSHDATA 41 (41バイトプッシュ)
EC公開鍵(x04 + X + Y)
グレーの部分は署名値で保護されているので
改竄することはできない
01
41
04dc47f1…
•例えば x48 バイトをプッシュしたい場合
① プッシュデータサイズをそのまま指定する場合
[48] (※x01-4bまでの値で使えます)
② プッシュデータサイズを1バイトで表現する場合 OP_PUSHDATA1(x4c)
[4c][48]
トランザクション展性とは何か?
スタックプッシュにはスクリプトで数種の表現方法がある
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 80
③ プッシュデータサイズを2バイトで表現する場合 OP_PUSHDATA2(x4d)
[4d][48][00]
④ プッシュデータサイズを4バイトで表現する場合 OP_PUSHDATA4(x4e)
[4e][48][00][00][00]
前のscriptSigで[48]を①~④どれで置き換えてもスクリプトの意味と処理は同じ
ただ、置き換えるとトランザクションID(=ハッシュ値)は違ってしまう
トランザクションのscriptSigの処理内容を変えずにIDを変えられる性質
=トランザクション展性(Transaction Malleability)
トランザクション展性攻撃とは?
Bitcoin P2Pネットワーク
txid’:93fb41…
AからFに7BTC
scriptSig=4c48…
正しいトランザク
ションの登録を
DoSで妨害
改竄版が
誤って登録される
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 81
txid:75facd…
AからFに7BTC
scriptSig=48…
txid’:93fb41…
AからFに7BTC
scriptSig=4c48…
盗聴と
わずかな改竄
(署名改竄には
あたらない)
DoSに近い大量の
登録要求
以降、お釣りなどの利
用の際に、
エラーになる場合も
トランザクション展性攻撃とは
「何か?」また「何ではないか?」
①Mt.Gox社などトランザクションIDのみで独自に送金履歴管理
している古い実装の場合に不整合が起きた
どんな問題だったのか?
公開鍵と署名値のスクリプトを意味的には同じままスクリプトを
変えることにより、トランザクションIDの不一致を狙った攻撃
何が起きたか?
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 82
している古い実装の場合に不整合が起きた
②一部のウォレットアプリでID不整合によりお金の移動、口座残
高などの参照ができなくなった
③お釣りなどの利用の際に送金エラーになることが出てくる
①ほとんどの部分は署名で保護されているので、お金の盗難に結
びつく送金先、送金額の変更はできないため、直接的お金の盗
難はこの攻撃では起きない
何は起きないか?
代表的なトランザクション展性ポイント
バージョン 01000000
入力数 01
前の取引ハッシュ 2cfd73…
前の出力インデックス 0
スクリプトバイト長 8b
scriptSig
B秘密鍵に
よる署名値
入
力
①
BさんからCさんへの署名済取引記録Tx1
Bの公開鍵公開鍵
署名値
PUSHDATA 48 (48バイトプッシュ)
ASN.1形式のECDSA署名値(R,S)
SIGHASH_ALL (全てを署名対象に)
48
30450221…
01
先頭に余計な
データをプッシュ
しても最後2つ
しか利用しない
処理に影響のない
プログラム
(OP_DROP等)
の追加
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 83
シーケンス終端記号 ffffffff
出力数 01
出金額(BTC) 2.9995
スクリプトバイト長 19
scriptPubKey
送金先の参照
Cさんの
公開鍵
ハッシュ
出
力
①
ブロックロック時間 00000000
Bの公開鍵公開鍵 SIGHASH_ALL (全てを署名対象に)
PUSHDATA 41 (41バイトプッシュ)
EC公開鍵(x04 + X + Y)
グレーの部分は署名値で保護されているので
改竄することはできない
01
41
04dc47f1…
署名値Sを
「-S」に
プッシュサイズを
1/2/3/5
バイト表現に
(参考)他に可能なトランザクション展性
① ECDSA署名の正負
ECDSA署名の値(R,S)ではSを-Sとしても署名値としては有効。
② DERエンコードされていないECDSA署名値
OpenSSLではDERエンコードされていない署名値でも検証可能。0.8.0以降ではこのような
トランザクションは受理されなくなった。
③ 最初の余分なデータプッシュ
最初に余分に何回データプッシュ命令を実行しても処理されない。
④ scriptSig中のPUSHでないオペレーション
PUSHでないオペレーションが入っていても署名検証結果は同じとなってしまう
⑤ プッシュオペレータの表現75バイトまでそのまま、OP_PUSHDATA{1,2,4} (前述)
⑥ scriptPubKeyのオペコードの部分についてのみ、入力は整数として扱われるためゼロパディ
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 84
⑥ scriptPubKeyのオペコードの部分についてのみ、入力は整数として扱われるためゼロパディ
ングしても値は同じとなる。
⑦ スクリプトで無視される入力
scriptPubKeyにおいてOP_DROPなど無視されるオペレーションがある。
⑧ Sighashフラグによるマスク
Sighashフラグはスクリプトの一部を無視するのに使える。
⑨ 送金者(か秘密鍵にアクセスできる人)はいつでも同じ入力と出力を使う新しい署名を生成でき
る。
⑩ scriptSig中のECC公開鍵において非圧縮、圧縮フォーマットを入れ替える。
参考:https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki
まとめ
85© 2014 Fuji Xerox Co., Ltd. All rights reserved.
•使われている暗号(ハッシュ、楕円曲線暗号)
•用語解説
– ウォレット、アドレス、鍵
– トランザクション
– ブロックチェイン
– マイニング
まとめ
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 86
– マイニング
•二重利用などの問題をどのように解決してきたか
•トランザクション展性
についてご紹介させて頂きました。
•個々の技術に目新しさはないが、不正利用防止や運用のために
様々な工夫がされておりオモシロイ。研究レベルではいろいろ
思いつくだろうが現実に利用されているのだから。
•ただ、トランザクションのデータ構造やプロトコルなど何とな
く稚拙に思えるところもあって、そのアンバランス感が不思議
に思える。
ビットコインに対する私見
© 2014 Fuji Xerox Co., Ltd. All rights reserved. 87
•特に、スクリプトを導入したのは失敗で、データと処理を分け
るのが基本だったのでは?(トランザクション展性問題もあるし)
•ビットコイン自体に設計上の問題があったとしても、それを解
決した第二、第三世代の暗号通貨に移行すればいいだけ。(一太
郎と同じ)
•個人的に非常に興味深いのはそれ自体価値がないハッシュ計算
が価値(通貨)を生み出している所。(証明書の鍵ID付加価値)
Xerox、Xeroxロゴ、およびFuji Xeroxロゴは、米国ゼロックス社の登録商標または商標です。

More Related Content

Bitcoinを技術的に理解する