Demystifying Address Lookup Tables on Solana

A Comprehensive Guide to Leveraging Lookup Tables and v0 Transactions

INTRODUCTION

Although primarily intended for developers who have some level of advancement with Solana development, this article is written in such a manner as to enable less-experienced readers grasp the concept all the same, and gain some insight into how Solana works.

We will attempt to find the answers to the question of why lookup tables were designed and what they are, considering why and how we should use them. Let’s dive right into it.

THE SOLANA TRANSACTION FORMAT

Every Solana transaction must contain a list of addresses of all accounts that it will interact with. The Solana runtime environment uses this information to properly lock accounts as part of its parallel execution. An excerpt from this article by Solana co-founder Anatoly Yakovenko says:

On Solana, each instruction tells the VM which accounts it wants to read and write ahead of time. This is the root of our optimizations to the VM.

* Sort millions of pending transactions.

* Schedule all the non-overlapping transactions in parallel.

Solana transactions are constrained to be at most 1232 bytes due to a size restriction of 1280 bytes on protocol network packets. This means that there’s a limit to how much data a transaction can contain in the form of instructions and addresses.

Lookup tables were designed as a solution to this limitation, and seek to enable developers to fit much more instructions and accounts into a single transaction. It was conceptualized alongside a new transaction format called Versioned Transactions which was developed to allow transactions make use of lookup tables without backward-incompatible changes to the old format.

While the original transaction format (now labelled legacy) is still supported and widely used today, the current maximum supported transaction version is the V0 transaction format which supports lookup tables.

For more information about Solana transactions, check out the documentation.

TRANSACTION LIMITS AND COMPOSABILITY

This segment aims to outline how exactly the aforementioned limits might place constraints on the kinds of transactions developers can compose. If you’re uninterested in this and simply want to get started with lookup tables, feel free to simply skip to the next section!

Sources agree that the maximum number of accounts that can be specified on a legacy Solana transaction is anywhere between 32 and 35 (see the first sections of the official docs and the original proposal). In this section, we attempt to derive our own estimate of this number.

A legacy Solana transaction consists mainly of 3 parts: the instructions, the signatures, and an array of addresses required by the instructions:

1. A Transaction is made up of an array of signatures(64 bytes each) and a Message.
2. A Message is itself made up of a fixed header(3 bytes), a recent block-hash(32 bytes), an array of account keys(32 bytes each), and an array of Compiled-Instructions.
3. A Compiled-Instruction is made up of a program-id-index(1 byte), an array of account-indexes(1 byte each), and an array of bytes of variable length to represent the instruction data.

Considering the above, let’s do some quick napkin math to approximate the maximum possible number of accounts in a single transaction:

• To maximize space, we consider the minimum possible length of an instruction. That would be 1 + (1 * max_accounts) + 0.
• We also assume that there’s just a single instruction in the message. This means that the message length in the minimal case is 3 + 32 + (32 * max_accounts) + 1 + (1 * max_accounts).
• In the minimal case for signatures, we have the minimum of one signature. This takes our total transaction size to (1 * 64) + 36 + (33 * max_accounts).
• We expect 100 + (33 * max_accounts) ≤ 1232.

The above steps shows that the maximum number of accounts in a single transaction is approximately 34.

This ultimately places limits on composability and would make developers need to separate large enough transactions into multiple instead. This would break atomic guarantees without the use of advanced confirmation and retry logic to make it work.

WHAT ARE ADDRESS LOOKUP TABLES?

An Address Lookup Table(also known as a LUT or ALT) is at its core a data structure that is optimized for storing a collection of account addresses.

What this means is that rather than reference addresses directly by their keys in a transaction, it is possible to store them in the lookup table account and specify them succintly by just their 1-byte indexes.

To get all the accounts it needs unto its execution environment, the runtime knows to treat v0 transactions differently by loading the lookup table list first, and only loading the actual accounts after subsequent accesses against it to get their keys.

This means that the size cost of referencing x accounts in a v0 transaction is effectively compressed to just the size of the lookup table address and x indexes, a total of (32 + x) as opposed to (32 * x) in a legacy transaction.

source: https://solanacookbook.com/guides/versioned-transactions.html#address-lookup-tables-lut

USING VERSIONED TRANSACTIONS AND LOOKUP TABLES

