mimblewimble team mailing list archive

[Andrew Poelstra <apoelstra@xxxxxxxxxxxxxx>]

I recently described how to do hash-preimage challenges in MimbleWimble by adding
the ability to sign hashes and consensus-requiring the preimage to be revealed for
this signature to be considered valid [1]. This was met by concerns about additional
complexity, trying to use features before the design space had been fully fleshed
out, permanent data storage in the blockchain, and concerns about fungibility.

Pieter Wuille in particular has stressed to me what a great feature of MW it is
that everything looks the same, and that breaking this property should be taken
very seriously.

At the Stanford BPASE Conference [2] I gave a talk where I briefly mentioned that
it was possible to do atomic swaps with no preimages at all. I'll explain how to
do this in a second, but first I want to revise my proposal from my last mail.

  * Each kernel (née excess value) K signs the challenge H(K || f || L), where
    K is the kernel itself, f is the fee it is attesting must exist in this
    transaction, and L is an optional locktime, measured in blockheight.

  * By default L is the empty string, there needs to be a special flag to indicate
    that it is nontrivial. Hopefully the actual presence of nontrivial locktimes
    will be rare since they are only used in the adversarial backout case of most
    protocols. Since a locktime L must stay in the blockchain forever we should
    discourage their use somehow.

So I'm removing all script support, even for just hash preimages.


Ok, so algebraically how do atomic swaps work in a scriptless way? Suppose I'm
trying to send Igno 1 MW1 coin on one chain in exchange for MW2 coin on another.
Then:

  1. As before we send our coins to 2-of-2 outputs on each chain. Each of us
     refuses to move our coin until the other has given us a locktimed "refund"
     transaction; we set our locktimes so I can retrieve my coin before he can
     retrieve his.

     (So far this is the same as the classic Bitcoin atomic swap by Tier Nolan [3];
     the difference in locktimes is because during part of the protocol Igno can
     take his coins but I can't yet take mine, so I want to be sure he can't do
     this and simultaneously back out. This way ff he takes the coins, I can take
     mine, but if he backs out then I've long since backed out, and these are his
     only possibilities.)

  2. Igno and I construct transactions that move the locked coins to their final
     destinations. We agree on the kernels and signature nonces, and in particular
     on signature challenges e and e'.

  3. Igno sends me a "conversion" keys sconv which satisfies

         sconv * G = R - R' + eP - e'P'

  4. I sign the MW1 transaction giving Igno his coin and send him the signature.

  5. Now Igno signs the MW1 transaction, giving himself his coin. To do this he adds
     his signature

         s = k + xe

     where `k` is his secret nonce and `x` his secret key are values I don't know
     but which have been forced on him (their public counterparts are committed
     in the hash `e`).

  6. I then compute s' = s + sconv, which is Igno's half of the MW2 transaction,
     and am able to take my coins.


Observe that I can verify sconv is legitimate in step (3), and that this verification
equation is sufficient to force my computed s' to verify iff s does. Observe further
that once the two signatures are public, anybody can compute "sconv" as s' - s, which
gives us two properties:

  1. It assures that sharing sconv does not harm the security of anyone's keys, since
     it's publicly computable anyway by anybody who has access to the final signatures.

  2. This scheme is deniable, since it depends on Igno giving me sconv before I knew
     s', which neither of us can prove. In other words either of us could fabricate
     the above transcript for any pair of signatures.



My thinking is that this atomic linking of multiple transactions is a fairly general
primitive that can be used to link lightning channels etc, and that we might not need
hash preimages for this after all.



[1] https://lists.launchpad.net/mimblewimble/msg00022.html
[2] https://cyber.stanford.edu/blockchainconf
[3] https://bitcointalk.org/index.php?topic=193281.msg2224949#msg2224949



-- 
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