path: root/c8/ad92c18ce2c21658e5483850f4b4696576bc5a

Return-Path: <earonesty@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 6635BC000B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 18 Feb 2022 13:53:26 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 3F15641D74
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 18 Feb 2022 13:53:26 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.398
X-Spam-Level: 
X-Spam-Status: No, score=-1.398 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001,
 HEADER_FROM_DIFFERENT_DOMAINS=0.25, HTML_MESSAGE=0.001,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
 autolearn=no autolearn_force=no
Authentication-Results: smtp4.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=q32-com.20210112.gappssmtp.com
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id uX-actqd2K2M
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 18 Feb 2022 13:53:23 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-lj1-x230.google.com (mail-lj1-x230.google.com
 [IPv6:2a00:1450:4864:20::230])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 5C79C4087D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 18 Feb 2022 13:53:23 +0000 (UTC)
Received: by mail-lj1-x230.google.com with SMTP id v22so2526718ljh.7
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 18 Feb 2022 05:53:23 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=q32-com.20210112.gappssmtp.com; s=20210112;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=eIPaaBxenu2KHVV0toJsQWp7CBFfZzIzdqrwgPOYNo4=;
 b=gWjbvGeAWHhWBeLJNvLuYYm39Sl21zHVz/MwPPftmnD8UDzEfDbdU2pfisrNdFjVqE
 ZTQd1eVTJZ6LppOA7ByKcVm5am29o9efHPYsz8AsHuNaVoGu5VKTrzx98tI5cHT8CJJG
 fd3NPVwmBcUm24Ys/T0nzv1HXE5LtH4uNz0vpwNvcC1eR/F3GTUwVKi9OOKh2oX4H1z+
 zKF0RbkMYD14dlNvK7oORn9uqCPMzOC3UE7shRFxuQIQBB9G8Na5iLEMGLOiNwPKtzwf
 tMZ/0XfBqgP/fUXxLql9/zTFo5/BnGjYijvzLEwHwTFoI2QAhBeX/o62jjiuGZ0951Dk
 4iTw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=eIPaaBxenu2KHVV0toJsQWp7CBFfZzIzdqrwgPOYNo4=;
 b=IVx0okUddjnGCUgTb3j20JO0UFpHHLS58PSD2Yo90pkkRm1wnEYQzAP5w8ctBIySwx
 zZlEGCq2FeY3EDatNtGhe/bHHjDKb6bDbFqKPWCpwqMz2cc+LtrrpZDUsUMsx6yaOOBD
 EqY6FxhQR8M6LZK4ie+2uyuNX8xwmN4BlMP/20tt78bndgF9238M9S9zl7c7oyHGc16J
 3r3Vg5NHw9i6DVXoZSVaMtgf4wIjEZ6jUKJTQ0Wfb843MZdf+iQuL5q/9ai44f9Gpran
 lStRiQaiy40khBk1wpHeKVnVG2+5bCJ5UqtKYFuZ8nCRuj9AXQ/CHHyouZGU41enTfHB
 D4gw==
X-Gm-Message-State: AOAM530Rz5vxsoNyS1NCv2nmkc/5CVjxsuS3Eor/gNrqjyr0Pxurm4GQ
 MhEh203VK/d0kMiG9odcRrQXQz+Cfl2JDOcLL53+EIh7pIFf
X-Google-Smtp-Source: ABdhPJwmzmkX05PUD4AXgXNoihUxMim8TZv1FMFXEdrxochwnwHeddBOd28BFQQYU/TBGT93C6Of3bfOf5pSxx6j7Vw=
X-Received: by 2002:a2e:80c6:0:b0:244:e40a:75bc with SMTP id
 r6-20020a2e80c6000000b00244e40a75bcmr5800393ljg.519.1645192400917; Fri, 18
 Feb 2022 05:53:20 -0800 (PST)
