I don’t think it needs to. The challenger can just watch to see if a withdrawal exceeds the amount they know was allocated to the ancestor, in which case they know and can prove the withdrawal is fraudulent.
Yes, but I think this can be enforced cryptoeconomically. An attempt to spend a ancestor or descendant of a previously withdrawn coin can be challenged by revealing the withdrawal. The contract just keeps track of the remaining balance in X.
This still seems underspecified. What I am worried about is this scenario: say there are coins X.00, X.01, X.10, X.11, each with 2 eth, and I own X.00. Let’s say X.01, X.10 and X.11 are colluding. X.11 exits 2.1 eth, and I don’t notice anything wrong (since our LCA is X, and 2.1 < 8). After that confirms, X.01 and X.10 both submit withdrawals. I must be able to somehow prevent all of them from succeeding. In this case, I can prove to the contract that X.1 was worth 4 eth, and the confirmed exit of X.11 and the in-flight exit of X.10 total more than 4 eth. This does imply that I have to watch every single exit of X.something, which means that a coin with t telomeres each belonging to a separate owner the overhead is t^2, which is suboptimal.
Dang, you’re completely right. To do it cryptoeconomically, users would need
to keep track of running balances of their siblings and uncles, and store all those withdrawal transactions (only like N log N total though, I think, so not TOO bad) in case they need to reveal them to challenge something. There are maybe other ways to do it that involve tracking the balance in a Merkle sum tree on the parent chain… would have to think about the tradeoffs.
We are implementing an exchange using plasma and we bumped into some issues:
Its unclear how an exchange could use plasma cash without fungibility. If I want to buy size 3 but there are only sellers of size 2 and 5, there is no match. This implies we cannot write a matching engine that works as expected (ie price-time priority, etc)
Challenge of type (iii) is unclear. From my understanding, an invalid output A can be created and spent into B and then into C (all owned by same user colluding with operator) i.e A->B->C. C is withdrawn providing B and C. A may be withheld (not published). How would challenge (iiii) be made? Even if A were published, can the challenge be blocked by providing B?
I see a few sharding proposals here. I think they are fundamentally flawed if coins from shard A cannot be sent to shard B. The network effect of money is lost completely. I have no interest in coins that I can only spend at certain places. This will make shards the equivalent of gift-cards.
The right sharding approach should shard the processing but not the network.
The idea is that most people would deposit with coins of a specified size, similar to existing real-world denominations (1, 2, 5, 10, 20, 50…)¸ and there would be specialized exchangers that can convert many small-denomination coins into larger-denomination coins.
How would challenge (iiii) be made?
As I am understanding, the idea is that the chain creates an invalid output A, then a child of A, B, then a child of B, C, and then tries to exit C.
I would challenge by providing the parent of A.
I think they are fundamentally flawed if coins from shard A cannot be sent to shard B.
Our sharding proposals definitely don’t have that property; there’s an entire line of research around how to make cross-shard transactions maximally efficient.
What if A is deposit on root chain that is supposed to create a new coin? Do deposits on root-chain have parents?
If A is a deposit on the root chain, then A can’t be invalid.
If A is a deposit on the root chain, then A can’t be invalid.
Im just claiming A exists. Lets say there are 20 different coins from real deposits on root chain. Im claiming A is the 21st coin (doesn’t really exist on root and not published). How can challenge (iii) be submitted?
I’m guessing that naive way out of this is to require the root chain entry and entire coin history MUST be provided for every withdrawal.
Of course A,B,C is the shortest chain but nothing prevents the operator from creating 10K transfers before attempting a withdrawal. This would create a very large withdrawal tx.
The point is that the first invalid or unavailable transfer in the chain is not a deposit, and so it has a parent (which is valid and available), and so a challenge can be done based on that.
Late response, I think the merged token ID is an issue here. If each merged token has a unique ID, then (I think?) we have \sum_{r=2}^{n}{C(n,r)} unique IDs. This is only an issue if the Merkle tree is sparse. We can still prove non-existence in the tree if the leaf nodes are sorted, but the proof becomes more involved.
Sorry, I don’t follow. If two given coins are not currently merged, then the given slot in the sparse Merkle tree is blank. (It doesn’t even have to be blank—it’s just irrelevant). So it doesn’t matter any more than future deposits do.
I think the tree would have to be extremely large if it’s sparse and contains every possible unique ID. Did you have ideas for storing the unique IDs efficiently?
In a sparse Merkle tree most of the leaves are empty, so you can precompute them and their parents, grandparents, etc. So it’s no trouble to have a sparse Merkle tree with 2^32 elements.
I just looked back at this, and I think it’s a very good idea.
The size of the bloom filter will still have to be linear with the number of transactions. However, this probably works extremely well for a medium-low throughput Plasma Cash chain.
Not only does this work very well on its own, it’s even possible to have the bloom filters be relayed off the root chain. Here’s a mechanism for that:
For ~5000 txs per block and a 1/100000 false positive rate, this scheme requires the user store 119814 bits per bloom filter. In exchange, the user only needs to ask for the proof of non-existence for any false positives. Users will, for the most part, never have to ask for non-existence proofs.
Yep, my apologies, you’re correct there.
Did anyone come up with a solution for the case where some tx might be included in a block but the block is withheld? I’m not sure I entirely like the idea that the owner will attempt to exit and be challenged by the operator, thereby revealing the information required to properly exit.
The other option is to allow the owner to sign off on a message that allows the new owner to exit from the coin. New owner provides signed message + exit proof for last known tx (owned by old owner) + hash of tx from owner to new owner (may or may not be included in a block). Tx from owner to new owner can’t be used to challenge exit unless actual new owner != exiting new owner.
^ effectively limbo exits as discussed w/ David/Piotr/Joseph except w/o requirement that old owner submits a tx first.
In the scenario where a block withholding attack is happening, presumably all coin owners cannot construct coin validity proofs, since blocks have been withheld; a coin owner can have private knowledge that his coin is valid (ie I has a validity proof up till a certain block, and then I know I’ve never spent the coin from that block onwards) but cannot prove this to a third party. So how do the economics of this work? Is it expected that the new owner pays the old owner in exchange for the old owner signing such a message in your scheme?
I’m not sure I entirely like the idea that the owner will attempt to exit and be challenged by the operator, thereby revealing the information required to properly exit.
Correct me if I’m wrong but from my understanding of the spec even if blocks are being withheld, as long as once blocks are unavailable you don’t spend any coins, a legitimate coin owner can start an exit for which no challenges can be constructed.
Edit: unless you’re talking about the case where the chain becomes unavailable when you have a transaction in-flight?
Yep, exactly. Sorry for the confusion. I’m assuming the chain is Byzantine when the tx is in-flight, so the tx may or may not be included.
The signed message from the old owner to the new owner would basically “bypass” the child chain and complete the payment on the root chain. Standard challenge rules would apply except with the tx that may or may not be included in the child chain as the tx that’s being exited.
Hi, I have a question about the non-inclusion proof.
If an empty transaction is the same regardless of coin (just 0), then how could one know this is really the proof of a particular coin?
If the empty transaction for each coin is different, then we can only pre-compute for like 1 million coins, but not 1 billion coins?
Or there are something I missed about this proof?