I see, nice work. Have you done any work on exits?
What sort of work do you mean?
Let’s look at the liveness proof (at “Our liveness property states…”), something isn’t clear for me there.
You’ve proven that if o \in I(t_{n+1}) then the two “implied components” of the XOR won’t happen at the same time. In fact you proved this twice, since the two statements:
o \in E(T_{n+1}) \implies O(t_{n+1}) \cap E(T_{n+1}) = \varnothing \implies O(t_{n+1}) \not\subseteq E(T_{n+1})
and
O(t_{n+1}) \subseteq E(T_{n+1}) \implies o \not\in E(T_{n+1})
are in contraposition, therefore equivalent.
However, the implication that at least one of the “implied XOR components” is true, provided o \in I(t_{n+1}) is still to be proven.
Maybe a way to prove would be to prove the contraposition of the whole thing, i.e.:
\forall o \in E(T_{n})
(o \in E(T_{n+1}) \land O(t_{n+1}) \subseteq E(T_{n+1})) \lor (o \not\in E(T_{n+1}) \land O(t_{n+1}) \not\subseteq E(T_{n+1})) \implies o \not\in I(t_{n+1})
but that seems not easily manipulable, I’m stuck here.
If you’re willing to accept our proofs that both will not happen at once, then I think the guarantee of at least one happening just follows from canonical(t_{n+1}) \vee \neg canonical(t_{n+1}) \ , since each was used as an intermediate step in the proofs.
There is a case where neither will happen (input is double spent, noted by \setminus DS(T_{n})). We need to update the original statement and proof to reflect this.
Non-breaking, but should be clarified.
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.
Hello @kfichter
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])
Sincerely, Alex
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.
Good day, Kelvin.
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.
Sincerely, Alex
1 Like
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.
1 Like
Hey Kelvin,
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.
Let me know if I’m missing something.
Also following from shamatar’s example:
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.
1 Like
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.
1 Like
Hey Kelvin,
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.
1 Like
Only the owner of UTXO1 (Alice) can create a valid signature spending UTXO1. The operator would not be able to spend UTXO1 here.