Each lab will consist of a small problem and details of how to proceed. Each lab is intended to give every student hands-on experience with the core concepts and technologies covered during the course.  A student may concentrate, as a team member, on one technology over another for the final project, but labs are designed to give each and every student exposure to all the technologies that come into play.  You need to submit labs to the TAs for grading--see submission instructions below.  Generally, unless otherwise specified, you will have one week to complete each assigned lab.

See the syllabus for information on grading.  Turning in lab assignments on time is required, without exception, and all late deliveries will be penalized, regardless of cause.  Submit your assignments to the subversion repository according to the directions on the syllabus page.

Lab 7   Due: 5:00 PM, Friday, May 24, 2019

BACKGROUND:

Problem 1:  Write a Base58 encoding function:  

Create a working directory for Lab 7. 

We covered Base58Check encoding in our lecture.  Your first task is to write, in your language of choice, an implementation for base58 encoding.  A general introduction to Base58 encoding can be found on the Bitcoin wiki here.  An online site that will allow you to type in any text to check whether your function is working correctly can be found here.  You can both encode and decode on this site; therefore, you can check that your implementation of the algorithm is functional there.  You may find the BitcoinWiki discussion here helpful.  The associated video will also likely prove helpful.

Note that for Problem 1, all you have to do is write a functioning Base58 encoder.  You do not need to provide a decoder.  You can check your results online at the site mentioned above.  Note that although there are numerous libraries that provide working functions and methods for doing Base58 encoding, written in a variety of languages, you are expected to produce your own version of the algorithm and you may not use one existing, either in source code or in a library (such as SSL, bitcoinlib, etc.).  Note that if you can find and copy an implementation of base58 encoding online, we likely can find it too.  So do your own work.

Further, a Base58 encoder and decoder for legal bitcoin addresses can be found here.

Problem 2:  Bitcoin Address Generation:  

Step 1:  You will need base58check available (we will reuse yours from Problem 1 above a little later) to run the script that serves as our initial example.  To install, simply execute:  "sudo pip install base58".  Confirm that you have it installed and available by executing:

$ echo "hi" | base58

As output, you should see:  "c55T".

Step 2:  Download this zip file into your working directory.  Unzip it and type make.  If you get an error about secp256k1 being missing, you need to install this small library from source as follows:

git clone https://github.com/libbitcoin/secp256k1
cd secp256k1
./autogen.sh
./configure
make
sudo make install

Then, visit this web page that describes in detail how to create a bitcoin address (for mainnet) from a secret and public key created through elliptic curve cryptography along with various hashing algorithms.  Read through the page carefully to see how the bitcoin address "1PMycacnJaSqwwJqjawXBErnLsZ7RkXUAs" is created from an initial private ECDSA Compressed Public Key of "18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725". 

After understanding the general idea, execute the following script in the directory you unzipped the zip file above in (after having successfully run make):

$ runitCPP3.sh
Starting with ECDSA key from STEP 0: 18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725
STAGE 0 is: 18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725
secret: 1qN5zM32g7pvJictqC1nz2v8kpMvdws3m5PMb7WEVrrAMQoZvsE
Public key: 0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352
STAGE 1 is: 0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352
Private key: 1qN5zM32g7pvJictqC1nz2v8kpMvdws3m5PMb7WEVrrAMQoZvsE
EC Point: 0450863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b23522cd470243453a299fa9e77237716103abc11a1df38855ed6f2ee187e9c582ba6
s: 0450863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b23522cd470243453a299fa9e77237716103abc11a1df38855ed6f2ee187e9c582ba6
x coord: 50863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352
y coord: 2cd470243453a299fa9e77237716103abc11a1df38855ed6f2ee187e9c582ba6
Public Key Compressed:
0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352
Working with Compressed Public Key: 0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352
STAGE 2 is: 0b7c28c9b7290c98d7438e70b3d3f7c848fbd7d1dc194ff83f4f7cc9b1378e98
STAGE 3 is: f54a5851e9372b87810a8e60cdd2e7cfd80b6e31
STAGE 4 is: 00f54a5851e9372b87810a8e60cdd2e7cfd80b6e31
STAGE 5 is: ad3c854da227c7e99c4abfad4ea41d71311160df2e415e713318c70d67c6b41c
STAGE 6 is: c7f18fe8fcbed6396741e58ad259b5cb16b7fd7f041904147ba1dcffabf747fd
STAGE 7 is: c7f18fe8
STAGE 8 is: 00f54a5851e9372b87810a8e60cdd2e7cfd80b6e31c7f18fe8
STAGE 9 is: 1PMycacnJaSqwwJqjawXBErnLsZ7RkXUAs

Notice the output above that is preceded with the prefix "STAGE X:" with X running from 0 through 9.  Compare the output of these various STAGE outputs [0-9] above with the steps described in the web page above.  Note especially in the code (both C++ and the shell script b58converter2.sh) that we are working with binary data.  This should be familiar to you now.  Note and understand what the multiple calls to xxd -r -p are doing.

Step 3:  Your job is to code, in your language of choice, the specific steps 0 through 9.  For Problem 2 (with the exception of STAGE 9 below), you may use any set of libraries available to perform the ECDSA cryptography as well as any library functions (openSSL, bitcoinlib, etc.) providing the requirements for STAGEs 0 through 8 (your mileage may vary if you chose libreSSL FYI...you are better off using the actual OpenSSL libraries).  You may find the OpenSSL libraries here.  For those working in python, you will want to make sure you have pip installed ecdsa and that you are importing (at least) os, binascii, ecdsa, annd hashlib.  There are of course other options as well. 

Everyone will be dealing with very big numbers here.  So make sure you have the appropriate tools in place for such support (e.g., Golang people might look into "math/big", etc.).  And of course there are the C++ bitcoin core libraries as well...e.g., libbitcoin.

Note in the final stage, STAGE 9, you are to use your own Base58Check encoding function that you created above in Problem 1.  Your code output should match the output of each of the "STAGE X" printouts from runitCPP3.sh above (you do not need to match the other output unless you wish...that said, we will be impressed if you can print out the EC point value).  That is to say, at a minimum, your output should display (precisely, at a minimum):

$ myprog
STAGE 0 is: 18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725
STAGE 1 is: 0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352
STAGE 2 is: 0b7c28c9b7290c98d7438e70b3d3f7c848fbd7d1dc194ff83f4f7cc9b1378e98
STAGE 3 is: f54a5851e9372b87810a8e60cdd2e7cfd80b6e31
STAGE 4 is: 00f54a5851e9372b87810a8e60cdd2e7cfd80b6e31
STAGE 5 is: ad3c854da227c7e99c4abfad4ea41d71311160df2e415e713318c70d67c6b41c
STAGE 6 is: c7f18fe8fcbed6396741e58ad259b5cb16b7fd7f041904147ba1dcffabf747fd
STAGE 7 is: c7f18fe8
STAGE 8 is: 00f54a5851e9372b87810a8e60cdd2e7cfd80b6e31c7f18fe8
STAGE 9 is: 1PMycacnJaSqwwJqjawXBErnLsZ7RkXUAs

Once you have your desired output from STAGE 9, viz. "1PMycacnJaSqwwJqjawXBErnLsZ7RkXUAs", you should verify that this is indeed a valid bitcoin mainnet address by visiting this site and entering the address.

NOTE:  You are not expected to code your own implementation of elliptic curve private key generation.  You may leverage any of a number of libraries that provide such capability, including python's ecdsa etc.  Java people may wish to investigate options from Bouncy Castle.