From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id CC532DD8 for ; Thu, 19 Sep 2019 08:39:14 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-lf1-f67.google.com (mail-lf1-f67.google.com [209.85.167.67]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1B20B108 for ; Thu, 19 Sep 2019 08:39:13 +0000 (UTC) Received: by mail-lf1-f67.google.com with SMTP id r2so1712714lfn.8 for ; Thu, 19 Sep 2019 01:39:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=iFhHw1tljHvtLVFgPndALt1xAhQq8J8EycY+/0DYUOI=; b=F/sVu2ctnbiqkZZZi2dDla2OApPBpck/mBfB6JYQW4c25FRr/D8Bi9BnkfY9qfwTvc YuSNUH5Y9JY2RYIYR60PZIcaP7IOA5cFM+TCk61WDlXInl1bvOLo8rw/fk3chqbTnN1K 06AeD7lhKq4OwemVVdZo86g2gfiUF3mCt4Q3YhIqXCBXk1W9ACk4vmOQJInee+tqwiPo poSel0IlvCAjcYD/A1dCVySsIOogK1A8DfO2ofuoioLk7jj1QnIKM3sTJttJnUfVgy20 3HUPTFgEmJuhcl05w6DLjajRKY+wiS3Q35ir5Stl/TVibMCjcyKX6TAxqm+T5WEJ+ZZa 9HwA== 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; bh=iFhHw1tljHvtLVFgPndALt1xAhQq8J8EycY+/0DYUOI=; b=sUepJIp8CiIZuPsRvWLKc0k6BylsBiA+1EnZBocHnXgRB84ENZg4t1fkJWcaJcCbyV WOhXtHVz4Nx2KLFEf4UWx4o0N7F3Xqep5HBTvy03p44y9SaaoQIUKz5XoLDY21viqRIu Iu/IlQaV2j8fGkJMs3UCf/wDvfU5zkcghkjLekyB+Pq8gScjPRnRY0V1EgUfeIczvGzS fiApRnmoXpnY1PnGbsUcMcDa0v2rkYcRrV6b3SRwb80k1W4lsbYHLWvxCAO8ZEc7/oO+ OaePe3uARksbCQ/q9hfbJhZoGBLB37KRrQKZnGE3Jn6KPiU//d/semlOuwonX4ImXFgd T7WA== X-Gm-Message-State: APjAAAWxPa0KYmicre5KeAugoDoFamvXVvFwMRFp2hgWWRbpXj/oDh8j uWOZcsDa947QFcSfr+sCElVba2i6APTVcMcsvF4klGFU X-Google-Smtp-Source: APXvYqxsR2iaDOLwDuCMwjjmcVamvHzNgqqD+SwxakD+2FPNULWpsTDILf/LKl6Dwau80U9OAWNr0CN45S8T3JVRu6I= X-Received: by 2002:ac2:5e9e:: with SMTP id b30mr4383974lfq.5.1568882351104; Thu, 19 Sep 2019 01:39:11 -0700 (PDT) MIME-Version: 1.0 References: <7e7SBK5tLdpzTkgh-sNrAZR7qnPfu_i0tHY5ia4pk3Mjdw3dSZx3kcKiIMC9Hmu_lp8Y3mBFqlqsA_iHobJo58MSiW8NW1zKHUQKOWuuw4c=@protonmail.com> In-Reply-To: <7e7SBK5tLdpzTkgh-sNrAZR7qnPfu_i0tHY5ia4pk3Mjdw3dSZx3kcKiIMC9Hmu_lp8Y3mBFqlqsA_iHobJo58MSiW8NW1zKHUQKOWuuw4c=@protonmail.com> From: Martin Schwarz Date: Thu, 19 Sep 2019 10:39:00 +0200 Message-ID: To: ZmnSCPxj via bitcoin-dev Content-Type: multipart/alternative; boundary="0000000000003b66ba0592e3e364" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, 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: Thu, 19 Sep 2019 10:38:47 +0000 Subject: Re: [bitcoin-dev] Timelocks and Lightning on MimbleWimble 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: Thu, 19 Sep 2019 08:39:14 -0000 --0000000000003b66ba0592e3e364 Content-Type: text/plain; charset="UTF-8" Isn't there some way to "rebase" a relative lock-time to some anchor even further in the past while cancelling out the intermediate transactions? best regards, Martin On Thu, Sep 19, 2019 at 9:52 AM ZmnSCPxj via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Good morning list, > > I was reading transcript of recent talk: > https://diyhpl.us/wiki/transcripts/scalingbitcoin/tel-aviv-2019/edgedevplusplus/blockchain-design-patterns/ > > And in section "Taproot: main idea": > > > Q: Can you do timelocks iwth adaptor signatures? > > > > ... > > > > A: This is one way it's being proposed by mimblewimble; but this > requires the ability to aggregate signatures across transactions. > > > > Q: No, there's two transactions already existing. Before locktime, you > can spend wit hthe adaptor signature one like atomic swaps. After locktime, > the other one becomes valid and you can spend with that. They just double > spend each other. > > > > A: You'd have to diagram that out for me. There's a few ways to do this, > some that I know, but yours isn't one of them. > > I believe what is being referred to here is to simply have an `nLockTime` > transaction that is signed by all participants first, and serves as the > "timelock" path. > Then, another transaction is created, for which adaptor signatures are > given, before completing the ritual to create a "hashlock" path. > > I find it surprising that this is not well-known. > I describe it here tangentially, for instance: > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-April/016888.html > The section "Payjoin2swap Swap Protocol" refers to "pre-swap transaction" > and "pre-swap backout transaction", which are `nLockTime`d transactions. > Later transactions then use a Scriptless Script-like construction to > transfer information about a secret scalar x. > > My understanding of MimbleWimble is that: > > * There must exist a proof-of-knowledge of the sum of blinding factors > used. > This can be trivially had by using a signature of this sum, signing an > empty message or "kernel". > * I believe I have seen at least one proposal (I cannot find it again now) > where the "kernel" is replaced with an `nLockTime`-equivalent. > Basically, the `nLockTime` would have to be explicitly published, and it > would be rejected for a block if the `nLockTime` was less than the block > height. > * There may or may not exist some kind of proof where the message being > signed is an integer that is known to be no greater than a particular > value, and multiple signatures that signed a lower value can somehow be > aggregated to a higher value, which serves this purpose as well, but is > compressible. > > My understanding is thus that the above `nLockTime` technique is what is > indeed intended for MimbleWimble cross-system atomic swaps. > > -------- > > However, I believe that Lightning and similar offchain protocols are **not > possible** on MimbleWimble, at least if we want to retain its "magical > shrinking blockchain" property. > > All practical channel constructions with indefinite lifetime require the > use of *relative* locktime. > Of note is that `nLockTime` represents an *absolute* lifetime. > > The only practical channel constructions I know of that do not require > *relative* locktime (mostly various variants of Spilman channels) have a > fixed lifetime, i.e. the channel will have to be closed before the lifetime > arrives. > This is impractical for a scaling network. > > It seems to me that some kind of "timeout" is always necessary, similar to > the timeout used in SPV-proof sidechains, in order to allow an existing > claimed-latest-state to be proven as not-actually-latest. > > * In Poon-Dryja, knowledge of the revocation key by the other side proves > the published claimed-latest-state is not-actually-latest and awards the > entire amount to the other party. > * This key can only be presented during the timeout, a security > parameter. > * In Decker-Wattenhofer decrementing-`nSequence` channels, a kickoff > starts this timeout, and only the smallest-timeout state gets onchain, due > to it having a time advantage over all other versions. > * In indefinite-lifetime Spilman channels (also described in the > Decker-Wattenhofer paper), the absolute-timelock initial backoff > transaction is replaced with a kickoff + relative-locktime transaction. > * In Decker-Russell-Osuntokun, each update transaction has an imposed > `nSequence` that forces a state transaction to be delayed compared to the > update transaction it is paired with. > > It seems that all practical offchain updateable cryptocurrency systems, > some kind of "timeout" is needed during which participants have an > opportunity to claim an alternative version of some previous claim of > correct state. > > This timeout could be implemented as either relative or absolute lock > time, but obviously an absolute locktime would create a limit on the > lifetime of the channel. > Thus, if we were to target an indefinite-lifetime channel, we must use > relative lock times, with the timeout starting only when the unilateral > close is initiated by one participant. > > Now, let us turn back to the MimbleWimble. > As it happens, we do *not* actually need SCRIPT to implement these > offchain updateable cryptocurrency systems. > 2-of-2 is often enough (and with Schnorr and other homomorphic signatures, > this is possible without explicit script, only pubkeys and signatures, > which MimbleWimble supports). > > * Poon-Dryja revocation can be rewritten as an HTLC-like construct (indeed > this was the original formulation). > * Since we have shown that, by use of two transaction alternatives, one > timelocked and the other hashlocked, we can implement an HTLC-like > construct on MimbleWimble, that is enough. > * Relative locktimes in Decker-Wattenhofer are imposed by simple > `nSequence`, not by `OP_CSV`. > HTLCs hosted inside such constructions can again use the > two-transactions construct in MimbleWimble. > * Ditto with indefinite-lifetime Spilman. > * Ditto with Decker-Russell-Osuntokun. > * The paper shows the use of `OP_CSV`, but aj notes it is redundant, and > I agree: > https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-March/001933.html > > Thus, it is not the "nonexistence of SCRIPT" that prevents Lightning from > being deployed on MimbleWimble. > > Instead, it is the "nonexistence of **relative** locktime" that prevents > Lightning over MimbleWimble. > > Why would **relative** locktimes not possibly exist? > In order to **validate** a relative locktime, we need to know the > blockheight that the output we are spending was confirmed in. > > But the entire point of the "magical shrinking blockchain" is that > already-spent outputs can be removed completely and all that needs to be > validated by a new node is: > > * The coin-creation events. > * The current UTXO set (plus attached rangeproofs). > * The blinding keys. > * Signatures of the blinding keys, and the kernels they sign (if we use > the "kernels encode `nLockTime`" technique in some way, they should not > exceed the current supposed blockheight). > > The problem is that an output that exists in the UTXO set might be > invalid, if it appears "too near" to an `nSequence` minimum spend of a > previous output that was spent in its creation. > That is, the above does not allow validation of **relative** locktimes, > only **absolute locktimes**. > (At least as far as I understand: there may be special cryptographic > constructs that allow signatures to reliably commit to some relative > locktime). > > This means that relative locktimes need to be implemented by showing the > transactions that spend previous UTXOS and create the current UTXOs, and so > no backwards to coin-creation events. > This forces us back to the old "validate all transactions" model of > starting a new node (and seriously damaging the entire point of using > MimbleWimble anyway). > > I do not believe it is the lack of SCRIPT that prevents > Lightning-over-MimbleWimble, but rather the lack of relative locktime, > which seems difficult to validate without knowing the individual > transactions and when they were confirmed. > > Regards, > ZmnSCPxj > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --0000000000003b66ba0592e3e364 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Isn't there some way to "rebase" a relative = lock-time to some anchor even further in the past while cancelling out the = intermediate transactions?

best regards,
Marti= n

On Thu, Sep 19, 2019 at 9:52 AM ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfo= undation.org> wrote:
Good morning list,

I was reading transcript of recent talk: https://diyhpl.us/wiki/tran= scripts/scalingbitcoin/tel-aviv-2019/edgedevplusplus/blockchain-design-patt= erns/

And in section "Taproot: main idea":

> Q: Can you do timelocks iwth adaptor signatures?
>
> ...
>
> A: This is one way it's being proposed by mimblewimble; but this r= equires the ability to aggregate signatures across transactions.
>
> Q: No, there's two transactions already existing. Before locktime,= you can spend wit hthe adaptor signature one like atomic swaps. After lock= time, the other one becomes valid and you can spend with that. They just do= uble spend each other.
>
> A: You'd have to diagram that out for me. There's a few ways t= o do this, some that I know, but yours isn't one of them.

I believe what is being referred to here is to simply have an `nLockTime` t= ransaction that is signed by all participants first, and serves as the &quo= t;timelock" path.
Then, another transaction is created, for which adaptor signatures are give= n, before completing the ritual to create a "hashlock" path.

I find it surprising that this is not well-known.
I describe it here tangentially, for instance: https://lists.linuxfoundation.org/pipermail/bitcoi= n-dev/2019-April/016888.html
The section "Payjoin2swap Swap Protocol" refers to "pre-swap= transaction" and "pre-swap backout transaction", which are = `nLockTime`d transactions.
Later transactions then use a Scriptless Script-like construction to transf= er information about a secret scalar x.

My understanding of MimbleWimble is that:

* There must exist a proof-of-knowledge of the sum of blinding factors used= .
=C2=A0 This can be trivially had by using a signature of this sum, signing = an empty message or "kernel".
* I believe I have seen at least one proposal (I cannot find it again now) = where the "kernel" is replaced with an `nLockTime`-equivalent. =C2=A0 Basically, the `nLockTime` would have to be explicitly published, an= d it would be rejected for a block if the `nLockTime` was less than the blo= ck height.
=C2=A0 * There may or may not exist some kind of proof where the message be= ing signed is an integer that is known to be no greater than a particular v= alue, and multiple signatures that signed a lower value can somehow be aggr= egated to a higher value, which serves this purpose as well, but is compres= sible.

My understanding is thus that the above `nLockTime` technique is what is in= deed intended for MimbleWimble cross-system atomic swaps.

--------

However, I believe that Lightning and similar offchain protocols are **not = possible** on MimbleWimble, at least if we want to retain its "magical= shrinking blockchain" property.

All practical channel constructions with indefinite lifetime require the us= e of *relative* locktime.
Of note is that `nLockTime` represents an *absolute* lifetime.

The only practical channel constructions I know of that do not require *rel= ative* locktime (mostly various variants of Spilman channels) have a fixed = lifetime, i.e. the channel will have to be closed before the lifetime arriv= es.
This is impractical for a scaling network.

It seems to me that some kind of "timeout" is always necessary, s= imilar to the timeout used in SPV-proof sidechains, in order to allow an ex= isting claimed-latest-state to be proven as not-actually-latest.

* In Poon-Dryja, knowledge of the revocation key by the other side proves t= he published claimed-latest-state is not-actually-latest and awards the ent= ire amount to the other party.
=C2=A0 * This key can only be presented during the timeout, a security para= meter.
* In Decker-Wattenhofer decrementing-`nSequence` channels, a kickoff starts= this timeout, and only the smallest-timeout state gets onchain, due to it = having a time advantage over all other versions.
* In indefinite-lifetime Spilman channels (also described in the Decker-Wat= tenhofer paper), the absolute-timelock initial backoff transaction is repla= ced with a kickoff + relative-locktime transaction.
* In Decker-Russell-Osuntokun, each update transaction has an imposed `nSeq= uence` that forces a state transaction to be delayed compared to the update= transaction it is paired with.

It seems that all practical offchain updateable cryptocurrency systems, som= e kind of "timeout" is needed during which participants have an o= pportunity to claim an alternative version of some previous claim of correc= t state.

This timeout could be implemented as either relative or absolute lock time,= but obviously an absolute locktime would create a limit on the lifetime of= the channel.
Thus, if we were to target an indefinite-lifetime channel, we must use rela= tive lock times, with the timeout starting only when the unilateral close i= s initiated by one participant.

Now, let us turn back to the MimbleWimble.
As it happens, we do *not* actually need SCRIPT to implement these offchain= updateable cryptocurrency systems.
2-of-2 is often enough (and with Schnorr and other homomorphic signatures, = this is possible without explicit script, only pubkeys and signatures, whic= h MimbleWimble supports).

* Poon-Dryja revocation can be rewritten as an HTLC-like construct (indeed = this was the original formulation).
=C2=A0 * Since we have shown that, by use of two transaction alternatives, = one timelocked and the other hashlocked, we can implement an HTLC-like cons= truct on MimbleWimble, that is enough.
* Relative locktimes in Decker-Wattenhofer are imposed by simple `nSequence= `, not by `OP_CSV`.
=C2=A0 HTLCs hosted inside such constructions can again use the two-transac= tions construct in MimbleWimble.
* Ditto with indefinite-lifetime Spilman.
* Ditto with Decker-Russell-Osuntokun.
=C2=A0 * The paper shows the use of `OP_CSV`, but aj notes it is redundant,= and I agree: https:= //lists.linuxfoundation.org/pipermail/lightning-dev/2019-March/001933.html<= /a>

Thus, it is not the "nonexistence of SCRIPT" that prevents Lightn= ing from being deployed on MimbleWimble.

Instead, it is the "nonexistence of **relative** locktime" that p= revents Lightning over MimbleWimble.

Why would **relative** locktimes not possibly exist?
In order to **validate** a relative locktime, we need to know the blockheig= ht that the output we are spending was confirmed in.

But the entire point of the "magical shrinking blockchain" is tha= t already-spent outputs can be removed completely and all that needs to be = validated by a new node is:

* The coin-creation events.
* The current UTXO set (plus attached rangeproofs).
* The blinding keys.
* Signatures of the blinding keys, and the kernels they sign (if we use the= "kernels encode `nLockTime`" technique in some way, they should = not exceed the current supposed blockheight).

The problem is that an output that exists in the UTXO set might be invalid,= if it appears "too near" to an `nSequence` minimum spend of a pr= evious output that was spent in its creation.
That is, the above does not allow validation of **relative** locktimes, onl= y **absolute locktimes**.
(At least as far as I understand: there may be special cryptographic constr= ucts that allow signatures to reliably commit to some relative locktime).
This means that relative locktimes need to be implemented by showing the tr= ansactions that spend previous UTXOS and create the current UTXOs, and so n= o backwards to coin-creation events.
This forces us back to the old "validate all transactions" model = of starting a new node (and seriously damaging the entire point of using Mi= mbleWimble anyway).

I do not believe it is the lack of SCRIPT that prevents Lightning-over-Mimb= leWimble, but rather the lack of relative locktime, which seems difficult t= o validate without knowing the individual transactions and when they were c= onfirmed.

Regards,
ZmnSCPxj

_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--0000000000003b66ba0592e3e364--