ZK 101

Privacy is cool again, but it comes with its own set of puzzles to solve. The buzz around zero-knowledge proofs (ZKPs) is proof (pun intended) that these cryptographic marvels have serious potential. But what exactly are ZKPs, and why should we care? To get our minds around this, we need to take a little detour into the world of number theory and cryptography.

We'll kick things off by wrapping our heads around some number theory basics—think of it as the secret sauce that makes cryptography tick. We’ll explore concepts like groups, modular arithmetic, and the Chinese remainder theorem (which is as cool as it sounds). After that, we'll dive into cryptographic primitives. This math-y appetizer will set us up nicely to tackle the main course: the core principles of zero-knowledge proofs (which are not going to be address in this article).

REALLY IMPORTANT: we strongly recommend you to learn the basics of polynomials --which are not going to be covered in this article. A good video to start with is embedded below:

Number Theory

Understanding the principles of number theory is relevant for anyone interested in cryptography. It provides the mathematical foundation that underpins much of modern cryptographic practice. Concepts such as group theory and modular arithmetic form the building blocks for more advanced topics. By exploring these ideas, we can better appreciate how they contribute to the security and efficiency of cryptographic algorithms, and ultimately, to the implementation of ZKPs.

Groups and Group Theory

A group is the ultimate math playground. Let's think that you have a bunch of objects (that’s your set), and a way to mix and match them (that’s your operation). The cool part? No matter how you combine these objects, they always stay within the playground—no one sneaks out! There's also a "do nothing" element (called the identity element) that just hangs out and doesn’t change anything when you combine it with other objects. And just like in a well-structured playground, there’s always a way to "undo" any action (that’s the inverse element), making sure things can go back to how they were.

Definition:

A group is a set G paired with a binary operation (think of it as a way to combine any two elements) that satisfies four axioms:

1. Closure: If you take any two members a and b from our group G and combine them using our operation (let’s call it *), the result will always be another member of the group. In other words, no one leaves the club!
   a * b ∈ G for all a, b in G
2. Associativity: This is the group’s way of saying, “It doesn’t matter how we group things when we combine them!” If you’re combining three elements a, b, and c, you can first combine a and b, then combine the result with c, or combine b and c first, then combine with a. The final result will be the same.
   (a * b) * c = a * (b * c) for all a, b, c in G
3. Identity Element: There’s a special member in the group (let’s call it e) that acts like a "do nothing" element. When you combine e with any other member a in the group, it leaves a exactly as it was. It’s the group’s way of keeping things unchanged when needed.
   e * a = a * e = a for all a in G
4. Inverse Element: For every member a in the group, there’s another member b in the group that can undo a’s effect. When you combine a and b (or b and a), you get back to our "do nothing" element e. This is like having a built-in undo button!
   a * b = b * a = e where b is the inverse of a

Example: The Additive Group ZN

Let’s jump into a concrete example to see a group in action! Meet the additive group ZN, which is about adding numbers together. This group consists of integers from 0 to N-1 and uses addition as its operation. But here’s the twist—it’s all done modulo N. The identity element here is 0 (because adding 0 doesn’t change anything), and for any number x, its inverse is N - x, which brings the sum back to 0 under modulo N.

Abelian (Commutative) Groups

Next up, we’ve got abelian groups—the chill, go-with-the-flow type of groups. In these groups, the order of combining elements doesn’t matter. This means a * b is the same as b * a for any elements a and b in the group. This property is super handy in cryptography because it simplifies many operations. You can think of abelian groups as the math equivalent of “no fuss, no muss.”

Cyclic Groups

Formally, a group G is called cyclic if there exists an element g in G such that every element h in G can be written as h = g^k for some integer k. The element g is the generator of the group, and we often denote the group as ⟨g⟩.

Discrete Logarithms

Given a cyclic group G with a generator g and an element h in G, the discrete logarithm of h to the base g is the integer x such that:

h = g^x

This is denoted as x = logg(h).

Computational Complexity

Computing discrete logarithms isn’t just hard—it’s cryptographically hard, meaning it's tough enough to keep your secrets safe. This difficulty is the backbone of many secure communication protocols, like the Diffie-Hellman key exchange and digital signatures.

Example in Z*N

