オブジェクトの広場はオージス総研グループのエンジニアによる技術発表サイトです

クラウド/Webサービス

ビットコイン論文からさぐる ブロックチェーンのヒント

第4回 タイムスタンプ
オージス総研
樋口 匡俊
2019年5月28日

今回はビットコイン論文の第3章「Timestamp Server」で説明されている、タイムスタンプ技術について見ていきます。第3章自体は非常に短いので、そこで挙げられている参考文献を中心に見ていくことにします。

ビットコイン論文におけるタイムスタンプ

タイムスタンプ (timestamp) は、二十年以上前から存在するセキュリティ技術です。最近でも、総務省のトラストサービス検討ワーキンググループにおいて、「トラストサービス」を支える技術の一つとして、活用に向けた議論が進められています。

総務省のホームページによると、タイムスタンプとは、「ある時刻にその電子データが存在していたことと、それ以降改ざんされていないことを証明する技術」です。

前回見たとおり、サトシは二重使用問題を解決するにはトランザクションの順番を知る必要があると考えました。タイムスタンプは、そのための基本的な枠組みとして、ビットコインに取り入れられています。

しかし、第3章「Timestamp Server」は、ビットコイン論文全12章の中で最も短い章です。図こそ付いていますが、ビットコインのタイムスタンプがどのようなものか、第3章だけで理解することは難しいように思います。

その短さとは反対に、参考文献の数は最も多い章です。論文末尾の参考文献リスト8本のうち4本がタイムスタンプの文献であり、第3章の文献なのです。

タイムスタンプの参考文献

タイムスタンプの参考文献4本のうち3本は、米国 Bellcore の研究者だったスチュアート・ヘイバー (Stuart Haber) とスコット・ストルネッタ (Scott Stornetta) らによって書かれたものです。

残りの1本は、TIMESEC というタイムスタンプ研究プロジェクトの論文です。TIMESEC は、ベルギーの大学 UCLouvain と KU Leuven の研究者らによって進められた、同国の国家プロジェクトでした。

4本とも、発表されたのは1990年代です。前回の電子マネーもそうですが、サトシはビットコインの開発にあたり、20世紀の技術を参考にしているのですね。

TIMESEC は、ヘイバー＆ストルネッタの研究から多くの影響を受けています。そこでまずは、彼ら二人の論文を中心に、タイムスタンプとはどのようなものか見ていくことにしましょう。

タイムスタンプの使いどころ

ヘイバー＆ストルネッタは、タイムスタンプを研究した背景として、文書や音楽、写真、動画などのデジタル化を挙げています。デジタル化が進めば、データを作成・変更したのはいつなのか証明しなければならない状況も増えると見込んだのです。

1990年代半ば、彼らは Surety Technologies (現 Surety, LLC) という会社を立ち上げ、自分たちの研究を商用化しました。当時、投資会社に向けて行ったプレゼンの資料には、彼らがタイムスタンプを適用できると考えていた領域が書き連ねてあります。

  • 監査証跡、システム・ログ (audit trail, system logs)
  • 通話履歴、通話記録、ファックス (phone logs, phone records, faxes)
  • 刑事上の証拠、裁判記録 (criminal evidence, court records)
  • 公証人 (notary public)
  • 写真、Ｅメール (photographs, e-mail)
  • 実験記録 (lab records)
  • 暗号学的証明書 (cryptographic certificates)
  • 資金移動、株取引 (funds transfers, stock trades)
  • 米国環境保護庁や食品医薬品庁への申請 (EPA, FDA submissions)
  • 政府への申告 (gov’t filings) ※ 税金等

筆者がこれらを眺めて思ったのは、なんだかどれもブロックチェーンの資料で見たことがあるような気がする、ということでした。具体例を挙げるのはひかえますので、上記の単語とブロックチェーンとを組み合わせて検索してみてください。

ブロックチェーンはデジタル資産の管理に活用できる、などと言われることがありますね。ブロックチェーンのユースケースとして検討されているものは、デジタル化の進展を見越して研究されたタイムスタンプのユースケースと、重なる部分が多いように思います。

ナイーブなタイムスタンプ

ヘイバー＆ストルネッタは、まず「デジタル貸金庫 (digital safety-deposit box)」と称するタイムスタンプサービスの考察からはじめています。※1

デジタル貸金庫

「デジタル貸金庫」は、クライアントが通信回線を通してデータを送ると、データをまるごとコピーして日時とともに保存します。後日、そのデータがその日時に存在していたこと、改ざんされていないことの確認が必要になったら、保存しておいたコピーおよび日時と突き合わせるのです。

彼らは、このタイムスタンプの方式をナイーブ (naive) と表現しています。問題がいくつもあるのに気付かないような、だまされやすく、うぶな人たちの方式だというわけです。

問題の一つは、プライバシー (privacy) です。クライアントは特に対策を施さず、データをそのまま送っているため、データの内容がサービスには丸見えです。

また、動画など大きなサイズのデータを送る場合、貧弱な回線容量 (bandwidth) では時間がかかります。サービス側も大きなストレージ (storage) を確保しなければなりません。

さらに、機能不全 (incompetence) に陥る可能性もあります。送信中にデータが壊れたり、サービスが保存したデータのコピーを誤って壊してしまうかもしれないのです。

ナイーブなタイムスタンプの改良

これらの問題を解決するため、ヘイバー＆ストルネッタは、ハッシュ (hash) とデジタル署名 (digital signature) の利用を提案しています。

改良① ハッシュ

まず、データはそのままの形では送らず、ハッシュという値に変換して送るようにします。

ハッシュ値は、「CE714BACCF60B190E7978BF56E31737C」のような意味不明で不規則な値になります。元のデータの内容が読み取れなくなりますので、先ほどのプライバシーの問題が解決するというわけです。

また、動画など大きなデータであっても、ハッシュ値に変換すると数十文字程度の小ささにおさめることができます。これによって、回線容量やストレージの問題も緩和できるようになります。

タイムスタンプを発行する対象は、元のデータではなく、そのハッシュ値とします。なぜそれでよいのかというと、あるデータのハッシュ値と、他のデータのハッシュ値とが、同じ値になることはめったに無いからです。後日、検査を行うときは、元のデータとコピーを突き合わせるのではなく、ハッシュ値を突き合わせて、同じ値であればほぼ間違いなく同じデータとみなせるのです。

改良② デジタル署名

クライアントがデータをハッシュに変換して送ると、サービスはハッシュに日時をくっつけたものにデジタル署名をして送り返します。

前回見たとおり、デジタル署名は、ある人があるデータを作成したことを検証できる技術でしたね。クライアントは署名を検証することで、サービスが目的のデータに対してタイムスタンプを押してくれたことを確認できますし、壊れたデータに署名するような機能不全が発生していたら検出できるわけです。

信頼できるタイムスタンプサービス

ハッシュとデジタル署名を用いて改良したタイムスタンプサービスを図示してみます。

信頼できるタイムスタンプサービス

クライアントは、タイムスタンプを発行するよう、タイムスタンプサービスにリクエストを送ります。リクエストには、タイムスタンプの対象となるデータのハッシュが含まれています。サービスは、ハッシュと日時に署名を付けて、レスポンスとして送り返します。

さて、これでナイーブではなくなった、と言ってよいのでしょうか？

ヘイバー＆ストルネッタは、まだ本質的な問題がある、と言います。その問題とは、第2回でもとり上げたトラスト (trust) の問題です。

図のような仕組みが成り立つためには、信頼できるタイムスタンプサービス (trusted time-stamping service) が存在しなければなりません。この改良したタイムスタンプサービスは、信頼できる第三者機関 (Trusted Third Party) すなわち TTP なのです。

節操のないタイムスタンプサービス

信頼できるタイムスタンプサービスには、サービスとクライアントが結託すること (colluding) を防ぐ仕組みが無い、とヘイバー＆ストルネッタは指摘します。サービスがクライアントと共謀して、うそのタイムスタンプ (false/fake timestamp) を発行することを防げないと言うのです。

例えば、アリスの発明品に関するタイムスタンプがあるとします。競争相手のボブは、同じようなものを後から発明したにも関わらず、サービスに何らかの見返りを与えるなどすれば、過去にさかのぼったタイムスタンプを発行してもらえるかもしれません。

アリスがいくら自分のタイムスタンプの正しさを主張しても仕方ありません。ボブのタイムスタンプも、「信頼できる」タイムスタンプサービスが発行した「正しい」タイムスタンプですので、先に発明したのはボブということになってしまいます。タイムスタンプが、過去から将来に亘ってうそ偽りなく公平に発行されるかどうかは、サービスを信じるよりほかないのです。※2

ヘイバー＆ストルネッタは、理想として、どんなに節操のない (unscrupulous) タイムスタンプサービスであっても、そのサービスが証明した日時は常に正しく、たとえうそのタイムスタンプを発行しようとしてもできないことを保証する仕組みがほしいと述べています。

誰が見張りを見張るのか？

そのような理想を実現することは、はたして可能でしょうか？

ヘイバー＆ストルネッタは多くを語らず、かわりに「しかし、誰が見張りを見張るのか？(But who will guard the guards themselves?)」という詩を引用しています。※3

おそらく、一人目の「見張り」はタイムスタンプサービスでしょう。サービスは、タイムスタンプを発行することで、誰かが日時をごまかすことを防いでいます。

そのサービスが信頼できないのであれば、サービスを監視する新たな見張りが必要になります。しかし、その新たな見張りも確実に信頼できるとは言い切れません。すると、その新たな見張りを見張る別の見張りが必要になります。そうして見張りは際限なく増えていきますが、いつまでも安心できるようにはならないのです。

このように彼らは、理論的にはトラストの問題を解決することは不可能であると暗示しながら、現実的と思われる対処方法を提案しています。以下、そのうちの二つを見ていきましょう。

トラストの問題の対処方法① リンキング

クライアントからタイムスタンプサービスへは、リクエストが随時送られてきます。どのようなリクエストが送られてくるか、サービスは前もって知ることはできません。

それならば、新たに発行するタイムスタンプに、既に発行したタイムスタンプの順番を含めるようにすれば、前後関係がハッキリするのではないか？そのような発想に基づき、タイムスタンプを順番につなげていく方法をリンキング (linking) といいます。

リンキング

タイムスタンプ間の関連を示す情報は、リンキング情報 (linking information) といいます。リンキング情報には、それ以前のリンキング情報（のハッシュ）を含めておきます。

例えば図のように、タイムスタンプ６０を発行したことの証明書には、リンキング情報６０を含めるようにします。リンキング情報６０には、その一つ前のリンキング情報５９を含めます。同様に、５９には５８の、５８には５７のリンキング情報を含めます。

ヘイバー＆ストルネッタは、このようにして形成されるタイムスタンプのつながりを、チェーン (chain) あるいはストリーム (stream) と表現しています。

もしも節操のないタイムスタンプサービスが、タイムスタンプ５８と５９の間にうそのタイムスタンプＸを差し込もうとしたとしましょう。その場合、まずはリンキング情報５９を、５８ではなくＸを含むよう書き換えなくてはなりません。しかし、すでにタイムスタンプ５９の証明書は発行済みであり、書き換えることは現実的ではありません。

仮に、リンキング情報５９を書き換えることができたとしても、それだけでは足りません。リンキング情報６０には、書き換える前の５９が残っているので、６０も書き換えなくてはならないのです。さらに、６１、６２、６３と、新たにタイムスタンプを発行するたびに、書き換えなくてはならないリンキング情報は増えていきます。それに伴い、節操のないタイムスタンプサービスがチェーンを書き換えられる可能性も、ますます低くなっていくわけです。

トラストの問題の対処方法② 分散型トラスト

分散型トラスト (distributed trust) は、タイムスタンプを発行するにあたり、無作為に選出された複数のクライアントがデジタル署名を行う方式です。信じる対象がたった一つの TTP ではなく、複数のクライアントに分かれているため、分散型といいます。

ヘイバー＆ストルネッタは、この方式であれば中央の信頼できるタイムスタンプサービスは不要だと述べています。彼らもサトシのように、TTP に依存しない方式も模索していたのですね。

TIMESEC の目標

ヘイバー＆ストルネッタは、その後もタイムスタンプの研究、改良を進めていきました。その成果を大いに取り入れたのが、TIMESEC プロジェクトです。

TIMESEC によると、タイムスタンプの方式は大きく二つに分けられます。

  1. TTP に基づく方式
  2. 分散型トラストに基づく方式

すでにヘイバー＆ストルネッタの最初の論文から数年が経過していましたが、当時商用化されていたタイムスタンプは、すべて1番の方式だったそうです。そこで TIMESEC でも、TTP に基づく方式を検討することになりました。

2番の分散型トラストについては、仕事 (professional environment) で利用するのはあまり現実的ではないと判断しました。多数の協力 (cooperation) が必要なことなど欠点があるのだそうです。

TIMESEC は、TTP に依存はするものの、TTP に対するトラストを最小化する (lower the necessary trust on the third party) ことをプロジェクトの目標としました。できる限り、信頼できるタイムスタンプサービスに依存しなくてすむような方式を研究することにしたのです。

ラウンドとマークルツリー

研究の結果、TIMESEC はトラストを最小化するとともに、大量のリクエストを効率よく処理できる方式を選択しました。本記事では、その方式をラウンド方式と呼ぶことにします。

ラウンド方式では、クライアントからのリクエスト一つ一つに対して、つどつどタイムスタンプを発行するのではなく、まとめて一度に発行します。一定時間待って、その間送られてきたリクエストをまとめて処理するのです。そうした処理一回一回をラウンド (round) と言います。※4

一つのラウンドには、複数のリクエストがたまります。たまったリクエストは、次の図のような二分木 (binary tree) にまとめられます。

ラウンドと二分木

図の右側、ラウンド６０の一番下に並んでいるハッシュＡ, Ｂ, Ｃ, Ｄ が、リクエストに含まれるハッシュです。

それらを二つずつペアにして新たなハッシュを算出します。図のハッシュＡＢはハッシュＡとＢのペア、ハッシュＣＤはハッシュＣとＤのペアをハッシュ化したものです。

そうしてペアのハッシュを下から順に繰り返し求めていくと、最後にひとつのハッシュにまとめることができます。そのハッシュを、ラウンド・ルート・バリュー (round root value) と呼びます。図のハッシュＡＤがラウンド・ルート・バリューです。

ラウンド・ルート・バリューからは、さらにもう一つハッシュを算出します。ラウンド・バリュー (round value) です。

ラウンド・バリューは、ラウンド・ルート・バリューと、ひとつ前のラウンド・バリューとを組み合わせて算出します。要するに、二分木をリンキングするのです。リンキングすることで、各ラウンドの前後関係が明らかなものとなり、タイムスタンプサービスが不正を行うことが難しくなるわけです。

各ハッシュのタイムスタンプには、それぞれの属する枝 (branch) を再構築するために必要な情報を含めておきます。例えば、ハッシュＡのタイムスタンプには、次のような情報を含めます。

  • はじめにハッシュBとペアにしてハッシュＡＢを求める
  • ハッシュＡＢをハッシュＣＤとペアにしてハッシュＡＤ、すなわちラウンド・ルート・バリューを求める
  • ラウンド・ルート・バリューとラウンド・バリュー５９をペアにしてラウンド・バリュー６０を求める

こうした情報を用いて枝を再構築できれば、そのハッシュはそのツリーに属すること、つまりそのラウンドに属することが分かります。このように、ラウンド方式のタイムスタンプとは、あるデータがあるラウンドで処理されたことの検証に用いる証明書のようなものだと言えます。

TIMESEC は二分木と呼んでいますが、このような二分木は発案者の名前をとって、マークルツリー (Merkle Tree) と呼ばれることがあります。マークルツリーは上記のような検証を効率よく行えることが知られています。

