user9382: Peter Wuille recently explained how ECDSA pubkey recovery is done, in response to my question.
So it's basically that for a given base64 signature, the value v in v,r,s provides the specific coordinates, hence the recid (recovery ID).
Example from BitcoinCore test vectors:
> sig =
> "H8PgOb/liZzt3QQHJn9kLBqH7E/i+SC6JTwYGtdNdOjnXzFqXnHMZqP7oZ1wb1QiQ3H/kF8xC9Yx7pK9ddlx8TA"
> addr = "1K5Z1nxN4mjUgCLpSXMRkeZxuAMpbn2CQB" wif =
> "KwfJTiKdcjNMjBu4ksgGd21EZXz6JomoZNbirP3nfd3K9ZMXMEUi"
> 
> v,r,s = vrs = (31,
> 88597177789312009809148107221292570613390338668815747761545214128303675599079L,
> 43057030252916568867525408201971649068117337291455262356277580652864892694832L)

The value of v is 27 + recid for uncompressed keys and 31 + recid for compressed keys.
Ive run a Python loop using pybitcointools which signs a message using a random key, and I've yet to ever see v=29 or v=30. Why is this? Is it by design, or is it just a very low probability event? 

user208: For random signatures, it is an extremely low probability event. Around 1 in 2128, so it will likely never ever actually happen.
However, you can easily construct a valid signature that has one of those, and the recovery algorithm will give you an actual public key for it. It just won't be a public key anyone actually knows the secret key for.

9382: <p>Peter Wuille recently explained how ECDSA pubkey recovery is done, <a href="https://bitcoin.stackexchange.com/questions/38351/ecdsa-v-r-s-what-is-v">in response to my question</a>.</p>

<p>So it's basically that for a given base64 signature, the value <code>v</code> in <code>v,r,s</code> provides the specific coordinates, hence the <code>recid</code> (recovery ID).</p>

<p>Example from <a href="https://github.com/petertodd/python-bitcoinlib/blob/master/bitcoin/tests/data/signmessage.json" rel="nofollow noreferrer">BitcoinCore test vectors</a>:</p>

<pre><code>&gt; sig =
&gt; "H8PgOb/liZzt3QQHJn9kLBqH7E/i+SC6JTwYGtdNdOjnXzFqXnHMZqP7oZ1wb1QiQ3H/kF8xC9Yx7pK9ddlx8TA"
&gt; addr = "1K5Z1nxN4mjUgCLpSXMRkeZxuAMpbn2CQB" wif =
&gt; "KwfJTiKdcjNMjBu4ksgGd21EZXz6JomoZNbirP3nfd3K9ZMXMEUi"
&gt; 
&gt; v,r,s = vrs = (31,
&gt; 88597177789312009809148107221292570613390338668815747761545214128303675599079L,
&gt; 43057030252916568867525408201971649068117337291455262356277580652864892694832L)
</code></pre>

<p>The value of v is <code>27 + recid</code> for uncompressed keys and <code>31 + recid</code> for compressed keys.</p>

<p>Ive run a Python loop using <a href="https://github.com/vbuterin/pybitcointools" rel="nofollow noreferrer">pybitcointools</a> which signs a message using a random key, and I've yet to ever see <code>v=29</code> or <code>v=30</code>. Why is this? Is it by design, or is it just a very low probability event? </p>
 208: <p>For random signatures, it is an extremely low probability event. Around 1 in 2<sup>128</sup>, so it will likely never ever actually happen.</p>

<p>However, you can easily construct a valid signature that has one of those, and the recovery algorithm will give you an actual public key for it. It just won't be a public key anyone actually knows the secret key for.</p>
