search

Tribler / tribler

Privacy enhanced BitTorrent client with P2P content discovery
https://www.tribler.org
GNU General Public License v3.0
4.74k stars 445 forks source link

blockchain-regulated markets #2559

Closed synctext closed 4 years ago

synctext commented 7 years ago

Marketplace with blockchain based reputation system supporting bid,ask, and cancel messages. 20160928_103741

Our previous running code, needs work: http://repository.tudelft.nl/islandora/object/uuid:c1816da8-c82e-47bc-bde2-4f35b9a3e775

synctext commented 7 years ago
synctext commented 7 years ago

Existing literature (no code, just ideas):

synctext commented 7 years ago

Economic theory foundation: https://scholar.google.nl/citations?view_op=view_citation&hl=en&user=ZEDUm5UAAAAJ&citation_for_view=ZEDUm5UAAAAJ:2osOgNQ5qMEC

synctext commented 7 years ago

Ongoing 15 pages of decentral markets survey .tex : https://github.com/Tribler/tribler/issues/2535

synctext commented 7 years ago

Related implementation on central server from 2011 that can handle 6 million orders per second on a single thread on a 3 GHz machine.

synctext commented 7 years ago

Getting started with coding:

devos50 commented 7 years ago

Additional resource: https://github.com/Tribler/dispersy/pull/517

synctext commented 7 years ago

The decentral market is now smoothly operational in Gumby: transactions

devos50 commented 7 years ago

Gumby experiment link: https://jenkins.tribler.org/job/pers/job/market_experiment_devos50/

Like the AllChannel experiment, this can (should?) become a performance/health indicator for our decentralised market.

synctext commented 7 years ago

Current survey draft. .pdf

Suggestions:

Sections:

related work: evolution over past 15 years: 

Some of the first research concerned with P2P agent-based marketplaces is that of
Youll [27]. In this work, a framework for an agent-mediated P2P marketplace was
suggested and implemented in Java using a centralized trader registry. Searching for
potential traders is done using an adaption of the Contract Net protocol [5]. The use of
Web Services that are based on standard protocols, e.g., WSDL and SOAP, along with a
decentralized registry implemented over a P2P network such as Gnutella (as suggested
in [17]) seems a more suitable choice for P2P marketplace implementations. The important
issue of traders’ trustworthiness was briefly mentioned in Youll’s work, but not
really handled. Coalitions between traders were not checked. In addition, no simulations
or analysis of experimental results were provided to justify why decentralized
marketplaces might be better than centralized ones.
Another justification for decentralized marketplaces can be derived from [16], where
a P2P-agent double continuous auction was presented. It was shown that such a decentralized
auction displays price convergence behavior similar to that of the centralized
auction. However, the P2P auction outperforms the centralized auction in the sense that
it has a constant cost in the number of message rounds needed to find the market equilibrium
price when the number of traders increases, whereas a central auctioneer incurs a
linear cost in this case. It would be interesting to extend this work and introduce quality
of products or trustworthiness of agents into the simulation.
Turner et al. describe in [23] a P2P resource market where buyers and sellers trade
their surplus resources, e.g., CPU cycles, storage, and bandwidth. They suggest that
each entity in the market might issue its own currency, and propose the Lightweight
Currency Protocol as a standard protocol for the interaction between users and currency
issuers. This protocol might be a building block on top of which P2P marketplaces
could be implemented.
The theoretical work of Neeman et al. [15] shows that when buyers and sellers
are given the opportunity to choose between trading through a centralized market or
through a decentralized one, they would both prefer the centralized option. However,
they assume in their work that a homogeneous product is traded and that the centralized
market incurs no costs. We are interested (by contrast) in the case where the product
traded is not necessarily homogeneous; products from different sellers may have different
qualities. Furthermore, not all trading partners can be assumed to be trustworthy.
This might lead to the emergence of coalitions based on trading relationships, explored
for example in [2].
devos50 commented 7 years ago

@basvijzendoorn these tickets seems to have overlap, see https://github.com/Tribler/tribler/issues/2535#issuecomment-260346273 for another table of content.

synctext commented 7 years ago
synctext commented 7 years ago

http://www.the-blockchain.com/2017/02/26/0x-open-protocol-decentralized-exchange-ethereum-blockchain/

synctext commented 7 years ago

ToDo Bas, read and run the code :

synctext commented 7 years ago

THE Core economic theory of markets from 1970: https://github.com/dmvaldman/library/blob/master/economics/Akerlof%20-%20The%20Market%20for%20Lemons.pdf

devos50 commented 7 years ago

