Point validation on Ed25519 curve yeilds unexpected results

[Ahmer-Zuberi]

I want to understand the expected input format of the following function crypto_core_ed25519_is_valid_point as the output results are incorrect based on the provided argument.

Questions

1. Is the input format of the stated function correct in the code?
2. How do you convert a Hash to a Point representation?

Code

std::vector<u8> createProgramAddress (const std::vector<u8>& seeds, const std::string& programId)
{
    std::vector<u8> buffer;
    buffer.insert(buffer.end(), seeds.begin(), seeds.end());
    buffer.insert(buffer.end(), programId.begin(), programId.end());
    std::string discriminator = "ProgramDerivedAddress";
    buffer.insert(buffer.end(), discriminator.begin(), discriminator.end());
    std::vector<u8> hash = sha256(buffer);
    return std::move(hash);
}
std::vector<u8> findProgramAddress(const std::vector<u8>& seeds, const std::string& programId)
{
    int nonce = 255;
    std::vector<u8> seedsWithNonce = seeds;
    while (nonce != 0) {
        seedsWithNonce.push_back((uint8_t)(nonce));
        std::vector<u8> hash = createProgramAddress(seedsWithNonce, programId);
        if (crypto_core_ed25519_is_valid_point(hash.data()) == 1) {
            // std::cout << "Found program address: " << Base58::bitcoin().encode(hash.data(), hash.size()) << std::endl;
            return std::move(hash);
        }
        seedsWithNonce.pop_back();
        nonce--;
    }
    return std::vector<u8>();
}
[5:38](https://iintellect-usa.slack.com/archives/D06RW6KR5EY/p1723811886294219)
std::string a = "metadata";
    auto METAPLEX = Base58::bitcoin().decode("metaqbxxUerdq28cj1RbAWkYQm3ybzjb6a8bt518x1s");
    auto TOKEN = Base58::bitcoin().decode("HVQFiG7xAktfVVaZ5w1XNSUKhV1EFbGKgjeffyKU9XyM");
    std::vector<u8> seeds;
    seeds.insert(seeds.end(), a.begin(), a.end());
    seeds.insert(seeds.end(), METAPLEX.begin(), METAPLEX.end());
    seeds.insert(seeds.end(), TOKEN.begin(), TOKEN.end());
    auto metadata_pda = findProgramAddress(seeds, METAPLEX);

[jedisct1]

I'm not familiar with Solana. What does createProgramAddress() do?

Some googling led me to solana-labs/solana#11323 which suggests that createProgramAddress() returns points that are not on the curve. So is_valid_point() would fail.

For 2) there are many ways to do it. It depends on the protocol.

[Ahsan-Sarbaz]

Hi, I am one of his teammates.

What we want to do is take a SHA 256 hash of some seed and check if the "PublicKey" (sha256 hash) lies on the ed25519 curve, if it does we bump the seed and check untill we have a PublicKey that falls of the Curve, which is a ProgramDerivedAddress in Solana Terms.

So the question really is how to use crypto_core_ed25519_is_valid_point to see if the hash is valid point on curve, because that way we are using this function is not correct, now we think the input format is not correct so, how do we mutate the hash to be in a format valid to the said function.

Thanks.

[jedisct1]

Once again, according to the Solana documentation, CreateProgramAddress returns a point that is not on the curve. So crypto_core_ed25519_is_valid_point() should return 0. Your code does the opposite.

[Ahsan-Sarbaz]

Hi,
Thanks for the reply.

This is the Whole picture so to speak.

std::vector<u8> createProgramAddress(const std::vector<u8>& seeds, const std::vector<u8>& programId)
{
    std::vector<u8> buffer;
    buffer.insert(buffer.end(), seeds.begin(), seeds.end());
    buffer.insert(buffer.end(), programId.begin(), programId.end());
    std::string discriminator = "ProgramDerivedAddress";
    buffer.insert(buffer.end(), discriminator.begin(), discriminator.end());
    std::vector<u8> hash(crypto_hash_sha256_BYTES);
    crypto_hash_sha256(hash.data(), buffer.data(), buffer.size());

    return hash;
}

std::vector<u8> findProgramAddress(const std::vector<u8>& seeds, const std::vector<u8>& programId)
{
    int nonce = 255;
    std::vector<u8> seedsWithNonce = seeds;
    while (nonce != 0) {
        seedsWithNonce.push_back((uint8_t)(nonce));
        std::vector<u8> hash = createProgramAddress(seedsWithNonce, programId);
        
        auto isOnCurve = crypto_core_ed25519_is_valid_point(hash.data()) == 1;
        std::string yes_no = isOnCurve ? "Yes" : "No";

        std::cout << Base58::bitcoin().encode(hash.data(), hash.size()) 
            << " Nonce : " << int(nonce) 
            << " is on curve: " << yes_no << std::endl;


        // disabled to show the whole process
        //if (!isOnCurve) {
        //    return hash;
        //}
        seedsWithNonce.pop_back();
        nonce--;
    }
    return std::vector<u8>();
}


int main() {
    if (sodium_init() < 0) {
        std::cerr << "Failed to initialize libsodium." << std::endl;
        return 1;
    }

    std::string metadata = "metadata";
    auto metadaPublicKey = Base58::bitcoin().decode("metaqbxxUerdq28cj1RbAWkYQm3ybzjb6a8bt518x1s");
    auto tokenPublicKey = Base58::bitcoin().decode("89SDvBNx6msHBKwGzfvSe5qDuBwfodQD4kQrg2M1pump");

    std::vector<u8> seeds;
    seeds.insert(seeds.end(), metadata.begin(), metadata.end());
    seeds.insert(seeds.end(), metadaPublicKey.begin(), metadaPublicKey.end());
    seeds.insert(seeds.end(), tokenPublicKey.begin(), tokenPublicKey.end());
    
    std::vector<u8> programId;
    programId.insert(programId.end(), metadaPublicKey.begin(), metadaPublicKey.end());


    findProgramAddress(seeds, programId);

	return 0;
}

oeYvGnXVjg9MoZJCh6F4kSjZycnyHMFAxjH9A2vEKjB Nonce : 255 is on curve: No
6PQoABfPYM3TQZPZuVtnaUGGfrmu43cKcqhNcG4XqbpV Nonce : 254 is on curve: No
3oHseHCkdZn7NK9J7rSQyMqfRu3zM7EuKy1UfPvwm9kh Nonce : 253 is on curve: Yes
Dj6bfDFcdvru1Z1CexWnveVZYPfRtrvLxghvegXuLHwB Nonce : 252 is on curve: No
5FKb1VJDPix6G7vdPYHXmMv9saEYuMSH11Z67t2ypF7T Nonce : 251 is on curve: No
2F9u5w7UtUPDEwMsfhh3F6mmU2K1H19fXd1PiKA4w9PN Nonce : 250 is on curve: No
9PctBtkUfSNyKBJeCqXYoY1thGdZcJRZmCWS5XzweG61 Nonce : 249 is on curve: No
8T9KKxYCprn32ZQb9TrGXiLGYioJpAm7N3usoJnkvwL2 Nonce : 248 is on curve: No
9kU7Wwta55Y2oUXh9mCMpwAhYduZia6gfW1Mh6ZbrHTq Nonce : 247 is on curve: Yes

Now the key with nonce 251 should the be first one to be off curve and as you can see the output is clearly wrong, the keys are generated correct since the the key with nonce 251 is the PDA, so in this case only the is_valid_point part is wrong.