Introduction

This is a three-part whitepaper that describes the Accelchain blockchain. This whitepaper is for engineering teams building protocol-conforming wallets and miners. At the end of Part 3, your engineering team will be able to build a working node that is capable of processing transactions, mining accelcoin, and participating in the global Accelchain network.

We direct investors to our investor onboarding team.

Requirements and Libraries

Install the Racket cryptography library from the command line:

On Windows PowerShell:
```
& C:\Program Files\Racket\raco.exe pkg install crypto
```
On macOS Terminal:
```
"/Applications/Racket 8.5/bin/raco" pkg install crypto
```
You may have Racket 8.6 installed instead of 8.5.
We have provided a crypto-extras.rkt file makes the Racket cryptography library easier to use. Download it and put it in the same directory as your solution.

To use the library add (require "./crypto-extras.rkt") to the top of your solution file.
We have provided a hashtable-extras.rkt file to make immutable hash tables available.

To use the library add (require "./hashtable-extras.rkt") to the top of your solution file.

Immutable Hash Tables

We discussed association lists and binary search trees in the previous lab. An immutable hash table is is a map from keys to values, just like association lists and BSTs. However, under the hood, Racket does work to make lookups and inserts significantly faster. The hashtable-extras library defines the following functions:

;; A [Hash-Table-of X Y] is a (make-hash (list (list X Y) ...))
;; where X is the key and Y is the value that the key maps to

;; make-hash : [List-of [List-of-Two X Y]] -> [Hash-table-of X Y]
;; Creates a hash table from a list of pairs.

;; hash-has-key? : [Hash-table-of X Y] X -> Boolean
;; Checks if a hash table has a key. Returns #true if it does, #false otherwise.

;; hash-ref : [Hash-table-of X Y] X -> Y
;; Returns the value associated with the key in the hash table.

;; hash-set : [Hash-table-of X Y] X Y -> [Hash-table-of X Y]
;; Returns a new hash table with the key mapped to the value.

;; hash-remove : [Hash-table-of X Y] X -> [Hash-table-of X Y]
;; Returns a new hash table with the key removed

;; hash-keys : [Hash-table-of X Y] -> [List-of X]
;; Returns a list of all the keys in the hash table

;; hash-values : [Hash-table-of X Y] -> [List-of Y]
;; Returns a list of all the values in the hash table

Cryptography

The Racket cryptography library gives you access to a wide variety of cryptographic operations. However, we are only going to use two of them:

We will use 512-bit RSA public/private keys to sign transactions and identify wallets.
We will use the SHA-256 cryptographic hash function to build the block chain.

The crypto-extras library makes these operations easy to use, and defines the following functions and data:

;; A PrivateKey is a String that represents a 512-bit RSA private key.

;; A PublicKey is a String that represents a 512-bit RSA public key.

;; A Signature is a String that represents a 512-bit RSA signature.

;; digest : String -> Nat
;; Produces the SHA256 digest of the given string. SHA256 is a cryptographic
;; hash function that is used in many blockchains, and we will use it too.

;; secret->public : PrivateKey -> PublicKey
;; Generates a public key from a private key.

;; make-signature : String PrivateKey -> Signature
;; Signs a string with a private key.

;; check-signature : PublicKey String Signature -> Boolean
;; Checks if the given string was signed by the given public key.

You may be wondering why we use strings to represent keys and signatures instead of numbers. It turns out these strings represent numbers compactly, and we need them to be strings to send them over the network.

Auxiliary Data Definitions

;; An [Optional X] is one of:
;; - X
;; - #false
;;
;; Interpretation: Either a value of type X or #false

Part 1: Offline Validation and Mining

In the first part of this whitepaper, we will develop mining and validation algorithms for Accelchain that work offline. Therefore, your program will not be engaging in real trades with others at this time.

You should use the following data definitions verbatim in your solution.

