mimblewimble team mailing list archive

mimblewimble team

Mailing list archive

Message #00119
Re: [POLL] Perfectly hiding vs perfectly binding
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 signtocontract 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 paytocontract 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 slightlymorethandouble 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 2530% 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 postquantum world.
My feeling is that such users should go create a onewaypeg 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 paytocontract 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
conspiracyminded detractors.
7. Unconditional soundness slightly simplifies the user model, in that it adds
an amountindependent 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 walletrecoveryfromseed 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 cutthrough. But I'd guess that outputs users
care about recovering the most are longlived 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 2025%, 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/secp256k1mw/pull/1
In that we have an open problem about asset soundness  this affects
only issued assets, not Mimblewimble which can only a small mostlyfixed
list of assets anyway.
[3] See https://0bin.net/paste/8zkHY2OALVJaQeJg#lJML4QUq2isZKlIR5+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
Attachment:
signature.asc
Description: PGP signature
Follow ups
References