实现Bitcoin中的Hashcash Mining算法。
Overview
The aim of this project is to provide you with experience in writing (a) a
program that interacts with other programs over a network (socket
programming), and (b) multi-threaded applications. Specifically, you will
write a server-based proof-of-work solver for the Hashcash mining algorithm
used in Bitcoin.
This requires you to implement the functions in the Simple Stratum Text
Protocol (SSTP), which is used to format messages between clients and your
server program. The SSTP is described in Section 3. Background information
related to the the Bitcoin mining process is described in Section 2. Detailed
requirements and implementation guidelines are listed in Section 4.
Your program must be written in standard C. Use the POSIX pthread library for
multi-threaded tasks. Other dynamic and static libraries are prohibited.
Your program must run on the School of Engineering Linux server digitalis or
digitalis2.
Background
Introduction to Bitcoin
Bitcoin is the world’s first successful cryptocurrency and a payment network
that is currently valued at more than 20 billion dollars. The system follows a
fully decentralised peer-to-peer network topology and transactions take place
between users directly without an intermediary. Transactions are verified by
network nodes and recorded in a distributed ledger, commonly known as the
blockchain.
Bitcoins are created as a reward in a competition where miners offer their
computing power to record bitcoin transactions into the blockchain. This
activity is called mining and successful miners are rewarded with transaction
fees and the ability to create Bitcoins to pay to themselves1 .
In this project, we will not explore the purpose of mining in detail. However,
we will focus on the steps necessary for you implement a server program that
can execute the mining process using the SHA-256 algorithm. To get you
started, please read the document https://en.bitcoin.it/wiki/Proof_of_work
It is important to note, that in general, it is very difficult to produce a
valid proof-of-work solution of the mining process as there are 2256 possible
outputs for some random input. Therefore, this is a problem that should be
solved with some means of multi-threading, which enables you to distribute the
workload.
Hashcash Algorithm
The Hashcash algorithm used in the Bitcoin mining process is described below:
Find x such that H(H(x)) = y and y < target
- H is the SHA-256 hash function (see subsection 2.3)
- target is a 256-bit unsigned integer, which represents the largest acceptable hash value of some input.
See Section 4-Stage B for details on how to calculate the target value from an
appropriately formatted input protocol message (as described in Sections 3) - x is defined as a seed value concatenated with nonce i.e., seed | nonce where:
- seed is a 64 byte array, which is provided by a client through a protocol message (see Section 3 for details)
- nonce is a 64 bit unsigned integer (nonce basically means “number once” ie., an arbitrary number that may only be used once.)
Hence, the goal is to find a nonce value, which when concatenated with seed
creating x, yields a hash that is less than target. To do this, the search
starts from some initial nonce value and checks whether the conditions listed
above hold. If they do, great, you have a solution. If not, increment the
nonce value and try again (and again and again … until a solution is found).
Cryptographic Hash Function SHA-256
Bitcoin’s mining algorithm, Hashcash, utilises a cryptography hash function
known as the Secure Hash Algorithm (SHA-2). SHA-2 is a collection of six hash
functions with digests (hash-values) that are 224, 256, 384 or 512 bits. For
the purposes of our task, we will only be using the SHA-256 to produce a
proof-of-work.
Knowing the specifics of how SHA-256 works is not necessary for the purposes
of this project. A reference implementation of SHA-256 has been provided for
you. The source code can be downloaded from the LMS.
Simple Stratum Text Protocol (SSTP)
Before working through the SSTP messages listed below, you should familiarise
yourself with the primitive types provided by the standard C library. In this
project, you will also make use of:
- BYTE : unsigned char
- uint256 : BYTE[32] You can download source code for uint256 from the LMS
Your server-based proof-of-work solver will use the Simple Stratum Text
Protocol (SSTP).
Every protocol message should be delimited with the carriage return, followed
by a line feed (i.e., \r\n). You may assume that every protocol message has a
pre-defined length. Any message exceeding this pre-defined length will be
considered an invalid message and you must handle this correctly with an ERRO
message. Every message is comprised of a message header (4-bytes in length)
followed by its payload (the length of which depends on the actual message).
All network messages must be encoded and parsed in network byte order (i.e.,
big endian order).
There are seven messages in the protocol - your task in this project is to
implement all of them
Ping Message PING
PING
On receive, the server replies with a PONG message.
Pong Message PONG
PONG
Your server should reply with an error message ERRO informing the client that
PONG messages are strictly reserved for server responses.
Okay Message OKAY
OKAY
Your server should reply with an error message ERRO explaining that is not
“okay” to send OKAY messages to the server.
Error Message ERRO
ERRO reason: BYTE[40]
Example:
ERRO with an appropriate explanation
On receive, your server should reply with an error message ERRO indicating
that this message should not be sent to the server.
Solution Message SOLN
SOLN difficulty:uint32 seed:BYTE[64] solution:uint64
Example:
SOLN 1fffffff 0000000019d6689c085ae165831e934ff763ae46a218a6c
172b3f1b60a8ce26f 10000000232123a2
(Note: line wrap used in seed simply for formatting on the project spec)
On receive, your server should check if the concatenation of the seed and the
solution (which is actually a particular nonce value) does in fact produce a
hash which satisfies the target requirement derived from the difficulty value
(see Section 4-Stage B below for details). Here, an 8 byte hexadecimal
representation has been used for the difficulty.
If it is a valid proof-of-work, then you should reply with OKAY. Otherwise,
reply with ERRO with a 40-byte string describing what the error is.
Work Message WORK
WORK difficulty:uint32 seed:BYTE[64] start:uint64 worker count:uint8
Example: WORK 1fffffff 0000000019d6689c085ae165831e934ff763ae
46a218a6c172b3f1b60a8ce26f 1000000023212399 02
(Note: line wrap used in seed simply for formatting on the project spec)
Once again, an 8 byte hexadecimal representation has been used for the
difficulty. start is the initial nonce value4 and worker count is the number
of threads to use in the computation task. See section 2.3 for an explanation
of the computation steps.
On receive, your server should queue this work in a work queue. Once a proof-
of-work solution is found, reply with the SOLN message with the correct nonce
(i.e., the solution field in the SOLN message) which produces the proof-of-
work solution.
Abort Message ABRT
ABRT
On receive, your server should traverse the work queue and remove all pending
work for the client that sent this message. It should also pre-maturely
terminate all active proof of work worker threads. Once this is completed, an
OKAY response should be sent.
Requirements
We strongly recommend that you complete the project in four clearly defined
stages listed below.
Stage A
Create a simple text-based server capable of handling multiple concurrent
requests. This basically means extending the TCP server program introduced in
the labs so that it can correctly reply to simple messages received from
client programs concurrently.
You will have to make a decision as to the best way to deal with concurrent
requests from clients. Begin by implementing a simple plain-text server that
is capable of receiving and sending PING/PONG messages. Then add the OKAY and
ERRO messages.
Your server should also be able to receive requests (messages) from more than
one client at any given time and still be able to manage the processing of
protocol messages between all connected clients.
Stage B
Extend your server program from Stage A so that when an appropriately
formatted message is received from a client, your server program will parse
the message and perform appropriate computations on the parsed message to
verify whether the message is a valid solution for the proof-of-work. That is,
your server must be capable of validating whether a properly formatted SOLN
message contains a valid proof-of-work.
To make things easier for you in Stages B (and Stages C and D) helper
functions (i.e., uint256 functions and functions to execute SHA-256) have been
provided for you. You can download the source code from the LMS.
Given the fact that the target requires 64 bytes of text space within a block
protocol message, a mapping between the target and difficulty in the SOLN
message is used. Here, difficulty is represented using a 32 bit unsigned
integer and the corresponding mathematical formula to compute the target.
When your server is processing a SOLN message, it still should be able to
receive requests from multiple clients and manage the processing of protocol
messages between all connected clients. For example, your server must be
capable of immediately responding to PING messages with a PONG for a separate
client.
Stage C
Your server program will be extended again such that it can compute a proof-
of-work for a given WORK message by parsing the input received from the client
and creating a specific number of threads to do the actual computations. The
solution verification tasks completed in the previous Stage will also be used
here.
To complete this task, you will have to maintain a work queue based on the
current submitted client WORK messages. You will need to implement a server
function that finds a valid proof-of-work for each job in the queue (in turn)
by iteratively incrementing the nonce based on a properly formatted WORK
message. When you find a solution, the server replies with the SOLN message.
To keep things simple, in this Stage you should just use one thread to do the
computation.
While searching for the proof-of-work, your server implementation must still
be able to respond to all requests from clients. For example, while the search
for a proof-of-work solution is carried out, your server must be capable of
immediately responding to PING messages with a PONG etc.
Stage D: Bonus marks
In this final bonus mark Stage, you will further extend your server program so
that multiple threads (workers) can be used to do the computation (or
searching for a proof-of-work ). The actual number of threads to be used will
be given in the WORK message.
Your server will need to handle incomplete messages (i.e., messages that have
not ended with a delimiter). Your server must store incomplete messages in a
buffer and continue to receive the subsequent segments of incomplete messages
until the message is delimited or exceeds the maximum message length.
On client disconnection, all queued work from the client should be removed
from the work queue. Active worker threads working on searching for proof-of-
work solutions should also stop working immediately and should start working
on the next work item in the work queue.
Server Log File
You must continually write to a log file (./log.txt)5 detailing each (and
every) interaction between the server and individual clients. Each log file
entry will include:
- a time-stamp (system date/time)
- IP address of the client or 0.0.0.0 for the server
- a socket id (or file descriptor) for the client connection
- SSTP message for the exchange between server and client
Note: Your log file should reflect the Stages of the project task that you
have completed. If your server crashes you may not have any entries in your
log file - so take care.
Limits
The following limits will be used:
- maximum number of clients: 100
- maximum number of pending jobs: 10
- maximum number of processors: unbounded
- maximum number of threads: unbounded
One final comment: there is no need to handle unsolvable WORK messages. We
will not be giving you any unsolvable work.
