Ripple's settlement algorithm, compared to Favorati

[Martin Brock]

I wish to discuss possible differences between Favorati and Ripple.
The discussion involves technical details that will interest few
people other than Ryan, and Ryan thus far hasn't responded to an
email. He has worked on this project for many years, so it can't
always have his attention. If anyone knows Ryan personally, I'll
appreciate an introduction. This wiki is my only other prospect, so
here goes.

First, I'll introduce some nomenclature that Ripple doesn't use.

At Favorati, "respect" is the inverse of "trust". If you trust me,
then I respect you or owe you respect, i.e. I owe you a favor. I have
trust, and you have respect. When you have respect, you may spend it.

The respect you may spend with me has four forms, 1) respect that I
owe you directly, 2) respect that I owe you indirectly, 3) respect
that others owe you and 4) your self-respect.

1) If you do me a favor, I owe you a favor in return. You have my
direct respect. When you spend this respect by accepting a favor from
me, I return your favor; therefore, my obligation to you decreases,
and you do not owe a favor as a consequence.

2) If I respect someone (who respects someone who respects
someone ...) who respects you, I respect you indirectly. You have my
indirect respect. You may trigger a chain of settlements by asking
your respectors (to ask their respectors ...) to ask me to do you a
favor. You do not owe a favor in return, and everyone in the chain
reduces an obligation to someone in the chain.

3) A mutual friend owes you a favor, and I prefer the friend's respect
to yours. You ask your friend to respect me instead of you, and I do
you a favor. You do not owe me a favor in return. The friend no longer
owes you a favor. The friend owes me a favor instead.

4) You spend your self-respect when I do you a favor and you owe me a
favor in return.


1) and 2) decrease the total respect in the system (the "money
supply"). 3) does not change total respect. 4) increases total
respect.


With this introduction, I can describe Favorati's settlement
algorithm.

Mary wants a $10 favor from Luke.

1) Spend Luke's direct and indirect respect for Mary. Spend less
recent respect before spending more recent respect. The calculation of
indirect respect is recursive. The recursive procedure follows spends
less recent respect first at each level. The procedure potentially
searches the entire network, but if the server caches the network in
RAM, this search is not a problem. The algorithm is O(n) or
thereabouts, so a dedicated server can search millions of
relationships in seconds.

2) If 1) is less than $10, transfer Mary's respect to Luke,
transferring stronger respect before transferring weaker respect.

A friend's respect for Mary is "stronger" (from Luke's perspective) if
Luke's willingness to increase his trust for the friend is greater.
Luke expresses this willingness in a trust policy recorded at
Favorati.net. If Luke is unwilling to accept Mary's respect, no
transfer occurs.

Unlike 1), Favorati does not "ripple" transfers of respect, i.e. if
Paul owes Peter and Peter owes Mary, Favorati does not transfer Paul's
respect for Peter to Luke. Automatic settlement only transfers Peter's
direct respect for Mary.

Indirect transfers could increase Mary's spendable respect and also be
preferable to Luke if Luke trusts Paul more than Peter; however, an
indirect transfer could create a circuit in the trust network, and the
settle algorithm assumes no circuits. I'd like to ripple here, but at
this point, I need an algorithm that cannot create a circuit, and I
haven't thought enough about it. Avoiding circuits when the network is
decentralized is also a problem.

3) If 1) + 2) is less than $10,
Mary owes Luke the balance, i.e. she spends her self-respect and thus
owes Luke a favor in return. Luke's trust policy must permit it.


I can now discuss possible differences between Ripple and Favorati.

In 1), Ripple's order of path traversals could differ. Ripple could
use an order other than least recent first.

In 2), Ripple's order of transfers could differ.

In 2), Ripple could ripple transfers.


I haven't read Ripple's code yet, but the wiki discusses two
transaction algorithms, a naive approach and a more sophisticated
approach.

http://ripple-project.org/Implementation/Transactions

Presumably, the wiki refers to the ripple in 1), since it refers to a
target. A ripple in 2) has no specific target. It seeks Mary's respect
from any member in Luke's trust policy. Both algorithms differ from
the approach in 1).

The naive approach uses the shortest path from Luke to Mary, followed
by the next shortest path and so on. In general, this approach is
computationally intractable. The shortest path problem has an
efficient solution, but finding paths in order by length does not. The
longest path problem is NPC.

http://en.wikipedia.org/wiki/Longest_path_problem

Also, I'm not sure what the wiki means by "shortest". Apparently,
based on the more sophisticated approach, "shortest" refers to
geographical distance between members, and the shortest path algorithm
uses a heuristic, i.e. it orders nodes at each level by distance to
Mary as the crow flies. I'm a GIS guy in my day job, and I've used
this heuristic in an implementation of Dijkstra's shortest path
algorithm in other contexts; however, Favorati's settlement algorithm
does not seek a shortest path.

I don't fully understand the more sophisticated approach; however,
minimizing geographic path length or distance to the target in 1)
confuses me generally. This approach seems to consume more local
respect first, leaving more distant respect. If the wiki refers to a
ripple in 2), minimizing geographic distance makes more sense, since
the algorithm then transfers more local respect to Luke before
transferring more remote respect.

If anyone got this far, you have my respect.

[Martin Brock]

I'd also like to discuss exchange rates between different standards of
value (currencies). First, here's a little history.

When I started Favorati, the site used only one standard of value,
common labor. Sometime last year, I started showing the site to mostly
libertarian friends at freebanking.org and received lukewarm response,
apparently because the "mutualist" label and common labor as a
standard turns them off. I accept the label myself, but it strikes
some libertarians as too "left wing". The site should encourage
mutually beneficial commerce, so I don't want to alienate anyone with
political labels, and I also want to demonstrate the feasibility of
multiple, competing standards of value.

So I decided to support multiple standards and exchange rates. This
change wasn't easy, and I've only recently begun to feel that I have
it "right". At Favorati, a member specifies a standard of value
(essentially a currency) when joining, and he also specifies rates of
exchange between his standard and other standards. Each member
promises only his own standard of value, but a member may accept any
standard.

Currently, the site supports four standards, common labor, gold,
silver and U.S. dollars. Adding another standard is trivial. I'm
thinking of adding bitcoin and some sort of food standard. I'm not a
fan of bitcoin as a standard of value for extending credit myself, but
the currency generates a lot of buzz, and the site could demonstrate
the weakness of a standard like bitcoin compared with a standard like
common labor or a standard basket of food. Bitcoins are hoarded even
more easily than gold, and we've already seen the consequent price
volatility in dollar markets. Bitcoin bubbles are now an empirical
fact.

When a member posts an offer at Favorati, he specifies a value (a
price) in his standard of value, and when he views another member's
offer, he also sees the price in his standard, using the other
member's exchange rate. For most purposes, a member may assume that
everyone else uses his standard of value; however, if a member expects
a friend to return a favor by returning the standard, he must accept
the friend's standard not his own. This "payment in cash" is the last
resort option for settlement, and ideally it occurs rarely.
Ordinarily, settlement occurs by rippling.

I can now discuss possible differences with Ripple.

I joined Villages recently, and when I joined, I did not specify a
standard of value or exchange rates. Presumably, a member may specify
any currency each time he posts an offer. This approach is very
flexible, but it could be an accounting nightmare if a member owes and
is owed many different currencies. Favorati tries to solve this
problem by allowing each member to view the market only through a
single, preferred standard of value.

Also, when I joined, I didn't specify exchange rates, so settlement
(rippling) presumably uses exchange rates shared by all members. If
so, these exchange rates must emerge in some market other than
Villages. If all members share exchange rates, the settlement
algorithm is much simpler, because it need not determine whose
exchange rate to use at step in a ripple; however, this approach
overrides individual choice and concedes the authority of an external
market. At Favorati, an individual member decides how much he values a
standard, like gold or common labor. If another member disagrees with
him sufficiently, he doesn't deal with the other member in that
standard. He either doesn't see the other member's offer or he sees a
very high prices in his own standard that he will not accept.

Later, I'll discuss how Favorati's settlement determines whose
exchange rate to use at each step in a ripple.

[Ryan Fugger]

On Sun, Jan 15, 2012 at 8:08 AM, Martin Brock <reston...@gmail.com> wrote:
> Unlike 1), Favorati does not "ripple" transfers of respect, i.e. if
> Paul owes Peter and Peter owes Mary, Favorati does not transfer Paul's
> respect for Peter to Luke. Automatic settlement only transfers Peter's
> direct respect for Mary.
>
> Indirect transfers could increase Mary's spendable respect and also be
> preferable to Luke if Luke trusts Paul more than Peter; however, an
> indirect transfer could create a circuit in the trust network, and the
> settle algorithm assumes no circuits. I'd like to ripple here, but at
> this point, I need an algorithm that cannot create a circuit, and I
> haven't thought enough about it. Avoiding circuits when the network is
> decentralized is also a problem.
>

No circuits are created if you always prefer to spend existing
balances/respect before issuing new balances/respect. This is how
Villages does it. (It also prefers to spend balances that are higher
relative to the corresponding credit limit than those that are lower.)

In Ripplepay, and in the distributed protocol and Ripple generally,
circuits aren't too big a deal, because regardless of the path taken
by a transfer, the same transfers are possible in the network
afterwards. In other words, circuits don't clog the network.

In general, finding a Ripple payment path is a min-cost flow problem:

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

The cost of using a path can be defined in terms of exchange rates,
balance to credit limit ratio, spending existing credit vs. issuing
new credit, number of hops, or anything really.

Ryan

[Ryan Fugger]

On Mon, Jan 16, 2012 at 7:46 AM, Martin Brock <reston...@gmail.com> wrote:
> I joined Villages recently, and when I joined, I did not specify a
> standard of value or exchange rates. Presumably, a member may specify
> any currency each time he posts an offer. This approach is very
> flexible, but it could be an accounting nightmare if a member owes and
> is owed many different currencies. Favorati tries to solve this
> problem by allowing each member to view the market only through a
> single, preferred standard of value.
>

