Starknet : get complete pubKey from X part

[PhilippeR26]

Hello, In Starknet network, the public key stored in the accounts is a reduced part of the complete pubKey. Only the X part is stored. To be able to perform a signature verification, Starknet is launching a Python code to recover the complete (X+Y) pubKey . I would like, with your Typescript library, to recover the complete pubKey from the X part, or at least the Y coordinate from the X part. You said me that this code can be used : https://github.com/paulmillr/noble-curves/blob/669641e0a3692140eb5d1ab9298c1bfb9592df9f/src/abstract/weierstrass.ts#L687

I made some extraction of this code. I would like to perform a test, with a signature verification, but the compiler do not like this :

import { starkCurve } from '../utils/ec';

const message = ["0x53463473467", "0x879678967", "0x67896789678"];
const msgHash = starkCurve.hashChain(message) as string;
const sign = starkCurve.sign(msgHash, privateKey);

const verif = starkCurve.verify(sign, msgHash, pubKey3)

• variable sign is SignatureType.

• verify function expect signature: Hex

and the ts compiler do not accept this type mismatch.

How to proceed?

[PhilippeR26]

OK, found .toDERHex() to solve the problem.

Unfortunately, the test didn't pass. My code in starknet.js project (it uses bigint) : https://github.com/PhilippeR26/starknet.js/blob/8c6e532ac401dbb3bc15a702046b0b34e864124a/src/perso/signatureTest.ts :

const _0n = BigInt(0);
const _1n = BigInt(1);

/**
 * y² = x³ + ax + b: Short weierstrass curve formula
 * @returns y²
 */
function weierstrassEquation(x: bigint): bigint {
  const { a, b } = starkCurve.CURVE;
  return x * x * x + a * x + b;
}
function isValidFieldElement(num: bigint): boolean {
  return _0n < num && num < starkCurve.CURVE.Fp.ORDER; // 0 is banned since it's not invertible FE
}

const privateKey = '0x5b7d4f8710b3581ebb2b8b74efaa23d25ab0ffea2a4f3e269bf91bf9f63d633';
const pubKey = starkCurve.bytesToHexEth(starkCurve.getPublicKey(privateKey, false)); // complete
const pubKey3 = starkCurve.getStarkKey(privateKey); // only X part
console.log('pubKey  =', pubKey);

console.log('pubKey3 =', pubKey3);
const x = BigInt(pubKey3);

// code from https://github.com/paulmillr/noble-curves/blob/669641e0a3692140eb5d1ab9298c1bfb9592df9f/src/abstract/weierstrass.ts#L694
if (!isValidFieldElement(x))
  throw new Error('Public key provided not valid : Point is not on curve');
const y2 = weierstrassEquation(x); // y² = x³ + ax + b
const y = starkCurve.CURVE.Fp.sqrt(y2); // y = y² ^ (p+1)/4

console.log('      y =', addHexPrefix(y.toString(16)));
const pubKey2 = '0x40' + x.toString(16) + '05' + y.toString(16);
console.log('pubKey2 =', pubKey2);
const message = ['0x53463473467', '0x879678967', '0x67896789678'];
const msgHash = starkCurve.hashChain(message) as string;
const sign = starkCurve.sign(msgHash, privateKey);

const verif = starkCurve.verify(sign.toDERHex(), msgHash, pubKey2);
console.log('verif =', verif);

Result :

pubKey  = 0x4033536f4552cccd4250f954d33d9fb5ddeef6da5558f256bca9d46a43bee660d05cd0df03c1de238516dc6bb139bcd4d1aa920fb01a4f316408c1db31701ac71
pubKey3 = 0x33536f4552cccd4250f954d33d9fb5ddeef6da5558f256bca9d46a43bee660d
      y = 0x232f20fc3e21dd8ae923944ec6432b2e556df04fe5b0ce9bf73e24ce8fe5390
pubKey2 = 0x4033536f4552cccd4250f954d33d9fb5ddeef6da5558f256bca9d46a43bee660d05232f20fc3e21dd8ae923944ec6432b2e556df04fe5b0ce9bf73e24ce8fe5390
verif = false

[PhilippeR26]

It seems to be a problem of concatenation of X & Y, to create the complete pubKey. This works :

privateKey = '0x5b7d4f8710b3581ebb2b8b74efaa23d25ab0ffea2a4f3e269bf91bf9f63d634'
const pubKey2 = '0x040' + x.toString(16) + '0' + y.toString(16);

If I change one character of the private Key, it fails.

[paulmillr]

Fixed in the last commit. Can you try github version?

git clone ...
cd curves
npm install && npm run build

# create file a.js with this content:
import * as start from './lib/esm/stark.js';

