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

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

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

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

[ZmnSCPxj]

Good morning John Law,


> (at the expense of requiring an on-chain transaction to update
> the set of channels created by the factory).

Hmmm this kind of loses the point of a factory?
By my understanding, the point is that the set of channels can be changed *without* an onchain transaction.

Otherwise, it seems to me that factories with this "expense of requiring an on-chain transaction" can be created, today, without even Taproot:

* The funding transaction output pays to a simple n-of-n.
* The above n-of-n is spent by an *offchain* transaction that splits the funds to the current set of channels.
* To change the set of channels, the participants perform this ritual:
  * Create, but do not sign, an alternate transaction that spends the above n-of-n to a new n-of-n with the same participants (possibly with tweaked keys).
  * Create and sign, but do not broadcast, a transaction that spends the above alternate n-of-n output and splits it to the new set of channels.
  * Sign the alternate transaction and broadcast it, this is the on-chain transaction needed to update the set of channels.

The above works today without changes to Bitcoin, and even without Taproot (though for large N the witness size does become fairly large without Taproot).

The above is really just a "no updates" factory that cuts through its closing transaction with the opening of a new factory.

Regards,
ZmnSCPxj

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

[Jeremy]

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

John let me know that he's posted some responses in his Github repo
https://github.com/JohnLaw2/btc-iids

probably easiest to respond to him via e.g. a github issue or something.

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