mimblewimble team mailing list archive

[Ethan Heilman <ethan.r.heilman@xxxxxxxxx>]

MimbleWimble has the freaky property that transactions and thus blocks
can transform from invalid to valid by the addition of new
transactions and blocks. Depending on how MimbleWimble blocks and
transactions are validated this could cause hardforks in the
blockchain. However if we are careful in how we perform validation we
can avoid forks.

Three ways in which transactions/blocks can move from valid to invalid.
========

1. Invalid Range proof: Transaction Tx1 has an invalid rangeproof, Tx2
spends Tx1 and has a valid range proof. When Tx1 is unspent, it is
invalid, but as soon as Tx2 spends Tx1, Tx1 becomes valid since the
rangeproof is cut-through.

Tx1<---Tx2

2. Doublespending transactions: A Block B1 contains two Transactions
Tx2 and Tx3 which are doublespends i.e. they both spend the same
output in Tx1. The block B1 which includes Tx2 and Tx3 would be
invalid, but a child block B2 could contain a transaction Tx4 which
spends both Tx2 and Tx3 such that Tx4 is valid (corrects for the
inflation that make doublespends invalid) and Tx2 and Tx3 are
cut-through hiding the doublespend.

Tx1<--(T2 and Tx3)<--Tx4

Notice that in both examples the end state is a valid UTXO set.
Nothing bad has happened, no new money has been created, stolen or
lost.

3. Big blocks: Assume that MimbleWimble has a block size limit. The
Block B1 is above this limit and so will be treated as invalid by the
network, but when aggregated with a child block B2 the cut-throughs
reduce the aggregation of B1 and B2 to a very small size.

B1 = too big
B1+B2 = just the right size

How this can cause forks:
========
Consider the following forked blockchain:

B1
|
B2
|   |___
|         |
B3A   B3B
|         |
B4A   B4B

Block B3A contains invalid transactions which are cut-through in B4A.
Block B3B contains invalid transactions which are cut-through in B4B.

An attacker could:
1. Send half the network B3A and an aggregated block consisting of B3B+B4B.
2. Send the other half B3B and an aggregated block consisting of B3A+B4A.

If peers in the network first validate blocks before aggregating them
i.e. then they will treat B3A and B3B as invalid. However if they also
accept aggregated blocks they will treat B3A+B4A or B3B+B4B as valid.
Thus, depending on how this validation works, the network *could*
hardfork since each half might see the other fork as invalid.

There are probably some subtle validation bugs we should watch out for
here. For instance non-full nodes which sync using aggregated blocks
might fork from full-nodes that validate each block individually.

This seems preventable by either:
1. transmitting proofs that block is invalid and rejecting all invalid blocks,
2. aggregating before performing blockchain validation,
3. or by allowing parties to send you aggregate blocks even if you
know one of the component blocks is invalid.

In regards to [0] are horizons still being contemplated? I don't see
why they are necessary if we keep the kernels around forever.

[0]: https://github.com/ignopeverell/grin/blob/master/doc/chainsync.md