Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 3D710D95 for ; Sat, 10 Aug 2019 13:01:55 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ot1-f66.google.com (mail-ot1-f66.google.com [209.85.210.66]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8CA8E82D for ; Sat, 10 Aug 2019 13:01:53 +0000 (UTC) Received: by mail-ot1-f66.google.com with SMTP id j19so66542209otq.2 for ; Sat, 10 Aug 2019 06:01:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=monash.edu; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=SM/S4QM457OyBHLKFgA3bDhdqYEbW5I2JA32trsiFQ4=; b=fxA+4roxE4PnsOK3XsrUGru9NAIeNNIW/JV2iaqLfmQBP/bEwTgnbv/A4PwAbb/Ilq fcROfoRmH1pGj4ptiHZgmPDz+q2drVNfNJDtfGzsYT/HMNyrtR72TJZtdY4j+gAE5v4m AVA9VflYRTuKg6rXBGuY+D1vnLfBkQ7HjD4VIKmoE4oBUmwwYu9TCxn1xGMc7cp/CKpI PrmhweyOOKlnx1fdmEKWOxG+cNQ0cnlxdFBSvs6i8dx08sj2R/g+YyoEXcPfjZGf9c1+ tVMVi5I4raz+E2ign8b/nguIdZ2XusH3ZaFAb4vEJ5nBi1axcvA0+e/z3dokD4IChpoZ zf4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=SM/S4QM457OyBHLKFgA3bDhdqYEbW5I2JA32trsiFQ4=; b=WiisXwY4/2IXE0yApQrD3riG2uL+Md93xXXMkbZcqxSCcHWI0gSwhDCgZHVzHrDaka E0sOn8EoiPDD1OqaT65X9hpCP7OcXUEY1jCak0mPSsbSKAuU3XWDBHAXy6LQwogbL0+v I+EoYbrGjbpL0QvONlytm9Qc7PngefKv314PiC/2N55gLcT38riXblRj8v7KW+ktISYQ AuF17OGC8HAccC7KZBO7ys0TkNmwGVuxq+up83J8mtdJ/iDCg9VKt1NVkwcqT7pCH+ez 7TL9lJw2ow0T4CQ8skm0+Pn5VTyUYDyMSgdGXu75XISCj336uIXKfwHI/M0hqLPJptAc v82A== X-Gm-Message-State: APjAAAW8mZwMYO94ikn+h4vKV8Zs1LmNJO0JHWvpeXvwq8RDeCSuj06M WKa0DVAfzcKKCxIywBJdTjd3/+uXSWlYFS7CWsW+eccx X-Google-Smtp-Source: APXvYqzOt7qtDo46ih23COc7EuAto/XGvDx0vKWR0HQCrlTPEpCU/L1niQZOTDj43cWh+pprKD8BLM5zELDMXr6ZSIs= X-Received: by 2002:a6b:3883:: with SMTP id f125mr12167688ioa.109.1565442112416; Sat, 10 Aug 2019 06:01:52 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Runchao Han Date: Sat, 10 Aug 2019 23:01:41 +1000 Message-ID: To: Bitcoin Protocol Discussion , ZmnSCPxj Content-Type: multipart/alternative; boundary="00000000000007546b058fc2e52d" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Sat, 10 Aug 2019 13:03:32 +0000 Cc: "jiangshan.yu@monash.edu" Subject: Re: [bitcoin-dev] OP_LOOKUP_OUTPUT proposal X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 10 Aug 2019 13:01:55 -0000 --00000000000007546b058fc2e52d Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable If I remember it right, Alice first signs the WJT transaction, sends it to Bob, then Bob signs it and makes this transaction valid. If so, there are two problems. First, Bob gets the valid tx first, and he can choose not to send it to Alice. Second, even if Bob honestly sends Alice this tx, Alice cannot fully control when to broadcast this to, as Bob also has this transaction. If Bob first signs then Alice signs, Alice still has optionality, as she can choose whether to publish this tx and preimage. Runchao On Sat, Aug 10, 2019 at 10:50 PM ZmnSCPxj wrote: > Good morning Runchao, > > > > > Sent with ProtonMail Secure Email. > > =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90 Original = Message =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90 > On Saturday, August 10, 2019 1:44 PM, Runchao Han > wrote: > > > Hi ZmnSCPxj, > > > > Thanks for your reply. > > > > I agree with your opinions about OP_LOOKUP_OUTPUT. > > Indeed, the pruning mechanism renders this opcode unrealistic for some > nodes. Also, the execution of OP_LOOKUP_OUTPUT depends on the time of > verifying this tx. > > > > However, I=E2=80=99m concerning of some security issues of your mention= ed > protocol (Alice pays the premium contingently on Bob participating). > > If I understand it right, Alice and Bob should create a payment channel= , > and mutually construct the funding transaction that =E2=80=9CAlice pays B= ob 10,000 > WJT; Bob hash-timelocked pays Alice 1,000,000WJT=E2=80=9D, where the time= lock is > T+24. > > Here, Bob is responsible for broadcasting this tx after confirming > Alice=E2=80=99s funding transaction on BTC blockchain. > > No, Bob is not. > > The signature exchange for the WJT-side funding tx is done by: > > 1. Alice waits for Bob to provide all its signatures for inputs that will > fund the 1,000,000 WJT payout. > 2. Alice signs its inputs that will fund the 10,000 WJT premium. > 3. Alice broadacasts the completely signed funding tx. > > Alice is the one responsible for broadcasting the funding tx. > > If Bob stalls, it is not a Bob side option (i.e. Bob cannot stall then > continue the protocol when the exchange rate moves to its favor) as Alice > can refuse to sign and broadcast the funding tx once it has decided Bob i= s > trolling it, thus Bob cannot force Alice to perform. > > If Alice stalls, Bob can double-spend one of its inputs at a low feerate. > This either aborts the protocol, or if Alice then broadcasts the funding > tx at the pre-agreed feerate and it is confirmed, the premium is now > already paid to Bob. > > Regards, > ZmnSCPxj > > > In this case, Bob can arbitrage by broadcasting this tx after T+24. In > this way, Bob receives the 10,000WJT, but Alice cannot redeem 1,000,000WJ= T > anymore. > > If the premium (10,000WJT) is also hash-timelocked, Alice can keep > unraveling the preimage, which makes the atomic swap still premium-free. > > > > In the original atomic swap, Bob is incentivised to broadcast his > funding transaction, otherwise he may miss the opportunity to redeem > Alice=E2=80=99s asset. > > Also, Alice will lose nothing regardless of how Bob behaves, because > Alice locks all her money by hashlock. > > However, Alice cannot lock the premium using hashlock. This gives Bob > opportunity to arbitrage Alice=E2=80=99s premium. > > > > What is implied here is that, where the premium should go strictly > depends on where Bob=E2=80=99s asset goes. > > If the Bitcoin=E2=80=99s timelock can be =E2=80=9Crelative=E2=80=9D (e.= g. the timestamp can be > x+24 where x is the timestamp of the block with this transaction), I thin= k > this protocol works. > > Unfortunately, the =E2=80=9Cx=E2=80=9D here is also an external state a= ccording to your > definition. > > > > In conclusion, I believe your comments on OP_LOOKUP_OUTPUT reasonable, > but cannot make sure if the premium mechanism can be implemented by using > HTLCs. > > > > Thanks, > > Runchao > > > > > On 10 Aug 2019, at 12:29 am, ZmnSCPxj ZmnSCPxj@protonmail.com wrote: > > > Good morning Haoyu LIN et al., > > > > > > > We have investigated this problem in very detail. We analysed how > profitable the arbitrage can be given the default timelock setting (24/48 > hrs). Our result shows that the profit can be approximately 1% ~ 2.3%, > which is non-negligible compared with 0.3% for stock market. This can be > attractive as it's totally risk-free. Please refer to our paper > https://eprint.iacr.org/2019/896, and the related code > https://github.com/HAOYUatHZ/fair-atomic-swap if interested. > > > > Several studies have proposed for solving this problem e.g., > http://diyhpl.us/wiki/transcripts/scalingbitcoin/tokyo-2018/atomic-swaps/ > and https://coblox.tech/docs/financial_crypto19.pdf. Their basic idea is > that, the transaction for the premium needs to be locked with the same > secret hash but with a flipped payout, i.e. when redeemed with the secret= , > the money goes back to Alice and after timelock, the premium goes to Bob = as > a compensation for Alice not revealing the secret. However, this introduc= es > a new problem: Bob can get the premium without paying anything, by never > participating in. > > > > To solve this, the transaction verifier needs to know the status of > an dependent transaction. Unfortunately, Bitcoin does not support the > stateful transaction functionalities. Therefore, we propose the new opcod= e: > OP_LOOKUP_OUTPUT. It takes the id of an output, and produces the address = of > the output=E2=80=99s owner. With OP_LOOKUP_OUTPUT, the Bitcoin script can= decide > whether Alice or Bob should take the premium by ` OP_LOOKUP_OUTPU= T > OP_EQUALVERIFY`. > > > > > > I believe an unsaid principle of SCRIPT opcode design is this: > > > > > > - No SCRIPT opcode can look at anything that is not in the > transaction spending from the SCRIPT. > > > > > > This issue underlies the previous `OP_PUBREF` proposal also. > > > The reason for this is: > > > > > > - We support a pruning mode, where in only the UTXO set is retained= . > > > If `OP_LOOKUP_OUTPUT` exists, we cannot prune, as > `OP_LOOKUP_OUTPUT` might refer to a TXO that has been spent in very early > historical blocks. > > > > > > - The SCRIPT interpreter is run only once, at the time the > transaction enters the mempool. > > > Thus it cannot get information about the block it is in. > > > Instead, the SCRIPT interpreter can have as input only the > transaction that is attempting to spend the SCRIPT. > > > > > > > > > In any case: > > > > > > > However, this introduces a new problem: Bob can get the premium > without paying anything, by never participating in. > > > > > > Premium payment can be made contingent on Bob participating. > > > Of course, it does mean the premium is paid using the destination coi= n. > > > It also requires the destination coin to support SegWit. > > > Let me explain by this: > > > > > > 1. Alice and Bob agree on swap parameters: > > > > > > - Alice will exchange 1 BTC for 1,000,000 WJT from Bob. > > > - Alice will pay 10,000 WJT as premium to Bob. > > > - Alice will lock BTC for 48 hours. > > > - Bob will lock WJT for 24 hours. > > > - The protocol will start at particular time T. > > > > > > 2. Alice generates a preimage+hash. > > > 3. Alice pays 1 BTC to a HTLC with hashlock going to Bob and > timelocked at T+48 going to Alice. > > > 4. Alice presents above UTXO to Bob. > > > 5. Alice reveals the WJT UTXOs to be spent to pay for the 10,000 WJT > premium to Bob. > > > 6. Alice and Bob generate, but do not sign, a funding transaction > spending some of Bob coin as well as the premium coin from Alice. > > > This pays out to 1,010,000 WJT (the value plus the premium) HTLC. > > > The hashlock branch requires not just Alice, but also Bob. > > > The timelock branch at T+24 just requires Bob. > > > > > > 7. Alice and Bob generate the claim transaction. > > > This spends the funding transaction HTLC output and pays out > 1,000,000 WJT to Alice and 10,000 WJT to Bob. > > > > > > 8. Alice and Bob sign the claim transaction. > > > This does not allow Bob to make the claim transaction valid by > itself as it still requires the preimage, and at this point, only Alice > knows the preimage. > > > > > > 9. Alice and Bob sign the funding transaction and broadcast it. > > > 10. Alice completes the claim transaction by adding the preimage and > broadcasts it. > > > 11. Bob sees the preimage on the WJT blockchain and claims the BTC > using the preimage. > > > > > > If Bob stalls at step 8, then there is no way to claim the premium, a= s > the funding transaction (which is the source of the claim transaction tha= t > pays the premium) is not valid yet. > > > After step 9, Bob has been forced to participate and cannot back out > and claim the premium only. > > > This is basically this proposal: > https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-January/00= 1798.html > > > In addition, if you really want the premium to be denominated in BTC, > I have a more complicated ritual: > https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-January/00= 1795.html > > > The described ritual only sets up the American Call Option, but by th= e > time it has been set up, the premium has been paid already and the rest o= f > the execution is claiming the American Call Option. > > > Thus, I believe there is no need to add `OP_LOOKUP_OUTPUT`. > > > Regards, > > > ZmnSCPxj > > > --00000000000007546b058fc2e52d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
If I remember it right, Alice first signs the WJT tr= ansaction, sends it to Bob, then Bob signs it and makes this transaction va= lid.

If so, there = are two problems.
First, Bob gets the valid tx first= , and he can choose not to send it to Alice.
Second,= even if Bob honestly sends Alice this tx, Alice cannot fully control when = to broadcast this to, as Bob also has this transaction.

If Bob first signs then Alice signs, Alice = still has optionality, as she can choose whether to publish this tx and pre= image.

Runchao

On Sa= t, Aug 10, 2019 at 10:50 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
Good morning Runchao,




Sent with ProtonMail Secure Email.

=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90 Original Me= ssage =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90
On Saturday, August 10, 2019 1:44 PM, Runchao Han <runchao.han@monash.edu> wrote= :

> Hi ZmnSCPxj,
>
> Thanks for your reply.
>
> I agree with your opinions about OP_LOOKUP_OUTPUT.
> Indeed, the pruning mechanism renders this opcode unrealistic for some= nodes. Also, the execution of OP_LOOKUP_OUTPUT depends on the time of veri= fying this tx.
>
> However, I=E2=80=99m concerning of some security issues of your mentio= ned protocol (Alice pays the premium contingently on Bob participating). > If I understand it right, Alice and Bob should create a payment channe= l, and mutually construct the funding transaction that =E2=80=9CAlice pays = Bob 10,000 WJT; Bob hash-timelocked pays Alice 1,000,000WJT=E2=80=9D, where= the time lock is T+24.
> Here, Bob is responsible for broadcasting this tx after confirming Ali= ce=E2=80=99s funding transaction on BTC blockchain.

No, Bob is not.

The signature exchange for the WJT-side funding tx is done by:

1. Alice waits for Bob to provide all its signatures for inputs that will f= und the 1,000,000 WJT payout.
2. Alice signs its inputs that will fund the 10,000 WJT premium.
3. Alice broadacasts the completely signed funding tx.

Alice is the one responsible for broadcasting the funding tx.

If Bob stalls, it is not a Bob side option (i.e. Bob cannot stall then cont= inue the protocol when the exchange rate moves to its favor) as Alice can r= efuse to sign and broadcast the funding tx once it has decided Bob is troll= ing it, thus Bob cannot force Alice to perform.

If Alice stalls, Bob can double-spend one of its inputs at a low feerate. This either aborts the protocol, or if Alice then broadcasts the funding tx= at the pre-agreed feerate and it is confirmed, the premium is now already = paid to Bob.

Regards,
ZmnSCPxj

> In this case, Bob can arbitrage by broadcasting this tx after T+24. In= this way, Bob receives the 10,000WJT, but Alice cannot redeem 1,000,000WJT= anymore.
> If the premium (10,000WJT) is also hash-timelocked, Alice can keep unr= aveling the preimage, which makes the atomic swap still premium-free.
>
> In the original atomic swap, Bob is incentivised to broadcast his fund= ing transaction, otherwise he may miss the opportunity to redeem Alice=E2= =80=99s asset.
> Also, Alice will lose nothing regardless of how Bob behaves, because A= lice locks all her money by hashlock.
> However, Alice cannot lock the premium using hashlock. This gives Bob = opportunity to arbitrage Alice=E2=80=99s premium.
>
> What is implied here is that, where the premium should go strictly dep= ends on where Bob=E2=80=99s asset goes.
> If the Bitcoin=E2=80=99s timelock can be =E2=80=9Crelative=E2=80=9D (e= .g. the timestamp can be x+24 where x is the timestamp of the block with th= is transaction), I think this protocol works.
> Unfortunately, the =E2=80=9Cx=E2=80=9D here is also an external state = according to your definition.
>
> In conclusion, I believe your comments on OP_LOOKUP_OUTPUT reasonable,= but cannot make sure if the premium mechanism can be implemented by using = HTLCs.
>
> Thanks,
> Runchao
>
> > On 10 Aug 2019, at 12:29 am, ZmnSCPxj ZmnSCPxj@protonmail.com wrote:
> > Good morning Haoyu LIN et al.,
> >
> > > We have investigated this problem in very detail. We analyse= d how profitable the arbitrage can be given the default timelock setting (2= 4/48 hrs). Our result shows that the profit can be approximately 1% ~ 2.3%,= which is non-negligible compared with 0.3% for stock market. This can be a= ttractive as it's totally risk-free. Please refer to our paper = https://eprint.iacr.org/2019/896, and the related code https://github.com/HAOYUatHZ/fair-atomic-swap if interested.
> > > Several studies have proposed for solving this problem e.g.,= http://diyhpl.us/wiki/tran= scripts/scalingbitcoin/tokyo-2018/atomic-swaps/ and https://coblox.tech/docs/financial_crypto19.pdf. Their basic idea is= that, the transaction for the premium needs to be locked with the same sec= ret hash but with a flipped payout, i.e. when redeemed with the secret, the= money goes back to Alice and after timelock, the premium goes to Bob as a = compensation for Alice not revealing the secret. However, this introduces a= new problem: Bob can get the premium without paying anything, by never par= ticipating in.
> > > To solve this, the transaction verifier needs to know the st= atus of an dependent transaction. Unfortunately, Bitcoin does not support t= he stateful transaction functionalities. Therefore, we propose the new opco= de: OP_LOOKUP_OUTPUT. It takes the id of an output, and produces the addres= s of the output=E2=80=99s owner. With OP_LOOKUP_OUTPUT, the Bitcoin script = can decide whether Alice or Bob should take the premium by `<output> = OP_LOOKUP_OUTPUT <pubkeyhash> OP_EQUALVERIFY`.
> >
> > I believe an unsaid principle of SCRIPT opcode design is this: > >
> > -=C2=A0 =C2=A0No SCRIPT opcode can look at anything that is not i= n the transaction spending from the SCRIPT.
> >
> > This issue underlies the previous `OP_PUBREF` proposal also.
> > The reason for this is:
> >
> > -=C2=A0 =C2=A0We support a pruning mode, where in only the UTXO s= et is retained.
> >=C2=A0 =C2=A0 =C2=A0If `OP_LOOKUP_OUTPUT` exists, we cannot prune,= as `OP_LOOKUP_OUTPUT` might refer to a TXO that has been spent in very ear= ly historical blocks.
> >
> > -=C2=A0 =C2=A0The SCRIPT interpreter is run only once, at the tim= e the transaction enters the mempool.
> >=C2=A0 =C2=A0 =C2=A0Thus it cannot get information about the block= it is in.
> >=C2=A0 =C2=A0 =C2=A0Instead, the SCRIPT interpreter can have as in= put only the transaction that is attempting to spend the SCRIPT.
> >
> >
> > In any case:
> >
> > > However, this introduces a new problem: Bob can get the prem= ium without paying anything, by never participating in.
> >
> > Premium payment can be made contingent on Bob participating.
> > Of course, it does mean the premium is paid using the destination= coin.
> > It also requires the destination coin to support SegWit.
> > Let me explain by this:
> >
> > 1.=C2=A0 Alice and Bob agree on swap parameters:
> >
> > -=C2=A0 =C2=A0Alice will exchange 1 BTC for 1,000,000 WJT from Bo= b.
> > -=C2=A0 =C2=A0Alice will pay 10,000 WJT as premium to Bob.
> > -=C2=A0 =C2=A0Alice will lock BTC for 48 hours.
> > -=C2=A0 =C2=A0Bob will lock WJT for 24 hours.
> > -=C2=A0 =C2=A0The protocol will start at particular time T.
> >
> > 2.=C2=A0 Alice generates a preimage+hash.
> > 3.=C2=A0 Alice pays 1 BTC to a HTLC with hashlock going to Bob an= d timelocked at T+48 going to Alice.
> > 4.=C2=A0 Alice presents above UTXO to Bob.
> > 5.=C2=A0 Alice reveals the WJT UTXOs to be spent to pay for the 1= 0,000 WJT premium to Bob.
> > 6.=C2=A0 Alice and Bob generate, but do not sign, a funding trans= action spending some of Bob coin as well as the premium coin from Alice. > >=C2=A0 =C2=A0 =C2=A0This pays out to 1,010,000 WJT (the value plus= the premium) HTLC.
> >=C2=A0 =C2=A0 =C2=A0The hashlock branch requires not just Alice, b= ut also Bob.
> >=C2=A0 =C2=A0 =C2=A0The timelock branch at T+24 just requires Bob.=
> >
> > 7.=C2=A0 Alice and Bob generate the claim transaction.
> >=C2=A0 =C2=A0 =C2=A0This spends the funding transaction HTLC outpu= t and pays out 1,000,000 WJT to Alice and 10,000 WJT to Bob.
> >
> > 8.=C2=A0 Alice and Bob sign the claim transaction.
> >=C2=A0 =C2=A0 =C2=A0This does not allow Bob to make the claim tran= saction valid by itself as it still requires the preimage, and at this poin= t, only Alice knows the preimage.
> >
> > 9.=C2=A0 Alice and Bob sign the funding transaction and broadcast= it.
> > 10.=C2=A0 Alice completes the claim transaction by adding the pre= image and broadcasts it.
> > 11.=C2=A0 Bob sees the preimage on the WJT blockchain and claims = the BTC using the preimage.
> >
> > If Bob stalls at step 8, then there is no way to claim the premiu= m, as the funding transaction (which is the source of the claim transaction= that pays the premium) is not valid yet.
> > After step 9, Bob has been forced to participate and cannot back = out and claim the premium only.
> > This is basically this proposal: https://lists.linuxfoundation.org/pipermail/lightn= ing-dev/2019-January/001798.html
> > In addition, if you really want the premium to be denominated in = BTC, I have a more complicated ritual: https://lists.linuxfoundation.org/pipermail/lightning-= dev/2019-January/001795.html
> > The described ritual only sets up the American Call Option, but b= y the time it has been set up, the premium has been paid already and the re= st of the execution is claiming the American Call Option.
> > Thus, I believe there is no need to add `OP_LOOKUP_OUTPUT`.
> > Regards,
> > ZmnSCPxj


--00000000000007546b058fc2e52d--