mimblewimble team mailing list archive

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

>I like this in principle, but how efficiently is it possible for us to do
this diffing?

We could probably use something like set reconciliation. I don't know
the area well but I was looking into it a few years ago for increasing
the efficiency of block propagation in the Bitcoin network. Reading
around online it seems like performance depends on the size of the
difference not the size of the set, which is great news for us since
we can expect very large sets with very small differences.

https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf

You could speed this up by including your local mempool and also
caching recently cut-through transactions so you can undo them
quickly.


On Thu, Mar 16, 2017 at 12:57 PM, Andrew Poelstra
<apoelstra@xxxxxxxxxxxxxx> wrote:
> On Thu, Mar 16, 2017 at 12:50:57PM -0400, Ethan Heilman wrote:
>> >The problem with this is that if I've got a blockchain of the form
>> >  ABC DE FG
>> >and Ethan has a blockchain of the form
>> >   ABCD EFG'
>>
>> If you store the inputs and outputs of a transaction together rather
>> than mixing all the inputs and outputs then this problem boils down
>> to:
>> "I'll treat your fork as valid and only if you send me the block
>> headers, kernel diff and missing UTXO set members at the head of your
>> fork"
>>
>> A fork switch would happen like this:
>> 1. Andrews fork is longer.
>> 2. Andrew we diff kernel sets and Andrew sends me the new kernels.
>
> Kernel sets I think are easy, we always want all the kernels of blocks in
> the chain, and no others. So this can be done alongside diffing headers,
> which can be done very cheaply and easily.
>
>> 3. We diff UXTO sets and Andrew individually sends me each member of
>> his UTXO set which I don't have.
>> 5. I exclude each individual UTXO from my UTXO set which isn't in
>> Andrews UTXO set to reconstruct Andrew's UTXO set.
>> 5. Thus, I reconstruct Andrews UTXO set while only having to receive
>> the UXTOs which he has that I don't.
>
> I like this in principle, but how efficiently is it possible for us to do
> this diffing?
>
>> 6. I validate the fork with my new UTXO set and kernels. i.e. I compute
>>
>> isBalanced( ABCDEFG )?
>>
>> 7. If it passes I adopt the fork.
>>
>
> :thumbsup:
>
>>
>> On Thu, Mar 16, 2017 at 12:36 PM, Andrew Poelstra
>> <apoelstra@xxxxxxxxxxxxxx> wrote:
>> > On Thu, Mar 16, 2017 at 12:23:45PM -0400, Ethan Heilman wrote:
>> >> Hi Andrew,
>> >>
>> >> > Say that none of these blocks are valid individually but the compactions AB and AC are valid. I post both to
>> >> the network, now everyone is split between the two, and the next block
>> >> will force a reorg.
>> >> >Logistically, how does somebody who has AB in their blockchain switch to AC?
>> >>
>> >> Since half the network has AC they must provide AC or the AB half will
>> >> not consider the new fork valid. This would be similar to Bitcoin
>> >> where if I have the longest fork but refuse to share some of the
>> >> transactions in that fork, that form is considered invalid.
>> >>
>> >> >For that matter, how did anyone validate AB in the first place? Compact validation of an entire chain is easy because you need no inputs, but compact validation of partial chains is harder because you need a subset of each blocks' inputs.
>> >>
>> >> Good point.
>> >>
>> >
>> > Ok, so I think where we're headed is:
>> >
>> >   - We should generalize blocks to "frankenblocks" which are ranges of
>> >     consecutive blocks where cutthrough inputs and outputs are pruned
>> >
>> >   - We should have a better name for frankenblock :)
>> >
>> >   - They can be considered for the purposes of PoW accounting to be
>> >     atomic units whose difficulty is the sum of the individual blocks'
>> >     difficulty.
>> >
>> >   - Reorg/sync logic should be able to request frankenblocks, and know
>> >     the exact frankenblock partition was used to produce the chain (so
>> >     that reorgs can happen without breaking frankenblocks apart).
>> >
>> > The problem with this is that if I've got a blockchain of the form
>> >
>> >    ABC DE FG
>> >
>> > and Ethan has a blockchain of the form
>> >
>> >    ABCD EFG'
>> >
>> > (G is replaced by G'), how are we going to sort this out? If Ethan's fork
>> > wins, I'll want a replacement for frankenblock FG, which Ethan can't provide,
>> > and conversely I can't replace EFG'. The winner would need to provide the
>> > entire blockchain to the loser.
>> >
>> >
>> > A simple solution is to prune only the rangeproofs of cut-through outputs,
>> > which allows reorgs to happen within frakenblocks, and still provides the
>> > majority of the efficiency benefit.
>> >
>> >
>> > --
>> > 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
>> >
>>
>>
>
> --
> 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
>