Technical Guide | Specifications for Plasma Cash Block Structure

One of the most important improvements introduced by Plasma Cash is "light proofs." The Plasma architecture requires users to download the entire Plasma chain to secure their funds. With Plasma Cash, they only need to download the Merkle branches associated with their own funds.

This is achieved by introducing a new transaction validity condition: transactions for a particular CoinID are only valid in the CoinIdth leaf of the Merkle tree. Therefore, downloading only the branch is enough to be sure that there are no valid transactions for the coin. The problem with this solution is that the transaction is a "card" on this denomination: if you want to trade multiple coins, you need multiple trades.

If we put a scope-based transaction into a branch of a regular Merkle tree, the light proofs become unsafe. This is because having a branch does not guarantee that other branches will not intersect:

• Introduction to Blockchain Technology | Atomic Exchange
• How to build a distributed exchange based on atomic interchange technology using Oraclize
• Bai Shuo: From the technical point of view, DeFi feasibility, 3 major challenges, 8 big mistakes, how to crack | 2019 Global Blockchain (Hangzhou) Summit Forum

Both 4th and 6th describe the range of transactions (3, 4). Having a branch does not guarantee that another branch does not exist.

Using a regular Merkle tree, the only way to ensure that no other branches intersect is to download them all and check them. But that is no longer a light proofs!

At the heart of our Plasma implementation is a new block structure and an accompanying new transaction validity condition that allows us to get light proofs for range-based transactions. The block structure is called the Merkle sum tree, where each hash is followed by a sum value.

The new validity condition uses the sum value of the particular branch to calculate the start and end ranges. This calculation is carefully designed so that the calculation ranges of the two branches are unlikely to overlap. Transfers are only effective if their own scope is within this range, so this will return us to our light customers!

This section will detail the specification of the sum tree, the scope of the range calculation, and how to actually construct a sum tree that satisfies the scope.

We have written two implementations of the Plasma-Merkle sum tree: one is done in the operator's database and the other is in memory for testing in the Plasma utility.

Sum tree node specification

Each node in the Merkle sum tree is 48 bytes, as shown below:

[32 byte hash][16 byte sum]

It is no coincidence that the 16-byte length of the sum is the same as the coinID!

We have two auxiliary properties, .hash and .sum, which will bring up these two parts.

For example, for somenode = 0x1b2e79791f28c27ed669f257397e1deb3e522cf1f27024c161b619d276a25315ffffffffffffffffffffffffffffffffffff

We have node.hash == 0x1b2e79791f28c27ed669f257397e1deb3e522cf1f27024c161b619d276a25315 and node.sum == 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

Parental calculation

In a regular merkle tree, we construct a binary tree of hash nodes up to a root node. Specifying and tree formatting is a simple matter of defining a parent (left, right) calculation function that accepts two siblings as arguments.

For example, a regular Merkle sum tree has: parent = function(left,right){return Sha3(left.concat(right))} where Sha3 is a hash function and concat appends these two values ​​together.

To create a merkle sum tree, the parent function must also join the addition of its child functions. Sum value:

Note that parent.hash is a promise for each sibling.sum and hashes: we hash the full 96 bytes of both.

Calculate the extent of the branch

The reason we use the Merkle sum tree is because it allows us to calculate the specific range of branch descriptions and is 100% sure that there are no other valid overlapping branches.

We calculate this range by adding left and right sums to the branch. In each parent calculation, initialize both to 0. If the containing certificate specifies the same level on the right, then right sum+=right.sum; if left sum+=left.sum is added to the left, take left sum+=left.sum.

Then, the scope of the branch description is [leftsum, root.sum-rightsum]. See the example below:

In this example, the effective range of branch 6 is [21+3, 36–5) == [24, 31]. Note 31–24=7, which is the sum of the leaves 6! Similarly, the effective range of branch 5 is [21, 36-(7+5)) == [21, 24). Note that its end is the same as the beginning of branch 6!

You will find that constructing a Merkle sum tree is not possible, it has two different branches covering the same range. At one level of the tree, the sum must be broken! Try to "spoof" leaves 5 or 6 by making another branch that intersects the range (4.5, 6). Fill in only the gray box?

You will find that at some level of the tree this is impossible:

This is how we get light customers. We refer to the branch scope as implicitStart and implicitEnd because they are calculated "implicitly" from the inclusion proof. We implemented a branch checker in plasma-utils via calculateRootAndBounds() for testing and client-side validation checks:

Using smart contracts in Vyper

Note that the range you type is the beginning and end, which is the full 16 bytes.

In a regular Merkle tree, we build the underlying nodes by hashing "leaves":

Given a txa ​​with a single transfera, what should the value be? It turns out that it is not just transfera.end-transfera.start. The reason is that if the transmission does not touch, it will break the scope of the branch. We need to "fill" the sum value to explain this gap, otherwise root.sum will be too small.

Interestingly, this is a non-deterministic choice because you can fill nodes to the right or left side of the gap. We have chosen the following "left justified" scheme to resolve the leaves into blocks:

We call the lowest-level .sum value the parsedSum of the branch, and the TransferProof pattern contains a .parsedSum value that is used to reconstruct the bottom node.

Branch validity and implied NoTx

Therefore, the validity conditions of the branch checked by the smart contract are as follows: implicitStart <= transfer.typedStart <transfer.typedEnd <= implicitEnd. Note that in the original design of the tree in "Plasma CashFlow", some leaves are filled with a special "notx" transaction to indicate that the range has not been processed. With this format, coins that are not traded are only coins within the range of [implicitstart, transfer.typedstart] and [transfer.typednd, implicitend]. Smart contracts guarantee that coins in these ranges cannot be used for any challenge or reaction to exit.

Atomic Multisends

Usually (in order to support transaction fees and exchanges) transactions require multiple transfers to occur either or not, and the result is that each .transfer needs to contain a valid transaction – each .transfer has a specific transfer.typedStart and .typedEnd The effective sum of the. However, for each of these inclusions, it is still a hash of the full UnsignedTransaction – not a single Transfer.hash that is parsed to the bottom.

This article reprints the public number: Blockchain Research Laboratory

The content of Haina College will be centered on: blockchain technology, product community, economic model and other comprehensive knowledge system output. Feel free to contact the author WeChat: csschan1120

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