aiken-design-patterns v1.5.0

aiken_design_patterns/linked_list

Storing lists in datums is generally impractical, as its growth can lead to unspendable UTxOs due to limited resources available on-chain.

A linked list is a construct for storing an infinitely large array of elements on-chain, such that each element is represented with a UTxO that points to its immediate successor.

The presumption throughout is that the datum of the spending contract which holds the linked list UTxOs is of type Element<a, b>. So the recommended approach is to define your datum as its applied alias:

pub type Datum = linked_list.Element<RootType, NodeType>

There are two opinionated designs that should be highlighted:

  1. The elements are required to have no scripts attached to them. The continuations are already provided with too many values. Providing their reference script fields would overwhelm the API even further. So far this doesn’t seem to be a needed feature.
  2. While continued anchor nodes are validated to go to the same address, for new/removed nodes only the payment parts are validated to match the anchors’. This allows customization of staking parts of new nodes, while preserving the staking parts of existing elements.

Types

Element<root_data, node_data>

The terminology used here is as follows:

  • Root is the first element of the linked list
  • Node is any other element in a linked list other than the root
  • Element is the umbrella term to refer to either the root or nodes

You probably won’t need to interact with this.

Constructors

  • Element { data: ElementData<root_data, node_data>, link: Link }

ElementData<root_data, node_data>

Similar to Element above, the API is designed so that you wouldn’t need to work with this datatype directly.

Continuations that provide element data implicitly signal whether it should be coerced into a root_data or a node_data through the (potential) key. That is, if no key is provided, it means the element at hand is a root element.

Constructors

  • Root { data: root_data }
  • Node { data: node_data }

ElementEval<a>

Similar to Eval, but with polymorphic return type. This allows returning custom types with get_element_info.

Alias

ElementEval<a> = fn(PolicyId, RootKey, NodeKeyPrefix, NodeKeyPrefixLength) -> a

ElementInfo<a>

Type alias for the continuation function passed to get_element_info.

Alias

ElementInfo<a> = fn(Lovelace, Option<NodeKey>, Data, Link) -> a

Eval

This is the datatype for allowing you to provide environment constants. To be a bit nerdy, this is essentially a Reader monad.

To prevent excessive overhead, this function requires the length of the key prefix to be provided explicitly, next to the key prefix itself (otherwise the length should have been validated on-chain).

The length of the RootKey can be 32 bytes at the maximum. On the other hand, the length of any of the NodeKeys can be at most (32 - NodeKeyPrefixLength). “Length” here refers to the number of bytes after the asset name is decoded from any of the encoding schemes (e.g. UTF-8).

Alias

Eval = fn(PolicyId, RootKey, NodeKeyPrefix, NodeKeyPrefixLength) -> Bool

Alias

Link = Option<NodeKey>

LovelaceChange

Alias

LovelaceChange = Lovelace

NodeData

Alias

NodeData = Data

NodeKey

Alias for representing the keys of linked list nodes. This must be at least one byte long, and contracts should implement validations on them depending on their needs.

Requiring keys to be unique is the recommended approach (e.g. making sure it’s hash of an input’s out ref). If you do need to allow duplicate keys, proceed with extreme caution as linked list integrity breaks without some other means of preserving it.

As with the general principle of this API, for ordered operations (e.g. insert_ascending), proper ordering is already validated.

Alias

NodeKey = ByteArray

NodeKeyPrefix

Bytes prefixing all linked list nodes (i.e. all elements except for the root).

Note that the total number of bytes allowed for NFTs of linked list elements can be 32 bytes at most. Therefore, if for example your prefix occupies 4 bytes, your keys can have 28 bytes at most.

Alias

NodeKeyPrefix = ByteArray

NodeKeyPrefixLength

A sort of boilerplate to reduce execution budgets. You can use const to leverage Aiken compiler’s optimizations:

pub const node_key_prefix = "🔗"

pub const node_key_prefix_length =
  bytearray.length(node_key_prefix)

Alias

NodeKeyPrefixLength = Int

RootData

Alias

RootData = Data

RootEval

