Concepts

Lineage Tokens use a novel method of inductive proof to prove the ancestry (the lineage) of a token, without requiring an indexer. Every valid spend of a token proves that the spend before it was valid too, and so on, all the way back to the issuance that the Issuer signed. One Transaction at the tip proves the token’s whole history, on chain, with no indexer, no token server and no data kept off chain.

This comes at the cost of a small penalty: a token’s Transaction grows by a small, fixed number of bytes at every hop. For an ordinary transfer, that growth is at most 455 bytes a hop (for the fungible token), and as little as 152 bytes for the fuelled family. You can see the growth of each kind of token in Figure 2.

In this section we will explain how the construct works, and how it achieves this outcome. The pages that follow cover each kind of token in turn.

How the proof works

A Lineage Token is an Output whose Script checks where it came from. Every time the token moves, the spending Transaction carries along a set of records. The Script needs these records to rebuild, byte for byte, the Transaction being spent, as well as that Transaction’s parent. It then hashes what it has rebuilt, and compares the result with the txids it is spending.

Figure 1 shows the simplest Lineage Token, the NFT, issued and then passed on twice.

Figure 1: A Lineage NFT, issued and transferred twice. Hop 2’s spend runs checks A and B

Referring to Figure 1, we notice a few interesting things:

1. The token is Output 1: a header, then OP_CODESEPARATOR, then the code. The code is the same bytes in every hop. The header is different in every hop, because it describes the Transaction it sits in.
2. Input 0 of each transfer carries the record of the Transaction it spends. Hop 2 carries the record of hop 1 and, nested inside it, the record of the issuance, which ends with the Issuer’s Signature.
3. When hop 2 spends the token, the Script rebuilds hop 1 from the record and compares its hash with t₁ (step A). It then rebuilds the issuance and compares its hash with t₀ (step B). The rebuilt issuance holds the same code, so we know that the same Script ran, and passed, when hop 1 was made.
4. Each hop wraps one more header and its Signatures around the record, so the record grows by the same number of bytes at every hop.

The parts

Let’s start with the pieces a Lineage Token is built from.

The token Output. Its Locking Script is a fixed-size header pushed as data, followed by OP_CODESEPARATOR, followed by the code. The code is fixed per kind of token (its archetype), and a wallet recognises a token by those exact code bytes and nothing else. The header holds the facts about this particular token: the Token ID, the Issuer, the owner, and the outpoints of the Transaction’s own Inputs.

The Token ID is the txid of the issuance. An issuance’s own header holds zeros in that position, and every later header holds the ID.

The owner is a HASH160 of a Public Key. Only a Signature by that key moves the token.

The record. Each token Transaction carries the record of its parent in its Unlocking Script. That record consists of the parent’s header and Signatures and, inside that, the parent’s own record. The record ends with the Issuer’s Attestation.

The shape. Every token Transaction has the same layout:

• Transaction version 1, locktime 0, and every sequence final.
• Input 0 is the token, and Input 1 is a P2PKH funding coin.
• For the NFT, Output 0 is the change and Output 1 is the token.

The fuelled family is the exception here. It puts the token at Output 0 and needs no funding coin. Only the issuance looks different again: its Input 0 is an ordinary coin.

Two ways to spend a token

It turns out there are two ways to spend a token Output, and it is important to understand both.

• The normal path is a transfer. The unlock carries the Transaction’s Sighash preimage, the owner’s Signature and key, and the record. The Script rebuilds this Transaction (step A) and its parent (step B), as in Figure 1, checks the Issuer’s Attestation if the parent is the issuance, fixes the Outputs (the new token keeps the code and the Token ID), and checks the owner’s Signature.
• The cheap path is the owner’s Signature on its own. This ends the token, since no later spend accepts its Output as a token. A burn uses this path on purpose.

Never spend a token as a coin

A token Output accepts a plain Signature, just like P2PKH. A wallet that signs one as an ordinary coin destroys the token. The libspiffy plugins keep token Outputs out of ordinary payments, but only for as long as they are registered. Do not build your own Transactions that spend token Outputs.

The Issuer

An Issuer has two keys:

• A Rabin Key, which is the key the Script can check cheaply. Its HASH160 is in every header. The Issuer signs each new token’s ID with it, and that Signature is the Attestation.
• An Ed25519 identity key, which signs an Identity Anchor. The Identity Anchor is a Transaction that publishes the Rabin Key’s hash, together with the Issuer’s name and other metadata.

The Attestation names the anchor’s txid. At the issuance’s first spend, the Script checks that the Rabin Key in the header signed this Token ID. The payee in turn checks, from the anchor, that this Rabin Key is the one the Issuer published. The issuer shows how to set up both.

Issuing to yourself, then distributing

An Issuer always issues a new token to its own key first, and then transfers it to the first holder. Why go to the trouble? The first transfer carries the Attestation, and that is where the nodes check it. A bad Attestation therefore fails with the Issuer’s own Transaction, never with a customer’s. It costs one extra hop. The plugins do this for you: issue makes the token the issuing wallet’s, and transfer distributes it.

For the same reason, an issuance cannot be sold or bought. The swap and the Listed NFT both refuse it.

What the payee checks

Before a wallet shows a token as received, it checks three things, in this order:

1. The BEEF (the wallet’s job). libspiffy checks the transfer’s ancestry against its block headers. This proves that the funding history is in real blocks. It does not prove that this transfer will be mined.
2. The token (libtokensv’s job). LtReceive.check (or FnftReceive.check for the fuelled family; the plugins’ LtNftReceive and friends take a BEEF) rebuilds the transfer and its parent from the record, checks that the token is paid to the key you gave the sender, runs the token’s Script on the spend, and verifies the Attestation against the Issuer’s anchor. It returns a holding, or throws LtRefused with the reason.
3. The network (the wallet’s job). We submit the transfer to ARC, and count the token as held only once it is SEEN_ON_NETWORK or MINED. The sender could spend the same token twice, and only the network decides which spend wins.

The anchor should itself come with a merkle proof, which you check against your headers. A valid Signature on an anchor that was never mined does not prove that it is the Issuer’s published identity.

What a wallet stores

For each token it holds, a wallet stores the raw bytes of the Transaction that paid it, the reissue links if there are any, and the Issuer’s anchor (cached by its txid). Everything else, including the record that the next transfer must carry, comes from those bytes (LtBuilder.fromRaw).

Keep the raw bytes

The next spend rebuilds the token’s Transaction byte for byte. Store and pass on the raw bytes you received. Do not deserialise and serialise a token Transaction with a library that might change its encoding, and never make one with a version other than 1.

Growth, and redeeming and reissuing

Each transfer wraps one more header and its Signatures around the record, so a token Transaction grows by the same number of bytes at every hop. Figure 2 shows this for each kind of Lineage Token, measured over thirty hops. Hover over the chart, or use the arrow keys, to read the sizes at any hop.

The measurements

Hop	NFT	Listed NFT	Fungible token	Fuelled NFT	Voucher NFT
0 (issuance)	2,756	2,950	5,938	2,796	3,085
1	6,038	6,435	12,470	6,064	6,642
5	7,583	8,009	14,288	6,672	7,251
10	9,512	9,981	16,565	7,432	8,010
15	11,441	11,951	18,838	8,192	8,771
20	13,373	13,919	21,115	8,953	9,530
25	15,302	15,889	23,389	9,712	10,290
30	17,231	17,861	25,664	10,473	11,050

Figure 2: Transaction size by hop, measured with libtokensv 0.2.0

Referring to Figure 2:

1. The first transfer is the big step. The issuance spends ordinary coins, while every transfer carries the Sighash preimage, which holds the code a second time, as well as the record.
2. From there on, every line is straight. The NFT grows by about 386 bytes a hop (a 172-byte header and 214 bytes of Signatures), the Listed NFT by 394, and the fungible token by 455.
3. The fuelled family (the Fuelled NFT, the Voucher NFT and the Note) grows by only about 152 bytes a hop. A fuelled transfer has no funding coin, so there is less to record.
4. The fungible token starts higher, because its code is more than twice the size of the NFT’s.

The measurements come from a test in our examples, examples/libtokensv/test/growth_test.dart, which passes each kind of token between two holders for thirty hops and checks that every hop adds the same number of bytes.

To bring a token back to its starting size, the holder transfers it to the Issuer. The Issuer ends it, and issues a successor on the end’s Output 0. Only one Transaction can spend that Output, so a token has at most one successor.

The successor has a new Token ID. This is not quite ideal, since we would still like to show that it continues the old token. To do so, each holder passes on a link (the end Transaction, and the record of the Transaction it ended) together with the token, newest first. The payee’s check walks the links back, and reports the first token of the lineage as the holding’s origin. A token without links is still valid. Its origin is then itself.

Keys

The builders sign through LtKey, which comes in three forms:

• svPrivateKey.lt wraps a dartsv key that is held in this process.
• WalletKey signs through a wallet’s transaction signer, so the Private Key never leaves the wallet.
• LtGivenSignature carries a Signature made elsewhere (the swap uses it).

Inside libspiffy, the plugins get the right key from the wallet by its hash, and never see a Private Key.

Byte order

Token IDs, txids and outpoints in the builder API are bytes in the order that Transactions carry them. The txid that dartsv’s Transaction.id and block explorers show is the reverse. The plugins’ params take display-order txids (in hex), as libspiffy does.

// Token ids and txids in this API are bytes in the order transactions
// carry them. The txid a block explorer shows is the reverse.
final shown = Transaction.fromHex(hex.encode(iss.raw)).id;
expect(hex.encode(iss.txid.reversed.toList()), shown);

What the token does not guarantee

It is worth being clear about what all of the above does not give us:

• That a transfer will be mined. For that we wait for the network (see above).
• That the Issuer is honest, or issues only once. The anchor names the Issuer, and you trust it as you would the person or company behind it.
• That a token without links is the newest form of its lineage.
• Privacy. Every transfer carries the token’s full history since issuance, and its change goes back to the funding coin’s key.

How the examples are set up

The examples on these pages use fixed keys, made-up coins, and a check that runs a Transaction’s Input through dartsv’s Script interpreter, as a node would. They live in test/support/fixtures.dart:

/// A fixed private key per number, so every run builds the same bytes.
SVPrivateKey keyOf(int n) => SVPrivateKey.fromBigInt(BigInt.from(0x7a5e0000 + n));

/// The HASH160 of a key's compressed public key: what a token header names
/// as its owner.
List<int> pkhOf(SVPrivateKey k) => hash160(hex.decode(k.publicKey.toHex()));

var _coins = 0;

/// A P2PKH coin of [sats] owned by [k]. A wallet gets these from its UTXO
/// set. Here the outpoint is made up, which the interpreter does not mind.
LtCoin coinOf(SVPrivateKey k, [int sats = 100000]) {
  _coins++;
  final txid = sha256([_coins, 0x5e, 0xed]);
  return LtCoin(outpoint(txid, 0), k.lt, sats);
}

final _flags = {
  VerifyFlag.SIGHASH_FORKID,
  VerifyFlag.LOW_S,
  VerifyFlag.NULLFAIL,
  VerifyFlag.MINIMALDATA,
  VerifyFlag.MINIMALIF,
  VerifyFlag.SIGPUSHONLY,
  VerifyFlag.UTXO_AFTER_GENESIS,
};

/// Runs Input [input] of the raw Transaction [raw] through dartsv's Script
/// interpreter against the Output it spends ([lock], holding [sats]), as a
/// node would. Throws a ScriptException when the script refuses it.
void spends(List<int> raw, int input, List<int> lock, int sats) {
  final tx = Transaction.fromHex(hex.encode(raw));
  Interpreter().correctlySpends(tx.inputs[input].script!, SVScript.fromByteArray(Uint8List.fromList(lock)), tx, input,
      _flags, Coin.valueOf(BigInt.from(sats)));
}

LtCoin, outpoint and the .lt extension are libtokensv’s, while hash160 and sha256 are dartsv’s. Each example’s issuer.lt and issuer.anchor are the Issuer from The issuer.