In the past years cryptocurrency blockchains (like Bitcoin and Namecoin) have seen significant adoption with the promise of using such blockchains as general-purpose databases and/or key-value stores. Cryptocurrency blockchains provide a zero-trust infrastructure, where users can securely store and retrieve information while providing security guarantees that only the owner of a particular private-key can write/modify the data. In theory, many decentralized services/application can be built using cryptocurrency blockchains as key-value stores. However, the area is relatively new and rapidly evolving with little production experience/data available to guide design tradeoffs. In this talk, we describe our experience of operating a large real-world deployment of a decentralized naming service, called Openname, built on top of a cryptocurrency blockchain (Namecoin). We present the various challenges that we had to overcome while registering/updating over 30,000 users on the blockchain and discuss how our experience informed the design of a new blockchain-based key-value store, called Blockstore. All of our code is available as open-source at http://github.com/openname.