---
# System prepended metadata

title: Anonymous Message Board

---

# Anonymous Message Board Protocol

Anonymous Message Board lets people post messages and interact with the posted messages anonymously. This protocol assumes that the admin(creator of group) knows some offchain public data(email id) which are used to send group invites. The invite embeds a link which is used by invited people to generate proofs. If proofs are verified, then the invited people can join the group. 

## Parties involved

- **Admin:** Admin is the person who creates a new group and initiates the setup phase with the help of server. Admin's only purpose is the launch of group. It includes inviting initial members and super members as well.

- **Super User:** Super member is the person elected by the admin or by the other members. Super users have some privileges such as, the ability to change the group rules, more weightage in the voting.

- **Member:** Member is the ordinary person in the group. They can post messages, interact with it, and also can add new members. 

## Purpose of centralized entity

Centralized entity aka server is responsible for hosting the whole message board interface and the data associated with it such as group messages, and group members list. The identities of group members are on the blockchain. So, the server does not control the member identities.

## Purpose of decentralized entity

Decentralized identity aka blockchain (succint blockchain to be precise) is responsible for members' authentication. It does so through a smart contract deployed on the blockchain which is responsible for verifying the proofs posted by members.

---
## The Setup Phase

This the beginning phase where admin creates the group and sends invite to initial members and super users. 

- The admin of the group keeps the **email_list** which holds the Email and **organisation_list** of every inviting users including members and super members.

- The admin posts the hashed mail lists along with the merkle root computed with mails as leaves on a smart contract. Then, the admin generates path indices, path hashes for every mail in the list
- The admin generates a $\text{Group Link}$ and sends it along with the merkle root, path indices, and path hashes to every mail in the **email_list**.

- Every invited super user/member performs the following:
    - Generate $MemPublicKey/MemPrivateKey$.

    - **$Proof_1$**: Statements about member identity(e.g., proving the nationality using Anon Aadhaar). This is necessary to ensure that every person in the group are unique and to not let a single person gets access to the group more than once. Also, this can be used by a new member in proving a particular identity to get accepted to the group.

        Proof1 is achieved by verifying the passport data along with the signature provided by the respective government. As we trust the government, it is just enough to verify the signature and constrain the data values (as required. For e.g., should be a citizen of some country to get accepted to the group.)

    - **$Proof_2$**: Statements about its receipt of email. This is necessary to prevent an adversary from acquiring the link and joining the group.   

        Proof2 is generated by parsing the email content along with signature header provided by Relayer serives(Gmail, Outlook, etc.). Then the signature header is verified and email content is constrained.
        
    - **$Proof_3$**: Prove whether the hash of user's email is one of the mails in the email list. The centralized entity may maliciously change the email list provided by the admin at the start of setup phase. So, this membership proof will ensure that every person joining the group hold one of the emails in email list.
        
- Members generate $Proof_4$ by;
    - Compute $\text{Addr Commitment} = Sha256(PublicKey_x || PublicKey_y)$
    - Assert $\text{Addr Commitment} == Sha256(PublicKey_x || PublicKey_y)$
    
    It is necessary to ensure that the member/super user uses the public key associated to the blockchain account $A$. 
    
- Every super user/member gets a blockchain account $A$ associated with their $MemPublicKey/MemPrivateKey$ pair.
    
- $Proof_1$, $Proof_2$, $Proof_3$, and $Proof_4$ are sent to the message board.

- The message board verifies all the proofs onchain and if valid, generates $\text{Verifiable Credential} = {Proof_1, Proof_2, Proof_3, Proof_4}$. And also sends the valid proof signal to the invited user who then generates a $userID$

$userID$ is needed to uniquely identify each person in the group. But this must be done only when all proofs are verified. So, the person can claim here is an identifier which uniquely links to a Verifiable Credential.