In the multiplicative group Z*N (the set of integers less than N that are coprime to N), the discrete logarithm problem can be described like this: Given g and h in Z*N, find the exponent x such that:

g^x ≡ h (mod N)

It’s a challenge that cryptographers love to solve, but thankfully for us, it’s a puzzle that takes a long time without the right tools.

Modular Arithmetic

When we think about modular arithmetic, we shift our perspective from an infinite set of numbers to a finite set of the first n natural numbers. If any given integer falls outside this range, we 'wrap it around' to fit within these bounds. A helpful analogy is to think of it like a clock:

For example, in this clock we choose 6 first numbers. Now, let us see where the number 10 will land. We can think of it as a rope, the length of which is ten units:

If we attach the rope to the beggining of the circle, we will see that after one rotation we still have a portion of the rope left, if we continue, it will land in the number 4:

So, for a more formal definition, we would say that for integers a and b, and a positive integer N (our modulus), we say that a is congruent to b modulo N, written as:

a ≡ b (mod N)

if N divides the difference a - b. In other words, a and b leave the same remainder when divided by N.

Basically, one number is congruent to another if they have the same reminder when you divide them with the same number.

Addition and Multiplication:

In modular arithmetic, addition, subtraction, and multiplication are performed as usual, but the result is then taken modulo N. Think of it as doing regular math, but whenever you hit the “modulus,” you start counting from zero again.

For example:

(a + b) (mod N)

(a × b) (mod N)

This “wrapping around” behavior is what makes modular arithmetic so useful in cryptography—it keeps everything neatly within a specific range, which is super handy for things like encrypting data.

Multiplicative Inverses

An essential concept in modular arithmetic is the multiplicative inverse. For a number a to have a multiplicative inverse modulo N, there must be a number b such that:

a × b ≡ 1 (mod N)

The number b is called the multiplicative inverse of a modulo N, and it exists if and only if a and N are coprime (i.e., their greatest common divisor is 1). This is like having a secret code that when combined with another number brings you back to the identity element (which is 1 in multiplication).

Example:

Consider the modulus N = 7. In this case, the integers {0, 1, 2, 3, 4, 5, 6} form a complete set of residues modulo 7. If we compute 3 + 5 modulo 7, we get:

3 + 5 = 8

8 ≡ 1 (mod 7)

So,

3 * 5 ≡ 1 (mod 7)

This means that 3 and 5 are multiplicative inverses of each other modulo 7.

Applications

Modular arithmetic is used in algorithms like RSA and Diffie-Hellman. It allows for operations on large numbers to be performed efficiently while keeping the results within a manageable range.

One key operation is modular exponentiation, which involves raising a number to a power and then taking the result modulo N. This is fundamental in many cryptographic protocols because it ensures that calculations stay within a finite set of values, making the math both secure and efficient.

Modular Exponentiation

Modular exponentiation might sound like a mouthful, but it’s a really neat trick. It refers to the process of computing a^b (mod N). Essentially, you’re raising a number a to a power b and then taking the remainder when divided by N.

Now, you might be thinking, "That sounds like it could involve a lot of math!" And you’d be right—if it weren’t for a nifty shortcut called repeated squaring. This method significantly reduces the number of operations required, making it much more efficient, especially when dealing with large numbers.

In cryptography, where we often work with huge numbers, this efficiency is golden. Modular exponentiation is the backbone of many cryptographic algorithms, helping us keep data secure without needing a supercomputer for every calculation.

Euclidean Algorithm and GCD

The Greatest Common Divisor (GCD) of two integers is like the ultimate peacemaker—it’s the largest positive integer that divides both numbers without leaving any remainder. The GCD is a cornerstone concept in number theory and pops up all over the place in cryptography.

Definition:

For any two integers a and b, the GCD of a and b, denoted as gcd(a, b), is the largest integer d such that:

d | a and d | b

where | denotes divisibility. In simpler terms, d is the biggest number that can evenly divide both a and b.

Euclidean Algorithm

The Euclidean Algorithm is a clever and efficient method for finding the GCD of two numbers. It’s based on the principle that the GCD of two numbers also divides their difference. Here’s how it works:

1. Given two integers a and b, where a ≥ b, divide a by b to get a quotient q and a remainder r:

a = bq + r

2. Replace a with b and b with r. Repeat this process until r = 0.
3. The last non-zero remainder is the GCD of a and b.

Mathematically, this process is expressed as:

gcd(a, b) = gcd(b, r)

and so on, until r = 0.

Example:

Let’s find the GCD of 252 and 105 using the Euclidean Algorithm:

1. Compute the remainder of 252 divided by 105:

252 = 105 × 2 + 42

2. Replace 252 with 105 and 105 with 42. Then compute the remainder:

105 = 42 × 2 + 21

3. Replace 105 with 42 and 42 with 21. Then compute the remainder:

42 = 21 × 2 + 0

Since the remainder is now 0, the last non-zero remainder is the GCD:

gcd(252, 105) = 21

Extended Euclidean Algorithm

The Extended Euclidean Algorithm is like the Euclidean Algorithm’s big sibling. Not only does it find the GCD of two numbers, but it also expresses the GCD as a linear combination of the two numbers:

gcd(a, b) = ax + by

where x and y are integers. This extra step is useful for finding multiplicative inverses in modular arithmetic.

Applications

The Euclidean Algorithm and its extended are essential in algorithms like RSA (stay tuned, we’ll cover that soon!), where finding the multiplicative inverse is a crucial step. Mastering these algorithms is key to cracking many cryptographic processes.

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) simplifies computations by breaking them down into smaller, more manageable parts. This is especially useful in cryptography, where you often need to juggle several modular equations at the same time.

Statement of the Theorem

The Chinese Remainder Theorem states that if you have a set of integers n1, n2, …, nk that are pairwise coprime (meaning the greatest common divisor of any pair is 1), and any integers a1, a2, …, ak, then there exists a unique integer x modulo N, where N is the product of the ni's, such that:

x ≡ a1 (mod n1)

x ≡ a2 (mod n2)

\vdots

x ≡ ak (mod nk)

In other words, CRT guarantees there’s a unique solution modulo N for this system of congruences.

Example

Consider the system of congruences:

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

Follow these steps to find x:

1. Compute N:

   N = 3 × 5 × 7 = 105

2. Compute the partial products Ni:

   N1 = 105/3 = 35

   N2 = 105/5 = 21

   N3 = 105/7 = 15

3. Compute the multiplicative inverses Mi:
   • M1 such that 35 × M1 ≡ 1 (mod 3):

     35 ≡ 2 (mod 3)    entonces    2 × M1 ≡ 1 (mod 3)    →    M1 = 2

   • M2 such that 21 × M2 ≡ 1 (mod 5):

     21 ≡ 1 (mod 5)      ⇒      M2 = 1

   • M3 such that 15 × M3 ≡ 1 (mod 7):

     15 ≡ 1 (mod 7)      ⇒      M3 = 1

4. Construct the solution x:

   x ≡ 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 (mod 105)

   x ≡ 140 + 63 + 30 (mod 105)

   x ≡ 233 (mod 105)

   x ≡ 23 (mod 105)

So, the solution is x ≡ 23 (mod 105).

The Multiplicative Group ZN*

The Multiplicative Group ZN* is a set of all integers less than N that are relatively prime to N (meaning their greatest common divisor with N is 1), and the group operation is multiplication modulo N.

Definition:

Formally, the multiplicative group ZN* is defined as:

ZN* = {a ∈ {1, 2, ... , N-1} | gcd(a, N) = 1}

where the operation is multiplication modulo N.

Properties of ZN*

Just like any other group, ZN* comes with a set of properties that make it a well-behaved mathematical playground:

• Closure: If a, b ∈ ZN*, then the product ab (mod N) is also in ZN*.
• Associativity: The multiplication operation in ZN* is associative.
• Identity: The element 1 serves as the identity element in ZN* because:

  1 × a ≡ a × 1 ≡ a (mod N)

  for any a ∈ ZN*.
• Inverses: For each a ∈ ZN*, there exists an element b ∈ ZN* such that:

  a × b ≡ 1 (mod N)

  This b is called the multiplicative inverse of a modulo N.

Example:

Consider N = 10. The elements of Z10* are the integers less than 10 that are relatively prime to 10:

Z10* = {1, 3, 7, 9}

The group operation is multiplication modulo 10. For example:

3 × 7 ≡ 21 ≡ 1 (mod 10)

So, 3 and 7 are inverses of each other in Z10*.

Euler's Totient Function

The order of ZN* (the number of elements in ZN*) is given by Euler's Totient Function, denoted as φ(N). If N has the prime factorization:

N = p1k1 × p2k2 × ... × pmkm

then:

φ(N) = N (1 - 1/p1) (1 - 1/p2) ... (1 - 1/pm)

Primes and Primality Testing

Prime numbers are the building blocks of number theory and play a crucial role in cryptography. A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.

Definition of a Prime Number

A prime number p is an integer greater than 1 such that the only divisors of p are 1 and p itself. Formally:

p is prime if ∀ d ∈ ℤ, d | p ⇒ d = 1 or d = p

Importance of Primes in Cryptography

Prime numbers are fundamental in cryptographic algorithms, especially in public-key cryptography like RSA, Diffie-Hellman key exchange, and elliptic curve cryptography. The security of these systems often depends on the difficulty of factoring large composite numbers or computing discrete logarithms, both of which are computationally hard problems when primes are involved.

Primality Testing

Primality testing is the process of determining whether a given number n is prime. Several algorithms exist for primality testing, ranging from simple trial division to more complex probabilistic and deterministic methods.

1. Trial Division:

   The simplest method of primality testing involves dividing n by all integers up to √n. If none divide evenly, n is prime.

   This method is inefficient for large numbers because it requires a large number of divisions.

2. Fermat's Little Theorem:

   Fermat's Little Theorem states that if p is a prime and a is an integer such that 1 ≤ a < p, then:

   ap-1 ≡ 1 (mod p)

   This theorem is the basis for the Fermat primality test, which is a probabilistic test.

3. Miller-Rabin Primality Test:

   The Miller-Rabin test is a probabilistic algorithm that improves upon Fermat's test. It is based on the observation that for a prime p, certain congruences must hold. It repeatedly checks these conditions with different random bases to increase the confidence that a number is prime.

   While not deterministic, it can be made highly reliable by increasing the number of iterations.

4. AKS Primality Test:

   The AKS primality test is a deterministic algorithm that runs in polynomial time. It is based on the idea that a number n is prime if and only if:

   (x - a)n ≡ (xn - a) (mod n)

   This test is theoretically important, though less commonly used in practice due to its complexity and slower performance compared to probabilistic tests.

Example: Miller-Rabin Primality Test

The Miller-Rabin test checks whether a number n is prime by writing n - 1 as 2s × d, where d is odd. It then picks a random base a and checks if:

ad ≡ 1 (mod n)

or if for some r where 0 ≤ r < s:

a2r × d ≡ -1 (mod n)

If neither condition is met, n is composite. Otherwise, it is probably prime. Repeating this test with different bases a increases confidence in the result.

Discrete Logarithms and the Discrete Log Problem

The concept of discrete logarithms is a cornerstone in the construction of secure communication protocols. The difficulty of solving the discrete log problem is what provides the security in many cryptographic systems.

Definition of Discrete Logarithm

Given a cyclic group G with a generator g and an element h ∈ G, the discrete logarithm of h to the base g is the integer x such that:

h = g^x

This is denoted as:

x = logg(h)

where logg(h) is the discrete logarithm of h with respect to the base g.

Discrete Logarithm in Modular Arithmetic

In modular arithmetic, the discrete logarithm problem is typically posed in the multiplicative group Zp*, where p is a prime number. The problem is to find x given g and h such that:

h ≡ g^x (mod p)

This is a difficult problem to solve efficiently, especially when p is large, making it a cornerstone of cryptographic security.

The Discrete Log Problem

The Discrete Logarithm Problem (DLP) is the challenge of finding the discrete logarithm x given g and h in a cyclic group. Formally, given g and h in G, find an integer x such that:

h = g^x

This problem is computationally hard in many groups used in cryptography, such as Zp* and certain elliptic curve groups.

Computational Complexity

The discrete logarithm problem is known to be hard to solve efficiently in general, particularly in the groups commonly used in cryptographic applications. The best-known algorithms, like the baby-step giant-step algorithm and the number field sieve, still require exponential or sub-exponential time to solve in large groups. This hardness forms the basis of security for many cryptographic systems.

Example in Zp*

Consider p = 23, and let the generator g = 5. If we know that:

h ≡ 5^x (mod 23)

and h = 8, the problem is to find x such that:

5^x ≡ 8 (mod 23)

Through trial or using specific algorithms, we find that x = 3 because:

5^3 = 125 ≡ 8 (mod 23)

Applications

The security of several cryptographic systems relies on the hardness of the discrete logarithm problem. For example:

• Diffie-Hellman Key Exchange: The security of this protocol is based on the difficulty of computing the discrete logarithm in a large prime modulus.
• ElGamal Encryption: This encryption scheme also relies on the difficulty of solving the discrete log problem.
• Digital Signatures: Algorithms like the Digital Signature Algorithm (DSA) and ECDSA (Elliptic Curve DSA) are based on the discrete log problem.

Variants of the Discrete Log Problem

• Computational Diffie-Hellman (CDH) Problem: Given ga and gb in G, compute gab without knowing a or b. This is believed to be as hard as solving the DLP.
• Decisional Diffie-Hellman (DDH) Problem: Given g^a, g^b, and g^c in G, determine whether c = ab modulo the group order. This is believed to be easier than the CDH and DLP.

These problems and their computational difficulty are essential for ensuring the security of many cryptographic protocols.

Quadratic Residues

A quadratic residue modulo n is an integer that can be expressed as the square of some integer modulo n. Quadratic residues play a significant role in number theory and cryptography, particularly in the construction of certain cryptographic protocols.

Definition

An integer a is called a quadratic residue modulo n if there exists an integer x such that:

x^2 ≡ a (mod n)

If no such x exists, then a is called a quadratic non-residue modulo n.

Example

Consider the modulus n = 7. To determine the quadratic residues modulo 7, we compute the squares of the integers 0, 1, 2, ..., 6 modulo 7:

0^2 ≡ 0 (mod 7)

1^2 ≡ 1 (mod 7)

2^2 ≡ 4 (mod 7)

3^2 ≡ 9 ≡ 2 (mod 7)

4^2 ≡ 16 ≡ 2 (mod 7)

5^2 ≡ 25 ≡ 4 (mod 7)

6^2 ≡ 36 ≡ 1 (mod 7)

Thus, the quadratic residues modulo 7 are {0, 1, 2, 4}.

Properties of Quadratic Residues

For a prime modulus p, exactly half of the non-zero elements of Zp are quadratic residues. If p ≡ 3 (mod 4), then for any quadratic residue a, the value of x such that:

x^2 ≡ a (mod p)

can be efficiently computed using:

x ≡ a(p+1)/4 (mod p)

- For any integer n, the quadratic residues modulo n form a subgroup of the multiplicative group Zn*.

Legendre Symbol

The Legendre symbol (a/p) is a notation that helps determine whether an integer a is a quadratic residue modulo a prime p. It is defined as:

(a/p) =
{ 0 if a ≡ 0 (mod p)
} 1 if a is a quadratic residue modulo p and a ≠ 0 (mod p)
} -1 if a is a quadratic non-residue modulo p

Example of Application

In the context of the BBS generator, given a modulus n = pq, where p and q are large primes, and a seed x0, the sequence is generated by:

xi+1 = xi^2 (mod n)

The output bit at each step is the least significant bit of xi.

The hardness of breaking the BBS generator is based on the difficulty of the quadratic residuosity problem: given an integer a modulo n, determine whether a is a quadratic residue modulo n without knowing the factorization of n.

Cryptographic Primitives

Cryptographic primitives are the building blocks of cryptographic systems, forming the basis for secure communication, data integrity, and authentication. Let's explore some key cryptographic primitives, including hash functions, symmetric and asymmetric encryption, and digital signatures.

Hash Functions

Hash functions play a pivotal role. They are mathematical algorithms that take an input (or 'message') and return a fixed-size string of bytes. This output, typically a digest, appears random and is unique to the input provided.

Technical Breakdown

• Determinism: A hash function is deterministic, meaning the same input will always produce the same output.
• Fixed Output Size: Regardless of the input size, the hash output will always have a fixed length, making it predictable and consistent.
• Pre-image Resistance: Given a hash value h, it is computationally infeasible to reverse-engineer the original input m such that H(m) = h.
• Collision Resistance: It is hard to find two different inputs m1 and m2 such that H(m1) = H(m2). This ensures that each unique input has a unique hash.
• Avalanche Effect: A small change in the input (even a single bit) should produce a significantly different hash, ensuring the hash is sensitive to input variations.