Worked on a first very basic version of a Trustchain credits <-> BTC market in Tribler. I've integrated the Bitcoin wallet and made an API endpoint to get the balance, both confirmed and unconfirmed using the Electrum wallet. Note that the asks and bids are requested using the RESTful API. In addition, when Tribler discovers a new ask/bid, the list in the GUI is automatically updated and sorted accordingly.

market_screen

TODO (GUI-related):

synctext commented 7 years ago

good screenshot. will include it in grant submission for Tuesday.

devos50 commented 7 years ago

I've rewritten some of the wallet logic. We now support more than one wallet and each wallet has a short identifier. The main idea is that we have various wallets that holds assets, i.e.:

More wallets can easily be added in the future.

Also, some of the API endpoints have been rewritten. One can query all the wallets available with a call to GET /wallets. This returns a list of identifiers of each wallet (i.e. btc and mc). Each wallet has various methods that should be implemented:

This allows us to get rid of the PaymentProviders in the current decentralised market code and use wallets that are integrated in Tribler instead.

Finally, the GUI has to be redesigned slightly to support multiple wallets and multiple assets.

synctext commented 7 years ago

Good progress. If now API access is hacked, wallet access is possible. Needs to be hardend.

ghost commented 7 years ago

Privacy of Traders problem description https://www.sharelatex.com/project/58c7d6390d2b81b36b2736a3

synctext commented 7 years ago

0) connectable ! Control of wallet! New message order-match-made

@devos50 critical above item slipped of the roadmap. We need to detect if peer is connectable. Everything assumes full connectability.

devos50 commented 7 years ago

A small update here. Last week, I've been working on writing a big integration test that tests the decentralized market from ask/bid dissemination up to and including making transactions (with real bitcoin!). This works well and the Jenkins job can be found here: https://jenkins.tribler.org/job/pers/job/market_community_btc_credits_test/. The wallets used in this test are encrypted.

In addition, I've spent some time improving the incremental payments system. Also, I've included a bloom filter in each introduction request so the order books are synchronized between two users. This addresses bootstrapping problems since we have no persistency of orders in our market.

Also, the timeout mechanism of asks and bids has been fixed and I've added an event so orders are dynamically removed from the GUI. This all works pretty neat.

@synctext regarding the connectability of peers, I rather implement a generic check in Tribler for this since there might be more components in the future that requires connectability. Do you agree if we just disable creating new orders and display a warning if a peer is not connectable for a first iteration?

devos50 commented 7 years ago

BTC <-> Tribler reputation can now be exchanged without problems. In addition, I've added support for trading between multiple wallets, like a real currency exchange. This means that we can also add more types of wallets later.

devos50 commented 7 years ago

Existing decentralized solutions:

Comparable centralized solutions for cryptocurrency trading:

More related work:

(decentralized) matching:

This video explains why it's hard to build order books on the blockchain. I should note that they assume a "traditional" blockchain with proof-of-work consensus which causes latency and thus possibilities for market/order manipulation.

devos50 commented 7 years ago

Must-read related work: http://www.econinfosec.org/archive/weis2014/papers/Clark-WEIS2014.pdf

Jaapp- commented 7 years ago

Beta testing branch market_community: no tracebacks and able to do some trading. 2017-06-09-121448_1000x1075_scrot

MitchellHop commented 7 years ago

able to create negative balance on my Tribler reputation credits. We conducted a collusion attack on the live network. We did several back and forth transactions to create an endless amount of reputation. Note the -1*10^12 reputation in the screenshot below. screenshot from 2017-06-09 12-16-00

devos50 commented 7 years ago

