Thursday, November 17, 2005

Secure and accurate time sources

Broadcasts using sound or radiation, from sources such as radio, bell towers, and astronomical phenomena, must send out the same value to every receiver. A remote beacon such as a pulsar has perfect security: the access structure is any party, and its complement, the attack structure, is the empty set. For human controlled broadcasts, the attack structure consists only of the broadcaster and the access structure is any receiver.

Natural broadcasts are thus immune to the problem (known in computer science as the Byzantine Generals problem) of a transmitter sending different values to different receivers. Indeed, distributed network researchers have gone to great lengths to recreate this simple property on the Internet with logical broadcast protocols. The results are incomplete and very inefficient compared to physical broadcasts.

Nature provides clocks that are oblivious to the malicious intentions of any outside parties and many orders of magnitude more accurate than random delays that face attackers on the Internet. If critical Internet servers were synchronized to natural clocks in a secure and timely fashion, they would be immune to attacks that relied on uncertainties in timing. Here are some comparisons of the stability (error creep) in good natural clocks. Pulsars overtake atomic clocks in accuracy after about 4 months.

Oscillator Stability1 sec1 day1 month
Cesium Beam10^-1010^-1310^-13
Hydrogen Maser10^-1310^-1410^-13


David Mercer said...

My home network's clock (set from the network) is sometimes under attack by my cats. They will occasionally get too rambunctious and flip a switch on a powerbar!

Iang said...

By pulsar, do you mean the star type in the sky or some form of technology?

Nick Szabo said...

The kind in the incorruptable heavens. Pulsars retain the valuable security property (as with astronomy-based time checks throughout history but unlike atomic clocks) that many people can observe the same "clock ticks" simultaneously and independently.