[WIP] Whisper reputation system and incentivization 0.0.2
=========================================================

this document describes a reputation system for whisper nodes
and incentivization mechanism that will be built on top of it.

the proposed design might be extended to any p2p service, such as mail service or LES. it is however out of the scope of this document.

# why reputation system?

imagine a device that connects to a network without any prior knowledge about the
network. it uses discovery to obtain a bunch of nodes and connects with them. however, it doesn't give
us any information about the quality of service that each node provides. but we need such guarantee if
service is not free.

for example, in the case of a whisper, we want every node to be connected to multiple peers
and maintain high uptime. but since we connected to the network for the first time - we know nothing
about peers reliability. in case if the connection is free - we won't lose anything if peer will
disappear shortly after the connection was made. but if it is not then the user will pay for a potentially
shitty connection.

so that's a problem which a reputation system will aim to solve. it will provide a reliable rating for the network participants. additionally, it will have to be resistant to:
- boosting rating using sybils
- falsifying feedback to devalue someone's rating
- whitewashing

# payments and incentivization

we have two types of participants in our network:
1. persistent nodes usually running on VPS and connected with many peers and high uptime
2. user nodes, usually mobile devices with restricted resources and limited uptime

from the network quality point of view, we are only interested in the 1st type of nodes, because
they increase the size and capacity of the network. for such nodes reputation system must guarantee
that if the node will maintain high uptime, connect with many peers, and forward messages reliably
- it won't have to pay anything, have a high rating and potentially make additional profit.

The 2nd type of nodes can't provide the same quality of service as 1st. so in order
to participate in the network, they must share the costs of the network usage. but they are interested
to pay only such node that can guarantee a high quality of service.
so reputation system will help them to find such service, and after that, they will engage
in some sort of payment procedure (will be discussed later).

# reputation system design

the current design is based mostly on [5] and [6], borrowing ideas from other papers.
there are other algorithms (i will cover them later) but most of them work in a similar way:
1. each node has a watchdog algorithm that is service dependent
2. based on transitivity of trust we get metrics from other nodes
3. based on the aggregation of collected and local metrics - we determine the general rank of the peer

there are also extensions that can provide better latency and anonymity in the reputation system, but we will explore them later.

## watchdog algorithm

We want to control two properties:
1. peer relays messages reliably and consistently
2. it maintains high uptime

The control loop can be found in the diagram below:


Every interval we select peers that will be assessed. For every such peer, we will send regular whisper message with unique identifiers (nonce, peer id). We will wait a configurable amount of time to receive the message. It must be received from any other peer in the network.
If the message received during under expected timeout - we will increment rating of the peer.

After the first round succeeded - we will periodically repeat same procedure in order to guarantee high uptime. If we don't receive expected message, or receive it too late, - rating will be decremented.
Additionally, we will have to use techniques for exponential increase/decrease of the rating
based on consistent peer behavior. The exact scheme will be documented after simulation research.

## collected metrics and transitivity of trust

In addition to locally computed metrics, described in the previous section, we will use metrics from peers with a high ranking. Algorithm for collecting such metrics presented below:


When we join the network for the first time, we have very little data about it. Thus we have 2 options:
1. participate in the network for a long time, before deciding on the consistency of a peer performance
2. use a pre-trusted set of nodes [2].

In our case identities of the pre-trusted nodes, can be stored on the chain.
The diagram above represents initial node bootstrap using such pre-trusted nodes.
When a device joins the network for the first time it will form a list of verifiers based on the information stored on a chain.
Once the device collected enough information about the network, it will be possible to avoid using the chain for verification. Ratings stored locally will be used instead.

Once the list of verifies is formed, we ask each verifier for a rating of each peer. Verifier should
respond only with QoS information collected locally, and only if it communicates with peer itself.
Otherwise, the reputation system will be highly susceptible to dishonest evaluators.

Once we requested feedback from verifiers we will compute mean feedback, using
local verifier rank as a weight. In case if all verifiers are pre-trusted -
they will have equal ranks.

Example with nodes with different ranks:

| peer | t1/12 | t2/10 | rst |
|------|-------|-------|-----------------------|
| p1 | 7 | 8 | 12/22 * 7 + 10/22 * 8 |
| p2 | 2 | 1 | 12/22 * 2 + 10/22 * 1 |

Example with pre-trussted nodes:

| peer | t1 | t2 | rst |
|------|----|----|-------------------|
| p1 | 5 | 4 | 1/2 * 5 + 1/2 * 4 |
| p2 | 0 | 7 | 0 + 1/2 * 7 |

TODO one thing followup is conflicting votes resolution. there are several techniques that
can be used. we must validate them based on the simulation result.

## metrics aggregation and peers selection

once we have local and collected rating we can compute general rating based
on the weights for local and collected rating. the idea here is that we can either
trust our local results or collected results more. this is not finalized but I assume
that mobile device will have to trust more in the collected metrics since it won't be an active participant in the network for most of the time.

we will need to select peers for 2 actions:
1. subset of peers will be used to asses quality of other peers
2. peers for connections

for the purpose of assessing quality, we will always maintain top 10% of peers based on rating.
for peers that are used for connections - we will try to connect opportunistically with peers with the highest rating. target peer will assess our rating and based on comparison with its own rating
it will determine if we need to pay.

# exploiting reputation system

## dishonest feedback from low-rank nodes

Any feedback provided by low-rank nodes won't have any effect if we have
a feedback from high-rank nodes. To avoid such exploit node should
prefer getting feedback from high-rank nodes, and try to discover more
of them if previously used nodes will become unavailable.

