The advent of blockchain protocols such as Bitcoin has ignited much excitement, not only for their realization of novel financial instruments, but also for offering alternative solutions to classical problems in fault-tolerant distributed computing and cryptographic protocols. Underlying many of such protocols is a primitive known as “proof of work” (PoW), which for over 20 years has been liberally applied in the cryptography and security literature to a variety of settings, including spam mitigation, sybil attacks, and denial of service protection; its role in the design of blockchain-based protocols, however, is arguably its most impactful application. At a high level, the way PoWs enable such protocols is by slowing message passing for all parties indiscriminately, thus generating opportunities for honest parties’ views to converge, under the assumption that their aggregate computational power exceeds that of the adversary.
In this talk we discuss the evolution of our understanding of the PoW primitive, where pinning down the exact properties sufficient to prove the security of the protocols they enable has been elusive. We first identify such properties, and then construct a protocol whose security can be reduced to them in the standard model, assuming a common reference string (CRS). All previous protocols rely on the “random oracle” methodology. Second, regarding the realizability of important problems in distributed computing and cryptographic protocols, such as Byzantine agreement and secure multiparty computation, we show how this type of primitive allows us to realize them in the presence of a higher number of corrupted parties and weaker setup assumptions. We resolve this apparent contradiction with a new paradigm we call “Resource-Restricted Cryptography,” which hints at “how to do cryptography when cryptography is not possible.”
