How likely is it that no bump will be found when searching for a PDA given some seeds and program_id?

Question

The rust docs outline that

The processes of finding a valid program address is by trial and error, and even though it is deterministic given a set of inputs it can take a variable amount of time to succeed across different inputs.

The anchor-lang docs provide a similiarly helpful code example to explain this concept.

fn find_pda(seeds, program_id) {
  for bump in 0..256 {
    let potential_pda = hash(seeds, bump, program_id);
    if is_pubkey(potential_pda) {
      continue;
    }
    return (potential_pda, bump);
  }
  panic!("Could not find pda after 256 tries.");
}

.

I understand that while technically possible, the likelihood that this occurs is statistically improbable.

What I'd like to know is exactly how statistically improbable.

Does the probability vary based on certain factors, and if so how?

Answer 1

A PDA is a 256 bit number that is not a valid Solana Public Key, so to answer this question, we first need to define what a Solana Public Key is: Since Solana uses Edd25519 for its keys, a Solana Public Key is a 256-bit integer that lies on Curve25519, aka any 256 bit integer smaller than the curve's prime, p = 2^255 - 19.

Since we are working with 256-bit integers when generating a new value using the PDA algorithm, we have n = (2^256 - 1) - (2^255 - 19) ≈ 5.8 * 10^76 possible 256-bit integers that do not lie on Curve25519. Since we attempt to generate a PDA with 256 different values, the probability of not finding a valid bump in any of these attempts is the chance that we don't pick one of the n invalid Curve25519 values out of the total set of possible values a 256-bit value can take on, 256 times in a row:

(1 - (n/(2^256-1)) )^256 ≈ 1.4* 10^(-63), or 1.4 in 1 vigintillion.

Edit: Since you asked if inputs affect this probability - no, as we attempt to generate the new PDA using a cryptographic hash, which has as a property that any input has an equal probability of leading to any resulting value the hash can possibly produce.

Answer 2

Elliot provides a great mathematical answer but I'm not sure it answers the implicit question about how likely you are to run into issues.

I'm assuming you're asking this question as you're going to be dealing with a an on-chain program. On-chain programs are limited in their compute budget. So, you might actually run out of compute units long before exhausting the total 256 attempts used by the find_program_address algorithm.

In practice, you absolutely do need to keep this in mind and should use create_program_address instead of find_program_address whenever possible.

As for how likely this event is, that entirely depends on the program and how much of the 200k compute budget the instruction is consuming already.

For those interested, the system call compute budgets are defined here:

https://github.com/solana-labs/solana/blob/master/program-runtime/src/compute_budget.rs#L93