新聞の活用

ラウンド・バリューの一部は、新聞 (newspaper) などのメディアに定期的に掲載します。掲載されるラウンド・バリューは、ビッグ・ラウンド・バリュー (big round value) と呼ばれます。※5

検証を行うときは、新聞からビッグ・ラウンド・バリューを取得し、タイムスタンプの情報と組み合わせ、ラウンド・バリューのチェーンを再構築します。もしも、うそのデータが混じっていると、新聞のビッグ・ラウンド・バリューと矛盾する値が算出されるので、不正が発覚するというわけです。

このように、ビッグ・ラウンド・バリューは、他のタイムスタンプに対するトラストの根拠であり、誰もが信じなければならないものです。そして、そのトラストを支えるのは、新聞のようなメディアなのです。※6

この場合の新聞は、変更不能で、広く裏付けられたメディア (unmodifiable, widely witnessed media) として選ばれています。たしかに、新聞は広い範囲に配られ、大勢の人が中身を確認できます。一部、二部ならともかく、すべての新聞紙上のビッグ・ラウンド・バリューを変更することは困難でしょう。

ラウンド方式の使いどころ

ラウンド方式は、ラウンドの時間を長くとると、より大量のリクエストを一度に処理できるようになります。

そのかわり、同じラウンドに属するデータ同士の前後関係は保証されません。9時に受け取ったデータも、10時に受け取ったデータも、同じラウンドに属するのであれば、どちらが早いかハッキリしたことが言えないのです。

リクエストを受け取った順に、ツリーの左から右へ順番に並べることにしておけばよさそうですが、サービスが本当にそのような順番で並べてくれることを保証する仕組みはありません。サービスを信じればよいのですが、トラストを最小化したい TIMESEC としてはそれは避けたいところです。

ラウンド方式で保証されるのは、ラウンド同士の順番です。ラウンドは一定時間ごとに処理されるので、例えば、ラウンド５９の次にリンキングされたラウンド６０に属するデータは、ラウンド５９に属するデータよりも一定時間あとのデータであると言えるわけです。

このようにラウンド方式は、精度の高い日時を記録するかわりに、順番を効率よく判定することに向いていると言えるでしょう。

第3章「Timestamp Server」

以上を踏まえて、最後に第3章「Timestamp Server」を読んでいきましょう。第3章は、ほぼ、ここまで見てきたことの要約・言い換えとなっています。

A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper or Usenet post [2-5].

タイムスタンプサーバーは、タイムスタンプを付与する複数のアイテムからなるブロックのハッシュを取得し、例えば新聞や Usenet の投稿などにおいて、そのハッシュを広く発信することで機能する [2-5]。

タイムスタンプサーバー

ヘイバー＆ストルネッタと TIMESEC の文献に基づき、タイムスタンプサーバーについて説明しています。文末の「[2-5]」はその文献番号です。

ブロック (block) とは、TIMESEC でいうラウンドに相当するものですね。各ラウンドで、複数のアイテム (item) にまとめてタイムスタンプを発行するわけです。

主なアイテムはトランザクションです。二重使用問題を解決するには、精度の高い日時は特に必要なく、トランザクションの順番が分かればよいので、前後関係を効率よく判定できるラウンド方式を採用するわけです。

トランザクションはマークルツリーにまとめられるのですが、それについては論文の第7, 8章で説明されます。

ブロックのハッシュは、TIMESEC でいうラウンド・バリューに相当するものですね。ラウンド・バリューを公開する先としては、新聞の他に Usenet が挙げられています。Usenet とは、フォーラムのようにニュースなどを共有、議論できる分散型システムのことです。

The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash.

タイムスタンプは、そのデータがその時点でたしかに存在しており、それはどう見ても、そのハッシュになるためだということを証明する。

単なるタイムスタンプの目的、機能の説明ですね。

Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.

各タイムスタンプはひとつ前のタイムスタンプをそのハッシュに取り込んで、チェーンを形成していき、さらに付け加えられていく各タイムスタンプがそれ以前のタイムスタンプを強化していく。

これも単なるリンキングの説明ですね。

以上で第3章は終わりです。しかし、これではまだ TIMESEC のいう、TTP に基づくタイムスタンプ方式の域を出ていません。

新聞と PoW

言うまでもなく、サトシは TTP に基づかない方法を考えます。続く第4章「Proof-of-Work」を少しだけ読んでみましょう。

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proof-of-work system similar to Adam Back’s Hashcash, rather than newspaper or Usenet posts.

P2P に基づく分散タイムスタンプサーバーを実装するには、新聞や Usenet の投稿ではなく、アダム・バックのハッシュキャッシュと類似のプルーフ・オブ・ワークのシステムを用いる必要がある。

サトシは、タイムスタンプを発行できるサーバーが複数存在する、分散タイムスタンプサーバー (distributed timestamp server) の仕組みを導入しようとします。しかし、それぞれのサーバーが勝手にタイムスタンプを発行し、それぞれ勝手に新聞にラウンド・バリューを掲載するわけにはいきません。

そこで、新聞のかわりに、プルーフ・オブ・ワーク (proof-of-work) 略して PoW のシステムを導入すると言うのです。

TIMESEC は新聞を、変更不能で広く裏付けられたメディアとみなしていましたね。そのかわりと言うからには、PoW には新聞と同様の性質が期待されるわけですが、その説明は次回としたいと思います。

おわりに

今回はビットコイン論文の第3章「Timestamp Server」で説明されているタイムスタンプ技術について、論文の参考文献を中心に説明しました。

ヘイバー＆ストルネッタも TIMESEC も、トラストの問題を完全に解決できるかどうかという問いについては慎重な姿勢を見せていますが、その上でなお、トラストの問題にできる限り対処しようとしました。

サトシは、分散タイムスタンプサーバーを実装するため、新聞のかわりに PoW を導入することにしました。ただ、それ以外の基本的な仕組みはラウンド方式に則っています。

タイムスタンプとブロックチェーンは、その仕組みや適用領域など、重なる部分が多いと思われます。本記事末尾の参考資料などをもとに、さらにタイムスタンプについて調べてみると、ブロックチェーンについて考えるヒントに出会えるかもしれません。

注

※1: 原文では二重引用符付きで “digital safety-deposit box” と表記されており、特定のサービスを指すものではありません。

※2: 信頼できるタイムスタンプサービスについては、問題視ばかりせず、「安全性だけではなく、（中略）リスク等を含めたコストも十分考慮することが必要」（「デジタルタイムスタンプ技術の現状と課題」p.26）と言えるでしょう。信頼できるタイムスタンプサービスと似たような仕組みを持つ、RFC 3161 (Time-Stamp Protocol (TSP))という標準提案も存在します。

※3: ローマの詩人ユウェナーリス (Juvenal) の詩の英訳。この句を含む全体は、岩波文庫「ローマ諷刺詩集」第六歌を参照。

※4: 「round」という用語は、Benaloh らの論文「Efficient Broadcast Time-Stamping」からとったものでしょう。ヘイバー＆ストルネッタは、かわりに「interval」という言葉を用いています。

※5: こちらのツイッターの投稿から、ニューヨーク・タイムズに掲載されたリンキング情報とヘイバーの写真を見ることができます。

※6: 最近ストルネッタはインタビューに応えて、新聞にリンキング情報を載せるアイデアの本質は、「ユーザー自身が部分的な記録の保有者になること(the people who wanted the service became holders themselves of part of the record)」だと述べています。

参考資料

ヘイバー＆ストルネッタについては、主に以下の文献を基に説明しています。

  • Stuart Haber, W. Scott Stornetta. How to Time-Stamp a Digital Document, Advances in Cryptology-CRYPTO’ 90, 1991 ※ ビットコイン論文の参考文献に挙げられているのは「Journal of Cryptology」に掲載された版

TIMESEC については、主に以下の文献を参考にしました。

日本語の資料としては、以下が参考になります。

以下は、その他の参考文献です。