Cryptographically secure IOUs without a trusted third-party

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:
  • Non-deniability - The issuer must not be able to plausibly claim they did not issue the IOU. He must also be unable to claim the note has already been redeemed unless he can prove it somehow.
  • Transferability - The current owner of a note must be able to transfer it to a new owner, without requiring the involvement of the original issuer, or any trusted third-party.
  • Accountability - If the note is modified or duplicated, it must be possible to determine who tampered with it.
The solution, it turns out, is relatively simple. First, assume ...

Update on Anagram Trees

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 ...

Damn Cool Algorithms, Part 3: Anagram Trees

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 ...

Damn Cool Algorithms, Part 2: Secure permutations with block ciphers

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 ...

Apartments in Dublin

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 ...

First week at Google Dublin

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.

Leaving NZ, again.

So, first a quick update on everything I've been leaving out on this blog: Waaaay back in February, I was offered a (phone) job interview with Google. Things proceeded well, and a while ago, I was made an offer of a job as a Site Reliability Engineer in Dublin, which I accepted. I resigned from my position in NZ, sorted out stuff for moving, and hopped on a plane.

I'm writing this entry from a Dublin internet cafe. I arrived here in Ireland mere hours ago, and I'm still exhausted and jetlagged, but I have to do something with the time until I can let myself try and sleep. Hence the sudden update.

First, for those wondering, Hayley, the love if my life, is, alas, still back in NZ for the moment. At the moment it looks like she'll be joining me up here in about 6 weeks.

When I arrived in Dublin, I was met by someone hired by Google, who drove me to my temporary accommodations provided for me for the next 30 days. Light commentary on the city was provided. Upon reaching my accommodation, I was handed off to someone else, who gave ...

I am teh famous, LOL!

LOLCode.NET was featured at TechED07, in a presentation by Nick Hodge, a "Professional Geek" for Microsoft. He's posted a video of the presentation on his blog.

Now I just need to convince them to integrate it into the next edition of VS... - Now your LOLCats can use the CLR!

The past few days, I've been working on a .NET compiler for the LOLCode language.

LOLCode is an emerging esoteric (and hilarious) language based on the dialect used in LOLCats images. It's been siezed upon by a group of people (myself included, now), and is being expanded into a real, workable, turing complete esoteric language (though nobody has proven its turing completeness yet!).

The LOLCode.NET compiler is now working, and as a nearly-free bonus for using the .NET platform, you can even debug it in Visual Studio:

I still can't believe I'm looking at LOLCode and its x86 disassembly in Visual Studio.

Dynamic code generation in .NET

I've written up a rather lengthy document on different methods of dynamically generating code in .NET - two current methods, and one hypothetical one based on a C extension called "`c" (tickc). I think it does a fairly good job of illustrating just how awkward dynamic code generation is in current mainstream languages, and how much simpler and more understandable (and in many cases, more efficient) it could be.