Play with Plasma: Implementing Plasma's Substitutability

Foreword

This article is intended to introduce concepts such as checkpoints, proof compression, and Merkel trees.

This article is part of a series of articles written by Daniel Goldman about Plasma. For more information on Plasma's theoretical foundations, Plasma MVP and Plasma Cash, see " Playing with Plasma (1): Getting Started with Zero and " Playing with Plasma (2): Talking about Plasma Cash ".

In the previous article, we started the research journey of Plasma. We hope to find a high-throughput payment system that not only preserves the security of the Ethereum blockchain, but also requires only occasional constant-scale chain transactions.

Let's take our eyes off the Plasma Cash structure – in the previous article, we mentioned that this structure implements many of the features we want, but it also brings two major flaws: the “coin” of Plasma Cash actually It is an irreplaceable token (which limits the flexibility of payment denominations) and it requires users to store a large and growing data set.

In this article, we'll explore some of the other features and mechanisms based on Plasma Cash that are designed to circumvent – ​​or at least mitigate – these deficiencies (and/or rethink Plasma Cash).

• The return rate is 29%! Great God uses sentiment analysis to create a bitcoin trading algorithm
• Gu Yanxi: Ten Basic Elements of the Economic Model of the Pass
• Global Blockchain, Digital Assets Regulatory Policy and Practice – ASEAN

Disclaimer: Things will become more and more complicated. Quoting the metaphor of mathematician Peter Saran, this type of research is like trying to flatten a carpet that is slightly larger than the room in which it is located. Whenever you step on the corner of the carpet, the other corner will unexpectedly tilt. In addition, this article is about to open a study on Plasma. As we will see, some issues remain unresolved. Much of the content discussed here is still in the process of exploration and remains to be evolving and discovering.

Then next, the first is:

Reduce the amount of data on the client, Strategy 1: Checkpoints

We see (we will call it later) vanilla Plasma Cash (Vanilla has the meaning of vanilla, and the old-fashioned/ordinary meaning, here is the meaning of the pun). The amount of data that each client needs to store over time The transition has grown linearly.

That is, for each coin, each Plasma block needs a Merkel certificate that contains (or is spent) or not included (the ownership of the currency remains the same). This complete history is necessary because no one knows what part of the evidence the user needs in the dispute resolution process. The complete storage of the data itself is painful enough, and it is no different to transfer all of this data to the next owner at each payment.

To help alleviate this pain, we might as well contemplate a solution: for example, every two weeks, or every 500 Plasma blocks, the Plasma chain will officially have some "chain events" to determine some (or all) Plasma. The ownership of the Cash currency.

That is to say, once this "chain event" is finalized, it will become a historical checkpoint: once you need to verify the proof of ownership of the current moment, you only need to go back to this point. There is no longer any dispute about previous history. Therefore, we can safely discard the Merkel proof of the previous block. At the same time, this scheme will define a specific upper limit for the size of the required client data. perfect!

The first thing we need to do to make these checkpoints work is to identify the Plasma operator (or other participants, but for the sake of simplicity, let us assume that it is the operator) how to prove a particular Plasma block The complete state of ownership of the currency.

As you may have guessed, this involves a Merkel tree: the operator constructs a tree that maps each coin to its owner's address and then sends the Merkel root to the master. chain. Each owner receives a corresponding Merkel branch. If after 2 weeks (or any other time), the data is not questioned, then we will assume that the status of this checkpoint has been officially recognized (this does require each user to receive the data online and the chain Monitor it. But keep in mind that Plasma requires the same activity as other Layer 2 structures.)

Is that ok? Oh, life is not that simple. Unfortunately, the above checkpoint mechanism introduces a very annoying edge condition.

Suppose a malicious/damaged/boring operator can no longer share any Merkel proof data with the user after broadcasting a Merkel root on a checkpoint. What should we do?

Any method that forces the user to force the operator to provide this data will cause us to fall into the wrong-equivalent area of ​​the speaker-listener and (often) introduce damage vectors and other complications. We can say that users can still safely withdraw funds back to the main chain, which is technically without any problems. The problem is that each user must now be evacuated to the main chain, and because of the checkpoints we just introduced, they must do so within a limited window (ie, two weeks). The "large-scale exit" corner of the carpet that was cleverly pressed in the previous article was tilted up again.

