@circles/transfer

circles-transfer

Find maximum flow and transitive transfer steps in a trust graph

Handbook | Releases | Contributing

Utility module for Circles to find the Maximum flow and necessary transitive transfer steps in a trust graph with multiple tokens.

For performance reasons this module uses the native pathfinder process by chriseth to find the transfer steps.

Requirements

• Node.js (tested v14)

Installation

# Make it a dependency
npm i @circles/transfer

# Copy the native pathfinder process into your project folder
cp ./node_modules/@circles/transfer/pathfinder ./pathfinder

Usage

import findTransitiveTransfer from '@circles/transfer';

// Define a weighted trust graph between trusted tokens. Each edge describes
// how much ("capacity") of what token ("token") can be sent from which node
// ("from") to which ("to").
//
// The csv file has de format `from,to,token,capacity`. Store it somewhere (for example ./graph.csv):
//
// 0x5534d2ba89ad1c01c186efafee7105dba071134a,0x83d878a6123efd548341b468f017af31d96b09b6,0x5534d2ba89ad1c01c186efafee7105dba071134a,10
// 0x83d878a6123efd548341b468f017af31d96b09b6,0xe08fe38204075884b5dbdcb0ddca0e033f9481a7,0x83d878a6123efd548341b468f017af31d96b09b6,7
// 0x83d878a6123efd548341b468f017af31d96b09b6,0xe08fe38204075884b5dbdcb0ddca0e033f9481a7,0xe08fe38204075884b5dbdcb0ddca0e033f9481a7,5
// ...

// Find required transfer steps to send tokens transitively between two nodes:
const { transferSteps, maxFlowValue } = await findTransitiveTransfer(
  {
    from: '0x5534d2ba89ad1c01c186efafee7105dba071134a',
    to: '0x29003579d2ca6d47c1860c4ed36656542a28f012',
    value: '5',
  },
  {
    edgesFile: './graph.csv', // Path to graph file
    pathfinderExecutable: './pathfinder', // Path to `pathfinder` program
    timeout: 1000 * 5, // Stop process when it takes longer than x milliseconds
  },
);

// ... we get the maximum possible value. If transfer value is smaller it will
// be the same:
console.log(`Can send max. ${maxFlowValue}`);

// ... and finally the transfer steps:
transferSteps.forEach(({ step, from, to, value, token }) => {
  console.log(`${step}.: Send ${value} of ${token} from ${from} to ${to}`);
});

Development

circles-transfer is a JavaScript module, tested with Jest, transpiled with Babel and bundled with Rollup.

# Install dependencies
npm install

# Run test suite
npm run test
npm run test:watch

# Check code formatting
npm run lint

# Build it!
npm run build

Pathfinder

pathfinder is a C++ program by chriseth compiled for Linux arm64 in this repository. To update the pathfinder in the api, build a native binary according to the README instructions from chriseth and move the target into your project.

The version we are using corresponds with this commit: https://github.com/chriseth/pathfinder/commit/41f5eda7941e35dc67ebdb04a842eb7d65c810ef

License

GNU Affero General Public License v3.0 AGPL-3.0