master thesis placeholder - decentralised learning with security and unbounded scalability

[synctext]

Grades for With Honor graduation. So focus on a full scientific thesis. Graduation Fri 7 July 2023?

Brainstorm {proudly copied from Rohan issue}. Current main idea:

• Web3Trust: finding truth in a sea of misinformation
  • Search algorithm: user searches for a certain hashtag, goal is to find relevant items
  • Different focus, not machine learning, but trust, fraud, and spam.
  • Not so simple trust-aware model: items have an association with multiple tags. Users crowd-source these associations of items and tags. Items have a certain popularity with users, influencing their relevance ranking. Finally, users have a position within the user-to-user trust graph. It is possible that the majority of users is evil and actively spreading false tags and misinformation. essence: assume the majority is evil. then solve, good luck 🤞
• First papers to explore here: https://scholar.google.com/scholar?q=trust+framework+and+reputation
  • Realise that Big Tech creates these things and never shares their tricks
  • Thousands of the worlds best developers work in secret on secret algorithms to decide what is quality and what is spam, fraud, or misinformation.
  • Academia is underfunded and has no deployment after 20+ years of trying. Except for Tribler obviously 😁
  • ConTrib: Maintaining fairness in decentralized big tech alternatives by accounting work
  • strongest possible reputation
  • the pioneering 2001 paper
  • Work towards something like this: Towards global Consensus on Trust #3357 (comment)
  • as early as 2001 it was published we need some sort of point system against freeriding, the Tribler lab tried to unify the idea of trust building and freeriding prevention.
  • huuuge overview of trust as investigated in multi-agent community. Useful as a warning! This community explored lots mechanisms which are impossible to automate, let alone our requirement for a friction-less mechanism for building trust.

Other directions for inspiration:

• fundamentals of Web3: evolution of cooperation against monopolies, surveillance, and misinformation
  • understand the German Math from the lab by an actual mathematician
  • The most scientific line we have: evolution of cooperation
  • Mathematical proof of something under all possible attacks
  • Web3 architecture with an evolving formula to decide if agents are good or evil. (or gullible)
  • possible idea: some peers helped you and helped others, you trust them more.
    • Essential data structure: work graph {which agent helped another agent}
    • Work graph is also subject to attacks, misreporting, lying, slandering, white washing, Sybil attacks, etc.
    • Graph of trust is build up when you see helpful. Graph walks, exploration, discovery.
    • Preferential treatment of most trusted peers
    • Within a network of untrusted peers you discover trust vectors for trusted services.
    • Alternative idea: peers with same preference for items (similarity graph)

OR

• Foundations of Web3 search with fraud, misinformation, and lawyer attacks.
  • See prior work on Tag-based navigation with Web3 zero-server context by the lab from 16 years ago
  • Prior federated ML work from lab
  • Search algorithm: user searches for a certain tag, goal is to find relevant items
  • Focus on the Web3 machine learning part.
  • Define a good gradient decent approach, without sharing private info. For instance, ClickLog data.
  • Overlap with msc student on learn-to-rank {not a problem, just awareness, problem big enough for team of students}

OR

• Quantification of decentralisation of Web3 and the old age of P2P
  • All Web3 solutions have full central control or central servers
  • Nice nostalgia assignment
  • Nobody cares!
  • Great formulation of {Web3} challenges by Prof. Verborgh:

Imagine a large and complex knowledge graph that cannot be stored in a single place, because of a variety of reasons
(practical, societal, legal or other). Instead, this knowledge graph is spread across multiple sources; perhaps to the
extent that every person has their own space where they store their own data. And there is no coordination of which
data is stored where, and how data is exposed. This is what we call a _decentralized knowledge graph_.
An additional complexity is that each piece of data in this graph can have different permissions associated with it:
not all data is public, and some of it can only be read or written by certain people.

OR

DAO cryptoeconomics. Warmly recommended is this cutting-edge of science stuff:
https://brian2509.github.io/test-123213/thresh-hold%20signatures/frost-implementations/
== crypto for creating an leaderless organisation scaling to billions of people and billions of treasury money.

First step: literature survey. Example from a while ago. 24 Oct target finish (start thesis 2 weeks early)

[ThomasWerthenbach]

I have read through the existing papers, and am still of the opinion that trust in web3 is still my favorite direction. Over the last two weeks, I have spent much time looking for related work and have composed a self-use document in which all relevant papers I have read are stated and briefly summarized for later use.

The papers I have found can be divided into the following sections:

• Existing trust mechanisms (mainly based on trust in an entity)
• Sybil attack defense mechanisms
• Trust in general
• Monitoring spread of misinformation
• Methods of extracting a trustworthiness value from resource content
• Trust graphs

After having read the papers, I, as of now, do not know of any work where the user is capable of frictionlessly experiencing trust in web3 based on resource content alone. Many existing algorithms are based on the notion that agents can perform work for each other, and it can automatically be checked whether this work was actually performed. For resource content, the solution is not so trivial, as computers can not be trusted with automatically scanning content and determining its trustworthiness. The following methods have been proposed:

• Use links to other pages (good pages do not point to bad pages), but this would result in a directed graph on which it may be inefficient to calculate trustworthiness. Another issue is that not all good pages are referenced by other good pages.
• Mapping the trust from the tagger to the tags. If the tagger can be trusted, then the tags they have set can also be trusted. If the same tags have been applied many times to a certain by trusted taggers, the more likely it is that this tag can be entrusted to said resource. This solution may work using a trust graph, but does not solve the underlying problem: real users will still need to assess resources and now not only indicate whether they trust some content, but also assign tags to these. Users will also need to specify which taggers they trust.
• Use Machine Learning to detect trustworthiness. This can be optimized by making some assumptions, such as: images containing text are likely to be spam. It is however hard to determine how effective this method would prove against content on topics the ML model was not trained upon (e.g. a news article about a new global crisis).

One of my own ideas (brainstorming): Use the duration spent accessing a certain resource as a metric to determine trustworthiness of a resource for a specific search query. Not much work has been performed on this method, but it does come with a few serious drawbacks:

• Sybil attacks
• Requires a 'session' to determine the amount of time spent accessing a resource (instead of just retrieving a resource once).

I have more similar ideas, but they are all prone to Sybil attacks or require the notion of a 'session'.

Another thought: if we were to use a trust graph, true information might be classified as unreliable due to its distance from the user in the trust graph. Also, how does the user indicate who to trust? This can only be built dynamically if the user provides feedback on whether articles are trustworthy (AKA not friction-less)

Work document:
Literature_survey__explorate_literature_work_document.pdf

[synctext]

Web3 with a trust framework for good, evil, truth, and misinformation

Web3 platform information and finance are under continuous relentless attack. We craft a future-proof architecture for trust in Web3.

One method (find source) to measure trustworthiness, is by measuring time spent accessing certain resources. For a given query, trustworthy resources will be accessed for a longer amount of time than untrustworthy resources. [...] Connect trustworthiness value to search query, such that people looking for untrustworthy information will still be able to find it, as it may be considered trustworthy for a given query.

We present the first first frictionless Web3 platform which autodetects trustworthiness based reports by strangers. We combine a privacy-first method for detecting content attention, peer-to-peer collaboration, explicit user feedback on misinformation, the user-to-user trust network, and use this to asses trustworthiness.

ToDo: try to make an axiomatic model of your model
Related: ATRank: An Attention-Based User Behavior Modeling Framework for Recommendation
Measurement: Youtube has deeply flawed autodetection: "The way that YouTube and a lot of platforms operate is they rely a lot of passive data collection in order to infer what your preferences are"
HN discussion on Youtube broken search; seems thesis topic "Web3 videos search" is unsolved.

Idea: to solve Sybil attacks the only thing we actually need is is "reputation staking". Users putting their own reputation on the line when claiming that a certain profile is real "I know this real person! this is not a fake identity". Instead of a social graph we have a "validity-of-personhood" graph. Mechanism to implement could be tamper-proof recording of "invite code sharing" and invite code acceptance. Could be thesis focus, dropping the tag complexity.
Social Turing Tests: Crowdsourcing Sybil Detection

