Byzantine-resilient, asynchronous, yet decentralized federated learning

[synctext]

Key points:

• Cum Laude ambitions
• thesis science must come above everything else
• possible direction with most science imaginable
• TBM compatible; thus governance of the global financial system (who owns capitalism)
• single universal global market
  • liquidity attracts liquidity
  • near-zero cost trust
  • inherently superior and open
  • by design hostile to speculators, hft, and any middleman
  • mechanism design against speculation tax
  • market makers redundant?
• startup use-case for bootstrapping liquidity
  • real euros and real dollar plus Bitcoins?
  • real mortgage market?
  • avoid utopia thinking
  • re-use existing infrastructure from the lab
• thousands of DAO/blockchain competing projects, with fancy white papers and high ambition level
• integrity of the market : fakes, extortion, and fraud
• companies become a front-end for shared critical infrastructure, they keep their helpdesk and customers. However, they can do deals with customers from competitors in a single highly liquid market
• entirely non-custodial, no proxy tricks, autonomous-entities-only principle
• market consolidation and domination mechanism
  • design some principle that Booking.com, Expedia and Airbnb see that this is an existential threat and they decide to all join, collaborate, and extend the global market; instead of being cut-off.
  • Why did The Internet eat all other proprietary communication protocols? re-use that trick!
  • Booking.com, Expedia and Airbnb: they sort of become ISPs for the global market infrastructuur.
  • disruptive change: everything becomes transparent and open; pricing, utilisations, market share, etc.
• game theory: fully self-interest driven
  • no helping others for free
  • willing to do effort for your own interest, safety and fraud prevention
  • maintenance?
  • Delft University should not be special; always ability to fork away; keep everybody honest

[devos50]

Interesting thesis direction!

We aim to achieve this goal with our own decentralized exchange, which is fundamentally different from existing DEXes. I think the OP identified the main flaws of existing DEXes (e.g., BitShares, Waves, OasisDEX...). Even though the idea of DEXes is interesting, their liquidity is too low to attract traders. Furthermore, even though they offer trust-less asset settlement, their (transaction) costs are still high (of course, this also depends on the specifications of the underlying protocols). Finally, there are many fairness issues attached to blockchain-based exchanges.

I think market fairness as central thesis component could be a viable and novel research direction. This ties directly into mechanism design and behavior of individual agents, whose goal is to optimize their own profits. Can we make a market that provides fairness to traders? Fairness is a multi-dimensional property so you might want to focus on a specific aspect of fairness.

[synctext]

Some overlap here, however they just want their own coin to become big https://docs.bisq.network/dao/phase-zero.html

Bisq, a peer-to-peer exchange network designed for secure, private and
censorship-resistant trading of bitcoin for national currencies and other cryptocurrencies
[snip]
Appendix A: Roles defines the roles individuals play when participating in the Bisq DAO,
such as trader, contributor and stakeholder, and defines several categories of high-trust
bonded contributor roles such as maintainer, operator, and administrator;

[jverbraeken]

