In this paper we first show how to remove the latter assumption, presenting a ``bootstrapped'' Bitcoin-like blockchain protocol relying on 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 \emph{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.
Category / Keywords: cryptographic protocols / Bitcoin, bootstrapping, unlinkability Original Publication (with minor differences): IACR-PKC-2018 Date: received 13 Oct 2016, last revised 23 Mar 2018 Contact author: pagio91i at gmail com Available format(s): PDF | BibTeX Citation Version: 20180323:151116 (All versions of this report) Short URL: ia.cr/2016/991