Accelerating Additive NTT Calculations Using GPUs
Advisor: Aaron Glanzer
Internship Location: Mason Department of Cyber Security Engineering
Onsite Mentor: Tanvir Arafin
The scalability and privacy of modern blockchain technologies rely on Zero-Knowledge Proofs (ZKPs), which are protocols that allow a prover to verify the truth of a statement while revealing as little information as possible about the statement. Currently, the mathematics used for these proofs rely on Elliptic Curve Cryptography (ECC), the industry standard for the security of the modern internet. However, ECC can be broken using Shor’s Algorithm, an algorithm that can only be run on quantum computers. This makes quantum computing, which is expected to become widespread in the 2030s, a threat to modern internet security. Anticipating this threat, cryptographers have come up with different protocols that do not need ECC. One such protocol is BINIUS, a proof system that operates over binary fields rather than the large prime fields used in ECC. However, the practical speed of BINIUS is currently by its reliance on the computationally expensive Additive Number Theoretic Transform (ANTT). By optimizing memory access patterns and exploiting the parallelism of GPUs, this project aims to find if hardware-aware optimizations on GPUs can significantly speed up the state-of-the-art implementation of the ANTT.
Project Blog
Week 0: Introduction!
Currently, I am working with Dr. Arafin at George Mason University (GMU), and my research project focuses on optimizing encryption programs for use on GPUSs in order to allow for encryption that can withstand quantum computing without requiring too much processing power. More specifically, by optimizing memory access patterns and exploiting the parallelism of GPUs, this project aims to answer the following research question: Can hardware-aware optimizations on GPUs significantly speed up the state-of-the-art implementation of the ANTT?
The scalability and privacy of modern blockchain technologies rely on Zero-Knowledge Proofs (ZKPs). However, these ECC-based proofs face an existential threat with the rapid advancement of quantum computing. Anticipating the threat of quantum computers, cryptographers have come up with different protocols that do not rely on ECC. One such protocol is BINIUS, a proof system that operates over binary fields rather than the large prime fields used in ECC. BINIUS offers the advantages of being post-quantum secure and also leveraging the native binary architecture of modern CPUs and GPUs, theoretically offering faster proof generation in comparison to ECC. However, the practical speed of BINIUS is currently constrained by the Polynomial Commitment Scheme (PCS), which relies on the Additive Number Theoretic Transform (ANTT), the most computationally expensive part of the BINIUS proof system. By accelerating the ANTT, this research directly contributes to post-quantum cryptographic protocols. By optimizing these kernels for a wider range of hardware, the hardware barrier to entry can be lowered, making it less expensive for people to join the blockchain and contribute computation for proofs.
Week 1: Understanding The Zerocheck Protocol
As part of my ongoing research, I spend a lot of time researching how to optimize post-quantum cryptography for GPU acceleration. Although our focus is on accelerating the Additive Number Theoretic Transform (ANTT) at a hardware level, I have had to grasp the high-level math behind it. Recently, I have been studying the math behind the BINIUS proof system’s zerocheck protocol. A traditional Zero-Knowledge Proof system is based on Elliptic Curve Cryptography (ECC), which is highly vulnerable to future quantum computers. However, BINIUS is not only secure against future quantum computers but also very efficient on current hardware because it only needs bitwise XOR operations for addition and doesn't require operations over large prime fields.
Part of the zerocheck scheme is the Polynomial Interactive Oracle Proof (PIOP) layer. When a program is converted into math, its execution is encoded into a multilinear polynomial. The PIOP framework is used to combine all computational rules into a single global constraint polynomial. If this polynomial evaluates to exactly zero, the zerocheck ensures that no computational constraints are violated across a Boolean hypercube.
Checking every vertex on this hypercube is computationally impossible for large programs. BINIUS handles this bottleneck by reducing the zerocheck to a sumcheck protocol. Instead of checking millions of individual points, this interactive protocol compresses the workload down to a single evaluation at a random coordinate. By the Schwartz-Zippel Lemma, if this single random evaluation checks out as zero, the probability of a false positive is overwhelmingly small.
Week 2: Understanding The Sumcheck Protocol
Sumcheck
Sumcheck is an interactive protocol where a prover convinces a verifier that a multivariate polynomial has hypercube evaluations that sum up to S. Since we are using Sumcheck for Zerocheck, S = 0. This protocol proceeds over n rounds.
The prover first computes a univariate "round" polynomial, Rₖ(X), defined by:
Rₖ(X) = ∑ (for v ∈ {0,1}ⁿ⁻ᵏ⁻¹) D(r'₀, ..., r'ₖ₋₁, X, v₀, ..., vₙ₋ₖ₋₂).
After that, the verifier checks if Rₖ(0) + Rₖ(1) = Sₖ. Initially, S₀ = S. If the verification is passed, then the protocol proceeds to the next round.
To transition to round k+1, the verifier sets Sₖ₊₁ = Rₖ(r'ₖ) and sends a new random challenge r'ₖ₊₁ to the prover.
If the prover passes all n rounds, the verifier can be confident that the multivariate polynomial sums up to S on the hypercube.
Security
The security of the Sumcheck protocol relies on the mathematical guarantee that a cheating prover cannot convince the verifier of a false claim. This guarantee is based on the Schwartz-Zippel lemma.
Suppose a prover wants to cheat and provide a fake polynomial. In the first round, the cheating prover is forced to invent and send a fake polynomial R'₀(X) of degree d that satisfies R'₀(0) + R'₀(1) = S₀.
After the prover commits to this fake polynomial, the verifier samples a random challenge r'₀ from a large finite field F. The target for the next round is set to S₁ = R'₀(r'₀). For the prover to lie successfully and continue with the protocol, the fake polynomial must intersect the true polynomial at this exact random point, meaning R'₀(r'₀) = R₀(r'₀).
However, the Schwartz-Zippel Lemma states that two distinct polynomials of degree d can intersect at a maximum of d points. Since the verifier selects r'₀ randomly from the entire field F, the probability of accidentally picking an intersection point is very low:
Pr[R'ₖ(r'ₖ) = Rₖ(r'ₖ)] ≤ d / |F|
Because the protocol runs for n rounds, the probability that the prover succeeds is thus:
Pr[False Proof] ≤ (n · d) / |F|
Since we will use a very large field (e.g. F over 2²⁵⁶), it is extremely unlikely that the prover is able to fake a proof. Thus, we can be confident in the security of this protocol.
Week 3: GPU Programming and Parallelization
As part of my ongoing research project, I have been spending a lot of time looking for ways to optimize the performance of advanced cryptography for GPU acceleration. While our main area of interest is the acceleration of the Additive Number Theoretic Transform (ANTT) in hardware, the architecture of parallel computing is just as important. In the last few weeks, I have been looking into the way in which Graphics Processing Units (GPUs) fundamentally change the way in which calculations are carried out. A normal processor or CPU is designed to handle complex tasks quickly, though only a few at a time. A GPU, on the other hand, is designed for parallelization, with thousands of cores working together to perform simpler calculations.
The BINIUS proof system includes the ANTT, which is a complex mathematical operation required to perform calculations on massive polynomial equations. When a computational constraint is encountered, the operation required to resolve the constraint involves the execution of millions of individual arithmetic operations. While the execution of these operations is complex, the fact that they must be carried out sequentially on a normal CPU creates a bottleneck in the system. While the execution of every operation individually is computationally not possible for the complex calculations required in the BINIUS proof system, the solution to the bottleneck is the way in which GPU programming works. By restructuring the ANTT to include parallelization, the calculations required to execute the individual operations of the proof system are carried out in parallel. This effectively compresses the execution time of the operation by a great degree. By ensuring the parallelization is optimized, the hardware acceleration ensures the BINIUS system is not only secure against quantum threats in the future but also highly efficient.
Week 4: Memory Coalescing
In working towards speeding up the ANTT, I've had to face some major obstacles when programming GPUs. One of the most significant is memory access patterns.
It turns out, despite the fact that GPUs allow for massive parallelization to quickly execute the ANTT computations, there is a drawback to using GPUs. Namely, if a GPU has a lot of threads executing computations, how do you transfer data to these threads fast enough so that you minimize the number of idle threads?
The answer lies in a technique known as memory coalescing. In a GPU, each group of threads, referred to as "warps," requests some information from the global memory. Now, when a GPU requests memory, it does not just grab one variable at a time. Rather, it gets large blocks of data from the global memory, as accessing only one variable at a time would be inefficient. If our threads request memory addresses that are scattered randomly across the board, the GPU has to perform multiple, slow transactions to get all threads the data they need. However, if we align our code so that adjacent threads access sequential memory addresses, the hardware can "coalesce" those requests into a single, highly efficient transaction.
For a computationally intensive algorithm like ANTT, it is important to optimize every aspect of our implementation so we save as much time as possible. By carefully choosing how our threads access data from the global memory, we end up saving a lot of time by ensuring our GPU threads are always busy.
Week 5: The Difficulty of Parallelizing Recursion
Recursion is a powerful technique for tackling tough problems through the implementation of a process that calls itself - i.e. breaks down a problem by dividing it into smaller, more easily executable tasks. The FFT, which happens to be the mathematical sister of the ANTT, is traditionally implemented via recursion. It works brilliantly at dividing a large polynomial into two parts, dealing with each of those and combining them again. Using a standard CPU, recursion does the job without any trouble.
Not so much with GPUs.
Let's take a closer look at the problem of memory. Every time a recursive function is called on a computer, the current data is stored in special memory called the "stack". CPUs are equipped with enormous stacks, allowing them to deal with recursion without any issue. However, GPUs gain phenomenal processing speeds due to their ability to run multiple threads concurrently. Since when we try and parallelize recursion, and all the threads try to build their respective stacks, the localized memory in the GPU will get overloaded immediately, resulting in either a bottleneck or crash.
To allow our program to harness the power of the GPU hardware, we have to completely break away from recursion. We don't allow the algorithm to call itself anymore but rewrite it into an iteration. That means unrolling the mathematics of the operation into a simple, bottom-up loop process called a butterfly network. Iteration eliminates the need for stack memory and allows for the mapping of the procedure onto the concurrent threads of the GPU while allowing for the recursive ANTT structure to be preserved.
Week 6: What are Zero Knowledge Proofs?
Imagine a ring-shaped cave with a single entry point dividing into paths A and B. Somewhere deep in there, there is a magic door connecting the paths that opens whenever someone utters a secret password.
Assume that I need to prove to you that I know that password but cannot reveal it under any circumstances. How can we achieve it?
First, you go out of the way while I enter the cave and randomly select one of two possible paths. You then approach the entry point and shout a random request: "Exit from path B!". If indeed I know the secret password, then opening the door becomes easy for me. As long as I am able to leave the cave through the requested path in each round of our experiment, after twenty tries you become completely convinced of this fact and still remain clueless about the word. This is how the well-known Ali Baba Cave works.
And it turns out that the same technique of proving knowledge of passwords without disclosing any private data is widely used in modern cryptography to verify user data. Such proofs are known as Zero-Knowledge Proofs (ZKP).
Week 7: Abstract Algebra and ANTT
Writing CUDA kernels for post-quantum protocols like BINIUS requires composing hardware instructions using only math. The basis of mathematics starts from two different types of algebraic structures known as rings and fields, where ring elements support addition, subtraction, and multiplication while their division is well-defined for all non-zero members of the field. One thing that stands out regarding the use of cryptography compared to other branches of computing is the ability to operate with finite fields that have specific sizes and cannot be rounded off and thereby guarantee the required mathematical precision for proving Zero-Knowledge Protocols. As for the cases where a finite field of zeros and ones will not provide sufficient security, its extension is very important. For this purpose, extension fields are required to be constructed from quotient rings by dividing polynomial rings by an irreducible polynomial (i.e., equivalent to a prime number).
More precisely, the above mentioned approach proves to be useful when designing efficient hardware solutions, thus providing significant performance improvements. Namely, the protocol of BINIUS runs in the environment of characteristic-2 binary extension fields, allowing for perfect correspondence between mathematical abstraction and typical GPU architecture. Taking this fact into account, field additions can be replaced with bitwise XOR operations while carrying out optimized carry-less multiplications on the GPU. Furthermore, ANTTs in such fields lead to fast polynomial multiplication whenever vector operations are coalesced into memory space.
Week 8: Measuring The Execution Time of a Program
As you know from my past blogs, the goal of my project is to develop an ultra-fast implementation of an advanced mathematics algorithm – Additive NTT with the usage of a graphics processing unit (GPU).
But if our goal is optimization, how do we measure the time it takes for a program to run? There are many different ways to do this in the computer world, but there is one specific way to measure time accurately in order to find bottlenecks in such a complex system. There are three components we need to consider:
1. To measure the time it takes to do the calculations, we need to use CUDA events. It measures the execution time of the program exclusively on the GPU.
2. The time it takes for the data to be transferred from the GPU to the CPU, and vice versa. This should be measured separately, since the speed of calculations is worthless if the time of data transfer is too high! This allows us to know if the time taken to transfer data is too large.
3. The last thing we need is a profiler called Nsight Systems. It will give us a detailed analysis and tell us where the slowest parts of our program are.
Week 10: Countering Runtime Variance
As we were making progress with our implementation of hardware acceleration of the Additive Number Theoretic Transform (ANTT) for the BINIUS proof system, we faced a very common issue in GPU programming – execution time variance. Despite achieving excellent peak performance with our CUDA implementations, we had trouble achieving consistent execution times.
Variance issues are known to occur in high-speed cryptographic systems frequently. In GPU architectures, the source of variance may lie in minor differences in memory access patterns or even in warp divergence leading to diverging thread blocks.
This week I was actively profiling our kernels to find potential hardware bottlenecks. Through careful optimization of our memory access patterns and using the L1 and L2 memory efficiently, we managed to achieve more consistent execution times. This is a very thorough process involving a lot of tweaking parameters and fine tuning. But now, our performance graphs look amazing.