In this work, we study and formalize security notions for algorithm substitution attacks (ASAs) on cryptographic puzzles (A full version of this work is available at https://eprint.iacr.org/2022/477 ). Puzzles are difficult problems that require an investment of computation, memory, or some other related resource. They are heavily used as a building block for the consensus networks used by cryptocurrencies. These include primitives such as proof-of-work, proof-of-space, and verifiable delay functions (VDFs). Due to economies of scale, these networks increasingly rely on a small number of companies to construct opaque hardware or software (e.g., GPU or FPGA images): this dependency raises concerns about cryptographic subversion. We first explore the threat model for these systems and then propose concrete attacks that (1) selectively reduce a victim’s solving capability (e.g., hashrate) and (2) exfiltrate puzzle solutions to an attacker. Our findings reveal that these devices could be subverted today, and detecting some attack variants is extremely hard and costly. We then suggest defenses, several of which can be applied to existing cryptocurrency hardware with minimal changes. We also discover that mining devices for many major proof-of-work cryptocurrencies already demonstrate errors exactly how a potentially subverted device would. Given that these attacks are relevant to all proof-of-work cryptocurrencies that have a combined market capitalization of around a few hundred billion dollars (2023), we recommend that all vulnerable mining protocols consider making the suggested adaptations today.