public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* [bitcoin-dev] Inherited IDs - A safer, more powerful alternative to BIP-118 (ANYPREVOUT) for scaling Bitcoin
@ 2021-09-17 16:58 Jeremy
  2021-09-18 11:37 ` Anthony Towns
  2021-09-21  2:11 ` [bitcoin-dev] [Lightning-dev] " ZmnSCPxj
  0 siblings, 2 replies; 5+ messages in thread
From: Jeremy @ 2021-09-17 16:58 UTC (permalink / raw)
  To: Bitcoin development mailing list, lightning-dev

[-- Attachment #1: Type: text/plain, Size: 7155 bytes --]

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>

[-- Attachment #2: Type: text/html, Size: 9161 bytes --]

^ permalink raw reply	[flat|nested] 5+ messages in thread
* Re: [bitcoin-dev] Inherited IDs - A safer, more powerful alternative to BIP-118 (ANYPREVOUT) for scaling Bitcoin
@ 2021-10-10 22:03 jlspc
  0 siblings, 0 replies; 5+ messages in thread
From: jlspc @ 2021-10-10 22:03 UTC (permalink / raw)
  To: bitcoin-dev, lightning-dev

[-- Attachment #1: Type: text/plain, Size: 7825 bytes --]

Response to email from Anthony Towns sent on 20210918 at 11:37:40 UTC
==============================================
aj,

Thanks for taking the time to go through my paper on inherited IDs (IIDs). Also, thanks for your concise and accurate description of the IID proposal and the 2Stage channel protocol. I'm glad you feel the 2Stage protocol might be better than eltoo for a two-party channel.

I want to address other parts of the paper that were obviously not as clear, as they led to two important misunderstandings.

First, there is the issue of the use of an operator in the "timeout trees", "update-forest" and "challenge-and-response" factory protocols. While those protocols do include a party that is designated as the "operator", the operator is in no way a trusted party. While it's true that one would prefer an operator that follows the protocol fully and promptly, as that would allow one to keep the protocol off-chain, the operator can never take funds or prevent others from obtaining the funds that are due to them. In fact, this is exactly analogous to the selection of the party with whom one shares a two-party lightning channel. If one views lightning as being trust-free, then one will also view "timeout trees", "update-forest" and "challenge-and-response" to be trust-free.

Second, there is the question of whether or not IIDs can be simulated with anyprevout. I don't believe that they can. Consider for example the case where Alice has an on-chain funding transaction F1 with output F1:0 that will be spent by a (currently off-chain) transaction F2 with output F2:0 that will be spent by a settlement transaction S. Assume further that there is an on-chain control transaction C1 with output C1:0 owned by untrusted operator O, where C1:0 will be spent by a (currently off-chain) transaction C2 with output C2:0 that may, in certain cases, also be spent by S. In particular, assume F1 puts a covenant on F2 such that F2 puts a covenant on S, where the covenant on S can be met by either: A) waiting a CSV delay of one time unit (defined to be long enough to allow a party with a competing transaction to put that competing transaction on-chain first) and then spending only F2:0 (where F2:0 is referenced via IID) and giving ownership of S:0 to Alice, or B) waiting until a CLV reaches time T_lock and then spending both F2:0 and C2:0 (where F2:0 and C2:0 are referenced via IIDs).

Assume that after Alice put F1 on-chain she wants to transfer ownership of the output S:0 to Bob without having to put F2 or S on-chain. She can do this with IIDs as follows. First, Alice asks the untrusted operator O to put C2 on-chain where C2 puts a covenant on S that forces S to spend both F2:0 and C2:0 (where F2:0 and C2:0 are referenced via IIDs) and to give ownership of S:0 to Bob (by making it spendable using Bob's public key).

There are two cases. First, if O promptly puts the desired C2 on-chain, then Alice and Bob can wait until T_lock (while putting nothing else on-chain), at which point Bob can be assured that he owns S:0 (as any attempt by Alice to spend S:0 by meetiing the covenant using case A above can be thwarted by Bob putting S on-chain first using case B above). Second, if O puts a different C2 on-chain, or fails to put any C2 on-chain promptly, Alice can reclaim her funds by putting F2 on-chain, waiting one time window, and then putting S on-chain using case A above.

Thus, IIDs provide a trust-free means for Alice to transfer funds from F1 to a party that is unknown to Alice when she puts F1 on-chain. I see two problems in tryinig to use anyprevout to achieve the same result. First, I don't know of any mechanism by which Alice can create a covenant that F2 puts on S which implements case B above. In some other settings, I can understand how one could use unique single-use keys in place of IID outputs. However, in this setting I don't see how to define a covenant that F2 puts on S that in case B forces the other input to spend C2:0, as signatures that are evaluated in spending F2:0 don't commit to the output scripts of other inputs to S. Second, and more fundamentally, even if one could define a covenant that F2 puts on S in case B forcing the other input to be signed by a single-use key owned by O, that still wouldn't unconditionally transfer ownership to Bob (without putting F2 and S on-chain). That's because in order to have single-use keys play the role of IIDs, they have to truly be single-use and there is no way Bob can know that O won't just sign some other S' that competes with S and sends S':0 to O, thus stealing the funds. Please let me know if I've missed something here.

The example above isn't very useful, as it doesn't cut down on the number of on-chain transactions required to transfer ownership from Alice to Bob. However, it does capture the core functionality that IIDs provide that (I believe) anyprevout does not provide. This functionality is exactly what enables "update-forest" and "challenge-and-response" to allow a single on-chain transaction to transfer ownership of thousands or millions of channels in a trust-free manner, thus accomplishing with one on-chain transaction what would have required thousands or millions of anyprevout transactions (at least as far as I can tell). This is exactly the power of IIDs that I was referring to, and I found surprising that this power was actually the result of restricting how a signed transaction can be used (as compared to a signed transaction that uses anyprevout).

I hope clearing up these two misunderstandings is enough to pique your interest in reading the "timeout trees", "update-forest" and "challenge-and-response" protocols in more detail, as I'd be interested in your expert opinion on them.

My remaining comments are minor compared to the previous ones.
* Regarding the worst-case delay for eltoo-2party vs. 2Stage, I agree that there is no single agreed upon model for analyzing this and opinions may differ. In any case, I think that if one had a nearly-expired HTLC (or if one is setting the lock time for an HTLC) and one could choose between eltoo-2party, where the other party could have thousands or millions of transactions competing with your settlement transaction, and 2Stage, where the other party can have at most one competing transaction, some would prefer 2Stage.
* In comparing eltoo-2party and 2Stage, I was surprised that you didn't consider 2Stage's elimination of watchtowers for one or both parties as being an advantage. I had through that would be a big win in practice.
* Regarding footnote 13's description of OP_CODESEPARATOR, I realize that that footnote does not capture the change made in taproot. I addressed that issue on p. 54 (and explained it in footnote 43), as footnote 13 was designed to explain OP_CODESEPARATOR to those not already familiar with it, while p. 54 was designed for the experts.
* Regarding the new address type for floating transactions mentioned in the paper, thanks for the correction. I'll remove this from the next version.

In summary, the paper shows that:
1) IIDs can be used to eliminate watchtowers for one or both parties in a two-party channel (2Stage),
2) IIDs can be used to create factories that allow very large numbers of new users to obtain bitcoin in a watchtower-free and trust-free manner (timeout trees),
3) IIDs support trust-free factories with unbounded numbers of parties (and channels) that allow the channels to be bought and sold by anyone, including parties not originally in the factory, with a single on-chain transaction, and
4) IIDs achieve these results while using a more constrained, and thus safer, change to Bitcoin than the support for floating transactions.

Are these results of interest?

Thanks,
John

Sent with [ProtonMail](https://protonmail.com/) Secure Email.

[-- Attachment #2: Type: text/html, Size: 8611 bytes --]

^ permalink raw reply	[flat|nested] 5+ messages in thread

end of thread, other threads:[~2021-10-10 22:03 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-09-17 16:58 [bitcoin-dev] Inherited IDs - A safer, more powerful alternative to BIP-118 (ANYPREVOUT) for scaling Bitcoin Jeremy
2021-09-18 11:37 ` Anthony Towns
2021-09-21  2:11 ` [bitcoin-dev] [Lightning-dev] " ZmnSCPxj
2021-09-24  7:27   ` Jeremy
2021-10-10 22:03 [bitcoin-dev] " jlspc

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox