strongest possible reputation system

[synctext]

Idea: strongest possible reputation system by combining all existing science.

Problem: our scientists Rahim, Adele, Nitin and Dimitra did not combine their work.
Reason: optimal publication strategy is one clean and simple idea
There are no joint publications, no re-usage of algorithms and little collaboration.

We evaluated in isolation multiple enhancements to make accounting of contributions stronger and incentive compatible:

• max-flow calculation
• delete old information to reduce storage cost
• depletion of often used paths, provides sybil resilience with additional bookkeeping
• introduce negative trust, these negative edges increase sybil attack resilience
• friendship as an edge property to strengthen the trust overlay against sybils
• age as an peer property to strengthen against sybil attack
• biased random walk, taking into account peer and edge properties
• double signed signature (proof-of-work)
• append-only signatures, misreporting attack degrades it to weaker white-washing attack
• running total account of consumed and contributed resources, degrades misreporting attack
• transfer encrypted information, only provide decode key after proof-of-work is signed
• incremental signatures, reduce risk-taking by demanding signatures during transfer
• use n-hop Max-Path to reduce compulational cost
• reason from betweenness centrality node
• use full gossip

Reputation system proposals often assume either:

1. Tamper-proof and scalable storage of information
2. Scalable storage of information

Option number 1 is beyond the state-of-the-art, without assuming an honest central server with infinite capacity. Option number 2 is difficult to achieve. For scalability seasons, the storage layer will always be imperfect and will never offer both instant, accurate and complete recall of information. Thus we need to be able to tolerate limited accuracy or coverage in addition to the usual misreporting, lying and sybil creation.

A reputations system needs to determine (assuming background gossip of trust vectors):
 1 Who to talk to
 2 how to reach them
 3 What to say
 4 How much to trust

Existing work is focused on no.4 mostly, while the others have proven to be
much harder to solve. Nobody identified them as a problems and no
solutions exist.
Trust calculation is just 50 lines of code, while no. 1-3 is beyond
the state-of-the-art in epidemic protocols.

Missing topics:
3. "what to say", Efficient synchronisation of BarterCast (subgraph) trust vectors

Existing material:
 1. Who to talk to
    Biased random walk
 2. how to reach them
    Churn resiliance, state preservation, live overlay, NAT traversal, etc
 4. How much to trust
   Meulpolder 2008: Max-flow
   Rahim: various sybil-limiters
   Adele: rewards also effort
   Dimitra: betweenness centrality
   Nitin: sybil-limiters

[synctext]

Churn and NAT traversal are critical concepts. All peers keep open connections with several neighbors to fix this. We need an algorithm to traverse such live edges.

[synctext]

This will be moved earlier in the roadmap. Multi-chain will evolve with numerous small steps into this envisioned perfect system.

• append-only datastructure
• payout to seeders
• isolated Gumby experiment with various peers
• visualization of the multi-chain graph
• crawler for dataset collection
• stress experiment generating a million multi-chain records.
• deploy inside Tribler
• payout to hidden seeders and two intermediary proxies (1 private GB : 5 GB of network load)
• ratio tracking inside GUI
• keep-alive to top-N barter partners
• random walk using edge traversal
• peers start collecting barter records
• hidden services biased towards reliable bandwidth providers
• ratio enforcement on proxy requests and hidden seeding

If we go beyond one million users it is possible the database becomes a bottleneck. We will first analyse, modify and tune the algorithms. If this has proven to be insufficient we evaluate libraries such as: overkill approach for billions of edges or Python graph database (inactive)

[synctext]

branching concept
Two main issues with current multi-chain design is the exclusive nature of signatures and the need for a blocksize. We want to get rid of 1) bloat and 2) blocking.

First is the simple addition of compression. Consider the following use case. Two peers exchange 1 GByte of data. Multichain gets very bloated if each 25MByte requires additional signatures and another sequence number in a new record. We can compress entries by allowing two participants to sign the same record with the same sequence number with the same participants, but with a higher amount.
Blocksize matters less when overwriting is allowed, as previous records are replaced. This sadly removes elegance and simplicity, as signing information with the same sequence number no longer constitutes lying.

Non-blocking.
Sequence numbers are no longer unique in this design modification. Each peer keeps a sequence number, but for concurrent events it is re-used. Instead of calling it a double spending attack, we call it "branch racing". Only re-connected branches are valid. We still want to preserve the single-chain per peer design principle.

Show above are thee peers A,B, and C with their Multi-chain records. Their multichain is depicted starting at sequence numbers 21, 3, and 8 respectively. For peers A and B two records are replace with a final 300 / 0 units exchanged, final record between A and C is 64 / 8 units. The key point is that the final sequence number for the B-C record is 5, merging it back into a single main chain.

Requirement for attack resilience: merging back does not require anybodies cooperation. So use a weld-node: point where total up/ down is updated and Merkle hashe of: main branch and side branch is taken. Only signed by owner.

[pimotte]

In my opinion, we should avoid branching at all costs.

The problem we are solving with branching is two-fold: First the blocking issues on timeouts, second the infinite growth of the datastructure.

The second problem can be easily resolved by having some sort of secondary archive multichain. In this multichain, you are allowed to archive a transaction older than X period of time. This transaction will be your new genesis block and others are not allowed to ask you for earlier transactions (so you can delete them).

The first problem can be resolved by scaling the moment of signature request by the bandwith available. Incoming signature requests will never cause a problem for you, only for the other party, if you currently have an unanswered signature request outstanding. Hence, a client should only ask for a signature from someone else, if the probability of receiving another request before receiving a response is sufficiently low. (This can be estimated using simple probability/queuing theory).

[pimveldhuisen]

On archiving:
Does this not make it possible to lie about your history before time X? Or do we intend to base reputation only on the period from now to X? This might be viable if X is sufficiently large, say a few years, but a long history might be useful for Sybil resilience.

On request timing:
A very elegant idea, but I think it is not guaranteed to work. What if there never comes a time when the probability of receiving another request before receiving a response is sufficiently low ?
If a client interacts with N peers at the same time, and these peers are replaced by new peers at a rate of n per minute, the client will need to sign at least n blocks per minute, even if it never signs while a transfer is still ongoing. If the signing round trip takes t minutes, n is limited by 1/t. Let's say a round trip takes two seconds, then n is 30 new peers per minute. There is a sort of load balancing by making busy nodes do the relatively cheap responding and the quiet nodes the relatively expensive requesting, but this n peers per minute limit is still there on average. Question: is this a viable limit?

[pimveldhuisen]

Alternative concept: half-signed only, or optimistic requesting

Another way of going around the blocking problem is to base the chain on only half signed blocks.

1. You note down your interaction in a block and sign it.
2. You can then base your next block on the hash of only the block with your signature. This means there is no blocking.
3. You request your peer to sign the same interaction in his chain. For him too, there is no blocking.
4. The peers sends his block back to you, giving you irrefutable evidence of the interaction.

The peer can refuse to create the corresponding block on his chain, but this is no different from him refusing to sign your block. You can add fake blocks to your own chain, but without evidence they are not valid.

[synctext]

ToDo: merge major/minor seq idea, half-signed+revert.

[Captain-Coder]

In a session with @synctext, we discussed the half-signed only and branching options. He was especially concerned about having the vertical compression (updating transactions) and the difficulty with the reuse of sequence numbers. This could be solved by introducing a minor sequence number.

(Alternatively you could accept a gap in the sequence numbering, as long as it is not decreasing. It's the hashes that provide the real linkage anyway. Same result, you never use a sequence number twice.)
But what do you do if one of the partners suddenly goes offline (or refuses to sign your next block)? Lets say C refuses to sign the last block in this example. @synctext noted that it would be possible to have A update its last block to refer to the last block of the B-C interaction. Resulting in this graph:

This saves you from having to forgo all the credit from interaction B-C. Note that A will only update the block if it is still the head of the chain of A for obvious reasons. If A is not able to cooperate then you have to accept that one of the branches cannot continue. Probably the one with the smallest credit.

I'm thinking that nodes will have to be fair and open about all this parallel stuff and allow that "unmergable" transactions and any replaced/overriden blocks be harvested by a crawler. Because what if C secretly decides to use 3.1 or 4.0? It would look bad if B denied any knowledge of this block.

Also this would still combine with PimV.'s half-signed as default proposal.

[synctext]

design dream 1: if you do not follow the protocol, you never get any of the benefits.
design dream 2: protocol violations by design result in an irrefutable "proof-of-misbehavior".
design dream 3: double spending attacks are easily detected afterwards (prevention==costly).

branching: signing a certificate with the same sequence number (major+minor) constitutes a double spending attack, instant banning. An elegant and easy mechanism. This is the key reason for sequence numbers, they become a coin that can only be spend once or represent 1 truth. Append-only ensures any record freezes past behavior. A single record represents an exact position in the chain, impossible without sequence numbers.

[pimotte]

The whole problem with having any branching option is that the "design dream 2" mentioned above is lost. The fact that a client has multiple branches means that they cannot be forced to rebase or merge it back into their main branch. This means that there exists a "sidebranch hiding attack", in which a client cannot be forced to divulge a side-branch existing. To make up for this, there would need to be some mechanism that forces user to merge or rebase branches. However, this means that proofs of misbehavior get much more convoluted.

My proposal for the compression is to be fairly lax with sending signing requests, scaling blocks with both the number of interactions with that person and the bandwith of the originator.

If this during the experimental phase turns out to yield too much growth still, or too many unsigned/dropped transactions, because of the block size, I would be in favour of exploring a secondary datastructure where we consolidate some of the information. But I would like to see if the compression is an actual problem before moving towards those kinds of solutions.

[pimveldhuisen]

For the alpha version of multichain:

• Do not use branching: the costs seem to outweigh the benefits
• Non-blocking multichain: base your chain on the hash of only your fields. Collect the other half as evidence
• Sign a block for the remaining amount on the closure of the circuit