Payment Pools / Coin Pools

Day 13: Rubin's Bitcoin Advent Calendar

Welcome to day 13 of my Bitcoin Advent Calendar. You can see an index of all the posts here or subscribe at judica.org/join to get new posts in your inbox

Payment Pools are a general concept for a technique to share a single UTXO among a group. They’ve been discussed for a couple years1, but now that Taproot is active are definitely more relevant! In this post we’ll go through some really simple Payment Pool designs before turning it up a little bit :)

Mechanistically, all that is required of a Payment Pool is that:

  1. It’s a single (shared) UTXO2
  2. Every user can get their funds out unilaterally3
  3. A set4 of users can authorize spend the funds
  4. Unspent funds/change stays in the pool

Why Pool?

Pools are really great for a number of reasons. In particular, Payment Pools are fantastic for Scalability since they mean 1 utxo can serve many masters, and also each txn only requires one signature to make a batched payment from a group. Payment Pools are kinda a killer version of a coin-join where you roll the funds from coinjoin to coinjoin automatically5, giving you great privacy. We’ll also see how they benefit decentralization in a couple of days.

What’s the simplest design that can satisfy this?

Imagine a coin that is either N-of-N multisig OR a transaction distributing the coins to all users. The Sapio would look a bit like this:

struct SimplePool {
    /// list of all initial balances
    members: HashMap<PublicKey, Amount>
}

impl SimplePool {
    /// Send their balances to everyone
    #[then]
    fn ejection(self, ctx: Context) {
        let mut t = ctx.template();
        for (key, amount) in self.members.iter() {
            t = t.add_output(amt, &key, None)?;
        }
        t.into()
    }

    /// all signed the transaction!
    #[guard]
    fn all_signed(self, ctx: Context) {
        Clause::Threshold(self.members.len(),
                          self.members
                              .keys()
                              .map(Clause::Key)
                              .collect())
    }
}

impl Contract for SimplePool {
    declare!{then, Self::ejection}
    declare!{finish, Self::all_signed}
}

Let’s check our list:

  1. It’s a single UTXO – Check
  2. Every user can get their funds out unilaterally – Check, with SimplePool::ejection
  3. A set of users can authorize spend the funds – Check, unanimously
  4. Unspent funds/change stay in the pool – We’ll give this a Check, just don’t sign transaction that don’t meet this contstraint.

So we’re good! This is all we need.

But is it really all we need?

It’d be nice if the Payment Pool had a little bit more structure around the updating so that a little bit less was left to the user to do correctly. Luckily, Sapio has tools for that. Let’s define a transition function in Sapio that generates what we should do with Simple::all_signed.

The transition function should take a list of signed updates per participant and generate a transaction for signing (signing the inputs helps with coordinating not signing the incorrect transaction). Any leftover funds should be sent into a new instance of the Payment Pool for future use.

We’ll also make one more change for efficient ejections: In the version I gave above, the unilateral ejection option exits everyone out of the pool, which kinda sucks.

However, we will ‘hybridize’ the payment pool with the tree payment. Then, you would have “hierarchical” pools whereby splitting would keep pools alive. E.g., if you had 30 people in a pool with a splitting radix of 2, 1 person force-ejecting themselves would create something like 1 pool of size 15, 1 pool of size 7, 1 pool of size 4, 1 pool of size 2, and 2 ejected people. They can always re-join a pool again after!

First, we’ll define the basic Pool data and interface:

#[derive(Deserialize, JsonSchema, Clone)]
struct NextTxPool {
    /// map of all initial balances as PK to BTC
    members: BTreeMap<PublicKey, AmountF64>,
    /// The current sequence number (for authenticating state updates)
    sequence: u64,
    /// If to require signatures or not (debugging, should be true)
    sig_needed: bool,
}

impl Contract for NextTxPool {
    declare! {then, Self::ejection}
    declare! {updatable<DoTx>, Self::do_tx}
}

Now we’ll define the logic for ejecting from the pool:

impl NextTxPool {
    /// Sum Up all the balances
    fn total(&self) -> Amount {
        self.members
            .values()
            .cloned()
            .map(Amount::from)
            .fold(Amount::from_sat(0), |a, b| a + b)
    }
    /// Only compile an ejection if the pool has other users in it, otherwise
    /// it's base case.
    #[compile_if]
    fn has_eject(self, ctx: Context) {
        if self.members.len() > 1 {
            ConditionalCompileType::Required
        } else {
            ConditionalCompileType::Never
        }
    }
    /// Split the pool in two -- users can eject multiple times to fully eject.
    #[then(compile_if = "[Self::has_eject]")]
    fn ejection(self, ctx: Context) {
        let mut t = ctx.template();
        let mid = (self.members.len() + 1) / 2;
        // find the middle
        let key = self.members.keys().nth(mid).expect("must be present");
        let mut pool_one: NextTxPool = self.clone();
        pool_one.sequence += 1;
        let pool_two = NextTxPool {
            // removes the back half including key
            members: pool_one.members.split_off(&key),
            sequence: self.sequence + 1,
            sig_needed: self.sig_needed,
        };
        let amt_one = pool_one.total();
        let amt_two = pool_two.total();
        t.add_output(amt_one, &pool_one, None)?
            .add_output(amt_two, &pool_two, None)?
            .into()
    }
}

Next, we’ll define some data types for instructing the pool to update:

/// Payment Request
#[derive(Deserialize, JsonSchema)]
struct PaymentRequest {
    /// # Signature
    /// hex encoded signature of the fee, sequence number, and payments
    hex_der_sig: String,
    fee: AmountF64,
    payments: BTreeMap<Address, AmountF64>,
}
/// New Update message for generating a transaction from.
#[derive(Deserialize, JsonSchema)]
struct DoTx {
    /// # Payments
    /// A mapping of public key in members to signed list of payouts with a fee rate.
    payments: HashMap<PublicKey, PaymentRequest>,
}
/// required...
impl Default for DoTx {
    fn default() -> Self {
        DoTx {
            payments: HashMap::new(),
        }
    }
}
impl StatefulArgumentsTrait for DoTx {}

/// helper for rust type system issue
fn default_coerce(
    k: <NextTxPool as Contract>::StatefulArguments,
) -> Result<DoTx, CompilationError> {
    Ok(k)
}

Lastly, we’ll define the logic for actually doing the update:

impl NextTxPool {
    /// all signed the transaction!
    #[guard]
    fn all_signed(self, ctx: Context) {
        Clause::Threshold(
            self.members.len(),
            self.members.keys().cloned().map(Clause::Key).collect(),
        )
    }
    /// This Function will create a proposed transaction that is safe to sign
    /// given a list of data from participants.
    #[continuation(
        guarded_by = "[Self::all_signed]",
        coerce_args = "default_coerce",
        web_api
    )]
    fn do_tx(self, ctx: Context, update: DoTx) {
        // don't allow empty updates.
        if update.payments.is_empty() {
            return empty();
        }
        // collect members with updated balances here
        let mut new_members = self.members.clone();
        // verification context
        let secp = Secp256k1::new();
        // collect all the payments
        let mut all_payments = vec![];
        let mut spent = Amount::from_sat(0);
        // for each payment...
        for (
            from,
            PaymentRequest {
                hex_der_sig,
                fee,
                payments,
            },
        ) in update.payments.iter()
        {
            // every from must be in the members
            let balance = self
                .members
                .get(from)
                .ok_or(CompilationError::TerminateCompilation)?;
            let new_balance = Amount::from(*balance)
                - (payments
                    .values()
                    .cloned()
                    .map(Amount::from)
                    .fold(Amount::from_sat(0), |a, b| a + b)
                    + Amount::from(*fee));
            // check for no underflow
            if new_balance.as_sat() < 0 {
                return Err(CompilationError::TerminateCompilation);
            }
            // updates the balance or remove if empty
            if new_balance.as_sat() > 0 {
                new_members.insert(from.clone(), new_balance.into());
            } else {
                new_members.remove(from);
            }

            // collect all the payment
            for (address, amt) in payments.iter() {
                spent += Amount::from(*amt);
                all_payments.push(Payment {
                    address: address.clone(),
                    amount: Amount::from(*amt).into(),
                })
            }
            // Check the signature for this request
            // came from this user
            if self.sig_needed {
                let mut hasher = sha256::Hash::engine();
                hasher.write(&self.sequence.to_le_bytes());
                hasher.write(&Amount::from(*fee).as_sat().to_le_bytes());
                for (address, amt) in payments.iter() {
                    hasher.write(&Amount::from(*amt).as_sat().to_le_bytes());
                    hasher.write(address.script_pubkey().as_bytes());
                }
                let h = sha256::Hash::from_engine(hasher);
                let m = Message::from_slice(&h.as_inner()[..]).expect("Correct Size");
                let signed: Vec<u8> = FromHex::from_hex(&hex_der_sig)
                    .map_err(|_| CompilationError::TerminateCompilation)?;
                let sig = Signature::from_der(&signed)
                    .map_err(|_| CompilationError::TerminateCompilation)?;
                let _: () = secp
                    .verify(&m, &sig, &from.key)
                    .map_err(|_| CompilationError::TerminateCompilation)?;
            }
        }
        // Send any leftover funds to a new pool
        let change = NextTxPool {
            members: new_members,
            sequence: self.sequence + 1,
            sig_needed: self.sig_needed,
        };
        // We'll use the contract from our last post to make the state
        // transitions more efficient!
        // Think about what else could be fun here though...
        let out = TreePay {
            participants: all_payments,
            radix: 4,
        };
        ctx.template()
            .add_output(change.total(), &change, None)?
            .add_output(spent, &out, None)?
            .into()
    }
}

Now it’s pretty neat – rather than “exercise for the reader”, we can have Sapio generate payment pool updates for us. And exiting from the pool is very efficient and keeps most users online. But speaking of exercises for the reader, try thinking through these extensions6

No Code: Payout to where?

Payouts in this version are defined as being to an address.

How creative can we get with that? What if the payment request is 1 BTC to address X and we generated X as a 1 BTC expecting Vault in Sapio?

What else cool can we do?

Cut-through

We could make our DoTx differentiate between internal and external payouts. An internal payout would allow for adding a new key OR for increasing the balance of an existing key before other payments are processed. E.g., suppose we have Alice with 1 BTC and Bob with 2, under the code above Alice sending 0.5 to Bob and Bob sending 2.1 to Carol externally would fail and would remove funds from the pool. If we want to keep funds in the pool, we can do that! And if we want the balance from new internal transfers, could process before any deductions.

Internal tranfers to multiple addresses per user can also be used to improve privacy!

Adding Inputs

It should also be possible to have external inputs add balance to the pool during any state update.

Fees?

I basically glance over fees in this presentation… But there is more work to be done to control and process fees fairly!

Cold-er Ejections

If you get kicked out of a pool because you went offline, might you be able to specify – per user – some sort of vault program for the evicted coins to go into?

Howdy Partner

Who is next to whom is actually kinda relevant for a Pool with Efficient Ejections.

For example, if the pool splits because of an undersea cable breaking off France and Britain, dividing users based on English or French would be much better than random because after one transaction you could have all the English and French users split and able to communicate again.

What different heuristics might you group people by? Reputation system? Amount of funds at stake? Random? Sorted lexicographically?

Let’s look at some pictures:

Creating a Pool

Pool Created!

Inspecting the Root

Entering an update

Updated TX Graph

(had a ux bug, need to fix it before I add this :p)

Do Payment Pools Need CTV?

Not necessarily. Payment pools as shown can be done today, but they require participants to use their own emulation / pre-signing servers before depositing funds.

This might not seem bad; we already need everyone online for an update, right? It’s truly not awful. However, many use cases of payment pool essentially require being able to generate a payment pool without having all of the parties online at the time of creation. E.g., imagine that your exchange matches you with reputable payment pool counterparties when you withdraw (if you request it). We’ll see the need concretely in a future post.

What about the Taproots

Unfortunately, rust-bitcoin/miniscript work on Taproot is still ongoing, so I can’t show you how cool Taproot is for this. But essentially, our Self::all_signed clauses become just a single key! And they can be non-interactively generated at every level for the tree-ejection version. This is great! It will work pretty much automatically without changing the user-code once the compiler supports taproot. Huge boon for privacy and efficiency!

Contrast this V.S….

As noted1, there are some other proposals out there.

It’s the author’s opinion that Sapio + CTV are the best form of payment pool compared to alternatives for both scalability and privacy. To fully understand why is a lot more technical than this already technical post (beleive it or not).

If you want to get into it, you can see my accounting for costs on the mailing list:

It boils down to a few things:

  1. Cheaper
  2. Simpler
  3. More Composable
  4. Better Privacy

In posts coming soon we’ll get a heck’n lot more creative with what goes inside a payment pool, including lightning, mining pools, and “daos”! But that’s all for today.

  1. Credit is boring, but I presented the ideas for them originally at SF Bitdevs in May 2019, and Greg Maxwell followed up on the concept more thoroughly in #bitcoin-wizards afterwards. Gleb and Antoine have also been thinking about it recently (under the name Coin Pools – to be honest we’ll have to duke it out since I like the name Coin Pools better than Payment Pool so unclear if it’s going to be like “payment channels” for a variety of designs or “the lightning network”…), as well as AJ/Greg with TLUV 2

  2. Debatably, one could have a protocol where it’s a number of utxos but the core idea is that it should not be 1 user to 1 utxo. 

  3. This implies that no user can block the other users. 

  4. Usually all users, not a subset. But possible to do fewer than all. 

  5. Credit to Greg Maxwell for this description. It’s potent. 

  6. please do try! I think you can :) 

to continue the conversation...

© 2011-2021 Jeremy Rubin. All rights reserved.