Initial exploratory literature review: (a) digital marketplaces (https://fetch.ai/wp-content/uploads/2019/10/Fetch.AI-Economics-white-paper.pdf) (b) distributed ledgers used for financial purposes (http://www.smallake.kr/wp-content/uploads/2018/09/E_JPX_working_paper_No15.pdf / https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3352293) (c) peer-to-peer lending (https://www.oecd.org/daf/ca/The-Potential-for-Blockchain-in-Public-Equity-Markets-in-Asia.pdf)

[jverbraeken]

Initial thoughts after reading some literature, before discussing with Johan:

• One universal platform on which every supply/demand-market can be built (from Uber to Airbnb, from Amazon to stock markets, from insurers to lenders)
• Everything peer-to-peer to prevent extra costs from middlemen
• Goal = mainstream adoption ===> integration of payments methods such as Paypal and creditcards is essential + governments should be able to regulate the platform within their regions
• The throughput necessary will easily (!) exceed 9000 transactions/second. _{^{For trading in USA alone, system should be able to handle 800 million trades/day => 9000 per second}}
• Still struggling with who's going to pay the electricity bills

The idea is that anyone can create a market. I identified several considerations that a market creator should consider:

1. Checks before the market can be created
   • Government regulations (stocks, airbnb, uber)
     • A partitioned scheme that keeps certain transactions within certain locations may be required to satisfy local jurisdictional requirements
2. At creation time
   • Send potential buyers/sellers amessage when new marketplace has opened?
     • E.g. notify a bank when someone wants to borrow
   • Digital or physical product?
   • Semantic links with other markets (e.g. ubers in Delft subset of ubers in South-Holland, black ubers subset of ubers)
3. At run-time
   • Buyer
     • Anonymous or not?
       • Anonymity of both parties is crucial for stock markets, but undesirable for airbnb markets
   • Product
     • Scheduling of the good? (airbnb)
       • Can change every now and then
     • Location of the good? (uber / airbnb)
       • Can change every now and then
     • Order book
       • Type of matching
         • Mostly relevant for stock exchanges: first-in-first-out or pro-rata?
       • Fixed price level or not?
       • Can you see the other asks/bids or not?
         • On stock markets this is desirable, on Amazon this is unnecessary
       • Additional service
         • Reviews for the product or not?
           • Does not make sense for the stock market, but very valuable for airbnb
           • How to handle fake reviews?
         • Recommended items?
   • Seller
     • Anonymous or not?
       • Anonymity of both parties is crucial for stock markets, but undesirable for airbnb markets
4. At purchase time
   • KNY/AML/CTM? (know your customer / anti-money laundering / counter-terrorism financing)
   • (for physical goods: ) choose third-party escrow to provide protection?
   • Payment details
     • Automatic / manual approval of purchase
       • E.g. does airbnb owner want to have the renter
     • Collatoral or not? (house, car)
     • Payment obligation (paying right now, in terms, physical or monetary goods, crypto or fiat, …)
   • Conditions to enter a marketplace
     • E.g. age for adult stuff or creditworthiness for loans
     • For loans we still need creditworthiness for external party
       • In USA they have a system with bad privacy
       • In Netherlands based on financial situation and loan payment history
       • Additional details may be obligatory to deploy bailiff (incassobureau/deurwaarder)
5. After purchase
   • Should some party by notified to keep track of the order?
     • E.g. corporate share register managed by a transfer agent for stock markets
   • Cancellation possibility after the item has already been purchased
     • _{^{"The ability for clients to correct/cancel/adjust transactions that were inadvertently charged or credited to the wrong account is a common occurrence and well managed by today’s financial institutions. Additionally, complex financial transactions often include the ability to reverse the transaction based on contractual stipulations as a desirable feature. The ability to cancel or reverse a transaction is not supported in today’s distributed ledger platform, and it is not clear today how the platform could evolve to support that"}}
   • Vendor obligation (sending product right now, in terms, lottery, …)

[synctext]

great taxonomy start! Trustchain is consensus-free, thus no electricity for mining. What are two isolated markets that can be merged into a single infrastructure? Preferably with low competition, high fees, low innovation, and incentives to use your open alternative.

[synctext]

Brainstorm... Inspired by this payout platform it would be possible to build market trackers(). A payout is provided if the stock market is either below or above a certain mark. Use our DAO #5143 with shared ownership of Bitcoins.

• currency trading: Euro/Dollar rate prediction market + actual exchange, clearance and settlement.
• largest: new york stock exchange tracker
• long-term public trackers
• Prediction market for climate change: #2882 (everybody can invest against/on climate change within minutes. This is impossible today. our 2017 idea)
• food pricing ???

[devos50]

I am currently working on a classification/overview of existing electronic market/trade mechanisms based on blockchain technology (for a possible paper). This also includes literature on prediction markets, like Augur. I have collected 130+ (mostly peer-reviewed) articles so far and categorised them. I think there is quite some overlap with topics that you brought up. If you are interested in them, I can share them with you 👍

[synctext]

can you post a list here? + URLs possible even...

[devos50]

@synctext sure! I'm using the Papers application to organize and categorize all the literature that I read, and I'm currently in the process of reading/summarizing each paper. I think the list below is quite complete regarding academic work, but there are still a few open-source (non-peer-reviewed) implementations missing.

Atomic Swaps

Alt chains and atomic transfers

Atomic Cross-Chain Swaps.

Atomic Cross-chain Swaps - Development, Trajectory and Potential of Non-monetary Digital Token Swap Facilities.

Atomic Cross-Chain Swaps with Improved Space and Time Complexity.

Atomic Crosschain Transactions for Ethereum Private Sidechains.

Atomic Swaptions: Cryptocurrency Derivatives

Cross-chain Deals and Adversarial Commerce.

Extending Atomic Cross-Chain Swaps.

On the optionality and fairness of Atomic Swaps.

On the specification and verification of atomic swap smart contracts.

Privacy-Preserving Cross-Chain Atomic Swaps

The state of atomic swaps

(via @papersapp) http://scholar.google.comjavascript:void(0) https://dblp.org/rec/conf/podc/Herlihy18 http://aetic.theiaer.org/archive/v3/v3n1/p5.html https://dblp.org/rec/journals/corr/abs-1905-09985 https://dblp.org/rec/journals/corr/abs-1904-12079 http://arxiv.org/abs/1807.08644v2 https://dblp.org/rec/journals/pvldb/HerlihySL19 http://link.springer.com/10.1007/978-3-030-31500-9_14 http://dl.acm.org/citation.cfm?doid=3318041.3355460 http://arxiv.org/abs/1811.06099v1 http://fc20.ifca.ai/wtsc/WTSC2020/WTSC20_paper_20.pdf http://diyhpl.us/wiki/transcripts/scalingbitcoin/tokyo-2018/atomic-swaps/

Auctions

PASTRAMI: Privacy-preserving, Auditable, Scalable&Trustworthy Auctions for Multiple Items

Succinctly Verifiable Sealed-Bid Auction Smart Contract.

Verifiable Sealed-Bid Auction on the Ethereum Blockchain.

(via @papersapp) http://link.springer.com/10.1007/978-3-030-00305-0_1 http://link.springer.com/10.1007/978-3-662-58820-8_18

Custodial Exchanges

Bitcoin: Economics, Technology, and Governance

Bitcoin Transaction Malleability and MtGox

Making Bitcoin Exchanges Transparent

Provisions: Privacy-preserving Proofs of Solvency for Bitcoin Exchanges

ShapeShift

Tesseract - Real-Time Cryptocurrency Exchange Using Trusted Hardware.

The Arwen Trading Protocols (Full Version).

Why Preventing a Cryptocurrency Exchange Heist Isn’t Good Enough

(via @papersapp) http://pubs.aeaweb.org/doi/10.1257/jep.29.2.213 https://link.springer.com/chapter/10.1007/978-3-319-11212-1_18 https://link.springer.com/chapter/10.1007/978-3-319-24177-7_28 http://dl.acm.org/citation.cfm?doid=2810103.2813674 https://shapeshift.io http://dl.acm.org/doi/10.1145/3319535.3363221 https://dblp.org/rec/journals/iacr/HeilmanLG20 https://link.springer.com/chapter/10.1007/978-3-030-03251-7_27

Decentralized Exchanges

0x: An open protocol for decentralized exchange on the Ethereum blockchain

A Demonstration of Sterling - A Privacy-Preserving Data Marketplace.

A Distributed Digital Asset-Trading Platform Based on Permissioned Blockchains

Beaver - A Decentralized Anonymous Marketplace with Secure Reputation.

Bisq - The peer-to-peer Bitcoin Exchange

BitShares 2.0: General Overview

Coincer: Decentralised Trustless Platform for Exchanging Decentralised Cryptocurrencies

Decentralized blockchain-based electronic marketplaces

Decentralizing the Stock Exchange using Blockchain An Ethereum-based implementation of the Bucharest Stock Exchange.

Deconstructing Decentralized Exchanges

Enigma Catalyst : A machine-based investing platform and infrastructure for crypto-assets

Etherdelta

Fast and secure global payments with Stellar

Fragmentation of Distributed Exchanges

IDEX: A Real-Time and High-Throughput Ethereum Smart Contract Exchange

IDMoB - IoT Data Marketplace on Blockchain.

Komodo BarterDEX

Kyber Network whitepaper

Localbitcoins

Loopring: A decentralized token exchange protocol

Mind my value - a decentralized infrastructure for fair and trusted IoT data trading.

Open bazaar protocol

Polkadot: Vision for a heterogeneous multi-chain framework

Republic Protocol: A decentralized dark pool exchange providing atomic swaps for Ethereum-based assets and Bitcoin

Resource Control in P2P Cryptocurrency Networks

SmartExchange: Decentralised Trustless Cryptocurrency Exchange

Swap: A Peer-to-peer Protocol for Trading Ethereum Tokens

Waves.Exchange | Buy crypto with 0% fees

XCLAIM: Trustless, Interoperable, Cryptocurrency-Backed Assets

(via @papersapp) https://static.xcj.com/uploads/20180518/xumb4xmv3o1516701172833.pdf http://dl.acm.org/citation.cfm?doid=3229863.3275603 https://link.springer.com/chapter/10.1007/978-3-030-05764-0_6 https://dblp.org/rec/journals/iacr/SoskaKCD16 https://docs.bisq.network/exchange/whitepaper.html https://cryptorating.eu/whitepapers/BitShares/bitshares-general.pdf https://link.springer.com/chapter/10.1007/978-3-319-64701-2_53 https://dl.acm.org/doi/10.1145/3158333 https://ieeexplore.ieee.org/document/8516610/ https://assets.pubpub.org/ob89i66u/61573938834913.pdf https://etherdelta.com http://dl.acm.org/citation.cfm?doid=3341301.3359636 http://arxiv.org/abs/1910.11216v2 https://ieeexplore.ieee.org/document/8525388/ https://files.kyber.network/Kyber_Protocol_22_April_v0.1.pdf https://localbitcoins.com https://raw.githubusercontent.com/Loopring/whitepaper/master/en_whitepaper.pdf http://dl.acm.org/citation.cfm?doid=3131542.3131564 http://docs.openbazaar.com http://scholar.google.comjavascript:void(0) http://arxiv.org/abs/1810.11675v1 https://link.springer.com/chapter/10.1007/978-3-030-04849-5_32 https://swap.tech/whitepaper/ https://waves.exchange https://ieeexplore.ieee.org/document/8835387/

Blockchain-based Energy Trading

Blockchain-based electricity trading with Digitalgrid router

Consortium Blockchain for Secure Energy Trading in Industrial Internet of Things.

Crypto-trading: Blockchain-oriented energy market

Energy trading for fun and profit buy your neighbor's rooftop solar power or sell your own-it'll all be on a blockchain

Implementation of blockchain-based energy trading system

Privacy-Preserving Energy Trading Using Consortium Blockchain in Smart Grid.

Security and Privacy in Decentralized Energy Trading Through Multi-Signatures, Blockchain and Anonymous Messaging Streams.

Towards resilient networked microgrids: Blockchain-enabled peer-to-peer electricity trading mechanism

(via @papersapp) https://ieeexplore.ieee.org/abstract/document/7991065/ http://ieeexplore.ieee.org/document/8234700/ https://ieeexplore.ieee.org/abstract/document/8240547/ https://ieeexplore.ieee.org/abstract/document/8048842/ https://www.emerald.com/insight/content/doi/10.1108/APJIE-12-2017-037/full/html https://ieeexplore.ieee.org/document/8613816/ https://dblp.org/rec/journals/tdsc/AitzhanS18 https://ieeexplore.ieee.org/abstract/document/8245449/

Matchmaking

0x: An open protocol for decentralized exchange on the Ethereum blockchain

Etherdelta

Libra - Fair Order-Matching for Electronic Financial Exchanges.

Loopring: A decentralized token exchange protocol

Swap: A Peer-to-peer Protocol for Trading Ethereum Tokens

The cost of decentralization in 0x and EtherDelta

(via @papersapp) https://static.xcj.com/uploads/20180518/xumb4xmv3o1516701172833.pdf https://etherdelta.com http://dl.acm.org/citation.cfm?doid=3318041.3355468 https://raw.githubusercontent.com/Loopring/whitepaper/master/en_whitepaper.pdf https://swap.tech/whitepaper/ https://hackingdistributed.com/2017/08/13/cost-of-decent/

Prediction Markets

A permissioned blockchain-based implementation of LMSR prediction markets.

A Smart Contract Oracle for Approximating Real-World, Real Number Values

Augur: a decentralized, open-source platform for prediction markets

Decentralized Prediction Market Without Arbiters.

Gnosis whitepaper

(via @papersapp) https://linkinghub.elsevier.com/retrieve/pii/S016792361930257X https://drops.dagstuhl.de/opus/volltexte/2020/11970 http://cryptoverze.com/wp-content/uploads/2019/01/augur.pdf http://link.springer.com/10.1007/978-3-319-70278-0_13 http://scholar.google.comjavascript:void(0)

Security Aspects of Trading

Flash Boys 2.0 - Frontrunning, Transaction Reordering, and Consensus Instability in Decentralized Exchanges.

Footprints on a Blockchain: Trading and Information Leakage in Distributed Ledgers

On the impossibility of fair exchange without a trusted third party

On the optionality and fairness of Atomic Swaps.

Provisions: Privacy-preserving Proofs of Solvency for Bitcoin Exchanges

The cost of decentralization in 0x and EtherDelta

The Decentralized Financial Crisis: Attacking DeFi

Zexe - Enabling Decentralized Private Computation.

(via @papersapp) https://dblp.org/rec/journals/corr/abs-1904-05234 http://jot.pm-research.com/lookup/doi/10.3905/jot.2017.12.3.005 https://pdfs.semanticscholar.org/208b/22c7a094ada20736593afcc8c759c7d1b79c.pdf http://dl.acm.org/citation.cfm?doid=3318041.3355460 http://dl.acm.org/citation.cfm?doid=2810103.2813674 https://hackingdistributed.com/2017/08/13/cost-of-decent/ http://arxiv.org/abs/2002.08099v1 https://dblp.org/rec/journals/iacr/BoweCGMMW18

Settlement Mechanisms

A protocol for interledger payments

Atomically Trading with Roger - Gambling on the Success of a Hardfork.

Blockchain-based secure digital asset exchange scheme with QoS-aware incentive mechanism.

Blockchain-based settlement for asset trading

Blockchain router: A cross-chain communication protocol

Bootstrapping a Blockchain Based Ecosystem for Big Data Exchange.

Centrally Banked Cryptocurrencies.

Cross-asset trading within blockchain networks

Cross-Chain Payment Protocols with Success Guarantees

DeXTT - Deterministic Cross-Blockchain Token Transfers.

Escrow Protocols for Cryptocurrencies - How to Buy Physical Goods Using Bitcoin.

Fair and Decentralized Exchange of Digital Goods.

Fair Two-Party Computations via Bitcoin Deposits.

FairSwap - How To Fairly Exchange Digital Goods.

Hallex: A trust-less exchange system for digital assets

How to Use Bitcoin to Design Fair Protocols.

Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains

HyperPubSub - Blockchain Based Publish/Subscribe.

Implementing an Asset Trading System Based on Blockchain and Game Theory

Liquid Speed: On-Demand Fast Trading at Distributed Exchanges

Market design for trading with blockchain technology

On the impossibility of fair exchange without a trusted third party

Optimistic Protocols for Fair Exchange.

PEX - Privacy-Preserved, Multi-Tier Exchange Framework for Cross Platform Virtual Assets Trading.

Pisa - Arbitration Outsourcing for State Channels.

Proof of Delivery of Digital Assets Using Blockchain and Smart Contracts.

Real-time Money Routing by Trusting Strangers with your Funds.

Resource trading in blockchain-based industrial Internet of Things

SDTE - A Secure Blockchain-Based Data Trading Ecosystem.

Towards Decentralized Equilibrium Asset Trading Based on Blockchain.

Trading Real-World Assets on Blockchain - An Application of Trust-Free Transaction Systems in the Market for Lemons.

Trading Stocks on Blocks - Engineering Decentralized Markets

Trust Is Risk - A Decentralized Financial Trust Platform.

Usable optimistic fair exchange.

XChange - A Blockchain-based Mechanism for Generic Asset Trading In Resource-constrained Environments.

XCLAIM: Trustless, Interoperable, Cryptocurrency-Backed Assets

(via @papersapp) http://blockchainlab.com/pdf/interledger.pdf http://link.springer.com/10.1007/978-3-319-67816-0_19 https://ieeexplore.ieee.org/document/8808111/ https://academic.oup.com/rfs/article-abstract/32/5/1716/5427772 http://ieeexplore.ieee.org/document/8029360/ https://dblp.org/rec/conf/ndss/DanezisM16 https://patents.google.com/patent/US20190311351A1/en http://arxiv.org/abs/1912.04513v1 http://arxiv.org/abs/1905.06204v1 http://link.springer.com/10.1007/978-3-319-70972-7_18 https://dblp.org/rec/journals/corr/abs-2002-09689 http://link.springer.com/10.1007/978-3-662-44774-1_8 https://dl.acm.org/doi/10.1145/3243734.3243857 https://dblp.org/rec/journals/iacr/BentovK14 http://dl.acm.org/citation.cfm?doid=3190508.3190538 https://ieeexplore.ieee.org/document/9049532/ https://ieeexplore.ieee.org/abstract/document/8945822/ http://arxiv.org/abs/1907.10720v1 http://blockchain.cs.ucl.ac.uk/wp-content/uploads/2016/11/Paper_18.pdf https://pdfs.semanticscholar.org/208b/22c7a094ada20736593afcc8c759c7d1b79c.pdf http://portal.acm.org/citation.cfm?doid=266420.266426 https://ieeexplore.ieee.org/document/9045515/ http://dl.acm.org/citation.cfm?doid=3318041.3355461 https://ieeexplore.ieee.org/document/8501910/ https://ieeexplore.ieee.org/document/8696786/ https://ieeexplore.ieee.org/abstract/document/8657779/ https://ieeexplore.ieee.org/document/8759960/ https://ieeexplore.ieee.org/document/8855688/ http://link.springer.com/10.1007/s12599-017-0499-8 https://link.springer.com/chapter/10.1007/978-3-319-59144-5_34 https://dblp.org/rec/journals/iacr/LitosZ17 https://linkinghub.elsevier.com/retrieve/pii/S138912861100301X http://arxiv.org/abs/2004.05046v1 https://ieeexplore.ieee.org/document/8835387/

Various

Attacking the DeFi Ecosystem with Flash Loans for Fun and Profit.

Beware the Middleman - Empirical Analysis of Bitcoin-Exchange Risk.

Blockchain-enabled Intelligent Asset Exchange for a Circular Economy.

Challenges and Opportunities Associated with a Bitcoin-Based Transaction Rating System.

Dispute Resolution for Smart Contract-based Two-Party Protocols.

Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains

Measuring the Longitudinal Evolution of the Online Anonymous Marketplace Ecosystem.

Overview of Emerging Blockchain Architectures and Platforms for Electronic Trading Exchanges

Peer Review - Toward a Blockchain-enabled Market-based Ecosystem.

Shared Ledger Accounting - Implementing the Economic Exchange pattern.

The Economics of Cryptocurrency Pump and Dump Schemes

The Emerging Role of Electronic Marketplaces on the Internet.

Tokenization: Open Asset Protocol on Blockchain

Towards atomic cross-chain token transfers: State of the art and open questions within tast

(via @papersapp) http://arxiv.org/abs/2003.03810v2 http://link.springer.com/10.1007/978-3-642-39884-1_3 https://dblp.org/rec/journals/ercim/AskoxylakisAD17 http://link.springer.com/10.1007/978-3-662-44774-1_3 https://ieeexplore.ieee.org/document/8751312/ http://dl.acm.org/citation.cfm?doid=3190508.3190538 https://dblp.org/rec/conf/uss/SoskaC15 http://www.ssrn.com/abstract=2867344 https://dblp.org/rec/journals/cais/Avital18 https://linkinghub.elsevier.com/retrieve/pii/S0306437919304892 https://papers.ssrn.com/abstract=3310307 http://portal.acm.org/citation.cfm?doid=280324.280330 https://ieeexplore.ieee.org/abstract/document/8711021/ https://dsg.tuwien.ac.at/projects/tast/pub/tast-white-paper-1.pdf

[jverbraeken]

Thanks a lot for the suggestions @synctext @devos50 👍🏻👍🏻 I hadn't heard of Augur yet, very interesting project indeed! Will change my proposed taxonomy a bit to allow for prediction markets. Would be great if you could share your summaries of those papers @devos50! My holiday is over unfortunately, from July onwards I'll dedicate all my time to this thesis project

[jverbraeken]

great taxonomy start! Trustchain is consensus-free, thus no electricity for mining. What are two isolated markets that can be merged into a single infrastructure? Preferably with low competition, high fees, low innovation, and incentives to use your open alternative.

I'd need to look more into that. At first sight, I'd say that Tinder is a great example since they have a near-monopoly, very high fees, and close to no innovation.

[devos50]

I'd need to look more into that. At first sight, I'd say that Tinder is a great example since they have a near-monopoly, very high fees, and close to no innovation.

See Matchpool: dating on a blockchain

You can collect 'arrows' by proposing love interests. You are rewarded with more arrows as the relationship advances and gets more intimate 😄.

[jverbraeken]

Haha nicee, awesome project 😂😂

[synctext]

Coming 6 weeks:

• come up with wow-factor stuff
  • Example: an open market for tax evasion for normal people
  • now only the elite can do tax minimisation. Always use a proxy. At least 200 private jet aircraft have been imported through "the Isle of Man" and cut tax bills by £790m ($1bn).
  • digitize the Vermont-EU private tax-free pension buildup or the https://en.wikipedia.org/wiki/Paradise_Papers proxies for zero-taxation
  • lega online market for services which minimize your tax through loopholes.
  • Moral high-ground: grow political will to plug the holes that the elite exploits.
  • ToDo: find an bootstrap thesis prototype and showcase market
• beyond engineering, https://github.com/jverbraeken/UniversalMarket/wiki/Plan
• Freeze the final direction in 3 month
• it has to have scientific grounding for highest grade, novel algorithm or architecture
• make markets safe: escrow, iterative payment versus delivery
• make markets universal, build upon FBase "device drivers" for specific markets
• build upon programmable money of Internet-of-Money IBAN integration
• go beyond target2
• Advise: read complex papers by the IMF and federal reserve
• Fully distributed can be very fast
• Focus on a core problem, like Fairswap mentioned above.

Universal market research questions from kick-off presentation:

• Universal market: search in all these goods, semantics, and relevance ranking
• Universal market: large storage requirement of all these product descriptions, 1 number to rule them all (everybody switch to the Joost Numbering System (JNS))
• Universal market: custodians, open market, transparent, and low-cost

Existing:

• https://github.com/Tribler/trustchain-superapp/blob/master/README.md#ai-trading-bot
• https://play.google.com/store/apps/details?id=nl.tudelft.trustchain

[jverbraeken]

[synctext]

Please read the current status of our global AI marketplace tooling: https://github.com/Tribler/tribler/files/4929974/Dollynator.-.Final.Report.pdf After contributions by 31 students in various courses over the years, it is quite sophisticated. Bug-free also obviously :wink:

[jverbraeken]

15 additional screenshots

              

[synctext]

• https://github.com/jverbraeken/UniversalMarket/wiki/Points-for-consideration
• Follow a structured process;
  • no wow-factor! thesis direction found yet.
  • read ideas of others to come up with superior smart ideas
  • August: document 10+ thesis ideas in few sentences; scientific challenge (axiomatic science: the market primitive! Cheating is guaranteed to be eventually detected; infra: bitshares, waves, etc,; Matching algorithms for trades; ID: no trolls, intermediaries: trustworthy; persistence and finality: core concepts; decentralised finance: P2P lending constructs; Market leaders: Amazon,Target2; custodian: boring stuff)
  • September: pick your top-3 ideas, expand them to 1 page of scientific challenge + state-of-the-art, related work.
  • September 30: decide on direction.
  • October: fully focus on single direction.
• Decentral systems:
  • latency is not a problem in (de)central systems, its about engineering excellence
  • long-tail is not a problem in (de)central systems, its about engineering excellence
  • right to be forgotten is not a problem in (de)central systems, its about engineering excellence
• new insight: market primitives for digital markets are easier. Involving the physical world introduces many messy problems. Easier to show novel science in the digital-only markets. Transactions are atomic, fraud is easier to detect, tamper-proof logging solves honesty, incremental payments, and still markets are fragmented!
• Strong disincentive to establish a universal market. No monopoly power. if the single market is created, forces companies to join it.
• monopoly problems:
  • http://andras.niedermayer.ch/wp-content/uploads/2014/08/PFS-2016-06-27-AN-SL.pdf
  • https://papers.ssrn.com/sol3/papers.cfm?abstract_id=980755
• Universal market for digital goods:
  • Digital services (unique goods which can't be copied)
  • Steam alternative, content for gaming market
  • Spotify alternative, content for music industry
  • Netflix alternative, content for movie industry
  • Unify: limited supply, fixed price, bid/ask, lottery, etc.

[devos50]

Some (peer-reviewed) work related to your ideas: Domain Ontology for Digital Marketplaces.

[jverbraeken]

[synctext]

Ideas for thesis focus:

• middleware for distributed machine learning (toward decentralised computation)
  • mobile-first zero-cost AI (fully decentralised, zero-server, no upkeep cost)
  • resilient against abuse (troll army)
  • data never leaves mobile (only training vectors, etc)
  • it simply works (its not about the 10% state-of-the-art performance)
  • self-scaling (from 1 thousand to 1 billion users)
  • scientific progress: select those ideas which will scale it the real world and provide the empirical evidence.
• Second idea
• ToDo: the imperfect scientific paper which everybody jumps upon and improves upon. Seed a community and start a platform.

[jverbraeken]

We choose to focus first on federated learning (instead of distributed learning), because this field is less researched and poses more significant challenges regarding incentives/privacy/security. When this works, extending the functionality to support distributed learning is fairly trivial.

Some literature:

Must-haves

Step 1

Create IPv8 overlay in SuperApp and let it run on a few servers, see:

• https://github.com/Tribler/kotlin-ipv8/blob/8792a95243f84979dfeaaaf37fae78c8d0485df8/doc/OverlayTutorial.md
• https://github.com/Tribler/kotlin-ipv8/tree/8792a95243f84979dfeaaaf37fae78c8d0485df8
• https://github.com/Tribler/trustchain-superapp/blob/master/doc/AppTutorial.md

Step 2

Successfully train a CNN on the MNIST database on a single node

Step 3

Implement most basic gossiping protocol for distributed CNN-training: https://arxiv.org/pdf/1611.04581.pdf

• Create block type I: blk_parameters

Should-haves

Step 4

Prevent attacks (sybil + injection)

1. Strong identities by giving people €0,01 when they use the app and hashing their bank account
2. Peers select models by (1) taking a sample of models based on the reputation of the peers that created them, and (2) test their performance on their local data, take the 3 best performing models, and take the average of them
3. Letting everyone verify if contribution of a random other person improves the accuracy based on his/her own data => put this on the blockchain (RONI)
   • Create block type II: blk_reputation
   • Establish reputation based on KRUM, median, FoolsGold, ...
   • Problem: doesn't work well for non-IID environments, see: https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9066920
   • Put most emphasis on most recent interactions in calculating someone's reputation
   • Incentive mechanism: limit functionality of app when people don't train the model
   • Reputation calculation also based on how well a peer evaluates other peers

Literature:

• https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8832210
• https://arxiv.org/pdf/1811.09904.pdf (reputation denoted as "stake")
• https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8994206
• https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9150433 (want to take similar approach, but with reputations)

Step 5

Use differentially private noise to enhance privacy

• Also consider using Shamir secrets: https://arxiv.org/pdf/1811.09904.pdf
• Or make all peers completely anonymous
• Or apply dimensionality reduction (PCA): https://arxiv.org/pdf/1902.10799.pdf

Could-haves

Step 6

Replace SGD (that everyone uses, why???) with something way better https://ruder.io/optimizing-gradient-descent/index.html#whichoptimizertouse

Step 7

Develop a general supply/demand platform where people can request other people to train their models, people choose which models they want to train

• Financial incentives
• Both federated and distributed learning

Step 8

Take the average of lots of models in the early stages of the network (initially large fluctuations) and phase this averaging out when the model eventually converges

• Use averaging based on weights to put more emphasis on models trained with lots of training data (FedAVG / FedSGD)

[jverbraeken]

Research questions:

1. How can we prevent sybil/injection attacks in a decentralized federated learning system?
2. Practically all papers use SGD to train decentralized neural networks; would better parameter optimization methods also work well in decentralized settings?
3. Can we replace a blockchain to store the model parameters with an eventually consistent system (trustchain) to achieve superior performance?

[synctext]

Now it is really secure :laughing: ; key thesis selling point. Key related work: Biscotti.

Concrete thesis direction proposal: federated learning on edge devices is a new emerging field with significant promise, but numerous unsolved challenges around privacy, security, and incentives. This thesis will significantly address the state-of-the-art by demonstrating a performance leap beyond classical Gradient Decent, security advancement without reliance on external trusted third parties or services, address the privacy issue without introducing brittle zero-knowledge proofs, and provide incentive alignment. Our solution relies on secured gossip to address model pollution and Sybil attack by providing easy-to-use trust framework which utilises Internet latency diversity, graph analysis of user activity, and transaction properties for attack-resilience.

Concrete goal: in 6 weeks a "Poisoning attack" (Wednesday 21 Oct). Possible future sprints past this date:

• broader attacks
• broader attacks and taxonomy of defence mechanisms
• what dataset to use. For instance, high-impact social relevance on edge devices: Anticipating Accidents in Dashcam Videos dataset. video analysis is core of many scientific papers. Possible to release this inside Superapp, re-use code, ask volunteers to mount this in car, live network for scientific publication?
• incentive alignment, wild idea: Who sees the fastest car on the road today? Detect and show how fast cars are going which overtake you on the highway. Fun, improve safety and automatically publish photos with unredacted license plates to Trustchain. Re-use like https://github.com/pddenhar/OpenCV-Dashcam-Car-Detection

[jverbraeken]

Update September 23

1. Created new superapp module
2. Ping-pong between 2 devices
3. Train MNIST dataset on single phone
4. Simulate distributed MNIST training on single phone
5. Create an faster TFTP-alternative by sending ~50 messages simultaneously (speedup: ~11x faster)
6. Implement weighted averaging
7. Train MNIST dataset distributed on 2 phones

[synctext]

• Next step is fragmenting the dataset on 2 phones
• TFTP is 40 years old, modern protocol in Java: https://github.com/iiljkic/utp4j
• usage of https://github.com/eclipse/deeplearning4j/
• for comparison of achieved additional performance to related work it is required to use the usual datasets and usual configs.
• Focus on the test, attack emulation, and research infrastructure for 1 month?
• Attacks to test
  • "Honest, but curious" attack first
  • injection of spam/fake attack from 1 node
  • creation of numerous fake identities
• Defense:
  • Noise :-)
  • use Trustchain, latency diversity, and transaction graph properties

[synctext]

Please use the highly cited more modern HAL dataset, instead of MNIST. Deep Learning Towards Mobile Applications

[jverbraeken]

Update October 7

1. Implement UTP library (speedup ~9x faster)
2. Add CIFAR-10 and UCI-HAR dataset + well-performing neural networks
3. Redesign UI
4. Store relevant training information in custom log files that are easily accessible for the user
5. Compress model updates before sending them over the network
6. Enable the user to show/hide log entries from specific classes

Issue Simultaneously receiving/sending packets sometimes crashes => packets not always received by the listener

Links https://github.com/jverbraeken/trustchain-superapp https://github.com/jverbraeken/kotlin-ipv8 https://1drv.ms/u/s!AvNMRY4ml2WPgZhA-uL0CvZys_FopA?e=1tEZyo

[synctext]

Great progress again!

• Enhanced Kotlin IPv8 with UTP support, still has 1 pending bug
  • Complete packet drop when doing concurrent connections. Thus incoming & outgoing connections are not possible.
  • Create single end-to-end test please.
  • Create single end-to-end test with concurrent connections for debugging
• ML compression related work
  • Communication-efficient learning of deep networks from decentralized data
  • Federated Learning: Challenges, Methods, and Future Directions
  • Federated Learning: Strategies for Improving Communication Efficiency
  • Distributed Mean Estimation with Limited Communication
  • Distributed Consensus With Limited Communication Data Rate
• Possible directions (for end March deadline)
  • keep the Sybil attack central, security, ease of polluting models. An attack can be expressed in Euros.
  • identify cool highly cited papers
  • re-produce their algorithm in Superapp
  • select the next hot paper (FoolsGold, Mitigating Sybils in Federated Learning Poisoning)
  • kill it with fake identities for 100 Euro of cloud hardware
  • repeat and show that all known algorithms are flawed.
  • be mean: https://www.schneier.com/blog/archives/2017/08/confusing_self.html, a great paper: adversarial machine learning
  • bootstrap and state convergence.
  • core: federated learning speedup
  • concept of difficulty applied to federated ML: booststrap time, network partitions, faults, etc.
  • use a tamper-proof data structure to record progress
  • how to deal with 50MByte of progress data every 10 seconds (5 MByte/sec for every phone)
• Experimental results
  • Key to scientific article (REQUIRED)
  • Android emulation, cloud usage or DAS6
  • Run locally 4 instances on laptop

Red warning signs appear when a field produces a Survey-of-Surveys. Solid paper actually with 205 citations around Mobile Edge Computing (MEC).

[jverbraeken]

Update October 22

1. Solved the bug in UTP => sending and receiving simultaneously works and is stable
2. Configure and start machine learning task directly from command line
3. Thorough literature research
4. Started on literature review / thesis document (see https://1drv.ms/w/s!AvNMRY4ml2WPgZhhnJnQjTpIwT-5vw?e=WOJUlo)
5. Further delineating of thesis topic: "Byzantine-resilient, asynchronous, yet decentralized federated learning"

Main idea: Improve current state-of-the-art byzantine defense algorithm Mozi, see https://www.groundai.com/project/towards-byzantine-resilient-learning-in-decentralized-systems/

1. Main innovation 1: almost all current methods require a (significant) set of incoming samples to be able to take the average or median or something similar. I want to use a "moving window kind of thing" to let the agent update its model immediately when a new samples arrives
2. Main innovation 2: almost all papers use simple averaging; I want to use weighted averaging based on (a) how well a model scores and (b) how frequent a peer has already sent data (frequency filter, see https://arxiv.org/pdf/1802.07928.pdf)
3. Main innovation 3: almost all current algorithms require i.i.d. data. I want to loosen this unrealistic assumption (agent A has classes X and Y, agent B has classes Y and Z) and allow for non-i.i.d. data by sending the updated model only to nodes that are quite similar in terms of private data. I will do this by checking the cardinality of the private set intersection between the data labels of both nodes.
4. Evaluate the impact of a warm-start
5. Usage of ring communication (and compare this approach with random peers, close neighbors, etc.)
6. Be the first paper in this field to distinguish between exploration (asking other peers to send you their model) and exploitation (improving your own model), and formalizing the trade-off between these things
7. (Comparison with improved BRIDGE (BRIDGE cuts off the top #maxbyzantine and bottom #maxbyzantine incoming values. I reduce this 2b constraint to b by searching for the "most coherent" logical sequence of data (bit like Minimum-Diameter Averaging)))
8. (Maybe something with PCA to filter out byzantine values (probably doesn't work because there are many (!!!) more dimensions than training samples))
9. (Maybe something with RANSAC, particle filters, iterated/iterative filtering, Monte Carlo, ... These methods might also be useful to filter out byzantine values)

Other idea: (I think this approach yield worse performance than the former, because nodes can abuse their reputation, can make use of the fact that they don't have a reputation yet, can assign excellent reputation to malicious nodes or the other way around. Additionally, it still depends on an algorithm that combines incoming models (which should be, in my opinion, the algorithm described above) Trustchain-enabled reputation-assisted federated learning

1. First, every node receives models from other nodes + half blocks with the hash of the model signed by the sender
2. Node checks reliability of peers by checking the trustchain
3. Then the node tests every model with his own local data and puts on the trustchain another half block including the accuracy
4. The best performing models are combined with the BRIDGE algorithm and then further trained with the node's local data samples
5. The node tests if this final model performs better than his old model
6. If new model performs worse, throw it away
7. If new model performs better, send it to other nodes along with a half block containing the hash of the new model, signed with the node's private key

Question to Martijn/Johan:

• Perhaps we can use X.509 certificates for strong identities (certificate that binds a public key to a name which is signed by a trust anchor). How does this work in the decentralized blockchain-world?

[synctext]

• The solid progress needed for the trip towards Cum Laude by March
• Byzantine defense algorithm Mozi: "cars can collaboratively learn powerful models of traffic sign classification for autonomous driving; in a social network, users can learn better".
• Random failure, large-scale, already difficult enough not large-scale Sybil and collusion
• Random failures; No Data poisoning, no model poisoning attacks
• no targeted model poisoning, specific adversarial pixel pattern, no known defence..
• Thesis needs a "wow factor", include something like storyline below
• Blockchain lab is in need of AI in space
  • Defect and Fault Tolerance focus
  • Space radiation is known to flip bits, Injecting bit flip faults by means of a purely software approach: a case studied
  • Master course with 40+ students need a focus and attractive buzz
  • Why not mix&match all the SpaceX, Terminator AI, and Blockchain Gold
  • Space Investment Fund is a DAO which aims to be the first to launch byzantine- fault tolerant space swarm satellites.
  • This thesis provides the AI tech basis for this work
  • Delft has a satellite launch program and is home to several space companies
  • Get a good example dataset, sahara+satellite+data
• Actual space-based satellite "train" from NASA
• This thesis is about core technology, generic in nature and broadly applicable. To showcase the new possibilities we unlock beyond MNIST we introduce JoostSpace.
• With Zulu server, 5 x 512 GByte memory in our Tribler cluster; 250 instances may be possible
• Learn-To-Learn. Building on Alphazero, adversarial learning, competitive self-play, evolutionary learning. We generated several theories and did a meta-emulation to determine the fitness. What Fitness function?
• 23 Sep 2020 paper: Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation
• Mozi, 70 nodes, 2 week target to reproduce, Byzantine = 50%. "Fig. 5: The worst accuracy of the benign nodes under the bit-flip attack."

[devos50]

I've read the MOZI paper in detail to get a better understanding of the field and techniques used.

I see how their approach is novel (combining distance-based and performances-based vector selection), however, I am slightly confused by the experimental results. Figure 6 shows that MOZI is indeed resilient against common attacks, but not more significantly than DBulyan. In fact, MOZI sometimes exhibits less accuracy than other aggregation rules, e.g., simple average, even under the sophisticated attack (Figure 6c). The "average" strategy actually seems to perform very well in most cases, and shows decent convergence. The authors claim that "the advantage of MOZI over other strategies is obvious" but I strongly disagree with this claim. Figure 7 shows "average" is also very performant compared to MOZI. What are then the main reasons why one should pick MOZI? Am I missing something here?

Some other comments/questions:

• The paper mentions two use-cases for decentralized learning: Internet-of-Vehicle and recommendations in social networks. The latter use-case is close to what we aim to do in our lab, also see #3752. There should be another open issue for music recommendation somewhere. The evaluation of the paper is not tied to a specific use-case, which potentially undermines their results since it is not a realistic experimental setup with respect to an application domain. You should keep this in mind for your own evaluation.
• I noticed that the paper assumes that network messages do not get lost. Their Byzantine behaviour only considers sending carefully-crafted estimates to neighbours.
• As we also discussed last week, a key design decision of your system is synchronous learning vs asynchronous learning. The MOZI authors opt for synchronous learning.
• Why is it not realistic to add an additional validation dataset to a centralised parameter server?
• It was not clear to me how the "connection ratio" is defined. Was this described in the paper?

[jverbraeken]

WIP update November 9

1. Fixed several super nasty bugs with UTP (ConcurrentHashMap instead of regular HashMap, Dispatchers.IO context for coroutine instead of default context, incorrect timing between threads, etc.)
2. Discovered that restarting my laptop when packages are not being delivered anymore often magically solves the problem and endless hours of debugging
3. Sending and receiving UTP from/to many peers simultaneously works correctly
4. Created batch script / Visual Basic file to redirect localhost ports to the emulator ports + changed source code of android-ipv8 to send updates to peers with the same IP-address to localhost instead of the network
5. Everything running stable on 4 emulators (together with Android Studio consuming 27GB of RAM)
   • However, only with the tiny MNIST dataset to prevent out-of-memory exceptions
   • More emulators gets really slow
6. Create for every peer a random (seed=port) training/test dataset with a user-configurable number of samples per class
7. User can select communication pattern
   • Communicate updates to everyone (too slow, discommend using this option at the moment)
   • Communicate updates to random peer (during my first trial run this resulted in the sequence: 59235, 59243, 59243, 59235, 59235, 59235, 59235, 59235, 59243. This is random, but clearly suboptimal)
   • Communicate updates in a round-robin schedule
   • Communicates updates in a ring schedule (e.g. peer 1, 2, 4, 8, 16, 32, ..., 1, 2, 4, ...)
8. Implemented Coordinate-Wise Median, Trimmed Mean, Krum, BRIDGE, and MOZI
9. Implemented 3 behaviors (including 2 data poisoning attacks): benign, noise attack, label-flip attack
10. Implemented 3 model poisoning attacks (Fang, 2020): https://www.usenix.org/system/files/sec20summer_fang_prepub.pdf
11. Full redesign of the UI
    • 

Also discovered some weird quirk in MOZI: when all other peers have a model that results in worse performance than the peer's own model, the peer will still average its own model with the model of the best other peer.

• Advantage: when peer has overfitted on its own data, using the model of the other peer can improve the peer's model
• Disadvantage: the assumption that the algorithm works well, even when all other nodes are malicious, doesn't hold anymore

[jverbraeken]

@devos50 Thanks for your comment!

I see how their approach is novel (combining distance-based and performances-based vector selection), however, I am slightly confused by the experimental results. Figure 6 shows that MOZI is indeed resilient against common attacks, but not more significantly than DBulyan. In fact, MOZI sometimes exhibits less accuracy than other aggregation rules, e.g., simple average, even under the sophisticated attack (Figure 6c). The "average" strategy actually seems to perform very well in most cases, and shows decent convergence. The authors claim that "the advantage of MOZI over other strategies is obvious" but I strongly disagree with this claim. Figure 7 shows "average" is also very performant compared to MOZI. What are then the main reasons why one should pick MOZI? Am I missing something here?

Well, simple average results indeed in better performance than MOZI, but the authors mention that "For baseline, we consider the same decentralized system configuration without Byzantine nodes, and using the Average Aggregation rule (Equation 2). The model trained from this setting can be regarded as the optimal one."

The paper mentions two use-cases for decentralized learning: Internet-of-Vehicle and recommendations in social networks. The latter use-case is close to what we aim to do in our lab, also see #3752. There should be another open issue for music recommendation somewhere. The evaluation of the paper is not tied to a specific use-case, which potentially undermines their results since it is not a realistic experimental setup with respect to an application domain. You should keep this in mind for your own evaluation.

Thanks! I'll keep that in mind 👍🏻. The HAR dataset (that is implemented in the current version) is a pretty realistic use-case I think.

I noticed that the paper assumes that network messages do not get lost. Their Byzantine behaviour only considers sending carefully-crafted estimates to neighbours.

Mmh, yeah that's correct, and currently the same on my setup because messages don't get lost between emulators since all network traffic is on the same computer. However, I think it's reasonable to make the attackers as strong as possible to simulate a worst-case scenario (attackers are weaker when their packets get lost on the way to the benign node).

As we also discussed last week, a key design decision of your system is synchronous learning vs asynchronous learning. The MOZI authors opt for synchronous learning.

Exactly! Asynchronous learning with lots of nodes that are significantly lagging behind is much more challenging that synchronous learning and has received relatively little attention from the scientific community. The authors also assume an i.i.d. dataset instead of a non-i.i.d. dataset which makes everything a lot easier. I think I'll focus first on tackling the non-i.i.d. challenge (since the i.i.d. assumption is completely ridiculous in real-life) and maybe in a later stage focus on making the algorithm work in asynchronous settings (because synchronous settings are actually realistic in real-life; you can "simply" synchronize every day with the other nodes)

Why is it not realistic to add an additional validation dataset to a centralised parameter server?

Good question! It is very realistic and there is a lot of literature using this approach. However, it can be hard to get enough data because the data might be very privacy-sensitive (e.g. Whatsapp messages, Tinder recommendations, or photos). Additionally, unless you get all data from all users (in which case federated learning doesn't make sense) you will have a lot more validation data when users validate incoming updates themselves (this doesn't always result in better performance because the validation data is scattered across all users, but hey, topic for future research).

• It was not clear to me how the "connection ratio" is defined. Was this described in the paper?

No, the authors forgot to mention that. I think that connection ratio refers to the fraction of nodes with which every node communicates its updates

[devos50]

Possibly related work:

• Detecting Fake Accounts on Social Media
• Distributed stochastic gradient descent for link prediction in signed social networks
• Social recommendation algorithm based on stochastic gradient matrix decomposition in social network

[synctext]

• Follow the standard papers within the field: "Yet another superior defence"?
  • General Internet-deployed Federated Learning Framework
  • Or sell the science
• Current state-of-the-art: it only works in fantasy papers with ideal data input, ignores time (one-shot; no real-time incoming data), and ideal correlation (IID, no real-world power law, distributions, and correlations)
  • data decay, cold start, network is converged
  • "Real-World data and model" storyline (Your described innovation 1 & 3 in above comments)
• What is your key selling point of thesis? Wow-factor?
• Evaluation section (obviously MNIST) with:
  • ?Medical: CH-MNIST and Breast Cancer Wisconsin (Diagnostics)
  • ? Deceptive Youtube content, and/or Fake accounts problem, etc.

[jverbraeken]

Minor update:

• Much better on-device simulation. Can simulate with 32GB RAM a maximum of 75 nodes. Note that this is a simulation, so the results are different for a truly distributed setting
• Started on a script to run all tests after each other

  Major update:

  Implemented 1st version of BRISTLE (Byzantine-Resilient decentralIzed StochasTic Federated lEarning)

• Or perhaps prepend "pro" to emphasize that my solution focuses on practical real-life scenarios? => Pro-BRISTLE (Practical yet Robust Byzantine-Resilient decentralIzed StochasTic Federated lEarning) About fancy datasets
• I think it's important to keep the focus on the defense mechanism part, because that's the innovative contribution of the paper. The "wow factor" comes from the fact that this algorithm is not only decentralized (just like Byrdie, BRIDGE, and MOZI), but is also unique in several aspects: it can handle non-i.i.d. data, and can work in an asynchronous setting, both of which are complex to achieve. Creating/using a fancy dataset doesn't add a lot to the scientific contribution of BRISTLE and deserves its own paper because creating a proper neural network for a complex dataset is highly non-trivial
• The UCI Human Activity Recognition dataset is the most popular on Kaggle (https://www.kaggle.com/datasets?search=smartphone&sort=votes), resembles a typical real-life scenario and has enough training samples (namely 7350). Therefore I'll use this dataset for my research.
• Additionally I'll use the MNIST dataset, because this dataset is used by practically every paper in the FL domain.
• Finally, I'm considering using the CIFAR-10 dataset which is also very popular, easy to transform to a non-i.i.d. version, and considerably more complex than MNIST and HAR.

  Features

• Direct averaging of results => nice so that your models isn't learning many iterations on a sub-optimal model
• Better outlier detection because of keeping track of last x updates
• Exploration vs exploitation strategy to enable fully asynchronous program
• Private set intersection cardinality (PSI-CA) to enable non-i.i.d. support

Structure of thesis

Results

(I'm not sure if this is the way to go... There are a lot of different variables that can be combined in a lot of different ways...)

Pseudocode

Pseudocode old version, you can skip this, perhaps slightly more readable than the formal version

Main:

similarPeers <- getSimilarPeers()
network = createNetwork()
trainDataSetIterator, testDataSetIterator = createIterators()

repeat:
    network.fit(trainDataSetIterator.nextBatch()
    if models received from other peers:
        averageParams = integrateParameters(network)
        network.setParameters(averageParams)
        recentOtherModels.add(newOtherModels)
        limit recentOtherModels to the 20 most recent models
    endif
end repeat

integrateParameters:

distances = euclideanDistance(ownModel, newOtherModels, recentOtherModels)
exploitationModels = first X models with the smallest distance
Exclude non-new models from exploitationModels
explorationModels = from (distances \ exploitationModels \ recentOtherModels), randomly select Y models
combinedModels = exploitationModels ∪ explorationModels
calculate for the peer's own model per class the loss on a random data sample
calculate for all combinedModels the loss on the same random data sample
calculate weight for every combined model
set new model to weighted average of combined models

calculateWeights

for every peer:
    C = cardinality of PSI with peer
    bestClasses = the C classes with the lowest loss for the other peer
    smallestOtherLoss = sum of the losses of the other peer for bestClasses
    smallestOwnLoss = sum of the losses of self for bestClasses
    weight = max(0, 8 - 4 * (smallestOtherLoss / smallestOwnLoss)

getSimilarPeers:

[synctext]

:clap: :fireworks: :clap: You have reached the milestone of a thesis conceptual outline! (towards end-March) Now I would recommend keeping focus on getting state-of-the-art results, and possibly tweak until you get solid results. No gap between simulation and real-world ML. practical stuff on port forwarding emulators

Key focus: how to sell your idea

Experiments:

• different datasets
• different scale
• different attacks types
• different attack strengths
• different Byzantine faults (ref1 and ref2, plus https://github.com/rolandomar/hermes) upto 100%
• failure of prior work

[jverbraeken]

Probleem: Mijn oplossing werkt erg slecht als de nodes hun onvolledige neural networks moeten combineren tot 1 gezamenlijk neural network. Hoe kan dit worden opgelost? Door gebruik te maken van een geavanceerde techniek genaamd Elastic Weight Consolidation. Ik heb iets van 2 weken eraan zitten werken, maar deeplearning4j (de enige machine learning library die werkt op Java) is totaal niet geschikt voor het implementeren van deze techniek. Tensorflow is hier véél geschikter voor, maar werkt alleen op Python (helaas zijn Android apps altijd in Java). Wat zijn de mogelijkheden?

1. Geen Android app maken maar een normale Windows/Linux app (maar dan gooi ik wel effectief maanden aan werk weg, aangezien veel tijd zat in code specifiek in de superapp)
2. Mijn algoritme niet geschikt maken voor non-i.i.d. data (wat nou juist de belangrijkste innovatie was van het hele algoritme)
3. Gebruik maken van een andere techniek. Hierbij moet ik veronderstellen dat een klein gedeelte van de training data wel degelijk publiek beschikbaar is (redelijke veronderstelling, maar toch jammer dat ik deze moet maken). Deze techniek is bovendien minder effectief. Ik kan wel eventueel daarnaast in Python wel de effectiviteit van Elastic Weight Consolidation laten zien, en dan in mijn thesis beargumenteren dat zodra Tensorflow ook op Android werkt we dan alle reden hebben om aan te nemen dat met Elastic Weight Consolidation mijn algoritme nog een stuk effectiever is.

De laatste optie heeft momenteel mijn voorkeur.

[jverbraeken]

Update December 12

1. Researched EWC for 2 weeks, but this technique is with the current libraries available for Android software development infeasible (see post above).
2. Automated generation of all figures with one click of a button
3. Re-added CIFAR-10 and HAR to the available datasets (needed to be rewritten so that we can get more fine-grained insight into their performance)

Specific scenario's in which my algorithm will probably outperform other algorithms

1. When our node generates very litle data while all other nodes generate tons of data
2. When (for example due to high bandwidth costs) other nodes only send very seldom an update of their parameters
3. When our node joins in quite late, when all other nodes already have much better performance
4. When the nodes have data of different classes (with some overlap in-between)

Other announcement:

1. A few weeks ago I was pretty busy at De Kleine Consultant (consultancy organization in Delft), so I could spend less time on my thesis. Mid-January I'll manage a team as a Project Manager which will take ~15-20 hours per week. That is why I plan to finish my thesis probably a month later (end of April).

[synctext]

ToDo for next meeting:

• Performance of Figures for state-of-the-art
• Reproduce in true decentral setting
• Focus on initial text of Results section + initial performance figures
• reminder: ask David Tax, Jesse Krijthe, or Marco Loog for their expert review

[jverbraeken]

Update January

1. Simulation results ready (results below are slightly outdated, fixed several bugs in the meantime)
2. Huge performance improvements (+- 24h => +- 6h to run the entire simulation)
3. Bug fixing in TFTP/UTP => fully distributed environment working
4. Cannot use the emulators anymore :(:(:(

[synctext]

• Solid results!
• Already sufficient for graduation.
• Now focus on boosting the core scientific contribution
• Further think about February as a dedicated month for high-risk research.

[jverbraeken]

Update January 27th

1. Finally got it working on the Zulu server => first results with 50 nodes (note: training takes 24 hours for test with 50 nodes, undetermined but significantly longer time for most complex model with 250 nodes). Unfortunately, the results don't seem to make sense, so have to do some bug fixing...
2. Also finished first distributed test with the maximum number of 16 nodes. Performance is quite a bit lower than in the non-distributed setting. Again lots of debugging needed
3. Finished significant part of my actual thesis
4. Determined research direction for coming weeks: achieving good performance in non-i.i.d. settings. A trivial rehearsal strategy yields okay-ish results, but the performance is not excellent. Techniques such as Elastic Weight Consolidation, SI, AR1, or AR* are all dependent on advanced custom loss functions (something that the library DeepLearning4j does not support :(:(:( ). However, it would very interesting to investigate other methods such as CWR+ and Generative Replay. These performance of these methods has never been investigated in a federated setting before and should significantly better performance than the methods currently being used (namely Rehearsal-based methods and EWC)

Thesis.pdf

[synctext]

• Solid status
  • simulation 250 nodes
  • emulation: 16 nodes
• Highest level of Thesis work is an accept in a top venue
  • build upon the fact that it actually works!
  • "Class A": https://sigir.org/sigir2021/call-for-demonstrations/index.html
• Private Set intersection cardinality is a performance killer, excursively usable in theory.
• How to combine strong byzantine fault tollerant, non i.i.d. data and offer decent performance?
  1. ignore outliers?
  2. Magic function to determine truth versus spam?
  3. federated learning: unique local dataset. You have local knowledge of what is correct, trustworthy, spam and fake.
  4. probabilistic? We can't identify bad actors, but we assume to be able to do some estimation. Use a DAG which indicates the trustworthiness of nodes.
  5. Above is silly idea: we are in supervised learning setting, we can test incoming models for superiority, replace our own inferior model and thus iterate towards perfection.
  6. Bootstrap vulnerability: no local data yet means you cant identify spam or adversarial data

[jverbraeken]

Update February 29th

https://www.tudelft.nl/en/student/eemcs-student-portal/education/graduation-msc/green-light

• Ontzettend goede performance op het MNIST dataset in non-i.i.d. setting. Absoluut een grote stap vooruit t.o.v. de huidige state-of-the-art
• Om te trainen op non-i.i.d. datasets gebruikt Pro-BRISTLE o.a. "deep transfer". Hiervoor moeten we veronderstellen dat er altijd wel een dataset beschikbaar is dat "een beetje lijkt" op het dataset dat de gebruiker wil trainen. Een "ongewenst" 🙈🙈🙈 bijeffect van deze techniek is dat het netwerk orders van grootte sneller leert met slechts een fractie van de netwerkcommunicatie. De performance van Pro-BRISTLE is hiermee totaal absurd veel beter dan die van de huidige state-of-the-art, maar dit komt dus door een "oneerlijk" voordeel: het gebruiken van een ander vergelijkbaar dataset.
• => daarom ga ik eerst de performance van de huidige state-of-the-art algoritmes laten zien. Daarna modificeer ik deze algoritmes met deep transfer en laat ik zien dat ze véél beter presteren. Daarna voeg ik resultaten van Pro-BRISTLE toe en laat ik zien dat dit algoritme in non-i.i.d. omgevingen en/of een asynchronous omgeving en/of een Byzantine omgeving aanzienlijk beter presteert
• Heb Pro-BRISTLE nog niet aan de praat gekregen voor meer complexe datasets dan MNIST... Batch normalization lijkt het probleem te zijn
• Obstakel is de tijd die nodig is om experimenten te runnen. Voor CIFAR-10 minimaal 24 uur op Zulu, voor goede performance nog langer
• Implementeren van deep transfer is vrij tijdrovend, omdat ik ook een vergelijkbaar dataset voor elk dataset moet toevoegen en hierop heel goede performance MOET halen omdat elke error uiteindelijk in het eindresultaat x2 terugkomt :(
• 75% accuracy gehaald op het WISDM dataset. Deze (of Mobi-Act) wil ik gebruiken voor deep transfer naar HAR (Human Activity Recognition). Kleine issues met verschillende sampling rates en vervuilde datasets
• Helemaal happy met Zulu :)

[jverbraeken]

Thesis.pdf

[jverbraeken]

Thesis.pdf

[synctext]

• PSI is vulnerable against brute force item discovery: https://arxiv.org/abs/2004.03976
• Fully connected component assumption, if you put a high PSI threshold
• Quick related work search on federated learning and non-iid data:
  • http://proceedings.mlr.press/v119/karimireddy20a.html (2020)
  • https://arxiv.org/abs/1806.00582 (2018)

[devos50]

I did a high-level screening of your thesis. Great work and good content! Below you can find my comments:

Overall major feedback:

• You are too humble with your contributions. Use language like: “We improved all key aspects of decentralized federated learning, presenting a realistic, attack-resilient solution for the first time. We envision broad use of our novel algorithms, bla bla etc. We experimentally demonstrate that Pro-Bistle is highly scalable and attack-resilient compared to state-of-the-art solutions”.
• Focus more on your contribution instead of enumerating all other work performed by others.
• (maybe something for discussion) you do a nice job of introducing ML and its role in society, but chapter 2 demands a lot from the reader (e.g., familiarity with concepts like convergence). Since the field is so broad and extensive, it is challenging to find the right balance between briefness and accuracy.
• You are explaining many, many algorithms in Chapter 2 which makes me feel lost as reader. Since your contribution is not fleshed out yet, it makes me wonder where this story goes. Adding hints to your solution would help with this.
• Formulating your research (sub)questions to the end of the introduction would improve the structure of your thesis. You can refer to these RQs in Chapter 2 and 3 and summarise in your conclusion how you addressed these RQs.
• Your thesis definitely improves state-of-the-art solutions but it is very hard to maintain a mental overview of all components, how they address the problems, and how they are inter-connected.

Overall minor feedback:

• Some references are broken.
• Make the spelling of Pro-Bristle consistent (this would be easier in LaTeX since you can write a macro for that).

Subtitle:

• new -> novel (the word ‘new’ is slightly informal in this context)

Intro:

• the first sentence of 1.1 is slightly misleading: you start with explaining statistics while the caption suggests that the paragraph is about machine learning.
• abbreviations like i.e. and e.g. should always be followed by a comma (so: i.e., its bias)
• 1.1 would benefit from some citations
• (nit) I personally don’t like using citations as nouns.
• “Why federated learning” should be a subsection I guess?
• Don’t use a quote as a full sentence (“Federated Learning brings the code …”)
• You repeated the parameter server explanation in 1.3 (it is already introduced in 1.2)
• I would like to see trade-offs when describing some of the design principles in 1.3.
• Suggestion: “ruined by” -> “subverted by”
• It is common to fully spell out numbers below twenty (3 major reasons -> three major reasons)
• Avoid using one-sentence paragraphs.
• Elaborate on what ‘synchronous’ and ‘asynchronous’ exactly means in this context.
• (nit) don’t use the character x to indicate a variable if you don’t use it later.
• Overall, I think section 1.3 (asynchronous) can be compressed.
• Stalled processes -> stale processes?
• You haven’t explained what i.i.d is but you refer to it in 1.4. Please elaborate it earlier (as a design principle I guess?)
• “There are several types of machine learning …” I feel that this sentences does not add much. P.lease elaborate on your solution instead and position your work accordingly later in the thesis.
• I also think you can merge 1.4 and 1.5 into “Key Contributions and Thesis Outline”

Chapter 2:

• “is commonly used here take an empirically” there is something wrong with this sentence.
• I would consider adding a figure showing a parameter server vs. not using a parameter server.
• You could structure 2.3 by using bold words at the beginning of your subsections (e.g., Krum - bla bla). Even though there a transition between paragraphs, it feels like a wall of text. More structure would also enable more familiar readers to skip descriptions they are familiar with.
• Not sure if this is common for Word documents, but you should add a label/caption to figures so you can reference to it. Figures feel detached from the text.

Chapter 3:

• Maybe make your assumptions (which are now at the start of Chapter 3) more explicit by adding a section ‘system model and assumption’. Here you can also state other characteristics of the target environment, e.g., the reliability of communication channels.
• “This part of Pro-Bristle is complex enough” -> suggestion: rephrase it to “For presentation clarity, we describe this part of Pro-Bristle in Section X”.
• In the “Non-i.i.d components” subsection, you talk about detection of Byzantine behaviour. Isn’t your goal to prevent it (which is a harder problem)?
• “These challenges are addressed … as illustrated in Figure 3. First, we take a step back”. Why take a step back? Don’t leave the reader hanging, please explain the Figure!
• Your pseudocode is not explained at all. Use line numbers and mark interesting parts.

Chapter 4:

• Just a few citations suffice to convince that MNIST is frequently used to evaluate algorithms in this domain.
• The threat model is something you should discuss earlier since it influences the design of your solution.
• Maybe 4.9 is more suitable to go to the ‘conclusion’ section (e.g., add a ‘reflection’ section). Great read though, I highly appreciate these discussions.

Chapter 5:

• (nit) Why use these pink/black boxes instead of subsections?
• Phrase the first sentence of Chapter 5 more positively, e.g., “Due to the unique properties of Pro-Bristle, it is challenging to directly compare it to existing methods. However, …”
• “The number of parameters is obviously …” suggestion: to structurally evaluate the extensive parameter space of our solution, we …”.
• Maybe you can make a table listing the default experiment parameters.
• I have never seen a legend at the bottom of the page, and the figures not attached to it.
• This chapter would benefit from subsections and more structure in general.