I know there’s plenty of specs that provide a topical overview of how the signature is generated on Avalanche (via the secp256k1 curve). But how exactly is the signature generated?
Like, specifically, I’m curious about how the ‘nonce’ is derived in the secp256k1 signature operation.
I can tell that its deterministic, but nothing I’ve seen ties it to RFC-6979 standard. So, if not that, what is being used to determine the ‘nonce’ (k) for each signature? My best guess (after pouring over documentation for hours) is that it must be a function of the actual message hash itself (but not via any HMAC construction ).
If there are any devs that could shed some light on this, that would be amazing. Thank you!
Great question! I’ll walk through how RFC-6979 signatures (which avoid nonce reuse ) are generated in AvalancheGo (used by avalanche-cli) and AvalancheJS (used by wallet.avax.network) below.
Sign
SignHash
func (k *PrivateKeySECP256K1R) SignHash(hash []byte) ([]byte, error) {
sig := ecdsa.SignCompact(k.sk, hash, false) // returns [v || r || s]
return rawSigToSig(sig)
}
Note that we call the ecdsa package in the github.com/decred/dcrd repository directly as is recommended by their README: dcrd/README.md at 9408498fd00555dd268e4987e5c89cd53ab9051f · decred/dcrd · GitHub
ecdsa.SignCompact
// SignCompact produces a compact ECDSA signature over the secp256k1 curve for
// the provided hash (which should be the result of hashing a larger message)
// using the given private key. The isCompressedKey parameter specifies if the
// produced signature should reference a compressed public key or not.
//
// Compact signature format:
// <1-byte compact sig recovery code><32-byte R><32-byte S>
//
// The compact sig recovery code is the value 27 + public key recovery code + 4
// if the compact signature was created with a compressed public key.
func SignCompact(key *secp256k1.PrivateKey, hash []byte, isCompressedKey bool) []byte {
// Create the signature and associated pubkey recovery code and calculate
// the compact signature recovery code.
sig, pubKeyRecoveryCode := signRFC6979(key, hash)
compactSigRecoveryCode := compactSigMagicOffset + pubKeyRecoveryCode
if isCompressedKey {
compactSigRecoveryCode += compactSigCompPubKey
}
// Output <compactSigRecoveryCode><32-byte R><32-byte S>.
show original
Note that SignCompact explicitly states that the caller must provide the result of hashing a larger message (which is performed in “1) Sign”). It does not stipulate that this hash must be HMAC’d as that will be done in “5) secp256k1.NonceRFC6979”.
signRFC6979
// signRFC6979 generates a deterministic ECDSA signature according to RFC 6979
// and BIP0062 and returns it along with an additional public key recovery code
// for efficiently recovering the public key from the signature.
func signRFC6979(privKey *secp256k1.PrivateKey, hash []byte) (*Signature, byte) {
// The algorithm for producing an ECDSA signature is given as algorithm 4.29
// in [GECC].
//
// The following is a paraphrased version for reference:
//
// G = curve generator
// N = curve order
// d = private key
// m = message
// r, s = signature
//
// 1. Select random nonce k in [1, N-1]
// 2. Compute kG
// 3. r = kG.x mod N (kG.x is the x coordinate of the point kG)
// Repeat from step 1 if r = 0
// 4. e = H(m)
show original
secp256k1.NonceRFC6979
// NonceRFC6979 generates a nonce deterministically according to RFC 6979 using
// HMAC-SHA256 for the hashing function. It takes a 32-byte hash as an input
// and returns a 32-byte nonce to be used for deterministic signing. The extra
// and version arguments are optional, but allow additional data to be added to
// the input of the HMAC. When provided, the extra data must be 32-bytes and
// version must be 16 bytes or they will be ignored.
//
// Finally, the extraIterations parameter provides a method to produce a stream
// of deterministic nonces to ensure the signing code is able to produce a nonce
// that results in a valid signature in the extremely unlikely event the
// original nonce produced results in an invalid signature (e.g. R == 0).
// Signing code should start with 0 and increment it if necessary.
func NonceRFC6979(privKey []byte, hash []byte, extra []byte, version []byte, extraIterations uint32) *ModNScalar {
// Input to HMAC is the 32-byte private key and the 32-byte hash. In
// addition, it may include the optional 32-byte extra data and 16-byte
// version. Create a fixed-size array to avoid extra allocs and slice it
// properly.
const (
privKeyLen = 32
hashLen = 32
show original
rawSigToSig
// raw sig has format [v || r || s] whereas the sig has format [r || s || v]
func rawSigToSig(sig []byte) ([]byte, error) {
if len(sig) != SECP256K1RSigLen {
return nil, errInvalidSigLen
}
recCode := sig[0]
copy(sig, sig[1:])
sig[SECP256K1RSigLen-1] = recCode - compactSigMagicOffset
return sig, nil
}
This utility function just reorders [v||r||s] to be [r||s||v].
sign
/**
* Takes a message, signs it, and returns the signature.
*
* @param msg The message to sign, be sure to hash first if expected
*
* @returns A {@link https://github.com/feross/buffer|Buffer} containing the signature
*/
sign(msg: Buffer): Buffer {
const sigObj: elliptic.ec.Signature = this.keypair.sign(msg, undefined, {
canonical: true
})
const recovery: Buffer = Buffer.alloc(1)
recovery.writeUInt8(sigObj.recoveryParam, 0)
const r: Buffer = Buffer.from(sigObj.r.toArray("be", 32)) //we have to skip native Buffer class, so this is the way
const s: Buffer = Buffer.from(sigObj.s.toArray("be", 32)) //we have to skip native Buffer class, so this is the way
const result: Buffer = Buffer.concat([r, s, recovery], 65)
return result
}
keypair.sign
// ECDSA
KeyPair.prototype.sign = function sign(msg, enc, options) {
return this.ec.sign(msg, this, enc, options);
};
ec.sign
EC.prototype.sign = function sign(msg, key, enc, options) {
if (typeof enc === 'object') {
options = enc;
enc = null;
}
if (!options)
options = {};
key = this.keyFromPrivate(key, enc);
msg = this._truncateToN(new BN(msg, 16));
// Zero-extend key to provide enough entropy
var bytes = this.n.byteLength();
var bkey = key.getPrivate().toArray('be', bytes);
// Zero-extend nonce to have the same byte size as N
var nonce = msg.toArray('be', bytes);
// Instantiate Hmac_DRBG
var drbg = new HmacDRBG({
show original
The README for indutny/elliptic states that the implementation uses RFC6979 to generate deterministic “k” values (the logic used in “3) ec.sign”): elliptic/README.md at 43ac7f230069bd1575e1e4a58394a512303ba803 · indutny/elliptic · GitHub
To demonstrate that both AvalancheGo and AvalancheJS produce RFC6979-compliant signatures, we also added compliance tests to both repos using the test cases provided in this BitcoinTalk thread: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms (RFC 6979) .
You can find the compliance tests here:
Hope that helps with your wallet development (and anyone else who may be doing so)! Please reach out if you have any additional questions.
3 Likes
If you’d like to verify any of this yourself without running any code locally, visit the site Paul Miller — Noble cryptography (which runs a hosted version of GitHub - paulmillr/noble-secp256k1: Fastest JS implementation of secp256k1. Independently audited, high-security, 0-dependency ECDSA & Schnorr signatures. , a popular and audited secp256k1 library that produces RFC6979-compliant signatures).
You can then select any one of the passing compliance tests from the AvalancheGo PR (Add rfc6979 test vectors by StephenButtolph · Pull Request #1222 · ava-labs/avalanchego · GitHub ). In this case, we select the first one:
You can then put the corresponding private key and message into the website shared above (Paul Miller — Noble cryptography ) and it will produce an identical signature (see the “compact” signature response): 33a69cd2065432a30f3d1ce4eb0d59b8ab58c74f27c41a7fdb5696ad4e6108c96f807982866f785d3f6418d24163ddae117b7db4d5fdf0071de069fa54342262
1 Like
