The Construction of the Soul Part 3: Soulbound Token with zk-SNARK Implementation
Contents
1. What are ZK Proofs
2. How can ZK Proofs be used with SBTs?
3. What is zk-SNARK?
4. High-Level Explanation of how ZKSBT works
→ 4.1.1 Generate a random Lambda.
→ 4.1.2 Generate proving key and verification key
→ 4.1.3 Sharing of proving and verification key
→ 4.1.4 Generation of Proof
→ 4.1.5 Verification of User’s Attribute
5. TL;DR of the High-Level Example
5.1 On-chain vs Off-chain Algorithms
6. Implementation of zkSBT
6.1 Circuit Creation
6.2 Setup Phase
→ 6.2.1 Key Generation
6.3 Proof Generation Phase
6.4 Verification Program Phase
→ 6.4.1 How can projects use Verifier.sol in their SBT?
→ 6.4.1.1 Risk: Preventing Replay Attacks
6.5 Implementation Architecture
7. Composability of ZKSBT (zk-SNARK SBT) with Counter Party Soul
7.1 Monolithic Approach: SBT issuer takes responsibility
7.2 Polylithic Approach: Each project takes responsibility
8. Conclusion
Abstract
In part 2 of the series, we went through the implementation of SBTs and how we can secure privacy. However, during the discussion of privacy, we saw how easy a user’s privacy may be jeopardised if the user gave out his secret in order to authenticate an attribute. As a result, using Zero Knowledge technology to secure user data could be a critical option.
In this post, we will discuss how ZK might be a critical technology for increasing the privacy of SBT users’ data and how projects could apply it.
In this article, we will go through how ZK could be a pivotal technology to increase the privacy of users’ data for SBT and how projects could go about implementing Zero Knowledge SoulBound Token (zkSBT).
1. What are ZK Proofs
Zero-Knowledge proofs allow one party (the prover) to prove to another (the verifier) that a statement is true, without revealing any information beyond the validity of the statement itself.
The prover has to convince the verifier that he possesses knowledge of a secret parameter, called a witness, satisfying some relation, without revealing the witness to the verifier or anyone else.
| A witness is a valid solution to our constraints.
| A constraint refers to the polynomial equation we converted our problem to. Each solution to the problem has to fit within the constraint. For example, proving that the user’s credit score is 3 can be converted simply to the constraint x = 3.
2. How can ZK Proofs be used with SBTs?
The projects can validate the attributes of a Soul by using ZK proofs (e.g., that it has certain memberships). They can also do so by allowing users to verify arbitrary assertions without giving any further information other than the statement itself.
For example, in a world where government documents and other attestations are cryptographically provable, someone could prove a statement like “I am a citizen of Singapore, who is over 18 years old and has a university degree in computer science, who has not yet claimed an account in this system.”
There are other ZK implementations; however, zk-SNARKs is the most prominent ZK technology utilised in applications such as Dark Forest Eth, Tornado cash, and ZK-Rollups.
3. What is zk-SNARK?
zk-SNARK is an implementation of ZK-proof technology that stands for zero-knowledge succinct, non-interactive argument of knowledge.
The individual parts of the acronym have the following meaning:
- Zero-Knowledge: During the interaction, the verifier learns nothing apart from the statement’s validity.
- Succinct: The proofs are short and fast to verify.
- Non-interactive: There is no or only a little interaction. For zk-SNARKs, there is usually a setup phase and, after that, a single message from the prover to the verifier. Furthermore, SNARKs often have the so-called “public verifier” property, meaning anyone can verify the proofs themselves.
- ARguments: The verifier is only protected against computationally limited provers. Provers with sufficient processing power can generate proofs/arguments about incorrect statements. This is regarded as “computational soundness,” as opposed to “perfect soundness.”
- of Knowledge: it is not possible for the prover to construct a proof/argument without knowing a certain so-called witness.
In simple terms, this essentially means that the proof is a collection of data that can be independently verified without the involvement of the prover.
For more information on why zk-SNARKS work, you can check out this series which goes deeper into the proofs of zk-SNARKs.
4. High-Level Explanation of how ZKSBT works
For the sake of the example, the user of SBT is the prover, and the project that issues the SBTs to the user is the verifier.
Suppose a project is looking to see if users have a certain attribute `secret_attribute`. The user has to prove that they have the attribute `secret_attribute` without revealing their secret `s`, which is used to hash attribute `secret_attribute` to hash `hash_attribute`.
Normally, the user would prove this by giving the secret `s` to the project, after which the project could compute the hash `hash_attribute`. However, with zk-SNARK, the user can just submit the proof that they possess attributes `secret_attribute` without revealing their secret `s`.
We can describe the scenario of the user with the following program C:
In other words: the program accepts a public hash `hash_attribute` and a secret value `secret_attribute` and returns true if the SHA–256 hash of `secret_attribute` equals `hash_attribute`.
Using the function `C(hash_attribute,secret_attribute)`, the user needs to create proof that they possess `secret_attribute`, without having to reveal `secret_attribute`. This is the general problem that zk-SNARKs solve.
In order to implement this proving and verification system, the project has to first perform the following actions:
4.1.1 Generate a random Lambda.
Generation of the lambda is the first step for the proofs. Take note of the generator’s secret parameter lambda. Anyone with knowledge of this parameter may create fake proofs that evaluate true without knowing the secret `w`.
Thus, running the generator requires a very safe approach to ensure that no one discovers and stores the parameters anywhere. This was the rationale for the Zcash team’s incredibly complicated ceremony to produce the proving key and verification key while ensuring the parameter lambda was destroyed in the process.
4.1.2 Generate proving key and verification key
The project has to generate two publicly available keys — proving key `pk`, and a verification key `vk`. The key generator program G takes a secret parameter `lambda` and a program `C`. These keys are public parameters that only need to be generated once for a given program C.
In most cases, this program C is implemented in the form of circuits (more details in the next section).
A trusted independent group separate from the user and project could run the generator and create the proving key `pk` and verification key `vk` in such a way that no one learns about lambda.
Anyone who trusts that the parties involved can then use these keys for future interactions.
4.1.3 Sharing of proving and verification key
The project will share the proving key `pk` and verification key `vk` with the users. These keys can then be used to generate proofs based on the attributes of the user, as well as verify the attributes.
The term “sharing” is used loosely here. Projects are not required to explicitly disclose them, but they can offer a function in the front end that allows users or counterparties to perform their own proofs or verification.
4.1.4 Generation of Proof
The user then needs to prove that he knows the `secret_attribute` that hashes to the known hash `hash_attribute`. To do so, the user runs the proving algorithm `generate_proof` using the inputs pk, H and s to create the proof `prf` :
H is the public hash of s using SHA256.
When the project wants to check if a user has a certain attribute:
4.1.5 Verification of User’s Attribute
The user presents the generated proof `prf` to the project who runs the verification function `verify(vk, H, prf)`.
The project computes `verify(vk, hash_attribute, prf)` which returns true if the proof is correct, and false otherwise.
This verifying algorithm can be on-chain as well.
If the verification algorithm returns true, the project can be confident that the user has the attribute, but the user did not need to reveal their attribute to the verifying project.
5. TL;DR of the High-Level Example
A zk-SNARK consist of three algorithms `G`, `P`, `V` defined as follows:
Generator Program
The key generator ‘G’ accepts a secret parameter ‘lambda’ and a program ‘C’ to produce two publicly available keys, a proving key ‘pk’ and a verification key ‘vk’. These keys are public parameters that can be generated just once for a certain program ‘C.’
The generation algorithm can be off-chain with the proper disposal of lambda. The proving key and verification key generated can then be shared with the users.
Note that program C is also known as a public arithmetic circuit.
Prover Program
The prover P accepts the proving key ‘pk,’ a public input ‘x,’ and a private witness ‘w’ as inputs. The algorithm generates a proof `prf = P(pk, x, w)`
The proof generation by the user can be done off-chain with the proving and verification key and their witness. Off-chain generation of proof is recommended as it is computationally expensive to generate proof and the users’ secrets might be revealed on-chain.
| A witness is converted from a user’s secret, which is a valid solution to our constraints.
Verifier Program
The verifier V computes `V(vk, x, prf)` which returns true if the proof is correct, and false otherwise. Thus this function returns true if the prover knows a witness `w` satisfying `C(x,w) == true`.
Verification can be done on-chain as it is relatively small and takes inputs of proof, a hash of the secret, and a verification key as public input parameters.
5.1 On-chain vs Off-chain Algorithms
Off-chain
- The project (verifier) will run the generator to generate the proving key and verification key.
- Any user (prover) can then use the proving key to generate an off-chain proof.
- The user can do so by running the proving algorithm with the following inputs — proving key, public input and private witness (generated from the hash of the secret and the secret).
On-chain
- The general verification algorithm inside a smart contract can be run with the proof, hash of the secret, and verification key as public input parameters.
- The outcome of the verification algorithm can then be used to trigger other on-chain activity.
The image below shows a summary of the whole process from creating the program to the generation and verification of proof using zk-SNARK.
6. Implementation of zkSBT
We have gone through a high-level example of how zk-SNARKs and SBT could work together. In this section, we will go through a trivial example of how a project could implement zk-SNARKs and SBTs to come together to allow counterparties to verify the attributes of a Soul.
Suppose a credit lending platform mints an SBT for a user and assigns a credit score to the user.
The credit lending platform wants to allow other counterparties’ projects to verify if the user score is above a certain threshold.
How might we be able to create this?
There are 4 different parts to this application. The front end, backend, smart contracts and the circuits. The circuits are the main component relevant for the generation and verification of zk proofs and therefore we will focus more on that.
6.1 Circuit Creation
Before we can make use of zk-SNARKs, we first have to convert our program specifications into circuits. For the creation of circuits, we are using the circom2 library designed by the IDEN3 team. This library has been used in many other popular applications, such as Tornado Cash and the game, Darkforest Eth.
For example, the circuit design intends to allow users to mint an SBT with a credit score assigned but no one else knows what the credit score is. However, the user can still demonstrate that his credit score is above the threshold and that he is creditworthy.
In simple terms, we will design a simple circuit that returns true if the user’s score is above the public threshold without having the user reveal his score.
https://github.com/SpartanLabsXyz/zk-sbt/blob/master/circuits/demo/circuits.circom
We have included other example circuits in our repository for different use cases. Projects can consider different circuits for their specific constraints.
https://github.com/SpartanLabsXyz/zk-sbt/tree/master/demo/circuits
A Note on Circuit Design
The harder part of zk-SNARKs is implementing the proper circuit constraints to ensure that the program performs. If the circuit is not implemented properly, it could be exploited and the exploit is very hard to detect because of the zero-knowledge nature of the program.
|What is a circuit?
| Circuit refers to the program in which our constraint is determined.
| zk-SNARKs cannot be applied to any computational problem directly. The problem first needs to be converted into the right form. The first step is to convert the program into an algebraic circuit.
| For more information check out their docs
A — B > 0, where A is the user’s secret, and B is our threshold used in the verification algorithm.
6.2 Setup Phase
Firstly, the credit lending platform first generates a random lambda λ. In the case of our example, we are using powers of tau which is a trusted setup of multi-party ceremonies to generate the random lambda in a decentralized manner.
Note that there exist different complex procedures to generate this random lambda because it’s crucial that it remains unknown to prevent anyone from faking their proofs.
For our application, we have created an example script `execute.sh` to run the setup process.
6.2.1 Key Generation
To create and check proofs, we use a library called SnarkJS, built by Jordi Baylina and Iden3. SnarkJS uses your circuit to generate proving and verification code in JavaScript and Solidity, as well as protocol parameters and proving and verification keys.
Example of proving key and verification key:
https://github.com/SpartanLabsXyz/zk-sbt/tree/master/circuits/demo
6.3 Proof Generation Phase
“Proof” is what a user generates in order to prove an attribute about themselves.
However, before the input attribute of the user can be used as proof, it must first be converted into a witness.
Using the circom2 library, we can easily generate the witness with the command
`node generate_witness.js circuit.wasm ../input.json witness.wtns`
Where input.json is the user’s input, which is the user’s credit score.
The generation of proof can be done off-chain on the client side where it takes the input of the program (in the circuit), the witness and the proving key. Using snarkjs with Groth16 protocol, we can generate it with
`snarkjs groth16 prove circuit_0001.zkey witness.wtns proof.json public.json`
| Groth16 is a specific implementation of a zkSNARK proving scheme. Read more here.
Once we generate the proofs, we can move on to verification of the proof by the user.
6.4 Verification Program Phase
For verification, we are performing it on-chain. Using the `snarkjs` library, the user can generate the verification algorithm from the verification key provided. The verification algorithm can then be used to generate a solidity smart contract using the `snarkjs` library
After the generation of `Verification.sol`, we can use it for proving that a given SBT has valid attributes using the function `verifyProof`.
Essentially `verifyProof` is a function that takes in a hash and a proof and returns a boolean.
Contracts: https://github.com/SpartanLabsXyz/zk-sbt/blob/master/contracts/Verifier.sol
6.4.1 How can projects use Verifier.sol in their SBT?
Projects can include the Verifier as an interface in the SBT Contract as shown in the function `validateAttribute`.
This allows any project to include the on-chain verification mechanism where all the users need is their proof, and verification key to verify their attributes.
https://github.com/SpartanLabsXyz/zk-sbt/blob/master/contracts/zkSBT.sol
validateAttribute
The inputs `a,b,c,inputs` in the function are parameters generated by snarkjs generate call function.
`@param _soul` is the address of the soul. `@param verifierAddress` is the address deployed for the Verifier.sol contract. The function returns true if the proof is valid, false otherwise
6.4.1.1 Risk: Preventing Replay Attacks
One of the risks of the verification algorithm is how attackers might be able to submit another user’s proof as their own and thus be verified. Projects have to take note that this might be possible. Some solutions are adding checks or nullifiers to prevent an attacker from submitting another user’s proof.
6.5 Implementation Architecture
In a nutshell, zk-SNARKs with Circom and Snarkjs implementation can be summarized with the implementation below.
Users can create proofs locally, and then upload short proofs for constant-time verification inside a smart contract, where computation is expensive.
The overall architecture can be viewed in our repository here:
https://github.com/SpartanLabsXyz/zk-sbt#architecture
For more information on the steps to integrate zk-SNARKs, you can refer to our GitHub or more specifically, the script `execute.sh` that is used to generate all the algorithms and proofs.
https://github.com/SpartanLabsXyz/zk-sbt/blob/master/circuits/execute.sh
7. Composability of ZKSBT (zk-SNARK SBT) with Counter Party Soul
In our example, we combined the role of the project that issues SBT with counterparties that might want to verify the attributes of the soul. However, for the composability of SBTs with other counterparties projects that might want to verify attributes of a user’s SBTs, we would have to make a few changes depending on the approaches used.
7.1 Monolithic Approach: SBT issuer takes responsibility
In the case where the data in the SBT is straightforward, the SBT issuer might want to generate their own lambda, proving key, and verification key. They could then provide an interface that allows counterparty projects to verify the attributes of a user.
The advantage is that this allows for easy adoption of SBT as other projects can make use of the existing verification mechanisms without generating and storing their own lambda.
However, this may not be feasible if the data within SBTs is varied and there exist several different programs C that aim to attest to the different attributes of SBT.
7.2 Polylithic Approach: Each project takes responsibility
The individual counterparty project would be responsible for generating the lambda, proving key, and verification key, rather than the SBT issuer or a centralized institution. The keys and verification method would then be distributed to the user via the project’s application.
However, the SBT issuer should provide clear documentation of the data structure of the SBT containing the characteristics while keeping the data private.
This strategy may be appropriate for SBT issuers who do not want to take full responsibility for securing their secret. Furthermore, if several proofs of the data within SBT are required, it may necessitate multiple verification programs, each with its own proving and verification key.
Furthermore, this strategy eliminates reliance on a central body and instead places the responsibility of ensuring the validity of the proofs on the projects themselves.
This strategy, however, would require that each project develop its own generation, proving, and verification algorithms based on the attributes being tested.
8. Conclusion
In summary, this article is a primer on how zk technology can be used to make SBT truly private and how projects can implement zkSBT in solidity.
SBTs allow for the integration of social identities with trustless composability, if done right, could change the future of the web3 ecosystem. The core aspects of trust and ownership can be on-chain to enhance social composability in the world of smart contracts, and that could open many possibilities for decentralised applications.
In this series Construction of the Soul, we laid out our vision for SBTs, their potential use cases, and how their key features can be implemented. We’ve sketched out the design principles and implementation of the SBTs, but our work is just beginning.
An important future research direction is to scope the exact limits of different kinds of data permissions, the specific combinations of techniques that work to keep data private and the products that can be built on top of SBTs to create a “pseudonymous economy”.
Let’s build a better future for web3 with the socio-economic integration that SBT brings! LFB!
We will release an end-to-end demo of zkSBTs utilizing the code that we went through in this session next week. Stay tuned!
Disclaimer: This post is for general information purposes only. It does not constitute investment advice or a recommendation or solicitation to buy or sell any investment. It should not be used in the evaluation of the merits of making any investment decision. It should not be relied upon for accounting, legal or tax advice or investment recommendations. This post reflects the current opinions of the authors and is not made on behalf of Spartan Labs or its affiliates and does not necessarily reflect the opinions of Spartan Labs, its affiliates or individuals associated with Spartan Labs. The opinions reflected herein are subject to change without being updated.
About the Author
This is part 3 of a 3-part Soul Bound Token Tech Thought Leadership Article Series, co-authored by Yong Kang Chia and Jun Hao Yap of Spartan Labs.
Spartan Labs is a venture studio under Spartan Group that advises and co-builds projects with the most optimal and effective design at launch and beyond by providing tokenomics design and project implementation. Spartan Labs also produces research reports and articles that are aimed at helping web3 users gain insightful perspectives with regard to the developments and issues within the space.
