Program Derived Addresses - A Deep Dive
Tags: solana, pda, rust, squads
Published: 2024-02-25 05:52:55


## Chapters
* [Introduction to cryptographic pairs](#introduction-to-cryptographic-pairs)
* [Elliptic Curves](#elliptic-curves)
* [Message Signing](#message-signing)
* [PDAs and how it differs from Ed25519](#pdas-and-how-it-differs-from-ed25519)
* [Use cases of PDAs](#use-cases-of-pdas)
* [Ephemeral Signers](#ephemeral-signers)
* [Squads Protocol](#squads-protocol)
* [Utilisation of PDAs in Squads](#utilisation-of-pdas-in-squads)
* [Conclusion](#conclusion)

---

## Introduction to cryptographic pairs

Before diving deep into cryptographic pairs, one must understand what even is a cryptographic pair. Let's say you are living in a shared apartment where people have the same key for the lock that you are using to lock/unlock the door. Multiple key duplicates to access one encrypted data point. This is what we call **symmetric cryptography**. 

Now again, let's say that you are living in the same shared apartment, but instead of multiple people, it's you and the apartment owner living together. The apartment owner lets you lock the door, but not being able to unlock it, for safety reasons. Only the owner who possesses the unlock key can be able to unlock the door for you. This is basically what **asymmetric cryptography** is. The tenant has the benefits of living inside the house and accessing the data point, but the key to accessing it lies only under the apartment's owner. Similarly, in cryptography, the person who has the private key for a public address doesn't need to share the private key, but still be able to send/allow the intended message to another person. In real-world scenarios, people mix and match asymmetric and symmetric that fulfill their use cases.

Now that we have a basic idea about what the basics of symmetrical/asymmetrical cryptography are, here is a well-known/used list of asymmetric cryptographic keypairs. 

1. [RSA](https://www.ibm.com/docs/en/zos/2.1.0?topic=keys-rsa-private-public)


2. [DSA](https://www.google.com/search?q=DSA+keypair&sca_esv=130c2c2530734d82&sxsrf=ACQVn0-Aqg7A9q-l-uIDeDx2wdK2LNzARA%3A1708153850603&ei=-lvQZeW5JIyKseMP6-SG0Aw&ved=0ahUKEwjlnvL76LGEAxUMRWwGHWuyAcoQ4dUDCBA&uact=5&oq=DSA+keypair&gs_lp=Egxnd3Mtd2l6LXNlcnAiC0RTQSBrZXlwYWlyMgcQABiABBgNMggQABgFGB4YCjIGEAAYCBgeMggQABgFGB4YDTILEAAYgAQYigUYhgMyCxAAGIAEGIoFGIYDMgsQABiABBiKBRiGA0jBBlCmAljgBHABeAGQAQCYAW6gAdoBqgEDMC4yuAEDyAEA-AEBwgIKEAAYRxjWBBiwA8ICBhAAGB4YDYgGAZAGCA&sclient=gws-wiz-serp)


3. [ECDSA](https://www.hypr.com/security-encyclopedia/elliptic-curve-digital-signature-algorithm#:~:text=The%20Elliptic%20Curve%20Digital%20Signature%20Algorithm%20(ECDSA)%20is%20a%20Digital,elliptic%20curve%20cryptography%20(ECC).)


4. [EdDSA](https://cryptobook.nakov.com/digital-signatures/eddsa-sign-verify-examples)

and much more ...

We will focus on **EdDSA**, specifically **Ed25519**, and how we can create Program Derived Addresses in Solana.

---

## Elliptic Curves

The Edwards curve Digital Signature Algorithm or EdDSA in short, uses a mathematical elliptic curve. An elliptic curve is plotted over a graph via the function ```y2 = x3 + ax + b```. It looks visually like the image beneath.

![Elliptic Curve](https://miro.medium.com/v2/resize:fit:1100/format:webp/1*2PxXNwMceh1XC_waAP9NiA.jpeg)

But why use an elliptic curve even? Not going to fry your brains for a technical approach, but basically, it's way harder to brute-force crack an EdDSA private key than an RSA private key. It's extremely popular and a common tool used in encryption-based requirements, like government internal communications and text message encryptions. The structure of an EdDSA is similar to RSA (having private and public keys), but the way the public key is derived is where the security is possessed. Whilst we do have many variants in EdDSA like **Ed448-Goldilocks**, **Ed25519ph**, and **Ed25519ctx**, we are going to deal with *Ed25519* as that is the keypair Solana and adopted globally for message communication (signatures and verification). If one requires just the asymmetric part, one can go ahead with **curve 25519**. A deep technical walkthrough about EdDSA and Ed25519 by **Cloudflare** is explained [here](https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography)

---

## Message Signing

A message is nothing but the context the private key is used for. Signing a message essentially helps us verify that the person whom we expected to receive from is the one who sent it, and not spoofed by someone else. We can see some examples here. User A wants to send a text message to User B. User A uses their private key to *sign* the text message, and as a result, the signature as well as the message is sent to User B. User B now wants to verify if the message is sent by User A, by simply checking the signature and the public key of User A. 

In Solana, users transfer messages for not just text purposes but also for financial purposes. NFT transfers, listing, and market orders are all examples of the simple scenario explained above. All regular consumers in Solana such as hot wallets, ledgers, and Solana seed vaults in Saga mobiles use this mechanism to sign messages. 

---

## PDAs and how it differs from Ed25519

Now that we have a brief idea so far regarding how keypairs work and what it takes to sign a message that's valuable to the receiver, there is a hybrid version of keypairs in Solana called **Program Derived Addresses** or **PDA**s in short. In the *Elliptic Curves* section, we have seen the graph that's plotted under a certain equation right? The normal Ed25519 keypairs lie on either curve point over that graph. These normal keypairs as we mentioned earlier, are usually owned by the ***[System Program](https://explorer.solana.com/address/11111111111111111111111111111111)*** and they are the wallets we use daily. However, where PDA differs is that they neither lie on the curve, nor they do not have a private key. So just to summarize, a PDA differs from a regular keypair via two things.
- Does not possess a private key
- Provide an option to be owned by the creator's program (also through the System program but we will discuss this later)

But that brings us to the next question, if a PDA does not have a private key, how could it sign a transaction's message and securely send it over to the receiver? That's where we have a seeding/salting mechanism. The following process is how we derive/use a PDA in Solana

1. We pass a random array of strings (usually defining what the PDA is for), that get converted to [little endian](https://dicom.nema.org/dicom/2013/output/chtml/part05/sect_7.3.html#:~:text=Little%20Endian%20byte%20ordering%20is,in%20increasing%20order%20of%20significance.) bytes. This is known as the **seeds array**. The random array of strings doesn't mean it generates randomly every time, but the choice of seeds is random. But once the seeds are created/generated, one must choose those seeds in the same order it was created/generated, as they all get converted to **Unsigned integer array of each number being under 8 bytes**.


2. The hash function tries to derive an address and checks if the resultant public key is generated through the seeds and not lying inside the ed25519 curve.


3. If we still aren't successful in keeping out from the curve, we *iterate* through a range from 0 - 255 and apply this number alongside the **seeds array**. This number variation is known as **bump**. A PDA usually consists of the initial seeds and a numeric bump value. They together are referred to as the **signer seeds**.


4. When we require a PDA to sign for a transaction, instead of the private key we would be using normally, we would be using these **signer_seeds** as a replacement, and then sign the transaction.


5. The receiving user can now verify the same way how they would do so for a regular keypair signature.

The following core logic snippet is how a PDA is generated. 

```rust
pub fn try_find_program_address(seeds: &[&[u8]], program_id: &Pubkey) -> Option<(Pubkey, u8)> {
    // We start with the bump from 255 and iterate to 0
    let mut bump_seed = [255];
    for _ in 0..255 {
        // Collecting the seeds (the array of strings)
        let mut seeds_with_bump = seeds.to_vec();
        // We then append the digit that is currently iterating through with the seeds array.
        seeds_with_bump.push(&bump_seed);
        // We try creating the pubkey through the current combination and the program ID 
        // that becomes the owner of this address 
        // and check if it's a valid off-curve address.
       if let Ok(address) = create_program_address(&seeds_with_bump, program_id) {
            return Some((address, bump_seed[0])
        }
        // If we fail to find one, we continue through the next iteration, subtracting the current value by 1.
        bump_seed[0] -= 1;
    }
     None
}
```

Now this brings us to the next question. Why even spend all this effort to create/use/utilize a PDA? Why not just assign servers/bots random keypairs and store them in a secured place to sign them when it's needed? That brings us to the next topic of *Use cases* of PDAs. But in short, signing transactions using keypairs is always less secure and anyone can spoof it when the keypair gets compromised.

---

## Use Cases of PDAs

Let's now take some of the use cases where PDAs might be useful. Automation and trustless patterns are the core usages used through PDAs.

### Escrow-based systems

This is one of the classic examples where programmatic signatures are required. User A requires X amount of tokens for Y amount of currently holding tokens. User A then proceeds to deposit the Y amount of tokens to the escrow program. Here, the escrow program has a PDA which becomes the spokesperson on behalf of the program. This PDA now has the token account as its authority and receives the Y amount of tokens. When User B agrees to send X amount of tokens for the already deposited Y amount of tokens, the PDA now repeats the same actions for the X amount of tokens, and then automatically transfers the required X tokens to User A and Y tokens to User B.

Manual transfers would lead to trust issues and compromises, but this would be the best advocate for to use of PDAs.

### Temporary Delegates

Let's assume that you need a staking platform where the user is not willing to transfer the token, but still be able to receive the APY rewards. Scenarios like these help PDAs freeze the user's NFT in their wallet so that they won't be able to transfer the token, while still being able to get rewarded. 

### Programmatic investments through algorithmic findings

Certain Decentralized finance applications split through the user's investments and get the maximum yields through depositing user funds to a PDA and then the PDA behaves as a vault to invest/withdraw funds from certain protocols based on the user's risk parameters. Applications like this allow users to not have the hassle of remembering more than 1 address and constantly having to monitor the markets' volatility.


Another key functionality of PDA is something known as **program derived ephemeral signers** which is what we are going to learn more about in the next section.

### Dictionary-based data storage

PDAs can also be used for on-chain storage of individual user details. For example, let's say an on-chain social platform is present. Each user profile can be made as a PDA with the following seeds ```['user', 'social platform', user. pubkey, created_timestamp]``` and then assign certain data points to that address, essentially making it a key-value pair (key being the PDA and value being the data object).

---

## Ephemeral Signers

Before talking about ephemeral signers, let's talk about a certain instruction in System Program called `CreateAccount`.


```rust
/// Create a new account
/// # Account references
///   0. `[WRITE, SIGNER]` Funding account
///   1. `[WRITE, SIGNER]` New account
CreateAccount {
    /// Number of imports to transfer to the new account
    lamports: u64,
    /// Number of bytes of memory to allocate
    space: u64,
    /// Address of the program that will own the new account
    owner: Pubkey,
},
```

The new account as well as the funding account would need to be signed. This means, that the account that we are creating needs to be signing the signing the transaction along with the user who is creating that account. The following way is how we would create the transaction from the client side. (We have ignored all the unnecessary code, and just focussed on the required part for this topic)

```typescript
async function createAccount() {
    const connection = new Connection(RPC_URL);
    const userKeypair = Keypair.fromSecretKey(Buffer.from(userKeypairBytes));
    // Generating a keypair to create an account
    const accountKeypair = Keypair.generate();
    
    const rent = 1_000_000;
    const createAccountIx = SystemProgram.createAccount({
        fromPubkey: userKeypair.publicKey,
        lamports: rent,
        space: SIZE_OF_THE_ACCOUNT,
        newAccountPubkey: accountKeypair.publicKey,
        programID: DESTINATION_PROGRAM_ID
    });
    
    // Creating transaction (cut short here due to context)
    const tx = [createAccountIx];

    // Signing part
    tx.sign(userKeypair);
    tx.sign(accountKeypair); // The account that is created
    
    // Transaction being sent
    await connection.sendTransaction(tx);
}
```

The line where `tx.sign(accountKeypair)` is the part where the account needs to have its signature privileges. However, the moment when this transaction is created, we wouldn't need this keypair forever, because the instructions involving this account moving forward would just expect the authority of this account to be signing, and not this account's signing privileges. In other words, this account keypair's **short-lived** is also known as **ephemeral signer**. An ephemeral signer is just like a regular key pair, but since its purpose is short-lived and no one stores the key pair of the account, the resultant account would never be able to interact on its behalf after the initialization. 

We can have a question now, why even think about ephemeral signers in the first place? Well, in short, regular ephemeral signers cannot be called inside smart contracts to be invoked, as we have to either make a delegate to that account's keypair or make a **programmable ephemeral signer**. 

That is exactly what we are going to discuss about in the next topic.

---

## Squads protocol

Squads protocol is a multi-sig smart wallet platform where users can create transactions and similar members can either approve or reject the transaction, resulting in maximum governance facilities and trustless methodologies. 

Sqauds protocol maximizes PDAs to its maximum to provide multiple features for consumers. The 2 main primary features of Squads protocols are leveraging the following concepts

1. Creating a smart wallet using PDAs

2. Ability to assign programmatic ephemeral signers through PDAs

3. Assigning spending limits through PDAs

4. Ability to batch transactions through PDAs

We will be discussing both of these points in the upcoming topic via referring to the [squads-v4](https://github.com/Squads-Protocol/v4) protocol repository.

---

## Utilisation of PDAs in Squads

### Creating a smart wallet using PDAs

Here at Squads, A multi-sig is created through the following seeds. 
```rust
let multisig_seeds = &[b"multisig", 
    b"multisig", 
    create_key.key().as_ref() // A random key that is used for seeding
]
```

The multi-sig PDA acts as the key-value pair we discussed earlier, essentially storing important information like the signing threshold, the members that are within the multi-sig, the config authority who can change these settings, and much more. 


A smart wallet is essentially using a PDA with the following seeds. This is referred to as Vault.

```rust
let vault_seeds = &[
    b"multisig",
    multisig_key.as_ref(), // multi-sig's PDA address
    b"vault",
    &args.vault_index.to_le_bytes(), // defaulted to 0
];
```

A key difference between Multisig's PDA and the Smart Wallet's PDA is that, in Multisig's PDA, the owner of the public key is the Squads program ID itself, whereas in Vault PDA, we *do not* create the account itself, because if the account is created, then it won't be able to be under the System program to act as a normal wallet but become a restricted address to be used within the bounds of the Squads program. 

One good example is sending SOL to a random address. A PDA should have special instructions (such as Lamport arithmetic and checks for balance) to do a System Instruction, but where with this setting, we can simply create a System Program's transfer instruction, and it would work just like a regular Phantom/Backpack/Solflare wallet. If you remember during the introductory section of PDAs, we referred that a PDA can be declared either under the owned program or the system program. 

The smart wallet's PDA is like a hybrid version of being able to programmatically sign under the squads' program, as well as having the potential to hold assets just like a normal wallet.

Another key reason why smart wallets are PDAs is that they can be executed at any point in time without worrying about the expiration of block hash and other client-side limitations. A transaction message is deserialized and sent as an instruction argument, which is stored under a **transaction** PDA.

The transaction PDA is then read during execution and the vault PDA executes the transaction wherever that account is marked as a signer.

So, in summary, the vault PDA essentially becomes a normal wallet address, but with the additional feature of multi-sig approvals.

---

### Program-derived Ephemeral Signers

As we said earlier, ephemeral signers are short-lived and serve no purpose after the account responsible is created through the System program, but since we can't execute the transaction on a chain from just private key bytes, and have the need to execute in a delayed fashion (after the decision of voting approval), Squads once again leverage PDAs through **program derived ephemeral signers**

Let's say we have a transaction of 2 different instructions
1. Creating a mint account

2. Creating a nonassociated token account (plain keypair)

Both mint accounts and normal token accounts require ephemeral keypairs to be added as signers. We create a transaction generating the above transaction and deserializing it. The general seed pattern for a program-derived ephemeral signer is as follows

```rust
let ephemeral_signer_seeds = &[
    b"multisig",
    transaction_key.as_ref(), // The transaction state PDA (key-value pair technique)
    "ephemeral_signer",
    &ephemeral_signer_index.to_le_bytes(), // The index order of the total ephemeral signer count
];
```

Since we need about 2 ephemeral signers, we would start from index 0 to the count length - 1 as the **ephemeral signer index**. 
In this way, after the decision amongst members has been made to approve it, the ephemeral signers are passed as signers inside the transaction, and sent as CPI instructions. 

By this, not only are we able to save the signer's keypair (basically the signer seeds) from executing at a later point in time, but we also allow the Squads program to sign as well programmatically. This allows complete automation of transaction executions. 

Program-derived ephemeral signers, in summary, help us to create any instruction that requires short-lived keypairs, through PDAs.

### Spending limits

In squads v4, either through the multisig config authority or through a config transaction, one can create a **spending limit** PDA. This allows users inside the multisig, to define certain spending limits for certain tokens (including SOL and SPL). A spending limit PDA consists of the following seeds

```rust
let spending_limit_seeds = &[
    b"multisig",
    multisig.key().as_ref(), // multisig PDA
    b"spending_limit",
    args.create_key.as_ref(), // Random key to aid in random generation
]
```

Once this limit PDA is created, it has the necessary data to limit the spending usage either per day week or month. The spending limit is also created, to make sure the redundant vault transactions aren't created and directly using spending limit PDA just for token transfer transactions. 

---

## Conclusion

Thus, we have learned why PDA exists in Solana, and how we can leverage such powerful features through PDAs that help benefit the mass consumer market.