But this data will not be lost, we can save this data through the additional work form of "encryption economic aggregate signature" (I dare to swear that the real situation does not sound so scary). In essence, we slightly modified the proof of ownership so that the operator asked for the signature of the owner of each coin in the checkpoint. In other words, the operator can only set checkpoints for the currency with the explicit consent of the owner of the currency. The operator will then post some additional data on the chain to prove which coins are included in the checkpoint (imagine that each currency is represented in a list of binary digits, where "1" indicates consent/containment, and " 0" means not included).

Although this method seems counter-intuitive, it is enough to solve the problem! The key here is that each coin corresponds to a specific valid owner, and these owners know exactly what their identity is. In the same way, they also know whether they agree with a specific checkpoint.

Therefore, the only thing that these owners need to worry about is that they did not sign their currency when the checkpoint was set up, but they saw a "1" in the slot of the coin. In this case, they can only question – they know that the challenge is justified – and invalidate the checkpoint. As a result, we avoided the situation of large-scale exits and the checkpoints were safe.

The Layer 2 purists may have noticed at once that the chain requirements here are not "strictly Plasma" solutions. The size of the bitmap data is linearly related to the number of coins. But in reality, this cost should be quite small. Especially in most cases, we can use a simple bit field compression technology to greatly reduce the amount of data. In addition, the presence of checkpoints is very advantageous for their notarized currency. Therefore, the cost of a chain transaction can be ideally amortized among the owners of all currencies. Finally, the establishment of checkpoints follows the principle of voluntariness, and it is ultimately (at a glance) a very specific point of optimization.

Reduce the amount of data on the client, Strategy 2: Proof Compression

Another more advanced solution for reducing storage requirements is to effectively compress multiple Plasma block certificates into a single certificate.

Let us recall again that for Vanilla Plasma Cash, each block needs a Merkel certificate about whether it is included. The existing ideas, we add another requirement about inclusion: we not only need the chain Merkel root and the chain Merkel branch, we also need a chain "RSA accumulator (that is, pure use of number theory to prove membership) )" and "knowledge proof under a chain (details will be explained later, skip it now)." Both need to prove the inclusion problem, but only one of them needs to make proof that it is not included. That is to say, a coin is either included in the block or not included, and there is no other possibility. (For inclusion, the opposite of "A and B" becomes "(for uncontained proof) A or B".

At a higher level, this structure is based on the fact that the fact that it is not included is essentially easier to prove. And if a coin is included in the block, then we need more data – at least the address of the new recipient. In the case of not being included, we only need to say "this currency is not included." Obviously, we should apply this asymmetrical and simpler commitment to the cases that are not included.

(High energy ahead: fear mathematics do not enter)

After a lot of simplification, the following is how it works: As with the usual Plasma Cash MO, each currency will get an ID in the form of a natural number, but now we add an additional requirement that all of these IDs must be prime numbers. The RSA accumulator (G) submitted by each Plasma block is itself a number that self-updates as the Plasma block is transferred based on the currency.

Essentially, in the current block, G will grow exponentially with the ID of the currency being spent. For example, in the 101st block, the currency of the transferred currency has 5, 7, 17, 53, and 83 (both prime numbers). Let us assume that the value of the accumulator submitted by the 100th block is G100 (this is a large number), then the value of the accumulator of the 101st block is calculated as follows:

The value of this new G101 will be submitted to the main chain.

In the world of Layer 2 under the chain, if Alice (assuming she has a currency with the ID "17") wants to make sure that her own currency has been submitted to the accumulator, then she only needs the remainder of 17, which is 5 * 7 * 53 * 83 (153965). She gets G101 and G101 is on the main chain, which verifies:

This confirms her currency ID, which is already accepted by the accumulator. At the same time, she also got the submission information of the usual Merkel branch. Once she confirms this, there is no problem.

Now, let's consider Bob, the owner of the coin with ID 11. It should be noted that this currency has not been transferred in the 101st block. In order to get proof that the currency is not included in the block, Bob only needs a formula to show that 11 is not a factor of 153965. In other words, Bob essentially only needs one number. Once Bob has obtained this number, based on the "any/or" nature of the above requirements, Bob does not have to worry about any Merkel branch business that is not associated with the proof.

Finally, the most critical point is that the above process can be applied to multiple arbitrary numbered blocks, taking into account the nature of exponentiation and prime decomposition. That is, this process can be done based on multiple discrete blocks. In other words, the uncontained proof between the 100th block and the 101st block looks exactly the same as the uncontained proof between the 100th block and the 1 millionth block. Both only need Bob to store a number.

(end of mathematics)

If we think further, we are almost certain that in the life cycle of a particular coin, the currency is likely to only happen occasionally. For most Plasma blocks, this currency may never have changed. Through the mechanism we just introduced, the interval between the transfer processes of coins now only requires a constant amount of data (ie one or two numbers). So, now the client's data storage will only increase with each currency transfer. this point is very important.

Please note that the above scheme is a bit too simplistic: according to the above rules, the value of G will soon become very large. We did some detail processing to make this value have an upper bound on a modulo M. This modulus allows us to limit the growth of the accumulator's value while still retaining all the prime factors we need. However, even with this cap, if Alice and Bob want to perform the verification step, they still need to do some very heavy arithmetic operations. However, it turns out that this problem can be overcome: we can use several compression certification schemes. This means that Alice and Bob can only validate the results they care about without having to do complete and cumbersome calculations often.

However, there is an extremely complex problem that needs to be addressed. I am sorry to tell you that there is no simple solution so far. Simple, lightweight proof verification is really a good thing, but let's not forget that these proofs first need some "lucky" (ie operators) to generate these proofs. For example, for consumer notebooks, the computational cost of computing a large number of composite indices is very high.

Therefore, we need at least the operator to have a sophisticated server-side device. Some people hope that we can find ways to parallelize these operations, or outsource part of this work to multiple operators, or even the entire user base of the Plasma chain. In addition, by chance, other unrelated Ethereum ecosystem studies have sparked Plasma researchers' interest in verifiable delay functions (ASICS). The verifiable delay function ASICS also needs to calculate a large number of exponential stacks, so this may be helpful. Finally, other methods are similar to the RSA accumulator structure, but with different mathematical/cryptographic details—including vector commit information and different ZK-SNARK/STARK schemes. We are still exploring. However, it remains to be seen whether these studies will eventually overcome the computational bottlenecks to some extent economically.

Alternative payment: thinking from a numerical perspective

Finally, we may wish to make some changes, such as reducing the basic restrictions of Plasma Cash, that is, the irreplaceability of its assets. If we create a Plasma Cash coin worth 5 Ethereum, the coin cannot be split or merged – for the rest of its life, it is a coin worth 5 Ethereum.

To solve this problem, we first rethink our view of Plasma Cash, rather than actually changing any of its features (at least for the time being!).

Let us imagine a Plasma Cash chain in which each coin represents a single asset with a fixed denomination that is substitutable in the main chain (such as Ethereum). Before that, we talked about treating each currency as an irreplaceable token with a unique ID. Alice's ID 2342 may be worth 20 Ethereum. Let's make an equivalent mental transformation. Imagine that all the Ethereum in this Plasma chain is ordered in the order of the digit segments. If there are a total of 5000 Ethereum coins on the chain, then this line segment will extend from 0 to 5000. Alice's 20 Ethereums are no longer represented by a unique (although arbitrary) currency ID, but by a segment of the digit line segment ("Ethernet from 520 to 540"). In order to guarantee the legitimacy of each person's ownership of the Ethereum, the contract must enforce the following functions: Whenever a new "scope" is created, the old number field exists in the interval that was not previously occupied by other ranges. As long as we can guarantee this, we can build a new model that is isomorphic to the old Plasma Cash.

So far, everything is going well. Now, let's make another upgrade: Suppose Alice is spending her "coin", which means that we are now transferring ownership of her "number range" to the other party. What if Alice can not only assign this range to the new owner but also change the endpoints of the range during the transfer process? If this feature is implemented, Alice is free to pay Bob no more than 20 Ethereum denominations, such as "only 520 to 523 Ethereum."

In order to adapt to this situation, we need to make a little change to the structure of Plasma Cash: we will retain the concept of "coin", and each coin will represent the smallest unit of the digit segment we want to support (assuming 0.00001 ethers) currency). Now, these "coins" are only an abstract existence. Literally, they do not form part of the Plasma block. Instead, each block is now a trading tree, and each transaction is spent within a given range. If a "coin" within a particular range is owned by another non-expenditure party (owner), the real owner can challenge it. At this point, we will use the cryptographic economic challenge game inside the familiar vanilla Plasma Cash to solve the problem.

