6

As a beginner, what is a good way to understand the purpose of Program Derived Addresses being bumped until they are off of the ed25519 elliptic curve?

What is the ed25519 elliptic curve?

How is it used within Solana that PDAs require getting bumped off of it?

2 Answers 2

10

As a beginner, what is a good way to understand the purpose of Program Derived Addresses being bumped off of the ed25519 elliptic curve?

The purpose of being off the curve is so that only the program a PDA is derived from can sign on behalf of the PDA.

It's not that they are being bumped off, it's just that some public key values are on it, and some are off.

From the Public Key class createWithSeed method's comments:

  /**
   * Derive a public key from another key, a seed, and a program ID.
   * The program ID will also serve as the owner of the public key, giving
   * it permission to write data to the account.
   */

Program derived address (PDA) accounts are just non-executable Solana accounts - they have a valid Solana address which looks just like a base58 encoded string of a public key. A key difference (see what I did there?) is that a PDA has no corresponding private key. PDAs being "off the curve" just means that the program a PDA is derived from acts as the owner of the PDA.


How is (the ed25519 elliptic curve) used within Solana to cause PDAs being bumped off of it necessary?

The cryptographic function for finding PDAs is as likely to derive a public key which is on the curve as it is to derive one that's off the curve.

The "bumping" refers the cryptographic strategy of nudging the output to a result which is off the curve. You can see it here in how the nonce is set to 255 then handled with a decrementing -- operator.

From the findProgramAddressSync function's comments:

  /**
   * Find a valid program address
   *
   * Valid program addresses must fall off the ed25519 curve.  This function
   * iterates a nonce until it finds one that when combined with the seeds
   * results in a valid program address.
   */

There is also, as an example of how the curve positioning is used in Solana, a method on the PublicKey class called, isOnCurve ("Check that a pubkey is on the ed25519 curve") which returns a boolean:

  • true i.e. "on the curve" when the account has a corresponding private key
  • false i.e. "off the curve" when the account has no private key.

From a support function is_on_curve, the curve-finding "function and its dependents were sourced from here"


What is the ed25519 elliptic curve?

From the article, "Everything you wanted to know about Elliptic Curve Cryptography"

The basic procedure of ECC is this:

  • Choose a curve and a point P on the curve (everyone uses the same point)
  • Choose an arbitrary very large number N (this is your private key).
  • Using point addition, add P to itself N times
  • The x-coordinate of N*P is your public-key

As I understand these things, elliptic curve cryptography is fundamental to "asymmetric encryption" and how we obtain the public and private key pairs we use for digital signatures. The Ed25519 elliptic curve is basically just a particular ECC which uses SHA-512. For more on the naming, see here, but basically it comes from the use of 2^255-19 in Montgomery coordinates:

  • "Montgomery coordinates" (X,Y) satisfy Y^2 = X^3 + AX^2 + X mod 2^255-19, where A = 486662.
2
  • 1
    "they have a valid public key" this is an inaccurate bit of solana terminology misuse. we call a bunch of stuff "pubkey" that isn't really a public key, PDAs being a prime example. consider the the accounts address space as a hashmap keyed (where the misnomer originated!) by a 32-byte vector Address (a type that should exist, but doesn't). Address is then split into two domains, on-curve (Pubkey addresses) and off-curve (PDAs). From there, the off-curve domain is sub-domained by program-id. We neglect the bastard child legacy *WithSeed derivation scheme
    – trent.sol
    Commented Jul 23, 2022 at 5:00
  • "only the program a PDA is derived from can sign on behalf of the PDA.". How does that happen? What exactly stops others (a bad player) from signing on behalf of the PDA? Why only the source program can sign it? What does the program know that others cannot? Commented Feb 5, 2023 at 21:38
5

ed25519 is the elliptic curve digital signature scheme used by Solana to sign transactions. Ed25519 keypairs are generated by mapping a random point on the curve (private key) to another point on the curve (public key) via some elliptic curve arithmetic that isn't pertinent here.

Since programs live in cleartext on chain, they can't keep a private key secret so they can't safely digitally sign instructions that require a program-controlled authority. Instead, the runtime uses the PDA scheme to promote program-controlled authorities to signers artificially, assuming the appropriate seeds are provided. PDAs are forced off-curve to ensure that it is impossible to generate a real ed25519 keypair that would allow attacker to bypass the program's logic by creating a real digital signature for the PDA pubkey.

4
  • "forced" off curve, or "defined as" so?
    – MmmHmm
    Commented Jul 23, 2022 at 14:34
  • 1
    well "no private key exists with this address value as a public key" was a design goal. So we "designed" the derivation protocol to "force" the addresses off-curve. both? :)
    – trent.sol
    Commented Jul 23, 2022 at 17:09
  • If there is no private key, what exactly stops attackers from signing using the same method as used by the program? Why only the source program can sign it? After all, the program must be using some code/logic (which is often publicly available) to somehow sign it, without using a private key? What does the program know that others cannot? Commented Feb 5, 2023 at 21:49
  • the runtime verifies that the supplied seeds generate the candidate address for the called program. the called program's address (program id) is effectively a hash domain, carving out an explicit derived address space for that program. the logic is irrelevant as the caller cannot control which program id the runtime uses for this calculation. tricking the runtime into signing for one program's instruction as another program amounts to a second preimage attack against sha256, which we take as improbable
    – trent.sol
    Commented Feb 6, 2023 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.