CS 6410: Advanced Systems (Fall 2018)

MVB: A Minimally-Viable Blockchain

(09/3/18 - 05:02PM)

Introduction

In this project you will be implementing a minimally viable blockchain, called MVB, and – consequently – will instantiate a new coin called MVBCoin.

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.

Deliverables

You will be submitting a .zip file of a directory which you will call mvbcoins. The internals of the directory will be laid out in the following manner:

mvbcoins/
    Makefile
    README.txt
    src/
  1. Makefile is executed by simply calling make (See Makefile. Internally, the Makefile should compile your sources and output a file called node inside mvbcoins/
  2. README.txt will include any special information you want us to know about your submission. This could include potentially some steps we need to take before running make. For example, your MVBCoins node is required to work on Fractus and may require some instructions for installing a software package. However, most likely (and ideally), README.txt should be empty and without any special instructions. But if you must absolutely request some special instructions, this is the place to put them. We will, however, not accept special instructions on modification of system-wide environment variables, such as – for example – special setups to GOPATH and GOROOT if you are using GO.

After calling make, mvbcoins will look as follows

mvbcoins/
    Makefile
    README.txt
    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.

Part 1: Transactions (Due 9/10/18 11:59PM)

Due 9/14/18 11:59PM

In Part 1, you will implement code to receive transactions from other nodes and broadcast the transactions to peers. Your executable will need to accept the following command line arguments: For example, if your node binds to port 9000 and your peers are on ports 9001 and 9002, you would run
./node --port 9000 --peers 9001,9002
Part 1 has two portions, 1.a and 1.b. You should complete 1.a before implementing 1.b.

Part 1.a: Messages

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.

Now, let’s say VALUE1 is, for example, a port number. If the port is 9000, then the most efficient way of encoding the value 9000 is in a 14 bit number, which you round up to 16 bits, for a total of 2 bytes. YOU WILL NOT BE EFFICIENT. You will, on the other hand, encode each digit as a single character, such that each digit is 1 byte. Furthermore, you must prepend the number with any leading zeros. In other words, you may not encode the port with only 4 bytes. You must encode with 6 bytes. In that case, VALUE1 must be the encoded byte string b’009000’, which as a raw byte array is [48 48 57 48 48 48].

For Part 1, there will only be two types of messages the node can send and receive.
  1. 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.
  2. CLOSE
    (1B)
    [1]
    This indicates that no more transactions will be sent.
    The only byte is the opcode, which is 1.
Any messages (TRANSACTION and CLOSE messages) should be forwarded to peers.
When you receive a CLOSE message, this means you will not receive more messages and once you are done processing, your node should terminate.

Part 1.b: UTXO Set

The UTXO set maintains how much money each SENDER and RECEIVER has in their account. When a node receives a transactions, it looks up the sender and receiver in the UTXO set and adds / removes the corresponding transaction AMOUNT. For this project, you will assume there are 100 sender / receiver accounts that can send or receive money. Each account initially has 100,000 MVBCoins.
The account IDs are the SHA hashes of intergers. Given an integer i, to create a SHA hash, you will have to do something like the following: id = to_string(sha256.sum(int_to_byte_array(i)))
Example Output:
sha256function('0') -> ‘5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9’
We will define 100 accounts, using the numbers 0 to 99. The UTXO set is initialized as follows:
for i = 0 to 100:
  account = get_sha_hash(i)
  add {account, 100000} to UTXO set

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. <\p>

Testing

You will download on CMS executables called tester and server. This tester will send transactions to your code. To see a full list of accepted arguments for tester, run ./tester -h. For now, the only parameters you need to worry about are:

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. Use the following command, exactly: zip -r mvbcoins.zip mvbcoins

Part 2: Blocks (Due 9/17/18 11:59PM)

In Part 2, you will add support for blocks to your node. You will need to add the following arguments to your node:

Messages

Your node will also need to be able to handle the following messages:

Blocks

If your node has numTransactionsInBlock number of transactions, it is time to mine. To mine, first compute
hash = to_string(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.
The hash is computed by finding the HASH of these values concated together.
When you compute the 32 byte HASH using your chosen NONCE, you check if the number of 0's correspond to your difficulty level. For example, if difficulty is 3, then you want to ensure that the first 3 bytes are integer 48 (this is '0'). If difficulty is 0, then you do not need any leading zeros. Once an appropriate nonce is found, the block has been mined, and must be broadcast to all peers.

When you create a block, you must broadcast the block to your peers. If you receive a block, you do not need to add the block to your block chain.

A good way to test whether your basic logic is correct is to set difficulty to 0, so you don't want to wait for your miner to find a nonce.

Submitting

Zip your entire mvbcoins software distribution directory and submit the output mvbcoins.zip. Use the following command, exactly: zip -r mvbcoins.zip mvbcoins

Part 3: Concurrency (Due 9/24/18 11:59PM)

For Part 3, you will optimize your node, using concurrency. For this part, add the following command line arguments: Make sure to fully exploit the parallelism offered by the number of cores available.

Submitting

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

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.