Common Hash Functions:

• MD5: Once widely used, MD5 produces a 128-bit hash but is now considered insecure due to vulnerabilities.
• SHA-1: Produces a 160-bit hash and is stronger than MD5 but still has known vulnerabilities.
• SHA-256: A part of the SHA-2 family, this function produces a 256-bit hash and is widely used in secure applications, including Bitcoin.
• SHA-3: A newer hash function with different design principles, offering strong security levels.

Applications

• Data Integrity: Hash functions ensure data hasn't been altered during transmission or storage. For example, comparing the hash of a downloaded file with a known value can verify the file's integrity.
• Digital Signatures: Hash functions are used to create a hash of a message, which can then be signed with a private key to ensure the message has not been tampered with.
• Password Storage: Instead of storing passwords in plaintext, systems store the hash of the password. When a user attempts to log in, the system hashes the entered password and compares it to the stored hash.
• Proof of Work: In blockchain systems like Bitcoin, hash functions generate cryptographic puzzles that miners must solve to add new blocks to the chain.
• Message Authentication Codes (MACs): Hash functions are used with a secret key to create a MAC, ensuring the integrity and authenticity of a message.

Encryption and Signature Schemes

When learning about digital signatures, a common narrative is presented: Alice, a user with a secret (private) key, can sign a message that can be verified by anyone using her corresponding public key.

However, the underlying mechanisms are often overlooked. Implicitly, it is understood that deriving a private key from a public key should be impossible. This is crucial because it prevents anyone who possesses Alice's public key from producing signatures in her name (hence the term "private").

Now, suppose Alice and another individual, Bob, agree on a generator point G on the elliptic curve. Alice then chooses a random number d from the set of integers modulo q, so d < q. Also, let’s assume d is a large number, not just 12 or 35. This will be her private key.

Alice proceeds to calculate Q = [d]G, leveraging the power of point doubling, and obtains another point in the group — this will be her public key, which she can safely share with Bob.

Evidently, Q encodes information about the private key. Bob could try to calculate a number d such that Q = [d]G, but the problem is that if our elliptic curve group is “large enough,” it would take Bob a really, really long time. And this is precisely the secret sauce: finding d, even when knowing Q and G, should be nearly impossible. This is known as a version of the discrete logarithm problem (DLP).

Of course, if our group happens to have 1,000 elements, or if the number Alice chooses is “small,” trying possible values of d is a manageable task. You can probably write a script that solves the problem in under 10 minutes — this is called brute forcing. The DLP problem really shines when we have massive groups. For instance, the curve 25519 has subgroups of order around 2^250. That’s quite a large number. Good luck trying to brute-force d.

Encryption

Alice now holds a number d as her private key, and Bob holds the corresponding public key Q, which is a point on the elliptic curve. What can they do with this?

With these cryptographic tools, they’re ready to start building some cool stuff — like encrypting data!

Imagine Bob wants to protect a message so that only Alice can read it. If they were teenagers in school, they might exchange a secret message written in code that only they can understand. Since they both know the secret code, they can both decrypt the message — this process is called symmetric encryption. Sounds straightforward, right?

So, how does this work in real-world applications? Think about it like this: any message is just a sequence of zeros and ones — a binary number. If we modify this number, it turns into a seemingly random string of data, commonly known as ciphertext. The key here is that the transformation is reversible, meaning the original message can be recovered.

To clarify, the reversibility is handled by the logical XOR operation. But don’t worry about that detail — the important part is that with a shared secret key, we can securely mask the original message.

Cryptographic Accumulators

A cryptographic accumulator is a primitive with several advanced properties that can be used to build various zero-knowledge proof systems. Let’s explore the concept, the underlying mathematics, and an example application.

A recent development in this area is that proof verifications can now be implemented in Ethereum smart contracts. Notably, the main type of accumulators is similar to RSA and is based on modular exponentiation, supported since the Byzantium fork (EIP-198).

We can think of a cryptographic accumulator as a supercharged hash function that operates on sets. A standard hash function, like SHA-3, takes a single message and outputs a fixed-size hash. An accumulator, however, takes a set of values and compresses them into a single, constant-size number. In a sense, accumulators are the asymmetric cryptography counterpart to Merkle trees and Bloom filters.

