Date: Fri, 18 Feb 2022 23:39:49 +0000
To: Antoine Riard <antoine.riard@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <0mhhHzTun8dpIcLda1CLFihMsgLoWQUEE8woKUKhf_UHYps2w7jVzbJAUJ302kQEB1ZdvMfakP9IBUHLM8bGns-pg0NHmpuak3yjpphjJnw=@protonmail.com>
In-Reply-To: <CALZpt+Ee9kuVjpXYgOb_7dB7Yr8HYmicdRhfgXsQkey2szNDHg@mail.gmail.com>
References: <6nZ-SkxvJLrOCOIdUtLOsdnl94DoX_NHY0uwZ7sw78t24FQ33QJlJU95W7Sk1ja5EFic5a3yql14MLmSAYFZvLGBS4lDUJfr8ut9hdB7GD4=@protonmail.com>
 <CALZpt+Ee9kuVjpXYgOb_7dB7Yr8HYmicdRhfgXsQkey2szNDHg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 Anthony Towns <aj@erisian.com.au>
Subject: Re: [bitcoin-dev] `OP_EVICT`: An Alternative to
	`OP_TAPLEAFUPDATEVERIFY`
Precedence: list

Good morning ariard,


> > A statechain is really just a CoinPool hosted inside a
> > =C2=A0Decker-Wattenhofer or Decker-Russell-Osuntokun construction.
>
> Note, to the best of my knowledge, how to use LN-Penalty in the context o=
f multi-party construction is still an unsolved issue. If an invalidated st=
ate is published on-chain, how do you guarantee that the punished output va=
lue is distributed "fairly" among the "honest" set of users ? At least
> where fairness is defined as a reasonable proportion of the balances they=
 owned in the latest state.

LN-Penalty I believe is what I call Poon-Dryja?

Both Decker-Wattenhofer (has no common colloquial name) and Decker-Russell-=
Osuntokun ("eltoo") are safe with N > 2.
The former has bad locktime tradeoffs in the unilateral close case, and the=
 latter requires `SIGHASH_NOINPUT`/`SIGHASH_ANYPREVOUT`.


> > In principle, a set of promised outputs, if the owners of those
> > outputs are peers, does not have *any* inherent order.
> > Thus, I started to think about a commitment scheme that does not
> > impose any ordering during commitment.
>
> I think we should dissociate a) *outputs publication ordering* from the b=
) *spends paths ordering* itself. Even if to each spend path a output publi=
cation is attached, the ordering constraint might not present the same comp=
lexity.
>
> Under this distinction, are you sure that TLUV imposes an ordering on the=
 output publication ?

Yes, because TLUV is based on tapleaf revelation.
Each participant gets its own unique tapleaf that lets that participant get=
 evicted.

In Taproot, the recommendation is to sort the hashes of each tapleaf before=
 arranging them into a MAST that the Taproot address then commits to.
This sort-by-hash *is* the arbitrary ordering I refer to when I say that TL=
UV imposes an arbitrary ordering.
(actually the only requirement is that pairs of scripts are sorted-by-hash,=
 but it is just easier to sort the whole array by hash.)

To reveal a single participant in a TLUV-based CoinPool, you need to reveal=
 O(log N) hashes.
It is the O(log N) space consumption I want to avoid with `OP_EVICT`, and I=
 believe the reason for that O(log N) revelation is due precisely to the ar=
bitrary but necessary ordering.

> > With `OP_TLUV`, however, it is possible to create an "N-of-N With
> > Eviction" construction.
> > When a participant in the N-of-N is offline, but the remaining
> > participants want to advance the state of the construction, they
> > instead evict the offline participant, creating a smaller N-of-N
> > where *all* participants are online, and continue operating.
>
> I think we should dissociate two types of pool spends : a) eviction by th=
e pool unanimity in case of irresponsive participants and b) unilateral wit=
hdrawal by a participant because of the liquidity allocation policy. I thin=
k the distinction is worthy, as the pool participant should be stable and t=
he eviction not abused.
>
> I'm not sure if TLUV enables b), at least without transforming the unilat=
eral withdrawal into an eviction. To ensure the TLUV operation is correct=
=C2=A0 (spent leaf is removed, withdrawing participant point removed, etc),=
 the script content must be inspected by *all* the participant. However, I =
believe
> knowledge of this content effectively allows you to play it out against t=
he pool at any time ? It's likely solvable at the price of a CHECKSIG.

