Repository files navigation

Small repo for implementing the 2018 EUROCRYPT paper"Simple Proofs of Sequential Work" by Cohen and Pietrzak. Also used as part of our CS244 project in Professor Kung's class at Harvard University.

This is currently aexperimental repository.

DO NOT USE THE CURRENT VERSION OF THIS REPO IN ANY REAL WORLD PROGRAM.

I repeat

DO NOT USE THE CURRENT VERSION OF THIS REPO IN ANY REAL WORLD PROGRAM.

This is used as a proof of concept before we implement the scheme withcryptographically secure primitives, possibly in a different programming language.Also you really shouldn't be running a random persons repository thatprobably has crippling security vulnerabilities anyway...

Python 3.6 is REQUIRED to run this code using your computer's entropy source.This is because we use thesecrets module first introduced in Python 3.6 toget better random numbers than python's oldrandom library.

Most of the scheme is implemented inscheme.py and the main functions forthe prover and the verifier are listed inposw.py that can be importedfor use in other areas. You can run a small test by runningpython3 posw.pywhich should return true. The file simulates running the scheme for an honestprover and verifier.

Install the python requirements with

pip install -r requirements.txt

If using a Mac, you can use ourinstall.sh script to install the required dependencies. Unfortunately for Ubuntu 16.04 and older distros, installingpython3.6 is a bit annoying - standard repositories still only support up to python3.5.

chmod +x install.sh./install.sh

Then, you can run a simple test with

python3 posw.py --helpusage: posw.py [-h] [-n N] [-t T]Runs a test prover-verifier proof of sequential work assuming both parties arehonest.optional arguments:  -h, --help  show this help message and exit  -n N        depth of the DAG  -t T        number of challenges in gamma

Parameter selection is important. Try not to go over 20 for n, t can be anywhere from 0 to 2^n and it works fine.

The parameters described in the paper (and are named in the same way in the source code) are

• N: The time parameter which we assume is of the form2^n-1 for an integer n
• w: A statistical security parameter from which the random nonce is generated from
• H: A random oracle (we used default of sha256) that maps (0, 1)* to (0, 1)^w

Many thanks to Professor Kung for his intellectually interesting discussions, as well as Marcus Comiter for all the help in the class.

• Balloon Hashing Dan Boneh, Henry Corrigan-Gibbs, and Stuart Schechter. A Memory-Hard Function Providing Provable Protection Against Sequential Attacks

• Publicly Verifiable Proofs of Sequential Work The earlier paper that this repository is based on, by Professor Salil Vadhan.

• Simple Proofs of Sequential Work The paper that this repository is based on. Was presented in Eurocrypt 2018.