path: root/58/8310ec797f594d8cf308810cfdbd55527e1d3e

Return-Path: <jlrubin@mit.edu>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 6A0A7C000D;
 Fri, 17 Sep 2021 16:59:02 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 4F57340766;
 Fri, 17 Sep 2021 16:59:02 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: 0.476
X-Spam-Level: 
X-Spam-Status: No, score=0.476 tagged_above=-999 required=5
 tests=[BAYES_50=0.8, HTML_MESSAGE=0.001, PDS_OTHER_BAD_TLD=1.975,
 RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Received: from smtp2.osuosl.org ([127.0.0.1])
 by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id G19mDaVTIn-s; Fri, 17 Sep 2021 16:59:00 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11])
 by smtp2.osuosl.org (Postfix) with ESMTPS id A765540173;
 Fri, 17 Sep 2021 16:58:59 +0000 (UTC)
Received: from mail-il1-f180.google.com (mail-il1-f180.google.com
 [209.85.166.180]) (authenticated bits=0)
 (User authenticated as jlrubin@ATHENA.MIT.EDU)
 by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id 18HGwvDw009217
 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT);
 Fri, 17 Sep 2021 12:58:57 -0400
Received: by mail-il1-f180.google.com with SMTP id a20so10964010ilq.7;
 Fri, 17 Sep 2021 09:58:57 -0700 (PDT)
X-Gm-Message-State: AOAM530LmnvJ6ay62Y87lI5y9BZd+sF4GsNBoIOXT7q8gHvAqFU2YGrf
 aMZoB2hycsDBoQ66/H7J67mu12rPw/z9FSiYU04=
X-Google-Smtp-Source: ABdhPJyfeOewRuRkUwe+JMH8XzU7EPcb6iJO9hlFiEv/aSImVbFvvyS1ONI6JCjZAEmgVmhwotHB/r7pWVePE3EMjAE=
X-Received: by 2002:a92:c0c4:: with SMTP id t4mr9013143ilf.235.1631897936842; 
 Fri, 17 Sep 2021 09:58:56 -0700 (PDT)
MIME-Version: 1.0
From: Jeremy <jlrubin@mit.edu>
Date: Fri, 17 Sep 2021 09:58:45 -0700
X-Gmail-Original-Message-ID: <CAD5xwhh-1zUbPgYW6hE8q3CmhFZFdEqjx5pB7+VFM4mV=1FfaQ@mail.gmail.com>
Message-ID: <CAD5xwhh-1zUbPgYW6hE8q3CmhFZFdEqjx5pB7+VFM4mV=1FfaQ@mail.gmail.com>
To: Bitcoin development mailing list <bitcoin-dev@lists.linuxfoundation.org>, 
 lightning-dev <lightning-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000d5d82d05cc33d8b1"
Subject: [bitcoin-dev] Inherited IDs - A safer,
 more powerful alternative to BIP-118 (ANYPREVOUT) for scaling
 Bitcoin
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 17 Sep 2021 16:59:02 -0000

--000000000000d5d82d05cc33d8b1
Content-Type: text/plain; charset="UTF-8"

Bitcoin & LN Devs,

The below is a message that was shared to me by an anon account on Telegram
(nym: John Law). You can chat with them directly in the https://t.me/op_ctv
or https://t.me/bips_activation group. I'm reproducing it here at their
request as they were unsure of how to post to the mailing list without
compromising their identity (perhaps we should publish a guideline on how
to do so?).

Best,

Jeremy


Hi,

I'd like to propose an alternative to BIP-118 [1] that is both safer and
more
powerful. The proposal is called Inherited IDs (IIDs) and is described in a
paper that can be found here [2]. The paper presents IIDs and Layer 2
protocols
using IIDs that are far more scalable and usable than those proposed for
BIP-118
(including eltoo [3]).

Like BIP-118, IIDs are a proposal for a softfork that changes the rules for
calculating certain signatures. BIP-118 supports signatures that do not
commit to the transaction ID of the parent transaction, thus allowing
"floating
transactions". In contrast, the IID proposal does not allow floating
transactions, but it does allow an output to specify that child transaction
signatures commit to the parent transaction's IID, rather than its
transaction
ID.

IID Definitions
===============
* If T is a transaction, TXID(T) is the transaction ID of T.
* An output is an "IID output" if it is a native SegWit output with version
2
  and a 32-byte witness program, and is a "non-IID output" otherwise.
* A transaction is an "IID transaction" if it has at least one IID output.
* If T is a non-IID transaction, or a coinbase transaction, IID(T) =
TXID(T).
* If T is a non-coinbase IID transaction, first_parent(T) = F is the
transaction
  referenced by the OutPoint in T's input 0, and IID(T) = hash(IID(F) ||
F_idx)
  where F_idx is the index field in the OutPoint in T's input 0 (that is,
T's
  input 0 spends F's output F_idx).

IID Signature Validation
========================
* Signatures that spend IID outputs commit to signature messages in which
IIDs
  replace transaction IDs in all OutPoints of the child transaction that
spend
  IID outputs.

Note that IID(T) can be calculated from T (if it is a non-IID or a coinbase
transaction) or from T and F (otherwise). Therefore, as long as nodes store
(or
calculate) the IID of each transaction in the UTXO set, they can validate
signatures of transactions that spend IID outputs. Thus, the IID proposal
fits
Bitcoin's existing UTXO model, at the small cost of adding a 32-byte IID
value
for certain unspent outputs. Also, note that the IID of a transaction may
not
commit to the exact contents of the transaction, but it does commit to how
the
transaction is related to some exactly-specified transaction (such as being
the
first child of the second child of a specific transaction). As a result, a
transaction that is signed using IIDs cannot be used more than once or in an
unanticipated location, thus making it much safer than a floating
transaction.

2-Party Channel Protocols
=========================
BIP-118 supports the eltoo protocol [3] for 2-party channels, which improves
upon the Lightning protocol for 2-party channels [4] by:
1) simplifying the protocol,
2) eliminating penalty transactions, and
3) supporting late determination of transaction fees [1, Sec. 4.1.5].

The IID proposal does not support the eltoo protocol. However, the IID
proposal
does support a 2-party channel protocol, called 2Stage [2, Sec. 3.3], that
is
arguably better than eltoo. Specifically, 2Stage achieves eltoo's 3
improvements
listed above, plus it:
4) eliminates the need for watchtowers [2, Sec. 3.6], and
5) has constant (rather than linear) worst-case on-chain costs [2, Sec.
3.4].

Channel Factories
=================
In general, an on-chain transaction is required to create or close a 2-party
channel. Multi-party channel factories have been proposed in order to allow
a
fixed set of parties to create and close numerous 2-party channels between
them,
thus amortizing the on-channel costs of those channels [5]. BIP-118 also
supports simple and efficient multi-party channel factories via the eltoo
protocol [1, Sec. 5.2] (which are called "multi-party channels" in that
paper).

While the IID proposal does not support the eltoo protocol, it does support
channel factories that are far more scalable and powerful than any
previously-
proposed channel factories (including eltoo factories). Specifically, IIDs
support a simple factory protocol in which not all parties need to sign the
factory's funding transaction [2, Sec. 5.3], thus greatly improving the
scale
of the factory (at the expense of requiring an on-chain transaction to
update
the set of channels created by the factory). These channel factories can be
combined with the 2Stage protocol to create trust-free and watchtower-free
channels including very large numbers of casual users.

Furthermore, IIDs support channel factories with an unbounded number of
parties
that allow all of the channels in the factory to be bought and sold by
anyone
(including parties not originally in the factory) with a single on-chain
transaction in a trust-free manner [2, Secs. 6 and 7]. As a result, a single
on-chain transaction can be used in place of thousands, or even millions, of
Lightning or eltoo on-chain transactions. These channel factory protocols
make
critical use of IIDs and do not appear to be possible with BIP-118.

Next Steps
==========
If IIDs sounds interesting, please take a look at the IID paper [2]. It
contains
many results not listed above, including rules for SVP nodes, protocols for
off-chain channel networks, Layer 2 protocol extensions, support for
covenants
(including vaults), and nearly matching lower and upper bounds on
multi-party
channels.

The paper also includes 3 options for how IIDs could be added to Bitcoin
via a
softfork [2, Appendix A]. I'm new to Bitcoin and am not sure which of these
3
options is best. If anyone finds the IID proposal valuable, I would greatly
appreciate it if they were willing to pick the best option (or invent an
even
better option) for adding IIDs to Bitcoin and create a BIP for that option.
Hopefully, IIDs will provide a safe way to dramatically scale Bitcoin while
improving its usability.

Thanks,
John


References
==========

[1] BIP-118: https://anyprevout.xyz and
https://github.com/bitcoin/bips/pull/943

[2] Scaling Bitcoing with Inherited IDs, by John Law:
    iids13.pdf at https://github.com/JohnLaw2/btc-iids

[3] eltoo: A Simple Layer2 Protocol for Bitcoin, by Decker, Russell &
Osuntokun:
    https://blockstream.com/eltoo.pdf

[4] The Bitcoin Lightning Network, by Poon & Dryja:
    https://lightning.network/lightning-network-paper.pdf

[5] Scalable Funding of Bitcoin Micropayment Channel Networks, by Burchert,
    Decker & Wattenhofer: http://dx.doi.org/10.1098/rsos.180089

Acknowledgments
===============
Thanks to Ruben Somsen and Jeremy Rubin for their helpful comments.

Also, thanks to Bob McElrath for his original brainstorm that led to the
creation of the IID concept:
https://diyhpl.us/wiki/transcripts/2019-02-09-mcelrath-on-chain-defense-in-depth

<https://twitter.com/JeremyRubin>

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

<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:arial,he=
lvetica,sans-serif;font-size:small;color:#000000">Bitcoin &amp; LN Devs,</d=
iv><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-s=
erif;font-size:small;color:#000000"><br></div><div class=3D"gmail_default" =
style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:#0000=
00">The below is a message that was shared to me by an anon account on Tele=
gram (nym: John Law). You can chat with them directly in the=C2=A0<a href=
=3D"https://t.me/op_ctv">https://t.me/op_ctv</a> or=C2=A0<a href=3D"https:/=
/t.me/bips_activation">https://t.me/bips_activation</a> group. I&#39;m repr=
oducing it here at their request as they were unsure of how to post to the =
mailing list without compromising their identity (perhaps we should publish=
 a guideline on how to do so?).</div><div class=3D"gmail_default" style=3D"=
font-family:arial,helvetica,sans-serif;font-size:small;color:#000000"><br><=
/div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans=
-serif;font-size:small;color:#000000"><div class=3D"gmail_default">Best,</d=
iv><div class=3D"gmail_default"><br></div><div class=3D"gmail_default">Jere=
my</div><div class=3D"gmail_default"><br></div><div class=3D"gmail_default"=
><br></div></div><div class=3D"gmail_default" style=3D"font-family:arial,he=
lvetica,sans-serif;font-size:small;color:#000000">Hi,<br><br>I&#39;d like t=
o propose an alternative to BIP-118 [1] that is both safer and more<br>powe=
rful. The proposal is called Inherited IDs (IIDs) and is described in a<br>=
paper that can be found here [2]. The paper presents IIDs and Layer 2 proto=
cols<br>using IIDs that are far more scalable and usable than those propose=
d for BIP-118<br>(including eltoo [3]).<br><br>Like BIP-118, IIDs are a pro=
posal for a softfork that changes the rules for<br>calculating certain sign=
atures. BIP-118 supports signatures that do not<br>commit to the transactio=
n ID of the parent transaction, thus allowing &quot;floating<br>transaction=
s&quot;. In contrast, the IID proposal does not allow floating<br>transacti=
ons, but it does allow an output to specify that child transaction<br>signa=
tures commit to the parent transaction&#39;s IID, rather than its transacti=
on<br>ID.<br><br>IID Definitions<br>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D<br>* If T is a transaction, TXID(T) is the transaction ID of T.<br>*=
 An output is an &quot;IID output&quot; if it is a native SegWit output wit=
h version 2<br>=C2=A0 and a 32-byte witness program, and is a &quot;non-IID=
 output&quot; otherwise.<br>* A transaction is an &quot;IID transaction&quo=
t; if it has at least one IID output.<br>* If T is a non-IID transaction, o=
r a coinbase transaction, IID(T) =3D TXID(T).<br>* If T is a non-coinbase I=
ID transaction, first_parent(T) =3D F is the transaction<br>=C2=A0 referenc=
ed by the OutPoint in T&#39;s input 0, and IID(T) =3D hash(IID(F) || F_idx)=
<br>=C2=A0 where F_idx is the index field in the OutPoint in T&#39;s input =
0 (that is, T&#39;s<br>=C2=A0 input 0 spends F&#39;s output F_idx).<br><br>=
IID Signature Validation<br>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>* Signatures that spend IID outputs commit t=
o signature messages in which IIDs<br>=C2=A0 replace transaction IDs in all=
 OutPoints of the child transaction that spend<br>=C2=A0 IID outputs.<br><b=
r>Note that IID(T) can be calculated from T (if it is a non-IID or a coinba=
se<br>transaction) or from T and F (otherwise). Therefore, as long as nodes=
 store (or<br>calculate) the IID of each transaction in the UTXO set, they =
can validate<br>signatures of transactions that spend IID outputs. Thus, th=
e IID proposal fits<br>Bitcoin&#39;s existing UTXO model, at the small cost=
 of adding a 32-byte IID value<br>for certain unspent outputs. Also, note t=
hat the IID of a transaction may not<br>commit to the exact contents of the=
 transaction, but it does commit to how the<br>transaction is related to so=
me exactly-specified transaction (such as being the<br>first child of the s=
econd child of a specific transaction). As a result, a<br>transaction that =
is signed using IIDs cannot be used more than once or in an<br>unanticipate=
d location, thus making it much safer than a floating transaction.<br><br>2=
-Party Channel Protocols<br>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>BIP-118 supports the eltoo protocol [3] f=
or 2-party channels, which improves<br>upon the Lightning protocol for 2-pa=
rty channels [4] by:<br>1) simplifying the protocol,<br>2) eliminating pena=
lty transactions, and<br>3) supporting late determination of transaction fe=
es [1, Sec. 4.1.5].<br><br>The IID proposal does not support the eltoo prot=
ocol. However, the IID proposal<br>does support a 2-party channel protocol,=
 called 2Stage [2, Sec. 3.3], that is<br>arguably better than eltoo. Specif=
ically, 2Stage achieves eltoo&#39;s 3 improvements<br>listed above, plus it=
:<br>4) eliminates the need for watchtowers [2, Sec. 3.6], and<br>5) has co=
nstant (rather than linear) worst-case on-chain costs [2, Sec. 3.4].<br><br=
>Channel Factories<br>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<b=
r>In general, an on-chain transaction is required to create or close a 2-pa=
rty<br>channel. Multi-party channel factories have been proposed in order t=
o allow a<br>fixed set of parties to create and close numerous 2-party chan=
nels between them,<br>thus amortizing the on-channel costs of those channel=
s [5]. BIP-118 also<br>supports simple and efficient multi-party channel fa=
ctories via the eltoo<br>protocol [1, Sec. 5.2] (which are called &quot;mul=
ti-party channels&quot; in that paper).<br><br>While the IID proposal does =
not support the eltoo protocol, it does support<br>channel factories that a=
re far more scalable and powerful than any previously-<br>proposed channel =
factories (including eltoo factories). Specifically, IIDs<br>support a simp=
le factory protocol in which not all parties need to sign the <br>factory&#=
39;s funding transaction [2, Sec. 5.3], thus greatly improving the scale<br=
>of the factory (at the expense of requiring an on-chain transaction to upd=
ate<br>the set of channels created by the factory). These channel factories=
 can be<br>combined with the 2Stage protocol to create trust-free and watch=
