Goal: As the Coronavirus Pandemic of 2019/2020 unfolds, a COVID-19 'Immunity Passport' has been mooted as a way to enable individuals to return back to work. While the quality of antibody testing, the availability of vaccines, and the likelihood of even attaining COVID-19 immunity continue to be researched, we address the issues involved in providing tamper-proof and privacy-preserving certification for test results and vaccinations. Methods: We developed a prototype mobile phone app and requisite decentralized server architecture that facilitates instant verification of tamper-proof test results. Personally identifiable information is only stored at the user's discretion, and the app allows the end-user selectively to present only the specific test result with no other personal information revealed. The architecture, designed for scalability, relies upon (a) the 2019 World Wide Web Consortium standard called 'Verifiable Credentials', (b) Tim Berners-Lee's decentralized personal data platform 'Solid', and (c) a Consortium Ethereum-based blockchain. Results: Our mobile phone app and decentralized server architecture enable the mixture of verifiability and privacy in a manner derived from public/private key pairs and digital signatures, generalized to avoid restrictive ownership of sensitive digital keys and/or data. Benchmark performance tests show it to scale linearly in the worst case, as significant processing is done locally on each app. For the test certificate Holder, Issuer (e.g. healthcare staff, pharmacy) and Verifier (e.g. employer), it is 'just another app' which takes only minutes to use. Conclusions: The app and decentralized server architecture offer a prototype proof of concept that is readily scalable, applicable generically, and in effect 'waiting in the wings' for the biological issues, plus key ethical issues raised in the discussion section, to be resolved.