The aim is to build a system where users can register their Eth address. The system will assign a “uniqueness score” to each registered address. They way it works is that users send a deposit to get their Eth address included in the register and then any Eth address in the register can “vouch” for any other Eth addresses in the register. This creates a network where the nodes are the Eth addresses and the links are the nodes that have vouched for each other. Then the system runs an algorithm on this ‘trust graph’ to assign a “uniqueness score” to each node, which is a sort of measure of how well connected the node is with the rest of the graph. This “uniqueness score” is designed to be resistant to sybil-attacks, so it is hard for one person to get many accounts in the register with a high uniqueness score (i.e. it will be possible for someone to register many addresses but difficult to get all these addresses to reach a high score).
Having a sybil-resistance system would be useful for certain applications, and the value of such a system has been discussed by Vitalik a few times:
Computing the uniqueness score for each node from the data of the network of nodes and links, involves running a ‘pagerank’ style algorithm on the network. This algorithm requires a lot of computation, so is too expensive to be run by a smart contract. Hence it is more feasible to build the system as a zk-rollup. Then the scoring algorithm can be run offline by a L2 operator and the L2 operator can send the scores to the smart contract, along with a SNARK proof that the scores have been calculated correctly. The system will be implemented as an application-specific zk-rollup, as opposed to an app on an existing L2 rollup, because this will allow us to write a more efficient circuit specifically for the scoring algorithm.
Sequencer: Initially the zk-rollup will have just one operator, which we call the ‘sequencer’. This is a single machine that stores the state(accounts and links and scores) as a Merkle tree. Users send txn requests to the sequencer in a specified format. It collects these user transactions into a batch and then updates the state Merkle tree and then sends to contract three things:
New state root: This is the root of the updated state tree.
Snark Proof: This is a piece of data that proves that the state was updated correctly. More precisely, given the previous state root, the new state root and this proof data, it is possible for anyone to be sure that the new state root is the root of the same Merkle tree after a set of valid txns have been applied.
Txn data: The sequencer also sends the data of the txns it included in the batch to the contract to be stored, however they are sent in a very compressed format. The point of this is so anyone can recreate the full state tree just from onchain data (i.e. data store on the Ethereum blockchain).
Contract: Smart contract on Ethereum. It stores the current state root. Periodically, it receives a new batch from the sequencer. When it receives a new batch, it checks the snark proof is correct (this can be done quite cheaply, and is much cheaper than applying each txn in the batch to see if the new state roots match). If the proof is correct, the contract updates its state root variable to the new state root. The contract also stores the txn data, but doesn’t process it (its just there for data availability). Some transactions (such as depositing ETH to your L2 account) are sent directly to the L1 contract. When this happens the txn isn’t applied to the state tree immediately, instead the contract stores the txn in a queue. Then the sequencer can read the queue in the contract, and include those txns in the next batch. (The contract has some logic to enforce the sequencer to process these “L1 txns” if they are waiting in the queue.)
Circuit: The circuit is a program that contains the logic of applying txns and updating the state tree. It is written in circom language. It is created and fixed at the start of the L2 launching and published so the public can check the logic is doing the right thing. When the circuit is created, we get two pieces of data related to the circuit called the “proving key” and “verifier key”. The prover (in this case the sequencer) can use some ‘public inputs’ (the old root and new root), the proving key and some ‘private inputs’ (the txn data they have received from users) to create a ‘proof’. Then the verifier (the contract) can use the verification key, the same public inputs and the proof, to check if it is true that there exists a valid set of txns that take the state from the old root to the new root.
As an example of how this system could be used, a user could prove they own an account with a score above a certain threshold. This could be done via a merkle proof, i.e. prove a certain leaf exists in the account tree, or a zk proof if they didn’t want to reveal which account is theirs. This can be done by other Dapps, we can provide the proving algorithm and they can include the verification check in their contract.