Merkle forest を利用した RSA accumulator による proof of inclusion/exclusion 生成について


#1

Log(coins)-sized proofs of inclusion and exclusion for RSA accumulators で提案されている Merkle forest を利用した proof of inclusion と proof of exclusion の原理について理解できず、困っています。

具体的には、上記リンク先における

We can deal with this problem by extending the scheme further, making a Merkle forest instead of a tree:

以降の話です。

自分が途中まで読み解いたログは こちら なのですが、書きながらわけがわからなくなってきました。何かを根本的に勘違いしているような気がしており、1 人で唸っても正しい理解にたどり着ける気がしないので、何卒、皆さまの脳をお貸しください:pray:


#3

slice が未定義なまま aligned slice が出てきている件を整理したいです

slice とは:素数でできたMerkle Treeのノードのこと?
aligned slice とはproof of non-membership対象leavesの直上の親にあたるsliceノードのこと?


P.S.
aligned slice は、おそらく一番大きなツリーのleavesの位置に存在する。
そのツリーよりもひとつ小さなツリーのsliceと、大きなツリーそのもののsliceが対応するsliceに着目して、それ以下のleavesを指して aligned slice と呼ぶのではないかと思っている


#4

なるほど、なんで小さい木はnon-inclusion用なのかというのは、「non-inclusion用だからaligned sliceで浅めにproofを作れちゃって、leavesの分までデータを持たなくていいから、結果として木が小さく見えている」ということですね


#5

実は僕もここわからなくて、以下の方を先に理解しようとしてました。https://ethresear.ch/t/short-rsa-exclusion-proofs-for-plasma-prime/4318

でも @m0t0k1ch1さんのscrapboxを見てたら少しわかった気がします。

まずここで紹介されている最初の方法を方法1、forestの方を方法2として考えてみます。

方法1

方法1ではcoin0, 1に関して

  • non-inclusion=1k
  • inclusion=2k

ここでkはaccumulatorの基本proofサイズ(例えば64bytesとか)
それでこのinclusionが2kなのを、方法2で緩和したいのだと思います。(ここは @m0t0k1ch1さんのscrapboxで理解しました)

方法2

複数coinのinclusion proofには「より左の(より高い)(より深さが短い)」treeを使用してproofサイズを下げているのだと解釈しました。
coin0, 1のinclusionを確認するために、もしmerkle treeであれば13のinclusionがあれば良いとなるところを、それはできないので(その方法はnon-inclusion proofで使用したいはずなので)、左の木の7と3にしています。その代わりsingle elementのproofと競合するので、13のexclusionを確認しないといけません。またより大きなaligned sliceと競合しないように2のexclusionも確認しないといけないと思います。

inclusion=4k
non-inclusion=3k

これだと前の方法よりもproofサイズが大きいのですが。

もし4coinだったら
inclusion=6k
non-inclusion=4k

もし16coinだったら
inclusion=10k(方法1だと32kになってるはず)
non-inclusion=6k(方法1だと16kになってるはず)

って感じなのでしょうか? :sweat_smile:


#6

2^2のcoinのinclusionだとパターンが見えてくる気がしました。


#7

@sg42 @syuhei176 ありがとうございます!いただいたヒントをもとにもう一歩で理解できそうな気がしてきました。

そこで、一旦、現状の自分の認識が @syuhei176 さんに解説していただいたものとズレていないかを確認してみたいです。

Merkle forest の構造としては以下を仮定します。

Merkle forest

Plasma Cash に適用する場合、19 と 23 と 29 と 31 が 1 fragment に対応するはずなので、それを念頭に置きつつ、「ある slice を accumulator に追加する場合、実際に accumulator はどのような演算をするか」という観点で自分の認識を整理してみます。

  • slice [0](19)を追加する:A’ = A^{5 * 13 * 19}
    • single element slice
  • slice [0…1](19 と 23)を追加する:A’ = A^{3 * 7}
    • size 2^1 の aligned slice
  • slice [0…2](19 と 23 と 29)を追加する:A’ = A^{3 * 5 * 7 * 17 * 29}
    • 一部が size 2^1 の aligned slice な slice
  • slice [0…3](19 と 23 と 29 と 31)を追加する:A’ = A^2
    • size 2^2 の aligned slice

上記、合ってるでしょうか?


#8

これを別々のaccumulatorに追加するのであれば、おそらく僕の理解と同じなのですが、Plasmaでの使い方として、複数ブロックで同一のaccumulatorに追加していくことを考えているはずで、そうするとおかしくなりそうですね。。
slice [0…1]を追加する時に、13を除けないので、A’ = A^{23}を追加しないとつじつまが合わなそうですよね。
ちょっとわからなくなって来ました:sweat_smile:


