It shouldn't be hard to make the actual bits themselves live on the blockchain. It's trivial to make values so that their hashes have certain bits set to 0 or 1

It shouldn't be hard to make the actual bits themselves live on the blockchain. It's trivial to make values so that their hashes have certain bits set to 0 or 1 as you chose (as long as you only use a few bits per hash)...