* [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
@ 2022-02-18 2:45 ZmnSCPxj
2022-02-18 13:53 ` Erik Aronesty
` (2 more replies)
0 siblings, 3 replies; 16+ messages in thread
From: ZmnSCPxj @ 2022-02-18 2:45 UTC (permalink / raw)
To: Anthony Towns, bitcoin-dev
`OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
======================================================
In late 2021, `aj` proposed `OP_TAPLEAFUPDATEVERIFY` in order to
implement CoinPools and similar constructions.
`Jeremy` observed that due to the use of Merkle tree paths, an
`OP_TLUV` would require O(log N) hash revelations in order to
reach a particular tapleaf, which, in the case of a CoinPool,
would then delete itself after spending only a particular amount
of funds.
He then observed that `OP_CTV` trees also require a similar
revelation of O(log N) transactions, but with the advantage that
once revealed, the transactions can then be reused, thus overall
the expectation is that the number of total bytes onchain is
lesser compared to `OP_TLUV`.
After some thinking, I realized that it was the use of the
Merkle tree to represent the promised-but-offchain outputs of
the CoinPool that lead to the O(log N) space usage.
I then started thinking of alternative representations of
sets of promised outputs, which would not require O(log N)
revelations by avoiding the tree structure.
Promised Outputs
----------------
Fundamentally, we can consider that a solution for scaling
Bitcoin would be to *promise* that some output *can* appear
onchain at some point in the future, without requiring that the
output be shown onchain *right now*.
Then, we can perform transactional cut-through on spends of the
promised outputs, without requiring onchain activity ("offchain").
Only if something Really Bad (TM) happens do we need to actually
drop the latest set of promised outputs onchain, where it has to
be verified globally by all fullnodes (and would thus incur scaling
and privacy costs).
As an example of the above paradigm, consider the Lightning
Network.
Outputs representing the money of each party in a channel are
promised, and *can* appear onchain (via the unilateral close
mechanism).
In the meantime, there is a mechanism for performing cut-through,
allowing transfers between channel participants; any number of
transactions can be performed that are only "solidified" later,
without expensive onchain activity.
Thus:
* A CoinPool is really a way to commit to promised outputs.
To change the distribution of those promised outputs, the
CoinPool operators need to post an onchain transaction, but
that is only a 1-input-1-output transaction, and with Schnorr
signatures the single input requires only a single signature.
But in case something Really Bad (TM) happens, any participant
can unilaterally close the CoinPool, instantiating the promised
outputs.
* A statechain is really just a CoinPool hosted inside a
Decker-Wattenhofer or Decker-Russell-Osuntokun construction.
This allows changing the distribution of those promised outputs
without using an onchain transaction --- instead, a new state
in the Decker-Wattenhofer/Decker-Russell-Osuntokun construction
is created containing the new state, which invalidates all older
states.
Again, any participant can unilaterally shut it down, exposing
the state of the inner CoinPool.
* A channel factory is really just a statechain where the
promised outputs are not simple 1-of-1 single-owner outputs,
but are rather 2-of-2 channels.
This allows graceful degradation, where even if the statechain
("factory") layer has missing participants, individual 2-of-2
channels can still continue operating as long as they do not
involve missing participants, without requiring all participants
to be online for large numbers of transactions.
We can then consider that the base CoinPool usage should be enough,
as other mechanisms (`OP_CTV`+`OP_CSFS`, `SIGHASH_NOINPUT`) can be
used to implement statechains and channels and channel factories.
I therefore conclude that what we really need is "just" a way to
commit ourselves to exposing a set of promised outputs, with the
proviso that if we all agree, we can change that set (without
requiring that the current or next set be exposed, for both
scaling and privacy).
(To Bitcoin Cashers: this is not an IOU, this is *committed* and
can be enforced onchain, that is enough to threaten your offchain
counterparties into behaving correctly.
They cannot gain anything by denying the outputs they promised,
you can always drop it onchain and have it enforced, thus it is
not just merely an IOU, as IOUs are not necessarily enforceable,
but this mechanism *would* be.
Blockchain as judge+jury+executioner, not noisy marketplace.)
Importantly: both `OP_CTV` and `OP_TLUV` force the user to
decide on a particular, but ultimately arbitrary, ordering for
promised outputs.
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.
Digression: N-of-N With Eviction
--------------------------------
An issue with using an N-of-N construction is that if any single
participant is offline, the construction cannot advance its state.
This has lead to some peopple proposing to instead use K-of-N
once N reaches much larger than 2 participants for CoinPools/statechains/
channel factories.
However, even so, K-of-N still requires that K participants remain
online, and the level K is a security parameter.
If less than K participants are online, then the construction
*still* cannot advance its state.
Worse, because K < N, a single participant can have its funds
outright stolen by a quorum of K participants.
There is no way to prove that the other participants in the same
construction are not really sockpuppets of the same real-world
entity, thus it is entirely possible that the K quorum is actually
just a single participant that is now capable of stealing the
funds of all the other participants.
The only way to avoid this is to use N-oF-N: N-of-N requires
*your* keys, thus the coins are *your* coins.
In short: K-of-N, as it allows the state to be updated without your
keys (on the excuse that "if you are offline, we need to be able to
update state"), is *not your keys not your coins*.
K-of-N should really only be used if all N are your sockpuppets,
and you want to HODL your funds.
This is the difference between consensus "everyone must agree" and
voting "enough sockpuppets can be used to overpower you".
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.
This avoids the *not your keys not your coins* problem of K-of-N
constructions, while simultaneously providing a way to advance
the state without the full participant set being online.
The only real problem with `OP_TLUV` is that it takes O(log N)
hash revelations to evict one participant, and each evicted
participant requires one separate transaction.
K-of-N has the "advantage" that even if you are offline, the state
can be advanced without evicting you.
However, as noted, as the coins can be spent without your keys,
the coins are not your coins, thus this advantage may be considered
dubious --- whether you are online or offline, a quorum of K can
outright steal your coins.
Eviction here requires that your coins be returned to your control.
Committing To An Unordered Set
------------------------------
In an N-of-N CoinPool/statechain/channel factory, the ownership
of a single onchain UTXO is shared among N participants.
That is, there are a number of promised outputs, not exposed
onchain, which the N participants agree on as the "real" current
state of the construction,
However, the N participants can also agree to change the current
state of the construction, if all of them sign off on the change.
Each of the promised outputs has a value, and the sum of all
promised values is the value of the onchain UTXO.
Interestingly, each of the promised outputs also has an SECP256K1
point that can be used as a public key, and the sum of all
promised points is the point of the onchain UTXO.
Thus, the onchain UTXO can serve as a commitment to the sum of
the promised outputs.
The problem is committing to each of the individual promised
outputs.
We can observe that a digital signature not only proves knowledge
of a private key, it also commits to a particular message.
Thus, we can make each participant sign their own expected
promised output, and share the signature for their promised
output.
When a participant is to be evicted, the other participants
take the signature for the promised output of the to-be-evicted
participant, and show it onchain, to attest to the output.
Then, the onchain mechanism should then allow the rest of the
funds to be controlled by the N-of-N set minus the evicted
participant.
`OP_EVICT`
----------
With all that, let me now propose the `OP_EVICT` opcode.
`OP_EVICT` accepts a variable number of arguments.
* The stack top is either the constant `1`, or an SECP256K1
point.
* If it is `1` that simply means "use the Taproot internal
pubkey", as is usual for `OP_CHECKSIG`.
* The next stack item is a number, equal to the number of
outputs that were promised, and which will now be evicted.
* The next stack items will alternate:
* A number indicating an output index.
* A signature for that output.
* Output indices must not be duplicated, and indicated
outputs must be SegWit v1 ("Taproot") outputs.
The public key of the output will be taken as the public
key for the corresponding signature, and the signature
only covers the output itself (i.e. value and
`scriptPubKey`).
This means the signature has no `SIGHASH`.
* As the signature covers the public key, this prevents
malleation of a signature using one public key to a
signature for another public key.
* After that is another signature.
* This signature is checked using `OP_CHECKSIG` semantics
(including `SIGHASH` support).
* The public key is the input point (i.e. stack top)
**MINUS** all the public keys of the indicated outputs.
As a concrete example, suppose A, B, C, and D want to make a
CoinPool (or offchain variant of such) with the following
initial state:
* A := 10
* B := 6
* C := 4
* D := 22
Let us assume that A, B, C, and D have generated public
keys in such a way to avoid key cancellation (e.g.
precommitment, or the MuSig scheme).
The participants then generate promised outputs for the
above, and each of them shares signatures for the promised
outputs:
* sign(a, "A := 10")
* sign(b, "B := 6")
* sign(c, "C := 4")
* sign(d, "D := 22")
Once that is done, they generate:
* Q = A + B + C + D
* P = h(Q|`<1> OP_EVICT`) * Q
Then they spend their funds, creating a Taproot output:
* P := 42
If all participants are online, they can move funds between
each other (or to other addresses) by cooperatively signing
using the point P, and the magic of Taproot means that use
of `OP_EVICT` is not visible.
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 := 6", and they reveal the `OP_EVICT` Tapscript
as well as sign(b, "B := 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.
Note that the opcode as described above allows for multiple
evictions in the same transaction.
If B and C are offline, then the remaining participants
simply need to expose multiple outputs in the same
transaction.
Security
--------
I am not a cryptographer.
Thus, the security of this scheme is a conjecture.
As long as key cancellation is protected against, it should
be secure.
The combined fund cannot be spent except if all participants
agree.
A smaller online participant set can be created only if a
participant is evicted, and eviction will force the owned
funds of the evicted participant to be instantiated.
The other participants cannot synthesize an alternate
signature signing a different value without knowledge of the
privkey of the evicted participant.
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.
As the signature covers the pubkey, it should be safe to
use a non-hardened derivation scheme so that only a single
root privkey is needed.
Additional Discussion
---------------------
### Eviction Scheme
We can consider that the eviction scheme proposed here is the
following contract:
* Either all of us agree on some transfer, OR,
* Give me my funds and the rest of you can all go play with
your funds however you want.
The signature that commits to a promised output is then the
agreement that the particular participant believes they are
entitled to a particular amount.
We can consider that a participant can re-sign their output
with a different amount, but that is why `OP_EVICT` requires
the *other* participants to cooperatively sign as well.
If the other participants cooperatively sign, they effectively
agree to the participant re-signing for a different amount,
and thus actually covered by "all of us agree".
### Pure SCRIPT Contracts
A "pure SCRIPT contract" is a Taproot contract where the
keyspend path is not desired, and the contract is composed of
Tapscript branches.
In such a case, the expected technique would be for the
contract participants to agree on a NUMS point where none
of the participants can know the scalar (private key) behind
the point, and to use that as the internal Taproot pubkey
`Q`.
For complete protocols, the NUMS point can be a protocol-defined
constant.
As the `OP_EVICT` opcode requires that each promised output
be signed, on the face of it, this technique cannot be used
for `OP_EVICT`-promised outputs, as it is impossible to sign
using the NUMS point.
However, we should note that the requirement of a "pure SCRIPT"
contract is that none of the participants can unilaterally
sign an alternate spend.
Using an N-of-N of the participants as the Taproot internal
pubkey is sufficient to ensure this.
As a concrete example: suppose we want an HTLC, which has a
hashlock branch requiring participant A, and a timelock branch
requiring participant B.
Such a simple scheme would not require that both A and B be
able to cooperatively spend the output, thus we might have
preferred the technique of using a NUMS point as Taproot
internal pubkey.
But using a NUMS point would not allow any signature, even the
`OP_EVICT`-required signatures-of-promised-outputs.
Instead of using a NUMS point for the Taproot internal pubkey,
we can use the sum of `A[tmp] + B[tmp]` (suitably protected
against key cancellation).
Then both A and B can cooperatively sign the promised output,
and keep the promised output in an `OP_EVICT`-enforced UTXO.
After creating the signature for the promised output, A and B
can ensure that the keypath branch cannot be used by securely
deleting the private keys for `A[tmp]` and `B[tmp]`
respectively.
### Signature Half-Aggregation
It is possible to batch-validate, and as `OP_EVICT` must
validate at least two signatures (an eviction and the
signature of the remaining) it makes sense to use batch
validation for `OP_EVICT`.
Of note is that Schnorr signatures allow for third-party
half-aggregation, where the `s` components of multiple
signatures are summed together, but the `R` components
are not.
(Warning: I am not aware of any security proofs that
half-aggregation is actually **safe**!
In particular, BIP-340 does not define half-aggregation,
and its batch validation algorithm is not, to my naivete,
extensible to half-aggregation.)
Basically, if we are batch validating two signatures
`(R[0], s[0])`, `(R[1], s[1])` of two messages `m[0]`
and `m[1]` signed by two keys `A[0]` and `A[1]`, we
would do:
* For `i = 0, 1`: `e[i] = h(R[i]|m[i])`
* Check: `(s[0] + s[1]) * G` is equal to `R[0] + e[0] * A[0] + R[1] + e[1] * A[1]`.
As we can see, the `s` can be summed before being
posted on the blockchain, as validators do not need
individual `s[i]`.
However, `R` cannot be summed as each one needs to be
hashed.
This half-aggregation is third-party, i.e. someone
without any knowledge of any private keys can simply
sum the `s` components of multiple signatures.
As `OP_EVICT` always validates at least two signatures,
using half-aggregation can remove at least 32 weight
units, and each additional promised output being evicted
is another signature whose `s` can be added to the sum.
Of course, **that depends on half-aggregation being
secure**.
### Relationship to Other Opcodes
`OP_CTV` does other things than this opcode, and cannot
be used as a direct alternative.
In particular while `OP_CTV` *can* commit to a set of
promised outputs, if a promised output needs to be
published, the remaining funds are now distributed over a
set of UTXOs.
Thus, "reviving" the CoinPool (or offchain variant thereof)
requires consuming multiple UTXOs, and the consumption of
multiple UTXOs is risky unless specifically designd for it.
(In particular, if the UTXOs have different signer sets,
one signer set can initially cooperate to revive the
CoinPool, then spend their UTXO to a different transaction,
which if confirmed will invalidate the revival transaction.)
This opcode seems largely in direct competitiong with
`OP_TLUV`, with largely the same design goal.
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.
It may be possible to implement `OP_EVICT` in terms of
`OP_TX`/`OP_TXHASH`, `OP_CSFS`, and a point-subtraction
operation.
However, `OP_EVICT` allows for the trivial implementation
of batch validation (and, if half-aggregation is safe, to
use half-aggregation instead), whereas we expect multiple
`OP_CSFS` to be needed to implement this, without any
possibility of batch validation.
It may be possible to design an `OP_CSFS` variant that
allows batch validation, such as by extending the virtual
machine with an accumulator for pending signature
validations.
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-18 2:45 [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY` ZmnSCPxj
@ 2022-02-18 13:53 ` Erik Aronesty
2022-02-18 14:48 ` ZmnSCPxj
2022-02-18 13:55 ` Jonas Nick
2022-02-18 18:09 ` Antoine Riard
2 siblings, 1 reply; 16+ messages in thread
From: Erik Aronesty @ 2022-02-18 13:53 UTC (permalink / raw)
To: ZmnSCPxj, Bitcoin Protocol Discussion; +Cc: Anthony Towns
[-- Attachment #1: Type: text/plain, Size: 20246 bytes --]
hey, i read that whole thing, but i'm confused as to why it's necessary
seems like N of N participants can pre-sign an on-chain transfer of funds
for each participant to a new address that consists of (N-1) or (N-1)
participants, of which each portion of the signature is encrypted for the
same (N-1) participants
then any (N-1) subset of participants can collude publish that transaction
at any time to remove any other member from the pool
all of the set up (dkg for N-1), and transfer (encryption of partial sigs)
is done offchain, and online with the participants that are online
On Thu, Feb 17, 2022 at 9:45 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
> ======================================================
>
> In late 2021, `aj` proposed `OP_TAPLEAFUPDATEVERIFY` in order to
> implement CoinPools and similar constructions.
>
> `Jeremy` observed that due to the use of Merkle tree paths, an
> `OP_TLUV` would require O(log N) hash revelations in order to
> reach a particular tapleaf, which, in the case of a CoinPool,
> would then delete itself after spending only a particular amount
> of funds.
> He then observed that `OP_CTV` trees also require a similar
> revelation of O(log N) transactions, but with the advantage that
> once revealed, the transactions can then be reused, thus overall
> the expectation is that the number of total bytes onchain is
> lesser compared to `OP_TLUV`.
>
> After some thinking, I realized that it was the use of the
> Merkle tree to represent the promised-but-offchain outputs of
> the CoinPool that lead to the O(log N) space usage.
> I then started thinking of alternative representations of
> sets of promised outputs, which would not require O(log N)
> revelations by avoiding the tree structure.
>
> Promised Outputs
> ----------------
>
> Fundamentally, we can consider that a solution for scaling
> Bitcoin would be to *promise* that some output *can* appear
> onchain at some point in the future, without requiring that the
> output be shown onchain *right now*.
> Then, we can perform transactional cut-through on spends of the
> promised outputs, without requiring onchain activity ("offchain").
> Only if something Really Bad (TM) happens do we need to actually
> drop the latest set of promised outputs onchain, where it has to
> be verified globally by all fullnodes (and would thus incur scaling
> and privacy costs).
>
> As an example of the above paradigm, consider the Lightning
> Network.
> Outputs representing the money of each party in a channel are
> promised, and *can* appear onchain (via the unilateral close
> mechanism).
> In the meantime, there is a mechanism for performing cut-through,
> allowing transfers between channel participants; any number of
> transactions can be performed that are only "solidified" later,
> without expensive onchain activity.
>
> Thus:
>
> * A CoinPool is really a way to commit to promised outputs.
> To change the distribution of those promised outputs, the
> CoinPool operators need to post an onchain transaction, but
> that is only a 1-input-1-output transaction, and with Schnorr
> signatures the single input requires only a single signature.
> But in case something Really Bad (TM) happens, any participant
> can unilaterally close the CoinPool, instantiating the promised
> outputs.
> * A statechain is really just a CoinPool hosted inside a
> Decker-Wattenhofer or Decker-Russell-Osuntokun construction.
> This allows changing the distribution of those promised outputs
> without using an onchain transaction --- instead, a new state
> in the Decker-Wattenhofer/Decker-Russell-Osuntokun construction
> is created containing the new state, which invalidates all older
> states.
> Again, any participant can unilaterally shut it down, exposing
> the state of the inner CoinPool.
> * A channel factory is really just a statechain where the
> promised outputs are not simple 1-of-1 single-owner outputs,
> but are rather 2-of-2 channels.
> This allows graceful degradation, where even if the statechain
> ("factory") layer has missing participants, individual 2-of-2
> channels can still continue operating as long as they do not
> involve missing participants, without requiring all participants
> to be online for large numbers of transactions.
>
> We can then consider that the base CoinPool usage should be enough,
> as other mechanisms (`OP_CTV`+`OP_CSFS`, `SIGHASH_NOINPUT`) can be
> used to implement statechains and channels and channel factories.
>
> I therefore conclude that what we really need is "just" a way to
> commit ourselves to exposing a set of promised outputs, with the
> proviso that if we all agree, we can change that set (without
> requiring that the current or next set be exposed, for both
> scaling and privacy).
>
> (To Bitcoin Cashers: this is not an IOU, this is *committed* and
> can be enforced onchain, that is enough to threaten your offchain
> counterparties into behaving correctly.
> They cannot gain anything by denying the outputs they promised,
> you can always drop it onchain and have it enforced, thus it is
> not just merely an IOU, as IOUs are not necessarily enforceable,
> but this mechanism *would* be.
> Blockchain as judge+jury+executioner, not noisy marketplace.)
>
> Importantly: both `OP_CTV` and `OP_TLUV` force the user to
> decide on a particular, but ultimately arbitrary, ordering for
> promised outputs.
> 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.
>
> Digression: N-of-N With Eviction
> --------------------------------
>
> An issue with using an N-of-N construction is that if any single
> participant is offline, the construction cannot advance its state.
>
> This has lead to some peopple proposing to instead use K-of-N
> once N reaches much larger than 2 participants for CoinPools/statechains/
> channel factories.
>
> However, even so, K-of-N still requires that K participants remain
> online, and the level K is a security parameter.
> If less than K participants are online, then the construction
> *still* cannot advance its state.
>
> Worse, because K < N, a single participant can have its funds
> outright stolen by a quorum of K participants.
> There is no way to prove that the other participants in the same
> construction are not really sockpuppets of the same real-world
> entity, thus it is entirely possible that the K quorum is actually
> just a single participant that is now capable of stealing the
> funds of all the other participants.
> The only way to avoid this is to use N-oF-N: N-of-N requires
> *your* keys, thus the coins are *your* coins.
> In short: K-of-N, as it allows the state to be updated without your
> keys (on the excuse that "if you are offline, we need to be able to
> update state"), is *not your keys not your coins*.
>
> K-of-N should really only be used if all N are your sockpuppets,
> and you want to HODL your funds.
> This is the difference between consensus "everyone must agree" and
> voting "enough sockpuppets can be used to overpower you".
>
> 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.
>
> This avoids the *not your keys not your coins* problem of K-of-N
> constructions, while simultaneously providing a way to advance
> the state without the full participant set being online.
>
> The only real problem with `OP_TLUV` is that it takes O(log N)
> hash revelations to evict one participant, and each evicted
> participant requires one separate transaction.
>
> K-of-N has the "advantage" that even if you are offline, the state
> can be advanced without evicting you.
> However, as noted, as the coins can be spent without your keys,
> the coins are not your coins, thus this advantage may be considered
> dubious --- whether you are online or offline, a quorum of K can
> outright steal your coins.
> Eviction here requires that your coins be returned to your control.
>
> Committing To An Unordered Set
> ------------------------------
>
> In an N-of-N CoinPool/statechain/channel factory, the ownership
> of a single onchain UTXO is shared among N participants.
> That is, there are a number of promised outputs, not exposed
> onchain, which the N participants agree on as the "real" current
> state of the construction,
> However, the N participants can also agree to change the current
> state of the construction, if all of them sign off on the change.
>
> Each of the promised outputs has a value, and the sum of all
> promised values is the value of the onchain UTXO.
> Interestingly, each of the promised outputs also has an SECP256K1
> point that can be used as a public key, and the sum of all
> promised points is the point of the onchain UTXO.
>
> Thus, the onchain UTXO can serve as a commitment to the sum of
> the promised outputs.
> The problem is committing to each of the individual promised
> outputs.
>
> We can observe that a digital signature not only proves knowledge
> of a private key, it also commits to a particular message.
> Thus, we can make each participant sign their own expected
> promised output, and share the signature for their promised
> output.
>
> When a participant is to be evicted, the other participants
> take the signature for the promised output of the to-be-evicted
> participant, and show it onchain, to attest to the output.
> Then, the onchain mechanism should then allow the rest of the
> funds to be controlled by the N-of-N set minus the evicted
> participant.
>
> `OP_EVICT`
> ----------
>
> With all that, let me now propose the `OP_EVICT` opcode.
>
> `OP_EVICT` accepts a variable number of arguments.
>
> * The stack top is either the constant `1`, or an SECP256K1
> point.
> * If it is `1` that simply means "use the Taproot internal
> pubkey", as is usual for `OP_CHECKSIG`.
> * The next stack item is a number, equal to the number of
> outputs that were promised, and which will now be evicted.
> * The next stack items will alternate:
> * A number indicating an output index.
> * A signature for that output.
> * Output indices must not be duplicated, and indicated
> outputs must be SegWit v1 ("Taproot") outputs.
> The public key of the output will be taken as the public
> key for the corresponding signature, and the signature
> only covers the output itself (i.e. value and
> `scriptPubKey`).
> This means the signature has no `SIGHASH`.
> * As the signature covers the public key, this prevents
> malleation of a signature using one public key to a
> signature for another public key.
> * After that is another signature.
> * This signature is checked using `OP_CHECKSIG` semantics
> (including `SIGHASH` support).
> * The public key is the input point (i.e. stack top)
> **MINUS** all the public keys of the indicated outputs.
>
> As a concrete example, suppose A, B, C, and D want to make a
> CoinPool (or offchain variant of such) with the following
> initial state:
>
> * A := 10
> * B := 6
> * C := 4
> * D := 22
>
> Let us assume that A, B, C, and D have generated public
> keys in such a way to avoid key cancellation (e.g.
> precommitment, or the MuSig scheme).
>
> The participants then generate promised outputs for the
> above, and each of them shares signatures for the promised
> outputs:
>
> * sign(a, "A := 10")
> * sign(b, "B := 6")
> * sign(c, "C := 4")
> * sign(d, "D := 22")
>
> Once that is done, they generate:
>
> * Q = A + B + C + D
> * P = h(Q|`<1> OP_EVICT`) * Q
>
> Then they spend their funds, creating a Taproot output:
>
> * P := 42
>
> If all participants are online, they can move funds between
> each other (or to other addresses) by cooperatively signing
> using the point P, and the magic of Taproot means that use
> of `OP_EVICT` is not visible.
>
> 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 := 6", and they reveal the `OP_EVICT` Tapscript
> as well as sign(b, "B := 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.
>
> Note that the opcode as described above allows for multiple
> evictions in the same transaction.
> If B and C are offline, then the remaining participants
> simply need to expose multiple outputs in the same
> transaction.
>
> Security
> --------
>
> I am not a cryptographer.
> Thus, the security of this scheme is a conjecture.
>
> As long as key cancellation is protected against, it should
> be secure.
> The combined fund cannot be spent except if all participants
> agree.
> A smaller online participant set can be created only if a
> participant is evicted, and eviction will force the owned
> funds of the evicted participant to be instantiated.
> The other participants cannot synthesize an alternate
> signature signing a different value without knowledge of the
> privkey of the evicted participant.
>
> 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.
> As the signature covers the pubkey, it should be safe to
> use a non-hardened derivation scheme so that only a single
> root privkey is needed.
>
> Additional Discussion
> ---------------------
>
> ### Eviction Scheme
>
> We can consider that the eviction scheme proposed here is the
> following contract:
>
> * Either all of us agree on some transfer, OR,
> * Give me my funds and the rest of you can all go play with
> your funds however you want.
>
> The signature that commits to a promised output is then the
> agreement that the particular participant believes they are
> entitled to a particular amount.
>
> We can consider that a participant can re-sign their output
> with a different amount, but that is why `OP_EVICT` requires
> the *other* participants to cooperatively sign as well.
> If the other participants cooperatively sign, they effectively
> agree to the participant re-signing for a different amount,
> and thus actually covered by "all of us agree".
>
> ### Pure SCRIPT Contracts
>
> A "pure SCRIPT contract" is a Taproot contract where the
> keyspend path is not desired, and the contract is composed of
> Tapscript branches.
>
> In such a case, the expected technique would be for the
> contract participants to agree on a NUMS point where none
> of the participants can know the scalar (private key) behind
> the point, and to use that as the internal Taproot pubkey
> `Q`.
> For complete protocols, the NUMS point can be a protocol-defined
> constant.
>
> As the `OP_EVICT` opcode requires that each promised output
> be signed, on the face of it, this technique cannot be used
> for `OP_EVICT`-promised outputs, as it is impossible to sign
> using the NUMS point.
>
> However, we should note that the requirement of a "pure SCRIPT"
> contract is that none of the participants can unilaterally
> sign an alternate spend.
> Using an N-of-N of the participants as the Taproot internal
> pubkey is sufficient to ensure this.
>
> As a concrete example: suppose we want an HTLC, which has a
> hashlock branch requiring participant A, and a timelock branch
> requiring participant B.
> Such a simple scheme would not require that both A and B be
> able to cooperatively spend the output, thus we might have
> preferred the technique of using a NUMS point as Taproot
> internal pubkey.
> But using a NUMS point would not allow any signature, even the
> `OP_EVICT`-required signatures-of-promised-outputs.
>
> Instead of using a NUMS point for the Taproot internal pubkey,
> we can use the sum of `A[tmp] + B[tmp]` (suitably protected
> against key cancellation).
> Then both A and B can cooperatively sign the promised output,
> and keep the promised output in an `OP_EVICT`-enforced UTXO.
> After creating the signature for the promised output, A and B
> can ensure that the keypath branch cannot be used by securely
> deleting the private keys for `A[tmp]` and `B[tmp]`
> respectively.
>
> ### Signature Half-Aggregation
>
> It is possible to batch-validate, and as `OP_EVICT` must
> validate at least two signatures (an eviction and the
> signature of the remaining) it makes sense to use batch
> validation for `OP_EVICT`.
>
> Of note is that Schnorr signatures allow for third-party
> half-aggregation, where the `s` components of multiple
> signatures are summed together, but the `R` components
> are not.
>
> (Warning: I am not aware of any security proofs that
> half-aggregation is actually **safe**!
> In particular, BIP-340 does not define half-aggregation,
> and its batch validation algorithm is not, to my naivete,
> extensible to half-aggregation.)
>
> Basically, if we are batch validating two signatures
> `(R[0], s[0])`, `(R[1], s[1])` of two messages `m[0]`
> and `m[1]` signed by two keys `A[0]` and `A[1]`, we
> would do:
>
> * For `i = 0, 1`: `e[i] = h(R[i]|m[i])`
> * Check: `(s[0] + s[1]) * G` is equal to `R[0] + e[0] * A[0] + R[1] + e[1]
> * A[1]`.
>
> As we can see, the `s` can be summed before being
> posted on the blockchain, as validators do not need
> individual `s[i]`.
> However, `R` cannot be summed as each one needs to be
> hashed.
>
> This half-aggregation is third-party, i.e. someone
> without any knowledge of any private keys can simply
> sum the `s` components of multiple signatures.
>
> As `OP_EVICT` always validates at least two signatures,
> using half-aggregation can remove at least 32 weight
> units, and each additional promised output being evicted
> is another signature whose `s` can be added to the sum.
> Of course, **that depends on half-aggregation being
> secure**.
>
> ### Relationship to Other Opcodes
>
> `OP_CTV` does other things than this opcode, and cannot
> be used as a direct alternative.
> In particular while `OP_CTV` *can* commit to a set of
> promised outputs, if a promised output needs to be
> published, the remaining funds are now distributed over a
> set of UTXOs.
> Thus, "reviving" the CoinPool (or offchain variant thereof)
> requires consuming multiple UTXOs, and the consumption of
> multiple UTXOs is risky unless specifically designd for it.
> (In particular, if the UTXOs have different signer sets,
> one signer set can initially cooperate to revive the
> CoinPool, then spend their UTXO to a different transaction,
> which if confirmed will invalidate the revival transaction.)
>
> This opcode seems largely in direct competitiong with
> `OP_TLUV`, with largely the same design goal.
> 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.
>
> It may be possible to implement `OP_EVICT` in terms of
> `OP_TX`/`OP_TXHASH`, `OP_CSFS`, and a point-subtraction
> operation.
> However, `OP_EVICT` allows for the trivial implementation
> of batch validation (and, if half-aggregation is safe, to
> use half-aggregation instead), whereas we expect multiple
> `OP_CSFS` to be needed to implement this, without any
> possibility of batch validation.
> It may be possible to design an `OP_CSFS` variant that
> allows batch validation, such as by extending the virtual
> machine with an accumulator for pending signature
> validations.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
[-- Attachment #2: Type: text/html, Size: 22555 bytes --]
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-18 2:45 [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY` ZmnSCPxj
2022-02-18 13:53 ` Erik Aronesty
@ 2022-02-18 13:55 ` Jonas Nick
2022-02-18 18:09 ` Antoine Riard
2 siblings, 0 replies; 16+ messages in thread
From: Jonas Nick @ 2022-02-18 13:55 UTC (permalink / raw)
To: ZmnSCPxj, Bitcoin Protocol Discussion
On the topic of half aggregation, Chalkias et al. gave a convincing security
proof last year:
https://eprint.iacr.org/2021/350
As an aside, half aggregation is not exactly the scheme in the OP because that
one is insecure. This does not affect Zmn's conclusion and was already
pointed out in the original half aggregation thread:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014306.html
It is required that each of the "s"-values are multiplied with a different
unpredictable value, for example like this:
https://github.com/ElementsProject/cross-input-aggregation/blob/master/slides/2021-Q2-halfagg-impl.org#schnorr-signature-half-aggregation-1
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-18 13:53 ` Erik Aronesty
@ 2022-02-18 14:48 ` ZmnSCPxj
2022-02-18 15:50 ` Erik Aronesty
0 siblings, 1 reply; 16+ messages in thread
From: ZmnSCPxj @ 2022-02-18 14:48 UTC (permalink / raw)
To: Erik Aronesty; +Cc: Bitcoin Protocol Discussion, Anthony Towns
Good morning Erik,
> hey, i read that whole thing, but i'm confused as to why it's necessary
>
> seems like N of N participants can pre-sign an on-chain transfer of funds for each participant to a new address that consists of (N-1) or (N-1) participants, of which each portion of the signature is encrypted for the same (N-1) participants
>
> then any (N-1) subset of participants can collude publish that transaction at any time to remove any other member from the pool
>
> all of the set up (dkg for N-1), and transfer (encryption of partial sigs) is done offchain, and online with the participants that are online
As I understand your counterproposal, it would require publishing one transaction per evicted participant.
In addition, each participant has to store `N!` possible orderings in which participants can be evicted, as you cannot predict the future and cannot predict which partiicpants will go offline first.
Finally, please see also the other thread on lightning-dev: https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-February/003479.html
In this thread, I point out that if we ever use channel factories, it would be best if we treat each channel as a 2-of-2 that participates in an overall N-of-N (i.e. the N in the outer channel factory is composed of 2-of-2).
For example, instead of the channel factory being signed by participants `A`, `B`, `C`, `D`, instead the channel factory is signed by `AB`, `AC`, `AD`, `BC`, `BD`, `CD`, so that if e.g. participant B needs to be evicted, we can evict the signers `AB`, `BC`, and `BD`.
This means that for the channel factory case, already the number of "participants" is quadratic on the number of *actual* participants, which greatly increases the number of transactions that need to be evicted in one-eviction-at-a-time schemes (which is how I understand your proposal) as well as increasing the `N!` number of signatures that need to be exchanged during setup.
But yes, certainly that can work, just as pre-signed transactions can be used instead of `OP_CTV` or pretty much any non-`OP_CHECKMULTISIG` opcode, xref Smart Contracts Unchained.
Regards,
ZmnSCPxj
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-18 14:48 ` ZmnSCPxj
@ 2022-02-18 15:50 ` Erik Aronesty
2022-02-18 16:06 ` ZmnSCPxj
0 siblings, 1 reply; 16+ messages in thread
From: Erik Aronesty @ 2022-02-18 15:50 UTC (permalink / raw)
To: ZmnSCPxj; +Cc: Bitcoin Protocol Discussion, Anthony Towns
[-- Attachment #1: Type: text/plain, Size: 3065 bytes --]
> As I understand your counterproposal, it would require publishing one
transaction per evicted participant.
if you also pre-sign (N-2, N-3, etc), you can avoid this
> In addition, each participant has to store `N!` possible orderings in
which participants can be evicted, as you cannot predict the future and
cannot predict which partiicpants will go offline first.
why would the ordering matter? these are unordered pre commitments to move
funds, right? you agree post the one that represents "everyone that's
offline"
> But yes, certainly that can work, just as pre-signed transactions can be
used instead of `OP_CTV`
i don't see how multiple users can securely share a channel (allowing
massive additional scaling with lighting) without op_ctv
On Fri, Feb 18, 2022 at 9:48 AM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote:
> Good morning Erik,
>
> > hey, i read that whole thing, but i'm confused as to why it's necessary
> >
> > seems like N of N participants can pre-sign an on-chain transfer of
> funds for each participant to a new address that consists of (N-1) or (N-1)
> participants, of which each portion of the signature is encrypted for the
> same (N-1) participants
> >
> > then any (N-1) subset of participants can collude publish that
> transaction at any time to remove any other member from the pool
> >
> > all of the set up (dkg for N-1), and transfer (encryption of partial
> sigs) is done offchain, and online with the participants that are online
>
>
> As I understand your counterproposal, it would require publishing one
> transaction per evicted participant.
> In addition, each participant has to store `N!` possible orderings in
> which participants can be evicted, as you cannot predict the future and
> cannot predict which partiicpants will go offline first.
>
> Finally, please see also the other thread on lightning-dev:
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-February/003479.html
> In this thread, I point out that if we ever use channel factories, it
> would be best if we treat each channel as a 2-of-2 that participates in an
> overall N-of-N (i.e. the N in the outer channel factory is composed of
> 2-of-2).
> For example, instead of the channel factory being signed by participants
> `A`, `B`, `C`, `D`, instead the channel factory is signed by `AB`, `AC`,
> `AD`, `BC`, `BD`, `CD`, so that if e.g. participant B needs to be evicted,
> we can evict the signers `AB`, `BC`, and `BD`.
> This means that for the channel factory case, already the number of
> "participants" is quadratic on the number of *actual* participants, which
> greatly increases the number of transactions that need to be evicted in
> one-eviction-at-a-time schemes (which is how I understand your proposal) as
> well as increasing the `N!` number of signatures that need to be exchanged
> during setup.
>
>
> But yes, certainly that can work, just as pre-signed transactions can be
> used instead of `OP_CTV` or pretty much any non-`OP_CHECKMULTISIG` opcode,
> xref Smart Contracts Unchained.
>
> Regards,
> ZmnSCPxj
>
[-- Attachment #2: Type: text/html, Size: 3671 bytes --]
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-18 15:50 ` Erik Aronesty
@ 2022-02-18 16:06 ` ZmnSCPxj
0 siblings, 0 replies; 16+ messages in thread
From: ZmnSCPxj @ 2022-02-18 16:06 UTC (permalink / raw)
To: Erik Aronesty; +Cc: Bitcoin Protocol Discussion, Anthony Towns
Good morning Erik,
> > As I understand your counterproposal, it would require publishing one transaction per evicted participant.
>
> if you also pre-sign (N-2, N-3, etc), you can avoid this
It also increases the combinatorial explosion.
> > In addition, each participant has to store `N!` possible orderings in which participants can be evicted, as you cannot predict the future and cannot predict which partiicpants will go offline first.
>
> why would the ordering matter? these are unordered pre commitments to move funds, right? you agree post the one that represents "everyone that's offline"
Suppose `B` is offline first, then the remaining `A` `C` and `D` publish the eviction transaction that evicts only `B`.
What happens if `C` then goes offline?
We need to prepare for that case (and other cases where the participants go offline at arbitrary orders) and pre-sign a spend from the `ACD` set and evicts `C` as well, increasing combinatorial explosion.
And so on.
We *could* use multiple Tapleaves, of the form `<A> OP_CHECKSIG <BCD> OP_CHECKSIG` for each participant.
Then the per-participant `<A>` signature is signed with `SIGHASH_SINGLE|SIGHASH_ANYONECANPAY` and is pre-signed, while the remainder is signed by `<BCD>` with default `SIGHASH_ALL`.
Then if one participant `B` is offline they can evict `B` and then the change is put into a new UTXO with a similar pre-signed scheme `<A> OP_CHECKSIG <CD> OP_CHECKSIG`.
This technique precludes pre-signing multiple evictions.
>
> > But yes, certainly that can work, just as pre-signed transactions can be used instead of `OP_CTV`
>
> i don't see how multiple users can securely share a channel (allowing massive additional scaling with lighting) without op_ctv
They can, they just pre-sign, like you pointed out.
The same technique works --- `OP_CTV` just avoids having ridiculous amounts of combinatorial explosion and just requires `O(log n)` per eviction.
Remember, this proposal can be used for channel factories just as well, as pointed out, so any objection to this proposal also applies to `OP_CTV`.
Regards,
ZmnSCPxj
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-18 2:45 [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY` ZmnSCPxj
2022-02-18 13:53 ` Erik Aronesty
2022-02-18 13:55 ` Jonas Nick
@ 2022-02-18 18:09 ` Antoine Riard
2022-02-18 23:39 ` ZmnSCPxj
2 siblings, 1 reply; 16+ messages in thread
From: Antoine Riard @ 2022-02-18 18:09 UTC (permalink / raw)
To: ZmnSCPxj, Bitcoin Protocol Discussion; +Cc: Anthony Towns
[-- Attachment #1: Type: text/plain, Size: 28812 bytes --]
Hi Zeeman,
> After some thinking, I realized that it was the use of the
> Merkle tree to represent the promised-but-offchain outputs of
> the CoinPool that lead to the O(log N) space usage.
> I then started thinking of alternative representations of
> sets of promised outputs, which would not require O(log N)
> revelations by avoiding the tree structure.
In the context of payment pools, I think the O(log N) revelations can be
avoided already today by pre-signing all the combinations of
promised-but-offchain outputs publications order. However, this approach
presents a factorial complexity and appears as an intractable problem for
high-number of pool users.
I think this factorial complexity issue is the primary problem to enable
scalable payment pools. This issue appears to be solvable by introducing an
accumulator at the script interpreter level. IMO, the efficiency of the
accumulated set representations comes as a second-order issue.
In the comparison of different covenant primitives, I believe we should ask
first if the flexibility offered is enough to solve the factorial
complexity. I would say performance trade-offs analysis can only be
conducted in logically equivalent primitives.
> 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 output
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.
> (To Bitcoin Cashers: this is not an IOU, this is *committed* and
> can be enforced onchain, that is enough to threaten your offchain
> counterparties into behaving correctly.
> They cannot gain anything by denying the outputs they promised,
> you can always drop it onchain and have it enforced, thus it is
> not just merely an IOU, as IOUs are not necessarily enforceable,
> but this mechanism *would* be.
> Blockchain as judge+jury+executioner, not noisy marketplace.)
To be fair towards the Bitcoin Cashers, I think there are still limitations
of LN, we have not solved yet. Especially, w.r.t to mass exits from the
off-chain layers to the chain, where the blocks would stay fulfilled longer
than the standard HTLC timelocks, at a fee price point that the average
user can't buy... I'm not sure if we have outlawed the "bank runs" scenario
yet of LN.
I would say yes the Blockchain is a juge authority, but in the worst-case
we might be all in market competition to get enforcement.
> 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 same
complexity.
Under this distinction, are you sure that TLUV imposes an ordering on the
output publication ?
> 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.
`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 is a
single byte 0x01, the internal pubkey is used
for verification.
> * 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.
> * 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 evict
everyone as all the output signatures are known among participants and free
to sum ? (at least not considering fees)
> 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 := 6", and they reveal the `OP_EVICT` Tapscript
> as well as sign(b, "B := 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.
I believe this is unsafe if we retain as an off-chain construction security
requirement that a participant should have the unilateral means to enforce
the latest agreed upon state at any time during the construction lifetime.
I would say an OP_EVICT construction could solve the issue where the pool
participants exchange pre-signatures of the internal pubkey with the
withdrawing participant point removed. However, I believe such fix would a)
block promised outputs batching (or at least in a pre-committed way like
radix pools) and b) be grieved by the factorial complexity described above.
> 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).
> 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 updated
internal pubkey, this set of signers verify that promised output N does
bind to the published state N ?
> 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
signature validation (first to restrain spend authorization inside the
pool participants, second to attach fees at broadcast-time).
> It may be possible to design an `OP_CSFS` variant that
> allows batch validation, such as by extending the virtual
> machine with an accumulator for pending signature
> validations.
I agree that in the context of payment pools, aggregation of
non-cooperative unilateral spends is a scalability bottleneck, especially
in the face of mempools congestion. If we rely on merkle
trees as the accumulator primitive, there is still the path to aggregate
many branches in-flight.
Any misunderstandings of this proposal are my own.
,
Antoine
Le jeu. 17 févr. 2022 à 21:45, ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> a écrit :
> `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
> ======================================================
>
> In late 2021, `aj` proposed `OP_TAPLEAFUPDATEVERIFY` in order to
> implement CoinPools and similar constructions.
>
> `Jeremy` observed that due to the use of Merkle tree paths, an
> `OP_TLUV` would require O(log N) hash revelations in order to
> reach a particular tapleaf, which, in the case of a CoinPool,
> would then delete itself after spending only a particular amount
> of funds.
> He then observed that `OP_CTV` trees also require a similar
> revelation of O(log N) transactions, but with the advantage that
> once revealed, the transactions can then be reused, thus overall
> the expectation is that the number of total bytes onchain is
> lesser compared to `OP_TLUV`.
>
> After some thinking, I realized that it was the use of the
> Merkle tree to represent the promised-but-offchain outputs of
> the CoinPool that lead to the O(log N) space usage.
> I then started thinking of alternative representations of
> sets of promised outputs, which would not require O(log N)
> revelations by avoiding the tree structure.
>
> Promised Outputs
> ----------------
>
> Fundamentally, we can consider that a solution for scaling
> Bitcoin would be to *promise* that some output *can* appear
> onchain at some point in the future, without requiring that the
> output be shown onchain *right now*.
> Then, we can perform transactional cut-through on spends of the
> promised outputs, without requiring onchain activity ("offchain").
> Only if something Really Bad (TM) happens do we need to actually
> drop the latest set of promised outputs onchain, where it has to
> be verified globally by all fullnodes (and would thus incur scaling
> and privacy costs).
>
> As an example of the above paradigm, consider the Lightning
> Network.
> Outputs representing the money of each party in a channel are
> promised, and *can* appear onchain (via the unilateral close
> mechanism).
> In the meantime, there is a mechanism for performing cut-through,
> allowing transfers between channel participants; any number of
> transactions can be performed that are only "solidified" later,
> without expensive onchain activity.
>
> Thus:
>
> * A CoinPool is really a way to commit to promised outputs.
> To change the distribution of those promised outputs, the
> CoinPool operators need to post an onchain transaction, but
> that is only a 1-input-1-output transaction, and with Schnorr
> signatures the single input requires only a single signature.
> But in case something Really Bad (TM) happens, any participant
> can unilaterally close the CoinPool, instantiating the promised
> outputs.
> * A statechain is really just a CoinPool hosted inside a
> Decker-Wattenhofer or Decker-Russell-Osuntokun construction.
> This allows changing the distribution of those promised outputs
> without using an onchain transaction --- instead, a new state
> in the Decker-Wattenhofer/Decker-Russell-Osuntokun construction
> is created containing the new state, which invalidates all older
> states.
> Again, any participant can unilaterally shut it down, exposing
> the state of the inner CoinPool.
> * A channel factory is really just a statechain where the
> promised outputs are not simple 1-of-1 single-owner outputs,
> but are rather 2-of-2 channels.
> This allows graceful degradation, where even if the statechain
> ("factory") layer has missing participants, individual 2-of-2
> channels can still continue operating as long as they do not
> involve missing participants, without requiring all participants
> to be online for large numbers of transactions.
>
> We can then consider that the base CoinPool usage should be enough,
> as other mechanisms (`OP_CTV`+`OP_CSFS`, `SIGHASH_NOINPUT`) can be
> used to implement statechains and channels and channel factories.
>
> I therefore conclude that what we really need is "just" a way to
> commit ourselves to exposing a set of promised outputs, with the
> proviso that if we all agree, we can change that set (without
> requiring that the current or next set be exposed, for both
> scaling and privacy).
>
> (To Bitcoin Cashers: this is not an IOU, this is *committed* and
> can be enforced onchain, that is enough to threaten your offchain
> counterparties into behaving correctly.
> They cannot gain anything by denying the outputs they promised,
> you can always drop it onchain and have it enforced, thus it is
> not just merely an IOU, as IOUs are not necessarily enforceable,
> but this mechanism *would* be.
> Blockchain as judge+jury+executioner, not noisy marketplace.)
>
> Importantly: both `OP_CTV` and `OP_TLUV` force the user to
> decide on a particular, but ultimately arbitrary, ordering for
> promised outputs.
> 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.
>
> Digression: N-of-N With Eviction
> --------------------------------
>
> An issue with using an N-of-N construction is that if any single
> participant is offline, the construction cannot advance its state.
>
> This has lead to some peopple proposing to instead use K-of-N
> once N reaches much larger than 2 participants for CoinPools/statechains/
> channel factories.
>
> However, even so, K-of-N still requires that K participants remain
> online, and the level K is a security parameter.
> If less than K participants are online, then the construction
> *still* cannot advance its state.
>
> Worse, because K < N, a single participant can have its funds
> outright stolen by a quorum of K participants.
> There is no way to prove that the other participants in the same
> construction are not really sockpuppets of the same real-world
> entity, thus it is entirely possible that the K quorum is actually
> just a single participant that is now capable of stealing the
> funds of all the other participants.
> The only way to avoid this is to use N-oF-N: N-of-N requires
> *your* keys, thus the coins are *your* coins.
> In short: K-of-N, as it allows the state to be updated without your
> keys (on the excuse that "if you are offline, we need to be able to
> update state"), is *not your keys not your coins*.
>
> K-of-N should really only be used if all N are your sockpuppets,
> and you want to HODL your funds.
> This is the difference between consensus "everyone must agree" and
> voting "enough sockpuppets can be used to overpower you".
>
> 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.
>
> This avoids the *not your keys not your coins* problem of K-of-N
> constructions, while simultaneously providing a way to advance
> the state without the full participant set being online.
>
> The only real problem with `OP_TLUV` is that it takes O(log N)
> hash revelations to evict one participant, and each evicted
> participant requires one separate transaction.
>
> K-of-N has the "advantage" that even if you are offline, the state
> can be advanced without evicting you.
> However, as noted, as the coins can be spent without your keys,
> the coins are not your coins, thus this advantage may be considered
> dubious --- whether you are online or offline, a quorum of K can
> outright steal your coins.
> Eviction here requires that your coins be returned to your control.
>
> Committing To An Unordered Set
> ------------------------------
>
> In an N-of-N CoinPool/statechain/channel factory, the ownership
> of a single onchain UTXO is shared among N participants.
> That is, there are a number of promised outputs, not exposed
> onchain, which the N participants agree on as the "real" current
> state of the construction,
> However, the N participants can also agree to change the current
> state of the construction, if all of them sign off on the change.
>
> Each of the promised outputs has a value, and the sum of all
> promised values is the value of the onchain UTXO.
> Interestingly, each of the promised outputs also has an SECP256K1
> point that can be used as a public key, and the sum of all
> promised points is the point of the onchain UTXO.
>
> Thus, the onchain UTXO can serve as a commitment to the sum of
> the promised outputs.
> The problem is committing to each of the individual promised
> outputs.
>
> We can observe that a digital signature not only proves knowledge
> of a private key, it also commits to a particular message.
> Thus, we can make each participant sign their own expected
> promised output, and share the signature for their promised
> output.
>
> When a participant is to be evicted, the other participants
> take the signature for the promised output of the to-be-evicted
> participant, and show it onchain, to attest to the output.
> Then, the onchain mechanism should then allow the rest of the
> funds to be controlled by the N-of-N set minus the evicted
> participant.
>
> `OP_EVICT`
> ----------
>
> With all that, let me now propose the `OP_EVICT` opcode.
>
> `OP_EVICT` accepts a variable number of arguments.
>
> * The stack top is either the constant `1`, or an SECP256K1
> point.
> * If it is `1` that simply means "use the Taproot internal
> pubkey", as is usual for `OP_CHECKSIG`.
> * The next stack item is a number, equal to the number of
> outputs that were promised, and which will now be evicted.
> * The next stack items will alternate:
> * A number indicating an output index.
> * A signature for that output.
> * Output indices must not be duplicated, and indicated
> outputs must be SegWit v1 ("Taproot") outputs.
> The public key of the output will be taken as the public
> key for the corresponding signature, and the signature
> only covers the output itself (i.e. value and
> `scriptPubKey`).
> This means the signature has no `SIGHASH`.
> * As the signature covers the public key, this prevents
> malleation of a signature using one public key to a
> signature for another public key.
> * After that is another signature.
> * This signature is checked using `OP_CHECKSIG` semantics
> (including `SIGHASH` support).
> * The public key is the input point (i.e. stack top)
> **MINUS** all the public keys of the indicated outputs.
>
> As a concrete example, suppose A, B, C, and D want to make a
> CoinPool (or offchain variant of such) with the following
> initial state:
>
> * A := 10
> * B := 6
> * C := 4
> * D := 22
>
> Let us assume that A, B, C, and D have generated public
> keys in such a way to avoid key cancellation (e.g.
> precommitment, or the MuSig scheme).
>
> The participants then generate promised outputs for the
> above, and each of them shares signatures for the promised
> outputs:
>
> * sign(a, "A := 10")
> * sign(b, "B := 6")
> * sign(c, "C := 4")
> * sign(d, "D := 22")
>
> Once that is done, they generate:
>
> * Q = A + B + C + D
> * P = h(Q|`<1> OP_EVICT`) * Q
>
> Then they spend their funds, creating a Taproot output:
>
> * P := 42
>
> If all participants are online, they can move funds between
> each other (or to other addresses) by cooperatively signing
> using the point P, and the magic of Taproot means that use
> of `OP_EVICT` is not visible.
>
> 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 := 6", and they reveal the `OP_EVICT` Tapscript
> as well as sign(b, "B := 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.
>
> Note that the opcode as described above allows for multiple
> evictions in the same transaction.
> If B and C are offline, then the remaining participants
> simply need to expose multiple outputs in the same
> transaction.
>
> Security
> --------
>
> I am not a cryptographer.
> Thus, the security of this scheme is a conjecture.
>
> As long as key cancellation is protected against, it should
> be secure.
> The combined fund cannot be spent except if all participants
> agree.
> A smaller online participant set can be created only if a
> participant is evicted, and eviction will force the owned
> funds of the evicted participant to be instantiated.
> The other participants cannot synthesize an alternate
> signature signing a different value without knowledge of the
> privkey of the evicted participant.
>
> 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.
> As the signature covers the pubkey, it should be safe to
> use a non-hardened derivation scheme so that only a single
> root privkey is needed.
>
> Additional Discussion
> ---------------------
>
> ### Eviction Scheme
>
> We can consider that the eviction scheme proposed here is the
> following contract:
>
> * Either all of us agree on some transfer, OR,
> * Give me my funds and the rest of you can all go play with
> your funds however you want.
>
> The signature that commits to a promised output is then the
> agreement that the particular participant believes they are
> entitled to a particular amount.
>
> We can consider that a participant can re-sign their output
> with a different amount, but that is why `OP_EVICT` requires
> the *other* participants to cooperatively sign as well.
> If the other participants cooperatively sign, they effectively
> agree to the participant re-signing for a different amount,
> and thus actually covered by "all of us agree".
>
> ### Pure SCRIPT Contracts
>
> A "pure SCRIPT contract" is a Taproot contract where the
> keyspend path is not desired, and the contract is composed of
> Tapscript branches.
>
> In such a case, the expected technique would be for the
> contract participants to agree on a NUMS point where none
> of the participants can know the scalar (private key) behind
> the point, and to use that as the internal Taproot pubkey
> `Q`.
> For complete protocols, the NUMS point can be a protocol-defined
> constant.
>
> As the `OP_EVICT` opcode requires that each promised output
> be signed, on the face of it, this technique cannot be used
> for `OP_EVICT`-promised outputs, as it is impossible to sign
> using the NUMS point.
>
> However, we should note that the requirement of a "pure SCRIPT"
> contract is that none of the participants can unilaterally
> sign an alternate spend.
> Using an N-of-N of the participants as the Taproot internal
> pubkey is sufficient to ensure this.
>
> As a concrete example: suppose we want an HTLC, which has a
> hashlock branch requiring participant A, and a timelock branch
> requiring participant B.
> Such a simple scheme would not require that both A and B be
> able to cooperatively spend the output, thus we might have
> preferred the technique of using a NUMS point as Taproot
> internal pubkey.
> But using a NUMS point would not allow any signature, even the
> `OP_EVICT`-required signatures-of-promised-outputs.
>
> Instead of using a NUMS point for the Taproot internal pubkey,
> we can use the sum of `A[tmp] + B[tmp]` (suitably protected
> against key cancellation).
> Then both A and B can cooperatively sign the promised output,
> and keep the promised output in an `OP_EVICT`-enforced UTXO.
> After creating the signature for the promised output, A and B
> can ensure that the keypath branch cannot be used by securely
> deleting the private keys for `A[tmp]` and `B[tmp]`
> respectively.
>
> ### Signature Half-Aggregation
>
> It is possible to batch-validate, and as `OP_EVICT` must
> validate at least two signatures (an eviction and the
> signature of the remaining) it makes sense to use batch
> validation for `OP_EVICT`.
>
> Of note is that Schnorr signatures allow for third-party
> half-aggregation, where the `s` components of multiple
> signatures are summed together, but the `R` components
> are not.
>
> (Warning: I am not aware of any security proofs that
> half-aggregation is actually **safe**!
> In particular, BIP-340 does not define half-aggregation,
> and its batch validation algorithm is not, to my naivete,
> extensible to half-aggregation.)
>
> Basically, if we are batch validating two signatures
> `(R[0], s[0])`, `(R[1], s[1])` of two messages `m[0]`
> and `m[1]` signed by two keys `A[0]` and `A[1]`, we
> would do:
>
> * For `i = 0, 1`: `e[i] = h(R[i]|m[i])`
> * Check: `(s[0] + s[1]) * G` is equal to `R[0] + e[0] * A[0] + R[1] + e[1]
> * A[1]`.
>
> As we can see, the `s` can be summed before being
> posted on the blockchain, as validators do not need
> individual `s[i]`.
> However, `R` cannot be summed as each one needs to be
> hashed.
>
> This half-aggregation is third-party, i.e. someone
> without any knowledge of any private keys can simply
> sum the `s` components of multiple signatures.
>
> As `OP_EVICT` always validates at least two signatures,
> using half-aggregation can remove at least 32 weight
> units, and each additional promised output being evicted
> is another signature whose `s` can be added to the sum.
> Of course, **that depends on half-aggregation being
> secure**.
>
> ### Relationship to Other Opcodes
>
> `OP_CTV` does other things than this opcode, and cannot
> be used as a direct alternative.
> In particular while `OP_CTV` *can* commit to a set of
> promised outputs, if a promised output needs to be
> published, the remaining funds are now distributed over a
> set of UTXOs.
> Thus, "reviving" the CoinPool (or offchain variant thereof)
> requires consuming multiple UTXOs, and the consumption of
> multiple UTXOs is risky unless specifically designd for it.
> (In particular, if the UTXOs have different signer sets,
> one signer set can initially cooperate to revive the
> CoinPool, then spend their UTXO to a different transaction,
> which if confirmed will invalidate the revival transaction.)
>
> This opcode seems largely in direct competitiong with
> `OP_TLUV`, with largely the same design goal.
> 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.
>
> It may be possible to implement `OP_EVICT` in terms of
> `OP_TX`/`OP_TXHASH`, `OP_CSFS`, and a point-subtraction
> operation.
> However, `OP_EVICT` allows for the trivial implementation
> of batch validation (and, if half-aggregation is safe, to
> use half-aggregation instead), whereas we expect multiple
> `OP_CSFS` to be needed to implement this, without any
> possibility of batch validation.
> It may be possible to design an `OP_CSFS` variant that
> allows batch validation, such as by extending the virtual
> machine with an accumulator for pending signature
> validations.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
[-- Attachment #2: Type: text/html, Size: 31050 bytes --]
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-18 18:09 ` Antoine Riard
@ 2022-02-18 23:39 ` ZmnSCPxj
2022-02-19 0:56 ` Jeremy Rubin
2022-02-22 0:17 ` Antoine Riard
0 siblings, 2 replies; 16+ messages in thread
From: ZmnSCPxj @ 2022-02-18 23:39 UTC (permalink / raw)
To: Antoine Riard; +Cc: Bitcoin Protocol Discussion, Anthony Towns
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 output 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 same 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 to.
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 is 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 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, 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 := 6", and they reveal the `OP_EVICT` Tapscript
> > as well as sign(b, "B := 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 updated 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 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 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/003479.html
Regards,
ZmnSCPxj
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-18 23:39 ` ZmnSCPxj
@ 2022-02-19 0:56 ` Jeremy Rubin
2022-02-19 1:17 ` ZmnSCPxj
2022-02-19 1:46 ` Greg Sanders
2022-02-22 0:17 ` Antoine Riard
1 sibling, 2 replies; 16+ messages in thread
From: Jeremy Rubin @ 2022-02-19 0:56 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 11052 bytes --]
This is a fascinating post and I'm still chewing on it.
Chiming in with two points:
Point 1, note with respect to evictions, revivals, CTV, TLUV:
CTV enables 1 person to be evicted in O(log N) or one person to leave in
O(log N). TLUV enables 1 person to leave in O(1) O(log N) transactions, but
evictions take (AFAICT?) O(N) O(log N) transactions because the un-live
party stays in the pool. Hence OP_EVICT helps also make it so you can kick
someone out, rather than all having to leave, which is an improvement.
CTV rejoins work as follows:
suppose you have a pool with 1 failure, you need to do log N txns to evict
the failure, which creates R * log_R(N) outputs, which can then do a
transaction to rejoin.
For example, suppose I had 64 people in a radix 4 tree. you'd have at the
top level 4 groups of 16, then 4 groups of 4 people, and then 1 to 4 txns.
Kicking 1 person out would make you do 3 txns, and create 12 outputs total.
A transaction spending the 11 outputs that are live would capture 63 people
back into the tree, and with CISA would not be terribly expensive. To be a
bit more economical, you might prefer to just join the 3 outputs with 16
people in it, and yield 48 people in one pool. Alternatively, you can
lazily re-join if fees make it worth it/piggybacking another transaction,
or operate independently or try to find new, better, peers.
Overall this is the type of application that necessitates *exact* byte
counting. Oftentimes things with CTV seem inefficient, but when you crunch
the numbers it turns out not to be so terrible. OP_EVICT seems promising in
this regard compared to TLUV or accumulators.
Another option is to randomize the CTV trees with multiple outputs per
party (radix Q), then you need to do Q times the evictions, but you end up
with sub-pools that contain more people/fractional liquidity (this might
happen naturally if CTV Pools have channels in them, so it's good to model).
Point 2, on Eltoo:
One point of discomfort I have with Eltoo that I think is not universal,
but is shared by some others, is that non-punitive channels may not be good
for high-value channels as you do want, especially in a congested
blockspace world, punishments to incentivize correct behavior (otherwise
cheating may look like a free option).
Thus I'm reluctant to fully embrace designs which do not permit nested
traditional punitive channels in favor of Eltoo, when Eltoo might not have
product-market-fit for higher valued channels.
If someone had a punitive-eltoo variant that would ameliorate this concern
almost entirely.
Cheers,
Jeremy
--
@JeremyRubin <https://twitter.com/JeremyRubin>
On Fri, Feb 18, 2022 at 3:40 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> 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 output
> 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 same
> 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 to.
> 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 is
> 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 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,
> 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 := 6", and they reveal the `OP_EVICT` Tapscript
> > > as well as sign(b, "B := 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 updated
> 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 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 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/003479.html
>
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
[-- Attachment #2: Type: text/html, Size: 16297 bytes --]
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-19 0:56 ` Jeremy Rubin
@ 2022-02-19 1:17 ` ZmnSCPxj
2022-02-19 1:46 ` Greg Sanders
1 sibling, 0 replies; 16+ messages in thread
From: ZmnSCPxj @ 2022-02-19 1:17 UTC (permalink / raw)
To: Jeremy Rubin, Bitcoin Protocol Discussion
Good morning Jeremy,
> This is a fascinating post and I'm still chewing on it.
>
> Chiming in with two points:
>
> Point 1, note with respect to evictions, revivals, CTV, TLUV:
>
> CTV enables 1 person to be evicted in O(log N) or one person to leave in O(log N). TLUV enables 1 person to leave in O(1) O(log N) transactions, but evictions take (AFAICT?) O(N) O(log N) transactions because the un-live party stays in the pool. Hence OP_EVICT helps also make it so you can kick someone out, rather than all having to leave, which is an improvement.
>
> CTV rejoins work as follows:
>
> suppose you have a pool with 1 failure, you need to do log N txns to evict the failure, which creates R * log_R(N) outputs, which can then do a transaction to rejoin.
>
> For example, suppose I had 64 people in a radix 4 tree. you'd have at the top level 4 groups of 16, then 4 groups of 4 people, and then 1 to 4 txns. Kicking 1 person out would make you do 3 txns, and create 12 outputs total. A transaction spending the 11 outputs that are live would capture 63 people back into the tree, and with CISA would not be terribly expensive. To be a bit more economical, you might prefer to just join the 3 outputs with 16 people in it, and yield 48 people in one pool. Alternatively, you can lazily re-join if fees make it worth it/piggybacking another transaction, or operate independently or try to find new, better, peers.
>
> Overall this is the type of application that necessitates *exact* byte counting. Oftentimes things with CTV seem inefficient, but when you crunch the numbers it turns out not to be so terrible. OP_EVICT seems promising in this regard compared to TLUV or accumulators.
>
> Another option is to randomize the CTV trees with multiple outputs per party (radix Q), then you need to do Q times the evictions, but you end up with sub-pools that contain more people/fractional liquidity (this might happen naturally if CTV Pools have channels in them, so it's good to model).
Do note that a weakness of CTV is that you *have to* split up the CoinPool into many smaller pools, and re-merging them requires waiting for onchain confirmation.
This overall means you have no real incentive to revive the original CoinPool minus evicted parties.
`OP_EVICT` lets the CoinPool revival be made into the same transaction that performs the evict.
> Point 2, on Eltoo:
>
> One point of discomfort I have with Eltoo that I think is not universal, but is shared by some others, is that non-punitive channels may not be good for high-value channels as you do want, especially in a congested blockspace world, punishments to incentivize correct behavior (otherwise cheating may look like a free option).
>
> Thus I'm reluctant to fully embrace designs which do not permit nested traditional punitive channels in favor of Eltoo, when Eltoo might not have product-market-fit for higher valued channels.
>
> If someone had a punitive-eltoo variant that would ameliorate this concern almost entirely.
Unfortunately, it seems the way to any kind of N > 2 construction *with* penalty would require bonds, such as the recent PathCoin idea (which is an N > 2 construction *with* penalty, and is definitely offchain for much of its operation).
Having a Decker-Russell-Osuntokun "factory" layer that hosts multiple Poon-Dryja channels is not quite a solution; if old state on Decker-Russell-Osuntokun layer pushes through, then its obsolete Poon-Dryja channels will have all states invalid and unclaimable, but in case of Sybil where some participants are sockpuppets, it would still be possible for a thief to claim the funds from an "invalidated" Poon-Dryja channel if that channel is with a sockpuppet.
Regards,
ZmnSCPxj
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-19 0:56 ` Jeremy Rubin
2022-02-19 1:17 ` ZmnSCPxj
@ 2022-02-19 1:46 ` Greg Sanders
2022-02-19 7:21 ` Billy Tetrud
1 sibling, 1 reply; 16+ messages in thread
From: Greg Sanders @ 2022-02-19 1:46 UTC (permalink / raw)
To: Jeremy Rubin, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 12416 bytes --]
> One point of discomfort I have with Eltoo that I think is not universal,
but is shared by some others, is that non-punitive channels may not be good
for high-value channels as you do want, especially in a congested
blockspace world, punishments to incentivize correct behavior (otherwise
cheating may look like a free option).
Without derailing the conversation too far, "fully" punitive channels also
make large value channels more dangerous from the perspective of bugs
causing old states to be published. High value channels you'll need to have
very high uptime. If you're available, your counterparty is incentivized to
do a mutual close to reduce fees and remove timelocks on outputs. I think
these tradeoffs will result in both types existing for N==2.
On Sat, Feb 19, 2022 at 8:56 AM Jeremy Rubin via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> This is a fascinating post and I'm still chewing on it.
>
> Chiming in with two points:
>
> Point 1, note with respect to evictions, revivals, CTV, TLUV:
>
> CTV enables 1 person to be evicted in O(log N) or one person to leave in
> O(log N). TLUV enables 1 person to leave in O(1) O(log N) transactions, but
> evictions take (AFAICT?) O(N) O(log N) transactions because the un-live
> party stays in the pool. Hence OP_EVICT helps also make it so you can kick
> someone out, rather than all having to leave, which is an improvement.
>
> CTV rejoins work as follows:
>
> suppose you have a pool with 1 failure, you need to do log N txns to evict
> the failure, which creates R * log_R(N) outputs, which can then do a
> transaction to rejoin.
>
> For example, suppose I had 64 people in a radix 4 tree. you'd have at the
> top level 4 groups of 16, then 4 groups of 4 people, and then 1 to 4 txns.
> Kicking 1 person out would make you do 3 txns, and create 12 outputs total.
> A transaction spending the 11 outputs that are live would capture 63 people
> back into the tree, and with CISA would not be terribly expensive. To be a
> bit more economical, you might prefer to just join the 3 outputs with 16
> people in it, and yield 48 people in one pool. Alternatively, you can
> lazily re-join if fees make it worth it/piggybacking another transaction,
> or operate independently or try to find new, better, peers.
>
> Overall this is the type of application that necessitates *exact* byte
> counting. Oftentimes things with CTV seem inefficient, but when you crunch
> the numbers it turns out not to be so terrible. OP_EVICT seems promising in
> this regard compared to TLUV or accumulators.
>
> Another option is to randomize the CTV trees with multiple outputs per
> party (radix Q), then you need to do Q times the evictions, but you end up
> with sub-pools that contain more people/fractional liquidity (this might
> happen naturally if CTV Pools have channels in them, so it's good to model).
>
>
> Point 2, on Eltoo:
>
> One point of discomfort I have with Eltoo that I think is not universal,
> but is shared by some others, is that non-punitive channels may not be good
> for high-value channels as you do want, especially in a congested
> blockspace world, punishments to incentivize correct behavior (otherwise
> cheating may look like a free option).
>
> Thus I'm reluctant to fully embrace designs which do not permit nested
> traditional punitive channels in favor of Eltoo, when Eltoo might not have
> product-market-fit for higher valued channels.
>
> If someone had a punitive-eltoo variant that would ameliorate this concern
> almost entirely.
>
> Cheers,
>
> Jeremy
>
>
>
> --
> @JeremyRubin <https://twitter.com/JeremyRubin>
>
> On Fri, Feb 18, 2022 at 3:40 PM ZmnSCPxj via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
>
>> 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 output
>> 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 same
>> 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 to.
>> 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
>> is 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
>> 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,
>> 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 := 6", and they reveal the `OP_EVICT` Tapscript
>> > > as well as sign(b, "B := 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 updated
>> 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 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 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/003479.html
>>
>>
>> Regards,
>> ZmnSCPxj
>> _______________________________________________
>> 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
>
[-- Attachment #2: Type: text/html, Size: 18156 bytes --]
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-19 1:46 ` Greg Sanders
@ 2022-02-19 7:21 ` Billy Tetrud
2022-02-19 11:41 ` ZmnSCPxj
0 siblings, 1 reply; 16+ messages in thread
From: Billy Tetrud @ 2022-02-19 7:21 UTC (permalink / raw)
To: Greg Sanders, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 13525 bytes --]
> "fully" punitive channels also make large value channels more dangerous
from the perspective of bugs causing old states to be published
Wouldn't it be ideal to have the penalty be to pay for a single extra
transaction fee? That way there is a penalty so cheating attempts aren't
free (for someone who wants to close a channel anyway) and yet a single fee
isn't going to be much of a concern in the accidental publishing case. It
still perplexes me why eltoo chose no penalty at all vs a small penalty
like that.
On Fri, Feb 18, 2022, 19:46 Greg Sanders via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> > One point of discomfort I have with Eltoo that I think is not
> universal, but is shared by some others, is that non-punitive channels may
> not be good for high-value channels as you do want, especially in a
> congested blockspace world, punishments to incentivize correct behavior
> (otherwise cheating may look like a free option).
>
> Without derailing the conversation too far, "fully" punitive channels also
> make large value channels more dangerous from the perspective of bugs
> causing old states to be published. High value channels you'll need to have
> very high uptime. If you're available, your counterparty is incentivized to
> do a mutual close to reduce fees and remove timelocks on outputs. I think
> these tradeoffs will result in both types existing for N==2.
>
> On Sat, Feb 19, 2022 at 8:56 AM Jeremy Rubin via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
>
>> This is a fascinating post and I'm still chewing on it.
>>
>> Chiming in with two points:
>>
>> Point 1, note with respect to evictions, revivals, CTV, TLUV:
>>
>> CTV enables 1 person to be evicted in O(log N) or one person to leave in
>> O(log N). TLUV enables 1 person to leave in O(1) O(log N) transactions, but
>> evictions take (AFAICT?) O(N) O(log N) transactions because the un-live
>> party stays in the pool. Hence OP_EVICT helps also make it so you can kick
>> someone out, rather than all having to leave, which is an improvement.
>>
>> CTV rejoins work as follows:
>>
>> suppose you have a pool with 1 failure, you need to do log N txns to
>> evict the failure, which creates R * log_R(N) outputs, which can then do a
>> transaction to rejoin.
>>
>> For example, suppose I had 64 people in a radix 4 tree. you'd have at the
>> top level 4 groups of 16, then 4 groups of 4 people, and then 1 to 4 txns.
>> Kicking 1 person out would make you do 3 txns, and create 12 outputs total.
>> A transaction spending the 11 outputs that are live would capture 63 people
>> back into the tree, and with CISA would not be terribly expensive. To be a
>> bit more economical, you might prefer to just join the 3 outputs with 16
>> people in it, and yield 48 people in one pool. Alternatively, you can
>> lazily re-join if fees make it worth it/piggybacking another transaction,
>> or operate independently or try to find new, better, peers.
>>
>> Overall this is the type of application that necessitates *exact* byte
>> counting. Oftentimes things with CTV seem inefficient, but when you crunch
>> the numbers it turns out not to be so terrible. OP_EVICT seems promising in
>> this regard compared to TLUV or accumulators.
>>
>> Another option is to randomize the CTV trees with multiple outputs per
>> party (radix Q), then you need to do Q times the evictions, but you end up
>> with sub-pools that contain more people/fractional liquidity (this might
>> happen naturally if CTV Pools have channels in them, so it's good to model).
>>
>>
>> Point 2, on Eltoo:
>>
>> One point of discomfort I have with Eltoo that I think is not universal,
>> but is shared by some others, is that non-punitive channels may not be good
>> for high-value channels as you do want, especially in a congested
>> blockspace world, punishments to incentivize correct behavior (otherwise
>> cheating may look like a free option).
>>
>> Thus I'm reluctant to fully embrace designs which do not permit nested
>> traditional punitive channels in favor of Eltoo, when Eltoo might not have
>> product-market-fit for higher valued channels.
>>
>> If someone had a punitive-eltoo variant that would ameliorate this
>> concern almost entirely.
>>
>> Cheers,
>>
>> Jeremy
>>
>>
>>
>> --
>> @JeremyRubin <https://twitter.com/JeremyRubin>
>>
>> On Fri, Feb 18, 2022 at 3:40 PM ZmnSCPxj via bitcoin-dev <
>> bitcoin-dev@lists•linuxfoundation.org> wrote:
>>
>>> 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 output 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 same
>>> 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 to.
>>> 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
>>> is 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
>>> 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, 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 := 6", and they reveal the `OP_EVICT` Tapscript
>>> > > as well as sign(b, "B := 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
>>> updated 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 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 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/003479.html
>>>
>>>
>>> Regards,
>>> ZmnSCPxj
>>> _______________________________________________
>>> 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
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
[-- Attachment #2: Type: text/html, Size: 19885 bytes --]
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-19 7:21 ` Billy Tetrud
@ 2022-02-19 11:41 ` ZmnSCPxj
2022-02-19 21:59 ` Billy Tetrud
0 siblings, 1 reply; 16+ messages in thread
From: ZmnSCPxj @ 2022-02-19 11:41 UTC (permalink / raw)
To: Billy Tetrud, Bitcoin Protocol Discussion; +Cc: Greg Sanders
Good morning Billy,
> > "fully" punitive channels also make large value channels more dangerous from the perspective of bugs causing old states to be published
>
> Wouldn't it be ideal to have the penalty be to pay for a single extra transaction fee? That way there is a penalty so cheating attempts aren't free (for someone who wants to close a channel anyway) and yet a single fee isn't going to be much of a concern in the accidental publishing case. It still perplexes me why eltoo chose no penalty at all vs a small penalty like that.
Nothing in the Decker-Russell-Osunstokun paper *prevents* that --- you could continue to retain per-participant versions of update+state transactions (congruent to the per-participant commitment transactions of Poon-Dryja) and have each participant hold a version that deducts the fee from their main owned funds.
The Decker-Russell-Osuntokun paper simply focuses on the mechanism by itself without regard to fees, on the understanding that the reader already knows fees exist and need to be paid.
Regards,
ZmnSCPxj
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-19 11:41 ` ZmnSCPxj
@ 2022-02-19 21:59 ` Billy Tetrud
0 siblings, 0 replies; 16+ messages in thread
From: Billy Tetrud @ 2022-02-19 21:59 UTC (permalink / raw)
To: ZmnSCPxj; +Cc: Bitcoin Protocol Discussion, Greg Sanders
[-- Attachment #1: Type: text/plain, Size: 1219 bytes --]
Thanks for the clarification ZmnSCPxj!
On Sat, Feb 19, 2022 at 5:41 AM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote:
> Good morning Billy,
>
> > > "fully" punitive channels also make large value channels more
> dangerous from the perspective of bugs causing old states to be published
> >
> > Wouldn't it be ideal to have the penalty be to pay for a single extra
> transaction fee? That way there is a penalty so cheating attempts aren't
> free (for someone who wants to close a channel anyway) and yet a single fee
> isn't going to be much of a concern in the accidental publishing case. It
> still perplexes me why eltoo chose no penalty at all vs a small penalty
> like that.
>
> Nothing in the Decker-Russell-Osunstokun paper *prevents* that --- you
> could continue to retain per-participant versions of update+state
> transactions (congruent to the per-participant commitment transactions of
> Poon-Dryja) and have each participant hold a version that deducts the fee
> from their main owned funds.
> The Decker-Russell-Osuntokun paper simply focuses on the mechanism by
> itself without regard to fees, on the understanding that the reader already
> knows fees exist and need to be paid.
>
> Regards,
> ZmnSCPxj
>
[-- Attachment #2: Type: text/html, Size: 1550 bytes --]
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-18 23:39 ` ZmnSCPxj
2022-02-19 0:56 ` Jeremy Rubin
@ 2022-02-22 0:17 ` Antoine Riard
2022-02-23 11:42 ` ZmnSCPxj
1 sibling, 1 reply; 16+ messages in thread
From: Antoine Riard @ 2022-02-22 0:17 UTC (permalink / raw)
To: ZmnSCPxj; +Cc: Bitcoin Protocol Discussion, Anthony Towns
[-- Attachment #1: Type: text/plain, Size: 10981 bytes --]
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évr. 2022 à 18:39, ZmnSCPxj <ZmnSCPxj@protonmail•com> a écrit :
> 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 output
> 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 same
> 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 to.
> 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 is
> 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 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,
> 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 := 6", and they reveal the `OP_EVICT` Tapscript
> > > as well as sign(b, "B := 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 updated
> 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 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 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/003479.html
>
>
> Regards,
> ZmnSCPxj
>
[-- Attachment #2: Type: text/html, Size: 12098 bytes --]
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
2022-02-22 0:17 ` Antoine Riard
@ 2022-02-23 11:42 ` ZmnSCPxj
0 siblings, 0 replies; 16+ messages in thread
From: ZmnSCPxj @ 2022-02-23 11:42 UTC (permalink / raw)
To: Antoine Riard; +Cc: Bitcoin Protocol Discussion, Anthony Towns
Good morning Antoine,
> 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 ?
`OP_TLUV` leaves the transaction output with the remaining Tapleaves intact, and, optionally, with a point subtracted from Taproot internal pubkey.
In order to *truly* revive the construct, you need a separate transaction that spends that change output, and puts it back into a new construct.
See: https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-February/003479.html
I describe how this works.
That `OP_EVICT` does another `CHECKSIG` simply cuts through the separate transaction that `OP_TLUV` would require in order to revive the construct.
> > 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.
*shrug* Okay!
> > 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.
See also: https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-February/003479.html
Generally, the reason for a channel to go *onchain*, instead of just being removed inside the channel factory and its funds redistributed elsewhere, is that an HTLC/PTLC is about to time out.
The blockchain is really the only entity that can reliably enforce timeouts.
And, from the above link:
> * If a channel has an HTLC/PTLC time out:
> * If the participant to whom the HTLC/PTLC is offered is
> offline, that may very well be a signal that it is unlikely
> to come online soon.
> The participant has strong incentives to come online before
> the channel is forcibly closed due to the HTLC/PTLC timeout,
> so if it is not coming online, something is very wrong with
> that participant and we should really evict the participant.
> * If the participant to whom the HTLC/PTLC is offered is
> online, then it is not behaving properly and we should
> really evict the participant.
Note the term "evict" as well --- the remaining participants that are presumably still behaving correctly (i.e. not letting HTLC/PTLC time out) evict the participants that *are*, and that is what `OP_EVICT` does, as its name suggests.
Indeed, I came up with `OP_EVICT` *after* musing the above link.
Regards,
ZmnSCPxj
^ permalink raw reply [flat|nested] 16+ messages in thread
end of thread, other threads:[~2022-02-23 11:43 UTC | newest]
Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-02-18 2:45 [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY` ZmnSCPxj
2022-02-18 13:53 ` Erik Aronesty
2022-02-18 14:48 ` ZmnSCPxj
2022-02-18 15:50 ` Erik Aronesty
2022-02-18 16:06 ` ZmnSCPxj
2022-02-18 13:55 ` Jonas Nick
2022-02-18 18:09 ` Antoine Riard
2022-02-18 23:39 ` ZmnSCPxj
2022-02-19 0:56 ` Jeremy Rubin
2022-02-19 1:17 ` ZmnSCPxj
2022-02-19 1:46 ` Greg Sanders
2022-02-19 7:21 ` Billy Tetrud
2022-02-19 11:41 ` ZmnSCPxj
2022-02-19 21:59 ` Billy Tetrud
2022-02-22 0:17 ` Antoine Riard
2022-02-23 11:42 ` ZmnSCPxj
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox