Preventing Sybil Attacks: Runes, PoW, and CAPTCHAs

Put simply, Sybil attacks are where one person or entity creates multiple fake identities, usually to either subvert some part of a reputation system, or to effectively create large scale denial-of-service attacks. [1] Sybil attacks present problems to systems that maintain a low barrier of identification. With Loki’s focus on privacy and its P2P nature, methods are required to identify unique individuals without requiring some proof of personhood (i.e. government ID or License) .

In Loki’s case, Sybil attacks could be used to either spam path creation on Lokinet (more on this later) or, more worryingly, to force Service Nodes to store offline messages on behalf of the attackers, quickly exhausting the storage capacity of Service Nodes. Without user verification, both of these attacks could have a potentially crippling effect on the use of Lokinet and Loki Messenger.

There have been a number of software tools devised to identify legitimate, unique identity without requiring real world ID. Most people interact with these tools everyday- the most common being CAPTCHAs. In a CAPTCHA, a human is faced with a problem that is typically hard to solve for a computer but easy for a human. This slows down the automation process that a malicious party would use to construct large numbers of identities. Another system commonly used is browser fingerprinting. Services like Cloudflare use these tests often, with the idea being that they can determine, through the use of cookies, referrals and a number of other browser specific cues provided through javascript, whether a user is a robot.

Although the above methods provide some effective protections from Sybil attacks, they all require a strong element of centralisation in that they require a centralised server to verify the solution to each CAPTCHA. Unfortunately, this goes against Loki’s core philosophy of decentralisation. There are two well used and well studied systems, however, that allow us to achieve a similar effect without the same centralisation. The first is proof-of-work (PoW); in this system, the user performs a set of difficult calculations and then attaches this as a certificate to send a message or create a path. An attacker who pretends to be thousands of different people, would be required to perform that calculation thousands of times, costing money in computing cycles and making the attack considerably more difficult and inefficient.

The second commonly used system is fee-for-service; every time a user utilises the system to create a tunnel or send a message, they pay a fee. With this model it becomes costly to spam the network due to the additional fees invoked.

Both of these systems have some inherent flaws. The difficulty (pun intended) with PoW systems is deciding how hard it should be to produce one of these proofs which you can attach to a message or path creation. Make it too hard, and users with low spec computers or mobile devices will struggle to use your system. Make it too easy, and it will be cheap enough for an attacker to produce large quantities of proofs, negating the effectiveness of your system. The major issue with fee-for-service models is that they restrict usage of the service you provide. As services are increasingly provided for free, users have become reluctant to go through the process of purchasing a cryptocurrency and paying micro transactions each time they send a message. Additionally, since the groups that potentially benefit the most from Loki are the underprivileged, marginalised and persecuted, requiring them to purchase Loki from an exchange would be a non-starter.

So, what does Loki do differently? Previously, Loki presented the idea of Runes and the Runechain- with Runes representing a medium term (30 Days) access token to the Loki network that could be mined and sold. However, over time we have realised that Runes are not the most optimal solution. Runes present a number of issues. First, if Runes ever become profitable to mine, then average users will lack the means to produce them from a home computer. This would be the natural result of miners rushing to produce a profitable token that they can sell, increasing the hashrate significantly and strangling out the average consumer. In turn, this would mean that users would have to buy Runes from somewhere… But where? A centralised exchange? This creates another vector for temporal analysis where exchanges can collect the identity of users and link this with sold Runes, essentially assigning real IP addresses to Lokinet users. It has become clear that Runes create more problems than they solve; they also increase the complexity of Loki, in requiring two separate blockchains be maintained.

What’s the solution? Loki can functionally prevent Sybil attacks using a PoW system- it just needs a little tweaking, hence the new scheme: Loki Messenger now requires a Blake2b hash with sufficient difficulty to be produced for every offline message sent. This hash is attached to the header of each message, which is functionally similar to schemes used by Bitmessage and Hashcash. [2][3]

However, unlike other PoW systems, the difficulty of Loki’s hash function is based on the desired Time-To-Live (TTL) for each message. This means that if User A wants to send a message that lasts on User B’s swarm (an article on swarms will be coming soon) for 6 hours, the POW User A needs to calculate will be much less difficult than a message that needs to last for 24 hours. This difficulty adjustment method combats the constant rise in difficulty that stops low computing power individuals from using Loki messenger.

This scheme operates similarly for path creation in Lokinet. The fear with path creation is that users can request for Service Nodes be part of their paths. If they spam this process and require that Service Nodes stay in their paths for long periods of time, they can end up saturating Service Nodes with unnecessary paths that won’t be used. This would deny service to legitimate users. To prevent this, paths that are longer lived than the default path TTL will be required to attach a PoW to their request, this PoW difficulty rises linearly with the TTL for the path.

By using a TTL adjusted PoW system, Loki can prevent Sybil attacks while maintaining an equitable network that is free and open to users all over the world, as well as to those who may not have access to Loki or a powerful computer.


[1] “The Sybil Attack – The Free Haven Project.” https://www.freehaven.net/anonbib/cache/sybil.pdf. Accessed 25 Jun. 2018.
[2] “Bitmessage: A Peer-to-Peer Message Authentication and Delivery ….” 27 Nov. 2012, https://bitmessage.org/bitmessage.pdf. Accessed 25 Jun. 2018.
[3] “Hashcash – A Denial of Service Counter-Measure – Hashcash.org.” 1 Aug. 2002, http://www.hashcash.org/papers/hashcash.pdf. Accessed 25 Jun. 2018.

Leave a Reply

Your email address will not be published. Required fields are marked *