ビットコインの原論文を読む 5節 ネットワーク

ビットコインでは、最終的に全参加者が一つの取引履歴を共有します。また、誰かが不正な取引をネットワークにねじ込もうとしても、ノード間で多数決投票(のようなもの)が行われ、少数派は負けます。それらのメカニズムを解説します。

5 ネットワーク

本ネットワークは、次に示すステップで動作する。

  1. 取引を行うと、その情報がすべてのノードに広められる。
  2. 各ノードは、取引情報を集めてブロックを生成する。
  3. 各ノードは、ブロックに対する演算量証明を開始する。
  4. 演算量証明に成功した最初のノードは、そのブロックを全ノードに広める。
  5. 各ノードは、ブロックを、多重使用が無く正しい取引だけを含むことを確認して、受け付ける。
  6. 各ノードは、受け付けたブロックのハッシュ値を埋め込んで、次のブロックを生成し始める。これが、ブロックを受け付けたことの表明ともなる。

続きを読む

ビットコインの原論文を読む 4節 演算量証明

4 演算量証明

P2Pベースで分散タイムスタンプサーバを実装するためには、新聞やネットニュースなどよりも、むしろアダム・バックのハッシュキャッシュ[6]のようなシステムが必要である。これは、演算に費やした時間を他人に頼らずに証明する手法で、例えば「SHA-256のようなハッシュ関数を通すと最初のnビットがすべて0となるような値」を総当たりで発見することによって実現できる。そのような演算にかかる平均時間は、nに対して指数関数的に増大する。それに対して、検証する側はハッシュ関数を1回計算するだけで良い。

提案するタイムスタンプネットワークでは、ブロックデータとNonceと呼ばれる数字を組み合わせる。Nonceを適当な値から1ずつ増やし続けて、ハッシュ値の最初のnビットがすべて0になる場合を探索する。このようにCPUを使って演算量を証明しておけば、ブロックの内容を改ざんして辻褄を合わせるためには、同じ計算をもう一度行わなくてはならなくなる。さらにその後ろにブロックがチェーンでつながっていたら、それらすべてに対する演算をやり直す必要がある。

続きを読む

ビットコインの原論文を読む 3節 タイムスタンプサーバ

3 タイムスタンプサーバ

提案する解決法は、タイムスタンプサーバを必要とする。タイムスタンプサーバとは、ブロックを受け取ってハッシュ値を計算し、一般的には新聞やネットニュースのような仕組みで配信するサーバである[2-5]。データをハッシュ化しタイムスタンプに組み込むことにより、そのデータがその時点で存在したことを、明確に証明する。また、タイムスタンプは、一つ前の段階のタイムスタンプをハッシュ化したものを組み込み、チェーンを作る。そのため、タイムスタンプが後方に連なるに従って、信頼性が増して行くことになる。

fig2

続きを読む

ビットコインの原論文を読む 2節 電子通貨のやり取り

2 電子通貨のやり取り

本システムでは、コインを、デジタル署名をつなげたチェーンの形で表現する。コインを支払う側は、前回までのコインの取引内容をハッシュ化した値と、受取人の公開鍵をハッシュ化した値とを合わせて、電子的に署名する。それをコインの最後に付け加え、受取人に送信する。受取人は電子署名を検証することにより、そのコインを誰が所有していたかという履歴を辿れる。

fig1

続きを読む

ビットコインの原論文を読む 1節 はじめに

ビットコイン原論文を読む企画、まだ導入部分です。概要の続きです。

1 はじめに

インターネットを介した既存の取引は、支払いを電子的に実行するために、信頼できる第三者機関を必要とする。現在は、もっぱらそれを金融機関が請け負っている。大半の取引は問題なく行われているが、信頼に基づくモデルにつきものの脆弱性問題に苦しみ続けている。また金融機関が間に入ると、利用者間のいざこざを仲裁する必要性が生じるため、完全に非可逆的な取引を行えない。仲裁には費用がかかるため、取引コストが増大したり、取引額の下限を設けて少額取引を制限せざるを得なくなったりする。これにより、非可逆的な支払いで非可逆的なサービスを受けるという枠組みを実現できず、多大なコストが生じてしまう。また、可逆的な取引には、互いに信頼できる相手とでなければ成り立たないという問題もある。そのため、販売側は顧客のことをより深く知ろうとし、本来必要ではないような情報まで要求して、顧客を苛立たせる。そのような対策を立てても、ある割合で詐欺が発生することは回避できない。こういったコストや、支払いが確実に行われるかわからないという問題は、物質的な通貨を利用することで解決する。だが、電子取引では、信頼機関を設けること以外の解決策が見つからなかった。

続きを読む

ビットコインの原論文を読む 概要

まずは原論文Abstractから。

概要 真のP2P電子通貨が実現すると、金融機関の介在無しに、利用者から利用者へと直接オンラインで支払いできるようになるだろう。電子署名によって、その機能の一部は実装可能である。だが従来の方法では、多重使用を禁ずるために第三者機関を設置する必要があり、電子通貨の利点を生かせなかった。本論文で提案するのは、多重使用問題をP2Pネットワークで解決する方法である。このネットワークは、ハッシュ関数による演算量証明を利用する。その証跡をチェーンでつなぎ続けることにより、いつ、どのような取引が行われたかを証明可能にする。チェーン内の取引履歴を改ざんしようとしたら、時間をかけて演算量証明をやり直さなければならない。過去の出来事を時系列的に確認する場合には、ネットワーク上で最長のチェーンを調べれば良い。さらに、最長チェーンは、CPU能力を最も費やした計算結果でもある。CPU能力を持つ者の大半が、ネットワークへの攻撃者を無視していれば、その善良なノード群が作るチェーンは、攻撃者のそれを長さで上回り続ける。このネットワークに必要な規則は、極めて簡素である。メッセージはベストエフォートで拡散すれば良いし、各ノードはいつ離脱・再接続しても構わない。再接続時に最長チェーンを受け取ることによって、離脱していた間に何が起きたかを把握できるからである 続きを読む

コミックマーケット(C85)に参加します。

サークル「ピッチブレンド」は、コミックマーケットC85の3日目(12/31)西へ-06aブースで、次の2点を出展します。

1 新刊「空を夢見た機械式計算機 九元連立方程式求解機」
500円、A5 44ページ(表紙紙4P含む)、黒一色刷(予定)
hyoushi.jpg
国立科学博物館で展示されている機械式計算機『九元連立方程式求解機』だけにテーマを絞って作った本です。その来歴、使用法、計算原理などを解説します。数学が嫌いな人は前半の歴史編だけでもお楽しみ下さい。好きな人は、ラストの運動方程式解説までおつきあいただければ幸いです。

そして、この本で取り上げた九元連立方程式求解機のシミュレータを公開しました。実行には、Wolfram CDF Playerが必要です。
https://googledrive.com/host/0B3lZVwR_2l7kQzFRM1ctNHMwNVE/LinearSolve.html
本で読んだ後にでも、これで理論を確認していただければ、と思います。

2 既刊「最後の歯車式計算機クルタ クルト・ヘルツシュタルク氏インタビュー」
700円、B5 66ページ(表紙紙4P含む)、黒一色刷
curtahyoushi.PNG
クルタ計算機という小型手回し計算機が、かつてありました。この本は、その開発者クルト・ヘルツシュタルク氏へのインタビュー(1987年)を翻訳したものです。計算機屋の跡継ぎとしての少年期、ライバル会社と争った青年期、そしてユダヤ人であることを理由に入れられた収容所、しかしそこでの計算機設計、終戦後もスポンサー探しに走り回る日々、生産を始めてからもトラブルが……。と波瀾万丈の人生がこの一冊で語られます。

2冊とも、デザインは発笑探検隊の東内拓理さんです。
なお、今回はビットコイン決済を受け付けます。おそらく、こういう手続きになるかと。
1 振込先アドレス(QR)のカードをお渡しします。
2 モバイル等で振り込んでいただきます。
3 ブース側で決済を確認します。(約10分間かかるので、別の場所をまわってもらいます。)
4 カードを掲示後に、本をお渡しします。
はい。普通に買うよりも手間がかかります。実験的取り組みなので、何人かで打ち切ってしまうかもしれません。ご容赦下さい。
以上です。みなさん、12/31にお会いしましょう。

2013年大阪大学入試問題(前期理系)数学問5を一瞬で解く

 今年の入試では、大阪大学の理系数学でユニークな問題が出ました。問1はx->0でsinx/x->1を証明せよというもので、個人的には高校生に解かせるのはいかがなものかと思うのですが、それよりも問5です。これがなかなか面白い。

2013年大阪大学入試問題(前期理系)数学問5より
(取り付きやすくするために表現をアレンジしています。)
 n個(n≧3)の箱と球があり、それらには1からnまでの番号が重複無く付けられている。まず球1をいずれかの箱にランダムに入れる。球2以降は、自分の番号と同じ番号の箱が空いていたらその箱に、空いていなかったら空いている箱のいずれかにランダムに入れる。これを球nまで繰り返す。この時、
(1)球nは箱1か箱nに入ることを証明せよ。
(2)球n-1が箱n-1に入る確率を求めよ。
(元の問題はこちら

 なかなかの難問だと思います。(1)は、柔軟に考えればさほど苦労せずに解けます。問題は(2)です。以下の解答を見ずに、一度チャレンジしてみることをおすすめします。

続きを読む

レターパックプラスを最大容積に成型すると、こうなる。

 前回、レターパックプラスを成型した時の容積が最大で4585cm^3になることを示したのですが、実際にそれを確かめてみたくなりました。そこで、封筒を膨らませるシミュレーションを作ってCGを描いてみます。結果はこうなりました。
pb1.png
 この形、3Dプリンタで造ってみたい……。

続きを読む

レターパックプラスで最大何リットルの荷物を送れるのか

(MathJaxを使っているので、古いブラウザでは数式が表示されないかも知れません。)
 先日、本を何冊か送る機会があったのですが、その時にレターパックプラスを使いました。レターパックプラスは、500円固定料金の郵便で規定の封筒を使用し、切手を貼らなくても相手に届くという大変便利なものです。封筒の大きさは決まっていますが、これを立体成型して直方体の形を作る方法があり、すると意外に大きなものが入ります。こことかここのページを参考にして、本を送りました。
 では、$24.8cm×34cm$のレターパックプラスに、最大でどれぐらいの体積の直方体を入れられるでしょうか。立体成型のやり方から分かるとおり
\[直方体の周囲長 \leq レターパックプラスの周囲長\]
である必要があります。従って直方体の縦・横・高さをそれぞれ$x, y, z$(cm)とすると、$x, y, z$は非負で
\[2(x+z) \leq 24.8 \times 2\]
\[2(y+z) \leq 34 \times 2\]
を満たします。この条件下で体積$V=x y z$を最大化するわけです。

続きを読む