Date: Sun, 10 Feb 2019 14:46:30 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Johnson Lau <jl2012@xbt.hk>
Message-ID: <20190210044630.oiktdihkbyavglzp@erisian.com.au>
References: <9F8C0789-48E9-448A-A239-DB4AFB902A00@xbt.hk>
	<9bae18fa-3266-61ce-0b62-6ee429198260@gmail.com>
	<dceb1831-9bc7-eae7-fdf2-c907701c0efe@gmail.com>
	<E280BF09-ABE8-4AD8-BE29-A9D87AD09207@xbt.hk>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
In-Reply-To: <E280BF09-ABE8-4AD8-BE29-A9D87AD09207@xbt.hk>
User-Agent: NeoMutt/20170113 (1.7.2)
Cc: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Safer NOINPUT with output tagging
Precedence: list

On Sun, Feb 10, 2019 at 12:48:40AM +0800, Johnson Lau wrote:
> 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 way I look at this is:

 * you can have a "channel factory" of 3 or more members (A,B,C,...)
 * it's protected by an n-of-n multisig output
 * it contains some combination of:
    - spends directly to members
    - lightning channels between pairs of members
    - channel factories between subgroups of members
 * when initially setup, the factory just has direct spends to each
   member matching the amount they contributed to the factory
 * whether you create a lightning channel or a sub-factory is the same
   decision as whether you create a lightning channel or a factory
   on-chain, so there's no combinatorial explosion.

You can close any channel factory by publishing it (and any higher level
channel factories it was a subgroup of) to the blockchain (at which point
the lower level channel factories and lightning channels remain open),
or you can update a channel factory off-chain by having everyone agree
to a new state -- which is only possible if everyone is online, of course.

Updates to transactions in a lightning channel in a factory, or updates
to a subfactory, don't generally involve updating the containing factory
at all, I think.

I don't think there's much use to having sub-factories -- maybe if you
have a subgroup that's much more active and wants to change channel
balances between each other more frequently than the least active member
of the main factory is online?

As far as NOINPUT goes; this impacts channel factories because cheating
could be by any member of the group, so you can't easily penalise the
cheater. So an eltoo-esque setup where you publish a commitment to the
state that's spendable only by any later state, and is then redeemed
after a timelock seems workable. In that case closing a factory when
you can't get all group members to cooperatively close looks like:

   funding tx: n-of-n multisig

   state commitment: n-of-n multisig
      spends funding tx or earlier state commitment
      spendable by later state commitment or settlement

   settlement: n-of-n multisig
      relative timelock
      spends state commitment
      spends to members, channels or sub-factories

The settlement tx has to spend with a NOINPUT sig, because the state
commitment could have had to spend different things. If it's a
sub-factory, the funding tx will have been in a factory, so the state
commitment would also have had to be a NOINPUT spend. So tagging
NOINPUT-spendable outputs would mean:

 - tagging state commitment outputs (which will be spent shortly with
   NOINPUT by the settlement tx, so no real loss here)

 - tagging settlement tx outputs if they're lightning channels or
   sub-factories (which is something of a privacy loss, I think, since
   they could continue off-chain for an indefinite period before being
   spent)


I think Johnson's suggested elsewhere that if you spend an input with a
NOINPUT signature, you should make all the outputs be tagged NOINPUT (as
a "best practice rule", rather than consensus-enforced or standardness).
That would avoid the privacy loss here, I think, but might be confusing.

If you wanted to close your factory and send your funds to an external
third-party (a cold-wallet, custodial wallet, or just paying someone
for something), you'd presumably do that via a cooperative close of the
factory, which doesn't require the state/settlement pair or NOINPUT
spends, so the NOINPUT-in means NOINPUT-tagged-outputs doesn't cause
a problem for that use case.


FWIW, I think an interesting way to improve this model might be to *add*
centralisation and trust; so that instead of having the factory have
an n-of-n multisig, have it be protected by k-of-n plus a trusted third
party. If you have the trusted third party check that the only balances
that change in the factory are from the "k" signers, that allows (n-k)
members to be offline at any time, but the remaining members to rebalance
their channels happily. (Theoretically you could do this trustlessly
with covenants, but the spending proofs on chain would be much larger)

Of course, this allows k-signers plus the trusted party to steal funds.
It might be possible for the trusted party to store audit logs of the
partial signatures from each of the k-signers for each transaction to
provide accountability -- where the lack of such logs implies the
trusted third party was cheating.

Cheers,
aj