Villages accounts only have a single standard of value for simplicity:
hours of unskilled labour. So there are no exchange rates in
Villages.

> Also, when I joined, I didn't specify exchange rates, so settlement
> (rippling) presumably uses exchange rates shared by all members. If
> so, these exchange rates must emerge in some market other than
> Villages. If all members share exchange rates, the settlement
> algorithm is much simpler, because it need not determine whose
> exchange rate to use at step in a ripple; however, this approach
> overrides individual choice and concedes the authority of an external
> market. At Favorati, an individual member decides how much he values a
> standard, like gold or common labor. If another member disagrees with
> him sufficiently, he doesn't deal with the other member in that
> standard. He either doesn't see the other member's offer or he sees a
> very high prices in his own standard that he will not accept.
>

In Ripplepay, the system determines exchange rates from global
currency markets. It is impossible to exchange between dollars and
hours, but everything else has an exchange rate to and from dollars,
so is inter-convertible. I chose to use global exchange rates so
users didn't have to continually update their exchange rates as
standards of value varied in relation to each other over time.

The distributed protocol, and Ripple generally, are compatible with
any way that servers wish to allow users to set their exchange rates,
including specifying custom ones as in Favorati. I have this as a
proposed feature for a future version of Ripplepay, although I haven't
had a lot of demand for it really.

> Later, I'll discuss how Favorati's settlement determines whose
> exchange rate to use at each step in a ripple.
>

I would be interested in hearing that, and if you have considered
using a min-cost flow algorithm...

Ryan

[Martin Brock]

> In Ripplepay, the system determines exchange rates from global
> currency markets. It is impossible to exchange between dollars and
> hours, but everything else has an exchange rate to and from dollars,
> so is inter-convertible. I chose to use global exchange rates so
> users didn't have to continually update their exchange rates as
> standards of value varied in relation to each other over time.

At Favorati, doing a favor is a demand deposit, unless the terms of an
offer specify otherwise. All debts are payable "in cash" on demand.
"In cash" refers to a member's chosen standard. If my standard is
silver, I always owe silver, so I may only deal with people accepting
silver. A member owes his own standard but may accept any standard,
thus the exchange rates.

Ideally, members leave "cash in the bank", i.e. they wait for an offer
they can accept and then settle by rippling. At some point, I hope to
implement installment payments and possibly some sort of default
insurance. Default insurance is very questionable, but people have
come to expect it.

Although I accept the "mutualist" label, I also accept the subjective
theory of value, so each member determines the value of goods,
including standards he will accept, subjectively. A member may value a
particular standard more or less than other members, regardless of the
market rate of exchange. A change in the last rate at which an
exchange occurs doesn't necessarily signal a change in an individual's
preference.

Varying exchange rates create an arbitrage opportunity, but this fact
doesn't bother me. If gold is my standard, people coveting gold could
accumulate my obligations from people with different exchange rates in
order to demand payment in gold from me, but people desiring a gold
standard should understand this process. I prefer common labor as a
standard for reasons that would eventually become apparent to people
choosing gold.

> I would be interested in hearing that, and if you have considered
> using a min-cost flow algorithm...

I haven't thought about min-cost flow per se. Trust isn't exactly a
flow, i.e. people can trust me more than I trust other people, but I
think I know what you have in mind.

I added an illustration with multiple standards to Favorati.net. The
same example is illustrated directly above it using a single standard.

Luke's standard is gold, and he owes 1.25 grams of gold to Paul.
Paul's standard is dollars, and he owes $30 to Peter.
Peter's standard is silver, and he owes 1 ounce of silver to Mary.

Peter will exchange an ounce of silver for $40.
Paul will exchange $50 for a gram of gold.
Luke will exchange a gram of gold for five hours of common labor.

Mary's standard is common labor. How much common labor does Luke owe
her?

Peter will exchange an ounce of silver for $40.00, so he will exchange
his obligation to Mary for a $40 reduction in Paul's obligation to
him. Paul owes Peter only $30, so the "flow" from Peter to Paul in
this ripple is the smaller of $30 and $40.

Paul will exchange $30 for 0.6 grams of gold, so he will exchange his
$30 obligation to Peter for a 0.6 gram reduction in Luke's obligation
to him. 0.6 is the smaller of Paul's obligation to Peter, converted to
gold using Paul's exchange rate, and Luke's obligation to Paul in
gold.

Finally, Luke will exchange 0.6 grams of gold for 3 hours of common
labor, so Mary may expect Luke to accept this quantity of her standard
in exchange for the obligation that Luke owes her indirectly.

Discussing the settlement algorithm here has driven me to ponder it
again, at least. I realize now that a ripple in step 2) above cannot
add a circuit to the network, so I've implemented this ripple, i.e. if
Paul owes Peter and Peter owes Mary and Luke trusts Paul (with a
credit limit), then Mary may "spend" Paul's indirect respect in a
transaction with Luke. My strategy in this ripple is to maximize the
trustworthiness of respect transferred to Luke in terms of Luke's
trust policy, so if Peter is closer to his credit limit than Paul,
Luke acquire's Paul's respect before Peter's.