# Mimblewimble と Grin 概論 *この文章を他の言語で読む： [English](../intro.md), [Español](intro_ES.md), [Nederlands](intro_NL.md), [Русский](intro_RU.md), [日本語](intro_JP.md), [Deutsch](intro_DE.md), [Portuguese](intro_PT-BR.md), [Korean](intro_KR.md), [简体中文](intro_ZH-CN.md).* Mimblewimble は、極めてよいスケーラビリティ、プライバシー、そして代替可能性（fungibility）の解決法を提供 するブロックチェーンのフォーマット・プロトコルである。Mimblewimble は、ほとんどすべてのブロックチェーンの 実装に存在する課題を解決する。 Grin は、その Mimblewimble ブロックチェーンを実装する OSS プロジェクトであり、完全なブロックチェーン、 暗号通貨のデプロイメントに必要なギャップを埋めるものである。 Grin プロジェクトの主なゴールと特徴は以下： * デフォルトでプライバシーが保たれていること。これにより、選択的に必要な情報を開示する能力を排除することなく、完全な代替可能性を実現できる。 * ユーザー数を最大限に、トランザクション数を最小限にスケールさせることができるため、 [TODO: enhance translation] 他のブロックチェーンに比べて大きなスペース節約が可能である。 * 強固で証明された暗号技術。 Mimblewimble は、数十年にも渡る攻撃やテストに耐えてきた楕円曲線暗号に のみ依存する。 * デザインがシンプルなため、長年に渡って監査・メンテナンスが容易である。 * コミュニティドリブンであり、ASIC耐性のあるマイニングアルゴリズム（Cuckoo Cycle） を採用しているのでマイニングの非中央集権化を促す。 ## Tongue Tying for Everyone 本ドキュメントは、ブロックチェーンと基礎的な暗号学の理解を前提としている。 それに留意しながら、我々は Mimblewimble の技術的なビルドアップと、それがどのように Grin に 応用されているかの説明を試みる。本ドキュメントが多くの技術に慣れ親しんだ読者にとって理解しやすい ものであることを願う。我々の目的は、読者に Grin について興味をもってもらい、可能な方法で Grin に 貢献していただくことである。 この目的を達成するため、Mimblewimble の実装としての Grin を理解するための主要なコンセプトを いくつか紹介する。まずはじめに、Grin を基礎づける楕円曲線暗号（ECC）のいくつかの関係する性質についての簡単な説明を し、その後、Mimblewimble ブロックチェーンのトランザクションとブロクについてのキーとなる要素について説明する。 ### Tiny Bits of Elliptic Curves まずは楕円曲線暗号の概要から見ていく。Mimblewimble の仕組みを理解するのに必要な分のみ検討し、ECCの複雑な部分を掘り下げすぎないようにする。 より詳細な掘り下げた部分を知りたい読者は、[こちらのリンク](http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/)が助けになるだろう。 楕円曲線を暗号にもちいる目的は、単純に大きな点の集合のためである。これを _C_ と呼ぶことにする。 この集合に属する点は、足し算、引き算、またスカラー倍の演算をすることが可能です。 _k_ を整数としたとき、 スカラー倍の演算をすることで `k*H` を計算することが可能だ。そしてこの計算結果も曲線 _C_ 上の点になる。 _j_ をもう一つの整数としたとき、`(k+j)*H` を計算することもできる。そしてこれは `(k*H + j*H)` の値 と等しい。楕円曲線上の点の足し算とスカラー倍演算はそれぞれ交換法則と結合法則を満たす。即ち： (k+j)*H = k*H + j*H 楕円曲線暗号では、十分に大きな数 _k_ を秘密鍵として選んだ時、 `k*H` が公開鍵とされる。 公開鍵 `k*H` の値を誰かが知ったとしても、それから _k_ を推測することは不可能に近い（ 別の言い方をすると、掛け算は trivial なのに対し、曲線上での「割り算」は極端に難しい）。 上の式 `(k+j)*H = k*H + j*H` を見ると、 _k_, _j_ を共に秘密鍵とした時、秘密鍵同士の和から 得られる公開鍵は、それぞれの秘密鍵から得られる公開鍵の和と等しいことが分かる。Bitcoin では、 HDウォレットがこの原理を大いに利用している。そして Mimblewimble と Grin もこの性質を利用する。 ### Transacting with Mimblewimble トランザクションの構造には Mimblewimble の核となる信条を見ることができる： 強固なプライバシーと機密性の保証だ。 Mimblewimble トランザクションのバリデーションは以下の２つの性質に依る： * **ゼロサムの検証** outputs に -inputs を足した値は常にゼロであること。 これはトランザクションが新たなコインを作っていないことを証明する。 _実際の送金額を露呈することなしに_。 * **秘密鍵の所有** 他のほとんどの暗号通貨と同様に、トランザクションアウトプットの所有は、楕円曲線暗号の 秘密鍵を持っていることによって保証される。しかし、秘密鍵の所有の証明は、直接トランザクションに署名 することで行われるわけではない。 後の章では残高、所有権、おつりと証明について説明するが、ここでこれらの２つの性質がどのように達成されるか が詳述される。 #### 残高 上述した楕円曲線暗号の性質を利用しているので、トランザクションの value を秘匿化することができる。 _v_ を トランザクション input または output の value とし、_H_ を楕円曲線としたとき、 [TODO: 「楕円曲線上の点」では？] トランザクションに直接 _v_ を書き込むのではなく、 `v*H` を代わりに書き込むことができる。これは、ECC演算を用いることで、 トランザクションの outputs の和は inputs の和に等しいことを検証できるからである： v1 + v2 = v3 => v1*H + v2*H = v3*H この性質をトランザクション毎に検証することによって、プロトコルはトランザクションがなにもない空中からお金を作り出していないことを、 実際の value を知ることなく検証できる。しかし、使用できる value の数は有限であり、それらをすべて試すことでトランザクションの value を推測することは可能である。加えて、 v1 とそれから導出できる `v*H` を知っているということは、ブロックチェーン上のすべての value が v1 の output からわかってしまうということを意味する。これらの理由から、２つ目の楕円曲線 _G_ （実際には、 _H_ と同じ 曲線上の他の生成元である）と秘密鍵 _r_ を *目くらまし因子（blinding factor）* として導入することにする。 今、トランザクションの input/output value は次のように表すことができる： r*G + v*H ここで、 * _r_ は blinding factor として用いられる秘密鍵で、 _G_ は楕円曲線暗号の生成元、これらの積 `r*G` は対応する公開鍵である。 * _v_ は input/output value で _H_ は別の生成元である。 楕円曲線暗号の基本的な性質により、_v_, _r_ は共に推測不可能である。 `r*G + v*H` は _Pedersen Commitment_ と呼ばれる。 例として、input 2つ、output 1つのトランザクションを作成したいとしよう。 手数料はここでは無視する。値はそれぞれ： * input value を vi1, vi2 * output value を vo3 とする。これらは以下の等式を満たす： vi1 + vi2 = vo3 それぞれの value に対して blinding factor として秘密鍵を生成し、それぞれの value を対応する Pedersian Commitment で 置き換えると、以下の等式が得られる： (ri1*G + vi1*H) + (ri2*G + vi2*H) = (ro3*G + vo3*H) 結果として以下の等式が成り立つ必要がある： ri1 + ri2 = ro3 これが Mimblewimble の第一の柱である。すなわち、トランザクションを検証するための演算は value を知ることなくして実行可能であるということだ。 最後に、本アイディアは実際には Greg Maxwell の [Confidential Transactions](https://elementsproject.org/features/confidential-transactions/investigation), から派生したものである。 更にこれは Adam Back の Bitcoin に応用されている準同型暗号に関する提案から派生したものである。 #### 所有権 前の章において、秘密鍵を blinding factor として導入することでトランザクションの value を 秘匿化した。Mimblewimble の第二のポイントは、この秘密鍵を活用して value の所有権を証明できる ということです。 Alice があなたに 3 coin を送金し、その額を秘匿化するために、あなたは 28 を blinding factor として選択した（実用では秘密鍵である blinding factor は十分に大きい数であることに注意）。 するとブロックチェーンのどこかに次の output が現れ、あなたによってのみ使用可能である： X = 28*G + 3*H 加算の結果である _X_ は誰からも見ることができる。送金額 3 は Alice とあなただけが知っていて、 28 はあなただけが知っている。 この 3 coin を再び転送するには、プロトコルは 28 の値をどうにかして知っている必要がある。 これがどのような仕組みかを説明するために、送金された同じ 3 coins を Carol に転送したいとしよう。 次のようなシンプルなトランザクションを作成する： Xi => Y ここで、_Xi_ は output _X_ を使用した input で、 _Y_ は Carol の output である。 秘密鍵である 28 の値を知ることなしにこのようなトランザクションを作成し残高を移動させる方法はない。 実際、Carol がこのトランザクションによって残高を移動させるには、彼女は送金された金額（value）と あなたの秘密鍵を知る必要がある。すなわち： Y - Xi = (28*G + 3*H) - (28*G + 3*H) = 0*G + 0*H すべての計算結果がゼロになることをチェックすることで、新しいコインが作られていないことを再確認できる。 待て待て。今、あなたは Carol のアウトプットの秘密鍵を知っている（今回の場合、あなたの残高を移すための秘密鍵と同じものだ） から、あなたは Carol からお金を盗むことができてしまう！ この問題を解決するためには、 Carol は自分で選んだ秘密鍵を用いる。 例えば彼女が 113 を選んだとして、ブロックチェーンに書き込まれるのは： Y - Xi = (113*G + 3*H) - (28*G + 3*H) = 85*G + 0*H こうすると、トランザクションの値は今や合計がゼロにならなくなり、 _excess value_ が _G_ の項として 残る（85）。これはすべての blinding factors の和である。しかし `85*G` は楕円曲線 _C_ 上の有効な 公開鍵であるので、秘密鍵 85 のとき、任意の x, y について `x*G + y*H` が _G_ 上の有効な公開鍵 であるのは `y = 0` の場合のみである。 よって検証に必要なプロトコルは (`Y - Xi`) が _G_ 上の有効な公開鍵であることと、取引している 関係者が全員秘密鍵を知っていることである（Carolのトランザクションの例では 85）。これを実現する 最もシンプルな方法は、 excess value (85) で作成した署名を条件とすることである。そうすると、 以下のことがバリデートできる： * 取引中の関係者が全員秘密鍵を知っていて、 * (transaction outputs) - (transaction inputs) がゼロになること （秘密鍵にマッチする有効な公開鍵のみが署名を検証可能であるため）。 すべてのトランザクションに付属している署名は、マイニング手数料などの他のデータと合わせて、 _transaction kernel_ と呼ばれ、バリデーターにチェックされる。 #### いくつかの細かい点について この章では、お釣りがどのように導入されるか、またすべての値が非負であることの証明となる range proof の要件について議論することで、トランザクションの構成についての詳細を詳しく述べる。これらの両方とも、 Mimblewimble と Grin を理解するために必ず必要というわけではない。したがって、もし急いでいるのならば [まとめ](#まとめ) まで読み飛ばしてもらって構わない。 ##### お釣り Alice から受け取った 3 coins のうち 2 coins を Carol に送金したいとする。 そのためには、残りの 1 coin を自らにお釣りとして送金する。もう一つの秘密鍵（12 とする）を blinding factor として生成しお釣りの output を保護する。Carol は以前の例と同じように 自らの秘密鍵を使用する。 Change output: 12*G + 1*H Carol's output: 113*G + 2*H ブロックチェーンに最終的に残るのは以前の例とよく似ている。 そして今回も署名は excess value を使って作成される。この例では 97 である。 (12*G + 1*H) + (113*G + 2*H) - (28*G + 3*H) = 97*G + 0*H ##### Range Proofs 上記の計算はすべて、トランザクションの value が常に正であるという前提に依存している。 負の金額を導入してしまえば、すべてのトランザクションにおいて新しい資金を作ることが できてしまい極めて重要な問題である。 例えば、input value が 2、output value が 5 のトランザクションを作成できる。 そして -3 は、前の章の定義によると有効なトランザクションである。 もし _x_ が負だとしても対応する `x*H` を他と見分けることはできないので、 これを用意に検知することはできない。 この問題を解決するため、Mimblewimble は（これも Confidential Transaction に由来しているが） range proofs と呼ばれるさらに他の暗号学的概念を利用する。 range proofs とは、その数字を知ること無く その数字が特定の範囲の大きさであることを証明するものである。ここでは range proof について詳細には 記さないが、任意の `r*G + v*H` について _v_ がゼロ以上であること、さらにオーバーフローしないこと を証明できるということだけを知っていれば十分である。 また、上のような例から有効な range proof を作り出すためには、excess value 作り署名するために使われる 113 と 28 の両方の value を知っている必要がある、ということも重要です。この理由と、より詳細な range proofs の説明は [range proof paper](https://eprint.iacr.org/2017/1066.pdf) を参照。 #### まとめ Mimblewimble のトランザクションは以下の要素を持つ： * inputs の組。１つ前の outputs を参照・使用する。 * 以下を含む新しい outputs の組： * value と blinding factor（新しい秘密鍵）を曲線上で掛け算し、足したもの。 r*G + v*H * v が非負であることを示す range proof * 明示的なトランザクション手数料 * excess blinding value（outputs の合計から inputs の合計を引いたもの） を取り、それを秘密鍵として計算することで作成される署名データ。 ### Block と Chain State これまでに、Mimblewimble のトランザクションが、有効なブロックチェーンに 必要な性質を満たす一方で、強い匿名性を提供する方法を説明しました（ i.e. トランザクションは新たなお金を作らない、所有権の証明は秘密鍵によって 行われる）。 Mimblewimble のブロックフォーマットはこれに新たなコンセプトを１つ追加することで導入 される： _cut-through_ である。これを追加することによって、Mimblewimble chain は 以下の特徴を得る： * 極めて良いスケーラビリティ。これは、セキュリティを犠牲にすることなく大量のトランザクションデータ を省略することによって向上する。 * トランザクションデータをミキシングし、除くことによるさらなる匿名性の向上 * とても効率的に新しいノードがネットワークと動機することのできる能力 #### Transaction の集約 トランザクションは以下の要素から成り立つことを思い出そう - * inputs の集合、1つ前の outputs の集合を参照・使用する * 新しい outputs の集合（Pedersen commitments） * transaction kernel。以下の要素から成る * kernel excess （Pedersen commitment to zero） * トランザクション署名（kernel excess を公開鍵として使用） tx は署名され、署名は _transaction kernel_ に含まれる。署名は _kernel excess_ を用いて 生成され、公開鍵はトランザクションの値の合計が 0 になることの証明となる。 (42*G + 1*H) + (99*G + 2*H) - (113*G + 3*H) = 28*G + 0*H この例えは公開鍵は `28*G` となっている。 任意の有効なトランザクションについて、以下が言える（簡単のため手数料は無視する） - sum(outputs) - sum(inputs) = kernel_excess ブロックは単に inputs, outputs, transaction kerbels を集約したものであるということに気がつけば、同じことがブロックに関しても言える。 tx outputs の和から tx inputs の和を引いて、その結果である Pedersen commitment を kernel excesses の和と比較できる - sum(outputs) - sum(inputs) = sum(kernel_excess) 少し単純化して言うならば（ここでも手数料は無視することにする）、Mimblewimble のブロックはトランザクションと同様に扱うことが可能である・ ##### Kernel Offsets 上で説明した Mimblewimble のブロックとトランザクションには、小さな問題がある。ブロックの中の構成要素から、トランザクションを再構成することが可能（ときには容易）であるということだ。これは明らかにプライバシーの観点から良くないことだ。これは、「部分集合」の問題である - inputs, outputs, transaction kernels の集合が与えられた時、これらの部分集合によって有効なトランザクションが再構築できてしまう。 例えば、次の２つのトランザクションがあるとする - (in1, in2) -> (out1), (kern1) (in3) -> (out2), (kern2) これらを以下のようにブロックに集約することができる - (in1, in2, in3) -> (out1, out2), (kern1, kern2) （inputs と outputs の差がゼロとなるように）トランザクションを再現するためにすべてのあり得る順列を試すことは、ごく簡単である - (in1, in2) -> (out1), (kern1) そして、我々は、残りの要素で他の有効なトランザクションを組み立て直すことが可能であることを知っている - (in3) -> (out2), (kern2) この問題を和らげるため、transaction kernel 毎に _kernel offset_ という値を含めることにする。これは、コミットメントの和がゼロであることを検証するために、kernel excess に追加する必要がある blinding factor (秘密鍵)である - sum(outputs) - sum(inputs) = kernel_excess + kernel_offset トランザクションをブロックに集約する時、ブロックヘッダに _一つだけ_ aggregate offset を保存する。これにより、一つ一つの transaction kernel offsets に分解できない一つの offset を作ることができた。そしてトランザクションは再構成できない - sum(outputs) - sum(inputs) = sum(kernel_excess) + kernel_offset トランザクションを構成する際、鍵 `k` を `k1+k2` に分割する。transaction kernel `(k1+k2)*G` については、`k1*G` （excess）と `k2`（offset）をパブリッシュし、トランザクションに `k1*G` で署名をする。 ブロックを構成する際には、単純に `k2` を足し合わせて一つの集約した `k2` offset を生成でき、それによりブロックの中のすべてのトランザクションをカバーできる。個々のトランザクションの `k2` offset を再構成するのは不可能である。 #### Cut-through ブロックは、マイナーに複数のトランザクションを１つの集合に集め、チェーンに追加させる働きがある。 次のブロックの表現では、トランザクションを3つ含み、inputs と outputs のみ表記することにする。 inputs はそれらが使用する outputs への参照である。以前のブロックに含まれる output を小文字の x で表記する。 I1(x1) --- O1 |- O2 I2(x2) --- O3 I3(O2) -| I4(O3) --- O4 |- O5 すると、以下の２つの性質に気づく： * いくつかの outputs は直接ブロック内の inputs によって使用されている（I3 は O2, I4 は O3 を使用している） * それぞれのトランザクションの構造は実際にはあまり意味をなさない。個々のトランザクションの和がゼロなので、それらの合計であるすべてのトランザクションの inputs と outputs の和はゼロでなければならない。 トランザクションにおいても似たように、ブロックの中でチェックする必要があるのは所有権が証明されているという こと（_transaction ketnels_ によって可能）と、ブロック全体が（coinbase 以外で）新たなコインを加えて いないということである。 したがって、全体的な和に対する寄与が相殺されるので、 inputs と outputs の組合わせを排除することができる。それにより以下のようなよりコンパクトなブロックになる： I1(x1) | O1 I2(x2) | O4 | O5 トランザクション構造が排除され、inputs と outputs の順番がもはや意味をなさないことに注目されたい。 しかしながらこの場合でも、このブロック内のすべての outputs の和から inputs を引いた結果は、ゼロで あることが保証されている。 ブロックは、単純に以下の要素から成っている： * ブロックヘッダ * cut-through 後に残っている inputs のリスト * cut-through 後に残っている outputs のリスト * ブロック全体をカバーする一つの kernel offset * それぞれのトランザクションに対して transaction kernels が存在し以下の要素から成る： * すべての commitment の和から得られる公開鍵 `r*G` * excess value によって生成された署名 * マイニング手数料 このように構成された時、Mimblewimble ブロックは極めて良いプライバシーを提供する： * transaction kernel のみによって中間（cut-through）トランザクションが表現される * すべての outputs が同じに見える：互いに区別することのできないとても大きな数だけである。 いくつか outputs を除きたいと考えたとき、すべてを取り除かなければならない。 * すべてのトランザクション構造が取り除かれ、どの output がどの input と組になっているかを 知るのは不可能である。 それでもなお、バリデートすることができる！ #### Cut-through All The Way 前の例のブロックに戻ろう。I1 と I2 によって使用された outputs x1 と x2 はそれ以前にブロックチェーン に出現していなければならない。したがってこのブロックが追加された後は、これらの outputs、そして I1, I2 もチェーン全体から取り除くことができる。それらは総額には影響しないからだ。 一般化すると、任意の時点において（ヘッダーを除いて）チェーンの状態は以下の情報によって要約される： 1. マイニングによって作られたコインの総額 1. utxo の完全な集合 1. それぞれのトランザクションに対する transaction kernel はじめの情報はブロック高（ジェネシスブロックからの距離）から推定することができる。 そして、utxo と transaction kernel は共に極めてコンパクトだ。これは２つの重要な結果を持っている： * Mimblewimble ブロックチェーンのノードが保持する必要のある状態はとても少量である（ bitcoinサイズのブロックチェーンでは数ギガバイトのオーダーなのが、数百メガバイトにまで最適化 され得る）。 * Mimblewimble チェーンのネットワークに新しいノードがジョインする時、送信する必要のある 情報の量もまたとても少量である。 さらに、output を足したり除いたりするだけでも、 utxo の完全な集合は改ざんできない。そうすると transaction kernel 内の blinding factor の和と outputs 内の blinding factor の和が 違ってしまうからである。 ### 結論 このドキュメントでは、Mimblewimble ブロックチェーンの根底にある基本的な原理を 説明した。楕円曲線暗号の加算の性質を用いることで、完全に不透明な、しかしバリデート することのできるトランザクションを構築することができた。そしてこの性質をブロックに 一般化することによって、大量のブロックチェーンのデータを節約することができ、素晴らしいスケーリング、新しいピアの高速な同期が可能となった。