Current title: Attack resistant trust metrics Possible alternate title: Measuring trust in networks Current chapter list: Chapter 1: Introduction This book is about trust metrics. Today's Internet is a vast, highly diffuse network, spanning many different administrative domains. In such a network, only some of the users are worthy of trust. Attacks, of which spam is currently the most pervasive, are part of everyone's experience. The study of trust metrics assumes a network comprised of both good and bad (attacker-controlled) nodes, and attempts to classify them as good (accepted) or bad (rejected) as accurately as possible given the data available. This book asks, and to a great extent answers, the question of how good a trust metric can be. The core of the book discusses two practical trust metrics, based on network flow and eigenvectors, along with experience from implementing a community web site based on them. Chapter 2: Trust Metrics Introduces the concept of trust metrics, surveys the literature of existing trust metrics, provides a quantitative framework for analyzing trust metrics. Most existing trust metrics are based on the "scalar" assumption that the decision of deciding whether a node is accepted can be made independently for each such node. However, this assumption severely limits the best-case attack resistance of any such trust metric. We present a simple trust metric, based on network flow, that achieves this upper bound. Chapter 3: Group Trust Metrics Introduces the concept of group trust metrics, which relax the "scalar" assumption of the previous chapter, and compute the trust metric for all nodes simultaneously. We then present a simple group trust metric, also based on network flow, which provides a good guarantee on the total number of bad nodes accepted by the metric, as opposed to the catastrophic failure characteristic of all scalar trust metrics. Chapter 4: Advogato The advogato.org website was launched in Nov. 1999 as a testbed for the group trust metric described in the previous chapter. Advogato is a community site for free software developers, and has been remarkably successful in providing a forum for high quality discussions, and is almost completely free of trolls, spam, and abuse, in spite of its openness to new members, and requires an extremely low amount of manual administration. This chapter presents some details of the implementation, as well as much practical experience gained from running a real community site. Chapter 5: Name Services The original motivation for exploring trust metrics was to develop a distributed database for managing a namespace, with goals similar to DNS, but without the single-point of failure vulnerabilities inherent to the strictly hierarchical structure of DNS. To balance the practical needs of such a system against the design goal of security in a decentralized architecture is quite difficult. This chapter presents a design for such a service, along with some analysis. Chapter 6: Attack-Resistant Metadata (Eigenvector-based metrics) The group trust metric presented in Chapter 3 has the relatively narrow goal of evaluating membership in a community within a larger network. A similar problem is to determine the trustworthiness of metadata, for example which music is worth listening to or which blogs are worth reading. This chapter presents a trust metric based on eigenvectors suited for such a task. This metric, and its analysis, are closely related to Google's PageRank. Chapter 7: Stamp Trading Networks One of the most important potential applications of trust metrics is filtering out spam. However, where the trust metrics in previous chapters address the problem of authenticating individual users or pieces of metadata, the goal of a spam-resistant trust metric is to provide a bound on the total number of bad messages passed through the system. A spam filter based on a weaker metric, for example authenticating users as non-spammers, could let through unlimited quantities of messages once the attacker has gained a single bad authentication. This chapter outlines a design for such a trust network, based on trading authentication tokens valid for a single message each ("stamps") in a distributed network. To expand the thesis into a full book-length work, there should probably be a couple of additional chapters. Appealing topics include discussion of the "Sybil attack" analysis from Microsoft Research (my take is that it is based on some unnecessarily pessimistic assumptions), comparison of systems that include both positive and negative certifications ("X is a bad node") as opposed to positive only ("X is a good node"), and deeper quantitative analysis of spam resistance techniques (a primary result here would be that the single greatest vulnerability of hashcash based systems such as Microsoft's "Penny Black" is virus-borne attacks). Readership and market I know of no similar or directly competing books. Here are a number of books with some overlap of interest: "Peer to Peer", published by O'Reilly "Linked", by Albert-Laszlo Barabasi "Smart Mobs: The Next Social Revolution", by Howard Rheingold "Six Degrees", by Duncan Watts Motivational essay Most traditional study of computer security is rooted in the assumption of a hierarchical model - a computer system with important data, guarded by a system administrator whose job includes keeping outside intruders from gaining access to sensitive information. Such a model may work well in contexts such as military command-and-control systems, but is wholly inadequate for today's Internet, a diffuse and dynamic network with no clearly defined boundaries, much less an "inside" and an "outside". My work on trust metrics addresses the challenges of such a distributed network. Instead of a centrally administered passport-like credential, trust metrics attempt to measure membership in a community. I show, through both theoretical analysis and practical experience, that they can be quite accurate at this measurement. There are many possible applications for trust metrics, from community oriented sites such as Advogato, to music recommendation systems, to effective spam filters, and so on. In addition, a deep intellectual understanding of the concepts I discuss, notably attack resistance, could contribute to the study of social networks and other related fields. Unfortunately, my work has been rather inaccessible to the general public. The underlying theory (graph theory, network flows, eigenvectors) is not trivial, generally requiring a graduate-level understanding of the field. In addition, this work has generated only one peer-reviewed published paper, and I have only attended a handful of conferences to spread the word in person. As a result, the community of those who are deeply familiar with the work is quite small. Thus, I am excited about the possibility of presenting these ideas in the form of a book. Because of the inherent difficulty of the topic, it obviously is not suitable for a mass audience, but I believe it would appeal to sophisticated readers both in academia and among those striving to implement more flexible trust relationships in practical websites and related network tools. I have a story to tell about trust metrics, and very much relish the prospect of telling my story to the world through this book. Estimated length: 40-50 thousand words I expect there'll be twenty or so line drawings and graphs. A draft of the thesis is online at: http://www.levien.com/thesis/compact.pdf Estimated completion date for first draft: 30 June 2004. My employer has graciously offered a sabbatical for the purpose of completing the writing. Author bio Raph Levien has a Masters degree in Computer Science from UC Berkeley, 1995. He is currently Chief Technologist on the Ghostscript project, employed full-time by Artifex software. He is a fairly well-known figure in the community of free software developers, based on his contributions to Gimp, vector graphics tools, and the Advogato community website.