tower-free<br>channels including very large numbers of casual users.<br><br=
>Furthermore, IIDs support channel factories with an unbounded number of pa=
rties<br>that allow all of the channels in the factory to be bought and sol=
d by anyone<br>(including parties not originally in the factory) with a sin=
gle on-chain<br>transaction in a trust-free manner [2, Secs. 6 and 7]. As a=
 result, a single<br>on-chain transaction can be used in place of thousands=
, or even millions, of<br>Lightning or eltoo on-chain transactions. These c=
hannel factory protocols make<br>critical use of IIDs and do not appear to =
be possible with BIP-118.<br><br>Next Steps<br>=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D<br>If IIDs sounds interesting, please take a look at the IID paper [2].=
 It contains<br>many results not listed above, including rules for SVP node=
s, protocols for<br>off-chain channel networks, Layer 2 protocol extensions=
, support for covenants<br>(including vaults), and nearly matching lower an=
d upper bounds on multi-party<br>channels.<br><br>The paper also includes 3=
 options for how IIDs could be added to Bitcoin via a<br>softfork [2, Appen=
dix A]. I&#39;m new to Bitcoin and am not sure which of these 3<br>options =
is best. If anyone finds the IID proposal valuable, I would greatly<br>appr=
eciate it if they were willing to pick the best option (or invent an even<b=
r>better option) for adding IIDs to Bitcoin and create a BIP for that optio=
n.<br>Hopefully, IIDs will provide a safe way to dramatically scale Bitcoin=
 while<br>improving its usability.<br><br>Thanks,<br>John<br><br><br>Refere=
nces<br>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br><br>[1] BIP-118: <a href=3D"https=
://anyprevout.xyz">https://anyprevout.xyz</a> and <a href=3D"https://github=
.com/bitcoin/bips/pull/943">https://github.com/bitcoin/bips/pull/943</a><br=
><br>[2] Scaling Bitcoing with Inherited IDs, by John Law:<br>=C2=A0 =C2=A0=
 iids13.pdf at <a href=3D"https://github.com/JohnLaw2/btc-iids">https://git=
hub.com/JohnLaw2/btc-iids</a><br><br>[3] eltoo: A Simple Layer2 Protocol fo=
r Bitcoin, by Decker, Russell &amp; Osuntokun:<br>=C2=A0 =C2=A0 <a href=3D"=
https://blockstream.com/eltoo.pdf">https://blockstream.com/eltoo.pdf</a><br=
><br>[4] The Bitcoin Lightning Network, by Poon &amp; Dryja:<br>=C2=A0 =C2=
=A0 <a href=3D"https://lightning.network/lightning-network-paper.pdf">https=
://lightning.network/lightning-network-paper.pdf</a><br><br>[5] Scalable Fu=
nding of Bitcoin Micropayment Channel Networks, by Burchert,<br>=C2=A0 =C2=
=A0 Decker &amp; Wattenhofer: <a href=3D"http://dx.doi.org/10.1098/rsos.180=
089">http://dx.doi.org/10.1098/rsos.180089</a><br><br>Acknowledgments<br>=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>Thanks to Ruben Somsen and=
 Jeremy Rubin for their helpful comments.<br><br>Also, thanks to Bob McElra=
th for his original brainstorm that led to the<br>creation of the IID conce=
pt:<br><a href=3D"https://diyhpl.us/wiki/transcripts/2019-02-09-mcelrath-on=
-chain-defense-in-depth">https://diyhpl.us/wiki/transcripts/2019-02-09-mcel=
rath-on-chain-defense-in-depth</a><br></div><br><div><div dir=3D"ltr" class=
=3D"gmail_signature" data-smartmail=3D"gmail_signature"><div dir=3D"ltr"><a=
 href=3D"https://twitter.com/JeremyRubin" target=3D"_blank"></a></div></div=
></div></div>

--000000000000d5d82d05cc33d8b1--