Cryptophage

About:

Cryptophage is a collaborative project between blockchain groups (the Ethereum Foundation and Protocol Labs), hardware and algorithm experts (Supranational), and academics (Sabanci University). It is the result of applied research into an exciting cryptographic construction, verifiable delay functions (VDF). Cryptophage is an open-source implementation of a VDF that runs on an FPGA and can be easily launched in AWS F1.

Cryptophage was used to solve the LCS35 ‘crypto-puzzle’ created by Ron Rivest in 1999. The LCS35 puzzle was designed to take 35 years to ‘crack’. The Cryptophage project solved it in 2 months.

Timelocks

The LCS35 'crypto-puzzle' is an example of timelock encryption. Timelock encryption allows you encrypt a message "into the future". That is, it allows you to encrypt a message such that it can only be decrypted at a certain point in the future. The time restriction is not based off of 'wall-clock' time, but rather computational time. Decrypting the message requires a number of sequential calculations, where each step in the calculation depends on the previous step, allowing hardware to mimic the passage of physical time.

Verifiable Delay Functions

Motivation for the Cryptophage effort came from the discovery in 2018 of an exciting new cryptographic primative called a Verifiable Delay Function (VDF). VDFs provide cryptographic proofs of the passage of time without a trusted third party. They are based on the same sequential computation as timelocks

The security of VDFs depend on the wide availability of commodity hardware to run the sequential computations quickly. An attacker should not be able to run the computation faster than some assumed speed advantage, often referred to as 'Amax' For example, we may assume that an attacker can not build hardware that runs over 100 times faster than commonly available hardware

VDFs can provide a source of unbiasable randomness in blockchain protocols, allowing the blockchain network to more securely place participants into different roles. These heterogenous roles can help to improve the scalability of blockchain networks. To practically realize these applications, there is an effort to design and distribute state-of-the-art hardware to run these sequential computations. This hardware will run fast enough to severly limit the possible speed advantage an attacker may have. If you'd like to contribut funding or expertise to this research, please reach out

About the LCS35 Time Capsule of Innovations:

From April 12th to April 14th of 1999, MIT celebrated the 35th anniversary of the MIT Laboratory of Computer Science (now CSAIL). The event was attended by computer science pioneers such as Robert Metcalfe, Bill Gates, Ron Rivest, and Tim Berners-Lee.

At the event, a ‘Time Capsule of Innovation’ was created. The capsule contained artifacts that contributors thought would have, or already had, a significant impact on computer science and technology. These artifacts referenced the WC3, zero-knowledge proofs, and RSA cryptography. The time capsule was sculpted by architect Frank Gehry and currently resides inside the lobby of the Ray and Maria Stata Center. The time capsule was set to be unsealed either 35 years from the date of the event (~2033), or upon completion of the LCS35 crypto-puzzle.

FAQ:

What’s a cryptophage?

Cryptophage is named after the Chronophage (time-eater) clock in Cambridge, England. The Cryptophage is a ‘secret eater’.

What does it do?

Cryptophage is an FPGA-based system that performs modular squaring with extremely low latency using innovative new algorithms designed by Erdinc Ozturk at Sabanci University. Modular exponentiation is a widely used technique in the field of public-key cryptography.

How fast is Cryptophage?

Cryptophage can do one 2048 bit modular squaring approximately every 70 nanoseconds. In comparison, a high-end desktop processor would take over 1000 nanoseconds to complete the same operation.

How many squarings did it do?

Approximately 80 trillion modular squaring operations were required to solve the puzzle.

When did you start the ‘crypto-puzzle’?

We began work on the cypto-puzzle in early 2019.

Why does fast modular squaring matter?

We began the investigation into hardware acceleration for modular squaring as the result of an interest in the application of verifiable delay functions to blockchain networks. Verifiable delay functions can help improve the security and scalability of blockchain networks. However, they are primarily useful only to the extent that the computational complexity of the VDF can be reasonably mapped to an elapsed real time. Our work helps to better estimate the extent to which these algorithms can be accelerated with purpose-built hardware

Where can I get the code?

The code will be made available here over the next couple of weeks.

What’s a Verifiable Delay Function (VDF)?

A verifiable delay function is a function that takes a certain amount of time to compute, and cannot be accelerated through parallelization/additional processors. Once computed, the output can be quickly verified by anyone.

How Can VDFs be used?

VDFs can be used to create resource-efficient blockchain protocols, and can assist in the construction of proof-of-replication algorithms. You can find more detail about these use cases and others here.

Is this just a new type of mining?

No -- While VDFs can be seen as a type of ‘proof-of-work’ or hashcash, VDFs differ in that the work can not be greatly parallelized. VDFs have the potential to help create secure consensus algorithms with drastically lower energy costs.

Does Cryptophage mean VDFs are broken?

No -- in fact, implementing fast VDFs provides a better way to reason about their security as delay functions.

How can I keep up with the progress?

Twitter: Supranational | Ethereum | Protocol Labs

Hosted on IPFS