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.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.