The usage of process choreographies and decentralized Business Process Management Systems has been named as an alternative to centralized business process orchestration. In choreographies, control over a process instance is shared between independent parties, and no party has full control or knowledge during process runtime. Nevertheless, it is necessary to monitor and verify process instances during runtime for purposes of documentation, accounting, or compensation. To achieve business process runtime verification, this work explores the suitability of the Bitcoin blockchain to create a novel solution for choreographies. The resulting approach is realized in a fully-functional software prototype. This software solution is evaluated in a qualitative comparison. Findings show that our blockchain-based approach enables a seamless execution monitoring and verification of choreographies, while at the same time preserving anonymity and independence of the process participants. Furthermore, the prototype is evaluated in a performance analysis.