An Algorithm For Transitive Transaction

Note: This article was written while conducting research for the Polis Foundation and was first published on their blog here.

Transitive transaction describes the process whereby two untrusted (unconnected) agents on a network can transact (exchange coins) using their common, mutually trusted connections acting as intermediaries.

The following provides a description of the transitive transaction algorithm Polis uses in our network-based economic modeling (supporting definitions are provided further down).

A Buyer agent (B) and a Seller agent (S) are two agents that exist on the same network. They do not have to be neighbors. B wants to buy something from S for a transaction amount (price) P.

Step 1: Find all paths through the network between B and S using the network's Adjacency Matrix as follows:

1. Record each of B’s neighbors (connections) as a path
2. Recursively search each of B’s neighbors uncommon neighbors (connections) until
   a. S is found (a success), or
   b. The recursion exceeds a step limit without finding S (a failure), or
   c. The path loops back to B before finding S (a failure)
3. Record all paths found to S
4. Sort them from shortest to longest

Step 2: Determine if there is enough liquidity on each path to support the deal

Step 3: If a liquid path is found, record the transaction (writing appropriate transaction records in the ledgers of each agent along the path, including B and S) or record a transaction failure due to insufficient liquidity.

Supporting Definitions

• Every agent has their own, personal currency. All currencies have the same transfer price, currently zero (not to be confused with the transaction price).

• An agent A will accept the following types of currency from agent B if A and B are mutually trusted neighbors (connected). A will accept

  1. B’s currency
  2. Any of A’s currency B might possess
  3. Any currency B has from other agents that both A and B trust (are directly connected, named mutually connected agents).

• Deal liquidity means agent B possesses a basket of currency types that agent A will accept in sufficient quantity to meet or exceed the transaction amount (price).

• The order for which a bag of currency equalling the transaction amount is passed from B to A is

  1. If B holds A’s coins, these will be transferred first
  2. Next, if necessary, coins from mutually connected neighbors will be transferred
  3. Finally, if necessary, B’s coins will be transferred to A

• In the case above with B and S transacting, and B and S not being neighbors (being unconnected), these measures of liquidity and rules of coin transfer hold for all agents situated on each segment of the path between B and S. In this case B and S will transact but not not share coins directly, instead a chaining process is performed using the agents along the selected network path that lies between them as intermediaries.

Notes

• It is by convention only that we use the shortest available liquid path.

• Similarly, by convension, we use the first liquid path discovered from an ordered list regardless if there are one or more paths of the same length.

• Similarly, by convension, we adopt the order of coin types transferred from B to A to meet the transaction price.

• A curious consequence of this apparatus is ones “current balance” is relative, one may have as many “current” balances as one has neighbors.