Skip to content

master thesis placeholder - decentralised learning with security and unbounded scalabilityย #7027

Closed

Description

@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:

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

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)

Activity

  1. added this to the milestone on Aug 31, 2022
  2. ThomasWerthenbach commented on Sep 15, 2022

    @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

  3. synctext commented on Sep 15, 2022

    @synctext
    MemberAuthor

    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

  4. synctext commented on Sep 30, 2022

    @synctext
    MemberAuthor

    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.
    image
    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

  5. ThomasWerthenbach commented on Sep 30, 2022

    @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

  6. synctext commented on Sep 30, 2022

    @synctext
    MemberAuthor
  7. changed the title [-]master thesis placeholder - ??? trust function, misinformation, novel model and algorithm, something[/-] [+]master thesis placeholder - solving the online trust problem[/+] on Sep 30, 2022
  8. ThomasWerthenbach commented on Oct 2, 2022

    @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 RA * c, where RA 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 RA increases, RB increases by RA * 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 RA decreases, RB decreases by RA * 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 RB decreases with some value LB, RA decreases by LB/(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 RB increases with some value GB, RA increases by GB/(distance + 1) iff the event causing the reputation change is within a distance d from both node A and B.

    Some related work:

    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'.

  9. ThomasWerthenbach commented on Oct 4, 2022

    @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.

  10. synctext commented on Oct 5, 2022

    @synctext
    MemberAuthor

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

  11. Dmole commented on Oct 13, 2022

    @Dmole
    Contributor

    Related; #3657

  12. ThomasWerthenbach commented on Oct 14, 2022

    @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

  13. 33 remaining items

  14. changed the title [-]master thesis placeholder - solving the online trust problem[/-] [+]master thesis placeholder - decentralised learning with security and unbounded scalability[/+] on Mar 29, 2023
  15. ThomasWerthenbach commented on Apr 7, 2023

    @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).

  16. synctext commented on Apr 7, 2023

    @synctext
    MemberAuthor
    • 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.
  17. ThomasWerthenbach commented on Apr 28, 2023

    @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.
  18. synctext commented on Apr 28, 2023

    @synctext
    MemberAuthor
    • 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 ๐Ÿ˜ธ
  19. ThomasWerthenbach commented on May 22, 2023

    @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.
  20. synctext commented on May 22, 2023

    @synctext
    MemberAuthor
    • 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.
  21. ThomasWerthenbach commented on Jun 5, 2023

    @ThomasWerthenbach

    This week's update:

    Thesis draft

    Additional remarks:

  22. synctext commented on Jun 5, 2023

    @synctext
    MemberAuthor
    • 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.
  23. ThomasWerthenbach commented on Jun 6, 2023

    @ThomasWerthenbach

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

  24. ThomasWerthenbach commented on Jun 18, 2023

    @ThomasWerthenbach
  25. synctext commented on Jun 19, 2023

    @synctext
    MemberAuthor
    • 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.
  26. ThomasWerthenbach commented on Jun 26, 2023

    @ThomasWerthenbach
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions