Zero-Knowledge Proof in NuLink

In NuLink, clients can store its data over a decentralized system. The Storage Layer of NuLink is a secure network created for the purpose of storing confidential data in encrypted form. At present, we utilize IPFS (InterPlanetary File System)[Ben14] as the primary decentralized storage network.

The IPFS is a set of composable, peer-to-peer protocols for addressing, routing, and transferring content-addressed data in a decentralized file system. Many popular Web3 projects are built on IPFS - see the ecosystem directory (opens new window)for a list of some of these projects.

A potential IPFS system is Filecoin[fil]. Filecoin is a peer-to-peer network that stores files, with built-in economic incentives and cryptography to ensure files are stored reliably over time. In Filecoin, users pay to store their files on storage providers. Storage providers are computers responsible for storing files and proving they have stored them correctly over time. Anyone who wants to store their files or get paid for storing other users’ files can join Filecoin. Available storage, and the price of that storage, are not controlled by any single company. Instead, Filecoin facilitates open markets for storing and retrieving files that anyone can participate in. Filecoin is built on top of the same software powering IPFS protocol. Filecoin is different from IPFS because it has an incentive layer on top to incentivize contents to be reliably stored and accessed.

A key components of Filecoin is its proof systems. Filecoin uses various proof of storage system[ABC⁺07] to ensure files are stored in storage nodes correctly. Here we start from the basic proof of storage system and show how it works.

Proof of storage system ensures data integrity and availability only at a specific time point (i.e. the time the challenge is issued). A simple example is as follows.

Suppose that a user wants to store its data $F$ in a storage node. The user can sample several random strings $\{r_{i}\}$, hash the concentrate of data and random strings $\{h_{i}=hash(F\|r_{i})\}$ and store these hashes itself. Then it require the storage node to store $F$. Every time the user wants to check data integrity, it sends unused $r_{i}$ to the storage node and require the storage node to return $hash(F\|r_{i})$. Easy to find, if the storage node didn’t store the data $F$, it would not able to compute $hash(F\|r_{i})$ for random string $r_{i}$.

However, as one can see, above solution is quite inefficient, especially at the case that the size of $F$ is huge. To solve this issue, we need to rely the idea that “Checking that most of a file is stored is easier than checking that all is”. Divides $F$ into $k$ blocks $\{m_{i}\}_{i\in[k]}$. The user stores the hash tree of $\{m_{i}\}$. Every time need to check data integrity, require the storage node to return blocks $\{m_{t_{i}}\}_{i\in[k^{\prime}]}$ where all $t_{i}$ are samples randomly from $[k]$ and $k^{\prime}$ is much small than $k$. The user checks the correctness of sending blocks via hash tree. As one can see, if the storage node drops too much blocks (e.g., half blocks), it will fails in the checking with a high probability (e.g., $1-2^{-k^{\prime}}$). Here we still need to fill the gap that the storage node might drops a small number of blocks. For the case that there is only one storage node, we could use the technique of error correcting code so that dropping a small number of blocks would not fail the reconstruction of the entire files. For the case that there are lots of storage nodes, one can store the blocks simultaneously in lots of nodes to solve this issue. Further more, the proofs can be compressed via zk-SNARKs.

Unfortunately, tradition PoS only guarantee that a standard-alone prover or storage node had possession of some data at the time of the challenge/response. And there are various practical attacks that malicious nodes could exploit to get rewarded for storage they are not providing: Sybil attack, outsourcing attacks, generation attacks.[fil]

• •

  Sybil Attacks: Malicious miners could pretend to store (and get paid for) more copies than the ones physically stored by creating multiple Sybil identities, but storing the data only once.

• •

  Outsourcing Attacks: Malicious miners could commit to store more data than the amount they can physically store, relying on quickly fetching data from other storage providers.

• •

  Generation Attacks: Malicious miners could claim to be storing a large amount of data which they are instead efficiently generating on-demand using a small program.

In practical, we usually use two varieties of PoS, Proof-of-Replication and Proof-of-Spacetime [ACET20].

Proof-of-Replication (PoRep) is a novel Proof-of-Storage which allows a server (i.e., the prover P) to convince a user (i.e., the verifier V) that some data D has been replicated to its own uniquely dedicated physical storage. It can prevent the Sybil attack, outsourcing attacks, and generation attacks.

