Return-Path: 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 Date: Fri, 17 Sep 2021 09:58:45 -0700 X-Gmail-Original-Message-ID: Message-ID: To: Bitcoin development mailing list , lightning-dev 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 --000000000000d5d82d05cc33d8b1 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Bitcoin & LN Devs,

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=A0https://t.me/op_ctv or=C2=A0https://t.me/bips_activation group. I'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>
Best,

Jere= my


Hi,

I'd like t= o propose an alternative to BIP-118 [1] that is both safer and more
powe= rful. 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 proto= cols
using IIDs that are far more scalable and usable than those propose= d for BIP-118
(including eltoo [3]).

Like BIP-118, IIDs are a pro= posal for a softfork that changes the rules for
calculating certain sign= atures. BIP-118 supports signatures that do not
commit to the transactio= n ID of the parent transaction, thus allowing "floating
transaction= s". In contrast, the IID proposal does not allow floating
transacti= ons, but it does allow an output to specify that child transaction
signa= tures commit to the parent transaction's IID, rather than its transacti= on
ID.

IID Definitions
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D
* 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 wit= h version 2
=C2=A0 and a 32-byte witness program, and is a "non-IID= output" otherwise.
* A transaction is an "IID transaction&quo= t; if it has at least one IID output.
* If T is a non-IID transaction, o= r a coinbase transaction, IID(T) =3D TXID(T).
* If T is a non-coinbase I= ID transaction, first_parent(T) =3D F is the transaction
=C2=A0 referenc= ed by the OutPoint in T's input 0, and IID(T) =3D hash(IID(F) || F_idx)=
=C2=A0 where F_idx is the index field in the OutPoint in T's input = 0 (that is, T's
=C2=A0 input 0 spends F's output F_idx).

= IID Signature Validation
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D
* Signatures that spend IID outputs commit t= o signature messages in which IIDs
=C2=A0 replace transaction IDs in all= OutPoints of the child transaction that spend
=C2=A0 IID outputs.
Note that IID(T) can be calculated from T (if it is a non-IID or a coinba= se
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, th= e 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 t= hat 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 so= me exactly-specified transaction (such as being the
first child of the s= econd child of a specific transaction). As a result, a
transaction that = is signed using IIDs cannot be used more than once or in an
unanticipate= d location, thus making it much safer than a floating transaction.

2= -Party Channel Protocols
=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
BIP-118 supports the eltoo protocol [3] f= or 2-party channels, which improves
upon the Lightning protocol for 2-pa= rty channels [4] by:
1) simplifying the protocol,
2) eliminating pena= lty transactions, and
3) supporting late determination of transaction fe= es [1, Sec. 4.1.5].

The IID proposal does not support the eltoo prot= ocol. However, the IID proposal
does support a 2-party channel protocol,= called 2Stage [2, Sec. 3.3], that is
arguably better than eltoo. Specif= ically, 2Stage achieves eltoo's 3 improvements
listed above, plus it= :
4) eliminates the need for watchtowers [2, Sec. 3.6], and
5) has co= nstant (rather than linear) worst-case on-chain costs [2, Sec. 3.4].
Channel Factories
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3DIn general, an on-chain transaction is required to create or close a 2-pa= rty
channel. Multi-party channel factories have been proposed in order t= o allow a
fixed set of parties to create and close numerous 2-party chan= nels between them,
thus amortizing the on-channel costs of those channel= s [5]. BIP-118 also
supports simple and efficient multi-party channel fa= ctories via the eltoo
protocol [1, Sec. 5.2] (which are called "mul= ti-party channels" in that paper).

While the IID proposal does = not support the eltoo protocol, it does support
channel factories that a= re far more scalable and powerful than any previously-
proposed channel = factories (including eltoo factories). Specifically, IIDs
support a simp= le factory protocol in which not all parties need to sign the
factory&#= 39;s funding transaction [2, Sec. 5.3], thus greatly improving the scaleof the factory (at the expense of requiring an on-chain transaction to upd= ate
the set of channels created by the factory). These channel factories= can be
combined with the 2Stage protocol to create trust-free and watch= tower-free
channels including very large numbers of casual users.
Furthermore, IIDs support channel factories with an unbounded number of pa= rties
that allow all of the channels in the factory to be bought and sol= d by anyone
(including parties not originally in the factory) with a sin= gle 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 c= hannel factory protocols make
critical use of IIDs and do not appear to = be possible with BIP-118.

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

The paper also includes 3= options for how IIDs could be added to Bitcoin via a
softfork [2, Appen= dix 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
appr= eciate it if they were willing to pick the best option (or invent an evenbetter option) for adding IIDs to Bitcoin and create a BIP for that optio= n.
Hopefully, IIDs will provide a safe way to dramatically scale Bitcoin= while
improving its usability.

Thanks,
John


Refere= nces
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

[1] BIP-118: https://anyprevout.xyz and https://github.com/bitcoin/bips/pull/943
[2] Scaling Bitcoing with Inherited IDs, by John Law:
=C2=A0 =C2=A0= iids13.pdf at https://git= hub.com/JohnLaw2/btc-iids

[3] eltoo: A Simple Layer2 Protocol fo= r Bitcoin, by Decker, Russell & Osuntokun:
=C2=A0 =C2=A0 https://blockstream.com/eltoo.pdf
[4] The Bitcoin Lightning Network, by Poon & Dryja:
=C2=A0 =C2= =A0 https= ://lightning.network/lightning-network-paper.pdf

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

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

Also, thanks to Bob McElra= th for his original brainstorm that led to the
creation of the IID conce= pt:
https://diyhpl.us/wiki/transcripts/2019-02-09-mcel= rath-on-chain-defense-in-depth

--000000000000d5d82d05cc33d8b1--