Reputation and Bonding on Mesh

[buck54321]

Hey all, I've been attacking reputation from a few different angles, but I haven't really found the right fit yet. Since others have expressed interest in this subject, I thought I'd open it up for discussion.

@dev-warrior777 shared this paper regarding a decentralized reputation system that does a good job of laying out the challenges we face. It's worth a read.

I also want to note that traded funds are protected by the atomic swap protocol, and the worst a bad actor could do is to incur on-chain transaction fees and temporarily locked funds. I think it's important to recognize that there is little incentive to being a jerk on Mesh. Bad actors can really only grief the network. There is no coin to be gained.

Features of the reputation system that I'm certain about.

• There are two level of reputation.
  • Clients track reputation data for all other clients that they interact with. We'll just call this Reputation.
  • Tatanka Mesh nodes will aggregate Reputation data reported from clients and compile into a score. We'll call this AggregateReputation.
• The number of Reputation reports considered as part of the AggregateReputation will be limited. Maybe 100 or so most recent.
• Users with low or no AggregateReputation will require a bond in order to use Mesh.
• When trading, the amount a client is willing to match with a counterparty will be limited by the counterparty's AggregateReputation. This is analogous to the trading limits in the v0 dex protocol.

Features that I'm feeling good about.

• The range of possible Reputation that clients report to Mesh will be small. I'm thinking [-127, 127].
• The possible effects of a given single interaction on a counterparty's Reputation score will be fairly limited. For positive interactions,
  the only effect would be a +1. For negative interactions, the effect could be larger, and would of course be negative.
• Users with an AggregateReputation score above a certain critical reputation score will no longer require a bond to use Mesh. Should their score drop below that level, they would be required to bond back up though.
• Bonds will be instantly refundable after their maturation period. Once a user surpasses the critical reputation score, they can refund their bond without delay.

Features I'm considering

• More recent interactions could be weighted more heavily in the Reputation score
• There could be a couple of different interaction types, with some types more persistent than others. This is analogous to how different types of interactions have different depths in v0 dex. (See matchOutcomes, preimageOutcomes, orderOutcomes in auth.go)
• There could be a sort of recursiveness built in such that a negative interaction would have a larger effect for counterparties with higher reputation. This might mitigate the ability of a user to game the system by building their reputation up so that they can do some maliciousness, rinse, repeat, while still preventing an unfortunate occurrence like a network outage from completely decimating a counterparty's score beyond the point of no return.
• Users with high AggregateReputation could hand out a limited number of voucher bonds to onboard other users. These would act the same as regular bonds, but would require no actual funds.

[norwnd]

Hey, the general design looks pretty clean, it's probably worth to go into some details and discuss possible failure-scenarios (to either improve this reputation system further, or at least better understand the trade-offs it makes),

would be interesting to know what happens in the following scenarios:

• lets say we have client A (a good/honest actor who has good reputation with mesh network), what does it take for malicious client(s) to "get his reputation down into negative territory" (and would that be harder if more than 1 client is targeted) ? I assume only bonded clients (and/or clients above critical reputation score) will be able to affect AggregateReputation of client A, but even then - if I can spin up a bunch of malicious clients (say, 100 of them, each bonded with small amount of DCR) and start deliberately downvoting all other clients on the network denying them mesh accesses (presumably forever, or for a long time) ... if this kind of attack is super-simple to pull off there probably isn't much benefit to having reputation system in the first place (it would just trade-off one set of problems for another); I guess this can be somewhat addressed by weighing client contributions to AggregateReputation by their overall trading-participation - so it would better reflect what "most active" participants think of this particular client A, it still can be gamed though because "most active" doesn't mean "good/honest"
• related to the above ^ when client submits his Reputation contribution to mesh server(s) does he prove this contribution somehow (eg. by providing some signature he received from corresponding counterparty client) ? And how hard would it be to fake such a proof ? Is there a way to prove ALL various misbehaviors, perhaps with server's help ?
• if the nuances listed above ^ are too complex to work out & implement in reliable & robust manner, perhaps it's worth considering something like trusted reputation sources - designated (by Decred community) clients or servers who's judgement will have a higher weight, or maybe even be the only judgement we ever really need (it could be revoked by social coordination in case such trusted server operator misbehaves in obviously bad ways)
• do server(s) provide any inputs to AggregateReputation ? And wouldn't it be simpler to leave clients out of reputation system responsibilities entirely and instead let the server(s) do all the work (naively, server(s) feels like more appropriate place to track reputation since it tracks all trades & trade-outcomes in one place) ?
• another aspect you've probably considered/discussed in the past (but I'd like to ask about it since it's relevant) is - it seems the approach you've outlined above defines reputation as a sort of "uniform truth everybody contributes too", while an alternative way to treat reputation would be for each server to figure out how good/bad each of his clients are on his own using reputation-information gossiped by all other servers only as a "starting guess" (rather than a "uniform truth"); this approach feels like a natural extension of how DEX currently behaves, server can't be fooled into thinking bad of good/honest clients, but the downside is that server is slightly more vulnerable to new client(s) initially (likely not an issue if parameters are tweaked properly)