[synctext]

Tried to look online for you for more broader perspective on Web3 trust. This is 2019 ML stuff with theoretical grounding: Privacy Risks of Securing Machine Learning Models against Adversarial Examples.

Analyzing Federated Learning through an Adversarial Lens All by Patreek Mittal from Princeton: PAC-learning in the presence of evasion adversaries and 2022 work: Formulating Robustness Against Unforeseen Attacks

[ThomasWerthenbach]

This iteration I spent mainly on reading more papers and made a start on the literature survey itself (see attached document).
I deliberately kept my approach to web3 trust somewhat broad, as we have not settled on a fixed thesis direction yet.
The current plan is to look at existing trust mechanisms and sybil defense mechanisms. It will also contain comparisons of different mechanisms and possible matches between sybil defense and trust mechanisms. Furthermore, we also define a common set of data structures to which all related works are mapped to ease comparison (e.g. we only define 1 trust graph structure to which all discussed mechanisms using trust graphs are mapped).

The idea of "reputation staking" seems very interesting. Although it makes me wonder:

• How should people gain reputation, which they can then put on the line?
• How can we make this frictionless?
• Should we infer content reputation directly from the reputation of the entity that provides the content?
• How are fake entities detected?

The linked paper on social turing tests relies on a workforce actively checking entities, whereas we do not have such a trustworthy workforce (assume everyone is malicious).

I am not sure about the papers on ML stuff (ML is not my forte), although I could consider leaving the hardcore ML outside the scope of this thesis and work solely on trust between cluster nodes.

Take the attached document with a grain of salt, as it is merely a work document at the current stage.

Literature_survey.pdf

[synctext]

• UK GOV: How to accept a vouch as evidence of someone’s identity. Insightful part is the: Accepting a vouch as evidence an identity has existed over time
• Vouch-based system: Innocent by association: early recognition of legitimate users
• Sybil in 2022: Total Eclipse of the Heart – Disrupting the InterPlanetary File System
  
• Reminder: you did not find this classical reputation overview and have large overlap with this 2009 article A survey of attack and defense techniques for reputation systems
• In Google we trust!?
• Structure by "Attacks & Defenses", scientific problems, literature taxonomy, existing industrial approaches, or potential directions for collective solution: to re-invent The Internet.
• One of 27400 papers about reputation systems on Scholar.google (now with Web3 favor): The Case for AI Based Web3 Reputation Systems
• reputation systems for open collaboration
• ideas for solution from Tribler lab
• What direction to take?
  • the final overview with a survey of surveys of trust and reputation
  • Specialise: DAO "reputation system"
  • You are engineer !! Solution-focused direction 🚜
  • Most fertile directions for solving the misinformation crisis (e.g. re-inventing The Internet)
  • The design space is finite, use social,political,economical,legal, and technology to box-in any attacker. Simple.
    • build web-of-trust
    • duplicate social graph, SybilGuard: Defending Against Sybil Attacks via Social Networks
    • cost of initial identity
    • social capital accounting
    • assume long-lived entities, assume long-lived identities, assume we can detect defection, report misbehaviour globally
    • five rules for the evolution of cooperation
• prior work from TUDelft student from 4 years ago, commercial systems and academic work

[ThomasWerthenbach]

On using vouching in reputation mechanisms: I have read the document by Microsoft on their vouching mechanism. However, that work is not focused on a decentralized setting:

First, existing Sybil defenses are generally designed for decentralized environments, where each user would like to independently determine the legitimacy of a small set of other users. In such a setting, the knowledge of an existing good user who wishes to perform Sybil tests is a given. On the other hand in our scenario, we would like to identify new legitimate users based on a collection of unclassified users.

A possible model I thought of, which supports web3 deployment, might include the following axiomatic properties:

