Comment by Animats | Hacker News Reader

Comment by Animats | Hacker News Reader

The concept is interesting, and they have had some successes.

There's some handwaving about trust. They claim resistance against Sybil attacks, which is the biggest problem in anonymous distributed systems. That's where someone creates large numbers of phony identities to spam email, create link farms, and abuse reputation systems. If they could actually do that, they'd have a huge win. It's the basic reason P2P systems fail. They have a paper on how they do that, "On the Sybil-Proofness of Accounting Mechanisms in P2P Networks"[1] That's more important than this paper.

The other paper is analyzing Tribler, which is like BitTorrent. "Agents gossip about their transaction partners and inform others about their trustworthiness. Agents’ respective transaction histories are disseminated along the network. From this information agents can aggregate an approximation of their peers’ reputations such that free riders and otherwise uncooperative agents can be identified." Much of this is aimed at balancing the "seeders" and "leechers" of a file-sharing system.

Their TrustChain system is a more distributed blockchain-like system. Everybody has some chained blocks, and there's overlap, but nobody has all of them. The goal seems to be that most forgery is detected, but not all of it. In exchange for being only approximate, the system goes faster, uses less storage, and scales bigger.

All this is buildup to addressing the question of whether a group of nodes can cooperate to increase their reputation. The Sybil paper is a whole thesis on this, and heavy going. They're trying for a graph theory result.

I'm not clear on this, but the crux of the argument seems to be that in the seeder/leecher scenario, they can create a system where the cost of faking being a good seeder is higher than the cost of being one. This seems to depend on a cost metric which is internal to the network. If the benefit to the attacker is outside the network (sales from spams, higher reputation for a product or candidate), this might not work.

Good ideas there. They don't claim to have solved the general case, but they're trying.

[1] https://repository.tudelft.nl/islandora/object/uuid%3A6b4011...

> That's more important than this paper.

Author here. Deeply honoured that you carefully analysed our work. Yes, I agree that progress on the Sybil attack would be of high impact. We are in the process of strengthening our graph theory result. After already spending 18 year on it, we're getting close to a general "Universal Trust Machine" level result.

Recent science: https://www.sciencedirect.com/science/article/pii/S138912862... Recent thoughts: https://github.com/Tribler/tribler/wiki/The-design-of-a-trus...

There's also PeerReview: Practical Accountability for Distributed Systems [1] published in 2007:

PeerReview ensures that Byzantine faults whose effects are observed by a correct node are eventually detected and irrefutably linked to a faulty node. At the same time, PeerReview ensures that a correct node can always defend itself against false accusations.

[1] https://doi.org/10.1145/1323293.1294279

Author here. Yes, PeerReview is the most important piece of literature for us. We use a lot of similar concepts. Difference is that we're working for the past 18 years on getting this fully working, and deployed. Science is slowly making progress towards an "Internet-of-Trust".

- PeerReview assumes full network knowledge which is unrealistic in open p2p networks.

- PeerReview is built for full protocol replay and replication whereas TrustChain selectively replicates relevant information in the network. This significantly reduces storage and communication overhead, at the cost of fraud cases staying under the radar.

Latest work is our upcoming AAMAS 2021 publication, "Achieving Sybil-proofness in Distributed Work Systems", https://staff.science.uva.nl/u.endriss/aamas-2021/programme/...

I've always wondered why blockchains always assume all nodes are equal in trust. Why I can't add special trust to certain nodes? I mean this is what makes a 50% attack possible. Most people can trust their family members, close friends and neighbors, while only anonymous nodes can lead to a 50% attack.

Allowing users to assign different levels of trust to different nodes complicates things. If nothing else it requires that the user be able to accurately identify which node is which. This typically requires exchanging keys through a secure external service. I agree it's a worthwhile goal, but more work needs to be done to figure out how to avoid the problems found in systems like the PGP web of trust.

I was more thinking of something along the lines of "if there are more than one blockchains, pick the one shared by my trusted nodes"

Here is how you can migigate sybil attacks:

It has three pieces.

1. As people vote, a counter voteCount goes up. And also X = hash(X + latestVoterAddress). You become eligible based on X being the random number, rather than the block hash. The advantage here is we don’t have 40 minute limitation because X only changes as people vote and you can store as many historic X as u want.

Also how to store the last N historic values: you preallocate an array of N values and then you have a cursor that goes c = (c + 1) % N and it wraps around. That is how you can indicate which C to check and make sure you are still eligible. For example you can be eligible until 1000 new votes are cast.

We can combine with OR the randomness based on block hash (time based) and the randomness based on X (vote based) and you are eligible for 40 minutes or 1000 new votes whichever takes longer.

2. This is what I want to call Proof of Quality (PoQ) instead of Proof of Popularity (PoP). It’s not about how many people voted for you or how much capital was invested in you. But rather, whether people thought you were actually the best in a certain quality.

When you are eligible to vote, you should NOT be able to vote for whomever you want directly. You can vote indirectly, like in Mark Zuckerberg’s FaceMash: “who is more attractive, A or B?” And we update them with ELO rating formula as if they played a chess game. Then whoever gets highest ELO rating is the winner!

If there are a lot of candidates we can also have option for more than one (“choose most attractive from among A, B, C, D, E”) but arrow’s incompleteness theorem says two choices is the only way you can actually capture EVERYONE’s preferences

A variation of that is when you vote for some value to go up or down by 1% or some predetermined random % between 0 and 10. The result of everyone voting is what we use on-chain, eg when we combine the dot product of how much to issue for various tagged UBI categories etc.

What if we have only 2-5 candidates? Then this indirect voting thing wouldn’t work to prevent sybil attacks and we can only rely heavily on the “eligible to vote” where only 5% of people are eligible to vote at any given time. Someone with a lot of accounts can game that system. Luckily with our projects we will be voting for an ever growing number of candidates so we can use PoQ to determine top 10 in last 24 hours!

3. Your account address cannot proceed to vote for anyone else until you have voted in the current match-up in front of you (“Who is the most attractive, A B or C?”)

Just have a mapping in the smart contract which stores the random seed that made you become eligible. And don’t allow changing it until you voted. Have a parameter “votesPerSession” which allows a person to vote in up to votesPerSession matchups before they need to become eligible again. Thus #1 and #3 are used for rate-limiting them and #2 is for avoiding shilling specific items.

Reply on news.ycombinator.com