Nick's blog

O2 Ireland proudly advertise that their mobile broadband offering works for both Windows and Mac. Then they proceed to offer only windows instructions, with no hint of how to get it working on a mac. This is, obviously, less than helpful. To complicate things, the generic instructions for getting Huawei modems working in OSX aren't entirely sufficient: The PIN on the sim card has to be disabled first, and the Huawei app for setting the APN doesn't seem to work in 10.5. So here are the instructions, in a nutshell:

1. Find a windows computer with administrator priveliges. Plug in the modem and follow the installation instructions. When prompted, enter your pin, then select Tools -> Pin Options -> Disable Pin. Enter your pin again. If you're trying these directions for a network other than O2 Ireland, this would be a good time to check the settings for the APN name, too.

Yes, I know it sucks to have to use a PC to set it up. It might be possible to do this by putting the 3G sim into a cellphone and disabling the PIN using that - I haven't tried, but it seems like it should work.

2. Follow the rest of the instructions here, with the following addenda:
- You may not need to add the device as described. In my case, it automatically added itself to the network preferences panel, and just needed configuring.
- The E220 drivers work fine if you have an E270, too.
- If you're using O2 Ireland, the APN you want to enter is "open.internet".

I just came across this job opening. I'd like to think I'm uniquely suited for the position.

Unfortunately, I don't live in the US or Canada, and I'm quite happy with my current job at Google. Oh well.

As DHT implementations proliferate and harmonise, the prospect of multiple widely-deployed applications using the same or compatiable DHT implementations is increasingly becoming a reality. There are a large and increasing number of DHT libraries out there, such as Entangled , and FreePastry, being used by an increasing number of applications.

However, most of these implementations are vulnerable to a simple but subtle bug: They have no way of distinguishing one DHT network from another. Although each application's DHT network or networks start off separate, if, by chance or deliberate action a node from a different but compatiable DHT is introduced, the 'self healing' property of DHTs will ensure that, sooner or later, the two networks become merged into a single DHT.

This is not a problem for single-purpose DHT implementations such as those used by BitTorrent or Overnet, since they generally establish a single DHT with all compatiable clients participating in any case. Nor is this a problem for networks designed with heterogenous applications in mind, such as CSpace. However, this still leaves a number of DHT libraries that don't fall into either of these categories.

If DHTs from two distinct applications using compatiable implementations become merged, the outcome depends to a large extent on how those applications make use of the DHT. If they use compatiable parameters and only make use of the basic DHT store/retrieve/find-node functionality, the impact may be minimal, though differences in persistence time and maximum size for stored elements can still lead to issues. If the DHTs have different parameters, such as the number of nodes to replicate inserted data to, the result may be subtly broken - a DHT that no longer fulfils the guarantees the software expects from it.

If the two applications expect very different things from their DHTs, though, such as a varying set of RPCs supported, the result could be a complete breakdown in the usefulness of the DHT. If your application expects that the vast majority of participating nodes will support its custom doFoo RPC (not an unreasonable expectation when you control the application), and suddenly half the nodes don't, the probability is that the application's behaviour will be severely degraded, at best.** This amounts to an entirely accidental Denial of Service attack on both applications involved.

The solution is relatively simple, of course - simply add an application identifier or 'magic number' to the DHT protocol, and require each application to specify an identifier unique to it. Then, the DHT library can simply discard packets with IDs it doesn't recognise.

In a quick survey of current DHT implementations, at least the following seem to be vulnerable:

Freepastry is notable in that it does provide for a 'magic number' facility. However, this is buried deep in the protocol stack, and is not required in order to create a Freepastry DHT instance.

I'm not aware of this bug occurring yet, but with increasing use of DHTs, it seems to me to be all but inevitable that it will occur at some point. Further, restoring normal behaviour after it has occurred is likely to be extremely difficult, likely requiring starting an entirely new DHT instance and moving all existing clients over to it.

** Please forgive my overuse of generalities. As I'm speaking of a general bug shared across many libraries and implementations, it's hard to be specific about the impact.

In response to a comment in the freenode.net/#appengine channel by someone wishing their App Engine app could receive email, I put together smtp2web, a simple service that accepts mail for an address (or your entire domain), and sends it via HTTP POST to a URL you specify. If you're running in a restricted environment such as App Engine, this means you can now receive email. Even if you're not, this is a lot simpler to use than writing your own SMTP server (or adding custom handlers to most existing servers).

Someone's already blogged about it, too.

Last night, having finally found my Cybook again, I downloaded Cory Doctorow's latest novel, Little Brother. Like all his other works, it's available for free download under a creative commons license, and like all his other books, it's excellent.

Unlike his other books, Little Brother is scary. Not scary in a "something's creeping up behind you" sort of way, but scary in a "completely plausible, yet utterly terrifying" way. The book is set in the (very) near future, and is focused around some of the most surveiled people in society - no, not prison inmates, high-school children. Imagine George Orwell's 1984, only a lot more immediate. Though disturbing enough to begin with, describing as it does worrying yet (alas) completely plausible intrusions in the name of 'security', everything takes a turn for the worse when a terrorist attack sends security paranoia into overdrive.

This is not a light hearted, "fun" novel. Though I don't live in the US, what happens there in the name of the "war on terror" affects me and everyone else. Starting as it did from a plausible and worryingly immediate beginning, the plot developments followed the same pattern, making it hard to criticise any of them as particularly unlikely. The result - something as bad in its way as any tin-pot dicatorship in a third world country - drives home just where this absurd path leads.

It's not all doom and gloom, though. The actions of the protagonist in fighting back against the absurdities and stupidities of modern security theater are things that anyone with access to instructables and a hell of a lot of guts can do, and the use of social networking and the internet to organise a large group of people around a common goal is simultaneously realistic and encouraging.

I started reading this as an ebook last night, and by the time I was halfway through, had ordered 4 copies off Amazon - this is a book I want to show to as many people as I can. Though it's aimed at teens, it's excellent reading for anyone socially aware and with a bent for technology.

I only hope that we can do our best to make this novel age as badly as possible. I sincerely hope that my (thus-far hypothetical) children someday read this book and scoff at how ridiculous it is.

I did eventually get a response from Gohop - my apologies for not posting it sooner. Here's the response:


Not entirely to my satisfaction, since they haven't promised to do anything, really - just offered an apology.

Edit: Also worth noting is that she claims that "the system in this case booked the next available alternatives, seating you apart", which contradicts what the arline told us - that our tickets weren't group-coded in the first place, so 'the system' didn't know it should be trying to seat us together at all.

Here's the email I just sent gohop:


Update: I got a response 8 days later.

Just a quick update: Yes, I did get back from Switzerland (with a new passport), eventually.

I also went back to NZ, got married to my (now) wife Hayley, and had a wonderful honeymoon. After a horrid flight back (about which more later), we're now back in Ireland and ready to go back to work.

Photos of the wedding will be forthcoming in a week or two for anyone who cares.

(Though of all the places to be stuck, this isn't a bad one)

I've been on holiday in Switzerland with my SO for the past few days, staying with a friend. Just after christmas, however, we took the train up to Zermatt to spend the night and see the matterhorn. However, on the train from Losanne to Visp, my bag was stolen. The bag containing my Passport and my Work Permit, not to mention my work laptop, the new watch I bought just the day before, and a bunch of other things.

To top it off, it looks like we're not covered by travel insurance (I thought we were).

And now I can't leave until I get a new passport issued and mailed to me. Fortunately, this only takes 3 days (plus postage) if I pay for expedited processing, but the passport office doesn't open until the 3rd.

Also on the plus side, I got some nice photos of the fantastic fireworks show in Zurich for new year, which I hope to post soon, and I'm able to work out of our Zurich office while I wait for my passport.

Recently, a friend and I were discussing peer-to-peer systems, and the difficulty of tracking obligations, and of reliably reporting a peer's actions while making fraud difficult or impossible. A subset of this problem is P2P currency: I want to be able to write someone a promissory note or IOU in such a way that they can transfer it to other parties (presumably to eventually be redeemed by them), but without them being able to duplicate it (or rather, in such a way that duplicates are detectable, and the identity of the peer to duplicate it can be determined). So our hypothetical peer-to-peer currency requires the following attributes: The solution, it turns out, is relatively simple. First, assume every peer has its own public/private keypair, which serves as its identity. Further assume that every peer knows every other peer's public key, or has some way to determine it.

To issue a note, the issuer creates a new note, with a header specifying the identity of the issuer, the value of the note, the time it was issued, and any other details - for example, the note may have an expiration date.

Whenever the current owner of the note wishes to transfer it to a new owner, he appends the identity of the new owner to the note and signs the whole thing with his public key. Every note will have at least one owner and signature appended, as the original issuer does this when giving the IOU to its original recipient.

A note's validity can be checked by verifying the 'chain of custody' described by the identities and signatures, which must follow the pattern id(issuer), id(a), sig(issuer), id(b), sig(a), id(c), sig(b), ... Further, any peer can prove to any other peer that they own a particular (valid IOU) by simply sending it to them - notes need not be kept secret, as they are useless to anyone other than the person whose identity is last in the chain of custody. Thus, peers considering an exchange can simply send each other all their notes so they can be examined and offers made.

If a peer wishes to try and duplicate a note, they must either invalidate the chain of custody, rendering the note useless, or duplicate it, appending a different identity in each case and signing it. When the note is discovered to have been duplicated - eg, at the point when someone attempts to redeem a note a second time - the identity of the fraudster can be determined by comparing the chains of custody and identifying the last peer the two notes have in common.

The value of a note to a peer in a system where fraud may be attempted is not the face value of a note, however. The value to a peer is the face value of the note, multiplied by the probability that it believes each peer in the chain was honest and did not duplicate the note, multiplied by other factors, such as a consideration for how close the note is to expiry, if that is implemented. Since this means that notes with longer chains of custody are worth less than those with shorter ones, it should be possible, if the original issuer is online, for a peer to send the note back to the issuer, requesting a 'new' one with a blank chain of custody (but the same value and expiry date) in return. This way, trust can be enhanced without requiring the original issuer to be online at all times.

It is also worth noting that in cases when a peer attempts to redeem or renew a note, only to be told by the issuer that that note has already been redeemed, and that their copy is worthless, that the peer need not take the issuer's word for it - they can demand a copy of the note that was redeemed, which serves as both proof and a means of identifying the culprit.

One major issue that this system does not solve is that any peer can invent as many cryptographic identities as they wish, and if they wish to commit fraud, they can use those identities to do so. Analysis techniques can likely be used to track down the actual culprit in scenarios like this, but this could be arbitrarily difficult to do. Alternately, a trusted third party issuer could be required for certificates only, or the peer's identity could be based on their IP address or other identifying factor, limiting the number of identities they can invent.

Finally, it's worth noting that the system proposed here is very similar to that used to endorse checks in the real world.

Feedback on this algorithm is much appreciated. Ideas on how a practical peer-to-peer transfer or storage system could practically use such an algorithm are also appreciated!

Original Post

One nice thing about working at Google is that you are surrounded by very smart people. I told one of my coworkers about the anagram tree idea, and he immediately pointed out that reordering the alphabet so that the least frequently used letters come first would reduce the branching factor early in the tree, which has the effect of reducing the overall size of the tree substantially. While this seems obvious in retrospect, it's kind of unintuitive - usually we try to increase the branching factor of n-ary trees to make them shallower and require fewer operations, rather than trying to reduce it.

Trying it out with an ordering determined by looking at the branching factor for each letter produces results that bear this out: Memory is reduced by about a third, and the number of internal nodes is reduced to 858,858 from 1,874,748, a reduction of more than 50! Though I haven't benchmarked it, difficult lookups are substantially faster, too.

The next logical development to try is to re-evaluate the order of the alphabet on a branch-by-branch basis. While I doubt this will have a substantial impact, it seems worth a try, so I'll give it a go and update with results.

Edit: Re-evaluating the symbol to choose on a branch-by-branch basis had a bigger impact than I anticipated: The tree created with my sample dictionary now has a mere 661,659 internal nodes. Here's the procedure for creating a tree using this method:

Assuming you have: Implemented in Python, this is actually substantially larger in memory and on disk than the previous approach, likely due to overhead with using classes instead of tuples as the nodes. In statically-typed languages, however, the overhead should be substantially outweighed by the benefit of the reduction in node count.

Note that the result of this alternate method is that while the letter to branch on is different for every node, following nodes from any leaf to the root of the tree always results in a valid permutation of the alphabet used.

Edit 2: The code for a Python implementation incorporating these ideas can be found here.

I hesitate to call this algorithm "damn cool", since it's something I invented* it myself, but I think it is rather cool, and it fits the theme of my algorithms posts, so here it is anyway.

When it comes to finding anagrams of words, a frequent approach is to use an anagram dictionary - simply put, sort the letters in your word to provide a unique key that all anagrams of a word have in common. Another approach is to generate a letter-frequency histogram for each letter in your word. (Both these approaches are more or less equivalent, in fact.) These approaches make the problem of finding exact single-word anagrams for strings very efficient - O(1) if you use a hashtable.

However, the problem of finding subset anagrams - a word that contains a subset of the letters in a string - is still rather inefficient, requiring either a brute force O(n) search through the dictionary, or looking up every substring of the sorted input string, which is O(2^l) with the number of letters in the input string. Finding subset anagrams is significantly more interesting, too, as it has applications in finding multi-word anagrams, as well as being applicable to problem domains such as scrabble.

However, with a little more effort, and the above observation that we can generate a histogram that uniquely represents a given set of letters, we can generate a tree structure that makes looking up subset anagrams much more efficient. To build the tree, we follow this simple procedure:

Assume we have the following information: For each term in the lexicon:
The result of following this simple procedure is a fixed-height tree, 27 nodes deep, with all the words in the leaf nodes, and each internal tier of the tree corresponding to a symbol from the alphabet. Here's an (abbreviated) example:


Once the tree is built, we find subset anagrams for an input string as follows:

Assume we have the following information:
Runtime analysis of this algorithm is rather difficult, for me, at least. Intuitively and in practice, it's a lot faster than either of the brute-force approaches, but quantifying that in big-O notation is something that's escaped me. As an upper bound, it cannot be less efficient than O(n) - only a constant factor worse than the brute-force approach. As a lower bound, a lookup in which the frontier set always has one node, lookup time is proportional to the length of the alphabet, or O(1). The average case depends on how large a subset of the dictionary the input string selects. Quantifying by the size of the output, approximately O(m) operations are required. If anyone knows how to determine more solid bounds for runtime, please do let me know in the comments.

One disadvantage of this approach is that there is substantial memory overhead. Using my Python implementation of the algorithm, and importing /usr/share/dict/words, which is approximately 2MB on this machine results in over 300MB of memory consumed. Using the Pickle module to serialize to disk, the output file is over 30MB, and compresses with gzip down to about 7MB. I suspect part of the large memory overhead is due to the minimum size of Python's dictionaries; I will modify the implementation to use lists and update this post if I can make it more efficient.

Here's a few stats on the tree generated that may be of interest:
Total words: 234,936
Leaf nodes: 215,366
Internal nodes: 1,874,748

From this we can see that the average cardinality of internal nodes is very low - not much more than 1. A breakdown of the number of nodes in each tier helps clarify this:

The cardinality of nodes towards the top of the tree is fairly high, but the tree quickly flattens out, and the last four tiers of the tree account for almost half of the total nodes. This suggests one possible space optimisation: Removing the last few tiers of the tree and concatenating their leaf nodes together. When performing lookups, check the selected nodes to ensure they are actually subset anagrams of the input string.

* It's possible I'm simply rediscovering something that's well known in the computer science community, or perhaps mentioned in a computer science paper 30 years ago. Significant searching hasn't turned up anyone using an algorithm like this, or anything else more efficient than the brute-force approaches outlined.

Edit: The source to my initial implementation is here.

Edit: Converting my Python implementation to use lists reduced memory consumption by roughly half. I'll post figures for the pickled tree and the source code when I have the opportunity.

Edit: More updates can be found here.

It's been too long since I blogged about anything much, and way too long since I posted the first Damn Cool Algorithms post, which I promised would be a series. So here's part 2.

To start, I'm assuming you know what a permutation is - basically a shuffling of a sequence of items in a particular order. A permutation of the range 1-10, for example, is {5,2,1,6,8,4,3,9,7,10}. A secure permutation is one in which an attacker, given any subset of the permutation, cannot determine the order of any other elements. A simple example of this would be to take a cryptographically secure pseudo-random number generator, seed it with a secret key, and use it to shuffle your sequence.

What if you want to generate a really, really big permutation - one so big precomputing and storing it isn't practical or desirable? Furthermore, what if you want it to be a secure permutation? There's a really neat trick we can pull with block ciphers that allows us to generate a secure permutation over any range of numbers without first having to precompute it.

A block cipher, for anyone that isn't familiar with them, is a common cryptographic primitive. It takes blocks of ciphertext of some fixed lengths - 64 or 128 bits is common - and encrypts it. Given the same key and the same block of plaintext, it will always generate the same block of ciphertext. Messages larger than a single block are encrypted using one of a number of modes of operation, allowing messages much larger than a single block to be encrypted and decrypted securely. When using a block cipher for encryption, choice of the mode of operation is critical. For the purposes of generating a secure permutation, however, we're only going to be encrypting a single block at a time, so we don't have to worry about modes of operation.

If you look at how a block cipher operates - taking any block of a given length (think of blocks as very large numbers here) and converting it uniquely to another block, such that it can be converted back again, a block cipher is already a secure permutation. If we progressively encrypt larger numbers (1, 2, 3, and so on), we get out a random seeming sequence of output numbers that is guaranteed not to repeat as long as we don't repeat our input. It's easy to prove this to yourself: If it repeated, then you would have two input numbers with a single output number, and it would thus be impossible to decrypt uniquely. So the same properties that a block cipher requires are the properties that make it useful to us.

All very well, you say, but what if I want a permutation over a range that isn't a power of two? This is where the clever trick comes in. Take a block cipher that's got a block length slightly larger than you want. Use it as described above, encrypting progressively higher numbers in a sequence to generate elements in the permutation. Whenever the output of the encryption is outside the range you want for your permutation, just encrypt it again. Repeat until you get a number within the range you want. Again, we're guaranteed uniqueness by the block cipher, and we're also guaranteed (by exhaustion) that we will eventually get a number within the desired range.

Obviously, there are some factors that need to be taken into consideration before pursuing this route. You want to select a block cipher that is not much larger than the range you wish to generate a permutation over - preferably the next power of two. The ratio of the cipher's range to the permutation's range defines the average amount of work you will have to perform, so if the cipher has a range four times that of your permutation, you'll need to do an average of four encryptions for each value. Since most block ciphers are 64, 128, or more bits, this can be problematic. For this purpose, I've found the TEA cipher to be particularly adaptable. It is easy to create variants that are 32, 64, 128 or more bits long, and from there, the bitshifts in the main loop are easily adjusted to produce a cipher with a length that's any power of 4, without needing to shorten the key to the point where it's easily brute-forced.

It's also worth noting that although this technique is aimed at generating very large secure permutations, it is equally useful for a permutation that doesn't need to be secure or secret - your secret key simply becomes your random seed for the permutation. There are many situations in which this can be useful - what you essentially have is a mapping function from index to permutation value, so you can calculate the value of any subset of the permutation that you wish.

Finally, bear in mind that due to the factorial explosion of the number of possible permutations, the keyspace of your cipher is almost certainly going to be much smaller than the number of possible permutations. For most purposes this probably does not matter, since the number of possible permutations is too large to enumerate anyway, but if your key is sufficiently short, it allows the possibility of an attacker doing an exhaustive search of your keyspace to find the permutation that generates the subsequence of the permutation he has access to.

Update: Yossi Oren points to this excellent paper in the comments. It covers exactly what I describe here (only much more comprehensively, of course).

Yesterday morning, someone from the relocation company came by to pick me up and take me on a bit of a tour of Dublin, with an emphasis on the sort of neighbourhoods I might like to live in. There's a fairly wide variety of housing available here in Dublin, though if you want a garden you're more or less out of luck unless you're particularly wealthy.

One particular place that impressed me, however, were the apartments at the Gasworks - the same facility the Google offices are on. There's a lot of apartment buildings there, all fairly nice, but the really impressive one is the old Gasometer. Basically, they took a gasometer, demolished everything but the frame, then built an apartment building inside it. It's pretty big:


What's really impressive, though, is what they've done inside. The building is shaped like a torus, with a large open area in the middle. They've planted a large tree in the center, and the end effect is that you have almost a sanctuary-type environment inside. My pictures really don't do it justice, especially with the overcast weather we're having, but here they are anyway:



None of the apartments are inhabited yet - I presume there's some finishing work yet to be done. I really hope they're renting them about the time we need one - it looks like it'd be a really cool place to live.

I just finished my first week at Google Dublin. It's been a blast.

The first couple of days of general induction are a bit slow, but once you meet your team, stuff really speeds up. The sheer amount of information I've been exposed to and had to learn this week is astounding.

I'm really looking forward to next week, not to mention going down to Mountain View for more training.