So now, the new puzzle becomes: How does Alice succinctly prove to Bob that all the coins she is trading are owned by herself, and that there are no other transactions that overlap or “overflow” into their own scope? ? If it is before, then every transaction will be included in a certain currency, but for now, we need some kind of proof to convey information about other transactions in the block in some way.

In order to achieve this goal, we will introduce another version of the Merkel tree! We call this new data structure the Merkel index tree. The leaves of the tree are the transactions themselves, and each transaction represents the transfer of coins within a certain range. The new feature of the Merkel index tree is that every node in the tree now gets a number assigned to it. The rules are as follows:

(1) The range of leaves at the bottom of the tree must be consecutively arranged (ie, the end point of each range must be less than the starting point of the next range), and

(2) The value of each parent node is equal to the smaller value of its two child nodes (if its child nodes are ranges, then we use the starting value of each range as a reference).

As long as a range of recipients verify that the above rules are true, Merkel's proof is enough to convince them that there is no overlap in the scope. Such a structure is difficult to attack.

Therefore, the above structure allows Alice to simply send a sub-portion of a range it owns. In a sense, this is a "split" of her Ethereum. Next, we want users to be able to "merge" their Ethereum. Assuming Bob has a total of 12 Ethereums, he received Ace from 520 to 523 and from 1001 to 1010. We hope that Bob will be able to pay these 12 Ethereums as a single holistic atom.

With some clever conversions, we can do this: there are no barriers in the network to block a single transaction while specifying multiple ranges for payment. If any of the range displays are invalid, all range of payment requests will be cancelled. The problem here is that the recipient now needs to trace the history of the two ranges above. Of course, if they send all of these ranges plus a portion of the extra range to the other party, then the recipient needs a history of all relevant scopes. Therefore, we gradually began to approach the terminal that required all participants to verify the entire chain. The corner of the "proof size" of the carpet has been tilted up.

To solve this problem, when the size of the history begins to approach a tricky level, each party can "defragment" its scope. They only need to exchange scope with other participants (equivalently) so that the scope begins to integrate as much as possible. One can think of this as a channel rebalance strategy in a payment channel network. Operators with a global view of the entire network can clearly help achieve this goal. We have already discussed several encryption economic mechanisms and defragmentation algorithms to achieve this goal, but which one works best, it needs to be verified in practice.

(Note: Another family of structures, the hybrid channel/Plasma model, can also provide us with greater payment substitutability. This section will continue to be discussed in subsequent articles).

in conclusion

Congratulations, you have achieved the alternative of Plasma! So what should we do next? Is the problem of Plasma already cracked by us? It's hard to say that the above solution is not quite a killer solution, I always feel that there is still not much satisfaction. At the same time, the various technologies in this toolkit may ultimately be enough to achieve a true Plasma chain. Time will tell the answer.

In any case, the research and development of Plasma is still moving at an alarming rate. So when you read this article, you will find that there are more things waiting for you to consider (sorry). Let's see you next time.

Thanks to Ben Rose, Dan Robinson and Georgios Konstantopolous for their discussion and feedback.

Reference link:

Https://www.theblockcrypto.com/2019/03/20/understanding-plasma-part-2-make-plasma-fungible-again/

Author | Daniel Goldman

Source | Contributor Network

Compile | 喏呗尔

We will continue to update Blocking; if you have any questions or suggestions, please contact us!