##### --------------------------------------------------------------The Setup Phase-----------------------------------------------------------
```mermaid
sequenceDiagram
    participant A as Admin (Centralized Entity)
    participant S as Message Board System
    participant U as Invited User
    participant B as Smart Contract

    Note over A: Keeps PublicList (Email, Organization)
    A->>S: Creates a new group with initial email list
    A->>B: Posts the Organisation List
    A->>B: Posts the email hashes 
    S->S: Generates group invite
    S->>U: Send Group Link
    U->>U: Get or create blockchain account A
    U->U: Generate proof1, proof2, proof3, proof4
    U->>S: Send proof1, proof2, proof3, proof
    S->>B: verify proof1, proof2, proof3, proof4
    S->>U: Proofs are valid
    U->>S: Sends the user ID
    S->S: Generate Verifiable Credential
    Note over S: VC = {Proof_1, Proof_2, Proof_3, Proof_4, Proof_5}

```

### Admin Actions

Admin creates the group and invites members as follows:

```rust
fn init_setup(MailList = [m_1, m_2, ..., m_n]):
    groupLink = generate_link()
    
    for user_email in MailList:
        send(user_email, groupLink)
```

Once the admin receives all the proofs, it finalizes the setup.

```rust
fn setup_final(proof_1, proof_2, proof_3, proof_4):
    if verify(proof_1) and verify(proof_2) and verify(proof_3) and verify(proof_4):
        vc = { proof_1, proof_2, proof_3, proof_4 }
        send_proof_valid_signal()
    else:
        abort()
```

### Invited User Actions

Once the invited user receives the mail, it performs the following:

```rust

fn setup_keygen(PublicParameters):
    // every invited user generates membership key
    membershipKey = generate_key(PublicParameters)

// every invited user generates proof_1
fn setup_proof1_gen(credentials, publicInputs):
    zk_circuit { 
        proof_of_identity(credentials, publicInputs) 
    }

// every invited user generates proof_2
fn setup_proof2_gen(email_contents, email):
    zk_circuit {
        proof_of_email(email_contents, email)
    }

// every invited user generates proof_3
fn setup_proof3_gen(merkle_root, path_indices, path_hashes email):
    zk_circuit {
        computed_merkle_root = compute_merkle_root(email_contents, email)
        computed_merkle_root == merkle_root
    }

// every invited user generates proof_4
fn setup_proof4_gen(addr_commitment, pub_key_x, pub_key_y):
    zk_circuit { 
        addr_commitment == Sha256(public_key_x || public_key_y)
    }

fn gen_userID():
    gen_random() // It can be a 64 bit value.
```
---
## Adding a Member by Super User

## Super User Actions

- The super user invokes the `Add member`.

- `setup_proof1_gen()` and `setup_proof2_gen()` of the setup phase is triggered.

- The super user verifies $Proof_1$ and $Proof_2$.

- If verified, voting protocol is triggered which displays the new member's proof which can be verified any super users.

- If the poll goes in favour, he will be accepted.

- When the new member is accepted, existing super users/members re-randomize their userID. This is necessary to avoid tracing who is the new member.

- `setup_group_key_gen()`, `setup_proof3_gen()`, `setup_proof4_gen()`, and `setup_final()` are all triggered sequentially.

```rust
fn super_user_auth_add_member():
    click_add_member() // in the ui where the super user clicks the add member button
    proof1 = setup_proof1_gen()
    proof2 = setup_proof2_gen()

    if verify(proof1) and verify(proof2) is true:
        if vote_count() > threshold:
            setup_group_key_gen() 
            proof3 = setup_proof3_gen()
            proof4 = setup_proof4_gen()
            if verify(proof3) and verify(proof4) is true:
                setup_final()
            else:
                abort()
        else:
            abort()
    else:
        abort()
            
```

##### --------------------------------------Adding a new member by existing members------------------------------------
```mermaid
sequenceDiagram
    participant SU as Super User/User
    participant S as Message Board System 
    participant B as Smart Contract
    participant NM as New Member
    participant O as Other Super Users
    participant OT as Other SU/Members
    
    Note over SU: Party who proposes to add new member
    
    SU->>S: Inputs adding member's email
    S->>NM: Sends the group invite through mail
    S->>O: Initiate voting protocol
    S->>O: Display new member's proofs
    O->>B: Submit Vote
    S->>B: Checks number of votes > threshold
    alt Vote Passes
        NM->NM: Generate proof1, proof2
        NM->>S: Return proof1, proof2.
        S->>S: Generates Group Ring Key
        NM->NM: Generate proof3, proof4
        NM->>S: Return proof3, proof4
        S->>B: verify proof1, proof2, proof3, proof4
        alt If proof1, proof2, proof3, proof4 are valid
            S->>NM: Proofs are valid
            NM->>S: Send the userID
            S->S: Stores VC { proof1, proof2, proof3, proof4 }
            S-->>SU: Member added successfully
            S->>OT: A new member was added
            OT->>S: Send the re-randomized userID
        else If proofs are not valid
            S->>SU: Addition aborted (Proof 1/2/3/4 failed)
        end
    else Vote Fails
        S-->>SU: Addition aborted (Vote failed)
    end
```
---
## Post a Message

```rust

fn post_message(message = m):

    M = sha256(m)

    post_id = M

    send_to_server(post_id, M)
```

##### ----------------------------------------------------------Posting a Message------------------------------------------------------------
```mermaid
sequenceDiagram
    participant M as Member
    participant S as Message Board System
    participant I as Server

    M->>M: Create post m
    S->S: M = sha256(m)
    S->>S: post_id = {M, R'}
        S->>I: send_to_server(post_id, M)
        I-->>S: Confirmation
        S-->>M: Post successful
```


---
## Voting protocol (using PLUME)


### Setup and Roles

- **Super Users**: A designated group of users with voting rights on the message board.
 
- **Message Board**: A platform where propositions are posted and voted upon. Each proposition is assigned a unique identifier.

### Message Creation

- Each proposition to be voted on is defined as a message $m$. The message contains details such as the proposition's name and description.


### Voting Process

1. **Compute Values**: The voter executes `compute_nullifier_sig()` using their secure enclave.

2. **Generate Proof**: The voter uses a client-side zkSNARK prover to generate a proof $\pi$ by executing `verify_nullifier_sig()`. This proof demonstrates:
   - Ownership of a valid public key
   - Validity of PLUME Nullifier.

3. **Transaction Payload**: The voter prepares a transaction payload containing:
   - The proof $\pi$.
   - Their vote value (Yes/No).

4. **Sign the Transaction**: The voter signs the transaction payload to ensure integrity and prevent tampering.

**NOTE:** Signing can be avoided because it is not possible to verify without leaking the public key. Our protocol is still secure with signing made optional.

```rust
fn vote(b_secret_key = sk, b_public_key = pk, random = r, generator = g, message = m, public_key_list = [pk_1, .., pk_n], vote_value = YES/NO):
    nullifier, s, c = compute_nullifier_sig(sk, pk, r, g, m)
    
    zk circuit {
        verify_nullifier_sig(nullifier, g, m, pk, s, c, public_key_list)
    }

    execute_txn(proof, vote_value, pk)
    
```
### Posting and Verification

- **Submission**: The signed transaction payload is submitted to the message board.

- **Verification**: The message board's verification mechanism ensures that:
  - The proof $\pi$ is valid.
  - The signature is correct(optional). 
  - The vote has not been double-spent (i.e., the nullifier is unique and not reused).

### Result Compilation

- Once the voting period is over, the results are compiled based on the submitted votes. The final decision on the proposition is made according to the tally of valid votes.

- If the proposition is about adding/removing members, the proposition will pass if **atleast 3 out of the total super users vote in favour or atleast 50% of the total members vote in favour.**

- For any other propositions, **30% of super users vote or 50% of members vote** is required to pass it.

### Benefits of the Protocol

- **Anonymity**: The PLUME protocol ensures that the voter's identity remains anonymous while providing proof of eligibility(membership)

- **Integrity**: The requirement for a final signature on the transaction payload prevents malicious alterations of the message or vote.

### Why we need nullifier?

To prevent a person in the board from voting twice, we require every person to commit to some value and post it onchain along with the vote. If the same person attempts to vote twice, he will give the same committed value which already exists. So, the malicious vote is nullified and double spending is prevented.


---
## PLUME Signature

```rust
fn compute_nullifier_sig(b_secret_key = sk, b_public_key = pk, random = r, generator = g, message = m, public_key_list = [pk_1, .., pk_n]):
    nullifier = sha256(m, pk).pow(sk)
    
    c = sha256(nullifier, g.pow(r), sha256(m, pk).pow(r))

    𝑠 = r + sk * c

    return nullifier, s, c
```

```rust
fn verify_nullifier_sig(nullifier, generator = g, message = m, public_key = pk, sig = s, c, public_key_list = [pk_1, .., pk_n]):

    c ==sha256(g, pk, sha256(m, pk), nullifier, g^s / pk^c, sha256(m, pk)^s / nullifier^c)
    
    for s in public_key_list:
        if s == pk:
            return true
        else:
            return false
```
---
## Group Signature Scheme

We propose to use ring signature scheme developed by [Monero](https://github.com/monero-project/urs). See the pseudocode below to know more. 

```python
function NewPublicKeyRing(capacity):
    public_key_ring = [0 for i in capacity]

    return public_key_ring

# Adds a new public key to the ring
function Add(public_key_ring, new_public_key):
    public_key_ring.append(new_public_key)

    return public_key_ring

function GroupSign(message, private_key, public_key_ring):
    # Step 1: Generate a random nonce for each public key in the ring
    nonces = []
    for each public_key in public_key_ring:
        nonce = GenerateRandomNonce()
        nonces.append(nonce)

    # Step 2: Compute the initial hash for the first step
    ring_hash = Hash(message, public_key_ring, nonces)

    # Step 3: Iterate through each public key in the ring
    signature_elements = []
    for each public_key in public_key_ring:
        if public_key corresponds to the signer's public key:
            # Step 4: If it’s the signer's public key, use the private key to compute the signature element
            signature_element = ComputeSignatureElement(private_key, ring_hash)
        else:
            # Step 5: For other public keys, generate a random signature element
            signature_element = GenerateRandomSignatureElement()

        # Add the signature element to the list
        signature_elements.append(signature_element)

    # Step 6: Finalize the ring signature using the signature elements and ring hash
    final_signature = Hash(signature_elements, ring_hash)

    # Step 7: Return the final signature
    return final_signature

function Verify(message, signature, public_key_ring):
    # Step 1: Extract the signature elements from the signature
    signature_elements = ExtractSignatureElements(signature)

    # Step 2: Generate the nonces for each public key in the ring
    nonces = []
    for each public_key in public_key_ring:
        nonce = GenerateRandomNonce()
        nonces.append(nonce)

    # Step 3: Compute the initial hash
    ring_hash = Hash(message, public_key_ring, nonces)

    # Step 4: Verify each signature element
    for each public_key, signature_element in public_key_ring and signature_elements:
        computed_element = ComputeSignatureElementFromPublicKey(public_key, ring_hash)
        
        # Step 5: If any computed element does not match the provided signature element, return False
        if computed_element != signature_element:
            return False

    return True
```

## Proof of Identity

We use proof of passport protocol to generate proofs about identity. Here is the rough example of using it:

```typescript
fn proof_of_identity():
    // every function used in this function is available in proof of passport library

        passportData = mockPassportData_sha256WithRSAEncryption_65537; 
        mt = MT(poseidon2([a, b]));
        bitmap = Array(90).fill("1");
        scope = "1";
        majority = ["1", "8"];
        secret = "0";
        mrz_bytes = packBytes(formatMrz(passportData.mrz));
        pubkey_leaf = getLeaf({
            signatureAlgorithm: passportData.signatureAlgorithm,
            modulus: passportData.pubKey.modulus,
            exponent: passportData.pubKey.exponent,
        }).toString();
        commitment = poseidon6([
            secret,
            PASSPORT_ATTESTATION_ID,
            pubkey_leaf,
            mrz_bytes[0],
            mrz_bytes[1],
            mrz_bytes[2]
        ])
        mt.insert(commitment);
        inputs = generateCircuitInputsDisclose(
            secret,
            PASSPORT_ATTESTATION_ID,
            passportData,
            imt as any,
            majority,
            bitmap,
            scope,
            "5"
        );
        // Generate proof and public signals
        proof, publicSignals = groth16.Prove(
            inputs,
            path_disclose_wasm,
            path_disclose_zkey
        );
        return proof, publicSignals

fn verify(proof, public_inputs):
        proofOfPassportVerifier = ProofOfPassportWeb2Verifier({
            scope: scope,
            // sample threshold
            requirements: [["older_than", "18"], ["nationality", "France"]]
        });
        proofOfPassportWeb2Inputs = ProofOfPassportWeb2Inputs(publicSignals, proof);
        result = proofOfPassportWeb2Verifier.verify(proofOfPassportWeb2Inputs);    

        return result
```

## Proof of Email

We use proof of email to make the incoming member prove that he is actually the recepient of the email invitation to whom it is intended to. For that we need to create regex and convert into NFA to prove that the email substring matches the expression. Regex for that is;

```
{
     "parts":[
         {
             "is_public": false,
             "regex_def": "email was meant for @"
         },
         {
             "is_public": false,
             "regex_def": "[a-z]+"
         },
         {
             "is_public": false,
             "regex_def": "."
         }
     ]
}
```

After generating the proof of valid regex, authenticity of email is proved by verifying the RSA signature signed by the email server. We use the `zkemail` cli tool from [here](https://github.com/zkemail/halo2-zk-email) for that. See the README to know how to use it.

## Link generation

```rust
function generate_link(groupId, inviterId, expirationTime):
    token = generateRandomToken()  // Generate a secure random token
    
    baseUrl = "https://yourmessageboard.com/invite"
    inviteLink = baseUrl + "?token=" + token
    
    return inviteLink

function generateRandomToken():
    // Generate a secure random token
    return secureRandomString(32)  
```

## Computing merkle root

```rust
function compute_merkle_root(hashed_leaves):
    current_level = hashed_leaves

    while len(current_level) > 1:
        next_level = []

        // Pair up nodes and hash them together
        for i = 0 to len(current_level) - 1 step 2:
            if i + 1 < len(current_level):
                // Hash the concatenation of the current pair
                combined_hash = Hash(current_level[i] || current_level[i + 1])
            else:
                // If there's an odd number of nodes, replicate the last node
                combined_hash = Hash(current_level[i] || current_level[i])

            // Add the combined hash to the next level
            next_level.append(combined_hash)

        // Move to the next(upper) level
        current_level = next_level

    // Return the root
    return current_level[0]

```
## Stack

- Library to write zk circuits: We are gonna target SP1 which is a ZK-VM that generates proof of execution of Rust code. So, we are gonna use rust language and target SP1. 
- Ring Signatures library: https://github.com/monero-project/urs
- Proof of identity circuit library: https://github.com/zk-passport/openpassport
- Proof of email circuit library: https://github.com/zkemail/zk-email-verify / https://github.com/zkemail/halo2-zk-email
- About zk-regex: https://prove.email/blog/zkregex

## Notes

- The message board acts on behalf of admin and super user actions with respect to adding a new member.

- We generate anonymous credentials from the passport data because most of the governments provides the digital passport signed by them which makes it verifiable anywhere.

- Difference between super user and the user is that super user has the right to change the group rules, and to change the voting rules.

- We need to have an access list smart contract which lets admin store hashed email lists and also any other members/super users can store hashed email of any new member they are proposing to add. We must make sure that members/super users dont add malicious mail id. To protect that, we must enable multisig authentication to allow smart contract state to change.

- We tried compiling simple zk circuits (fibonnaci, sha256, poseidon) that target Succint's SP1 ZKVM. From initial running, we found out running circuits take 16GB+ RAM which is infeasible. So, we decided to use halo2 library provided by Axiom for writing circuits. It can provide fast client side proving.

## TODO

- [ ]  Eligibility to elect super user
- [ ]  Eligibility to elect super user from the members
- [ ]  Criteria to kick out a member/super user
- [x]  Construct Public Identifier
- [x]  Randomizing public identifier when new member is joined

## Attack Vectors

**1. How new member is checked that he does not belong to the group already?**

We have $proof_1$ to ensure that the person with same identity cannot join twice.

**2. What if the centralized entity changes the email list sent by admin by adding some other mail ids?**

We have $proof_3$ to ensure that if any person other than the lists held by admin joins the group, this proof will fail.

**3. Is it safe to generate userID locally by the member/super user itself?**

Yes. As long as their proofs are valid, it is fine to link their VC with an identifier. Because it is not possible for external members to join the group, IDs must correspond to one of the group members/super users but cannot identify who.