かんがえる、かがんでいる人

考えたことをまとめます。

Bulletproofの話

f:id:ton96O:20181115175553j:plain

以前「zk-SNARKsとzk-STARKsの話」という記事を書きました。

その際引用した資料でzk-SNARKs・zk-STARKsと並んでBulletproofというものがありました。
今回はそちらについて書いてみたいと思います。

 

Monero Becomes Bulletproof – DigitalAssetResearch – Medium

より、XMRにBulletproofを使う概要としてはここに尽きるかと思います。

Bulletproofs are a big deal, as they can increase the privacy of digital currency transactions and at the same time dramatically decrease their size.

Bulletproofは、電子通貨取引のプライバシーを向上し、同時にその規模を劇的に縮小することができるため、大きな解決案です。
Bulletproof自体は、信頼しなければならないセットアップを必要としない非対話式ゼロ知識証明です。
(PIVXにも使用されるようです。利用理由は同じようなものでした。)

 

上記引用記事によると

This technology is intended to address one of the main drawbacks of RingCT: the size of the range proofs this scheme produces.

この技術はRingCTの主な欠点の1つ、すなわちこの仕組みがもたらす範囲証明のサイズに対処することを意図しています。

RingCTの説明をしておきます。XMRのRing SignaturesとConfidential Transactionsを組み合わせたものです。
暗号通貨ひとり勉強会
こちら様が素晴らしいです。
Moneroのリング署名の匿名性はチェーンのフォークによって損なわれうる
こちらでは、

Moneroは主にリング署名・RingCT・ステルスアドレスという3つの技術によって取引の匿名性を確保しています。

と、RingCTはRing Signaturesと別もの扱いされています。
ざっくり、RingCTは送金元アドレスと送金量を隠す技術と理解しておきます。

 

 

ここまでの確認です。

Bulletproofを調べています。

そこでXMRにBulletproofが使われようとしている記事を参照しました。プライバシープロトコルとしてBulletproofが採用される最初の事例のようです。

それにはRingCTの欠点である範囲証明のサイズが関係しているのでした。

RingCTはというと、送金元アドレスと送金量を隠す技術という事でした。

 

 

続けます。

On one hand, the use of NIZKP Bulletproofs does not require a trusted setup for parameter generation, like Zcash’s Powers of Tao ceremony. On the other hand, the verification of a Bulletproof is more time consuming than zk-SNARKs.

ここでいうNIZKPは「非対話式ゼロ知識証明」とでも訳しましょうか、一方通行なんですね。
そこだけを見ると「zk-SNARKsと同じだな」というところですが、別物です。
NIZKPはBulletproofで使われている仕組みです。
zk-SNARKsとzk-STARKsの話でも書きました、zk-SNARKsは、そのセットアップ自体を信頼しなければなりません。
しかし、Bulletproofはzk-STARKs同様、それが必要ありません
一方でzk-SNARKsに比べ検証に時間がかかるようです。

On the other hand, the verification of a Bulletproof is more time consuming than zk-SNARKs.

一方、Bulletproofの検証はzk-SNARKよりも時間がかかります。

 

概要でお伝えした通り、「プライバシーを向上し、同時にその規模を劇的に縮小することができる」一方で検証時間はzk-SNARKの方が短くて済むようです。
XMRのトランザクションサイズは線形関数的、Bulletproofにおいては対数関数的な増加をします。

線形関数的とは

f:id:ton96O:20181115175207j:plain

対数関数的とは

f:id:ton96O:20181115175222j:plain

上記だと原点に近い部分で急激なコスト上昇がある、と思われるかと思います。

しかし、XMRは相当なトランザクションがあるのですね。だからもっと右の方が延長していきます。
それであれば、対数関数的な施策を取った方が良いとご理解いただけると思います。

なので、XMRに役に立つであろうという事でした。 

 

GitHub - adjoint-io/bulletproofs: Bulletproofs are short non-interactive zero-knowledge proofs that require no trusted setup
から、範囲証明や内積範囲証明によるトランザクションの低減は、表現方法の変更により実態の伝達を損なうことなく伝達内容量を減らすことができる事だと理解しています。(間違っていたらご指摘ください)


例えば
AAAAAAAAAAAAABBBBB

A*13+B*5
と表現できます。どちらでも同じことを意味していますし、情報を受け取った方は内容を再現できるでしょう。
上は18文字、下は8文字。伝達すべき情報が削減できました。


しかし
AABBBCCCCDDDEEFFFFGHHHHIJJ
だと
A*2+B*3+C*4+D*3+E*2+F*4+G*1+H*4+I*1+J*2
と、こんな具合に「低減されるには条件がある」という事は忘れてはいけないようです。
上記だと「連続する部分が多い場合効果的」と言えるでしょう。

Bulletproofs: Efficient Range Proofs for Confidential Transactions(pdf注意)
でも

Non-interactive zero-knowledge protocols for general statements are not possible without using a common reference string, which should be known by both the prover and the verifier.

証明者と​​検証者両者に知らされているべき共通の参照文字列を使用しないNIZKPは不可能です。
とあります。
実際はその条件をクリアしているので大丈夫なのですが、何らかの効率化には前提や条件がある事は忘れてはいけないようです。

 

 

 

上記
Bulletproofs: Efficient Range Proofs for Confidential Transactions(pdf注意)
はまだ全部読めていません、というか、難しくて正確な理解はコスパが悪すぎます。
さらには
Bulletproofs: Short Proofs for Confidential Transactions and More(pdf注意)
まだ、あるんです。

文章だけ寝かせておいても意味がないのでとりあえずこれで挙げます。

 

参考
Bulletproofs: Efficient Range Proofs for Confidential Transactions(pdf注意)
Bulletproofs: Short Proofs for Confidential Transactions and More(pdf注意)
Monero Becomes Bulletproof – DigitalAssetResearch – Medium

Bulletproofs:Short Proofs for Confidential Transactions and More
Non-interactive zero-knowledge proof - Wikipedia

誰か、「Bulletproofs」って言ったかい? | PIVX

Bulletproofs pre-release – Interstellar – Medium

Bulletproofs: The New Kid in Blockchain Security Land

スタンフォード大学のACGが目指す『Bulletproof』とは
GitHub - adjoint-io/bulletproofs: Bulletproofs are short non-interactive zero-knowledge proofs that require no trusted setup

From Zero Knowledge Proofs to Bulletproofs Paper | waxwing's blog

匿名属性認証における効率的な範囲証明プロトコルの提案(pdf注意)

Schnorrの非対話型ゼロ知識証明(NIZKP)について定義しているrfc8235を読んでみた - Develop with pleasure!

?