# Grant Summary on Accelerating MSM on Mobile with GPUs

Improving the efficiency of zero-knowledge proofs (ZKPs) is crucial for enhancing privacy and scalability in privacy-preserving applications. [Mopro-22 Grant](https://hackmd.io/@moven0831/mopro-22-improving-msm) focuses on leveraging GPU acceleration to boost the performance of multi-scalar multiplication (MSM) on mobile devices.

This blog post summarizes the progress and future plans to enhance proving speed using GPUs on mobile phones, aimed at enthusiasts and professionals interested in cryptographic optimizations.

## Background and Context

### Understanding MSM and Its Importance

Multi-Scalar Multiplication (MSM) is a fundamental operation in various cryptographic protocols, particularly pairing-based zk-SNARKs like Groth16. Efficient MSM performance is essential for the scalability and responsiveness of these systems. However, executing MSM on mobile devices presents significant challenges due to the limited computational power of mobile CPUs.

### GPU Acceleration

Graphics Processing Units (GPUs) offer parallel processing capabilities that can handle multiple computations simultaneously. Leveraging GPUs for MSM operations presents a promising solution to overcome the performance limitations of mobile CPUs.

### Related Work

Our approach builds upon existing efforts such as the [Zprize 2022 MSM on Mobile Acceleration](https://github.com/z-prize/2022-entries/tree/main/open-division/prize7-msm-mobile), [Lambdaworks Metal MSM](https://github.com/lambdaclass/lambdaworks), and utilizes [Arkworks](https://github.com/arkworks-rs) for cryptographic primitives.

## Project Overview

### Objectives

- **Integrate MSM Algorithms:** Incorporate various MSM implementations into the Mopro framework.
- **Benchmark Performance:** Compare MSM performance against existing solutions using Arkworks as a baseline.
- **Optimize for Mobile GPUs:** Utilize Apple's Metal API to tailor MSM algorithms for mobile GPU architectures.
- **Documentation:** Provide comprehensive guides for enabling GPU acceleration in the proving process on mobile devices.

### Methodology

Our approach involves integrating MSM algorithms into Mopro, conducting extensive benchmarks on both simulators and real devices, optimizing these algorithms using the Metal API, and iteratively addressing performance bottlenecks.

<figure align="center">
<a href="https://hackmd.io/_uploads/S1mEaZuRC.png">
<img src="https://hackmd.io/_uploads/S1mEaZuRC.png" alt="High Latency"/>
<br>
</a>
<center><em>GPU Channels of Metal MSM</em></center>
</figure>

## Milestone Progress Reports

### [Milestone 1: Integration and Benchmarking](#Associated-Reports-to-This-Grant)

**Objectives:**
Integrate Zprize MSM works into Mopro and establish Arkworks Pippenger MSM as a baseline.

**Achievements:**
- Successfully integrated TrapdoorTech’s MSM.
- Adapted benchmarking methods and conducted initial performance comparisons.

### [Milestone 2: GPU Acceleration with Metal API](#Associated-Reports-to-This-Grant)

**Objectives:**
Explore GPU acceleration using Metal, integrate Halo2curve MSM, and build GPU exploration examples.

**Achievements:**
- Implemented Metal shaders and benchmarked different curves (BN254 vs BLS12-377).
- Migrated Lambdaworks’ Metal shaders.
- Identified performance bottlenecks in the accumulation phase and optimized parallel computation strategies.

**Challenges:**
- Faced GPU hang errors on larger MSM instances.
- Compatibility issues with Metal-rs, resolved by switching to the updated `metal` crate.

**Next Steps:**
Refine Metal implementations and address GPU stability on mobile devices.

### [Milestone 3: Advanced Optimization and Parallelism](#Associated-Reports-to-This-Grant)

**Objectives:**
Enhance parallelism in MSM algorithms, implement bucket-wise MSM, and leverage precomputation techniques.

**Achievements:**
- Transitioned to bucket-wise MSM to maximize GPU parallelism.
- Conducted extensive benchmarking on Apple M3 chips, extracting more parallelism suitable for GPU computation.

**Challenges:**
- GPU hang errors persisted for larger instances.
- Incompatibility with Metal’s built-in sort functions, leading to the use of CPU-based sorting.

**Next Steps:**
Continue optimizing accumulation phases and explore alternative sorting mechanisms.

### [Milestone 4: Final Benchmarking and Integration](#Associated-Reports-to-This-Grant)

**Objectives:**
Benchmark all MSM implementations on real iOS devices, refactor MSM into a standalone crate, and prepare for integration into proving systems.

**Achievements:**
- Completed extensive benchmarks showing similar trends to simulators and laptops.
- Isolated MSM code into a standalone crate for easier integration.
- Identified GPU accumulation as the primary performance bottleneck.

**Challenges:**
- GPU hang errors on real devices and limitations in Metal’s built-in sort functions.
- Precompute MSM scalability issues for larger instances.

**Next Steps:**
Integrate GPU-acceleration crate into proving systems, support curve-specific MSM algorithms, and continue mobile GPU optimization.

## Benchmarking MSM Algorithms on iOS Devices

Detailed information for the testing device.

<figure align="center">
<a href="https://hackmd.io/_uploads/ryqXX-OKC.jpg">
<img src="https://hackmd.io/_uploads/ryqXX-OKC.jpg" alt="Testing Device Info"/>
<br>
</a>
<center><em>Testing Device Info</em></center>
</figure>

> [hardware reference](https://www.gsmarena.com/apple_iphone_14_pro-11860.php)

* Phone type: IPhone 14 pro
* ChipSet: Apple A16 Bionic (4nm)
* CPU: Hexa-core (2x3.46 GHz Everest + 4x2.02 GHz Sawtooth)
* GPU: Apple GPU (5-core graphics)
* Memory: 6GB RAM

### Methodology
<!-- e.g. Device Setup, Benchmarking Process, Metrics -->
The unit for all column is ms.

| Instance Size | arkwork (baseline) | Metal (GPU) | Bucket Wise Msm | Precompute Msm | result(screen shot) |
| ------------- | ------------------ | ---------------- | ------------------ | ------------------ | ---------------------------------------- |
| 2^10 | 11.29 | 21.31 (-88.66%) | 80.54 (-613.07%) | 25.57 (-126.41%) | [](https://imgur.com/tzjjEgQ.png)<br> |
| 2^12 | 19.34 | 62.85 (-225.00%) | 331.15 (-1612.43%) | 82.93(-328.85%) | [](https://imgur.com/ShdhJaS.png)<br> |
| 2^14 | 53.11 | - | 221.17 (-316.43%) | 265.68 (-400.24%) | [](https://imgur.com/6cx0LwH.png)<br> |
| 2^16 | 198.11 | - | 759.87 (-283.57%) | 888.23 (-348.36) | [](https://imgur.com/LRARN41.png) |
| 2^18 | 707.95 | - | 2938.61 (-315.09%) | 1429.06 (-101.86%) | [](https://imgur.com/XE3BVFV.png)<br> |
| 2^20 | 1902.76 | - | 7341.82 (-285.85%) | - | [](https://imgur.com/oJY6O0T.png)<br> |

### Footnote

When the instance size is larger than $2^{14}$, `MetalMsm` encounters a GPU Hang error. For sizes above $2^{18}$, `precomputeMsm` takes an excessive amount of time generating extended points, which might cause the process of generating the proving key and verification key to be too slow, as indicated in the log below. Additionally, deserialization takes even longer than in `arkwork (baseline)`. Therefore, `precomputeMsm` is not compared for instance sizes $2^{20}$ and $2^{22}$.

**Key Insights:**

- **Memory Management Needs Improvement:** The current Metal MSM implementation encounters GPU hang errors with larger instances, limiting scalability.
- **Bottlenecks:** The accumulation phase in bucket-wise Metal MSM remains the primary performance bottleneck.
- **Precompute MSM:** While offering speedups, precompute MSM introduces substantial I/O overhead, making it unsuitable for larger instances.

## Future Work and Next Steps

> Please refer to [the profiling report](#Associated-Reports-to-This-Grant) for detailed GPU activities of Metal MSM.

To address the critical challenges identified, we will prioritize the following tasks:

1. **Reduce CPU-GPU Latency and Improve Synchronization**
- **Streamline Data Transfers:** Implement batching and asynchronous methods to minimize latency.
- **Enable Concurrent Processing:** Optimize synchronization to allow simultaneous CPU and GPU workloads, enhancing overall throughput.

2. **Resolve GPU Stability Issues for Larger MSM Instances**
- **Fix GPU Hang Errors:** Investigate and eliminate the causes of GPU hangs when handling larger MSM instances.
- **Refine Metal Shaders:** Update and optimize Metal shader code to ensure compatibility and stability across various mobile devices.

3. **Optimize EC Point Conversion Efficiency**
- **Accelerate Encoding:** Develop faster algorithms or alternative data representations to significantly reduce the time spent on converting EC points from 64-bit to 32-bit.

4. **Enhance Parallelism in the Accumulation Phase**
- **Improve Bucket-wise MSM:** Refine parallel computation strategies to speed up the accumulation process.
- **Implement GPU-based Sorting:** Replace CPU-based sorting with GPU-optimized solutions to decrease latency and boost performance.

## Conclusion

**Project Mopro-22** has made substantial strides in accelerating MSM operations on mobile GPUs, laying the groundwork for more efficient cryptographic proofs on the go. While challenges like GPU stability and accumulation optimization remain, our progress opens new avenues for research and development in mobile cryptography. We invite the community to join us in this exciting journey towards faster, more efficient proving systems.

## References and Further Reading

- #### **Associated Reports to This Grant**
- [General Grant Proposal - Mopro-22](/ZL-PmVl7SGq0IBt6mAGC8A)
- [Milestone 1 Report](/ZCxFpQ8AROyYGTl5GLqAGQ)
- [Milestone 2 Report](/YtTVJUArRmWrdvaTza2LGg)
- [Milestone 3 Report](/v8WPAG8-RsCANrbv_seSXw)
- [Milestone 4 Report](/6aYxLgNZTaGG4gbXkZUlCw)
- [Profiling on Metal MSM](https://hackmd.io/@moven0831/profiling-metal-msm)
- [Guide for Extending Custom Functions Through Mopro](https://github.com/zkmopro/gpu-acceleration/blob/main/guide-for-extending-ffi.md)

- #### **GitHub Repositories:**
- [zkmopro/mopro](https://github.com/zkmopro/mopro)
- [zkmopro/gpu-acceleration](https://github.com/zkmopro/gpu-acceleration)
- [Zprize 2022 MSM on Mobile Acceleration](https://github.com/z-prize/2022-entries/tree/main/open-division/prize7-msm-mobile)
- [Ingonyama - Icicle](https://github.com/ingonyama-zk/icicle/blob/main/wrappers/rust/icicle-curves/icicle-bn254/src/msm/mod.rs)

- #### **Technical Articles and Papers:**
- [BeH22: Multi-Scalar Multiplication for SNARKs](https://hackmd.io/@moven0831/BeH22)
- [Optimization Strategies for MSM](https://hackmd.io/@drouyang/msm)
- [Performance Optimization | Metal by Tutorials](https://www.kodeco.com/books/metal-by-tutorials/v2.0/chapters/24-performance-optimization)

- #### **Tools and Frameworks:**
- [Arkworks](https://github.com/arkworks-rs)
- [Metal-rs](https://github.com/gfx-rs/metal-rs)
- [Lambdaworks](https://github.com/lambdaclass/lambdaworks)
- [Halo2curve](https://github.com/privacy-scaling-explorations/halo2curves)

## Acknowledgments

We extend our gratitude to our advisors Oskar and Vivian, and the open-source community for their invaluable support to Mopro-22 Grant.