Removing Sybils from an Open Network

43 points by mattwilsonn888 1 year ago | 54 comments
  • xmcqdpt2 1 year ago
    This is super specific to an obscure blockchain. I feel like OP should provide a Conflict of Interest statement.
    • trevelyan 1 year ago
      Saito isn't an obscure blockchain. The formal proof of its sybil-proof properties is also chain-agnostic.

      https://github.com/SaitoTech/papers/blob/main/sybil/A_Simple...

      It would be difficult to modify POS to have these properties, but the question of how best to accomplish that would be something for developers in those other networks to address.

    • pawelduda 1 year ago
      Ok, I've read about this before but can someone with big brain dispute this? Seems like a solution to quite a problem but as it's crypto, not entire truth could be told here
      • f_devd 1 year ago
        The core of their argument is:

        > as any routing node which self-clones to gain a larger share of routing-work for a given transaction also reduces by half the ability for that transaction to contribute towards the valid block production work threshold

        Seems like the primary assumption is that Sybill only happens vertically (one node being taken as multiple), but in reality Sybil is usually a per-actor problem, i.e. a CDN could be by a single actor created to ensure minimal hops thereby creating an effective Sybill attack.

        Disclaimer: this is my read of their system it might have different counter-measures/assumptions.

        • 1 year ago
          • SkepticalSense 1 year ago
            The paper is deeply flawed. The most important flaw is admitted by the authors in the paper in the final paragraph of Part 1.:

            "Until we reach the point we can formally establish that users are incentivized to broadcast their transactions to multiple nodes, we ask readers to treat this assumption as a design parameter as well."

            To put it simply, the proof requires behavior by users which is neither incentivised or enforced. Other egregious flaws are that the "proof" insists that sybil actors do things not required of non-sybil actors, i.e. add unnecessary routing hops, and that sybil actors are arbitrarily excluded from being the orgin node.

            • trevelyan 1 year ago
              You missed the last paragraph.

              The dominant strategy for users is indeed to broadcast two nodes.

            • trevelyan 1 year ago
              Author of the original paper this write-up was based on here. The sybil attack as a theoretical problem is defined in the "Red Balloons" paper ("information propagation without self-cloning") so that might be a good starting point.

              The solution formally and mathematically achieves these properties:

              - not profitable to add routing hops - profitable to share with others - not profitable to share with yourself (!!!)

              If you have a single central entity somewhere that isn't a sybil attack. Nothing wrong with being concerned about network centralization, but you're much less likely to have it in sybil-proof systems as above given that nodes suddenly have commercial incentives to share data as opposed to hoarding it.

            • mattwilsonn888 1 year ago
              Could you explain a bit more how your example of 'a single actor minimizing hops' creates an effective Sybil attack? If I understand, you mean to describe a node which is not adding unnecessary hops but is itself posing as unique identities to different users.

              If so, the response to that is: 'this type of behavior doesn't grant this node an increased ability to influence consensus compared to if they routed all data under the same identity.'

              • charcircuit 1 year ago
                If you wanted to send a transaction you would need to pick a node to share it with. The goal of the Sybil attack is to try and increase the likelyhood that it gets shared to nodes the attacker owns. The attacker then shares the transaction directly to miners.

                If gossip works by picking 3 random nodes to share transactions with if an attacker owns 1000 out of 1010 nodes they will very likely be the only one who transactions get shared to.

                • f_devd 1 year ago
                  In the immediate term it would be the same as using a single mode except with higher proportional rewards. However depending on the architecture that is the only motivation needed and depriving others of rewards; in the long term this could result in centralization of routing nodes (by control) and finally censorship.

                  It also seems unclear how consistent routing work is determined; how does the entire network agree on the minimal routing when there are many routes with the same 'depth' ; it also seems to conflict with minimal amount of routing work is required by the difficulty.

                  The goal of Sybil mitigation is to prevent any actor from gaining any undue control and this doesn't sufficiently show that to me.

                • charcircuit 1 year ago
                  In other words it Sybil attacks that create long chains of nodes owned by the some person, but it doesn't stop Sybil attacks that aim to get everyone else on the network to route through you instead of someone else.
                  • mattwilsonn888 1 year ago
                    Right - and this gets to perhaps the stickiest point on this: is a node a Sybil if they are the most efficient route into the network? If a single node can make all the blocks, they still only hurt themselves by adding hops (reducing block time, opening door for someone else to do it faster).

                    Many people argue that because nodes can still create an arbitrary number of identities, that they are in fact Sybilling. I believe that is incorrect, and [Wikipedia](https://en.wikipedia.org/wiki/Sybil_attack) seems to agree:

                    "[A Sybil Attack] is an attack wherein a reputation system is subverted by creating multiple identities"

                    If you take 'reputation system' generally to mean a system where nodes are gaining power from their identity, or in the case of Saito: their behavior, then you can easily say Saito is Sybil Proof even if it allows arbitrary identities because the 'reputation' you use to influence the network cannot be gamed by making additional identities - even though making them is free.

              • 1 year ago
                • katella 1 year ago
                  Why should routing nodes be rewarded at all.
                  • mattwilsonn888 1 year ago
                    The short answer is that it keeps the system fully 'trust-free' (permisionless), and that it, in the same way Bitcoin incentivizes hashing random numbers, incentivizes routing nodes to form efficient networks (networks which race to get fee paying data into blocks while minimizing hops).

                    --

                    Routing nodes will lose to competitors if another routing path on the same fee is included in a block. They also diminish the 'work' in the transaction (which overcomes the threshold to make blocks) by adding hops - so it's only worth it to add hops in order to 'win the race.' All nodes in the path have an expected value on the fee, but the further into the chain of hops, the more that diminishes.

                    In a technical sense, it isn't necessary to then reward those routing nodes to keep the anti-Sybil property for the routing network itself, but it does give other nice properties related to trustlessness and network provision.

                    1. Data pays no fees, routers get no rewards

                    Assuming data is published to a shared medium which requires some threshold of "work" which stems from the data, then even just the act of including that data into your medium becomes more difficult the more hops it accumulates. You then of course rely on trust assumptions to fight spam.

                    2. Data pays fees, routers get no rewards

                    If you use some measure of cost to create data, you can handle spam, and that cost determines how much work the data carries with it and thus how likely it is to be included into the medium (trying to be very general here, but in the linked article that medium is a blockchain). The trust assumptions here rest with the routing nodes 'doing their duty.'

                    3. Data pays fees, routers get rewards

                    This is the model Saito has - it removes trust assumptions for users and routers as if one tries to 'scam' the other (either a Sybilling user creating fake data, or a Sybilling router creating fake hops), the native money can be leveraged to create recourse without an authoritative audit or punishment - purely economic.

                    • trevelyan 1 year ago
                      Do you want your transaction fee to pay for mining, or do you want it to pay for the servers that run the network? If it pays for mining, who pays for the servers that run the network?
                    • 38 1 year ago
                      • xerox13ster 1 year ago
                        I hate to be that person, but as someones with Dissociative Identity Disorder I really wish we would stop using this term and go back to pseudospoofing. I cannot express just how much I HAAATE that the "solution" for a "Sybil" attack is Decentralized IDentification, or DIDs. It's a wholesale theft of the language that defines my existence and will lead many people to associate those with DID with the story of Sybil which woefully outdated and from a time when we knew far less about dissociaton than we do today.

                        This has led me to understand empathically why there were people suggesting we change bus terminology from master/slave to anything else.

                        • ilyt 1 year ago
                          I don't think there is any context where those 2 shortcuts would be mistaken for one another.

                          > This has led me to understand empathically why there were people suggesting we change bus terminology from master/slave to anything else.

                          I guess you haven't been one fixing the fallout that pointless shit caused.

                          • kazinator 1 year ago
                            I don't think there is any context in which a bus mastering DMA controller would be mistaken for a plantation owner.
                          • hifromwork 1 year ago
                            This comment is very surprising to me. I don't think it's reasonable to expect any three-letter acronym will only mean one thing. For example my usual nickname has three letters, and has around 20 definitions on wikipedia, including sex-related, drug-related and politically charged meanings (I don't identify with).

                            In fact, DID already has a disambiguation page on Wikipedia: https://en.wikipedia.org/wiki/DID_(disambiguation). I don't think Dublin Institute of Design or Data Item Descriptions constitute "a wholesale theft of a language".

                            • lovemenot 1 year ago
                              It's not DID alone that's the problem. I believe the parent is triggered by the confluence of Sybil and DID.
                            • lovemenot 1 year ago
                              It's clearly an unfortunate clash of both DID and Sybil in two separate nomenclatures. Each of which, in its own domain, has different referents.

                              However, like many of the peer comments here I feel the overlap of these two domains is vanishingly small. Presumably only yourself and a handful of others would even be aware of the etymology.

                              As you feel so strongly, perhaps a well-written blog post would rank highly for anyone curious enough to disambiguate.

                          • THOMPSON231 1 year ago
                            [dead]
                            • Rowanbarland 1 year ago
                              [dead]
                              • pluto_modadic 1 year ago
                                Solving Sybils for any blockchain is kinda something rational, ethical cryptographers wouldn't want to do... but I'm sure you can pay someone to claim they've solved it.

                                I'm kinda okay with blockchains always remaining vulnerable and becoming relics of the past. It's all a scam. Not patching it.

                                • klabb3 1 year ago
                                  You mean because of the hype and scams associated with blockchain technology?

                                  I would agree with the assessment, but avoiding it for research would be equally dumb. The tech itself has very interesting properties and potential applications outside of “finance”. It’s just a decentralized and slow global db with an (empirically battletested) consensus mechanism.

                                  • littlestymaar 1 year ago
                                    > with an (empirically battletested) consensus mechanism.

                                    In fact there almost as many consensus mechanisms as there are blockchains. In the beginning it was PoW that defined what was a blockchain, but with its obsolescence in favor of Proof of stakes for many chains the situation got muddier. Facebook's Libra/Diem for instance was based on a strongly consistent algorithm (as opposed to the eventually consistent nature of PoS) that's not that different from PBFT and ByzPaxos.

                                    • mattwilsonn888 1 year ago
                                      I'd argue that most PoS networks are not fundamentally different from the consensus algorithms before Bitcoin - the difference is they include a token as an entry point into authority, and that getting caught attacking will demerit tokens from you.

                                      But the attack vectors are the same, and now there is an incentive to pull off an attack since the system is representing money people are willing to trade for goods. I think PoS is dangerous for this reason - same vulnerabilities and defenses but with higher stakes on both sides.

                                      Not defending PoW wholesale, but it is fundamentally different as a network defense tool - though, it too has a reward for attacking it, so long as you can get 51% together - or less with selfish mining (network latency attacks).

                                • MollyRealized 1 year ago
                                  I asked GPT-4 if they could "summarize for idiots". I do not have enough knowledge to say if they summarized it accurately, but for anyone like me, who felt like a very big dummy while reading this, here's the summary:

                                  The essay discusses a method to prevent Sybil attacks, where a single adversary controls multiple nodes on a network to subvert the network's functionality, in blockchain networks by making it unprofitable for malicious nodes to add unnecessary 'hops' in transaction paths. Saito's mechanism rewards nodes for efficiently routing transactions to block producers, thus making Sybil attacks less lucrative. This is further illustrated with mathematical proof and examples comparing honest and Sybil behaviors, highlighting how the expected rewards change in both scenarios .