Paper 2021/1292

Fast Extended GCD Calculation for Large Integers for Verifiable Delay Functions

Kavya Sreedhar and Mark Horowitz and Christopher Torng

Abstract

The verifiable delay function (VDF) is a cryptographic primitive that requires a fixed amount of time for evaluation but is still efficiently verifiable. VDFs have been considered a promising candidate for the core function for blockchain systems given these fast verification but slow evaluation properties. NUDUPL is a state-of-the-art algorithm for VDFs and revolves around a core computation involving squaring within class groups of binary quadratic forms. While prior work has focused on fast software implementations for this squaring, few papers have investigated hardware acceleration, and no prior works accelerate the NUDUPL algorithm in particular. Since the most time-consuming operation in the NUDUPL algorithm is an extended GCD calculation, we present an efficient design and implementation to accelerate this computation. We conduct a detailed study of the hardware design space and build an ASIC implementation for 1024-bit integers in an open-source 180nm-130nm hybrid technology (SKY130). Our design runs with a 3ns cycle time and takes an average of 3.7us per computation. After normalizing technologies for comparison, we achieve a VDF squaring speedup of 10X compared to the only prior class-group-based VDF accelerator and 4X compared to the Chia Network's software implementation, the highest speedup possible by accelerating only the GCD. We sped up the extended GCD calculation by 14X compared to the hardware implementation and 38X compared to the software. We make our entire codebase publicly available as part of our tapeout with the Efabless Open MPW2 shuttle sponsored by Google.