Public key infrastructure (PKI) provides the basis of authentication and access control in most networked systems. In the Internet of Things (IoT), however, security has predominantly been based on pre-shared keys (PSK), which cannot be revoked and do not provide strong authentication. The prevalence of PSK in the IoT is due primarily to a lack of lightweight protocols for accessing PKI services. Principal among these services are digital certificate enrollment and revocation, the former of which is addressed in recent research and is being pushed for standardization in IETF. However, no protocol yet exists for retrieving certificate status information on constrained devices, and revocation is not possible unless such a service is available. In this work, we start with implementing the Online Certificate Status Protocol (OCSP), the de facto standard for certificate validation on the Web, on state-of-the-art constrained hardware. In doing so, we demonstrate that the resource overhead of this protocol is unacceptable for highly constrained environments. We design, implement and evaluate a lightweight alternative to OCSP, TinyOCSP, which leverages recently standardized IoT protocols, such as CoAP and CBOR. In our experiments, validating eight certificates with TinyOCSP required 41% less energy than validating just one with OCSP on an ARM Cortex-M3 SoC. Moreover, validation transactions encoded with TinyOCSP are at least 73% smaller than the OCSP equivalent. We design a protocol for compressed certificate revocation lists (CCRL) using Bloom filters which together with TinyOCSP can further reduce validation overhead. We derive a set of equations for computing the optimal filter parameters, and confirm these results through empirical evaluation.