<p>This will be less of a theoretical answer and more of practical guidance; while developing Secp256k1 or Bitcoin libraries, I always found the following table handy:</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>y-parity</th>
<th>x-order</th>
<th>compression</th>
<th>recovery id</th>
<th><code>v</code></th>
</tr>
</thead>
<tbody>
<tr>
<td>even</td>
<td>less than <code>n</code></td>
<td>false</td>
<td>0</td>
<td>27</td>
</tr>
<tr>
<td><em>odd</em></td>
<td>less than <code>n</code></td>
<td>false</td>
<td>1</td>
<td>28</td>
</tr>
<tr>
<td>even</td>
<td><em>more</em> than <code>n</code></td>
<td>false</td>
<td>2</td>
<td>29</td>
</tr>
<tr>
<td><em>odd</em></td>
<td><em>more</em> than <code>n</code></td>
<td>false</td>
<td>3</td>
<td>30</td>
</tr>
<tr>
<td>even</td>
<td>less than <code>n</code></td>
<td><em>true</em></td>
<td>0</td>
<td>31</td>
</tr>
<tr>
<td><em>odd</em></td>
<td>less than <code>n</code></td>
<td><em>true</em></td>
<td>1</td>
<td>32</td>
</tr>
<tr>
<td>even</td>
<td><em>more</em> than <code>n</code></td>
<td><em>true</em></td>
<td>2</td>
<td>33</td>
</tr>
<tr>
<td><em>odd</em></td>
<td><em>more</em> than <code>n</code></td>
<td><em>true</em></td>
<td>3</td>
<td>34</td>
</tr>
</tbody>
</table>
</div>
<p>let me explain the columns:</p>
<ul>
<li><code>y-parity</code> or often just <code>parity</code> describes whether the <code>y</code>-coordinate of the public key point <code>R(x, y)</code> is even. this is important because in most cases, the signature only contains <code>r = R.x</code> and not <code>R.y</code>. This speeds up signature recovery. (Secp256k1)</li>
<li><code>x-order</code> is a super rare edge-case where a point's <code>x</code>-coordinate is actually above the order of the curve <code>n</code>. In 99.99999999% of the cases, this is false. (Secp256k1)</li>
<li><code>compression</code> is just an indicator whether you want a compressed or an uncompressed public key. (Bitcoin)</li>
<li><code>recovery_id</code> just indicates which of the four potential point's <code>y</code>-coordinates is to be used. (Secp256k1)</li>
<li><code>v</code> is how we encode this value. For uncompressed keys we use <code>v = recovery_id + 27</code> and for compressed <code>v = recovery_id + 31</code>. (Bitcoin)</li>
</ul>
<p>If you want to understand how this works for Ethereum, you would have to read <a href="https://github.com/ethereum/EIPs/blob/master/EIPS/eip-155.md" rel="nofollow noreferrer">EIP-155</a> which also introduces an additional variable of <code>chain_id</code> for replay protection: <code>v = 2 * chain_id + 35 + recovery_id</code>. (Ethereum)</p>
<blockquote>
<p>What I am struggling with is how do we determine that <code>num</code> number?</p>
</blockquote>
<p>That's the recovery ID from the table above.</p>

CC BY-SA 4.0
2022-01-09T12:40:32.273Z
2022-01-09T12:40:32.273Z
q9f
<p>There may be another method to determine the Recovery ID(rec_id). Since the Recovery ID can only have 4 possible values(0/1/2/3), if you already have the message to sign, public key, and signature, you can try each Recovery ID value and determine which one yields the correct public key value.</p>
<p>There is already an implementation of this function called &quot;ecRecover&quot;. For example, in Python, you can use <code>ecdsa_raw_recover</code> from <code>py_ecc</code> library(<a href="https://github.com/ethereum/py_ecc/blob/v6.0.0/py_ecc/secp256k1/secp256k1.py#L154" rel="nofollow noreferrer">source code</a>). This function allows you to derive possible public key from the given Recovery ID:</p>
<pre class="lang-python prettyprint-override"><code>def ecdsa_raw_recover(msghash: bytes, vrs: Tuple[int, int, int]) -&gt; &quot;PlainPoint2D&quot;:
    v, r, s = vrs
    if not (27 &lt;= v &lt;= 34):
        raise ValueError(&quot;%d must in range 27-31&quot; % v)
    x = r
    xcubedaxb = (x * x * x + A * x + B) % P
    beta = pow(xcubedaxb, (P + 1) // 4, P)
    y = beta if v % 2 ^ beta % 2 else (P - beta)
    # If xcubedaxb is not a quadratic residue, then r cannot be the x coord
    # for a point on the curve, and so the sig is invalid
    if (xcubedaxb - y * y) % P != 0 or not (r % N) or not (s % N):
        raise ValueError(&quot;sig is invalid, %d cannot be the x coord for point on curve&quot; % r)
    z = bytes_to_int(msghash)
    Gz = jacobian_multiply(cast(&quot;PlainPoint3D&quot;, (Gx, Gy, 1)), (N - z) % N)
    XY = jacobian_multiply(cast(&quot;PlainPoint3D&quot;, (x, y, 1)), s)
    Qr = jacobian_add(Gz, XY)
    Q = jacobian_multiply(Qr, inv(r, N))
    Q_jacobian = from_jacobian(Q)

    return Q_jacobian
</code></pre>

CC BY-SA 4.0
2023-08-04T02:08:13.717Z
2023-08-04T02:08:13.717Z
DGideas
<p>FWIW this is what I have found regarding this question. Basically there are two ways of finding what libraries call &quot;recid&quot; or recovery ID. Most of them use the first method but there is another way:</p>
<h1>Method 1:</h1>
<ul>
<li>Only requires <code>r</code> and <code>s</code> so it can be performed by anyone as long as you have the signature and the &quot;message&quot; that was signed.</li>
<li>It is so much slower because it has 3 scalar multiplication and based on cofactor of the elliptic curve used the whole operation may be repeated 2*(h+1) times, which is up to 4 times for bitcoin with secp256k1 curve (99% of the time it is 1 or 2 times).</li>
</ul>
<p>The steps are explained in section 4.1.6 of <a href="http://www.secg.org/sec1-v2.pdf" rel="nofollow noreferrer">SEC:1</a>, I won't repeat them here.</p>
<p>To find <code>recid</code> you check the calculated public key with the given public key or hash of it and report number of rejected public keys as <code>recid</code>. For example if <code>x=r+(0*order)</code> and <code>Q</code> was used then <code>recid=0</code> and if <code>-Q</code> was used then <code>recid=1</code> and so on.</p>
<h1>method 2:</h1>
<ul>
<li>It requires full <code>r</code> or <code>R=(x<sub>R</sub>, y<sub>R</sub>)</code> so it can only be done while signing (requires having the private key).</li>
<li>It is much faster because there is no additional calculations. It just needs value checks which are fast.</li>
<li>This is usually referred to as <code>v</code> in libraries</li>
</ul>
<p><code>byte v = if(R.X &gt; curve.N) then 2 else 0) | (if R.Y.IsEven then 0 else 1);</code></p>
<p>Basically it is check to see if <code>x<sub>R</sub></code> is bigger than curve order (N) and whether <code>y<sub>R</sub></code> is even or odd. Something that should not be forgotten is a &quot;flip&quot; that is performed based on <code>s</code> and whether <code>s</code> was used in the signature or <code>-s</code></p>
<p><code>if s &gt; curve.N/2 then v^=1 else do nothing</code></p>
<p>** Note that in the end you need to calculate the following:<br />
<code>recid = 27 + v + (if compressed 4 else 0)</code></p>

CC BY-SA 4.0
2018-12-22T11:16:40.037Z
IMO you should also accept this as the answer
arubi
CC BY-SA 4.0
2018-12-22T11:00:50.043Z
2018-12-22T11:00:50.043Z
2020-06-16T11:10:03.350Z
Coding Enthusiast
<p>I do realize that in bitcoin when we return the signature result for signing a message the first byte includes information for recovering the public key required for verification using a formula like this: </p>

<pre><code>27 + (4 if comp. 0 if not) + (0&lt;=num&lt;=3)
</code></pre>

<p>What I am struggling with is how do we determine that <code>num</code> number?
According to section 4.1.6 of <a href="http://www.secg.org/sec1-v2.pdf" rel="noreferrer">SEC:1</a> for recovering public keys:</p>

<ol>
<li><code>x = r + jn</code></li>
<li>Calculate <code>Q</code> based on <code>R</code> if invalid move to next</li>
<li>Calculate <code>Q</code> based on <code>-R</code></li>
</ol>

