Improve DevX for ECDSA Gadget

[45930]

Summary

O1JS has implemented the primitives needed to verify ECSDA over Secp256k1 signatures (used in ethereum and other blockchains), but the developer experience leaves room for improvement.

Current State

The only examples of the ECDSA gadget in o1js use o1js to produce the signature and to verify the signature. (example)

It's not clear how to bring a signature that was produced elsewhere into o1js to verify in a zkapp.

Desired State

It should be intuitive to verify signatures produced by other libraries, and we should have examples demonstrating how to do it.

[45930]

I wrote a one-file script to reproduce my confusion:

import { createHash } from 'crypto';
import elliptic from 'elliptic';
import { Bytes, createEcdsaV2, createForeignCurveV2, Crypto } from 'o1js';

const ec = elliptic.ec;
const eCurve = new ec('secp256k1');

class Secp256k1 extends createForeignCurveV2(Crypto.CurveParams.Secp256k1) {}
class Ecdsa extends createEcdsaV2(Secp256k1) {}

const msgStr = 'data to sign...';
const msgHash = createHash('sha256').update(msgStr).digest();

const msg = Bytes.from(msgHash);

const [ellipticSig, ellipticPubKeyStr] = generateEllipticSignature(msg);

const valid = await verifyEllipticSignature(ellipticPubKeyStr, ellipticSig, msg)

if(valid) {
    console.log("Woohoo!");
} else {
    console.log("Boo")
}

function generateEllipticSignature(msg: Bytes): [elliptic.ec.Signature, string] {
    // keys are generated outside of o1js
    const keys = eCurve.genKeyPair();
    // message is signed outside of o1js
    const signedMessage = keys.sign(msg.toHex());

    console.log("Original Message Hex: ", msg.toHex());
    console.log("Generated Public Key (x, y): ", {x: BigInt(keys.getPublic().getX().toString()), y: BigInt(keys.getPublic().getY().toString())});
    console.log("Signed Message r: ", signedMessage.r.toString())
    console.log("Signed Message s: ", signedMessage.s.toString())
    console.log("Signed Message Recovery Parameter: ", signedMessage.recoveryParam)
    console.log("\n--------\n")

    // return the signed message and the public key
    return [signedMessage, keys.getPublic().encode('hex', false)];
}

async function verifyEllipticSignature(pubKeyStr: string, sig_: elliptic.ec.Signature, msg: Bytes) {
    const publicKey = eCurve.keyFromPublic(pubKeyStr, 'hex');

    const sig = Ecdsa.from({
        r: BigInt(sig_.r.toString()),
        s: BigInt(sig_.s.toString())
    })

    console.log("Message to Verify Hex: ", msg.toHex());
    console.log("Using Public Key (x, y): ", {x: BigInt(publicKey.getPublic().getX().toString()), y: BigInt(publicKey.getPublic().getY().toString())});
    console.log("o1js Signature r: ", sig.r.toBigInt());
    console.log("o1js Signature s: ", sig.s.toBigInt());

    const valid = sig.verifyV2(msg, {x: BigInt(publicKey.getPublic().getX().toString()), y: BigInt(publicKey.getPublic().getY().toString())})

    console.log(valid);

    return valid.toBoolean();
}

This produces the console output:

Original Message Hex:  600ccd547b5fb59ea086531a04a685ee233370efc2b3d405aadc7c4046bf6a28
Generated Public Key (x, y):  {
  x: 86189233451021773474723608004204089990019789109585505776798781824862023843702n,
  y: 22029297388474245292261573982564520982428684660875598882433404667073377168782n
}
Signed Message r:  26412225483864025643496420963759518510490086519585809315769104300161982798468
Signed Message s:  44938886766995701917066427197522961654919958093541736878438392249356908831559
Signed Message Recovery Parameter:  0

--------

Message to Verify Hex:  600ccd547b5fb59ea086531a04a685ee233370efc2b3d405aadc7c4046bf6a28
Using Public Key (x, y):  {
  x: 86189233451021773474723608004204089990019789109585505776798781824862023843702n,
  y: 22029297388474245292261573982564520982428684660875598882433404667073377168782n
}
o1js Signature r:  26412225483864025643496420963759518510490086519585809315769104300161982798468n
o1js Signature s:  44938886766995701917066427197522961654919958093541736878438392249356908831559n
Bool { value: [ 0, [ 0, 0n ] ] }
Boo

[45930]

@mitschabaude , I'm curious if there's already a good way to do this and I am not aware of it? @xomexh and ZKON need this functionality, but we can't figure it out.

[mitschabaude]

@45930 there's EcdsaSignature.fromHex() and the same code could be used to convert the public key from hex. Not sure if that's helpful

[45930]

@mitschabaude

Using fromHex naively still doesn't solve. In fact, it's a step backwards, where I no longer get the correct r and s from the signature.

Taking my previous script, but redefiningverifyEllipticSignature as

async function verifyEllipticSignature(pubKeyStr: string, sig_: elliptic.ec.Signature, msg: Bytes) {
    const publicKey = eCurve.keyFromPublic(pubKeyStr, 'hex');

    console.log("0x" + sig_.toDER("hex"));
    const sig = Ecdsa.fromHex("0x" + sig_.toDER("hex"))
    // const sig = Ecdsa.from({
    //     r: BigInt(sig_.r.toString()),
    //     s: BigInt(sig_.s.toString())
    // })

    console.log("Message to Verify Hex: ", msg.toHex());
    console.log("Using Public Key (x, y): ", {x: BigInt(publicKey.getPublic().getX().toString()), y: BigInt(publicKey.getPublic().getY().toString())});
    console.log("o1js Signature r: ", sig.r.toBigInt());
    console.log("o1js Signature s: ", sig.s.toBigInt());

    const valid = sig.verifyV2(msg, {x: BigInt(publicKey.getPublic().getX().toString()), y: BigInt(publicKey.getPublic().getY().toString())})

    console.log(valid);

    return valid.toBoolean();
}

I get this output:

Original Message Hex:  600ccd547b5fb59ea086531a04a685ee233370efc2b3d405aadc7c4046bf6a28
Generated Public Key (x, y):  {
  x: 66376532417572341108538389592499769630690499687507286862557198547144924106497n,
  y: 70137503311559413807896566433955281109418958467930028323305115299301418868917n
}
Signed Message r:  91285253305354722425924516760033026968352637395442340025075021819522247814321
Signed Message s:  17966561509375377632481679746834476364352030619653746436032593972532912984930
Signed Message Recovery Parameter:  1

--------

0x3045022100c9d19f5645d6e03e2f2e566a714c6872aad50529cd12b6e63a5ecac754abecb1022027b8b6a492a262eb1e080a6d75285891f3a6b50b5f6aac16a6b21ebaed9e1362
Message to Verify Hex:  600ccd547b5fb59ea086531a04a685ee233370efc2b3d405aadc7c4046bf6a28
Using Public Key (x, y):  {
  x: 66376532417572341108538389592499769630690499687507286862557198547144924106497n,
  y: 70137503311559413807896566433955281109418958467930028323305115299301418868917n
}
o1js Signature r:  21832943872720452211990715115160106559667072383821415543639507697926852468426n
o1js Signature s:  90159858601325260252901974951977160945833758734654399215238706087012965553830n
Bool { value: [ 0, [ 0, 0n ] ] }
Boo

[45930]

Working on breaking this down further...

Updated script using ethers.js:

import { ethers, Signature } from 'ethers';

import { Bytes, createEcdsaV2, createForeignCurveV2, Crypto, Keccak } from 'o1js';

class Secp256k1 extends createForeignCurveV2(Crypto.CurveParams.Secp256k1) {}
class Ecdsa extends createEcdsaV2(Secp256k1) {}

const msgStr = 'data to sign...';
const msgUint8s = new TextEncoder().encode(msgStr);

const [signature, publicKey] = await generateEthereumSignature(msgUint8s);

const valid = await verifyEthereumSignature(publicKey, signature, msgUint8s)

if(valid) {
    console.log("Woohoo!");
} else {
    console.log("Boo")
}

async function generateEthereumSignature(msg: Uint8Array): Promise<[ethers.Signature, string]> {
    const wallet = ethers.Wallet.createRandom();
    const rawSig = await wallet.signMessage(msg);
    const signedMessage = Signature.from(rawSig);

    console.log("Original Message: ", msg);
    console.log("Generated Public Key hex: ", wallet.signingKey.publicKey);
    console.log("Generated Public Key x: ", BigInt("0x" + wallet.signingKey.publicKey.slice(4).slice(0, 64)));
    console.log("Generated Public Key y: ", BigInt("0x" + wallet.signingKey.publicKey.slice(4).slice(64)));
    console.log("Signed Message r: ", BigInt(signedMessage.r))
    console.log("Signed Message s: ", BigInt(signedMessage.s))
    console.log("\n--------\n")

    return [signedMessage, wallet.signingKey.publicKey];
}

