Content-Type: text/plain;
	charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 12.0 \(3445.100.39\))
From: Johnson Lau <jl2012@xbt.hk>
In-Reply-To: <dceb1831-9bc7-eae7-fdf2-c907701c0efe@gmail.com>
Date: Sun, 10 Feb 2019 00:48:40 +0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <E280BF09-ABE8-4AD8-BE29-A9D87AD09207@xbt.hk>
References: <9F8C0789-48E9-448A-A239-DB4AFB902A00@xbt.hk>
	<9bae18fa-3266-61ce-0b62-6ee429198260@gmail.com>
	<dceb1831-9bc7-eae7-fdf2-c907701c0efe@gmail.com>
To: Alejandro Ranchal Pedrosa <a.ranchalpedrosa@gmail.com>,
	bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Safer NOINPUT with output tagging
Precedence: list

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 =
<bitcoin-dev@lists.linuxfoundation.org> 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