MIME-Version: 1.0
References: <7e7SBK5tLdpzTkgh-sNrAZR7qnPfu_i0tHY5ia4pk3Mjdw3dSZx3kcKiIMC9Hmu_lp8Y3mBFqlqsA_iHobJo58MSiW8NW1zKHUQKOWuuw4c=@protonmail.com>
In-Reply-To: <7e7SBK5tLdpzTkgh-sNrAZR7qnPfu_i0tHY5ia4pk3Mjdw3dSZx3kcKiIMC9Hmu_lp8Y3mBFqlqsA_iHobJo58MSiW8NW1zKHUQKOWuuw4c=@protonmail.com>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Fri, 20 Sep 2019 04:54:34 +1000
Message-ID: <CAH5Bsr1G6r-g_so96ALo0gpboWDduRaZzFT7Z1rDBFdzDHsXTA@mail.gmail.com>
To: ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000009305d50592ec7dae"
Subject: Re: [bitcoin-dev] Timelocks and Lightning on MimbleWimble
Precedence: list

--0000000000009305d50592ec7dae
Content-Type: text/plain; charset="UTF-8"

Hi ZmnSCPxj,

I can give some context on the exchange during the talk. I was the "Q" and
Andrew Polestra was the "A".

I followed up with Andrew after and he indeed knew about the pre-signed
nlocktime transaction double spend technique (actually, I thought he was
the one who originally came up with that idea for scriptless atomic swaps).
He clarified saying that you can do that with locktime (absolute time
locks) but not with sequence numbers (relative time locks). i.e. to enforce
sequence numbers you need to use OP_CHECKSEQUENCEVERIFY. He said that it
would make sense to change that so it's enforced regardless of script.

However, I talked to Antoine Riard later who was adamant that sequence
numbers already worked as expected. He pointed to the fact that BIP68
already describes it as an independent constraint [1]

So if things do work as described in BIP68 then we should be able to do
lightning on Bitcoin without any script once we have Schnorr. I'm keen to
actually figure out all the details of how to do this. It works in my head
but I think I should write it down somewhere to make sure it works.

 [1] https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki

LL


On Thu, Sep 19, 2019 at 5:52 PM 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
>

--0000000000009305d50592ec7dae
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi ZmnSCPxj,<div><br></div><div>I can give some context on=
 the exchange during the talk. I was the &quot;Q&quot; and Andrew Polestra =
was the &quot;A&quot;.=C2=A0</div><div><br></div><div>I followed up with An=
drew after and he indeed knew about the pre-signed nlocktime transaction do=
uble spend technique (actually, I thought he was the one who originally cam=
e up with that idea for scriptless atomic swaps). He clarified saying that =
you can do that with locktime (absolute time locks) but not with sequence n=
umbers (relative time locks). i.e. to enforce sequence numbers you need to =
use OP_CHECKSEQUENCEVERIFY. He said that it would make sense to change that=
 so it&#39;s enforced regardless of script.<div><br></div><div>However, I t=
alked=C2=A0to Antoine Riard later who was adamant=C2=A0that sequence number=
s already worked as expected. He pointed to the fact that BIP68 already des=
cribes it as an independent constraint [1]</div><div><br></div><div>So if t=
hings do work as described in BIP68 then we should be able to do lightning =
on Bitcoin without any script once we have Schnorr. I&#39;m keen to actuall=
y figure out all the details of how to do this. It works in my head but I t=
hink I should write it down somewhere to make sure it works.</div><div><br>=
</div><div>=C2=A0[1]=C2=A0<a href=3D"https://github.com/bitcoin/bips/blob/m=
aster/bip-0068.mediawiki">https://github.com/bitcoin/bips/blob/master/bip-0=
068.mediawiki</a></div><div><br></div><div>LL</div><div><br></div></div></d=
iv><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On =
Thu, Sep 19, 2019 at 5:52 PM ZmnSCPxj via bitcoin-dev &lt;<a href=3D"mailto=
:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.o=
rg</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margi=
n:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex=
">Good morning list,<br>
<br>
I was reading transcript of recent talk: <a href=3D"https://diyhpl.us/wiki/=
transcripts/scalingbitcoin/tel-aviv-2019/edgedevplusplus/blockchain-design-=
patterns/" rel=3D"noreferrer" target=3D"_blank">https://diyhpl.us/wiki/tran=
scripts/scalingbitcoin/tel-aviv-2019/edgedevplusplus/blockchain-design-patt=
erns/</a><br>
<br>
And in section &quot;Taproot: main idea&quot;:<br>
<br>
&gt; Q: Can you do timelocks iwth adaptor signatures?<br>
&gt;<br>
&gt; ...<br>
&gt;<br>
&gt; A: This is one way it&#39;s being proposed by mimblewimble; but this r=
equires the ability to aggregate signatures across transactions.<br>
&gt;<br>
&gt; Q: No, there&#39;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.<br>
&gt;<br>
&gt; A: You&#39;d have to diagram that out for me. There&#39;s a few ways t=
o do this, some that I know, but yours isn&#39;t one of them.<br>
<br>
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&quot; path.<br>
Then, another transaction is created, for which adaptor signatures are give=
n, before completing the ritual to create a &quot;hashlock&quot; path.<br>
<br>
I find it surprising that this is not well-known.<br>
I describe it here tangentially, for instance: <a href=3D"https://lists.lin=
uxfoundation.org/pipermail/bitcoin-dev/2019-April/016888.html" rel=3D"noref=
errer" target=3D"_blank">https://lists.linuxfoundation.org/pipermail/bitcoi=
n-dev/2019-April/016888.html</a><br>
The section &quot;Payjoin2swap Swap Protocol&quot; refers to &quot;pre-swap=
 transaction&quot; and &quot;pre-swap backout transaction&quot;, which are =
`nLockTime`d transactions.<br>
Later transactions then use a Scriptless Script-like construction to transf=
er information about a secret scalar x.<br>
<br>
My understanding of MimbleWimble is that:<br>
<br>
* There must exist a proof-of-knowledge of the sum of blinding factors used=
.<br>
=C2=A0 This can be trivially had by using a signature of this sum, signing =
an empty message or &quot;kernel&quot;.<br>
* I believe I have seen at least one proposal (I cannot find it again now) =
where the &quot;kernel&quot; is replaced with an `nLockTime`-equivalent.<br=
>
=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.<br>
=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.<br>
<br>
My understanding is thus that the above `nLockTime` technique is what is in=
deed intended for MimbleWimble cross-system atomic swaps.<br>
<br>
--------<br>
<br>
However, I believe that Lightning and similar offchain protocols are **not =
possible** on MimbleWimble, at least if we want to retain its &quot;magical=
 shrinking blockchain&quot; property.<br>
<br>
All practical channel constructions with indefinite lifetime require the us=
e of *relative* locktime.<br>
Of note is that `nLockTime` represents an *absolute* lifetime.<br>
<br>
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.<br>
This is impractical for a scaling network.<br>
<br>
It seems to me that some kind of &quot;timeout&quot; 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.<br>
<br>
* 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.<br>
=C2=A0 * This key can only be presented during the timeout, a security para=
meter.<br>
* 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.<br>
* 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.<br>
* 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.<br>
<br>
It seems that all practical offchain updateable cryptocurrency systems, som=
e kind of &quot;timeout&quot; is needed during which participants have an o=
pportunity to claim an alternative version of some previous claim of correc=
t state.<br>
<br>
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.<br>
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.<br>
<br>
Now, let us turn back to the MimbleWimble.<br>
As it happens, we do *not* actually need SCRIPT to implement these offchain=
 updateable cryptocurrency systems.<br>
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).<br>
<br>
* Poon-Dryja revocation can be rewritten as an HTLC-like construct (indeed =
this was the original formulation).<br>
=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.<br>
* Relative locktimes in Decker-Wattenhofer are imposed by simple `nSequence=
`, not by `OP_CSV`.<br>
=C2=A0 HTLCs hosted inside such constructions can again use the two-transac=
tions construct in MimbleWimble.<br>
* Ditto with indefinite-lifetime Spilman.<br>
* Ditto with Decker-Russell-Osuntokun.<br>
=C2=A0 * The paper shows the use of `OP_CSV`, but aj notes it is redundant,=
 and I agree: <a href=3D"https://lists.linuxfoundation.org/pipermail/lightn=
ing-dev/2019-March/001933.html" rel=3D"noreferrer" target=3D"_blank">https:=
//lists.linuxfoundation.org/pipermail/lightning-dev/2019-March/001933.html<=
/a><br>
<br>
Thus, it is not the &quot;nonexistence of SCRIPT&quot; that prevents Lightn=
ing from being deployed on MimbleWimble.<br>
<br>
Instead, it is the &quot;nonexistence of **relative** locktime&quot; that p=
revents Lightning over MimbleWimble.<br>
<br>
Why would **relative** locktimes not possibly exist?<br>
In order to **validate** a relative locktime, we need to know the blockheig=
ht that the output we are spending was confirmed in.<br>
<br>
But the entire point of the &quot;magical shrinking blockchain&quot; is tha=
t already-spent outputs can be removed completely and all that needs to be =
validated by a new node is:<br>
<br>
* The coin-creation events.<br>
* The current UTXO set (plus attached rangeproofs).<br>
* The blinding keys.<br>
* Signatures of the blinding keys, and the kernels they sign (if we use the=
 &quot;kernels encode `nLockTime`&quot; technique in some way, they should =
not exceed the current supposed blockheight).<br>
<br>
The problem is that an output that exists in the UTXO set might be invalid,=
 if it appears &quot;too near&quot; to an `nSequence` minimum spend of a pr=
evious output that was spent in its creation.<br>
That is, the above does not allow validation of **relative** locktimes, onl=
y **absolute locktimes**.<br>
(At least as far as I understand: there may be special cryptographic constr=
ucts that allow signatures to reliably commit to some relative locktime).<b=
r>
<br>
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.<br>
This forces us back to the old &quot;validate all transactions&quot; model =
of starting a new node (and seriously damaging the entire point of using Mi=
mbleWimble anyway).<br>
<br>
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.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--0000000000009305d50592ec7dae--