On-Chain Linked List

Distribute data across multiple UTxOs to overcome datum size limits and enable uniqueness proofs on-chain.


  ╭──────╮  ╭───────╮  ╭────────╮  ╭────────╮  ╭───────╮
  │•Head•├─>│ Apple ├─>│ Banana ├─>│ Orange ├─>│ Peach │
  ╰──────╯  ╰───────╯  ╰────────╯  ╰────────╯  ╰───────╯

The Challenge

Two fundamental limitations in Cardano’s UTxO model:

Datum size limits - Storing lists in datums is impractical. As a list grows, it can lead to unspendable UTxOs due to limited on-chain resources and transaction size limits.
Non-existence proofs - Validating that something doesn’t exist on-chain is impossible with standard UTxOs. You only have access to transaction inputs, so detecting duplicates (e.g., preventing double votes) requires a data structure that guarantees uniqueness on insertion.

How It Works

Each node is a UTxO containing:

A unique NFT identifying the node
A datum with the node’s key, reference to next node, and user data

For ordered lists, proving uniqueness becomes simple: inspect two adjacent keys and verify the new key fits between them according to the ordering (a < b < c). This guarantees no duplicate exists in that range.

Operations (insert, remove) consume existing nodes and produce updated ones, with the minting policy enforcing list invariants.

When to Use This Pattern

Best for:

Preventing duplicates (e.g., one vote per user, unique registrations)
Growing collections that would exceed datum size limits
Registries requiring uniqueness guarantees
On-chain state that needs membership proofs

Not ideal for:

High-frequency updates (each operation is a transaction)
Random access lookups (requires sequential traversal)
Small, fixed-size collections (simpler to use datum lists)

Two Variants

Variant	Module	Key Ordering	Insert Methods
OrderedLinkedList	`scalus.patterns.OrderedLinkedList`	Sorted (key < ref)	`insert`, `prepend`, `append`
UnorderedLinkedList	`scalus.patterns.UnorderedLinkedList`	Any order	`prepend`, `append` only

When to use which:

OrderedLinkedList: When you need sorted data or efficient lookup by key range
UnorderedLinkedList: When order doesn’t matter and you only add to head/tail

API Reference

Operation	Ordered	Unordered	Description
`init`	✓	✓	Create empty list (mint head NFT)
`deinit`	✓	✓	Destroy empty list (burn head NFT)
`insert`	✓	✗	Insert node at sorted position
`prepend`	✓	✓	Insert at beginning (after head)
`append`	✓	✓	Insert at end
`remove`	✓	✓	Remove node (burn node NFT)

Data Structures


import scalus.patterns.{Cons, Node, Common, Config}
 
// Node datum - stored in each UTxO
case class Cons(
    key: Option[TokenName],  // None = head node, Some(key) = regular node
    ref: Option[TokenName],  // Reference to next node (None = end of list)
    data: Data               // User data stored in this node
)
 
// Node representation for validation
case class Node(value: Value, cell: Cons)
 
// Shared transaction context
case class Common(policy: PolicyId, mint: Value, inputs: List[Node], outputs: List[Node])
 
// Configuration for the list
case class Config(init: TxOutRef, deadline: PosixTime, penalty: Address)

Implementation Guide

How Insert Works (Ordered)


           ╭────────╮  ╭────────╮
           │ Banana ├─>│ Orange │   INPUTS
           ╰───┬────╯  ╰────┬───╯
               │            │
           ┏━━━V━━━━━━━━━━━━V━━━━━━━━━━━━━━┓
           ┃   Insert "Kiwi" Transaction   ┃
           ┗━━━┯━━━━━━━━━━┯━━━━━━━━━━┯━━━━━┛
               │          │          │
           ╭───V────╮  ╭──V───╮  ╭───V────╮
           │ Banana ├─>│ Kiwi ├─>│ Orange │  OUTPUTS
           ╰────────╯  ╰──────╯  ╰────────╯

           (Banana < Kiwi < Orange maintained)

Validation ensures:

Parent node’s ref is updated to point to new node
New node’s ref points to what parent previously referenced
Keys maintain sorted order (for OrderedLinkedList)
Exactly one NFT is minted for the new node

Ordered Linked List


import scalus.patterns.OrderedLinkedList as LinkedList
 
@Compile
object MyOrderedListValidator extends DataParameterizedValidator {
 
    inline override def mint(cfgData: Data, redeemer: Data, tx: TxInfo): Unit = {
        val config = cfgData.to[Config]
        val action = redeemer.to[OrderedNodeAction]
        val ownPolicy = tx.findOwnMintingPolicyHash
 
        val (common, inputs, outputs, signatories, validRange) =
            LinkedList.mkCommon(ownPolicy, tx)
 
        action match
            case OrderedNodeAction.Init =>
                LinkedList.init(common)
            case OrderedNodeAction.Deinit =>
                LinkedList.deinit(common)
            case OrderedNodeAction.Insert(key, covering) =>
                LinkedList.insert(common, key, covering)
            case OrderedNodeAction.Prepend(key, covering) =>
                LinkedList.prepend(common, key, covering)
            case OrderedNodeAction.Append(key, covering) =>
                LinkedList.append(common, key, covering)
            case OrderedNodeAction.Remove(key, covering) =>
                LinkedList.remove(common, key, covering)
    }
}

Unordered Linked List


import scalus.patterns.UnorderedLinkedList as LinkedList
 
@Compile
object MyUnorderedListValidator extends DataParameterizedValidator {
 
    inline override def mint(cfgData: Data, redeemer: Data, tx: TxInfo): Unit = {
        val config = cfgData.to[Config]
        val action = redeemer.to[UnorderedNodeAction]
        val ownPolicy = tx.findOwnMintingPolicyHash
 
        val (common, inputs, outputs, signatories, validRange) =
            LinkedList.mkCommon(ownPolicy, tx)
 
        action match
            case UnorderedNodeAction.Init =>
                LinkedList.init(common)
            case UnorderedNodeAction.Deinit =>
                LinkedList.deinit(common)
            case UnorderedNodeAction.Prepend(key, covering) =>
                LinkedList.prepend(common, key, covering)
            case UnorderedNodeAction.Append(key, covering) =>
                LinkedList.append(common, key, covering)
            case UnorderedNodeAction.Remove(key, covering) =>
                LinkedList.remove(common, key, covering)
    }
}

Redeemer Types


// For OrderedLinkedList
enum OrderedNodeAction derives FromData, ToData:
    case Init
    case Deinit
    case Insert(key: PubKeyHash, covering: Cons)
    case Prepend(key: PubKeyHash, covering: Cons)
    case Append(key: PubKeyHash, covering: Cons)
    case Remove(key: PubKeyHash, covering: Cons)
 
// For UnorderedLinkedList
enum UnorderedNodeAction derives FromData, ToData:
    case Init
    case Deinit
    case Prepend(key: PubKeyHash, covering: Cons)
    case Append(key: PubKeyHash, covering: Cons)
    case Remove(key: PubKeyHash, covering: Cons)

Key Uniqueness: Keys must be unique within a list. For OrderedLinkedList, the invariant node.key < node.ref must hold for all nodes.

NFT Management: Each node is represented by a unique NFT. The minting policy controls list operations - init/insert/prepend/append mint NFTs, while deinit/remove burn them.

UTxO Indexer - For efficient input-output mapping
Stake Validator - For reducing validation costs

Resources

Anastasia Labs: Aiken Linked List - Original Aiken implementation
Plutarch Linked List Guide - Detailed pattern explanation
Scalus Design Patterns - Implementation and tests
OrderedLinkedListExample - Ordered variant example
UnorderedLinkedListExample - Unordered variant example