Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`

From: Erik Aronesty <erik@q32•com>
To: ZmnSCPxj <ZmnSCPxj@protonmail•com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Cc: Anthony Towns <aj@erisian•com.au>
Subject: Re: [bitcoin-dev] `OP_EVICT`: An Alternative to `OP_TAPLEAFUPDATEVERIFY`
Date: Fri, 18 Feb 2022 08:53:09 -0500	[thread overview]
Message-ID: <CAJowKg+cK3ZjPCjcDK8v5qFA=uCHD7gcR8ymroXBFicU5jzY8Q@mail.gmail.com> (raw)
In-Reply-To: <6nZ-SkxvJLrOCOIdUtLOsdnl94DoX_NHY0uwZ7sw78t24FQ33QJlJU95W7Sk1ja5EFic5a3yql14MLmSAYFZvLGBS4lDUJfr8ut9hdB7GD4=@protonmail.com>

[-- 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 --]