(define-struct transaction [serial sender-sig sender-key receiver-key amount])
;; A Transaction is a (make-transaction Nat Signature PublicKey PublicKey Nat)
;;
;; (make-transaction serial sender-sig sender-key receiver-key amount) represents a
;; single transaction that moves amount accelcoin from sender-key to receiver-key.
;; Moreover:
;;
;; 1. The amount must be positive;
;; 2. The signature signs the string (string-append receiver-key ":" (number->string amount))
;;    with the private key corresponding to sender-key.

(define-struct block [transactions nonce miner-key])
;; A Block is a (make-block [List-of Transaction] Nat PublicKey)
;;
;; (make-block transactions nonce miner-key) represents a block of transactions mined by miner-key.
;; The transactions are processed left-to-right. Thus (first transactions) occurs before 
;; (second transactions).


;; A Blockchain is a [NE-List-of Block]
;;
;; The first element of a Blockchain is the latest block and the last element is the first
;; block or the *genesis block*. The genesis block has zero transactions and all other blocks have
;; three or more transactions.

Examples of Transactions

Writing examples of transactions is a big pain, because you have to generate a signature, while taking care not to accidentally put the private key in the transaction. You also need examples of private and public key. Here is an example that you can use (but we will do better):

(define ALICE-PRIVATE-KEY "MIIBOgIBAAJBAMrPOfefdvowOwAplxY/NLkJFymyedikvwvsyhtQ98CawNXeKydg+WYD9YzQW1tIY5Ta1bqZhk5hpWGM4eusKxkCAwEAAQJAMtQW2hmsLu3xi4vg4uF6bDl8BaZGZWZ8vxdcW9ZCEZIEtnYGlkpwoG5YcUp3a39YRP+Nt2fA6bmPbvjmWAspkQIhAPodYjlh0p7P4QodsvQinMRp9Z8knfBmYeQpg/0otBMVAiEAz5Tjyw0Yanh6CCIvDRKQ+SvdTMvrJykIMyzmsWgYSPUCIEwGvIG2w3/0rnIVvvzIvKBTmQ7L4ZpedKkXGYDNa5dVAiAfRL5Lh911rFA1iXCs927/GaxsNQtnCrdBfjIB5zxBQQIhAO0ZN+PGdjJfbhivUdgfx+DbrHkClSWT8SidILAbgQkd")
(define BOB-PRIVATE-KEY "MIIBOwIBAAJBAKy4zO2w1HfXMNHSCYKuheD+5ZkAlHubePYNOVvi3gA/AQ1S0HcRFmTkzFz/SCp+0cZ3wErzHhKXmvgIrjLbdYMCAwEAAQJACBwBGyPTRfEnjKJk6erRxFeTZhSd5BPPoRXL3KGRNMesv5qct9QNbHA2ghjY4Z1gokwLgCViG88FvG0qMKGNSQIhANduvtUGGvqeb+c6khwi60sf/3KMa082IjC3fe4RosJPAiEAzT8eusKDsL3q38i1o6E4pzUuW4oK0ta1BCGEdZn2kI0CIDb6bz8ECNyOlHZJL0J48t1ANDuydCxJ313ZZgzceVHnAiEApVA7vg1B6K9vaIPO2VbXvMW26wAKq7tH3WXpvJcf41kCIQCTv8zWOp8Dq3NKTdFZD28NCohpiEOAP3yMng9HhXcAqg==")
(define ALICE-PUBLIC-KEY (secret->public ALICE-PRIVATE-KEY))
(define BOB-PUBLIC-KEY (secret->public BOB-PRIVATE-KEY))

;; Sends 100 accelcoins from Alice to Bob
(define EX-TRANSACTION-0
  (make-transaction
   0
   (make-signature (string-append BOB-PUBLIC-KEY ":" (number->string 100)) ALICE-PRIVATE-KEY)
   ALICE-PUBLIC-KEY
   BOB-PUBLIC-KEY
   100))

We hope you agree that just writing an example of a transaction is really annoying.

Design the following function that makes it easier to write examples of transactions:

;; build-transaction: Nat PrivateKey PublicKey Nat -> Transaction
;; (build-transaction serial sender-private-key receiver-public-key amount) builds a transaction
;; that sends amount from the sender to the receiver.

