Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id B5B5ECDAC for ; Sat, 9 Feb 2019 16:49:16 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from sender-of-o51.zoho.com (sender-of-o51.zoho.com [135.84.80.216]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5FE3613A for ; Sat, 9 Feb 2019 16:49:15 +0000 (UTC) ARC-Seal: i=1; a=rsa-sha256; t=1549730948; cv=none; d=zoho.com; s=zohoarc; b=kpbPYYnNhafvE/Z2QX4NAkDYeeqzlkTaCgQNfvFBKCssmMPLyT/h+TAapYie0Ln8FGHbGUnGWLmMhXScSEbzcpygdXmpPq9DLOZIdjBADNG9fKLCa/8J9N8KGLzpuN9+Cc01Ubq5e9cDIzRxOYSobNLy67t7WQAFqGFK+LFBc/A= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zoho.com; s=zohoarc; t=1549730948; h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:MIME-Version:Message-ID:References:Subject:To:ARC-Authentication-Results; bh=DBTQFl5X6EeREOr/CJ6sZpMuYJJASJtN4nQiAlgXZOE=; b=Rcw5iqzmyxn3Zo1RxOx78Z+GAJa916B3Fn8pTo6z/BTltvfc1HZUy0pH//QQ1WV9EPqwBh06e/XZuXMdpHUmcE0FuEMeoG2ix48IAJQG7heEFh1AGuShmszlhCPcBSLonn4aLbgqkwDz3iHWrdffk92l0yukpChxnRxTDmiVg4o= ARC-Authentication-Results: i=1; mx.zoho.com; dkim=pass header.i=xbt.hk; spf=pass smtp.mailfrom=jl2012@xbt.hk; dmarc=pass header.from= header.from= Received: from [10.8.0.105] (pcd687179.netvigator.com [218.102.219.179]) by mx.zohomail.com with SMTPS id 1549730945987588.8970549640836; Sat, 9 Feb 2019 08:49:05 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 12.0 \(3445.100.39\)) From: Johnson Lau In-Reply-To: Date: Sun, 10 Feb 2019 00:48:40 +0800 Content-Transfer-Encoding: quoted-printable Message-Id: References: <9F8C0789-48E9-448A-A239-DB4AFB902A00@xbt.hk> <9bae18fa-3266-61ce-0b62-6ee429198260@gmail.com> To: Alejandro Ranchal Pedrosa , bitcoin-dev X-Mailer: Apple Mail (2.3445.100.39) X-ZohoMailClient: External X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,MIME_QP_LONG_LINE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Sat, 09 Feb 2019 18:49:52 +0000 Subject: Re: [bitcoin-dev] Safer NOINPUT with output tagging X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 09 Feb 2019 16:49:16 -0000 In a 3 parties channel, let=E2=80=99s say the balance for A, B, C is 2, = 3, 6BTC respectively, there are few ways they could make the settlement = tx. The first type we may call it =E2=80=9Csimple settlement=E2=80=9D, which = has 3 outputs with A=3D2, B=3D3, C=3D6. The second type we may call it =E2=80=9Cfully combinatorial = settlement=E2=80=9D, which has 3 outputs with (A & B), (B & C), and (A & = C). The value distribution is flexible, but never exceed the total = balance of the involved parties. For example, (A & B) may have any value = between 0 and 5BTC. For the following example, I will use (A & B) =3D 3; = (B & C) =3D 6; (A & C) =3D 2, but there are infinitely many valid = combinations. The third type we may call it =E2=80=9Cpartially combinatorial = settlement=E2=80=9D. It may have 2 multi-sig outputs, for example, (A & = B) =3D 4 and (B & C) =3D 7; or 1 multi-sig output and 1 single-sig = output, for example, (A & B) =3D 5 and C=3D6 (known as "semi-cooperative = channel closing=E2=80=9D SCCC in my last post) I=E2=80=99ll just focus on the fully combinatorial settlement. The = partial type works in the same way, with benefits and limitations. In a combinatorial settlement, the multi-sig outputs are actually = eltoo-style scripts. Therefore, A and B will further distribute the = value of (A & B) by a 2-party eltoo channel (=E2=80=9Cbranch channels"). = Again, there are infinitely many valid ways to distribute the values. If = the AB branch channel is distributed as A=3D1 and B=3D2, then the BC = channel must be B=3D1 and C=3D5, and the AC channel must be A=3D1 and = C=3D1. A clear benefit of this model is that any 2 parties could trade with = each other, in the absence of any other party(s), as long as there is = enough liquidity in their branch channel. There is also no way to = =E2=80=9Cfork=E2=80=9D the state, because liquidity is restricted to = each branch channel. In some way, this is like the existing lightning = network where the 3 parties have direct channel with each other. = However, this is superior to lightning network, because when the 3 = parties are online simultaneously, they could re-distribute the channel = capacities without closing any channels. They could even change it to a = partially combinatorial settlement. If they find that A and C rarely = trade with each other, they could remove the (A & C) output, and improve = the capacities of the remaining channels. If C is going offline for a = week, they could make it (A & B), C, (aka. SCCC) which will maximise the = capacity of the AB branch channel, and minimise the cost in case C is = not coming back. A problem with combinatorial settlement is the increased costs of = uncooperative settlement. It is more expensive, as more parties are = missing. Simple settlement has the same settlement cost for any number = of missing party. However, even if one party is missing, a simple = settled channel will cease to function and force an immediate on-chain = settlement. In combinatorial settlement, the surviving parties may keep = trading, may or may not with reduced capacity depending on the exact = settlement model, and in the meantime hope that the missing parties may = return. It requires 6 outputs for 4 parties doing fully combinatorial = settlement, 10 outputs for 5 parties, 15 outputs for 6 parties, etc. = However, in a many parties situation, not every parties might want to = trade with all the other parties, and those branch channels might be = omitted to improve the capacities of the other channels. If some pairs = want to trade without a direct branch channel, they might try to find a = third (internal) party to forward the tx. When the next time all parties = are online, they could rearrange the branch channel capacities at no = cost. The combinatorial settlement model could be generalised to a = hierarchical settlement model, where we might have 4 settlement outputs = (A&B&C), (A&B&D), (A&C&D), (B&C&D) for a 4-party channel, and each = settlement output will have 3 branch channels. If A is missing, for = example, we will still have one BC branch channel, one BD branch = channel, one CD branch channel, and one BCD 3-party branch channel. The = benefit of having a BCD 3-party branch channel is the 3 parties could = rearrange the channel capacities without involving A. Let=E2=80=99s say = D is going for vacation, he could do a SCCC in the BCD branch channel to = maximise the capacity of its BC channel. Without the involvement of A, = however, the capacities of the other BC, BD, and CD branch channels are = not modifiable, and B and C=E2=80=99s balance in the BD/CD channels are = frozen during the absence of D. As the number of parties increase, the number of settlement txs will = grow factorially in a fully hierarchical settlement model, and will soon = be out-of-control. The result could be catastrophic if many parties are = gone. So the group needs to continuously evaluate the risks of each = party being missing, and modify the settlement model accordingly. > On 9 Feb 2019, at 6:01 PM, Alejandro Ranchal Pedrosa via bitcoin-dev = wrote: >=20 > Hi all, >>=20 >> Side note: I was not able to come up with an similar, eltoo-like = protocol that works >> if you can't predict in advance who will become absent. >>=20 > An eltoo-like protocol that works (without going on-chain) if you = can't predict in advance who will become absent would be a childchain. = If the off-chain protocol can continue updating in the abscence of other = parties, it means that other parties' signatures must not be required = when they are not involved in the off-chain state update. If other = parties' signatures must not be required, there must be a way of having = a common verifiable 'last state' to prevent a party to simultaneously = 'fork' the state with two different parties, and double-spend. A = solution for this is a childchain for Bitcoin. An example of this is = what is known as a 'Broken Factory' attack [1] = (https://bitcoin.stackexchange.com/questions/77434/how-does-channel-factor= y-act/81005#81005) >=20 >> If the expectation is that the unresponsive party returns, = fungibility is >> not reduced due to output tagging because the above scheme can be = used >> off-chain until the original channel can be continued. >=20 > I believe that in many cases other parties won't be able to continue = until the unresponsive parties go back online. That might be true in = particular scenarios, but generally speaking, the party might have gone = unresponsive during a factory-level update (i.e. off-chain closing and = opening of channels), while some parties might have given out their = signature for the update without receiving a fully signed transaction. = In this case they do not even know which channel they have open (the one = of the old state that they have fully signed, or the one for the new = state that they have given out their signature for). This is known as a = 'Stale Factory', and can be exploited by an adversary in a 'Stale = Factory' attack [1]. Even if they knew which state they are in (i.e. the = party went unresponsive but not during a factory-level update), some of = them might have run out of funds in some of their channels of the = factory, and might want to update, while they will not be willing to = wait for a party to go back online (something for which they also have = zero guarantees of). >=20 > An eltoo-like protocol that works (allowing going on-chain) if you = can't in advance who will become absent, then this is precisely why = 'Transaction Fragments' have been suggested. They allow an eltoo-like = protocol even when one cannot predict in advance who will become absent, = or malicious (by publishing invalid states), cause the non-absent = parties can unite their fragments and create a valid spendable = factory-level transaction that effectively kicks out the malicious = parties, while leaving the rest of the factory as it was. To the best of = my understanding, the eltoo original proposal also allows this though. >=20 > Best, >=20 > Alejandro. >=20 > [1]: Scalable Lightning Factories for Bitcoin, = https://eprint.iacr.org/2018/918.pdf >=20 >=20 > On 08/02/2019 20:01, Jonas Nick via bitcoin-dev wrote: >> Output tagging may result in reduced fungibility in multiparty eltoo = channels. >> If one party is unresponsive, the remaining participants want to = remove >> the party from the channel without downtime. This is possible by = creating >> settlement transactions which pay off the unresponsive party and fund = a new >> channel with the remaining participants. >>=20 >> When the party becomes unresponsive, the channel is closed by = broadcasting the >> update transaction as usual. As soon as that happens the remaining >> participants can start to update their new channel. Their update = signatures >> must use SIGHASH_NOINPUT. This is because in eltoo the settlement = txid is not >> final (because update tx is not confirmed and may have to rebind to = another >> output). Therefore, the funding output of the new channel must be = NOINPUT >> tagged. Assuming the remaining parties later settle cooperatively, = this loss >> of fungibility would not have happened without output tagging. >>=20 >> funding output update output = settlement outputs update output >> [ A & B & C ] -> ... -> [ (A & B & C & state CLTV) | (As & Bs & Cs) ] = -> [ NOINPUT tagged: (A' & B'), -> ... >> = C' ] >> If the expectation is that the unresponsive party returns, = fungibility is >> not reduced due to output tagging because the above scheme can be = used >> off-chain until the original channel can be continued. >>=20 >> Side note: I was not able to come up with an similar, eltoo-like = protocol that works >> if you can't predict in advance who will become absent. >>=20 >> On 12/13/18 12:32 PM, Johnson Lau via bitcoin-dev wrote: >>> NOINPUT is very powerful, but the tradeoff is the risks of signature = replay. While the key holders are expected not to reuse key pair, little = could be done to stop payers to reuse an address. Unfortunately, = key-pair reuse has been a social and technical norm since the creation = of Bitcoin (the first tx made in block 170 reused the previous public = key). I don=E2=80=99t see any hope to change this norm any time soon, if = possible at all. >>>=20 >>> As the people who are designing the layer-1 protocol, we could = always blame the payer and/or payee for their stupidity, just like those = people laughed at victims of Ethereum dumb contracts (DAO, Parity = multisig, etc). The existing bitcoin script language is so restrictive. = It disallows many useful smart contracts, but at the same time prevented = many dumb contracts. After all, =E2=80=9Csmart=E2=80=9D and =E2=80=9Cdumb=E2= =80=9D are non-technical judgement. The DAO contract has always been = faithfully executed. It=E2=80=99s dumb only for those invested in the = project. For me, it was just a comedy show. >>>=20 >>> So NOINPUT brings us more smart contract capacity, and at the same = time we are one step closer to dumb contracts. The target is to find a = design that exactly enables the smart contracts we want, while = minimising the risks of misuse. >>>=20 >>> The risk I am trying to mitigate is a payer mistakenly pay to a = previous address with the exactly same amount, and the previous UTXO has = been spent using NOINPUT. Accidental double payment is not uncommon. = Even if the payee was honest and willing to refund, the money might have = been spent with a replayed NOINPUT signature. Once people lost a = significant amount of money this way, payers (mostly exchanges) may = refuse to send money to anything other than P2PKH, native-P2WPKH and = native-P2WSH (as the only 3 types without possibility of NOINPUT) >>>=20 >>> The proposed solution is that an output must be =E2=80=9Ctagged=E2=80=9D= for it to be spendable with NOINPUT, and the =E2=80=9Ctag=E2=80=9D must = be made explicitly by the payer. There are 2 possible ways to do the = tagging: >>>=20 >>> 1. A certain bit in the tx version must be set >>> 2. A certain bit in the scriptPubKey must be set >>>=20 >>> I will analyse the pros and cons later. >>>=20 >>> Using eltoo as example. The setup utxo is a simple 2-of-2 multisig, = and should not be tagged. This makes it indistinguishable from normal = 1-of-1 utxo. The trigger tx, which spends the setup utxo, should be = tagged, so the update txs could spend the trigger utxo with NOINPUT. = Similarly, all update txs should be tagged, so they could be spent by = other update txs and settlement tx with NOINPUT. As the final = destination, there is no need to tag in the settlement tx. >>>=20 >>> In payer=E2=80=99s perspective, tagging means =E2=80=9CI believe = this address is for one-time-use only=E2=80=9D Since we can=E2=80=99t = control how other people manage their addresses, we should never do = tagging when paying to other people. >>>=20 >>> I mentioned 2 ways of tagging, and they have pros and cons. First of = all, tagging in either way should not complicate the eltoo protocol in = anyway, nor bring extra block space overhead. >>>=20 >>> A clear advantage of tagging with scriptPubKey is we could tag on a = per-output basis. However, scriptPubKey tagging is only possible with = native-segwit, not P2SH. That means we have to disallow NOINPUT in = P2SH-segwit (Otherwise, *all* P2SH addresses would become =E2=80=9Crisky=E2= =80=9D for payers) This should be ok for eltoo, since it has no reason = to use P2SH-segwit in intermediate txs, which is more expensive. >>>=20 >>> Another problem with scriptPubKey tagging is all the existing bech32 = implementations will not understand the special tag, and will pay to a = tagged address as usual. An upgrade would be needed for them to refuse = sending to tagged addresses by default. >>>=20 >>> On the other hand, tagging with tx version will also protect = P2SH-segwit, and all existing wallets are protected by default. However, = it is somewhat a layer violation and you could only tag all or none = output in the same tx. Also, as Bitcoin Core has just removed the tx = version from the UTXO database, adding it back could be a little bit = annoying, but doable. >>>=20 >>> There is an extension to the version tagging, which could make = NOINPUT even safer. In addition to tagging requirement, NOINPUT will = also sign the version of the previous tx. If the wallet always uses a = randomised tx version, it makes accidental replay very unlikely. = However, that will burn a few more bits in the tx version field. >>>=20 >>> While this seems fully compatible with eltoo, is there any other = proposals require NOINPUT, and is adversely affected by either way of = tagging? >>> _______________________________________________ >>> bitcoin-dev mailing list >>> bitcoin-dev@lists.linuxfoundation.org >>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>>=20 >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev