How to use collusion to detect collusion in Gitcoin Grants?
Original Title: “Attack and Defense of Quadratic Funding”
Written by: DAOrayaki
Explore the attack vector of Gitcoin Grants
Open source projects are the same as other public goods. Because of the richness of the products they provide (open source), they get less funds than the value they create for others. The reasons behind this are the non-excludable of public goods (meaning that no one can stop you from using it even if you don’t pay), and the non-rivalrous of consumption (meaning, I’m right The use of public goods will not harm you).
For example, national defense, urban parks, public roads and buildings are all public goods. The difficulty with public goods is that, due to the non-exclusive nature of the goods produced, people are likely to choose to free ride rather than pay their share of what they should have paid. Just like the slacker in your high school group project, who didn’t make any contribution, but still got all the honor of your hard work. Free riders are the reason why we don’t fully support public goods in society. Traditionally, the free-riding problem is solved by internalizing public goods (enclosures of public good) through taxation or privatization (such as land ownership or copyright law). However, these issues often involve a central agency—government, company, or non-profit committee—to compulsorily collect payments and allocate funds.
However, large central agencies are not necessarily efficient in allocating resources-they often do not know what the most important public interest is or how much support each project actually requires. This kind of information comes from bottom-up to be more effective, rather than top-down. In 2018, Vilatik, Zoe, and Glen proposed a new solution to this problem: Quadratic funding. It has an algorithm that matches the sponsor’s funds with small donors (thus receiving disproportionate rewards), because small donors as a whole may have a greater collective insight into which open source projects are most beneficial to the community . In addition, encouraging small donations is healthy for the long-term development of the Ethereum community ecosystem, because the Ethereum community ecosystem is forming a large number of public goods, so the above public goods dilemma is appearing in its community.
GitCoin, clr.fund, and HackerLink (DoraHacks’ developer platform) are using QF as their funding matching algorithm as a way to co-fund public goods projects with the community. So far, GitCoin grants have funded many projects in the Ethereum ecosystem, and HackerLink grants have funded projects such as BSC, Flow, Filecoin, Solana, HECO, etc. (For details, see Social Experiment | Let the community fund a huge burst of energy, when quadratic voting meets a hackathon ; geeks and painters | open source projects, NFTs and simplified Harberger tax )
Taking GitCoin as an example, this article mainly explores collusion scenarios using Quadratic Funding and Pairwise Quadratic Funding mechanisms, and proposes to mobilize the community to discover more hypothetical scenarios . Then, these hypothetical attack vectors will be used to test the effectiveness of the “Optimality Gap” algorithm, which is our solution for detecting collusion patterns through data science.
Use collusion to detect collusion in Gitcoin Grants
Conspiracy refers to “secret agreement or cooperation, especially to achieve an illegal or fraudulent purpose.” Collusion in economics usually involves an agreement between two or more sellers, aimed at taking action to suppress competition between sellers in the market. Because sellers compete with each other to provide consumers with low prices, a collusion agreement will increase the price consumers pay for this product. Because of this harm to consumers, it is against the antitrust law to fix prices through agreements between producers, so participants must keep secrets.
Famous collusion cases in history: such as the bidding of equipment contracts for the power equipment industry in the 1950s; a series of railway price increase agreements during the 1880s and 1990s; the Organization of Petroleum Exporting Countries (OPEC) represents the composition of oil-producing countries An attempt to conspiracy agreement to increase oil prices.
Conspiracy in the Internet era: In 2015, Ariel Ezrachi, a professor of law at the University of Oxford, and Maurice E. Stuckle, a professor of law at the University of Tennessee, proposed the concept of algorithmic collusion. Later in 2016, the “Prospects and Risks of Algorithm-Driven Economy” introduced in detail that computer collusion is dangerous. Although traditional antitrust laws prevent companies from fixing prices, data-driven algorithms can quickly monitor the prices of competitors. And adjust the price uniformly. Increasingly transparent prices seemed to be beneficial to consumers, but ironically ended up hurting them. The changing market reality is to transfer the power of market pricing to a small number of companies. In a data-driven economy, dynamic pricing and personalized services continue to evolve until they lead to consumer manipulation.
Collusion in the encrypted world: often manifested as attacks through collusion, collusion, and bribery. Such as: transaction verification, collaborative collusion, etc.
The mission of Gitcoin is to match sponsorship funds with a quadratic financing (QF) mechanism to help open source developers to collaborate and obtain economic benefits from their donations to community grants.
As pointed out in the previous article, quadratic fundraising is vulnerable to several attack vectors. The most prominent of these are Sybil attacks—that is, attackers create many fake accounts to play with the system, and collusion—that is, secret coordination between malicious real users. Solving these attack vectors is inherently difficult, and is made more complicated by the overlap with the transaction patterns generated by the contributions of legal and organic grants.
This article will briefly explain the quadratic fundraising (QF) algorithm, introduce several types of attack scenarios, and briefly introduce the optimization gap as a metric for marking potential collaborators.
Our goal is to help the community understand the mechanism of QF and the potential methods for designing and mitigating attack vectors so that the community can have more powerful detection tools to report potential attacks.
QF or the solution to “Free Rider Problem”
Open source projects are the same as other public goods. Because of the richness of the products they provide (open source), they get less funds than the value they create for others. The reasons behind this are the non-excludable of public goods (meaning that no one can stop you from using it even if you don’t pay), and the non-rivalrous of consumption (meaning, I’m right The use of public goods will not harm you).
For example, national defense, urban parks, public roads and buildings are all public goods. The difficulty with public goods is that, due to the non-exclusive nature of the goods produced, people are likely to choose to free ride rather than pay their share of what they should have paid. Just like the slacker in your high school group project, who didn’t make any contribution, but still got all the honor of your hard work. Free riders are the reason why we don’t fully support public goods in society.
Oscar knew what was going on-even though he was a little dissatisfied.
Traditionally, the free-riding problem is solved by internalizing public goods (enclosures of public good) through taxation or privatization (such as land ownership or copyright law). However, these issues often involve a central agency—government, company, or non-profit committee—to compulsorily collect payments and allocate funds.
However, large central agencies are not necessarily efficient in allocating resources-they often do not know what the most important public interest is or how much support each project actually requires. This kind of information comes from bottom-up to be more effective, rather than top-down.
In 2018, Vilatik, Zoe, and Glen proposed a new solution to this problem: Quadratic funding. It has an algorithm that matches the sponsor’s funds with small donors (thus receiving disproportionate rewards), because small donors as a whole may have a greater collective insight into which open source projects are most beneficial to the community .
In addition, encouraging small donations is healthy for the long-term development of the Ethereum community ecosystem, because the Ethereum community ecosystem is forming a large number of public goods, so the above public goods dilemma is appearing in its community.
Gitcoin uses QF as its funding matching algorithm in the ongoing Gitcoin Grants ecosystem, which is one of the main funding sources for Ethereum projects and startups.
The intuitive description of QF, green is community donations, and yellow is the sponsorship funds matching the quadratic power. The red circle is the total allocation of funding.
QF is to calculate the square root of each community’s contribution, add them, and take the square of the sum. After that, the funding agency (Gitcoin) pays the difference between the result of the “QF” and the matching funds of large institutional donors (such as the Ethereum Foundation and other well-known DeFi projects).
Therefore, this algorithm disproportionately subsidizes matching funds to projects that many small donors donate, instead of projects with only a few large donors. In fact, it is more trusting in the number of people supporting a project, rather than The number of dollars.
Gitcoin Grants Attack Vector 101
To understand how to defend against the attack media inherent in QF, you must first think like an attacker. Uncovering different patterns of attack vectors allows us to design simple and rigorous tools to detect these patterns in a real-time, potentially high-risk financing environment, with risks of up to millions of dollars.
This part will explore different methods of quadratic financing game:
- Split contributions
- Coordinating fake contributions with real people/accounts (coordinating fake contributions with real people)
- Split grants
- Sub-strategy and escalation (metagaming and escalation)
Split donations
As suggested by Vitalik’s blog post, the QF mechanism may be affected by sybil attacks and collusion attacks. An attacker can decide to create a fake grant, donate to himself, and collect matching funds as “interest”. Since the increase in the number of donations leads to more matching funds, the simplest form of attack is to divide the donations into multiple accounts and donate them to yourself.
The left side of the figure above shows a normal grant donation match (green is donation, yellow is matching funds), and the right side shows an “optimized” grant contribution match, indicating how multiple smaller donations lead to The same amount of matching funds.
In the figure above, we can see that as the area of ​​the green square (original donation) decreases but the number increases, the ratio of the yellow area (matching funds) to the green area (donations) also increases. In the most extreme case, if the number of green squares increases to an unlimited number of unlimited donations, theoretically you can use a small amount of original donations to attract a large amount of matching funds, as long as you divide the donations into many accounts.
Of course, many of the above attack vectors have been mitigated by the security measures taken by the Gitcoin team, which we will discuss below.
This is a simple mathematical problem. M is the original donation, and n is the number of donations that the “seed funds” are divided into.
For example, please see the following tweet from the @GitcoinDisputes account about the collusion against the Gitcoin Grant in July 2020.
The GitcoinDisputes account itself is a commendable signaling tool for coordinating bad behavior in the Grants ecosystem.
In order to reduce the sybil attack vector, that is, to create fake accounts to catch matching grants, Gitcoin currently does use the Sybil detection algorithm (assigning a Sybil score to the user), and incentivizing users to work on some different platforms (mainly including BrightID, Idena, POAP and 3box) for authentication, each additional layer provides more grants matching.
You can get a ” trust bonus ” for verifying more accounts for your Gitcoin match
The effect of this is to ensure that the additional funding matching funds are used for the identity with a higher probability of being a real person. However, there are other forms of conspiracy attacks that go beyond the scope of mere witch attacks.
Coordinate the relationship between false donations and real users
Although creating fake accounts to attract matching funds can be prevented by anti-jamming design, collusioners can “mine Gitcoin matching funds” by coordinating a group of real accounts, and distribute “interest” among the groups to easily implement them Of tricks.
An example of publicly bribing Grant donations.
In order to reduce the risk of collusion attacks, Gitcoin uses the new “Pairwise mechanism” proposed by Vitalik. The basic idea is to reduce the matching of donations from donors that seem to be highly coordinated to the same funding pool. If two donors (a pair) donate a group of similar grants, then the matching fund of the grant will be discounted by a certain amount.
There may be more considerations about the matching mechanism-this solution assumes that organic contributions often rarely overlap with each other, but we often see the opposite in organic communities, that is, they support each other’s work. The matching mechanism may also penalize the collection of grants, which is a tool that users can donate to a list of pre-selected items. Just like any well-designed solution to solve a specific type of collusion, there are always other ways to play this game.
In order to further mitigate collusion attacks, Gitcoin adopts a marking mechanism, and users who are required to cheat can report the cheaters to the Gitcoin dispute resolution program. It only takes 1 user to report the collusion behavior to “bust” the entire plan. In the 8th round, about 35 markers were reported.
Split grants (grants) / create fake grants (grants)
Another way to avoid witch attack detection and matching funding is to divide existing funds into many funds, or create fake grants and coordinate real accounts to donate to them.
As long as the co-conspirators can find some way to divide the large “donations” into many small accounts and collect them with small grants proposals, they can attract more matching funds, because the QF mechanism is disproportionately based on the number of participants. Rewards, not the amount of donations for each participant.
For example, a malicious actor can divide their grant into several small grant proposals, and divide their initial “seed” funds into dozens of small donations, and each donation is donated to these small funding proposals without generating overlapping.
Although this type of collusion has not been notified by the community, it is likely to happen with sufficient incentives and a growing matching pool size.
This type of behavior may also be noticed in closely integrated organic communities, such as Commons Stack or Metagame, in which many small, interconnected groups work closely together to fund and achieve greater goals. We should note that any system mechanism introduced to reduce collusion must minimize the negative impact on organic community participation, otherwise it may deprive the users seeking services of their rights.
An attack vector is established by 3 agents and 9 grants with optimized funding strategies, and then injected into the Gitcoin Grants data.
Game, MetaGame and Upgrade
Readers may have noticed by now, this endless game of hide and seek between attackers and Grant moderators. With the establishment of new mechanisms to prevent these attacks (such as MACI design, witch resistance, SybilScores, community tagging, or matching funding), co-conspirators came up with increasingly sophisticated strategies, from fake funding and accounts to bad actors Large-scale coordination. We must note here that any custom-designed analytical solution for a specific type of collusion problem can (and likely) be manipulated by another well-designed collusion strategy.
It is for this reason that the algorithmic governance policy we recommend is simple and universal, and is rigorous and mathematically reasonable. We pursue great simplicity.
Detect collusion through success: optimize gap indicators
We suggest that instead of trying to identify and capture all types of collusion, it is better to design a mechanism that makes efficient collusion impossible. When the cost of collusion is greater than the benefit, malicious actors will naturally lose their enthusiasm for collusion.
First of all, we have to determine which type of fund donation can attract matching funds to the greatest extent. The ultimate goal of collusion is to attract as many matching funds as possible with limited original funds.
Testing the effectiveness of the optimization gap requires inputting fabricated attack vectors into the data to see if they are found
Therefore, we did not try to enumerate countless collusion strategies and design specific solutions to solve each strategy, but to solve the collusion problem from another angle. By marking grants with an efficient matching fund donation model as suspicious, we can ensure that all grants with large matching funds are captured so that we can pass them to the Gitcoin dispute process for review.
Second, our goal is to empower the collective wisdom of the Gitcoin team and community to capture collusion. We believe that by simply explaining the collusion pattern of the QF mechanism and providing tools to identify and act on this information, we can authorize and coordinate the entire community against these black sheep.
What is Optimality Gap
The optimization gap is a measure of the degree of “optimization” of matching funds by a particular community. The basic idea is that it is always possible to rearrange and recombine donations related to a community (or subgraph) so that you can get the maximum total funds from the total fund pool.
At the conceptual level, high-efficiency communities will have a relatively low optimization gap, while most communities will have a median optimization gap. Given that the co-conspirators implement deliberate strategies, we can assume that, in general, they usually receive efficient funding.
But how do we precisely define the optimization gap of a community? First, we define the optimization gap as the difference between the largest matching funds and the actual matching funds in the preselected adjacent subgraphs. Taking into account the existing grants and donors and their original donations, if the donors donate to the project in a different mode, the optimization gap will calculate the difference between the matching funds it can get and the actual matching funds.
As for the community, there are several defined methods, such as the use of community detection algorithms or unsupervised learning. This is an open research question. Now we are using a heuristic method, which assumes that a community can be proxied by using neighboring subgraphs. This is essentially a distance method used to determine relevant checks community.
Use the “optimization gap” to generate signals to flag suspicious optimization funds for closer inspection.
Empowering community research
Our goal in this article is to authorize researchers in the Gitcoin community to use these tools to test and iterate their own research questions, to release the wisdom of the crowd and explore how to mitigate QF attack vectors.
The real power of open source is that the models generated today can be iterated and go further than we are now.
In the following repo, you can find the implementation of some of the attack vectors we discussed in this article, you can use cadCAD for testing, or even build it yourself! We want to see people design their own collusion patterns , use these algorithms, and propose improvements.
Our ongoing research aims to identify possible collusion patterns. In the first phase of the research, we constructed simple attack scenarios, implemented them in the cadCAD model, and tested them to see if they can be captured using the Optimality Gap algorithm. In the upcoming research, we plan to scale up and flag collusion attacks by making full use of real-time Gitcoin data.
As always, we encourage the community to explore and experiment with the Gitcoin cadCAD model repository, where you can access many of the data in this analysis.
GitHub repository: https://github.com/gitcoinco/gitcoin_cadcad_model
Gitcoin: twitter.com/gitcoin
BlockScience: twitter.com/block_science
cadCAD: twitter.com/cadcad_org
