Securing a Blockchain with a Noninteractive Zero-Knowledge Proof

In cryptography, a zero-knowledge proof (ZKP) is a method by which one party can prove to another party that they know value x, without conveying any information apart from the fact that they know value x. We have already written about the general concepts surrounding ZKP and noninteractive ZKP, as well as provided some use cases for employing the protocol within a blockchain.

This time, we examine one of the most prominent examples of noninteractive ZKP—the zk-SNARK protocol, and how blockchain applications can make use of it. You will also learn how others major blockchain networks, such as Ethereum and Hyperledger, use a noninteractive zero-knowledge proof to verify transactions.

What is a noninteractive ZKP?

Noninteractive zero-knowledge proofs are those ZKPs that do not require interaction between a verifier and a prover. Zero-knowledge succinct noninteractive argument of knowledge (zk-SNARK) is a ZKP-based protocol with the following additional features:

• Succinct. The size of the proof is small enough to be verified in a few milliseconds.
• Noninteractive. The proof transcript consists of a single message—from the prover to the verifier.
• Argument of knowledge. A computationally sound proof: soundness holds against the prover that leverages polynomial-time—i.e., a bounded computation.

zk-SNARK consists of the three functions:

1. A key generator (G) takes a secret parameter (λ) and generates two publicly available keys—a proving key (pk) and a verification key (vk).
The key generator function
2. The prover function (PF) takes pk as an input, x as a common input, and w as a private input. The function generates a proof: prf = PF(pk, x, w).
The prover function
3. The verifier function (VF) computes VF(vk, x, prf), which returns Accept if the proof is correct and Reject if it is not.
The verifier function

Note that the secret parameter λ is used in the key generator. This parameter sometimes makes it tricky to use zk-SNARK in real-world applications. The reason for this is that anyone who knows λ can generate fake proof (fake prf), so that VF(vk,x,fake prf) evaluates to Accept without knowing the secret parameter. Thus, running the generator requires a very secure process to make sure no one learns about the parameter or saves it anywhere.

zk-SNARK example: Zcash

To get a better understanding of zk-SNARK, we can look at Zcash, the first widespread application of zk-SNARK. In most public blockchains like Bitcoin, Ethereum, Bitshares, etc., transactions are validated by linking the sender and receiver addresses, as well as input and output values. Using zk-SNARK, Zcash is able to prove that a transaction is valid without disclosing critical information, such as addresses and values involved.

The sender of a shielded transaction creates proof that shows (with a high probability) the following:

• The input values sum to the output values for each shielded transfer.
• The sender proves they have the private spending keys of the input notes. This gives the sender authority to spend shielded payments.
• The private spending keys of the input notes are cryptographically linked to a signature over the whole transaction. This protects the transaction from being modified by a party, which does not know the private keys.

To determine what transactions are spendable, Bitcoin tracks unspent transaction outputs (UTXOs). In Zcash, the shielded equivalent of a UTXO is called a commitment. Spending a commitment involves revealing a nullifier. Zcash nodes keep lists of all the created commitments and revealed nullifiers. Commitments and nullifiers are stored as hashes to prevent revealing pertinent information.

Commitments and nullifiers stored as hashes

A commitment is published for each new note created by a shielded payment. This commitment consists of a hash, containing the recipient’s address, the amount being sent, a number unique to the rho note, which can later derive the nullifier, and a random nonce.

The hash function to find a commitment

When a shield transaction is spent, the sender uses their spending key to publish a nullifier, which is the hash of rho from an existing unspent commitment, and also uses ZKP to prove they are able to spend it. The hash must be different from the set of nullifiers tracking spent transactions kept by every node in the blockchain.

The hash function to find a nullifier

The ZKP protocol for a shield transaction will verify the previous conditions, as well as the following:

• For each input note, a revealed commitment exists.
• The nullifiers and note commitments are computed correctly.
• It is infeasible for the nullifier of an output note to collide with the nullifier of any other note.

Zcash utilizes a set of proving and verifying keys to create and check proofs in addition to the spending keys used to control addresses. These keys are generated in the public parameter ceremony and then distributed to the participants of the Zcash network.

The sender uses their proving keys to ensure that their inputs are valid for each shield transaction. Miners check the shielded transactions follow consensus rules by validating the prover’s computation with the verifying key.

The prover does more work up-front in Zcash’s proof generation. However, this simplifies the verifying process enabling transactions to be verified in milliseconds.

Next, we take a look at how Ethereum and Hyperledger (Fabric and Indy) utilize noninteractive ZKP to validate transactions.

zk-SNARK example: Ethereum

In September 2018, Vitalik Buterin published an article about on-chain scaling to potentially 500 transactions per second. This was a solution based on zk-SNARK.

The main idea is to scale asset transfer transactions on Ethereum by a huge amount without using layer 2, which introduces liveness assumptions, but through employing ZK-SNARKs to mass-validate transactions. There are two classes of users—a transactor and a relayer.

A relayer takes a set of operations from transactors and combines them all into a transaction. The relayer then makes a zk-SNARK proof to prove the validity and publishes the zk-SNARK proof, as well as the transaction data in a highly compressed form to blockchain. A relayer gets rewarded for this by transaction fees from transactors.

In this case, the cost of a zk-SNARK verification with the latest protocols is about 600,000 gas with an additional 50,000 gas for overhead. The main goal for zk-SNARK implementation in the Ethereum blockchain is to reduce the total transaction cost.

The AZTEC team has implemented a ZKP-based solution on a smart-contract level in the Ethereum blockchain. You can use private transactions in Ethereum with an AZTEC smart contract via the confidentialTransfer function. A standard AZTEC zero-knowledge transaction costs between 800,000–900,000 gas.

