There's lots of newer research on trust-based systems that could be applicable here, e.g. a game-theoretic approach where entities are gauged based on ratings o

There's lots of newer research on trust-based systems that could be applicable here, e.g. a game-theoretic approach where entities are gauged based on ratings over repeated transactions. Think iterated prisoner's dilemma crossed with PageRank, which effectively wards against many types of collusion including simple sybil attacks. Most of it hasn't been validated in the real world on any scale, but I believe it is possible to do quite a bit better than we have seen - the only web-of-trust stuff I've seen in practice is ancient compared to the state of research. One outstanding problem that comes to mind is certificate revocation when you have lost control of the private keys. I think a multi-sig solution could probably mitigate this to a fair extent, so you still have some level of pseudo-trust between entities and a way to effectively call someone up and say, "hey, I screwed up and need to kill this thing".