MIME-Version: 1.0
References: <6nZ-SkxvJLrOCOIdUtLOsdnl94DoX_NHY0uwZ7sw78t24FQ33QJlJU95W7Sk1ja5EFic5a3yql14MLmSAYFZvLGBS4lDUJfr8ut9hdB7GD4=@protonmail.com>
 <CALZpt+Ee9kuVjpXYgOb_7dB7Yr8HYmicdRhfgXsQkey2szNDHg@mail.gmail.com>
 <0mhhHzTun8dpIcLda1CLFihMsgLoWQUEE8woKUKhf_UHYps2w7jVzbJAUJ302kQEB1ZdvMfakP9IBUHLM8bGns-pg0NHmpuak3yjpphjJnw=@protonmail.com>
In-Reply-To: <0mhhHzTun8dpIcLda1CLFihMsgLoWQUEE8woKUKhf_UHYps2w7jVzbJAUJ302kQEB1ZdvMfakP9IBUHLM8bGns-pg0NHmpuak3yjpphjJnw=@protonmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Mon, 21 Feb 2022 19:17:52 -0500
Message-ID: <CALZpt+EUm06LxMmaQd0wxZ5cNtE_+jCQUWDmVrGTJx6ADQT4mA@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="00000000000058867605d890483e"
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

--00000000000058867605d890483e
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Zeeman,

> 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
arbitrary but necessary ordering.

AFAIU the TLUV proposal, it removes the constraint in the *outputs
publication ordering*, once they have all been generated. The tree update
mechanism ensure that whatever the order of dependency :
- the spend path can't be replayed because the user leaf is removed
- the key path can be re-used by remaining participant because the
withdrawing user point is removed

However, I agree that TLUV enforces a constraint in the *spends path
ordering* for the reason you raise.

I think `OP_EVICT` also removes the constraint in the *outputs publication
ordering*. AFAIU, opcode semantics you can mark as indicated any subset of
them. Further, it also solves the *spends paths ordering* as you don't need
to reveal O(log N) hashes anymore.

However, I don't think it's solving the *outputs publication ordering*
issues with the same non-cooperative property of TLUV. TLUV doesn't assume
cooperation among the construction participants once the Taproot tree is
setup. EVICT assumes cooperation among the remaining construction
participants to satisfy the final CHECKSIG.

So that would be a feature difference between TLUV and EVICT, I think ?

> I thought it was part of Taproot?

I checked BIP342 again, *as far as I can read* (unreliable process), it
sounds like it was proposed by BIP118 only.

> No, I considered onchain fees as the only mechanism to avoid eviction
abuse.

I'm unsure about the game-theory robustness of such abuse deterrent
mechanisms... As the pool off-chain payments are cheaper, you might break
your counterparty economic predictions by forcing them to go on-chain
before fee spikes and thus increasing their liquidity operational costs. Or
evicting them as a time where the fees are lower than they have paid to
get-in.

> A single participant withdrawing their funds unilaterally can do so by
evicting everyone else (and paying for those evictions, as sort of a
"nuisance fee").

I see, I'm more interested in the property of a single participant
withdrawing their funds, without affecting the stability of the off-chain
pool and without cooperation with other users. This is currently a
restriction of the channel factories fault-tolerance. If one channel goes
on-chain, all the outputs are published.

Antoine

Le ven. 18 f=C3=A9vr. 2022 =C3=A0 18:39, ZmnSCPxj <ZmnSCPxj@protonmail.com>=
 a =C3=A9crit :

> Good morning ariard,
>
>
> > > A statechain is really just a CoinPool hosted inside a
> > >  Decker-Wattenhofer or Decker-Russell-Osuntokun construction.
> >
> > Note, to the best of my knowledge, how to use LN-Penalty in the context
> of multi-party construction is still an unsolved issue. If an invalidated
> state is published on-chain, how do you guarantee that the punished outpu=
t
> value 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
> publication is attached, the ordering constraint might not present the sa=
me
> complexity.
> >
> > 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 t=
o.
> This sort-by-hash *is* the arbitrary ordering I refer to when I say that
> TLUV 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
> arbitrary 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
> the pool unanimity in case of irresponsive participants and b) unilateral
> withdrawal by a participant because of the liquidity allocation policy. I
> think the distinction is worthy, as the pool participant should be stable
> and the eviction not abused.
> >
> > I'm not sure if TLUV enables b), at least without transforming the
> unilateral withdrawal into an eviction. To ensure the TLUV operation is
> correct  (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
> the 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`
> > ----------
> >
> > >  * If it is `1` that simply means "use the Taproot internal
> > >    pubkey", as is usual for `OP_CHECKSIG`.
> >
> > IIUC, this assumes the deployment of BIP118, where if the  public key i=
s
> a single byte 0x01, the internal pubkey is used
> > for verification.
>
> I thought it was part of Taproot?
>
> >
> > >  * Output indices must not be duplicated, and indicated
> > >    outputs must be SegWit v1 ("Taproot") outputs.
> >
> > I think public key duplication must not be verified. If a duplicated
> public key is present, the point is subtracted twice from the internal
> pubkey and therefore the aggregated
> > key remains unknown ? So it sounds to me safe against replay attacks.
>
> Ah, right.
>
> > >  * The public key is the input point (i.e. stack top)
> > >    **MINUS** all the public keys of the indicated outputs.
> >
> > Can you prevent eviction abuse where one counterparty threatens to evic=
t
> everyone as all the output signatures are known among participants and fr=
ee
> 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,
> so a single party evicting everyone else has to pay for the eviction of
> everyone 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
> participant 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
> evicting everyone else (and paying for those evictions, as sort of a
> "nuisance fee").
> The signatures for each per-participant-eviction can be exchanged before
> the 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
> promises signatures are shared at state setup, therefore no additional
> contribution 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
> the promised output are ultimately restrained by a signature of the updat=
ed
> internal pubkey, this set of signers verify that promised output N does
> bind to the published state N ?
>
> If the internal pubkey is reused (for example, if all participants are
> online and want to change state cooperatively) then the component keys ne=
ed
> 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 requi=
re
> at least one signature validation  (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
> eviction of participants here:
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-February/0=
03479.html
>
>
> Regards,
> ZmnSCPxj
>

--00000000000058867605d890483e
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi Zeeman,<br><br>&gt; To reveal a single participant in a=
 TLUV-based CoinPool, you need to reveal O(log N) hashes.<br>&gt; 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 arbitrary b=
ut necessary ordering.<br><br>AFAIU the TLUV proposal, it removes the const=
raint in the *outputs publication ordering*, once they have all been genera=
ted. The tree update mechanism ensure that whatever the order of dependency=
 :<br>- the spend path can&#39;t be replayed because the user leaf is remov=
ed<br>- the key path can be re-used by remaining participant because the wi=
thdrawing user point is removed<br><br>However, I agree that TLUV enforces =
a constraint in the *spends path ordering* for the reason you raise.<br><br=
>I think `OP_EVICT` also removes the constraint in the *outputs publication=
 ordering*. AFAIU, opcode semantics you can mark as indicated any subset of=
 them. Further, it also solves the *spends paths ordering* as you don&#39;t=
 need to reveal O(log N) hashes anymore.<br><br>However, I don&#39;t think =
it&#39;s solving the *outputs publication ordering* issues with the same no=
n-cooperative property of TLUV. TLUV doesn&#39;t assume cooperation among t=
he construction participants once the Taproot tree is setup. EVICT assumes =
cooperation among the remaining construction participants to satisfy the fi=
nal CHECKSIG.<br><br>So that would be a feature difference between TLUV and=
 EVICT, I think ?<br><br>&gt; I thought it was part of Taproot?<br><br>I ch=
ecked BIP342 again, *as far as I can read* (unreliable process), it sounds =
like it was proposed by BIP118 only.<br><br>&gt; No, I considered onchain f=
ees as the only mechanism to avoid eviction abuse.<br><br>I&#39;m unsure ab=
out the game-theory robustness of such abuse deterrent mechanisms... As the=
 pool off-chain payments are cheaper, you might break your counterparty eco=
nomic predictions by forcing them to go on-chain before fee spikes and thus=
 increasing their liquidity operational costs. Or evicting them as a time w=
here the fees are lower than they have paid to get-in.<br><br>&gt; A single=
 participant withdrawing their funds unilaterally can do so by evicting eve=
ryone else (and paying for those evictions, as sort of a &quot;nuisance fee=
&quot;).<br><br>I see, I&#39;m more interested in the property of a single =
participant withdrawing their funds, without affecting the stability of the=
 off-chain pool and without cooperation with other users. This is currently=
 a restriction of the channel factories fault-tolerance. If one channel goe=
s on-chain, all the outputs are published.<br><br>Antoine<br></div><br><div=
 class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0ven. 1=
8 f=C3=A9vr. 2022 =C3=A0=C2=A018:39, ZmnSCPxj &lt;<a href=3D"mailto:ZmnSCPx=
j@protonmail.com">ZmnSCPxj@protonmail.com</a>&gt; a =C3=A9crit=C2=A0:<br></=
div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bor=
der-left:1px solid rgb(204,204,204);padding-left:1ex">Good morning ariard,<=
br>
<br>
<br>
&gt; &gt; A statechain is really just a CoinPool hosted inside a<br>
&gt; &gt; =C2=A0Decker-Wattenhofer or Decker-Russell-Osuntokun construction=
.<br>
&gt;<br>
&gt; Note, to the best of my knowledge, how to use LN-Penalty in the contex=
t of multi-party construction is still an unsolved issue. If an invalidated=
 state is published on-chain, how do you guarantee that the punished output=
 value is distributed &quot;fairly&quot; among the &quot;honest&quot; set o=
f users ? At least<br>
&gt; where fairness is defined as a reasonable proportion of the balances t=
hey owned in the latest state.<br>
<br>
LN-Penalty I believe is what I call Poon-Dryja?<br>
<br>
Both Decker-Wattenhofer (has no common colloquial name) and Decker-Russell-=
Osuntokun (&quot;eltoo&quot;) are safe with N &gt; 2.<br>
The former has bad locktime tradeoffs in the unilateral close case, and the=
 latter requires `SIGHASH_NOINPUT`/`SIGHASH_ANYPREVOUT`.<br>
<br>
<br>
&gt; &gt; In principle, a set of promised outputs, if the owners of those<b=
r>
&gt; &gt; outputs are peers, does not have *any* inherent order.<br>
&gt; &gt; Thus, I started to think about a commitment scheme that does not<=
br>
&gt; &gt; impose any ordering during commitment.<br>
&gt;<br>
&gt; I think we should dissociate a) *outputs publication ordering* from th=
e b) *spends paths ordering* itself. Even if to each spend path a output pu=
blication is attached, the ordering constraint might not present the same c=
omplexity.<br>
&gt;<br>
&gt; Under this distinction, are you sure that TLUV imposes an ordering on =
the output publication ?<br>
<br>
Yes, because TLUV is based on tapleaf revelation.<br>
Each participant gets its own unique tapleaf that lets that participant get=
 evicted.<br>
<br>
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.<br>
This sort-by-hash *is* the arbitrary ordering I refer to when I say that TL=
UV imposes an arbitrary ordering.<br>
(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.)<br>
<br>
To reveal a single participant in a TLUV-based CoinPool, you need to reveal=
 O(log N) hashes.<br>
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.<br>
<br>
&gt; &gt; With `OP_TLUV`, however, it is possible to create an &quot;N-of-N=
 With<br>
&gt; &gt; Eviction&quot; construction.<br>
&gt; &gt; When a participant in the N-of-N is offline, but the remaining<br=
>
&gt; &gt; participants want to advance the state of the construction, they<=
br>
&gt; &gt; instead evict the offline participant, creating a smaller N-of-N<=
br>
&gt; &gt; where *all* participants are online, and continue operating.<br>
&gt;<br>
&gt; I think we should dissociate two types of pool spends : a) eviction by=
 the pool unanimity in case of irresponsive participants and b) unilateral =
withdrawal by a participant because of the liquidity allocation policy. I t=
hink the distinction is worthy, as the pool participant should be stable an=
d the eviction not abused.<br>
&gt;<br>
&gt; I&#39;m not sure if TLUV enables b), at least without transforming the=
 unilateral withdrawal into an eviction. To ensure the TLUV operation is co=
rrect=C2=A0 (spent leaf is removed, withdrawing participant point removed, =
etc), the script content must be inspected by *all* the participant. Howeve=
r, I believe<br>
&gt; knowledge of this content effectively allows you to play it out agains=
t the pool at any time ? It&#39;s likely solvable at the price of a CHECKSI=
G.<br>
<br>
Indeed, that distinction is important.<br>
`OP_TLUV` (and `OP_EVICT`, which is just a redesigned `OP_TLUV`) supports (=
a) but not (b).<br>
<br>
&gt; `OP_EVICT`<br>
&gt; ----------<br>
&gt;<br>
&gt; &gt; =C2=A0* If it is `1` that simply means &quot;use the Taproot inte=
rnal<br>
&gt; &gt; =C2=A0 =C2=A0pubkey&quot;, as is usual for `OP_CHECKSIG`.<br>
&gt;<br>
&gt; IIUC, this assumes the deployment of BIP118, where if the=C2=A0 public=
 key is a single byte 0x01, the internal pubkey is used<br>
&gt; for verification.<br>
<br>
I thought it was part of Taproot?<br>
<br>
&gt;<br>
&gt; &gt; =C2=A0* Output indices must not be duplicated, and indicated<br>
&gt; &gt; =C2=A0 =C2=A0outputs must be SegWit v1 (&quot;Taproot&quot;) outp=
uts.<br>
&gt;<br>
&gt; I think public key duplication must not be verified. If a duplicated p=
ublic key is present, the point is subtracted twice from the internal pubke=
y and therefore the aggregated<br>
&gt; key remains unknown ? So it sounds to me safe against replay attacks.<=
br>
<br>
Ah, right.<br>
<br>
&gt; &gt; =C2=A0* The public key is the input point (i.e. stack top)<br>
&gt; &gt; =C2=A0 =C2=A0**MINUS** all the public keys of the indicated outpu=
ts.<br>
&gt;<br>
&gt; Can you prevent eviction abuse where one counterparty threatens to evi=
ct everyone as all the output signatures are known among participants and f=
ree to sum ? (at least not considering fees)<br>
<br>
No, I considered onchain fees as the only mechanism to avoid eviction abuse=
.<br>
The individual-evict signatures commit to fixed quantities.<br>
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.<br>
<br>
<br>
&gt; &gt; Suppose however that B is offline.<br>
&gt; &gt; Then A, C, and D then decide to evict B.<br>
&gt; &gt; To do so, they create a transaction that has an output<br>
&gt; &gt; with &quot;B :=3D 6&quot;, and they reveal the `OP_EVICT` Tapscri=
pt<br>
&gt; &gt; as well as sign(b, &quot;B :=3D 6&quot;).<br>
&gt; &gt; This lets them change state and spend their funds without<br>
&gt; &gt; B being online.<br>
&gt; &gt; And B remains secure, as they cannot evict B except using<br>
&gt; &gt; the pre-signed output, which B certifies as their expected<br>
&gt; &gt; promised output.<br>
&gt;<br>
&gt; I think in the context of (off-chain) payment pool, OP_EVICT requires =
participant cooperation *after* the state update to allow a single particip=
ant to withdraw her funds.<br>
<br>
How so?<br>
<br>
A single participant withdrawing their funds unilaterally can do so by evic=
ting everyone else (and paying for those evictions, as sort of a &quot;nuis=
ance fee&quot;).<br>
The signatures for each per-participant-eviction can be exchanged before th=
e signature exchange for the Decker-Wattenhofer or Decker-Russell-Osuntokun=
.<br>
<br>
<br>
&gt; &gt; The combined fund cannot be spent except if all participants<br>
&gt; &gt; agree.<br>
&gt;<br>
&gt; If all participants agree minus the evicted ones, correct ? The output=
 promises signatures are shared at state setup, therefore no additional con=
tribution from the evicted participant (I think).<br>
<br>
Yes.<br>
<br>
&gt;<br>
&gt; &gt; To prevent signature replay, each update of an updateable<br>
&gt; &gt; scheme like CoinPool et al should use a different pubkey<br>
&gt; &gt; for each participant for each state.<br>
&gt;<br>
&gt; I&#39;m not even sure if it&#39;s required with OP_EVICT, as the publi=
cation of the promised output are ultimately restrained by a signature of t=
he updated internal pubkey, this set of signers verify that promised output=
 N does bind to the published state N ?<br>
<br>
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.<br>
<br>
The tweaking can be done with non-hardened derivation.<br>
<br>
<br>
&gt; &gt; Its advantage is reduced number of eviction transactions,<br>
&gt; &gt; as multiple evictions, plus the revival of the CoinPool,<br>
&gt; &gt; can be put in a single transaction.<br>
&gt; &gt; It has the disadvantage relative to `OP_TLUV` of requiring<br>
&gt; &gt; point operations.<br>
&gt; &gt; I have not explored completely, but my instinct suggests<br>
&gt; &gt; that `OP_TLUV` use may require at least one signature<br>
&gt; &gt; validation anyway.<br>
&gt;<br>
&gt; I believe you can slightly modify TLUV to make it functional for CoinP=
ool revival, where you want to prevent equivocation among the remaining set=
 of signers. Though, I&#39;m leaning to agree that you may require at least=
 one signature validation=C2=A0 (first to restrain spend authorization insi=
de the pool participants, second to attach fees at broadcast-time).<br>
<br>
Yes, TLUV does have that advantage relative to CTV, and `OP_EVICT` is &quot=
;just&quot; a redesigned `OP_TLUV`.<br>
<br>
In particular, I first developed my thoughts on revivable constructs with e=
viction of participants here: <a href=3D"https://lists.linuxfoundation.org/=
pipermail/lightning-dev/2022-February/003479.html" rel=3D"noreferrer" targe=
t=3D"_blank">https://lists.linuxfoundation.org/pipermail/lightning-dev/2022=
-February/003479.html</a><br>
<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>

--00000000000058867605d890483e--