mimblewimble team mailing list archive

[Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>]

If you're talking about cut-through in the transaction pool (and not in a block), there's an issue where I send you some money and I have some change. You spend the money, I spend my change and those 2 transactions get independently cut-through. Then they look like double spends.

A solution could involve some regularly randomly elected set of nodes that could perform locks (ala Paxos) to detect those issues. But it adds a fair amount of complexity. There may be more elegant solutions but I haven't spent a lot of time thinking about those quite yet (but maybe someone has?).

- Igno

-------- Original Message --------
Subject: Re: [Mimblewimble] Potentional method of hardforking MimbleWimble via freaky invalid to valid block transitions
Local Time: March 15, 2017 3:06 PM
UTC Time: March 15, 2017 10:06 PM
From: ethan.r.heilman@xxxxxxxxx
To: Andrew Poelstra <apoelstra@xxxxxxxxxxxxxx>
mimblewimble@xxxxxxxxxxxxxxxxxxx

>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".

I completely buy this argument which is why I don't understand why
there would be a threshold for blocks to be compacted. I love the idea
of the WimbleMimble blockchain being just a big evolving proof of no
inflation or theft". What is the downside to having every peer
cut-through transactions as they are spent? Am I missing an attack?

It seems like this would handle forks. As long as you never aggregate
your UTXO set, if a competing fork wins you ask for the missing
kernels in the other fork, diff the UTXO set changes and validate.

On Wed, Mar 15, 2017 at 5:23 PM, Andrew Poelstra
<apoelstra@xxxxxxxxxxxxxx> wrote:
>
> 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
>
>
> --
> Mailing list: https://launchpad.net/~mimblewimble
> Post to : mimblewimble@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~mimblewimble
> More help : https://help.launchpad.net/ListHelp
>

--
Mailing list: https://launchpad.net/~mimblewimble
Post to : mimblewimble@xxxxxxxxxxxxxxxxxxx
Unsubscribe : https://launchpad.net/~mimblewimble
More help : https://help.launchpad.net/ListHelp