mimblewimble team mailing list archive

mimblewimble team

Mailing list archive

Message #00047
Re: Scriptless scripting and deniable swaps
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 2of2 outputs for holding
2) prepare locktimed refunds from the 2of2 outputs in case the swap fails
3) prepare the swapping transactions from the 2of2 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 2of2 outputs for holding
input blinding/output kernel
nonce/challenge signature
MW Igno rI0*G+a*H rI1 rI1rI0 kI1
sI1=kI1+e1*(rI1rI0)
MW Andrew rA1 rA1 kA1
sA1=kA1+e1*rA1
MW tx1 (rI1+rA1)*G+a*H rI1+rA1rI0
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 2of2 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 2of2 outputs in case the swap fails
input output kernel nonce/challenge signature
MW Igno rI2*G+a*H rI2rI1 kI2
sI2=kI2+e2*(rI2rI1)
MW Andrew rA1 kA2
sA2=kA2+e2*rA1
MW tx2 (rI1+rA1)*G+a*H rI2rI1rA1 e2=H(LkI2*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 2of2 outputs
input output kernel nonce/challenge signature
MW Igno rI1 kI3
sI3=kI3+e3*rI1
MW Andrew rA3*G+a*H rA3rA1 kA3
sA3=kA3+e3*(rA3rA1)
MW tx3 (rI1+rA1)*G+a*H rI1+rA3rA1 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 = sI3sI3' = kI3+e3*rI1  (kI3'+e3'*(rI3'rI1')) and
Andrew verifies that sconv*G = kI3*Ge3*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 hashpreimage challenges in MimbleWimble by adding
> the ability to sign hashes and consensusrequiring 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 2of2 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
References