Dmytro Zakharov¹, Oleksandr Kurbatov¹, Manish Bista² and Belove Bist², ¹Distributed Lab, Ukraine, ²Alpen Labs, USA

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.

Bitcoin, Bitcoin Script, Fast Multiplication, Elliptic Curve Scalar Multiplication, BitVM