Credential fraud is a widespread practice that undermines investment and confidence in higher education systems and bears significant economic and social costs. Legacy credential verification systems are typically time-consuming, costly, and bureaucratic, and struggle against certain classes of credential fraud. In this paper, we propose a comprehensive blockchain-based credential verification solution, Cerberus, which is considerably more efficient, easy and intuitive to use, and effectively mitigates widespread manifestations of credential fraud. Cerberus also improves significantly upon other blockchain-based solutions in the research literature: it adheres closely to the existing credential verification ecosystem, it addresses a threat model informed by real-world fraud scenarios. Moreover, Cerberus uses on-chain smart contracts for credential revocation, and it does not entail students or employers to manage digital identities or cryptographic credentials to use the system. We prototype our solution and describe our attempt to design an online verification service with a rich feature set, including data privacy, transcript verification, and selective disclosure of data. We hope this effort contributes positively to towards alleviating the problem of fake credentials.