How we achieved anonymity on Web3 token-based elections

At the heart of Vocdoni's mission there is to innovate secure and anonymous voting mechanisms, as we believe it's a primitive for fair and legitimate participation in many scenarios.

Voter's anonymity can be easily preserved in 1Person-1Vote scenarios, as we already offer with our SDK and UIs using zk-Snarks. However, for token-based elections, separating identities from votes is not enough because token holders have a unique balance for a token, making them easy to identify as the weight of a vote can be correlated with an address.

In this article, we'll detail our approach to resolving this issue.

Introduction

A key part of the Vocdoni stack is Census3. Census3 is a service that checks for updates to a list of tokens or other crypto assets, and maintains an updated list of holders for each registered token. This service allows users to create a census based on a token, or combining censuses using strategies, in a way compatible with Vocdoni's blockchain (Vochain).

Census3 allows creating public or anonymous-compatible censuses and publishes them on IPFS, allowing for a transparent use and public auditing. But when the election is configured to be anonymous, we must consider not only the addresses of the holders, but also their balances because depending on the token holder distribution it could be easy to identify voters.

In the context of public blockchain technology where balances are public, preserving voter anonymity on token-based elections is a big challenge. To address this, we have been considered different approaches:

• Find a way or mechanism to keep the balance secret.
  ❌ Balances are public, and the Vochain needs to know the weight value to perform some checks and to calculate the results.

• Find a way to hide the balances.
  ✅ Modifying the balances as little as possible to make them difficult to correlate with identities and achieving sufficient anonymity.

The Vocdoni protocol is very flexible on how to configure and process elections. That includes weighted voting. In this type of election, not all voters wield the same power; instead, their voting power is determined by their token holdings as defined in the census.

Rounding censuses

To ensure that the balances of token-based censuses remain private, we must alter them in some way. However, any change must meet two requirements:

1. The resulting balance must be less than or equal to the original one.

2. The resulting balance should stay as close to the original as possible.

We explored two approaches:

• Statistical approach: Using a classification algorithm based on k-means but introducing the minimum number of members in a cluster requirement.
  ❌ Unfortunately, this approach required too many iterations to converge.

• Logical approach: Sorting participants by their balance and then grouping them, with some data cleaning techniques.
  ✅ This approach proved sufficient to provide a solution.

Logical approach

We have developed an algorithm to meet these requirements, rounding balances to the nearest one, forming groups of at least 3 (privacyThreshold) equal balances. This process obscures individual holder's balances. The algorithm optimizes the number of members in a group, taking in account the difference between balances, to reduce the accuracy loss.

Basic steps

1. Identify and exclude outliers: Participants balances are analyzed to detect outliers using z-score algorithm.

2. Forming groups: Participants are initially grouped based on the privacy threshold. A group can extend to include participants with identical balances or with balances differences falling below the groupBalanceDiff criteria.

3. Balancing groups: For each group, we adjust the balances, rounding them down to the smallest amount within the group to obscure individual values.

4. Accuracy loop: The algorithm tries to find the highest accuracy possible while maintaining a minimum privacy threshold. It starts with the minimum privacy threshold and increases it by a small amount until the accuracy is maximized.

For example, here is the pseudocode of the core part, grouping participants (2):

Function groupAndRoundCensus
    Input: participants (array of Participant), privacyThreshold (integer), groupBalanceDiff (pointer to big integer)
    Output: array of Participant

    Sort participants by balance
    Initialize groups as an empty array of array of Participant
    Initialize currentGroup as an empty array of Participant

    For each participant in participants
        If currentGroup is empty
            Add participant to currentGroup
        Else
            Set lastParticipant to the last element in currentGroup
            Calculate balanceDiff as the absolute difference between participant's balance and lastParticipant's balance

            If the length of currentGroup is less than privacyThreshold OR balanceDiff is less than or equal to groupBalanceDiff
                Add participant to currentGroup
            Else
                Add currentGroup to groups
                Set currentGroup to a new array containing only participant

        If it's the last iteration
            Add currentGroup to groups

    Set roundedCensus to the result of flattening and rounding groups to the minimun balance
    Return roundedCensus
End Function

Results accuracy

To measure accuracy, we compare the total of the adjusted balances from the census against the sum of the original balances, incorporating outliers in both calculations for consistency.

Our tests covered censuses involving 21 different tokens, showcasing various holder counts and token formats, including ERC20, ERC721, and POAP. This comprehensive testing ensures our approach is robust across different Web3 assets.

Initial conclusions

Our algorithm has several advantages, such as simplicity and speed. However, there's room for refinement. For example, tokens characterized by uneven distribution among holders present a challenge, as outliers not fitting into any group maintain their original balances, potentially revealing their identity.

Another problem identified is the loss of accuracy. The algorithm allows for parameter adjustments to enhance precision, and these can certainly be used to improve accuracy, but we didn't find any pattern in our test to do so. We've established parameter settings that generally perform well across various token types and distributions, so we consider this to be sufficient for now.

We've also detected potential vulnerabilities to specific attacks. For example, acquiring a certain amount of a token to manipulate the algorithm into grouping an address with others could theoretically expose that address. However, such strategies are impractical and unlikely to significantly impact election outcomes. This type of attack also requires an analysis of balance distributions, complicating its execution.

Additionally, among other possible enhancements, there is also the possibility of improving the algorithm's performance.

This is our first implementation to token-based anonymous elections. But we'll be pleased to hear about better approaches, or suggestions, to achieve anonymous voting on these and other types of elections. We warmly invite you to share them with us at chat.vocdoni.io or info[at]vocdoni.org