mimblewimble team mailing list archive

[Andrew Poelstra <apoelstra@xxxxxxxxxxxxxx>]

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

Attachment: signature.asc
Description: PGP signature