DistributedNet

From BovineNet

Jump to: navigation, search

distributed.net is a non-profit distributed computing organization that I co-founded in Spring 1997 while I was a student at Harvey Mudd College. By using distributed.net, thousands of computers around the world can collectively join together to work on large-scale computing problems. Historically, distributed.net has worked on breaking cryptographic challenges, however we are beginning to focus on other mathematically interesting problems too. Although the term didn't exist at the time we first started, this sort of work is now known as volunteer computing.

Contents

[edit] How distributed.net began

(The distributed.net timeline corresponds with the following narration and highlights some events not mentioned.)

I originally became interested in distributed computing (around Feb 1997) when another HMC student showed me an existing distributed computing project that he had come across on the web at zero.genx.net (New Media Labs). Their implementation involved a simple TCP/IP program that would connect to their single keyserver, fetch a single RC5-56 block (2^28 keys per block), and then work on it before sending the results back to the server.

However, by having a single keyserver and clients that processed single unit blocks at a time, the genx.net effort made themselves particularly vulnerable to network disruptions. Their server was using a reportedly unstable version of IRIX and was particularly vulnerable to the network "SYN" attack that had become popular among hackers at the time. This inevitably caused the genx.net server to frequently be unreachable, causing the everybody's genx-clients to go idle from lack of work to process.

My HMC friends expressed their displeasure at only occasionally being able to contact the genx.net server and I agreed that it was a significant problem. Since I was looking for an interesting programming challenge, I thought it would be interesting to try developing my own Windows winsock server that could sit between the unreachable genx.net server and the clients running on my friends' machines. Just a few weeks earlier I had written a simple multi-threaded webserver as an experiment, so this seemed like a good chance for code reuse. The source code for the genx client was publicly available, so it was relatively trivial to adapt my code for the genx.net protocol. I soon had an operational "buffering proxy server" that would connect to the genx.net server whenever possible, rapidly transmitting and receiving hundreds of blocks at a time (so that it could withstand being unable to reconnect to the genx server for possibly many more hours).

Simultaneously, I was also working on compiling my own optimized clients and servers based on the original genx.net source:

  • an optimized Win32 command-line Winsock client that did not depend on a large 1.5 MB support cygwin.dll library, and incorporated inline assembly to achieve speeds more than double that of the win32 client that genx supplied.
  • a 16-bit MS-DOS based client that used IPX (via INT calls to LSL.COM/IPXODI.COM) instead of TCP/IP. This special MS-DOS based client was actually installed in place of the standard HMC Academic Computing network Login Prompt screen for many months, allowing the cycles of unused workstations to be utilized while they were waiting for someone to login. This client's bland-looking display exactly matched the original HMC Logon Prompt (so it wouldn't be noticed) except for a single letter displayed in the upper-right corner. The letter would alternate between 'w' and 'W' while it was waiting for IPX network activity, or display an animating stick ('/', '-', '\', '|') as it was cracking blocks.
  • an associated Win32 IPX coordinating server to manage the SAP broadcasts and service requests from the MS-DOS IPX clients mentioned above. IPX is of course typically only routed within a local intranet and not over the open Internet, so you would have needed to ensure that deploy one of these within IPX-broadcast range of those clients. This IPX coordinator effectively functioned as a buffering keyproxy itself, though I typically just directed it to retrieve RC5 blocks from another of my full buffering keyproxies. Also of note is that this IPX coordinator subdivided normal RC5 blocks and distributed smaller work blocks (each designed to only take about 30 seconds of processing) that were later rejoined. The small work size was necessary because my Login Prompt client was running on a pure network-boot environment (with no scratch space to save a partially completed block if it needed to quit because someone has pressed a key and wanted to log in), and so I wanted to minimize the amount of wasted CPU by discarding a partial block.
  • 32-bit protected mode MS-DOS clients that directly utilized TCP/IP (via the WATTCP library) and IPX (via thunks to real-mode IPXODI) were both attempted, however these were never released or widely used due to stability problems.
  • a 16-bit Windows 3.x command-line Winsock client to allow people still running Windows 3.1 to particpate. Multitasking gracefully was a little difficult because of the cooperative task-switching and threadless nature of Windows 3.1, however this client still left the machine fairly usable.
  • the buffering keyproxy for Win32 Winsock that enabled all of the above things to continue processing RC5-56 blocks even when the genx.net keyserver was down for hours or even days. My buffering keyproxy was later expanded to randomly generate blocks if a client was requesting work, and the proxy had run out of blocks to distribute (the clients at the time did not have the ability to randomly generate blocks themselves if needed).


While I was developing all of the above programs, I had accidentally discovered that a number of RC5-56 fans had begun gathering on Efnet IRC in the #rc5 channel. I began sharing my developments with the people there, and soon people besides my friends at HMC were running my clients and connecting to my proxy server. As the number of clients connecting to my proxy continued to grow, I began allowing a few of the regulars in #rc5 help me by running buffering proxy servers too.

[edit] The end of genx (aka "v1")

During this entire time (mid March 1997), connectivity to the genx.net server had become extremely poor and the server was almost never reachable. It was frequently several days between successful connections. Eventually near the end of March, it was confirmed that the New Media Labs' RC5 server had been permanently shut down due to the instability of the machine.

Action is quickly taken over the next few days and I add memory-mapped keyspace table tracking to my buffering keyproxy codebase to enable it to confidently generate blocks and ensure that it has not previously distributed that block to someone else already. The remaining buffering key proxies run by the people I had met in the #rc5 channel then pointed all of their servers toward my computer in my dorm room that was running my new "keymaster". My computer at the time was a Pentium 150 with 64MB of RAM, running Windows 95. Additionally, I ran a webserver on that machine to host the client downloads and provide live statistics for all participants.

Through the use of clever DNS round-robin techniques, we were able to make all of the buffering proxies accessible through a single DNS name. If one proxy was down the client, would timeout and automatically attempt to reconnect to another one. Additionally, the keymaster could go down for several hours at a time, since the buffering proxies held enough blocks to serve clients for several hours at a time. By May 1997, the domain name "distributed.net" was officially registered for our use.

The statistics database at this time was amazingly simple in design. It was simply a Windows INI file with separate sections for [email] and [ip], and each value in those sections held the total number of completed blocks for that email or IP address. Each time another block was received by the keymaster, it would use GetPrivateProfileInt and SetPrivateProfileString to update the INI with the new block count. The statistics web pages were produced by a simple CGI script that loaded the entire INI file into a list and bubble-sorted it by block count, before displaying the results in an HTML table. As extremely inefficient as this all sounds, it was actually pretty adequate for quite a long time (considering the total participant list was still short enough to comfortably view on a single page in your web browser).

Around May 1997, the inefficiencies (and 64k limits) of the Win95 GetPrivateProfile functions became too constraining and the keymaster was switched to keeping a binary tree of the entire statistics INI file in memory, and periodically writing out the new contents to a fresh text file. This also marked the debut of a new set of stats CGIs by Adam Beberg ("Duncan3" from #rc5) to replace my original versions. Stats were still mostly live data, though because of the periodic syncing of the stats to disk, they were really only accurate to the minute.

  • a radically rewritten Win32 GUI client that was designed in Borland's Object Windowing Library (OWL). This innovative rewrite of the client sported a new user-interface that was significantly more usable. It made it significantly easier for new participants to become a part of the effort.
  • a simplified "personal proxy" based off of the full keyservers was released. The purpose of this personal version was to allow multiple corporate or university users to share a single local buffering proxy, reducing network latency and consolidating external network utilization.

[edit] The release of "v2"

Up until this time, all of the our clients still used the same network protocol that the original genx clients used. However, the freely available nature of the original source code made it relatively easy for various malicious people to fraudulently compile a client that immediately claimed to have completed a work block, without actually doing anything. This of course resulted in astounding block completion rates, and required us to attempt to manually detect these activities and nullify those blocks so that they could be redistributed to other legitimate users.

Additionally, the inability of the old clients to work on more than 1 block at a time before needing to make contact with the keyserver again was a significant limitation for many users who operated on modems. Arguably, the 1 block limit could also be a vulnerability for us too, but we were not yet showing any signs of incapacity because of the two-tiered nature of the separate keymaster and buffering proxy server layers.

These two major issues were sufficient reason to warrant a complete client rewrite. In July 1997, the first stable "v2" client was released. On October 22, 1997 the solution key for the RC5-56 challenge was found, after 212 days processing. Percent of keyspace completed: 47.03%

The next higher length RC5 challenge from RSA was quickly started (RC5-64), which marked a significant jump in client version numbering, giving rise to the "v2.6400" clients. In order to participate in the 64-bit keylength RC5 challenge, all clients had to be upgraded to the new v2.6400 line of clients.

On January 13, 1998 distributed.net officially begins participation in the DESII-1 competition, which was a challege to show the weakness of the keylength size used in DES encryption. To meet this challenge, distributed.net released a new dual-core client that could participate in both RC5-64 and DES contests, marking the release of the "v2.7000" line of clients. On February 23, 1998 DES-II-1 was finished (about 41 days to completion). distributed.net resumes full dedication back to the RC5-64 contest.

On July 13, 1998 the "v2.7100" clients are released for the DESII-2 challenge, which later falls 4 days later. On January 19, 1999, the DESIII challenge is started in cooperation with the "DeepCrack" computer to complete the challenge in a record 22 hours, 15 minutes, 4 seconds.

On November 17, 1999 distributed.net releases its "v2.8000" clients that add support for participation in the "CSC" contest. On January 15, 2000 (my birthday!) the solution is found.

On Feb 15, 2000 distributed.net starts the launch of a non-cryptographic challenge, the search for Optimal Golomb Rulers (with 24-marks). However, due to unexpected problems it is later temporarily suspended, only to be officially resumed on July 13, 2000. On August 1, 2000 the first pass of OGR-24 is completed and distribution of OGR-25 stubs is started.

[edit] External links

General distributed.net
My personal links
Retrieved from "http://jeff.bovine.net/DistributedNet"