Paper 2024/1236
Optimizing Big Integer Multiplication on Bitcoin: Introducing w-windowed Approach
, Distributed Lab, Distributed LabAbstract
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
- BitcoinBitcoin ScriptFast MultiplicationElliptic CurvesScalar MultiplicationBitVM
- 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},
url = {https://eprint.iacr.org/2024/1236}
}
