CS 4000

Homework # 5: CS Coin and Parallel Processing

(50 pts.)

Introduction

Bitcoin, and other digital currencies use a concept called “proof of work” to award digital

money to those who perform computational work. The concept is somewhat straightforward,

as we explain next. To demonstrate proof of work, we assume that we have a function f that

is one-way in the sense that computing y = f(x) is easy, given x, but computing the inverse,

i.e., x = f

−1

(y) is hard to do. So, I could give you a number z and a one-way function f, and

you could “prove that you did some work” by giving me the x such that f(x) = z. For such

an x, it is easy to verify that f(x) = z because you can simply compute f(x) and compare

it to z.

The function that bitcoin uses as f is the SHA256 cryptographic function. The output

of SHA256 is always a 256-bit unsigned integer. For bitcoin, the proof of work for a number

z is finding a number x such that SHA256(x) < z. This is, in principle, a bit easier than

actually finding a number x such that f(x) = z, but the best known approaches are basically

brute force (i.e., try all possibilities).

CS Coin

For this assignment, we have decided to create our own digital currency called “CS Coin.” A

CS coin miner can request a mining task from the World CS government. This mining task

is a pair of large integers (256 bit) hl, ri where l < r. The miner’s task is to find an integer z

such that l < SHA256(z) < r. Once the miner discovers such a number z, they inform the

World CS government and are awarded a CS Coin. CS coin’s are currently valued at $0.50

a piece, but their value is expected to skyrocket during the next global pandemic. (There is

an internet rumor by CSanon, the brother of Qanon, that during the next pandemic that CS

coin will be the only valid currency for buying toilet paper. So, people who frequent certain

Facebook forums are stocking up on CS coin at an amazing rate.)

Base Code

I have implemented two sequential C++ programs: cs_miner.cc and coin_verify.cc, and

I have provided a Makefile that compiles both programs into executables called miner and

verify, respectively. Each program use the openssl and boost libraries. You may need to

install these on your local machines if you want to run your code at home.

The program miner reads in two large integers l and r and produces an integer z such

that l < sha256(z) < r. I have also provided a number of coin challenges (e.g., coin_try14).

To run the program, enter

./miner <coin_try14 > coin14

This will redirect the input from the file coint_try14 to the program and stores the result

in a file coin14. The program verify can test whether you successfully found a coin. To

test if your program runs correctly, enter

cat coin_try14 coin14 | ./verify

If you successfully found a coin, the verify program will print “true.” Otherwise, it prints

“false” and fails. The verify program is always fast. The miner is slow.

Part 1:OpenMP or C++ Threads (30 pts.)

For part 1, use OpenMP or C++ Threads to build a parallel version of the miner program.

Your program should be race condition free and should achieve a speedup of at least 3 on a

4 core machine on sufficiently hard coin challenges.

Part 2:OpenMPI (20 pts.)

For part 2, use OpenMPI to build a parallel version of the miner program. Your program

should be race condition free and it should achieve a speed up of at least 6 when run on a

sufficiently hard coin challenge on 10 machines.

Extra Credit (10 pts.)

I will post a difficult CS coin challenge. Your task will be to mine a coin as fast a possible.

To get the extra credit points, you will submit your solution to this coin challenge.

CS 4000

# Homework # 5: CS Coin and Parallel Processing

Original price was: $35.00.$30.00Current price is: $30.00.

## Reviews

There are no reviews yet.