mimblewimble team mailing list archive

[Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>]

I wanted to amend my proposal on compact blocks to refine further the "first n bytes of input/output/kernel hashes". Obviously this opens up a possibility of collision forgery, which can then increase network chattiness.

BIP152 introduced a good solution by introducing short transaction ids (which we can generalize to inputs/outputs/kernels):

https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki#Short_transaction_IDs

It does force a full re-hashing of the pool on each block but siphash 2-4 is fast and we don't need to introduce a new crypto primitive as siphash 2-4 is already used by Cuckoo Cycle.

I was also playing with the idea of committing to the short tx ids in the block header (instead of the tx hashes) to avoid network-level malleability or compact blocks but after checking with instagibbs on bitcoin-wizards (thanks!) that seems like a premature optimization right now. Bitcoin doesn't have such a thing and just plain ban on misbehavior seems to work well enough so far.

- Igno

-------- Original Message --------
Subject: Re: [Mimblewimble] Compact blocks
Local Time: March 4, 2017 4:20 PM
UTC Time: March 5, 2017 12:20 AM
From: igno.peverell@xxxxxxxxxxxxxx
To: John Tromp <john.tromp@xxxxxxxxx>
mimblewimble@xxxxxxxxxxxxxxxxxxx

Now that we're going down that path, I'm starting to wonder whether we should treat inputs, outputs and kernels all in that same way. It's definitely simpler.

Here's the proposal:
- Across the wire, blocks have the regular list of inputs, outputs and kernels. At the minimum, they must have one output and one kernel (coinbase).
- Blocks can also include the first n bytes of input/output/kernel hashes that are part of the block but not fully included.
- A node receiving a block with partial hashes checks them against its the transaction pool.
- Known input/output/kernels are added, missing ones (or collisions) are asked to the block sending node all in one batch.
- Once everything is known, the full block can be validated.

This still leaves the possibility to have full blocks, including all the data. In the general case the blocks should be very compact and requests for more data will only be commonplace for nodes newly started. It also gives an incentive to miners to have a fairly full transaction pool (to avoid further requests).

As far as how many bytes of the hash, as John mentioned, 8 bytes (a u64) seem to suffice. I believe the chances of collisions with a pool of 100,000 elements would still be less than 0.00000003%. 4 bytes would likely be too small, a transaction pool of the same size would have 69% of collisions.

- Igno

-------- Original Message --------l
Subject: Re: [Mimblewimble] Compact blocks
Local Time: March 3, 2017 2:47 PM
UTC Time: March 3, 2017 10:47 PM
From: john.tromp@xxxxxxxxx
To: Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>, mimblewimble@xxxxxxxxxxxxxxxxxxx

dear Igno,

> That is, the receiver will look up how many kernel she has matching the hint.
> If 0 or more than 1, it will query peers for a list of all known
> matching kernels.

Uhm, that should be: ask the sending peer to expand the hint to a full kernel.

regards,
-John