• All reputation changes of all entities are stored on a decentralized tamper-proof ledger.
• If some node A vouches for some node B, the reputation of B increases by R_A * c, where R_A is the reputation of node A and c is some constant 0 < i < 1.
• Every reputation change has a source which is the node responsible for the reputation change, i.e. if A vouches for B, B gains reputation due to A's action, thus B's reputation change has source A.
• There exists a global constant d, which defines the amount of hops reputation can propagate. This implies that if some node J is transitively vouched for by node K, but the distance between these is larger than d, the reputations of node K and node J are independent. Another implication is that every node has a dynamic work graph which contains all nodes within a distance of d hops which may affect their reputation, or which reputation they may affect.
• All nodes start with some global reputation constant larger than 0.
• Nodes that have been exposed get a reputation of 0.
• Vouching happens friction-less (e.g. sending a message).
• If node A (transitively) vouches for node B and R_A increases, R_B increases by R_A * c / (distance + 1) iff the event causing the reputation change is within a distance d from both node A and B.
• If node A (transitively) vouches for node B and R_A decreases, R_B decreases by R_A * c / (distance + 1) iff the event causing the reputation change is within a distance d from both node A and B.
• If node A (transitively) vouches for node B and R_B decreases with some value L_B, R_A decreases by L_B/(distance + 1) iff the event causing the reputation change is within a distance d from both node A and B.
• If node A (transitively) vouches for node B and R_B increases with some value G_B, R_A increases by G_B/(distance + 1) iff the event causing the reputation change is within a distance d from both node A and B.

Some related work:

• Surfing a Web of Trust: Reputation and Reciprocity on CouchSurfing.com
• Innocent by Association: Early Recognition of Legitimate Users
• Who Watches the Watchmen? A Review of Subjective Approaches for Sybil-Resistance in Proof of Personhood Protocols
• VoteTrust: Leveraging friend invitation graph to defend against social network Sybils
• The Sybil Attack in Sensor Networks: Analysis & Defenses (briefly talks about it)
• Fourth-factor authentication: somebody you know

Idea: the possibility of a 'negative vouch': I am will to put some of my reputation at stake by saying that this person is not real. Although some incentive may be required for 'vouching negatively'.

[ThomasWerthenbach]

Another idea. Less complex and (as far as I know) unexplored approach adopting a vouch graph:

• Nodes can vouch for other nodes (can happen frictionlessly).
• If some node A wants to verify the reputation of node B, they verify if a directed vouch path exists, if it does not, node A does not trust node B.
• If such a path does exist, node A will pseudo randomally select c nodes on the path from node A to node B to perform a computationally expensive task. If this task is not performed, the refusing nodes can be exposed. This node must now be isolated from the network. All nodes that vouched for this node will be punished and need to perform the computationally expensive task, causing malicious networks to burn.
• Need to find good value of c depending on path length.
• Need to find good computational task, such that it is not too easily computed nor too difficult: what happens when popular nodes get selected too often (maybe ask one of the nodes that vouches for them or for which they have vouched to complete the task???)
• Choice of nodes to perform computationally expensive task may be influenced by the amount of time a vouch has existed (if a vouch has existed for longer periods of time it is more likely to be trustworthy?).
• We can temporarily exclude nodes from network in case of a timeout???

Or, instead of the nodes that have vouched for exposed nodes having to perform the expensive task themselves:
if a node is exposed, all nodes that have vouched for this node lose their vouches.

[synctext]

tip: deep analysis of why academia failed and only industry succeeded ?

[Dmole]

Related; #3657

[ThomasWerthenbach]

This iteration was spent mainly on (re)writing the literature survey. I have also read some more papers and plan to continue expanding on the current literature survey.

Thoughts/discussion points for next meeting:

• I have defined a framework to decompose and present the core components of a reputation mechanism, currently consisting of: general strategy, mathematical foundation, resilience. During the lab meeting, Johan briefly mentioned complexity. I am still considering to at this one (and maybe merge resilience with general strategy).
• I plan to eventually include at least 7 or 8 reputation mechanisms and extensively describe them (as already done with PageRank and MeritRank).
• I am not yet 100% sure what to include in the background. The current placeholder describes how big-tech can and should not be trusted with the responsibility for creating trust, but I am not sure if this fits well in the context of this survey.

Current progress:
Literature_survey.pdf