A solution to sibyl attack problem for Upala identity proof system.
An effective mechanism to detect and confirm people using multiple IDs.
I’m developing a new identity proof system Upala. It’s purpose is to distinguish people from bots and clones (people with multiple IDs). One person — one ID. It is a huge goal. To get there I started a series of posts, showing my thinking process. I will then transform these posts into whitepaper.
While brainstorming ideas to solve the sibyl attack problem in the previous post, I came to a solution. In this post I will describe it detail.
The sibyl attack problem
I used an illustration proposed by Markus Knecht and added a bit of a drama. Here are two situations:
1: Alice and Bob are twins. They live in the same flat. Alice is out in the morning and home in the afternoon. Bob is out in the afternoon and home in the morning. They meet different people when they are out but never the same ones. They never invite guests.
2: Isabel is diagnosed with dissociative identity disorder. She has two phones. One has an account registered with her real name. And the other is registered with her alter ego — Sibylla. Isabel is out in the morning and home in the afternoon. There she changes her pale pink standard waitress uniform for a stunning evening gown and goes to a luxurious cocktail party. She gracefully grabs the phone registered for Sibylla. Isabel and “Sibylla” meet different people and never invite anybody to “their” home.
Here Isabel is performing a sibyl attack. We need to “punish” Isabel and “reward” Alice and Bob. But these situations are completely indistinguishable when trying to analyze social connections.
The solution
Components: a smart-phone app, a face recognition server, FOAM’s proof of location service.
Here is how registering a new user looks like in short:
- Take a picture of a registering user using Upala app (I never mentioned the project name before. Upala means Opal in Sanskrit. Will soon devote a post to it too)
- Detect twins with face-recognition algorithm
- If twins are detected they need to take selfies simultaneously in different places (proof of location)
- Random validators confirm that the new selfies depict the same people as their ID photos
The solution lacks validators incentives. This is one of the many questions for the further research.
Now to details.
Take a picture of a new user
Two friends meet. One is in the system (Bob), the other (Alice) wants to receive a new shiny decentralized censorship-free unique id.
- Alice installs the Upala app.
- Bob takes a picture of Alice using the new app on her phone. The app guides Bob to shoot the right perspective, face size, light, etc.
- The app creates an ID for Alice.
- The app indexes Alice’s face features, adds current block hash, encrypts it and uploads it to a face recognition server. The features are assigned an id hash, not the id itself. So that face-recognition server cannot identify Alice.
- Bob and Alice confirm their “handshake” in their apps.
- Bob takes a picture together with Alice. The app constructs a picture for validation — adds their ID photos to the scene.
- Random validators confirm (by staking tokens) that they see 2 different people and that each of them has the right ID photo. Validators cannot see IDs. They only see photos associated with IDs.
Face recognition server detects twins
Face recognition server using Alice’s face features looks for Alice in its database. If there is no suspicion for a twin, Alice is considered a unique person and gets a high score.
If the algorithm suspects a sibyl attack (finds a twin), some additional work should be done.
Suppose Alice has a twin from another part of the world — Sally.
People looking alike (twins) confirm their uniqueness
In order to confirm that we are really dealing with twins we need to see them together — same time, same place, same photo. But a more realistic approach is to witness them at the same time, but in different places. This is where FOAM may be helpful.
FOAM is a blockchain-based location service. Unlike GPS it will allow to reliably prove device location.
Alice and Sally will have to undergo another verification process:
- They decide on the interval when they are about to take photos. The allowed length of the interval is calculated depending on their timezones.
- Within the allowed interval they take pictures through the Upala app. Every picture has the latest block hash, person’s ID hash, location-proof data (FOAM).
- Both photos are validated by a random set of validators. Validators only need to confirm that the new photos correspond to the ones that were used for IDs creation. The fact that the photos were taken at the same time in different parts of the globe confirms that the people are different.
A failure to do this procedure would mean we have a sibyl attack.
Components
Do we need all this complexity: friends handshake, location proof and face recognition? Can we get rid of some of the components?
I like the mantra I came up with in my previous post: it does matter who you are, where you are and who you friends with. I think I’ll use it my future development a lot.
It does matter who you are. Face recognition.
Without face recognition we will have to compare every newcomer with every existing user. This is practically impossible. Face recognition allows us to lower the amount of work to a practical level. The system will only ask to confirm the suspected twins. I believe it is the most crucial part of the sibyl attack protection and has a high chance to become a part of Upala first release.
Face recognition works really well. Try using my photo to find me among 100 million of active users of Russian social network vk.com. And remember we can adjust the “suspicion score” on the go balancing between accuracy and amount of work.
The face recognition system will probably be from a 3-rd party. We need to make sure that this 3-rd party will have no access to user’s credentials. I thought of some zkSnarks cryptography, a private key generated in a multi-party computation procedure similar to the one used by ZCash. But I cannot assemble it in my head right now. Let me just blatantly declare that it is possible and drop this uncommented scheme below as an indisputable prove.
It does matter where you are. FOAM’s proof of location service.
In order to prove that we are dealing with twins (not a person with multiple IDs) we either need to photograph them together or take two photos simultaneously in different locations (or within an interval equal to a flight time). To prove that pictures are taken at the same time but in different places we need location proof.
Do we have to wait until FOAM releases their proof of location service? Well, I believe, for a state of the art system — yes we need FOAM. But we can start small. We can use known landmarks to confirm location for now. Put something available on Google street view on the background. Validators will have to do the additional work of confirming a landmark.
Can we do without location proof at all? I can’t imagine any other realistic way except some sophisticated biometry: DNA tests, chips, cornea, fingerprints, palm vein scanners, etc. I’d say palm vein scanners would be a realistic approach but with an addition of notary entities and the right incentives for them. In other words it is a palm vein scanners cost VS FOAM’s release date question. Intuitively I rely on FOAM.
It does matter who you are friends with.
Why Alice needs Bob? Why cannot anyone just take a selfie and register in the system? The mechanism above will work just fine without any invitation procedure. Yes, it will, but there are some problems:
- What if malicious Alice starts registering every day? She brakes the face recognition algorithm, makes a realistic doll and starts spamming Sally. Sally’s uniqueness score will go down.
- Or what if lazy Sally doesn’t want to cooperate and confirm her uniqueness. This time Alice will have an unfairly low score.
- What if Bob will pay people from the street to use their photos to create a battalion of bots.
These problems seem to be unsolvable without a reputation system. That’s why we need friends. The mechanism to replicate trust between friends is yet to be found — hopefully one of the following posts will be devoted to that.
Conclusion
A sibyl attack protected system possesses an additional and not so obvious benefit. It allows starting communities independently in different parts of the world. Clusters of people don’t need to be intersected to trust each other.
The mechanism described above has a good chance of becoming a part of the Upala ID system which will provide human uniqueness. Will now think on reputation and incentives.
Clap and support
Thank you for reading! The bare fact that you are here is very motivating. If you would like to help more, take a look at my other articles, share your thoughts, buy my ads, help me fund the project.
