Provided is a process that establishes user identities within a decentralized data store, like a blockchain. A user's mobile device may establish credential values within a trusted execution environment of the mobile device. Representations of those credentials may be generated on the mobile device and transmitted for storage in association with an identity of the user established on the blockchain. Similarly, one or more key-pairs may be generated or otherwise used by the mobile device for signatures and signature verification. Private keys may remain resident on the device (or known and input by the user) while corresponding public keys may be stored in associated with the user identity on the blockchain. A private key is used to sign representations of credentials and other values as a proof of knowledge of the private key and credential values for authentication of the user to the user identity on the blockchain.