<p>Since j (cofactor of secp256k1) is 0 and 1 and there are two values for R. So there should be 4 possible public keys. Is <code>num</code> the number of public keys that we rejected before reaching the correct one? Because that is the only explanation that I can come up with based on comparisons I have made between signatures generated using Electrum and public key recovery I have done myself using SEC1.</p>

<p><strong>Bonus question</strong>: Why was 27 chosen?</p>

CC BY-SA 4.0
2018-12-19T12:34:22.983Z
I'm not sure what `num` means there either, but I wrote this a while ago which might interest you.  It explains exactly how to encode and decode the recid byte :
https://github.com/fivepiece/sign-verify-message/blob/master/signverifymessage.md#encoding-of-a-recoverable-signature
arubi
CC BY-SA 4.0
2018-12-19T13:03:30.717Z
@arubi Thanks for the reply. Based on your comment and another answer I've received on bitcointalk, I believe the main cause of my confusion is that I was thinking you find that `num` _after_ signing and finding `r,s`. But it seems like you must find it _during_ using the y coordinate of `r` which is discarded and doesn't come out of sign function. Now I am trying to figure out the details...
Coding Enthusiast
CC BY-SA 4.0
2018-12-19T22:58:26.230Z
Dupe https://bitcoin.stackexchange.com/a/38909
dave_thompson_085
<signature><ecdsa><message-signing>
How to determine first byte (recovery ID) for signatures (message signing)?
Coding Enthusiast
# How to determine first byte (recovery ID) for signatures (message signing)?

(Asked by: username_0 on 2018-12-19)

I do realize that in bitcoin when we return the signature result for signing a message the first byte includes information for recovering the public key required for verification using a formula like this:

```
27 + (4 if comp. 0 if not) + (0<=num<=3)

```

