Non-interactive Zero-knowledge Proof

Non-interactive zero-knowledge proofs are zero-knowledge proofs where information between a prover and a verifier can be authenticated by the prover, without revealing any of the specific information beyond the validity of the transaction itself. This function of encryption makes direct communication between the prover and verifier unnecessary, effectively removing any intermediaries. The core trustless cryptography "proofing" involves a hash function generation of a random number, constrained within mathematical parameters (primarily to modulate hashing difficulties) determined by the prover and verifier.

With this cryptographic engine, the prover must demonstrate the validity of the transaction, by solving the hash of a random number. Finally, proof of the answer is returned to the verifier, without revealing its value.

There are many different methods for establishing a cryptographic proof of hash validity. Perhaps the most notable method, proof of work, involves computing the proper hash value by means of brute force guessing using computational power. A far more scalable approach involves the more modern proof of stake, which leverages the pooled public-key authenticity of blockchain validator networks.

History

Blum, Feldman, and MicaliManuel Blum, Paul Feldman, and Silvio Micali. Non-Interactive Zero-Knowledge and Its Applications. Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988). 103–112. 1988 showed in 1988 that a common reference string shared between the prover and the verifier is sufficient to achieve computational zero-knowledge without requiring interaction. Goldreich and OrenOded Goldreich and Yair Oren. Definitions and Properties of Zero-Knowledge Proof Systems. Journal of Cryptology. Vol 7(1). 1–32. 199
(PS)
/ref> gave impossibility results for one shot zero-knowledge protocols in the standard model. In 2003, Shafi Goldwasser and Yael Tauman Kalai published an instance of an identification scheme for which any hash function will yield an insecure digital signature scheme.Shafi Goldwasser and Yael Kalai. On the (In)security of the Fiat–Shamir Paradigm. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03). 2003 These results are not contradictory, as the impossibility result of Goldreich and Oren does not hold in the common reference string model or the random oracle model. Non-interactive zero-knowledge proofs however show a separation between the cryptographic tasks that can be achieved in the standard model and those that can be achieved in 'more powerful' extended models.

The model influences the properties that can be obtained from a zero-knowledge protocol. Pass showed that in the common reference string model non-interactive zero-knowledge protocols do not preserve all of the properties of interactive zero-knowledge protocols; e.g., they do not preserve deniability. Non-interactive zero-knowledge proofs can also be obtained in the random oracle model using the Fiat–Shamir heuristic.

Blockchain Applications

In 2012, Alessandro Chiesa et al developed the zk-SNARK protocol, an acronym for ''zero-knowledge succinct non-interactive argument of knowledge''. The first widespread application of zk-SNARKs was in the Zerocash blockchain protocol, where zero-knowledge cryptography provides the computational backbone, by facilitating mathematical proofs that one party has possession of certain information without revealing what that information is. Zcash utilized zk-SNARKs to facilitate four distinct transaction types: private, shielding, deshielding, and public. This protocol allowed users to determine how much data was shared with the public ledger for each transaction.

In 2017, ''Bulletproofs'' was released, which enable proving that a committed value is in a range using a logarithmic (in the bit length of the range) number of field and group elements. Bulletproofs was later implemented into Mimblewimble protocol (the basis for Grin and Beam, and Litecoin via extension blocks) and Monero cryptocurrency.

In 2018, the ''zk-STARK'' (zero-knowledge Scalable Transparent Argument of Knowledge) protocol was introduced,Scalable, transparent, and post-quantum secure computational integrity, Ben-Sasson, Eli and Bentov, Iddo and Horesh, Yinon and Riabzev, Michael, 2018
offering transparency (no trusted setup), quasi-linear proving time, and poly-logarithmic verification time.{{cite web, title=Scalable, transparent, and post-quantum secure computational integrity , date=March 6, 2018 , authors=Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev , publisher=International Association for Cryptologic Research , url=https://eprint.iacr.org/2018/046.pdf , accessdate=October 24, 2021

Definition

Originally, non-interactive zero-knowledge was only defined as a single theorem-proof system. In such a system each proof requires its own fresh common reference string. A common reference string in general is not a random string. It may, for instance, consist of randomly chosen group elements that all protocol parties use. Although the group elements are random, the reference string is not as it contains a certain structure (e.g., group elements) that is distinguishable from randomness. Subsequently, Feige, Lapidot, and Shamir introduced multi-theorem zero-knowledge proofs as a more versatile notion for non-interactive zero-knowledge proofs.

Pairing-based non-interactive proofs

Pairing-based cryptography has led to several cryptographic advancements. One of these advancements is more powerful and more efficient non-interactive zero-knowledge proofs. The seminal idea was to hide the values for the pairing evaluation in a commitment. Using different commitment schemes, this idea was used to build zero-knowledge proof systems under the sub-group hidingJens Groth, Rafail Ostrovsky, Amit Sahai: Perfect Non-interactive Zero Knowledge for NP. EUROCRYPT 2006: 339–358 and under the decisional linear assumption.Jens Groth, Rafail Ostrovsky, Amit Sahai: Non-interactive Zaps and New Techniques for NIZK. CRYPTO 2006: 97–111 These proof systems prove circuit satisfiability, and thus by the Cook–Levin theorem allow proving membership for every language in NP. The size of the common reference string and the proofs is relatively small; however, transforming a statement into a boolean circuit incurs considerable overhead.

Proof systems under the sub-group hiding, decisional linear assumption, and external Diffie–Hellman assumption that allow directly proving the pairing product equations that are common in pairing-based cryptography have been proposed.

Under strong knowledge assumptions, it is known how to create sublinear-length computationally soundproof systems for NP-complete languages. More precisely, the proof in such proof systems consists only of a small number of bilinear group elements.Helger Lipmaa. Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. TCC 2012: 169–189

References

Theory of cryptography