Split Tickets & LN Part 1 - MRTTREE

Published 2019-11-11

TL;DR

This proposes a Smart Contract construct tailored to the use case of a group of users which wish to collectively pool their funds into a single utxo and then be able to redeem these funds either cooperatively off-chain via LN or uncooperatively on-chain safely, in a non-custodial way and with the smallest possible impact to the blockchain.

We can achieve this by creating a new opcode, using a series of transactions with scripts inspired by LN Submarine Swaps[3] [4] , Channel Factories[5] [6] and HTLCs[1] and a special service offered by an entity willing to swap funds between the two layers. Please see the full list of works that influenced this design at the end of the post.

MRTTREE construct with full off-chain redemption by users and on-chain settlement in a single transaction by provider.

High Level Overview

Start with the observation that an HTLC preimage can be used as a secp256k1 private key. Along with a multisig Schnorr protocol (MuSig or some other protocol which safely allows key aggregation) we can create smart contracts along with a transaction construct useful in the context of LN that I’m currently calling “Multi-Redeemer Tx Tree” (MRTTREE for funsies :) ).

The main goal for this is to allow multiple independent users that have control of a single utxo via a group key to have the ability to redeem their funds off-chain by allowing a service to take control of the on-chain funds.

A high level overview of the simplest MRTTREE follows.

“Provider” in the following will mean the on-chain coordinator party. It has off-chain outbound bandwidth and wishes to redeem the on-chain funds.

“User” or “Financer”1 is one of the entities claiming ownership to part of the amount held by this on-chain utxo and which wish to reclaim these funds off-chain.

Provider and users coordinate in an interactive protocol to create, publish and wait for confirmation of the MRTTREE root utxo, then proceed to the redeem stage to disburse the funds ideally with all on-chain funds going to the provider in a single new output and the users redeeming theirs via off-chain payments.

The protocol to construct these shared smart contracts will be detailed in a later section. The following is an overview of the resulting scheme.

There is a pre-built (signed) binary tree of transactions which spend from the root utxo. The first transaction (spending the utxo directly) is signed by all participants and creates two outputs, each redeemable with a group key that involves half of the users. Each of these outputs has a pre-built (signed) corresponding transaction which redeems (only) this utxo and creates two other outputs, involving half again of the users.

Repeat for as many levels as needed to get to the transaction creating the leaf nodes.

Complete MRTTREE tree of transactions originally funded by a single output from which each user has a claim to a certain amount.

The leaf utxo is pretty similar to an HTLC in that it’s spendable by presenting a preimage to a given hash. The major trick is that this preimage is also the private key used by the user to sign the previous levels of the transaction tree, such that by presenting the preimage of the hash the user is implicitly conceding to the provider the ability to rewrite the transaction tree and spend the user controlled portion of the original root utxo as the provider sees fit.

The user is willing to provide this preimage as long as the provider pays off-chain. This is done by using an HTLC tied to the same preimage hash and therefore is atomic.

In the ideal case, assuming perfect collaboration of all off-chain parties with the provider, the full utxo can be redeemed by the provider to a provider-controlled p2pkh address in a single on-chain transaction by using all revealed preimages to recreate the private group key and sign a new transaction.

In the case where some of the users fail to collaborate and redeem the funds off-chain, the provider can send the minimum amount of transactions on-chain to redeem his funds; he only needs to send the non-rewritten branches of the original tree of transactions while branches where all users collaborated can be aggregated into the highest possible levels.

Redemption of a few leaf UTXOs off-chain allowing the provider to grab the individual funds.

Redemption of most branches off-chain allowing the provider to rewrite large parts of the transaction tree.

In the case where the provider does not cooperate to a subset of users, they can also redeem the funds on-chain by using the original preimage and their pre-signed branches of the MRTTREE.

The net result is that as much as possible of the original utxo amount is retrieved off-chain reducing the required blockchain congestion while still ensuring all participants have a way to resolve disputes without having to resort to a custodial third party.

After presenting the generalized picture of how to redeem a single on-chain utxo to multiple off-chain actors I’ll proceed to discuss some important points.

Preimage Selection

The first security consideration of the MRTTREE scheme is about ensuring that the preimage used by an untrusted user actually corresponds to the private key required to sign the transaction tree.

In order to ensure that we define a new opcode tentatively called OP_PUBSECP256K1FROMPRIV which pops a value from the stack, assumes it’s a private key, computes the corresponding secp256k1 public key and pushes back the serialized public key (in compressed form) to the stack.

This allows interesting new smart contracts but for our purposes we’ll just require one, based on the following snippet (assuming the preimage is at the top of the stack):

OP_PUBSECP256k1FROMPRIV OP_HASH160 [user-pubkey-hash] OP_EQUALVERIFY

Adding this conditional check in the code paths of the full scripts that redeem using a preimage we can bind the user to only spend using a preimage that is also a private key with a given corresponding public key (hash).

During the construction of the transaction tree and initial root utxo script the provider can ensure that the [user-pubkey] sent by a user is the one used in the group key of the branches where he is present and therefore can guarantee that either the user will redeem the funds (therefore providing the private key) or he himself will be unable to spend them.

Note that this has obvious security considerations related to disclosing a private key, though these are largely applicable to regular HTLC preimages as well.

Another important security aspect is that revealing private keys which were derived on a BIP32 wallet exposes other private keys of the same non-hardened branch for anyone with access to an extended public key (see the original BIP32 spec for more specifics).

One solution to the previous issue is to use private keys tweaked in some deterministic way to allow restoration from seed while still not using an actual BIP32 private key. For example, instead of using a BIP32 private key directly, hash it then use that hash as the private key during construction of the MRTTREE.

Timelocking & Ownership Assurance

In order to prevent the user from doubly redeeming the funds (once off-chain and once on-chain) the leaf scripts need to ensure spending transactions carry appropriate timelocks for different scenarios, using individual keys to identify the redeeming player (either the provider or financer).

In the basic MRTTREE scheme just proposed this would mean that a preimage + [sig with provider-controlled pubkey] can redeem the funds after a timelock of n blocks while a preimage + [sig with user-controlled pubkey] can redeem only after n*2 blocks, such that after revealing the preimage to the provider (and redeeming the funds off-chain) even in the case of some other user sending the transaction tree on-chain the provider will be able to redeem funds before the user has a chance to double spend them.

To incentivize settling off-chain, redeeming via the pre-built tree of transactions should also carry an appropriate timelock so that collaboration from all users is preferred.

When extending the basic MRTTREE to cover other use cases, we must take care around designing appropriate timelocks and ownership to each redeeming branch condition.

Types of MRTTREE

The previous overview describes a Loop In MRTTREE which performs a similar role to the Loop In Submarine Swap: it can refill off-chain channels by having an endpoint consume on-chain coins.

This assumes that the group of users had previously created the group utxo somehow. This can be done either by directly coordinating and funding the single utxo from multiple previous outpoints or by performing the inverse operation: a Loop Out MRTTRRE.

The Loop Out case can swap ownership of on-chain funds from a single owner to a group of off-chain users by creating the MRTTREE Smart Contract as a fallback case if the coordination protocol fails to successfully complete. The end result for this case is the single utxo controllable by the group while the provider receives off-chain funds from them.

This instance needs an additional conditional branch to return unclaimed funds to the provider but it is otherwise very similar to the Loop In.

Individual User Amount Claims

The MRTTREE construction assumes that each user has unique claim to a certain percentage of the original group-controlled funds and that every other user agrees to this claim.

Do note that each individual user only needs to ensure that his own claim is correct, redeemable and protected against incorrect double spend and at least on a first order analysis is indifferent to all other claims.

This means that the resulting leaf utxos can have any amount and as long as the user controlling that amount verifies the correctness of the transaction tree leading up to it, he is satisfied that the conditions to execute the smart contract are correct.

The branches of the tree don’t necessarily need to be balanced in their amounts, however that’s probably a worthy heuristic to pursue.

Privacy Considerations

As a privacy improvement users could coordinate to use same-sized amount “slots”, such that all users redeem a multiple of a single denomination through several off-chain routes.

This helps to obfuscate the total amount controlled by each user and with careful design of a P2P trustless protocol similar to CSPP for coordination even the participating users wouldn’t be able to tell the amount controlled by other parties.

This might unduly increase the tree depth though, and is not necessary to (and in fact might further complicate) illustrating the basic protocol, so I’ll leave the design of this protocol as a future exercise.

Fees and Minimum Amounts

The fees for the on-chain tree of transactions need to be deduced at each level, which means for every additional user more fees will need to (potentially) be paid on-chain.

This serves as an added incentive for off-chain settlement, assuming LN fees remain lower than on-chain relaying fees (which is likely).

It also imposes a hard limit on the minimum amount of participation for each user (given the total number of users) such that every leaf utxo does not drop below the dust amount.

The provider might also elect to charge some fee for the service of providing off-chain settlement of the on-chain funds, which the simplest way to implement is to simply return off-chain a slightly smaller amount than the provider is receiving on-chain.

This promotes cooperation of the provider, since it will be in his best interest to send the funds to the user to receive a larger payout.

Creating the MRTTREE with AMHLs instead of HTLCs

One proposed update to the Lightning Network is to use Anonymous Multi-Hop Locks (AMHLs) instead of the standard LN HTLCs to perform multi-hop payments in a way that prevents the wormhole (fee skipping) attack and that increases privacy by not having a global ID for each payment (the payment hash).

AMHLs work by locking the payment coins into a contract redeemable by a set of group keys. The main feature of these group keys is that, apart from the last one which is the one intended for the final receiver of the payment and can be redeemed individually by him, the ones in intermediate hops are only released in lockstep: the payment on the “left” side of a channel pair can only be retrieved once the node has had its “right” side retrieved by the next party in the multi-hop payment. This is cryptographically ensured by having each party hold an individual key and making each respective “left” side require all previous keys on the “right” side plus the node’s own key.

Overview of the AMHL protocol for locking coins.

In the AMHLs as defined in the original paper the sender of the funds is in full control of the payment release material (private keys). This is in contrast to HTLCs where the receiver generally has the required preimage.

In order to adapt the current MRTTREE creation protocol to AMHLs we’d need to have the receiver also contribute some private material to the group keys unknown to the sender and ensure that this key is the one used in the tree of transactions such that as the receiver redeems the funds, the sender will be able to redeem back on-chain in an atomic way.

Relation to Channel Factories

Channel Factories are a proposed way of increasing LN channel numbers without requiring the creation of a large number of utxos on chain via funding transactions.

They work by requiring a number of participants to fund a single utxo on-chain and then multiple “allocation” transactions can be made, which split the funds between arbitrary pairs of participants, implicitly creating LN channels in the process.

Unilateral closes can be performed by members in case of non-cooperation by sending sets of transactions relevant to them.

The MRTTREE construct was partly inspired by channel factories. The key difference is that the group utxo in the MRTTREE case is not meant to fund new LN channels but rather to perform some on-chain operation (staking in Decred) while allowing complete off-chain redeeming of the funds by swapping them on-chain with a single entity not necessarily present in the original group.

Relation to Submarine Swaps

Submarine Swaps are a way of replenishing inbound or outbound bandwidth of a given channel by atomically swapping those for on-chain funds.

As such, they also influenced the design of the MRTTREE protocol. In fact, a MRTTREE operation can also be seen as a kind of submarine swap (since it’s exchanging on-chan and off-chain funds), except that it’s multiparty instead of two party.

Group Coordination

Note that the MRTTREE construct is only used as a way of ensuring that individual users that claim ownership of part of an utxo can eventually redeem their share even in the face of uncooperative peers.

Group coordination is still needed to spend the funds in some other way. For example, in a crowd funding application, the group might decide (after pooling the funds in a single utxo) to allow a third party to redeem the full funds if some other (blockchain external) condition is met while maintaining the option to redeem the funds if that condition hasn’t been fulfilled yet. Or using a Loop Out MRTTREE a provider will send the on-chain funds to a receiving organization only if all off-chain financers send their contribution.

Other applications may also be developed which require less than complete agreement by the users to spend the funds in some other prescribed way by using a threshold signature scheme and possibly some new not yet thought out scripts. While this is intriguing it is outside the scope of this and the following articles.

Interactive Construction

I’ll now proceed to an explanation of the process to safely construct and redeem the basic (Loop In) MRTTREE off-chain will be explained next. Assume the following:

  • A set of n users (“financers”) collectively control an on-chain utxo via a multisig n-of-n Schnorr group key. Each has a claim for some % amount of this utxo and has off-chain inbound bandwidth greater than this amount.

  • A “provider” has off-chain outbound bandwidth available across many channels, greater than the amount of on-chain funds.

  • Provider and users can communicate using a specific service ran by the provider.

We’ll now construct a MRTTREE that will move control of the on-chain funds from the provider to the group of users.

