Hey Dan/Vitalik, would you mind explaining why ZK snarks wouldn’t work to prove ownership of a coin non-interactively?

From what I understand, exit transactions for a coin would be recorded on the parent block-chain, and you would need to prove no exit transactions had been made. So would that not just increase the number of the proofs by a factor of d, the depth of the plasma tree for a coin.

I’m assuming you can’t use any ZK-snarks on the parent chain (which would require trusted setup, and for everyone to share your security assumptions, etc); you can only use ZK-snarks for user-to-user proofs. So the receiving user needs enough data to be able to respond to any possible type (iii) challenge, for when they attempt to exit.

That’s not the hard part of the proof (the Ethereum state root suffices to prove that); you have to prove (directly) that you own the coin at time T, and (cryptoeconomically) that nobody spent that coin on the plasma chain after time T, and that there is a valid history of that output tracing back to the deposit, with no double-spends. That last part is what you need the additional data for; otherwise you can’t respond to a type (iii) challenge (even if you know, through a ZK-snark, that your coin does have a valid history).

They can prove integrity of a history, but a ZK snark does NOT give you the information that you need to fend of challenges in the challenge-response game that tries to prove that there are no earlier correct histories.

Ok thanks. It seems to me, as long as you share information about which coins are being spent every epoch, you can have ZK proofs for non-existence. However, you don’t need to share all the information relating to that coin.

Suppose leaf nodes of the transaction tree were two tiered, with data at the bottom relating to a transaction , and a hash of the data at the top.
Operators could share general data about the whole tree excluding the bottom tier of leaf nodes to the network.

To construct a non-existence proof, you can:
(1) show that your coin is not included in the merkle tree
(2) Suppose wlg. that you have a coin, and someone has just now fraudulently double spent it. You can prove that this person spending the coin could not have been you, the person with (up until now) a valid proof of ownership. We do this by including an extra field in the leaves.

In the bottom tier of the leaf we also include a signature of the hash of the transaction.

We now have two hashes on the top tier, one for the transaction and one for your signature of the hash of the transaction. A non-existence proof is a proof that your signature of the transaction hash could not hash to the value stored and so the transaction is invalid.

I think that is sufficient as a construction to prove that you are the rightful owner of a coin at time t, if indeed you are.

To construct a non-existence proof, you can:
(1) show that your coin is not included in the merkle tree

Yes, but what if A sends a transaction to B, while that transaction is inflight the Plasma chain becomes byzantine, and so the transaction gets included after some unavailable Plasma blocks? Then B does not have the data to prove that the transaction is not a double-spend.

(1) Transactions could contain a block number so it would be impossible to put a transaction in a later block, and generate a proof for it.
(2) If A doesn’t receive the merkle information from the byzantine chain, she could exit before the new block is finalised in the parent block.
(3) We assume it is A’s responsibility to pass on the merkle information to B.

I guess such a scheme might then require proofs of non-existence for withdrawals in the parent chain.

Transactions could contain a block number so it would be impossible to put a transaction in a later block, and generate a proof for it.

So a transaction generated after block N would have N+1 included in them and so could only be included in block N+1? That is brilliant; it actually does remove the need to worry about inflight transactions.

Yeah, this seems like a potential attack even if there is a maxBlockNumber in the transaction. The chain operator could create (but withhold data for) a block, thus griefing everyone sending or receiving coins in that block. If the spent coins eventually attempts to exit, the operator could challenge the exit by revealing the path for the transaction spending that coin.

So maybe you need to restore confirm signatures?

Then you get dramatically worse latency for transaction finality; you have to wait a week or whatever or the previous coinholder is free to withdraw them.

Well, all the proofs considered by the parent chain for exit transactions are interactive (except the one that just identifies the coin being withdrawn). So that’s always the protocol. But I don’t think it helps the griefing attack I describe above, where the plasma chain operator can force users to make invalid withdrawal attempts (and thus lose whatever security deposit you require for those). The only solution for that I see would be to bring back confirm signatures.

That’s not a problem. If the operator challenges the exit, in that process they reveal the Merkle branch that then allows the recipient to exit with the funds unimpeded.

(And I’m not assuming that there are large penalties for attempting an exit that gets challenged here)

All right, although then there’s a griefing/deanonymization/YOLO attack where you make spurious withdrawal attempts on large deposits to force a challenge. But maybe the numbers work out OK.

