Bram - I realised after I posted that my attack does not necessarily allow you to cause a given statement to have unlimited confidence. It doesn't in the case of your proposal, for example. The application I usually have in mind when I think about trust metrics is prevention of crapflooding and similar nasties; to do that you need a bound not on the maximum trust the adversary can gain for a particular entity, but on the number of entities they can arrange to have trust for. If you want that, I think you can't have the "Adding Certification Criterion".

Actually, there's a way you can, but only if you add another restriction. If you allow a free graph - that is, a valid graph is any graph which has valid labels on the arcs - then you can't have it. But if you have some local condition affecting the arcs leaving a given node - such as that no two arcs leaving the same node may carry the same positive integer - then you can still do it.

Incidentally the Advogato algorithm (for people, not for diaries) fails the Isomorphism Criterion.

What sampling algorithm are you proposing? is it (1) make random compromise choices about all nodes (perhaps lazily), (2) see if there's an uncompromised path? The SD of the trust value computed would be 1/(2 * sqrt(n)) for n samples. Also I guess it's pretty cheap to collect trust levels for all nodes - "find all reachable nodes" is a pretty fast algorithm. However, the problem with using randomised algorithms for trust is that if your trust was very near some trust threshold, you would find yourself flapping either side of the threshhold on different days...