Modern society is increasingly surrounded by, and accustomed to, a wide range of Cyber-Physical Systems (CPS), Internet-of-Things (IoT), and smart devices. They often perform safety-critical functions, e.g., personal medical devices, automotive CPS and industrial automation (smart factories). Some devices are small, cheap and specialized sensors and/or actuators. They tend to run simple software and operate under control of a more sophisticated central control unit. The latter is responsible for the decision-making and orchestrating the entire system. If devices are left unprotected, consequences of forged sensor readings or ignored actuation commands can be catastrophic, particularly, in safety-critical settings. This prompts the following three questions: (1) How to trust data produced by a simple remote embedded device? and (2) How to ascertain that this data was produced via execution of expected software? Furthermore, (3) Is it possible to attain (1) and (2) under the assumption that all software on the remote device could be modified or compromised? In this paper we answer these questions by designing, proving security of, and formally verifying, VAPE: Verified Architecture for Proofs of Execution. To the best of our knowledge, this is the first of its kind result for low-end embedded systems. Our work has a range of applications, especially, to authenticated sensing and trustworthy actuation, which are increasingly relevant in the context of safety-critical systems. VAPE architecture is publicly available and our evaluation demonstrates that it incurs low overhead, affordable even for lowest-end embedded devices, e.g., those based on MSP430 or ARV ATMega processors.