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

[synctext]

idea of an internet neighbourhood in which you are born. Inspired by evolution of cooperation, the social, biological angle with vouching, friends, "social capital" [ref], blood-ties, merit, and hometown. Other angle is the commercial reputation angle with rationality, slander, fake identity and fraud.
In scope? "Gossip and Ostracism Promote Cooperation in Groups"
See how many surveys there are currently: https://scholar.google.com/scholar?q=%22survey%22+trust+and+reputation
Angle: Someone told me I can trust you: a social reputation mechanism survey

Edit: this old paper from 2003 on trust in online shopping has been cited over 10000 times! See excellent related work table going back to 1967.

[ThomasWerthenbach]

Final version of literature survey

I will spend the coming week mainly on focusing on a more specific model/algorithm for the thesis until our next meeting (which is also the kick-off for the master thesis).

[synctext]

Related work: This paper introduces a novel and economical protocol, entitled KarmaNET, which binds any routing protocol with trust to build a trusted social path and create judicious forwarders. This creates incentives for nodes to build good karma, and excises any node that has accumulated too much bad karma.

btw: quick reading feedback.. Table 1: please add year column. Plus also "something deep sciency" like:

Titles sadly need to be boringly clear: Survey on social reputation mechanisms: Someone told me I can trust you
Seriously: 😲 no figures or illustrations? 0️⃣ Not even a social network picture?
1992 related work, PGP COMPLETES_NEEDED == Number of Completely Trusted Introducers Needed and CERT_DEPTH - How Deep May Introducers Be Nested

More in-depth comments:

• Axiomatic model for your vouching (2 oct comment derived)
  • Social graph. Users which known other users {user-to-user trust matrix}
  • users have long-lived private identities with selective disclosure.
  • Users prefer certain items {formerly known as ClickLog; very private}
  • Items obtain trustworthiness, discoverability, and relevance ranking through other trusted users
• start with an overview model (spoiler of your storyline)
  • "Overview of all social reputation mechanisms discussed in this survey"
  • Core feature of as column. PageRank example: "The underlying assumption is that more important websites are likely to receive more links from other websites. Count incoming links and their quality."

Year	Trust model name	Trust model definition
1999	PageRank [4]. The underlying assumption is that more important websites are likely to receive more links from other websites. Count incoming links and their quality.
2011	Trust by association (TbyA) [7]
2015	SocialTrust [8]

• explain your taxonomy and define. Zero-social, social graph, and binary group membership.

• your vouching model: boost of reputation of unlimited many others, but you have strictly limited incoming vouching power; plus path decay; therefore there is a bound and Sybils are weakly beneficial {very informal}

• broad view: "Trust and reciprocity: Interdisciplinary lessons from experimental research"

• Master thesis idea: design of vouching-based algorithm, implement, deploy, measure, and evaluate ???

  • Frictionless
  • Android address book
  • Bootstrap privacy-first social graph
  • Discover your online friends, using social O(1) DHT stuff?
  • Our 2016 running code: https://research.tue.nl/files/3524712/Metis255949.pdf
  • A 1 month mathematical proof of Sybil tolerant, against weakly beneficial Sybil attacks.

[synctext]

Related work:
We show how nodes expressing their trust relationships through the ledger can bootstrap and operate a value system, and general transaction system, and how Sybil attacks are thwarted. We empirically evaluate our system as a secure Federated Byzantine Agreement System

[llegard]

"The Alchemy of Trust: The Creative Act of Designing Trustworthy Socio-Technical Systems"

When designing a system with multiple stakeholders in their multiple contexts, how does one decide which trust model(s) to apply? And furthermore, how does one go from selecting a model or models to translating those into design? We review and analyse two prominent trust models, and apply them to the design of a trustworthy socio-technical system, namely virtual research environments.

https://dl.acm.org/doi/pdf/10.1145/3531146.3533196

[ThomasWerthenbach]

Latest version of literature survey (would like to start focusing exclusively on thesis):
Literature_survey.pdf

Latest vouching model:

• Vouches need to be accepted by both parties.
• For two nodes to interact, a vouch path must exist connecting the nodes (in any direction).
• There exists an upper bound on both the amount of incoming and outgoing vouches.
• Vouches are permanent (tamper proof ledger?)
• Reputation can be calculated using the following recursive formulae:
  $$R(i) = U(i) + c \cdot \sum_{j \in i_{in}}R_i(j) + d \cdot \sum_{k \in i_{out}}R_i(k)$$
  $$R_{path}(i) = U(i) + c \cdot \sum_{j \in i_{in} \setminus path}R_{path + i}(j) + d \cdot \sum_{k \in i_{out} \setminus path} R_{path + i}(k)$$
  where:
  • $U(i)$ might be either an underlying reputation mechanism or a function returning 1, i.e. $U(i) = 1$.
  • $i_{in}$ and $i_{out}$ represent incoming and outgoing vouches of node $i$, respectively.
  • $0 &lt; c &lt; 1$ and $0 &lt; d &lt; 1$ and $c &gt; d$ (receiving a vouch is worth more than vouching for another.
  • $|path| &lt; s$ (only nodes within distance s can affect you), where $s &gt; 1$.
• We assume the existence of a Sybil detection model.
• When a node is discovered to be a malicious node, their reputation is multiplied with $f &lt; -1$. As vouches are permanent, the parents are directly affected. (stored in tamper proof ledger?)

Nice points:

• There is an incentive for vouching, as both the voucher and the vouchee gain reputation.
• Nodes are punished when discovered to be malicious.
• It is difficult to create attack edges, as both parties need to accept a vouch and should leverage the risk of the other party being exposed as malicious.

Not so nice points:

• The strength of this reputation mechanism is heavily affected by the strength of the underlying Sybil detection model.
• While there exists an upper bound on the amount of reputation one can gain, smart adversaries launching a Sybil attack can still gain notably high reputation within the Sybil region if we assume that $U(i) = 1$.

Other remarks/observations:

• As vouches are permanent, and the amount of incoming and outgoing vouches is limited, users need to think thoroughly about their vouches. If a nearby node is exposed as malicious, it is not so easy to create a new node/account as you can likely not reconnect with the same users (as they also have a limited amount of vouches). Therefore, if one wants to be able to instantiate the same vouches again, except for with the malicious node, all neighbours will need to create a new node/account and therefore, recursively, the entire network.

Possible improvements:

• Use MeritRank-inspired transitivity decay for punishing separate components, requiring the existence of multiple attack edges. However, such attack edges are difficult to create as both parties need to accept a vouch.

Open questions:

• How to deploy this model?

[synctext]

• quite polished, good stuff 🎉

• Figure 2. shorter "PageRank example with 2 algorithm rounds." numerical example within survey text itself

• Only minor mistakes: "table 1".

• Foundation for this conclusion: "Nowadays, this responsibility of creating trust cannot be entrusted to private corporations." is 1 Google example? 'Lawmakers from the US House of Representatives accused Facebook, Amazon, Google and Apple of "abuses of monopoly power" in a 449-page report'

• "2. Background and "3 Definitions" are not informative, suggestion: proposed trust models. "definitions and terminology", "4. individual"; "4. Personalised reputation calculations"

• It lacks a deep insight or new knowledge. It simply lists social trust.

• Brainstorm... Survey-of-surveys table...list a few of the successful industrial mechanisms:
  

• Your master thesis, your choice. But reading this algorithm and how it could possible work in an application, I'm sceptical this is useful work. (2 weeks investment/learnings)

• Main drawback of Vouching is the significant social friction. You need to have friend inside the system. This is a crippling pre-condition for system growth. Possibly theory-only thesis 🗑️

• 15 December: soft deadline for a 3-6 lines of problem description with draft thesis title. in IEEE.tex format already

  • Federated Machine Learning {for MusicDAO}
    • Prior master thesis
    • censorship-resistant machine learning
    • unstoppable machine learning
  • MeritRank with freedom-of-computing
  • ThomasRank {MeritRank improved}
  • MeritRank deployed MusicDAO {cmdline script with sybil attack. try and learn}
  • Something with optionally using telephone adress book for enhanced security ???

[ThomasWerthenbach]

Proposed direction:
Look into a new part of decentralized federated machine learning where we abandon privacy and focus on collaborative machine learning. We assume the existence of a public dataset (paper citation network?) OR peers are willing to share their data. Peers then train their model in a decentralized federated manner on (a part of) the dataset and aggregate their model with the models of peers. Reputation mechanisms play a large role in these interactions and Sybil attacks are a huge risk, this is where MeritRank may come into play.

Additional 'nice to have' features:

• Use the increasingly popular notion of transfer learning and aggregate models using a method inspired by the performance-based integrator by Joost.
• Also, to improve efficiency, we should look into improving MeritRank by making it incremental in the context of dynamic graphs.
• The used public dataset may be unlabeled and require manual labeling by users, creating their own 'private' dataset.

Alternatively, a more focused approach:
Improve on the work of Joost by integrating MeritRank and perform more extensive evaluations.

[ThomasWerthenbach]

Final literature survey

[synctext]

Infinitely shrinking ToDo list

• Quality is great! Would like to be on the author list. Upload to :arxiv as this author
• add --- student project --- , see example
• Starts with a bad sentence: "As internet availability remains to spread across the globe"
• Add a 9th system (2008) my prior work 🙃 https://pure.tudelft.nl/ws/portalfiles/portal/57108987/de8b3e51fd56cbeb1d6d02e2c7a28c8d6acb.pdf AND (2006) https://iptps06.cs.ucsb.edu/papers/Pouw-Tribler06.pdf
• GroupRep: R_j missing summation of u_i_j
• IPGroupRep: missing index i at s and r.
• Meritrank: no formula in main table (just pick one)
• "In recent events, Alphabet Inc. has been fined" add (e.g. Google)
• "TRIBLER", too loud, Tribler
• Google is being attacked from all sides by scammer, expand ref from [36]: "1973 paper on “A New Evolutionary Law”. In this hypothesis, Van Valen posited that organisms must constantly adapt and evolve because they live in an ever-evolving ecosystem, competing for survival against other ever-evolving organisms. "
• [38] that is the 2008 version, also published already in Feb 2006 😃
• Too short citation: "Seuken, Sven and David C. Parkes. Forthcoming. On the sybil-proofness of accounting mechanisms. Proceedings of the 2011 Workshop on the Economics of Networks, Systems, and Computation (NetEcon'11)."
• "[52] “European digital identity,” Oct 2022."

Master thesis
"Collaborative machine learning" 🎉 Lets do that! Meritrank is perfect, so Sybil storyline. But the use-case: pdf parsing, tiktok, or MusicDAO.

First Sybil-resilient federated machine learning on edge devices. Use Meritrank. Improve meritrank or improve federated learning??? Choose! Strict 3 weeks practical thesis direction exploration. Spend 3 days getting this code working. Formulate IEEE 1-column "Problem Description". Check usability of great dataset: 170,919 Creative Commons articles in the arXiv for biology. Explore: https://github.com/DQ-Zhang/refchaser Java: https://github.com/CeON/CERMINE
We do 1 evaluation and aim to fix direction. (MusicDAO, recommendation for open source TikTok OR team Rohan semantic knowledge graph for keyword search)

[ThomasWerthenbach]

Note on master thesis direction which @synctext asked me to write down after meeting with Rohan and Johan:

I would like to keep my thesis quite generic by continuing around the point where Joost (Bristle) left off (make it better/integrate with meritrank) as well as perform more thorough evaluation (both with and without Android device emulation for sequential round simulation). There is no point in focusing on a very specific field early on. However, a 'nice to have' would be to integrate it with either the Music DAO or the Literature DAO.

[synctext]

Thnx for the clarification! Lets see if we can nail down the non-iid part and possible dataset(s) for your thesis (e.g. I'm an ML beginner).

• Simple intro with Enron and other energy company valuations
• Federated Learning on Non-IID Data: A Survey
• Can we assume this one million song dataset and extensions like taste_profile_song_to_tracks.txt.zip are non-iid or iid?
• Learning the similarity function between two songs or two scientific articles, should we assume non-iid?

To Discuss: "design, deployment, security, and even usage of federated machine learning with non-iid".

Update: @devos50 do not use experimental dataset (e.g. MusicDAO) AND create a new algorithm. So just boring imageNET because MNIST is just too embarrassing. Use the "edge devices" storyline, to set us apart from classical learning and provide our byzantine and fault-tolerance context.

[ThomasWerthenbach]

@grimadas Notes from meeting just now:

I am looking into the possibilities of improving MeritRank. Possible gaps:

• Stranger policy
• Incentives for edge creation (may be closely tied with stranger policy)
• New strategies for bounds

On a further note: while improving MeritRank would be great, I am not sure whether this will actually be included in my master thesis. Integrating 'current' MeritRank with decentralized learning will be a prior step.

[synctext]

Brainstorm results. Focus Decentralised machine learning with non-iid

• Datasets - non-i.i.d.
  • ImageNET
  • One million songs taste profiles (classification/recommendation)
  • Just two datasets with 1 novel algorithm (classification)
  • Hyperparameters: learning rate, hidden layers, etc. {just get from literature}
• large-scale simulation for experimental results
  • Still DeepLearning4Java
• Deployment experiment with 10-ish Android "edge devices"
  • No DeepLearning4Java, edge-devices! No 250MByte to spare.
  • Stochastic gradient decent from scratch
• novelty of Meritrank++ with Bristle(++)

Sprint goal: familiar and datasets going (Kotlin).

[synctext]

Cardinal lesson for your thesis design and experiments, don't mix like Bristle:
1 thesis 1 story.

[ThomasWerthenbach]

Note after lab meeting of yesterday:
After discussing my previously proposed algorithm with Bart, we found that it may work in certain use cases. However, it requires us to very concretely explain every component, rather than saying (in the extreme case): "because bristle did it". After yesterday's lab meeting, we now have three possible thesis directions which have a lot of overlap:

1. Algorithm 1: we continue with the current plan of integrating parts of Bristle and MeritRank and perform very thorough evaluation. In this case, we will need to clarify why we use transfer learning. The most obvious answers may be:

   • Decentralized learning may run on any device, including low-resource edge devices.
   • All peers aim to train a personalized model, given a pre-trained global model. However, with this reasoning one may wonder why we would perform the learning distributed at all.

2. Algorithm 2: we describe a new decentralized learning algorithm which makes use of reputation, for example MeritRank, to achieve stronger global accuracy. As a suggestion, we could choose this approach:

   1. Upon receiving our neighbours' models, we calculate a score for every received model, e.g. the accuracy or a similarity function. This score will in turn affect the edge weight between the two nodes in the trust graph.
   2. After having calculated the reputation, using some reputation mechanism, we take the weighted average of all our neighbours' models and our own model based on the reputation scores. Note: this algorithm may need some extra 'clever' idea in the aggregation process to better support non-iid datasets.

3. We invent a novel methodology which can be used to structurally combine reputation mechanisms with decentralized learning approaches. We then use this methodology to study the performance change caused by the introduction of reputation by combining many reputation mechanisms with many decentralized learning approaches. Note that this will result in a large amount of experiments. An example of such methodology may be:

   1. Upon receiving our neighbours' models, we calculate a score for every received model, e.g. the accuracy or a similarity function. This score will in turn affect the edge weight between the two nodes in the trust graph.
   2. The selected reputation mechanism will use these scores to calculate the neighbours' reputations.
   3. Given that all our aggregation methods work with some form of averaging, we linearly shift the received weights towards our own model depending on the reputation: $m_j' = (1-r) \cdot m_i + r \cdot m_j$, where $m_i$ is our own model, $m_j$ is our neighbour's model and $r$ is the reputation score provided by the selected reputation mechanism. By doing so, we simulate weights to the neighbours' models without modifying the internals of the existing decentralized learning method.
   4. The existing decentralized learning methods now receive the linearly modified models and perform aggregation.

Note: the third thesis direction will include the second direction, as the second direction is simply the combination of weighted average and MeritRank. However, by choosing the third direction, we will not only find out the performance improvement of the second thesis direction, but also quantify the general increase of performance through introducing reputation metrics to decentralized learning. On the other hand, going with option 2 may allow us to add some extra neat tricks, such as gossiping edge weights, rather than broadcasting them

[synctext]

(relevant for future work, possibly relevant for this thesis)
Open dataset from former TUDelft student. Last week this work was put online by Princeton University, Sony AI, and Meta AI: "Beyond web-scraping: Crowd-sourcing a geographically diverse image dataset"

we rethink the dataset collection paradigm and introduce GeoDE, a geographically diverse dataset with 
61,940 images from 40 classes and 6 world regions, and no personally identifiable information, 
collected through crowd-sourcing. We analyse GeoDE to understand differences in images collected
in this manner compared to web-scraping. Despite the smaller size of this dataset, we demonstrate
its use as both an evaluation and training dataset, highlight shortcomings in current models, as well
as show improved performances when even small amounts of GeoDE (1000 - 2000 images per region)
are added to a training dataset. We release the full dataset and code at this https URL

https://geodiverse-data-collection.cs.princeton.edu/

[ThomasWerthenbach]

Possible new idea (with inspiration from @devos50 ):
We present the the first-ever algorithm for dealing with Sybils in decentralized learning.

For federated settings, there already exists a very nice defence mechanism: FoolsGold. They have shown it is possible to detect Sybils in federated learning by looking at the updates of the weights of the models every round (Sybils tend to have very similar updates every round). Visualization of intuition behind FoolsGold:

However, in decentralized learning, this task becomes a bit more complex, as there is no central aggregator, and we do not have access to all trained models.

My suggestion for solving this in a decentralized setting consists of the following items:

1. Every node runs a variant of FoolsGold, which incorporates reputation, for model aggregation.
2. We incorporate a probabilistic gossiping mechanism which retrieves the model gradients from peers in order to detect possible Sybils
3. We use a reputation mechanism for bounding the gain of Sybils through punishing certain network topologies and decaying the effect of distant attack edges (inspired by MeritRank).

This way we handle the following cases:

• Multiple attack edges to node i $\rightarrow$ protected by item 1.
• A single attack edge to node i and one to our neighbour node j $\rightarrow$ protected by item 2 in combination with item 1.
• A single attack edge to node i and one to a distant indirectly connected node j $\rightarrow$ tolerated and effect dampened by item 3.
• Sybil may perform honest work elsewhere in the network to increase their reputation, in case they want to target some specific region $\rightarrow$ dampened by item 3.

[synctext]

-the model gradients obtained from peers becomes the self-confession of being a Sybil.
-Dampening is used and strangers are mostly rejected. Attack resilience increases, but informativeness is negatively impacted.

So these ideas all sounds interesting. Create a "thesis ideas" PDF. Next step is to find an academic sponsor. For msc thesis grading. Key question to ask: what idea is could be published in an academic venue?
btw all these federated AI types are hopelessly naive. Fundamental thesis contribution; extend the mathematical proof of David Parkes, Seuken and Stannet. Proof that it is impossible to protect federated learning from Sybils. Whatever the filter, whatever the algorithm, whatever the similarity, whatever the data gathering about you, you can fake it.

[devos50]

I do have some concerns about the proposed solution and non-IIDness of data. Non-IID data will lead to (honest) gradients with large differences and might incorrectly classify nodes as being Sybil. This effect is probably even more pronounced as each node has access to less models.

It is hard to say if this idea works or not, and what it offers compared to related solutions. I would suggest an incremental approach here: 1) reproduce the experimental results of FoolsGold in centralised settings so you have a solid baseline, 2) have every node in the decentralized network run the FoolsGold main logic and quantify the "decentralisation penalty" / costs of decentralization in terms of attacker efficiency and possibly overhead, 3) add your magic solution and see how much it improves the situation.

We use a reputation mechanism for bounding the gain of Sybils through punishing certain network topologies

Are you dynamically modifying the network topology? Note that there has been some work on building "optimal" network topologies to accelerate model convergence, see for example this paper.

I was also recently pointed to this work that might be related to your approach.

[ThomasWerthenbach]

Thesis very very first draft (work document):
Thesis_thomas_werthenbach_very_first_draft.pdf

All thesis ideas:
Thesis_ideas.pdf

Last week, I continued on the latest idea (Foolsgold decentralized). During this time, I have reconsidered the use of a reputation scheme $\rightarrow$ I don't believe we need this initially anymore. The use of only a smart gossiping mechanism will likely have the same effect. If we consider all the previously named cases:

• Multiple attack edges to node i $\rightarrow$ protected by FoolsGold.
• A single attack edge to node i and one to our neighbour node j $\rightarrow$ protected by both FoolsGold and our gossiping mechanism.
• A single attack edge to node i and one to a distant indirectly connected node j $\rightarrow$ effect of attack will be dampened with the increase of distance. Nodes still update model every training round, which causes any effect to the model caused by attacks to be dampened.
• Sybil may perform honest work elsewhere in the network to increase their reputation, in case they want to target some specific region $\rightarrow$ does not apply to us, as we can not accurately provide feedback due to the non-iidness.

By using this approach, we do the following:

• We are the first to study Sybil attack in decentralized learning, and are given the opportunity to identify possible effective Sybil attacks.
• FoolsGold's authors mentioned that the aggregation is rather expensive due to the cosine similarity calculation. Solved by using decentralized learning, in which the aggregator has access to fewer models.
• We can perform some thorough analysis on the maximum effect of Sybils on the long term, depending on the degree and max travel distance of models.
• We would create the second paper on poisoning attack resilience in decentralized learning. However, the prior paper (9 December 2022!) has some naive assumptions, which our algorithm does not have:
  • It is assumed that all poisoning updates are very different from honest model updates, which may not necessarily be the case (similar to distance-based prioritizer from Bristle), especially in non-IID environments.
  • It is assumed that there exists an, upfront decided upon, adjacency matrix, defining all edge weights.
  • It is assumed that any connection between a malicious i and honest node j is smaller than some constant $\epsilon$, such that $(j, i, w) \in E, w &lt; \epsilon$ and $0 &lt; \epsilon &lt; \frac{1}{2}$.

Main disadvantage of this approach:

• It only defends against targeted poisoning attacks in combination with the Sybil attack, as model updates from different nodes need to be compared.

Possible extension: the current idea of this new algorithm will only protect against targeted poisoning attacks (the adversary has a certain goal for which all Sybil need to send similar updates). Untargeted poisoning attacks (the adversary simply wants to ruin the global model by inserting random model updates) will not be caught by this algorithm, as no Sybil model update may be similar. What we could do: by evaluating all received models on your own data, a naive reputation score can be calculated, which may be used in a more complex reputation scheme. The benefit of doing this is that nodes need to be somewhat sure that received models are not just random noise. The drawback of such an approach is, evidently, the non-iidness of data, which will result in inaccurate reputation scores, which means that you may only trust someone who has somewhat similar data. (we sacrifice informativeness for resilience)

Proposed plan:

1. Reproduce results from FoolsGold in federated learning.
2. Apply plain FoolsGold to decentralized learning (and see it fail in certain situations).
3. Apply the gossiping scheme for increased resilience (we can perform analysis on the amount of increased resilience).
4. Optional: apply the reputation scheme described previously to increase resilience against untargeted poisoning attacks.

Lastly, I am planning on performing extensive evaluations (different network topologies, multiple datasets, many nodes).

[synctext]

• Amazing start, quite promising
• Thesis: FoolsGoldPlus is a fertile direction.
• Do not start running yet (e.g. no experiments), first set a direction on paper and document alternatives
• what are you going to focus on: theory, eval, Python notebook classic, or classic library (ML+Sybil+defense)
• Use lab knowledge: Sybil expertise (cost of attack, renting 1 GB per second, 1 Million Ipv4); or machine learning as main element
• Contribution to science, hard to grasp versus personal gain and recognition (With Honors)

[ThomasWerthenbach]

Shorter update this week:
As advised, I started looking for potential examination committee members and I believe that I collected quite a good selection:

• Johan: Distributed systems and Sybil attack expert.
• Federated learning expert.
• Machine learning expert (to cover the correctness of the machine learning techniques used within our experimens).

Let's further discuss this during our meeting.

Furthermore, I have done some more reading on related work and started preparing the first experiment (reproducing FoolsGold's results). This experiment is almost ready to be performed on the DAS6.

Repo: https://github.com/ThomasWerthenbach/Repple

[synctext]

• great progress 🚀 Grading committee team getting ready
• Strong claim, add bit of credibility. Like: We are the first to study decentralised learning and the cardinal cybersecurity issue: the Sybil attack. Various scientific papers mention the vulnerability of decentralised learning, but do not offer any experiments or solution. Other work discusses closely related issues such as Byzantine robust decentralised learning. Yet this related work... Add table with 7+ most related papers.
• Python implementation of FoolsGold, IPv8, and PyTorch.
• Dataset selection: ongoing.
• Decide: balance Distributed Systems vs. ML direction for thesis

D-cliques: Compensating noniidness in decentralized federated learning with topology

[ThomasWerthenbach]

This week's update:
Continued working on experiments. I have used Gumby and IPv8 on the DAS6 to run experiments (see code here).

I am well under way with a simple framework in which I will be able to run all necessary experiments. To verify correct code execution, I ran default decentralized learning and federated learning both non-IID and IID (1 hour):

I also implemented a simple targeted poisoning Sybil attack, in which all Sybils attempt to affect the final model to classify a certain class as another class (label-flip attack). This graph shows the result with 100 Sybils and 100 honest nodes. (9 hours)

However, if we decrease the amount of Sybils to 50, we get this graph: (5 hours)

Furthermore, I started reproducing FoolsGold's results: (1 hour)

Next iteration, I'm planning on continuing the reproduction of FoolsGold's results. Implement the backdoor attack and show how FoolsGold does/should not work as well in decentralized learning. I will also start on our own algorithm for which it does work.

General observation: Machine learning people often do not see some risks in decentralized systems. However, decentralized systems people do not know much about machine learning. Trans-disciplinary research is required to truly push the frontier forward.

Hypothesis: naively applied decentralized FoolsGold may be vulnerable to very specific targeted poisoning sybil attacks. The lack of a centralized server decreases informativeness during the aggregation process. Attempt to removing the central server will result in significant performance degradation.

After this week, I am confident that given the proper implementation, we may be able to apply this to a large decentralized network (of android devices)

Our assumption is that generating random model updates is extremely cheap. Therefore, this will only work for targeted poisoning attacks, rather than untargeted poisoning attacks.
Experiment defense against duplication + random noise attack

[synctext]

Great progress!
Suggest to keep focus, focus, and focus on getting publishable experimental results.
Breakthrough potential: you can defend against targeted Sybil majority with added noise.

[ThomasWerthenbach]

This week's update (it's a long one):

More experimental results: our approach works

We have shown that FoolsGold works relatively well in specific cases. For example, in the case where we have a random geometric graph with 50 random honest nodes and 50 sybils performing a label-flipping attack. It is clear that FoolsGold performs significantly better than the basic averaging algorithm.

If we compare FoolsGold to our own solution, we see that we lose some accuracy while completely removing the attacker's success. (Probably still need to tweak our algorithm a bit)

However, if we consider a different network topology, in which the honest nodes form a random geometric graph among themselves, but each have exactly one attack edge we see how our approach achieves much better results.

Note I realise this is a naive network topology, but it shows clearly how FoolsGold is not well-equipped in some decentralized learning configurations.

Our novel gossiping mechanism

Our gossiping mechanism works as follows:

• Peers randomly select a neighbour to propagate a new random update history to.
• Peers randomly propagate update histories received from (in)direct neighbours.
• Peers will never send update histories from (in)direct neighbours to a neighbour from which they have received said update history.
• MAYBE: update histories are expire after a fixed number of rounds.
• The update history to-be-propagated is chosen randomly according to the exponential distribution: $P(X) = \lambda e^{-\lambda x}$, where $\lambda$ is some pre-defined constant and x is the amount of hops the update history has traveled. We calculate the probability for every model history in our local database, normalize such that the sum equals 1 and then randomly select a model from our reweighed distribution (will include mathematical definitions in paper).

We will also perform theoretical analysis of this gossip mechanism and determine the relation between attack edge distribution and $\lambda$

Note: spoofing identities is out of scope of this research.

FoolsGold's experimental evaluation

Furthermore, I found that the results presented in Foolsgold are not very realistic. First of all, they only use 10 honest participants, which is by far not enough participants to obtain realistic results. Note that amount of participants coincidentally corresponds to the amount of classes in MNIST and CIFAR-10. This brings us to the second point: their definition of non-IID entails that every peer has all/most samples of a single class. However, using the Dirichlet distribution for determining the class distribution over the peer is more realistic and more accepted in the scientific community (credits to Martijn). This means that Foolsgold's effectiveness is exagerated as it has been evaluated in an unrealistic environment, which, if necessary, we can prove. This does not mean that FoolsGold is useless; the core idea is still genius and works, and we can improve on it.

Experiments

Now that we have shown our solution works, I believe it is a good week to start fixating on which experiments we want to perform and which graphs to include in the paper. As one would expect there are many parameters involved in these decisions. I have composed a list of the relevant parameters, as well as whether I intend to include them.

Parameter	Intend to differentiate in some form	Remarks
Datsets/ML job	Yes	MNIST, FashionMNIST, CIFAR-10, CIFAR-100, CELEBA
Number of peers	No/very little
Decentralized learning algorithm	Yes	Our algorithm, FoolsGold, FedAvg, Krum, more?
Poisoning attacks	Yes	Backdoor attack, label-flipping attack
Sybil attacks	Yes	Different attack edge topologies (one attack edge per node, fewer than one attack edge per node)
Probabilistic gossiping mechanism	Maybe	We can increase/decrease the likelihood of propagating the update history of distant neighbours
Network topology	Yes	Question: How do we realistically simulate peer-to-peer networks? I have used random geometric graphs up to this point. Cannot seem to find any papers about this particular aspect. Also not sure which sybil attack edge network topologies to use.
Weight relevance	Probably	Smart sybils can add intelligent irrelevant noise to their model updates to seem different from each other. Therefore, we would do best to filter only for relevant weights (see part after this table).
Data distribution	Maybe	We can change the degree to which data is distributed non-IID (by changing the Dirichlet $\alpha$-parameter)

Weight relevance

As was noted in FoolsGold's paper and by Johan previously. The cosine similarity function no longer works if Sybils add random irrelevant noise to the model updates. Therefore, we have strong motivation to consider techniques for determining the relevant weights in the model updates and only perform the cosine similarity on these. The paper proposing FoolsGold does not go into details on this, and only looks at the output layer to directly map edge weight to probilities. I believe that we can do better and look at all weights in the model. Therefore, I have composed the following techniques (note that I do not yet know which one will be most effective).

• Absolute weight gradients: Weights which have the largest gradient after training are the most important weights, as they will affect the output of the model the most. Disadvantage is that this may be biased due to non-IID distributions.

• Absolute weight magnitude: Weights with a larger absolute magnitude will have a greater impact on the model and are therefore more important. Disadvantage is that many small weights combined may still produce (loss of informativeness).

• Layer-wise relevance propagation (favourite option thus far): after having classified a sample, the output layer of the neural network has propabilities mapping to each class. These probabilities can be considered the relevance of that specific edge. If we propagate these relevances backwards through the network, we obtain a distribution on how much each weight has contributed to the output of the model. This distibution can be used to obtain the X% most relevant weights to perform the cosine similarity function on. Ironically, this technique is incredibly similar to the random flood algorithm I have proposed several weeks ago.

I am not planning to go much more into details here due to time constraints, but I would like to discuss this aspect and present our findings on the best option.

Paper

I am also planning to think about the paper structure. This is my current plan:

Paper structure:

1. Introduction
   • Include 'preview' graph(s) showing our algorithm's success
   • Contributions
