OPTIMIZING BIG INTEGER MULTIPLICATION ON BITCOIN:INTRODUCING W-WINDOWED APPROACH

A crucial component of any zero-knowledge system is operations with finite fields. This, in turn, leads to the implementation of the fundamental operation: multiplying two big integers. In the realm of Bitcoin, this problem gets revisited, as Bitcoin utilizes its own stack-based and Turing-complete scripting system called Bitcoin Script. Inspired by Elliptic Curve scalar multiplication, this paper introduces the w-windowed method for multiplying two numbers. We outperform state-of-the-art approaches, including BitVM’s implementation. Finally, we also show how the windowed method can lead to optimizations not only in big integer arithmetic but in more general arithmetic problems.