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 Blockchain Name System, built on top of a cryptocurrency blockchain (Namecoin).