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

4 演算量証明

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

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

Continue reading

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

3 タイムスタンプサーバ

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

fig2

Continue reading

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

2 電子通貨のやり取り

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

fig1

Continue reading

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

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

1 はじめに

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

Continue reading

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

まずは原論文Abstractから。

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

コミケにおけるビットコイン決済試行の結果

 今回のコミックマーケットC85では、試験的にビットコイン決済を導入しました。その顛末を残しておきます。
準備編
 まず決済環境の用意です。Android携帯にはビットコインアプリがいくつかあるようですが、私が使っているiPhoneでは、アップルの方針なのかビットコイン決済が可能なアプリが許可されていません。いろいろと考え、最終的に自宅のWindows PCにiPhoneからSSH+VNCでアクセスすることにしました。
 対面でビットコインを使ったことがないため、取引にかかる時間がわかりませんでしたが、聞くところによると10分ほど必要だとのことです。そうなると、購入者には決済完了まで待たせて、買い物などで暇を潰してもらわなくてはなりません。
 それは仕方ないにしても、問題となるのは、複数の人が決済を待っている場合です。最初は、ブースにQRコードを表示して「ここに振り込んでください」とでも書いておこうと思ったのですが、リアルタイムで決済不可だとすると、誰が払ったのかわからなくなります。2人が待っている時に、1人分しか払い込まれていないのに、両人が「払った」と主張することが考えられます。送金者のアドレスを確認すれば良いではないかとも思いましたが、ビットコインでは送金情報はすべて公開されます。そのため、正規の購入者が私のアドレスに払い込んだのをネットで見て、送金元のアドレスを第3者が用意することが、原理的には可能です。

Continue reading

コミックマーケット(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にお会いしましょう。

DMM.comの3Dプリントサービスを利用してみました

なぜかあのDMM.comが3Dプリントサービスを開始しました。面白そうなので早速使ってみました。
プリントするデータはこれです。国土地理院で公開されている10mメッシュデータを、自作プログラムでSTL形式に変換したものです。場所は谷川岳。日本全国のデータが公開されているので、どの山でもデータを作成可能です。サイズは横50mm、奥行き43mm。
dmm5.jpg

Continue reading

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)です。以下の解答を見ずに、一度チャレンジしてみることをおすすめします。

Continue reading

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

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

Continue reading