ADK

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

更新日:

ADKの情報を追ってきましたが、実は技術面も理解したい。

 

どんなことかと言うと、、、

ADKは個人の資産が政府等にわからないように、資産のプライバシーをとくに重視した暗号通貨です。

いかに資産を他人に把握されずにしつつ、送金をスムーズにできるか、そういったところの開発に苦心されています。

 

それをホワイトペーパーで説明されています。

少しは理解したい...

 

ただ、残念ながら私には技術的な知識が無いので理解するのも難しく、皆さんへうまく説明することもできません。

 

そこで、まずはホワイトペーパーを訳してみることにしました。

 

 

 

ホワイトペーパー

さて、ADKのホワイトペーパーはgithubにあります。

 

ここです(HP)。

ホワイトペーパーは2018年1月に書かれたドラフト版(ver0.04)で、内容も今後変わると思います。

 

まず英語の時点で読む気にならない。

 

ということで訳すわけなのですが、前にSlackの有志が訳してくれたものがあります。

ただし、これは一番最初に公表されたもの(ver 0.02)をベースにしたものです。

 

現在のとは内容が変わっていますので、これを参考に訳しました。

 

※ADKを広めるため、理解を深めるために訳しています。

 

翻訳内容に変な部分があれば、すべては私の責任です。

何かあれば教えてくださいm(__)m

(翻訳後のPDFはこちら→ PDF )

 

 

概要(Abstract)

本書では、新しい仮想通貨「Aidos Kuneen(ADK)」を紹介します。Aidos Kuneenは、量子コンピュータ時代にふさわしく、ブロックレスで匿名性に優れており、分散処理とスケーラビリティを一切の手数料なしに実現した仮想通貨です。

このコインでは、トランザクションが互いに参照しあい、DAG(Directed Acyclic Graph)構造を形成する「iMesh」を採用しています。

悪意のある二重決済を防ぐためにDAG構造を調べ、どの取引が高い確率で正規のものであるかを「SPECTRE」に基づき判断します。「SPECTRE」により、ネットワークの演算力の50%までの攻撃への耐性があります。

署名には、数ある耐量子コンピュータのアルゴリズムのなかで最も実用的で、署名サイズと公開鍵サイズが比較的小さいハッシュベースの署名「XMSS」を採用しています。

ネットワーク内の匿名性を与えるために、ADKはAKShuffleを採用しています。AKShuffleは耐量子コンピュータのためのゼロ知識証明「ZKBoo(ZKB++)」を組み込み、全ネットワークで真の匿名転送を実現します。

IoT部門の将来の予想される成長へ対応するため、coPoW(cooperative Proof of work)を導入します。コインの送信者は、coPoWにより共同でPoWを実行することができます。

最後に、あるトランザクションをDAG上で確定させるために必要な、最小の参照トランザクション数を求めるために、iMeshにおける末端トランザクション数ごとに起きうる状況のシミュレーションを行いました。これは、トランザクションサイズにできるだけ影響を与えない形で、より短い承認時間になるシステムを目指すために行われました。

 

 

序論(Introduction)

2008年にSatoshi Nakamoto[1]により紹介されたかつては知られていない暗号通貨、ビットコインは現在、一般人や政府にも広く注目を浴びています。ビットコインネットワーク内で、トランザクションはブロックへ書かれます。このブロックはProof of Work(PoW)システムを使い、マイナーとして知られる強力なコンピューターによって暗号学で承認されます。ブロックが承認されるとブロックチェーンという適切な名前の、ブロックが連続して成長する鎖の末端に付け加えられます。マイナーはその後、ビットコインネットワーク上で取引をした送信者から、トランザクション手数料という形でブロックの承認の報酬を与えられます。

現在、ブロックチェーンに10分ごとに1つほどの速度でブロックが加えられます。トランザクションはブロック内で入出力アドレスにより構成されており、入力アドレス自体が前のトランザクションの出力アドレスです。これはネットワーク内にある全ての過去のビットコイントランザクションの監査可能な履歴をもたらします。所有権を証明するために、Elliptic Curve Digital Signature Algorithm (ECDSA:楕円曲線電子署名アルゴリズム)を使ってトランザクションを署名することでオーナーが正規であるかを確認しています。

 

しかしながら近年、ビットコインは以下の様な問題を抱えている事が明らかになっています。

・低いスケーラビリティ

ビットコインのコアノードにおいて、ブロックサイズに限りがあり、上限を超えるとトランザクションの保存ができません。その為、多くのトランザクションが同時に送信された場合、現行ブロックにトランザクションの保存がされなくなってしまうスケーラビリティ問題が生じてしまいます。

・高い手数料

トランザクションの利用者はブロックにトランザクションを含めるためにインセンティブとしてマイナーに送金手数料を払わなければなりません。ビットコインの取引が増え価格が上昇すると、ビットコインの手数料も相対的に高くなります。すると、ビットコインネットワークによる少額の送金手数料が送金されるビットコイン自体の価値を超えてしまいます。このため、少額の送金を行う場合は、複雑なスキームが必要となります。(例:マイクロペイメントチャンネル)

・量子コンピューターに対する脆弱性

2017年時点で量子コンピューターの開発は未だ初期段階ですが、小さな量子ビットで量子演算の実験は着々と進められています。Googleは量子演算技術の商用実用化を5年以内に実現するとレポートしています[11]。その一方でShor’sアルゴリズム[10]によると、ビットコイン等に使われているECDSAを含む離散対数署名は量子コンピューターの圧倒的な演算力により容易に突破されてしまいます。

・脆弱な匿名性

ビットコインを利用する為には、過去に利用されたトランザクションを参照してトランザクションを実行せねばならず、これらのトランザクション情報は全て公開されています。故に、誰でもアドレス間のビットコインの移動を見ることができるのです。

