Strictly speaking they are stored in an app called "Contacts Storage" on your phone. Unless you have told it not to they will also be synced with your Gmail account. So the answer to "on device or in cloud?" is "both?", but it's the local copy that the phone used.
(Keeping them in the cloud only would be silly and wasteful, since you'd need a data connection to access them. But I can't say I'd put it past Google, who have often behaved as if they think everyone is always connected and has infinite data, to come up with such a stupid idea

).