Write UTXO-based Susbtrate Runtimes

Off-Narrative Labs

Last update: Mar 19, 2023

Related tags

Overview

Tuxedo

Write UTXO-based Substrate Runtimes

Architecture
Repository Contents
Funding and Roadmap
Building and Running Locally
Docker
Testing and Code Quality
License

Architecture

Tuxedo is a framework for developing Substrate runtimes with the UTXO model.

In the standard UTXO model each transaction provides some inputs that represent pieces of current state to be consumed, and provides some outputs which are new pieces of state to be added to the UTXO set. The chain logic then checks that the input and output sets satisfy some constraints. For example, the input coins must have value greater or equal to the output coins. Tuxedo generalizes this model slightly in two ways. First, by adding a notion of peeks, which are pieces of state to be read only, and not modified or consumed. This reduces the frequency with with transactions race for particular UTXOs. Second, by abstracting the notion of checking a transactions so that runtime developers can plug in their own custom "Tuxedo Pieces" or use some from a standard library. Rather than being constrained to build only a cryptocurrency, developers can build proof of stake, governance, NFT games or anything else they choose.

Tuxedo makes the process of developing UTXO-based runtimes faster and safer by freeing developers from having to re-implement all of the common and error-prone UTXO logic in each chain. It also makes the process more standard by providing developers with simple interfaces for their Tuxedo Pieces. When developing a Tuxedo piece, a developer will complete some or all of these following tasks.

Declaring Data Types

If the Tuxedo piece has any custom data types, they must be declared by implementing the UtxoData trait. For example, a crytpocurrency may have a data type called Coin or a voting solution may have data types called Poll and Vote. The developer only has to declare the data type; there is no notion of a "storage item" because there is no global state in the UTXO model. All state is local to individual UTXOs.

Defining Transaction Constraints

All Tuxedo pieces will define one or more sets of constraints that a transaction must satisfy to be valid. This is done through a ConstraintChecker trait. Unlike the accounts model, the Tuxedo piece is not responsible for calculating the final state after the transaction. Rather, the final state is passed in as the transaction's output set. The piece only checks that the appropriate constraints are met. For example, it may check that in an on-chain chess game, the input piece really is allowed to move to the location specified in the output. In a more classic example, it will check that the tokens being spent are of greater or equal value to the tokens being created.

Declaring Verification Logic

Each individual UTXO in the UTXO set is protected by a piece of associated logic that determines when it may be spent. This logic is defined in the Verifier Trait. The most classic example is that the UTXO is owned by a particular public key and the transaction must be signed by that key in order to unlock the input. Other examples also exist, such as, the UTXO may be claimable by anyone, or by nobody at all, or it may require a valid proof or work to be consumed.

Tuxedo core provides the most common verification logic already, so it is uncommon that individual pieces need to add custom verification logic, but the possibility exists none-the-less.

Note on Unit Testing

A Tuxedo piece should be thoroughly unit tests, like any quality piece of software. It is worth noting that, because all state is local to UTXOs and there are no global storage items, the unit tests can be much simpler than a typical account-based Substrate runtime. It is not even necessary to uses storage externalities when testing Tuxedo pieces because Tuxedo core handles all of the storage access itself. The piece developers only have to focus on the actual constraint-checking logic.

Repository Contents

This mono-repo contains the core Tuxedo code as well as an example node built with Tuxedo and a proof-of-concept wallet to transfer tokens.

Tuxedo Core

The reusable core of the Tuxedo framework lives in the tuxedo-core directory. This crate will be used by every runtime built with Tuxedo. The best way to explore this crate is by browsing its code or its hosted rustdocs. It contains:

The core data types for the UTXO model such as Input, Output, OutputRef, Transaction, and others.
A standard interface for developers to access the UTXO set.
Common transaction validation logic that all UTXO transactions need to conduct.
A dynamic typing system to allow developers to store bespoke data types in the UTXO set in a type-safe manner,
Public interfaces for developers to implement while writing their own Tuxedo pieces.

Template Runtime

There is an example runtime built with Tuxedo in the tuxedo-template-runtime directory. This runtime is analogous to the popular Substrate node template runtime, but it uses Tuxedo and the UTXO model rather than the accounts model. Developers wanting to build with Tuxedo should inspect this example runtime to get familiar with how to use Tuxedo, and then fork it to begin developing their own runtime.

The best way to explore this runtime is by browsing its code or its hosted rustdocs

Template Node

There is an example node built with the Tuxedo template runtime. Because Tuxedo is primarily a runtime development framework, there is not much interesting or unique to Tuxedo to see in this crate. It is mostly a copy from the popular Substrate node template.

Wallet

The repo contains a proof-of-concept wallet in the wallet directory. This wallet will be expanded to be a fully-featured usable cryptocurrency wallet over the next few weeks (see the roadmap below). For now, the PoC is enough to demonstrate that transferring tokens works.

Funding and Roadmap

Special thanks to the Web 3 Foundation for their support of Tuxedo through their grants program.

As part of this grant we will deliver three milestones. More details are available in the Tuxedo grant application.

✅ Core Tuxedo Functionality (complete)
🏗️ User wallet (in development)
🔜 Full Documentation and Tutorial (not yet started)

After the grant work is complete we intend to continue developing Tuxedo. The future is less clear, but our current ideas include:

🔮 Cumulus and Parachain support including cross-chain UTXOs
🔮 Zero-knowledge runtimes a-la zero-cash and zexe
🔮 UTXO-native Smart Contracts based on the pi-calculus

Building and Running Locally

First you'll need to have a working Rust and Substrate development environment. Then you can build Tuxedo like any other Rust project

# Clone to repository
git clone https://github.com/Off-Narrative-Labs/Tuxedo
cd tuxedo

# Build the node
cargo build --release -p node-template

# Build the wallet
cargo build --release -p tuxedo-template-wallet

Once you have the node and wallet built, you can run a development node.

# Check out the CLI if you want to
# It supports all standard Substrate CLI options
./target/release/node-template --help

# Start a development node
./target/release/node-template --dev

Then, in a separate terminal, experiment with the PoC wallet.

# Check out the minimal PoC CLI
./target/release/tuxedo-template-wallet --help

# Confirm that a 100 token genesis utxo is present in storage
./target/release/tuxedo-template-wallet verify-coin 000000000000000000000000000000000000000000000000000000000000000000000000

  000000000000000000000000000000000000000000000000000000000000000000000000:
    Found coin worth 100 units owned by 0xd2bf4b844dfefd6772a8843e669f943408966a977e3ae2af1dd78e0f55f4df67

# Split the 100 tokens into two of values 20 and 25, burning the remaining 5
./target/release/tuxedo-template-wallet spend-coins \
  --input 000000000000000000000000000000000000000000000000000000000000000000000000 \
  --output-amount 20 \
  --output-amount 25

  f15c546f47b2447ecebc7327e7670ee3e600cbebd3eb529549a585066c38fe1400000000:
    Found coin worth 20 units owned by 0xd2bf4b844dfefd6772a8843e669f943408966a977e3ae2af1dd78e0f55f4df67
  f15c546f47b2447ecebc7327e7670ee3e600cbebd3eb529549a585066c38fe1401000000:
    Found coin worth 25 units owned by 0xd2bf4b844dfefd6772a8843e669f943408966a977e3ae2af1dd78e0f55f4df67


# Further split the 25 token utxo into 10 and 5, burning the remaining 10
./target/release/tuxedo-template-wallet spend-coins \
  --input f15c546f47b2447ecebc7327e7670ee3e600cbebd3eb529549a585066c38fe1401000000 \
  --output-amount 10 \
  --output-amount 5

  06fa6e2a1875ee6cab54e863a244bf2577dba8061782c20411f49168e0a18a9300000000:
    Found coin worth 10 units owned by 0xd2bf4b844dfefd6772a8843e669f943408966a977e3ae2af1dd78e0f55f4df67
  06fa6e2a1875ee6cab54e863a244bf2577dba8061782c20411f49168e0a18a9301000000:
    Found coin worth 5 units owned by 0xd2bf4b844dfefd6772a8843e669f943408966a977e3ae2af1dd78e0f55f4df67

# Join the 20 token utxo and 10 token utxo back into a single 30 token utxo, burning nothing
./target/release/tuxedo-template-wallet spend-coins \
  --input f15c546f47b2447ecebc7327e7670ee3e600cbebd3eb529549a585066c38fe1400000000 \
  --input 06fa6e2a1875ee6cab54e863a244bf2577dba8061782c20411f49168e0a18a9300000000 \
  --output-amount 30

  f8ee7f42d81b749223da7a49838df414aef6f4343da59bc4798335d67886f13000000000:
    Found coin worth 30 units owned by 0xd2bf4b844dfefd6772a8843e669f943408966a977e3ae2af1dd78e0f55f4df67

Docker

Developers and curious individuals who want to quickly try out Tuxedo and its template runtime can save the setup and compile time by using docker. CI publishes Docker images for both the example node and the PoC wallet at https://github.com/orgs/Off-Narrative-Labs/packages.

Docker is a complex software and there are many ways to pull and run images and map host ports to container ports. For those not already familiar with Docker, you may benefit from referencing the docker documentation or building and running locally instead.

The following commands are meant as a quickstart that will work on most platforms for users who already have Docker setup.

# Run a development node with Docker
docker run --network host ghcr.io/off-narrative-labs/tuxedo --dev

# In a separate terminal, explore the PoC wallet's CLI
docker run --network host ghcr.io/off-narrative-labs/tuxedo-wallet --help

# Use the PoC wallet to confirm that a 100 token genesis utxo is present in storage
docker run --network host ghcr.io/off-narrative-labs/tuxedo-wallet verify-coin 000000000000000000000000000000000000000000000000000000000000000000000000

  000000000000000000000000000000000000000000000000000000000000000000000000:
    Found coin worth 100 units owned by 0xd2bf4b844dfefd6772a8843e669f943408966a977e3ae2af1dd78e0f55f4df67

More example commands are listed above in the section on running locally. They all work with docker as well.

Testing and Code Quality

Tuxedo strives for excellent code quality which is enforced through unit tests, and clippy linting. Both of these are enforced in the CI, which you are free to inspect. You may also run them locally.

# Run unit tests on all aspects of the project
cargo test

# Run clippy (which requires nightly)
cargo +nightly clippy

License

Apache 2.0

Comments

Reconsider the strong `Redeemer` / `Verifier` separation
In the current design, Tuxedo has a very strong separation between the logic that allows a single input to be consumed and the logic that checks whether a transaction is valid. This issue is to consider the pros and cons of that separation and decide to what extent it should be kept.

Note on Terminology

Before going on, I'll observe that I accidentally used the same terms as IOHK's abstract model with different meanings :facepalm:

| Tuxedo Term | Abstract Model Term | Definition | | ----------- | ------------------- | ---------- | | Verifier | None - token logic hard coded | The logic used to determine whether the consumed inputs and created outputs meet all necessary constraints | | Redeemer | Verifier | The logic used to determine whether an individual input can be consumed | | Witness | Redeemer | The data, likely a signature, that satisfies the logic to consume an input

Arguments for the strong separation

Pro 1: Writing pieces is very simple

With the current separation in place, the author of a piece doesn't need to care anything about whether individual inputs can be consumed. This is entirely handled by tuxedo executive. By the time the execution reaches the individual piece all that is left is typed data for the piece to check.

Arguments against the strong separation

Con 1: Pieces can't forcefully consume inputs

In some cases it is useful to consume a UTXO for housekeeping purposes.

Example 1: Consider a coupon with an expiration date. This UTXO would likely be guarded by a CheckSig so only the owner can use it. But if the expiration date passes, anyone should be able to clean up the state.

Example 2: In the proof of existence piece, two users could claim the same hash. When these competing claims are discovered anyone should be able to clean up the latter claim because the former is more legitimate. This is encountered in the current codebase

This can be addressed with a notion of evictions. See below.

Con 2: Dynamic ownership is not immediately intuitive

In FRAME, pallet sudo is commonly used to guard functionality behind a signature by the sudo key. This is similar to hoe SigCheck works except that the key is dynamic. In Tuxedo this cannot be implemented as a redeemer because the sudo key is stored in state (a utxo) but redeemers do not have access to other state.

This could also be solved with evictions. (Again, see below).

Con 3: Paying a private user

In many cases, a Tuxedo piece may want to pay assets to a specific private user. Consider a a treasury that wants to make a payment to a user, or a NFT game that charges some fees and allocates them to the original developer. When the output redeemers are not available, this cannot be done.

Possible Design Changes

Evictions

