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.
A few thoughts, please correct me if I am wrong:
(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.
How is N+1 counted? Would have to ignore deposit/exit blocks.
Also, what if the tx is included in block N+1, N+1 is published to the root chain but withheld?
You could just have the parent chain broadcast the hash of the merkle tree and wait a period of time, allowing others to withdraw, before it commits.
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.
Ok, thats fair.
If A gives a proof till the current block it is universally accepted.
A can still give a proof of coin till t, which can be overridden by B if he has a proof of the coin at t+1.
…
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:
Here’s a very simple proposal:
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.
Other options:
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.