In the following example result will be 0 because neither a sybil 1 or 2 have any weight.
high-rank nodes in the following example, are either trusted nodes (from the chain) or regular
high-rank nodes.

| | sybil 1 / 0 | sybil 2 / 0 | high rank 1 / 10 | high rank 2 / 10 | rst |
|---------|-------------|-------------|------------------|------------------|-----|
| boosted | 25 | 27 | 0 | 0 | 0 |

## dishonest feedback from high-rank nodes

If adversarial node achieved high rank in the network it can be used
to boost other nodes rating. Because we are using weighted average - the more
nodes with higher rank you will have the more power you have on the rating in the network.

in the following example, we have 4 nodes in the network, and all of them are of equal rank:

| | peer 1 | peer 2 | peer 3 | peer 4 | result |
|---------|--------|--------|--------|--------|-----|
| boosted | 10 | 10 | 0 | 0 | 5 |

in this example, either group of peers - 1/2 or peers 3/4 might be lying. there are several ways to devalue such feedback:
1) don't use feedback that is different from the majority (TODO find a paper where it was mentioned)
2) guarantee that feedback requested only from peers that are currently used by a node.
if 'peer 1' rated highly 'boosted' - it can result in the drop of connection to 'peer 1' and establishing a new connection to 'boosted'. Thus reducing potential profits of 'peer 1'. so there is simply no incentive for doing so.

TODO followup on "trust" rating explored in [3].

## freeriding, whitewashing, and spam

we must disallow freeriding and potentially a whitewashing (which has similar effects on the network) because
earning reputation will become irrelevant. and reputation is a basis of incentivization in the following design.

the most secure strategy would be to put a cost on identity creation, such as a deposit on the chain.
and without such deposit, any peer will be disconnected by an honest participant of the network.
if peers make a deposit and it spams - node just blacklists such peer forever. deposit will be eventually
lost if a majority of the network blacklists the peer.
TODO such deposit can be used to make periodical payments.

however, it might be a huge problem for Status-IM adoption, and almost certainly not a good strategy to
begin with. we may have to use more naive tools to prevent spam, such as controlling spam by public IP,
since public IPs are not free. But in general, there must be additional research made in order to prevent spam in the network.

# payment system and interactions with blockchain

there are 3 potential ways the current system will interact with blockchain. For now, only 2 of them are present on the diagram:


1. blockchain will store a list of pre-trusted identities
those identities will be used to provide initial feedback about the network
when the peer joins the network for the first time. see reputation spec for details of this procedure

2. payments must be timed and verifiable

The idea behind payment system is that it must protect a user from service provider bad behavior,
which will be noticed either locally or based on feedback from verifiers. A user will pay for every
N units of time, for example, 10 minutes. If bad behavior is noticed or rank is dropped - we can
stop payments and waste as little money as possible. On the other hand - if we observe only high QoS
we will proceed with payments, but the service provider won't have to claim each payment on the chain.

payment object:

| field | type |
|-----------|---------|
| receiver | address |
| token | address |
| value | uint256 |
| start | uint |
| end | uint |
| signature | bytes |

The token is an erc20 token address and value is an amount that will be paid to the service provider.
start and end is a window which is covered by the payment. there are 2 ideas behind such a window:
1. allow payments to accumulate
2. prevent a replay of the payment
so once such payment is executed - 'end' is saved in storage and any payment with end lower then the last one is invalid.
In order to execute a payment, recover address from the signature. Hash that will be used for recovery
is derivative from all 5 previous fields.

Validation for start and end parameters, must act as compare and set mechanism, for example:

| current | start | end | result | valid |
|---------|-------|-----|--------|-------|
| 0 | 0 | 1 | 1 | true |
| 1 | 0 | 2 | 1 | false |
| 1 | 1 | 4 | 4 | true |
| 1 | 2 | 4 | 4 | false |

The goal is to protect against replay, such if payment 1-4 was accepted, you can't claim a payment for 1-2.
But also allow accumulation, so that if you receive 1-2 at first, you can claim only 1-4, which should include
1-2.

3. stake as whitewashing protection

in order to protect from a whitewashing, we may need to require a stake from every identity, even when it
first connects to a network. followup discussed in the section on exploits.

# simulation

Before starting with full implementation we need to make a simulation with a core of the protocol.
The goal is to validate the system under active exploits, before starting implementation.
Possible test cases:
1. boost rating using low-cost sybils
2. how fast rating will drop if the node stops to provide high QoS
3. devaluing other nodes

# TODO implementation

## reputation system core implementation

## whisper watchdog and changes in whisper API

must be possible to send a message to a single peer instead of broadcast

## protocol for collecting remote ranking

we will have another p2p protocol, to request ranking from peers
it will be probably a simple libp2p protocol, similar to rendezvous
since we use libp2p on our nodes, and it simply easier to implement libp2p
protocol instead of devp2p.

## smart contract to store pre-trusted nodes

we may re-use the same thing we do for mail servers

## interface to interact with payments

# literature

[1]: algorithmic game theory book: a chapter on reputation systems

[2]: reputation system that preserves anonymity https://eprint.iacr.org/2009/442.pdf

[3]: TwoHop https://onlinelibrary.wiley.com/doi/epdf/10.1002/sec.355

[4]: peertrust https://www.it.iitb.ac.in/~madhumita/trust/xiong03peertrust.pdf

[5]: 2017 trust in delay tolerant network
http://www.gsd.inesc-id.pt/~mpc/pubs/mswim33s-magaiaA.pdf

[6]: a robust reputation system for mobile networks 2002
https://infoscience.epfl.ch/record/519/files/bucheggerL04A.pdf