Decentralized systems are built from a set of coordinating independent services. Yet these services might not trust each other, making it difficult to maintain the integrity of the whole application. This dissertation explores two different approaches to achieving provable integrity guarantees in such systems. The first technique, realized in Solidus, applies cryptographic tools to provably preserve the integrity of a blockchain-based financial transaction system while hiding the sender, receiver, and value of each transaction. The second complements the cryptographic approach by showing how to achieve strong integrity guarantees for realistic systems using language-based Information Flow Control (IFC). Traditional IFC systems only provide strong integrity guarantees in the absence of endorsement---treating inputs as more trusted than their source---but endorsement is necessary in real-world systems. This work classifies two ways in which unrestricted endorsements can compromise system integrity if attackers violate implicit assumptions. In both cases, IFC ideas help define security and support language-based rules to provably eliminate all attacks in the class.