For our example, we explore a minimal script that uses a single versioned transaction to transfer SOL to 50 different accounts. While this could feasibly be split into multiple transactions, it is a good showcase of how to compose a large number of instructions in scenarios where atomicity is an absolute requirement. This can only be done if they’re all in the same transaction.

Setup: We start by setting up our typescript project setup with yarn init, tsc — init, yarn add -D typescript, and yarn add ts-node. Next, we add the @coral-xyz/anchor and @solana/web3.js libraries which our program will depend on.

Since we’ll be testing on localnet, we request an airdrop of the SOL we would need to complete our transaction. We also generate 50 random accounts and an array containing transfer instructions to each of those accounts:

const provider = AnchorProvider.env();

await provider.connection.confirmTransaction(
  await provider.connection.requestAirdrop(
    provider.publicKey,
    300 * LAMPORTS_PER_SOL 
  )
);

let recipients = new Array<PublicKey>();
for (let i = 0; i < 50; ++i) {
  recipients.push(Keypair.generate().publicKey);
}
let instructions = new Array<TransactionInstruction>;

for (let i = 0; i < 50; ++i) {
  instructions.push(SystemProgram.transfer({
    fromPubkey: provider.publicKey,
    toPubkey: recipients[i],
    lamports: 4 * LAMPORTS_PER_SOL 
  }));
}

Next we import the AddressLookupTableProgram class from the @solana/web.j3 providing lookup table functionality:

import { AddressLookupTableProgram } from "@solana/web3.js";

To initialize our lookup table, we call the createLookupTable method to generate our create instruction and send it as a transaction.

const [create, lut] = AddressLookupTableProgram.createLookupTable(
  {
    authority: provider.publicKey,
    payer: provider.publicKey,
    recentSlot: await provider.connection.getSlot("finalized")
  }
);
await provider.sendAndConfirm(new Transaction().add(create));

The lookup table used in a v0 transaction must hold all the addresses the transaction references. To add our addresses to the lookup table, we use the extend instruction. We do this in batches of 15 as trying to fit all those addresses as input data to a single transaction would exceed limits:

let lookupAccounts = [SystemProgram.programId, provider.publicKey].concat(recipients);
const batch = 15;
for (let i = 0; i < lookupAccounts.length; i += batch) {
  const extend = new Transaction().add(AddressLookupTableProgram.extendLookupTable(
    {
      payer: provider.publicKey,
      authority: provider.publicKey,
      lookupTable: lut,
      addresses: lookupAccounts.slice(i, i + batch)
    }
  ));
  await provider.sendAndConfirm(extend);
}

Finally, since there is a requirement that lookup tables cannot be activated until the slot they’re created in is not in the slot hashes sysvar, we wait a little while for our lookup table account to be fully activated. Once that’s done, we construct a v0 transaction that includes all of our instructions and send it to the blockchain.

We then write some checks to assert that each of the instructions was executed successfully. This shows that our script works:

const message = new TransactionMessage({
  payerKey: provider.publicKey,
  recentBlockhash: (await provider.connection.getLatestBlockhash()).blockhash,
  instructions,
});
let v0Transaction = new VersionedTransaction(message.compileToV0Message([lookupTable]));
v0Transaction = await provider.wallet.signTransaction(v0Transaction);
const v0TransactionSize = v0Transaction.serialize().length;
console.log(`The size(in bytes) of our v0 Transaction is ${v0TransactionSize}.`);

// We send and confirm the transaction:
let sig = await provider.connection.sendTransaction(v0Transaction);
await provider.connection.confirmTransaction(sig, "finalized");
console.log(`Transaction executed with signature ${sig}.`);

// Now we check the final state of our accounts to make sure that the transaction was successful.
let i = 0;
for (let recipient of recipients) {
  let balance = await provider.connection.getBalance(recipient, "finalized");
  console.log(`Recipient ${i}'s balance: ${balance}.`);
  ++i;
  assert(balance >= 4 * LAMPORTS_PER_SOL);
}

Here’s what the complete code looks like:

And there you have it! We’ve just been able to reference as many as 50 accounts in a single transaction with lookup tables, where it was previously impossible.

The hope is that with this tutorial, you can now apply this pattern to build so much more powerful applications!

A sample repository with steps to run this script for yourself can be found here: https://github.com/galadd/LUTs