Along with Vitalik’s suggestion: you can actually include security deposits, but modify the protocol to avoid the griefing attack. Suppose A wants to transfer to B- the idea of the protocol is to give A a way to burn her ownership of a coin once a transfer has been made. A will only burn her coin if data of her transaction is made available from the operator. Let me know your thoughts:

So, A makes a transaction to B. A also sends the operator a signed hash of a random number that is to be included in the leaf node of her coin along with all the other stuff mentioned.
To prove ownership of a coin: B must now also prove that he has the random number that hashes to that value. Now, A will wait until data is available before she gives B the pre-image. As soon as Bob gets the pre-image he broadcasts it to the rest of the network.
If A attempts to exit, we only slash her deposit if the pre-image of her committed hash is revealed by someone.

What’s nice about this scheme is also that no one else can generate a proof of ownership if A is still the real owner, even if the operator misbehaves. A is in complete control of her coin, regardless of the operator’s actions. We can still disincentivise dishonest withdrawals by slashing balances.

This seems equivalent to what I call a “confirm message” in minimal viable plasma; though there is an important optimization here: you just need to reveal a hash preimage instead of verifying a signature.

Has anyone written about how operators of Plasma Cash take fees? I immediately see a few possibilities:

Fees are paid as some small Plasma Cash coin. Users still don’t need to check the entire chain, but this is (potentially) poor UX if we require users to hold a cache of low value coins. However, this is the most “Plasma Cash”-like approach.

Fees are paid as a “fee token.” Fee Tokens are indivisible/non-mergeable tokens that can be validated in the same manner as Plasma Cash (imagine ERC721). Transactions always cost 1 FT. This is similar to (1), except that FT value is determined by some market. Some assumptions are being made there that FTs will typically flow to operators, who will sell them back to users to keep the system running. Wouldn’t want any users to hoard FTs to stall the system. Has the unfortunate side-effect that transactions can’t be given priority based on fee. I need to consider the economics of this one more thoroughly.

Fees are paid in some fungible coin/token alongside the Plasma Cash coins. I couldn’t find a way to make this desirable because you’d inevitably have to verify the entire set of fee transactions. You might be able to separate this from the Plasma Cash chain by creating a “fee chain” where each fee tx necessarily references some Plasma Cash txid. A lot of issues with this construction, not considering complexity.

Every transaction must include a “total fee” in its body. The Plasma chain operator only accepts transactions if their total fee exceeds that of their parent tx, and prioritizes by total_fee - parent_total_fee. When a coin is withdrawn, the amount that can be withdrawn is equal to deposit_size - total_fee.

Though this certainly would ruin nice clean exact-denomination coins.

Another missing alternative here is transaction fees through channel payments.

One potential complexity I see with this construction is the realization of fees. Operators could “exit” on a fee by referencing a specific coin. We’d have to also maintain a mapping on the root chain of coin IDs to total fee claimed. The owner of that coin could then challenge if they prove that latest total_fee - total_fee_claimed is less than sum of all fees claimed on that coin by the operator.

This works for a single operator but becomes more complex if the chain is operated in some way that different operators claim fees individually.

But it definitely does ruin clean exact-denomination coins.

Another possibility is accepting a fee from a separate “fee balance” on the root chain. You’d deposit X ETH (or whatever) into the root contract specifically to be used for fees. Each Plasma Cash tx would specify a fee. Users can then only ever withdraw the fee balance minus the total fees they’ve specified on each transaction. This is never more than what they’ve deposited initially.

A withdrawal from the fee balance would be followed by a challenge period where anyone can prove that the total fees specified by the user is greater than the total fees the user claims to have specified. Operators are the only ones harmed if a user tries to withdraw more than they’re allowed to withdraw because withdrawals can never exceed the current fee balance. Operators already have to validate the entire chain, so they’d have the information required to challenge. Operators just wouldn’t accept a transaction if the user tries to specify a fee that’s greater than their current available fee balance.

Plasma chain operator charges for deposits, then executes transactions for free, using conventional methods to prevent denial of service attacks. This doesn’t really change the trust model because the chain operator can censor whatever they want anyway.

Plasma chain operator also runs a “change service” for which they maintain many very-small-denomination coins (as @kfichter suggested way above); the transaction fee is withheld as part of this.

I think payment channels and cross-chain atomic swaps are pretty difficult on Plasma Cash (even if the spending conditions supported time locks and hash locks) because the channel operator has the power to both censor transactions and withhold data (i.e. a revealed preimage). But I guess you could use a regular ETH payment channel and forget atomicity because the fee amounts are so small.