Indeed, that distinction is important.
`OP_TLUV` (and `OP_EVICT`, which is just a redesigned `OP_TLUV`) supports (=
a) but not (b).

> `OP_EVICT`
> ----------
>
> > =C2=A0* If it is `1` that simply means "use the Taproot internal
> > =C2=A0 =C2=A0pubkey", as is usual for `OP_CHECKSIG`.
>
> IIUC, this assumes the deployment of BIP118, where if the=C2=A0 public ke=
y is a single byte 0x01, the internal pubkey is used
> for verification.

I thought it was part of Taproot?

>
> > =C2=A0* Output indices must not be duplicated, and indicated
> > =C2=A0 =C2=A0outputs must be SegWit v1 ("Taproot") outputs.
>
> I think public key duplication must not be verified. If a duplicated publ=
ic key is present, the point is subtracted twice from the internal pubkey a=
nd therefore the aggregated
> key remains unknown ? So it sounds to me safe against replay attacks.

Ah, right.

> > =C2=A0* The public key is the input point (i.e. stack top)
> > =C2=A0 =C2=A0**MINUS** all the public keys of the indicated outputs.
>
> Can you prevent eviction abuse where one counterparty threatens to evict =
everyone as all the output signatures are known among participants and free=
 to sum ? (at least not considering fees)

No, I considered onchain fees as the only mechanism to avoid eviction abuse=
.
The individual-evict signatures commit to fixed quantities.
The remaining change is then the only fund that can pay for onchain fees, s=
o a single party evicting everyone else has to pay for the eviction of ever=
yone else.


> > Suppose however that B is offline.
> > Then A, C, and D then decide to evict B.
> > To do so, they create a transaction that has an output
> > with "B :=3D 6", and they reveal the `OP_EVICT` Tapscript
> > as well as sign(b, "B :=3D 6").
> > This lets them change state and spend their funds without
> > B being online.
> > And B remains secure, as they cannot evict B except using
> > the pre-signed output, which B certifies as their expected
> > promised output.
>
> I think in the context of (off-chain) payment pool, OP_EVICT requires par=
ticipant cooperation *after* the state update to allow a single participant=
 to withdraw her funds.

How so?

A single participant withdrawing their funds unilaterally can do so by evic=
ting everyone else (and paying for those evictions, as sort of a "nuisance =
fee").
The signatures for each per-participant-eviction can be exchanged before th=
e signature exchange for the Decker-Wattenhofer or Decker-Russell-Osuntokun=
.


> > The combined fund cannot be spent except if all participants
> > agree.
>
> If all participants agree minus the evicted ones, correct ? The output pr=
omises signatures are shared at state setup, therefore no additional contri=
bution from the evicted participant (I think).

Yes.

>
> > To prevent signature replay, each update of an updateable
> > scheme like CoinPool et al should use a different pubkey
> > for each participant for each state.
>
> I'm not even sure if it's required with OP_EVICT, as the publication of t=
he promised output are ultimately restrained by a signature of the updated =
internal pubkey, this set of signers verify that promised output N does bin=
d to the published state N ?

If the internal pubkey is reused (for example, if all participants are onli=
ne and want to change state cooperatively) then the component keys need to =
be re-tweaked each time.

The tweaking can be done with non-hardened derivation.


> > Its advantage is reduced number of eviction transactions,
> > as multiple evictions, plus the revival of the CoinPool,
> > can be put in a single transaction.
> > It has the disadvantage relative to `OP_TLUV` of requiring
> > point operations.
> > I have not explored completely, but my instinct suggests
> > that `OP_TLUV` use may require at least one signature
> > validation anyway.
>
> I believe you can slightly modify TLUV to make it functional for CoinPool=
 revival, where you want to prevent equivocation among the remaining set of=
 signers. Though, I'm leaning to agree that you may require at least one si=
gnature validation=C2=A0 (first to restrain spend authorization inside the =
pool participants, second to attach fees at broadcast-time).

Yes, TLUV does have that advantage relative to CTV, and `OP_EVICT` is "just=
" a redesigned `OP_TLUV`.

In particular, I first developed my thoughts on revivable constructs with e=
viction of participants here: https://lists.linuxfoundation.org/pipermail/l=
ightning-dev/2022-February/003479.html


Regards,
ZmnSCPxj