ZK Social Graph

Our team has developed an Web3 social Dapp ”ZK Social Graph” that focuses on improving networking and connectivity among users during conferences and events. Rewarding active users and addressing the challenges of scalability with zero knowledge proof are key elements . Here's a breakdown:

👉 What “ZK Social Graph” offers 👈

1. Connectivity Solution: It aims to help users find the shortest path to connect with each other. This is especially valuable in networking situations, where people often meet a lot of new contacts and struggle to keep track.

2. Rewarding Active Users: It incentivizes users to engage with your social graph Dapp, both by on-boarding new users and by rewarding active users who have a significant number of followers or connections.

👉Why Graph Algorithms Matter👈

1. Valuing Users: Graph algorithms can help determine a user's value within the network by analyzing their connections and influence.

2. Explaining Connectivity: Metrics can explain the level of connectivity a user has within the network, which is essential for assessing their importance.

3. Reward Mechanisms: Using well-known graph algorithms can also facilitate the development of fair and effective reward mechanisms for active users.

Our approach of using zk Bellman-Ford to find the shortest path and reward users based on provable connectivity appears to be a promising solution to the challenges associated with on-chain computation. However, it's important to carefully consider the implementation details and potential trade-offs to ensure the scalability and security of our project. Additionally, user privacy and data protection should also be a priority in “ZK Social Graph”.

• Building circuits

We used circom to write circuits for bellman ford algorithm. In the process, we figured out that it is not trivial to port the algorithm into a circuit, so we had to fallback to matrix computation to optimize the circuit. It is very similar to a LP problem in convex optimization, where you need to find the constraints of objective function and formulate matrix multiplication from it. We have extended on top of circom-matrix library(https://github.com/socathie/circomlib-matrix), with some custom modifications.

• Proving eth storage Since user can game with the state of the graph (nodes and edges) we need to make sure that the inputs to the proof is actually the values stored in our contract storage slots. In order to do this, we used Axiom's storageQuery to get the value with the storage proof, and we use this storage proof along with our bellman ford circuit proof. Both proofs are submitted to the contract, where we run verification for both. If it satisfies both verifications it rewards the users by updating the balances. The policy of rewarding a user can be varied.

• Building dapps.

We have a wasm verifier in client, however since the circuit had 200k+ contstraints we had to reduce the size of the graph, and also remove some constraints. The dapp works by requesting a eth storage proof to the axiom service, and upon the response, we start proving for bellman ford algorithm as well. If we have both proofs, we can send transaction to connect() method in our contract, and rewards will be given to the users in the shortest path. One seamless way we could have taken is that axiom service allows halo2 circuit proof on their side, which removes the need to proving and verifying twice. Sadly it was too late to change the circom implementation to halo2, and couldn't use the proof integration that axiom is providing. I think for actually zk usage on client side, their way of handling storage proof and circuit proof at once would be quite useful.