What I am struggling with is how do we determine that `num` number?
According to section 4.1.6 of [SEC:1](http://www.secg.org/sec1-v2.pdf) for recovering public keys:

1. `x = r + jn`
2. Calculate `Q` based on `R` if invalid move to next
3. Calculate `Q` based on `-R`

Since j (cofactor of secp256k1) is 0 and 1 and there are two values for R. So there should be 4 possible public keys. Is `num` the number of public keys that we rejected before reaching the correct one? Because that is the only explanation that I can come up with based on comparisons I have made between signatures generated using Electrum and public key recovery I have done myself using SEC1.

**Bonus question**: Why was 27 chosen?

**Tags:** signature, ecdsa, message-signing

> **Comments:**
> **username_1**: I'm not sure what `num` means there either, but I wrote this a while ago which might interest you.  It explains exactly how to encode and decode the recid byte : https://github.com/fivepiece/sign-verify-message/blob/master/signverifymessage.md#encoding-of-a-recoverable-signature  
> **username_0**: @username_1 Thanks for the reply. Based on your comment and another answer I've received on bitcointalk, I believe the main cause of my confusion is that I was thinking you find that `num` _after_ signing and finding `r,s`. But it seems like you must find it _during_ using the y coordinate of `r` which is discarded and doesn't come out of sign function. Now I am trying to figure out the details...  
> **username_2**: Dupe https://bitcoin.stackexchange.com/a/38909  

---

## 3 answers

### Answer by username_0 on 2018-12-22. Score: 6 | Accepted answer

FWIW this is what I have found regarding this question. Basically there are two ways of finding what libraries call "recid" or recovery ID. Most of them use the first method but there is another way:

# Method 1:

* Only requires `r` and `s` so it can be performed by anyone as long as you have the signature and the "message" that was signed.
* It is so much slower because it has 3 scalar multiplication and based on cofactor of the elliptic curve used the whole operation may be repeated 2\*(h+1) times, which is up to 4 times for bitcoin with secp256k1 curve (99% of the time it is 1 or 2 times).

The steps are explained in section 4.1.6 of [SEC:1](http://www.secg.org/sec1-v2.pdf), I won't repeat them here.

To find `recid` you check the calculated public key with the given public key or hash of it and report number of rejected public keys as `recid`. For example if `x=r+(0*order)` and `Q` was used then `recid=0` and if `-Q` was used then `recid=1` and so on.

# method 2:

* It requires full `r` or `R=(xR, yR)` so it can only be done while signing (requires having the private key).
* It is much faster because there is no additional calculations. It just needs value checks which are fast.
* This is usually referred to as `v` in libraries

`byte v = if(R.X > curve.N) then 2 else 0) | (if R.Y.IsEven then 0 else 1);`

Basically it is check to see if `xR` is bigger than curve order (N) and whether `yR` is even or odd. Something that should not be forgotten is a "flip" that is performed based on `s` and whether `s` was used in the signature or `-s`

`if s > curve.N/2 then v^=1 else do nothing`

\*\* Note that in the end you need to calculate the following:  
`recid = 27 + v + (if compressed 4 else 0)`

> **Comments:**
> **username_1**: IMO you should also accept this as the answer  

---

### Answer by username_3 on 2022-01-09. Score: 2

This will be less of a theoretical answer and more of practical guidance; while developing Secp256k1 or Bitcoin libraries, I always found the following table handy:

| y-parity | x-order | compression | recovery id | `v` |
| --- | --- | --- | --- | --- |
| even | less than `n` | false | 0 | 27 |
| *odd* | less than `n` | false | 1 | 28 |
| even | *more* than `n` | false | 2 | 29 |
| *odd* | *more* than `n` | false | 3 | 30 |
| even | less than `n` | *true* | 0 | 31 |
| *odd* | less than `n` | *true* | 1 | 32 |
| even | *more* than `n` | *true* | 2 | 33 |
| *odd* | *more* than `n` | *true* | 3 | 34 |

let me explain the columns:

* `y-parity` or often just `parity` describes whether the `y`-coordinate of the public key point `R(x, y)` is even. this is important because in most cases, the signature only contains `r = R.x` and not `R.y`. This speeds up signature recovery. (Secp256k1)
* `x-order` is a super rare edge-case where a point's `x`-coordinate is actually above the order of the curve `n`. In 99.99999999% of the cases, this is false. (Secp256k1)
* `compression` is just an indicator whether you want a compressed or an uncompressed public key. (Bitcoin)
* `recovery_id` just indicates which of the four potential point's `y`-coordinates is to be used. (Secp256k1)
* `v` is how we encode this value. For uncompressed keys we use `v = recovery_id + 27` and for compressed `v = recovery_id + 31`. (Bitcoin)

If you want to understand how this works for Ethereum, you would have to read [EIP-155](https://github.com/ethereum/EIPs/blob/master/EIPS/eip-155.md) which also introduces an additional variable of `chain_id` for replay protection: `v = 2 * chain_id + 35 + recovery_id`. (Ethereum)

> What I am struggling with is how do we determine that `num` number?

That's the recovery ID from the table above.


---

### Answer by username_4 on 2023-08-04. Score: 0

There may be another method to determine the Recovery ID(rec\_id). Since the Recovery ID can only have 4 possible values(0/1/2/3), if you already have the message to sign, public key, and signature, you can try each Recovery ID value and determine which one yields the correct public key value.

There is already an implementation of this function called "ecRecover". For example, in Python, you can use `ecdsa_raw_recover` from `py_ecc` library([source code](https://github.com/ethereum/py_ecc/blob/v6.0.0/py_ecc/secp256k1/secp256k1.py#L154)). This function allows you to derive possible public key from the given Recovery ID:

```python
def ecdsa_raw_recover(msghash: bytes, vrs: Tuple[int, int, int]) -> "PlainPoint2D":
    v, r, s = vrs
    if not (27 <= v <= 34):
        raise ValueError("%d must in range 27-31" % v)
    x = r
    xcubedaxb = (x * x * x + A * x + B) % P
    beta = pow(xcubedaxb, (P + 1) // 4, P)
    y = beta if v % 2 ^ beta % 2 else (P - beta)
    # If xcubedaxb is not a quadratic residue, then r cannot be the x coord
    # for a point on the curve, and so the sig is invalid
    if (xcubedaxb - y * y) % P != 0 or not (r % N) or not (s % N):
        raise ValueError("sig is invalid, %d cannot be the x coord for point on curve" % r)
    z = bytes_to_int(msghash)
    Gz = jacobian_multiply(cast("PlainPoint3D", (Gx, Gy, 1)), (N - z) % N)
    XY = jacobian_multiply(cast("PlainPoint3D", (x, y, 1)), s)
    Qr = jacobian_add(Gz, XY)
    Q = jacobian_multiply(Qr, inv(r, N))
    Q_jacobian = from_jacobian(Q)

    return Q_jacobian

```


---

