Plasma Cash verification cost
m0t0k1ch1.icon Plasma Cash の検証コストに関する議論を整理する
---.icon
問題提起
If there is a Plasma block every minute, then if one holds a coin for a year the size of the non-spend proof for a payment is
kladkogex：Plasma（Cash）のブロックが毎分生成されるとして、コインを 1 年間保有した場合、支払い時に必要な non-spend proof のサイズは以下のようになる。
60 * 24 * 365 * 100 * 10 * 256 = 17 Gbyte
m0t0k1ch1.icon 256 は Merkle tree が扱うハッシュのサイズかな（ならば 100 * 256 と並べてほしいが）
This assumes that an average payment transfers 10 coins and that the depth of the Merkle tree is 100
kladkogex：「支払い時には平均 10 コインが移動する」「Merkle tree の深さは 100」を仮定している
This needs to be multiplied by 2 because the receiver needs to send the change back. So it is 34 GByte total traffic
kladkogex：受け手はお釣りを返す必要があるので、これは 2 倍になる。つまり、合わせて 34 GB のトラフィックとなる。
How feasible is the entire payment then? How long will it take for sender to upload and for receiver to download and verify 17 GB of data and then pay the change back and then for the sender to verify the proof for the change? Uploading 17 GB of data will mean days for many people that have asymmetric DSL.
kladkogex：これの実現可能性はどれほどだろうか？送り手が 17 GB のデータをアップロードし、受け手がそれをダウンロードして検証してお釣りを返し、送り手がそれを検証する。これにどのくらいの時間がかかるだろう？ADSL を利用する多くの人々は、17 GB のデータをアップロードするのに数日を要する。
---.icon
現状提案されているソリューション
Compression
Most of the coin validity proofs are exclusion proofs, and those can be compressed using SNARKs/STARKs. For e.g. if we use constant-sized proofs this means that a coin validity proof will only increase in size when a coin is spent.
ldct：coin validity proof のほとんどは exclusion proof であり、それらは SNARKs/STARKs によって圧縮できる。例えば、コインが使用された回数分しか coin validity proof のサイズが大きくならないような proof もある。
m0t0k1ch1.icon exclusion proof は、コインの所有者に変更にがない場合に発行される証明
Back-of-the-envelope calculation: if a coin is spent once per day, the proof size becomes 1.2 MB per coin.
ldct：簡易的な試算：あるコインが 1 日 1 回使用される場合、proof のサイズは 1 コインあたり 1.2 MB になる。
m0t0k1ch1.icon これ、自分で計算してみるべきだな
Checkpointing
We know that withdrawing and re-depositing a coin will “reset” the length of the coin validitiy proof; this construction allows you to do this at an amortized cost of 1 bit of storage (SSTORE) per coin.
ldct：コインを引き出して再度デポジットすれば、coin validity proof のサイズはリセットされる。これは、1 コインあたり 1 ビット分のストレージの償却コスト（SSTORE）で可能。
m0t0k1ch1.icon SSTORE は、Ethereum においてストレージにデータを格納するための opcode
Back-of-the-envelope calculation: if we do this every 3 months would make the proof size is upper-bounded at 0.4 GB per coin at the cost of a few cents per year.
ldct：簡易的な試算：これを 3 ヶ月ごとに行えば、年間数セントのコストで proof のサイズの上限が 1 コインあたり 0.4 GB になる
m0t0k1ch1.icon 注：ldct は withdrawing and re-depositing を推奨しているわけではない
m0t0k1ch1.icon checkpointing については、それをプロトコルとして組み込んだ Plasma XT も参照 Combinations Thereof
We can combine these two techniques by doing a checkpoint when even the compressed proofs get too big. Analysis: with checkpoints, we can have the coin validity proof grow as$ O(f(n))and the per-unit-time cost of owning a coin grow as$ O(g(n))with the constraint that$ fg \in O(n)where$ nis the total number of plasma blocks (i.e. increases by 1 per minute).
ldct：圧縮 proof のサイズが大きくなり過ぎた場合に checkpoint を打つなどして、これら 2 つのテクニックを組み合わせることもできる。 coin validity proof のサイズが$ O(f(n))で大きくなり、1 コインを保有する単位時間あたりのコストが$ O(g(n))で大きくなるとすると、checkpoint によって$ fg \in O(n)にできる。なお、$ nは（1 分ごとに生成される）Plasma ブロックの総数とする。
Three points on this tradeoff space are
ldct：このトレードオフ空間における 3 つの点は以下。
m0t0k1ch1.icon 以下 3 つのうちどれかを満たすとどれかが満たせなくなる、みたいな話かな
1. Bounded proof sizes, constant rent (e.g. 1 cent/year/coin)
2. Constant cost to own a coin, but proof size grows linearly (e.g. 1.7gb /year)
3. Both cost and proof size are$ O(\sqrt{n})
ldct：
1. proof のサイズは有限、コストは一定（例えば、1 コインを 1 年保有すると 1 セント）
2. 1 コインを保有するコストは一定だが、proof のサイズは線形に大きくなる（例えば、1 年あたり 1.7 GB）
3. コストと proof のサイズはともに$ O(\sqrt{n})
m0t0k1ch1.icon コストには「A：データ保持コスト」と「B：金銭的コスト」があると考える
m0t0k1ch1.icon 1：A はある一定値を超えることはないが、B は時間とともに増大（例えば checkpoint アリの場合で、このときの B は checkpoint を打つためのコストに相当するのだと思う）
m0t0k1ch1.icon 2：A は時間とともに増大するが、B は一定（例えば checkpoint ナシの場合で、このときの B は deposit 時のコストに相当するのだと思う）
m0t0k1ch1.icon 3：1 と 2 の中間？
By combining them we relax the constraint to$ fg \in O(s)where$ sis the number of spends of the coin (i.e. increases by 1 every time the coin is spent).
ldct：組み合わせることで、制約は$ fg \in O(s)に緩和される。なお、$ sはコインの使用回数。
m0t0k1ch1.icon これが圧縮の効果ということかな
---.icon
zk-SNARKs/STARKs の活用
For succint/scalable verification technology in general, this depends on the exact construction and there are trade-offs, eg STARKs have lower prover cost and longer proof sizes (hundreds of kilobytes vs hundreds of bytes). The trade-offs come into play because depending on exactly how you want to compress the proofs, maybe the verification must be doable on-chain, or maybe it is sufficient to do them client-side.
ldct：一般的に、簡潔/スケーラブルな検証技術は厳格な構成に依存しており、ここにはトレードオフがある。例えば STARKs は、prover のコストは小さいが proof のサイズは大きい（数百 KB vs. 数百 B）。proof をどのように圧縮したいかによってトレードオフが生まれるので、それに応じて検証をオンチェーンで行わなければならなくなるかもしれないし、クライアント側で行うだけで十分となるかもしれない。
For the specific zk-SNARK construction I believe that the verification costs is low (dominated by two elliptic curve pairings) but the costs of the trusted setup as well as prover cost are quite high (@kfichter estimated hours per plasma block to produce a proof of the validity of an entire block). For asymptotic costs I have the following table in my notes (note: I don’t understand everything in this table!) for the cost of doing various things for an arithmetic circuit of with$ Nwires,$ lof which are public:
ldct：ある特定の zk-SNARK の構成については、（2 つの楕円曲線ペアによって支配されているため）検証コストは低いが、信頼できるセットアップのコストと prover のコストは非常に大きい（kfichter の見積りだと、1 Plasma ブロックの正当性についての proof を生成するためには数時間を要する）。漸近的なコストについて、自分のノートには以下の表がある（注：自分はこの表の中身を全て理解しているわけではない）。これは、$ N本の線から構成され、そのうち$ l本が公開されているような演算回路に対して、様々な手法を用いた場合のコストである。
m0t0k1ch1.icon ふーむ。。書いてあることがわからんぞよ。。。
https://gyazo.com/78bf79a68c5d6b39f57ebb67bce0365d