Plasma snapp - fully verified plasma chain

Layer 2 Plasma
24

Yeah you can definitely handle this if you still keep the challenge period (someone can prove the balance is wrong). That would be the “simplest” use of these proof systems for Plasma, IMO. Would also remove the need for the operator to submit the balance along with each withdrawal.

1 Like
25

In the following I am reformulating everything using epochs. In the above proposal, I was requiring that the receiving party was online for every block, in which (s)he was receiving a transaction. In the following, the assumptions are milder: The receiving party needs to be online only once an epoch for receiving the transaction.

Plasma snapp:

TL;DR

The following specification outlines a new plasma version which utilizes snarks to prove its integrity and validity. Via an interlinking between exit requests and deposits with the correctness proof of a block - the snark -, we are able to specify an implementation without any need for exit challenge games and confirmation signatures. Unfortunately, the concept of exit queues is still needed.

Removing the exit games and confirmation signatures allow us to remove much of the complexity of plasma, which is currently hindering the implementation of more sophisticated protocols beyond simple token-transfers. This proposed version will facilitate to integrate more protocols into plasma by making the snarks itself handling these protocol advancements.

Introduction:

Over the last half a year, there has been made tremendous advancements regarding fully verifiable plasma chains. New signature mechanism and hashing mechanism were found, helping to reduce proving times significantly.

These advancements enable the following with reasonable timings:

  • storing the complete state of a plasma chain encoded as a StateRootHash on ethereum

  • this StateRootHash can be updated by a central operator by providing a snark proving a valid state transition

  • A valid state transition is proven within the snark by opening one or several leaves of the merkle tree describing the current state, checking the user’s signatures, doing predefined operations, updating the leaf and finally recalculate the stateRootHash.

How this can be in done in detail, you can find over here: [https://github.com/barryWhiteHat/roll_up

](https://github.com/barryWhiteHat/roll_up)

However, snarks do not solve the problems associated with data unavailability. Also, the snarks need to be aware of any incoming deposit request to the plasma chain and outgoing withdrawal requests. This post will describe a solution for these two remaining issues.

Proving valid state transactions

In this model, the state is described by leaves of the StateMerkleTree. Each leaf is a list of a

[public key, amount of token, epoch of last transfer].

The epoch is an increasing number, which increases after processing k blocks, which have transfers.

The plasma contract is aware of the current state, as we store it as the variable StateRootHash in the contract.
State transitions are tracked on the smart contract via the list of StateRootHashes:
StateRootHash_1 -> StateRootHash_2 -> … -> StateRootHash_n.
The plasma contracts also stores the verification keys of the snarks of 3 different programs: P_transfer, P_deposit, and P_exits for 3 different kinds of state changes. These verification keys allow the plasma contract verifying that the state changes for a new block are actually valid ones.

Let us call the program checking the correctness of a state transition based on transfer P_transfer:

P_transfer(StateRootHash_i, current epoch, [witness transactions data]) = (StateRootHash_(i+1))

A transaction is a value transfer from one leaf to another leaf. P_transfers checks the following:

  • Leaf of sending account exists

  • Leaf of sending account has the needed balance for transfer

  • The transfer transaction is signed by the private key associated with the public key stored in the sending leaf and the transaction is intended for the current epoch

  • Subtracts balance from sending leaf, updates the epoch of last transfer, updates the StateRootHash

  • Leaf of receiving account exists

  • Owner of receiving account accepts updating the epoch of last transfer for the current epoch

  • Updates balance and epoch of last transfer of receiving account

The witness transaction data will be used by the snark proof, but they will never touch the rootchain. It is only needed to create once the witness of the snark.

This is pretty straightforward. But how do we make the plasma chain aware of deposits and withdrawal? We think the following trick will do the job:

The information of several deposits, which are sent to the plasma contract, can be hashed together to a depositHash by the plasma contract. By requiring the snark proof to take the depositHash as a public variable, we can enforce the snark proof to process all deposits.

The program P_deposit checking the correctness of deposits would look like this

P_deposit(StateRootHash_i, DepositHash_i, [witness deposit data]) = (StateRootHash_(i+1))

A deposit is a value transfer into an empty leaf. Whether a leaf is empty, we will store on the ethereum mainchain in a mapping: leafOccupation. P_deposit does the following:

  • Insert public key and deposit amount into the leaf

  • Updates the StateRootHash

The same can be done for exits: All exit requests can be collected by the plasma contract. The operator submits for each exit request the currently withdrawable balance from the plasma chain. Then these information are hashed together in an exitRequestHash and by making it a public input the snark, we can enforce the snark to process this exit request.

P_exit(StateRootHash_i, ExitRequestHash_i, current epoch, [witness exit data]) = (StateRootHash_(i+1))

A withdrawal tries to exit all balance out of a leaf. The snark checks the following:

  • Leaf has not sent or received a transaction within the last 14 epochs. (If this would be the case, the operator would have to set the predefined withdraw balance to 0, and the snark would be exited.)

  • Leaf currently stores exactly the predefined balance

  • Deletes the complete leaf, updates StateRootHash

Unfortunately, exits with a fraction of the balance are not supported by this protocol.

Note that the operator needs to set the withdrawal balance, as only he knows for sure the current balance. Still, the snark enforces the operator to set the correct balance, as otherwise he will not be able to find a proof. If someone makes an exit request, which is not valid, the operator will set the balance in the exit to 0. Exit request against non-occupied leaves are prevented by the plasma smart contract.

These three different programs allow the operator to append the plasma chain with 3 different block types (deposits, transfers and exits) by sending over the respective snark prover key. The plasma smart contract would enforce that registered pending exits would be processes at first, forcing the operator to submit exit blocks, before deposit or blocking transfer blocks. Likewise, if there are deposits pending since several blocks, then the plasma contract would force the plasma operator to include deposit blocks, before any transfer blocks are accepted. Only if there are no pending deposits or withdrawals, then the plasma chain allows appending transfers blocks.

Roll back of the tip of unavailable chains

This above construction interlinks very well deposits and exits with the snark proofs. Unfortunately, it can not prevent the data unavailability case. It could always happen that the operator would publish a StateRootHash and nobody knows the content of this new state. Using priority queues for exits and an unwinding mechanism, we can solve the problem:

If the chain operator stops publishing new valid blocks for 3 days, then the plasma root chain contract would allow swapping the operators. Then anyone else can extend the plasma snapp chain provided that the new operator hands in valid snark for his new blocks.

If no one can build on the tip of the plasma chain, then the last block of the plasma chain will be removed and we wait for people building on the second-highest block. We will continue this removal process of the plasma chain tip, until it is extended again by another operator. If clients are storing all the data of the plasma chain, then they could always become the operator themselves in such a situation. Thus, if they do not agree with the reversal of a block of the chain tip, they need to become the operator. This is a fair mechanism, as everyone can stop the roll back of the history.

Payment receivers should only acknowledge their payment as accepted, once they have the complete new state of the plasma chain. Then they could theoretically always prevent the roll back of their received transaction by becoming the plasma operator themselves.

Becoming a plasma operator is a heavy task, but on the other side, we could also incentivise this heavily by slashing the original operator and rewarding the new operator with these slashed funds: During the plasma chain creation, the operator has to make a deposit of x ether. If the plasma chain was stopped and the operator swapped, then the new operator would receive a fraction of this ether per submitted valid block. This ensures that the plasma chain is continued for quite some time after the original operator was switched and everyone has the chance to leave the chain.

But there is one hook, rolling back transactions of unavailable blocks might be fine, but unwinding withdrawals is not possible. However, there is a workaround: We require that

  • Exit requests are bundled into epochs: Each epoch can contain maximal x transfer blocks. Only if all withdrawal request in a epoch are processed with exit blocks, then the plasma smart contract will allow the withdrawal of the actual funds.
  • Exits will be included the earliest into an exit block 14 epochs after the last touch of the leaf, from which the funds should be withdrawn.
  • In order to have full security, users have to exit their funds at least 14 epochs after the data unavailability detection

If a users wants to withdraw, he sends a request to the plasma root-contract with the epochnr: the epochnr of last touch. The plasma contract then requires the snark to process this exit exactly at the epoch min(epochnr + 14, current epoch + 1).
Especially the plasma smart contract will make sure that a transfer block from the next epoch: epochnr + 15 is not accepted before the all exits from the epochnr+ 14 are processed.

Using this delayed mechanism, users funds are safe:

Imagine the block k within the epoch n is the first unavailable block.

  1. If the operator keeps on building blocks, but stops building new blocks before the epoch n+14 is finished, then all exits processed must be “old” transaction, which are anyways were not touched since the data unavailability. Even when blocks are unrolled until n, we require the new chain with the new blocks to include the same exits, but without paying for the exits again. Thus no funds are lost.

  2. If the operator keeps on building blocks and goes beyond the epoch n+14, then every user should have already registered their exit and the plasma contract would have made sure that it would have been withdrawn. The operator could then potentially revert his transaction without reverting the withdrawal, but since all users anyways have already withdrawn their funds, nothing would be left to steal.

Note: In order to make this mechanism work, everyone needs to know when their transaction might have been included into the plasma chain. Especially, the scenario needs to be prevented where the operator produces unavailable blocks and includes in these blocks old transactions of somebody and thereby prevents this person to withdraw. Hence, every transaction submitted by a customer should be valid only for a specific epoch. This will be checked by the snark.

Note2: A malicious operator could top up the balance of other users to touch their leaves in the unavailable block, and thereby preventing regular users to exit within 14 epochs. This attack vector can be migrated by requiring the operator to hand over to the snark as witness a message signed from the receiving party: "I am okay with receiving funds in epoch x".

Note3: This specification has the nice property that we can use any hash function for the state merkle tree within the snarks, as these hash functions do not need to be executed in the evm at all. This is a huge benefit. Only the deposits and exits need to be done with kecca, as here the evm will need to execute them as well.

3 Likes
26

Interestingly, proposed by @PhABC, the exit window can be made deterministic and ‘less Schrodinger’s cat’, in the cases where the operator of the chain is compliant, you can use a transaction to change the leaf to a special ‘exit value’ which allows you to exit on-chain without any challenge window. Think, if you burn ETH by sending it to ‘0x0’, it can never be recovered; the equivalent to exit the side-chain is to make the operator update a leaf you own to a special value which you can prove on-main-chain as being an exit.

e.g. I create a transaction which updates the leaf value to H(0, my-ethereum-address).

Then on-chain I prove the merkle tree path to the leaf in the root published by the operator, the contract checks merkle_prove(H(0, msg.sender), path) matches a root, then it nullifies that leaf index to make it un-exitable again, and the user receives their coin.

In the happy path, this makes on-chain exits very quick and with much less uncertainty, and with the worst case you have normal plasma exits.

27

Hi Harry,

Yes, nullifying the withdrawn leaf is already part of my proposal.

But unfortunately, I can not allow very quick exits, as this will create a problem. If we would allow quick withdrawals, then the operator could generate unavailable, valid blocks and send funds from old leaves to new ones. Then he would do the quick withdrawal on the new leaves, but later roll-back the unavailable blocks. Via the unroll mechanism, he would then also be able to withdraw from the other new leaves. That is why I am requiring people to withdraw funds only after ‘epoch of last touch of the leaf + 14 epochs’. IN this case everyone has enough time to withdraw before the operator can withdraw funds from his new leaves.

But if we would not roll-back, maybe we would get into a better situation.

28

I was going under the assumption that each leaf represents a non-fungible token, and without any possibility of transferring funds from one leaf to another, or the value of a leaf chaning - only the owner of a leaf would change.

If only the owner of the leaf changes then there is no problem with duplication of funds via the rollback mechanism and you can have fast/instant exits.

1 Like
29

Version 0.3
This new version has the big advantage that the receiver does not need to be online at all. Still, he epoch version might be better for more sophisticated protocols than just transfers, as eg. exchanges.
In this new version, the exit priority is no longer based on the last touch of the owners leave. It is calculated based on the height of the plasma chain block, from which a user wants to withdraw.

Plasma snapp:

TL;DR

The following specification outlines a new plasma version which utilizes snarks to prove its integrity and validity. Via an interlinking between exit requests and deposits with the correctness proof of a block - the snark -, we are able to specify an implementation without any need for exit challenge games and confirmation signatures. Unfortunately, the concept of exit queues is still needed.

Removing the exit games and confirmation signatures allow us to remove much of the complexity of plasma, which is currently hindering the implementation of more sophisticated protocols beyond simple token-transfers. This proposed version will facilitate to integrate more protocols into plasma by making the snarks itself handling these protocol advancements.

Introduction:

Over the last half a year, there has been made tremendous advancements regarding fully verifiable plasma chains. New signature mechanism and hashing mechanism were found, helping to reduce proving times significantly.

These advancements enable the following with reasonable timings:

  • storing the complete state of a plasma chain encoded as a StateRootHash on ethereum

  • this StateRootHash can be updated by a central operator by providing a snark proving a valid state transition

  • A valid state transition is proven within the snark by opening one or several leaves of the merkle tree describing the current state, checking the user’s signatures, doing predefined operations, updating the leaf and finally recalculate the stateRootHash.

How this can be in done in detail, you can find over here: [https://github.com/barryWhiteHat/roll_up

](https://github.com/barryWhiteHat/roll_up)

However, snarks do not solve the problems associated with data unavailability. Also, the snarks need to be aware of any incoming deposit request to the plasma chain and outgoing withdrawal requests. This post will describe a solution for these two remaining issues.

Proving valid state transactions

In this model, the state is described by leaves of the StateMerkleTree. Each leaf is a list of a

[public key, amount of token, blockheight of last transfer].

The plasma contract is aware of the current state, as we store it as the variable StateRootHash in the contract.
State transitions are tracked on the smart contract via the list of StateRootHashes:
StateRootHash_1 -> StateRootHash_2 -> … -> StateRootHash_n.
The plasma contracts also stores the verification keys of the snarks of 3 different programs: P_transfer, P_deposit, and P_exits for 3 different kinds of state changes. These verification keys allow the plasma contract verifying that the state changes for a new block are actually valid ones.

Let us call the program checking the correctness of a state transition based on transfer P_transfer:

P_transfer(StateRootHash_i, current block, [witness transactions data]) = (StateRootHash_(i+1))

A transaction is a value transfer from one leaf to another leaf. P_transfers checks the following:

  • Leaf of sending account exists

  • Leaf of sending account has the needed balance for transfer

  • The transfer transaction is signed by the private key associated with the public key stored in the sending leaf and the transaction is intended for the current block height

  • Subtracts balance from sending leaf, updates the epoch of last transfer, updates the StateRootHash

  • Leaf of receiving account exists

  • Updates balance of receiving leave

The witness transaction data will be used by the snark proof, but they will never touch the rootchain. It is only needed to create once the witness of the snark.

This is pretty straightforward. But how do we make the plasma chain aware of deposits and withdrawal? We think the following trick will do the job:

The information of several deposits, which are sent to the plasma contract, can be hashed together to a depositHash by the plasma contract. By requiring the snark proof to take the depositHash as a public variable, we can enforce the snark proof to process all deposits.

The program P_deposit checking the correctness of deposits would look like this

P_deposit(StateRootHash_i, DepositHash_i, [witness deposit data]) = (StateRootHash_(i+1))

A deposit is a value transfer into an empty leaf. Whether a leaf is empty, we will store on the ethereum mainchain in a mapping: leafOccupation. P_deposit does the following:

  • Insert public key and deposit amount into the leaf

  • Updates the StateRootHash

The same can be done for exits: All exit requests can be collected by the plasma contract. The user submits the exit request to the plasma contract by submitting his address and the height at which he would like to withdraw. This height is in most cases the first unavailable block. The operator is required to react upon each exit request by submitting the withdraw-able balance of the requested height from the plasma chain. Then these information [address, balance, StateRootHash of block of height for request] are hashed together in an exitRequestHash and by making it a public input the snark, we can enforce the snark to process this exit request.

P_exit(StateRootHash_i, ExitRequestHash_i,[witness exit data]) = (StateRootHash_(i+1))

A withdrawal tries to exit all balance out of a leaf. The snark checks the following:

  • Leaf has not sent out a transaction in the last 40k transfer blocks (equals 7 days) or withdrawal balance is 0
  • Leaf stored exactly the predefined balance at the specific height or withdrawal balance is 0.
  • Either the leaf in the latest state does not have a higher block-height of last transfer as the block-height, from which we are currently withdrawing or withdrawal balance must be 0.
  • Deletes the complete leaf, updates StateRootHash

Unfortunately, exits with a fraction of the balance are not supported by this protocol.

Note that the operator needs to set the withdrawal balance, as only he knows for sure the current balance. Still, the snark enforces the operator to set the correct balance, as otherwise he will not be able to find a proof. If someone makes an exit request, which is not valid, the operator will set the balance in the exit to 0. Exit request against non-occupied leaves is prevented by the plasma smart contract.

These three different programs allow the operator to append the plasma chain with 3 different block types (deposits, transfers and exits) by sending over the respective snark prover key. The plasma smart contract would enforce that registered pending exits would be processes at first, forcing the operator to submit exit blocks, before deposit or blocking transfer blocks. Likewise, if there are deposits pending for several blocks, then the plasma contract would force the plasma operator to include deposit blocks before any transfer blocks are accepted. Only if there are no pending deposits or withdrawals, then the plasma chain allows appending transfers blocks.

Roll back of the tip of unavailable chains

This above construction interlinks very well deposits and exits with the snark proofs. Unfortunately, it can not prevent the data unavailability case. It could always happen that the operator would publish a StateRootHash and nobody knows the content of this new state. Using priority queues for exits and an unwinding mechanism, we can solve the problem:

If the chain operator stops publishing new valid blocks for 3 days, then the plasma root chain contract would allow swapping the operators. Then anyone else can extend the plasma snapp chain provided that the new operator hands in valid snark for his new blocks.

If no one can build on the tip of the plasma chain, then the last block of the plasma chain will be removed and we wait for people building on the second-highest block. We will continue this removal process of the plasma chain tip until it is extended again by another operator. If clients are storing all the data of the plasma chain, then they could always become the operator themselves in such a situation. Thus, if they do not agree with the reversal of a block of the chain tip, they need to become the operator. This is a fair mechanism, as everyone can stop the rollback of the history.

Payment receivers should only acknowledge their payment as accepted, once they have the complete new state of the plasma chain. Then they could theoretically always prevent the rollback of their received transaction by becoming the plasma operator themselves.

Becoming a plasma operator is a heavy task, but on the other side, we could also incentivize this heavily by slashing the original operator and rewarding the new operator with these slashed funds: During the plasma chain creation, the operator has to make a deposit of x ether. If the plasma chain was stopped and the operator swapped, then the new operator would receive a fraction of this ether per submitted valid block. This ensures that the plasma chain is continued for quite sometime after the original operator was switched and everyone has the chance to leave the chain.

But there is one hook, rolling back transactions of unavailable blocks might be fine, but unwinding withdrawals is not possible. However, there is a workaround: We require that

  • Exits are processed only 40k transfer-blocks (7 days) after max( block-height of last transfer in leaf, block-height of plasma chain block, from which the balance should be read).
  • Exit requests are bundled per block: Only if all withdrawal requests from a certain block-height are processed, then the plasma smart contract will allow the withdrawal of the actual funds.
  • In order to have full security, users have to send an exit request for their funds at least 40k blocks after the data unavailability.

If a users wants to withdraw, he sends a request to the plasma root-contract with the blockheight n: the blockheight of the plasma chain from which his balance should be withdrawn. In the unhappy case, this would be the first unavailable block. The plasma contract then requires the operator to process this exit before the operator could hand in the transfer block of height max( block-height of last transfer, block-height of actual withdrawal request).+40k +1.

Using this delayed mechanism, users funds are safe:

Imagine the block n is the first unavailable block.

  1. If the operator keeps on building blocks but stops building new blocks before the block n+40k is finished, then all exits processed must be “old” accounts, which either were not touched since the data unavailability or the users are not aware of the . Even when blocks are unrolled until n, we require the new chain with the new blocks to include the same exits, but without paying for the exits again. Thus no funds are lost.

  2. If the operator keeps on building blocks and goes beyond the n+40 k, then every user should have already registered their exit and the plasma contract would have made sure that it would have been withdrawn. The operator could then potentially revert his transaction without reverting the withdrawal, but since all users anyways have already withdrawn their funds, nothing would be left to steal.

Note: In order to make this mechanism work, everyone needs to know when their transaction might have been included into the plasma chain. Especially, the scenario needs to be prevented where the operator produces unavailable blocks and includes in these blocks old transactions of somebody and thereby prevents this person to withdraw. Hence, every transaction submitted by a customer should be valid only for a specific block. This will be checked by the snark.

Note2: This specification has the nice property that we can use any hash function for the state Merkle tree within the snarks, as these hash functions do not need to be executed in the evm at all. This is a huge benefit. Only the deposits and exits need to be done with keccak, as here the evm will need to execute them as well.

30

Hey @josojo,

great job making the spec!

Have you seen the spec for roll_up (also WIP)?

What we realized in discussions is that roll back of unavailble chains can be used for mass exit acceleration, but you still need something like Plasma Cash exit guarantees. Otherwise a malicious operator can withdraw more money then she owns during the rollback steps, because nobody has data to challenge her.

The most viable model we’re looking at is Plasma Debit. It combines the possibility of arbitrary balances with strong guarantees in case of plasma exit, but comes at a cost of additional capital required on the operator side.

31

Because we cannot enter invalid states we are able to restart the chain from a previous state. We can also roll back and withdraw everyone who requests it before we restart it.

What we realized in discussions is that roll back of unavailble chains can be used for mass exit acceleration, but you still need something like Plasma Cash exit guarantees. Otherwise a malicious operator can withdraw more money then she owns during the rollback steps, because nobody has data to challenge her.

We don’t have to do full plasma exit games as we know that the current state is correct. So we can process withdraw much faster. We can also start rolling back the chain until we get to a point where we can restart. If we roll all the way back to the inital state we will probably need plasma exit to allow anyone who missed the inital exit request deadline to exit.

Have you seen the spec for roll_up (also WIP)?
@josojo would like your input on this spec. Hope to get it in decent state and then post it here.

32

Right. What I meant with Plasma Cash is that you need a guarantee that a certain piece of value is only exited once, which doesn’t work well if the lead data model is [balance, nonce] only.

33

I have a fundamental question regarding the popularity of snarks in plasma. Do we really think that a trusted setup is desirable? If there are a hundred flavors of plasma all using snarks, can we be sure that all have disposed of the lambda thoroughly?

If not, we will get into a state where one or two snark chains are discovered to have created fake proofs for a few months and the system will lose credibility.

I don’t see snarks being useful to remove the need for trust. The temptation to create a chain while hanging on to the power to fake a proof will eventually manifest. We basically have paypal level of trust if the developers create the lambda.

I also don’t see what snarks give you except succinctness. You can pay a bit more for additional parameters and avoid the trusted set up altogether.

34

The above seems to be a dangerous restriction. Can an attacker keep sending a tiny balance to an account to prevent it from ever withdrawing?

1 Like
35

I don’t see snarks being useful to remove the need for trust . The temptation to create a chain while hanging on to the power to fake a proof will eventually manifest. We basically have paypal level of trust if the developers create the lambda.

As many of these designs get closer to an implementation ready state it could make sense to run a MPC ceremony similar to the ZCash Powers of Tau ceremony except the code would need to be modified to support the alt_bn128 curve in Ethereum since at the moment the code only supports BLS12-381-Groth16. If this change is made, then anyone could participate in the generation of shared partial parameters which then can be used in a phase 2 ceremony to generate the parameters for specific application arithmetic circuits (sounds like this can be done in parallel for many circuits) i.e. many of these proposed Ethereum applications that use snarks. See this mailing post for more info: https://lists.z.cash.foundation/pipermail/zapps-wg/2017/000115.html

I also don’t see what snarks give you except succinctness. You can pay a bit more for additional parameters and avoid the trusted set up altogether.

At least in a Plasma context, snarks put stricter constraints on the operator since invalid state transitions are no longer possible (but censorship and data availability issues still remain).

2 Likes
36

P_transfer(StateRootHash_i, current block, [witness transactions data]) = (StateRootHash_(i+1))

I’d like to learn a bit more about how state can be cheaply transitioned. If this occurs once a block it may be cheap enough. Do you have any code samples that can give us more info?

The operator is required to react upon each exit request by submitting the withdraw-able balance

What happens if the operator does nothing for one of the withdraw requests?

37

We have not yet started the implementation. We first wanted to think this through theoretically. But, take a look at the roll_up project linked in the original post. They have already POC code for a simplified version, being closer to plasma cash.

We can track that onchain and prohibit other block productions than withdrawal blocks. This forces to the operator to process the chain or halt the chain completely.

38

Hey @josojo,

Congratulations, this is great! I wonder if the following idea solves the data-unavailability problem of this proposal:

Let’s say along with a StateRootHash, we also store a TouchedLeaves property for each block, which is a bitmap that shows which leaves of the state merkle-tree were affected in the corresponding state transition. E.g. if my state merkle-tree has just 4 leaves, and some state-transition in block 5 changed the balance of third leaf, TouchedLeaves[5] would be 0010, we ensure the validity of this bitmap by feeding it to our SNARK:

P_whatever(StateRootHash_i, [witness data]) = (StateRootHash_(i+1), TouchedLeaves_(i+1))

Users can now exit from StateRootHash of an older block, if the corresponding bit of their account is not 1 in all next blocks. So, if the operator submitted a block and didn’t give the merkle-proofs to its users, they don’t have to exit their coins only from the latest state.

39

We can also do something like this:

  • An account can only exit from the block which his latest update has occurred. (We know this since we have the TouchedLeaves bitmap for each block in public) So if the latest update on my account has occurred in the 5th block, I can only withdraw my funds by giving the state merkle-proof of my account in that block)
  • We require the operator to provide a SNARK, showing that all of the accounts that are updated in a certain block have signed the state-hash of that block (An account would only sign the hash of a block if he has the merkle-proof of that block)

Using this scheme, I can always be sure that I can withdraw my funds from the latest state of my account. Although this may solve the data-unavailability case of your proposal, it requires the payment receiver to be online (As the reciever needs to sign the new state-hash). The operator should also do a SSTORE (~20K gas) per block, per 256 accounts, which I think is not a big overhead.

1 Like
40

Hey @Keyvank,

good ideas :heart_eyes:. Here are some comments.

What happens if the operator receives your transaction and processes your transaction with many unknown transactions generated by himself in a block n. Then for this next block n, the output bit for your leaf would be 1. So you would have to withdraw at least from block n. But you don’t know any Merkle proof of this since you only know your transaction, but not all the other transactions, right?

First thought:
Unfortunately, this opens an attack surface against the operator. I could send the operator transactions, and then I don’t do any double signing. This would force the operator to restart the whole block proposing mechanism.

Second thought:
If people would not double sign the hash of the next state, but rather the hash of all transactions from the block, then we could avoid this ddos attack.
We could do it like that:

  • users send transactions to the operator

  • operator bundles transactions and gets a double-signing from the users of this transaction-bundle(signing of the hash of all transactions).

  • The snark would make sure, that only transactions are processed in the next block, for which the owner has double signed the transaction-bundle. ( Here, the set of processed transactions is a strict subset of the initial transaction-bundle)

  • If there are not too many transactions, anyone can brute-force which transactions were actually included by the operator and thereby recalculate the next ‘StateRootHash’ for the next block. If one does not want to rely on brute-force, the operator could be required to publish further data.

This approach of transactions-double-signing would help to withdraw from the latest block for people involved in the latest block. If this is combined with the touchedLeaf-bitmap, this would solve data-unavailabilities problems with the costs of reintroducing double signing. I think this is pretty cool.

One more thought:
Instead of working with touchedLeaves bitmaps, it might be possible to work with RSA-accumulators to encode a touch of a leaf more efficient.

1 Like
42

Wow, that was neat, guess your idea solves this, but I’m a little bit worried that it would make our circuits complicated. Do you have any approximations on how hard would it be for the operator to generate proofs for this? Are those circuits even feasible to construct in SNARKs?

Didn’t understand this part actually.

I guess we can’t use an encoded version of this bitmap here (RSA accumulators/Merkle-trees etc), because it would need a proof and brings back all the data-availability problems we had. So this touched-leaves thing should be completely public, and a bitmap is the most compact way of storing it (In case the number of txs were small, we can send the list of account-ids instead of the entire bitmap)

If all these works I guess roll-backs are not needed anymore. Right?

43

I think the only special circuits for this would be hashing and signature verification. This is for sure available.
It’s hard to give any approximations, my gut feeling is that it wouldn’t increase the required circuits by a factor of 2x

If a participant signs the proposed transaction bundle for the next block, the participant knows which transaction can be in the next snapp. But still, they don’t know exactly, which ones will be included, as they can not prediction who double signs their transactions. However, in order to calculate the next state, he needs to know exactly, which transaction was included.
The participant would usually get this information from the operator, but if he does not get the information, he can find these transactions by trial and error.

I don’t see the data unavailability problem araising here:

Either your transaction is in a block, but then you have double signed it and know the data, or your transaction is not in the block, but then you can generate the exclusion proof without knowing the actual data from this block. (I have never seen rsa accumulators in a snark, this might not be possible at all and needs further investigation)

1 Like
44

The issue with this double signing is that user need to be online, each time their balance sheet is touched(even if they are only receivers). So, if double signing works out, snapp developer could choose whether they prefer roll-backs or double signing. Both options might be cumbersome for the users :slight_smile:

1 Like