Sensor networks are deployed to monitor the physical environment in public and vulnerable locations. It is not economically viable to house sensors in tamper-resilient enclosures as they are deployed in large numbers. As a result, an adversary can subvert the integrity of the data being produced by gaining physical access to a sensor and altering its code. If the sensor output is timestamped, then tainted data can be distinguished once the time of attack is determined. To prevent the adversary from generating fraudulent timestamps, the data must be authenticated using a forward-secure protocol. Previous work requires the computation of n hashes to verify the (n+1)th reading. This paper describes PAST, a protocol that allows timestamps to be authenticated with high probability using a small constant number of readings. In particular, PAST is parameterized so that the metadata overhead (and associated power consumption) can be reduced at the cost of lower confidence in the authentication guarantee. Our protocol allows arbitrary levels of assurance for the integrity of timestamps (with logarithmically increasing storage costs) while tolerating any predefined fraction of compromised base stations. Unlike prior schemes, PAST does not depend on synchronized clocks.