The proofs that both will not happen at once look good, but they assume too much to be useful for the “at least one happens proof”. They assume that one of the xor components happens, which is what we’re supposed to be proving. Or am I missing something?
Could you try expanding on this reasoning that leads to at least one happening?
Meanwhile, I’ll try to tackle that proof from a different angle, I think you can prove the whole statement by proving these two implications:
1/ assume:
o \in unspent(reality(T_n)) o \not\in double_spent(T_n) o \in I(t_{n+1}) o \not\in E(T_{n+1}) (the “other xor component” not being true)
then these should imply O(t_{n+1}) \subseteq E(t_{n+1})
2/ assume:
o \in unspent(reality(T_n)) o \not\in double_spent(T_n) o \in I(t_{n+1}) O(t_{n+1}) \not\subseteq E(t_{n+1}) (the opposite “xor component” not being true)
then these should imply o \in E(T_{n+1})
Sadly, I can’t follow that through now, b/c in transit. If you could elaborate on your reasoning, I’ll delve into that a couple of days later or I’ll try to pick up with this method above.
Ah, yes–Kelvin is right, the initial definition of liveness is wrong. The third option is that if t_{n+1} is a double spend, then its inputs are removed from the list of exitable outputs E.
Would you clarify how a resolution should work in the following (hypothetical) example:
There is a transaction T1 has an input I1_0 spending an output UTXO1. Transaction T1 is in block N. T1 has in total two inputs and few outputs
There is a transaction T2 has an input I2_0 spending an output UTXO1 too (double spend). Transaction T2 is in block N. T2 has two inputs and few outputs
T2 has the second input I2_1 spending some UTXO2.
T2 has higher priority than T1 due to younger UTXO2.
There is another transaction T3 spending an output UTXO2 and colliding with T2.
T3 has higher priority than T2
That means that both inputs of T2 collide with some other transactions (so such transactions should be eliminated completely), but T1 still can not exit.
Another example: one of many inputs to transaction T is colliding with some other transaction. T has lower priority than another transaction. Lets name other inputs to transaction T as UTXO[i]. In this case should T be deemed as invalid challenge to attempts to exit UTXO[i]? (In case if other users try to exit a transaction producing those UTXO[i])
If T2 is included before T1, then T1 is not canonical and can’t be exited. Canonicity is determined by the position in the chain, not the priority of the youngest input.
So in your example, if the inclusion order is T1, T2, T3, then the outputs of T1 will be able to exit.
I’m sorry, looks like I didn’t make a clear example. Inclusion order is T3 - T2 -T1.
Nevertheless following your explanation T3 exists, T2 is deemed non-canonical, so T1 also exists as T2 is already non-canonical. Would you confirm such logic, right now it’s the only puzzling thing for me to compete the implementation.
If the order is T3, T2, T1 and assuming there are no other conflicting transactions in the chain, then T3 is the only transaction that can be exited. We define canonicity with respect to a single transaction - the set of competing transactions to t is the set of all transactions such that the transaction shares an input with t. The canonical transaction within that set is the transaction that’s included first. So in your example, T3 is canonical, but T2 and T1 are both not canonical (T2 because of T3, and T1 because of T2).
So even though T2 is not canonical, T1 is also not canonical because we look at all transactions when determining canonicity, not just other canonical transactions. The reason we make this distinction is because we would otherwise potentially get a long challenge-response game where each challenge is subsequently proven not canonical.
Very interesting post. I’m confused by this line in particular:
“Honest owners of inputs or outputs to t “piggyback” on this exit and post a bond. Users who do not piggyback will not be able to exit.”
My current understanding of the above is that an owner of one of the outputs in transaction t, may initiate an exit. Any honest owner of another output may “piggyback” on this exit and post a bond if they wish to exit as well. If they do not wish to exit, they do not need to post a bond and can start an Exit at a later time once the original exit has finalized.
Is this understanding correct? Do honest users have to post a bond to a transaction t regardless of if they wish to exit at that particular time? If so, why?
Also, why do the owners of the inputs of a transaction have to post a bond. Since they are inputs, they have already spend their UTXO’s in transaction t in order to create the outputs of transaction t. Thus, they shouldn’t be exiting their inputs to t if they are honest.
In the case where the priority order is T3, T2, T1 then the funds in UTXO1 are locked forever, right?
Since the original owners of UTXO1 cannot withdraw because users can post a proof that it was spent. The new conflicting owners in the outputs of T2 and T1 cannot exit because those transactions are both non-canonical.
Small nitpick - anyone can start the exit, not just an owner of the outputs.
Your understanding is correct. Honest users don’t need to post a bond if they don’t wish to.
Owners of the inputs need to post a bond in the case that t is not canonical (some input double spend is included earlier than t), and therefore the outputs aren’t exitable. Any unspent inputs to t should get their money back.
Also correct. The owner of UTXO1 spent in two transactions, so UTXO1 is no longer exitable, even if it wasn’t included in any canonical transactions.
Hey Kelvin,
FourthState (the team from Blockchain@Berkeley) were discussing More Viable Plasma. We came across a scenario where a validator can grief honest users who received transactions from validator-controlled addresses.
In the case where there is block withholding, in More Viable Plasma, the receivers of transactions can exit safely because their inputs occur before any invalid transactions inputs.
Consider the case where a validator sends a transaction to user A:
He then refuses to include that transaction, and instead spends those same inputs back to himself and withholds the block.
When user A posts a bond and tries to exit their unincluded transaction, the validator can challenge by submitting his included transaction which is the canonical transaction and claim A’s bond.
A loses their bond, even though A was not malicious. A validator that has sent multiple transactions that are in the mempool can grief all recipients of those transactions.
Only the validator can pull off such an attack, but there is no way for the user to know whether a received transaction was from a validator-controlled address. Thus when there is block-holding, an honest receiver must take on the risk that the sender may have been the validator and the honest receiver can potentially lose their bond.
Worse still, if user A tries to exit too soon after the withheld block, the validator may be able to challenge and publish the block immediately causing users to attribute the withheld block to low availability as opposed to malicious activity. This would allow the validator to get away with malicious activity without the punishment of a mass exit.
Does More Viable Plasma have a solution to this attack?
Yep, we thought about this problem significantly. I haven’t found a design that doesn’t have this griefing vector, unfortunately. Even confirmation signatures has a similar problem - imagine the following scenario:
A sends to B (operator).
A sees the transaction included in a block, publishes a confirmation to B.
B pretends to go offline, A attempts to withdraw from the original input.
B reveals tx + confirmation, griefing.
If you’re using offline confirmation signatures, then B doesn’t even need to be the operator. For the above to be a problem.
As for the second aspect (low availability), I don’t think it’s really a problem if clients have some standard wait period and will begin to exit automatically if they don’t receive a block within that period. Clients shouldn’t initiate an in-flight exit unless they’re sure that something bad has happened.
Why is a two phase exit game is necessary? In our discussion, we couldn’t come to the conclusion on why it is necessary if you can always challenge an exit within the first exit “phase”
@kfichter I’m still struggling with understanding this particular case. When you say “t is not canonical”, does this mean that the (honest) owner who posts a bond for a given input is challenging t as a double spend (and thereby obtaining the bond posted by the exit initiator)? Otherwise, I’m struggling to see the incentive for an owner of an input being spent by an inflight transaction to post a bond.
Ex:
Alice owns UTXO1, with a value of 10 PETH.
Alice spends UTXO1 to Bob, thereby creating UTXO2, to Bob (TX1). This is included, but withheld.
Operator spends UTXO1 to some address controlled by Operator (TX2).
Operator posts a bond, initiating exit for TX2.
Alice sees that there is a double spend for UTXO1 and posts a bond to exit UTXO1 in phase 2 (?).
In this case, how does Alice get her money back since only unspent inputs can exit?
Thanks for this very thorough construction by the way. We are planning to implement this in the near future.
A two phase exit game is necessary because there are scenarios where we need to provide enough time to challenge. For example, if inputs/outputs piggyback onto the exit, they’re subject to challenge. If we don’t have two phases, then the inputs/outputs could piggyback at the very last moment and there wouldn’t be enough time to challenge.
That’s kind of what I’m confused about; since only Alice can spend her UTXO that means any double spend must be made by Alice herself - in which case, why would she attempt to exit her own double spend?
So basically the idea of non-canonical applies to any input. This really only matters when there’s more than one input to a transaction. Let’s say Alice owns UTXO1 and Bob owns UTXO2. Alice and Bob make a transaction together (TX1) that spends UTXO1 and UTXO2. TX1 is withheld, not included. Bob double spends UTXO2 in another transaction (TX2). Now, if Alice attempts an in-flight exit on TX1, then someone can present TX2. Alice’s UTXO1 is otherwise unspent, so she can exit.
Thanks for explaining, I understand now! I had tunnel visioned on a TX being created by one actor only. Would it be right to say, in light of this, that the purpose of piggybacking on an input would be, essentially to prevent yourself from being unable to exit after the second (double spend) and therefore non-canonical tx?