Re: [bitcoin-dev] Inherited IDs - A safer, more powerful alternative to BIP-118 (ANYPREVOUT) for scaling Bitcoin

Re: [bitcoin-dev] Inherited IDs - A safer, more powerful alternative to BIP-118 (ANYPREVOUT) for scaling Bitcoin

[jlspc]

[-- 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 --]

Re: [bitcoin-dev] Inherited IDs - A safer, more powerful alternative to BIP-118 (ANYPREVOUT) for scaling Bitcoin

[Anthony Towns]

On Fri, Sep 17, 2021 at 09:58:45AM -0700, Jeremy via bitcoin-dev wrote,
on behalf of John Law:

> 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]. [...]

Pretty sure I've skimmed this before but hadn't given it a proper look.
Saying "X is more powerful" and then saying it can't actually do the
same stuff as the thing it's "more powerful" than always strikes me as
a red flag. Anyhoo..

I think the basic summary is that you add to each utxo a new resettable
"structural" tx id called an "iid" and indetify input txs that way when
signing, so that if the details of the transaction changes but not the
structure, the signature remains valid.

In particular, if you've got a tx with inputs tx1:n1, tx2:n2, tx3:n3, etc;
and outputs out1, out2, out3, etc, then its structual id is hash(iid(tx1),
n1) if any of its outputs are "tagged" and it's not a coinbase tx, and
otherwise it's just its txid.  (The proposed tagging is to use a segwit
v2 output in the tx, though I don't think that's an essential detail)

So if you have a tx A with 3 outputs, then tx B spends "A:0, A:1" and
tx C spends "B:0" and tx D spends "C:0", if you replace B with B',
then if both B and B' were tagged, and the signatures for C (and D,
assuming C was tagged) will still be valid for spending from B'.

So the question is what you can do with that.

The "2stage" protocol is proposed as an alternative to eltoo is
essentially just:

 a) funding tx gets dropped to the chain
 b) closing state is proposed by one party
 c) other party can immediately finalise by confirming a final state
    that matches the proposed closing state, or was after it
 d) if the other party's not around for whatever delay, the party that
    proposed the close can finalise it

That doesn't work for more than two participants, because two of
the participants could collude to take the fast path in (c) with some
earlier state, robbing any other participants. That said, this is a fine
protocol for two participants, and might be better than doing the full
eltoo arrangement if you only have a two participant channel.

To make channel factories work in this model, I think the key step is
using invalidation trees to allow updating the split of funds between
groups of participants. I think invalidation trees introduce a tradeoff
between (a) how many updates you can make, and (b) how long you have to
notice a close is proposed and correct it, before an invalidated state
can be posted, and (c) how long it will take to be able to extract your
funds from the factory if there are problems initially. You reduce those
delays substantially (to a log() factor) by introducing a hierarchy of
update txs (giving you a log() number of txs), I think.

That's the "multisig factories" section anyway, if I'm
following correctly. The "timeout trees", "update-forest" and
"challenge-and-response" approaches both introduce a trusted user ("the
operator"), I think, so are perhaps more comparable to statechains
than eltoo?

So how does that compare, in my opinion?

If you consider special casing two-party channels with eltoo, then I
think eltoo-2party and 2stage are equally effective. Comparing
eltoo-nparty and the multisig iid factories approach, I think the
uncooperative case looks like:

 ms-iid:
   log(n) txs (for the invalidation tree)
   log(n) time (?) (for the delays to ensure invalidated states don't
                    get published)

 eltoo: 1 tx from you
        1 block after you notice, plus the fixed csv delay

A malicious counterparty can post many old update states prior to you
poisting the latest state, but those don't introduce extra csv delays
and you aren't paying the fees for those states, so I don't think it
makes sense to call that an O(n) delay or cost.

An additional practical problem with lightning is dealing with layered
commitments; that's a problem both for the delays while waiting for a
potential rejection in 2stage and for the invalidation tree delays in the
factory construction. But it's not a solved problem for eltoo yet, either.

As far as implementation goes, introducing the "iid" concept would mean
that info would need to be added to the utxo database -- if every utxo
got an iid, that would be perhaps a 1.4GB increase to the utxo db (going
by unique transaction rather than unique output), but presumably iid txs
would end up being both uncommon and short-lived, so the cost is probably
really mostly just in the additional complexity. Both iid and ANYPREVOUT
require changes to how signatures are evaluated and apps that use the
new feature are written, but ANYPREVOUT doesn't need changes beyond that.

(Also, the description of OP_CODESEPARATOR (footnote 13 on page 13,
ominous!) doesn't match its implementation in taproot. It also says BIP
118 introduces a new address type for floating transactions, but while
this was floated on the list, the current draft of 118 just introduces
a new tapscript key type for normal taproot addresses)

I think you can pretty easily simulate this construction with
anyprevout. Where you would have had A:1 spent by B, and B:2 and B:3
spent by C, change the derivation paths for the keys a1, b2, and b3
to append "/1", "/1/2" and "/1/3" and don't reuse them, and sign with
anyprevout when constructing B and C and any replacement transactions
for B and C.  So I don't think this allows any new constructions that
anyprevout wouldn't.

Cheers,
aj

[bitcoin-dev] Inherited IDs - A safer, more powerful alternative to BIP-118 (ANYPREVOUT) for scaling Bitcoin

[Jeremy]

[-- 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 --]