Wednesday, July 1, 2015 12:00 am

Bitcoin Hash Functions and Printer Drivers

Written by
Rate this item
(1 Vote)

This is the second of two posts about a Bitcoin vending machine I built while working for NetBurner. Part 1 is more philosophical.

The logic of my Bitcoin vending machine is simple enough:

  1. Wait for a coin pulse
  2. Generate a new Bitcoin address
  3. Send coins from my address to the new one
  4. Print QR codes

And repeat. I used a thermal printer and a coin acceptor from Adafruit and controlled them with NetBurner’s MOD5441x development kit. The source code for the whole project is on Bitbucket.

1. Integrating the Coin Acceptor

Insert Coin; Receive Bitcoin

I programmed the coin acceptor to emit ten 100 millisecond pulses when it detects a quarter. The trick was to read this without frying the microcontroller - the CH–924 coin acceptor runs at 12 volts and the NetBurner board runs at 3.3. I’ve developed a healthy respect for the laws of physics, so I enlisted the help of NetBurner engineer Dan Ciliske. We figured out that the coin acceptor pulses at 5 volts with a 10k internal resistor, so I added another 20 kiloohms of resistance to bring the voltage down to 3.3.

An artist makes a voltage divider

Safely back in software-land, I used NetBurner’s high-resolution timer class to poll the GPIO pin:

while (1) {
    while(!J2[GPIO_PIN].read()) {
        timer->pollingDelay(PULSE_TIME);
    }
    counter = 0;

    while(J2[GPIO_PIN].read()) {
        counter++;
        timer->pollingDelay(PULSE_TIME*2);
    }
    if (counter == QUARTER_PULSES) {
        iprintf("\nQuarter accepted\n");
        Go();
    }
}

2. The Bitcoin Address Protocol

Now for the hard part. Or at least the frustrating part - debugging cryptography code is now up there with image processing and user-interface programming among my least favorite activities. If your hashes are off by even a byte, then everything breaks - and Bitcoin uses three different hashing algorithms, plus its own method of string encoding. I’m not even going to pretend to understand elliptic curve cryptography (let alone SHA–256 or RIPEMD–160), so I’ll walk through the process of generating Bitcoin addresses at a high level.

2.1 The Private Key

A standard Bitcoin private key is just a random 256-bit number: an array of 32 random bytes. Because I wanted to display the keys as QR codes, I decided to use the slightly more complicated mini private key format. That was around when I began to understand the Bitcoin approach to technical challenges: hash everything. Then hash it again.

A mini private key is an array of 30 characters - an S followed by 29 random choices from a list of 58 “readable” characters. To check if a key is valid, you stick a ? on the end and take the SHA–256 hash. If the hash begins with 0, then the original 30-character array is a valid mini private key. The only way to find one is by brute force: you keep generating candidates, adding that ?, and calling SHA–256 on the result until you find a hash that begins with 0. The full private key is - you guessed it - the SHA–256 hash of the mini private key.

candidate[0] = 'S';
candidate[30] = '?';

while (!found) {
    for (int i = 1; i < 30; i++) {
        candidate[i] = chars[GetRandomInt(58)];
    }
    SHA2Init(&ctx_sha, false);
    SHA2Update(&ctx_sha, candidate, 31);
    SHA2Final(hash, &ctx_sha);

    if (hash[0] == 0x00) {
        found = true;
    }
}

I’m a completionist, so I decided to print the full private key as well, albeit in wallet import format. The process of converting a 256-bit private key to wallet import format consists of prepending a version byte to the array - 0x80 for addresses on the main Bitcoin network - and then encoding the result with Bitcoin’s Base58Check algorithm. Base58Check converts binary data to human-readable strings that consist of the same 58 characters used in mini private keys, with the addition of a 4-byte checksum. The checksum bytes are derived from the double SHA–256 hash of the extended private key. You add the version byte, take the hash, take the hash again, append the first four bytes of the hash to the end of the private key plus the version byte, and encode the result in base–58. I used the b58enc function from libbase58 for that part.

