How do we get the recid / v from a signature, or produce a signature with one?

[CodeForcer]

The bitcoinjs-message library use the standard secp256k1 library, which returns R/S/V as parameters as part of the signature.

However, the tiny-secp256k1 library, used in bitcoinjs, doesn't appear to return the V or Recid from signatures. This creates some issues when passing bitcoinjs Signers into bitcoinjs-message, as bitcoinjs-message needs a recovery param (I presume this is the Recid).

If there a cryptographic method by which we can use this library to get a V/Recid value from a signature + hash, or to get the V/Recid whilst performing a signing?

Thanks!

[junderw]

This library does not need recid, so there are no methods that return or calculate it.

The two bits of the recid are:

LSB = "is Y value for signature r point odd?" MSB = "is X value for signature r point >= n (order)?"

MSB is almost always 0, so 99.9...% of recid will be integer of 0 or 1

[junderw]

To make it a little easier to understand, here's how it would be calculated in the current pure JS code.

ie. for the JS: https://github.com/bitcoinjs/tiny-secp256k1/blob/5a311f1fbfc4f7e3b619d1314f830ec19f405956/js.js#L188-L205

diff --git a/js.js b/js.js
index 5e0fd45..6382476 100644
--- a/js.js
+++ b/js.js
@@ -185,7 +185,7 @@ function __sign (hash, x, addData) {
   const d = fromBuffer(x)
   const e = fromBuffer(hash)

-  let r, s
+  let r, s, recid
   const checkSig = function (k) {
     const kI = fromBuffer(k)
     const Q = G.mul(kI)
@@ -201,6 +201,10 @@ function __sign (hash, x, addData) {
       .umod(n)
     if (s.isZero() === 0) return false

+    const isOddY = Q.y.isOdd()
+    const isHighX = Q.x.cmp(n) >= 0
+    recid = (isHighX << 1) | (isOddY << 0)
+
     return true
   }

@@ -214,7 +218,10 @@ function __sign (hash, x, addData) {
   const buffer = Buffer.allocUnsafe(64)
   toBuffer(r).copy(buffer, 0)
   toBuffer(s).copy(buffer, 32)
-  return buffer
+  return {
+    signature: buffer,
+    recovery: recid,
+  }
 }

 function verify (hash, q, signature, strict) {

[junderw]

Also, in the verify function you recreate the R point, so you would be able to calculate the recid if you have the public key and the signature.

[junderw]

This is what it looks like to get the recid during the verify function.

diff --git a/js.js b/js.js
index 5e0fd45..58e4dc2 100644
--- a/js.js
+++ b/js.js
@@ -255,6 +255,10 @@ function verify (hash, q, signature, strict) {
   // 1.4.5 (cont.) Enforce R is not at infinity
   if (R.isInfinity()) return false

+  const isOddY = R.y.isOdd()
+  const isHighX = R.x.cmp(n) >= 0
+  const recid = (isHighX << 1) | (isOddY << 0)
+
   // 1.4.6 Convert the field element R.x to an integer
   const xR = R.x

@@ -262,7 +266,11 @@ function verify (hash, q, signature, strict) {
   const v = xR.umod(n)

   // 1.4.8 If v = r, output "valid", and if v != r, output "invalid"
-  return v.eq(r)
+  const isValid = v.eq(r)
+  return {
+    verified: isValid,
+    recovery: isValid ? recid : null,
+  }
 }

 module.exports = {

[CodeForcer]

Thanks for your help @junderw. In particular your last example got me through my blocker on this. I will share my code for extending a BitcoinJs library signer into a BitcoinJs-message signer, in case it helps any other developers working on this particular issue:

export class BitcoinMessageSigner extends BitcoinSigner {
  sign(payload) {
    const signature = super.sign(payload, true)

    const recovery = this.recidFromSig(payload, this.publicKey, signature)

    return {
      signature,
      recovery,
    }
  }

  recidFromSig(payload, publicKey, signature) {
    const BN = require('bn.js')
    const secp256k1 = new ec('secp256k1')

    const n = secp256k1.curve.n
    const G = secp256k1.curve.g

    const Q = secp256k1.curve.decodePoint(publicKey)

    const r = new BN(signature.slice(0, 32))
    const s = new BN(signature.slice(32, 64))

    const e = new BN(payload)

    const sInv = s.invm(n)

    const u1 = e.mul(sInv).umod(n)
    const u2 = r.mul(sInv).umod(n)

    const R = G.mulAdd(u1, Q, u2)

    const isOddY = R.y.isOdd()
    const isHighX = R.x.cmp(n) >= 0
    const recid = (isHighX << 1) | (isOddY << 0)

    return recid
  }
}

I'm still code-cleaning, but the above example is working.

[junderw]

Be careful, as that is very slow.

You are using Signer because you have some sort of native implementation you're calling into, correct?

In which case you should get your native implementation to have a private method that returns the signature AND recid (in one go) and your key Signer class will throw away the recid and the message Signer class will keep it.

If not, and the private key is being managed in a Buffer in the JavaScript memory... then it is easier to just pass the privateKey Buffer to the message sign function.