A simple example of proof-of-replication is that, instead of storing the data blocks $\{m_{i}\}$, the user requires the storage nodes to store a replica $m^{\tau}_{i}$ of each data blocks. In the proof phase, the storage nodes prove the integrity and availability of replica through above PoS protocol. The key point here is that constructing a replica $m^{\tau}_{i}$ from the origin data $m_{i}$ and/or other replicas $m^{\tau^{\prime}}_{i^{\prime}}$ requires much more time than generating the PoS proofs (such a replica scheme can be constructed via seal scheme or delay encoding scheme.). And the user will reject those proofs if they takes too much time to generate. Though these methods, the malicious storage nodes cannot generate a valid proof with the help of other nodes in a short enough time.

Since the introduction of proof-of-replication, various of novel schemes are constructed, towards better prove/verification performance, proof size and/or security, such as [Fis19],[CYH⁺21] and so on.

Proof-of-Spacetime (PoSt) schemes allow prover P to convince verifier V that P has spent some “spacetime” (storage space used over time) resources. A direct solution is to require the storage nodes to generate a sequence of PoRep proofs. The challenge of each proof are generated through hashing the essential challenge, loop counter and the previous proof. Using such method, the adversary cannot generate proofs parallel and it has to generate those proofs one by one and owning the replica through all the time.

However, above solution will result a huge proof size and verification time. Since the introduce of PoSt, various of novel schemes are constructed, such as [ACET20, Mon23] . They reduce the proof size and verification time though various way, such as composable zk-SNARKs or verifiable delay-functions.

In NuLink, we require a storage layer to provide storage service. We will provide two possible solutions in the future.

The first solution is to rely on the existing distributed storage network, for example, Filecoin. Filecoin is built on top of IPFS protocol, and uses PoRep and PoSt to ensures data integrity and availability. We would provide a service so that NuLink users can store these data on Filecoin. After receiving a storage request from a NuLink user, we first need to transfer user’s NLK token into Filecoin cryptocurrency through existing zk-Bridge provider or other similar system we would develop and run over watch nodes. Then, we generate the storage order to store the (possibly preprocessed) data on Filecoin network. The retrieval of data is done in a similar way.

Here, NuLink will provide the client that help the user to a) transform its NLK token into Filecoin cryptocurrency via online zk-Bridge system or watch nodes, b) (optional) encrypt the data via homomorphic encryption scheme to ensure the secrecy, c) preprocess the (encrypted) data to generate proper storage order for Filecoin, and d) generate of retrieval order for future usage of data.

The second solution is to build the distributed storage network ourselves. On the top of IPFS protocol, we could utilize and develop the newest PoRep and PoSt schemes, reduce the communication bandwidth, and improve the prove and verification computation. We will use NLK token directly as the benefits of storage nodes. In the NuLink network, storage nodes are required to stake NLK tokens as collateral in order to offer their services and receive corresponding rewards. If the storage nodes violated the protocol, their staked NLK tokens would be slashed as a penalty.

We would also consider several optimizations for the goal of NuLink network, where the stored data might be as a input of some computations. For the case that the data is sensitive, the data should be encrypted via fully homomorphic encryption (FHE) scheme and using the homomorphic property of FHE to finish the computation. However, the size of FHE ciphertexts is much larger than plaintexts. One possible solution is the mixed encryption scheme, that is, encrypt the data using symmetric encryption (e.g., AES), store the symmetric ciphertexts rather than FHE, decrypt those symmetric ciphertexts homomorphically to generate the FHE ciphertexts of data for further computation via a FHE ciphertext of the secret key of symmetric encryption. However, these solution will result a lots of extra computation.

In our situation, we could use linear secret sharing scheme (with proper parameters) instead of symmetric encryption. Instead of store the data, we require the storage nodes to store a secret share of the data. In this way, unless the adversary control much enough nodes, it cannot learn any thing about the data. At the time that one need to compute over these data, we require each node to encrypt its secret share via the FHE encryption. Run the reconstruction algorithm of secret share in FHE ciphertexts and obtain the FHE encryption of the data. Due to that the reconstruction algorithm is a linear function, the computation cost is very light.

