zk-SNARKS and zk-STARKS: Zero-knowledge Proofs Description and How Do zk-SNARKS Work

Along with the numerous advantages of the Internet from which we can benefit, privacy is at risk when using it for social media or business purposes.

Around 90 million Facebook clients suffered damage from the data of Cambridge Analytica. The Wall Street Journal stated that this is just the beginning, and the results are expected to grow.

The Equifax data breach revealed private user information on social media channels. Thus, dates of birth for the majority of the population were exposed. The data of more than 55 million customers was also shared because of the Uber hack.

The security issues are obvious.

Confidentiality on Blockchain

Cryptocurrencies are primarily focused on the financial market, and offer execution of monetary and value transactions in the network. Blockchain technology enables money-exchange procedures and does not require a trusted third party.

This type of approach can also lead us to the loss or theft of our digital property. It can reveal our personal data or expose us to hacking, which can cause awful results for all parties.

Bitcoin, as a peer-to-peer network, provides access to all available ledger data. As blockchain is characterized by an open and transparent nature, every node has direct access to all records of all transactions that have ever been conducted on the network. In general, each node has the ability to trace any of the records and find out the total amount of Bitcoins in a particular blockchain wallet.

However, conducting a crypto transaction makes pseudonymity impossible. It reveals some of the data of the wallet owner, which can lead to a loss of financial security.

Blockchain technology lacks confidentiality, which has caused some difficulties with cryptocurrency acceptance. Privacy is a decisive factor that interferes with the implementation of its full potential.

The New Game-Changers: zk-SNARKS and zk-STARKS

Today, two leading technologies are offering their cryptocurrencies — Monero and ZCash — and are striving to solve protection issues. Monero uses the Ring Confidential signature technology. In contrast, Z-Cash takes advantage of zk-SNARK (Zero-knowledge scalable transparent argument of knowledge), a technology that provides the ability to conduct anonymous transactions.

zk-STARKs aim to provide fast, scalable solutions to ensure financial security. In this way, transaction encryption is possible. zk-STARKs were listed as one of the 10 Breakthrough Technologies of 2018. The fact that such widely-known organizations as R3 and Ethereum have already started to implement zk-STARKs in their use cases is proof of the high potential of zk-SNARKS.

Shafi Goldwasser, Silvio Micali, and Charles Rackoff created ZKPs in the 1980s. They’re exploring systems with which users can prove data by stating that they have knowledge of certain data without exposing it.

zk-SNARKs are built on Black2b cryptography that provides the ability to verify knowledge through one of the parties with ring-signature verification. As of today, only Zcash uses this technology.

The features of a Zero-knowledge proof:

• Completeness: a verifier can be convinced in the true data by an honest prover.
• Soundness: if the prover lies, the verifier will know it.
• Zero-Knowledge: if the statement is true, the verifier won’t find out what the statement actually is.

zk-SNARK (zero-knowledge Succinct Non-Interactive ARgument of Knowledge) needs to be:

• Zero-knowledge: if the statement is true, a verifier does not learn anything beyond the fact that the statement is true.
• Succinct: The size of the proof needs to be small enough to be verified in a few milliseconds.
• Non-Interactive: Only one set of information is sent to the verifier for verification, therefore there is no back and forth communication between the prover and verifier.
• Argument: A computationally soundproof: soundness holds against a prover that leverages polynomial-time, i.e. bounded computation.
• Knowledge: The proof cannot be constructed without access to the witness (the private input needed to prove the statement).

Smart contracts have a self-executing nature. To conduct a transaction, a sender has to transfer money to a receiver. After this, a smart contract can implement the transfer. However, some data is better to keep encrypted, to allow only the sender and receiver to trace it. ZKP helps to conduct a transaction and avoid revealing the participants, currency and sent amount.

It is worth saying that some groups can track the transactions of the largest wallet owners. However, they can only minimize the list of wallet owners for several individuals. There is no possibility of identifying the real wallet owner.

Zero-Knowledge Proofs

Before the appearance of ZKPs, a prover could be malicious and could cheat a verifier. Shafi Goldwasser, Silvio Micali, and Charles Rackoff questioned the true intentions of the verifier. They thought about how to reveal whether or not a verifier is telling the truth, and whether a prover can trust him/her.

To protect ourselves, we must first set a strong password and send it to the server. Then, the server hashes the password and checks to see whether it is correct. If someone tries to log in, the website will ask for a password. In case of attack, the password is compromised, and the results can be dire.

Zero-knowledge proofs provide a tool to help avoid such a scenario.

ZKP consists of two players: a prover and a verifier. The verifier has to convince the prover that he/she knows certain data of a secret item, but he/she doesn’t need to say any information about it.

Let’s imagine that program C possesses two parameters: x and w. The first one is public, and the other contains secret data. The result can be either true or false. The first player has to prove that he/she knows secret witness w, so C(x,w) is true.

If someone just wants to prove that he or she knows a secret piece of information without telling it to anyone, zk-SNARK is the best solution.
zk-SNARK has three inputs: G, P, and V.

G has a secret parameter, and the program creates two public keys: a proving key and a verification key. These inputs are open, and can be created only once.

Proof vs. Proof of Statement

With ZKP, we can prove two types of data: proof of the fact and proof of knowledge.

Proofs of fact are the well-known truths that a user wants to prove with ZKP: for example, whether data B belongs to group C.

Proof of knowledge is a way of stating that you have knowledge of a particular item without exposing any detail on it.

Remember that proving facts and proving knowledge are different, so the solutions to them can be completely different, too. The cryptocurrency world is based on “proof of knowledge,” as it gives no proofs to its users, so they must work on the basis of trust.

There is only the possibility to transform a particular fact into the correct parameter, and to prove it only after this step. The commonly-accepted form is “quadratic arithmetic program” (QAP), which is set to transform the code of a function.

Along with this function, users are provided with the ability to convert a fact into a QAP with input to the code and generate a solution, which is also called a “witness”.

The Difference Between zk-STARKs and zk-SNARKs

The more developed version of zk-SNARKS is called zk-STARKs (Zero-Knowledge Succinct Transparent Argument of Knowledge). It was created by Eli-Ben Sasson, a professor at the Technion-Israel Institute of Technology. He issued a special document that describes a faster solution in comparison to zk-SNARKS.

zk-SNARKs use public-key cryptography for safety, which means that they demand a leaner symmetric cryptography and collision-resistant hash functions. It also excludes some procedures of zk-SNARKs that need more money investments and are more vulnerable to attacks. zk-STARKs offer a set of solutions to surpass zk-SNARKs.

For zk-STARKs, we do not need a trusted setup that decreases money and time resources spent. The main differences between zk-SNARKS and zk-STARKs are:

• The complexity of the arithmetic circuit. In zk-SNARK and zk-STARK technologies, the code is generated in such a form as to be broken down into circuits and computed.
• The complexity of communication. With the increased complexity of the computation, the communication complexity of the zk-SNARK increases linearly, as well. zk-STARKs develop in the opposite way, and increase slowly as the computation size grows, which is the great advantage zk-STARKs in comparison to zk-SNARKs.
• the complexity of the prover. zk-STARK is 10 times faster than zk-SNARK.
• the complexity of the verifier. With the growth in computation size, zk-STARK enlarges slightly. On the other hand, SNARK needs less time
• for proof of confirmation than STARK. For example, STARK takes up to 100 ms to confirm, and SNARK only needs up to 10 ms.

One more thing to consider is that zk-SNARK is difficult to apply at the complexity of the proofs scale.

The Trusted Execution Environment(TEE) allows the offloading of secret computations in blockchain-based networks. TEE technologies — for example, Intel’s Software Guard Extensions (SGX) — isolate code execution, remote attestation, secure provisioning, and safe storage of data. Moreover, applications that use TEE are highly protected from hackers.

Voting

One more case that is definitely taking an advantage of ZKPs is voting. The voting procedure is well-known to every citizen of any country that has ever participated in a presidential election. A person endowed with voting rights chooses, in his or her opinion, the most suitable candidate from the others.

However, this requires personal verification, so many people are afraid of being judged for their choice. ZKP provides the option to vote faster, cheaper, and anonymously.

ZKP in Cryptocurrency

The Zcash cryptocurrency was developed by Zerocoin Electric Coin Company in September 2016. Zcash is the first cryptocurrency that applied ZKP to blockchain technology. This cryptocurrency provides fast, totally secure transactions without sharing data (for example, addresses or location) with anyone.

Zcash integration in Ethereum is an advantageous way of entering the Metropolis phase for Ethereum. Zooko Wilcox, Chief Developer at Z-Cash, presented at DevCon2 in Shanghai, where he described three methods of zk-SNARK application to Ethereum:

