Client Puzzles and HMAC
Here is a small scheme how this works :

 Server         Client
   |              |
   |     r,n      |  S: Find s such as HMAC(s,r) = xxxx0000
   |  ==========&gt; |   
   |              |  C: *compute HMAC(0,r) = 123456789*
   |              |  C: *compute HMAC(1,r) = 124687946*
   |              |  C: *compute HMAC(2,r) = 164946518*
   |              |  C: *compute HMAC(3,r) = 165498451*
   |              |  ...
   |              |  C: *compute HMAC(42,r) = 16540000*
   |              |  
   |    s = 42    |  C: Found it ! s is 42
   | &lt;=========== | 
   |              |  S: *compute HMAC(42,r) = 16540000*
   |      OK      |  S: Ok, access granted for you !
   |  ==========&gt; |   
   V              V  


As an example, lets assume you want only the last digit to be 0.
What are the chances if you were to compute the HMAC for a random number ? well $\frac{1}{10}$. So if you try 10 random numbers, the chances that you got at least one HMAC ending with 0 is pretty decent:

$P = 1 - ((1-\frac{1}{10})^{10}) \approx 65\%$.

However, the more 0 you ask at the end the harder it will be to find a solution. e.g. if you were to ask for 4 zeroes at then end, the chances that you would find $s$ after 1000 trials are :

$P = 1 - ((1-\frac{1}{10000})^{1000}) \approx 9,5\%$.

And after 10000 trials :

$P = 1 - ((1-\frac{1}{10000})^{10000}) \approx 63\%$.

Thus simply by increasing the number of zeros demanded, you increase a lot the time required to find the solution.

Why it is "secure", because you change the $r$ at each tentative. Therefore the client cannot pre-compute the solution.