mimblewimble team mailing list archive

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

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