Skip to content

Instantly share code, notes, and snippets.

@jcnelson
Last active Jan 16, 2022
Embed
What would you like to do?
Subnets

Disclaimer: I'm trying to flesh out a system that has only been described at a very high level. The purpose of this document is to write down notes on how I currently and tentatively believe subnets will work. This document is not authoritative, and may be significantly revised or even deleted.

All the credit for this approach goes to Aaron Blankstein. This document is based off of a conversation I had with him. I'm merely filling in the gaps.

What do we know about Subnets?

From what I've been able to gather, a Stacks subnet is shaping up to be a system that, at a high level, makes a lot of similar guarantees to sidechains and drivechains. It has the following properties:

  • Closed-membership: system liveness is driven by a whitelisted set of network participants.

  • Instant finality: Once a transaction is sent and applied to the subnet state, it stays applied.

  • 2-way peg: State on the subnet originates from state on the Stacks chain, and evolves on the subnet through subnet-specific transactions. But eventually, the state on the subnet re-materializes on the Stacks blockchain.

However, they're neither drivechains or sidechains because they operate under a totally different incentive model, which I outline below. In fact, they're not even blockchains.

What makes a Subnet tick?

What I suspect subnets will look like instead is a "super Lightning channel," inspired by Bitcoin's Lightning protocol:

  1. A set of users lock up their assets on Stacks in order to materialize them on the subnet.
  2. Subnet nodes begin relaying and processing off-chain trades between these users.
  3. Eventually, the subnet terminates; at which point, the final state of the subnet is applied to the state of its users' on-chain accounts as one large state-transition.

Crucially, users drive forward progress on this system, since they are the only party here with a financial incentive to do so. I do not believe that subnets wiill have their own native token (if they did, they'd be appchains), which precludes having subnets driven by Stacks miners or independent block producers (coincidentally, this observation is what makes Stacks different from a sidechain). The only remaining party to run the subnet are the users themselves. This is why I think of a subnet as a "super Lightning channel," since like Lightning, liveness is incentivized solely by users wanting to settle their latest account states on-chain.

How would Subnets work?

I don't think subnets will end up looking like blockchains at all. Under the hood, the constraints subnets operate under will give them the following unique properties that make them somewhat different from blockchains:

  • Only token state gets transferred to and from a subnet. Moving state to and from a subnet is expensive, since each "movement" requires sending a per-user Stacks transaction to modify the copy of that state on the Stacks blockchain (i.e. to lock it into the subnet, and to sync it with the state of the subnet). Therefore, it's important that the amount of data that needs to be moved per user is (a) constant, (b) known in advance, (c) smaller than the block limit (otherwise, users couldn't exit), and (d) explicitly owned by and financially valuable to users. Realistically, this means that only user-owned state of known size -- i.e. tokens on the Stacks chain -- will get transferred to and from subnets. It might be sufficient to implement subnets to only handle tokens.

  • Users can only interact with other subnet users. In order for a user to be able to exit a subnet, a user first must have explicitly joined it, even if they have no tokens initially. This is required to incentivize liveness -- it's for the same reason why Lightning channels have both a sender and receiver setup. If the user receives tokens within the subnet's execution, then they are incentivized to make sure their final token balances get written to the Stacks chain when the subnet terminates. But in order to make it possible for all users to be able to do this in a bound amount of time and space (i.e. to guarantee that the subnet actually does terminate), the system must know in advance who all the senders and receivers are.

The reason for both of these constraints is that the technical purpose of a subnet is to calculate a single "patch" against the Stacks state trie. This "patch" is simply the set of leaves and affected intermediate nodes in the trie that represent the cumulative token movements between all subnet users, but without the intermediate states. For example, if Alice sends Bob 1 STX 10 times, then the resulting "patch" only needs to reflect that Alice's STX balance is 10 STX lower and Bob's is 10 STX higher -- it doesn't need to reflect the intermediate facts that Alice's account from -1, -2, -3, etc. STX while Bob's went from +1, +2, +3, etc. This is what makes subnets an attractive scaling solution -- they have the potential to "compress" an unbound number of account changes (i.e. off-chain trades between users) into bound number of account changes (at most one change per token type per user). But to do this, the system must ensure that the size of the resulting "patch" cannot grow unbound -- mutating and storing state isn't free, so its maximum possible size must capped by both the number of participating users and the number of different types of tokens they bring with them to the subnet. Moreover, to ensure fairness, each user would pay for their "fair share" of the patch to move their own tokens on and off the subnet.

Subnet Operation

Subnet operation is handled by a smart contract on the Stacks chain that acts as an escrow for all tokens moved to the subnet. Users enter the subnet by sending their tokens to this smart contract, which holds onto them for the duration of the subnet's lifetime. Once the subnet terminates, users exit by proving that they have new balances thanks to trades they made on the subnet. They do so by submitting a "receipt" to the subnet operation smart contract that gives them the right to claim some of the tokens it holds. Each user's receipt reflects the final state of their token balances, after the subnet's execution terminates.

What would this receipt look like? I suppose this could look like a "vector-clocked Merkle tree." This is a Merkle tree with two sub-trees: one that represents all of the user accounts' token balances and nonces and signatures over them, and one that represents only the user accounts' nonces (note that the nonces are committed to in two places; more on this below). Here, the nonces form a vector clock. The root hash of a vector-clocked Merkle tree is just the hash of the roots of these two sub-trees. I'll assume that both sub-trees' leaves are totally ordered -- e.g. lexicographically by the owning account's address or similar -- so it's unambiguous how to build one.

The act of executing a trade between N users is the act of those users (a) updating their accounts' leaf nodes with the new nonces, balances, and signatures in the accounts subtree; (b) updating their respective nones in the nonces subtree, and (c) releasing an N-of-N-signed root hash from the resulting vector-clocked Merkle tree. The act of validating a trade is the act of doing the following:

  • verifying that the total number of tokens across all users has not changed and that all balances are positive (i.e. the tree is well-formed);
  • verifying the signatures on the root hash are valid and come from participating users;
  • verifying that the same users also signed off on their individual account leaves;
  • verifying that the authenticated accounts' nonces match the vector clock subtree;
  • verifying that the nonces of each affected user incremented by 1 when the trade was executed.

Each user maintains a copy of the vector-clocked Merkle tree through a gossip network. A trading set of N users can broadcast only the deltas (i.e. leaves and Merkle proofs) that encode the changes their N-way trade makes to the tree, and all users with a full tree will be able apply the delta to recover the updated tree that reflects the sequence of trades carried out. Users rely on the vector clock to determine the causal order in which deltas get applied -- i.e. the vector-clocked Merkle tree is a CRDT. Users recovering from a network partition can simply request the sequence of deltas that transform their last-seen tree into the latest tree seen by their peers.

This vector-clocked Merkle tree representation is designed to make it so that (1) users can prove that they were party to a given trade, and that (2) each trade commits to all its causally-dependant trades. It achieves (1) by verifying that the signatures on the Merkle root match the signature on the affected accounts. It achieves (2) by ensuring that each time a trade occurs, the nonce for each participant gets incremented and signed, and that the tree remains well-formed before and after applying the sequence of trades prior to the given trade.

Subnet Exits

Exiting a subnet is a two-phase operation. In the first phase, users agree on the latest vector-clocked Merkle tree root and vector clock. In the second phase, users withdraw their due tokens using the Merkle root to prove the validity of their withdrawals.

In the first phase, each user has the opportunity to write a signed Merkle tree root and associated vector clock to the escrow contract. It can be any such Merkle tree root and vector clock from the subnet's execution; because users execute a subnet to carry out trades, users are financially incentivized to write the latest such root and vector clock. A user would do this to prove the existence of a trade they were party to (and thus all causally-dependant trades that preceded it), in order to prove that they have the right to withdraw the tokens allotted to them in the corresponding Merkle tree. Because all participating users in an N-way trade sign off on the state of the Merkle tree once the trade completes, only one participant from that N-way trade needs to write the Merkle root and vector clock on N participants' behalfs.

The smart contract (1) assigns each user a "latest" Merkle root and vector clock (i.e. once someone submits a Merkle root with their signature), and (2) ensures that a user's "latest" Merkle root and vector clock can only be updated if a causally-later Merkle root and vector clock are submitted. Note that different users can have different "latest" Merkle roots and vector clocks; what matters is that the set of distinct Merkle roots represent Merkle trees that are not in conflict and can be merged. For example, this would let the system handle a plausible subnet execution where Alice and Bob only trade with one another, and Charlie and Danielle only trade with one another, but neither pair sees each other's trades (i.e. Alice and Bob's trades are not causally linked to Charlie and Danielle's trades). Alice could submit a Merkle root and vector clock that reflects her and Bob's activity, and Charlie could submit a different Merkle root and vector clock that reflects his and Danielle's activity, and despite the difference, all four users would be able to withdraw their tokens in the second phase because the two trees' vector clocks (and account Merkle subtrees) are not in conflict.

In the second phase, each user submits a Merkle proof off of their latest-such vector-clocked Merkle tree root from phase 1 to withdraw their due tokens. They prove that their account nonce and signature are consistent with both the root hash and the vector clock submitted in phase 1. If all goes well, then each user can claim what they are owed, and each user will submit only the branches of the Merkle tree for their own tokens and account state (thereby incrementally applying the Merkle tree patch against the Stacks state trie). In doing so, the act of all users exiting in phase 2 merges any distinct Merkle trees together into the final "patch" against the Stacks state trie.

Subnet Safety

The fact that each user signs the Merkle root of the tree at the end of each trade means that they commit to the vector clock state as well as their contract state. A malicious user cannot forge the signature of another user, and so thus cannot submit a vector clock or Merkle tree root that another user didn't sign. A malicious user can omit one or more signatures, but the omitted users can simply submit their signatures to the same Merkle root separately during phase 1 (thereby proving that they were also party to the trade).

If a malicious user attempts to double-spend, then it will get caught by the smart contract when or before the user tries to exit, because the resulting two Merkle tree roots and vector clocks will show that the malicious user had a write/write conflict. To disincentivize double-spending, the smart contract would use the proof of a write/write conflict to slash that user's tokens, and allot a commission to the (other) user that reported the proof. Anyone could submit a proof of a write/write conflict at any time during the subnet's lifetime, so any cascading effects of a subnet double-spend would be mitigated early. The act of proving write/write conflict in the subnet operation smart contract would also resolve the write/write conflict, permitting trades to continue (i.e. it sets the balances of all tokens of the offending user to 0 in the Merkle tree).

Future Work

All of the above is tentative. I'm writing this mainly to get my own thoughts in order, so others can review them. I have no roadmap or ETA for building subnets; my focus right now is on the appchains scaling solution. However, that shouldn't stop an ambitious Stacks developer from getting this off the ground ;)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment