multi-path support

[Apostolis Xekoukoulotakis]

I recently created a simple alpha quality graph processing system in C. It might take a while before it becomes bug free , anyway, I might be able to create a multi-path search algorithm based on my skip graph data structure. Would you be interested in such a thing? I could provide a zeromq socket with json serialization if you like.

From a technical point of view, the graph would have to be loaded into ram, I think 100bytes per node will suffice. The GPS is multi-threaded, so I assume that it will be really fast.

If I understand correctly, right now distances are precomputed and then fetched one by one from the database to find the shortest route.

--

Sincerely yours, 

     Apostolis Xekoukoulotakis

[Ryan Fugger]

Hi Apostolis. Cool that you're implementing this. Probably the most
useful thing for Ripple would be a good implementation of a minimum
cost flow algorithm:

https://en.wikipedia.org/wiki/Minimum-cost_flow_problem

This is what is done on Villages (albeit with the costs being the
desirability of using each edge, rather than the fees charged). There
are many different algorithms for solving this problem. In Villages,
I use the networkx python graph library for basic graph functions.
Networkx has an implementation of min cost flow, but in my tests it
was much slower than the one I implemented:

https://github.com/rfugger/villagescc/blob/master/cc/payment/mincost.py

Ripplepay uses a simpler but less useful and predictable
multipath-search algorithm.

It would be cool if you could integrate arbitrary exchange rates at
each step as well. What I was thinking is to convert the entire graph
to the recipient's units before doing the search, but this will
multiply the number of nodes immensely in general, since each path to
the recipient is potentially a different value for a node's IOUs once
converted. (Hopefully that makes sense -- I can illustrate if need
be.) Maybe there's a better way...

Implementing in C makes things fast, but it's not my first choice to
hack on, personally, so it's possible it may be more useful in the
long run once it's more certain how things will work. But if you want
to work on this aspect of things and figure out how things need to
work, it could be very useful indeed.

Thanks!

Ryan

> --
> You received this message because you are subscribed to the Google Groups
> "Ripple Project" group.
> To post to this group, send email to rippl...@googlegroups.com.
> To unsubscribe from this group, send email to
> rippleusers...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/rippleusers?hl=en.

[Walter]

General comment only here - for a related effort with some more ideas
about differences between settlement links in the multipath settlement
area, you might like to take a look at some of the sections of the
very beta IFEX Proposal at
http://www.ifex-project.org/our-proposals/ifex/2012-04-11-partial-draft

Thus far that project has seen little public discussion though a fair
number of people have joined the related mailing list and expressed
interest privately so there is definitely latent interest out there.

With particular reference to the ideas in this thread you might get
something out of skimming the sections:
- Transaction Terms
- Fee, Tax and Discount Support
- Settlement Paths

The key point is that it is difficult to rule out the requirement for
near-arbitrary routing preferences in a forward looking financial
network. Participants might wish to route based upon any or all of
the following:
- trust model (increasingly these may be dynamic/evolving)
- cost model (fee/tax/discount support, asset conversion requirements, etc.)
- temporal requirements (must arrive before a certain time within a
certain timezone, services in some nodes may be suspended over banking
holidays or due to scheduled/unscheduled outage, regulatory ingress,
etc.)
- assets supported
- integrated risk model (asset conversion / 'currency exchange', time
that funds are exposed/tied up, other types of risk)
- transaction reversal or non-reversal guarantees
- explicit preferences for or against specific traversed assets,
nodes/systems, or legal juridiction(s)

Each participant node may have its own preferences, and these may
change over time.

It's a complex and interesting problem space.

- Walter

[Ryan Fugger]

Thanks Walter. This is why I think it's important for a generalized
Ripple server to support clients that want to choose their own paths
for their own reasons, as well as offer a relatively simple cost-based
path-finding option to support less-sophisticated clients.

Ryan

[Apostolis Xekoukoulotakis]

OK guys, I ll look into what you said. As you know, I have my own reasons for creating a fast graph processing system. Since it is related to trust and finances, studying similar efforts will be very helpful.
Walter's ifex project is more general and practical and it will give me good insight.

Ryan , Do you know the architecture of networkx? Does it do parallel processing? I use message-passing between nodes.  I was inspired by signal/collect.

I will continue writing in C because I can reason in it. One of the reasons I cant really help in ripple in my spare time is the use of python, so I can understand your reluctance in using C. Right now, I am forced to use Java, smalltalk, C, and javascript so I am a bit overcumbered. My native languages are C and smalltalk.

I will provide a zeromq api, so you wont need to touch any source code. In any case, the programming model is very easy(actor-like).


Also, do you have any graph datasets I could benchmark on?

2012/7/27 Ryan Fugger <a...@ryanfugger.com>

[Ryan Fugger]

On Thu, Jul 26, 2012 at 7:09 PM, Apostolis Xekoukoulotakis
<xeko...@gmail.com> wrote:
> Ryan , Do you know the architecture of networkx? Does it do parallel
> processing? I use message-passing between nodes. I was inspired by
> signal/collect.
>

As far as I know, networkx is single-threaded basic python.

> I will continue writing in C because I can reason in it. One of the reasons
> I cant really help in ripple in my spare time is the use of python, so I can
> understand your reluctance in using C. Right now, I am forced to use Java,
> smalltalk, C, and javascript so I am a bit overcumbered. My native languages
> are C and smalltalk.
>

Not to push you to work in python, but don't let unfamiliarity ever
stop you. If you're proficient in C, java, and javascript, you'll
pick python up in an hour.

> I will provide a zeromq api, so you wont need to touch any source code. In
> any case, the programming model is very easy(actor-like).
>

Right. And if you're doing it for your own purposes anyways, then
I'll definitely see if I can use it. Thanks.

Ryan

[Apostolis Xekoukoulotakis]

Providing a zeromq api was meant so that you dont have to write any c code. If you prefer to write C code, then I wont create the api.

Implementing a minimum cost flow algorithm isnt something that I need right now. I will implement it only if it is useful to ripple.

I am currently reading this. Then I ll have to see how that translate to the asynchronous message passing computation model that I have. If you are interested, you can read the signal/collect paper, the part about the asynchronous computation and then help me translate the algorithms.

2012/7/27 Ryan Fugger <a...@ryanfugger.com>

[Ryan Fugger]

On Thu, Jul 26, 2012 at 10:51 PM, Apostolis Xekoukoulotakis
<xeko...@gmail.com> wrote:
> Providing a zeromq api was meant so that you dont have to write any c code.

Yeah, I get that, thanks.

> If you prefer to write C code, then I wont create the api.
>

I'm not a fan of writing C code if I don't have to :)

> Implementing a minimum cost flow algorithm isnt something that I need right
> now. I will implement it only if it is useful to ripple.
>

There's a C++ implementation of several min-cost flow algorithms here:

http://lemon.cs.elte.hu/pub/doc/1.2.3/a00534.html

LEMON comes with a python wrapper too, so I might just use that.

> I am currently reading this. Then I ll have to see how that translate to the
> asynchronous message passing computation model that I have. If you are
> interested, you can read the signal/collect paper, the part about the
> asynchronous computation and then help me translate the algorithms.
>

Have you ever used Go? It might be suited to this sort of thing...

Ryan

[Apostolis Xekoukoulotakis]

ok.

> Have you ever used Go?  It might be suited to this sort of thing...

The problem is not the language but the algorithm.

2012/7/27 Ryan Fugger <a...@ryanfugger.com>

--
You received this message because you are subscribed to the Google Groups "Ripple Project" group.
To post to this group, send email to rippl...@googlegroups.com.
To unsubscribe from this group, send email to rippleusers...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/rippleusers?hl=en.

[Apostolis Xekoukoulotakis]

http://lemon.cs.elte.hu/pub/doc/lemon-intro-presentation.pdf

After 10000 nodes, things get ugly.

I think we should care about performance before we reach at the point where we need it.

If the minimum cost flow algorithm is not scalable to the millions of nodes, then the ripple project is simply technically impossible and we should abandon it or change our goals to meet the technically possible.

That is exactly the reason why I am interested in performance. Right now, I only have a fancy idea. I need proof that it can be done.

2012/7/27 Apostolis Xekoukoulotakis <xeko...@gmail.com>

[Ryan Fugger]

I'm glad you're looking into this, Apostolis. 

An ideal solution for me would involve a pre-computed and easily-updatable ordered set of paths to use between any two nodes to minimize flow cost.  I can imagine starting with the set of all paths of length 1, combining those to form a set of paths with length 2, and so on, forming a tree containing paths of length n at level n, with each path having shorter paths as parents, all the way back to paths of length 1.  You would index all paths by (start, end), and order by cost for each (start, end) pair.  To update the tree, you'd update the length 1 path that has changed, and then propagate the update to all its ancestors.  To save time and space, you could trim out (or de-prioritize/de-index) paths that are not likely to be used because they have insufficient cheap capacity.  This could all be done in parallel on a large cloud deployment operated cooperatively by a group of larger server operators, or as a 3rd-party service, and queried remotely whenever Ripple servers needed a path.

But in the end if we can't always find the mathematical minimum cost flow in a reasonable amount of time, it doesn't mean Ripple is technically impossible, it just means that we need an approximation that gives decent results in much shorter time.  Most min-cost flow algorithms seem to work by refining an approximate solution until no more improvements are found.  We could just stop after a certain amount of time as long as a reasonable-cost criteria is met.  Your skip-graph idea is a possibility as well.

There are many other possibilities, depending on what the network topology ends up looking like.  For example, if a server knows of well-established high-volume cheap paths, those could be treated as a network backbone to be used wherever possible.  The server need then worry mainly about paths to and from the backbone, and might only occasionally need to search for alternative pathways.  In some sense, establishing this backbone is the same problem as trimming out paths that aren't useful in my ideal solution above.

The current protocol leaves it up to the payer to determine what route they want to use.  This means that as the network grows and handles higher transaction values, more resources can be devoted to improving routing calculations without requiring any change to the protocol.  I'm comfortable starting with something that can handle 10,000 nodes and work from there, especially with people like you already thinking about how to handle 1,000,000 nodes and beyond :)

Ryan

[Ryan Fugger]

On Sat, Jul 28, 2012 at 1:20 PM, Ryan Fugger <a...@ryanfugger.com> wrote:
> I can imagine starting with the set of all paths of length 1, combining those to form a set of paths with length 2, and so on, forming a tree containing paths of length n at level n, with each path having shorter paths as parents, all the way back to paths of length 1.

s/tree/DAG/

> You would index all paths by (start, end), and order by cost for each (start, end) pair. To update the tree, you'd update the length 1 path that has changed, and then propagate the update to all its ancestors.

s/ancestors/children/

Ryan

[Xekoukoulotakis Apostolos]

[Apostolis Xekoukoulotakis]

What you are saying is impossible. You want to save all possible paths.
The space complexity of this is O(n^2) multiplied ,most probably, by the cycle basis of your graph, multiplied by the average distance between 2 nodes.

If you trim something, you wont be able to update in some cases.


Ok, In conclusion, Ripple might not be able to reach more than a few thousands because people will not learn about it.
But You cant start a project and think like this.

I hope there are scalable algorithms for this. My skip-graph structure might work, i dont know right now.

I have also stopped looking into this. From a small search, I realized that very few have tried to parallelize it, thus it might be a tough problem, or maybe they are not trying to precompute things.

I am glad you thought of possible solutions.

2012/7/28 Xekoukoulotakis Apostolos <xeko...@gmail.com>

[Ryan Fugger]

On Sat, Jul 28, 2012 at 2:35 PM, Apostolis Xekoukoulotakis <xeko...@gmail.com> wrote:

What you are saying is impossible. You want to save all possible paths.
The space complexity of this is O(n^2) multiplied ,most probably, by the cycle basis of your graph, multiplied by the average distance between 2 nodes.

Each server only needs paths that start at its local nodes, so O(n) pairs, not O(n^2), for a server with a fixed number of nodes.

It's entirely possible, though not necessarily desirable, that the cycle basis of the network is a small set, if many nodes are simply client leaves of better-connected routing nodes.  This would be the case if most Ripple users decide not to perform any routing exchanges themselves, but to simply make and receive payments.  We don't yet know that this isn't the case, and so we may be worrying about nothing.
 

If you trim something, you wont be able to update in some cases.

That's why I said "or de-prioritize/de-index", because .  But if you trim an expensive path and later it becomes cheap (which is simple to discover), you would just have to compute its children to perform the update.

You might also trim on path length, server response times, server reliability, asset desirability, or any other number of factors.  Again, the goal isn't to necessarily get the mathematically cheapest path each time, but just something acceptable to the user.  If there aren't a lot of path options between two nodes, then trimming isn't appropriate, but paths are easy to compute.  If there are too many path options between two nodes, then trimming is appropriate to narrow the choices down to the most likely to be cheap and reasonable at any given point in time, and this makes path computation cheaper.  I don't see a problem.
 
Yes, I would expect this all to take a lot of effort to get right.  Hopefully there is enough value in the network to be worth it.  That is the real question, and one we can only answer by trying.

Ok, In conclusion, Ripple might not be able to reach more than a few thousands because people will not learn about it.
But You cant start a project and think like this.

I think it's far better to push ahead in the face of hypothetical future technical challenges than be paralyzed by them before they even happen.  I have enough other challenges to worry about.  If the network gets big enough that routing becomes a major challenge, that is a *great* problem to have!

Thanks for your input!

Ryan

[Apostolis Xekoukoulotakis]

I continue to believe that this wont work. Spliting the problem to many servers doesnt change the fact that it is a O(n^2) problem. Also I should have said that if k is the dimension of the basis, then the space complexity is multiplied by 2^k.

In any case, we have different kind of priorities. Why argue about something which you dont find important right now.

2012/7/29 Ryan Fugger <a...@ryanfugger.com>

[Ryan Fugger]

It may not be ultra-important right now, but it is interesting :)

So why don't you believe that it will work with smart trimming?  Obviously, you don't need to know every path between each node, just a set of decent ones.  Suppose we could trim it down to a maximum of 10 paths per (start, end) pair.  Would that be feasible, do you think?

Ryan

[Apostolis Xekoukoulotakis]

well, I dont know of the exact implication of trimming. To give you a definite answer, I ll need to work on it.
So since it is not a priority, I will make an example of a skip-graph search, and then leave this problem alone till it is required to be solved.

The skip graph has O(2n) space complexity. For the time complexity i am not sure right now.

Lets say we want to go from Heraklion Crete to Vancouver, Canada. We create a skip-graph on earth in this way.

The earth is the root node at level 0.
At level 1, we cover earth with the minimum number of 'balls' of d/2 diameter. d is the diameter of earth.
At level 2, we cover earth with balls of d/2^2 diameter such that each ball is contained is contained in a ball of the previous level.
At one point the balls are small enough that represent more or less a city.

Each ball has neighbors of balls of the same level. You create edges to represent that.
Each ball has a parent or parents and childs.

Now this is simply an example. In a graph, you start from cities and you go up to the whole graph.

How would you find the fastest way  from Vancouver to Heraklion?
Each city has a set of ids that represent the balls it is in.

We start by level 0.
Both cities are on earth. Interplanetary solutions are not part of the project yet :)
At level i, we find the shortest path.
if that path is of length k, what are the boundaries of the possilble minimum distance it can provide?
the boundaries are [k*d/2^i,(k+4)*d/2^i].

Now, maybe there are other paths in the same level that have a minimum boundary that is smaller than the maximum boundary of this path. For a perfect solution, we would have to search both of those routes.

After we pick a path at level i, we only have to search for paths that traverse inside those nodes.
In our exampe we might have a path at level i of average countrys diameter.
At level i+1, wed have to find a path from one country to the adjacent one.

So here it is, we can very fast discard paths.

Now here is a problem, the boundaries in a graph are not as good as those I described above.
Another one, I havent described how to parallelize this. We'd have to do searches concurrently. When a transaction happens, the graph should change to represent the broken paths, those that dont have more credit.

That's all. I better go back to my work now.

[Apostolis Xekoukoulotakis]

Now the real answer as to how to go from Vancouver to Heraclion, Crete is to take a plane.

2012/7/29 Apostolis Xekoukoulotakis <xeko...@gmail.com>

[Ryan Fugger]

On Sat, Jul 28, 2012 at 6:51 PM, Apostolis Xekoukoulotakis <xeko...@gmail.com> wrote:

well, I dont know of the exact implication of trimming. To give you a definite answer, I ll need to work on it.

Suppose we're storing paths as one hop at the head, and another path at the tail.  Trimming would go something like this:  Limit the number of paths stored per (start, end) pair to a fixed number, say 10, which are the top-rated by some heuristic like:

min(capacity, largest expected payment) / cost

Whenever we're adding or updating a path, check against the existing 10 or fewer stored paths for that (start, end) pair and drop the lowest of them, and all their children.  If a path's rating decreases, compare against all paths that can be created from one hop to a neighbour from the start, combined with all stored paths from that neighbour to the end (ignoring ones with loops), and drop it if another path is better.
 

The skip graph has O(2n) space complexity. For the time complexity i am not sure right now.

Lets say we want to go from Heraklion Crete to Vancouver, Canada. We create a skip-graph on earth in this way.

The earth is the root node at level 0.
At level 1, we cover earth with the minimum number of 'balls' of d/2 diameter. d is the diameter of earth.
At level 2, we cover earth with balls of d/2^2 diameter such that each ball is contained is contained in a ball of the previous level.
At one point the balls are small enough that represent more or less a city.

OK, I'm following.  How would we apply this to the Ripple network?  What would "distance" be?  It seems we would need a measure, like my heuristic above, that takes into account both path cost and path capacity.  The problem is, the unit value at each node can be arbitrary, so path cost and path capacity are not directly comparable between end nodes, even from a common starting node, so I don't know how we'd assign nodes into the hierarchy of balls.  I'm not sure how to resolve this.

But if we can resolve this, our methods are similar in that they involve reducing the set of paths to consider at payment time. 

Each ball has neighbors of balls of the same level. You create edges to represent that.
Each ball has a parent or parents and childs. 

 

How do skip graphs determine which edges to use to interface between higher-level balls?  How do you balance between choosing too few interfacing edges, potentially missing large numbers of useful paths, and the complexity of having too many paths to consider if there are many interfacing edges?  If I understand correctly, we can't use all the interfacing edges, since that does nothing to reduce complexity.

I've thought something along these lines before, wishing to create an organic hierarchy out of the Ripple network to simplify routing computations:

http://ripple-project.org/Protocol/CellStructureRouting
http://ripple-project.org/Protocol/BuildingCellsByBlockChain

Maybe there's something useful in the intersection of all these ideas?

Ryan

[Ryan Fugger]

On Sat, Jul 28, 2012 at 8:15 PM, Ryan Fugger <a...@ryanfugger.com> wrote:

OK, I'm following.  How would we apply this to the Ripple network?  What would "distance" be?  It seems we would need a measure, like my heuristic above, that takes into account both path cost and path capacity.  The problem is, the unit value at each node can be arbitrary, so path cost and path capacity are not directly comparable between end nodes, even from a common starting node, so I don't know how we'd assign nodes into the hierarchy of balls.  I'm not sure how to resolve this.

Thinking more...  In terms of capacity we could measure from the *end* node, and value a path by how many end-node units it can achieve.  But in terms of path cost, it doesn't seem possible to compare paths except between the same two endpoints...

Ryan

[Apostolis Xekoukoulotakis]

Ok, so first of all, to decide if trimming is an acceptable solution, we would have to compare with the current technology.

Apart from that, with trimming we would have reduced the cycle basis multiplication part to 10.
Updating such a structure though is very very difficult.
Some edges will have a global effect on thousands or millions of nodes. Think of what happened when the suez canal was built.

In our example the cost is the distance and the boundaries as before is the way to discard paths before traversing them.

Each edge in the initial graph has a capacity and a cost right?

if we are at level i, at level i-1 we would take as the cost of the edge that connects 2 balls as the minimum cost that can be achieved from a path that connects their centers in level i. We would also assign the capacity of that edge as the capacity of the new edge at level i-1.

Finding a multipath solution involves finding m shortest paths whose  total capacity is more or equal to the requested capacity.

Updating that structure is under investigation. I think of it like this. an edge in the initial graph can be unimportant so only ony one change in the graph would happen or it could be very important like the suez canal and then edges in the upper level would be removed. those edges in our example are for example connections between countries and in the upper level, connections between continents.

Due to the fact that each level has 1/2(in general, needs to be found for a weighted graph) less nodes than the previous, you would need to make 64 changes in the worst case if your initial graph had 2^64 nodes.

>How do skip graphs determine which edges to use to interface between higher-level balls?  How do you balance >between choosing too few interfacing edges, potentially missing large numbers of useful paths, and the >complexity of having too many paths to consider if there are many interfacing edges?  If I understand correctly, >we can't use all the interfacing edges, since that does nothing to reduce complexity.

As I said above we take only the one with the smallest cost. We update the graph by removing that path and try to find the rest of the paths. Updating is easy.

I dont really understand your last message. I think that the answer is what I said above. The capacity and cost between two balls is defined as the capacity and cost of the shortest(ie less cost) path between their centers in the "next" (i+1) level.

Because we take the cost between the 2 centers as the cost of the edge, we can only have an aproximation of what the final cost will be. Thats why we have un upper and lower bound on the cost.

Let me repeat that those are initial estimates which I did a while ago. It needs more testing and a way to parallelize things but I am optimistic.

2012/7/29 Ryan Fugger <a...@ryanfugger.com>

--

You received this message because you are subscribed to the Google Groups "Ripple Project" group.
To post to this group, send email to rippl...@googlegroups.com.
To unsubscribe from this group, send email to rippleusers...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/rippleusers?hl=en.

[Ryan Fugger]

On Sat, Jul 28, 2012 at 8:15 PM, Ryan Fugger <a...@ryanfugger.com> wrote:

Suppose we're storing paths as one hop at the head, and another path at the tail.  Trimming would go something like this:  Limit the number of paths stored per (start, end) pair to a fixed number, say 10, which are the top-rated by some heuristic like:

min(capacity, largest expected payment) / cost

Actually, instead of a fixed number of paths, it's probably better to target a certain amount of flow per source node, which could be variable per node.  That way you don't end up with 10 paths all having the same capacity-limiting edge, and missing out on a better set of paths in terms of overall flow capacity.
 

Whenever we're adding or updating a path, check against the existing 10 or fewer stored paths for that (start, end) pair and drop the lowest of them, and all their children.  If a path's rating decreases, compare against all paths that can be created from one hop to a neighbour from the start, combined with all stored paths from that neighbour to the end (ignoring ones with loops), and drop it if another path is better.

You would only need to rebuild all the other options if a path's rating fell below the other 10 paths in the set, or, if we're using capacity as a limit as above, if the overall capacity of the set diminished below the threshold, or anytime the cost of a path increased (which could be often, so you might only recheck this occasionally.

Ryan

 

[Ryan Fugger]

On Sat, Jul 28, 2012 at 10:20 PM, Apostolis Xekoukoulotakis
<xeko...@gmail.com> wrote:
> Ok, so first of all, to decide if trimming is an acceptable solution, we
> would have to compare with the current technology.
>
> Apart from that, with trimming we would have reduced the cycle basis
> multiplication part to 10.
> Updating such a structure though is very very difficult.

The process I've described doesn't seem difficult. Have I missed something?

> In our example the cost is the distance and the boundaries as before is the
> way to discard paths before traversing them.
>
> Each edge in the initial graph has a capacity and a cost right?
>

Not really. Each edge has a capacity and an exchange rate.

For example, I could have two edges to compare, one from node A -> B,
where B gives credit for 2 of his IOUs for each of A's he receives,
and another from node C -> D, where D gives credit for 3 of her IOUs
for each of C's she receives? Which one is cheaper? It depends on
what A, B, C, and D's IOUs mean.

*Paths* have a cost, which is given in the source node's IOUs per unit
that is received by the destination node. Paths between the same
source and destination can therefore be compared directly, but paths
with different source or destination cannot. This is why I'm not sure
we've even defined a proper distance measure on the Ripple graph yet
to even begin applying your method.

> if we are at level i, at level i-1 we would take as the cost of the edge
> that connects 2 balls as the minimum cost that can be achieved from a path
> that connects their centers in level i. We would also assign the capacity of
> that edge as the capacity of the new edge at level i-1.
>

How do we partition nodes into balls in the first place?

> Finding a multipath solution involves finding m shortest paths whose total
> capacity is more or equal to the requested capacity.
>
> Updating that structure is under investigation. I think of it like this. an
> edge in the initial graph can be unimportant so only ony one change in the
> graph would happen or it could be very important like the suez canal and
> then edges in the upper level would be removed. those edges in our example
> are for example connections between countries and in the upper level,
> connections between continents.
>
> Due to the fact that each level has 1/2(in general, needs to be found for a
> weighted graph) less nodes than the previous, you would need to make 64
> changes in the worst case if your initial graph had 2^64 nodes.
>

This is only true as long as there are no changes to the partitions at
any level, right? But the partitions are determined by some method
involving cost, and cost can change...

>

>
>>How do skip graphs determine which edges to use to interface between
>> higher-level balls? How do you balance >between choosing too few
>> interfacing edges, potentially missing large numbers of useful paths, and
>> the >complexity of having too many paths to consider if there are many
>> interfacing edges? If I understand correctly, >we can't use all the
>> interfacing edges, since that does nothing to reduce complexity.
>
> As I said above we take only the one with the smallest cost.

What if the cheapest edge (if it can even be determined) has very
little capacity, but there are slightly more expensive parallel paths
with lots of capacity? Would we have to recompute a portion of the
ball structure to make a larger payment? What if that involves
re-partitioning the entire system? What if there are other paths at a
higher level, but those are more expensive than the paths we've missed
out on? How would we properly know where to look without re-computing
the system minus the one path we've used? What if that one path is a
"Suez Canal"? Etc...

Ryan

[Ryan Fugger]

On Sat, Jul 28, 2012 at 10:21 PM, Ryan Fugger <a...@ryanfugger.com> wrote:
> Actually, instead of a fixed number of paths, it's probably better to target
> a certain amount of flow per source node, which could be variable per node.
> That way you don't end up with 10 paths all having the same
> capacity-limiting edge, and missing out on a better set of paths in terms of
> overall flow capacity.
>

Further, you can tune the target flow amount particularly to each
(start, end) pair based on any information you might have of the
likelihood and probable amount of a payment between those endpoints.
If you're a server doing routing computations for your own node's
payments (which is the most likely scenario, at least to start),
you'll have the most information about those nodes (payment history,
etc.). You can also prioritize your CPU usage to compute paths for
what are historically higher-demand pathsets between endpoints, so you
have fast up-to-date routing for most payments, and allow infrequent
payments to take a bit longer to compute.

You can also always fall back on the old on-demand min-cost flow
algorithms for payments whose needs exceed the limited number of
pre-computed paths you have stored. Or do some kind of recursive
path-building based on what you already have, to see if the paths you
trimmed can make up the difference. Not sure what would be faster...

Ryan

[Apostolis Xekoukoulotakis]

Is this the min-cost flow problem then? All my analysis was based on that.

If this is a multi-barter(iou) system, then I am working on a way to update the prices with the use of a spanning tree. It is the basis structure with which I intend to build my multi-barter system.
I stopped working on it to create the tools (the graph processing system) to benchmark its speed.

In fact, ripple with exchange rates between ious is what I will use as an insurance system.

I am not sure my methods can be used here. In my system, the user bids for specific products. Here you want the prices of all the products. I ll have to think on it.

>
>The process I've described doesn't seem difficult.  Have I missed something?

The problem is that there are many affected nodes, so in a change of an edge that is used by many nodes and edges, all those paths would have to recomputed.

>This is only true as long as there are no changes to the partitions at
>any level, right?  But the partitions are determined by some method
>involving cost, and cost can change...

When cost changes, the maximum number of changes is 64, depending on how huge that effect is, does it affect continents, or cities?

>What if the cheapest edge (if it can even be determined) has very
>little capacity, but there are slightly more expensive parallel paths
>with lots of capacity?  Would we have to recompute a portion of the
>ball structure to make a larger payment?  What if that involves
>re-partitioning the entire system?  What if there are other paths at a
>higher level, but those are more expensive than the paths we've missed
>out on?  How would we properly know where to look without re-computing
>the system minus the one path we've used?  What if that one path is a
>"Suez Canal"?  Etc...

We remove the cheap edge, make the necessary changes to the ball structure and try to find the next cheap path. It is certain that the result will be an optimal multi-path.

Of course, this doesnt seem like a min-cost flow problem to me or is it?

As for the rest, using a cache of routing paths can help.

Again, all my analysis was based on the fact that this is a min-cost flow problem.

2012/7/29 Ryan Fugger <a...@ryanfugger.com>

Ryan

--
You received this message because you are subscribed to the Google Groups "Ripple Project" group.
To post to this group, send email to rippl...@googlegroups.com.
To unsubscribe from this group, send email to rippleusers...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/rippleusers?hl=en.

[Apostolis Xekoukoulotakis]

How are balls created? I thought of this without weights.

With weights I assume, it will be like this.
At the initial graph, pick a number of nodes so that any two of them has distance(cost) more than 2. those nodes become the centers of the balls of the higher level and all other nodes are the children to the balls that contain them.
ETC.

2012/7/29 Apostolis Xekoukoulotakis <xeko...@gmail.com>

[Ryan Fugger]

On Sat, Jul 28, 2012 at 11:40 PM, Apostolis Xekoukoulotakis
<xeko...@gmail.com> wrote:
> Is this the min-cost flow problem then? All my analysis was based on that.
>

The min-cost flow problem is for one source, one sink, one amount, and
with costs given explicitly. My idea is to pre-compute as much as
possible without knowing the source, sink, or amount, and only knowing
the costs in relative terms (exchange rates), which is what the Ripple
graph provides. Then, when a (source, sink, amount) presents itself,
you can get the answer in minimal time, simply by peeling off the
cheapest pre-computed paths for that (source, sink) until you have
enough flow to satisfy your amount.

>>The process I've described doesn't seem difficult. Have I missed
>> something?
>
> The problem is that there are many affected nodes, so in a change of an edge
> that is used by many nodes and edges, all those paths would have to
> recomputed.
>

Yes, I don't see any way around that, regardless of method. This is
the "Suez Canal" you mentioned earlier.

> How are balls created? I thought of this without weights.
>
> With weights I assume, it will be like this.
> At the initial graph, pick a number of nodes so that any two of them has
> distance(cost) more than 2. those nodes become the centers of the balls of
> the higher level and all other nodes are the children to the balls that
> contain them.
> ETC.
>

OK, so you're solving the min-cost flow with a specified source, sink,
and amount, at payment time? I can see how we had some confusion
there...

I still don't get how you can pick a number of nodes so that any two
of them have distance(cost) more than 2 between them. 2 what? It is
meaningless to compare the cost of two paths unless the endpoints of
each are identical, because there are no absolute units of measure in
the system, only relative costs in units of output unique to each
node.

Also, where does "2" come from?

Thanks for your patience :)

Ryan

[Apostolis Xekoukoulotakis]

No the last message just explained what I did before. Nothing new.

I used 2 because that I what I used in the non-weighted graph. Any number will do as long as you understand that picking a big number will reduce the number of levels but will increase the complexity of finding a shortest path in each level.

Picking 2 in the non-weighted graph meant that finding a shortest path in a specific level was instant. 2 is the smallest number you can choose in this context.


What are the costs anyway? Can you give an example?

2012/7/29 Ryan Fugger <a...@ryanfugger.com>

Ryan

--
You received this message because you are subscribed to the Google Groups "Ripple Project" group.
To post to this group, send email to rippl...@googlegroups.com.
To unsubscribe from this group, send email to rippleusers...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/rippleusers?hl=en.

[Apostolis Xekoukoulotakis]

Forget all my previous analysis and give me an example where you transform exchange rates to costs so that I can solve the min-cost flow problem (single source-single sink).

2012/7/29 Apostolis Xekoukoulotakis <xeko...@gmail.com>

[Ryan Fugger]

On Sun, Jul 29, 2012 at 12:17 AM, Apostolis Xekoukoulotakis
<xeko...@gmail.com> wrote:
> Forget all my previous analysis and give me an example where you transform
> exchange rates to costs so that I can solve the min-cost flow problem
> (single source-single sink).
>

Yes, I think this is the core issue. Here's an idea:

If you know the destination node, you can calculate the relative value
for payment purposes of each other node's IOU units. Say the best
path from node N to node D (destination) has a cumulative exchange
rate of 1.4, so it takes 1.4 N-units to buy 1 D-unit. If there was
another path where those same 1.4 N-units only bought 0.8 D-units, you
could say the cost of that path was 0.2 D-units. In that way, you
should be able to define the cost of each edge as follows:

