investigate tx cut-through conflict resolution

[antiochp]

tl;dr Potentially resolve tx cut-through conflicts using an "optimistic locking" strategy. Monitor blocks added to the blockchain for conflicts and re-broadcast modified txs to resolve the conflict.

The Problem

Scenario: A simple tx (2 outputs, 1 of which is a change output). Both the change output and regular output both then immediately spent with 0-confirmations.

tx1        i1 -> (o2, o3)    kern1    # normal output + change output
tx2        i2 -> o4          kern2    # output subsequently spent
tx3        i3 -> o5          kern3    # change output subsequently spent 

(tx1 + tx2) can be cut-through to produce tx1,2 -

tx1,2      (i1, i2) -> (o2, o3, o4)    (kern1, kern2)
tx1,2      i1 -> (o3, o4)              (kern1, kern2)

or (tx1 + tx3) can be cut-through to produce tx1,3 -

tx1,3      (i1, i3) -> (o2, o3, o5)    (kern1, kern3)
tx1,3      i1 -> (o2, o5)              (kern1, kern3)

tx1,2 and tx1,3 conflict. They cannot both be successfully added to the tx pool. To an observer they appear to be a double spend on i1. Some nodes may see tx1,2 as valid (tx1,3 invalid) and others may see tx1,3 as valid (tx1,2 invalid).

Note: (tx1, tx2, tx3) can technically be cut-through to produce tx1,2,3 -

tx1,2,3    (i1, i2, i3) -> (o2, o3, o4, o5)    (kern1, kern2, kern3)
tx1,2,3    i1 -> (o4, o5)                      (kern1, kern2, kern3)

Note: this can be successfully carried out in various orders of operation -

1) Cut-through tx1,2 with tx3 -

tx1,2      i1 -> (o3, o4)              (kern1, kern2)
tx3        i3 -> o5                    (kern3)
tx1,2,3    (i1, i3) -> (o3, o4, o5)    (kern1, kern2, kern3)
tx1,2,3    i1 -> (o4, o5)              (kern1, kern2, kern3)

2) Cut-through tx1,3 with tx2 -

tx1,3      i1 -> (o2, o5)              (kern1, kern3)
tx2        i2 -> o4                    (kern2)
tx1,3,2    (i1, i2) -> (o2, o5, o4)    (kern1, kern3, kern2)
tx1,3,2    i1 -> (o5, o4)              (kern1, kern3, kern2)

tx1,2,3 and tx1,3,2 are identical if inputs, outputs, kernels are ordered lexicographically.

The problem occurs when a node sees tx1,2 and tx1,3 and is unable to cut-through. tx1,2 and tx1,3 are conflicting transactions (appear to be a double spend on i1).

tx1,2      i1 -> (o3, o4)              (kern1, kern2)
tx1,3      i1 -> (o2, o5)              (kern1, kern3)

Proposal for a possible approach to conflict resolution

The party that originally cut-through tx1 + tx3 to produce tx1,3 can resolve this situation by monitoring new blocks on the blockchain and looking for the corresponding kernels kern1 and kern3.

Specifically, if -

• kern1 in new block, but
• kern3 not in block Then we know either tx1 or tx1,2 was accepted but tx1,3 (or tx1,2,3) was not accepted.

In either case tx1,3 (or tx1,2,3) will never be accepted as it appears to be a double spend on i1.

The node can act to resolve this by broadcasting tx3. This is now similar to scenario 1 above with tx1,2 and tx3. These will not be cut-through as they will be in different blocks, but the txs are compatible and valid.

tx1,2      i1 -> (o3, o4)              (kern1, kern2)
tx3        i3 -> o5                    kern3

Intuitively this approach seems workable for more complex scenarios - Monitor blocks for conflicts (kernels included/excluded in the block). Broadcast adjusted txs as necessary.

The original cut-through attempt may be unsuccessful but we can broadcast txs in such a way that all desired txs are accepted even in the case of conflict.

[antiochp]

The other thing we need to consider is the (non-interactive) "CoinJoin" side of things. Specifically, another node can potentially take any pair (or any number) of txs and combine them in a way that looks indistinguishable from the cut-through situation above.

For example a pair of very simple, unrelated txs -

tx1      i1 -> o2     kern1 
tx2      i3 -> o4     kern2 
tx1,2    (i1, i3) -> (o2, o4)    (kern1, kern2)

Related - not only can a node spam the network with regular txs, they can take existing txs and simply add to them, making them appear to be cut-through txs. In the extreme case they could take every tx they see broadcast and cut-through them with spam txs, rebroadcasting them multiple times cut-through in different ways.

A dishonest node could produce -

tx1,2a
tx1,2b
tx1,2c
...

and flood the network with txs that other nodes have not yet seen. Knowing that only one of those would actually be accepted as a valid tx (fees for this spam would be minimal).

The mitigating factor here is other honest nodes will have seen the original txs and maybe there is something similar to the proposed "cut-through resolution" proposal that they can apply to un-cut-through (and therefore reduce the effectiveness) of these spam txs.

i.e. if there was a way for honest nodes to "deconstruct" these txs based on having seen the original tx1. We could derive tx2a by subtracting tx1 from tx1,2a. Same for tx1,2b etc.

This would not prevent the spam but the spam txs can all be accepted (and fees would need to be paid on them all).

[tromp]

Can nodes afford to only accept transactions with disjoint kernels into their pool? This should reduce lots of spam if workable.

[ignopeverell]

It may be a good pragmatic first step. I'm just a little tentative because you could block a transaction of mine with your cut-through, at least for a block. And if I'm not keeping an eye on it, it may be problematic for me.

[tromp]

I'm confused. Your transaction can only be cut-through if the receiver spends the output right away, before your transaction is confirmed. And if that gets cut-through, then both may be confirmed as one. How is that blocking?

[ignopeverell]

I send you some coins. You spend them right away, I spend my change right away.

[tromp]

So both you and I, while this original transaction is pending, are engaging in interactions with other parties to build 2 new transactions that spend both outputs? And by the time both these follow-ups gets broadcasted, the original still hasn't confirmed?

In that rare case it is possible that both ways of cut-through spread around, and only one of them gets confirmed. But then, the aggregator that cut-through two kernel sets and only sees one get confirmed, could still rebroadcast the latter.

Alternatively, one who spends an unconfirmed output could be aware of the tiny risk of averse cut-through and be prepared to re-broadcast if necessary.

[antiochp]

Agreed - I've been trying to think through various scenarios and the "unresolvable" ones all seem to boil down to this situation described above. The only parties that are able to resolve a situation like this are those involved in initial cut-through operations. Nobody else has enough information to either resolve the situation or rebroadcast anything after seeing one tx get confirmed. So there has to be some form of active monitoring of the pool and blockchain by the wallet (or possibly the trusted node that the wallet connects to?).

In terms of terminology, does "cut-through" refer to both the following cases (or just the first one) -

(in1) -> (out2)
cut-through with
(in2) -> (out3, out4)
to produce
(in1) -> (out3, out4) # in2/out2 "never existed"

(in1) -> (out2)
cut-through with
(in3) -> (out4, out5)
to produce
(in1, in3) -> (out2, out4, out5)

The latter cases is effectively CoinJoin. Txs are completely unrelated and disjoint but we can "combine" them to produce a single tx (multiple kernels). Is this combining also referred to as "cut-through"?

This case I think is slightly different (and interesting) because other nodes are able to resolve conflicts, not just the initial nodes involved in the txs. Any node can take any set of txs and combine them this way - but any node may also have information about the pre-combined txs and can reverse or compensate for the combining step.

I'd argue that a node does not increase anonymity by combining arbitrary txs as there is a reasonable chance other nodes have already seen one or more of the original un-combined versions. So its not actually in a nodes interest to do this (other nodes may simply undo this work). Unless - the node knows for certain it is the first node to have seen these txs.

[tromp]

No, plain aggregation is not cut-through. I just use cut-through as a synonym for input-output-cancellation.

One way to avoid the need to un-combine is by submitting a tx through a single chain of aggregators on its way to the miners/pools. In that case no-one will see the tx combined in different ways.

[antiochp]

Ok makes sense around terminology, just wanted to get it clear in my head. I think there is some confusion/ambiguity around this (at least to me).

• aggregation - we can freely combine any multiple transactions (analogous to CoinJoin)
• cut-through - actually removing intermediate outputs when aggregating 0-confirmation spend

And yeah - we are thinking along the same lines. There is actually no privacy advantage to a "regular" node doing either aggregation or cut-through. It actually introduces the possibility of a false sense of privacy. There is no guarantee that other nodes have not already seen the un-aggregated txs, unless -

• node is a dedicated aggregator (not even clear what this means, what guarantees they provide?)
• node originated the tx (and they know for sure nobody has seen the original txs)

In all other cases I think a node should attempt to un-aggregate txs if they can, while maintaining txs with disjoint kernels sets.

For example -

• node sees tx1 with kernel set (kern1, kern2)
  • node adds it to internal pool
  • node broadcasts tx1 to network
• nodes sees tx2 with kernels (kern1, kern2, kern3)
  • node identifies non-disjoint kernel set with existing tx (superset of existing tx in pool)
  • split tx2 into tx1 (kern1, kern2) and tx2b (kern3)
  • adds tx2b to pool (maintaining disjoint kernel sets)
  • broadcasts tx2b to network (note, does not broadcast tx2, assumes other nodes have seen tx1 and will trivially derive tx2b as we did)

If that last step is done consistently then there is no advantage (privacy or otherwise) for a node to attempt to aggregate txs, unless it is an aggregator node. So while any node can freely combine transactions, with no way of identifying this once combined, I think there is no incentive to actually do this. It is effectively just spam and redundant tx data on the network (except when explicitly requested).

Edit: said another way, the ability for a node to un-aggregate a tx reduces the incentive for other nodes to even bother trying, unless they are confident it will actually be beneficial to the network.

[antiochp]

@tromp - just reading your comments in gitter. https://gitter.im/grin_community/Lobby?at=5a81f9567084124a346b5a53

there will usually be very little cut-through since most outputs are only spent after being confirmed but aggregation is beneficial for privacy better aggregation requires slower propagation through dandelion network though

This is interesting. If we do implement Dandelion (or something analogous) then the nodes involved in the initial "stem" propagation can aggregate txs (and these nodes provide some kind of guarantee that they do not persist state at this stage), then once the tx flips to the "fluff" phase we stop aggregating and all nodes begin adding the tx to their internal tx pools.

Edit: we can combine Dandelion with tx aggregation (aka CoinJoin) in a Grin native way. Which feels significantly better than bolting Dandelion on to Grin as an afterthought.

[ignopeverell]

That is interesting...

[tromp]

Yeah, when I wrote "submitting a tx through a single chain of aggregators" I didn't even realize how well it matches the stems in Dandelion...

[quentinlesceller]

Solved by https://github.com/mimblewimble/grin/pull/1067 ?

[yeastplume]

I think this has been addressed (please feel free to reopen if not)