ZKP16 Hardware Acceleration of ZKP

Hardware Acceleration of ZKP"/>

ZKP16 Hardware Acceleration of ZKP

ZKP学习笔记

ZK-Learning MOOC课程笔记

Lecture 16: Hardware Acceleration of ZKP (Guest Lecturer: Kelly Olson)

• The What and Why of Hardware Acceleration

  • Hardware acceleration is the use of dedicated hardware to accelerate an operation so that it runs faster and/or more efficiently.
  • Hardware acceleration can involve optimizing functions and code to use existing hardware (COTS) or it may involve the development of new hardware designed for a specific task.
    • COTS (commercially available off-the-shelf) hardware includes CPUs, GPUs, and FPGAS
    • Custom hardware is often referred to as an ASIC
  • Examples
    

• Hardware acceleration for crytpo
  

• Why HW acceleration for ZKP

  • ZK （and non-ZK） proof generation has high overheads relative to native computation

• Goals of HW acceleration for ZKP

  • Throughput: increase the number of operations per system
  • Cost: reduce the cost of operation e.g. Bitcoin mining rigs are designed to reduce capital expenses ($/hash) and operational expenses (watts/hash)
  • Latency: reduce the time of an individual operation e.g. 2kBridges may want to reduce the proof generation time for faster finality

• Key Computational Primitives of ZKP

  • Each proof system, and associated implementation will have slightly different computational requirements.

  • Across a variety of proof systems these are three of the most computationally expensive operations

    • Multiscalar Multiplication (MSM)

      • A ‘dot product’ of elliptic curve points and scalars

      • Easily paralledizable

      • Optimization
        

        • When performing a MSM off of the host device, the scalars and sometimes points must be moved to the accelerator. The available communication bandwidth limits the maximum possible performance of the accelerator.
    • Number Theoretic Transformation (NTT)
      • Common algorithms like Cooley-Tukey reduce complexity from O ( N 2 ) O(N^2) O(N2) to O ( N I o g N ) O(NIogN) O(NIogN)
      • Not Easily paralledizable
      • Furthermore, these elements must be kept in memory to be operated on, imposing high memory requirements
    • Arithmetic Hashes (e.g., Poseidon)

  • SNARK V.S. STARK
    

    • The MSM, NTT and Hashes take 2/3 or more time in the proving system

  • Foundational Primitive: Finite Field Arithmetic (especially ModMul)

• Hardware Resources Required

  • Determining Computational Cost
    

  • Selecting the Right Hardware

    • Given that these workload are driven predominately by modular multiplication, we should look for platforms can perform a large number of multiplications, quickly and cheaply
    • Estimated HW performance can be evaluated by looking at # of hardware multipliers, size of hardware multipliers, and speed/frequency of each instruction
    • Examples
      

  • Two Key Components to HW Acceleration

    • ‘HW friendly’ Algorithm
    • Efficient Implementation

• Limits of Acceleration
  

  • Acceleration Pitfalls
    

  • Production Examples: Filecoin
    

• Current Status of Hardware Acceleration
  

• Future Directions for Hardware Acceleration