before allowing the creation of a bounded number of valid genesis pseudonyms. Decentralized Anonymous Credentials[@cryptoeprint:2013:622] was first to show how to decentralise the issuance of anonymous credentials and integrate them within a blockchain (i.e., Bitcoin), but they do not re-use previously existing credentials and they still rely on Proof-of-Work for Sybil-resistance. Decentralized Blacklistable Anonymous Credentials with Reputation[@cryptoeprint:2017:389] introduce blacklistable reputation on blockchains, but users must also publish their real-world identity (i.e., non-anonymous). QuisQuis[@quisquis] introduces the novel primitive of updatable public keys in order to provide anonymous transactions in cryptocurrencies, but it doesn’t consider their Sybil-resistance. DarkID[@darkID] is a practical implementation of an anonymous decentralised identification system, but requires non-anonymous pre-authentication and doesn’t consider Sybil-resistance. A previous work[@whoami] on secure identity registration on distributed ledgers achieved anonymity from a credential issuer, but the pre-authentication is non-anonymous, it doesn’t consider Sybil-resistance and it doesn’t re-use real-world cryptographic credentials. Recently, anonymous credentials on standard smart cards have been proved practical[@cryptoeprint:2019:460], but in a different setting where the credential issuer and the verifier are the same entity.

Previous works have also considered anonymous PKIs: for example, generating pseudonyms[@anonymousPKI] using a Certificate Authority and a separate Private Certificate Authority; however, this architecture is not coherent 