CS 6410: Advanced Systems (Fall 2019)

MVB: A Minimally-Viable Blockchain

Introduction

In this project you will be implementing a minimally viable blockchain, called MVB, and – consequently – will instantiate a new coin called MVBCoin. We have provided sample code in Go and in Java that is mostly complete, but it is up to you to implement some missing functionality, and eventually to create a parallelized implementation to allow faster mining of blocks.

Disclaimer #1: We are partially misleading you. While you will build many of the core components of a blockchain, there are certain components of actual cryptocurrencies (such as Bitcoin) which we will not have you worry about. Without these components, MVBCoin is actually unsafe and susceptible to attacks (such as double spends). Therefore, hold back on trading your MVBCoins!

Disclaimer #2: We assume that you have already familiarized yourself with the Bitcoin paper [1, 2], and have some rudimentary understanding of the protocol. This document will avoid any algorithmic descriptions, and rather simply focus on the technical details. Please read [1, 2] for protocol specifics.

Overview of an MVBCoin Node

In this project, your job is to complete an implementation of an MVBCoin node. A detailed explanation follows at the bottom of this webpage, but a quick summary is useful in order to understand the big picture of what you must implement.

The main job of an MVBCoin node is to receive transactions, collect them into blocks, and then find a nonce (an arbitrary sequence of bits) to add to the beginning of each block that causes the hashes of the blocks to begin with a certain number of zeroes. For this assignment, MVBCoin nodes all run on the same computer, but communicate using network protocols. This means that each MVBCoin node can be identified using a port number alone.

MVBCoin nodes take the following command line arguments:

port: The network port your node is listening on. This argument will always be provided.
peers: A comma separated list of peer ports your node will broadcast transactions received to.
numtxinblock: The number of transactions to be put in a block. Defaults to 50,000.
difficulty: Difficulty parameter. The hash of a valid block should start with at least this many zeroes.
numcores: The number of cores to be used for mining. Note that the sample code will only use one core on its own; you will implement this functionality in part 2 of this assignment.

An MVBCoin node can receive the following types of messages:

Transaction message : Describes one user's attempt to send money to another user. Once a node receives numtxinblock transactions, it should begin mining a block containing those transactions.
Block message : Sent by nodes that have successfully mined a block to inform other nodes about the presence of this block. Note that for simplicity in this assignment, each node produces its own independent chain, and does not add blocks produced by other nodes to its own chain.
Close message : Used to signal the current node to terminate itself. Once a node is sent a close message, it will not receive any further transaction messages. It should finish mining any complete blocks made from existing transactions, and then exit.
get_block message : Used to request a node to resend a given block in its own blockchain.

When a node receives a message other than a get_block message, it should forward this message to all of its peers.

Part 1: Complete Implementation (Due 9/19/19 11:59PM)

For part 1 of this assignment, we have provided you sample code implementing most of the functionality of an MVBCoin node. However, there are two sections that you must implement on your own:

1a: Rejecting repeat / invalid transaction messages

Currently, the sample code will accept (and forward) every tranasction message sent to it. This includes both repeat transactions, transactions with unknown senders and receivers, and transactions where the sender attempts to spend coins that they do not actually have. For this part of the assignment, you should implement some checks to ensure that this does not happen.

In order to implement this functionality, you should edit the handleTransaction() function in the sample code. You may want to use the transactionSeen and accountAmount variables. Note that because the node can receive two transaction messages simlutaneously from two different senders, you should make sure to protect any access to transactionSeen and accountAmount using either a mutex (in go), or a synchronized block (in Java).

For this assignment, we will define 100 accounts, using the sha256 hash of the numbers 0 to 99. Each account should start with 100000 MVBCoins. This initialization is already present in main in the sample code.

for i = 0 to 100:
  account = sha256.sum(i)
  add {account, 100000} to accountAmount

Again, if a node does not have enough money to send for the transaction, then do not broadcast the transaction to the node's peers. You should only process a transaction once. If you receive a duplicate transaction, do not process or broadcast it.

1b: Mining blocks

IMPORTANT: Each block is tagged with a miner address, which is simply the sha256 hash of your netid. You should make sure to edit mineManager and look for the comment, "TODO: Don't forget to change this to your own netid!", and edit the relevant string to match your own netid.

Currently, when the sample code receives enough transactions to publish a block, it publishes the block with an all-zero nonce. When hashing the block together with this nonce, the resulting hash will likely not begin with any zeroes. In other words, the sample code does not actually mine a valid block.

To fix this, you should edit the mine() function in Go, or the Miner class in Java. Currently these functions have stub implementations that do not actually perform any mining. You should replace the stub implementation with a fully functional one. For this assignment, the hash of a block is computed as follows:

hash = sha256.sum([NONCE] + [PRIOR HASH] + [BLOCKHEIGHT] + [MINER_ADDRESS] + BLOCKDATA)

NONCE is the randomly chosen 32 byte value for this puzzle, PRIOR HASH is the 32 byte hash of the prior block, BLOCKHEIGHT is the 32 byte value of the height of this block (genesis block starts at 0), MINER_ADDRESS is 32 byte address of your node, and BLOCKDATA is the byte array of transactions concatenated together.

Your miner implementation should repeatedly attempt to perform the above hash using different values for the nonce. Each time, it should check how many of the leading bytes of hash are zero. If the first difficulty bytes are all zero/null, this means that the nonce produces a valid block, and can be returned to mineManager through either noncechan in go or noncequeue in Java.

Note that the miner is called with the argument block. This argument is produced in mineManager, and has the following structure, where NULL_NONCE is simply 32 bytes that are all zero:

block = ([NULL_NONCE] + [PRIOR HASH] + [BLOCKHEIGHT] + [MINER_ADDRESS] + BLOCKDATA)

When your node creates a block, it should broadcast this block to its peers. mineManager already has this functionality implemented. Nodes do not add blocks received from other peers to their own chain.

Part 2: Concurrent Mining (Due 9/26/19 11:59PM)

Notice that despite taking the numcores argument, mineManager does not actually make use of this argument. In other words, the sample code does not have the ability to utilize more than one CPU core to mine at the same time. For this part of the assignment, you will implement this functionality. You will need to edit both mineManager and mine()/Miner. Note that, especially at low difficulties, two different mining threads may find two different valid nonces at the same time. You should ensure that this eventuality is properly handled in your final submission.

Submission Format

For both parts of this assignment, you will be submitting a .zip file of a directory named mvbcoins laid out in an identical fashion to our sample code. The directory should be laid out in the following manner:

mvbcoins/
    Makefile
    src/

