A vast majority of online services nowadays are built atop centralized systems, in which data is stored and managed by a trusted party. However, centralization brings significant drawbacks, such as a central point of attack, poor transparency, and poor auditability. Recent success in the field of blockchain has led to great interest in secure decentralized ledgers because they enable a set of heterogeneous parties to reach a consensus on the validity of data on ledgers without relying on centralized service providers. In addition, decentralized ledgers often promise a foundation of decentralized trust and auditability for applications. Unfortunately, the benefits of decentralized ledgers often come at the expense of privacy and efficiency.In this dissertation, I will present my work on secure and efficient decentralized ledgers. I will show how to improve the efficiency and privacy of decentralized ledgers, which involves the design of new cryptographic tools such as zero-knowledge proofs and authenticated data structures. I will also show how to leverage decentralized ledgers to build practical and secure systems for real-world applications such as the Internet of Things and file sharing services.