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/
- Makefile is executed by simply calling
make
(See Makefile. Internally, the Makefile should compile your sources and output a file called node inside mvbcoins/
- 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:
- port: Port your node is listening on
- peers: A comma separated list of peer ports your node will broadcast transactions received to.
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.
- 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.
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:
- ports: Ports to send transactions to. This is where you specify your node's port
- testtransaction: Indicates the tester should send transactions
- doublespend: 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. 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:
- numtxinblock: The number of transactions to be put in a block. Defaults to 50,000.
- difficulty: Difficulty parameter. This is the number of leading bytes that must be zero during mining
Messages
Your node will also need to be able to handle the following messages:
- 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]
If you receive GET_BLOCK, then you must reply to the sender with the block at the specified height. If an invalid height is given, you can ignore it.
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:
- numcores: The number of cores your node supports.
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
- 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.