This paper presents and evaluates SYN PoW, a novel approach to mitigating TCP SYN flooding attacks using minia-ture proofs-of-work. SYN Floods have been a common threat on the Internet for decades, and have increased dramatically in both scale and frequency in recent years. Currently, SYN Cookies are widely deployed as a mitigation against this threat, but as we demonstrate they scale poorly with the volume of attack and can be detrimental to performance. SYN PoW plays a similar role, but with several key advantages: (1) it protects bandwidth by dropping malicious SYN s without sending SYN-ACKs in response; (2) it facilitates in-network verification, enabling middle boxes to detect and drop malicious packets before they reach their target; (3) it shifts the primary cost burden of mitigation from attack victims to attackers themselves; and (4) it protects against spoofing attacks without requiring source address validation. We explain how proofs-of-work can be added to SYN packets in a way that complies with the current TCP standard, and demonstrate how SYN Po W outperforms SYN Cookies under high-volume SYN floods in controlled testbed experiments.