It took 3.5 years for Belgian programmer Bernard Fabrot to solve a cryptographic puzzle that was originally thought to take 35 years of computational time. The puzzle is what’s known as a “time-lock problem” – a time-consuming calculation that can only be accelerated by tuning your algorithm or by building faster computer hardware. Time-lock puzzles are interesting, and important, because they can’t be short-circuited simply by splitting the problem into pieces and throwing more computers at it. The puzzle essentially involves doing roughly 80 trillion successive squarings of a starting number, and was specifically designed to foil anyone trying to solve it more quickly by using parallel computing. The puzzle is an example of a “verifiable delay function” (VDF), meaning that its answer can only be solved after a certain number of steps.
The puzzle was originally published in 1999 as part of the celebration for MIT's Laboratory of Computer Science (LCS) 35th anniversary. The full description is here https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
In the original announcement, LCS promised that, if a correct solution was uncovered, they would open a special “time capsule” designed by architect Frank Gehry and filled with historical artifacts from the likes of Web inventor Tim Berners-Lee, Ethernet co-inventor Bob Metcalfe, and Microsoft founder Bill Gates. The capsule ceremony will happen Wednesday, May 15 at 4 p.m. at MIT’s Stata Center.
