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
<apoels...@wpsoftware.net> 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
--
Mailing list: https://launchpad.net/~mimblewimble
Post to : mimblewimble@lists.launchpad.net
Unsubscribe : https://launchpad.net/~mimblewimble
More help : https://help.launchpad.net/ListHelp