Similar to Eval, but for (init)[#init] and (deinit)[#deinit], which don’t validate node key prefixes.

Alias

RootEval = fn(PolicyId, RootKey) -> Bool

RootKey

An alias for the asset name of the NFT held in the root element. This can be zero bytes or more (32 bytes at most).

Keep in mind that some UTF-8 characters occupy more than 1 byte. For example the tree emoji (🌳) takes up 4 bytes.

Alias

RootKey = AssetName

Functions

Finalization Functions

run_eval_with(
  reader: Eval,
  list_nft_policy_id: PolicyId,
  root_key: RootKey,
  node_key_prefix: NodeKeyPrefix,
  node_key_prefix_length: NodeKeyPrefixLength,
) -> Bool

This typically ends up as boilerplate by defining a helper like this:

use aiken_design_patterns/linked_list

const node_key_prefix = "NODE"

const node_key_prefix_length =
  bytearray.length(node_key_prefix)

pub fn finalize_linked_list(
  eval: linked_list.Eval,
  list_nft_policy_id: PolicyId,
) -> Bool {
  linked_list.run_eval_with(
    eval,
    list_nft_policy_id,
    node_key_prefix,
    node_key_prefix_length,
  )
}

As an example, with this you’ll be able to turn your Eval results to Bools as such:

// In your minting contract:

let linked_list_eval = insert_ascending(...)

expect linked_list_eval |> finalize_linked_list(own_policy_id)


run_root_with(
  reader: RootEval,
  list_nft_policy_id: PolicyId,
  root_key: RootKey,
) -> Bool

run_element_with(
  reader: ElementEval<a>,
  list_nft_policy_id: PolicyId,
  root_key: RootKey,
  node_key_prefix: NodeKeyPrefix,
  node_key_prefix_length: NodeKeyPrefixLength,
) -> a

Initialization and De-initialization

init(
  nonce_validated: Bool,
  produced_element_output: Output,
  tx_mint: Value,
  root_validator: fn(Lovelace, Data) -> Bool,
) -> RootEval

Initialize a linked list, i.e. produce a UTxO which contains some ADA and the authentication NFT, with a Root element data. The asset name of the NFT (i.e. RootKey) is something that must be validated by passing the result of this function to run_root_with.

deinit(
  root_input: Input,
  tx_mint: Value,
  root_validator: fn(Lovelace, Data) -> Bool,
) -> RootEval

Deinitialize an empty list.

Element Addition and Removal

insert_ascending(
  anchor_element_input: Input,
  continued_anchor_element_output: Output,
  new_element_output: Output,
  tx_mint: Value,
  additional_validations: fn(
    LovelaceChange,
    Option<NodeKey>,
    Data,
    Lovelace,
    NodeKey,
    NodeData,
    Link,
  ) ->
    Bool,
) -> Eval

It is assumed the address from which the anchor element comes from is the destination address for the new node.

The additional_validations argument provides you with 7 values:

  1. Change in Lovelace count from anchor input to continued anchor output
  2. If the anchor element is a block, its key (i.e. asset name without the prefix) is provided
  3. Underlying data of the anchor element – note that this can come from either a Root or a Node
  4. Lovelace count of the new node UTxO
  5. Key (i.e. asset name without the prefix) of the new node
  6. Underlying data of the new node – note that this is extracted from a Node
  7. Link of the new node

insert_descending(
  anchor_element_input: Input,
  continued_anchor_element_output: Output,
  new_element_output: Output,
  tx_mint: Value,
  additional_validations: fn(
    LovelaceChange,
    Option<NodeKey>,
    Data,
    Lovelace,
    NodeKey,
    NodeData,
    Link,
  ) ->
    Bool,
) -> Eval

This is exactly like insert_ascending, with the exception that the inserted key is expected to be less than the anchor’s, and greater than anchor’s link (if any).

append_unordered(
  anchor_element_input: Input,
  continued_anchor_element_output: Output,
  new_element_output: Output,
  tx_mint: Value,
  additional_validations: fn(
    LovelaceChange,
    Option<NodeKey>,
    Data,
    Lovelace,
    NodeKey,
    NodeData,
  ) ->
    Bool,
) -> Eval

Append a new element at the very end of an unordered list. There is no validation for the new key to be greater than the anchor element’s.

additional_validations takes the same arguments as insert_ordered.

prepend_unordered(
  root_element_input: Input,
  continued_root_element_output: Output,
  new_element_output: Output,
  tx_mint: Value,
  additional_validations: fn(
    LovelaceChange,
    RootData,
    Lovelace,
    NodeKey,
    NodeData,
    Link,
  ) ->
    Bool,
) -> Eval

Prepend a new element at the very start of an unordered list. There is no validation for the new key to be less than the anchor/root element’s potential link.

additional_validations takes the same arguments as insert_ordered, without a possible element key, as the anchor is required to be root, which is a value that is already accessible.

remove(
  anchor_element_input: Input,
  removing_node_input: Input,
  continued_anchor_element_output: Output,
  tx_mint: Value,
  additional_validations: fn(
    LovelaceChange,
    Option<NodeKey>,
    Data,
    Lovelace,
    NodeKey,
    NodeData,
    Link,
  ) ->
    Bool,
) -> Eval

Remove a node. It expects two spent UTxOs: the node subject to removal, and its previous element (i.e. anchor element).

additional_validations takes the same arguments as insert_ordered, the difference being last NodeKey and NodeData are from the removing node.

Fold Functions

fold_from_root(
  anchor_root_input: Input,
  folding_node_input: Input,
  continued_anchor_root_output: Output,
  tx_mint: Value,
  additional_validations: fn(
    LovelaceChange,
    RootData,
    Lovelace,
    NodeKey,
    NodeData,
    Link,
    RootData,
  ) ->
    Bool,
) -> Eval

Spend a root element and its link, reproduce the root while expecting the node to be burnt. Additionally, performs an arbitrary validation on keys and underlying data.

This function ensures:

  • Authenticity of the UTxOs and root’s continued counterpart
  • The anchor is root, and that it correctly points to the folding node
  • The addresses are the same for all 3 UTxOs
  • Folded node is burnt
  • Root’s key is correct, and node’s key is prefixed as expected

The function you define for additional_validations is provided with 7 values (in order):

  1. Change in Lovelace count from input root to output
  2. Underlying data of the root
  3. Lovelace count of the folding node
  4. Key (i.e. asset name) of the folding node
  5. Underlying data of the folding node
  6. Link of the folding node
  7. Underlying data of the reproduced/continued root

Spending Script Helpers

spend_for_adding_or_removing_an_element(
  list_nft_policy_id: PolicyId,
  tx_mint: Value,
) -> Bool

Simply checks if there are any tokens getting minted/burnt in transaction’s mint field. How you provide list_nft_policy_id is most likely the “coupling” needed between the spending and minting endpoints.

spend_for_updating_elements_data(
  element_input_index: Int,
  continued_element_output_index: Int,
  element_input_outref: OutputReference,
  inputs: List<Input>,
  outputs: List<Output>,
  tx_mint: Value,
  additional_validations: fn(LovelaceChange, Option<NodeKey>, Data, Data) ->
    Bool,
) -> Eval

For spending an individual element within a linked list and reproducing it with an updated data, without affecting the structure of the linked list.

The continuation provides you with:

  1. Change in Lovelace count from input to output (i.e. output minus input).
  2. A possible node key (i.e. its asset name without the prefix). It’ll be None if the spent element is root.
  3. Input underlying data.
  4. Updated data in the reproduced element.

The transaction’s mint is required to ensure no link list assets are minted or burnt.

Exposed Helpers

get_element_info(
  element_utxo: Output,
  info_validations: ElementInfo<a>,
) -> ElementEval<a>

This should generally not be needed, but in cases where another script wants to validate expenditure from the linked list, this function can help.

After validating the authenticity of the provided element UTxO, it provides the continuation with:

  1. A possible NodeKey (i.e. it will be None if the element UTxO is root)
  2. Underlying data of the element
  3. Element’s link

Unlike other helpers, this one returns an ElementEval<a>. This is very similar to Eval. However, the type variable a allows the final evaluation to result in any typte rather than being restricted to Bool.

Search Document