transitive trust based on blockchain constructs

[synctext]

PhD Thesis direction

By using the learn-by-doing methodology we will create a transitive trust solution.
Specifically we will design, implement, deploy, and incrementally improve transitive trust solution using our own append-only TrustChain solution.

Steps and dependancies:

• True halves MultiChain true halves #2135
• live edges Multi-Chain live edge traversal with random walks #2458
• Gumby test coverage and deployment
• Remove Bloom filters and use Live Edge walking + record record + growing interval construct
  
• Creat N-Hop-Sync across TrustChain to replace Full-Sync that fails to scale.
• Move TrustChain down from community level to replace discovery community. First, cut Dispersy into two : Dispersy mini: Dispersy no longer stores any data in databases #2778
• Repair scalability of AllChannel with N-Hop-Sync

[pimveldhuisen]

Some work on live trust edges based in dispersy MultiChainCommunity, can be found on this branch:
https://github.com/pimveldhuisen/tribler/tree/trust-edges
Corresponding with this gumby branch:
https://github.com/pimveldhuisen/gumby/tree/trust-edges
And this DAS experiment:
https://jenkins.tribler.org/job/Tribler/job/Experiments/job/multichain/job/trust-walker_das/

[qstokkink]

Live edges rebooted and integrated.

Live edges implementation:
https://github.com/qstokkink/tribler/tree/live_edges
Live edges gumby experiment:
https://github.com/qstokkink/gumby/tree/live_edges

W.I.P. Visualization of trust based walks (Gumby experiment):
Getting some outside interference.

UPDATE: Live edges integrated:

[qstokkink]

Isolated 1000 node DAS5 experiment is now up and running:

I am still contemplating the right way to present this data. The above network graph is kind of messy.

[qstokkink]

I spent yesterday creating an R package which allows me to easily make animated png files. This allows me to more easily visualize the evolution of a network in an automated manner. (Plus, animation is great for propaganda purposes)

https://github.com/qstokkink/apng

[qstokkink]

Fun update. My animated png R package is now part of the official R package repository: https://CRAN.R-project.org/package=apng

[synctext]

in R..

epic!

[devos50]

Nice! I've used your R script (with some modifications) to plot the transactions in my decentralized market experiment:

[qstokkink]

The first (windowless/window size of 1) integration of UTP in Dispersy is now up and running: https://github.com/qstokkink/gumby/blob/utp_community/experiments/utp/utp_community.py

[synctext]

solid progress.
is there a protocol for 1UDP versus n-uTP transfers?

[qstokkink]

@synctext If I understood your question correctly, you want to know if multiple uTP transfers can be multiplexed over one UDP connection. If so: yes, you can have multiple uTP connections over a single UDP "link".

[synctext]

When two peers talk, do we have a protocol for indicating this is a single UDP Dispersy message or we now start setting up a uTP connection?
How to close? timeouts?

[qstokkink]

@synctext It is a single UDP Dispersy message, this makes it backwards compatible and allows it to make use of some of the Dispersy information shipped with it, without compromising the pure uTP protocol. The uTP connections are built on top of this Dispersy message.

The extra information we can use, is the member we are exchanging information with. This guarentees that there will be no connection_id collisions, so you will never accidentally (or on purpose) get someone else's data.

Closing the connections is done using the normal uTP ST_FIN message. In the worst case it will time-out (implemented with Twisted to avoid rogue threads and the like).

The interface for this functionality is as simple as:

community.send_utp_message(candidate, data)

The implementation will then take care of setting up a connection and closing it once the data (a string) has been sent to the candidate.

Another possible use of this, is sending Protocol Buffers messages of arbitrary size (no longer restricted to a single UDP packet).

[synctext]

nice.
So what we want as a perfect API is protocol buffer wrapping with uTP transfer. I guess. But still we want statistics for a basic progress bar when a large binary blob is received.

[qstokkink]

@synctext Sure, we can hook in progress statistics for the sender and the receiver without any issues whatsoever.

Also: I hooked up windowing and retransmissions today. Once I document and clean the code a bit, Dispersy-uTP is ready for shipping. I'm looking forward to the thumbnail implementation 👍

[synctext]

nice
another key usage is magnet channels. We want to enable Tribler channels like:
https://www.youtube.com/user/CODblackopsPS
1+ million posted videos... At 100Bytes per video, a big channel blob... 100MB..

[qstokkink]

Somewhat unrelated: for fun, I implemented auto-googling for thumbnails of suggested torrents and channels today. 90% of the time the resulting thumbnail is actually pretty good.

_{That one thumbnail will haunt me for the rest of my life.}

[synctext]

related work
Real-Time Operationg system for Robotics with publish/subscribe, messages, and other great pieces of technology in distributed systems. Inspiration example of how good documentation is made. Makes us look like absolute amateurs :-)
Define the top-level concepts plus all related topics in one consistent place and a final technical overview with proper code snippets.
Another example of appealing looking docs.

[qstokkink]

@synctext Functionally Dispersy can actually do more than that. The only thing we are missing in Dispersy is the fancy Arbiter system (which are pretty much Dispersy communities in disguise)* and TCP connections. However, as far as I can see, the user needs to set up his own TCP NAT rules in ROS; so no fancy TCP puncturing/hole punching in ROS either.

As far as docs go: touché, point taken. Their documentation is lightyears better than ours.

* Actually, we could even build such a system on top of the communities.

[qstokkink]

Alright, the uTP infrastructure has been refactored and documented (reminder: here) and is available for deployment once we need it.

I will now move on to peer rediscovery/repuncturing. This will open the doors for all of the more fancy goals we want to achieve.

EDIT: Instead, the focus will be to get the live_edges merged into Tribler/devel for the 7.1 release.
TODO list:

• Only share last block when walking
• Active keep-alive for nodes on edges

Here is an overview of how the live edges implementation hijacks the default Dispersy messages (live edge traversal -like teleporting home- is not captured in this diagram):

Note that the way the live-request, live-response and keep-alive are created is BACKWARDS COMPATIBLE and allows for INTRINSIC BOOTSTRAPPING. Also (not visualized here) the keep-alive is BIDIRECTIONAL.

The only reason the last block is not added onto the introduction response, is for fear that the message might get to big for an UDP packet to handle. One further implementation detail, is that the keep-alive timeout is now 60 seconds instead of the original design's 5 seconds: this can be changed at any time.

[qstokkink]

I'm starting the roll-out of live edges:

• Dispersy PR - Added keep-alive option to WCandidates dispersy#548, status: MERGED
• Tribler PR - Live edges #2979, status: MERGED
• Gumby PR - code done, status: cleaning code/commit history

[qstokkink]

While the live edges are being reviewed etc. I will move on to the n-hop-sync. The design is as follows:

n-hop-sync

Extend functionality of CommunityDestination:

• Instead of just having a fan-out for sharing this message (called node_count now), a depth parameter is added to determine (you guessed it) the sharing depth in the community.
• [Implementation detail] When a CommunityDestination is decoded from the wire-format its depth is decremented, when it is forwarded (see Dispersy._forward()) it is checked if the depth is greater than 0.

n-trust-hop-sync

At this point I will probably be fed up with the fact that the destinations are hardcoded and refactor the destination selection code into the Destination class, where it belongs. An extra Destination class will be created (called TrustDestination?) subclassing CommunityDestination, which will query the associated community through some get_trust() function to determine the candidates to send to. Actually, we can supply a candidate list to the CommunityDestination which just so happens to consist of our trusted candidates.

Status

• n-hop-sync PR - Added hop depth to CommunityDestination dispersy#551, status: MERGED
• n-hop-trust-sync PR - implicit through live edges PR

[synctext]

Inspiring animations for live edges and graph sampling: https://bost.ocks.org/mike/algorithms/

[synctext]

Related work on secure pairing, trust and discovery + remixing: https://github.com/solatis/bitgloom

[synctext]

More docs and related work on the Privacy+self-sovereign ticket: #3013 (comment)

[synctext]

Learning trust strategies in reputation exchange networks

This research proposes a method by which agents can learn trust
decision strategies using a q-learning technique. Q-learning [15]
is a well-known tool for learning best decision-making strategies
by associating actions with expected rewards. Several researchers
[3, 4, 9, 13, 19] have employed reinforcement learning techniques
to discover strategies for trust decisions. However, these trust
decisions only relate to fundamental transactions, as in the
Prisoner’s Dilemma [2]. Learning trust decision strategies in
reputation-transaction systems is significantly more difficult,
since in these systems, fundamental transaction decisions are not
independent from each other and from reputation transaction
decisions. An agent’s fundamental transactions with one partner
may influence its fundamental transactions with another, if its two
partners are able to communicate reputation information.
Learning an agent’s trust decision strategy is also complex
because multiple decisions can affect common results. For
example, falsely spreading negative reputations about a
trustworthy partner might cause other agents to trust the lying
agent while isolating the falsely accused agent.

[qstokkink]

Here's another (more up-to-date) list of Blockchain identity systems: https://github.com/peacekeeper/blockchain-identity

Also people are apparently starting to catch up to our ideas:
https://link.springer.com/chapter/10.1007/978-3-319-67816-0_21

[synctext]

We might have an alternative algorithm to find the non-sybil region of Trustchain by using an NP-hard graph search algorithm. That introduces the trust-mining concept for our internet-of-trust.org work. The maximum k-cluster in a DAG might indicate the largest honest region. phantom algorithm was presented by researcher Yonatan Sompolinsky at BPASE'18 event (.pdf not yet online). His earlier work on DAGchain: "SPECTRE: Serialization of Proof-of-work Events: Confirming Transactions via Recursive Elections".

[synctext]

Great Princeton work: SybilFuse: Combining Local Attributes with Global Structure to Perform Robust Sybil Detection

[synctext]

University College London: "Decentralizing Public Key Infrastructures with ClaimChains". Very similar design idea to our deployed technology; has Merkle tree and fancy skip list for efficiency. https://claimchain.github.io/

A ClaimChain consists of blocks, each block containing
all the information necessary to represent the claims of
one user about her own keys, and her beliefs about other
users’ ClaimChains (which we call cross references).
Users can access each other’s ClaimChains and combine
these beliefs to support the provision of evidence about
the binding between identities and keys. We note that
the design of ClaimChains could handle any generic
claims about user beliefs. However, for the sake of simplicity,
in this document we restrict ourselves to the
context of key management for messaging applications.
A core goal of our design is to support full decentralization.
Yet, ClaimChains are flexible in terms of
deployment.

[qstokkink]

This issue has been superseded by other issues. Live edge walking has been in Tribler for over a year now and there are other issues for trustworthy gossip.

[qstokkink]

Post-mortem: trust-based walking was a very bad idea.

[synctext]

Post-mortem2: load-balancing needs to be maintained when doing non-random walks! Trust introduces a strong bias. Destructive and leads to overloading of highly-trusted nodes in a power-law setting or complete neglect of low-trust nodes.