async function verifyEthereumSignature(pubKeyStr: string, sig_: ethers.Signature, msg: Uint8Array) {
    console.log("0x" + sig_);
    const sig = new Ecdsa({
        r: BigInt(sig_.r),
        s: BigInt(sig_.s)
    })

    const o1jsPublicKey = {
        x: BigInt("0x" + pubKeyStr.slice(4).slice(0, 64)),
        y: BigInt("0x" + pubKeyStr.slice(4).slice(64))
    }

    console.log("Message to Verify: ", msg);
    console.log("Using Public Key (x, y): ", o1jsPublicKey);
    console.log("o1js Signature r: ", sig.r.toBigInt());
    console.log("o1js Signature s: ", sig.s.toBigInt());

    const valid = sig.verifyV2(Bytes.from(msg), o1jsPublicKey)

    console.log(valid);

    return valid.toBoolean();
}

I am converting the string message to UInt8Array before getting to either library to eliminate string conversion as a factor.

I also added logging within o1js and found that a) the public key and signature appear to be reaching the final internal function correctly and b) it is the final check in src/bindings/crypto/finite-field.ts#equal that fails, which causes the check to fail. We are not bombing out on any edge cases.

New console output:

Original Message:  Uint8Array(15) [
  100,  97, 116,  97,  32,
  116, 111,  32, 115, 105,
  103, 110,  46,  46,  46
]
Generated Public Key hex:  0x046c36701234913b97d32c7d916592105397657f3b632cb1f68f2cfaf8c31fa7479f199c11aa2104dffd687a36005ab7bf6de05286c73353833dcac3f0e445103e
Generated Public Key x:  48945970874896667719305023402628702086989218761139739838954818825062067447623n
Generated Public Key y:  71962991250024680859121874849679850616250170728560897466817073715802760613950n
Signed Message r:  40479586769020999514857251798412524074341438074229133324305722536167548808931n
Signed Message s:  5195896602994363633841461007883925583954309016616196889777292273485439322166n

--------

0x[object Object]
Message to Verify:  Uint8Array(15) [
  100,  97, 116,  97,  32,
  116, 111,  32, 115, 105,
  103, 110,  46,  46,  46
]
Using Public Key (x, y):  {
  x: 48945970874896667719305023402628702086989218761139739838954818825062067447623n,
  y: 71962991250024680859121874849679850616250170728560897466817073715802760613950n
}
o1js Signature r:  40479586769020999514857251798412524074341438074229133324305722536167548808931n
o1js Signature s:  5195896602994363633841461007883925583954309016616196889777292273485439322166n
const
verifyEcdsaConstant pk:  48945970874896667719305023402628702086989218761139739838954818825062067447623 71962991250024680859121874849679850616250170728560897466817073715802760613950
verifyEcdsaConstant r, s:  40479586769020999514857251798412524074341438074229133324305722536167548808931 5195896602994363633841461007883925583954309016616196889777292273485439322166
Finite Field check  (p = 115792089237316195423570985008687907852837564279074904382605163141518161494337):  85316007631837789267752287354229839386129539608428872581138242724144446245629  ==  40479586769020999514857251798412524074341438074229133324305722536167548808931
Bool { value: [ 0, [ 0, 0n ] ] }
Boo

I will continue looking at this tomorrow.

[Shigoto-dev19]

In Ethereum, the message digest used for signing is computed differently, as specified in EIP-191. The sig.verifyV2 function was hashing the message directly, which led to a different message hash and caused the verification to fail.

To illustrate the difference in hashing, here’s a code snippet that demonstrates how to compute the correct hash, matching the Ethereum message format:

import { Keccak } from 'o1js';
import { MessagePrefix, toUtf8Bytes, hashMessage } from 'ethers';

// String to be signed
const msgStr = 'data to sign...';
const msgBytes = new TextEncoder().encode(msgStr); // Convert the message string to bytes

// Generate the hash using ethers.js
const ethersHash = hashMessage(msgBytes); // Hash the message using ethers.js

// Generate the hash using o1js Keccak (Ethereum format)
const o1jsHash = Keccak.ethereum([
  ...toUtf8Bytes(MessagePrefix),            // Ethereum message prefix
  ...toUtf8Bytes(String(msgBytes.length)),  // Length of the message in bytes
  ...msgBytes,                              // The actual message bytes
]).toHex();