#9

確かに、自分も単独の accumulator を使い続ける場合についてはあまり考察してませんでした。。

が、各ブロックにはそのときの accumulator の累算値が記録されていると考えると、基本的にはあるブロックからあるブロックまでの差分だけを考えて証明できればよい(proof of membership は対象が含まれる 1 ブロックに対して行い、proof of non-membership は対象が含まれてない複数ブロックに対して行う)はずなので、すごくなんとなくなのですが、この考え方で大丈夫なのではないかなと思っています。ただ、まだ理解が浅く断言はできないので、基本的な RSA accumulator を復習しながら、複数ブロックがあるパターンについて簡単な具体例を書いてみるなどした方がよさそうですね。

あと、話が変わるのですが、

の下に貼ってあるパターンについて、自分の理解だと以下のようになると思うのですが、どうでしょう?(aligned slice と記載している slice の membership を証明するという前提)


#10

確かに、もう一度ルールを見返してみると。

・The value corresponding to the subtree is not included in any lower tree in the forest.

のルール的に、右から2つ目のtreeはexclusionですね。


#11

提案1は、素数をノードに持つ二分木を作り、(a)「左右の子ノードの一方でもaccumulatorに含めるなら」自身もaccumulatorに含める、という方法でaccumulatorを作る。こうすることで、各ノードがaligned sliceに対応し、(b)「aligned sliceの葉のうち少なくとも一つ」がaccumulatorに入っているなら、そのaligned sliceそのものに対応するノードが入っている、という状況にできる。これでsliceに対するexclusionの証明が簡単にできる、というものですね。

ここで思ったのが、(a)を「左右の子ノードの両方をaccumulatorに含めるなら」に変更することで(b)が「aligned sliceの葉のうち全て」になり、inclusionを簡単に証明できるのでは、ということです。こちらをand木、提案1の方をor木と呼ぶことにします。or木、and木の両方を2つとも用意すればinclusion,exclusion共に証明できるように思います。

しかし、ここで使われいているのはforestで、xorとandを混ぜた加算器のような形になっているように読めます。この方法がor木and木の方法に対しどんなメリットがあるかは、よくわからないです。

後、

To prove membership of eg. coin 17, you would need to prove that[$ 2 * 5 * 17]is part of the accumulator

の所等について、「必要」であるのは17がaccumulatorに入っていることだけのように思います。もしかしたら、ここら辺の必要十分性の理解が重要なのかもしれません。


#12

ここで思ったのが、(a)を「左右の子ノードの両方をaccumulatorに含めるなら」に変更することで(b)が「aligned sliceの葉のうち全て」になり、inclusionを簡単に証明できるのでは、ということです。こちらをand木、提案1の方をor木と呼ぶことにします。or木、and木の両方を2つとも用意すればinclusion,exclusion共に証明できるように思います。

なるほど、and木とor気があれば確かに。面白いですね。ちょっと実際に計算量とメモリ量を計算してみましょうか。

To prove membership of eg. coin 17, you would need to prove that[$ 2 * 5 * 17]is part of the accumulator

多分ここは2, 5, 17を見ないと、仮に5が無かったら、13, 17のexclusion proofができてしまう気がします。


#13

確かに。or 木 + and 木は面白いですね。forest との計算量とメモリ量の比較は気になりますが、何よりシンプルなことは 1 つのメリットであるように思います。


#14

このスレの本題とは少し主旨がズレてしまうのですが、

^ で提案されている proof 生成方法が Vitalik が提案したものとはまた違うようで、

The similar prooving schema was proposed by @vbuterin here. We proposed schema with shorter proofs of inclusion (because we need to proof only inclusion of several numbers) and same proof of non-inclusion.

proof of inclusion をより短くできるとのこと。ただ、その下に記載されている説明がよくわからない。。。例えば末端の leaf 数が 2^2 の tree で P が具体的にどの部分を指すのかが分かればイメージしていけそうな気はするのですが、どこを指すのだろう。。。?

(ほぼ自明なことも含みますが)ヒントになりそうなことを以下にまとめます。

  • P は aligned slice
  • 集合演算が適用されているので、 P 自体は集合だと考えられる
  • P を引数とした childparent という関数が定義可能
    • これらの関数の返り値に集合演算が適用されているので、これらの関数の返り値は集合だと考えられる

これを読むまで、aligned slice は例えば下図だと [P3, P4] などに当たるという理解だったのですが、「その場合の child 集合とは。。。?」となって、何か間違えている気がしてきたのが今です。