What if a block contains two transactions that spend the same coin?
In my design, not possible. The transaction’s position in the Merkle tree must be the ID of the coin, so you cannot have two transactions in one block that spend the same coin.
4 Likes
Would coin ID => denomination be stored as a mapping on the root chain? That would limit the minimum viable deposit. You might be able to improve ux/decrease gas cost with a “change machine,” i.e. insert n root chain tokens/ETH and receive m coin IDs each with value n/m.
Also, how are transactions actually validated? Something like this?
- Validate that each transaction in the history I was given is actually included in its corresponding block with a Merkle membership proof and then
- Validate each proof of non-inclusion
I’m also interested in understanding how the non-inclusion proofs are generated.
Would coin ID => denomination be stored as a mapping on the root chain?
Yes.
I’m also interested in understanding how the non-inclusion proofs are generated.
A non-inclusion proof is basically a proof that there exists an object at the given position in the Merkle tree, and this object is empty data.
Basically yes.
Could the coin ID => denomination mapping be deterministic, e.g. create a complete binary tree of height 31, label each node with a 32-bit id and the denomination of a coin is 2^h where h is the height of its id in the tree. Users can only deposit in powers of two, there is an upper bound on the total amount that the chain can hold, and are allowed to split coins in half and merge them. A constraint is maintained that along each root-to-leaf path only one coin can be issued.
I don’t see why you couldn’t also just make it a non-binary tree. Say root node is worth some large value, second layer splits the value into many usable chunks (n 100 ETH coins), then each broken down into more (five 20 ETH coins), etc. etc.
How would this work? Would the user have to own the specific two consecutive coins in order to merge a layer up?
David Knott and I discussed a “merge/split” transaction where a user could point to specific coin IDs they own (by referencing outputs) and reshape them into new coin IDs that have different denominations but the same total value. This maintains the property that only specific users can be grieved (owners of those coin IDs). The transaction would require a challenge period much like the Plasma MVP exit transaction. A merge/split is invalidated under the same conditions as
This construction would allow users to modify their coins without having to exit and deposit again.
I also started thinking about the idea of “change providers” - users who carry a large amount of change to assist in transactions where one or both parties can’t make correct change. To illustrate:
Alice wants to send 7 ETH to Bob, but doesn’t have a 7 ETH coin. Alice has a 10 ETH coin and some smaller coins. Bob does not have a 3 ETH coin to send in return. Carol is a change provider who happens to have both a 7 ETH coin and a 3 ETH coin. Alice and Carol construct a transaction in which the following ownership transfers occur:
- Alice sends a 10 ETH coin to Carol
- Carol sends a 7 ETH coin to Bob
- Carol sends a 3 ETH coin to Alice
- Alice sends some small ETH coin to Carol as a fee
This last fee component is obviously the complicating factor, as it requires Alice to have some specific small ETH coin on hand to make the transaction. In the absence of a change provider, Alice could use the merge/split transaction mentioned above to convert her 10 ETH coin into 7 ETH and 3 ETH coins to transact with Bob. However, this is significantly slower due to the challenge period.
1 Like
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).
2 Likes
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.
1 Like
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.
1 Like
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)
2 Likes
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.
3 Likes