[buck54321]

• lets say we have client A (a good/honest actor who has good reputation with mesh network), what does it take for malicious client(s) to "get his reputation down into negative territory" (and would that be harder if more than 1 client is targeted) ? I assume only bonded clients (and/or clients above critical reputation score) will be able to affect AggregateReputation of client A, but even then - if I can spin up a bunch of malicious clients (say, 100 of them, each bonded with small amount of DCR) and start deliberately downvoting all other clients on the network denying them mesh accesses (presumably forever, or for a long time) ... if this kind of attack is super-simple to pull off there probably isn't much benefit to having reputation system in the first place (it would just trade-off one set of problems for another); I guess this can be somewhat addressed by weighing client contributions to AggregateReputation by their overall trading-participation - so it would better reflect what "most active" participants think of this particular client A, it still can be gamed though because "most active" doesn't mean "good/honest"

Sure. The Sybil attack. The bond presents a barrier, but we also want to keep bond sizes small to keep friction low for onboarding users. Weighting contributions to AggregateReputation by the AggregateReputation of the scorer is a possible mitigation tactic, as both you and @martonp have pointed out.

Tangential, but reputation-based matching limits are a key here too, I think. If Alice has no rep, Bob will only lock up a couple of shekels for the trade. Not no damage, but low damage. Hard to avoid the Sybil circlejerk though.

A couple of other thoughts

• Could we introduce the scorer's account age as a factor? Maybe account age could be established by reference to a bond that may or may not still be active, but a bond will have a reference to the user's public key in the transaction output data.
• There could be something to gain from IP tracking, but that's a huge can of worms that we should avoid at all costs. We'll definitely do some IP-based rate limiting up front though.
• Pattern analysis could help us to identify malicious actors, but hard to implement.

• related to the above ^ when client submits his Reputation contribution to mesh server(s) does he prove this contribution somehow (eg. by providing some signature he received from corresponding counterparty client) ? And how hard would it be to fake such a proof ? Is there a way to prove ALL various misbehaviors, perhaps with server's help ?

Spot on. Let's run through a couple of scenarios.

1. Alice shoots out a MatchRequest to the owner of a standing order, Bob. Bob accepts. Based on the assets they're trading, the best swap protocol is SchnorrSwapProtocolX or whatever, which mean Bob acts first. But Alice never sees Bob's initiation transaction. That's Bob's bad. Alice lowers Bob's Reputation score from 100 to 50, and wants to submit the score update to the mesh.
   • In this case, there was an initial interaction, the MatchRequest, that offers a chance for the parties to exchange some sort of dually-signed interaction proof that could be submitted with Alice's score update.
2. Alice shoots out a MatchRequest to the owner of a standing order, Bob. Alice gets no reply. After some period of time, Alice sees that Bob's order is still on the books. Why did Bob ignore Alice's MatchRequest? Pretty sus. Alice lowers Bob's score from 100 to 99, and won't try to match with Bob again for a while.
   • In this case, there was never a chance for them to generate an interaction proof. Hmm.

• if the nuances listed above ^ are too complex to work out & implement in reliable & robust manner, perhaps it's worth considering something like trusted reputation sources - designated (by Decred community) clients or servers who's judgement will have a higher weight, or maybe even be the only judgement we ever really need (it could be revoked by social coordination in case such trusted server operator misbehaves in obviously bad ways)

If you've got a plan, I'll read it, but it's a hard sell. Maybe something based on the PoS system? I'm not totally averse to mesh node operators having some power over reputation tweaks, but it would need justification and guardrails.

• do server(s) provide any inputs to AggregateReputation ? And wouldn't it be simpler to leave clients out of reputation system responsibilities entirely and instead let the server(s) do all the work (naively, server(s) feels like more appropriate place to track reputation since it tracks all trades & trade-outcomes in one place) ?

The server nodes don't know what a "trade" is. By design. Very intentional. And speaking from experience with dcrdex v0, relying on the middleman server to track minutiae is a losing game. Lots of processing and storage on the server. We want Tatanka nodes to be nimble.

Servers do see AggregateReputation. If Alice's AggregateReputation is too low, she has to present a bond before she can send or broadcast any messages across the mesh.

• another aspect you've probably considered/discussed in the past (but I'd like to ask about it since it's relevant) is - it seems the approach you've outlined above defines reputation as a sort of "uniform truth everybody contributes too", while an alternative way to treat reputation would be for each server to figure out how good/bad each of his clients are on his own using reputation-information gossiped by all other servers only as a "starting guess" (rather than a "uniform truth"); this approach feels like a natural extension of how DEX currently behaves, server can't be fooled into thinking bad of good/honest clients, but the downside is that server is slightly more vulnerable to new client(s) initially (likely not an issue if parameters are tweaked properly)

I don't plan to require a consistent view of reputation across mesh nodes. I think there has to be some wiggle room in there. As an early target, I think we should plan to have maybe 3 mutually-whitelisted Tatankas running, operated by established Decred community members in a somewhat public fashion (we got nothin' to hide). That should serve as a good platform to see how this probabilistic reputation system pans out.

