COVID-19 has altered the landscape of medical record issuing and verification. Multiple challenges have arisen in this new era as individuals are now required to prove their health status for traveling, working, or simply eating at a restaurant. Record verification across country borders is particularly hard to achieve as it requires collaboration at an international level, sharing potentially sensitive medical data. In this work, we propose VaxPass, a scalable system for COVID-19 record issuing and verification that facilitates this collaboration with minimal data leakage. At the core of our design lies a 2-tier blockchain architecture that allows individual issuing authorities to maintain their own 1st -level blockchain and only upload a small digest of their records, periodically, on the 2nd -level. Crucially, a verifier can check the validity of a certificate without having access to the 1st -level blockchain where the records actually reside. Our system also includes a mobile application and a web client. As we demonstrate, its performance scales well with the number of participants, making this the first solution able to support real-life inspired needs for such a system, while maintaining confidentiality of the medical data solely to privy entities.