I should start by saying that I am in favor of unconditional soundness. My reasons are twofold:
- First, user assurance that no inflation has happened or ever will
happen, even in the presence of a discrete logarithm break/QC.
Note that unlike Bitcoin, we can't just softfork in a replacement
for OP_CHECKSIG that will prevent theft in this case. We would need
to replace the output commitments and rangeproofs, which along with
some hash structures constitute the entirety of Mimblewimble's
consensus model. So users worried about _theft_ need to develop a new
quantum hard MW regardless of the outcome of this discussion.
(_Detecting theft_, at least in a way that you can prove to yourself
that it happened, is pretty easy -- just sign-to-contract the current
state of your wallet in every transaction you produce. This is quantum
secure and works regardless of soundness. I'll talk about this in
some future post about wallet design.)
- Secondly, it's important to realize that inflation is literally
undetectable with Pedersen commitments in the case of a discrete log
break. You can't even just open the commitments and add up the values
because the commitments will no longer have meaningful openings.
(Oleg Andreev has suggested using pay-to-contract to commit to the
"real" openings, which would work, but only if everybody did it...
and since it is unverifiable in the absense of a DL break, it seems
pretty unlikely that everyone would.)
I don't mean to imply by my second reason that I think a DL break is around
the corner or that quantum computers are going to show up tomorrow. I defer
to the many experts in the field who claim otherwise. What I mean is simply
that it makes me feel squeamish that this is possible, even in principle.
My expectation is that I'm the common case here.
Having said this, let me lay out the tradeoffs as I see them:
1. Unconditional soundness will slightly-more-than-double the computational
cost of verifying the chain. (Rangeproofs, asset proofs and kernel proofs
each take about twice as much time to verify, as does summing everything
up to make sure it all balances.)
2. Unconditional soundness will double the size of all output commitments,
asset commitments and kernels (from one curvepoint to two, 32 bytes to 64).
3. In addition to this, rangeproofs will grow by a factor of 25-30% from
~1.4Kb to ~1.8Kb [1] plus will require about 288 bytes [2] on top of that.
4. The soundness stuff will require some additional crypto dev work, which
I'm happy to do -- note that additional crypto work needs to be done
anyway because there's a way to hide rangeproof exponents that would
be cheaper _and_ have better privacy than my earlier idea about asset
denominations [3]. (The additional data for this will be about 320 bytes
without unconditional soundness, vs 384 with. And the unconditionally
sound variant will take about twice as long to validate. IMO this
particular cost is negligible.)
5. Unconditional soundness means we lose perfect hidingness. A computer that
can break arbitrary discrete logs will be able to see every amount. (Such
a computer will _not_ be able to unmerge transactions, except heuristically
by matching input and output amounts.) Maybe users want an emphemeral
system that simply implodes, erasing its tracks, in a post-quantum world.
My feeling is that such users should go create a one-way-peg to their own
chain, if it's really so ephemeral. (Igno: we should think about this
usecase and see what the most efficient way to burn coins is. Because
rangeproofs prove knowledge of coins' blinding factors the "fake key"
shenanigans that e.g. XCP did from Bitcoin won't work. I guess just adding
an optional "burn" field next to the "fee" in what the kernels sign would
suffice, and the kernel can pay-to-contract whatever other stuff the peg
validators want. ...But I digress.)
However:
6. Unconditional soundness will protect the integrity of the system (except
that theft will be possible) from hypothetical crypto breaks. It gives
users this assurance and also takes this line of attack away from
conspiracy-minded detractors.
7. Unconditional soundness slightly simplifies the user model, in that it adds
an amount-independent part to each output, which they can recognize (as,
say,
part of their BIP32/44 chain) even if they've forgotten the amount. If a
rangeproof is available this is sufficient for them to quickly compute the
original amount from this key, plus they can encrypt other data to
themselves
in the rangeproof. This makes wallet-recovery-from-seed very powerful.
This is possible even without unconditional soundness but it's much less
efficient.
(As Igno constantly reminds me, this only works if the outputs hit the
chain
rather than being immediately cut-through. But I'd guess that outputs users
care about recovering the most are long-lived ones that won't be spent
within
a single block.)
Cheers
Andrew
[1] Technically, what I mean is that we have a way to _shrink_ the rangeproofs
by 20-25%, but it only works with the perfectly hiding variant of CT/CA.
[2] The output commitment needs an extra point which is needed only for the
rangeproof; then there is an additional proof that is about 8 points
big. See the conversation here where Oleg and I worked this all out:
https://github.com/apoelstra/secp256k1-mw/pull/1
In that we have an open problem about asset soundness -- this affects
only issued assets, not Mimblewimble which can only a small mostly-fixed
list of assets anyway.
[3] See
https://0bin.net/paste/8zkHY2OALVJaQeJg#lJML4QUq2isZKlI-R5+MlaA/DeUk29idvO7+EtEOQaq
where Andrew Miller develops this idea. Denominations I talked about here
https://lists.launchpad.net/mimblewimble/msg00103.html though I don't give
performance numbers. They're not good. The size of proof in the body of
this mail is for amiller's scheme with 16 denominations per asset, and
does not increase with the number of assets. With two assets my idea
would allow only 4 denominations per asset in the same size, and the size
would increase with every additional asset the chain supported.
--
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
signature.asc
Description: PGP signature
-- Mailing list: https://launchpad.net/~mimblewimble Post to : mimblewimble@lists.launchpad.net Unsubscribe : https://launchpad.net/~mimblewimble More help : https://help.launchpad.net/ListHelp
