mimblewimble team mailing list archive

[Andrew Poelstra <apoelstra@xxxxxxxxxxxxxx>]

This came up in one of the early Reddit posts about the Voldemort paper,
but I can't find it now... essentially what you need to do is solution (3).
You have two block validation modes, "full" and "compacted". Note that any
block which is valid in the compacted sense is also valid in the full
sense, so you can switch from full to compact for sufficiently old blocks
but not the other way around.

I've argued elsewhere that compact validation is not weaker than full validation,
in the sense that it still guarantees the invariants of "no net inflation or
theft".

This means that if somebody makes an individually-invalid block that is
valid after aggregation, it would be seen by nodes as invalid until it became
old enough that they'd accept it as an aggregate. No more harmful than a
Bitcoin block with an out of range (too far in the future) timestamp.

Because there is no consensus threshold on the depth at which nodes switch
from full to compact validation, there is the potential for forks that last
for a substantial amount of time. But I think if everybody has their threshold
at several thousand blocks (which they ought to be doing anyway because
reorging a compacted chain requires redownloading the whole blockchain, super
slow), this attack would be prohibitively expensive...and not have a big
payoff.


Cheers
Andrew



On Wed, Mar 15, 2017 at 04:28:24PM -0400, Ethan Heilman wrote:
> 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
> 
> -- 
> Mailing list: https://launchpad.net/~mimblewimble
> Post to     : mimblewimble@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~mimblewimble
> More help   : https://help.launchpad.net/ListHelp
> 
> 

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
       --Joanna Newsom

Attachment: signature.asc
Description: PGP signature