Proof-of-like

Not surprisingly, I spend most of my free time browsing the inter-webs. I come across a lot of things that I like. But as a random stranger it is hard to convey that sentiment in a convenient yet meaningful way.

To be fair, most sites integrate the Facebook Like button or something in that vein. But my major qualm with these systems is that they require you to log in, tying your entire online identity to the act of liking. You basically broadcast your interests to the entire world. Also, these buttons are more about sharing content with your peers on social networks.

This got me thinking as to whether there is a way for somebody to like something anonymously on the Internet. The biggest problem that came to mind was spam – what is to stop somebody from abusing the system? Now, of all the spam combating methods out there the one I found most innovative was Hashcash. And so, I went about approaching the problem with that in mind. This brings me to proof-of-work systems.

Proof-of-work

Proof-of-work systems have been around for a while now. The basic principle is that, there is a class of problems for which it is hard to find a solution. Though, once a solution is found, verifying that it is valid is relatively easy. There is a fundamental asymmetry in the computational power required between finding and verifying a solution to such problems. This characteristic is exploited to build systems in which one party can trivially ensure the another party has – within limits; expended some amount of computational resource (CPU or memory).

Consider the problem of finding a suitable nonce value (\(n\)) such that when appended to some challenge string (\(C\)) and hashed the resulting hash value meets some constraint – like being lesser than a given target value (\(T_V\)).

$$ H( C||n ) < T_V $$

Since hashing is a one-way function, it is practically impossible – infeasible is a better word; to deduce the value of \(n\) from \(C\), therefore the only way to find a value for \(n\) is to brute force the search space, performing a large number of computations – depending on the difficulty of satisfying the constraint. Once a suitable value of \(n\) is found, a verifier needs to perform the hash function exactly once to check that the resulting hash matches the presented constraint.

Hashcash – one of the first widely implemented proof-of-work systems; was used to combat email spam and prevent denial-of-service attacks. Nowadays though, thanks to Bitcoin, proof-of-work systems have a much larger audience.

Outlining how a system for liking using proof-of-work functions,

Steps Involved

We have a client and server. Simply put, there are 5 basic steps,

Client sends requests, indicating that it wishes to like. This step is probably initiated by some form of user interaction. This interaction should also allow the user to modify a parameter indicating how much he likes the thing.

Server generates a challenge and sends it to the client. The challenge generated is probably a function of the user’s IP, a timestamp and of course, the URL of the page he likes. The generated challenge is stored in a cache and marked with an expiry timestamp after which, it gets flushed – a client must submit solution before this.

Client begins work. It performs an exhaustive brute-force search on the entire search space. The user probably has to stay on the page for the duration of this search – switching causes a demotion of priority and makes the search extremely slow.

Once, the client finds a suitable nonce, that satisfies the supplied constraint, it sends the value to the server tagged with the challenge that it solved.

Server verifies the nonce and assigns a reward value depending on the difficulty of a solution.

Issues

Environment

All of the client side code has to run in the browser. An important here consideration is that, while the client is working, it shouldn’t hinder the user’s interaction with the rest of the page. The Web Worker API is ideally suited for this, since it allows for a script to run without blocking the main UI thread on the page.

Speed

Running in the browser limits our ability to exploit the full CPU potential. And accessing the GPU from the browser requires the use of WebGL. The problem is that the WebGL context can only be accessed from the main UI thread.

Emscripten shows some impressive performance benchmarks. Hell, they’ve even gotten Unreal Engine to run in the browser!

Content vs. URL

At first, I thought that it would be better to base the challenge on the content of the page. The advantage of this is that it provides some kind of authentication – if the content of the page is changed in any way, all previous likes become invalid. The problem with that approach is that even minor edits can change the generated challenge – something to avoid.

Pluses

Parametric liking

Say I’ve got two articles of in front of me.

Now, I definitely like one but I think the other is way better. Earlier, my likes in both cases were worth the same! But now, I can actually like one more than the other.

How?, you may ask. Well, most proof-of-work functions have an adjustable difficulty parameter. The higher the value of this parameter, the longer it takes to find a nonce value that satisfies the solution, but it generates a higher reward value.

So, for something that I casually like, I can set a lower difficulty value. But, for something that I think is really great I can set a higher difficulty value.

Actual resource

This is really more of a symbolic benefit. Since liking is backed by a solution to a proof-of-work function, it can be safely assumed that the liker has expended some real amount of computational power in generating the nonce.

Not so pluses

Mobile

This idea doesn’t really play well with mobile devices for two main reasons.

1. CPU - It will take quite a while longer to like something.
2. Power - Liking frequently significantly drains the battery.

Undemocratic

In this system, not everybody is equally represented. A higher weightage is given to people that have more compute power. People who can afford more powerful systems end up having more liking power than the others.

Page focus

To perform the like, the liker must keep the page in focus. Otherwise, the brute-force job gets demoted to a background task and eventually it times out.

Links

I’ve started working on a server very creatively called HashLike – written in Golang. Check out the repo for more.