[jude-]

Blockstack engineer here.

Just providing a bit of background. The private key is _not_ stored on the blockchain; only the hash of the public key is. And even then, there are a couple of layers of indirection between the Bitcoin transaction itself and the storage of your (app-specific) public key. Specifically, one Bitcoin transaction registers a batch of ~160 username/public-key-hash/profile-storage-URL bindings, and from there, the profile storage URL resolves to the user's list of application-specific public keys and application-specific storage URLs.

Pertaining to questions of scalability in other threads, 160 usernames/transaction, when operated at 8 250-byte transactions/block (about 3.4% of Bitcoin's capacity), works out to ~184,000 user registrations/day (about the same as Twitter). Moreover, usernames can be resolved to public keys and storage URLs while the underlying transaction is being confirmed, so users don't have to wait to start using applications. All other user state is stored off-chain in the user's chosen storage provider, managed by a Gaia hub (Gaia being Blockstack's storage system: https://github.com/blockstack/gaia).

EDIT: clarifications