Permissionless blockchains reach decentralized consensus without requiring pre-established identities or trusted third parties, thus enabling applications such as cryptocurrencies and smart contracts. Consensus is agreed on data that is generated by the application and transmitted by the system’s (peer-to-peer) network layer. While many attacks on the network layer were discussed so far, there is no systematic approach that brings together known attacks, the requirements, and the design space of the network layer. In this paper, we survey attacks on the network layer of permissionless blockchains, and derive five requirements: performance, low cost of participation, anonymity, DoS resistance, and topology hiding. Furthermore, we survey the design space of the network layer and qualitatively show the effect of each design decisions on the fulfillment of the requirements. Finally, we pick two aspects of the design space, in-band peer discovery and relay delay, and demonstrate possible directions of future research by quantitatively analyzing and optimizing simplified scenarios. We show that while most design decisions imply certain tr ... mehradeoffs, there is a lack of models that analyze and formalize these tradeoffs. Such models could aid the design of the network layer of permissionless blockchains. One reason for the lack of models is the deliberately limited observability of deployed blockchains. We emphasize that simulation based approaches cope with these limitations and are suited for the analysis of the network layer of permissionless blockchains.