mimblewimble team mailing list archive

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

What is MimbleWimble default behavior in the event that a block
contains a doublespend? Is the block invalid like in Bitcoin?

I am going to assume MW treats blocks with doublespends as invalid.
Let me propose the following scenario:

1. An attacker computes a block B1 with a doublespend transaction Tx1
that has kernel K1,
2. The network will treat this block B1 as invalid,
3. The attacker when deletes Tx1 from B1 as if has been cut-through
even though it hasn't been spent. This block will still not validate
because the kernel K1 inflates the number of coins.
4. The attacker adds transaction Tx2 with kernel K2 using the blinding
factors from K1 such that K1+K2 no longer inflates the currency. Note
that Tx2 does NOT spend Tx1.
5. The attack includes Tx2 and K2 in block B2 and aggregates B2 with
B1 where Tx1 has been deleted.

The block B1 will now be treated as valid by a node if and only if it
is sent as an aggregate of B1+B2. However any node which attempts to
aggregate the blocks themselves will not be able to replicate a valid
B1+B2 aggregate because they don't know they can remove Tx1 once they
have K2.

Thus, as Andrew said earlier about solution 3 being the correct way to
handle this situation, nodes must allow other nodes to send them
cut-through blocks*. Solution 2 from my previous email "2. aggregating
before performing blockchain validation" does not work in this
scenario.

Thanks for letting think this through with you all,

Ethan

* An even stronger argument for this,is that a single miner could do a
bunch of cut-throughs and never release the "uncut block".

On Wed, Mar 15, 2017 at 9:23 PM, Ignotus Peverell
<igno.peverell@xxxxxxxxxxxxxx> wrote:
> Then yes, in blocks it totally makes sense to always cut-through. There may
> be a need for full history nodes in case "we mess up" but I don't think that
> should be the default.
>
> - Igno
>
>
> -------- Original Message --------
> Subject: Re: [Mimblewimble] Potentional method of hardforking MimbleWimble
> via freaky invalid to valid block transitions
> Local Time: March 15, 2017 6:19 PM
> UTC Time: March 16, 2017 1:19 AM
> From: ethan.r.heilman@xxxxxxxxx
> To: Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>
> Andrew Poelstra <apoelstra@xxxxxxxxxxxxxx>, mimblewimble@xxxxxxxxxxxxxxxxxxx
>
> I was thinking about cut-throughs after a block has been confirmed so
> that there would be no danger of that occurring.
>
> On Wed, Mar 15, 2017 at 7:02 PM, Ignotus Peverell
> <igno.peverell@xxxxxxxxxxxxxx> wrote:
>> 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
>>
>>
>
>