I don't think I have a proper post in me this week. Instead, here are some neat things I've seen online lately!
Finger trees - The Good Math, Bad Math blog occasionally has some really interesting stuff on computer science. Summary, for non-CS people: log(n) is good! We like log(n). Everything should run in O(log(n)).
Ethics for Machines - Evolutionary ethics may be a somewhat unsatisfying framework for moral reasoning, but it's also unexpectedly robust, which I'll take over aesthetics any day. This essay explores some of the ethical issues surrounding created machine intelligences.
We may have been wrong about dinosaur posture all along - This is the sort of question that would be solved really quickly if we just had a time machine of some sort.
An Inconvenient Talk - A bleak perspective on peak oil, from somebody who probably knows what he's talking about. Also points out that the rosier perspectives (the ones that we always hear) always come from politicians and oil company executives.
Thursday, May 28, 2009
Friday, May 22, 2009
Turning a computer off
For various reasons, I've become accustomed over the years to having my desktop running 24/7, to the point that I basically depend on it. This is less than ideal, though. It's a huge hassle when I'm moving or traveling, and it's a single point of failure when something goes wrong. It also wastes electricity, and since I've spent the last year paying my own electricity bills, this is suddenly very important to me.
Therefore, one of my projects for this summer is turning it off for a while. What follows is a list of things which will be problematic.
Instant messaging: Being signed on to AIM and similar services all the time is really convenient, even if I'm not around 24/7 to actually read the messages. With a desktop, this is easy - I can just leave my client of choice on and that's the end of it. Without one, my preferred solution would be something similar to meebo, but with a persistent connection on their end so that you could stay "online" all the time, and check received messages whenever you're on the site. The next best thing would be an "AIM proxy", which does the same thing but on hardware that I control. (Unfortunately, I would have to write this one myself, since nothing like this exists yet.)
Google Talk already supports this, as far as I can tell - too bad none of the people I talk to on AIM use it. XD
File access: Right now, I have access to all my files on my desktop, which is good. I also have a remote backup service that I sync to every week or so, which is better since it gives me read-only access to files even when my desktop is off.
Read-only is less than perfect, though, so I've been looking into distributed network filesystems. My requirements are that it must work on Windows, Mac, and Linux, have some kind of security, and allow for offline editing of files. NFS is the most widely used thing, but it fails two of those - no offline editing, and nonexistent authentication. AFS seems much more promising, but I haven't yet had a chance to play with it. Unfortunately, those two are the only options for distributed cross-platform filesystems. :(
RSS Reader: I used to use Liferea, which was a pain - really slow, no remote access, etc. I've since switched to my own RSS reader, feedme, which is fast enough, and can be accessed remotely through screen. I could shift this to a server at any point with a minimum of fuss, and keep getting updates uninterrupted.
This still has a single point of failure, though; ideally, I'd like to have multiple servers with synchronized state and automatic failover, possibly only grabbing the feeds to which it has the lowest latency... hrmm. I think I'm overengineering the hell out of this one, my current setup plus frequent backups is probably good enough.
IRC: The challenges for IRC access are similar to instant messaging, but the solution is quite a bit easier. If I can get a command-line IRC client configured such that it isn't a pain to use on a day-to-day basis, then I can just run that on a server and be done with it.
Bookmarks: I know there are services that sync your bookmarks across multiple computers, but I'd need one with support for multiple browsers (at a minimum, Firefox, Safari, and Chrome). Alternately, having a webpage somewhere with a list of my bookmarks would really be just as good. Something like this probably exists; further research is required.
Therefore, one of my projects for this summer is turning it off for a while. What follows is a list of things which will be problematic.
Instant messaging: Being signed on to AIM and similar services all the time is really convenient, even if I'm not around 24/7 to actually read the messages. With a desktop, this is easy - I can just leave my client of choice on and that's the end of it. Without one, my preferred solution would be something similar to meebo, but with a persistent connection on their end so that you could stay "online" all the time, and check received messages whenever you're on the site. The next best thing would be an "AIM proxy", which does the same thing but on hardware that I control. (Unfortunately, I would have to write this one myself, since nothing like this exists yet.)
Google Talk already supports this, as far as I can tell - too bad none of the people I talk to on AIM use it. XD
File access: Right now, I have access to all my files on my desktop, which is good. I also have a remote backup service that I sync to every week or so, which is better since it gives me read-only access to files even when my desktop is off.
Read-only is less than perfect, though, so I've been looking into distributed network filesystems. My requirements are that it must work on Windows, Mac, and Linux, have some kind of security, and allow for offline editing of files. NFS is the most widely used thing, but it fails two of those - no offline editing, and nonexistent authentication. AFS seems much more promising, but I haven't yet had a chance to play with it. Unfortunately, those two are the only options for distributed cross-platform filesystems. :(
RSS Reader: I used to use Liferea, which was a pain - really slow, no remote access, etc. I've since switched to my own RSS reader, feedme, which is fast enough, and can be accessed remotely through screen. I could shift this to a server at any point with a minimum of fuss, and keep getting updates uninterrupted.
This still has a single point of failure, though; ideally, I'd like to have multiple servers with synchronized state and automatic failover, possibly only grabbing the feeds to which it has the lowest latency... hrmm. I think I'm overengineering the hell out of this one, my current setup plus frequent backups is probably good enough.
IRC: The challenges for IRC access are similar to instant messaging, but the solution is quite a bit easier. If I can get a command-line IRC client configured such that it isn't a pain to use on a day-to-day basis, then I can just run that on a server and be done with it.
Bookmarks: I know there are services that sync your bookmarks across multiple computers, but I'd need one with support for multiple browsers (at a minimum, Firefox, Safari, and Chrome). Alternately, having a webpage somewhere with a list of my bookmarks would really be just as good. Something like this probably exists; further research is required.
Friday, May 15, 2009
Power-aware scheduling in TFlex
Whenever people ask me what I'm doing for my honors thesis, I find myself in a bit of a bind, because actually explaining what I'm doing properly would take entirely too long for casual conversation. I thought I'd do a post on what I'm actually doing, so that when I say I'm working on my research project this summer, y'all will have some idea what I'm actually talking about.
Unfortunately, actually explaining things properly requires a lot of background explanation.
Background: current architectures
When I say computer architecture, I'm not talking about buildings, but rather the internal structure of the processor, and the way it executes programs. If you take any current computer architecture, and handwave away a whole lot of implementation details, you'll almost always end up with about the same thing. Current architectures are all based on an extremely simple model: the processor reads an instruction from memory, does what the instruction says, and then moves on to the next instruction. Instructions are the basic units of computation - some commonly used instructions will perform various arithmetic operations, or read data from memory, or have the processor look elsewhere for the next instruction.
Well, it's not quite that simple. Modern processors can do all sorts of things to make the process faster, like reading the instructions from high-speed caches instead of main memory, or analyzing the dependencies between instructions so that they can execute more than one at a time. And instructions aren't that simple either; some can execute in a single cycle (where a cycle is on the order of nanoseconds), while others can take hundreds of cycles. With very few exceptions, though, computers maintain the illusion that they are executing instructions one at a time from memory.
Maintaining this illusion makes things really convenient for programmers, but it also means that computers aren't as fast as they could be. Moore's Law has given chip designers more transistors than they know what to do with. You could easily fit dozens or hundreds of simple execution units on a processor, but because the processor needs to pretend that it's executing one instruction at a time, it's very difficult for it to use more than four or so execution units at a time.
The problem doesn't lie in the current generation of processors, but in the current generation of architectures. To make computers significantly faster than they are now, we're going to need new architectures, explicitly designed for high levels of parallelism. Which brings me to my next topic...
The TRIPS architecture
TRIPS is an experimental architecture that was created here at the University of Texas. The most important feature of the TRIPS architecture is that it operates on blocks of instructions, rather than individual instructions. Memory access and control flow, both of which are traditionally foes of high-performance computing, are handled at the block level, rather than at each instruction. (Memory access is a problem because the amount of time it takes is highly unpredictable; control flow is a problem because the uncertainty about the next instruction to execute stops the processor for a short time.) Not handling these on a per-instruction basis also simplifies the individual execution cores.
Within each block, instructions are executed in dataflow order. This means that each instruction within a block runs as soon as its operands are ready for it, rather than having to wait for its turn in the instruction stream. This design implies that a block runs as fast as it's theoretically possible for it to run, unless it's constrained by the actual dimensions of the processor grid. TRIPS uses an 8x4 grid of processors, for 32 cores total.
(As an aside: this isn't just idle theorizing about abstract issues in computer architecture. They actually built a working prototype of TRIPS a few years back.)
This is all really neat stuff, and it solves a lot of scaling issues which current processors face really elegantly. But wait, it gets better!
The TFlex architecture
Parallelism is nice, but the sad fact is that some programs simply aren't parallelizable. Even if you were to try to run them on a processor like TRIPS, they would end up only using one core at a time. Wouldn't it be nice if you could put a program like that on one core, and use the other 31 cores for other stuff at the same time?
The TFlex architecture, a derivative of TRIPS, does exactly that. It allows you to divide the execution cores into different-sized tiles, and run totally different programs on each tile. So, for example, you could run two programs on two 4x2 tiles, and a third program on the remaining 4x4 block of space.
CPU scheduling is the process of allocating time on processors to programs on a computer. Generally, on computers like you or I would have, there are far fewer processors than there are programs running, so CPU scheduling involves switching between different programs quickly enough that you don't notice, while giving each one a fair share of CPU time. On TFlex, we have the luxury of approaching the problem a bit differently: since we can decide on the fly how many processors we want to have, and what sizes they should be, we can make the simplifying assumption that every program is running simultaenously. Context switches are fun (unless you're working on a project for OS, and it's due the next day, and the switch to kernel space is just a little bit off and the whole thing crashes when you run it... well, that's another story entirely), but for an experimental system they're not really necessary.
Every program will have slightly different performance characteristics on such a machine - the speed of a program doesn't vary linearly with the size of the tile it's running on, and the relation between performance and tile size varies tremendously. The reconfigurable nature of TFlex, then, adds a whole new dimension to the problem of CPU scheduling.
And that's it for background stuff.
My research project (finally)
My research is focused around power-aware CPU scheduling on the TFlex architecture. System performance isn't the only thing you might want to optimize for with scheduling - on TFlex, you can also schedule running programs to minimize power consumption, since the power consumption of a program varies with tile size. Currently, I'm working on figuring out the relationship between performance and power consumption. If they're strongly correlated, then it makes my life a lot easier, because optimizing for one will also optimize for the other. On the other hand, if there are significant tradeoffs between the two, the problem may turn out to be more interesting.
Once you end up considering both execution speed and power consumption, there are other interesting questions you can ask. For example: "I want to run these programs, within this power budget. How quickly can they run without going over?" On a power-constrained device, running off a battery, this could be a very useful thing to know. My main for this project is to design a CPU scheduler that addresses this problem, and others like it.
Unfortunately, actually explaining things properly requires a lot of background explanation.
Background: current architectures
When I say computer architecture, I'm not talking about buildings, but rather the internal structure of the processor, and the way it executes programs. If you take any current computer architecture, and handwave away a whole lot of implementation details, you'll almost always end up with about the same thing. Current architectures are all based on an extremely simple model: the processor reads an instruction from memory, does what the instruction says, and then moves on to the next instruction. Instructions are the basic units of computation - some commonly used instructions will perform various arithmetic operations, or read data from memory, or have the processor look elsewhere for the next instruction.
Well, it's not quite that simple. Modern processors can do all sorts of things to make the process faster, like reading the instructions from high-speed caches instead of main memory, or analyzing the dependencies between instructions so that they can execute more than one at a time. And instructions aren't that simple either; some can execute in a single cycle (where a cycle is on the order of nanoseconds), while others can take hundreds of cycles. With very few exceptions, though, computers maintain the illusion that they are executing instructions one at a time from memory.
Maintaining this illusion makes things really convenient for programmers, but it also means that computers aren't as fast as they could be. Moore's Law has given chip designers more transistors than they know what to do with. You could easily fit dozens or hundreds of simple execution units on a processor, but because the processor needs to pretend that it's executing one instruction at a time, it's very difficult for it to use more than four or so execution units at a time.
The problem doesn't lie in the current generation of processors, but in the current generation of architectures. To make computers significantly faster than they are now, we're going to need new architectures, explicitly designed for high levels of parallelism. Which brings me to my next topic...
The TRIPS architecture
TRIPS is an experimental architecture that was created here at the University of Texas. The most important feature of the TRIPS architecture is that it operates on blocks of instructions, rather than individual instructions. Memory access and control flow, both of which are traditionally foes of high-performance computing, are handled at the block level, rather than at each instruction. (Memory access is a problem because the amount of time it takes is highly unpredictable; control flow is a problem because the uncertainty about the next instruction to execute stops the processor for a short time.) Not handling these on a per-instruction basis also simplifies the individual execution cores.
Within each block, instructions are executed in dataflow order. This means that each instruction within a block runs as soon as its operands are ready for it, rather than having to wait for its turn in the instruction stream. This design implies that a block runs as fast as it's theoretically possible for it to run, unless it's constrained by the actual dimensions of the processor grid. TRIPS uses an 8x4 grid of processors, for 32 cores total.
(As an aside: this isn't just idle theorizing about abstract issues in computer architecture. They actually built a working prototype of TRIPS a few years back.)
This is all really neat stuff, and it solves a lot of scaling issues which current processors face really elegantly. But wait, it gets better!
The TFlex architecture
Parallelism is nice, but the sad fact is that some programs simply aren't parallelizable. Even if you were to try to run them on a processor like TRIPS, they would end up only using one core at a time. Wouldn't it be nice if you could put a program like that on one core, and use the other 31 cores for other stuff at the same time?
The TFlex architecture, a derivative of TRIPS, does exactly that. It allows you to divide the execution cores into different-sized tiles, and run totally different programs on each tile. So, for example, you could run two programs on two 4x2 tiles, and a third program on the remaining 4x4 block of space.
CPU scheduling is the process of allocating time on processors to programs on a computer. Generally, on computers like you or I would have, there are far fewer processors than there are programs running, so CPU scheduling involves switching between different programs quickly enough that you don't notice, while giving each one a fair share of CPU time. On TFlex, we have the luxury of approaching the problem a bit differently: since we can decide on the fly how many processors we want to have, and what sizes they should be, we can make the simplifying assumption that every program is running simultaenously. Context switches are fun (unless you're working on a project for OS, and it's due the next day, and the switch to kernel space is just a little bit off and the whole thing crashes when you run it... well, that's another story entirely), but for an experimental system they're not really necessary.
Every program will have slightly different performance characteristics on such a machine - the speed of a program doesn't vary linearly with the size of the tile it's running on, and the relation between performance and tile size varies tremendously. The reconfigurable nature of TFlex, then, adds a whole new dimension to the problem of CPU scheduling.
And that's it for background stuff.
My research project (finally)
My research is focused around power-aware CPU scheduling on the TFlex architecture. System performance isn't the only thing you might want to optimize for with scheduling - on TFlex, you can also schedule running programs to minimize power consumption, since the power consumption of a program varies with tile size. Currently, I'm working on figuring out the relationship between performance and power consumption. If they're strongly correlated, then it makes my life a lot easier, because optimizing for one will also optimize for the other. On the other hand, if there are significant tradeoffs between the two, the problem may turn out to be more interesting.
Once you end up considering both execution speed and power consumption, there are other interesting questions you can ask. For example: "I want to run these programs, within this power budget. How quickly can they run without going over?" On a power-constrained device, running off a battery, this could be a very useful thing to know. My main for this project is to design a CPU scheduler that addresses this problem, and others like it.
Saturday, May 9, 2009
Cop-out post
It is easy to forget while programming, but there is value inherent in simplicity.
(Hit a mental block on the post I had planned for yesterday. Real update next week, I swear >_>)
Thursday, April 30, 2009
Blanket Licensing
There is a push, in some circles, for blanket licensing of digital music. Essentially, you would pay a small fee, and in exchange have the right to download as much music as you want. I have seen several of the most respected people in the "free culture" community, most recently Richard Stallman, endorse this approach, which is a shame. Not only is it a poorly-thought-out idea, but it would be far worse in many ways than the current system.
First, a necessary distinction - there are both voluntary and involuntary blanket licensing schemes being proposed, both idiotic. In a voluntary system, there would be a few groups that would collect payment in exchange for the right to download music, and consumers would choose one, and everything would be happy until some rightsholder gets upset for some reason, and denies one service rights to their IP, and then all hell breaks loose because this system only makes sense if every service has rights to every song. Can you imagine the confusion that would result if some services only had rights to some songs, and the set of songs they had access to wasn't even constant? Involuntary blanket schemes have the same problems, but with the added downside that everybody, even people that don't like music, has to pay for it.
But, a music tax? That's kind of crazy, isn't it? Surely nobody would ever suggest doing something like that?
Here is a more troublesome problem. In a modern, decentralized filesharing network, it's impossible to accurately track what files are being downloaded. (BitTorrent is a notable exception here, but only because it was explicitly designed for such tracking.) However, it's the job of the organization collecting the money to distribute it to artists based on popularity. Since popularity can't be accurately tracked, how are they going to decide who gets what? Since it's not really possible to do it in a fair and transparent way, what recourse will artists have if they believe they're being cheated? And then, worse yet, you end up with a situation where fans can artificially inflate the measured popularity of their favorite bands at no cost to themselves. Gaming the system would become an arms race, and eventually the measured download counts would have little to no bearing on reality. Furthermore, let's not forget that by centralizing, we've introduced a single point of failure. Any corrupt accountant could throw piles of money to whichever artists they happened to like, and no one would be the wiser. The fact is that it is completely impossible on multiple levels to ensure that the collected money will be distributed fairly to the artists.
Blanket licensing would also end up being far more monopolistic than the current system, which is actually a pretty impressive feat. Consider the plight of somebody trying to start a new collection organization. In order to be taken seriously, you'd need to acquire rights to every song available from other organizations; if the existing organizations have made deals which lock out newcomers (and they will, short of legislation to the contrary) then you're stuck. Only licensing some content won't cut it - if you have to give people a list of songs they can't legally download with your service, they'll just go elsewhere.
This would also be a death sentence for independent artists. An artist looking to strike out on their own would be in a difficult situation - everybody expects music to be free, so nobody would actually be willing to pay them. They would be forced to sign up with a label, which could then pay them next to nothing, since that's better than the nothing they would get on their own.
And then, this is just for music. Further on down the road, are we going to have another monthly fee for movie downloads? ebook downloads? software? accessing web pages that were previously free? Where does it end? And this is assuming that entire industries would be able to unite under a single banner; almost certainly, this is a ridiculously optimistic assumption.
At some point we, as a society, are going to have to come to terms with the fact that anything that can be represented as binary - all information, in other words - will be available for free to everybody on the Internet. We can hem and haw and decry the whole state of affairs, we can theorize about ridiculous payment schemes to assuage our own guilty consciences ("it's okay as long as somebody's getting paid!"), but at the end of the day, there's something we need to accept. The solution cannot possibly involve the current system of copyright, which is now so far out of touch with the way the world actually works that, were it suggested anew today, it would be regarded as a joke. Instead of molding society to the law, we need to find a system that actually works, and remake the law to match that.
First, a necessary distinction - there are both voluntary and involuntary blanket licensing schemes being proposed, both idiotic. In a voluntary system, there would be a few groups that would collect payment in exchange for the right to download music, and consumers would choose one, and everything would be happy until some rightsholder gets upset for some reason, and denies one service rights to their IP, and then all hell breaks loose because this system only makes sense if every service has rights to every song. Can you imagine the confusion that would result if some services only had rights to some songs, and the set of songs they had access to wasn't even constant? Involuntary blanket schemes have the same problems, but with the added downside that everybody, even people that don't like music, has to pay for it.
But, a music tax? That's kind of crazy, isn't it? Surely nobody would ever suggest doing something like that?
Here is a more troublesome problem. In a modern, decentralized filesharing network, it's impossible to accurately track what files are being downloaded. (BitTorrent is a notable exception here, but only because it was explicitly designed for such tracking.) However, it's the job of the organization collecting the money to distribute it to artists based on popularity. Since popularity can't be accurately tracked, how are they going to decide who gets what? Since it's not really possible to do it in a fair and transparent way, what recourse will artists have if they believe they're being cheated? And then, worse yet, you end up with a situation where fans can artificially inflate the measured popularity of their favorite bands at no cost to themselves. Gaming the system would become an arms race, and eventually the measured download counts would have little to no bearing on reality. Furthermore, let's not forget that by centralizing, we've introduced a single point of failure. Any corrupt accountant could throw piles of money to whichever artists they happened to like, and no one would be the wiser. The fact is that it is completely impossible on multiple levels to ensure that the collected money will be distributed fairly to the artists.
Blanket licensing would also end up being far more monopolistic than the current system, which is actually a pretty impressive feat. Consider the plight of somebody trying to start a new collection organization. In order to be taken seriously, you'd need to acquire rights to every song available from other organizations; if the existing organizations have made deals which lock out newcomers (and they will, short of legislation to the contrary) then you're stuck. Only licensing some content won't cut it - if you have to give people a list of songs they can't legally download with your service, they'll just go elsewhere.
This would also be a death sentence for independent artists. An artist looking to strike out on their own would be in a difficult situation - everybody expects music to be free, so nobody would actually be willing to pay them. They would be forced to sign up with a label, which could then pay them next to nothing, since that's better than the nothing they would get on their own.
And then, this is just for music. Further on down the road, are we going to have another monthly fee for movie downloads? ebook downloads? software? accessing web pages that were previously free? Where does it end? And this is assuming that entire industries would be able to unite under a single banner; almost certainly, this is a ridiculously optimistic assumption.
At some point we, as a society, are going to have to come to terms with the fact that anything that can be represented as binary - all information, in other words - will be available for free to everybody on the Internet. We can hem and haw and decry the whole state of affairs, we can theorize about ridiculous payment schemes to assuage our own guilty consciences ("it's okay as long as somebody's getting paid!"), but at the end of the day, there's something we need to accept. The solution cannot possibly involve the current system of copyright, which is now so far out of touch with the way the world actually works that, were it suggested anew today, it would be regarded as a joke. Instead of molding society to the law, we need to find a system that actually works, and remake the law to match that.
Thursday, April 23, 2009
Notes from the switch to a command-line IRC client
For the past few years, I've been using XChat for all my IRC needs. It's been reliable so far, though I've had a few issues with the way it handles logs and configuration files. Every few months, though, somebody will tell me to switch to irssi or one of the other command-line IRC clients, because they're "better" in some vague, ineffable way. So, for the past week or so, I've been using Weechat. Here are my thoughts on the transition.
Weechat > XChat:
Weechat > XChat:
- Because it's command-line, I can use it with screen, which is incredibly convenient when I'm out somewhere.
- The control commands are a bit nicer than XChat's
- Handles configuration really well - you can make changes through the interface, and save them back to disk with a single command
- Lower memory usage
- Having a channel tree on the side of the screen is infinitely better than keyboard shortcuts for channel navigation. I've always said that the keyboard shortcut model for navigating between channels sucked hard, but now I have actual experience to back it up.
- You can't click on URLs in a command-line client, unless the terminal has some special support for it, and the URL is short enough that it doesn't get wrapped in half
- You can't copy/paste from a command-line client. I'm sure there's some kind of ugly hack to get around this, since it's a pretty basic thing to want to do, but there's no way to make it work cleanly.
- It's impossible to get a command-line client to integrate with your desktop, so there's no way, for instance, to get a notification on highlights
- I miss being able to scroll with a mouse wheel. Page Up/Down just isn't the same.
- Many of the keyboard shortcuts are really obscure. Traditionally, this is where command-line client zealots say something inane about how I can change them to something better if I don't like them.
Friday, April 17, 2009
Decentralized Reputation II
(for latecomers - previous post)
I wasn't looking forward to coming up with rules for dealing with transitive trust, but as it turns out, I'm in luck - I stumbled upon subjective logic a few days ago. It basically adds a few new logical operators for dealing with opinions in a surprisingly clean way. This paper has a better explanation than the wikipedia article, if you're curious. There are two key points that I'm going to make use of throughout this post: it's possible to reason about the amount of trust you should assign to opinions even through an arbitrarily deep trust chain, and in order to perform this reasoning accurately it's critical that you have access to the entire chain, not just the transitive opinions of people you trust.
Before I start, there are two things that you absolutely have to know about before this post will make any sense: cryptographic hashes, and public-key cryptography. (CS majors and other such people can probably skip this paragraph. :) A hash function takes some arbitrary data, and generates from it a fixed-size block of data. The hash needs to have some properties: given some data, you can generate a hash, but given a hash, you can't find some chunk of data which hashes to the same thing, or tell anything about the data that went into the hash. With public-key cryptography, you have two keys, which correspond to two functions that are inverses of each other. Furthermore, you can assume that key pairs are unique. With public-key, you can do things like give somebody one of the functions, and encode data with the other one, which simultaneously protects the data (because it's encrypted), and proves that you are who you say you are (because you would have to have the corresponding private key, if the data decrypts correctly with the public key you gave them).
Identity
This identifying property of public-key crypto is tremendously useful. It means that, for as long as you can keep the private key secret, you can prove that all messages signed with your private key are actually from you. Thus, a public/private keypair is at the core of the idea of an identity. Identity using public key crypto is largely a solved problem, so I won't spend all that much time on it.
One thing that's unfortunately missing from current implementations is a good method of key revocation. Rather than fiddling around with revocation keys that have to be broadcast somehow, I'm going to introduce the concept of an "identity server". An identity server in this scheme is a server, which has your private key (or better yet, a proxy key) and can answer requests about it. Individuals will be able to run their own ID servers, of course, but somehow I think that not everybody will want to.
Reputation
So we have an identity system, with identity servers - great! Except, computers can generate keypairs pretty darn quickly these days, so identities are a dime a thousand. We need some way to distinguish between legitimate people and hordes of spambots. We'd also like a way to know if a given person's trustworthy, which turns out to be a very similar problem. Getting a meaningful measure of trust from raw data is kind of tricky, which is why I'm going to invoke Jøsang's work on subjective logic here. We can compute a meaningful measure of trust for an identity given a network of trust and opinion ratings from various users, such that there's at least one unbroken chain between us and the identity we're trying to evaluate.
The big question (how will this all work?) then becomes three much easier questions: where do these ratings come from?, where do we go to get these ratings?, and how will we find unbroken chains?
Where the ratings come from is easy - people are already able to judge the trustworthiness of the people they interact with regularly, which should be enough data for the system to function. As we all know, everybody is at most six degrees away from Kevin Bacon, so the maximum number of hops we'll have to go to find somebody is twelve.
Where to get the ratings is a bit trickier, but still doable. The problem is that people tend to go offline at random times, meaning that we'll need to store the ratings in the Internet somewhere. A distributed service like DNS would be good, but we'll still need a stable source for ratings, that the distributed system could then be a cache of. (Aside: in fact, because of the nature of digital signatures, the distributed cache system wouldn't even need to be trusted. If you were walking down the street one day, and a shady-looking guy stepped out of an alley and handed you a digitally signed document on a floppy disk, you could be 100% certain that the document was authentic, if you had access to the signer's public key. Neat, eh?) An obvious candidate is the identity servers, since those already need to be up all the time. In my scheme, a person's identity server would be responsible for storing and giving out all the opinions that people have had about that person.
Alright, so here's one of the nifty bits - this came to me at about 3 AM while I was trying to fall asleep, as good ideas sometimes do. It seems that if the identity server is responsible for maintaining all opinions about you, good or bad, then it has no real reason to keep the bad ones. It could easily tell whoever asked that nobody has ever said anything bad about you, and nobody would be the wiser. What we need is a way for somebody leaving an opinion to prove that it was accepted. The obvious way to do this is to have the identity server sign incoming opinions and give back the signature, but there's still vulnerability here - the identity server could pretend to be suddenly deaf when you're saying mean things. On the other hand, we can imagine a three-step exchange, where you hand the server a hash of the opinion you want to give it, the server signs that and gives it back, and then you give the server the opinion. Remember, cryptographic hashes are opaque, so this means that the server is forced to accept all opinions. The user creating the opinion can simultaneously submit it to the distributed cache - this would ensure that an identity server which drops negative opinions can be discovered.
As for the third question - how are trust chains discovered? - this one is a little difficult. Finding optimal paths through a graph is easy if you have the entire graph lying around; not so much if it's spread out over thousands of computers, some of which are down at any given time. Ideally, we'd like to be able to find the best trust path between ourselves and some random other identity. However, we don't really need the best path; if a lot of paths exist, then some pretty good path is usually good enough. In that case, our slightly unreliable distributed cache suddenly looks pretty good - it has all the necessary data already, and with our relaxed requirements can give us exactly what we need.
So, there you have it. As far as I can think through, this proposal is mostly solid; I've spotted a few weak points already, and I might try to paper them over in a future post, but the core structure should stay the same. Even though this was originally a thought experiment, to prove that something like this is possible, I have a strange urge to actually implement it now ._.
I wasn't looking forward to coming up with rules for dealing with transitive trust, but as it turns out, I'm in luck - I stumbled upon subjective logic a few days ago. It basically adds a few new logical operators for dealing with opinions in a surprisingly clean way. This paper has a better explanation than the wikipedia article, if you're curious. There are two key points that I'm going to make use of throughout this post: it's possible to reason about the amount of trust you should assign to opinions even through an arbitrarily deep trust chain, and in order to perform this reasoning accurately it's critical that you have access to the entire chain, not just the transitive opinions of people you trust.
Before I start, there are two things that you absolutely have to know about before this post will make any sense: cryptographic hashes, and public-key cryptography. (CS majors and other such people can probably skip this paragraph. :) A hash function takes some arbitrary data, and generates from it a fixed-size block of data. The hash needs to have some properties: given some data, you can generate a hash, but given a hash, you can't find some chunk of data which hashes to the same thing, or tell anything about the data that went into the hash. With public-key cryptography, you have two keys, which correspond to two functions that are inverses of each other. Furthermore, you can assume that key pairs are unique. With public-key, you can do things like give somebody one of the functions, and encode data with the other one, which simultaneously protects the data (because it's encrypted), and proves that you are who you say you are (because you would have to have the corresponding private key, if the data decrypts correctly with the public key you gave them).
Identity
This identifying property of public-key crypto is tremendously useful. It means that, for as long as you can keep the private key secret, you can prove that all messages signed with your private key are actually from you. Thus, a public/private keypair is at the core of the idea of an identity. Identity using public key crypto is largely a solved problem, so I won't spend all that much time on it.
One thing that's unfortunately missing from current implementations is a good method of key revocation. Rather than fiddling around with revocation keys that have to be broadcast somehow, I'm going to introduce the concept of an "identity server". An identity server in this scheme is a server, which has your private key (or better yet, a proxy key) and can answer requests about it. Individuals will be able to run their own ID servers, of course, but somehow I think that not everybody will want to.
Reputation
So we have an identity system, with identity servers - great! Except, computers can generate keypairs pretty darn quickly these days, so identities are a dime a thousand. We need some way to distinguish between legitimate people and hordes of spambots. We'd also like a way to know if a given person's trustworthy, which turns out to be a very similar problem. Getting a meaningful measure of trust from raw data is kind of tricky, which is why I'm going to invoke Jøsang's work on subjective logic here. We can compute a meaningful measure of trust for an identity given a network of trust and opinion ratings from various users, such that there's at least one unbroken chain between us and the identity we're trying to evaluate.
The big question (how will this all work?) then becomes three much easier questions: where do these ratings come from?, where do we go to get these ratings?, and how will we find unbroken chains?
Where the ratings come from is easy - people are already able to judge the trustworthiness of the people they interact with regularly, which should be enough data for the system to function. As we all know, everybody is at most six degrees away from Kevin Bacon, so the maximum number of hops we'll have to go to find somebody is twelve.
Where to get the ratings is a bit trickier, but still doable. The problem is that people tend to go offline at random times, meaning that we'll need to store the ratings in the Internet somewhere. A distributed service like DNS would be good, but we'll still need a stable source for ratings, that the distributed system could then be a cache of. (Aside: in fact, because of the nature of digital signatures, the distributed cache system wouldn't even need to be trusted. If you were walking down the street one day, and a shady-looking guy stepped out of an alley and handed you a digitally signed document on a floppy disk, you could be 100% certain that the document was authentic, if you had access to the signer's public key. Neat, eh?) An obvious candidate is the identity servers, since those already need to be up all the time. In my scheme, a person's identity server would be responsible for storing and giving out all the opinions that people have had about that person.
Alright, so here's one of the nifty bits - this came to me at about 3 AM while I was trying to fall asleep, as good ideas sometimes do. It seems that if the identity server is responsible for maintaining all opinions about you, good or bad, then it has no real reason to keep the bad ones. It could easily tell whoever asked that nobody has ever said anything bad about you, and nobody would be the wiser. What we need is a way for somebody leaving an opinion to prove that it was accepted. The obvious way to do this is to have the identity server sign incoming opinions and give back the signature, but there's still vulnerability here - the identity server could pretend to be suddenly deaf when you're saying mean things. On the other hand, we can imagine a three-step exchange, where you hand the server a hash of the opinion you want to give it, the server signs that and gives it back, and then you give the server the opinion. Remember, cryptographic hashes are opaque, so this means that the server is forced to accept all opinions. The user creating the opinion can simultaneously submit it to the distributed cache - this would ensure that an identity server which drops negative opinions can be discovered.
As for the third question - how are trust chains discovered? - this one is a little difficult. Finding optimal paths through a graph is easy if you have the entire graph lying around; not so much if it's spread out over thousands of computers, some of which are down at any given time. Ideally, we'd like to be able to find the best trust path between ourselves and some random other identity. However, we don't really need the best path; if a lot of paths exist, then some pretty good path is usually good enough. In that case, our slightly unreliable distributed cache suddenly looks pretty good - it has all the necessary data already, and with our relaxed requirements can give us exactly what we need.
So, there you have it. As far as I can think through, this proposal is mostly solid; I've spotted a few weak points already, and I might try to paper them over in a future post, but the core structure should stay the same. Even though this was originally a thought experiment, to prove that something like this is possible, I have a strange urge to actually implement it now ._.
Subscribe to:
Posts (Atom)