[PhilippeR26]

Sorry. Not sure to have understood your answer...

[paulmillr]

and the ts compiler do not accept this type mismatch.

this was a bug and it was fixed. Can you try the most recent github commit?

[PhilippeR26]

git show :

commit 285aa6375dc90f085683dcec42934811800e2e42 (HEAD -> main, origin/main, origin/HEAD)
Author: Paul Miller <paul@paulmillr.com>
Date:   Mon Feb 20 15:50:29 2023 +0000

My code modified for this commit (./src/a.ts) :

import * as stark from '../stark';
const _0n = BigInt(0);

/**
 * y² = x³ + ax + b: Short weierstrass curve formula
 * @returns y²
 */
function weierstrassEquation(x: bigint): bigint {
  const { a, b } = stark.CURVE;
  return x * x * x + a * x + b;
}
function isValidFieldElement(num: bigint): boolean {
  return _0n < num && num < stark.CURVE.Fp.ORDER; // 0 is banned since it's not invertible FE
}
// const privKeyRandom=starkCurve.utils.randomPrivateKey;
const privateKey = '0x5b7d4f8710b3581ebb2b8b74efaa23d25ab0ffea2a4f3e269bf91bf9f63d634';
const pubKey = stark.getPublicKey(privateKey, false); // complete
const pubKey3 = stark.getStarkKey(privateKey); // only X part
console.log('pubKey  =', pubKey);

console.log('pubKey3 =', pubKey3);
const x = BigInt(pubKey3);

// code from https://github.com/paulmillr/noble-curves/blob/669641e0a3692140eb5d1ab9298c1bfb9592df9f/src/abstract/weierstrass.ts#L694
if (!isValidFieldElement(x))
  throw new Error('Public key provided not valid : Point is not on curve');
const y2 = weierstrassEquation(x); // y² = x³ + ax + b
const y = stark.CURVE.Fp.sqrt(y2); // y = y² ^ (p+1)/4

console.log('      y =', "0x" + y.toString(16));

const pubKey2 = '0x040' + x.toString(16) + '0' + y.toString(16);
console.log('pubKey2 =', pubKey2);
const message = ['0x53463473467', '0x879678967', '0x67896789678'];
const msgHash = stark.hashChain(message) as string;
const sign = stark.sign(msgHash, privateKey);

const verif = stark.verify(sign, msgHash, pubKey2);
console.log('verif =', verif);

But same problem. This case is OK, but any change in the privKey fails. Is there a method exposed to convert Uint8Array to string or bigint? (.getPublicKey returns Uint8Array)

[paulmillr]

You need a method that will be able to verify signatures using stark key which is 32 bytes. Correct?

[PhilippeR26]

Absolutely.

[PhilippeR26]

Hello Paul, I am still trying to find a solution. My main problem is that Starknet network is not providing the HEAD (0x02 or 0x03), so I don't know if calculated y should be even or odd. At the end, I have 2 solutions, one with my y, and one with neg(y). Is it a way to select the good one?

[paulmillr]

Not that i'm aware of.

[PhilippeR26]

Thanks. So, I will verify the message hash with both solutions, and if one succeed, the verification will return TRUE :

const yneg = stark.CURVE.Fp.neg(y); // to use if HEAD and y do not have same parity
// HEAD (0x02 or 0x03) is unknown (not provided by Starknet).
// So both solutions (y and neg y) have to verify the result.
// if one succeeds, verification is TRUE.
const pubKeySolution1 = '0x040' + x.toString(16) + '0' + y.toString(16);
const pubKeySolution2 = '0x040' + x.toString(16) + '0' + yneg.toString(16);
console.log('Calculated pubKey solutions are =\n', pubKeySolution1, "\n", pubKeySolution2);

// test
const message = ['0x53463473467', '0x879678967', '0x67896789678'];
const msgHash = stark.hashChain(message) as string;
const sign = stark.sign(msgHash, privateKey);

const verif1 = stark.verify(sign, msgHash, pubKeySolution1);
const verif2 = stark.verify(sign, msgHash, pubKeySolution2);
const verif = verif1 || verif2;
console.log('verif1 =', verif1);
console.log('verif2 =', verif2);
console.log('final result =', verif);

[PhilippeR26]

It's less elegant than an elephant in the middle of a frozen lake...but it works. Thanks a lot for your help 🙏. Will you soon correct .getPublicKey returns Uint8Array and release a new version with bug corrections post v0.7.1? And more important than all : stay safe 😞

[paulmillr]

Sure thing, will release a new version soon. Thanks!

[paulmillr]

released 0.7.2.

[PhilippeR26]

👍