NuLink allows users outsource the computation to the computation nodes or other computation service provider. There are two main security concerns, soundness and privacy. Soundness means that the output of the computation nodes is indeed the result of the computation over these data. And privacy means that the computation nodes or computation service provider cannot learn anything about the data. For the case that the parameters of computation model is also sensitive, the privacy also requires that the parameters of computation cannot leak. As one can see, the soundness is necessary for outsourcing computation and privacy is optional. In other words, there are several situations that privacy is not necessary.

No matter which situation it is, the main paradigm of the (zero-knowledge) proof of computation is as follows. Suppose that the data is $x$ (perhaps encrypted), which is sanded by the user or storage nodes, the computation function is $f$, which is public, and $r$ is the computation parameters, if exists. Generate $crs$ as the common reference string of the (zk-)SNARKs scheme for $L_{f}:=\{(x,y)|f(x,r)=y\}$. The computation node/service provider first computes the result of computation $y=f(x,r)$, records the computation processes and uses the prove algorithm of (zk-)SNARKs to generate the proof $\pi$ showing that $y$ is indeed the output of $f(x,r)$. After receiving the output $y$ and the proof $\pi$, the user uses the verification algorithm to verify the validness of proof $\pi$ for statement $(x,y)\in L_{f}$.

According to different cases, there will be numerous differences in practical instantiation.

Use LPCP-based SNARKs as example. Groth16[Gro16] scheme is one of the most famous LPCP based scheme. To use it, before outsourcing computation, both parties need to transform the computation function $f$ into an arithmetic circuits $C$ such that $f(x)=y\Longleftrightarrow C(x,y)=1$. Such a process is called arithmetization. It is a deterministic process and only need to do it for once. Secondly, the user runs the setup algorithm $Setup(1^{\lambda},C)$ to generate the $crs$. And it also needs to be run for only once for each computation function. The remaining process follows the above paradigm: the computation node compute the function and generate the proof, the user check the validness of proof.

We need to mention here that: Usually, the setup algorithm of Groth16 scheme should be run by a trusted third party. However, in the decentralize environment, it’s hard to instantiate such a party. And the correctness of crs is necessary for both soundness and zero-knowledge property of zk-SNARKs. But in this case, we do not need to consider zero-knowledge property, therefore we only need to consider the soundness. Soundness is used to protect the verifier, in this case, the user. There is no reason for users to generate a error crs to break the soundness as that it only damage themselves. Therefore, here we require the user to generate the crs.

Now, we talk about the cost of using Groth16. The arithmetization of computation function and the generation of common reference string can be done in offline and only need to be done for once. Groth16 is based on a bilinear group $(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G_{T}})$ To generate a valid proof, the prover needs to operate $O(|C|)$ group exponent operations. The proof of Groth16 only consists three group elements (two elements in $\mathbb{G}_{1}$ and one in $\mathbb{G}_{2}$). In practical, that’s about 128 bytes. The verification of Groth16 is about $(|x|+|y|)$ group exponent operations and three pairing operations. In practical, that’s about 2 millisecond.

As we can see, the performance of the proof size and verification time of Groth16 is quite good. In the meanwhile, the user needs to generate a crs for Groth16, which might cost a lot. Therefore, if the privacy is not necessary, and the user will run the function for lots of times, it is a good choice to use Groth16 as above. There are some good example about this case. For example, the meteorological observatory want to predict the tomorrow’s weather from its meteorological data. In this cases, the predict function could be a public function and it will be execute for almost everyday.

Using PIOP-based SNARKs as example. There are various PIOP-based SNARKs scheme, in NuLink, we are going to use PLONK scheme[GWC19] and its developing version (e.g.,[pro22],[CBBZ23]) due to their great verification and communication performance. Same as Groth16 scheme, both parties need to transform the computation function $f$ into an arithmetic circuits $C$ such that $f(x)=y\Longleftrightarrow C(x,y)=1$. Then, using existing common reference string (we will discuss it later), the prover use the computation data to generate the SNARKs proof and the user check the validness of proof.

There are two point here we need to mentioned.

The first one is the generation of crs. For the case that the crs is a common random string, both party can use the hash of the statement or some global random string as crs. For the case that the crs is a common structure string, in PIOP-based construction, these crs are usually universal and updatabale. That is, the generation or updata of crs is independent from the proved circuit and these crs are secure as long as there are at least one honest party take part in the generation of update of these crs. Therefore we only need to generate a limited number of crs for different size circuit in NuLink and the users only need to updata these crs for only once (then the user can use these crs for even different circuit).

The second one is the preprocessing of the circuit. Although the cre can be generated independent from circuit, unlike Groth16 or other LPCP-based scheme, the verification has to be dependent with both the description of circuit and inputs. But luckily, the verification progress can be devided into two phases, offline phase and online phase. Offline phase is only (deteministically) dependent with the description of circuit and the online is only dependent with the inputs. Therefore the user can preprocess the circuit and generate the necessary information in the offline phase for each circuit and conclude the online phase efficiently. Furthermore, the necessary information are usually encoded as polynomial commitments and therefore the user can outsource this generation to computation nodes and check the correctness by open random points.

As we discuss above, the online verification time and communication bandwidth is $O(\log s$ where $s$ is the size of circuit and by using proper scheme, the prover time is linear to circuit size. Furthermore, one can use the custom gate to further improve the performance. This approach is suit for most situations.

In this case, in order to protect the privacy of data, NuLink will introduce fully homomorphic encryption (FHE). More detail, the user will encrypt its data and require the computation nodes to evaluate the fuction over the ciphertext via FHE. Although it seems like the this case is similar with above one except the difference of compuation fucntions, the introduce of FHE will significantly increasing the size of circuits. Now, generating the crs for Groth16 will cost a lot. Therefore it is no more suitable to choose Groth16 in this case.

Therefore, we will mainly consider PLONK scheme in this case, especially HyperPlonk scheme which has linear prover time. Furthermore, in this case, the computation function will have lots of repeated subcircuit. That’s due to that evaluate the goal function over FHE ciphertexts will contain lots of homomorphic operations and bootstrapping operations. We will use the custom gate technique of PLONK to design specific circuit for these homomorphic operations and bootstrapping operations to further reduce the size and improve the performance.

In case 3, the computation is as the form of $y=f(x,r)$, where $r$ is the parameter hiding from the user. Now, we need to rely on the zero-knowledge property of (zk-)SNARKs.

Groth16 scheme: We have shown in Case 1 that the computation service provider can use Groth16 scheme to generate the proof for computation. Groth16 scheme has its zero-knowledge version, which only requires the prover to add several masking parameters. The key point here is that, in case 1 we require the user (verifier) to generate the crs for prover, as that we only consider soundness security. But here we also need to consider the zero-knowledge property, and the user might generate malicious crs to learn extra information of computation parameters and break the zero-knowledge property.

Therefore we need to check the validness of crs generated by user. There are various scheme[ABLZ17, ALSZ21] working on it. Some of them require the user to additionally generate a proof or some auxiliary group elements for prover to check crs. This method requires the user spend significant more time for generating crs and the prover is also required to exceed a crs verification algorithm for checking crs. Other schemes develop a way that the prover can directly check the correctness of crs and don’t need the verifier don’t need to generate additional strings. This method doesn’t increase the computation of verifier but significantly increase the work of prover. We will choose suitable method for different scenarios.

PLONK scheme and its developing varieties: Like Groth16 scheme, PLONK scheme and its developing varieties also have their zero-knowledge versions. They require the prover to add masking polynomial to hiding the witness, which will slightly increase the prover costs. And the verification algorithms remain the same as before or change slightly. Due to that these scheme are either in common randomness string model or in the universal and updatable common reference string model, their crs can be generated honestly in NuLink and we can easily change them into their zero-knowledge version with a small performance penalty.

These cases can be seen as the combination of Case 2 and Case 3. In this case, in order to ensure the privacy of data, we require the user to encrypt its data via FHE and the computation service provider exceed the computation via the homomorphic property of FHE; in order to ensure the privacy of computation parameters, we will use the zero-knowledge version of the SNARKs scheme. For the same reason, we will not use Groth16 scheme for these case. As a result, we will choose the zero-knowledge version of PLONK scheme and its developing varieties in this case. The generation of proof follows the same way as Case 1. We further use the custom gate technique to reduce the size of cirucit and improve the performance, and require the prover to use masking polynomial to hiding the computation parameters.

Besides ensuring the honest behaviors of storage nodes and computation nodes, zero-knowledge proof can also be used to ensure the behavior of trader is honest or the owned data satisfies the requirement. Although these scenarios can be seen as a special case of that proving the honest behaviors of computation nodes, the goal and requirement of these scenarios and the design of protocol are different. And therefore we put them into an independent subsection.

In this subsection, we will present several scenarios of transaction and show how zero-knowledge proof works in these scenarios.

In NuLink, the seller might have lots of digital contents that the seller want to sell. These digital contents could be music, illustration, cartoon or games. The seller could shows the overview of its digital contents and send the full version to the one who buys it. To reduce the online communication bandwidth, the seller could 1) upload the ciphertexts of its digital contents on the storage nodes (everyone can download it) and sends the secret keys to the one who buys it or 2) upload its digital contents in the plaintext mode on the storage nodes (only the one having admission can download it) and send a signature to the buyer which gives the buyer an admission to download the corresponding information from the storage nodes. The first method presents stronger privacy as that the storage nodes cannot learn the information of these digital contents while the second method presents skip the decryption process for buyer. Here we only consider the first mode.

In some cases, the buyer might don’t want to release its choice. It is a practicality requirement. For example, consider the following situation: A digital book seller sells books about diseases. And a patient wants to buy a book about its disease. Of course the patient doesn’t want others know about what it buys as it might leakage its disease. In fact, the information of what peoples buy might leak the information about their age, sex, income, where they live and so on, which they might even not realize.

Here we present one solution for handling above question. Suppose that the buyer wants to buy some files encrypted on the storage nodes and sold by the seller. The buyer first generates the first round of a two-round priced oblivious transfer (priced OT) with input its choice and the amount of transaction money, and broadcasts the transaction transcript (only contains the amount and the id of buyer and seller) as well as the priced OT message on the blockchain. The seller, after receives this message on blockchain, generates the second round of the priced OT with input of the secret key for decrypting files, as well as a zero-knowledge proof showing that the generation of priced OT is honest and the input secret key is consistent with the one of files. Finally, the buyer could extract these secret key from priced OT and decrypt the file. Easy to find that the details of transaction is hiding from anyone else and even the seller either doesn’t know what buyer buys. And the cheater is prevent via the zero-knowledge proof.

However, in above solution, the amount of transaction money is public. It is okay the prices of the goods of seller only have a few types. If the prices of the goods are difference from each other, it is still possible to learn what the buyer buys. To avoid this issue, a direct way is to require the seller avoid has lots of prices for its goods, and a complicate solution to avoid the public of the amount.

There are two places that leak the amount, the transaction and the priced OT. For the fist one, we rely on structure of zerocoin or zerocash that, with the help of zero-knowledge proof, get rid of the leakage of amount in transaction. For the second one, we use n-out-of-2n OT instead of priced OT. For more details, let $n$ be the amount of seller’s good. The buyer generates the first round message of the OT with input $r_{1}\|r_{2}$, where $r_{1}$ is the choice of buying and $r_{2}$ is a random string which makes the Hamming weight of $r_{1}\|r_{2}$ is $n$. We additional require the buyer generate a zero-knowledge proof showing the amount of money and the amount applied by OT is consistence. And the seller exceed the same as before except that now it uses the n-out-of-2n OT with proper inputs (the first n-th inputs are the corresponding public key and the last n-th inputs are dummy message) instead of priced OT.

NuLink PRE api will further develop zero-knowledge proof technology to implement information filter and value proof.

Specifically, when Bob wants to further filter information within a certain tag, he need to present some bonus, Alices can provide further value proof to get the rewards. The process is as follows:

Bob sends a reward to the network, which includes tags, specific content/picture requirements, and the duration. The Filter Nodes transfer the content requirements to Alice who have files with that required tag. Within the reward duration, Alice can generate a ZKP to prove that their file contains the specific content that Bob is looking for, without exposing the rest of the file’s other contents. The Filter Node reads the file from the storage node and verifies the proof, then return a file list to bob. The bonus is distributed to users who pass the verification and to the Filter Nodes.