Many years ago Ken Thompson wrote a famous paper for ACM entitled "Reflections on Trusting Trust" (PDF) describing how even if you had the source code to a program, and the source code to the compiler used to compile the program, you still couldn't be certain that everything that the program did corresponded to what was in the source code -- the compiler could add extra bits into the binary that weren't in the source code of either the original program or the compiler. It's been one of those "it's turtles all the way down" problems, in that to trust a given thing is as it looks from the apparent component bits, you need to trust all the component bits and everything involved in assembling them.

David Wheeler is soon to defend his PhD thesis on the topic of solving this problem, entitled Countering Trusting Trust through Diverse Double Compiling, the culmination of work that he's been doing for several years. Although at least from the abstract that too involves another trusted compiler (at least trusted not to be subverted in the same way), so maybe it is still turtles all the way down...

Anyway I was reminded of this by needing to apply for a new passport. One of the things that you need for the application is a witness to confirm that your photo matches who you are. And one of the classes of witnesses is "anyone with a valid NZ passport who will say they have known you for more than 12 months". Those people quite likely got their passports by having someone who knew them say who they are. So you can end up with this chain of people who all vouch for each other, with no independent confirmation. The passport situation mostly escapes from this problem because (a) there are substantial fines for supplying false information (which ups the ante), and (b) you still need to supply other proof that such an identity should exist (eg, birth certificate), so people can't just supply any name they want. But even so, the whole passport system, like many real world systems, largely relies on trusting trust. As has the computing world for a very long time. (Such systems work fairly well given compliance by most and a means to punish those who don't, as demonstrated by Robert Axelrod's (homepage) book "The Evolution of Cooperation".)

The other surprise of applying for a new passport (other than it now costing NZ$150 instead of NZ$80, and lasting 5 years instead of 10 -- I found the old receipt while digging out documents needed -- and will now come with a "track anywhere via radio transponder" chip) was just how young I look in my passport photo (even ignoring the fact that I now have a goatee, and was clean shaven before -- that, plus the fact that I often wear glasses on international flights rather than the contacts that I had in for my passport photos has lead to a few puzzled looks at the borders). There possibly is merit in replacing passports every 5 years (or at least less than 10) for that reason alone.