// Compare the hashes
console.log('ethers hash: ', ethersHash); // Hash generated by ethers.js
console.log('o1js Keccak hash: ', '0x' + o1jsHash); // Hash generated by o1js (with '0x' prefix)

Manually computing the hash in the same format as shown above isn’t always necessary. You can simply use hashMessage from ethers.js and pass the resulting message digest directly to the o1js circuit for Ethereum signature verification.

const isValid = signatureP.verifySignedHashV2(
  Secp256k1.Scalar.from(hashMessage(msg)), 
  publicKeyP
);

This approach ensures the message digest is formatted correctly, allowing the signature to be verified seamlessly within the o1js circuit.

[Shigoto-dev19]

Here's an example of how to use the o1js API to verify Ethereum signatures:

import { Wallet, hashMessage } from 'ethers';
import { Crypto, Provable, createEcdsaV2, createForeignCurveV2 } from 'o1js';

// Define Secp256k1 curve and ECDSA based on the curve using o1js
class Secp256k1 extends createForeignCurveV2(Crypto.CurveParams.Secp256k1) {}
class Ecdsa extends createEcdsaV2(Secp256k1) {}

// ethers
const wallet = Wallet.createRandom();
const privateKey = wallet.signingKey.privateKey;

const msg = 'message to sing...';
const signature = await wallet.signMessage(msg);

// o1js
const publicKeyP = Secp256k1.generator.scale(BigInt(privateKey));
const signatureP = Ecdsa.fromHex(signature);

const isValid = signatureP.verifySignedHashV2(
  Secp256k1.Scalar.from(hashMessage(msg)),
  publicKeyP
);

Provable.log('is valid: ', isValid);

[Shigoto-dev19]

The example above has been tested, and all tests pass successfully, as demonstrated in the following code:

import { Bytes } from 'o1js';
import { Wallet, hashMessage } from 'ethers';
import { Ecdsa, Secp256k1 } from './ecdsa.js';

/**
 * Generates a random message, signs it using ethers.js, and verifies the signature using o1js.
 */
async function generateAndVerifySignature() {
  // Generate a random 128-byte message and convert it to hex
  const msg = Bytes(128).random().toHex();

  // Generate a random wallet and extract the private key
  const wallet = Wallet.createRandom();
  const privateKey = wallet.signingKey.privateKey;

  // Sign the message with the private key using ethers.js
  const signature = await wallet.signMessage(msg);

  // Derive the public key from the private key using the Secp256k1 curve in o1js
  const publicKeyP = Secp256k1.generator.scale(BigInt(privateKey));

  // Parse the signature into a format that o1js can verify
  const signatureP = Ecdsa.fromHex(signature);

  // Verify the signature in o1js by hashing the message and comparing with the public key
  const isValid = signatureP.verifySignedHashV2(
    Secp256k1.Scalar.from(hashMessage(msg)), // Hash the message using ethers.js hashMessage
    publicKeyP
  );

  // Assert that the verification result is valid
  expect(isValid.toBoolean()).toBe(true);
}

describe('Ethereum Signature Verification with o1js', () => {
  it('should verify a single Ethereum signature', async () => {
    await generateAndVerifySignature();
  });

  it('should verify 10,000 Ethereum signatures', async () => {
    for (let i = 0; i < 10000; i++) {
      await generateAndVerifySignature();
    }
  });
});

[mitschabaude]

Manually computing the hash in the same format as shown above isn’t necessary. You can simply use hashMessage from ethers.js and pass the resulting message digest directly to the o1js circuit for Ethereum signature verification.

I don't think this is sufficient for many applications, because here the hash is computed outside the circuit and not provable.

That's fine if you only want to prove something about the hash.

But it's typically more interesting to prove something about the message. In that case, the hash has to computed in-circuit as well. (Compare e.g.: zkEmail)

[mitschabaude]

@Shigoto-dev19 from the code you post it looks like you should be able to use verifyV2() directly if only you add the message prefix and length.

I think it's worth changing verifyV2() to include this step, so it can be used on a message directly, in a provable way

[Shigoto-dev19]

I don't think this is sufficient for many applications, because here the hash is computed outside the circuit and not provable.

I agree @mitschabaude , it's only the case for verifySignedHashV2. I've updated the comment to emphasize that it's not always necessary.

[Shigoto-dev19]

