Finding credit paths between nodes in the Ripple network is its central component. How does it work? There are many possibilities.
How do nodes pass along queries?
Should routing keywords be given as hashes, or as bloom filter indices? Bloom filter indices give more anonymity, but lower accuracy....
Should each node keep an index of the distance to each keyword in each direction? Maybe. Requires a scheme to keep indices updated, and knowing that a certain keyword occurs at a node four steps in one direction has no bearing on the credit available along that path..
Start with the Basic Scheme above.
Search queries are non-branching routed walkers.
Nodes may route query-walkers based on any factors they choose, including:
Generally, nodes will assign a probability of quickly finding a path to the desired keywords through each neighbour based on the above factors, and route outgoing queries somewhat probabilistically.
Keywords are passed as hashes, by converting to uppercase and applying SHA-1.
Many different queries from the same transaction may be received and passed along by a given node. Nodes refuse to accept the same query a second time.
Queries that reach a dead end (a node with no available credit with any neighbour that has not already seen that query) retrace their steps. Retraced steps decrement TTL the same as forward steps. When TTL reaches 0, the query dies and no action is taken.
This type of search is fairly simple, and allows paths between relatively close nodes (many shared keywords) to be found quickly by sending out a few query walkers. If a path is not found quickly, more walkers, with higher TTL, can be sent out, until either a path is found or .
Not rigidly specifying the routing method at each node allows nodes to be innovative. The search may be more robust against certain types of failure because not all nodes are necessarily behaving identically.
Nodes remain relatively anonymous since they are identified only by an alias of their choosing, which can be different for every transaction. However, a node's transaction alias does get stored at every one of its neighbours it passes a query or path-found message to. I can think of no method to avoid this.
Payer and recipient nodes can disguise themselves as such by spoofing several alias stamps on the initial queries they send out to make it appear as though they are just passing along queries from some other source.
Hashing provides some privacy for the endpoints' keywords. It would be simple to discover common keywords (like geographic names) in their hashed form by brute force, however, since many nodes use these keywords, little information will be gained.
Less paranoid nodes could give their node a unique keyword that would mark every one of their transactions and possibly speed up routing a little, depending on how other nodes implemented keyword routing.
Nodes do not need to take advantage of the ability to participate anonymously. They could simply stamp queries with their node's ID or root URL.
Indices (attenuated bloom filters) at each node of the distance to each keyword in every direction to help routing. Requires a scheme for updating the indices while hopefully avoiding circular updates. Uses a little more bandwidth, but updates need not be very frequent (ie, daily) since the Ripple network is quite static, and new nodes can be found without updates propagating, since they have keywords in common with their neighbours.
A method of combining multiple queries into the same message to lessen traffic near the source, where many walkers may be sent out initially to the same node. This should be easy.