Decentralized cryptocurrencies such as Bitcoin have ignited much excitement, not only for their novel realization of central bank-free financial instruments, but also as an alternative approach to classical distributed computing problems, such as reaching agreement distributedly in the presence of potentially misbehaving parties, as well as to numerous other applications―contracts, reputation systems, name services, etc. The soundness and security of these applications, however, hinge on the thorough understanding of the fundamental properties of their underlying blockchain data structure, which parties (“miners”) maintain and try to extend by generating proofs of various kinds, “proofs of work” (PoW, aka “cryptographic puzzle”) perhaps being the most interesting ones.In this talk we formulate such fundamental properties of the blockchain, and show how applications such as consensus and a robust public transaction ledger can be built “on top” of them, assuming the adversary’s hashing power is strictly less than ½. The above properties hold assuming that all parties―honest and adversarial―”wake up” and start computing at the same time, or, alternatively, that they compute on a common random string (the “genesis” block) only made available at the exact time when the protocol execution is to begin. We also address the question of whether such a trusted setup/behavioral assumption is necessary, answering it in the negative by presenting a Bitcoin-like blockchain protocol that is provably secure without trusted setup. A direct consequence of this last construction is that consensus can be solved directly by a blockchain protocol without trusted setup assuming an honest majority (in terms of computational power), in contrast to what is known in the classical distributed computing literature, an apparent contradiction that we also explain.Most of this talk is based on joint work with Aggelos Kiayias (U. of Edinburgh), Nikos Leonardos (U. of Athens) and Giorgios Panagiotakos (U. of Edinburgh).