Paper 2024/1236 Original: eprint.iacr.org/2024/1236 ↗
Optimizing Big Integer Multiplication on Bitcoin: Introducing w-windowed Approach
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.
- History
- 2024-08-03: last updated
- 2024-08-03: published
- Short URL
- https://ia.cr/2024/1236
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}