AidoskuneenのWhitePaperの参考文献リンクをまとめました

こんにちは、しゃちです。

ついにお正月休みが明けてしまいましたね。

満員電車に揺られて会社に行くくらいなら地元に帰って農家になりたいなぁって思う今日この頃。

雄大な自然に囲まれてのんびりと暮らしたい。

という話を農家の友達に話すと「農家も意外と忙しいんだからね」ってよく怒られます。

ぽけーっと過ごしながら勝手にお金が溜まる生活を送りたいものです。

さてさて、今回の記事はただの備忘録です。

AidosKuneenのホワイトペーパーを読むに当たって巻末に書いてある参考文献のリンクをまとめました。

(参考文献はまだ読んでません。読む気力がでない……

AidosKuneenのホワイトペーパー

AidosKuneenのホワイトペーパーはGithubで取得できます。

場所はここです。

v0.04の「adk_whitepaper.pdf」をクリックするとpdfファイルがダウンロードできます。

今のところ、2018年1月14日に更新されたものが最新のホワイトペーパーになっています。

まだStep2の内容が盛り込まれる以前のものになっているので内容は少し古いかもです。

ホワイトペーパーの内容はすべて英語で記載されています。

ただでさえ技術もわからぬのに英語なの!?って思うでしょう。

この時点でちょっと読む気が失せますよね……。

でもご安心ください。

なんと……SKRさんが日本語に翻訳してくれています!

【翻訳】ADKのホワイトペーパー(ver0.04 ドラフト)の日本語訳

(SKRさん……すごい……)

という訳で、ADKのホワイトペーパーを読みたい方はSKRさんのブログをご覧ください。

参考文献のまとめ

Aidoskuneenのホワイトペーパーには18個の参考文献が記載されています。

ADKのホワイトペーパーを読み解くためにも、まずは参考文献から読んでいこうじゃないかって方がいるんじゃないでしょうか。

そんな方に向けて、参考文献のリンク集をまとめました。

意外と文献を探すのが手間取って大変でしたので備忘録ついでに共有します。

ちなみに全部英語の論文です。

[1] Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, 2008.

言わずとしれた名著。ビットコインの原点。サトシ・ナカモト!

一度は読んでおくことをおすすめします。

有名な論文なので日本語訳も存在します。

英語がめんどくさい方はこちらをどうぞ。

意外と短いのでさくっと読み終えることができます。

ブロックチェーンの基本的な知識は身に着けておいた方がいいと思います。

まったく知識がない方は下記の入門書がおすすめです。

上記論文をかみ砕いてわかりやすくした内容になっているので良かったです。


図解入門 最新ブロックチェーンがよーくわかる本

[2] Crypto Forum Research Group, draft-irtf-cfrg-xmss-hash-based-signatures-10 XMSS:Extended Hash-Based Signatures, 2017.

XMSSについての論文です。

ホームページはおそらくここです。

72ページもあるので気をしっかりもってお読みください。

ちなみにXMSSとは下記のことです。

XMSS

XMSS(eXtended Merkle Signature Scheme)は2011年に発表され,インターネット上のドラフトは2015年にできました。

いくつかの点を除いて,Merkle木のような構成になっています。XMSS木には,親ノードがハッシングされる前に子ノードへXORされるマスクがあります。全てのノードでマスクは異なります。

二つ目の特徴は,XMSS木の葉がOTS署名公開鍵のハッシュではなく,L木と呼ばれる別の木のルートであることです。

L木の葉の中には,WOTS+公開鍵の要素が格納されています。 WOTS+公開鍵をなぜ木に格納するのかはHuelsingが論文内で書いてあるので引用します。

The tree is not used to store a WOTS public key but to hash it in a way that we can prove that a second-preimage resistant hash function suffices (instead of a collision resistant one).
意訳:この木はWOTS公開鍵を格納するために使用されるのではなく,(衝突耐性の代わりに)第二原像攻撃耐性のあるハッシュ関数が十分であることを証明できるようにハッシングするために使われます。

引用元:ハッシュベース署名方式(4) XMSSとSPHINCS

……うん、次の論文に進みましょう。

[3] Serguei Popov, The tangle, 2017.

IOTAの論文ですね。

日本語版の論文はこちらです。

IOTAもDAGを使用しているので、ぜひ読んでおきたい論文ですね。

IOTA(アイオータ)やByteball(バイトボール)という暗号通貨をご存知だろうか。いま、ブロックチェーンとは異なる、DAG(有向非巡回グラフ)を利用した上記の暗号通貨が期待されている。ブロックチェーンでは、あるブロックに着目したときに、前後につながるブロックが必ず1つになるのに対し、DAGではブロックチェーンと同じように「向き」があるものの、あるブロックの前後には複数個のブロックが同時に連結可能という特徴がある。また、DAGでは、ビットコインのようなブロックサイズの概念がないため、理論上は無限の量のトランザクション(商取引)を処理することが可能である。現在ではビットコインの送金に数分、場合によっては数日かかることもあるのに対し、DAG構造を持った暗号通貨では、一瞬で送金することが可能である。

引用元:ブロックチェーンの先へ、DAGが実現する未来

DAGってなんぞやと思った人は下記のページがご参考になると思います。

とても丁寧に説明されているのでわかりやすいです。

DAG型暗号通貨のすすめ ブロックチェーンを代替しうる新技術

[4] Sheldon M. Ross, Introduction to Probability Models. 10th Edition, 2012.

こちらは論文ではなくて普通の本です。


Introduction to Probability Models, Tenth Edition

中古で6000円です。

(……高い)

ちなみに2019年4月に最新版が発売されます。


Introduction to Probability: Models and Applications (Wiley Series in Probability and Statistics)

お値段は13195円です。

(……高い!!!)

ちなみにこの本、ネットで読めちゃいます。

場所はこちら

なんでだろう……。いいのかな。

無料って聞くと、お得感より警戒心の方が大きくなるよね。

ちなみにアドレスをたどると、サウジアラビアのキングサウド大学が公開しているようです。

大学の生徒さんしかのぞいたら行けないアドレスが何かの手違いで一般公開されているのかもしれない……。

[5] Sergio Demian Lerner, DagCoin: a cryptocurrency without blocks, 2015.

一番最初にDAG構造を唱えたであろうと言われている暗号通貨DagCoinの論文ですね。

[6] Johannes Buchmann, Erik Dahmen, Andreas Hülsing, XMSS — A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions, 2011.

こちらもXMSSに関する論文ですね。

ちなみに論文の概要は下記のとおりです。

We present the hash-based signature scheme XMSS. It is the first provably (forward) secure
and practical signature scheme with minimal security requirements: a pseudorandom and a second
preimage resistant (hash) function family. Its signature size is reduced to less than 25% compared to
the best provably secure hash based signature scheme.

[7] Irene Giacomelli, Jesper Madsen, Claudio Orland, ZKBoo: Faster Zero-Knowledge for Boolean Circuits, 2016.

ZKBooを用いたゼロ知識証明の論文です。

海外のゼロ知識証明関連のまとめページはこちら

そもそもゼロ知識証明とはなんぞやという方はこちら

[8] Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, Greg Zaverucha, Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives, 2017.

こちらもゼロ知識証明に関する論文です。

[9] Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar, SPECTRE: Serialization of Proof-of-work Events: Confirming Transactions via Recursive Elections, 2016.

SPECTREに関する論文です。

SPECTREについては下記が参考になると思います。

ハイコーン(HYCON)が世界初のDAG∙スペクター合意アルゴリズムの開発に成功したと23日に明らかにした。
この技術が適用されると、ハイコーン∙ブロックチェーン∙ネットワークは、各ノードが分散処理され、スペクターを発動させることにより、最小3,000TPSでビザカードを運用するビザネットのように処理速度を実現することになるそうだ。

ハイコーンは6月自体メインネットを稼働した後、ゴースト・プロトコルの更新を通じて毎秒処理速度を2倍に増加させ、来月7日採掘量の90%に削減するハードフォークを計画、11月中にバイバック完了など、既存のブロックチェーン業界で想像できなかった革新をみせている。

スペクター合意アルゴリズムの開発も既存ロードマップの上、2019年上半期に終了するのが計画だった。少なくとも1年以上の技術開発がかかると予想していたが、ゴースト・プロトコルの更新が行われて1ヶ月も経ってないうちにDAG∙スペクターの開発に成功したというニュースを伝えたのだ。ハイコーンの保持者は、技術力と信頼という二つの信仰を持つようになった。

スペクター(SPECTRE)はSerialization of Proof-of-work Events:Confirming Transactions via Recursive Electionsの略である。
ビットコインがブロックチェーン・コンセンサスを維持する時ナカモト・プロトコルが使用される一方、ハイコーン・コンセンサスを維持にはスペクターというプロトコルが適用されるのである。

スペクターはブロック間の順序を決めるため、ブロックの間に投票アルゴリズムを適用することにより、ブロックチェーンを方向性非循環グラフ(directed acyclic graph:DAG)の形に一般化する。
スペクターを通じた取引は数秒以内に完了することができ、処理できるデータ量が最大化されるのだ。
それで、このプロトコルは、ナカモト・コンセンサスを適用する時に発生する信頼性と拡張性の矛盾を緩和させる。

ブロックチェーン・ネットワークの速度限界を改善するためにハイコーンがDAGと共に強調するキーワードはスペクター合意アルゴリズムである。スペクターはDAGの特性に合わせてトランザクションのスループットと転送速度を引き上げることに焦点が当てられている。

ハイコーン・ブロックチェーンにDAG∙スペクターが適用されると、ゴースト・プロトコルの更新に成功した10月31日に次ぐハイコーン∙ブロックチェーンのコンセンサス∙プロトコルがスペクターになるのだ。
解りやすく説明すると、ブドウの房のようにブロックがジグザグに定着されるが、これをDAG(Directed Acyclic Graph)構造だという。

DAGは数学的なtopology構造で、一方向にノードが繋ぐツリー構造である。
ブロックX内のトランザクションがブロックY内のトランザクションより先にブロックチェーンに追加されたり、逆にブロックYのトランザクションがブロックX内のトランザクションより先に追加される形態である。

グロスファー∙ハイコーンのキム∙テ∙ウォン代表は”12月中にブロックチェーン技術を客観的に理解し研究と評価できるグローバル∙ブロックチェーンの関連企業、開発者、研究所の参加者の方々を対象にミート∙アップを開催する計画だ。”と述べ、”このミート∙アップでハイコーン∙ブロックチェーンのDAG∙スペクター合意アルゴリズムの開発概要と技術デモンストレーションを発表する予定だ。”と世界初の具現に成功したハイコーン∙ブロックチェーン∙ネットワークに適用されるDAG∙スペクターの技術力に自信を持っている。

今までのスペクターはイスラエルの研究チーム(ヨナタンソムポーリンスキー、アビブジョハル)が設計した論文としてのみ存在したが、ハイコーンチームが具現に成功することによって世界初のその姿を現わすようになった同時に、大韓民国の暗号貨幣のハイコーンがグローバル∙ブロックチェーンの技術を先行した最初の事例として記録される見通しである。

引用元:世界初DAG / スペクター合意アルゴリズムの開発に成功

[10] Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,1995.

量子コンピューターで作用するアルゴリズムShorの論文です。

Shorについてはこちらが参考になると思います。

[11] Masoud Mohseni, Peter Read, Hartmut Neven, Commercialize early quantum technologies, 2017.

量子技術の商用化についての内容が記載されています。

webサイト版はこちら

[12] PQCRYPTO, Post-Quantum Cryptography for Long-Term Security, Initial recommendations of long-term secure post-quantum systems, 2015.

H2020 PQCRYPTO project(※78)は2015年3月から3年間限定で活動を開始したプロジェクトで、耐量子暗号に関連する研究活動が行われています。活動を開始した半年後の2015年9月には、暫定版ではありますが耐量子暗号アルゴリズムの推奨リスト(ポートフォリオ)の案が既にまとめられています。

引用元:Internet Infrastructure Review(IIR)Vol.31

……ということです。

[13] Nicolas van Saberhagen, CryptoNote v 2.0, 2013.

ByteCoinやMoneroなどに実装されている匿名技術のCryptNoteについて記載されています。

CryptNoteについて知りたい方はこちら

[14] John Tromp, Cuckoo Cycle: a memory bound graph-theoretic proof-of-work, 2014.

Proof-of-Work にはハッシュ関数を使うった問題(hashcash)を考えるのが一般的だが、これは乱数を用いて作られたグラフに対して巡回路を見つける問題を使うといいのでは?という内容の論文。 グラフを探索するため、メモリに対してランダムでアクセスする必要性が発生するため単純な実装ではGPUやASIC等で高速化するのはかなり難しく、いわゆる耐GPU/耐ASICを謳ったPoWアルゴリズム

引用元:【随時更新】暗号通貨・ブロックチェーン論文★必読リスト

[15] Anton Churyumov, Byteball: A Decentralized System for Storage and Transfer of Value.

Byteballのホワイトペーパーです。

グーグル翻訳で日本語化している方がいました。

興味ある方はこちら

[16] Michael Szydlo, Merkle Tree Traversal in Log Space and Time, 2004.

マークルツリーに関する論文です。

マークルツリーは、公開鍵暗号の開発者の一人であるラルフ・マークルによって1979年に発明されました。マークルツリーとは、ファイルのような大きなデータを要約した結果を格納するツリー構造の一種です。主に大きなデータの要約と検証を行う際に使用されます。その計算にはハッシュ関数が利用されていることから、ハッシュ木とも呼ばれています。

ブロックチェーンはブロックサイズに限りが有ることから大きなデータを書き込むことを苦手としています。これをマークルツリーを使って克服しています。一般的に大きなデータはブロックチェーンの外のサーバーにデータを置きます。そのデータをハッシュ化しそたものをブロックチェーンに書き込みます。こうすることで、ブロックチェーンに書き込まれたデータは、消すことができなくなり、記録として残り続けます。そして元データをハッシュ化したものと、ブロックチェーンに記録されたハッシュを比較することで、データの証明を行うことができます。

この場合、1データしかブロックチェーンに保存することができません。複数のデータを保存するときにマークルツリーが活躍します。複数のデータをマークルツリーを使うことで短いハッシュにまとめることができます。こうすることで、1つの取引で多くのデータの記録を残すことができます。1つの取引にまとめられるメリットとして、書き込む際の取引手数料を抑えることができる、1回の取引回数ですむため、取引の承認待ちも、その1取引分だけ待てば良いといことで、承認までの時間短縮にもつながります。

この方法を活用しているものはたくさんありますが、有名なところだとドキュメントなどの存在証明を行うサービスであるFactomがこの方式を使っています。

引用元:トランザクションデータを要約する技術「マークルツリー」

[17] PQCRYPTO, Post-Quantum Cryptography for Long-Term Security, 2015.

内容については[12]を参照ください。

[18] David Schwartz, Noah Youngs, Arthur Britto, The Ripple Protocol Consensus Algorithm, 2014.

リップルコンセンサスについて記載されています。

こちらで日本語化されている内容を読むことができます。

ちなみに本論文の概要は下記の通りです。

ビザンチン将軍問題のためのいくつかのコンセンサス・アルゴリズムが存在するが、特に分散型支払いシステムに関連する場合、ネットワーク内のすべてのノードが同期して通信するという要件が問題となり待ち時間が長くなってしまう。本研究では、大規模なネットワーク内で集合的に信頼できるサブネットワークを利用することにより、この要件を回避する新しいコンセンサスアルゴリズムを提示する。これらのサブネットワークに必要な「信頼」は実際には最小限であり、メンバーノードの原則的な選択によってさらに削減できることを示す。さらに、ネットワーク全体で合意を維持するために最小の接続性のみが要求されることも示す。結果として、レイテンシーの低いコンセンサスアルゴリズムが得られ、ビザンチン障害にもかかわらず頑健性が維持される。我々は、このアルゴリズムをRipple Protocolの一部として実装した。

引用元:Ripple Protocol Consensus Algorithm日本語訳

まとめ

参考文献のリンクについてまとめました。

内容についてはまだ読んでないのでなんとも言えませんが、参考文献を理解するだけで相当な知識が身に付きそうな気がします。

根性がある方はぜひ一読してみるとよいと思います。

Step2の実装が完了したらホワイトペーパーに合わせてADKのソースコードも見ていきたいですね。

 

今回は参考文献が多かったので関連するサイトを探すのがちょっと大変でした。

まとめている途中、ちょっと疲れたから手を抜いちゃおうと思ったのは秘密です。