Scaling

When there is a high demand for blockspace it becomes very expensive to make transactions. By using OP_CHECKTEMPLATEVERIFY, a large volume payment processor may aggregate all their payments into a single O(1) transaction for purposes of confirmation. Then, some time later, the payments can be expanded out of that UTXO when the demand for blockspace is decreased.

Without OP_CHECKTEMPLATEVERIFY, this is still possible to do with Schnorr signatures (even with ECDSA given multiparty schemes). However, it is not possible to do non-interactively, which fundamentally limits the viability of the approach as interacting to collect signatures from all recipients may be difficult or slow.

The sender of a congestion controlled transaction can choose from many different transaction structures.

The simplest option is a single committed transaction which expands from 1 output to N. Even this simple use case is highly useful because the expansion can wait till cheap block space is available.

As the number of recipients grows, a sender can commit to a tree of outputs using OP_CHECKTEMPLATEVERIFY. The tree permits them to confirm as many payments as they like (i.e., even more than can fit into a block). Such a technique starts to make sense when:

N*size_of(Output) > log(N)*size_of(OP_CHECKTEMPLATEVERIFY Txn) + size_of(Output)

Assuming straightforward transaction sizes, this is around 10 recipients.

Furthermore, the script can commit to variable size expansions – say, one node which expands by 2, by 4, by 8, etc. This allows a trade off between transaction overhead and immediately available block space. Depending on implementation (either at the transaction level, the script level, or via Taproot), the Merkle tree lookup in that case is O(log(log(N))) extra overhead, but the tree can be Huffman encoded to make it E[O(1)] depending on block demand.

Each node of the tree can also attempt to ‘opt in’ to preferring a multiparty signature based spend (using Schnorr signatures or Taproot), but if participants are offline or malicious the expansion can proceed to smaller groups.

The overall overhead of the tree approach (without optimizations) is from the perspective of each user O(log(N)) transactions with an expectation of just 1 additional transaction, and 2N from the perspective of the network. However, given the lack of signatures required for such transactions, the actual overhead is less.

Below is an example implementation of a tree payment in sapio.

// Copyright Judica, Inc 2021
//
// This Source Code Form is subject to the terms of the Mozilla Public
//  License, v. 2.0. If a copy of the MPL was not distributed with this
//  file, You can obtain one at https://mozilla.org/MPL/2.0/.

//! contracts for paying a large set of recipients fee efficiently
use sapio::contract::*;
use sapio::*;
use schemars::*;
use serde::*;
use std::convert::TryInto;
/// instructions to send an amount of coin to an address
#[derive(JsonSchema, Serialize, Deserialize, Clone)]
pub struct Payment {
    /// The amount of coin to send
    pub amount: bitcoin::util::amount::CoinAmount,
    /// # Address
    /// The Address to send to
    pub address: bitcoin::Address,
}
/// Create a tree of payments with a given radix
#[derive(JsonSchema, Serialize, Deserialize)]
pub struct TreePay {
    /// the list of payments to create
    pub participants: Vec<Payment>,
    /// the radix to use (4 or 5 near optimal, depending on if CTV emulation is used this may be inaccurate)
    pub radix: usize,
}

impl TreePay {
    then! {fn expand(self, ctx) {
        let mut builder = ctx.template();
        if self.participants.len() > self.radix {

            for c in self.participants.chunks(self.participants.len()/self.radix) {
                let mut amt =  bitcoin::util::amount::Amount::from_sat(0);
                for Payment{amount, ..}  in c {
                    amt += amount.clone().try_into()?;
                }
                builder = builder.add_output(amt, &TreePay {participants: c.to_vec(), radix: self.radix}, None)?;
            }
        } else {
            for Payment{amount, address} in self.participants.iter() {
                builder = builder.add_output((*amount).try_into()?, &Compiled::from_address(address.clone(), None), None)?;
            }
        }
        builder.into()
    }}
}

impl Contract for TreePay {
    declare! {then, Self::expand}
    declare! {non updatable}
}