Open Access

ARTICLE

Polynomial Commitment in a Verkle Tree Based on a Non-Positional Polynomial Notation

Kunbolat T. Algazy¹, Kairat S. Sakan^1,2,*, Saule E. Nyssanbayeva^1,2, Ardabek Khompysh^1,3

1 Information Security Laboratory, Institute of Information and Computational Technologies, Almaty, 050010, Kazakhstan
2 Faculty of Information Technology, Al-Farabi Kazakh National University, Almaty, 050040, Kazakhstan
3 Faculty of Languages and Humanities, Nur-Mubarak University, Almaty, 050040, Kazakhstan

* Corresponding Author: Kairat S. Sakan. Email:

Computers, Materials & Continua 2025, 84(1), 1581-1595. https://doi.org/10.32604/cmc.2025.065085

Received 03 March 2025; Accepted 24 April 2025; Issue published 09 June 2025

Abstract

This paper examines the application of the Verkle tree—an efficient data structure that leverages commitments and a novel proof technique in cryptographic solutions. Unlike traditional Merkle trees, the Verkle tree significantly reduces signature size by utilizing polynomial and vector commitments. Compact proofs also accelerate the verification process, reducing computational overhead, which makes Verkle trees particularly useful. The study proposes a new approach based on a non-positional polynomial notation (NPN) employing the Chinese Remainder Theorem (CRT). CRT enables efficient data representation and verification by decomposing data into smaller, independent components, simplifying computations, reducing overhead, and enhancing scalability. This technique facilitates parallel data processing, which is especially advantageous in cryptographic applications such as commitment and proof construction in Verkle trees, as well as in systems with constrained computational resources. Theoretical foundations of the approach, its advantages, and practical implementation aspects are explored, including resistance to potential attacks, application domains, and a comparative analysis with existing methods based on well-known parameters and characteristics. An analysis of potential attacks and vulnerabilities, including greatest common divisor (GCD) attacks, approximate multiple attacks (LLL lattice-based), brute-force search for irreducible polynomials, and the estimation of their total number, indicates that no vulnerabilities have been identified in the proposed method thus far. Furthermore, the study demonstrates that integrating CRT with Verkle trees ensures high scalability, making this approach promising for blockchain systems and other distributed systems requiring compact and efficient proofs.

---

Keywords

---