The AZTEC protocol utilizes a cutting-edge ZKP to enable private transactions on Ethereum. This allows for the logic of transactions to be validated, while keeping the values encrypted.

The AZTEC protocol smart contract validator ratifies a unique zero-knowledge proof that determines the legitimacy of a transaction via a combination of homomorphic encryption and range proofs.

• Homomorphic encryption allows the AZTEC protocol to perform mathematical operations with ciphertexts and get an encrypted result that corresponds to the result of mathematical operations with plaintexts. For example, a person can add two encrypted numbers without knowing the decrypted numbers. Then, another person can decrypt the encrypted sum of numbers without having numbers.
• Range proof enables the AZTEC protocol to validate that a secret number is within known limits without disclosing the secret number.

The AZTEC protocol also provides additional features, such as confidential representations of the ERC20 tokens, fully confidential digital assets, and decentralized confidential exchanges.

zk-SNARK example: Hyperledger Fabric

Identity Mixer (Idemix) is a noninteractive ZKP-based cryptographic protocol suite developed by IBM Research for privacy-preserving authentication and transfer of certified attributes.

Idemix works in a similar way as client certificates in a classical public-key infrastructure (PKI), but with two important differences:

• Flexible public keys. Rather than being bound to a single public key, users can have many independent public keys, called pseudonyms, for the same secret key, so that they can use a different pseudonym for each verifier or even for each session.
• Flexible credentials. The credentials that certify the user’s attributes can be transformed into valid tokens for any of the user’s pseudonyms that contain only a subset of the attributes in the original credential. The transformed token remains verifiable under the issuer’s public verification key.

Classical digital signatures cannot provide this sort of flexibility. Idemix relies on the Camenisch-Lysyanskaya (CL) signature scheme specifically designed to have efficient zero-knowledge proofs, which are cryptographic mechanisms to prove that one knows a valid signature with certain properties without having to reveal the signature itself.

Fabric is one of the most popular Hyperledger frameworks for the blockchain technology, which also integrates Idemix.

Fabric’s implementation of Idemix consists of three components:

• A core Idemix cryptopackage (in Golang) that implements basic cryptographic algorithms (key generation, signing, verification, and zero-knowledge proofs).
• MSP implementation for signing and verifying the transactions using the Identity Mixer cryptopackage.
• A CA service for issuing E-cert credentials using the Identity Mixer cryptopackage.

The Idemix architecture within Fabric

Fabric with the Idemix protocol provides strong authentication, as well as privacy-preserving features. It offers anonymity, the ability to transact without revealing the identity of the transactor, as well as unlinkability, the ability of a single identity to send multiple transactions without revealing that the transactions were sent by the same identity.

zk-SNARK example: Hyperledger Indy

Hyperledger Indy is a distributed ledger, purpose-built for decentralized identity. The framework provides a software ecosystem for private, secure, and powerful identity. Indy puts people, not the organizations that traditionally serve as central authority, in charge of decisions about their own privacy and disclosure. This enables all kinds of rich innovations, such as connection contracts, revocation, novel payment workflows, asset and document management features, creative forms of escrow, curated reputation, integrations with other cool technologies, etc.

Indy uses an open-source, distributed ledger technology. These ledgers are a form of a database that is provided cooperatively by a pool of participants, instead of by a giant database with a central admin. Data lives redundantly in many places, and it accrues in transactions orchestrated by many machines with strong, industry-standard cryptography protecting it.

The solution relies on Indy-anoncreds, a ZKP based on the Idemix protocol, to cryptographically secure credentials. The workflow of Indy-annoncreds begins with the prover creating a master key. This master key is used to guarantee that a credential uniquely belongs to the prover.

Creating a master key

The issuer sends a credential offer to the prover, who then creates and sends a credential request, which is signed using the prover’s master key.

Once the issuer receives the signed credential request, he/she creates a credential for the prover and signs it using the issuer’s private key. (The issuer’s public key is available in the public ledger for other participants.) The signed credential is then sent to the prover.

Creating, requesting, and issuing credentials

Next, the verifier sends a proof request to the prover, who in its turn creates and sends the proof back, which the verifier validates using the issuer’s public key.

Presenting credentials

As we can see, ZKP can provide much needed privacy for blockchain transactions requiring confidentiality. Furthermore, when a blockchain transaction needs to be validated, but the verifier has no access to the prover, organizations can still rely on noninteractive ZKP, such as zk-SNARK. This way, data privacy remains intact, and it only takes milliseconds to verify the transaction.

If you want to learn more about ZKP and zk-SNARK, check out our comprehensive research paper on the topic. It also describes the computational model and formal definition of an interactive proof protocol, as well explains how to implement Idemix in Go.

Want details? Watch the video!

During a blockchain meetup in Berlin, Dmitry Lavrenov of Altoros explained the concepts surrounding ZKP in more detail.

Related slides

Further reading

• A Zero-Knowledge Proof: Improving Privacy on a Blockchain
• Zero-Knowledge Proof: Verifying Blockchain Transactions with Less Risk
• Making Blockchain Comply with GDPR: The Challenges and Fixes
• Blockchain for Insurance: Less Fraud, Faster Claims, and New Models

About the author

Dmitry Lavrenov is Senior Blockchain R&D Engineer at Altoros. With a profound expertise in cryptography, he is knowledgeable about encryption algorithms, cryptanalysis, hash functions, and digital signatures. Dmitry is experienced in developing solutions based on Ethereum, EOS.IO, and Hyperledger Fabric for FinTech, healthcare, and other industries. He also possesses practical skills in synthesis and cryptanalysis of block and stream encryption algorithms, as well as in reverse engineering, analysis of software implementations, and malware analysis.