Ilan Komargodski

NTT Research Scientist

SPARK: A Proposal for Parallelizing Complex Computational Proofs

Computational proofs have become increasingly important over the years, due to our highly networked world where you might want to “outsource” parts of your own computational work to cloud vendors such as Microsoft Azure or Amazon Web Services (AWS). To illustrate the problem, imagine you want to calculate Pi to 5,000,000 digits, then use the result of this calculation in your own software to calculate something else. As a caveat, imagine if you have an error in your Pi calculation, your resulting calculation will become useless.

 

Calculating PI to 5,000,000 digits is a task that’s tailor-made for cloud computing, so you want to outsource it to AWS or Azure. However, how can you trust the cloud vendor not to take shortcuts, and simply create made-up numbers so it doesn’t have to spend the CPU cycles performing actual calculations? 

 

On the other end of the spectrum, the whole endeavor is not so useful if proving the calculation requires equal or longer amounts of time as performing the calculation, especially if some of these calculations require months to perform.

 

In his talk at Upgrade 2020, the recent NTT Research Summit, Ilan Komargodski proposed a solution he refers to as SPARK, an acronym for “Succinct Parallelizable Arguments of Knowledge,” based on joint research performed with Naomi Ephraim, Cody Freitag and Rafael Pass (watch the video presentation below). Their proposal significantly reduces the time required for the cloud vendor to provide proofs that it performed the calculation accurately and didn’t just make up results.

 

The idea is to perform parts of the calculation first, producing a temporary result, then to start creating proof of this temporary result in parallel – while continuing the main calculation using the temporary result. As the partial and temporary result is reached, the idea is to use a cryptographic hash function upon it to create a digest, which is then used as the starting point of the consecutive proofs.  This ensures the proof becomes computed consistently and mostly in parallel to the main calculation. By carefully setting up parameters, this results in T + polylog T time to compute both the main calculation and its proof, where T is the original time required to perform (only) the calculation.

 

The digest or hashing parts of this chain of proofs is similar to the way cryptographic blockchain works for Bitcoin and crypto currency technology. The hash resulting from the first block becomes the validator of the consecutive block, resulting in a chain of proofs that logically could not have been made up in any way, or tampered with to create false results.

 

Komargodski freely admits his work at this point is highly theoretical, and not yet ready for practical implementation – that’s a future step in the journey. In the meantime, check out the video below of Komargodski’s talk for more details on his team’s work or click here for a transcript of his talk.

 

For the full transcript of Ilan Komargodski’s presentation, click here.

 

Watch Ilan Komargodski’s full presentation below.

SPARKs: Succinct Parallelizable Arguments of Knowledge

Ilan-Komargodski-New

Ilan Komargodski
NTT Research Scientist