Panoramix presents “Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup” at the International Conference on Practice and Theory of Public Key Cryptography. Juan A. Garay, Aggelos Kiayias, Nikos Leonardos, Giorgos Panagiotakos

Bitcoin’s security is based on the assumptions that the adversarial hashing power is less than 1/2 and that all parties pre-agree on a `fresh’ genesis block. In this paper we show how to remove the latter asumption, presenting a “bootstrapped” Bitcoin-like blockchain protocol relying on proofs of work (POWs) that builds genesis blocks “from scratch” in the presence of adversarial pre-computation. Importantly, the round complexity of the genesis block generation process is independent of the number of participants.Next, we consider applications of our construction, including a PKI generation protocol and a consensus protocol without trusted setup assuming an honest majority (in terms of computational power).Previous results in the same setting (unauthenticated parties, no trusted setup, POWs) required a round complexity linear in the number of participants.

Paper available at: https://eprint.iacr.org/2016/991.pdf