// prepend version byte
key[0] = 0x80;
memcpy(key + 1, in, len);

// Base58Check

SHA2Init(&ctx_sha, false);
SHA2Update(&ctx_sha, key, len + 1);
SHA2Final(hash, &ctx_sha);

SHA2Init(&ctx_sha, false);
SHA2Update(&ctx_sha, hash, 32);
SHA2Final(hash, &ctx_sha);

// append checksum
key[len + 1] = hash[0];
key[len + 2] = hash[1];
key[len + 3] = hash[2];
key[len + 4] = hash[3];

b58enc(out_str, &out_len, key, len + 5);

Bitcoin depends heavily on SHA–256. Fortunately, I was able to use a NetBurner implementation that worked out of the box. For the next two algorithms, I was on my own.

2.2 The Public Key/ Bitcoin Address

Not that I’m masochistic enough to try implementing elliptic curve cryptography myself. Bitcoin public keys are composed of coordinates on a specific elliptic curve known affectionately as “secp256k1,” so I used the aptly-named libsecp256k1. A Bitcoin address is more than just a public key, though - it’s a Base58Check encoded string of a RIPEMD–160 hash of a SHA–256 hash of a public key. Of course it is. I used the Bitcoin core implementation of RIPEMD–160, which worked fine after I accounted for NetBurner’s big-endian architecture - TP’s Go Bitcoin Tests were an extremely helpful debugging tool. All told, the code to generate a Bitcoin address from a private key looks like this:

// ECDSA public key

ctx_ecc = secp256k1_context_create(SECP256K1_CONTEXT_SIGN);

if (!secp256k1_ec_pubkey_create(
        ctx_ecc, pub, &pub_len, priv, false)) {
    return -1;
}

secp256k1_context_destroy(ctx_ecc);

// SHA-256 hash

SHA2Init(&ctx_sha, false);
SHA2Update(&ctx_sha, pub, pub_len);
SHA2Final(hash_sha, &ctx_sha);

// RIPEMD-160 hash

ctx_ripemd = CRIPEMD160();
ctx_ripemd.Write(hash_sha, 32);
ctx_ripemd.Finalize(hash_ripemd + 1);

hash_ripemd[0] = 0x00;

// Base58Check

SHA2Init(&ctx_sha, false);
SHA2Update(&ctx_sha, hash_ripemd, 21);
SHA2Final(hash_sha, &ctx_sha);

SHA2Init(&ctx_sha, false);
SHA2Update(&ctx_sha, hash_sha, 32);
SHA2Final(hash_sha, &ctx_sha);

// checksum
hash_ripemd[21] = hash_sha[0]; 
hash_ripemd[22] = hash_sha[1];
hash_ripemd[23] = hash_sha[2]; 
hash_ripemd[24] = hash_sha[3];

b58enc(out_str, &out_len, hash_ripemd, 25);

It turns out that libsecp256k1 can use up to 9 kilobytes of stack space, so I spawn a new task with an expanded stack size for key generation.

3. Transactions - blockchain.info

Originally, I planned on transferring bitcoins to the newly created addresses myself. For each purchase, the idea was to create a Bitcoin transaction transferring funds from my address to the new address, sign it with my private key, and then broadcast it to the Bitcoin network. This turned out to be much more complicated than I had anticipated. Bitcoin addresses aren’t like bank accounts from which you can withdraw money; instead, the input to every transaction is a previous transaction. To send bitcoins from my “address,” I would create a transaction that has as its input the transaction that I used to purchase bitcoins in the first place. This is complicated by the fact that Bitcoin transactions exhaust the funds of their inputs. If I have $50 worth of bitcoin and create a transaction sending 25 cents to a new address, then the $49.75 left over is collected as a “mining fee” by the member of the Bitcoin network responsible for working the transaction into a block. Mining and the Bitcoin blockchain are outside the scope of this article, but take a look at this helpful post.

Bitcoin clients get around the exhaustive-transactions problem by sending leftover coins to change addresses. The “wallets” that allow users to send Bitcoins as if from a bank account are helpful abstractions - behind the scenes, funds are drawn from a growing collection of addresses that are assembled together in complex transactions. When I realized that managing transactions myself would require writing a full Bitcoin client, I decided to use a third-party API instead. I opted for the blockchain.info wallet API, which allows me to send bitcoins with a simple HTTP request:

/*
 * Composes a request that transfers a given amount of bitcoin 
 * to a given address
 * Note - bitcoin value is specified in 100 millionth BTC
 */
void GetPaymentRequest(char out[], char* address, long amount) {
    snprintf(out, strlen(out),
        "GET /merchant/" GUID "/payment?password=" 
            PASS "&to=%s&amount=%li HTTP/1.1\r\n"
        "Host: " BLOCKCHAIN_HOST "\r\n\r\n",
        address, amount
    );
}

NetBurner has a motto - “Networking in One Day!” - and it lives up to the branding. Sending HTTP requests over SSL was painless. The last time I tried to network an embedded device I lost six hours of a hackathon to the infamous Arduino WIFI shield, and eventually just gave up.

4. Printing QR Codes

Generating QR codes from the Bitcoin keys was easy enough; I just used libqrencode. Printing them on thermal paper was more challenging. The CSN-A2-T printer accepts bitmaps in a “one-bit-one-pixel” format, so 48 bytes represent one row of 384 pixels (the printer’s maximum width). On the other hand, libqrencode encodes each pixel with an entire byte - so each byte of a printer bitmap corresponds to 8 bytes of QR code data. Furthermore, bitmaps must be broken up into chunks to avoid overflowing the printer’s 256-byte buffer. I used nearest-neighbor interpolation to resize the QR codes to multiples of 8, and wrote the following code to print them. I used Adafruit’s thermal printer library as a reference.

void PrintQRCode(int fd, char data[], int size) {
    int rows = size;
    int row_bytes = (size + 7) / 8;

    int cols = (row_bytes >= BYTES_PER_ROW)
        ? BYTES_PER_ROW : row_bytes;

    // break the bitmap up into 256 byte chunks
    // to avoid overflowing print buffer

    int rowsinchunk = PRINT_BUFFER / cols;

    if (rowsinchunk > PRINT_BUFFER-1) {
        rowsinchunk = PRINT_BUFFER - 1;
    }
    else if(rowsinchunk < 1) {
        rowsinchunk = 1;
    }

    // for each group of rows
    for (int rowstart = 0; rowstart < rows; 
            rowstart += rowsinchunk) {
        int chunkrows = rows - rowstart;

        if (chunkrows > rowsinchunk) {
            chunkrows = rowsinchunk;
        }

        // begin printing new bitmap
        WriteCommand(fd, 
            CMD_PRINT_BITMAP, 2, (char[2]){chunkrows, cols});

        // for each row
        for (int r = rowstart; r < rowstart + chunkrows; r++) {
            for (int c = 0; c < cols; c++) {

                // each byte of the output bitmap
                // corresponds to 8 bytes of QR code data
                char byte = 0x00;

                for (int k = 0; k < 8; k++) {
                    if(data[(c * 8) + (r * rows) + k] & 0x1) {
                        // if this pixel is set, set the
                        // corresponding bit of the output byte
                        byte |= (0x1 << k);
                    }
                }
                WriteByte(fd, byte);
            }
        }
    }
}

You can scan the mini private keys with the Mycelium wallet to spend the bitcoins, or just scan the address to check your balance. After I finished the software I spraypainted that gorgeous logo on an aluminum case provided by NetBurner cofounder Paul Breed, and then I was done. This was a fun project - an excuse to learn more about Bitcoin and an opportunity to brush up on my embedded C.

If you’re interested in the more abstract motivations of this project, check out Part 1. If you’re not, check out the source code. This article was originally published at arcadeoftheabsurd.com

Read 1526 times Last modified on Thursday, July 27, 2017 6:58 am

Leave a comment

NetBurner Learn

The NetBurner Learn website is a place to learn faster ways to design, code, and build your NetBurner based product. Sign-up for our monthly newsletter!

Latest Articles