Defragmentation

Overview

PlasmaにおけるDefragmentationについて説明する。Plasma Cash/Cashflowでは価値にIDをつけることで、exit-gameでの安全性を増し、検証すべき履歴を自分の受け取る価値に最適化することができた。

しかしその一方で所有する価値の「断片化(fragmentation)」という問題が新たにできてしまった。

Chamberではdefragmentation機能により、断片化したsegmentをまとめることでexitする時のコスト/価値を下げる。

This document will describe our implementation of defragmentation function, one of the key features of Plasma Chamber. With Plasma Cash/Cashflow design, the process of corresponding unique ID to values promises more security of exit games and allows uses to optimize the size of history data that they have to hold and inspect to the value that they receive each time. However, another problem, fragmentation of indexed coins arose. Since each fragmented segment of the coins requires the same amount of gas cost, regardless the size of the segment, the more fragmented segments each user holds, the more exit cost will be required. That premises cause a bad user experience when exit cost grows so much that user cannot even evhold remittances with an amount of money that deserves the exit cost. Also there will be another problem when segment that a value sender holds are too small; it increases the receiver's inspection costs and time. If the segments in such transfer transactions are assembled and processed, TokenID will be indexed to each segment, not the transaction as a whole, hence history data that corresponds to each segment but doesn't depend on it size will be sent to transfer receiver. As a result, fragmentation is very inefficient from the perspective of the transaction history inspection.

これによりマイクロペイメントも可能にする。

By this feature, micro payment is expected to be allowed on Plasma.

Features

このdefragmentationを実現するために、Chamberではいくつかの要素を用意している。そして、以下の必要な実装は終わってる。

segment の atomic swap

signatureが揃わなかった時のためのforce includeの仕組み

defragmentationのためのplasma chainとwalletのimplementation

not implemented feature

Current edge of eth comunity research. We should implement this first.

no fragment transfer using special path

require multiple party atomic swap

pros: no fragmentation

cons

all users on the path should be online.

The size of "multiple party atomic swap transaction" become bigger.

There are some key components in our defragmentation in Plasma Chamber, and those key functions are already implemented.

Atomic swap of segments

Force include function in case when mutiples signatures are not collected concurrently

Customized implementation of Plasma chain and wallet for defragmentation

Here are links to each features' source codes.

force include:

Challenges

未解決の課題として以下がある。

現状ではsegmentを交換する二人が、二人ともオンラインじゃないといけない。

トランザクション発行後にconfirmation signatureを交換する必要があるため。

There is still a challenge with our implementation that we have to solve in the next. As of this moment, 2 end-users who are exchanging their segments, theoretically sender and recepitient of the transfer, have to both be online concurrently. This is because they have to exchange their coinfirmation signature after the transaction is issued.

これに対して解決策を提案する。

Grant Applyでの主要な提案

今回はオペレーターがswapを仲介することで、ユーザ同士のマッチングの必要をなくす提案を行う。

ユーザは一定期間ごとにオンラインになる。

現実的には「全てのユーザは」ではなく「一定の割合のユーザが」という条件にしたい

オペレーターは交換のための、一定のできるだけ少ないバッファーを持つ。

という条件のもとで、ある期間内にdefragmentationが終了することを示し実装する。

またオペレーター以外にも常時オンラインでかつ多くのPlasma内のETHを所有しているフルノード（merchantノードなど）を積極的に活用し、インセンティブをつける方法を設計する。

We will propose one possible solution for this problem.

- Operator can act as an intermediary fo the swap so that there is no need for 2 users to be matched at the same time.

In this proposal, users are supposed to be online at least once in a certain amount of period. Not every user, but a certain amount of users will have to be online, more rearistically. Operators will have to hold some, preferablly, as little segement pools as possible to delegate one of the users as a middleman of the transacion.

We are currenlty trying to complete the implementation of defragmentation with this specific condition above.

感触では、9割のユーザよりも大きなサイズのバッファーが存在すれば良い気がする（9割の合計ではなく、所有順に並べた時の上位1割に入る程度の額）

Plasma内で所有ETHの多いmerchantなどに積極的にdefragmentationをお願いすれば一番良い気がするが、あまり研究的要素はないかもしれない。どちらかというとCELの開発するmerchant用フルノードに、defragmentation機能を組み込むという話になる。atomic swap自体にインセンティブをつけるのは難しい。

実装自体は可能に思えるが、現実的に長期間運用できるかが問題なので、その仕組みについて研究開発していく感じにする

sg. 暗黙にmerchantが存在するユースケースに特化していくので気をつける

defragmentationの流れの例)O=Operator

1stepはOのSegmentとオンラインユーザのSegmentのswapで表現される. *はswap予定Segment

code:js

0-1(A*), 1-2(B), 2-3(C), 3-5(A*), 5-7(C), 7-10(B), 10-13(O*)

Aがオンライン

0-1(O), 1-2(B), 2-3(C), 3-5(O), 5-7(C), 7-10(B), 10-13(A)

Bがオンライン

0-1(O), 1-2(B), 2-3(C*), 3-5(O*), 5-7(C*), 7-10(B), 10-13(A)

Cがオンライン

0-1(O*), 1-2(B*),2-4(O*), 4-7(C), 7-10(B*), 10-13(A)

Bがオンライン

0-4(B), 4-7(C), 7-10(O), 10-13(A)

Example of the defragmentation process

* O = Operator

* 1 step is represented with operator's segment and swap of online users' segments

* segments with * is the one that are supposed to be swapped

code:js

0-1(A*), 1-2(B), 2-3(C), 3-5(A*), 5-7(C), 7-10(B), 10-13(O*)

A is online

0-1(O), 1-2(B), 2-3(C), 3-5(O), 5-7(C), 7-10(B), 10-13(A)

B is online

0-1(O), 1-2(B), 2-3(C*), 3-5(O*), 5-7(C*), 7-10(B), 10-13(A)

C is online

0-1(O*), 1-2(B*),2-4(O*), 4-7(C), 7-10(B*), 10-13(A)

B is online

0-4(B), 4-7(C), 7-10(O), 10-13(A)

More Research Needed

時間経過によって動かせない（所有者がオフラインの）segmentが増えるのではないか？

sg. exit periodが3ヶ月とかの長さだと多少深刻化しそうですね。シミュレートしてみたい

断片化(fragmentation)したバッファー(Slot)を、オペレーターがデフラグメントするには新たにデポジットするしかないのではないか？

Here, we would like to adress further research questions to investigate regaring our protocol design. We need more researchers to work with for these.

Wouldn't there be more segments held by offline users as time passes? This situation will be even more problematic if the exit period gets longer.