1. Baby Zoe (Zoe = Zcash on Ethereum). This is about adding a zk-SNARK pre-compiler on Ethereum and creating a Zcash smart contract on the platform. It helps to determine whether Ethereum will allow the creation of a zk-SNARK on top of its network.
2. Integration of Ethereum computability within Zcash.
3. The Alchemy project was designed to establish cooperation between two blockchains. It can be implemented by cloning BTC Relay, an Ethereum script that provides a Bitcoin light client.
4. Zero-knowledge proof offers an open and advantageous space for transaction implementation. The verification algorithm consists of building blocks that are included in Ethereum as precompiled contracts.

The generator runs out of the network to generate a proving key and a verification key. The prover establishes a proof with the proving key. This can also be implemented off-chain.

The verification algorithm is run along with the proof, the verification key, and the public parameters, which are added as the input data.

Let’s find out how zk-SNARKs can solve privacy issues on the network. A token contract has a mapping from addresses to balances:

mapping (address => uint256) balances

Now, let’s keep the same code, replacing the balance with the hash of the balance:

mapping (address => bytes32) balance Hashes

In this way, we cannot hide the addresses of users sending or receiving a transaction; only the balance and amount. This is also called a confidential transaction.

zk-SNARKs are used to transfer tokens from one address to another when one is generated by the sender and the other by the receiver.

As a rule, proving the size value of a transaction requires parameter verification:

balances[fromAddress] >= value
Remember that the hashes have to match the balances. Here is the program with x and w - the public and private inputs:
function senderFunction(x, w) {
return (
w.senderBalanceBefore > w.value &&
sha256(w.value) == x.hashValue &&
sha256(w.senderBalanceBefore) == x.hashSenderBalanceBefore &&
sha256(w.senderBalanceBefore - w.value) == x.hashSenderBalanceAfter
)
}

The program below is the receiver’s:

function receiverFunction(x, w) {
return (
sha256(w.value) == x.hashValue &&
sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore &&
sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter
)
}

The program checks the match between the balance, the value, and all hashes:

function transfer(address _to, bytes32 hashValue, bytes32 hashSenderBalanceAfter, bytes32 hashReceiverBalanceAfter, bytes zkProofSender, bytes zkProofReceiver) {
bytes32 hashSenderBalanceBefore = balanceHashes[msg.sender];
bytes32 hashReceiverBalanceBefore = balanceHashes[_to];

bool senderProofIsCorrect = zksnarkverify(confTxSenderVk, [hashSenderBalanceBefore, hashSenderBalanceAfter, hashValue], zkProofSender);

bool receiverProofIsCorrect = zksnarkverify(confTxReceiverVk, [hashReceiverBalanceBefore, hashReceiverBalanceAfter, hashValue], zkProofReceiver);

if(senderProofIsCorrect && receiverProofIsCorrect) {
balanceHashes[msg.sender] = hashSenderBalanceAfter;
balanceHashes[_to] = hashReceiverBalanceAfter;
}
}

For appropriate transaction implementation from the confidential side, one has to address a number of issues:

• Users have to track their balances client-side since they lose the balance the tokens can be returned. The balances could be stored encrypted on-chain with a key got from the signing key.
• Balances need to use 32 bytes of data and encode entropy in part of the balance to avoid reversing hashes to reveal balances.
• Always remember to double-check the address with which you are conducting the transaction.
• Communication is necessary in order to carry out the transaction. Remember that some parties may have a system to implement the transaction, so it can be accomplished as a “pending incoming transaction.”

Actually, the biggest challenge facing zk-SNARK technology trust conditions in the setup phase. Users can’t find out whether the setup phase has been ever compromised. So the main appeal is to be fair and build honest relations within the network.

Conclusion

Privacy is not a problem of blockchain anymore with Zero-Knowledge Proof technology. ZKPs allow nodes to prove data without exposing it. The following companies have already applied ZKP into their technologies:

• QED-it — an Israeli company that performs transactions to prove particular data without sharing it. Zero-knowledge proof allows auditing of financial institutions.
• NuCypher — an ICO project that specializes in proxy re-encryption. With ZKP, NuCypher offers the use of are-encrypted key instead of a public key. This makes it possible to share data safely with the re-encrypted key.
• Nuggets provides the ability to secure the data of online shops by encrypting information through ZKP technology.

Do you want to benefit from ZKP technology, too? Contact Applicature for information specific to your case!