ビットコインの論文翻訳（Bitcoin: A Peer-to-Peer Electronic Cash System）
■前書き
こん資料は基本的にBitCoinの英語論文を意訳したものである。
既に日本語訳版があるが、多少分かりづらいため、自分なりに訳した。
BitCoinの論文自体は非常に洗練されていて、背景知識がほとんど書かれていない。
ブロックチェーンの理解を深めたい方は、他の参考書類との併用をお勧めする。
０、書籍情報
論文：Bitcoin: A Peer-to-Peer Electronic Cash System
種類：原著
著者：Satoshi Nakamoto
サイト：www.bitcoin.org
URL（英語版）：https://bitcoin.org/bitcoin.pdf
URL（日本訳版）：https://www.kk-kernel.co.jp/qgis/HALTAK/FEBupload/nakamotosatoshi-paper.pdf
１、概要
オンライン取引は信頼されている第三者金融機関に依存している。
金融機関の手数料は取引のコストを増加させ、小口取引を妨げている。
個人情報にも良くない。金融犯罪を防ぐために金融機関は必要以上にユーザ情報を聞き出さないといけないが、それでも一定な割合で発生する。
現金を使う場合、支払いのコストと不確実性が回避できるが、信頼できる第三者のいないオンライン支払の仕組みは存在していない。
第三者の金融機関をなくすには、暗号的な証明に基づく電子決済の仕組みが必要だ。計算上逆引きが不可能で、エスクロー（中立な第三者）機構も容易に実現できる仕組み。
本論文では、P2P分散型タイムスタンプサーバーを用いて、取引の時系列順序の計算的証明を生成することにより、二重支出問題の解決策を提案する。
このシステムは、誠実なノードが攻撃者グループよりも多くのCPUパワーを持っている限り、安全である。
２、取引
電子コインをデジタル署名の連鎖として定義する。
各所有者は、直前の取引のハッシュと次の所有者の公開鍵にデジタル署名を行い、コインの末尾に追加することでコインを次の所有者に譲渡する。
受取人は署名を検証することで、所有権の連鎖を確認することができる。
一つの問題がある。
受取人は所有者がこのコインを二重に支払っていないことが確認できない。
受取人は所有者が以前に他の取引に署名していないことを知る必要がある。
唯一の方法は、すべての取引をチェックするしかない。
取引が一般に公表される、且つ、参加者たちが受け取った順番の単一の取引履歴に合意するシステムがあれば、実現可能である。
受取人は、取引する際に、大多数のノード（参加者）が「他の取引に署名されていない」を認めることを確認する。これは二重支払ではないことの証明になる。
３、タイムスタンプサーバー
一連の解決策はタイムスタンプサーバーから説明する。
タイムスタンプサーバーは対象ブロックのハッシュを計算し、広く公表する。
ハッシュにブロックのデータが入っているため、計算の時点に存在していたことが証明される。
タイムスタンプには前のタイムスタンプのハッシュが含まれていて、タイムスタンプを追加する度に前のタイムスタンプが強化され、連鎖（チェーン）が形成される。
４、証明作業
P2Pの分散タイムスタンプサーバーを実現するには、証明作業が必要である。
⚠️ ■この部分の意味は十分に理解できていない
For our timestamp network, we implement the proof-of-work by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits.
これはブロックにノンス（nonce）を付け加えることで実現する。
あるブロックの証明作業が完了していると、中のノンス（nonce）の再計算をしなければブロックの変更ができない。後継のブロックもあるため、すべての後継ブロックの再計算も必要となる。
多数決の代表問題について、考えよう。
もし１IPが１票だったら、多くのIPを割り当てることができる人によって覆される可能性がある。
証明作業は１CPU-1票である。
多数決の決断は最も長いチェーンで表現される。そこに最大の証明作業の労力が投入されている。
大多数のCPUパワーは誠実なノードによって制御されていれば、この誠実なチェーンは最も速く成長し、他のすべての競合チェーンを凌駕する。
過去のブロックを改ざんするには、攻撃者はこのブロックとそれ以後のすべてのブロックの証明作業をやり直し、誠実なノードの証明作業を追いつき、追い越す必要がある。
後続のブロックが追加されるにつれ、攻撃者の速度が遅く、追いつく確率は指数的に減少することは後程示す。
ハードウェアの処理能力の増加と稼働中ノードの関心の変化があるため、証明作業の難易度は１時間あたりの平均ブロック数の移動平均に依存する。ブロックの生成速度が速いと、難易度は高くなる。
５、ネットワーク
ネットワークは下記の手順に動く。
新取引はすべてのノードへブロードキャストされる。
各ノードは新取引をブロックに取り入れる。
各ノードはブロックの難しい証明作業をする。
ノードが証明作業を終えると、このブロックをすべてのノードへブロードキャストする。
ノードは、受信したブロック内の全ての取引が有効且つまだ消費されていない場合にのみ、そのブロックを受け入れる。
ノードは、受け入れたブロックのハッシュを前のハッシュとして使い、チェーンの次のブロックの作成に取り組むことで、ブロックの受け入れを表明する。
ノードは常に最長のチェーンを正しいものとみなし、それを延長する作業を続ける。
もし2つのノードが異なるブロックを同時にブロードキャストした場合、他のノードはどちらか一方を先に受け取る。ノートは先に受信したブロックを処理する。もしもう一方の枝が長かったら、もう一方の枝を保存する。
証明作業が完了すると、ある枝が長くなる。他の枝で作業しているノードはこの枝に切り替わる。
新取引のブロードキャストはすべてのノードに届く必要はない。多くのノードに到達しさえすれば、すぐにブロックに取り入れられる。
ブロックブロードキャストはメッセージの欠落にも耐性がある。
もしノードがあるブロックの受信をできなかった場合、次のブロックが届くときに見逃していたことに気づき、抜けたブロックを求めるすることができる。
６、インセンティブ
通常、各ブロックの最初の取引は、１枚のコインの発行という特別な取引である。
これは採掘されたコインで、取引ネットワークをサポートするノードへのインセンティブであり、流通にコインを発行する手段にもなる。
このコインの発行方法は、金の採掘者が金の流通を増やすために資源を費やすことに似ている。
消費されるのはCPU時間と電力である。
インセンティブは、取引手数料で賄うこともできる。取引の入力値と出力値の差額はその取引を含むブロックのインセンティブに加えられる。
所定数のコインが流通に入ると、取引手数料だけのインセンティブに完全に移行でき、インフレフリーが実現される。
インセンティブはノードが誠実であることを奨励するのに役立つかもしれない。
もし貪欲な攻撃者が誠実なノードより多くのCPUパワーを集めることができたら、そのCPUパワーを使って自分の支払額を盗み戻すか、新しいコインを生成するかのどちらかを選ばなければならないだろう。攻撃者は、システムや自分のコインの有効性を損なうより、ルールに従い、他の人より多くのコインを採掘し獲得する方が有益であると考えるはずでしょう。
７、ディスク容量の回復
コインの最新の取引が十分なブロックの中に入ると、それ以前の取引はディスク容量を節約するために破棄していい。
ブロックのハッシュを壊さずにこれを実現するために、取引はMerkle Treeにハッシュされている。木のルートだけがブロックのハッシュに含まれている。古いブロックは枝を切ってコンパクト化することができる。内部のハッシュは保存する必要がない。
取引のないブロックのヘッダーは$${80byte}$$。
ブロックは１０分間おきに生成されると仮定すると、１年間の容量は$${80byte\times 6\times 24\times 365=4.2MB}$$。
2008年の標準パソコンは2GBのメモリがあり、メモリ量はムーアの法則によって年間1.2GBの速度で増加している。ブロックのヘッダーをメモリに置いても問題ないはずである。
８、支払検証の簡易化
全ネットワークをフル稼働させなくても、支払いの検証が可能です。
ユーザーは最長の証明作業チェーンのブロックヘッダのコピーを保持するだけでよい。
最長であるかの確認は、ネットワークの各ノードへの問い合わせを確信が持てるまで続ける。
Merkle Treeの枝部分はタイムスタンプのついたブロックヘッダーと繋がっているため、取得できる。
自分の取引を自分で確認することはできないが、チェーンに付け加えて、他のノードがそれを受け入れること、さらにその後にブロックが追加されることで、ネットワークはこの取引を検証し受け入れることが確認できる。
そのため、誠実なノードがネットワークをコントロールしている限り、検証結果の信頼性が高い。
だが、ネットワークは攻撃者が制圧した場合に脆弱になる。
攻撃者がネットワークを制圧し続ける限り、取引が捏造でき、ネットワークが簡単に騙される。
これを防ぐための1つの方法は、無効なブロックを検出したときにアラートを発信し、受信したノードにブロック全体とアラートの取引をダウンロードさせ、一致性を確認させることである。
頻繁に支払いを受ける企業は、より独立したセキュリティと迅速な検証のために、独自のノードで実行するだろう。
９、コインの結合と分割
コイン単位で扱うことができるが、コイン単位で個々の取引を行うのはやりにくい。
コインの分割と結合が可能である。取引に複数の入力と出力を含めることができる。
通常、前の大きい金額から分割された一つの入力が来る。または、複数の小さな金額の入力がきて、組み合わせられる。出力は最大２つある。１つは支払用で、もう1つは残りのお釣りである。
ある取引が複数の取引に依存し、それらの取引がさらに多くの取引に依存するようなファンアウトは、ここでは問題にならないことに注意する必要がある。
取引履歴の完全なスタンドアロンのコピーを抽出する必要はない。
１０、プライバシー
従来の銀行は、情報へのアクセスを当事者と信頼できる第三者に限定することで、プライバシーポリシーを実現している。
ビットコインはすべての取引を公表する必要があるため、この方法は使えませんが、それでもプライバシーを維持することができる。
公開鍵を匿名にすればよい。
一般の人は、誰かが誰かに送金していることが分かるが、その取引が誰と繋がっているかの情報はない。
これは、証券取引所が公開する情報のポリシーに似ている。個々の取引の時間と規模、つまり「tape」は公開されるが、その当事者が誰であるかは分からない。
追加のファイアウォールとして、所有者は取引毎に新しいキーペアを使用して、自分にリンクさせないようにする必要がある。
多入力の取引の場合、必然的にそれらの入力が同じ所有者が所有していることが明らかになる。
もしキーの所有者が特定されたら、この所有者の他の取引も特定される、とのリスクは存在している。
１１、計算
攻撃者が誠実なチェーンより速く別のチェーンを生成しようとするシナリオを考える。
ただ、これができたとしても、無から価値を生み出したり、所有していないお金を奪ったりといった任意の変更ができるシステムにはならない。
ノードは無効な支払を受け入れることはなく、正直なノードはそれらを含むブロックを決して受け入れない。
攻撃者ができるのは、最近使ったお金を取り返すために自分の取引の一つを変更することだけである。
誠実なチェーンと攻撃者のチェーンの間の競争は、Binomial Random Walkとして特徴付けることができる。成功イベントは誠実なチェーンが１ブロック伸びてリードが＋１されることであり、失敗イベントは攻撃者のチェーンが１ブロック伸びて差がー１されることである。攻撃者がマイナスから追いつく確率は、「Gambler's Ruin problem」問題に似ている。無限のクレジットを持つギャンブラーが赤字からスタートし、損益分岐点を目指して無限の試行錯誤を繰り返すとする。彼が損益分岐点に到達する確率、つまり攻撃者が誠実なチェーンに追いつく確率は、以下のように計算できる。
$${p=}$$誠実なノードが次のブロックを見つける確率
$${q=}$$攻撃者が次のブロックを見つける確率
$${q_z=}$$攻撃者がz個のブロックの後ろから追いつく確率
$${q_z=\begin{Bmatrix} 1 & if p \leq q \\ (q/p)^z & if p \gt q \end{Bmatrix}}$$
p＞qと仮定すると、攻撃者が追いつかなければならないブロックの数が増えるにつれて、確率は指数関数的に低下する。このような不利な状況下では、攻撃者が早い段階で幸運な突進をしなければ、そのチャンスは遅れをとるにつれてどんどん小さくなっていく。
次に、新しい取引の受信者が、送信者が取引を変更できないと十分に確信するまでに、どれくらいの時間待つ必要があるかを考えてみる。送信者は攻撃者であり、受信者にしばらくの間自分が支払ったように思わせ、しばらくしてから自分への支払いに切り替えたいと考えていると仮定する。そうなれば受信者は警告を受けるが、送信者はそれが手遅れになることを望んでいる。
受信者は新しい鍵ペアを生成し、署名の直前に公開鍵を送信者に渡す。これにより、送信者が前もってブロックチェーンを準備し、運に恵まれるまで繰り返し、その瞬間に取引を実行することを防ぐことができる。
取引を送信すると、不正な送信者はこの取引の別バージョンを複数のチェーンで並列に密かにやり始める。
受信者は、その取引がブロックに追加され、その後にz個のブロックがつけられるまで待機する。彼は攻撃者の正確な進捗は分からないが、誠実なブロックが平均的な想定時間で作成されたと仮定すると、攻撃者の進捗は以下のポアソン分布の期待値で求められる。
$${\lambda=z\frac{q}{p}}$$
攻撃者が現時点に追いつく確率を求めるには、ポアソン分布密度に、その時点に追いつく確率を掛ける。
$${\sum_{k=0}^{\infin}\frac{\lambda^ke^{-\lambda}}{k!} \times \begin{Bmatrix} (q/p)^{z-k} & if k \leq z \\ 1 & if k \gt z \end{Bmatrix}}$$
分布の無限に長いテールの合計を避けるために整理すると・・・
$${1-\sum_{k=0}^{z}\frac{\lambda^ke^{-\lambda}}{k!} \times (1-(q/p)^{z-k})}$$
C言語に変換する。
#include <math.h>
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k <= z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i <= k; i++)
poisson *= lambda / i;
sum -= poisson * (1 - pow(q / p, z - k));
}
return sum;
}実行してみると、zの増加につれ、確率が指数的に下がっていくことが分かる。
q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012
q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006P が 0.1%未満の時に値を求めると…
P < 0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340１２、結論
私たちは、信頼に頼らない電子取引の仕組みを提案している。
電子署名から作られたコインという通常の枠組みは、強い所有権管理を実現したが、二重消費を防ぐ方法がなく不完全である。
これを解決するために、我々は証明作業を用いたP2Pネットワークを提案し、公開取引履歴を記録する。誠実なノードがCPUパワーの大部分を支配していれば、履歴はすぐに変更できないような計算量になる。このネットワークは非構造的でシンプルであるため、堅牢だ。各ノードは一緒に動くが、必要な協調性が少ない。ノードは特定される必要はない。メッセージは特定のところへ送信されることなく、最善努力原則で送信されればよい。ノードは自由に離脱することができ、再参加の際に不在の間に起こったことの証明作業を受け入れる。ノードはCPUパワーで投票し、有効なブロックを拡張することで受け入れを、無効なブロックを使わないことで拒否することを表明する。必要なルールやインセンティブは、この合意メカニズムによって実施することができる。
※引用論文
[1] W. Dai, "b-money," http://www.weidai.com/bmoney.txt, 1998.
[2] H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal
trust requirements," In 20th Symposium on Information Theory in the Benelux, May 1999.
[3] S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no
2, pages 99-111, 1991.
[4] D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping,"
In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
[5] S. Haber, W.S. Stornetta, "Secure names for bit-strings," In Proceedings of the 4th ACM Conference
on Computer and Communications Security, pages 28-35, April 1997.
[6] A. Back, "Hashcash - a denial of service counter-measure,"
http://www.hashcash.org/papers/hashcash.pdf, 2002.
[7] R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and
Privacy, IEEE Computer Society, pages 122-133, April 1980.
[8] W. Feller, "An introduction to probability theory and its applications," 1957.この記事が気に入ったらサポートをしてみませんか？