MIME-Version: 1.0
References: <6nZ-SkxvJLrOCOIdUtLOsdnl94DoX_NHY0uwZ7sw78t24FQ33QJlJU95W7Sk1ja5EFic5a3yql14MLmSAYFZvLGBS4lDUJfr8ut9hdB7GD4=@protonmail.com>
In-Reply-To: <6nZ-SkxvJLrOCOIdUtLOsdnl94DoX_NHY0uwZ7sw78t24FQ33QJlJU95W7Sk1ja5EFic5a3yql14MLmSAYFZvLGBS4lDUJfr8ut9hdB7GD4=@protonmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Fri, 18 Feb 2022 08:53:09 -0500
Message-ID: <CAJowKg+cK3ZjPCjcDK8v5qFA=uCHD7gcR8ymroXBFicU5jzY8Q@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000a4d8e305d84b3441"
X-Mailman-Approved-At: Fri, 18 Feb 2022 13:55:08 +0000
Cc: Anthony Towns <aj@erisian.com.au>
Subject: Re: [bitcoin-dev] `OP_EVICT`: An Alternative to
	`OP_TAPLEAFUPDATEVERIFY`
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 18 Feb 2022 13:53:26 -0000

--000000000000a4d8e305d84b3441
Content-Type: text/plain; charset="UTF-8"

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
>

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

<div dir=3D"ltr">hey, i read that whole thing, but i&#39;m confused as to w=
hy it&#39;s necessary<div><br></div><div>seems like N of N participants can=
 pre-sign an on-chain transfer of funds for each participant to a new addre=
ss that consists of (N-1) or (N-1) participants, of which each portion of t=
he signature is encrypted for the same (N-1) participants</div><div><br></d=
iv><div>then any (N-1) subset of participants can collude publish that tran=
saction at any time to remove any other member from=C2=A0the pool</div><div=
><br></div><div>all of the set up=C2=A0 (dkg for N-1), and transfer (encryp=
tion of partial sigs) is done offchain, and online with the participants=C2=
=A0that are online<br><br></div><div><br></div></div><br><div class=3D"gmai=
l_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Thu, Feb 17, 2022 at 9:45=
 PM ZmnSCPxj via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxf=
oundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br></di=
v><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;borde=
r-left:1px solid rgb(204,204,204);padding-left:1ex">`OP_EVICT`: An Alternat=
ive to `OP_TAPLEAFUPDATEVERIFY`<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D<br>
<br>
In late 2021, `aj` proposed `OP_TAPLEAFUPDATEVERIFY` in order to<br>
implement CoinPools and similar constructions.<br>
<br>
`Jeremy` observed that due to the use of Merkle tree paths, an<br>
`OP_TLUV` would require O(log N) hash revelations in order to<br>
reach a particular tapleaf, which, in the case of a CoinPool,<br>
would then delete itself after spending only a particular amount<br>
of funds.<br>
He then observed that `OP_CTV` trees also require a similar<br>
revelation of O(log N) transactions, but with the advantage that<br>
once revealed, the transactions can then be reused, thus overall<br>
the expectation is that the number of total bytes onchain is<br>
lesser compared to `OP_TLUV`.<br>
<br>
After some thinking, I realized that it was the use of the<br>
Merkle tree to represent the promised-but-offchain outputs of<br>
the CoinPool that lead to the O(log N) space usage.<br>
I then started thinking of alternative representations of<br>
sets of promised outputs, which would not require O(log N)<br>
revelations by avoiding the tree structure.<br>
<br>
Promised Outputs<br>
----------------<br>
<br>
Fundamentally, we can consider that a solution for scaling<br>
Bitcoin would be to *promise* that some output *can* appear<br>
onchain at some point in the future, without requiring that the<br>
output be shown onchain *right now*.<br>
Then, we can perform transactional cut-through on spends of the<br>
promised outputs, without requiring onchain activity (&quot;offchain&quot;)=
.<br>
Only if something Really Bad (TM) happens do we need to actually<br>
drop the latest set of promised outputs onchain, where it has to<br>
be verified globally by all fullnodes (and would thus incur scaling<br>
and privacy costs).<br>
<br>
As an example of the above paradigm, consider the Lightning<br>
Network.<br>
Outputs representing the money of each party in a channel are<br>
promised, and *can* appear onchain (via the unilateral close<br>
mechanism).<br>
In the meantime, there is a mechanism for performing cut-through,<br>
allowing transfers between channel participants; any number of<br>
transactions can be performed that are only &quot;solidified&quot; later,<b=
r>
without expensive onchain activity.<br>
<br>
Thus:<br>
<br>
* A CoinPool is really a way to commit to promised outputs.<br>
=C2=A0 To change the distribution of those promised outputs, the<br>
=C2=A0 CoinPool operators need to post an onchain transaction, but<br>
=C2=A0 that is only a 1-input-1-output transaction, and with Schnorr<br>
=C2=A0 signatures the single input requires only a single signature.<br>
=C2=A0 But in case something Really Bad (TM) happens, any participant<br>
=C2=A0 can unilaterally close the CoinPool, instantiating the promised<br>
=C2=A0 outputs.<br>
* A statechain is really just a CoinPool hosted inside a<br>
=C2=A0 Decker-Wattenhofer or Decker-Russell-Osuntokun construction.<br>
=C2=A0 This allows changing the distribution of those promised outputs<br>
=C2=A0 without using an onchain transaction --- instead, a new state<br>
=C2=A0 in the Decker-Wattenhofer/Decker-Russell-Osuntokun construction<br>
=C2=A0 is created containing the new state, which invalidates all older<br>
=C2=A0 states.<br>
=C2=A0 Again, any participant can unilaterally shut it down, exposing<br>
=C2=A0 the state of the inner CoinPool.<br>
* A channel factory is really just a statechain where the<br>
=C2=A0 promised outputs are not simple 1-of-1 single-owner outputs,<br>
=C2=A0 but are rather 2-of-2 channels.<br>
=C2=A0 This allows graceful degradation, where even if the statechain<br>
=C2=A0 (&quot;factory&quot;) layer has missing participants, individual 2-o=
f-2<br>
=C2=A0 channels can still continue operating as long as they do not<br>
=C2=A0 involve missing participants, without requiring all participants<br>
=C2=A0 to be online for large numbers of transactions.<br>
<br>
We can then consider that the base CoinPool usage should be enough,<br>
as other mechanisms (`OP_CTV`+`OP_CSFS`, `SIGHASH_NOINPUT`) can be<br>
used to implement statechains and channels and channel factories.<br>
<br>
I therefore conclude that what we really need is &quot;just&quot; a way to<=
br>
commit ourselves to exposing a set of promised outputs, with the<br>
proviso that if we all agree, we can change that set (without<br>
requiring that the current or next set be exposed, for both<br>
scaling and privacy).<br>
<br>
(To Bitcoin Cashers: this is not an IOU, this is *committed* and<br>
can be enforced onchain, that is enough to threaten your offchain<br>
counterparties into behaving correctly.<br>
They cannot gain anything by denying the outputs they promised,<br>
you can always drop it onchain and have it enforced, thus it is<br>
not just merely an IOU, as IOUs are not necessarily enforceable,<br>
but this mechanism *would* be.<br>
Blockchain as judge+jury+executioner, not noisy marketplace.)<br>
<br>
Importantly: both `OP_CTV` and `OP_TLUV` force the user to<br>
decide on a particular, but ultimately arbitrary, ordering for<br>
promised outputs.<br>
In principle, a set of promised outputs, if the owners of those<br>
outputs are peers, does not have *any* inherent order.<br>
Thus, I started to think about a commitment scheme that does not<br>
impose any ordering during commitment.<br>
<br>
Digression: N-of-N With Eviction<br>
--------------------------------<br>
<br>
An issue with using an N-of-N construction is that if any single<br>
participant is offline, the construction cannot advance its state.<br>
<br>
This has lead to some peopple proposing to instead use K-of-N<br>
once N reaches much larger than 2 participants for CoinPools/statechains/<b=
r>
channel factories.<br>
<br>
However, even so, K-of-N still requires that K participants remain<br>
online, and the level K is a security parameter.<br>
If less than K participants are online, then the construction<br>
*still* cannot advance its state.<br>
<br>
Worse, because K &lt; N, a single participant can have its funds<br>
outright stolen by a quorum of K participants.<br>
There is no way to prove that the other participants in the same<br>
construction are not really sockpuppets of the same real-world<br>
entity, thus it is entirely possible that the K quorum is actually<br>
just a single participant that is now capable of stealing the<br>
funds of all the other participants.<br>
The only way to avoid this is to use N-oF-N: N-of-N requires<br>
*your* keys, thus the coins are *your* coins.<br>
In short: K-of-N, as it allows the state to be updated without your<br>
keys (on the excuse that &quot;if you are offline, we need to be able to<br=
>
update state&quot;), is *not your keys not your coins*.<br>
<br>
K-of-N should really only be used if all N are your sockpuppets,<br>
and you want to HODL your funds.<br>
This is the difference between consensus &quot;everyone must agree&quot; an=
d<br>
voting &quot;enough sockpuppets can be used to overpower you&quot;.<br>
<br>
With `OP_TLUV`, however, it is possible to create an &quot;N-of-N With<br>
Eviction&quot; construction.<br>
When a participant in the N-of-N is offline, but the remaining<br>
participants want to advance the state of the construction, they<br>
instead evict the offline participant, creating a smaller N-of-N<br>
where *all* participants are online, and continue operating.<br>
<br>
This avoids the *not your keys not your coins* problem of K-of-N<br>
constructions, while simultaneously providing a way to advance<br>
the state without the full participant set being online.<br>
<br>
The only real problem with `OP_TLUV` is that it takes O(log N)<br>
hash revelations to evict one participant, and each evicted<br>
participant requires one separate transaction.<br>
<br>
K-of-N has the &quot;advantage&quot; that even if you are offline, the stat=
e<br>
can be advanced without evicting you.<br>
However, as noted, as the coins can be spent without your keys,<br>
the coins are not your coins, thus this advantage may be considered<br>
dubious --- whether you are online or offline, a quorum of K can<br>
outright steal your coins.<br>
Eviction here requires that your coins be returned to your control.<br>
<br>
Committing To An Unordered Set<br>
------------------------------<br>
<br>
In an N-of-N CoinPool/statechain/channel factory, the ownership<br>
of a single onchain UTXO is shared among N participants.<br>
That is, there are a number of promised outputs, not exposed<br>
onchain, which the N participants agree on as the &quot;real&quot; current<=
br>
state of the construction,<br>
However, the N participants can also agree to change the current<br>
state of the construction, if all of them sign off on the change.<br>
<br>
Each of the promised outputs has a value, and the sum of all<br>
promised values is the value of the onchain UTXO.<br>
Interestingly, each of the promised outputs also has an SECP256K1<br>
point that can be used as a public key, and the sum of all<br>
promised points is the point of the onchain UTXO.<br>
<br>
Thus, the onchain UTXO can serve as a commitment to the sum of<br>
the promised outputs.<br>
The problem is committing to each of the individual promised<br>
outputs.<br>
<br>
We can observe that a digital signature not only proves knowledge<br>
of a private key, it also commits to a particular message.<br>
Thus, we can make each participant sign their own expected<br>
promised output, and share the signature for their promised<br>
output.<br>
<br>
When a participant is to be evicted, the other participants<br>
take the signature for the promised output of the to-be-evicted<br>
participant, and show it onchain, to attest to the output.<br>
Then, the onchain mechanism should then allow the rest of the<br>
funds to be controlled by the N-of-N set minus the evicted<br>
participant.<br>
<br>
`OP_EVICT`<br>
----------<br>
<br>
With all that, let me now propose the `OP_EVICT` opcode.<br>
<br>
`OP_EVICT` accepts a variable number of arguments.<br>
<br>
* The stack top is either the constant `1`, or an SECP256K1<br>
=C2=A0 point.<br>
=C2=A0 * If it is `1` that simply means &quot;use the Taproot internal<br>
=C2=A0 =C2=A0 pubkey&quot;, as is usual for `OP_CHECKSIG`.<br>
* The next stack item is a number, equal to the number of<br>
=C2=A0 outputs that were promised, and which will now be evicted.<br>
* The next stack items will alternate:<br>
=C2=A0 * A number indicating an output index.<br>
=C2=A0 * A signature for that output.<br>
=C2=A0 * Output indices must not be duplicated, and indicated<br>
=C2=A0 =C2=A0 outputs must be SegWit v1 (&quot;Taproot&quot;) outputs.<br>
=C2=A0 =C2=A0 The public key of the output will be taken as the public<br>
=C2=A0 =C2=A0 key for the corresponding signature, and the signature<br>
=C2=A0 =C2=A0 only covers the output itself (i.e. value and<br>
=C2=A0 =C2=A0 `scriptPubKey`).<br>
=C2=A0 =C2=A0 This means the signature has no `SIGHASH`.<br>
=C2=A0 * As the signature covers the public key, this prevents<br>
=C2=A0 =C2=A0 malleation of a signature using one public key to a<br>
=C2=A0 =C2=A0 signature for another public key.<br>
* After that is another signature.<br>
=C2=A0 * This signature is checked using `OP_CHECKSIG` semantics<br>
=C2=A0 =C2=A0 (including `SIGHASH` support).<br>
=C2=A0 * The public key is the input point (i.e. stack top)<br>
=C2=A0 =C2=A0 **MINUS** all the public keys of the indicated outputs.<br>
<br>
As a concrete example, suppose A, B, C, and D want to make a<br>
CoinPool (or offchain variant of such) with the following<br>
initial state:<br>
<br>
* A :=3D 10<br>
* B :=3D 6<br>
* C :=3D 4<br>
* D :=3D 22<br>
<br>
Let us assume that A, B, C, and D have generated public<br>
keys in such a way to avoid key cancellation (e.g.<br>
precommitment, or the MuSig scheme).<br>
<br>
The participants then generate promised outputs for the<br>
above, and each of them shares signatures for the promised<br>
outputs:<br>
<br>
* sign(a, &quot;A :=3D 10&quot;)<br>
* sign(b, &quot;B :=3D 6&quot;)<br>
* sign(c, &quot;C :=3D 4&quot;)<br>
* sign(d, &quot;D :=3D 22&quot;)<br>
<br>
Once that is done, they generate:<br>
<br>
* Q =3D A + B + C + D<br>
* P =3D h(Q|`&lt;1&gt; OP_EVICT`) * Q<br>
<br>
Then they spend their funds, creating a Taproot output:<br>
<br>
* P :=3D 42<br>
<br>
If all participants are online, they can move funds between<br>
each other (or to other addresses) by cooperatively signing<br>
using the point P, and the magic of Taproot means that use<br>
of `OP_EVICT` is not visible.<br>
<br>
Suppose however that B is offline.<br>
Then A, C, and D then decide to evict B.<br>
To do so, they create a transaction that has an output<br>
with &quot;B :=3D 6&quot;, and they reveal the `OP_EVICT` Tapscript<br>
as well as sign(b, &quot;B :=3D 6&quot;).<br>
This lets them change state and spend their funds without<br>
B being online.<br>
And B remains secure, as they cannot evict B except using<br>
the pre-signed output, which B certifies as their expected<br>
promised output.<br>
<br>
Note that the opcode as described above allows for multiple<br>
evictions in the same transaction.<br>
If B and C are offline, then the remaining participants<br>
simply need to expose multiple outputs in the same<br>
transaction.<br>
<br>
Security<br>
--------<br>
<br>
I am not a cryptographer.<br>
Thus, the security of this scheme is a conjecture.<br>
<br>
As long as key cancellation is protected against, it should<br>
be secure.<br>
The combined fund cannot be spent except if all participants<br>
agree.<br>
A smaller online participant set can be created only if a<br>
participant is evicted, and eviction will force the owned<br>
funds of the evicted participant to be instantiated.<br>
The other participants cannot synthesize an alternate<br>
signature signing a different value without knowledge of the<br>
privkey of the evicted participant.<br>
<br>
To prevent signature replay, each update of an updateable<br>
scheme like CoinPool et al should use a different pubkey<br>
for each participant for each state.<br>
As the signature covers the pubkey, it should be safe to<br>
use a non-hardened derivation scheme so that only a single<br>
root privkey is needed.<br>
<br>
Additional Discussion<br>
---------------------<br>
<br>
### Eviction Scheme<br>
<br>
We can consider that the eviction scheme proposed here is the<br>
following contract:<br>
<br>
* Either all of us agree on some transfer, OR,<br>
* Give me my funds and the rest of you can all go play with<br>
=C2=A0 your funds however you want.<br>
<br>
The signature that commits to a promised output is then the<br>
agreement that the particular participant believes they are<br>
entitled to a particular amount.<br>
<br>
We can consider that a participant can re-sign their output<br>
with a different amount, but that is why `OP_EVICT` requires<br>
the *other* participants to cooperatively sign as well.<br>
If the other participants cooperatively sign, they effectively<br>
agree to the participant re-signing for a different amount,<br>
and thus actually covered by &quot;all of us agree&quot;.<br>
<br>
### Pure SCRIPT Contracts<br>
<br>
A &quot;pure SCRIPT contract&quot; is a Taproot contract where the<br>
keyspend path is not desired, and the contract is composed of<br>
Tapscript branches.<br>
<br>
In such a case, the expected technique would be for the<br>
contract participants to agree on a NUMS point where none<br>
of the participants can know the scalar (private key) behind<br>
the point, and to use that as the internal Taproot pubkey<br>
`Q`.<br>
For complete protocols, the NUMS point can be a protocol-defined<br>
constant.<br>
<br>
As the `OP_EVICT` opcode requires that each promised output<br>
be signed, on the face of it, this technique cannot be used<br>
for `OP_EVICT`-promised outputs, as it is impossible to sign<br>
using the NUMS point.<br>
<br>
However, we should note that the requirement of a &quot;pure SCRIPT&quot;<b=
r>
contract is that none of the participants can unilaterally<br>
sign an alternate spend.<br>
Using an N-of-N of the participants as the Taproot internal<br>
pubkey is sufficient to ensure this.<br>
<br>
As a concrete example: suppose we want an HTLC, which has a<br>
hashlock branch requiring participant A, and a timelock branch<br>
requiring participant B.<br>
Such a simple scheme would not require that both A and B be<br>
able to cooperatively spend the output, thus we might have<br>
preferred the technique of using a NUMS point as Taproot<br>
internal pubkey.<br>
But using a NUMS point would not allow any signature, even the<br>
`OP_EVICT`-required signatures-of-promised-outputs.<br>
<br>
Instead of using a NUMS point for the Taproot internal pubkey,<br>
we can use the sum of `A[tmp] + B[tmp]` (suitably protected<br>
against key cancellation).<br>
Then both A and B can cooperatively sign the promised output,<br>
and keep the promised output in an `OP_EVICT`-enforced UTXO.<br>
After creating the signature for the promised output, A and B<br>
can ensure that the keypath branch cannot be used by securely<br>
deleting the private keys for `A[tmp]` and `B[tmp]`<br>
respectively.<br>
<br>
### Signature Half-Aggregation<br>
<br>
It is possible to batch-validate, and as `OP_EVICT` must<br>
validate at least two signatures (an eviction and the<br>
signature of the remaining) it makes sense to use batch<br>
validation for `OP_EVICT`.<br>
<br>
Of note is that Schnorr signatures allow for third-party<br>
half-aggregation, where the `s` components of multiple<br>
signatures are summed together, but the `R` components<br>
are not.<br>
<br>
(Warning: I am not aware of any security proofs that<br>
half-aggregation is actually **safe**!<br>
In particular, BIP-340 does not define half-aggregation,<br>
and its batch validation algorithm is not, to my naivete,<br>
extensible to half-aggregation.)<br>
<br>
Basically, if we are batch validating two signatures<br>
`(R[0], s[0])`, `(R[1], s[1])` of two messages `m[0]`<br>
and `m[1]` signed by two keys `A[0]` and `A[1]`, we<br>
would do:<br>
<br>
* For `i =3D 0, 1`: `e[i] =3D h(R[i]|m[i])`<br>
* Check: `(s[0] + s[1]) * G` is equal to `R[0] + e[0] * A[0] + R[1] + e[1] =
* A[1]`.<br>
<br>
As we can see, the `s` can be summed before being<br>
posted on the blockchain, as validators do not need<br>
individual `s[i]`.<br>
However, `R` cannot be summed as each one needs to be<br>
hashed.<br>
<br>
This half-aggregation is third-party, i.e. someone<br>
without any knowledge of any private keys can simply<br>
sum the `s` components of multiple signatures.<br>
<br>
As `OP_EVICT` always validates at least two signatures,<br>
using half-aggregation can remove at least 32 weight<br>
units, and each additional promised output being evicted<br>
is another signature whose `s` can be added to the sum.<br>
Of course, **that depends on half-aggregation being<br>
secure**.<br>
<br>
### Relationship to Other Opcodes<br>
<br>
`OP_CTV` does other things than this opcode, and cannot<br>
be used as a direct alternative.<br>
In particular while `OP_CTV` *can* commit to a set of<br>
promised outputs, if a promised output needs to be<br>
published, the remaining funds are now distributed over a<br>
set of UTXOs.<br>
Thus, &quot;reviving&quot; the CoinPool (or offchain variant thereof)<br>
requires consuming multiple UTXOs, and the consumption of<br>
multiple UTXOs is risky unless specifically designd for it.<br>
(In particular, if the UTXOs have different signer sets,<br>
one signer set can initially cooperate to revive the<br>
CoinPool, then spend their UTXO to a different transaction,<br>
which if confirmed will invalidate the revival transaction.)<br>
<br>
This opcode seems largely in direct competitiong with<br>
`OP_TLUV`, with largely the same design goal.<br>
Its advantage is reduced number of eviction transactions,<br>
as multiple evictions, plus the revival of the CoinPool,<br>
can be put in a single transaction.<br>
It has the disadvantage relative to `OP_TLUV` of requiring<br>
point operations.<br>
I have not explored completely, but my instinct suggests<br>
that `OP_TLUV` use may require at least one signature<br>
validation anyway.<br>
<br>
It may be possible to implement `OP_EVICT` in terms of<br>
`OP_TX`/`OP_TXHASH`, `OP_CSFS`, and a point-subtraction<br>
operation.<br>
However, `OP_EVICT` allows for the trivial implementation<br>
of batch validation (and, if half-aggregation is safe, to<br>
use half-aggregation instead), whereas we expect multiple<br>
`OP_CSFS` to be needed to implement this, without any<br>
possibility of batch validation.<br>
It may be possible to design an `OP_CSFS` variant that<br>
allows batch validation, such as by extending the virtual<br>
machine with an accumulator for pending signature<br>
validations.<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000a4d8e305d84b3441--