Program Derived Addresses
除了普通的 account 之外，还有一种更为复杂和重要的 account 叫做 PDA（Program Derived Addresses），除了作为 storage， PDA 在 program authority 中扮演了重要的角色。
Program 使用 PDA 在 CPI 中对自身进行签名，以完成权限控制（authority）和权限划分（Account Maps）。
Whats PDA
把 program id（pubkey）的 32 bytes 和指定的 【seeds 👈任意长度的（最大16*32，包括 bump），且指定的，非随机的一段 bytes】拼起来，再拼一个 magic code named PDA_MARKER ，然后做 SHA256 HASH ，得到的 hash值被视为 PDA。
但是，需要保证PDA是无私钥的，这样才能确保只有program才能对 PDA进行签名，因此需要确保生成的 pubkey 不在 ED25519 曲线上
curve25519_dalek::edwards::CompressedEdwardsY::from_slice(_bytes.as_ref())
.decompress()
.is_some()
但是上面hash的所有input都是固定的，无法保证一定会生成一个不在曲线上的点，因此引入一个叫做 bump 1 byte 变量拼接到 input 中，bump 会从 0xff 一直递减遍历到 0 ，直到碰撞出第一个不在曲线上的点作为 PDA。
上面提到的hash input拼接顺序如下：
seeds[..] · bump · program_id · PDA_MARKER
Why PDA
solana中 program 和 account 是分开的，因此所有鉴权都应围绕 account 展开。哪最基础的 SPL-Token 举例，user A 的地址是 account A，token program 要为 account A 记账100 个 token，对于 account A 到 token program 管理的 account 映射有两种选择：
-
token program create 一个巨大的 account，所有的 用户记账都只需要更新这个 account 中的 1个 key-value即可。只需要 create account 并将 owner 授予 token program ，这样每次用户调用 transfer时由 token program 写入这个 account 即可。但这带来很多无法解决的问题：
- account 空间需要不断动态扩张，这很难维护；
- 这种哈希表的数据结构随着条目越来越多导致的碰撞，查表得速度越来越慢，消耗 CU 越来越大。
- 同一个token的转账无法并发，所有tx都在抢占这个account 的锁。
-
Token program 为每个用户都生成一个一一对应的 account（实际上是一对多）。这样寻址只需要做一次hash，且能保证每个用户的转账都可以并发。
How to use PDA
solana program 中有两个函数可以用来生成 PDA：
pub fn create_program_address(
seeds: &[&[u8]],
program_id: &Pubkey,
) -> Result<Pubkey, PubkeyError> {
create_program_address 不能保证生成的点不在曲线上，一般用于已知 bump 时避免在链上碰撞查找PDA。注意：如果 create_program_address 生成的点在曲线上，则会抛出 Error PubkeyError::InvalidSeeds。
pub fn find_program_address(seeds: &[&[u8]], program_id: &Pubkey) -> (Pubkey, u8)
find_program_address 将碰撞地址直到找到第一个不在曲线上的点并返回对应的 bump。
这个 seeds + bump 就是在上一节 CPI 中的
fn invoke_signed(
instruction: &Instruction,
account_infos: &[AccountInfo],
signers_seeds: &[&[&[u8]]],
) -> ProgramResult
方法的 signers_seeds 参数，传入对应的 seeds+bump 就可以让program对这个 PDA 地址进行签名。