You do not have to write unit tests for this function, but use it to write more examples of transactions. For example, here is a way to redo the example above:

(define EX-TRANSACTION-0 (build-transaction 0 ALICE-PRIVATE-KEY BOB-PUBLIC-KEY 100))

Design the following function to turn a transaction into a string:

;; transaction->string : Transaction -> String
;; Serializes a transaction into a string with the format
;; "transaction:sender-sig:sender-key:receiver-key,amount"

Examples of Blocks, Digests, and Mining

Now that you have transactions, you should write examples of blocks. Here is one example of a genesis block with no transactions:

;; A genesis block where Alice starts the blockchain and receives the first mining reward.
(define EX-BLOCK-0 (make-block '() 8631727707325622792404128232286945630015639849891523695238049493932286431978 ALICE-PUBLIC-KEY))

Write examples of real blocks that must have 3+ transactions. You will need to pick a nonce value for each block. Use 0 to get started; but you will need to mine to produce valid nonces.

We strongly recommend creates blocks that can plausibly start from a genesis block. So, a block that starts from the example block above should begin with Alice sending accelcoin to others.

Design the following function to calculate block digests:

;; block-digest: Digest Block -> Digest
;; (block-digest prev-digest block) computes the digest of block, given the digest 
;; of the previous block.
;;
;; The digest must be the digest of the following strings concatenated in order:
;;
;; 1. prev-digest as a string
;; 2. The transactions as strings (using transaction->string) concatenated in order
;; 3. The nonce as a string

Note that you cannot compute the block digest of a genesis block, since there is no previous block. Therefore, assume that the genesis block has digest 0. However, at this point you should calculate the digests of your example blocks.

In the Accelcoin protocol, block digests must be less than DIGEST-LIMIT:

;; Copy this definition to your solution
(define DIGEST-LIMIT (expt 2 (* 8 30)))

Are any of your block digests valid?

Design the following function:
```
;; mine-block : Digest PublicKey [List-of Transaction] Nat -> [Optional Block]
;; (mine-block prev-digest miner-public-key transactions trials)
;; tries to mine a block, but gives up after trials attempts.
;;
;; The produced block has a digest that is less than DIGEST-LIMIT.
```
Your function will have to guess a nonce. To make a guess, use the random function that is built-in. (random n) produces a positive integer less than n. However, n cannot be arbitrarily large. Use (random 4294967087) to get the widest range of values.

It is hard to test mine-block independently, so you do not need to write unit tests.
Use your mine-block function, which is essentially a smart constructor, to produce some valid blocks, including chains of valid blocks. You will need to specify a number of trials to allow. A million trials should be fairly reliable at mining a block.

You can test mine-block with block-digest as follows:
```
(define EX-MINED-BLOCK-1 ...)
(check-expect (< (block-digest 0 EX-MINED-BLOCK-1) DIGEST-LIMIT) #true)
```

Blockchain Validation

In addition to mining, we need to ensure that transactions and blocks are valid ( properly signed, with balances available, etc.) Without validation, you may end up accepting bogus transactions send by malicious peers.

We can break validation down into several independent steps listed below. Complete the following functions.

;; blocks-sized-ok? : Blockchain -> Boolean
;; Determines that every block has at least three transactions, and that
;; the genesis block has zero transactions.

;; no-duplicate-transactions? : Blockchain -> Boolean
;; Determines if every transaction in the blockchain appears exactly once. Every
;; transaction has a unique serial number that we use to determine if it is unique.

Recommendations:

Use list abstractions and helper functions.
It may help to design this helper:

  ;; map-transactions : (Transaction -> X) Blockchain -> [List-of X]
  ;; Essentially a transaction-level map for blockchains.

;; all-signatures-ok? : Blockchain -> Boolean
;; Determines if every transaction in the blockchain has a valid signature.

Recommendation: Use list abstractions and map-transactions.

;; valid-digests? : Blockchain -> Boolean
;; Determines if every block has a valid digest.

Recommendation: Write a (local) helper function with the following signature that uses the non-empty list template:

;; valid-digests-helper : Blockchain -> [Optional Digest]
;; (valid-digests-helper bc) produces #false if any block has an invalid digest.

Note that every block must have a valid digest. It is not enough for the latest block to have a valid digest.

;; account-balances-ok? : Blockchain -> Boolean
;; Determines if every transaction sends at least 1 accelcoin and every sender
;; always has enough accelcoin to send.

The miner receives 100 accelcoin as their mining reward for every block.

Recommendation: This is the most involved function in Part 1. We recommend designing the following helper functions:

;; A Ledger is a [Hash-Table-of PublicKey Nat]
;; A ledger maps wallet IDs (public keys) to the number of accelcoins they have.

;; reward : PublicKey Ledger -> Ledger
;; Grants the miner the reward for mining a block.

;; update-ledger/transaction: Transaction Ledger -> [Optional Ledger]
;; Updates the ledger with a single transaction. Produces #false if
;; the sender does not have enough accelcoin to send or if the transaction
;; amount is less than 1.

;; update-ledger/block : Block Ledger -> [Optional Ledger]
;; Updates the ledger with the transactions in a block, and rewards the miner.
;; Produces #false if any transaction in the block would make a sender's
;; balance negative. The miner receives their reward *after* all transactions
;; are procsed.


;; update-ledger/blockchain : Blockchain Ledger -> [Optional Ledger]
;; Produces the ledger for a blockchain, or #false if any transaction
;; would make the sender's balance negative.

With this series of helpers in place, you can use the following definition for account-balances-ok?:

(define (account-balances-ok? bc)
  (not (false? (update-ledger/blockchain bc (make-hash '())))))

Put everything together to validate a blockchain:
```
;; valid-blockchain? : Blockchain -> Boolean
;; Determines if a blockchain is valid.
```
Congratulations, you now have a validator.

Part 2: Validating Transactions on the Accelchain Network

In this part of the Accelchain whitepaper, we will cover:

How to validate transactions and blocks posted to the Accelchain network, and
How to post transactions to the Accelchain network.

Part 3 will cover mining on the network.

Prerequisites

We have updated crypto-extras.rkt and hashtable-extras.rkt. Please download them again.
You will also need http-extras.rkt.

Accelchain Protocol Update

Before using the Accelchain network, we update the data definition of transactions to include a new unique-string field, as shown below:

(define-struct transaction [serial unique-string sender-sig sender-key receiver-key amount])
;; A Transaction is a (make-transaction Nat String Signature PublicKey PublicKey Nat)
;;
;; (make-transaction serial unique-string sender-sig sender-key receiver-key amount) represents a
;; single transaction that moves amount accelcoin from sender-key to receiver-key.
;; Moreover:
;;
;; 1. The amount must be positive;
;; 2. The unique-string must be globally unique;
;; 2. The signature signs the string 
;;      (string-append unique-string receiver-key ":" (number->string amount))
;;    with the private key corresponding to sender-key.
;; 3. the unique-string is a string that is unique to this transaction.

The unique-string must be globally unique, and will protect your transaction from a “replay attack”, where a malicious party just repeats your transaction. You should:

Use the updated definition of Transaction above.
Update build-transaction to produce a unique string. You can use the (unique-string) function provided by the crypto-extras library.
Update the signature to include the unique string, as shown in the data definition.
Update transaction->string to produce a string in the format of "serial:transaction:unique-string:sender-sig:sender-key:receiver-key,amount" (added serial field and unique-string). This should also change the output of block-digest.
Update the rest of your code as appropriate.

Your Private Key

In the first part of the whitepaper, you used known private keys (e.g., ALICE-PRIVATE-KEY and BOB-PRIVATE-KEY) to sign transactions. Do not these keys on the Accelchain network. Anyone will will be able to steal accelcoins sent to those keys.

Instead, create a fresh private key as follows:

(require "./crypto-extras.rkt")
(make-secret)

The make-secret function produces a new, and unique private key every time it is applied. Save the generated key and store it as a constant in the program:

(define MY-SECRET-KEY "the string from (make-secret)")

Without this step, the private key is lost after the program quits, and any accelcoin sent to that key is lost forever. Finally, do not share this key with anyone. The public wallet ID is is (secret->public MY-SECRET-KEY). In the rest of the program, be careful not to accidentally use your private key when you mean to use your public key.

Limited Time Offer: Free Accelcoin

If you publicly post your public key on CampusWire, the staff will send you free accelcoin to help you get started trading. This is a limited time offer, valid while supplies last.

Free accelcoin

Broadcasting a Transaction on the Accelchain Network

The global Accelchain network has broadcaster nodes located worldwide. The nearest broadcaster node is in Holyoke, MA at the MGHPCC and its domain name is broadcaster.federico.codes.

You can visit https://broadcaster.federico.codes/0 to see all transactions and blocks beginning with the first block. (You can increase 0 to a higher number to see a suffix of the blockchain.)
You can post a transaction or block to the broadcaster to have it broadcast across the network.

Racket and other programming languages have libraries that make it relatively easy post web data. We have provided a small library that simplifies it a little further.

To broadcast a transaction, use the function:

(post-data "broadcaster.federico.codes" "/" transaction-str)

Above, transaction-str is a string that represents a transaction without the serial number. (The broadcaster will assign the serial number.) Specifically, transaction-str must be a string of the form:

"transaction:unique-string:signature:your-public-key:receiver-public-key,amount"

It will help to write the following function that uses post-data as described above:

;; send-transaction: PrivateKey PublicKey Nat -> Boolean
;; (send-transaction sender-private-key receiver-public-key amount) sends a
;; transactions to the Accelchain broadcaster.

Try to use it to send accelcoin to someone. After applying the function, if you or anyone visits https://broadcaster.federico.codes/0, you will see the transaction at the bottom of the blockchain, with its assigned serial number. NOTE: The stream of messages has a limited window of 50, so you may need to increase the starting id (0 in the example above) to find your message

Recall from Part 1, that a transaction is not processed until it is included in a block. Although you won’t build a miner until Part 3, others on the Accelchain network who will eventually mine your transaction while you are working on Part 2.

Validating Transactions

Finally, you’re ready to build a validator that runs online. Your validation code from Part 1 was designed to validate a complete blockchain. However, an online validator has to incrementally validate new transactions and blocks (and discard any invalid blocks or transactions it may receive.) You will be able to use most of your code from Part 1, but will need a few extra checks to validate online.

Your validator will need to implement two functions handle-block and handle-transaction and a design a data definition called ValidatorState:

```
handle-transaction : ValidatorState Transaction -> [Optional ValidatorState]
```
This function receives a ValidatorState and a new transaction. It produces #false if:

a. The transaction signature is invalid; or b. The transaction is a duplicate (based on unique-string).

Otherwise, it produces a new ValidatorState that records the new transaction. However, note that the new transaction is not procssed until it appears in a block.
```
handle-block : ValidatorState Block -> [Optional ValidatorState]
```
This function receives a ValidatorState and a new block. It produces #false if:

a. The block digest is invalid; b. The block has fewer than three transactions; c. update-ledger/block produces #false; or d. If any of the transactions in the block are duplicated or altered. (You must receive a transaction on handle-transaction before it appears in handle-block.)

Otherwise, it produces a new ValidatorState that adds the new block to the blockchain.
ValidatorState must have a Ledger, a Blockchain, and some other items that you will need to choose.

The initial value of ValidatorState will need to contain the genesis block of the Accelchain network, which is the following block:

(make-block '() 1337 "AAAAB3NzaC1yc2EAAAADAQABAAAAQQDbXz4rfbrRrXYQJbwuCkIyIsccHRpxhxqxgKeneVF4eUXof6e2nLvdXkGA0Y6uBAQ6N7qKxasVTR/2s1N2OBWF")

Remember that the genesis block is assumed to have digest 0 and awards 100 accelcoin to the mining public key in the block. So, the initial Ledger will award 100 accelcoin to the mining key shown above.

Putting it all together

Finally, you can put all of the pieces together to build a validator that runs online:

(define (go init-state)
  (blockchain-big-bang
     init-state
     [on-transaction transaction-handler]
     [on-block block-handler]))

When you run go, your validator will start to receive transactions and blocks, and run continuously.

Is it actually working? A blockchain relies on consensus. We wil post daily updates with the current ledger, so you can check if your ledger is equivalent.

Optional: Printing the State

blockchain-big-bang allows to specify a third optional handler (show-state):

(define (go init-state)
  (blockchain-big-bang
    init-state
    [on-transaction transaction-handler]
    [on-block block-handler]
    [show-state show-state-handler]))

The show-state handler will print out the state every 50 messages, without the handler the state will not be printed. You are not required to use this handler, but it may be handy for debugging. The handler consumes a function show-state-handler : ValidatorState -> String.

Part 3: Mining

Is this the end of crypto?

Undeterred by current events, you are now going to start mining Accelcoin. The rest of this whitepaper describes how to write a miner.

High-Level Overview

Remember that your miner is also a validator. You will receive transactions sent by others, but they may be bogus. So, use this opportunity to fix any issues with your validator from Part 2.
Your miner will need to be fast. To do that, we strongly recommend that you update ValidatorState in the following way:

a. Your validator does not actually need to store the full blockchain: all it needs is 1) the current ledger, 2) the set of pending transactions, 3) the set of unique strings for transactions that were received, and 4) the digest of the last block on the blockchain.

b. Instead of representing the set of pending transactions and unique strings as lists, you should represent them as follows:
- For the pending transactions, use [HashTable-of Nat Transaction] where the keys are the serial numbers of the transactions.
- For the unique strings, use [HashTable-of String Boolean] where the keys are the unique strings of the transactions.
Update transaction-handler to use update-ledger/transaction, and reject any transactions where update-ledger/transaction produces #false. Do not actually update the ledger, but just check that it would succeed.
We strongly recommend deleting functions that you do not need. E.g., you should not use functions such as valid-blockchain? at this point.
Finally, build a miner as described below.

Mining and Sending Blocks

To send blocks on the network, we need a way of serializing a Block into a String. The following function will do so:

(require racket/string)

;; block->string : Block -> String
;; Serializes a block into a string with the format.
(define (block->string blk)
  (local [(define transactions (block-transactions blk))
          (define transaction-strings
            (map (lambda (t) (string-replace (transaction->string t) ":" ";")) transactions))
          (define transaction-string (string-join transaction-strings ":"))]
         (format "block:~a:~a:~a" (block-nonce blk) (block-miner-key blk) transaction-string)))

To mine a block, write the following function:

;; mine+validate : ValidatorState PublicKey Number -> Boolean
;;
;; (mine+validate state miner-key retries)
;;
;; Uses mine-block (from Part 1) to mine the pending transactions in
;; the validator state.
;;
;; Produces #false if the retries are exhausted or if the number of pending
;; transactions is less than three.
;;
;; If mining succeeds, sends the serialized block using post-data and produces
;; #true.

Mining Blocks Indefinitely

A miner does not terminate after mining just one block. Moreover, others are mining the same transactions that you are. So, how would you know if the block you are currently mining has already been mined? To address this, you will alternate between mining and validating.

Define the function:

;; go-miner : ValidatorState PublicId Number -> ValidatorState
;;
;; (go-miner state miner-key retries) mines the pending transactions in state
;; uses `go` to validate the current blockchain, and then recurs indefinitely.

The number of retries function determines the rate between trying to mine a block and updating the ValidatorState from the broadcaster. When there are few miners in the blockchain this number should be high, while when there are a lot of miners this number should be low.

You can start by setting this number to a small constant. But, may eventually want to change it. Alternatively, you can try to build an algorithm that finds the optimal number of retries given your history of success and failure in mining blocks, but it is not required in the assignment.

Submission and Grading

Please delete unused functions from Part 1 in your final submission.
Put the public key of your miner in a comment on the first line of your submission.
The submission with the most accelcoin will receive a 100% grade for this assignment.
To receive more than 85%, you must mine some accelcoin. (Even if it’s just 1 coin.)
It is still possible to receive 100% without successfully mining, but unlikely.