A popular technique for tolerating Byzantine faults in open distributed systems is to group machines into sets called quorums, each of which has an honest majority. These quorums are then used as basic building blocks to design systems that are robust to adversarial faults. Despite over a decade of active research, all current algorithms require quorum sizes of Ω(logn), where n is the number of machines in the network. This size is important since communication cost scales polynomially in the size of the quorum. Given the stubbornness ofthis Ω(logn) barrier,a natural question is whether better bounds are possible. In this paper, we demonstrate that it is possible to reduce quorums sizes to O(loglogn), despite an adversary that controls a constant fraction of the computational resources in the network. Inparticular,we show that even with such small quorums, we can ensure that all but an o(1)-fraction of the machines can communicate with all but an o(1)-fraction of the machines in the network.