Nashx: "NASHX is about enabling two untrusted parties to make safe exchanges online by putting them in a Mexican standoff. We put two untrusted parties into Nash equilibrium, through a military strategy called Mutually assured destruction so that neither party has anything to gain by scamming one another." (http://nashx.com/About)

They use a neat strategy but not decentralized. Also nice to read about http://en.wikipedia.org/wiki/Mexican_standoff and http://en.wikipedia.org/wiki/Mutually_assured_destruction :)

hownashxworks

devos50 commented 7 years ago

When running some experiments on a larger scale, it turned out that there were still some errors that occurred in very unlikely circumstances. It took me quite some hours to hunt these down and fix them since I had to go through many MBs of log files.

The experiment now seems to function as it should and I'm ready to extract the first graphs out of it.

transaction_graph-2

devos50 commented 7 years ago

First (very preliminary) results with an order book where the Google stock symbol is traded:

efficiency

Note that the total quantity traded is barely affected when the network size increases. This is a promising result but the order book itself does not generate a very high load on the network. I will try with another order book that generates more traffic to see what happens.

devos50 commented 7 years ago

TODO:

Progress: https://www.sharelatex.com/project/594baae7e341f31a47fc0a13

devos50 commented 7 years ago

Update: first experiment with a third-party matchmaker succeeded, time to scale this up and test it better. In the image below, node 1 is the matchmaker that matches node 2 and 3 who have created an ask and bid respectively.

transaction_graph-3

devos50 commented 6 years ago

Taxi experiment using a real-world Uber dataset up and running: https://jenkins.tribler.org/job/pers/job/taxi_experiment_devos50/.

synctext commented 6 years ago

Related work bitsquare decentral market: Redundant data storage (flooded to all peers) and Resistant against spam/flooding So please copy or try to understand their magical solution

devos50 commented 6 years ago

First initial results of taxi-simulation using the market:

bandwidth

matching_efficiency

matching_latency

devos50 commented 6 years ago

After considerable effort, I managed to compile and run bitshares on the DAS5 (so we can compare it against our own implementation). I had to compile my own version of GCC, OpenSSL, CMake and Boost but it seems to work now.

devos50 commented 6 years ago

After some thinking, I feel that that the we are not really using the power of (our) blockchain (TradeChain) in the market implementation. Instead of using TradeChain as a post-market ledger, I envision it to be the core component of the market, used to account all ask/bid/order cancels, transactions and payments. In this scenario, the market becomes properly blockchain-regulated (or blockchain-powered I guess).

There are various advantages of doing this, the most obvious one being that all operations in the market become tamper-proof and irrefutable (this is already a property of the decentralized exchanges I’m comparing with, i.e. Waves and Bitshares). Making TradeChain an essential component in the market helps to make a more fair comparison with other blockchain-based exchanges. Another advantages is that we can combine gossiping of the blockchain and order synchronization between peers (currently, these are two separate processes, leading to increased communication costs). Finally, it provides more transparency since all market manipulations are recorded on TradeChain.

The only problem I foresee here is that some operations recorded on the TradeChain do not involve a transaction counterparty, for instance, cancelling one of your own orders. As a consequence, the block that captures the order cancellation only contains one signature, namely your own. To ensure entanglement, I propose to use one of the matchmakers as “witness node” that verifies that you have cancelled the order.

I think we have a strong platform to sell after we make TradeChain our core component: decentralized and scalable matchmaking, irrefutable and transparent transactions, zero transaction fees and near-instant clearing and settlement.

@synctext do you agree with this?

devos50 commented 6 years ago

Got the experiment with the Waves platform completely working: https://jenkins.tribler.org/job/pers/job/waves_experiment_devos50/57/. However, it seems that they use a centralized matchmaker server so it's not as decentralized as they claim. Transfer of value is recorded on a global blockchain however. Also, for every new buy/sell order, a small transaction fee has to be paid to the matchmaker.

devos50 commented 6 years ago

The Bitshares market is now also fully functional within Gumby (up to the point where I can make buy and sell orders): https://jenkins.tribler.org/job/pers/job/bitshares_experiment_devos50/116/. We are now ready to compare our implementation against these markets 👍

Next focus will be the refactoring of the market to make TradeChain our central component.

synctext commented 6 years ago

more related work, social markets: https://thenextweb.com/contributors/2017/08/29/can-blockchains-replace-retail-giants-like-amazon-ebay/#.tnw_tyPxx71b

synctext commented 6 years ago

Another ICO {scam} exchange market with low/no fees: https://bitcointalk.org/index.php?topic=2091630.0 Ready for business: 2019 :-)

devos50 commented 6 years ago

Related work: https://ico.wcex.co/whitepaper?lang=en (centralized but low fees)

devos50 commented 6 years ago

On the Impossibility of Fair Exchange Without a Trusted Third Party shows that it is impossible to facilitate a fair exchange without a TTP being involved. This is the reason why incremental payments should be used. Filecoin uses a similar philosophy, however, they consider this as future work while we have full support for incremental payments and transaction recording.

synctext commented 6 years ago

Bitcoin Historical Data - Bitcoin data at 1-min intervals from select exchanges, Jan 2012 to May 2017 and other datasets at that site.

devos50 commented 6 years ago

Now that the market is functional and the first emulation results are available, I will focus on improving the security of our platform. This includes a (basic) defense against the Sybil-attack using Temporal Pagerank. The unique property of Temporal Pagerank is that it incorporates the notion of time. The temporal aspect is often disregarded when we consider defenses against the Sybil attack (see Exploiting Temporal Dynamics in Sybil Defenses). The structure of our transaction ledger (TradeChain) is used as input for this algorithm. It has been proven that Temporal Pagerank is resistant against historical Sybil attacks. Additionally, it is computationally cheap.

At this point, the algorithm has been implemented and integrated in Tribler (PR will be opened soon) and the performance of the mechanism will be evaluated using a real-world dataset.

devos50 commented 6 years ago

The paper Bazaar: Strengthening user reputations in online marketplaces describes a novel technique to determine transaction risks in an online marketplace. The key idea is to create a risk graph and perform a max-flow computation on it from a specific buyer to a seller to asses whether a transaction should be flagged as fraudulent (or high-risk). Since max-flow computations is an expensive technique, they split up the complete graph into multiple, smaller graphs in a smart way. This provides a speedup of around 3x.

Their experiment is based on scraped eBay data, containing millions of purchases. The algorithm is driven by user-feedback where new feedback, either positive or negative, modifies the risk graph.

devos50 commented 6 years ago

After a bit more research I realized that the problem is not about sybil detection but rather about sybil prevention. Temporal Pagerank is not designed to detect Sybils since they are not guaranteed to be assigned a lower trust score than honest nodes, however, the effects of a Sybil attack on reputation are limited (but not as strong as NetFlow).

Fortunately, Temporal Pagerank is an asymmetric reputation system since it's personalized (the random walk starts from the set of your own half-interactions). This is beneficial since it has been proven that symmetric reputations mechanism cannot be Sybil-proof. Examples of symmetric algorithms are EigenTrust and regular PageRank.

I've considered various dataset to evaluate Temporal Pagerank, however, there have been some issues:

While I agree that using a social network dataset is nice, it lacks some desired properties that make Temporal Pagerank work. Additionally, I don't want to derivate much from the domain I've been exploring (peer-to-peer markets) so for now, I propose that I use my own scraped dataset with eBid transactions. This dataset contains 246.181 transactions, created by 13.955 users. Each transaction has a value (so it's a weighted graph) and a timestamp (so the set of transactions is ordered). So it contains all the properties we want and it's data from an e-commerce platform.

Next step is to perform a small (local) experiment with just the reputation algorithm to see how much influence Sybils have on their ranking (similar to the method described here). Next, we can emulate the market on the DAS-5, with crawling, and perform a Sybil attack to see how it works in a complete environment with nodes crawling the TradeChains of others.

devos50 commented 6 years ago

I just realized that NetFlow will not work for computing reputations of traders. Imagine a transaction between user A and B where a total value is exchanged of 20 dollars. Now, this is represented as an edge from A -> B and with an edge from B -> A with a weight of 20. However, when performing the first step of the NetFlow algorithm, the capacities of all new edges will always be zero (since the maximum flow from A -> B is the same as the maximum flow from B -> A) and as a consequence, the final trust scores of all agents will be zero. In fact, NetFlow is based on inequality between consumption and contribution.

Update: this also holds for the BarterCast algorithm.

devos50 commented 6 years ago

I've performed a few experiments with Temporal PageRank. First, I've rerun the experiment of Pim where he determined the computation time required for the algorithm. Instead of running it once, I've averaged the results over ten runs. We use the scraped data from eBid (described in one of my previous comments). The horizontal axis shows the total amount of transactions in the graph and the vertical axis the computation time. The results are shown for the preparation time of the data structure and the actual computation time for Temporal PageRank. We see that Temporal PageRank is a feasible algorithm, even for a graph with many traders and transactions.

compute_time

However, a more interesting question is how much reputation Sybil attackers are able to gain with Temporal PageRank. To determine this, we perform an artificial Sybil attack as follows: first, we pick 100 random nodes who will become attackers. Each of these attackers introduce a varying amount of additional Sybil nodes and initiates a transaction with a value of 1.000.000 with this Sybil. It has been proven that this gives the maximum amount of reputation to an attacker. We consider different amounts of additional Sybils introduced; 1, 2, 3, ... 10. We are interested in the average increase of PageRank score and rank by attackers when they perform a Sybil attack (this metric is used by most papers I've found that evaluate Sybil Attacks on PageRank). We consider three (related) reputation mechanisms: PageRank, Personalized PageRank and Temporal PageRank. The results of this experiment are shown in the following figures. As we see, Temporal PageRank is more resistant against Sybil attacks than the other two algorithms (yay!).

sybil_simulation_rank

sybil_simulation_score

devos50 commented 6 years ago

I was thinking a bit about the current implementation of the decentralised market in Tribler. While it's working (https://jenkins.tribler.org/job/pers/job/market_experiment_devos50/732/) and contains an implementation of the Temporal Pagerank algorithm, next point of actions can be the following: