Introducing Tokamak sybil-resitence
(Thanks to Kevin.J and Jake.J for feedback on this post)
In this post I will introduce a new project, part of the Tokamak Network ecosystem, called Proof-of-Uniqueness. The project aims to bring sybil-resistence to Tokamak Network and also Ethereum at large, and it is hoped that it will enable a whole category of new social/political applications to be built by developers.
Permisissionless networks often make use of a way for participants to prove they own something that is in limited supply. This could be computing power (Proof-of-work) or could be a token (Proof-of-stake). Another mechanism that could be very useful would be a way for participants to prove their uniqueness. This would be a way for a participant to prove that they are a unique person, and each person would only be able to make this proof at most once (i.e. sybil-resistence). The idea of issuing each unique person with a single non-transferable token (’soulbound token’) has been put forward by Vitalik in his article [1].
A system like this would be very useful for many social or political applications of blockchain technology. For example, with this it would be possible to create a currency that was minted equally by every person (aka UBI). A currency based on this rule would have a strucutre that incentivizes widespread adoption. Another example is voting. Many decentralised systems require some sort of voting mechanism in order to make decisions. This could be voting on things external to the system or it could be voting on things that are part of the protocol like parameters. If the voting rights are tied to a regular transferrable token, this can lead to the problem of vote buying. This problem is well illustrated in [2], but in essence it is a ‘tragedy of the commons’ situation where each user is willing to sell their vote to an attacker resulting in a worse outcome for all users.
After agreeing that it would be beneficial to have a system where users could prove their uniqueness, the next question is how can such a system be implemented? One project working on this is Proof of Humanity (PoH). They are creating a register of Ethereum addresses such that each address on the register corresponds to a unique human. To create a profile in PoH a user uploads a video selfie and other users vote on whether they believe that it is genuine and unique. (There is also a system whereby users can challenge duplicates and fakes). Our project aim is also to create a register of ethereum addresses, however it doesn’t use biometric data. Also, it only aims for approximate uniqueness, by defining a ‘uniqeuness score’ for each address in the register in a sybil-resistant way. This means that although someone can create an unlimited number of Ethereum addresses and add them to the register, the total ‘score’ of the addresses will still be limited.
Our project uses a mechanism similar to a web-of-trust. Adding an address to the register requires a deposit (which can be retrieved by removing the address from the register). Then any two registered addresses can vouch for each other by both ‘staking’ some of their deposit on each other. This gives the data of a weighted graph, where the nodes are the addresses and the edges are the pairs of addressses that have vouched for each other (the weight of an edge is the amount that was staked by the pair on each other).
From this weighted graph, a score is calculated for each address. The score is a measure of how well connected a particular address is and the measure is robust against manipulation and collusion. The algorithm to compute the score is computationally expensive so it is not possible to run the scoring algorithm in the L1 contract. Instead, the contract requires the updated scores to be submitted to it along with a proof that the score updates are correct. The contract will verify this proof and then update the state. To incentivize people to compute the scores for the contract, it will award a small amount of TON for a correct proof.
The way the contract works is that it stores the data of the weighted graph and will accept transactions that update this state, keeping them in a queue. Then anyone can create a batch of these transactions, compute the update of the state and provide a proof of correctness. At any time, there is only one possibility for the next block, namely the next N transactions in the queue (if the size of the queue is less than N, then the contract wont accept a proposed block). This means we dont need any leader selection process, its just the first valid proof from any user which creates the next block.
Next we’ll look at how the scoring algorithm works, with an example. The idea is to give a score to each node based on how well-connected it is to other nodes. One naive way to do this would be to set the score of a node to be its weighted degree. For example, if we are working with the weighted graph shown above, the weighted degree of node 4 is 6.2+5.5+5.0=16.7. However, assigning scores in this way is vulnerable to collusion attacks. For example if nodes 3 and 9 either collude, they could increase the weight of the link between them from 3.1 to 100 and get a much higher score. We want the scoring function to not be vulnerable to this type of manipulation. To do this we define the scoring algorithm as follows. First we start with a set of subsets of the nodes. In practice these will be the subsets that are smaller than a certain threshold. In the example these could be the subsets with at most 4 nodes. Then to compute the score for a node, we look at each of these subsets that contains the node and compute the sum of the weights of the links that are leaving this subset and divide it by the number of elements in the subset. The score is then defined to be minimum of these values. More precisely, the scoring function f is defined by:
This way of assigning uniquness score achieves the desired property that it protects against collusion of any subset of nodes up to the threshold size, since the total score assigned to the subset of nodes is limited by something external to the subset, namely the links joining it to the rest of the graph.
To see why this is true, consider again the scenario where nodes 3 and 9 collude and increase the weight of the link between them to 100. Even though this causes both the node to have high degree, it doesnt affect the quantity bdry({3,9})=5.0+5.5=10.5. Since the score of both nodes is limited by this quantity, the collusion doesn’t affect their scores.
(One thing to note is that defined in this way, computing the scores will be very expensive, however it is possible to do this computation more efficiently. Essentially, when computing the score for a node v instead of calculating the minimum over all subsets containing v, we first filter out all those subsets A for which bdry(A) is large as these will not have an effect when taking the minimum. This is done by running a type of diffusion on the graph starting from v. We are still working out the details for this more efficient version of the scoring algorithm.)
Finally, let us have a look at how privacy works with Proof-of-uniqueness. With a regular token, if a user wants to use their tokens to do some action and they don’t want this action to be associated to their account and the rest of its transactions, they can send their tokens to a brand new account through a mixer like Tornado Cash and then use this new account to do the action. With non-transferable tokens there is something analogous that can be done. Suppose a user wants to use their voting rights to vote on something, but they don’t want this action to be associated to their account. What they can do is create a zero-knowledge proof that they own an account with a ‘uniquness score’ above a certain threshold, without revealing which account they own. Then the voting protocol can check this proof and, if it is correct, allow them to vote. (The voting protocol can also ensure each account only votes at most once by using something called nullifier hashes). Note that this uses a different program that the one for computing the scoring algorithm, and any contract that wishes to intergrate with this system and check ownership proofs would need include the verifier code for this program.
In conclusion, this project aims to be a component of the Tokamak Network ecosystem that can be used by developers to create new and important applications. Its approach is aiming for full decentralisation and maximum privacy, avoiding the need for biometric data and instead using a newly developed ‘scoring algorithm’ to ensure sybil-resistence. The technologies utilized to implement the project include zero-knowledge proofs as well as some graph theory algorithms.
The roadmap of the project for 2023 looks like:
For further details on this project and to follow its development visit our github here.
