  Our modern world relies on a growing number of interconnected and interacting
devices, leading to a plethora of logs establishing audit trails for all kinds
of events. Simultaneously, logs become increasingly important for forensic
investigations, and thus, an adversary will aim to alter logs to avoid
culpability, e.g., by compromising devices that generate and store logs. Thus,
it is essential to ensure that no one can tamper with any logs without going
undetected. However, existing approaches to establish tamper evidence of logs
do not scale and cannot protect the increasingly large number of devices found
today, as they impose large storage or network overheads. Additionally, most
schemes do not provide an efficient mechanism to prove that individual events
have been logged to establish accountability when different devices interact.
  This paper introduces a novel scheme for practical large-scale tamper-evident
logging with the help of a trusted third party. To achieve this, we present a
new binary hash tree construction designed around timestamps to achieve
constant storage overhead with a configured temporal resolution. Additionally,
our design enables the efficient construction of shareable proofs, proving that
an event was indeed logged. Our evaluation shows that - using practical
parameters - our scheme can localize any tampering of logs with a sub-second
resolution, with a constant overhead of ~8KB per hour per device.
