Making unconfirmed utxos spendable by making them conditional

[paulperegud]

1. When submitting tx A, ask operator for partial block and partial merkle proof for this block.
2. Check if both are correct.
3. When spending utxo produced by A using transaction B, attach partial merkle proof to it (all signed by spender).
4. If operator will cheat and partial merkle proof will not match contents of the block (or block would be withheld), exit from A.
5. If operator will challenge you with B, it will need to show that merkle path corresponds to the block root. If not, challenge is invalid.
6. If challenge is valid - exit from B.

@boolafish

[paulperegud]

In this variant this idea does not works since it requires N rounds of interactive game on chain.

[paulperegud]

For a chain of such transactions all in-flight games can be played in parallel.

To challenge partial merkle proof - just show that there is some other tx in this place (or even show other merkle proof that shares a prefix with this one but is different in one of the known nodes).

Challenge of the partial merkle proof of in-flight tx input is a form of canonicity challenge. In-flight becomes not canonical, can exit only from inputs, particular input can't be piggybacked anymore.

[boolafish]

Noting down some possible holes I can think of and we must handle to make this work:

1. Data availability: only the user and operator would have the in-flight chained tx to be able to challenge a chained in-flight tx is used.
2. How to prove no in-flight double spending? If chained, you would need to prove all in-flight txs ancestors have never double spent. Feel like impossible in parallel game and with 1 or 2 steps to challenge.

[paulperegud]

Two more remark before I'll address your comment.

• Challenge of a partial merkle proof makes the input non-existent and increases priority of the exit (now an older input is the youngest input). This is a problem in terms of the way we are using priority queue but we can just insert exit into priority queue one more time. We will check if exit was already processed on taking the exit out of the queue.
• If partial merkle proof for older tx was challenged, this piece of data can be used to successfully challenge any younger partial merkle proof.

Now, addressing your points.

1. Double-spends by those in-flight exits are irrelevant since they are happening with very low priority (youngest input is in withheld block).
2. We never actually prove lack of double spends. We proof existence of particular double spend :-)

[boolafish]

[Note From the call]
My understanding of this idea. Let's say we have [Good block] --> [invalid tx, A --> B --> C].
A is using input from Good block. Now we try to prove that the partial merkle proof of A is in-consistent with/invalid. Since B is using A as input, we now re-calculate the exit priority of B to some other inputs that B is using. The in-consistency of partial merkle proof can be proven in parallel.

Remaining issues: let's say A double spent to B and B'. And B, B' each chained further on to C, C'.....
How to prove such historical double spending?

One more thing I come up with after the call: what would happen if B has no other input that can change the priority? But the output of A used in B will be challenged as used. How to make sure at least one of them is able to exit?

[paulperegud]

Remaining issues: let's say A double spent to B and B'. And B, B' each chained further on to C, C'.....
How to prove such historical double spending?

Since B and B' are using the same partial merkle proof input, they are just candidates. Normal process applies. Now, with C and C' we rely on detecting inconsistency in partial merkle proofs. C points at B, C' points at B'. We have 2 scenarios:

1. No data availability, everyone is exiting. Authors of C and C' are "splitting the piebreadcrumbs" with operator. Or operator is challenging them by revealing merkle proof invalidating partial merkle proofs of some of those transactions.
2. Full data availability - partial merkle proofs used in C and C' can be challenged by anyone.

One more thing I come up with after the call: what would happen if B has no other input that can change the priority? But the output of A used in B will be challenged as used. How to make sure at least one of them is able to exit?

If the input of B is non-existent due to bad partial merkle proof, the UTXO should be exited as the output of A (assuming A is canonical).

[paulperegud]

One more problem.

[Good block] --> [invalid tx -> valid tx, A --> B].

Now, operator does IFE from "valid tx", providing partial merkle tree for invalid tx. She exits with priority of invalid tx, before B. And she does not provide any proof material to invalidate B's input from A.

[boolafish]

Seems like this is not a feasible path to move further on. Close this now.
Could follow up #86 which provides similar feature.

[paulperegud]

Yes, this one is dead.