Makefile is executed by simply calling make (See Makefile. Internally, the Makefile should compile your sources and output a file called node inside mvbcoins/

After calling make, mvbcoins will look as follows

mvbcoins/
    Makefile
    node
    src/

If node is compiled in some strange directory, you will be penalized.

node can be written in Python, Golang, or Java. If you are submitting your program in Python, please ensure that it is wrapped up in a shell command, which then calls the interpreter. All tests will be run as:

./node arguments

Important: Your submission must work on Fractus. In general, a 32/64-bit Linux machine (not any arbitrary Unix, and definitely not Windows), but, in particular, Fractus from MP0.a (Eucalyptus) or MP0.b (OpenStack).

If your project cannot be compiled from the command line using the make file and needs some special IDE or tools, your submission will not be accepted.

Detailed Description of Message Types

When your node accepts a connection, it must read in messages from the sender. All messages will be raw bytes. By convention, if we say:

M = [VALUE1(6B)||VALUE2(32B)]

This means that the message is a 38 bytes message, where the first 6 bytes are VALUE1 and the next 32 bytes are VALUE2.

For this assignment, numeric values in messages will be encoded using base 10, and using the ASCII characters '0', '1', '2', '3', etc. In addition, values will be prepended with zeros in order to meet the size of their field. For example, in a BLOCK message, a BLOCKHEIGHT of 53 would be encoded as the string of ASCII characters "00000000000000000000000000000053". Though this is inefficient, this does make messages more readable when output in a raw form, which may help with debugging.

TRANSACTION
(1B, 32B, 32B, 32B, 32B)
[0, SENDER, RECEIVER, AMOUNT, TIMESTAMP]
The first byte is the opcode, which is 0.
The SENDER is the ID of the sender. This is the byte array of their ID
The RECEIVER is the ID of the receiver. This is the byte array of their ID
We will explain the ID parameter more in Part 1.b.
CLOSE
(1B)
[1]
This indicates that no more transactions will be sent.
The only byte is the opcode, which is 1.
BLOCK
(1B, 32B, 32B, 32B, 32B, 32B, 128B * numTransactionsInBlock)
[2, NONCE, PRIOR HASH, HASH, BLOCKHEIGHT, MINER_ADDRESS, BLOCKDATA]
Description: The first byte is the opcode, defaults to 2.
The NONCE is the nonce of this block, which must be mined.
PRIOR HASH is the hash of the prior block (genesis block hash PRIOR_HASH as SHA256(0)).
HASH = SHA256(NONCE||PRIOR HASH||BLOCKHEIGHT||MINER_ADDRESS||BLOCKDATA).
BLOCKHEIGHT is the height of the block (genesis block has height 0).
MINER_ADDRESS is your node address, as described above.
BLOCKDATA = [SENDER||RECEIVER||AMOUNT||TIMESTAMP||SENDER||RECEIVER||AMOUNT||TIMESTAMP…].
A block has numTransactionsInBlock number of transactions, for a total of 128B * numTransactionsInBlock bytes.
GET_BLOCK
(1B, 32B)
[3, BLOCKHEIGHT]

Any messages (other than GET_BLOCK messages) should be forwarded to peers.
When you receive a CLOSE message, this means you will not receive any more messages and once you are done processing, your node should terminate.

Testing

On CMS, there are two executables called tester and server. Tester will send transactions to your node. To see a full list of accepted arguments for tester, run ./tester -h.

The main parameters you need to worry about are:

ports: Ports to send transactions to. This is where you specify your node's port
testtransaction: Indicates the tester should send transactions
testblocks: Indicates the tester should send blocks. Note that you should not add these blocks to your own node's blockchain.
withdoublespends: Flag to test peers sending duplicate transactions
concurrentconns: Number of connections to simulate
numtransactions: Number of transactions to send to node
verbose: Increase detail of print output. This is useful for debugging

As an example, if your node is listening on port 10001 and you want to send 1000 transactions from a single connection, you would run:

./tester --ports 10001 --testtransaction --concurrentconns 1 --numtransactions 1000

server listens for incoming messages on port 10000 and prints the messages. This is a good way to check that you are broadcasting messages correctly.There are no parameters you need use, so all you have run is ./server. Be careful about how you connect to server, as it may print messages in a jumbled order if you send multiple concurrent messages. You should use tester and server to sanity check your message parsing.

Submitting

Zip your entire mvbcoins software distribution directory and submit the output mvbcoins.zip. You can use a command like: zip -r mvbcoins.zip mvbcoins

For part 2, in addition to the mvbcoins zip file, submit a document describing how your performance involves as the number of cores increases. The document should include

Initial performance at the end of part 2 and the final performance at the end of part 3.
How you profiled and discovered bottlenecks in your implementation.
Architecture Design: How you designed and improved your node to overcome the bottlenecks and take advantage of multiple cores.
A graph where the y-axis is the number of blocks/second, and the x-axis is --numcores.

References

[1] Bitcoin: A peer-to-peer electronic cash system. Nakamoto, Satoshi. Consulted 1.2012 (2008): 28.

[2] Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction. A. Narayanan, J. Bonneau, E. Felten, A. Miller, S. Goldfeder. Princeton University Press; 2016.
Read Chapters 1 and 2.