Every node would have at least one path of cost 0 to D, the one with
the best cumulative exchange rate. These 0-cost best-path edges form
a spanning tree. If edge A->B is not in the spanning tree, its cost
can be found by comparing how many D-units you can buy from A along
the spanning tree of 0-cost edges with how many D-units you can buy by
using the path A->B->..->D, where B->...->D is the zero cost path from
B to D on the spanning tree.

The problem then falls to computing the spanning tree. I'm not sure
you can do it without checking through all the paths that have a
chance of being cheaper than ones already checked, somewhat like I've
proposed in this thread...

Ryan

[Apostolis Xekoukoulotakis]

What is the cost of B->..->D per edge viewed for the point of view of A. Can all those costs be added to get the cost of the path?

In general , what you do seems correct. It is an entirely different problem though. Let me sleep on it.

2012/7/29 Ryan Fugger <a...@ryanfugger.com>

Ryan

--
You received this message because you are subscribed to the Google Groups "Ripple Project" group.
To post to this group, send email to rippl...@googlegroups.com.
To unsubscribe from this group, send email to rippleusers...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/rippleusers?hl=en.

[Apostolis Xekoukoulotakis]

I think you are correct though, you have to check all the paths.

2012/7/29 Apostolis Xekoukoulotakis <xeko...@gmail.com>

[Jorge Timón]

