Date: Wed, 13 Mar 2019 21:10:50 +1000
From: Anthony Towns <aj@erisian.com.au>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <20190313111050.qj3s6utpl2x34sam@erisian.com.au>
References: <20190313014143.ifffshwdux2jt7w5@erisian.com.au>
	<gs0Aizmvb8U11-Uz4RUqrEwgu00deU3JRhwHWbPjn8g1lZV3iaydqoYP3tldfrflHRC2HHJEZtAOVeYdaOW-chMcRdPVSiNYmqT6jSPnL1c=@protonmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <gs0Aizmvb8U11-Uz4RUqrEwgu00deU3JRhwHWbPjn8g1lZV3iaydqoYP3tldfrflHRC2HHJEZtAOVeYdaOW-chMcRdPVSiNYmqT6jSPnL1c=@protonmail.com>
User-Agent: NeoMutt/20170113 (1.7.2)
Cc: "bitcoin-dev@lists.linuxfoundation.org"
	<bitcoin-dev@lists.linuxfoundation.org>,
	"lightning-dev@lists.linuxfoundation.org"
	<lightning-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] [Lightning-dev] More thoughts on NOINPUT safety
Precedence: list

On Wed, Mar 13, 2019 at 06:41:47AM +0000, ZmnSCPxj via Lightning-dev wrote:
> > -   alternatively, we could require every script to have a valid signature
> >     that commits to the input. In that case, you could do eltoo with a
> >     script like either:
> >     <A> CHECKSIGVERIFY <B> CHECKSIG
> >     or <P> CHECKSIGVERIFY <Q> CHECKSIG
> > where A is Alice's key and B is Bob's key, P is muSig(A,B) and Q is
> > a key they both know the private key for. In the first case, Alice
> > would give Bob a NOINPUT sig for the tx, and when Bob wanted to publish
> > Bob would just do a SIGHASH_ALL sig with his own key. In the second,
> > Alice and Bob would share partial NOINPUT sigs of the tx with P, and
> > finish that when they wanted to publish.
> At my point of view, if a NONINPUT sig is restricted and cannot be
> used to spend an "ordinary" 2-of-2, this is output tagging regardless
> of exact mechanism.

With taproot, you could always do the 2-of-2 spend without revealing a
script at all, let alone that it was meant to be NOINPUT capable. The
setup I'm thinking of in this scenario is something like:

  0) my key is A, your key is B, we want to setup an eltoo channel

  1) post a funding tx to the blockchain, spending money to an address
     P = muSig(A,B)

  2) we cycle through a bunch of states from 0..N, with "0" being the
     refund state we establish before publishing the funding tx to
     the blockchain. each state essentially has two corresponding tx's,
     and update tx and a settlement tx.

  3) the update tx for state k spends to an output Qk which is a
     taproot address Qk = P + H(P,Sk)*G where Sk is the eltoo ratchet
     condition:
        Sk = (5e8+k+1) CLTV A CHECKDLS_NOINPUT B CHECKDLS_NOINPUT_VERIFY

     we establish two partial signatures for update state k, one which
     is a partial signature spending the funding tx with key P and
     SIGHASH_ALL, the other is a NOINPUT signature via A (for you) and
     via B (for me) with locktime set to (k+5e8), so that we can spend
     any earlier state's update tx's, but not itself or any later
     state's update tx's.

  4) for each state we have also have a settlement transaction,
     Sk, which spends update tx k, to outputs corresponding to the state
     of the channel, after a relative timelock delay.

     we have two partial signatures for this transaction too, one with
     SIGHASH_ALL assuming that we directly spent the funding tx with
     update state k (so the input txid is known), via the key path with
     key Qk; the other SIGHASH_NOINPUT via the Sk path. both partially
     signed tx's have nSequence set to the required relative timelock
     delay.

  5) if you're using scriptless scripts to do HTLCs, you'll need to
     allow for NOINPUT sigs when claiming funds as well (and update
     the partial signatures for the non-NOINPUT cases if you want to
     maximise privacy), which is a bit fiddly

  6) when closing the channel the process is then:

       - if you're in contact with the other party, negotiate a new
         key path spend of the funding tx, publish it, and you're done.

       - otherwise, if the funding tx hasn't been spent, post the latest
         update tx you know about, using the "spend the funding tx via
	 key path" partial signature

       - otherwise, trace the children of the funding tx, so you can see
         the most recent published state:
	   - if that's newer than the latest state you know about, your
	     info is out of date (restored from an old backup?), and you
	     have to wait for your counterparty to post the settlement tx
	   - if it's equal to the latest state you know about, wait
	   - if it's older than the latest state, post the latest update
	     tx (via the NOINPUT script path sig), and wait

       - once the CSV delay for the latest update tx has expired, post
	 the corresponding settlement tx (key path if the update tx
	 spent the funding tx, NOINPUT if the update tx spent an earlier
	 update tx)

       - once the settlement tx is posted, claim your funds

So the cases look like:

   mutual close:
     funding tx -> claimed funds

     -- only see one key via muSig, single signature, SIGHASH_ALL
     -- if there are active HTLCs when closing the channel, and they
        timeout, then the claiming tx will likely be one-in, one-out,
	SIGHASH_ALL, with a locktime, which may be unusual enough to
	indicate a lightning channel.

   unilateral close, no cheating: 
     funding tx -> update N -> settlement N -> claimed funds

     -- update N is probably SINGLE|ANYONECANPAY, so chain analysis
        of accompanying inputs might reveal who closed the channel
     -- settlement N has relative timelock
     -- claimed funds may have timelocks if they claim active HTLCs via
        the refund path
     -- no NOINPUT signatures needed, and all signatures use the key path
        so don't reveal any scripts

   unilateral close, attempted cheating:
     funding tx -> update K -> update N -> settlement N -> claimed funds

     -- update K, update N are probably SINGLE|ANYONECANPAY, so chain
        analysis might reveal the identity of both sides of the channel 
     -- update N and settlement N both use NOINPUT signatures and
        reveal CLTV script that looks like eltoo
     -- update N has timelock set
     -- settlement N has a relative timelock
     -- claimed funds may have timelocks if they claim active HTLCs via
        the refund path

     Notes:
      * cheating isn't 100% accurate: could be due to someone having to
        restore from an old backup

      * you could end up with:

          funding tx -> update K -> update W -> update N
	             -> settlement N -> claimed funds

	if someone restored from an old backup and posted K, a watchtower
	had a newer but not current state W, and finally you posted
	state N directly. with multiple watchtowers you might have more
	intermediate states' update tx's posted. afaics it has similar
	privacy results to the 2-update-tx case.

> So the restriction to add a non-NOINPUT sig in addition to a NOINPUT sig is still output tagging, as a cooperative close would still reveal that the output is not a 2-of-2.

With the above setup, you don't discover that NOINPUT was possible unless it
is actually needed because someone cheated.

As long as you're using muSig key path spending for a cooperative close,
you're not even revealing the output is 2-of-2, let alone a weird
2-of-2 variant.

> Ideally, historical data of whether onchain coin was used in Lightning or not should be revealed as little as possible.
> So in a cooperative close (which we hope, to be a common case), ideally the spend should look no different from an ordinary 2-of-2 spend.

With taproot, the goal is it shouldn't look different from an ordinary
"pay to public key" spend, and I think that's pretty achievable.

> Of course if the channel is published on Lightning, those who participated in Lightning at the time will learn of it, but at least the effort to remember this information is on those who want to remember this fact.

Well, presumaby lightning will continue to support private channels that
don't get published, and the concern's definitely valid for them!

> Now, this can be worked around by adding a "kickoff" transaction that spends the eltoo setup transaction.
> The eltoo setup transaction outputs to an ordinary 2-of-2.
> The kickoff outputs to an output that allows NOINPUT.
> Then the rest of the protocol anchors on top of the kickoff.
> [...]

I think this is possible too, but I think the scheme I describe above
is superior: iit means calculating a few more signatures each update,
but keeps more information off chain, which is better for privacy, and
probably cheaper (unless you have very high-frequency channel updates?).

Cheers,
aj