[security] How can bcrypt have built-in salts?

Coda Hale's article "How To Safely Store a Password" claims that:

bcrypt has salts built-in to prevent rainbow table attacks.

He cites this paper, which says that in OpenBSD's implementation of bcrypt:

OpenBSD generates the 128-bit bcrypt salt from an arcfour (arc4random(3)) key stream, seeded with random data the kernel collects from device timings.

I don't understand how this can work. In my conception of a salt:

• It needs to be different for each stored password, so that a separate rainbow table would have to be generated for each
• It needs to be stored somewhere so that it's repeatable: when a user tries to log in, we take their password attempt, repeat the same salt-and-hash procedure we did when we originally stored their password, and compare

When I'm using Devise (a Rails login manager) with bcrypt, there is no salt column in the database, so I'm confused. If the salt is random and not stored anywhere, how can we reliably repeat the hashing process?

In short, how can bcrypt have built-in salts?

This is from PasswordEncoder interface documentation from Spring Security,

 * @param rawPassword the raw password to encode and match
 * @param encodedPassword the encoded password from storage to compare with
 * @return true if the raw password, after encoding, matches the encoded password from
 * storage
 */
boolean matches(CharSequence rawPassword, String encodedPassword);

Which means, one will need to match rawPassword that user will enter again upon next login and matches it with Bcrypt encoded password that's stores in database during previous login/registration.

I believe that phrase should have been worded as follows:

bcrypt has salts built into the generated hashes to prevent rainbow table attacks.

The bcrypt utility itself does not appear to maintain a list of salts. Rather, salts are generated randomly and appended to the output of the function so that they are remembered later on (according to the Java implementation of bcrypt). Put another way, the "hash" generated by bcrypt is not just the hash. Rather, it is the hash and the salt concatenated.

To make things even more clearer,

Registeration/Login direction ->

The password + salt is encrypted with a key generated from the: cost, salt and the password. we call that encrypted value the cipher text. then we attach the salt to this value and encoding it using base64. attaching the cost to it and this is the produced string from bcrypt:

$2a$COST$BASE64

This value is stored eventually.

What the attacker would need to do in order to find the password ? (other direction <- )

In case the attacker got control over the DB, the attacker will decode easily the base64 value, and then he will be able to see the salt. the salt is not secret. though it is random. Then he will need to decrypt the cipher text.

What is more important : There is no hashing in this process, rather CPU expensive encryption - decryption. thus rainbow tables are less relevant here.