On secure chain selection rules from physical resources in a permissionless setting

Blockchains enable distributed consensus in permissionless settings, where participants are unknown, dynamically changing, and do not trust each other. While Bitcoin, based on Proof-of-Work (PoW), was the first protocol in this model, significant research has focused on permissionless protocols using alternative physical resources, specifically Proof-of-Space (PoSpace) and Verifiable Delay Functions (VDFs). This thesis investigates the theoretical limits and design space of longest-chain protocols in the fully permissionless and dynamically available settings using these three resources. First, we address the feasibility of blockchains relying solely on storage as a resource. We prove a fundamental impossibility result: there exists no secure longest-chain protocol based exclusively on Proof-of-Space in the fully permissionless or dynamically available settings. Further, we quantify the adversarial capabilities required to execute a double-spend attack. Our result formally justifies the necessity of coupling PoSpace with time-dependent primitives (such as VDFs) or to move to less permissive settings (quasi-permissionless or permissioned) to ensure security. Second, we generalize Nakamoto-like heaviest chain consensus to protocols utilizing combinations of multiple physical resources. We analyze chain selection rules governed by a weight function Γ(S, V,W), which assigns weight to blocks based on recorded Space (S), VDF speed (V ), and Work (W). We provide a complete classification of secure weight functions, proving that a weight function is secure against private double-spend attacks if and only if it is homogeneous in the timed resources (V,W) and sub-homogeneous in S. This framework unifies existing protocols like Bitcoin and Chia under a single theoretical model and provides a powerful tool for designing new longest-chain blockchains from a mix of physical resources.