  Logical clocks are a fundamental tool to establish causal ordering of events
in a distributed system. They have been used as the building block in weakly
consistent storage systems, causally ordered broadcast, distributed snapshots,
deadlock detection, and distributed system debugging. However, prior logical
clock constructs fail to work in a permissionless setting with Byzantine
participants. In this work, we introduce Chrono, a novel logical clock system
that targets an open and decentralized network. Chrono introduces a new logical
clock construct, the Decaying Onion Bloom Clock (DOBC), that scales
independently to the size of the network. To tolerate Byzantine behaviors,
Chrono leverages non-uniform incrementally verifiable computation (IVC) to
efficiently prove and verify the construction of DOBC clocks. We have applied
Chrono to build two decentralized applications, a weakly consistent key-value
store and an anti-censorship social network, demonstrating the power of
scalable, verifiable causality in a decentralized network.
