Chapter 3 — PDAs from First Principles

Companion code: programs/openhl-core/src/lib.rs (the process_create_market handler), scripts/create-market/src/main.rs, fuzz/basics/src/main.rs (the solinv harness for §3.7). Tested against: solana-pubkey 2.4.0, solana-cpi 2.2.1, solana-system-interface 1.0.0, solana-program 2.3.0.

§3.0 Framing

In Chapters 1 and 2 every account we touched was identified by an ad-hoc keypair — a Keypair::new() generated client-side, used to sign the create/assign transactions, then discarded. That works for a single-account demo. It does not work for anything else.

Consider how a user, three weeks from now, looks up the market account for (SOL, USDC). They didn't make the market; they don't have its keypair. There is no on-chain registry of "all markets" to scan. The only way to find the account is for the program to dictate where it lives — to derive its address from the parameters that identify it (base_mint, quote_mint, the program ID) in a way that anyone can recompute. Pubic key derivation, with no corresponding private key, attached to your program.

That is a Program-Derived Address (PDA). In this chapter we will:

1. Open solana-pubkey and read the PDA derivation algorithm — sha256 of seeds + program ID + a special marker, plus a one-byte "bump" to push the result off the ed25519 curve.
2. Walk find_program_address (and its sibling create_program_address) line by line, understanding why one iterates and the other doesn't.
3. Open solana-cpi and read invoke_signed. See how a program "signs" for a PDA it controls by passing the seeds back through to the runtime.
4. Walk our new process_create_market handler: derive the PDA, validate the caller passed the right account, CPI to System to allocate it, write the layout, store the bump.
5. Watch a single transaction replace Chapter 2's two-step [Assign, Initialize] flow.
6. Re-run the client with the same (base_mint, quote_mint) and watch the System program reject the duplicate creation — the address is fixed.

By the end you will be able to look at any Anchor #[account(init, seeds = [...], bump)] constraint and walk the whole derivation, CPI, and signature dance it expands to. You will also understand why so many PDA exploits begin with "the program forgot to verify that the passed account matched the derived PDA."

§3.1 The PDA algorithm

A regular Solana public key is a 32-byte point on the ed25519 elliptic curve. It has a corresponding private key, and that private key is what signs transactions. PDAs are deliberately not points on the curve — they are 32-byte hashes that happen to lie off the curve, which means no ed25519 private key can produce a signature for them. They can never be used to sign a transaction client-side. Only the program that derived them can authorize their use, via invoke_signed.

The algorithm lives in solana-pubkey-2.4.0/src/lib.rs:911–958. The hash construction itself is at line 928–933:

let mut hasher = solana_sha256_hasher::Hasher::default();
for seed in seeds.iter() {
    hasher.hash(seed);
}
hasher.hashv(&[program_id.as_ref(), PDA_MARKER]);
let hash = hasher.result();

Three inputs go into the hash:

1. Each seed, fed in concatenation order.
2. The program ID (32 bytes).
3. PDA_MARKER, a 21-byte constant defined at lib.rs:52:

   const PDA_MARKER: &[u8; 21] = b"ProgramDerivedAddress";
   

The marker is what stops anyone from constructing a normal keypair whose public key happens to collide with a PDA. Since real ed25519 keys are not generated by hashing b"ProgramDerivedAddress" after their seed material, a PDA can never be mistaken for an ordinary key.

After hashing, the 32-byte digest is checked against the curve at lib.rs:935–937:

if bytes_are_curve_point(hash) {
    return Err(PubkeyError::InvalidSeeds);
}

If the hash happens to land on the ed25519 curve, it is rejected — because such an address could in principle be signed for by some private key (statistical chance: 50%), and the whole point of a PDA is that no one can sign for it except its derived program. About half of all candidate seed combinations land on the curve and are rejected.

The runtime also enforces two structural limits, at lib.rs:45–47:

pub const MAX_SEED_LEN: usize = 32;
// ...
pub const MAX_SEEDS: usize = 16;

At most 16 seeds, each at most 32 bytes. These limits are big enough that you will never hit them in normal use; they exist to bound the worst-case syscall cost.

What the SDK hides: Anchor's seeds = [b"market", base_mint.key().as_ref(), quote_mint.key().as_ref()] constraint passes its seed array directly to this same algorithm at codegen time. The constraint also writes a bump field on your struct, which is the same byte we'll see in §3.2 — Anchor just hides where it came from.

Exercise §3.1. What happens if you pass an empty seed list to create_program_address? Look at the function start. The behavior is intentional but easy to miss.

§3.2 find_program_address vs create_program_address — the bump iteration

About half of arbitrary seed inputs land on the curve and fail. So how do you find a valid PDA for a given seed set? You append a one-byte counter (the bump), starting at 255, and try create_program_address with seeds || [bump], decrementing the bump until you find one that produces an off-curve hash. That is find_program_address.

From solana-pubkey-2.4.0/src/lib.rs:823–862 (off-chain path):

pub fn try_find_program_address(seeds: &[&[u8]], program_id: &Pubkey) -> Option<(Pubkey, u8)> {
    #[cfg(not(target_os = "solana"))]
    {
        let mut bump_seed = [u8::MAX];
        for _ in 0..u8::MAX {
            {
                let mut seeds_with_bump = seeds.to_vec();
                seeds_with_bump.push(&bump_seed);
                match Self::create_program_address(&seeds_with_bump, program_id) {
                    Ok(address) => return Some((address, bump_seed[0])),
                    Err(PubkeyError::InvalidSeeds) => (),
                    _ => break,
                }
            }
            bump_seed[0] -= 1;
        }
        None
    }
    // (target_os = "solana" branch delegates to sol_try_find_program_address syscall)
}

The function tries 255, 254, 253, ... until one works. The "canonical bump" is the highest such value — the first one tried — because both clients and the program should derive the same PDA, and "highest valid bump" is a unique deterministic answer.

For seeds whose first valid bump is 255 (very common), the loop runs once. For unlucky seed combinations the loop might run several times, paying ~1,500 CU per iteration on-chain. To avoid that cost on every CPI, programs store the bump in their account data the first time find_program_address succeeds — and use create_program_address(seeds || stored_bump) from then on, which never iterates. This is exactly what process_create_market does at lib.rs:312:

market.bump = bump;

create_program_address, by contrast, takes a fully-specified seed list and either succeeds or fails. It is the right tool for verification (cheap, deterministic) but the wrong tool for discovery (it doesn't know what bump to try). Use find_program_address once to discover and store; use create_program_address thereafter to verify.

What the SDK hides: Anchor's bump constraint stores the bump for you on init, and the bump = market.bump form on subsequent accesses uses the stored value (no iteration). The optimization is the same as ours; the only thing hidden is where the storage happens.

Exercise §3.2. Pick three seed prefixes (e.g., b"market", b"position", b"vault") and call find_program_address(&[prefix, &[0u8; 32], &[0u8; 32]], &your_keypair.pubkey()) for each in a small Rust test. Record the bump each returns. You'll almost certainly get 255 for at least two of them. Why is 255 so common?

§3.3 invoke_signed — how a program signs for its PDA

A PDA has no private key. So how does a CPI like System::create_account — which requires the new account to sign — work when the new account is a PDA?

The answer: the program signs for the PDA, by submitting the seeds (including the bump) alongside the CPI. The runtime re-derives the PDA from those seeds and the program ID; if the derived address matches the account the CPI is operating on, the runtime accepts the program as the signer.

From solana-cpi-2.2.1/src/lib.rs:251–273:

pub fn invoke_signed(
    instruction: &Instruction,
    account_infos: &[AccountInfo],
    signers_seeds: &[&[&[u8]]],
) -> ProgramResult {
    // ...
    invoke_signed_unchecked(instruction, account_infos, signers_seeds)
}

The signers_seeds parameter has type &[&[&[u8]]] — a slice of seed sets, one per PDA being signed for. Each inner &[&[u8]] is exactly what you'd pass to create_program_address.

Our usage at programs/openhl-core/src/lib.rs:297–301:

invoke_signed(
    &create_ix,
    &[payer_ai.clone(), market_ai.clone(), system_ai.clone()],
    &[&[MARKET_SEED, base_mint.as_ref(), quote_mint.as_ref(), &[bump]]],
)?;

The seeds we pass to invoke_signed are the same seeds we used to derive the PDA, plus the bump. The runtime hashes them, confirms the result equals market_ai.key, and treats the program as the signer for that account. The CPI then proceeds as if the market PDA had signed a real ed25519 signature.

A critical invariant: the program ID embedded in the hash is always the calling program. You cannot invoke_signed for a PDA derived from a different program's ID. This is what makes PDA ownership program-local — only the program that derived an address can sign for it.

What the SDK hides: Anchor's init constraint generates this exact invoke_signed call, with the seeds taken from your seeds = [...] constraint and the bump taken from the bump storage. The CPI is invisible because the macro generates it, but it is the same line of code.

Exercise §3.3. Modify process_create_market to call invoke_signed with the wrong bump (e.g., bump.wrapping_sub(1)). What error do you get? Trace it to a specific check in the runtime.

§3.4 process_create_market — the program side

We can now walk the program. From programs/openhl-core/src/lib.rs:196–321. Six numbered steps inside the handler. (1)–(3) cover payload size, signer check, and System-program-identity check — straightforward parameter validation. The interesting work starts at step (4):

// (4) Derive the expected PDA from the payload fields + program_id, and
// verify the caller passed us the right account. This is what binds
// a `(base_mint, quote_mint)` pair to a single, predictable address.
let (expected_pda, bump) = Pubkey::find_program_address(
    &[MARKET_SEED, base_mint.as_ref(), quote_mint.as_ref()],
    program_id,
);
if market_ai.key != &expected_pda {
    msg!(
        "create_market: passed market {} != derived PDA {}",
        market_ai.key,
        expected_pda
    );
    return Err(ProgramError::InvalidSeeds);
}

The market_ai.key != &expected_pda check is what makes the whole construction safe. Without it, the program would happily try to operate on whatever account the caller passed in slot 1 — and invoke_signed's seed-vs-key check would catch the mismatch later, but with a less helpful error. The explicit verification fails fast with a clean message.

There is a subtlety here: in process_create_market we always call find_program_address (the iterating version), even though we have a cheap alternative. Why not use create_program_address(seeds || [bump]) with a client-provided bump? Because the account doesn't exist yet — there's no on-chain market.bump to read. The client could pass the bump in the instruction data, but then the program would have to trust it and re-validate. find_program_address here is paying ~1500 CU once at creation; subsequent operations on this market (in later chapters) will read market.bump from the account and use create_program_address for free.

Step (5) is the CPI we covered in §3.3 — invoke_signed with the bump as the last seed. Step (6) writes the Market layout, identical to Chapter 2's process_initialize except for one new line at lib.rs:312:

market.bump = bump;

The bump is now persisted in the account itself. Any future instruction that touches this market — place_order, cancel, settle — will read market.bump and use create_program_address for free verification.

Exercise §3.4. Remove the explicit PDA verification (the if market_ai.key != &expected_pda block). Build and deploy. Construct a CreateMarket transaction passing a fresh Keypair::new() as the market account instead of the PDA. What error does the runtime surface? Why is the explicit check still worth keeping?

§3.5 The client — one instruction, no market keypair

The client side simplifies dramatically. From scripts/create-market/src/main.rs:

let (market_pda, bump) = Pubkey::find_program_address(
    &[MARKET_SEED, base_mint.as_ref(), quote_mint.as_ref()],
    &program_id,
);
// ...
let ix = Instruction {
    program_id,
    accounts: vec![
        AccountMeta::new(payer.pubkey(), true),
        AccountMeta::new(market_pda, false),
        AccountMeta::new_readonly(system_program::ID, false),
    ],
    data,
};

let tx = Transaction::new_signed_with_payer(
    &[ix],
    Some(&payer.pubkey()),
    &[&payer],
    blockhash,
);

Compare to Chapter 2's init-market, which needed:

• A market Keypair::new() generated client-side
• Two instructions: [System::Assign, openhl-core::Initialize]
• Two signers: [&payer, &market]

Chapter 3's version has:

• A market PDA derived from the seeds (no keypair, no secret)
• One instruction: openhl-core::CreateMarket
• One signer: [&payer]

The market account is marked AccountMeta::new(market_pda, false) — writable but not a signer. There is no keypair to sign with. The signing happens inside the program when invoke_signed provides the seeds.

The MARKET_SEED constant the client uses is imported from the program crate itself, at scripts/create-market/Cargo.toml:

openhl-core = { path = "../../programs/openhl-core", features = ["no-entrypoint"] }

With the no-entrypoint feature, the program's types and constants are available to host binaries without the BPF entrypoint coming along. The client uses openhl_core::MARKET_SEED — guaranteeing client and program agree on the seed prefix without copy-paste.

Exercise §3.5. Run create-market twice with the same --base-mint and --quote-mint. The second run will fail. The error returned by the validator will mention the System program. Find it in the System program source (solana-system-interface-1.0.0/src/error.rs) and identify the variant.

§3.6 What #[account(init, seeds = [...], bump)] actually generates

Anchor's PDA flavor of the init constraint expands to all of the work we did in this chapter, plus the work we did in Chapters 1 and 2. The correspondence:

Nine responsibilities for PDA-based init. Anchor expresses them in one attribute; we needed about 60 lines.

There is one thing Anchor does that we do not: it generates a canonical bump check on every subsequent access. When you later write #[account(seeds = [...], bump = market.bump)], Anchor calls create_program_address(seeds || bump) and asserts the result equals the passed account's key. This is the cheap verification we mentioned in §3.2 — paid once per access, free of iteration. Our future chapters will need the same check; we just write it by hand each time we touch a market.

§3.7 Recap + verify yourself

Recap diagram

Client                                  Program                                  Runtime
──────                                  ───────                                  ───────
find_program_address(           ──┐
  [b"market", base, quote],       │
  program_id) → (pda, bump)       │
                                  ▼
build single ix:                       process_create_market
  accounts: [payer S+W,                  find_program_address(
            pda W,                          [b"market", base, quote],
            system r/o]                     program_id) → (pda, bump)
  data: [tag=1, ...]                     assert market_ai.key == pda
                                         Rent::get().minimum_balance(...)
sign with [payer]                        invoke_signed(
                                           create_account(payer, pda,
send_and_confirm_tx           ─────►       lamports, space, program_id),
                                           accounts,
                                           &[&[b"market", base, quote, [bump]]]
                                         )
                                                                  │
                                                                  ▼
                                                            runtime: hash seeds,
                                                            verify == pda,
                                                            accept program as signer,
                                                            invoke System::create_account
                                         write Market layout (incl. market.bump = bump)
                                         return Ok

Three things to verify yourself

1. Deterministic address. Run create-market, note the printed market PDA. Delete the on-chain account (or use a fresh solana-test-validator), re-run with the same --base-mint, --quote-mint, --program. The address printed should be byte-identical. Then change the order of --base-mint and --quote-mint. The address should change — seed order is part of the derivation.
2. Bump stored. After running create-market, the hex dump should show a non-zero byte at offset 9 (the bump field). The client prints both the bump it derived and the bump the program wrote — they must match. Confirm with scripts/create-market/src/main.rs:163.
3. No private key needed. Use solana account <market_pda> and confirm Owner is your program ID. There is no corresponding entry in ~/.config/solana/, no keypair file anywhere — the address has no private key. This is what makes the PDA permanent: even if someone wanted to compromise it, there's no key to steal.

Now let a tool try the checks

process_create_market has three checks of its own: the payer signed, slot 2 is the System program, and the market is the PDA. solinv can tell you what happens when each one is gone. It fuzzes a native program: you describe each instruction (which accounts sign, which an attacker could pass instead), and it sends the instruction with a signer flag cleared or one account swapped. If a call goes through and changes state, that is a finding.

fuzz/basics/ is the harness for Chapters 3, 4 and 6. It sets up one market with CreateMarket and installs solinv the way its README tells anyone to, by git rev. You need the Solana toolchain and the Crucible CLI (cargo install --locked --git https://github.com/asymmetric-research/crucible --tag v0.1.0 crucible-fuzz-cli):

cargo build-sbf --manifest-path programs/openhl-core/Cargo.toml
cd fuzz/basics
cargo build --release --features invariant_ch3
timeout -s INT 60 crucible run openhl_basics_fuzz invariant_ch3 \
    --binary-in target/release/invariant_test --timeout 45

On the program as it is, no [FUZZ_FINDING] line appears. (Crucible checks --timeout only every 1000 iterations, hence the outer timeout; on macOS it is gtimeout from coreutils.) The CreateMarket spec clears the payer's signer flag, passes a market address that is not the PDA, and passes SPL Token where System belongs.

Exercise §3.7. Delete each of the three checks in turn, rebuild the program, run the fuzzer, and predict the result first. Here is what we measured, 45 seconds each:

Check deleted	Caught?	What refused the call instead
payer_ai.is_signer	no	the runtime: Cross-program invocation with unauthorized signer or writable account
system_ai.key == system_program::ID	no	the runtime: An account required by the instruction is missing
market_ai.key == expected_pda	no	the runtime: Cross-program invocation with unauthorized signer or writable account

Work out each row before reading on.

All three are backed by the runtime, at the CPI. The payer: create_account moves the payer's lamports, so System needs the payer's signature, and a program can pass on only signatures it was given (Chapter 6 §6.2 covers this signer privilege rule). The System program: the instruction the handler builds names system_program::ID itself, so whatever the caller put in slot 2, the runtime still needs the real System program's account, and it is not there. The PDA: invoke_signed signs for the address the seeds derive (§3.3), so a different address would have to sign for itself.

That is §3.3's point, seen from the outside: when you create a PDA, the runtime checks the seeds for you. Keep the three checks anyway, because they fail earlier and say what is wrong. The PDA check that no one does for you is at read time, when a later instruction is handed a market that already exists and has to decide whether to believe it. Chapter 6 §6.6 has you look for that with the same harness.

Hook into Chapter 4

You now have programs that own accounts, and addresses derived from your own seeds rather than ad-hoc keypairs. But you have not yet had to count. Every instruction so far has run in well under the Solana per-transaction compute budget — 200,000 compute units (CU) by default, up to 1.4 million if you request more. As soon as we add anything that loops — order book matching, batch settlement, even decoding a non-trivial Borsh structure — CU becomes the first constraint that breaks.

Chapter 4 introduces the compute budget as a real engineering concern. We add CU measurement to our Initialize instruction (via the sol_log_compute_units syscall), benchmark what each part costs, walk the heap allocator that programs use to pretend Rust's Box and Vec are free, and add a place_order instruction that has to fit inside a CU envelope. The chapter ends with the question that drives the entire rest of Phase A and B: how do you write an order book matcher that fits inside 200,000 CU?