Closed ignopeverell closed 6 years ago
I've tried to give this some thought as well.. trying to think of what can be malleateificatedified in a range proof and what attack vectors it could give. Thus far I can think of
-You can intercept and generate a new range proof with different keys, which won't validate for that output, so moot.
-If you know the keys, you can swap out generate a new range proof with the same keys, which will produce a different hash due to random elements in generating the proof (not 100% sure, but assuming). However, this shouldn't matter as the malleated proof will work just as well and doesn't break consensus
-You can modify the stored amount used for wallet restore.. which again doesn't change the validity of the proof.. again this can't be done without knowing the keys, and is very much optional whether the user wants to store it there or not (if they don't it just means they won't be able to restore their wallet unless they keep amounts around as well). Shouldn't matter
-You can intercept/change the switch commit after #207... (which probably isn't worth doing till bulletproofs). So this needs to stay in the UTXO sumtree. Validation shouldn't require looking at the switch commit anyhow, except post-quantamageddon. You could change this to be nonsense, but again, not without the private keys, and it's up to the user whether they even want to include it in the first place.
Post quantamageddon.. actually we are missing a piece of the puzzle here at present, because as far as I can make out the recent mailing list post is correct, and (vG+bG),H(bG) actually breaks the perfectly hiding quality of pedersen commits by making it possible to iterate through a finite number of values for v and testing the remainder for H(bG) ... so I very much could derive all needed keys and reconstruct the rangeproof in this case even though I wasn't the originator. To what end I don't know, and a lot more than rangeproof malleability is broken in this instance. But sumtree hashes should still be valid after quantageddon, so without them I wouldn't be able to ensure the rangeproof was actually produced by the owner.
Is the issue topic here effectively "Eliminate range proofs from headers, instead keeping them in a dedicated MMR" ?
Post Quant.Comp. is probably out of scope still for a while :) and when QC becomes a thing, there might be bigger targets than grin hotwallets, hopefully giving us time for an orderly move to at minmum back hot grin wallets with quantum-safe(r) cold wallets. @yeastplume Sorry I'm not understanding if, by ignoring QC, you think the proposed idea will work out? Maybe I'm actually asking if switch-commitments are already in the MMR wherefrom we want to remove range proofs (which they are, right?)
As I'm understanding, if removing is OK, then for #522 only option 2 remains viable.
But the switch commitment hash is committed to in the UTXO MMR, so it's not (and actually makes it even harder to malleate the range proof).
I was about to state I didn't think was true.
Looking through the code I just realized this is no longer true with the work in #615 getting merged... I think this was "cleaned up" in the process of migrating lock_heights from the switch commit to the output MMR on that branch.
Working on reintroducing this now - PR coming shortly.
Edit: (for my reference) - this is what tripped me up -
https://github.com/mimblewimble/grin/blob/7e7c8e157e2a649d8889a9544d7759bd92c959b0/core/src/core/transaction.rs#L584-L590
We don't need the switch commit hash when comparing hashes (in is_unspent
) - but we do need it in there when adding entries to the MMR.
Edit - fixed this minor omission in #630.
Q) what was the original reasoning behind committing to rangeproofs in a separate MMR and not just including them in the output MMR?
Probably phrasing this poorly but - if we don't commit to them anywhere then a non-archival node has no way of verifying these ever existed or that anybody else actually validated them? Does this matter?
The original reasoning was that we may want to prune them more aggressively and it seemed wrong to include them in the output "identity". A non-archival node shouldn't trust that anyone did any modification, it should just ask for the UTXO range proofs to verify by itself.
The rangeproofs need to be committed in a block. Otherwise it's impossile to reject a block on the basis that its rangeproofs are bad, since maybe there are good rangeproofs somewhere out there. IOW the anti-DoS function of the PoW is undermined. This is the same reason that in Bitcoin witness data is committed in blocks, even though its exact form doesn't affect anything on the protocol level.
Given that rangeproofs are committed, putting them in a separate tree makes sense because they're witness data, they aren't needed to build the chainstate, only to verify it. Lumping them into the output tree will force partial/probalistic validators to download (a lot of) extra unnecessary data. This was the motivation for segwit in the first place.
You're right of course. Thanks for chiming in.
It occurred to me today that committing to range proof hashes in a MMR doesn't really help us for anything except malleability. And that we didn't really care about range proof malleability.
Here is the whole argument (hopefully all true statements):
Am I missing something? By removing the range proof MMR we would gain 32 bytes in each header and log2(N)*32 bytes of state data for the MMR itself.
To be clear, I'm not suggesting removing range proofs or any of the validation or syncing logic. Just commiting to their hashes in a dedicated MMR.
/cc @yeastplume @antiochp @apoelstra