The process is as follows:

  • Users send the pubkeys that will be used to redeem funds and hash of the private key associated with that pubkey. Users also send their individual redeeming pubkey hash. Provider selects key pairs itself will use.

  • Provider assembles the group key using one key from each user and one from itself.

  • Provider prepares the root utxo pkscript which requires a group sig to redeem.

  • Provider prepares the tree of transactions (including the script for each intermediate and leaf utxo).

  • Provider partially signs each transaction.

  • Provider prepares the funding transaction which will spend from the user group controlled original utxo paying all funds directly to the root MRTTREE utxo.

  • Provider sends the transactions to users. Each user independently verifies that their desired funds are there, redeemable by presenting the original private key (as a preimage) and a signature by their individual key. Each user also independently verifies all transactions of the tree are otherwise valid. After verification, user signs all transactions in the tree and sends their signatures to provider.

  • Provider assembles all partial signatures into final signature scripts and sends those to users.

  • Users verify all signatures actually correctly redeem the transactions and all other conditions are met such that their individual funds can eventually be redeemed.

  • Users store the transaction tree, partially sign the funding transaction and send the signature back to the provider.

  • After the provider receives partial funding sigs from all users he combines them and publishes the funding transaction to the global blockchain mempool.

  • Participants wait a given number of confirmations of the funding transaction. At this stage different players might elect to wait different confirmation heights - even down to zero - depending on the absolute amount at stake, their trust level to the others and risk aversion.

  • Each user creates an invoice for their corresponding amount, tied to the same preimage hash of the first step (i.e. their private key used in the group key) and send it to the provider.

  • Provider begins the payment process by adding HTLCs routed to each user.

  • Users redeem the off-chain funds by presenting the preimage. Preimage flows through the payment route to the provider.

  • For every group of users of a given branch at a given level of the tree that has sent their preimages, the provider can rewrite that branch to redeem the full funds to a different address under its control. At the limit where all users have sent preimages, all funds are redeemable by a single transaction.

  • Before the timelock of the tree of transactions expires (making it spendable) the provider publishes all relevant (non rewritten) levels of the tree if there are any left, then sends the highest rewritten level of the tree then redeems any leaf utxos that remain for which is has preimages. Uncooperative off-chain users are free to redeem the on-chain funds at any point in the future without any further cooperation.

At the end of this process each cooperative individual user has redeemed their funds off-chain and the provider has grabbed as much as possible of the on-chain funds in as few transactions as possible.

Final Discussion

The MRTTREE Smart Contract construction is pretty interesting and useful by itself whenever a group of independent and untrusted users want to aggregate on-chain funds while maintaining a way for each independent entity to redeem its share.

When initially assembling and in every future fund movement the group coordinates such that there’s always a redeem path via the tree of transactions, ensuring any situation that causes any member to become uncooperative (either maliciously or fortuitously) doesn’t cause the utxo to be irredimably locked. As long as all state transitions agreed by the group include this path, each individual user is secure it can eventually receive its share back.

The existence of the Lightning Network as a second layer solution means we can now create a novel way to redeem the funds while decreasing the on-chain footprint. The only requirement is the creation of a new opcode that can ensure correctness of the preimage, binding the keypair used to a corresponding payment hash.

This construction will be used in split ticket sessions to allow building the utxo to fund the ticket and then to redeem the funds after a vote or revocation is issued. However this mechanism still requires a large degree of cooperation which ideally we’d want to reduce as much as possible. These will be the topics for the next post.

References & Bibliography

[1]

Poon, Joseph, and Thaddeus Dryja. “The bitcoin lightning network: Scalable off-chain instant payments.” (2016). Available at https://www.bitcoinlightning.com/wp-content/uploads/2018/03/lightning-network-paper.pdf

[2]

Fromknecht, Conner. “Connecting Blockchains: Instant Cross-Chain Transactions On Lightning” (2017). Available at https://blog.lightning.engineering/announcement/2017/11/16/ln-swap.html

[3]

Bosworth, Alex. “Submarine Swaps Github Repository” (2019). Available at https://github.com/submarineswaps/swaps-service

[4]

Lightning Labs. “Lightning Loop Github Repository” (2019). Available at https://github.com/lightninglabs/loop

[5]

Burchert, Conrad, Christian Decker, and Roger Wattenhofer. “Scalable funding of Bitcoin micropayment channel networks.” Royal Society open science 5, no. 8 (2018): 180089. Available at https://royalsocietypublishing.org/doi/pdf/10.1098/rsos.180089

[6]

Decker, Christian, and Roger Wattenhofer. “A fast and scalable payment network with bitcoin duplex micropayment channels.” In Symposium on Self-Stabilizing Systems, pp. 3-18. Springer, Cham, 2015. Available at http://people.cs.georgetown.edu/~cnewport/teaching/cosc841-spring19/papers/new/micropayment-channels-1.pdf

[7]

Decker, Christian, Rusty Russell, and Olaoluwa Osuntokun. “eltoo: A simple layer2 protocol for bitcoin.” White paper: https://blockstream.com/eltoo.pdf (2018).

Notes

[1]

“Financer” doesn’t make a lot of sense as far as naming goes on the basic Loop In MRTTREE but will become a useful distinction when discussing the mechanisms to construct split tickets - they are the ones funding the whole operation.


Comments