search

ledgerloops / strategy-pit

Testing ground for LedgerLoop strategies
Apache License 2.0
0 stars 0 forks source link

readme

LedgerLoops Strategy Pit

This repository is an experimentation ground for LedgerLoops strategies. Some strategies will integrate discovery of loops with negotiation of exchange rates, others may keep them separate.

The strategies are tested in different network models and with different network topologies.

Usage

npm install
npm test
npm run build
node ../ledgerloops/src/network-generator.js > __tests__/fixtures/testnet.csv
time node ./build/src/run.js

Network simulators

See also 2024 work on ngraph generator in ledgerloops/ledgerloops repo.

Basic

In the basic network simulator, nodes Alice and Bob can become neighbours with:

const alice = new Node('alice');
const bob = new Node('bob');
alice.meet(bob);

After that, Alice can contact Bob, for instance with a Meet message:

class MyStrategy extends Node {
  meet(other: Node): void {
    this.addFriend(other);
    other.receiveMessage(new Meet(this));
  }
  receiveMessage(sender: string message: Message): void {
    if (message.getMessageType() === `meet`) {
      this.addFriend(sender);
    }
  }
}

The Meet message will give Bob a handle to Alice, so now they can send each other any message they want:

bob.receiveMessage(this, new Probe('435af3b4'));

A Node#receiveMessage call may trigger other messages to be sent, so make sure that this doesn't get into an infinite loop. This in itself means that this network simulator is not Byzantine fault tolerant, because nodes have infinite patience in this model. Only one node is acting at a time, and while it is acting, all other nodes are completely asleep until the acting node responds.

Message ticks

The message ticks model (not implemented yet) improves upon the basic network simulator in that each node gets a change to execute on each clock tick, and messages sent during clock tick n will be delivered in clock tick n+1. Each node is allowed to act on each of the events that have been queued up for it (messages or otherwise), for unlimited time, so if one node gets into an infinite loop or long sleep, all other nodes will sleep too.

Message ticks with timeouts

The message ticks with timeouts model (not implemented yet) improves upon the message ticks network simulator in that on each clock tick, each node is allowed to act on each of the events that have been queued up for it (messages or otherwise), for up to a set limit (e.g. 1000ms per event).

Network Topologies

Triangle

The simplest network topology has 3 nodes (Alice, Bob and Charlie), and its links evolve as follows:

  1. None.
  2. Alice->Bob.
  3. Alice->Bob, Bob->Charlie.
  4. Alice->Bob, Bob->Charlie, Charlie->Alice.

Hour Glass

This network topology has 5 nodes (Alice, Bob, Charlie, Dave and Edward), and its links evolve as follows (Alice is at the center where two triangles meet):

  1. None.
  2. Alice->Bob.
  3. Alice->Bob, Bob->Charlie.
  4. Alice->Bob, Bob->Charlie, Charlie->Alice.
  5. Alice->Bob, Bob->Charlie, Charlie->Alice, Alice->Dave.
  6. Alice->Bob, Bob->Charlie, Charlie->Alice, Alice->Dave, Dave->Edward.
  7. Alice->Bob, Bob->Charlie, Charlie->Alice, Alice->Dave, Dave->Edward, Edward->Alice.

Current Strategies

Giraffe

The Giraffe is the first strategy to properly detect Kite Loops, see https://github.com/ledgerloops/strategy-pit/issues/15.

Saiga

The Saiga differs from the Giraffe in that it negotiates pegged loops (no exchange rates), see https://github.com/ledgerloops/strategy-pit/issues/24.

Badger

The Badger differs from the Saiga in that it uses majority-based all-or-nothing finality, see https://github.com/ledgerloops/strategy-pit/issues/29.

Second Generation Strategies

Stingray

The Stingray has a more detailed data storage (both for Flood Probes and for Trace Probes) than its predecessors Salmon, Pelican and Petrogale. A Stingray reacts to events with actions. Events are:

Actions are:

A Stingray will behave as follows: For every Meet, mint a probe and send it to all neighbours (including the new one) For every incoming probe:

A Probe is virgin for a neighbour if it was never sent to them and never received from them.

Jackal

Same as Stingray except that, as a mitigation for https://github.com/ledgerloops/strategy-pit/issues/7, the other node is told to pauze its messages during the batch of messages that are triggered by an onMeet event.

Squid

Same as Jackal except that, in consideration of https://github.com/ledgerloops/strategy-pit/issues/8, of the two nodes in a neighbour relationship, one unpauzes whenever the other one pauzes.

First Generation Strategies

Salmon

The Salmon strategy works as follows: When a Salmon Node meets a new node, it:

When a Salmon Node receives a Meet message:

When a Salmon Node receives a Probe message:

When a Salmon Node finds a loop:

When a Salmon Node receives a Loop message:

Three Salmons in a Triangle in the Basic simulator will successfully find three loops. They will not be able to detect that the three loops have exact overlap. They rely on the fact that a triangle has no forks. Forwarding a Loop message to all other contacts is a bug unless the number of other contacts is exactly one. This bug goes undetected in the Triangle topology, but Salmon loop detection would break if you put them in an Hourglass topology.

Also, Salmons don't implement exchange rate negotiation.

Pelican

Pelicans differ from Salmons in that they create multiple Loops per Probe - forking them whenever the network forks. This means they can handle not only the Triangle but also the Hourglass topology.

Due to a bug in a mechanism that was meant to prevent unnecessary probes to a newly met node, nodes in the second triangle don't get to see all the probes and loops.

Petrogale

The Petrogale is identical to the Pelican except that it always sends all existing probes to a newly met node, even if loops were already found for them.

I think in the hourglass test, the first triangle is found 3 times and the second triangle is found 8 times, although it's hard to tell because of #1 and #2.

Butterfly

The Butterfly uses: