How to check Cookie Token against bcrypt-hashed Token in DB when using Persistent Login Cookies?

Question

In this popular solution for Persistent Login Cookies which involves generating a random 128-bit "token" to be saved in the user's Cookie, Jens Roland recommends:

And DO NOT STORE THE PERSISTENT LOGIN COOKIE (TOKEN) IN YOUR DATABASE, ONLY A HASH OF IT! The login token is Password Equivalent, so if an attacker got his hands on your database, he/she could use the tokens to log in to any account, just as if they were cleartext login-password combinations. Therefore, use strong salted hashing (bcrypt / phpass) when storing persistent login tokens.

But how do you check the Cookie Token against the bcrypted Token in the DB to confirm the Cookie login is valid, when bcrypting the Cookie Token will always yield a different result (since bcrypting always uses a random salt)?

In other words, you can't just bcrypt the Cookie Token and look for a match in the DB since you will never find one, so how do you actually match it against the hashed version in the DB as per the recommended solution ("The server keeps a table of number->username associations, which is looked up to verify the validity of the cookie.")?

Edit:

Keep in mind that as per the recommended solution linked to above, a single user can have multiple Cookies/Tokens for different devices. I mention that because an answer was submitted (that has since been deleted) that assumed it was only one Token per user.

Answer 1

As mentioned in the previous answer, bcrypt stores the random salt as part of the hash, so each token entry in your database will include both random_salt and hashed_token.

When authenticating a 'remember me' login cookie (which should consist of userid and token), you will need to iterate over each of the token entries for that userid (usually just one entry, never more than a handful) and check each one separately using the stored random salt:

foreach (entry in stored_tokens_for_user) {
    if (entry.hashed_token == bcrypt(cookie.token, entry.random_salt))
        return true;
}
return false;

(if your database has built-in support for bcrypt as part of the query syntax, you can create a prepared statement to do this for you)