Protocol01

Ripple uses the Metropolis-Hastings algorithm for routing, as described in Clarke and Sandberg's presentation [[Routing in the Dark -> https://freenetproject.org/papers/vegas1_dc.pdf]] (PDF). 

  * "on-demand", "payable at end of month", "payable in 90 days", etc. as suffixes on regular units become different different units, stored on separate accounts
  * units definition must show how to do conversion to other units (present value calculation = defacto interest)

  * put account contracts in account creation messages, including units definition
  * have a units-udpate message that can hold custom fields for sharing units state (such as current interest rate)?

* link-state routing!
  * introduce a host-level connection for transmitting routing data, timing/heartbeat messages

If a node wishes to increase its partner's or its own credit limit, it sends a @@limit-request@@ message containing:

In the case of wishing to increase one's partner's credit limit, the request is interpreted as an offer.

The change is considered pending until the requesting node receives back a @@limit@@ message containing the same information as the @@limit-request@@, plus:

* a reference to the ID of the original @@limit-request@@ message

If a @@limit-reject@@ is received with the same account ID and reference to the request ID, then the credit change has been rejected.  The rejecting node may of course propose a different limit it considers appropriate by sending its own limit-request message anew.

If a node wishes to decrease either limit, it sends a @@limit@@ message, which is implemented immediately upon acknowledgment.  In this case, the request ID field is not required.  A node may not reject a decreased limit.

A node may cancel a limit request by responding to a limit acceptance message with a "request withdrawn" error.

%center%''by Ryan Fugger''

'''Contributors'''

* Brandyn Webb
* Evgeni Pandurski
* Matthew Toseland
* Jiri Baum

* alternative forking formula: minimize [sum over all forks(query amount * distance to target)] * # of forks

The recipient's receipt deadline to the payer should be well before the penalty deadline on any promise received.  Therefore, the recipient should wait until it has received promises equal to the entire payment amount before sending back any promises-received to the payer.

The recipient can cancel the transaction at any time by sending the payer a @@payment-cancel@@ and releasing its neighbours from their promises with a @@path-cancel@@ (see [[Cancelling Unneeded Paths -> #cancelling-paths]]).  The payer can cancel the transaction by sending the recipient a @@payment-cancel@@, informing it that it can release its neighbours from their promises.  Released promises should be propagated back down each payment path to free up those funds for other payments.

A node may release a neighbour from all or part of its promise at any time with a signed @@path-cancel@@ message:

* error codes

* per-hop fee-based routing spaces?
* weight location swap calculations by accounts' credit range to put more emphasis on high-capacity accounts?

  * Path Queries & Responses

  * Making Promises (Commit-Request)
  * Cancelling Unneeded Paths

* Initializing payment between the payer and recipient nodes

The authorization number field may be used to contain a single-use password to pre-authorize payments, so the node can automatically make payments when it receives a request containing a password from a pre-determined list that it holds.  The payment-request message may also be authorized by signing it with a certain key, contained in the node owner's smart card, for example, for point-of-sale scenarios.

'''Initializing Payment'''

The payer node contacts recipient node and communicates the following in a @@payment-init@@ message:

* payer's routing information

Transaction units allow the payer to mask the true units of the payment by inventing custom units.  However, this will hinder intermediaries' ability to properly conduct zero-fee path searches.  To guarantee overall fee limits on paths, transaction units must be recognizable to the intermediaries.  See [[Path Queries -> #path-queries]].

* payment amount in transaction units

Otherwise the recipient rejects the payment initiation with an error code.

'''Path Queries & Responses'''

The payer and recipient send out @@path-query@@ messages to one or more account partners, which they in turn pass on to one or more of their partners as described in [[Query Routing -> #query-routing]].  A path-query message consists of:

* swarm ID
* path ID
* direction of query, forward or backward, depending on whether query originates at payer or recipient
* transaction units
* credit available along this path so far, in transaction units

* credit available along path so far, in account units for that account (defines a conversion rate from transaction units to account units)

* the time this available credit guarantee will expire, measured in connection time between sender and recipient
* promise penalty deadline (forward: maximum offered; backward: minimum required)
* promise daily penalty rate (forward: maximum offered; backward: minimum required)
* promise final deadline (forward: maximum offered; backward: minimum required)
* the remaining hop limit for the query
* a bloom filter containing aliases for each of the locations visited on this paths

* the accumulated fee limit for this query (as a percentage of the query amount)

Final payment will be made using the paths found by queries within a single swarm.  Therefore, queries within a single swarm may not reserve the same credit.  Queries within different swarms, but with the same payment ID, may reserve the same credit.  Queries with different payment IDs may not reserve the same credit.  When a query forks in two separate directions, it splits into two different paths, but each maintain the same swarm ID.  To avoid overlap, payer-initiated (forward) queries should use even-numbered swarm IDs, and recipient-initiated (backward) queries odd-numbered swarm IDs.  See [[Query Routing -> #query-routing]]. 

The payer sends out "forward" queries, and the recipient sends out "backward" queries, refering to the direction the payment will ultimately take.  If fees are permitted, the backward queries are more precise:  the payment amount is generally interpreted as the amount to be received by the recipient (Paypal notwithstanding), and the backward queries begin by specifying this amount and accumulate fees as they propagate towards the payer.  Forward queries that permit fees must begin with an estimate of the payment amount including intermediary fees, which would generally be too high and result in too much credit being reserved.  However, forward queries play an important role as signposts towards the payer for the more-precise backward queries.

The transaction units allow the payer and recipient to recognize what percentage of the payment is actually being paid and received down a given path, regardless of fees or varying conversion rates between account units along the path.  For example, suppose node A is paying node C $100 through intermediary node B.  A's account with B may be in Euros, and B's account with C may be in Pounds.  Before paying 82 Euros to B, A must know how many dollars that represents to recipient C.  Intermediaries that do not recognize the transaction units cannot enforce overall fee limits on queries.

The account ID changes with each step the query is forwarded along, and lets the query recipient know which account with the sender is intended as part of the path, if there is more than one.  The amount in account units is the amount that is to be reserved on that account for this query's payment path.  It also defines a conversion rate between account units and transaction units that can be used to calculate whether or not the full query amount can be passed on to a single neighbour, and what proportion to pass on to various neighbours otherwise.  This conversion rate is also used in subsequent payment messages.

The target location is used by each intermediary to route the query.  Generally the target for forward queries is the recipient's location, and the target for backward queries is the payer's location, but this is not strictly required.  Either payer or recipient may direct the other to route their queries to a different target location, and then ensure that the node with this target location receives a query from the opposite direction to point back to the correct target.

The credit guarantee expiry time gives a deadline for the next phase of the payment to occur.  If this time limit is reached, the credit held for this path will be released and made available to other payments.  Each intermediary should subtract from this time before passing it on to give themselves a small buffer in which to process messages from the next payment phase.  The time is given in the connection time between each of the intermediaries, so each one must convert if the time on the incoming account is not in sync with the time on the outgoing account.  See [[Connection Time -> #connection-time]].

The promise penalty deadline, penalty rate, and final deadline refer to fields in the @@promise@@ message in the next payment phase.  In the forward query, they represent maximum bounds for those fields, and in the backward query, minimum bounds.  The times are again given in connection time, and the penalty rate is a daily percentage.

The hop limit is the maximum number of hops for all queries spawned from the one received, including forks.  When a query forks in several different directions, the hop limit must be divided up amongst them.

The bloom filter containing aliases of the locations already visited is to prevent loops -- no location should occur twice in the same path.  Nodes can use any alias they want as long as it is unique among potential intermediaries with high probability and they remember it to compare against incoming queries with the same payment and swarm IDs.

The per-hop fee limit is a limit on the percentage fee charged per hop in the path.  The accumulated fee limit is an overall limit to the fees on this query.  This can only be enforced if intermediaries recognize the transaction units.

When the query reaches the opposing payment endpoint, or creates a loop or otherwise hits a dead end, the node receiving the query message returns a @@path-response@@ message:

Fees charged may be integrated as a percentage into conversion rates between units.  There is no provision for flat fees at the moment.  Minimum fees for any payment through an account are shared with account partners as part of the account data.

Each node partitions its accounts into separate routing classes such that obligations are convertible between any accounts within a class (in other words, an incoming payment on any account might be routed out along any other account in its routing class).  Each routing class is then given a location, which is a decimal number between 0 and 1 representing a position on the boundary of a circle.  The distance between any two locations is defined as the distance along the boundary of the circle between their locations:

A @@path-query@@ is routed first in directions path-queries in the opposite direction were received for the same payment ID.  From among these directions, the neighbour with the location closest to the query's target location is chosen first.  If there is not enough credit, as determined by available credit specified on the opposing query received from that direction, to fulfill the entire query, new queries with new path IDs are forked off in subsequent directions which have received opposing queries.  Path IDs must be unique within a swarm.  Once directions having received opposing path-queries are used up, all the accounts in the routing class may be considered on the basis of distance to the target location, using available credit as determined by the account balances and limits.

Remember that credit amounts reported as available on queries must be held for that path and made unavailable for other payments until they time out.  Only other swarms from the same payment may access amounts held.

At all times, per-hop fee limits must be obeyed.  If a node would charge more than the per-hop fee limit, it must respond as though it were a dead end.  An account with a minimum fee on through payments higher than the per-hop fee limit on the query should therefore be ignored for the purposes of routing that query.

Note that with Metropolis-Hastings routing there is no requirement for nodes to report their own exact location as the routing target of messages from transaction partners.  They may report slightly inexact locations for privacy reasons, or the location of a neighbour, or an average of a group of neighbours to route the message through them.  This requires informing those neighbours ahead of time that the message is coming, by sending a @@path-query@@.

When the payer has found payment paths with enough combined available credit to complete the payment, it sends a @@promise message@@ to the first node on each path, representing its commitment to redeem a valid receipt that can be authenticated with the promise's authentication key up to the amount of credit indicated on the receipt, if presented before the stated deadline.  A promise renews the credit held for each path and gives a new deadline for the expiry of these holds.

* swarm ID
* path ID

* amount to be held for payment, in account units, according to conversion rate defined by neighbour in @@path-query@@ message
* promise penalty deadline
* daily penalty rate if receipt or path-cancel not received before the penalty deadline
* promise final deadline, after which promise expires

Each node passes the promise message on to the next node in the path, as determined by @@path-response@@s received in the previous phase.  At each step, the promise message is signed to the next node by the passing node's authentication key.  This serves to establish the integrity and non-repudiability of the promise.

The recipient can cancel the transaction at any time by informing the payer and releasing its neighbours from their promises with a @@path-cancel@@.  The payer can cancel the transaction by informing the recipient that it can release its neighbours from their promises.  Released promises should be propagated back down each payment path to free up those funds for other payments.

%center%''with contributions by Brandyn Webb, Evgeni Pandurski, and Matthew Toseland''

* separate routing spaces for:
  * convertible accounts
  * zero-fee account pairs
  * sub-0.1% fee pairs
  * sub-1.0% fee pairs
* path-cancel messages to release amounts frozen in path-available
* weight location swap calculations by accounts' credit range to put more emphasis on high-capacity accounts

* transaction units
* payment amount in transaction units

Transaction units allow the payer to mask the true units of the payment by inventing custom units.  However, this will hinder intermediaries' ability to properly conduct zero-fee path searched.  To guarantee zero-fee paths only, transaction units must be recognized by at least some of the intermediaries.  See [[Path Queries -> #path-queries]].

The payer sends out @@path-query@@ messages to one or more of their account partners, which they in turn pass on to one or more of their partners as described in [[Query Routing -> #query-routing]].  A path-query message consists of:

* query ID
* subquery ID
* credit available along this sub-query path so far, in transaction units

* the remaining visited-nodes limit
* the original proximity-aware hop limit
* the remaining proximity-aware hop limit
* the closest distance to the target so far on this sub-query
* a bloom filter containing aliases for each of the nodes visited by this subquery
* the per-hop fee limit for this query (as a percentage of the query amount)

The subquery ID is to distinguish between forked subpaths of the query.  The credit available along the path so far is to help route the query by preferring accounts that have that amount of available credit.  The visited-nodes limit is a cap on the nodes visited for this query ID.  The proximity-aware hop limit is only decremented when the subquery moves away from its target.  Whenever the subquery gets closer to its target, the hop limit is reset to its original setting.  The bloom filter of visited nodes is for detecting loops.

If the payer wishes to guarantee a per-hop fee limit of zero, it must specify transaction units that are known to most if not all of the intermediaries, so they can manage exchange rate differences between them.  Otherwise these might become de facto fees.

* decrement the remaining visited-nodes limit and assign that neighbour a proportion of it
* decrement or reset the hop limit
* put an alias it can remember into the visited-nodes bloom filter

* credit currently available for this payment on this account, in account units
* credit currently available for this payment on this account, in transaction units (defines conversion rate to transaction units)
* the time this available credit guarantee will expire

* the target's routing information (optional)
* the remaining visited-nodes limit (optional)
* the original proximity-aware hop limit (optional)
* the remaining proximity-aware hop limit (optional)
* the closest distance to the target so far on this sub-query (optional)
* a bloom filter containing aliases for each of the nodes visited by this subpath
* per-hop fee limit

The optional entries do not apply when following a query path back to the payer.

Path-available messages are routed just like queries (see [[Query Routing -> #query-routing]] below), except they are headed in the other direction.  They also act as an available credit guarantee for a certain period of time.  If no promise message is received by then, the frozen credit can be released.  For each neighbour it is passing a path-available message on to, a node should:

* decrement the remaining visited-nodes limit and assign that neighbour a proportion of it
* decrement or reset the hop limit
* put an alias it can remember into the visited-nodes bloom filter

to one of its neighbours, chosen randomly.  That neighbour passes it on randomly, decrementing the TTL by one.  When a node receives a @@swap-init@@ with a hop limit of one, it has been selected as a potential swap partner.  If the swap partner is not currently participating in another swap, it responds with a @@swap-accept@@, containing:

This is passed back to the swap initiator along the path followed by the @@swap-init@@.  If the swap partner is currently participating in a swap, then it replies with a @@swap-reject@@, and the previous intermediary tries another direction.

  * requires accounts to specify lowest fee charged on through-payments
* mechanism to limit messages per unit time per connection

Each node has a location, which is a decimal number between 0 and 1 representing a position on the boundary of a circle.  The distance between any two locations is defined as the distance along the boundary of the circle between their locations:

[@
d(x, y) = min(abs(x - y), 1 - abs(x - y))
@]

Each node regularly swaps locations with other randomly-chosen nodes in a systematic way to minimize the product of the distances to its neighbours.  Thus a node's location comes to be close in a certain sense to the location of its neighbours.  Path-finding messages can then be routed by passing them to those neighbours with locations closest to the target location.

Note that with Metropolis-Hastings routing there is no requirement for nodes to report their own exact location as the routing target of messages from transaction partners.  They may report slightly inexact locations for privacy reasons, or the location of a neighbour, or an average of a group of neighbours to route the message through them.  This requires informing those neighbours ahead of time that the message is coming, by sending a @@path-query@@ or @@path-available@@ as the case may be.

Nodes might also consider such things as past records of success in finding paths through various neighbours, connection latency, desirability of holding or spending certain obligations, exchange rates offered, network resources available with each neighbour, etc.  Fee-charging nodes have a profit motive to quickly find a relatively low-fee path that will appeal to the payer.

The Ripple network consists of user agents, or nodes, connected pairwise by abstract mutual-credit accounts which allow searching for paths in the network, and sending and tracking of obligations between the two parties through the passing of messages.  Payers must also be able to establish messaging connections to the recipients of their payments.  The nature of those connections depends on the particular message transport system being used.  Right now, there is a tentative [[binding to XMPP -> Main/XMPP binding]].

If a node receives a request to change the same limit as an existing open limit request, the second request should supercede the first.

If a node receives a request to change to same limit as an open limit request that ''it has sent'', it should reply with an error: "conflicting limit request ID xxx already open".  [Error codes to be defined...]

A node may cancel a limit request by replying to a limit-accept with a "request withdrawn" error.

* the new credit limit
* a note describing the request

When a messaging connection between two Ripple nodes is established, the node accepting the conection must send a @@time@@ message, consisting of its current time, UTC.  The node receiving the time message echoes back its own time message in reply, indicating that it agrees to use the other node's time as the official time for that connection.  If it disagrees, it replies with an error and sends its own time message.  If that time message is rejected, the connection is closed.  There is little reason to disagree with someone's time at the start of a connection, unless you have oustanding open transactions with the other node that are time-sensitive. 

Time messages can be used to discover connection latency.

A node wishing to receive a payment from another node may initiate contact with the potential payer node by sending a @@payment-request@@ message to his node's network ID:

The payment request may be followed by an @@payment-init@@ message from the potential payer, or ignored.

The payer node contacts recipient node and communicates the following in an @@payment-init@@ message:

Transaction units are integer units invented for the purposes of the transaction to mask the true nature (amount & units) of the transaction from intermediaries.  The number of transaction units consisting the entire payment as declared in the payment-init message defines the conversion rate between transaction units and actual units of payment.  A simple convention is to make one transaction unit equal one cent, although any conversion rate that allows the entire amount to be flexibly divided into integer transaction-unit amounts for payment down multiple paths is acceptable.

The recipient may accept the payment initiation with an @@payment-accept@@:

If a node wishes to change its partner's or its own credit limit, it sends a @@limit@@ message containing:

The change is considered pending until a @@limit-accept@@ containing the same information is received back.  If a @@limit-reject@@ is received with the same account ID and request ID, then the credit change has been rejected.  The rejecting node may of course propose a different limit it considers appropriate by sending its own limit message anew.

In the case of decreasing either limit, the limit message is considered as simply informative, and should be implemented immediately, with the limit-accept being sent back immediately.  A node may not reject a decreased limit.

In the case of increasing either limit, the message is interpreted either as a request or an offer and the limit-confirm or -reject may be delayed while the partner considers. 

If a node receives a credit-change message for an account on which it already has an open limit request that it has sent, it should reply with an error: "limit request ID xxx already open".  [Error codes to be defined...]

The change is considered pending until a @@credit-change-accept@@ containing the same information is received back.  If a @@credit-change-reject@@ is received with the same account ID and request ID, then the credit change has been rejected.  The rejecting node may of course propose a different limit it considers appropriate by sending its own credit-change message anew.

In the case of decreasing either limit, the credit-change message is considered as simply informative, and should be implemented immediately, with the credit-change-accept being sent back immediately.  A node may not reject a decreased limit.

If a node receives a credit-change message for an account on which it already has an open credit-change request that it has sent, it should reply with an error: "credit change request ID xxx already open".  [Error codes to be defined...]

The change is considered pending until a @@credit-change-accept@@ containing the same information is received back.  If a @@credit-change-reject@@ is received with the same account ID and request ID, then the credit change has been rejected.

In the case of decreasing either limit, the credit-change message is considered as simply informative, and should be implemented immediately, with the affirmative reply containing the credit-change-confirm.

In the case of increasing either limit, the message is interpreted either as a request or an offer and the credit-change-confirm may be delayed while the partner considers. 

no change occurs until the partner sends back another credit-change message confirming the new limit or specifying a lower limit than the one proposed.  If another credit-change message addressing the limit in question is sent by the node who proposed the original change, the original message is to be disregarded. 

* Metropolis-Hastings location-swapping

The credit available along the path so far is to help route the query by preferring accounts that have that amount of available credit.  Units of work is how queries are given a finite lifetime.  Each unit of work represents one query message being passed from one neighbour to another.  When a query is received from one neighbour and subsequently sent to several other neighbours, the units of work must be divided up amongst the subqueries, and each number decremented by one.  When units of work reaches zero, the query may be considered dead -- nodes should never pass a query with negative units of work.  Units of work may be ignored for path-available messages along established paths.  See [[Once a Path is Found -> #path-found]] below.

* calculate the desired conversion rate from transaction units to account units for the account with that neighbour, based on the conversion rate of the incoming query
* reduce the “credit available along the path” if the account with that neighbour has insufficient available credit

Other types of units may be useful for credit/reputation checks, although not for payment.  For example, a satisfied customer may give a merchant one unit of "satisfied customer" credit for each successful transaction with her.  Then a prospective customer could learn about that merchant's reputation by doing a credit check against "satisfied customer" units.


[[#location-swapping]]
'''Location Swapping'''

Ripple uses the Metropolis-Hastings algorithm for routing, as described in Clarke and Sandberg's presentation [[Routing in the Dark -> http://www.math.chalmers.se/~ossa/defcon13/vegas1_print.pdf]] (PDF). 

Each node has a location, which is a decimal number between -1 and 1 representing a position on the boundary of a circle.  The distance between any two nodes is defined as the distance along the boundary of the circle between their locations.  Each node regularly swaps locations with other randomly-chosen nodes in a systematic way to minimize the product of the distances to its neighbours.  Thus a node's location comes to be close in a certain sense to the location of its neighbours.  Path-finding messages can then be routed by passing them to those neighbours with locations closest to the target location.

See below for a [[specification of location-swapping -> #location-swapping]].

Nodes might also consider such things as past records of success in finding paths through various neighbours, connection latency, desirability of holding or spending certain obligations, exchange rates offered, number of queries sent to each neighbour, etc.

* the transaction alias for each account in the path, in order

* remove the previous account alias

The Ripple network consists of user agents, or nodes, connected pairwise by abstract mutual-credit accounts which allow searching for paths in the network, and sending and tracking of obligations between the two parties through the passing of messages.  Payers must also establish messaging connections to the recipients of their payments.  The nature of those connections depends on the particular message transport being used.  Right now, there is a tentative [[binding to XMPP -> Main/XMPP binding]].

'''Connection Time'''

When a messaging connection between two Ripple nodes is established, the connection initiator must send a @@time@@ message, consisting of its current time, UTC.  The node receiving the time message responds with its own time message in reply, indicating that it agrees to use the other node's time as the official time for that connection.  If it disagrees, it replies with an error and sends its own time message.  If that time message is rejected, the connection is closed.  There is little reason to disagree with someone's time at the start of a connection, unless you have oustanding open transactions with the other node that are time-sensitive. 

During the course of the connection, either node may send a time message to the other to verify the time.  If at any point the two nodes fail to agree on the current time, the connection should be closed.

Repeated time messages can be used to discover connection latency.

* each node's routing information (see Query Routing)

* payer's routing information (optional?)

  * a transaction-unique alias (each account must use the same alias for every message with the same payment ID)

The list of accounts in the path is to allow the payer to determine if two paths overlap and if so, what the actual total credit available along the two paths is.  Nodes may add dummy accounts to obfuscate the number of hops between payer and recipient or the recipient's identity.  The transaction alias for an account might be the payment ID appended to the account ID, hashed.

* stamp the account's transaction alias for this payment on the message
* stamp the credit available on this account for this transaction

* heartbeat messages to maintain agreement on current time?

* premix routing
  * tunnels a random distance away for sending and receiving transactions to hide payer and recipient ID from statistical analysis by neighbours
* [[interest]]
* limited query floods at one or both ends?

* for each account/connection along which this message has been passed:
  * a unique alias (each account must use the same alias for every message with the same payment ID)
  * credit currently available for this transaction, in transaction units, on the account on which the node will accept payment

When a node accepts a receipt, it must stamp the amount to be redeemed in account units, sign the receipt with its authentication key, and reply by sending the signed receipt back to the node from which it accepted the receipt.  This creates an undeniable record that the promise has been redeemed.  The sum of signed receipts from each partner to an account equals the account balance.  The original receipt is passed down the chain unchanged.

The payer may optionally volunteer payment forward up a path without delay, as long as she has received a copy of the receipt signed by the recipient, which is her proof-of-payment.  She can do this by appending the amount to be redeemed in account units to the receipt, signing it, and passing it forward.  Any intermediary receiving such a volunteered payment may in turn volunteer it forward to the next node up the chain.  This capability serves to speed up the finalization of the transaction, minimizing uncertainty and the time that credit must be held frozen.

The eventual goal is to define the Ripple network with a protocol enabling nodes to make and maintain mutual-credit accounts between them, and use the network of these accounts for making payments by finding paths to the payment recipient and passing obligations down those paths.  Nodes should also be able to verify another's reputation by checking the available credit through the network to the target node.

This document outlines in an abstract way the types of messages that need to be passed between nodes and the data contained in those messages.

'''To Do'''

* heartbeat messages?
* Metropolis-Hastings routing
  * swap mediated by disinterested third party?
  * optional to allow neighbours to ensure honest swapping by revealing neighbours' locations?
* payer can volunteer payment up the chain if recipient sends copy of signed receipt to payer
* interest
  * keep separate balance on account for each rate

The Ripple network consists of user agents, or nodes, connected pairwise by abstract mutual-credit accounts which allow tracking of obligations between the two parties.  The nature of those connections depends on the particular message transport being used.  Right now, there is a tentative [[binding to XMPP -> Main/XMPP binding]].

* each node's routing data (see Query Routing)

'''Query Routing'''

* credit available along path so far, in account units for that account (defines a conversion rate from transaction to account units)

The eventual goal is to define a protocol ethemnabling nodes on the Ripple network to make and maintain mutual-credit accounts between , and use the network of these accounts for making credit payments by finding paths to the payment recipient and passing credits/IOUs down those paths.  Also specified is a method of making credit/reputation check requests based on paths through the Ripple network.

The credit available along the path so far is to help route the query by preferring accounts that have that amount of available credit.  Units of work is how queries are given a finite lifetime.  Each unit of work represents one query message being passed from one neighbour to another.  When a query is received from one neighbour and subsequently sent to several other neighbours, the units of work must be divided up amongst the subqueries, and each number decremented by one.  When units of work reaches zero, the query may be considered dead -- nodes should never pass a query with units of work zero.  Units of work may be ignored for path-available messages along established paths.  See [[Once a Path is Found -> #path-found]] below.

[[#available-paths]]
'''Available Paths'''

The payment recipient also participates in the path-finding process.  If the payer has revealed some or all of his routing information during payment initiation, the recipient may immediately begin issuing @@path-available@@ messages.  Otherwise, he must wait until he receives a query to begin issuing them.  Path available messages contain:

Path-available messages are routed just like queries (see [[Query Routing -> #query-routing]] below), except they are headed in the other direction.  Queries received from the other direction with the same payment ID will naturally give very important routing hints!  For each neighbour it is passing a path-available message on to, a node should:

* replace account ID of previous step with account ID of next step
* calculate a conversion rate between transaction units and account units for the account with that neighbour, based on the conversion rate of the incoming path-available message
* change “credit available for this payment" if appropriate
* increase the "minimum promise time-to-penalty" to ensure that it incurs no penalty without being able to recoup the amount
* increase the “minimum promise life” to give it time to process the receipt if the deadline is near (see Making Promises and Finalizing Payment below)
* stamp its unique alias for this payment ID on the message
* stamp the credit available for this transaction on the account on which it will be accepting payment
* decrement the total units of work by one
* assign that neighbour a proportion of the remaining units of work available for that query

Nodes must store who passed them queries for a given payment ID.  Nodes must also store the aliases of the neighbours that passed path-available messages in case that path is selected for the next phase of the transaction, Making Promises, as well as conversion rates between account units and transaction units, minimum promise time-to-penalty and promise life.

'''Fees'''

Nodes should advertise their keywords to their neighbours with @@keyword-advertisement@@ messages.  Nodes can also advertise their distance to other keywords using this same message type:

* keyword
* number of hops to keyword

[[#path-found]]
'''Once a Path is Found'''

When a node sees a path-query and a path-available with the same payment ID, a path has been found.  The node that discovered the connection should immediately pass the path available message in the direction from which it received the path-query.  Units-of-work restrictions can be ignored on these messages.  It should also continue routing queries and path-available messages as usual, since further paths may be necessary to complete the entire payment, or may offer a lower price for the payer.

'''Making Promises (Commit-Request)'''

When the payer has found payment paths with enough combined available credit to complete the payment, it sends a @@promise message@@ to the first node on each path, representing its commitment to redeem a valid receipt that can be authenticated with the promise's authentication key up to the amount of IOUs indicated on the receipt, if presented before the stated deadline.  A promise serves to hold credit for the payment.

* payment ID
* path ID (a chain of promises defines a path)
* amount to be held for payment, in transaction units
* ID of account to be made part of path by this promise being passed
* amount to be held for payment, in account units, according to conversion rate defined by neighbour in path-available message
* promise time-to-penalty
* daily penalty rate if receipt or promise-release not received within time-to-penalty
* promise deadline, after which promise expires
* the payer's receipt authentication key for this payment path
* the recipient's receipt authentication key for this payment path
* the transaction alias for each node in the path, in order
* a timestamp to indicate the time the promise came into effect.

* calculate the amount held for payment in account units on the next account in the path according * to the conversion rate stated in the path-available message received on that account
* reduce the amount to be held for payment in transaction units if there is insufficient credit on the next account in the path
* shorten the time-to-penalty to what it indicated on the path-available message
* optionally increase the daily penalty rate
* shorten the deadline according to the promise life it indicated on the path-available message
* remove its own alias from the list of intermediaries

The path-available message referred to above is the most recent path-available message received with the same path forward to the payment recipient as the promise message, as determined by the list of transaction aliases.

'''Finalizing the Payment'''

The recipient sends the payer @@promise-received@@ messages, each indicating that a promise has been received:

* received promise's path ID
* final amount of promise in transaction units
* recipient's deadline for accepting the receipt for this path
* timestamp indicating current time

When the payer receives promise-received messages equal to or exceeding the amount of the payment, he generates @@receipt@@ messages matching the promises received by the recipient, –- one receipt per promise/path --  authenticates them individually with each path's authentication key, and sends them each to the recipient:

* payment ID
* path ID
* amount for this path in transaction units

'''Redeeming Promises (Commit)'''

'''Releasing Promises (Rollback)'''

A node may release a neighbour from all or part of its promise at any time with a signed @@promise-release@@ message:

* payment ID
* path ID
* amount to release, in transaction units
* error/reason code

'''Promise Penalties and Expiry'''

Penalties are collected by issuing a @@payment-request@@ to the offending node, containing the following special fields:

* penalty – payment ID
* penalty – path ID

If any promise's final deadline for accepting receipts passes, the issuing node should issue a @@promise-expired@@ notification, containing:

* payment ID
* path ID
* timestamp

Any node can fulfill an expired promise if it wishes and has available credit.  Any node can request that an expired promise be fulfilled by sending a @@promise-renew@@ request:

* payment ID
* promise ID

!! Appendices

'''Timing Disputes'''

'''Other Disputes'''

'''Credit/Reputation Requests'''

'''Units of Account'''

National currencies and other value units can be identified by arbitrary strings.  A natural ID for a national currency is its three-letter code.  Other standard units should include ounces of gold, grams of gold, hours, joules, and kilowatt-hours.  Since units of payment will have to be communicated between payer and recipient, it is important that unit codes be standardized.

For background on Ripple, see [[Money as IOUs in Social Trust Networks & A Proposal for a Decentralized Currency Network Protocol -> http://ripple.sourceforge.net/decentralizedcurrency.pdf]] (PDF).

!! Network Structure

!! Accounts

Accounts are created by one node offering to accept another's IOUs with an @@offer@@ message containing:

If the offer recipient accepts the offer, his node sends back an @@offer-accept@@ message:

Otherwise it sends an @@offer-reject@@ message. 

If a node wishes to change its partner's or its own credit limit, it sends a @@credit-change@@ message containing:

In the case where both nodes happen to send messages proposing to change the same limit simultaneously, the lower of the two proposals comes into effect.  In case of doubt, the other node's account state can be retrieved using a @@verify-account@@ query, described in [[Verifying Account Data -> #verify-account]] below.

If a node's routing information changes, it must send a @@routing-change@@ message to its neighbours:

To change network ID, a node must send a signed @@id-change@@ message containing the new network ID.  After the reply to this message, the receiving node must send all Ripple messages to the new ID.

Send a signed @@key-change@@ message containing the new key.  (Perhaps this should contain a revocation message for the old key?)

Send a @@verify-account@@ message to which the reply contains:

!! Payments

* Initiating payment between the payer and recipient nodes
* Path discovery, consisting of query messages sent out by the payer, and path-available message sent out by the recipient
* Making promises, where the payer propagates promises to redeem the payment receipt for IOUs forward down each payment path
* Finalizing the payment, where a receipt created by the payer is propagated back down the path by the recipient, and is redeemed for IOUs at each step.

'''Requesting Payment'''

A node wishing to receive a payment from another node may initiate contact with the potential payer node by sending a @@request-payment@@ message to his node's network ID:

* unique ID for the payment
* amount
* units
* time of request
* payment recipient's node's network address
* authorization number (optional)
* an explanatory note

The payment request may be followed by an @@initiate-payment@@ message from the potential payer, or ignored.

The authorization number may be used to pre-authorize payments, so the node can automatically make payments when it receives a request.  The request-payment message may also be authorized by signing it with a certain key, contained in the node owner's smart card, for example, for point-of-sale scenarios.

'''Initiating Payment'''

The payer node contacts recipient node and communicates the following in an @@initiate-payment@@ message:

* unique ID for the payment
* amount to be paid to recipient
* units of payment
* number of transaction units that will consist the entire payment
* payer's routing information (optional, may be a partial set)
* some explanatory text to the recipient

The recipient may accept the payment initiation with an @@accept-payment@@:

* payment ID
* amount to be paid to recipient
* units of payment
* number of transaction units that will consist the entire payment
* payer's explanatory text echoed back
* recipient's routing information
* recipient's authentication key for payment (used to sign receipts)
* public-key certificate establishing recipient's identity to the payer

This must be signed by the recipient's identifying certificate key, whose certificate may be authorized by an authority recognized by the payer and which identifies the recipient in a way acceptable to the payer.  This message serves as evidence that the recipient participated in the transaction.  The explanatory text can contain the reason for the payment.  It can be used to connect the recipient's signature on receipts to the recipient (see [[Finalizing Payment -> #finalizing-payment]].)

calculate a conversion rate between transaction units and account units for the account with that neighbour, based on the conversion rate of the incoming path-available message
change “credit available for this payment" if appropriate
increase the "minimum promise time-to-penalty" to ensure that it incurs no penalty without being able to recoup the amount
increase the “minimum promise life” to give it time to process the receipt if the deadline is near (see Making Promises and Finalizing Payment below)
stamp its unique alias for this payment ID on the message
stamp the credit available for this transaction on the account on which it will be accepting payment

'''Changing Network ID'''

To change network ID, a node must send a signed ''id-change'' message containing the new network ID.  After the reply to this message, the receiving node must send all Ripple messages to the new ID.

'''Changing Authentication Key'''

Send a signed ''key-change'' message containing the new key.  (Perhaps this should contain a revocation message for the old key?)

'''Verifying Account Data'''

Send a ''verify-account'' message to which the reply contains:

* account balance
* units of account
* credit limit for each node
* routing information for each node

'''Payment Messages'''

Several payment messages are also sent over account channels.  See the [[next section -> #payments]] for details.

[[#payments]]
!!! Payments

In the case where both nodes happen to send messages proposing to change the same limit simultaneously, the lower of the two proposals comes into effect.  In case of doubt, the other node's account state can be retrieved using a ''verify-account'' query, described in [[Verifying Account Data -> #verify-account]] below.

'''Changing Routing Information'''

If a node's routing information changes, it must send a ''routing-change'' message to its neighbours:

* the new set of routing information

For more information on routing information, see [[Query Routing -> #query-routing]] below.  The routing information messages do not have to be signed.

%center%''by Ryan Fugger''\\

'''Goal'''

For background on Ripple, see [[Money as IOUs in Social Trust Networks & A Proposal for a Decentralized Currency Network Protocol -> http://ripple.sourceforge.net/decentralizedcurrency.pdf]].

!!! Network Structure

The Ripple network consists of user agents, or nodes, connected pairwise by abstract mutual-credit accounts which allow tracking of IOUs between the two parties.  The nature of those connections and the message transport between them is defined by a particular transport binding.  Right now, there is a [[binding to XMPP -> Main/XMPP binding]].


!!! Accounts

* an account ID,  which serves as a permanent identifier for the account
* each node's ID
* the unit of account (see Units of Account)
* the number of decimal digits with which to keep this account
* a credit limit for each node
* a record of past debits and credits
* the current balance
* each node's routing keywords (see Query Routing)
* an authentication key for each node (see Authentication Keys)

'''Creating an Account'''

Accounts are created by one node offering to accept another's IOUs with an ''offer'' message containing:

* an account ID
* the offering node's network ID
* the offering node's routing information
* time of offer
* the units of account
* the number of decimal digits with which to keep this account
* the proposed credit limit for node receiving the offer
* some explanatory text to the recipient

If the offer recipient accepts the offer, his node sends back an ''offer-accept'' message:

* account ID
* current time and date
* its network address
* its routing information

* incorrect account ID
* offer withdrawn

Otherwise it sends an ''offer-reject'' message. 

'''Changing Credit Limits'''

If a node wishes to change its partner's or its own credit limit, it sends a ''credit-change'' message containing:

* account ID
* current time and date
* the address of the node whose credit limit is being changed
* the new credit limit.

In the case where both nodes happen to send messages proposing to change the same limit simultaneously, the lower of the two proposals comes into effect.  In case of doubt, the other node's account state can be retrieved using a ''verify-account'' query, described in [[Verifying Account Data -> #verfiy-account]] below.

!! %center%Ripple Application Protocol

%center%''Design Outline''