Sybil/collusion-resistant subsidies

[arjunhassard]

TLDR
A protocol may subsidise the earning of fees by providers (thereby enhancing the incentive to perform correspondingly useful work), without opening the door for sybil/collusion attacks, by taking into account the historical, verifiable destinations of payments made by users.

Proposal motivation 


• Decentralized networks typically utilise a growing monetary supply to incentivize nodes/workers/service-providers (hereafter: ‘providers’) to initially join the network and then help fund their operations. However, the basis for earning these subsidies often aligns poorly with the actual work performed on behalf of network users. This misalignment risks some providers configuring their machines to execute the bare minimum required to collect the subsidy, and neglecting real service requests from users (e.g. by being offline).
• A growing supply depreciates the value of the native token, so it should incentivise good service, punish poor service, or both. If it is profitable to collect the subsidy without actually serving users, then it is probable that a greater proportion of providers will do this, relative to a network with zero subsidies. This makes the network less reliable and delays or impedes adoption.
• Importantly, misaligned subsidies may also blunt the power of other incentives. In early epochs, when subsidies dwarf actual service fees (i.e. the sums paid by users to providers directly in exchange for work), and providers earn fees and subsidies based on different actions, user engagement (e.g. requesting service) is rendered a relatively impotent economic incentive. This limits its effectiveness in motivating good behaviour (e.g. maintaining a high uptime in order to reliably answer service requests).

Service layer sybil attack



In layer 2 networks that offer an infrastructural resource or service (e.g. access control, outsourced computation), it is particularly difficult to align the allocation of subsidies to the delivery of useful work, because commercial engagements between users and providers are point-to-point, unlimited and often extra-protocol. This means that subsidy mechanisms can be profitably sybil attacked, wherein a provider sets up two addresses and continually requests their own service (hereafter: ‘self-requesting’). They receive back the service fee and earn the subsidy on top for every fake transaction – theoretically repeatable until the supply is drained.


Proposal assumptions



1. Providers must stake collateral (i.e. lock tokens) in order to participate and service users. Stakes are sybil-resistant (i.e. they can’t be cheaply duplicated).
2. Service fees are paid in return for provider actions that constitute real work – aligned with good service and network health. For example, earning a micropayment in exchange for a correct re-encryption.
3. All fee transactions have the following publicly verifiable attributes:
   1. User address
   2. Provider address
   3. Timestamp
   4. Value of transaction (e.g. denominated in ETH or native token)



Note: an efficient architecture for transactions – which allows the regular verification of the four attributes above – involves state channels and linked signatures. Users and providers pass signed hashes of each transaction back and forth, which includes the amount paid and the total paid so far. This enables the total sum of fees between each user and provider to be aggregated and evaluated by the protocol – this can occur as regularly as is practical (e.g. once a month). For NuCypher, a ratcheted re-encryption channel is appropriate – see this proposal from @tuxxy, with the addition of a counter to each signed message to keep track of the agreed sum of fees thus far.

Proposal outline & example

To make the reasoning simple, let's discuss a highly idealised network in which:

• There are 1,000 tokens staked evenly by 10 providers (all for the same duration).
• There are 10 total users of the network.
• Each period (1 month), each user spends $10 on the service.
• Jobs and fees are assigned and split evenly by providers.
• We don’t know which providers are also users – i.e. there are between 10 and 20 entities interacting with the network. 


Hence in this network, providers earn a total of $10 per month – $1 from each user. This is obviously a toy example, and we will discuss ways to deviate from this unrealistic uniformity later.


To avoid opening the door to colluders, let’s add our final assumption, expressible in multiple ways: What % of other providers/stakers is would it be impossible or near-impossible to collude with?
What % of the network can we assume to be virtuous or incorruptible?
At which point (in % of the network), do costs of orchestrating collusion massively outweigh the gains?

For now, let’s assume it’s unfeasible to collude with more than 50% of the network. We can now safely assume that for each of the 10 users, at least $5 of the $10 they pay out each month is legitimate – i.e. they cannot get it back via a side channel from their colluder group.


Now let's zoom into a single, misbehaving provider – we’ll call her Alicesula. Alicesula wishes to sybil attack the subsidy mechanism posing as a user. She approaches other providers, and convinces 4 of the 10 to follow suit and collude with her. What happens? She pays out $10 in fees just like the other 9 users. She gets back $1 from herself, and $4 from her fellow colluders. This means: 


Alicesula’s net expenditure: self-requested fees + fees returned by colluders - outgoing fees 
$1 + $4 - $10  = -$5



Let’s say we add a $0.5 subsidy for every $1 earned in fees. Since, like other providers, Alicesula earned $10 in fees, she now additionally receives a subsidy of $5 for this month. This means that her illegitimate net earnings, and the net earnings of her colluders, sum to zero – despite their involvement in a cartel controlling 50% of the staked tokens. 



Subsidy calculation function

We seek a function that calculates a subsidy amount for each unit of value earned in fees by providers during a predefined period, accommodating inevitable deviation from perfect payment uniformity. This formula is a first attempt.


Other solutions

There are not many attempts to square this circle. However, some projects that involve a ‘protocol rebate’ mechanism – where service fees are paid into a pool and then rebated (distributed) out every so often, based on both the provider’s relative contribution to the pool and their relative stake size – have discussed appending a subsidy to the rebate. However, this is not sybil-resistant, and the only partial solution thus far has been to limit the size of the subsidy such that it is always lower than third-party costs (i.e. Ethereum gas) involved in each transaction and incurred by the provider – thereby ensuring that attempts to self-request would result in net negative earnings.