[minion-cvs] Revise path selection algorithm to make sense, incorpor...

[nickm@seul.org (Nick Mathewson)]

Update of /home/minion/cvsroot/doc/spec
In directory moria.mit.edu:/tmp/cvs-serv24481

Modified Files:
	dir-spec.txt 
Removed Files:
	path-spec.txt 
Log Message:
Revise path selection algorithm to make sense, incorporate into dirspec.

Index: dir-spec.txt
===================================================================
RCS file: /home/minion/cvsroot/doc/spec/dir-spec.txt,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- dir-spec.txt	20 Jun 2003 17:26:32 -0000	1.4
+++ dir-spec.txt	26 Jun 2003 03:02:34 -0000	1.5
@@ -51,6 +51,7 @@
    8.       Downloading directories
 
    A.1.     Appendix: Versioning and alphas
+   A.2.     Appendix: Suggested path selection algorithm
 
    X.       Open questions
 
@@ -571,6 +572,68 @@
    stable release comes out.  Stable releases will be taken off the list
    only for security or privacy reasons.
 
+A.2. Generating paths
+
+   Given a valid directory, clients MAY generate paths of any length
+   when they send messages.  Nonetheless, client implementors SHOULD
+   prefer consider the following approach to path selection, and
+   SHOULD be aware of anonymity issues if another algorithm is chosen.
+
+   Implementations MAY allow users to specify paths of their own.  If
+   they do, implementations SHOULD at least warn users who generate
+   paths that would not be generated by the standard algorithm.
+   Implementations that allow path selection SHOULD allow partial
+   path selection as well.
+
+   Implementations SHOULD at least allow users to specify 'random path
+   of length N', and 'random path of random length (E[length]=N)'.
+
+   [This algorithm is implemented in Mixminion 0.0.5]
+   
+   The inputs to this algorithm are:
+      1) The earliest time at which the path must be valid. (T_Start)
+      2) The latest time at which the path must be useable. (T_End)
+      3) A template consisting of two lists of server specifiers, one
+         list for each leg on the path.  A server specifier is either
+         a nickname, or the token 'ANY' to indicate a randomly chosen
+         server. When generating a SURB, the first list is empty.
+         When using a SURB, the second list is empty.
+      4) An exit address, unless using a SURB.
+
+   First, the client builds a list of 'current' server descriptors.
+   This list contains every server descriptor that meets these
+   criteria:
+
+      A) Is in the current directory.
+      B) Is valid continuously from T_Start through at least [[24
+         hours] from T_End.
+      C) Is published more recently than any other server descriptor
+         with the same nickname that meets criteria A and B.
+         (Remember, all Nickname comparisons are case-insensitive.)
+      D) Expires later than any other server descriptor with the same
+         nickname that meets criteria A and B and C.
+
+   The client also builds a list of 'preferred' server descriptors
+   This list contains every 'current' server descriptor that also
+   meets these criteria:
+
+      E) Has its nickname the 'Recommended-servers' list.
+ 
+   Next, the client resolves explicitly specified servers: every
+   server specifier with a provided nickname resolves into the
+   'current' server descriptor with that nickname.  If there is no
+   such server, the client gives an error message.
+
+   Next, the client picks the exit server (if not using a SURB).  If
+   the last entry of the second path specifier is ANY, the client
+   chooses an element at random from among those 'preferred' server
+   descriptors that support delivery to the exit address.
+
+   Finally, the client picks servers for each of the 'ANY' server
+   specifiers.  The client picks 'preferred' server descriptors at
+   random, with replacement, avoiding any sequence of two consecutive
+   server descriptors with the same nickname.
+   
 X. Open problems
    
    Because of possible partitioning attacks related to accidentally or

--- path-spec.txt DELETED ---