NAND to Tetris: Nothing short of awesome

Been a while since I posted, huh?

Well, here's an interesting development in my life: I finally started the NAND to Tetris course (part 2) on Coursera, which is based on the instructors' site.

I can say, whole-heartedly, that the course is awesome, and the first thing in a long time that has gotten me into a flow state.

The idea behind the course is this: they take you through (virtually) building a computer from a very basic level, showing all the abstraction layers that produce a computer's behavior.

It starts with logic gates -- specifically, the NAND gate (hence the name), since it's universal. Your first project is to use a hardware simulator to build several other logical gates from NAND. (NAND is just an AND gate with the outputs inverted, so that true and true yield false, everything else yields true.) The second project is to to build the arithmetic logic unit (ALU) in a CPU out of the components, so you basically have a configurable circuit: based on six control bits, you perform one of several possible functions on two 16-bit inputs.

The next project incorporates "flip flops", which allow you to repeatedly execute that circuit while also writing to and reading from some some persisted memory. Your inputs to the circuit then function as a kind of machine code.

The project after that then has you implement functions in that machine code, writing in an assembly language the authors created for the course that has a precise mapping to the machine code inputs in the CPU from the previous lesson. I can honestly say it was a really fun project to implement multiplication directly in assembly language!

Later on you write a compiler from a high level language into assembly (which then converts simply into machine code), in a way that's broken into two steps: a compiler from the high level language into a virtual machine that works on a stack with memory blocks, and a compiler from the virtual machine commands to assembly. I just recently finished that latter part (which comes first).

Those layers then build up to making a game that runs on your CPU, then an OS, and some other stuff I haven't delved into.

In the course of the projects, you use a hardware simulator, an assembler (for converting the assembly language into machine code), a CPU simulator, and a virtual machine simulator.

In order to catch up with the class an have enough leeway for a weekend trip, I went through much of the course over the weekend, and enjoyed every minute of it! I especially like how the break the projects into manageable pieces. For example, in the VM-to-assembly part, it first has you implement simple push/pop/add operations on a stack and run a test to verify that you can compile those commands. Further test suites give you a manageable set of operations to add.

I've written an actual compiler now! (albeit limited use...)

(Consider how fun this is, and how naturally it comes to me, maybe I picked the wrong field.)

One interesting challenge is that the CPU only has two registers call A and D, and only the A register is used when accessing memory, to know which word of memory to look at. It took me a while to figure out how you could say "look at the value in the memory location refered to in the memory location zero." Before I saw how you could do it, I implemented one project by having two separate code branches for the two possible values at the memory location!

Would love to link my code for the projects, but they discourage that to leave the challenge for others to solve.

EXCLUSIVE: Silas's bitcoin mining rig tell-all!

As part of an application I filled out recently (more on that in the future), I explained everything I went through to get my bitcoin mining rig up and running. But why bury that story in a place only one person will read it? Nay, my readers ought to hear about it as well! So, here's the story, with a photoalbum for each stage at the end.

***

In February 2011, I learned about Bitcoin and the feasibility of building a "mining rig" (machine that quickly computes lots of SHA256 hashes) to make money by generating bitcoins, which trade against dollars at a varying rate. Though I hadn't built a custom box before, the idea of setting up a mining rig excited me.

I looked over some rig designs in the Bitcoin.org wiki, and based on those, designed a custom setup that I figured would achieve the highest RoR (involving 4 GPUs connected to a motherboard in a large case) and ordered the parts. Some graphics cards had already been bid up to unprofitability (Radeon 5970) by other rig builders, so I picked a slightly slower (Radeon 5870) one that was several times cheaper.

Over the course of putting it together I ran into a number of problems, any one of which would have shut down my plans, but kept trying different things until I overcame them.

First, since I hadn't built a computer from (near) scratch I had to learn what parts (motherboard, SSD, CPU, RAM, PSU) went where, and how to optimally route the wires. Then, on bootup, I found the BIOS didn't see the hard drive, and traced the problem to a part of the case's internal wiring that wasn't passing the SSD's SATA flow through, so I bypassed that and plugged it in directly to the motherboard.



Then, after installing Ubuntu, I had to download the exact set of ATI drivers required for mining rig code to work. It turned out the latest drivers interfered with the mining code, so I had to get an earlier version that AMD no longer promoted (or pretty much acknowledged the existence of). From the forums I found that you had to manually enter the URL since nothing linked to it anymore, which allowed me to mine with the first GPU in a way that exploited its ability to do parallel hash calculations.

After configuring the GPU to send its computations to a mining pool (group of miners that combines computations to get a more predictable solution [hash inversion] rate), I opened up the box again to add the second GPU. (I had decided early on to add them one by one to make sure I understood what was going on at each stage.) Getting them both to work together introduced another problem, as they would somehow keep adjusting their hashing rate downward to the level of only one GPU. This required another trip back to the forums to learn new software to install, which still didn't work after numerous configurations, so I wrote down the whole process up to that point and re-installed the operating system. (I ended up doing this several times as a last resort at different stages.)



Once I got all 4 GPUs and a hardware monitor installed, I was able to get excellent hashing performance, but soon noticed that, with four high-power GPUs packed so closely together, they heated up to unacceptably high temperatures, so I took two out. That solved the temperature problem, but I still wanted all four to be able to run, so I looked into better cooling solutions. (For a short while I ran three cards safely by having one side of the case open and pointing a box fan at the cards, though this was obviously very inconvenient and wouldn't permit safe overclocking.)

It turned out that liquid cooling was my only option, which I had also never set up before. Nevertheless, I went forward and found a cooling block model (i.e., something that replaces the OEM GPU heat sink) that would fit my cards, as well as a cooling kit (pump, radiator, reservoir, tubing). I also ordered some parts that would directly connect different blocks together and so minimize the need for tubes.

When I got the cooling blocks, it turned out they didn't fit, because the particular variant of the Radeon card I was using had a non-standard PCB design (which I didn't realize was possible before). So I sent back the cooling blocks, found ones sure to match this specific design, and ordered those. Finally I was able to attach a block to each of the 4 GPUs. I then ran into another problem with the block-to-block connectors, which I couldn't figure out how to install (and had ambiguous directions), and had to be put in a tight spot, so I asked a more home-improvement-savvy friend how they worked.



I eventually got the connectors to install, but ran into another problem: because of space constraints, the tubing would require bends that were too sharp. I figured I needed a 90-degree angle fitting, but I couldn't get one at a local hardware shop because PC cooling parts all use British piping threads, which are incompatible with those carried in American stores. After finding a compatible one online, I realized that each day without the rig running was costing me money, and this was the only part holding it up, so I had it express-shipped to arrive the next day, allowing me to finish setting up the liquid cooling system.

I had to make a few choices then about which way to point the radiator air flow and otherwise optimize cooling capacity. I eventually settled on a design that had the radiator take air from the room and dump the exhaust into the case, which I partially mitigated by flipping one of the case fans to bring more external air in rather than taking it out.

At this point, there were fewer setbacks, but I was hesitant about circulating coolant inside the system if I couldn't first ensure there were no leaks. So, before closing the loop and adding the coolant, I configured some leakage tests where I would fill the system with distilled water, leaving an open tube at the top, sealing the other end, and ensuring plenty of towels around the potential leak points.



With this test configuration, I blew into the tube. I figured that if it could withstand this pressurization without leaking, I could be more confident about actual fluid circulation. Fortunately, none of the tests showed a problem, and I got the "production" liquid cooling system running.



Finally, I was able to have all four GPUs running overclocked, generating bitcoins for me through a mining pool, and staying at temperatures significantly below what I got before. I further optimized performance by using new mining software, experimenting with settings, and then saving a file with the commands to get the rig running optimally.

There were still some other kinks to sort out, like what to do about the immense heat it generated for the rest of my place, and how to monitor the mining pool status, but that about covers everything. Now, for the pictures:

Final result

The various stages (no captions, sorry):
Initial set-up
Putting four graphics cards in
Replacing OEM heat sinks on graphics cards with waterblocks
Installing the liquid cooling system

Virtualization is a riot!

Isn't it neat how computers can completely simulate other computers purely via software? (Background). Well, right now I'm reading a book that comes with a Linux Live CD containing relevant source code -- basically, a CD that you can boot from to see what it's like to use the operating system without interfering with the one you currently have. (Not to mention the benefit of having the exact same environment as the author so you can make sure It Works.) And that's how Live CDs are typically run: from bootup.

But with emulation, you don't need to reboot your whole computer just to get that Linux (or whatever OS) experience! You can set up a "sandbox" environment, or virtual machine that "pretends to be a computer". The software allocates a portion of your computing resources that you specify (disk space, RAM, etc.), and you just run the Live CD through that "pretend computer", freely switching from the window containing that virtual machine, to your web browser and whatnot. Again, it's without the hassle of rebooting every time you want to switch between that and the cute cat video you were watching.

So there I am -- I've got the virtual machine running a "sample" of an operating system off a Live CD, no need to reboot my "real" machine. But it gets better! I can go one step further and tell my pretend computer, "You know what? Let's go all the way. I want the full operating system -- not just the "sample" -- installed on your pretend hardware!" And then it dutifully runs through all the screens you would normally see when installing a Linux distro as your operating system, seizing control of the sandboxed software-that-thinks-it's-hardware, for a full wipe of the, um, non-OS you had there before.

Sorry, I don't know why ... I just find this all so hilarious ... virtualizing the use of a "sample" operating system before I install it on its virtual hardware.

(For those who are curious, the software I'm using is Oracle VM VirtualBox, available free for (IIUC) personal non-commercial use. I learned about it from LessWrong.com's failed attempts to teach others how to play with the site's code.)

Explaining – not setting – Bitcoin straight

Okay, I had some spare time last night, so I figured I’d sit down and write up an explanation of some of Bitcoin’s workings. The chief problem in explaining this to the layman is that, as a prerequisite, you need to understand the basics of public key cryptography (aka asymmetric cryptography), which, for the average person, is quite a tall order in itself. But since I’m the master at this kind of thing, here’s how I would put it:

First, to get something out of the way: nothing in Bitcoin is actually encrypted. Rather, it works, and works robustly, without centralization, specifically because all transactions are visible. The privacy comes in how the entities trading the coins are referred to in this transaction database, purely by their Bitcoin address (a string of numbers and letters, like 1mVQtx6rn…), which is like one of those supposed Swiss bank accounts you hear about that are only known by a number. (So yes, if you publicly and believably reveal that, "Hey, I own address 152zpfu5b20gh29...!", then people can see what you do via the address 152zpfu...) So rather than anonymous, Bitcoin is best described as pseudonymous (sue-DONN-i-MUS).

The reason that you need to know the basics of public key cryptography, rather, is that a lot of its "primitives" (building blocks) are used in Bitcoin, and the protocols used are heavily studied by professional cryptographers.

First primitive: public key-based digital signatures

How do you accomplish signatures in a digital world, where anyone can put any data on any storage medium? Like a physical signature, a digital one needs to meet the following characteristics:

A) Proof of identity: only you can produce your signature, so seeing your signature is proof that you endorse what you signed.
B) Non-repudiation: after giving your signature, you can't plausibly deny having signed it.
C) Non-transferability: your signature on Document1 can't be "moved" to a different Document2, implying your endorsement of the latter

Quite surprisingly, you can accomplish these goals with a kind of signature in the digital world. Here's the trick: you generate a keypair -- a "public key" and a corresponding "private key". You keep the private key secret, and tell everyone in the world your public key. You then use a "public key algorithm" (PKA) that takes as an input:

1) the message, M1, that you want to sign
2) your private key, SK1

and outputs a signature, SIG1. PKAs are designed so that computing this algorithm and generating this signature is quick and easy.

Then, if someone wants to verify that you really did sign message M1, they just verify that a certain mathematical relationship (corresponding to the particular PKA used) holds among your public key (which, remember, they know), your message M1, and your signature SIG1. Again, this process is designed to be quick and easy for the verifier.

So, how does this provide the desired qualities A through C above? A and B are satisfied by the fact that it is extremely difficult and time-consuming to produce SIG1 *unless* you know the private key SK1. (Inferring the private key from the public key is likewise too time-consuming to be finished anytime in the next few centuries.) So, the fact that you were able to (quickly) compute SIG1 is proof that you hold the private key corresponding to the public key, AND that (with a few caveats) you chose to use that key to generate the signature for M1.

This protocol satisfies criterion C (non-transferability) because, as you recall, SIG1 is partly a function of the message itself. This means that your signature will be different for each message you could conceivably want to sign. So someone can't take SIG1 and cite it as proof that you signed a different message M2 -- because the protocol's specified mathematical relationship will *not* hold for {M2, SIG1, public key} -- it will only hold for {M1, SIG1, Bob's public key}. To "forge" a signature, they would need to produce {M2, SIG2, Bob's public key}. But like I said above, it's way too hard for them to figure out what SIG2 would be unless they know your private key.

I'm deliberately leaving off the specific algorithms used for such systems so that this does not become unbearably long. Suffice to say, there are algorithms that accomplish this, and they mainly rely on modular arithmetic and prime numbers. I will only add that the class of function needed to produce such a PKA is known as a "trapdoor one-way function". That is any function f(x) such that:

- Given x, it's easy to compute f(x).
- Given a value V equal to f(x) for some unknown x, it's hard to find an x such that f(x) = V. (i.e., it's hard to invert f)
- But, if you know a specific piece of information particular to f, called the "trapdoor knowledge" (in the exposition above, this is the part played by the private key), it is *easy* to invert f

What role do public key signatures play in Bitcoin? They are used to prove to the network that the owner of address A1 (A1 also functioning as a public key!) really did authorize the transfer of certain coins to the next address. Other nodes in the network, in turn, are able to easily verify that the owner of A1 signed off on the transfer by checking that the mathematical relationship I mentioned above holds among the A1 public key, the message indicating the transfer, and the signature on the transfer. And if this relationship doesn't hold, the other nodes (per the Bitcoin protocol) ignore the purported transfer, acting like it didn't exist, and refuse to tell other nodes about it.

Second primitive: (cryptographically secure) hash functions

A hash function (in cryptography) is a function that takes an input of any length, and deterministically computes a fixed-length output based on it, such that the relationship between input and output "seems random", and there's no quicker way to compute the output, or otherwise learn *anything *about what the output will look like, than to churn through the hash function itself. I will make this make a bit more sense. For simplicity, call the input to a hash function its "preimage", and the output of a hash function its "digest" (the output is also referred to as the checksum or the [digital] fingerprint).

An example of a (weak) hash function most people are familiar with is the kids' game where you find out your "Star Wars" name or your "stage name” by doing something like, "Take the first syllable of the street where you grew up, and add on the last syllable of your middle name, plus the first syllable of where you were born." This name is a hash of all that data about yourself.

However, cryptographically-secure hash functions have to meet more stringent requirements. Like I said above, it must be really hard to make inferences about the relationships between classes of input and classes of outputs without actually grinding through the function for each input in the class. So, for example, you can't have a hash function where "small changes in the input (preimage) lead to small changes in the output (digest)". Rather, they are designed so that a tiny change in the preimage will *significantly *change the digest. More formally, cryptographically secure hash functions must meet the following characteristics:

- Given a digest, it's hard to find a preimage that hashes to that digest. This is called "[first] preimage resistance". (Note: because preimages can be any length and the hash length is fixed, there are an infinite number of preimages that hash to any given digest.)

- Given a preimage, it's hard to find another preimage that hashes to the same digest. This is called "second preimage resistance".

- It's generally hard to find *any* preimages (given or not), that hash to the same digest. Such instances are known as "collisions", and this trait is called, obviously, “collision resistance”.

(Exercise for the reader: how the Star Wars name game described above fail all of these?)

The function of hashes: in everyday data security, they serve the function of obscuring data in a way that limits its malicious uses. For example, websites don't actually store your password (if they know anything about security whatsoever). Rather, they store a *hash* of your password. That way, they can still verify you by password (Check: does the hash of the password given match the hash we have on record?), but if someone breaks into their database, all they get are the hashes. Because the hash function has first preimage resistance
(see above), the list is much less useful to the attacker because they have to accomplish the difficult task of finding preimages for the hashes they found.

Hashes are where the "miners" come into play: initial bitcoins are generated and allocated (and still are) based on who can solve a mathematical problem. That problem is similar to the one of breaking a hash function's (first) preimage resistance. But rather than having to find a preimage with a *specific* digest, the problem is to find a preimage whose hash is a *partial* match (for some specific number of digits) with a target digest string. So, it's like an easier version of breaking preimage resistance, though still requiring the ability to do lots of (parallel) calculations – because there is, by design, no shortcut to solving this but to try as many preimages as you can.

Anyway, that's about all for now, something for you to chew on and get some understanding of the whole thing. There’s still a lot left, but that should cover the pre-requisites.

Bitcoin mining rig is up!

Picture of my liquid-cooled box of 4 Radeon HD5870 cards, before closing up the case and actually getting it to work. It computes about 1.3 Gigahashes per second. (Click to enlarge.)



The side panel that closes it off (not shown) adds another large fan, which I inverted so it's sucking the hot radiator exhaust air out.

UPDATE 5/24/11: I've switched to the Phoenix miner, which somehow gets more hashes out of your card, so I'm now computing about 1.5 Ghash/sec.