from the code you post it looks like you should be able to use verifyV2() directly if only you add the message prefix and length.

I think it's worth changing verifyV2() to include this step, so it can be used on a message directly, in a provable way

@mitschabaude, indeedverifyV2() would work directly if we added the message prefix and length. The API seems to be designed primarily for Ethereum signature verification, so this change would make it functional, but I believe it has the potential to be more general-purpose.

Do you think it would be possible to instantiate verifyV2() to accept a provable hash function as input, allowing it to take the raw message bytes as the circuit input?

[mitschabaude]

Do you think it would be possible to instantiate verifyV2() to accept a provable hash function as input, allowing it to take the raw message bytes as the circuit input?

You can do exactly that, and be flexible about message encoding, already using verifySignedHash()

[Shigoto-dev19]

You can do exactly that, and be flexible about message encoding, already using verifySignedHash()

But it's not flexible in a provable way :thinking: , if SHA256 is to be used of example.

[mitschabaude]

But it's not flexible in a provable way 🤔 , if SHA256 is to be used of example.

so currently, verify just looks like this:

  verifyV2(message: Bytes, publicKey: FlexiblePoint): Bool {
    let msgHashBytes = Keccak.ethereum(message);
    let msgHash = keccakOutputToScalar(msgHashBytes, this.Constructor.Curve);
    return this.verifySignedHashV2(msgHash, publicKey);
  }

assume we make verifySignedHash() slightly more powerful so that it would also accept the msgHashBytes directly, and would perform keccakOutputToScalar itself in that case.

then everyone could make their own version of it with whatever hash function they liked, like this:

function myVerify(message: Bytes, publicKey: ForeignCurve) {
  let msgHash = Hash.SHA2_256.hash(message);
  return Ecdsa.verifySignedHashV2(msgHash, publicKey);
}

[Shigoto-dev19]

then everyone could make their own version of it with whatever hash function they liked, like this:

I see, that's solid :100: , thanks for the explanation @mitschabaude I will push a PR to update verifyV2 :)

[mitschabaude]

then everyone could make their own version of it with whatever hash function they liked, like this:

I see, that's solid 💯 , thanks for the explanation @mitschabaude I will push a PR to update verifyV2 :)

Aweseome! Please remember that it's a breaking change so might be worth adding a new method, which becomes verify() in v2

[mitschabaude]

@Shigoto-dev19 since I just played around with this, here is how you can do the conforming hash only with o1js Bytes:

const MessagePrefix = '\x19Ethereum Signed Message:\n';

const o1jsHash = Keccak.ethereum([
  ...Bytes.fromString(MessagePrefix).bytes, // Ethereum message prefix
  ...Bytes.fromString(String(msgBytes.length)).bytes, // Length of the message in bytes
  ...msgBytes.bytes, // The actual message bytes
]);

[Shigoto-dev19]

@Shigoto-dev19 since I just played around with this, here is how you can do the conforming hash only with o1js Bytes:

Thanks, yes, that’s the right approach :saluting_face:

[Shigoto-dev19]

Note that in the previous example, the publicKeyP was derived directly from the privateKey, which is not practical for general signature verification.

In real scenarios, for o1js signature verification, you’ll need to parse an ethers public key and for that you can use the @noble/curves/secp256k1 library.

Below is an example of how to parse public keys from ethers.js:

import { secp256k1 } from '@noble/curves/secp256k1';
import { getBytes } from 'ethers';

const wallet = Wallet.createRandom();

// Works with both uncompressed and compressed public keys
let bytes = getBytes(wallet.signingKey.publicKey);
// let bytes = getBytes(wallet.signingKey.compressedPublicKey);

if (bytes.length === 64) {
  const pub = new Uint8Array(65);
  pub[0] = 0x04; // Add the uncompressed public key prefix
  pub.set(bytes, 1);
  bytes = pub;
}

// Convert the public key bytes to an affine point using noble-curves
const point = secp256k1.ProjectivePoint.fromHex(bytes).toAffine();

// Replaces `const publicKeyP = Secp256k1.generator.scale(BigInt(privateKey));`
const publicKeyP = Secp256k1.from({ x: point.x, y: point.y });

[mitschabaude]

@Shigoto-dev19 would be nice to add that fromHex() method to o1js so you don't need noble.

Also, we could add a fromEthers method so that you can use wallet.signingKey.publicKey directly

[45930]

@Shigoto-dev19 your example is working for me 👍 nice work! This will be a great UX fix for o1js!