>=20
>=20
>=20
> > On 9 Feb 2019, at 6:01 PM, Alejandro Ranchal Pedrosa via bitcoin-dev <b=
itcoin-dev@lists.linuxfoundation.org> wrote:
> >=20
> > Hi all,
> >>=20
> >> Side note: I was not able to come up with an similar, eltoo-like proto=
col 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 of=
f-chain protocol can continue updating in the abscence of other parties, it=
 means that other parties' signatures must not be required when they are no=
t 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 s=
tate' to prevent a party to simultaneously 'fork' the state with two differ=
ent parties, and double-spend. A solution for this is a childchain for Bitc=
oin. An example of this is what is known as a 'Broken Factory' attack [1] (=
https://bitcoin.stackexchange.com/questions/77434/how-does-channel-factory-=
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 un=
til the unresponsive parties go back online. That might be true in particul=
ar scenarios, but generally speaking, the party might have gone unresponsiv=
e during a factory-level update (i.e. off-chain closing and opening of chan=
nels), while some parties might have given out their signature for the upda=
te without receiving a fully signed transaction. In this case they do not e=
ven know which channel they have open (the one of the old state that they h=
ave fully signed, or the one for the new state that they have given out the=
ir 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 s=
tate 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 c=
hannels of the factory, and might want to update, while they will not be wi=
lling 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 'Transactio=
n Fragments' have been suggested. They allow an eltoo-like protocol even wh=
en one cannot predict in advance who will become absent, or malicious (by p=
ublishing invalid states), cause the non-absent parties can unite their fra=
gments and create a valid spendable factory-level transaction that effectiv=
ely 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 als=
o 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 c=
hannels.
> >> If one party is unresponsive, the remaining participants want to remove
> >> the party from the channel without downtime. This is possible by creat=
ing
> >> 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 broadcas=
ting the
> >> update transaction as usual. As soon as that happens the remaining
> >> participants can start to update their new channel. Their update signa=
tures
> >> 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 an=
other
> >> output). Therefore, the funding output of the new channel must be NOIN=
PUT
> >> tagged. Assuming the remaining parties later settle cooperatively, thi=
s 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 proto=
col 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 co=
uld be done to stop payers to reuse an address. Unfortunately, key-pair reu=
se 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 l=
aughed at victims of Ethereum dumb contracts (DAO, Parity multisig, etc). T=
he existing bitcoin script language is so restrictive. It disallows many us=
eful smart contracts, but at the same time prevented many dumb contracts. A=
fter all, =E2=80=9Csmart=E2=80=9D and =E2=80=9Cdumb=E2=80=9D are non-techni=
cal 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 ti=
me 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 ris=
ks of misuse.
> >>>=20
> >>> The risk I am trying to mitigate is a payer mistakenly pay to a previ=
ous address with the exactly same amount, and the previous UTXO has been sp=
ent using NOINPUT. Accidental double payment is not uncommon. Even if the p=
ayee was honest and willing to refund, the money might have been spent with=
 a replayed NOINPUT signature. Once people lost a significant amount of mon=
ey 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 with=
out 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 taggi=
ng:
> >>>=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, a=
nd 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 th=
e update txs could spend the trigger utxo with NOINPUT. Similarly, all upda=
te txs should be tagged, so they could be spent by other update txs and set=
tlement 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 h=
ow other people manage their addresses, we should never do tagging when pay=
ing 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 anyw=
ay, nor bring extra block space overhead.
> >>>=20
> >>> A clear advantage of tagging with scriptPubKey is we could tag on a p=
er-output basis. However, scriptPubKey tagging is only possible with native=
-segwit, not P2SH. That means we have to disallow NOINPUT in P2SH-segwit (O=
therwise, *all* P2SH addresses would become =E2=80=9Crisky=E2=80=9D for pay=
ers) 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 tagg=
ed 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-seg=
wit, and all existing wallets are protected by default. However, it is some=
what a layer violation and you could only tag all or none output in the sam=
e tx. Also, as Bitcoin Core has just removed the tx version from the UTXO d=
atabase, adding it back could be a little bit annoying, but doable.
> >>>=20
> >>> There is an extension to the version tagging, which could make NOINPU=
T even safer. In addition to tagging requirement, NOINPUT will also sign th=
e version of the previous tx. If the wallet always uses a randomised tx ver=
sion, it makes accidental replay very unlikely. However, that will burn a f=
ew more bits in the tx version field.
> >>>=20
> >>> While this seems fully compatible with eltoo, is there any other prop=
osals 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
>=20
>=20