Interesting conversation in scalability, multi path and different
criteria (maybe several of them simultaneously) search.
Not sure I've understood Ryan's last proposal. I think I've done it,
but I'll keep on lurking the thread.
Apostolis, it is great that you're working on this problem at this
early stage. I also think that ZMQ can be very useful for the
protocol, even if I've never coded anything with it. I haven't used
Python yet neither (well, some little toys with the interactive mode,
but that doesn't count), but I'm really attracted to it. I've seen
lots of python conferences and I'm not even scared about performance.
There's many things out there: numpy, cython, pypy, pyCUDA...
Although I still have to code in java and javascript at work, I'm done
with the coding part of my last project for college and I expect to
turn python into my "main language", whatever that means.

About sharing efforts...The current Ripple protocol design is pretty
generic and extensible.
Walter, have you considered using it as the base for IFEX ?
I'm more convinced each day that the distributed ripple protocol will
be the glue for all alternative currencies and payment systems to work
together.
For the special case of chain currencies (bitcoin) in which the
settlement could be atomic with the rest of the ripple transaction, I
think another commit extension should be enough.

Jorge Timón

[Jorge Timón]

Interesting conversation in scalability, multi path and different
criteria (maybe several of them simultaneously) search.
Not sure I've understood Ryan's last proposal. I think I've done it,
but I'll keep on lurking the thread.
Apostolis, it is great that you're working on this problem at this
early stage. I also think that ZMQ can be very useful for the
protocol, even if I've never coded anything with it. I haven't used
Python yet neither (well, some little toys with the interactive mode,
but that doesn't count), but I'm really attracted to it. I've seen
lots of python conferences and I'm not even scared about performance.
There's many things out there: numpy, cython, pypy, pyCUDA...
Although I still have to code in java and javascript at work, I'm done
with the coding part of my last project for college and I expect to
turn python into my "main language", whatever that means.

About sharing efforts...The current Ripple protocol design is pretty
generic and extensible.
Walter, have you considered using it as the base for IFEX ?
I'm more convinced each day that the distributed ripple protocol will
be the glue for all alternative currencies and payment systems to work
together.
For the special case of chain currencies (bitcoin) in which the
settlement could be atomic with the rest of the ripple transaction, I
think another commit extension should be enough.

On 7/29/12, Apostolis Xekoukoulotakis <xeko...@gmail.com> wrote:

Jorge Timón

[Apostolis Xekoukoulotakis]

Yea, I can create such a graph processing system so easily because of zeromq. I am routing messages between threads with a ZMQ router.

If we omit the exchange rates, ie if we simply require to find a disjoint multi path between nodes, then, I think, the skip graph will do a good job, since the main information it holds is connectivity.

For the general problem, one needs a few days if there is an easy solution in the internet, to a month only to realize that this kind of problem is very difficult algorithmically.

But even if something is difficult, the question is not mathematical but mostly a engineering problem. Can the current technology be sufficient for the specific problem.

2012/8/2 Jorge Timón <timon....@gmail.com>

[Jorge Timón]

I want to use ZMQ too. So versatile...

I think that it may be a mathematical problem too. Is a question of
complexity and big graphs.
I don't remember if it was you, but someone said something about
balls. Maybe doing something like that, grouping several nodes into a
"supernode" and dividing the problem in find a "path between
supernodes/balls" and then find "concrete paths within
supernodes/balls" in the "superpath".

I guess the grouping has its difficulties too, so maybe this technique
is not that useful. Just brainstorming...

About technollogy...there's graph algorithms implemented for GPGPU.
Not sure about openCL, but CUDA has this:
http://code.google.com/p/thrust-graph/
And there must be more things out there:
http://stackoverflow.com/questions/2431310/graph-algorithms-on-gpu

I thought that would be developed after a first basic prototype
implementing the protocol, but maybe you already want to play with
that. I like the multi-CPU ZMQ approach though.

[Walter]

> About sharing efforts...The current Ripple protocol design is pretty
> generic and extensible.
> Walter, have you considered using it as the base for IFEX ?
> I'm more convinced each day that the distributed ripple protocol will
> be the glue for all alternative currencies and payment systems to work
> together.

I still haven't had the time to go through the proposal in depth, unfortunately.

In general, however, I could ask some pointed questions - how does the
proposal solve the following issues...
- Integration with existing state-issued currencies
- Integration with financial networks (settlement time? settlement
cost? settlement guarantee? transaction reversals?)
- Currency exchange rate fluctuation
- Unreliable links
- The potential for network split
- Differing software versions
- General risk issues (Insurance? Reliability without formal
registration under existing banking legislation?)
- Trust
- "Bad" nodes working together to corrupt or break the network
- Recovery from catastrophic failure without centralisation, or, if
centralised (as LETS community models I have seen seem to be for
inter-community credit sharing), how is it different to existing
systems in terms of scope for abuse?
- Differences between assets that are consolidated (eg. Bitcoin's
consensus, shares on a stock market) vs. non-consolidated
(state-issued currencies in cash circulation, gold, etc.)
... and that's just a few.

Here's some specific feedback on the protocol proposal v0.6 @
http://ripple-project.org/Protocol/Protocol06
- SSL is not a great choice today for secure communications - see
http://www.youtube.com/watch?v=Z7Wl2FW2TcA for example.
- I have read that it is considered bad practice to mandate specific
cryptographic algorithms with protocols (Applied Cryptography?)
- It is not a good idea to have a flat error space (waiting_for....).
What you will wind up with is loads of crazy state-based logic. What
you need is grouping - general states, with more specific states as an
option.
- HTTP is perhaps a limiting option for a financial networking
protocol as it limits people - just as TCP does - to point-to-point
communications. Many financial networks require broadcast/multicast
distribution of data, particularly when operating at scale. In
addition, there is a certain degree of overhead in SSL and HTTP that
introduces latencies that may not be desirable in certain financial
networking scenarios.

Sorry that I don't have time to go through more carefully. I really
believe what Ripple is trying to achieve and IFEX are very similar,
though perhaps there is a broader perspective behind the IFEX ideas as
they stand presently (which isn't to devalue the Ripple work, simply
to point out the differing perspective/scope of requirements
considered).

> For the special case of chain currencies (bitcoin) in which the
> settlement could be atomic with the rest of the ripple transaction, I
> think another commit extension should be enough.

The term 'special case' is definitely NOT a good sign if you're
planning a system to be a universal/generic solution.

- Walter

[Apostolis Xekoukoulotakis]

Are there answers to those questions from IFEX?

I find all those questions very interesting.

Some of them though dont need to be solved by ripple due to its different scope.

Is there an implementation we could look?
Can you give us a simple example of an ifex network
in which you point out the differences with the current financial system?

Also, do you have a routing algorithm or method?
Will this be full blown p2p or will it be business2business p2p?

I am asking because I am interested, not to find out which is best, I think they have different scope but with many common to solve problems.

2012/8/3 Walter <walter....@gmail.com>

--
You received this message because you are subscribed to the Google Groups "Ripple Project" group.
To post to this group, send email to rippl...@googlegroups.com.
To unsubscribe from this group, send email to rippleusers...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/rippleusers?hl=en.

[Walter]

> Are there answers to those questions from IFEX?

- Integration with existing state-issued currencies

The present ideas with IFEX are basically attempting to remain
entirely commodity/currency neutral, so this concern doesn't really
apply.

- Integration with financial networks (settlement time? settlement
cost? settlement guarantee? transaction reversals?)

As above, to some extent.

The general idea right now with regards to the questions in brackets
is to consider them as properties of settlement paths and to be able
to describe them accurately as such, consider them, and use them where
appropriate.

- Currency exchange rate fluctuation

Left to individual nodes to resolve. Idea is that temporal
limitations on settlement quotations function as hard limits with
regards to the temporal risk of currency/commodity exchange.

- Unreliable links

Left to individual nodes to resolve, though the integration of
cryptography can function as a resolver of doubt with regards to
failed multi-hop transactions, as well for the allocation of blame
(using non-repudiation, a guarantee to perform a settlement within a
certain amount of time can be held up as evidence of breach of
contract).

- The potential for network split

No notion of centralization, therefore not relevant.

- Differing software versions

Not super clear as yet but it as research so far has uncovered very
heterogenous needs from different parts of current financial
networking community it seems that extreme minialism in the basic
protocol is required, and some form of extension/capability
negotiation would be in common use from the word go.

- General risk issues (Insurance? Reliability without formal
registration under existing banking legislation?)

Thoughts right now are that this is offloaded to individual nodes,
though can be expressed and shared through descriptive properties of
settlement quotations (ie. "i can do that within <x> time and will
sign off on the fact (cryptographically)" - later failure to comply
can be held up as evidence to affect shared trust models).

- Trust

Some networks need this formalized, others do not. It seems that for
many uses GPG-style chains of trust might not be a bad idea -
certainly well supported on all platforms, seemingly much stronger and
more flexible than SSL's X.509 CA-style approach.

- "Bad" nodes working together to corrupt or break the network

No "shared view" means individual nodes are responsible for their own
decisions. By thus eschewing specific algorithms for actual
settlement-related decision making to implementers (ie. not having it
as part of the protocol), to a large extent such vulnerabilities are
also pushed out of scope.

- Recovery from catastrophic failure without centralisation, or, if
centralised (as LETS community models I have seen seem to be for
inter-community credit sharing), how is it different to existing
systems in terms of scope for abuse?

Currency/commodity neutral, so not applicable. Each node is
responsible for taking care of its own security and availability.

- Differences between assets that are consolidated (eg. Bitcoin's
consensus, shares on a stock market) vs. non-consolidated
(state-issued currencies in cash circulation, gold, etc.)

Entirely currency/commodity neutral. Consolidated commodities would
simply have different settlement paths that moved through the central
point of reference (eg. Bitcoin's blockchain-based consensus, a
consolidated stock on a market, etc.).

> Some of them though dont need to be solved by ripple due to its different
> scope.

My concern would be that it is impossible to avoid the key question of
how to make something relevant to the average person. The average
person cannot be asked to completely leave state-issued currencies,
since they tend to want goods/services that can only be acquired at
present using said currencies. (David's book highlights taxation as a
traditional means to force currency adoption.)

> Is there an implementation we could look?

Nope, but perhaps not far off.

Right now I've been busy with some commercial implementation related
to but not directly based upon IFEX.

Once that is complete, perhaps it will be interesting.

> Can you give us a simple example of an ifex network
> in which you point out the differences with the current financial system?

Please see the links in the 'Why IFEX?' box at http://www.ifex-project.org/

Basically points like:
- arbitrary currency/commodity support
- arbitrary settlement network support
- removes false barriers to innovation
- vastly simpler than protocols in broad use in present-era financial
networking
- does not mandate any particular approach
- supports arbitrary topologies

And the most important one:
- hopes to allow emerging digital currency based financial service
and settlement providers to compete with conventional financial world
on an equal footing, where they can begin to usurp the latter on the
basis of objectively measurable superior qualities (of speed, reach,
transaction fees, etc.)

Note that IFEX doesn't try to force any value judgements like "you
should value community and sustainability over cold hard fiat-cash"
(though I certainly don't think this would be bad advice for the world
at large!), so is perhaps more palatable to the general population.

> Also, do you have a routing algorithm or method?

The current description is based fuzzily on the notion that each node
makes its own decisions, so there is no need for an overall algorithm.

> Will this be full blown p2p or will it be business2business p2p?

There is no distinction between nodes. Any node can do anything.

Just as a bank could say "if you give me $<x> now, I will give you
$<y> in 12 months", so too could your cousin Larry.

Part of the issue here is obviously trust and reliability, and perhaps
GPG-based trust networks, nonrepudiation, and highly descriptive and
objective quotations (ie. absent the vague legalese in current public
financial services networks, which gets even worse when you cross
borders) can solve this issue.

- Walter

[Jorge Timón]

On 8/3/12, Walter <walter....@gmail.com> wrote:
>> Are there answers to those questions from IFEX?
>

> - Integration with existing state-issued currencies
>

> The present ideas with IFEX are basically attempting to remain
> entirely commodity/currency neutral, so this concern doesn't really
> apply.

Ripple IOUs can represent anything, including any national currency.
Different issuers would "mint" promises of those intruments

> - Integration with financial networks (settlement time? settlement
> cost? settlement guarantee? transaction reversals?)
>

> As above, to some extent.
>
> The general idea right now with regards to the questions in brackets
> is to consider them as properties of settlement paths and to be able
> to describe them accurately as such, consider them, and use them where
> appropriate.

The settlement would necessarily be out of the protocol, but the IOUs
could be binded to legal contracts. This extension is really simple,
just like independent companies certify digital signatures, they could
bind ripple keypairs to contracts.

> - Currency exchange rate fluctuation
>

> Left to individual nodes to resolve. Idea is that temporal
> limitations on settlement quotations function as hard limits with
> regards to the temporal risk of currency/commodity exchange.

Complete freedom in exchange rates in the current design.

> - Unreliable links
>
> Left to individual nodes to resolve, though the integration of
> cryptography can function as a resolver of doubt with regards to
> failed multi-hop transactions, as well for the allocation of blame
> (using non-repudiation, a guarantee to perform a settlement within a
> certain amount of time can be held up as evidence of breach of
> contract).

The non repudation is based on cryptography. Not sure if this solves
your concerns.

> - The potential for network split
>

> No notion of centralization, therefore not relevant.

No notion of centralization in the Ripple protocol neither.

> - Differing software versions
>
> Not super clear as yet but it as research so far has uncovered very
> heterogenous needs from different parts of current financial
> networking community it seems that extreme minialism in the basic
> protocol is required, and some form of extension/capability
> negotiation would be in common use from the word go.

The protocol is extensible. You don't need to change the core protocol
to extend it.

> - General risk issues (Insurance? Reliability without formal
> registration under existing banking legislation?)
>

> Thoughts right now are that this is offloaded to individual nodes,
> though can be expressed and shared through descriptive properties of
> settlement quotations (ie. "i can do that within <x> time and will
> sign off on the fact (cryptographically)" - later failure to comply
> can be held up as evidence to affect shared trust models).

As said, Ripple IOUs can represent legal contracts, including future
contracts for risk management. I guess the interested actors would
need to create an "specialized market" for those.

> - Trust
>
> Some networks need this formalized, others do not. It seems that for
> many uses GPG-style chains of trust might not be a bad idea -
> certainly well supported on all platforms, seemingly much stronger and
> more flexible than SSL's X.509 CA-style approach.

Ripple is based on trust between actors specified explicitly by
accepting a given currency/IOU. GPG-style web of trust would be out of
the core protocol, but again, an extension could solve these issue. I
don't really know how would they should do that though, because I
don't know what they want to acomplish.

> - "Bad" nodes working together to corrupt or break the network
>

> No "shared view" means individual nodes are responsible for their own
> decisions. By thus eschewing specific algorithms for actual
> settlement-related decision making to implementers (ie. not having it
> as part of the protocol), to a large extent such vulnerabilities are
> also pushed out of scope.

Here too. Individuals are responsible for their decisions.

> - Recovery from catastrophic failure without centralisation, or, if
> centralised (as LETS community models I have seen seem to be for
> inter-community credit sharing), how is it different to existing
> systems in terms of scope for abuse?
>

> Currency/commodity neutral, so not applicable. Each node is
> responsible for taking care of its own security and availability.

The same.

> - Differences between assets that are consolidated (eg. Bitcoin's
> consensus, shares on a stock market) vs. non-consolidated
> (state-issued currencies in cash circulation, gold, etc.)
>

> Entirely currency/commodity neutral. Consolidated commodities would
> simply have different settlement paths that moved through the central
> point of reference (eg. Bitcoin's blockchain-based consensus, a
> consolidated stock on a market, etc.).

I don't understand how stocks and chain currencies are comparable.
This touches my "special case". I agree that special cases should be
avoided but chain currencies are certainly an exception, they're the
only real form of digital cash. Which means the settlement could be
atomic within a Ripple transaction.
Without any extension for this, bitcoin settlements must be made
outside of the transaction. You would just not use the advantage of a
unique superiority.

>> Some of them though dont need to be solved by ripple due to its different
>> scope.
>
> My concern would be that it is impossible to avoid the key question of
> how to make something relevant to the average person. The average
> person cannot be asked to completely leave state-issued currencies,
> since they tend to want goods/services that can only be acquired at
> present using said currencies. (David's book highlights taxation as a
> traditional means to force currency adoption.)

Ripple suports national currencies. If users recycle keypairs enough,
it can be as untraceable as Open Transaction's so called untraceable
"cash", which are really IOUs from the minter.

> Here's some specific feedback on the protocol proposal v0.6 @
> http://ripple-project.org/Protocol/Protocol06
> - SSL is not a great choice today for secure communications - see
> http://www.youtube.com/watch?v=Z7Wl2FW2TcA for example.

Not an expert in network security, but I would prefer to leave the
transport out of the protocol. This way we could use Tor, for example.

> - I have read that it is considered bad practice to mandate specific
> cryptographic algorithms with protocols (Applied Cryptography?)

You're probably right. I would prefer to only specify them as Public
key cryptography, but I don't think this is a big deal. A change from
one algorithm to another sholdn't be that hard. We have to be aware
that it will happen though.

> - It is not a good idea to have a flat error space (waiting_for....).
> What you will wind up with is loads of crazy state-based logic. What
> you need is grouping - general states, with more specific states as an
> option.

I guess Ryan has to anwer to this one.

> - HTTP is perhaps a limiting option for a financial networking
> protocol as it limits people - just as TCP does - to point-to-point
> communications. Many financial networks require broadcast/multicast
> distribution of data, particularly when operating at scale. In
> addition, there is a certain degree of overhead in SSL and HTTP that
> introduces latencies that may not be desirable in certain financial
> networking scenarios.

I would prefer just JSON (or protocol Buffers, I don't care) and ZMQ.
Anyway most of the design is based on JSON.

> Sorry that I don't have time to go through more carefully. I really
> believe what Ripple is trying to achieve and IFEX are very similar,
> though perhaps there is a broader perspective behind the IFEX ideas as
> they stand presently (which isn't to devalue the Ripple work, simply
> to point out the differing perspective/scope of requirements
> considered).

Maybe we should talk about this in another thread. But if you make an
example with all the complexities you're concerned with, I bet I can
model the example with the Ripple concept. I've said a few times that
Ripple is a universal model for mutual credit. Now I believe that is a
universal model for monies in general. You can explain any form of
money by drawing a Ripple-like graph.

>> For the special case of chain currencies (bitcoin) in which the
>> settlement could be atomic with the rest of the ripple transaction, I
>> think another commit extension should be enough.
>
> The term 'special case' is definitely NOT a good sign if you're
> planning a system to be a universal/generic solution.

I know, but this is really a special case as I said above.