This is a thesis in two parts. First, we re-visit the foundations of consensus protocols, arguing that despite 50 years of research, there is room to make them simpler, more secure, and more efficient. As a pillar of distributed systems, consensus algorithms power everything from distributed databases to decentralized infrastructure. The protocols covered in this thesis (Streamlet (Chan and Shi, 2020), Simplex (Chan and Pass, 2023), and variants) are the simplest in the literature, and are now taught in universities and power an increasing number of projects in industry. Second, we re-examine the fundamental meaning of what it means for a protocol to be cryptographically secure -- the basis of Modern Cryptography. Classical "provable security" assumes that the attacker is probabilistic polynomial-time in nature (or perhaps quantum) and stateless. In contrast, our notion of Universal Reductions (Chan, Freitag, and Pass, 2022)) models attackers as arbitrary unbounded stateful algorithms -- agnostic to what computational model is physically realizable by the universe, yielding a more general (and future-proof) notion of security.