mimblewimble team mailing list archive
-
mimblewimble team
-
Mailing list archive
-
Message #00161
Re: Treeless block and UTXO set validation
Yes, I realized it yesterday, was pondering on it some more before emailing yet again. I take it as a lesson to sit for a couple days on a new idea that seems too good before emailing :)
And yes, protonmail is annoying that way, it detects the emails are from mailing lists but still spams them for not coming from a protonmail server...
- Igno
> -------- Original Message --------
> Subject: Re: [Mimblewimble] Treeless block and UTXO set validation
> Local Time: July 27, 2017 1:53 PM
> UTC Time: July 27, 2017 1:53 PM
> From: merope08@xxxxxxxxxxxxxx
> To: Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>
> mimblewimble@xxxxxxxxxxxxxxxxxxx <mimblewimble@xxxxxxxxxxxxxxxxxxx>
> For some reason this message was sent to spam in Protonmail. May be why there are so few replies.
> Sums are not sufficient to validate the UTXO set. Anybody who owns two outputs summing to a commitment `C` can give a peer any pair of commitments `C1` and `C2` with valid rangeproofs such that `C1 + C2 = C`, causing a disagreement on the UTXO set and therefore a consensus failure.
> The same is true for inputs although the room for mutation is more limited because there are only so many inputs to choose from.
> Same is true for kernels.
>
> Sent with [ProtonMail](https://protonmail.com) Secure Email.
>
>> -------- Original Message --------
>> Subject: [Mimblewimble] Treeless block and UTXO set validation
>> Local Time: July 26, 2017 5:45 AM
>> UTC Time: July 26, 2017 5:45 AM
>> From: igno.peverell@xxxxxxxxxxxxxx
>> To: mimblewimble@xxxxxxxxxxxxxxxxxxx <mimblewimble@xxxxxxxxxxxxxxxxxxx>
>> Hi all,
>> I think we could do without any type of Merkle tree, both in block headers and in the complete UTXO set (for sync). Please tell me if I'm wrong.
>> A block is composed of the following information (ignoring header):
>>
>> - Outputs, with a commitment, range proof and a features bitset.
>> - Inputs, which are just outputs commitments.
>> - Kernels, with the excess value, its signature and the fee.
>>
>> The UTXO set necessary to sync-up a new node, assuming it has the header chain already, is composed of outputs (all unspents) and kernels (all of them) with same information as above.
>> The purpose of putting some sort of Merkle tree root in a block header is to make it hard to mess with block data, as it would change the proof of work (also SPV but let's ignore that for a sec). Now lets get rid of all tree roots and just put 2 things in block headers: the sum of excess values over the whole block and the sum of excess values since genesis (summing all blocks). What can we mess with?
>>
>> - Output commitments can't be changed, wouldn't match the sums (both in block and total in UTXO set).
>> - Output range proofs can't be changed, they would get invalidated with respect to their commitment.
>> - Inputs can't be changed, would match the sum.
>> - Kernel excess can't be changed, wouldn't match the sums (also both in block and total in UTXO set)
>> - Kernel sig can't be changed, wouldn't validate with the excess as pubkey.
>> - Kernel fee can't be changed, wouldn't validate with the sig.
>>
>> Only the feature bitsets could be potentially messed with, but right now they're only used to flag coinbase kernels and outputs and messing with that would also invalidate sums.
>> The result would be that full nodes don't need to maintain any tree of any type, making it a lot simpler and saving a fair amount of space. Also when a new node wants to sync up, there's no tree to transfer and that process also get a fair amount simpler. If I'm right, I have to apologize to Merope for not seeing this earlier. And obviously we would lose some features, SPV would get harder and spent proofs, while still possible (I think), wouldn't be as elegant.
>> - Igno
Follow ups
References