Consider the simplest commit-reveal protocol: Alice has a secret message and publishes its hash, called a commitment. Later, she reveals the whole message to Bob, who can verify that it matches the commitment. If Alice used an accumulator instead of a hash, she could choose to reveal only one, some, or all parts of the message.

Proof of Membership

Accumulators work with sets of values. Later, we'll see examples of encoding data as set memberships. For now, assume Alice turned her message into a set of words and published the associated accumulator (which resembles a hash).

She can select some of the words and produce a proof, which is another constant-size number. This proof allows Bob to verify the integrity of the revealed words, confirming that they belong to the committed set. However, Bob does not learn anything about the other parts that were kept secret—this property is known as zero-knowledge.

Proof of Nonmembership

Interestingly, the opposite operation is also possible: Alice can prove to Bob that some words were not part of the committed set.

For example, Bob asks whether the first word was "cat" or perhaps "dog." Alice can provide proof that it was neither, and Bob can verify this. Yet, Bob still has no clue about what the actual word could be.

This is a unique property. Compare this with hash functions and Merkle trees: a hash of a value is not zero-knowledge—one can take any guess and check its hash. Or the value is protected by an unguessable salt, in which case one cannot prove the non-equality or nonmembership of a particular guess.

Accumulators resolve this paradox. Note that this type of proof does grow in size with the amount of data needed to disprove something.

The Mathematics

There are many variants of accumulators and formal studies on them. Let’s focus on one based on RSA. I’ll assume some familiarity with RSA (you can check Wikipedia for a primer) and present the basic ideas.

The first idea is to work with sets by computing the product of all values in a set. If we map the input data to prime numbers, their product will uniquely represent the set. Otherwise, there could be confusion: {2, 6} would give the same product (12) as {3, 4}. Sets will be written with curly braces like {x} and their product with capital letters like X.

Let’s pick a modulus N (the product of two large primes) and a generator G (any other prime). We’ll come back to this below.

For a set of secret values {u} and their product U, the accumulator C is computed by modular exponentiation. C is a number roughly the same size as N.

C = GU mod N

Next, let’s take a subset {r} of values from {u} to be revealed. To compute a proof, we actually need all the other values of {u} that remain secret, noted as {s}. In product form, we have R × S = U. The proof P is:

P = GS mod N

Then Alice reveals {r} and P to Bob. He will compute C' and verify that it equals the commitment C:

C' = PR mod N

By replacing P, we see that C' must equal C:

C' = G(S × R) = GU mod N

The system relies on the same assumptions as RSA:

• The hardness of the discrete logarithm (Bob finding U from C, or S from P)
• The RSA problem (Alice forging a false proof P)
• The hardness of integer factorization (finding the factors of N)

This also assumes that S is very large; otherwise, Bob could brute-force it. To prevent this, Alice can add a large random prime into {u}, which we could call a salt.

Proofs of non-memberships are a bit trickier, but here's the idea: take a set {x} that contains some elements not in the committed {u}, in addition to those that are (the set {r} above). The GCD (greatest common divisor) of X and U will be R. Alice will use the extended Euclidean algorithm to provide the coefficients that allow Bob to verify this fact.

Trusted Setup

A drawback of this system is that it requires the modulus N to be the product of two primes, but Alice must not know those factors. There are two approaches to this:

• Bob can generate N and ask Alice to make her proofs with it, and he will trust them. But Bob can use his factors to forge accumulators and proofs, so others will not trust them, and Alice has deniability.
• For public use, we need a trusted setup. This means that a computer must generate N from random factors and forget the factors. If it is believed that no one saved the factors, the system can be trusted.

Why Do We Need Off-Chain Computation?

As blockchain technology continues to evolve, off-chain computation is becoming increasingly crucial for enhancing the performance and scalability of blockchain networks. But why is this shift necessary?

Scalability

Blockchains are great, but they have their limits, especially when it comes to scalability. The decentralized nature of blockchain networks creates inherent challenges, particularly when too many on-chain computations start clogging up the system. Think of on-chain operations as the main stage at a concert—too many people trying to get on stage at once, and the show grinds to a halt. By offloading complex calculations and data storage to off-chain systems, we can keep the show running smoothly. Off-chain computation handles the heavy lifting, letting the blockchain focus on what it does best: secure, decentralized transaction validation. It’s like having a backstage crew working behind the scenes to ensure the performance goes off without a hitch.

