OP_PEEL: Unilaterally exitable coin pools

Published 2022-10-27

OP_PEEL

Unilaterally exitable coin pools.

Introduction

OP_PEEL allows building a pool of coins, rendered on-chain as a single UTXO, where each user can unilaterally withdraw funds by “peeling” the UTXO of some of its funds.

The main motivation for this mechanism is improving upon some of the drawbacks of MRTTREE-backed pools, in the following ways:

  • Removes the need to keep track of and pre-sign a large number of transactions
  • Removes the need to have timelocks and spending deadlines of the pool
  • Fixes possible griefing attacks for the on-chain liquidity provider
  • Reduces transaction fees paid for on-chain redeeming
  • Reduces on-chain footprint of on-chain redeeming

OP_PEEL works by ensuring that a given UTXO being spent in a transaction is split such that some amount is freely spendable by the holder of a private key while the rest of output amount is enforced to go back to a group key.

                          +------------+                     
                          | Single Key |                     
                     +--->| 1 DCR      |                     
                     |    +------------+                     
+-------------+      |                                       
| Group Input |------|                                       
| 10 DCR      |      |                                       
+-------------+      |    +--------------------+             
                     +--->| Group βˆ’ Single Key |             
                          | 9 DCR              |             
                          +--------------------+             

OP_PEEL Validation Equations

Reminder: Schnorr

Recall the standard Schnorr signature scheme:

$e = H(R,M)$

$sG = R + eX$

$Οƒ = (R, s)$

where

  • $M$ is the message
  • $R$ is the public nonce $R = rG$
  • $X$ is the public key $X = xG$

Reminder: MuSig

Recall the MuSig multi-signature scheme:

$L = H(X_0, …, X_n)$

$X_i’ = H(L,X_i)X_i$

$X’ = \displaystyle\sum_{i = 0}^{n-1}{X_i’}$

$R = \displaystyle\sum_{i=0}^{n-1}{R_i}$

$s_i = r_i + ex_i'$

$s = \sum{s_i}$

$Οƒ = (R, s)$

Where

  • $e$ is the same as a standard Schnorr sig

Unilateral Group Exit

This section informally explains how the script that controls a group built around the OP_PEEL opcode would work. This is a high level overview of the OP_PEEL semantics, and additional details about the specific encoding of the fields, concrete implementation nuances and the group building process will be provided in later sections.

For presentation purposes, assume an OP_PEEL group was built. The group consists of multiple “leaf elements”, each considered as “owned” by a specific key pair. The resulting group consists of:

ElementMeaning
$I = {0,…,n-1}$The set of indices of the group participants
$X’ = \displaystyle\sum_{i=0}^{n-1}{H(L,X_i)X_i}$The MuSig group key
$R = \displaystyle\sum_{i=0}^{n-1}{\sum_{j=0}^{n-1}{r_{ij}G}}$Joint nonce, one from each member for each leaf group element
$\forall{i \in I},s_{i} = \displaystyle{\sum_{j=0,j\neq i}^{n-1}{r_{ij}+H(X’,R,i)x’_j}}$A MuSig group signature scalar, one for each leaf group element excluding the scalar from the leaf’s owner

Now, assume a subset of the OP_PEEL group wishes to exit from it, by withdrawing their proportional amount of funds. A valid spending transaction will provide the following data (the subscript $_a$ means “already spent”, $_s$ means “spending”, $_r$ means “remaining”, and $_g$ means “previously in the group”):

ElementMeaning
$I_s \sube I - I_a$The spending indices are a subset of all indices, excluding those already spent
$n_s = \text{\textbar}I_s\text{\textbar}$The size of subset being spent
$n_r = n_g - n_s, n_r \ge 0$The number of remaining entries (“change”) needs to be non-negative
$X’ = X’_a + X’_s + X’_r$The group key equals the sum of the already spent, spending and remaining keys
$R = R_a + R_s + R_r$The joint nonce is the sum of the already spent, spending and remaining nonces
$s_s = \displaystyle\sum_{i\in I_s}{s_i} + r_{ii} + H(X’,R,i)x_i'$The signature scalar for the specific subset being wthdrawn, with the addition of the owner’s share of the signature
$\sigma = (R_{\sigma}, s_{\sigma} \colon X’_s )$A standard transaction signature under the $X’_s$ key

By providing the above data, the subset $I_s$ of the OP_PEEL group can prove that

  1. They were a part of the original group
  2. They have not yet redeemed their funds (i.e. are not part of $I_a$)
  3. They are in control of the corresponding joint private key $x’_s$
  4. The entire group has agreed that the subgroup can claim this particular subset

Overview of the OP_PEEL Semantics

The redeem script of an OP_PEEL group (interpreted as the “already spent” subset of the group) is:

$\gdef\opsep{\enspace,\enspace}$

$\text{RedeemScript} \Coloneqq [X’ \opsep X’_a \opsep R \opsep R_a \opsep n_g \opsep \text{𝙾𝙿\_𝙿𝙴𝙴𝙻}]$

While the signature script is the following:

$\text{SigScript} \Coloneqq [X’_s \opsep R_s \opsep I_s \opsep s_s \opsep R_Οƒ \opsep s_Οƒ]$

When verifying this particular signature script, the verifier pops all the data from the stack (using the standard P2SH verification scheme), then performs the following:

  • Compute $n_s = |I_s|$
  • If $n_s < n_g$:
    • Determine what the “change output” is
    • Compute $n_r = n_g - n_s$
    • Assert that the change output amount is a consistent fraction of the input: $A_{out} = \lfloor \cfrac{A_{in} * n_r}{n_g} \rfloor$
    • Assert the change output script is a P2SH output, paying to the corresponding redeem script $[X’ \opsep (X’_a + X’_s) \opsep R \opsep (R_a + R_s) \opsep n_r \opsep \text{𝙾𝙿\_𝙿𝙴𝙴𝙻}]$
  • Compute $s_vG = R_s + \displaystyle\sum_{i \in I_s}H(X’,R,i)X'$
  • Compute $s_sG$
  • Assert $s_vG = s_sG$
  • Perform the standard Schnorr tx signature validation over $(R_Οƒ, s_Οƒ : X’_s)$

In the next sections we discuss some issues related to the implementation of these semantics in the actual txscript engine.

Output Selection

In the case where $n_r > 0$ (i.e. not all funds are being widthdrawn from the OP_PEEL group), there is a need to ensure the “change output” (the remaining amount in the OP_PEEL group) is consistent.

In such a case, the verifier needs to be able to identify the correct output index in the spending transaction. A simple mechanism for doing this would be able to establish (in the OP_PEEL implementation) that the change output must have the same index as the input. This avoids having to specify (in the SigScript) the output index (which saves space) but is less flexible than explicitly specifying the index.

In the case where $n_r = 0$, there remains no change in the group, therefore the change checks are not performed.

Fractional Change Amount

For groups where the group size is not an integer factor of the individual leaf amounts, there is the issue that some leafs will be able to extract a larger amount from the group than others1 . This would be equivalent to saying there is a sub-atom change amount that gets accumulated over multiple widthrawals.

It’s preferable to build groups where the leaf amount is a multiple of the group size, to avoid such issue.

Encoding of the Spending Indices

The $I_s$ component of the signature script tracks which specific leafs are being widthdrawn from the group in this transaction.

This is a set of integers that needs to be encoded in the SigScript, therefore an efficient implementation is needed for its encoding under different scenarios: whether the indices are sparse (large difference between each individual one) or largely sequential, whether there are sequantial groups, the number of indices, etc.

The specific encoding format for this set will have to be decided while writing the specification for the OP_PEEL opcde. One example of an efficient set implementation is the Roaring Bitmap.

Verifier Performance Considerations

The most important performance consideration from the verifier’s point of view is the inner loop needed to compute the final verification point:

$$ s_vG = R_s + \displaystyle\sum_{i \in I_s}H(X’,R,i)X’ $$

This loop involves one hash, one EC scalar multiplication and one EC point addition for each leaf being widthdrawn, where the EC scalar multiplication is the slowest operation (by several orders of magnitude in the current implementation).

As such, some sort of maximum number of indices to be widthdrawn would have to be imposed (either on a per-input, per-transaction or per-block basis).

Group Building

The most straightforward protocol to build an OP_PEEL group is a three step protocol over a message board, similar to how a MuSig3 signature is buit:

  • Users share hashes for their individual $X_i$ and for all their $R_{ij}$
  • Users reveal their $X_i$ and $R_{ij}$
  • Users compute each $s_{ij} = r_{ij} + H(R,X’,i)x’_i $
  • Users share each $s_{ij}$ except for the $i=j$ case, which is kept secret

One interpretation of this procedure is that each OP_PEEL leaf is an individual MuSig over the unique tuple $(R,X’,i)$.

By keeping their own share a secret (i.e., not revealing $s_{ii}$), the user is assured they are the only ones that can redeem this particular leaf.

A more advanced protocol could be designed, using CSPP to improve privacy during the group building stage.

Considerations

Some considerations about this method for group building.

Linear Unilateral Group Exiting

The original MRTTREE group idea uses a logarithmic widthrawal mechanism, where to redeem an individual leaf amount, the entire branch needs to be broadcast. Only those leafs which are all descendants of a specific branch can be aggregated and rewritten into a single transaction output.

This leads to a simple griefing attack where an adversarial user may redeem every other leaf, forcing other user(s) to redeem each leaf in an individual transaction, thus increasing the total amount of fees paid and the total time required to redeem funds.

An widthdrawal from an OP_PEEL based group, on the other hand, is not suceptible to that attack, given that all leafs may be redeemed immediately, in a single transaction.

Delayed Widthdrawals

One disadvantage of OP_PEEL groups, however, is the fact that widrawals may be delayed by the remaining parties of the group, by purposefully performing redemptions of single leafs.

This is limited by the size of group (i.e. number of leafs), so users must be mindful of participating in large groups.

On the other hand, if multiple users are willing to coordinate, a single transaction may be used to redeem the funds of multiple users simply by following the standard procedure of summing their leaf shares (their various $s_ij$) and creating a standard MuSig for the redeeming transaction (the $(R_Οƒ, s_Οƒ : X’_s)$).

State Storage

In order to redeem a leaf in the future, users will need to store the individual $s_i = \displaystyle\sum{s_{ij}}$, plus the respective $R_{ij}$ and $x_i$, along with the group-wide information.

Conclusion

The main goal for introducing OP_PEEL is to build multi-user pools of funds, rendered as a single on-chain UTXO, such that any individual participant of the pool can unilaterally extract back its shares without requiring full or even partial group coordination protocols for the redemption stage of the contract

In such applications, the group first coordinates to build the UTXO that pays into an OP_PEEL contract under the entire group’s key. As individual participants wish to remove funds from the pool, they may create, sign and publish transactions that spend from the group UTXO. That participant’s share is sent to an address under their control, while the rest remains in the group.

One potential application is building multi-owner Decred tickets, where the users coordinate to pool funds if they do not have enough to purchase a single ticket individually.

By adding other clauses, timelocks or conditions to the redeem script, other uses might be found for multi-user pools of funds.


Notes

[1]
↩
Sample python program to demonstrate fractional widthrawal amounts.
from math import floor
def widthraw_amount(group_amount, n):
  ng = n # nb of leafs remaining in group
  amount = group_amount # Amount remaining in group
  ns = 1 # Number widtdrawn on each iteration
  while (ng > 0):
    if ng < ns:
      ns = ng
    nr = ng - ns
    change = floor((amount * nr) / ng)
    out = amount - change
    print("out: {:5d}  change: {:8d}  nr: {:5d}".format(out, change, nr))
    amount = change
    ng = nr # Remaining in this iteration is group for next

widthraw_amount(1001997, 1000)