mimblewimble team mailing list archive

[John Tromp <john.tromp@xxxxxxxxx>]

A while ago I had a chat with Andrew in
https://gitter.im/grin_community/Lobby where he helped explain multi
signature transactions to me, and I thought it might benefit others as
well to explain the atomic swap below in more detail.

So the setting is that Igno holds some coins on the MW altchain,
by knowing the blinding factor rI0 in an output rI0*G+a*H of a coins,
while Andrew holds some coins on an MW' sidechain,
by knowing the blinding factor rA0' in an output rA0'*G+a'*H of a' coins,
and they'll like to swap these.
Note that we require MW and MW' to use the same curve and generators G,H.
We adopt a notation for quantities that start
with a lower case letter for its role, followed by an uppercase letter for who
picked or computed it, a serial number, and an optional ' to
distinguish the two chains.
For simplicity we ignore change outputs and fees. As Igno has pointed
out, fees must also be listed and signed in the kernels, to prevent
relays and miners from hijacking fees (a relay could take half the fee
for itself by adding an output and kernel, while a miner could avoid
the coinbase locktime on fees).

The plan is to
1) prepare transfers from original outputs into 2-of-2 outputs for holding
2) prepare locktimed refunds from the 2-of-2 outputs in case the swap fails
3) prepare the swapping transactions from the 2-of-2 outputs
4) verifiably link Igno's signatures for the transactions in 3)
5) let Igno obtain his swapping coins on MW'
6) let Andrew obtain his swapping coins on MW

Let's see how each step works in detail.

1) prepare transfers from original outputs into 2-of-2 outputs for holding

            input       blinding/output   kernel
nonce/challenge      signature

MW Igno     rI0*G+a*H   rI1               rI1-rI0        kI1
       sI1=kI1+e1*(rI1-rI0)
MW Andrew               rA1               rA1            kA1
       sA1=kA1+e1*rA1
MW tx1                  (rI1+rA1)*G+a*H   rI1+rA1-rI0
e1=H(kI1*G+kA1*G)    s1=sI1+sA1

MW'Igno                 rI1'              rI1'           kI1'
       sI1'=kI1'+e1'*rI1'
MW'Andrew   rA0'*G+a'*H rA1'              rA1'-rA0'      kA1'
       sA1'=kA1'+e1'*(rA1'-rA0')
MW'tx1'                 (rI1'+rA1')*G+a*H rI1'+rA1'-rA0'
e1'=H(kI1'*G+kA1'*G) s1'=sI1'+sA1'

We assume that all commits to blinding factors and nonces are shared
between them.
Both parties must also construct range proofs for the 2-of-2 outputs,
details of which we ignore.

The constituent signatures sI1,sA1,sI1', and sA1' are not yet shared,
since locking up funds is only safe if refunds are assured for a failing swap.

2) prepare locktimed refunds from the 2-of-2 outputs in case the swap fails

            input       output     kernel       nonce/challenge       signature

MW Igno                 rI2*G+a*H  rI2-rI1      kI2
sI2=kI2+e2*(rI2-rI1)
MW Andrew                         -rA1          kA2
sA2=kA2+e2*-rA1
MW tx2  (rI1+rA1)*G+a*H            rI2-rI1-rA1  e2=H(L||kI2*G+kA2*G)  s2=sI2+sA2

The constituent signatures sI2 and sA2 are shared and verified by both parties.
Transaction tx2' on MW' is prepared similarly, but with a somewhat
earlier locktime L'.

Now that it's safe to share the constituent signatures sI1,sA1,sI1', and sA1',
they are summed into signatures s1 for tx1 and s1' for tx1'.

This step could be slightly simplified by picking rI2==rI1, and
omitting kI2 and sI2, taking s2=sA2. (Andrew remarked on this "it's
really easy to create footguns in MW reusing keys. Though I think in
this case it's actually safe, you're just directly reversing the first
transaction.")

When both tx1 and tx1' are confirmed, we can proceed with step 3).
If any remaining steps fail to complete for any reason,
then either party can issue their refund transaction.

3) prepare the swapping transactions from the 2-of-2 outputs

            input       output     kernel       nonce/challenge    signature

MW Igno                           -rI1          kI3
sI3=kI3+e3*-rI1
MW Andrew               rA3*G+a*H  rA3-rA1      kA3
sA3=kA3+e3*(rA3-rA1)
MW tx3  (rI1+rA1)*G+a*H           -rI1+rA3-rA1  e3=H(kI3*G+kA3*G)  s3=sI3+sA3

            input       output       kernel          nonce/challenge
    signature

MW'Igno                 rI3'*G+a'*H  rI3'-rI1'       kI3'
    sI3'=kI3'+e3'*(rI3'-rI1')
MW'Andrew                           -rA1'            kA3'
    sA3'=kA3'+e3'*-rA1'
MW'tx3' (rI1'+rA1')*G+a'*H           rI3'-rI1'-rA1'
e3'=H(kI3'*G+kA3'*G)  s3'=sI3'+sA3'

At this point the atomic swap is reduced to the exchange of signature
s3' for s3.
We need the revelation of s3' by Igno to reveal s3 to Andrew, which is
achieved by
having Andres know the difference between sI3 and sI3'.

4) verifiably link Igno's signatures for the transactions in 3)

Igno reveals sconv = sI3-sI3' = kI3+e3*-rI1 - (kI3'+e3'*(rI3'-rI1')) and
Andrew verifies that sconv*G = kI3*G-e3*rI1*G - kI3'*G+e3'*(rI3'-rI1')

5) let Igno obtain his swapping coins on MW'

Appearance of tx3' on MW' reveals s3'

6) let Andrew obtain his swapping coins on MW

Andrew computes s3 = sI3+sA3 = sconv+sI3'+sA3=sconv+s3'-sA3'+sA3 and issues tx3


On Fri, Feb 3, 2017 at 5:42 PM, Andrew Poelstra
<apoelstra@xxxxxxxxxxxxxx> wrote:
>
> 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