[norwnd]

Could we introduce the scorer's account age as a factor?

This could serve as an additional protection layer.

But overall I find it hard to convince myself a system built of such layers will be resistant to somebody handcrafting an attack that peels off those layers one by one ... adding layers shrinks attack surface, I'm just not sure its gonna converge to 0 as more layers are added.

Regardless, I think there still needs to be a well-thought mechanism for some kind of recovery from attacks reputation system doesn't cover (either it doesn't cover those by design since it would be too hard/complex to implement, or we just didn't account for those).

Namely:

• if user comes into Matrix support chat claiming he cannot trade on DEX because his reputation is low/negative - what steps can we take to help him if it's not really his fault (if he is a good actor and was a subject of attack on reputation system) ? Can we even tell if it's his fault or not (if, say, his Bison wallet connectivity is just bad and he should fix this first instead)
• what do we do if this ^ happens to many users (or most users) at some point, can we reboot reputation system somehow to some working (perhaps previously working) state ?

[buck54321]

if user comes into Matrix support chat claiming he cannot trade on DEX because his reputation is low/negative - what steps can we take to help him if it's not really his fault (if he is a good actor and was a subject of attack on reputation system) ? Can we even tell if it's his fault or not (if, say, his Bison wallet connectivity is just bad and he should fix this first instead)

Exactly. This is where I'm most open to node operators having some power. Perhaps they can generate some type of bond to offset unjust reputation hits. There are probably always going to be situations where a human touch is what's needed.

what do we do if this ^ happens to many users (or most users) at some point, can we reboot reputation system somehow to some working (perhaps previously working) state ?

That's a good question. I'll have to think about that. Some kind of way for node operators to agree to discard reputation scores after timestamp T maybe. Or maybe a temporary, waning, global reprieve for low reputation users.

[martonp]

Looks good.

Reputation provided by users with a higher AggregateReputation could be weighted higher in the calculation of another user's AggregateReputation.

Once a user surpasses the critical reputation score, they can refund their bond without delay.

How would this work?

[norwnd]

Clarifications help, thanks

As an early target, I think we should plan to have maybe 3 mutually-whitelisted Tatankas running, operated by established Decred community members in a somewhat public fashion (we got nothin' to hide). That should serve as a good platform to see how this probabilistic reputation system pans out.

My current understanding + thoughts on "trusted reputation system":

• automated(complex) reputation system we are discussing here is only really relevant in case DEX grows to large scale (many permission-less Tatankas running, many users overall to make DEX "valuable censorship target"), so it's likely not gonna be a problem for the upcoming year or two (and it's a good problem to have)
• but from the very launch you'd need to score DEX clients to prune especially bad ones, that's true

thus it would be reasonable to split the introduction of server mesh + automated reputation system in two phases to ship a working product faster to end users and give yourself more time to figure out the long-term solution,

phase 1:

• start with "trusted" set of servers (3 Tatankas like you mention) and let them score clients as they see fit (similar to how current server does it, tracking trades and such)
• might even get rid of the requirement to bond for clients (and instead for each new account let it put on ~10 free trades and adjust his free trades limit based on how he behaves from the point of view of "trusted" Tatankas)

this would allow to ship a working Tatanka mesh faster and test how/if it actually works as a mesh (without having to worry about bunch of other features that can break or introduce other friction points, like lost bonded funds)

phase 2:

• we have a working server mesh now, lets improve it step-by-step towards more automated(complex) reputation system outlined in this design-proposal (splitting this functionality as you see fit into something shippable so it's easier to test & polish each separate part/feature delivered)
• at some point enabling bonds back becomes necessary I guess
• at some point automated(complex) reputation system replaces the "trusted" reputation system Tatankas have been relying on so far, also making Tatankas more lightweight by design of this reputation system (but only 3 Tatanka nodes are running still, it's still permissioned in a sense of who can run a Tatanka server - so we can run some adversary tests against this automated(complex) reputation system in "our own sandbox")
• and finally, at some point we decide that reputation system works well and is reasonably stable against arbitrary adversary - so we remove the restriction of having 3 "trusted" Tatankas letting everybody else to run their own Tatanka

the main idea being if long-term design is well thought out to be decentralized and censorshit-resistant there is no reason not to ship a working product faster (get users & their testing / feedback faster)

[buck54321]

I was calling for a transitional model with a shared orderbook a couple of years ago, it just never materialized. Unfortunately, with the current murkiness and anticipated rigidity of the legal landscape, if we want anybody to run a Tatanka node, we need to get to a place where the servers have no involvement in managing the order book or trading data ASAP. We call it ᵃˡᵐᵒˢᵗP2P™.

And if we're going to get loosey-goosey with reputation, better off just going straight to mesh with a half-assed reputation system to start and working from there. Again, the antagonist gains nothing of value from griefing the mesh, only lost time and wasted tx fees.

[buck54321]

Important to note also that mesh is going to be added parallel to v0 dcrdex at first, so we'll still have a fallback should things go awry.