Blockchain 101: What Are zk-SNARKs?

What are zk-SNARKs?

zk-SNARK is an acronym for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge,” which is a proof construction where one can prove that he/she owns certain data without having to actually reveal it, without having to interact with the verifier.

Zcash is the first project to use zk-SNARKs’ zero-knowledge cryptography, thus enabling its transactions to be shielded but still verified as valid under the network’s consensus rules. This is what makes Zcash a coin with enhanced privacy.

“Zero-knowledge” proofs enable the owner of the information to prove to a verifying party that his/her statement is valid, without revealing any actual information except its validity. For this, a certain witness would be required, such as the preimage of a hash algorithm or the sequence to a certain Merkle-tree node.

“Succinct” zero-knowledge proofs have very short hash functions, which require only a few milliseconds to be verified, with a proof length of only a few hundred bytes.

“Non-interactive” constructions involve the prover and verifier having very little or no interaction at all. Currently, the process of generating zero-knowledge proofs that are non-interactive and short enough for blockchain publishing involves having an initial setup phase that creates a common point of reference between the two parties. This common reference string is often called a public verifier.

zk-SNAKRKs in Zcash

Zcash achieves zero-knowledge privacy by using a mathematical function to determine the validity of a transaction by returning the answer regarding its validity, without making available the information used in the calculation process. This is achieved by encrypting the network’s consensus rules in zk-SNARKs. The encoding goes through the following steps:

Computation → Arithmetic Circuit → R1CS → QAP → zk-SNARK

The mathematical representation of the transaction validation rules involves generating an “arithmetic circuit” after all the logical steps have been broken down into the smallest operations. Similar to a boolean circuit, the program is broken down into single arithmetic operations of addition, subtraction, multiplication, and division then converted into an arithmetic circuit.

z.cash

How zk-SNARKs are applied to create a shielded transaction

Zcash employs zk-SNARKs to determine that the conditions for a valid transaction have been met without revealing any addresses or transaction amounts.

The sender of a private transaction builds a proof that demonstrates the input values sum to the output values for every shielded transaction. He/She also proves that the private spending keys of the input notes are in his/her ownership, which would allow him/her to spend the coins.

A signature over the entire transaction is linked via cryptography to the private spending keys of the input notes, which does not allow a party that does not have access to these private keys to modify this transaction.

By tracking unspent transaction outputs (UTXOs) the Bitcoin blockchain is able to determine what transactions can be spent. The shielded version of a UTXO in Zcash is known as a “commitment”, its spending requires that a “nullifier” be revealed.

Lists containing all the commitments that have been made all the nullifiers that have been revealed are recorded by Zcash nodes. The nodes store this data as hashes, in order to avoid revealing any information regarding the commitments, or how the relate to their nullifiers.

When a shielded payment creates a new note, it publishes a commitment composed of four hashes:

• the recipient address of the note
• the amount being sent
• a unique note number “rho” (from which the nullifier is derived later on)
• a random one-time word(nonce).

This is how a hash function for a commitment looks like:

Commitment = HASH(recipient address, amount, rho, r)

In order to spend a shielded transaction, the spending key is used by the sender to publish a nullifier which represents the hash of the secret unique number (“rho”) from an existing unspent commitment, thus supplying a zero-knowledge proof that proves they are allowed to spend. This hash must be absent from the set of nullifiers which track spent transactions recorded by all blockchain nodes.

Nullifier = HASH(spending key, rho)

The zero-knowledge proof for a shielded transaction also verifies if the following affirmations are also true:

• for every input note, there has to be a commitment that has been revealed.
• The nullifiers and commitments are properly computed.
• It is impartible for the nullifiers of different output notes to crash amongst themselves

Zcash uses in addition to spending keys for address control, a set of proving and verifying keys that create and validate proofs. These keys are produced in the public parameter setup mentioned above and then distributed to all network participants.

The proving key is used by the sender uses to create a proof for the validity of their input. Miners then verify that the shielded transaction meets all consensus rules by using the verified key on the prover’s computation.

The design of Zcash’s proof generation system requires more work on the prover’s part, but the verifying is simplified to facilitate the major computational labor required by giving most of it to the creator of the transaction.

Zcash’s shielded transactions keep their privacy by using standard, trialed cryptography (hash functions and stream ciphers), but the addition of zk-SNARKs coupled with the system of commitments and nullifiers is what actually enables the transacting parties of the shielded transactions to demonstrate the validity of their encrypted transactions.

Final thoughts

Encrypted transactions enable their participants to benefit from using public blockchains while retaining their privacy.

The implementation of zk-SNARKs was first used in Zcash, but since Bitcoin Private (formerly ZClassic) appeared, there are bound to be more projects to employ this technology.