Optimizing Big Integer Multiplication on Bitcoin: Introducing w-windowed Approach

Dmytro Zakharov; Oleksandr Kurbatov; Manish Bista; Belove Bist

Paper 2024/1236

Optimizing Big Integer Multiplication on Bitcoin: Introducing w-windowed Approach

Dmytro Zakharov

, Distributed Lab

Oleksandr Kurbatov

, Distributed Lab

Manish Bista, Alpen Labs

Belove Bist, Alpen Labs

Abstract

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 not 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 solely but in more general arithmetic problems.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: Bitcoin Bitcoin Script Fast Multiplication Elliptic Curves Scalar Multiplication BitVM
Contact author(s): dmytro zakharov @ distributedlab com
ok @ distributedlab com
manish @ alpenlabs io
belove @ alpenlabs io
History: 2024-08-05: approved; 2024-08-03: received; See all versions
Short URL: https://ia.cr/2024/1236
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1236,
      author = {Dmytro Zakharov and Oleksandr Kurbatov and Manish Bista and Belove Bist},
      title = {Optimizing Big Integer Multiplication on Bitcoin: Introducing w-windowed Approach},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1236},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/1236}},
      url = {https://eprint.iacr.org/2024/1236}
}