Plutarch Linked List Guide

Linked list structures leverage the EUTXO model to enhancing scalability and throughput significantly. By linking multiple UTXOs together through a series of minting policies and validators, it can improve the user experience interacting with smart contract concurrently.

This project is funded by the Cardano Treasury in Catalyst Fund 10 (opens in a new tab) and is aimed at enhancing the capabilities of Cardano smart contracts in handling complex data structures.

Introduction to Linked List

The Plutarch Linked List is an on-chain, sorted linked list solution designed for blockchain environments, specifically utilizing NFTs (Non-Fungible Tokens) and datums. It provides a structured and efficient way to store and manipulate a list of key/value pairs on-chain.

Entry Structure

Each entry in the list comprises:

• NFT: A unique identifier for each entry.
• EntryDatum: A data structure containing the key/value pair, a reference to the entry's NFT, and a pointer to the next NFT in the list.

EntryDatum Definition

data EntryDatum = EntryDatum {
  key :: BuiltinByteString,
  value :: Maybe SomeValue,
  nft :: NFT,
  next :: Maybe NFT
}

• key: A unique identifier for the entry.
• value: The value associated with the key. It can be Nothing for the head entry.
• nft: The NFT representing the entry.
• next: The NFT of the next entry in the list, or Nothing for the last entry.

Operations

Inserting an Entry

Insertion involves:

• Inputs: Two adjacent list entries.
• Outputs:
  • The first input entry, modified to point to the new entry.
  • The newly inserted entry, pointing to the second input entry.
  • The second input entry, unchanged.

Validation Rules

• Keys must maintain the order: a < b < c, where a is the lowest, b is the new key, and c is the highest.
• The pointers must be correctly updated to maintain list integrity.

Removing an Entry

To remove an entry:

• Inputs: The entry to remove and its preceding entry.
• Output: The preceding entry is modified to point to what the removed entry was pointing to.

Utilizing NFTs as Pointers

NFTs serve as robust and unique pointers within the list. Their uniqueness is ensured by a specific minting policy related to the list's head NFT.

Key Considerations

• Efficiency: As on-chain lookups are inefficient, off-chain structures are recommended for this purpose.
• Datum Hashes: Not suitable for pointers due to the complexity of updates and security concerns.
• Security: The integrity of the list is maintained through careful minting policies and entry validation.

Advanced Features

• Forwarding Minting Policy (opens in a new tab): A feature of Plutus to control NFT minting dynamically.

• List Head: Utilizes an empty head entry for validating insertions at the start of the list.

• End-of-List Insertions: Handled by ensuring the last entry points to Nothing.

Plutarch Linked List implementation

Installation

To integrate the Plutarch Linked List library into your project, start by creating a cabal.project file, as this file is not automatically generated during the cabal init process. Then, proceed by including the following:

source-repository-package
  type: git
  location: git://github.com/Anastasia-Labs/plutarch-linked-list.git

Then in the your [name of your project].cabal file include the repository under the build-depends section

build-depends:
    base ^>= 4.11.1.0
  , plutarch-linked-list

Functions

The Plutarch Linked List implementation provides several functions to create and manipulate Linked List. Below is a brief overview of each function:

• pInit: Constructs the Linked List head
• pDeinit: Destructs the Linked List
• pInsert: Inserts a node into the linked list
• pRemove: Removes a node from the linked list

Sample validator

For a complete example, including tests and further explanations, reger to the provided sample validator: LinkedListSpec.hs (opens in a new tab).

Aiken Linked List implementation

Installation

To integrate the Aiken Linked List library into your project, start by adding to your aiken project .toml file the following:

[[dependencies]]
name = "Anastasia-Labs/aiken-linked-list"
version = "0.0.1"
source = "github"

Sample validator

For a complete example, including tests and further explanations, reger to the provided sample validator: sample.ak (opens in a new tab).

Case study

Linked list can be leveraged in smart contract applications where the order of inputs is not crucial, and multiple users can interact with the contracts simultaneously. For example, consider a decentralized voting system where users can cast their votes concurrently. A linked list data structure can be employed to store and manage the votes efficiently. Each user's vote can be represented as a node in the linked list, containing relevant information such as the user's address and their chosen candidate.

Acknowledgments

This documentation and the implementation of the Plutarch Linked List draw inspiration from an original idea presented in the Plutonomicon. We acknowledge the innovative concepts and approaches outlined in their work, specifically regarding associative data structures on blockchain platforms.

For further details on the foundational ideas and their context, please refer to the Plutonomicon's overview of associative data structures: Plutonomicon's Associative Data Structures Overview (opens in a new tab).

We express our gratitude to the creators and contributors of the Plutonomicon for their pioneering work in this area, which has significantly influenced the development of our Plutarch Linked List.