The idea of evictions is to add a field to the transaction that is similar to inputs or peeks (see #16), but the evicted inputs will be consumed regardless of whether their redeemer is satisfied. They will be forcefully removed.

This solves Con 1 by allowing anyone to call, for example, a CleanupExpiredCoupon verifier or a ResolvePoeDispute verifier which will forcefully remove the outdated state.

This also solves Con 2 with a little creative design. For an output that is intended to only be spent by root, make the redeemer NobodyCanEverSpend, then write a SpendByRoot that verifier evicts it as long as the payload to the verifier contains a signature by the sudo key.

Pass full outputs to verifier

Another alternative is to change the interface so that entire Outputs, including the redeemer, are passed to the verifiers. This solves Con 3 but has the disadvantage that the Verifier must now know which redeemers are available to the aggregate runtime.

Pass full transaction to verifier

We could weaken the separation even more by passing the entire transaction to the verifier. This has the all of the disadvantages of passing just the full outputs. It also has the disadvantage that it is the verifiers responsibility to check the redeemers. It has the advantage that evictions are no longer necessary because any verifier can simply choose to ignore the redeemer.

Both of the above

It may be possible, to expose all of these APIs to piece developers, letting them choose which to implement. Pieces that can get by with a simple API can use it, and ones that require more powerful but more complex and dangerous APIs can use them. This may be possible with blanket implementations. Something like.

trait SimpleVerifier { // --snip-- } trait PowerfulVerifier { // --snip-- } impl<T: SimpleVerifier> PowerfulVerifier for T { // --snip-- }
opened by JoshOrndorff 7
Adding new simple verifier for decoupling
This is the start of the migration to a new simple verifier as discussed in #27 this includes the following tasks:

[x] migrate old verifiers to new SimpleVerifier trait.

[x] update Executive logic

[x] Migrate old tests and old code depending old verifier logic
opened by coax1d 2
Test tuxedo core

This PR adds significant test coverage to the tuxedo-core crate.

I hope to achieve 100% according to cargo tarpaulin, but I'm not sure how practical that is. In any case, this will add enough coverage to give tuxedo users peace of mind that the core code is working as expected.

opened by JoshOrndorff 2
Duplicate output check is unnecessary and incorrect

Currently the tuxedo executive checks that there are no duplicate outputs in a given transaction. https://github.com/Off-Narrative-Labs/Tuxedo/blob/main/tuxedo-core/src/executive.rs#L53-L60

This logic is also present in the earlier utxo workshop. https://github.com/JoshOrndorff/utxo-workshop/blob/joshy-update-deps-may-2022/runtime/src/utxo.rs#L188-L191

But why is it necessary? It is perfectly valid for a transaction to consume a 20 token input and create two new outputs each worth 5 tokens that belong to the same pubkey.

Digging back through the git history, it seems this check has been present since a much older 2019 edition of the utxo-workshop where each output contained a user-provided salt. The user-provided salt was never realistic and was a hack to get something working in the early days. @nczhu noticed this and solved it in https://github.com/substrate-developer-hub/utxo-workshop/pull/45 (still an impressive PR after all this time!).

With the salt hack long-gone, I think it is safe to remove the duplicate output check.

opened by JoshOrndorff 2
Initial wallet for sending coins
Wallet for basics should:

[ ] Spend coins from Alice's genesis coin

[ ] Specify the output address and amounts for the outputs

[ ] check state and see the new coins
opened by coax1d 2
CI: Caching

This PR strives to add caching to the CI. I've just blindly installed the action which supposedly has "sensible defaults". Let's see whether it reduced CI time.

opened by JoshOrndorff 2
Tests for executive

Most of tuxedo executive needs better test coverage. Although we have some end-to-end testing through the wallet, and we have pretty good test coverage on the redeemers, we still need unit tests for the transaction checking and storage updating logic.

opened by JoshOrndorff 1
Spaces or Tabs
Yep, this is seriously the first issue on the repo :rocket:

I don't want to dive into the long history of which is fundamentally better. Because the answer is "neither; they're both fine; stop fussing about it and get back to coding". I just want to decide what is better in the context of this project in the Substrate ecosystem.

In #11 I added some CI, but cargo fmt is currently disabled because we have a combination of tabs and spaces and need to decide.

In favor of tabs

This is what the rest of the Substrate ecosystem uses, because this is what Gavin likes. Following suit will make it easier to merge changes from the upstream node template.

In favor of spaces

This is the default for cargo fmt and sticking with the default means we don't need to have a config file for cargo fmt. The repo is slightly simpler.

Tabs are used in the rest of the Substrate ecosystem because Gavin likes them. And we are Off Narrative Labs :rofl:
opened by JoshOrndorff 1
Cleanup and explain consensus authority sets

Tuxedo does not yet have any real PoS- or even PoA- style authority set management pieces. So for now we use simple hard-coded authority sets.

This PR improves this situation slightly by making all of the standard (Alice, Bob, Charlie, etc) keys readily available and providing comments explaining that that's what is happening.

opened by JoshOrndorff 1
Amoeba tests

This PR primarily adds tests for the amoeba example piece. It also fixes one small error that the tests found.

And finally, it moves the Bogus type from the money piece to a reusable location in the tuxedo core crate so that it can be used in tests for all pieces.

opened by JoshOrndorff 1
Proposed Main

This work combines the ideas from #1 and #2 to establish a tuxedo core as well as an example node that includes several pieces.

This should NOT be squashed because we want to keep all the history. In fact, if we agree to it, we should just push it to main with the cli rather than using the github ui.

opened by JoshOrndorff 1
Implement Peeks

This PR adds the peek functionality for reading state without consuming it as described in the original grant proposal.

This will help facilitate concurrency down the road. Even before that, it makes it nice that you can read state without re-writing it and therefore changing its OutputRef.

opened by JoshOrndorff 0
Wallet: Store local database of UTXOs

Currently the wallet requires the user to manually remember what OutputRef's belong to them. A real wallet will maintain a local database of UTXOs belonging to the keys in its keystore.

General Syncing Strategy

The wallet will need to scan the blockchain and check each transaction to see if any new outputs are available for any of the keys it controls (or more generally, if it knows how to produce a redeemer that satisfies the corresponding validator). This process is kind of roughly described in https://bitcoin.stackexchange.com/q/75840

To sync, we could add a subcommand Sync. When given this command, the wallet will look up the last block to which it synced from the filesystem, and query the node for all blocks from there to the tip, noting any new UTXOs along the way.

New Keys

When a new key is added, the user should specify from which block the wallet should resync. If no block is provided no resyncing happens. This is what a user would want when inserting never-before-used keys which couldn't have any possible existing UTXOs.

If the key has been used before and is just being restored to this wallet, the wallet will query the node for all blocks starting at the block the user provides (possibly genesis) to check for owned utxos.

Manually specifying owned UTXOs

We could consider letting the user skip the syncing, and instead manually specify the UTXOs that they already know are relevant. Maybe they are exported from another wallet. Although this may be premature optimization.

Storage Optimization

Users may choose to delete keys at any time. When this happens the wallet should also prune the now-useless database of UTXOs owned by the deleted keys. To make this operation performant, the wallet should store the database on a per-key basis.

Forks and Reorgs

We have to handle the reality of re-orgs. If the wallet syncs its local database to the tip of the chain, and then a few blocks are orphaned, the wallet will have inconsistent data. I haven't fully thought this through yet.

One strategy would be to rely on finality. But not all chains provide finality, and even when finality is available, this may lead to an unacceptable lag for the user.

Another strategy is to keep the local database stored on a per-block basis so that the wallet can actually revert the affected portion easily. When starting a sync, the wallet would query the node to see if its best known block is currently canonical. If so great, just do a linear sync. If not, find a common ancestor, revert local state after the fork block, and then do a linear resync. We'll have to see what RPCs the node provides to make this possible. There may also be some hints in Polkadot JS for a good strategy.

opened by JoshOrndorff 0
Test the wallet CLI

There is now a good amount of code in the wallet, and it will continue to grow. It needs to be tested in an automated way.

I'm not exactly sure how to test CLI app code. This wallet interacts with user input, a filesystem, and a running node via RPC connection. That seems harder to test than simple functions.

opened by JoshOrndorff 0
Integrate Keystore into wallet
This PR uses the Substrate keystore for key management in the wallet. This allows users to insert existing keys and generate new keys that will be persisted on disk between sessions. It also allows constructing transactions with inputs belonging to different public keys (and inputs that are up for grabs or a combination).

Not yet tested.

[x] Integrate sc- and sp-keystore

[x] Allow inserting pre-existing keys

[x] Allow generating new keys

[x] Allow signing transactions with inputs from multiple owners ~~- [ ] Actually test it~~ -- I tested it manually. Opened #47 for proper tests
opened by JoshOrndorff 0
Metadata

We should consider using metadata so we can have a dynamic wallet to submit transactions. We could take inspiration from https://github.com/paritytech/frame-metadata.

opened by JoshOrndorff 0