Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 9C61CC000D; Sat, 18 Sep 2021 11:37:50 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 7F14D6064B; Sat, 18 Sep 2021 11:37:50 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -0.099 X-Spam-Level: X-Spam-Status: No, score=-0.099 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, KHOP_HELO_FCRDNS=0.398, SPF_HELO_NONE=0.001, SPF_NONE=0.001, UNPARSEABLE_RELAY=0.001] autolearn=no autolearn_force=no Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5RcVF3UTqbtS; Sat, 18 Sep 2021 11:37:49 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 Received: from azure.erisian.com.au (cerulean.erisian.com.au [139.162.42.226]) by smtp3.osuosl.org (Postfix) with ESMTPS id 9E4DE6061B; Sat, 18 Sep 2021 11:37:49 +0000 (UTC) Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au) by azure.erisian.com.au with esmtpsa (Exim 4.92 #3 (Debian)) id 1mRYfB-0005zD-2v; Sat, 18 Sep 2021 21:37:46 +1000 Received: by sapphire.erisian.com.au (sSMTP sendmail emulation); Sat, 18 Sep 2021 21:37:40 +1000 Date: Sat, 18 Sep 2021 21:37:40 +1000 From: Anthony Towns To: Jeremy , Bitcoin Protocol Discussion Message-ID: <20210918113740.GA27989@erisian.com.au> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.10.1 (2018-07-13) Cc: lightning-dev Subject: Re: [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: Sat, 18 Sep 2021 11:37:50 -0000 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