これらの問題に取り組むため、私たちは新しい暗号通貨"Aidos Kuneen"を紹介します。iMeshというAidos KuneenネットワークはDAG(Directed Acyclic Graph:有向非巡回グラフ)技術を採用しています。これはブロックやブロックチェーンが存在せず、トランザクションが直接別のトランザクションを参照する技術です。トランザクションの確定は別トランザクションの投票(vote)数により決定されます。iMeshにより、スケーラビリティとマイナー無しの恩恵を受けることができるのです。そのため、マイニングのインセンティブを与える送金手数料が不要となります。

 

Aidos Kuneenは以下を提供するため、特に設計されています。

・スケーラビリティの向上

iMeshではトランザクションを確定するためにPoW計算が相対的に容易に行え、即時にiMeshに保存されます。故に、iMeshにトランザクションが保存されるのを待つ必要はありません。また、一度に保存できるトランザクション数やサイズに制限もありません。iMeshの利用が増えると、より多くのトランザクションが行われるようになります。つまり、ネットワークが成長すると、トランザクションの確定時間が短くなります。

・手数料なし

(マイナーが存在しないため)手数料を払う必要がないので、特別な知識や技術なくどんな量でも極少量でも送金する事が可能です。

・量子コンピューター耐性

Aidos Kuneenは強力な量子コンピューターセキュリティを持つハッシュ構造ベース署名を採用しています。量子コンピューター耐性を持たせるために、Ring-LWEを含む多くの格子構造ベースやハッシュ構造ベースの署名等があります。しかし、その多くは暗号鍵や署名のサイズが大きく実用的とは言えません。例えばRing-LWEや格子構造ベースの署名の暗号鍵のサイズは数キロバイトになります。それはつまり、これらの手法の1つを採用すると、アドレスが非常に長い文構造となり、技術の無い一般大衆が使われにくくなる。広く毎日使われることを目的とした暗号通貨にとって、これは全く適していません。

そのようなものとして、我々は代わりにハッシュ構造ベースの署名に注目しました。SPHINCSの様なハッシュ構造ベースの署名では、同じ公開鍵を複数回、再使用することができ、それは正しい方向への一歩です。しかし、SPHINCSでも他の方法と同じく、大きな公開鍵サイズ(約1 KByte)になってしまい、我々の利用には適しません。

ついに、人間の使いやすさと鍵サイズの理想的なバランスがあるものとして、拡張マークル署名方式(XMSS)を見つけました。これにより同じ公開鍵をかなりの回数(1000回以上)繰り返して利用することが可能となります。SPHINCSと異なり、XMSSはたった32Byteの軽い公開鍵で署名鍵サイズが約3KByteになりました。XMSSは2128bitsの量子コンピューターセキュリティにも対応しています。[12]

・強い匿名性

耐量子コンピューターの匿名性ではゼロ知識非対話(ZKNI)証明(ZKBoo) [7] を採用しています。より広いネットワークや受信者にアドレスを明かすことなくiMesh間を自由に転送することができます。

 

 

関連研究(Related Work

Monero1,Bytecoin2及びZcoin3

匿名性を得るするために、MoneroやByteCoinはCryptoNote [13] で言及されているリング署名を利用しています。リング署名は目新しい(公開鍵暗号のような)一方向性関数を使う署名を信頼していますが、残念なことにこの特徴は他のハッシュベース署名方法では見つけられません。Zcoinはzk-SNARKsと呼ばれるゼロ知識非対話証明(zero-knowledge non-interactive proof)を使用していますが、zk-SNARKsはペアリングベースの暗号を使っているため、量子コンピュータ耐性がありません。

CoinJoin5

匿名性を得るための他の潜在的な選択肢として、CoinJoinか(CoinShuffleのような)その変異を使うこともあります。しかしながら、CoinJoinは同時に送金するつもりの積極的な参加者の存在を必要とします。Aidos Kuneenのユーザーベースがまだ小さい初期段階に採用すると、マイナス面が表に出てしまいます。

IOTA6

IOTAはDAGベースで手数料がかからず、IoTに重点的に取り組む暗号通貨です。

IOTAはバイナリ(binary, 訳注:二進法)ベースの署名の代わりにトライナリ(ternary, 訳注:三進法)ベースの署名を使用する点が特徴的です。これは、トライナリの方がバイナリよりも計算効率が良いためです。Aidos Kuneenでは、(SIMDやSHA拡張セットのような)既存のCPU機能を完全に利用するために既存のバイナリベースの署名を使用することにしました。こうしたのは、現世代のデジタルプロセッサーは我々の要件を満たすにはすでに十分に速く効率的だと考えているからです。いくつかのIoT用のプロセッサーはすでにARMプロセッサーのようにSHA-2ベースのハッシュ処理のための専用回路を含んでいます。また、少なくとも短期から中期的にバイナリベースのシステムは消費者向けハードウェアでまだ主流であると考えています。

IOTAのホワイトペーパーに概要が紹介されているようにIOTAの承認プロセスは参照トランザクション数だけを数えています。DAG上で末端トランザクション総計が増えるにつれて(それは普通に起きる状況ですが)、参照(子孫)トランザクションが参照するこれらの末端トランザクションの割合が減ることに気づきます。つまり、攻撃者は彼らの悪意のあるトランザクション群をネットワークよりも潜在的に速く成長させられます。この対策として、私たちは文献 [9] で言及されているSPECTREベースの確認手順を紹介します。SPECTREではトランザクションの承認数は、参照トランザクション数だけでなく、そのトランザクションに投票した他のトランザクションの数も含みます。したがって、末端トランザクションが分岐するとしても、攻撃者は悪意のあるトランザクションを成長させることは難しくなります。

SPECTREの投票プロセスで、私たちはより速い承認のため、より速いDAGの収束が必要となります。IOTAチームに示されたホワイトペーパーでは、DAGの収束動作をはっきりと明らかにしませんが、むしろ’末端トランザクションの総数が安定したままだと期待する’と単純に記述しています。第9章ではDAGの収束を確実にするためにiMeshでの末端トランザクションの振る舞いをさらにシミュレーションします。

 

 

署名方法(Signature Scheme)

前述の通り、Aidos KuneenはIETF[2]のRFCドラフトに記載のXMSSを署名アルゴリズムに採用します。XMSSはXMSSはヴィンターニッツ・ワンタイム署名(WOTS+: Winternitz One Time Signature)を元にしています。WOTS+は一回だけの使用のために作られたハッシュベースの署名方法です。XMSSはWOTS+を頼りにして、一つのカギを複数回の署名に使えるようにするメカニズムです。

WOTS+

図1:WOTS+公開鍵の生成

図1は公開鍵の生成方法を表しています。公開鍵を作るためには、まず67個の32バイト長(256bit)のランダムバイナリデータを秘密鍵Privj, j = 1...67とします。そして、それぞれの32バイト長のバイナリデータPrivjはSHA256で合計15回ハッシュ化します。ハッシュ化を施す前に、PRF(擬似乱数関数)より生成された値とランダムバイナリデータの排他論理和(XOR)を取ります。この処理は、セキュリティレベルはそのままに署名サイズを削減するために採用しています。これにより67個の32バイト長バイナリデータである、公開鍵Pubj, j = 1...67ができます。

 

図2:WOTS+秘密鍵による署名生成

図2はメッセージの署名方法を示しています。署名生成については、まず最初にメッセージを256bitで一度ハッシュ化し、ハッシュ化されたメッセージの12bitチェックサムを算出します。すると、ハッシュ化されたメッセージとチェックサムから67個の4bitバイナリ文字列Ni,i = 1...67を取得できます。次に、秘密鍵の値Privjは公開鍵生成時に利用した物と同じ乱数値を使って排他論理和(XOR)を取りながらNn回ハッシュ化されます。すると、署名Sigj, j = 1...67が作成されます。

このチェックサムは悪意のあるメッセージからの攻撃を守るために使用されます。例えば、チェックサムが無くて、攻撃者が000…0(Ni=0,i=1...64)のハッシュを持つメッセージをつくったとき、署名が秘密鍵と一致してしまい、これにより攻撃者は秘密鍵を知ることができてしまいます。

 

図3:WOTS+検証

図3は署名の検証方法を示しています。署名の確認には、署名生成と同じ手順でメッセージからNiを計算します。そして、署名Sigjは(15 − Ni)回ハッシュ化を繰り返し、公開鍵生成時に使用した乱数で排他論理和を取って、Pub ′j(j = 1...67)を得ます。そして、Pub ′jが公開鍵Pubjと一致するかどうかを確認します。

 

XMSS

図4:XMSSの公開鍵生成

図4は、XMSSの公開鍵の生成方法を表しています。簡単に言うと、XMSSは、全ての公開鍵を集め1つの鍵にする、マークル木と呼ばれる木構造を構築したものです。したがって、一つの公開鍵を何回も使用することができます。

まず、2h個のWOTS+秘密鍵Privijと対応するWOTS+公開鍵Pubij(j = 1...67)を作る必要があります(hはマークル木の高さ)。このとき、2h個の’ltree’が生成されます。i個めのltree( i = 1...2h)はWOTS+公開鍵Pubijから作られます。WOTS+公開鍵Pubijをハッシュ化することでi個めのltreeのルートハッシュを受け取ります。i個めのltreeのルートハッシュはi個めのマークル木の葉になります。この操作をマークル木のすべての残りの葉を満たすまで2h回繰り返します。最終的にマークル木(ltreeのルート)の葉を互いにハッシュ化することにより、マークル木のルートハッシュが計算されます。このルートハッシュがXMSS公開鍵となります。

署名生成については、以前に使用されていない秘密鍵と対応する公開鍵を選び、WOTS+署名を計算します。XMSS署名は、WOTS+署名に「認証パス」(auth path)がついたものです。認証パスは、マークル木のルートハッシュ(すなわちXMSS公開鍵)を計算する為の追加バイナリデータです。

 

図5:XMSS用の認証パス

例えば、図5において3番の秘密鍵を署名に使用するものとします。この場合、検証者は署名から3番のノードが計算できます。しかしながら、12番のノードを特定する為にはまず4番のノードを特定する必要があります。同様にノード31のルートハッシュ(すなわちXMSS公開鍵)を特定するために署名者は認証パスに含まれるノード11と22も必要とします。このようにして、検証時には検証者はWOTS+署名と認証パスに沿ったノード値を所有する必要があります。こうして、検証者はマークル木のルートハッシュを計算することで、ルートハッシュがXMSS公開鍵と一致するかどうかを確認します。

 

付け加えておくと以下の特徴があります。

・署名者はどの秘密鍵が使用済みを記録する必要がある。これを実現するために、私たちは最小の保存コストで効率的なトラバーサルを提供するために対数マークルトラバーサル方式を使用する。

・公開鍵は、32バイトの擬似乱数のシードと32バイトのマークル木のルートハッシュから構成される。これまで説明した疑似乱数は全て、この32バイトの疑似乱数シードを元に生成される。公開鍵サイズが32バイトになるように署名の一部としてシードを含めます。

・署名鍵サイズはおよそ3キロバイトです。

・SHA256ハッシュは強い原像計算困難性を与えます(すなわち攻撃者はハッシュの出力値から入力値を推測できません)。これは仮に量子コンピューターであっても、公開鍵から秘密鍵を暴くことは難しい。

 

また、もしh(マークル木の階層数)を増やすと、公開鍵をさらに何回も使用できる様になります(しかし、これを行うと、最初の公開鍵の生成時に時間がかかるようになります)。

 

表1が示すようにAidos Kuneenでは、3種類のマークル木を用意しています。

決済ごとにアドレスを変えたり、同じアドレスで1000回もコインを送らないような一般ユーザは、公開鍵の生成には計算量の少ない階層数10を使用します。一つの公開鍵で何度もコインを送るような企業や商店は、高さ16や20を使用します。

ここで留意すべき点は、[2] で言及されているXMSSMTは全ての公開鍵を同時に作る必要はないが、XMSSと比べると署名データのサイズが約40KBと大きくなるので利用できないという事です。

 

 

iMesh

SPECTRE

コインの送信者がトランザクションを送るとき、そのトランザクションには他者が以前に送ったトランザクションを含みます。図6はiMeshと私たちが呼ぶトランザクションのDAG構造です。iMeshでは、送信者がDAGの末端トランザクション(現在どのトランザクションにも参照されていないトランザクション)と、親トランザクションが有効かどうかを確認し、有効なものを選びます。最終的に、送信者は有効だと確認されたトランザクションを送信者のトランザクションに含めます。

図6: iMesh

ビットコインなどブロックチェーンベースの暗号通貨に利用されるブロックは1つ前のブロックだけを参照しています。しかし、DAG構造は1つのトランザクションでたくさんのトランザクションを参照します。ブロックチェーンではチェーンは直線状に成長(一定時間ごとに1ブロック)していきますが、対してDAGではトランザクションが連結する性質を持っているので全方向に同時に成長できます。すなわち、DAGはブロックチェーンよりスケーラブルとなりうるわけです。

しかし、トランザクション間で不整合が生じた際、DAGの連結する性質の欠点が現れます。例えば、アドレスAに10枚のコインがあり、AがBに10枚のコインを送信するトランザクションをT1、AがCに10枚送信するもう一つのトランザクションをT2とします。うっかり同じコインを同時に支払おうとしてしまうと(二重支払いという)、2つの衝突したトランザクションがAにできます。ブロックチェーンベースのシステムの場合、片方(例えばT1)が一度ブロックに保存されると、もう一つ(例えばT2)は決してブロックに保存されることはないでしょう。一方DAGにおいては、衝突したトランザクション(図6に赤く色付けした部分)のどちらが有効か決めることは難しいです。この問題の解決のため、私たちは’SPECTRE’ [9] の投票の仕組みを利用します。

 

図7: 簡易なDAG上における投票の手順の例

SPECTREでは、それぞれの衝突したトランザクションに対して、それに投票したトランザクションを数えます。図7に投票の手順を示します。この図ではトランザクションXとYが不整合を起こしています。トランザクションXとトランザクション6~8は、自身の過去履歴にYではなくXだけを持つためXに投票します。同様に、トランザクションYとトランザクション9~11はYに投票します。トランザクション12はトランザクション10, 11, 12を含まないDAG上の多数派がどちらかによって投票を行います。

トランザクション1~5は、後続トランザクションにおいてYの投票者よりXの投票者の方が多いことからXに投票します。結果としてXの投票者がYの投票者より多くなることから、Xが正当だと判断され、Yが排除されるのです。

SPECTREにおいて、どのように投票によって決定されるかを解説します。

  1. 親としてトランザクションXだけを持つトランザクションはXに投票します(トランザクション6~8→X、9~11→Y)。

正直なノードは新しいトランザクションを生成し続けて、それが次に正直なトランザクションに投票するので、非正直な参加者により隠れて投票を保留されるトランザクションよりも正直なトランザクションが投票を得ます。

  1. 親としてXとYの両方を持つトランザクション(トランザクション12)は、投票者の多い方に投票します。新しいトランザクションが投票する事で前の決定に従い且つその投票を強化する事で、多数派を増幅させることを保証します。
  2. xもyも親として持たないトランザクションは、投票者の多数いる方に投票します。

このルールにより、Xの親の投票(トランザクション1~4)が、Xの票数を拡大させられます。これは万一Yが長い時間隠れていたときのためです。これは、プレマイン攻撃方法(すなわち、攻撃者が大きなトランザクションの塊(block)をネットワークから隠して作っておく方法)への対抗手段となります。正直なトランザクションがより多くの祖先トランザクションをもつ傾向にあるため、正直なトランザクションはルール1・2によりさらに投票を受けるはずです。

注釈:[9]で立証されたようにSPECTREは33%ではなく50%の演算力攻撃に耐えられます。

さらに、iMeshの受信者は送金前に、ビットコインよりも十分な数の他のトランザクションによって確認されるのを待つ必要があります。文献 [9] において新しいトランザクションが確認されるまで、どれくらいの時間(コインの)受信者が待つことになりそうか言及されています。もし私達がビットコインネットワークで支払いを受けるまでに5確認まで待つこととしましょう。ビットコインネットワーク内に攻撃者がハッシュパワーを30%持つと仮定すると、攻撃が成功する可能性は17.8%[1]です。iMeshでSPECTREの投票スキームを採用すると同様の場合、17.8%の攻撃可能性を得るには約130個の参照トランザクションが必要となります。iMeshネットワークが成長し、トランザクション頻度が増えると、トランザクションあたりの確認待ち時間は減るでしょう(すなわち、ネットワークが成長するにつれて、それは早くなります)。反対にいうと、Aidos Kuneenネットワークの初期段階においては、長い時間待つ必要があります。ネットワークのハッシュパワーも極めて小さくなりがちであり、攻撃者が試しに悪用するのに良い条件となります。この潜在的な攻撃を防ぐために、iMeshが成長するまで信頼されるフルノード間でトランザクションを確認する’AKConsensus’(次節で示します)という仕組みを取り入れます。

SPECTREでは、送信者は可能な限り多くのトランザクションを参照する意義があります。なぜなら、トランザクションの承認数は「そのトランザクションが参照しているトランザクション数」と「そのトランザクションが将来的に別のトランザクションにより参照される数」に依存するからです。つまり、より多くの過去トランザクションを参照すれば、より早くトランザクションが承認され、受信者に確実にコインを届けることができるのです。言い換えれば、トランザクションの参照数が少ない場合は承認に時間がかかるので受信者に支払いを拒否されるかもしれません。

また、iMeshにたくさんの末端トランザクションがあるとき、新しいトランザクションに参照される末端トランザクションの可能性は低くなることを述べておかなければなりません。そのため、私達はどれくらいの個数のトランザクションが1つのトランザクションから参照されるべきかを考慮する必要があります。この問題については、9章で紹介します。

 

 

AKConsensus

前節に記述のとおり、我々はiMeshの初期段階では十分なリソースのある攻撃者が全ネットワークのハッシュパワーの多数を現実的に支配できると推測します。このため、私たちはネットワークが成長する初期段階にはSPECTREコンセンサスメカニズムを完全には信頼できません。我々はSPECTREに引き継ぐ時間までトランザクションを承認するために、[18]に詳述される適度に信頼されるモデルのある「リップルプロトコルコンセンサスアルゴリズム」に基づく連合ビザンチン合意(FBA)を使用する一時的なシステム、「AKコンセンサス(AKConsensus)」を導入いたします。

リップルプロトコル内で、全トランザクションの承認を確定するためにFBAプロセスが使用されます。AKコンセンサスという似たプロセスをAidos Kuneenに採用します。しかしながら、ADKではリップルとは非常に異なるようにプロセスを実行します。AKコンセンサスが準備できると、信頼(された)ノードのグループがiMesh内からランダムに選択したトランザクションを周期的に見直します。信頼ノードのこのグループがトランザクションの承認で合意に達すると、そのトランザクションは「ステートメント」となり、ネットワーク内でマイルストーンの役割を果たします。

 

コンセンサスのプロセスは以下の通りです。

1.各フルノードはその信頼(された)リスト内で信頼ノードのアドレスを決めます。

2.フルノードの1つは見直しするトランザクションを選択し、その信頼リスト内で信頼ノードへそれを流します。このトランザクションは現在、「候補ステートメント」とします。

3.各信頼ノードはTの初期値を50%とします。

4.各信頼ノードは、候補ステートメントの正当性を部分的な履歴に基づいて見直します。

5.もし信頼ノードが候補ステートメントを正当だと判断したら、参照されたフルノードに「Yes」を投票します。もし、候補ステートメントを不正だと判断したら後で廃棄します。

6.もし、フルノードが一定期間内に信頼リスト上のノードから最低T%の「Yes」投票を受けなかったら、候補ステートメントは廃棄されます。

7.各信頼ノードは T = T + 10%へ増やします。

8.5の段階を繰り返します。

9.候補ステートメントが正当であるのでステートメントにするために、最後のラウンドではフルノードの信頼ノードの合意で最低T=80%が必要です。

注釈:ステートメントとして受け入れられるために、候補ステートメントは妥当なトランザクション構造を持ち、iMesh内で存在する必要があります。

 

図8:ステートメントとトランザクションの最終確認

 

図8は他のトランザクションにとってステートメントがマイルストーンとしてどのように動くかを説明します。フルノードはステートメントを「完全に正しい」と判断し、対立するトランザクションは各フルノードで廃棄されます。ステートメントに参照されるトランザクションは最終確認されたトランザクションとなります。

図8で数字がついたトランザクションはどのようにそれを参照するステートメントによって最終確認されるかを示します。例えば、No.2のトランザクションはステートメントNo.2によって最終確認されます。

 

対立するトランザクションの正当性を決めるために、AKコンセンサスで採用するルールは次の通りです。

・最も若いステートメントによって最終確認されるトランザクションは正しいと判断され、他のものは不正だと判断されます。

・もし対立するトランザクションが同じステートメントで最終決定されるなら、より古いタイムスタンプを持つものが正しいと判断されます。

・もし両方のトランザクションが同じタイムスタンプを持つなら、より小さなハッシュ値をもつものが正しいと判断されます。

 

AKコンセンサスは候補ステートメントを受けるために信頼ノード間で最低80%の合意を必要とします。その延長線上で考えると、不正な候補ステートメントを排除するために20%かそれ以上を必要とします。

AKコンセンサスの導入は完全に非中央集権の暗号通貨というADKの究極なビジョンと矛盾します。AKコンセンサスは、前に概要を記述した理由により、それ自体で攻撃に抵抗できるところへネットワークが成長するまで「必要悪」として受け入れます。さらに、ADKはユーザーベースで完全に手数料不要なプロダクトを提供できると強く信じています。AKコンセンサスの存在により、代わりとなる、初期のネットワーク保護のための「奨励される」メカニズムに頼る必要なく、当初からのこのビジョンを実現できるようになります。

 

 

Proof of Work

トランザクションを送信する際、コインの送信者は、ビットコインでマイナーが行うようにProof of Work(PoW)をする必要があります。スパムトランザクションによるDDos攻撃と二重支払い攻撃からiMeshを守るために、送金前にPoWが必要です。また、ネットワークの全参加者間でトランザクション承認の計算作業負荷を分散させるためにPoWを使用しています。一握りのマスターノードによる処理能力不足によりネットワークが制限されないようにし、その代わりに必要なだけ完全に自由に調整するためだ。PoW処理中、各トランザクションは「ノンス」という32bitの整数値の長さLを割り当てられます。このノンス値は、ブロックのハッシュが先頭に続く0を含むように設定されていて、サイクルLの一連の「カッコウグラフ」を作ります(詳細は以下で詳述)。先頭に続く0は、PoWにかかる時間を決め、平均5-10分かかるように調整しています。

PoWのためにAidos Kuneenは[14]で詳述するカッコウサイクルを採用します。カッコウサイクルは「カッコウハッシュテーブル」への鍵の挿入により起きます。カッコウハッシュテ-ブルはランダムな二部グラフのサイクル形成を自然に導くます。カッコウハッシュテーブルは2つの同一のテーブルで構成され、各テーブルは鍵をテーブル位置へ置くユニークなハッシュ関数を持ちます。これにより各鍵は2つの潜在的な位置が与えられます。新しい鍵が到着すると、それのテーブル上の位置がまず決まります。もし起こりうる両方の位置が現在、既存の鍵で占有されていたら、1つは抜き出されて、代わりの位置に挿入されます(もう一つの鍵を動かすかもしれません)。このプロセスは空いている位置が明らかになるか、所定の反復数まで続いて繰り返されます。このプロセスはカッコウグラフというサイクルの形成を導きます。カッコウグラフは各位置にノードがあり、挿入された各鍵のために線がある2部グラフで、鍵が内在できる2つの位置につながっています。

 

図9:カッコウグラフ

図9の最初の図形はN=8+8ノード、(2,15)、(4,9)、(8,5)、(4,15)、(12,11)、(10,5)、(4,13)の線が加えられた、方向を持ったカッコウグラフです。8番目の線(10,11)を加えるために、10→5→8→と11→12のコースを行き、異なるルート8と12を見つけます。後者のルートは短いので、12→11へルートを逆にすると、新しい線(11→10)を加えられます。その結果として真ん中の図形になります。9番目の線(10,13)を加えるために、10からより短いルートを見つけます。そして通路を逆にして新しい線(10→13)を加えます。すると右の図形になります。10番目の線(8,9)を加えるとき、8→5→10→13→4→15→2のルートと等しいルートのある9→4→15→2のルートを見つけます。この場合、1+(2つのルートが入るノードへのルートの長さの合計)でサイクルの長さを計算できます。その図形では、ルートはノード4へ入り、サイクルの長さは1+4+1=6と計算されます。

 

iMeshへのPoW機能としてカッコウサイクルを選んだのは次の理由です。

・私たちはビットコインと比べて非常に高いトランザクション量を見込んでいます。これはビットコインと違い、ADKの手数料不要という性質、すなわち頻繁な少額送金に対して経済的な阻害要因が無くなるからです。ADKには非常に早い承認方法が必要となります。

・クリプトナイトのような他の代表的なPoWアルゴリズムや一般にきわめてリソース消費的なスクリプトと違い、カッコウサイクルを使うと、フルノードはノンスの有効性をずっと速く確認できます。

・ブロック自体だけでPoWが実行されるビットコインと違い、ADKではPoWは個々のトランザクションごとにPoWする必要があります。ブロックと比べて非常に多く各トランザクションがあるため、ADKはPoW承認をするためにさらに能力が必要です。このため、非常に効率的な承認手段が必須であり、そのためにカッコウサイクルを採用しました。

・ネットワーク全体で攻撃者が頻繁なトランザクションを伝えられないように、ASICsやFPGAsのような専門的なハードウェアにより有利となるべきではありません。PoW時間は主にメモリアクセス速度が最重要なため、専門的な処理ハードウェアが基本的に無力になります。

 

PoWに次のカッコウサイクルのパラメーターを用いる予定です。

・サイクル長 L = 20 (トランザクションへのサイズ効果を最小化するため)

・ノード数 N = 225 (メモリ使用量128MBあたりにするため)

・容易さ N/M = 100%,(M:線数) (線トリミングにより最適化を防ぐため)

 

 

Co-operative Proof of Work

演算力が一般的に極めて低いIoT機器のために、coPoWという新しい協調型Proof of Workを導入します。coPoWを使うことによって、ネットワークが多くの未承認トランザクションを集めて、一つのより大きなトランザクション’Batch’にまとめることができます。これによって、Batch内の個々のトランザクション送信者は単独でするよりも、効果的に演算力をプールさせ、一単位としてバッチの承認ができるようになります。ビットコインのマイニングプールの非中央集権版のようにcoPoWは効果的に働き、低い演算力の多くの機器がまるで一つの強力な演算力を持つ機器のように、ネットワークで直接的に関わることができます。

 

coPoWは以下のように働きます。

  • coPowに参加したい送信者は、フルノードを介してネットワークに依頼を流します。
  • 参加したい他の者やcoPoWをすでにしている者はその依頼に反応します。
  • 送信者はcoPoWグループに参加します。
  • もしグループが作られていなければ、リーダーの選出が行われ、もしグループがすでに作られていれば、新しい機器が既存のリーダーが誰であるかの情報を取得します。
  • 送信者はリーダーにトランザクションを送り、Batchの他の参加者のトランザクションと混ぜ合わせられます。
  • 全送信者がBatchでPoWを開始します。
  • 送信者はリーダーに’PoW’の結果(難易度を調整する‘ターゲット値’の要求を満たすもの)を周期的に送ります。
  • 送信者はリーダーを介して他のパーティーからのPoWの結果を周期的に取得します。
  • もしパーティーの誰かが間違った結果を送信するとグループから排除されます。
  • もしパーティーの誰かが決められた期間に結果を送信できなかったら、リーダーはそのパーティーを排除し、残ったパーティー全てに再実施するよう命令を出します。
  • パーティーの1つが’最後のハッシュ’の解決に成功するまでプロセスは続き、PoWが完了後、そのグループは解散されます。

 

coPoWグループの参加パーティーはグループに活動的に参加していることを証明するため、リーダーにPoWの結果を周期的に送らなければなりません。これにより、グループに参加するが活動的には貢献しようとしないパーティーのタダ乗りを防ぐためです。(難易度を調整する)ターゲット値は最終のハッシュ値よりも簡単なように設定されています。これは限定的な演算力を持つ機器で必要時間内にターゲット値を満たせるようにするのに重要です。ターゲット値自体は変えられます。例えば、ターゲット値=最終のターゲット×2-5が低い能力のIoT機器のグループに採用されます。ターゲット値=最終ターゲット×2-2は一般的なデスクトップPCに採用されます。

匿名性を加えるために、coPoWの参加者はTorネットワークを参加者間やグループ間のコミュニケーションに使用することができます。

 

 

AKShuffle

匿名性を強めるために、私たちはAKShuffleという技術を使います。 AKShuffleでは、匿名でコインを送信するためにゼロ知識非対話型(ZKNI)証明を利用しています。 ZKNIによって、誰でも自分の秘密鍵を明らかにすることなく、いくつかの関数を満たすことで値を証明することができます。 例えば、アリスが暗号化関数fk(x)に対してxを入力し、kは暗号鍵とします。入力xでyを出力、すなわち fk(x)の出力値yをBobと共有します。ボブはアリスが実際にfk(x)がyを返すような鍵kを持っていることを知りたいとします。しかし、アリスは彼女のkを明らかにしたくありません。ZKNIを使うことによって、暗号鍵k自体を実際に見せることなく、彼女が本当に持っていることをボブに証明することができます。

私たちはZKNIの実装として [8] で言及されたZKBoo(ZKB ++)を利用します。ZKBooは、量子コンピュータ耐性(筆者注:量子計算機に対して耐性がある暗号方式)なハッシュと暗号化関数(AES)のみを使用します。

 

図10:AKshuffleの仕組み

図10は、AKShuffleの仕組みを次のように示しています:

トークンをシャッフルしたい人は、AKShuffleアドレスに送るだけです。シャッフルアドレスは暗号化関数fkmy(xmy)の出力です。kmyは秘密鍵であり、xmyは彼の公開入力です。もしユーザーがシャッフルされたトークンを出金したいなら、彼の通常のアドレスPKmy2(彼のXMSS公開鍵)に送る1つのトランザクションを作成するだけです。そのトランザクションは入力アドレスとして他人のAKShuffleアドレスfk1(x1) , fk2(x2) … fkn(xn)と彼のAKShuffleアドレスfkmy(xmy)を含みます。これにより、どのアドレスが実際に出金に利用されたか、外部からは分からないということです。所有権を証明するために、ユーザーは暗号鍵kmyを知っていることを証明することでゼロ知識非対話証明を満たします。これによってトランザクションに含まれるAKShuffleアドレスのうち一つが、fkmy(xmy)の出力と等しくなるようなkmyを知っていることを証明します。そのトランザクションはまた、Shuffleアドレスの再使用を防ぐためにユーザーの公開入力xmyを含みます。ユーザーがもともと入金した全量を出金することが求められることに注意してください。匿名性の維持のためにシステムはシャッフルアドレスの再使用を厳しく禁止しているため、一部のみの出金は許されていません。

注釈:AKShuffle用のトランザクションと通常決済のものは完全に異なります。AKShuffle(ZKBoo)はトークンのシャッフルだけのために使われます。そのため、他のユーザーに直接トークンを送るためにAKShuffleは使えません。これはZKBooの署名サイズが極めて大きいためです(入力数が5の場合は約500kBytesにもなります)。

 

 

ネットワーク

図11:Aidos Kuneenにおけるフルノードとクライアント(ウォレット)

Aidos KuneenのネットワークはP2P形式で送受信する一連のフルノードで構成されています。クライアントはAPIを通してこれらのフルノードもしくは自らのフルノードに直で接続できます。クライアントはネットワークにトランザクションを流すためにAPIリクエストを送信できます(これは通常はウォレットのアプリケーションにより自動的に行われます)。フルノード間でのトランザクションの送受信には、パケットサイズを削減するための効率的なシリアライゼーション(msgpack)を使用しています。

公開されたフルノードとクライアントとの間の接続には匿名化のためにTorネットワークも使用します。クライアントのトランザクションでIPアドレス等の機密情報を受信することがあるのでこれは不可欠です。

フルノード間の通信についてはTorは使用しません。これはTorネットワークを通したトラフィックはノード間の通信を遅くするためで、フルノード間の効率性がAidos Kuneenの全ネットワークのスピードに重要だからです。また、ノード間では匿名で通信する必要はほとんどありません。初期のクライアント-ノード接続がTorで守られていなかったとしても、初期受信ノードは他のトランザクションへ送信するときにクライアントの機密情報を送信しないためです。

残念ながらTorは耐量子コンピュータではありません。しかし、多数の参加者がいて確立され信頼できるネットワークという利点があります。少なくとも短期的にはTorネットワークによる強力な匿名性がAidos Kuneenにうまく合うと信じています。私たちは耐量子コンピュータ技術を与える他の潜在的な手法を調査し続けます。

 

表2はAidos Kuneenネットワークの基本的なパケットのコマンドを示します。

 

表2: 標準パケットコマンド

 

Leaves in iMesh

4章で述べたように、承認の速度はiMeshの末端(leaves)の数に依存します。これは末端トランザクションが増えると、新しいトランザクションがある1つの末端トランザクションを参照する確率が低くなるためです。

しかし、図12に示すように、いくつかのシナリオにおいては末端トランザクションが増えてしまう可能性があります。

図12:iMesh内の末端トランザクション

 

一つ目のシナリオは、攻撃者が意図的に非末端トランザクション(non-leaves)を参照してiMeshを遅くしようとする場合です。これは追加の参照されない末端トランザクションをiMeshに加えす効果があり、ネットワーク全体の効率性を下げます。

この状況に対抗するため、私たちは参照トランザクション数Nref≧3に設定し、攻撃者が末端トランザクションの数を見境なく増やすのを妨げられます。もし、攻撃者がトランザクションあたりに1つの末端トランザクションだけを追加できることとこれを組み合わせると、(攻撃者はネットワークの演算力の50%を超えてコントロールできない条件で)正直なトランザクションは攻撃者の新しい末端トランザクションを急速に参照することに気づきます。こうしてiMeshとそれらを統合し、非参照の末端トランザクションの管理できない成長を妨げることになります。

シナリオ1と似た状況で、攻撃者は多くの非常に低い(ゼロさえある)トランザクションを彼自体に流すこと、または短時間で多くの末端トランザクションの作成に加担するによってネットワークにスパムをばらまこうとするかもしれない。こうすると、承認時間が極めて長くなる。これは送信される値に関わらず、各トランザクションへPoWを要求することで簡単に防ぐことができる。

第3番目のシナリオでは、あるトランザクションT1がiMeshに入る際、もう一つT2が承認されようとする途中(PoW中)であり、iMeshにはまだ現れていない場合です。T1とT2は同じトランザクションを参照しているかもしれません。このシナリオは悪意があるとは限りませんが、実際、通常のネットワークで極めて頻繁に起きると予想されます。

この問題を解決するために、Nleavesを減らすため(iMeshを収束するため)に私たちはNrefを増やすことができます。しかしながら、これはトランザクションサイズの増加という望まない効果も持っています。そのため、私たちは小さな署名サイズを求めつつ、iMeshを収束するために最適なNref値を決める必要があります。

この目的のため、私たちはiMeshの振る舞いのシミュレーションを提示します。

まず、受信トランザクションのプロセスは、ポアソン過程(Poisson Flow)によってモデル化されると仮定しています。そしてトランザクションのサイズTxは(定数+32×Nref)Bytesで計算でき、PoW完了にかかる時間は指数分布によってモデル化することができます。そのため、λinをポアソン過程のレート、1/λpowをとPoW完了にかかる時間(指数分布の期待値)とします。ユーザートランザクションをλinのレートで生成し、トランザクションを参照するレートを含めて平均して1/λpowでPoWを完了します。

PoWを行っている間にも他のユーザーもまたトランザクションを生成し、PoW中の同じトランザクションを参照するかもしれません。時刻tにおける末端トランザクション数は、時刻t − t ′の(すなわち、時間の経過に伴い変動する)末端トランザクション数に依存するので、末端の数を表す式を解くことは困難です。したがって、我々は末端トランザクション数について振る舞いをシミュレートすることが必要です。

Algorithm1は、iMeshにおける末端トランザクション数をシミュレートするために使ったアルゴリズムを示しています。1/λpow = 10minutes (平均10分でPoWが完了することを意味する)として、1つのトランザクション内の参照トランザクション数をNref= 2, 4, 8, 16, 32とします。そして次のトランザクションλinをシミュレートします。

  1. λin=毎分 1トランザクション (1tx/min)※ユーザーベースが小さい時のiMesh初期段階のモデル
  2. λin=毎秒 1トランザクション (1tx/sec)
  3. λin=毎秒 5トランザクション (5tx/sec)※2017年5月のBitcoinネットワークの最大値
  4. λin=毎秒10トランザクション (10tx/sec)

付録の図13~17にシミュレーション結果を示します。λin = 1 tx/minに対するNref = 8, 16, 32の結果についてはNref = 4の結果と実質的に同じなため示しません。

これらの結果から、末端トランザクション数はNrefの数に比例して減少します。

λin = 1 tx/min かつNref = 2の場合でもDAGを収束させるには不十分です(Nleaves = 3~26)。Nref ≧ 4であればより良いでしょう(Nleaves = 1~18)。他のλin についてはNref = 2が他のNref よりも明らかに悪いです。例えば、λin = 5 TPSで、Nref = 2ではNleaves = 3800、Nref = 8ではNleaves = 500です。それゆえ、もしビットコインと同じスピードでiMeshにトランザクションが入ってくると仮定するのであれば、Nref = 2は使うべきではありません。

トランザクションのサイズTxは線形挙動を示し、Nref値が増えると倍になります。純粋にトランザクションサイズの観点から、最小のNref値を探すべきです。

私たちはまた、前に言及した各ケースにおいて、ある一つのトランザクションに対し、それを直接的・間接的に参照するトランザクション数Ndecendantがどのように増えるかについてもシュミレートします。 付録Bの図18-21に結果を示します。

これらの図では、X軸はiMeshが安定した後にiMeshに追加されたtransactionの数を示し、Y軸はあるランダムなトランザクションに対するトランザクション(子トランザクション)の参照数Ndecendantを示します。Ndecendantが理想的な速度で成長すればグラフは対角線となります。λin =1 tx/minの場合、任意のNrefグラフはほぼ対角線になります。しかし、λinが増加するとNdecendantは少なくなります。例えばλin = 5TPSでNdecendantは、Nref = 2で25000トランザクション後(つまり平均25000×0.2秒=平均1.39 時 間後)でも対角線状には増えません。Nref = 8では4000トランザクション後(つまり平均4000*0.2秒=平均13.3分後)に直線状に増加し始めます。

そのため、ある1つのトランザクションに対する参照数Nrefを変数とすることが最善だと考えます。初期設定としてNrefを8にしました。iMeshがBitcoinの最大TPS(秒あたりのトランザクション数)である毎秒λin = 5tx/secに成長したとしても、Nref = 8であればiMeshは#leaves = 500付近でうまく収束できるからです。さらに、Nref = 8 ≧ 3もあれば攻撃者が末端トランザクションを増やそうとするのを防ぐことが期待できます。

iMeshが大きくなれば最適なネットワークパフォーマンスを維持するためにNrefの値を見直すことになります。

 

 

10章 今後の計画

今後、Aidos Kuneenネットワークに以下の計画を統合予定です。

  • スケーラビリティーを上げるためにノード間でトランザクションを分散する。
  • Torのような匿名性、耐量子コンピュータ技術、分散ピア発見のためにKademliaベースの仕組みを実装する。
  • トランザクションサイズを削減するためにより洗練されたゼロ知識非対話証明(ZKNI)アルゴリズムを実装する。

 

 

11章 結論

私たちは新しい暗号通貨"Aidos Kuneen"を提示しました。

Aidos Kuneenは全てのトランザクションが直接的に互いを参照し合うDAG(Directed Acyclic Graph:有向非巡回グラフ)構造をもつiMeshを採用しています。

二重決済を防ぐため、全トランザクションから正しいトランザクションを確定するために"SPECTRE"を活用しています。

量子コンピューター耐性としては、署名スキームとしてハッシュベースの署名である"XMSS"を採用しています。

匿名性に対しては、量子コンピュータに向けてゼロ知識証明”ZKBoo(ZKB++)”を使ったAKShuffleを使用します。

IoTに向けてはcoPoWという、低能力の機器がリソースを合わせてグループでPoWを行い合う協調型PoWを採用しました。

最後に、私たちはネットワークの成長に伴うiMeshの末端トランザクション数とネットワークの振る舞いをシミュレーションしました。

 

 

表3:Aidos Kuneenの技術仕様

 

 

参考文献

[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.

[3] Serguei Popov, The tangle, 2017.

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

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

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

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

[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.

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

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

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

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

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

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

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

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

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

 

 

付録A シミュレーション結果-末端トランザクションの数Nleaves

 

 

付録B シミュレーション結果-Ndescendentの成長

 

-ADK

Copyright© いつかは気まま生活 , 2018 All Rights Reserved.