Cost Efficiency

Let’s face it—on-chain transactions can get expensive, especially when the network is busy. It’s like trying to catch an Uber during surge pricing; the cost can skyrocket when everyone’s trying to use the service at once. Off-chain computation, however, offers a budget-friendly alternative. By taking care of the computational heavy lifting off-chain, developers can significantly reduce the gas fees associated with executing smart contracts. This makes blockchain applications not just scalable, but also more economically viable, especially for businesses watching their bottom line.

Enhanced Functionality

Not all data is created equal, and not all data belongs on the blockchain. Some applications require access to large volumes of data or need to perform real-time analysis—tasks that are just too heavy for the blockchain alone. Off-chain computation steps in here, enabling smart contracts to handle more complex, sophisticated tasks. Whether it’s crunching numbers for financial derivatives or running predictive analytics, off-chain resources open up a world of possibilities for what blockchain applications can do.

Privacy and Security

Privacy matters, especially when dealing with sensitive data. You wouldn’t want your private emails broadcasted on a public billboard, so why would you store sensitive data on a public blockchain? Off-chain computation offers a secure alternative, processing data in environments where privacy can be maintained. With tools like zero-knowledge proofs (zk-proofs), it’s possible to verify computations without exposing the underlying data, ensuring compliance with privacy regulations like GDPR. It’s like having a secret vault where your sensitive information is safe, but still accessible when you need to prove it’s there.

Flexibility and Interoperability

In today’s interconnected world, no blockchain is an island. Off-chain computation makes it easier for different blockchain systems, and even traditional databases, to talk to each other. By using decentralized oracles, off-chain data can be pulled into the blockchain, allowing for more complex and meaningful interactions across various platforms. This flexibility is key for integrating blockchain technology into existing business processes, making it not just a cool new tool, but a practical one too.

In short, off-chain computation isn’t just a nice-to-have—it’s a must-have for tackling the challenges of scalability, cost, functionality, privacy, and interoperability in blockchain networks. By shifting some of the workload off-chain, we can unlock the full potential of blockchain technology, paving the way for wider adoption across various industries.

What on Earth is Zero-Knowledge Proofs?

Zero-knowledge proofs (ZKPs) sound like something straight out of a sci-fi movie, but they're a fascinating and powerful concept in cryptography. In essence, a zero-knowledge proof allows one party (the prover) to prove to another party (the verifier) that they know a specific piece of information without revealing what that information is. It’s like showing someone you know the password to a secret door without ever saying the password itself.

Imagine you want to prove to a friend that you can solve a particular puzzle, but you don’t want to give away the solution. A zero-knowledge proof is a way to convince your friend that you can indeed solve the puzzle, without them ever knowing how you did it.

How Do ZKPs Work?

The magic behind zero-knowledge proofs lies in a few core properties:

• Completeness: If the statement is true and the prover follows the protocol, the verifier will be convinced.
• Soundness: If the statement is false, no dishonest prover can convince the verifier that it’s true, except with some negligible probability.
• Zero-Knowledge: If the statement is true, the verifier learns nothing other than the fact that the statement is true.

Let’s take an example from everyday life. Say you’re colorblind and your friend isn’t. You have two balls that look identical to you, but your friend says they are different colors. How can your friend prove they’re different without showing you the colors?

Here’s the idea: Your friend can show you one ball and then hide it behind their back, randomly swapping the balls or not. They then show you the ball again and ask if it’s the same one or the other one. If you can’t tell the difference, you’ll guess right only half the time. But if your friend repeats this many times and you still guess right every time, they’ve convinced you that the balls are indeed different, without ever revealing which is which. This is a very simplified version of how zero-knowledge proofs work.

Want to learn more? Stay tuned to Web3Citizen! 😊

References

• MIT - Number Theory in Cryptography
• Zero Knowledge Podcast
• ZK-Learning Platform
• ZK Hack - Whiteboard Sessions
• Matter Labs - Awesome Zero-Knowledge Proofs
• How to Create a Zero-Knowledge Dapp - Hashnode Blog
• Stanford - Zero-Knowledge Proofs Notes