Grand Sums Study

This repository is a study about the grand-sum usage in multiset equality arguments proposed by Ulrich Haböck in the multivariate setting and adapted by Héctor Masip / Polygon zkEvm to the univariate setting. It explores the concept and implementation of grand-sums instead of grand-products.

To be able to compare the performance of grand-sums and grand-products, we have implemented both. The grand-product protocol is described here. The grand-sum protocol is described here.

⚠️ Warning: This Repository is for Study Purposes Only! ⚠️

Please note that this repository is intended for study and experimental purposes. It is not meant to be used in a production environment. The code provided here may not have undergone thorough testing, and it may contain bugs or security vulnerabilities.

Overview

The purpose of this study is to analyze and understand the grand-sums concept proposed by Héctor Masip. It provides an implementation of grand sums in JavaScript, allowing developers to explore and experiment with the concept.

Contents

The repository contains the following files:

• grand-sums.js: The JavaScript file containing the implementation of the grand-sums concept.
• example.js: An example usage of the grand-sums implementation.
• LICENSE: The license file specifying the terms of use for this repository.

Usage

Before running the tests, you need to create a tmp folder in the root of the repository. Then, you need to download the powersOfTau28_hez_final_11.ptau file from this link and place it in the tmp folder.

TODO List

• Update comments and loggers to the more general setting.
• Benchmarking: Compare grand-product vs. grand-sum (either single ones or multiple ones).
• Implement NTT-based polynomial arithmetic to be able to operate over the coefficients. Also $O(n\log(n))$ vs $O(n^2)$.
• Fix the edge case where nBits = 1.
• Generalize the API/protocol to run in the case of a vector arguments.
• Generalize the API/protocol to run in the case of selected vector arguments.
• Generalize the API/protocol to run in the case of multiple arguments (of any kind) at the same time.
• Implement lookups.
• Finish index.js to make it usable from the outside.

License

This study is released under the MIT License. Please review the license file for more details.