2. Background
   • Federated learning
   • Decentralized learning
   • Sybil attack
   • Poisoning attacks maybe?
3. Related work
   • FoolsGold? Not sure if we should count this as related work, given that it is so relevant.
   • Other sybil defense mechanisms (possibly federated learning)
4. Threat model
   • We discuss how the distribution of attack edges is very relevant to the success of the attack. We also define a mathematical representation the attack edge distribution.
   • Discuss more details about the targeted poisoning attacks we aim to defend against.
   • Discuss the best ways to attack our algorithm (add intelligent noise).
5. Our algorithm
   • Reintroduce FoolsGold (cannot be assumed that everyone fully understands it).
   • Introduce our gossiping mechanism (see above).
   • Introduce our weight relevance methodology (see above).
6. Theoretical analysis
   • Show how attack edge distribution relates to sybil success rate and gossip mechanisms parameter $\lambda$.
7. Experimental evaluation
   • Setup:
     • Refer to open source
     • IPV8, Gumby, DAS6, realistic evaluations, etc.
   • Experiment descriptions
   • Results
8. Discussion
9. Conclusion

Next iteration's plan

• Get more datasets up and running (perform one or two experiments per dataset to validate effectiveness)
• Get backdoor poisoning attack working
• Decide on what experiments to execute
• Continue with paper (write one or two chapters)
• Not yet start with implementation of weight relevance (that's something for iteration after the next)

Plenty of work to be done! :)

Also, this meeting we will have to complete the thesis examination committee form and submit it to the BoE.

[synctext]

• Solid progress
• For thesis:
  • decentralised learning challenge, Foolsgold is central server federated learning
    • prior work will never scale beyond a single server and a {fraction of} million users
    • we aim to empower decentralised Tiktok with a billion users?
  • Clearly a Problem Description (not background)
  • document clearly the essential algorithm of Foolsgold, when are you good and when an evil Sybil
  • Algorithmic delta clearly defined. You addition to make it work
• reasoning from your own strength: decentralised learning with attack resilience and unbounded scalability
  • not just tweaked federated prior work with incremental fix
  • new generation stuff, no need to cite Foolsgold anymore :-)
• gossip relay invites 10 GBit per second spam nodes.
  • never relay if the original IPv4 is online
  • relaying of taste buddies like its 2005
  • tolerate offline distributed P2P nodes: 5G connectivity of edge devices with hardware-accelerated continuous learning {insert more buzz and hype}
• Next sprint: experiment plan, which figures ??? 1st draft "Problem Description"

[ThomasWerthenbach]

@synctext Remark on Gossip relay feedback:
The importance of the relay is that we need the aggregated history of model updates, rather than the latest model update. I currently see two ways of solving this:

1. We sign our own update history every round and send it to our peers. The receiving peers store this history and are able to infer the model update by viewing the differences between their own stored history version and the one they just received (assuming the network is fixed for the entire process). However, if the network is not fixed and the topology may change, we send both the model update and the signed update history every round to our neighbours. Both methods require to also relay the IP address, as it allows the receiving peer to request the public key.
2. Send IP address of our neighbour rather than the model update history such that the peer can request the history themselves. However, this has two disadvantages over the previous option: 1) it allows a peer to modify their history, rather than having it checked by their neighbours and 2) if the peer is offline or for any other reason unreachable, the history cannot be retrieved.

I will for now assume the first option. Note that this will not affect the results of the experiments, but will likely simplify the code base.

[synctext]

https://proceedings.mlr.press/v162/zhang22w/zhang22w.pdf

UPDATE: try to do a grand thesis:
scalability of cloud, federated, and decentralized learning

Foolsgold attack assumption is completely naive , attacks have lots of compute and humans:

No shame in making storyline: Can't be solve. proving the hardness of distributed ML security. we need passport-level identity 💡

[ThomasWerthenbach]

This sprint's update:

Experiment_plan

Thesis with problem description and draft structure

Other completed tasks:

• Implemented the backdoor attack.
• Found and implemented more datasets.
• Started reading about convergence proofs (I would like to try to include one). Example
• Coding experiment framework is ready for the first large scale experiments (as described in experiment plan).

Plan for next sprint:

• Start with the experiments from the experiment plan
• Finish background, related work and threat model in thesis. Will maybe start on design section.
• Read some more on convergence proof and start with ours.

Note: I took your advice into account to keep a single storyline and decided that we should indeed likely not focus too much novel weight relevance methods (as described in my previous sprint update).

[synctext]

• Related work from my mailbox: https://link.springer.com/chapter/10.1007/978-3-030-22496-7_5
• How can you argue or even prove that gossip-based decentralised learning has unbounded scalability?
• Directions
  • "Towards Sybil Resilience in Decentralized Learning"
  • "Understanding scalability of cloud, federated, and decentralized learning" ? (but, most focus on decentral)
• Why is 5 years after the key paper nobody doing decentralised learning? Too much system/Sybil knowledge needed for machine learning community with mainly advanced statistics knowledge?
• In this work, we experimentally demonstrate FoolsGold’s inability to scale to an unbounded number of edge devices in federated learning and inept defensive capabilities against targeted poisoning attacks in decentralized learning. 👀
• We suggest an improved version of FoolsGold, too small selling. Counter example of over-the-top arrogant selling: our algorithm provides superior performance in all known valid metrics, the original FoolsGold is degraded into a mere subcomponent of our grand vision for the future of AI.
• Documenting the sad state of academic AI science. 'lack of hardware means we can't test our algorithm with ImageNET'
• Density of 1 means that every honest node in the network is connected to an attack edge. have a classical Sybil cluster with varied amount of attack edges towards honest nodes. Epic sybil attack: 90% bad people. Trick: amount of attack edges for total system collapse (pollution success).
• reading about convergence proofs, warning that this could be the productivity killer of your thesis process (e.g. phd track of 4 years, not secondary interest and single section msc thesis)
• polishing and re-writing phase of 10-page thesis is the main time killer
• Entire June 2023: from good text and completed results, and polished figure: to Perfect Paper.

[ThomasWerthenbach]

Thesis update:
Thesis_28-04-2023.pdf
In this early draft, you can find the produced results up to now, as well as the current progress on the thesis text. Do we want to assign a upper page limit? If we are to include all information I would like to include, we will reach about 16 pages.

Other notes:

• I am currently running experiments on the DAS-6 (we are about halfway there).
• With regard to the plan of reserving the entirety of June 2023 on rewriting the thesis paper, I am certain that we will reach this goal.

[synctext]

• Reviewing your draft thesis: very impressive. 16 pages no issue.
• About the name sydle, not ideal. suggestions: SybilWall. Inspired by one of 10 ChatGPT suggestions (ShieldWall) after using prompt "what is a good name for a sybil-defence algorithm in decentralised algorithm, like Foolsgold and crum" (others: SybilShield, SybilBarrier, SybilFortress, SybilGuardian)
• Figure 6: Pairwise cosine similarity computation time These numbers are from the DAS6 high-performance compute cluster, therefore computational hardware of 1 million Euro is required to obtained these attack costs.
• FoolsGold and Krum are totally inadequate for real-world usage in decentralised unsupervised learning. This field has only just started. To prafrase. Increasing success of the Sybil-defense by lowering expectations --- just label flipping and backdoor attack. Real-world attacks are still out of scope until 2030.
• D. The Sybil attack this sub-section lacks the mathematical rigour of prior sub-sections.
• IV. THREAT MODEL AND PRELIMINARIES it actually exclusively contains 6 assumptions.
• Number 5 In order to restrict the impact that any individual node may exercise on the network. This is a really big one. We assume the existence of an algorithm to reduce the global impact on the network of a single network address, network block, or latency-restricted geographical network attachment point.
• we define a parameter for SSP attacks seems more like opening text, as opposed to closure.
• Moreover, we integrate a probabilistic gossiping mechanism to for knowledge spreading, so you have a knowledge generator from raw info?
• Define your 3 homogeneous, semi-homogeneous, and sparse attack type inside threat model?
• Flip sub-sections? Figure 9: Comparison of Sydle against different techniques on ϕ = 1. First compare your idea to all known algorithms, then also vary the dataset a bit.
• techniques on ϕ = 1 feels quite artificial, drop either the 1 or 4 experiment and do a somewhat more realistic attack
• Difficult decision ahead on the backdoor attack. You could do a preview of future work. The principle of audits, witnesses and reproducability. If you can do random sampling and local validation of re-training of signed inputs, then we can get this "backdoor" performance: . . .
• VII. ANALYSIS one section earlier!
• Can your experiments claim "superior to existing algorithms"?
• discussed all questions within 2+ hour meet 😸

[ThomasWerthenbach]

This week's update:

Thesis draft

Additional remarks:

• Green light review this week.
• Thesis is almost complete content-wise. Only need to write a conclusion and resolve some todo's.
• We're on track for dedicating June to polishing paper.
• Experiments are complete.

[synctext]

• Mature thesis draft ✅
• no intro line for sections, bit ugly
• "manipulate other nodes’ local models or data.". Also include 'data signatures'. You assume cryptographic primitives to be safe and block spoofing.
• {repeating} Number 5 In order to restrict the impact that any individual node may exercise on the network. This is a really big one. We assume the existence of an algorithm to reduce the global impact on the network of a single network address, network block, or latency-restricted geographical network attachment point.

[ThomasWerthenbach]

This week's update:

Thesis draft

Additional remarks:

• Thesis will be sent to thesis committee tomorrow (20 working days before defense).
• Page with rules and times

[synctext]

• Impressive thesis draft, amongst the top of our population 👍
• Cardinal ToDo: readability of figures and text
• V. DESIGN OF SYBILWALL readability for first-time readers is quite hard I believe
• A. Adopting FoolsGold is this novel or incremental work?
• Sparse Sybil poisoning attack: It is conceivable that the probabilistic gossiping mechanism may be unable to disseminate knowledge to an extent that allows all attacked nodes to detect the presence of attack edges. Circular dependency for understanding. This little In short, requires understanding the upcoming detailed text.

[ThomasWerthenbach]

I have submitted the first thesis version for feedback to the thesis committee.

[ThomasWerthenbach]

first version of defence presentation

[synctext]

• Readability is the main concern, for "excellent level" thesis
• kept all master thesis results inside this 43-slide presentation 😲
• Explaining 24 figures in the 15 minutes you can talk about results 😨 (really explain just 4 experimental result figures)
• First explain your own algorithm from scratch: SybilWall
• Related work slide: 1 mention of Foolsgold, unsuitable for decentralised, main inspiration
• In short, SybilWall was designed to mitigate the three attack scenarios of the SSP attack too soon, circular dependency.

[ThomasWerthenbach]

Final thesis

arXiv submission