Preamble
In the blockchain context, zk-SNARK is an advanced security technology that enhances privacy and ensures transparency in cryptographic transactions.
Zk-SNARK allows to prove a knowledge without revealing that knowledge, keeping the user's information absolutely protected.
Zcash, a leading cryptocurrency, uses zk-SNARK technology to completely anonymize transactions, ensuring high security and not exposing users' personal information. This increases safety and reliability for users when making online transactions.
For part 1 of the “Exploring ZK-SNARKs” research series, I will dive into the important details about zk-SNARKs as well as the underlying algorithms and encryption behind this technology in great detail and easy for you to understand.
Concept and mechanism of action of zk-SNARK
Basics of zk-SNARK
Zk-SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge, roughly translated as “Concise and non-interactive proof of non-knowledge disclosure“(I translated it like that for easy understanding). This is a proof construction that allows one party (the prover) to prove that it possesses certain information, for example a secret key, without having to reveal that information and without requiring correspondence. cooperate with another party (verifier).
Currently, zk-SNARK is the most popular proof system in use.
We will break down the acronym “zk-SNARK” into smaller components to examine their meaning in the clearest way.
“Zero-Knowledge”: This means that the input information will be hidden and not revealed to the verifier. In other words, the verifier cannot know anything about that knowledge but only its validity.
“Succinct”(Short): This means that the generated proofs are small in size, about a few hundred bytes, and are verified quickly. This is the first benefit that SNARK brings.
“Non-interactive”: This is the second benefit of SNARK, both sides(prover and verifier), the proof consists of a single message from the prover to the verifier without the need for back-and-forth communication.
“Argument of knowledge”: Is a technical term meaning that if the verifier accepts a proof then the prover must actually know a secret related to the claim being proven verify (instead of just convincing the verifier that the statement is true).
Mechanism of action
Mathematically, zk-SNARK consists of 3 algorithms:
Key Generation(KG): This is a key generation algorithm, which will generate a pair of keys, one for proof (pk) and one for verification (vk). The key generation algorithm takes as input the security parameter λ and a C program, then outputs the keys. This step is also called the Trusted Setup step. We will go into its details in the section below.(pk, vk) = KG(λ, C)
Proving(P): This proof algorithm will prove by taking as input a proof key pk, a statement x and a witness w. The output is a proof prf.prf = P(pk, x, w)
Verification(V): The verification algorithm takes as input the verification key vk, statement x and proof prf. The output is accept or reject.
VerificationResult = V(vk, x, prf)
Benefits of ZK-SNARKs
ZK-SNARKs bring many important benefits, especially in enhancing anonymity, security, scalability and transaction efficiency in a variety of applications. Here are 2 key benefits for software applications:
Privacy: the “zero-knowledge” attribute allows hiding sensitive data related to calculations while still proving the correctness of the statement. In other words, zk-snark performs transactions without revealing personal information, keeping transaction information anonymous and secure. This is useful in cryptocurrencies like Zcash, where users can send funds without revealing the amount, origin, or destination of the transactions.
Scalability: Thanks to the small proof size and short verification time allows the verifier to quickly know that the computation was performed faithfully without having to rerun the computation, thereby reduces the time and resources required for verifying complex calculations, which increases system performance and reliability, while also helping to reduce costs and enhance its scalability.
Trusted setup ceremony
The trust setup process is an important one-time step that generates the necessary data set, which is used later every time cryptographic protocols are deployed.
In ZK-SNARK, this trust setup step is necessary to generate proof and verification keys. These keys are then made publicly available, allowing participants to use them to create and verify evidence.
For each new C program, a new trusted setup needs to be performed because it depends on the details of that C program. During setup, the KG key generation process uses a secret lambda and a C program as input to generate a public key (pk) and a verification key (vk).
(pk, vk) = KG(λ, C)
Therefore, the reliable setup process is not standard and should be conducted separately for each new program.
Toxic Waste (Toxic Waste)
A secret parameter called lamda is required for a reliable setup. This parameter, often called “Toxic Waste“, sometimes makes it difficult to apply zk-SNARK to practical applications.
This is because whoever holds this parameter has the ability to create fake evidence. Specifically, the lambda holder can generate a fake proof, called fakeProof, for any C program with public inputs x, such that
V(vk,x,fakeProof)=true
judged to be true without knowing the secret witness w. This is disastrous!
The most efficient way to generate public parameters for zk-SNARK is through someone generating a public and private key pair, similar to the ECDSA key pair, and then destroying the private key . However, the point of concern is how can we be sure that this side has actually eliminated those “toxic wastes” ?
Therefore, to solve this problem, Multi-Party Computation (Multi-Party Computation, MPC) is applied.
MPC is a cryptographic protocol that allows multiple parties to participate in distributed computation without any party having access to the other party's confidential data.
In each trust establishment process, multiple parties participate in the process together to generate the necessary cryptographic components, such as the public key (pk) and verification key (vk). Each party contributes part of its confidential data to this process.
The ultimate goal of each party after this process is to completely eliminate toxic waste. The reliability assumption in this case is that as long as one of the n participants is honest, the final outcome is guaranteed to be secure.
During a trust setup, each of the n parties brings their secret lambda to co-generate the proof and verification keys.
For this setup to fail, it would require all n parties to have bad intentions and share their secrets with each other. However, as long as one of the parties decides not to reveal their secret, the trust establishment process will still be successful, making the production of false evidence impossible.
The mathematics and coding behind zk-snark
Mathematical foundations
Group theory
ZK-SNARK takes advantage of group theory in performing calculations on elliptic curves and other groups, especially when using bilinear pairings and related algorithms.
Simply put, a group is a set of elements {a, b, c, …} combined with a binary operation, which we denote here as “•”.
A set and operation are called a group if they satisfy the following properties:
Closure: For all a and b in group G, the operation a • b must also be in G.
Associativity: For all a, b, and c in G, the operation (a • b) • c must equal a • (b • c).
Identity Element: There must be an element e in G such that for every element a in G, the operations e • a and a • e are equal to a. This element is unique.
Inverse Element: For every element a in G, there must be an element b in G, often called a^-1, such that the operations a • b and b • a are equal to from unit e.
Subgroups
When a subset of elements in a group obeys all the properties of the group, that set is called a subgroup of the original group.
Fields
A field is a special algebraic structure where a set of elements performs two basic operations: addition and multiplication. Each field must adhere to a series of basic axioms, which define and ensure its general properties.
Below are the axioms that a field must satisfy, with a, b, and c being any elements of the field F:
Associativity of addition and multiplication : a + (b + c)= (a + b) + c anda · (b · c) = (a · b) · c
Commutative properties of addition and multiplication : a + b = b + a and a · b = b · a
Addition and multiplication equation : There exist two different elements 0 and 1 in F such that a + 0 = a and a · 1 = a
Additive inverse : For every a in F, there exists an element in F, denoted −a, called the additive inverse of a such that a + (−a) = 0
Inverse of multiplication : For every a≠ 0 in F, there exists an element in F, denoted a^ -1, called the multiplicative inverse of a such that a · a^ -1 = 1
Distribution of multiplication with respect to addition : a· (b + c) = (a · b) + (a · c)
Examples of fields include the set of real numbers with addition and multiplication, as well as integers modulo a prime number, where both addition and multiplication are defined.
Finite fields
In ZK-SNARK, all operations are performed in finite fields, where values and operations are defined modulo a prime number or based on a prime polynomial.
A finite field is a field with a finite number of elements, for example the set of integers modulo p, where p is prime.
The number of elements in a field, called the order of the field, for a finite field can be:
Some prime numbers (prime field)
Or a power of a prime number (extended field)
In a simple prime field, an element can be represented by an integer from 0 to p-1, where Zp = {0, 1, …, p-1}.
The extension of Zp, called the multiplicative group Zp*, consists of elements that are coprime with p, i.e. Zp* = {1, …, p-1}.
Generators of finite fields
In every finite field, there exists an element called a generator, which is capable of generating all the elements in the group using its exponentiation.
For example, consider the group Z5* in the prime field Z5 = {0, 1, 2, 3, 4}, then Z5* = {1, 2, 3, 4}. In group Z5*, multiplication is a binary operation and multiplications are performed modulo 5; For example, multiplying 3 × 4 does not yield 12 but 2, since 12 mod 5 = 2.
Group Z5* is cyclic and has generators 2 and 3, because:
With generator 2, we have:
2^0 = 1,
2^1 = 2,
2^2 = 4,
2^3 = 3,
2^4 = 1 (repeat cycle)
And with generator 3, we have:
3^0 = 1,
3^1 = 3,
3^2 = 4,
3^3 = 2,
3^4 = 1 (repeat cycle)
These properties make Z5* a powerful group for cryptographic operations, and it is commonly used in cryptographic algorithms such as ZK-SNARKs.
Group homomorphisms
Homomorphisms are mappings between two similar algebraic structures, such as groups or fields, and they preserve the operations within that structure.
Specifically, a homomorphism is a mapping f from group A to group B, when the two groups have the same binary operation, such as multiplication or addition. This mapping preserves the operation, which means:
If ⋅ is a binary operation in the structure of groups A and B, then for every element a and b in group A, the mapping f satisfies the condition:
f ( x ⋅ y )= f ( x )⋅ f ( y )
This ensures that the result of the operation applied to the elements in group A, after being mapped to group B via f, remains equivalent to the operation performed directly on the group B.
Homomorphisms are fundamental to handling the properties of bilinear pairings, making the process of generating and verifying proofs in zk-SNARK more efficient.
Polynomials
Polynomials are a core component in building Quadratic Arithmetic Programs (QAPs), where problems are represented through polynomials and solved through polynomial evaluation and commitment.
A polynomial is a mathematical expression made up of variables and constants, using addition, multiplication, and exponentiation with non-negative integer exponents.
For example, the polynomial 5x² + 2x + 8 is a good example.
When considering a polynomial equation, it can represent an infinite number of different equations between numbers. For example, if we have the equation A(x) + B(x) = C(x) which is true, then it will also be true at all values of x, like:
A(0) + B(0) = C(0)
A(1) + B(1) = C(1)
A(2) + B(2) = C(2)
A(3) + B(3) = C(3)
and so on.
Regarding the degree of the polynomial, it is determined by the largest power of the variable in the polynomial. For example, the polynomial 6x⁴ + 2x³ + 3 has degree 4, because the highest power of the variable x is 4.
Cryptography
Hash functions
Hash functions are widely used to create “commitments” in cryptographic protocols, helping to ensure that data cannot be modified without detection.
A hash function is an algorithm or mathematical function that converts a variable-length string of input data into a fixed-length output string, called a hash value.
The hash function representation formula can be described as follows:
f ( m )= H
where f is the hash function, m is the message, and H is the resulting hash value.
Hash functions have many important properties, making them very useful in many cryptographic applications. Those attributes include:
Pre-image resistance: Mathematically, retrieving the original message from the hash value is very difficult.
Second pre-image resistance: Given a particular input message and its hash value, it is difficult to find another message that produces the same hash value.
Collision resistance: It is difficult to find two different messages that produce the same hash value.
A very desirable property of good hash functions is the Avalanche Effect. This is the property whereby a small change in the input will cause a large change in the output, making the output appear random and indistinguishable.
Encryption
Simply put, encryption is the process of converting an input message (plaintext) into a seemingly random output (ciphertext), so that only authorized people can decode and understand that information. Encryption is based on the use of a cryptographic key, which is a set of mathematical values that both the sender and receiver use to encrypt and decrypt information.
There are two types of encryption algorithms: Symmetric encryption and Asymmetric encryption.
Symmetric encryption
In symmetric encryption, the same key is used by all parties involved in the communication process to encrypt and decrypt the message. This key is kept secret between the parties to ensure the security of the information exchanged.
Asymmetric encryption
In asymmetric encryption, also known as public key encryption, there are two types of keys: a public key used for encryption and a private key used for decryption. The private key is kept private by the recipient (hence the “private key”), while the public key can be widely shared with anyone who wants to send confidential information (hence the “private key”). public").
Asymmetric encryption is widely used in the following situations:
Sending a secure message: The sender uses the recipient's public key to encrypt the message, then sends it to the recipient. Only the recipient in possession of the private key can decrypt and read the message.
Proving ownership of (knowledge of) a private key: In the process of proving ownership of a private key, the sender encrypts (or signs) the message with his private key and then sends it to the recipient. The recipient uses the sender's public key to decrypt the message. This process is often called digital signing, and the message so encrypted is called a “digital signature”. Thereby, a digital signature proves that the message was sent by someone who owns the corresponding private key, and also helps verify the integrity of the information in the message.
Homomorphic encryption (Homomorphic encryption)
Homomorphic encryption is highly influential in the design of high-level zero-knowledge proofs, because it allows calculations to be performed on encrypted data without having to decrypt them.
Homomorphic encryption is a special type of encryption that allows calculations to be performed directly on encrypted data. This means that additional calculations can be performed on encrypted data without the need for a secret key. The results of these calculations remain encrypted, ensuring security without revealing the original data content.
In practice, fully homomorphic encryption, which allows performing all kinds of arbitrary calculations on encrypted data, still has many limitations and is not yet widely applicable. However, performing certain operations on homomorphic structures is feasible and has been used in practical applications.
These operations include addition and multiplication on encrypted data, which has opened up new possibilities for secure data processing without decryption.
Elliptic Curve Cryptography (ECC)
In ZK-SNARK, elliptic curves play an important role thanks to the grouping operations on which bilinear pairing is performed. ECC (Elliptic Curve Cryptography) provides an efficient platform for creating and verifying zero-knowledge proofs.
An elliptic curve is a set of points that satisfy a specific mathematical equation. The equation for an elliptic curve has the following form:
Where, a and b are known constants. The graph of this equation looks like this:
There are many different representations of elliptic curves, but the technique is mainly about finding points that satisfy a certain mathematical equation.
The properties of elliptic curves make them very important in many fields of mathematics and especially in the field of cryptography.
An interesting property of elliptical curves is their horizontal symmetry. Any point on the curve can be reflected across the x axis while keeping the curve intact. This means that if you take any two points on the curve and draw a line through them, that line will intersect the curve at a third point.
Imagine this is a game of billiards , the ball is shot from a point and when it hits the elliptical curve, it bounces straight up or straight down, depending on its position relative to the x axis.
An interesting property of elliptical curves is that you can “dot” two points on the curve to create a new point. You can also successively “dot” a point with itself to create different points on the curve.
But the interesting thing is, if you know the final point and the initial point, calculating the number of “dots” required to get from the initial point to the final point is very difficult!
Imagine a person playing alone in a room, hitting the ball according to the rules of the game. Someone else then comes in and sees the final position of the ball. Even if they knew the initial position and the rules of the game, they would not be able to know how many times the ball was hit to get there without reviewing the entire game from the beginning. This creates a special property in cryptography, called irreversibility, and is the basis for many powerful applications such as the Trapdoor Function.
Discrete logarithms on elliptic curves are a difficult problem, which underpins elliptic curve-based cryptography. Unlike factorization, there is no shortcut that can solve this problem, making it significantly harder to break elliptic curve cryptography than with RSA and Diffie-Hellman.
While ECC provides a high level of security with shorter keys, it still retains good performance on low-power devices. This makes ECC the ideal choice for cryptographic applications on mobile devices and systems with limited resources.
At the end of this section, I have stated some basic mathematical and coding concepts behind zk-SNARK, in the next part, I will elaborate on more advanced concepts such as Quadratic Arithmetic Programs, Elliptic Curve Pairings.
Thank you for reading this far. If you liked this article, don't forget to follow and leave a round of applause.
Article source: Team Tech/Research – AlphaTrue
Reference source:
1.Nguồn: Reitwiessner, C. (2016). zkSNARKs in a nutshell. Ethereum blog, 6, 1-15. https://chriseth.github.io/notes/articles/zksnarks/zksnarks.pdf
2. https://medium.com/coinmonks/from-zero-to-hero-in-zero-knowledge-proofs-part-7-61d639c2ef02
3. https://celo.academy/t/zk-snarks-proofs-as-a-privacy-solution-on-the-blockchain/1961
4.Ngu: Chen, T., Lu, H., Kunpittaya, T., & Luo, A. (2022). A review of zk-snarks. arXiv preprint arXiv:2202.06877. https://arxiv.org/pdf/2202.06877.pdf
5. https://medium.com/coinmonks/from-zero-to-hero-in-zero-knowledge-proofs-part-8-262f923f1537
6. https://medium.com/@hira.siddiqui/from-zero-to-hero-in-zero-knowledge-proofs-part-2-ef17ce470f2d
7. Easttom, W. (2022). Modern cryptography: applied mathematics for encryption and information security. Springer Nature.
8. https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
