update zkp-based Sumcheck Algorithm-Component #572

SaaRaaS-1300 · 2025-09-25T11:06:20Z

add sumcheck protocol and matrix-multiplication-check in examples/zkp

gemini-code-assist · 2025-09-25T11:06:35Z

Summary of Changes

Hello @SaaRaaS-1300, I'm Gemini Code Assist¹! I'm currently reviewing this pull request and will post my feedback shortly. In the meantime, here's a summary to help you and other reviewers quickly get up to speed!

This pull request significantly expands the zero-knowledge proof (ZKP) examples by integrating two fundamental cryptographic primitives: the Sumcheck protocol and a Matrix Multiplication Check. These additions provide essential building blocks for constructing and verifying more complex ZKP systems, enhancing the educational and practical utility of the examples/zkp directory. The changes include core logic, necessary header files, and thorough unit tests to ensure functionality and correctness.

Highlights

Sumcheck Protocol: Introduced a new implementation of the Sumcheck protocol, including SumcheckProver and SumcheckVerifier classes, along with helper functions for polynomial evaluation and random field element generation.
Matrix Multiplication Check: Added a matrix-multiplication-check component, providing functions for mat_mat_multiplication and mat_vec_multiplication within the ZKP examples.
Build System Integration: Updated the BUILD.bazel file to include build rules and tests for both the new sumcheck and matmul_check components, ensuring proper compilation and testing.
Comprehensive Testing: New unit tests have been added for both the sumcheck protocol (covering honest and fraudulent provers) and the matrix-multiplication-check functions, validating their correctness and robustness.

Using Gemini Code Assist

The full guide for Gemini Code Assist can be found on our documentation page, here are some quick tips.

Invoking Gemini

You can request assistance from Gemini at any point by creating a comment using either /gemini <command> or @gemini-code-assist <command>. Below is a summary of the supported commands on the current page.

Feature	Command	Description
Code Review	`/gemini review`	Performs a code review for the current pull request in its current state.
Pull Request Summary	`/gemini summary`	Provides a summary of the current pull request in its current state.
Comment	@gemini-code-assist	Responds in comments when explicitly tagged, both in pull request comments and review comments.
Help	`/gemini help`	Displays a list of available commands.

Customization

To customize Gemini Code Assist for GitHub experience, repository maintainers can create a configuration file and/or provide a custom code review style guide (such as PEP-8 for Python) by creating and adding files to a .gemini/ folder in the base of the repository. Detailed instructions can be found here.

Limitations & Feedback

Gemini Code Assist may make mistakes. Please leave feedback on any instances where its feedback is incorrect or counter productive. You can react with 👍 and 👎 on @gemini-code-assist comments. If you're interested in giving your feedback about your experience with Gemini Code Assist for Github and other Google products, sign up here.

You can also get AI-powered code generation, chat, as well as code reviews directly in the IDE at no cost with the Gemini Code Assist IDE Extension.

Review the Privacy Notices, Generative AI Prohibited Use Policy, Terms of Service, and learn how to configure Gemini Code Assist in GitHub here. Gemini can make mistakes, so double check it and use code with caution. ↩

github-actions · 2025-09-25T11:06:36Z

All contributors have signed the CLA ✍️ ✅
_{Posted by the CLA Assistant Lite bot.}

gemini-code-assist

Code Review

This pull request introduces a sumcheck protocol and a matrix multiplication check, which are valuable additions for zero-knowledge proof examples. The implementation is mostly correct and well-structured. My review focuses on improving code quality, maintainability, and performance. Key suggestions include removing unnecessary dependencies and includes, refactoring duplicated code into helper functions, fixing a bug in random number generation, and optimizing polynomial evaluation and vector operations. The tests are a good start and cover basic honest and fraudulent scenarios.

gemini-code-assist · 2025-09-25T11:08:45Z

examples/zkp/sumcheck/sumcheck.cc

+}
+
+FieldElem RandFieldElem(const FieldElem& modulus) {
+  const size_t num_bytes = modulus.BitCount();


modulus.BitCount() returns the number of bits in the modulus, not the number of bytes. Using this value directly as the length for SecureRandBytes generates far more random data than necessary, which is inefficient. You should calculate the number of bytes by dividing the bit count by 8 and rounding up.

const size_t num_bytes = (modulus.BitCount() + 7) / 8;

examples/zkp/BUILD.bazel

gemini-code-assist · 2025-09-25T11:08:45Z

examples/zkp/sumcheck/matmul_check.cc

+
+#include "yacl/base/exception.h"
+
+#include <cmath>


The <cmath> header is included but does not seem to be used in this file. Please remove the unnecessary include.

gemini-code-assist · 2025-09-25T11:08:45Z

examples/zkp/sumcheck/matmul_check.cc

+        std::vector<FieldElem> y(log_N);
+        size_t temp_i = i;
+        for (size_t j = 0; j < log_N; ++j) {
+            y[log_N - 1 - j] = FieldElem(temp_i & 1);
+            temp_i >>= 1;
+        }


This logic to convert an integer to its binary representation is duplicated in mat_vec_multiplication (lines 93-98). To improve maintainability and reduce code duplication, consider extracting this logic into a helper function within an anonymous namespace.

For example:

namespace { std::vector<FieldElem> IntToBinaryVector(size_t value, size_t num_bits) { std::vector<FieldElem> bits(num_bits); for (size_t i = 0; i < num_bits; ++i) { bits[num_bits - 1 - i] = FieldElem(value & 1); value >>= 1; } return bits; } } // namespace

Then you could call it like std::vector<FieldElem> y = IntToBinaryVector(i, log_N); in both places.

gemini-code-assist · 2025-09-25T11:08:45Z

examples/zkp/sumcheck/matmul_check.cc

+        std::vector<FieldElem> point_A = u;
+        point_A.insert(point_A.end(), y.begin(), y.end());
+        std::vector<FieldElem> point_B = y;
+        point_B.insert(point_B.end(), v.begin(), v.end());


Constructing vectors by copying and then inserting can be inefficient due to potential reallocations. It's more performant to reserve the required capacity upfront and then insert the elements.

Suggested change

std::vector<FieldElem> point_A = u;

point_A.insert(point_A.end(), y.begin(), y.end());

std::vector<FieldElem> point_B = y;

point_B.insert(point_B.end(), v.begin(), v.end());

std::vector<FieldElem> point_A;

point_A.reserve(u.size() + y.size());

point_A.insert(point_A.end(), u.begin(), u.end());

point_A.insert(point_A.end(), y.begin(), y.end());

std::vector<FieldElem> point_B;

point_B.reserve(y.size() + v.size());

point_B.insert(point_B.end(), y.begin(), y.end());

point_B.insert(point_B.end(), v.begin(), v.end());

gemini-code-assist · 2025-09-25T11:08:46Z

examples/zkp/sumcheck/matmul_check.h

+using yacl::math::MPInt;
+using FieldElem = MPInt;


A using declaration in a header file can introduce names into the global or enclosing namespace of any file that includes it. It's better to use a single type alias to avoid this.

This can be simplified to using FieldElem = yacl::math::MPInt;.

Suggested change

using yacl::math::MPInt;

using FieldElem = MPInt;

using FieldElem = yacl::math::MPInt;

gemini-code-assist · 2025-09-25T11:08:46Z

examples/zkp/sumcheck/matmul_check_test.cc

+
+#include <cmath>
+
+#include <numeric>


The <numeric> header is included but not used in this file. Please remove it.

gemini-code-assist · 2025-09-25T11:08:46Z

examples/zkp/sumcheck/matmul_check_test.cc

+FieldElem EvaluateMultilinearTest(const std::vector<FieldElem>& g,
+                                  absl::Span<const FieldElem> r,
+                                  const FieldElem& modulus) {
+  size_t num_vars = r.size();
+  YACL_ENFORCE(g.size() == (1U << num_vars),
+               "Polynomial evaluation size mismatch number of variables");
+
+  std::vector<FieldElem> evals = g;
+  for (size_t i = 0; i < num_vars; ++i) {
+    std::vector<FieldElem> next_evals;
+    size_t current_size = evals.size() / 2;
+    next_evals.reserve(current_size);
+    const auto& r_i = r[i];
+
+    for (size_t j = 0; j < current_size; ++j) {
+      const auto& eval_at_0 = evals[j];
+      const auto& eval_at_1 = evals[j + current_size];
+
+      FieldElem one(1);
+      FieldElem one_minus_ri;
+      FieldElem::SubMod(one, r_i, modulus, &one_minus_ri);
+
+      FieldElem term1, term2, new_eval;
+      FieldElem::MulMod(eval_at_0, one_minus_ri, modulus, &term1);
+      FieldElem::MulMod(eval_at_1, r_i, modulus, &term2);
+      FieldElem::AddMod(term1, term2, modulus, &new_eval);
+      next_evals.push_back(new_eval);
+    }
+    evals = std::move(next_evals);
+  }
+  return evals[0];
+}


The function EvaluateMultilinearTest is identical to EvaluateMultilinear in sumcheck.cc. To avoid code duplication and improve maintainability, consider adding a dependency on :sumcheck in the matmul_check_test target in your BUILD.bazel file and reusing the existing function from sumcheck.cc.

gemini-code-assist · 2025-09-25T11:08:46Z

examples/zkp/sumcheck/sumcheck.cc

+
+#include "yacl/base/exception.h"
+
+#include <iostream>


The <iostream> header is included but not used in this file. Please remove the unnecessary include.

gemini-code-assist · 2025-09-25T11:08:46Z

examples/zkp/sumcheck/sumcheck.cc

+FieldElem EvaluateUnivariate(const UnivariatePolynomial& poly,
+                                const FieldElem& x,
+                                const FieldElem& modulus) {
+  FieldElem result(0);
+  FieldElem x_pow(1);
+
+  for (const auto& coeff : poly) {
+    FieldElem term;
+    FieldElem::MulMod(coeff, x_pow, modulus, &term);
+    FieldElem::AddMod(result, term, modulus, &result);
+    FieldElem::MulMod(x_pow, x, modulus, &x_pow);
+  }
+  return result;
+}


The current implementation of EvaluateUnivariate recomputes powers of x in each iteration. A more efficient approach is to use Horner's method, which avoids explicit power calculations and reduces the number of multiplications.

FieldElem EvaluateUnivariate(const UnivariatePolynomial& poly, const FieldElem& x, const FieldElem& modulus) { FieldElem result(0); for (auto it = poly.rbegin(); it != poly.rend(); ++it) { FieldElem::MulMod(result, x, modulus, &result); FieldElem::AddMod(result, *it, modulus, &result); } return result; }

SaaRaaS-1300 · 2025-10-20T15:53:18Z

Update Logup Lookup & Zerocheck section summarizes all ZKP-based sumcheck protocol suites into examples/zkp/sumcheck.
This part of the files is used to construct the basic PIOPs (Polynomial Interactive Oracle Proofs) for subsequent ZKP protocols.
Added features include Zerocheck, Onecheck, and Logup Lookup Arguments.
In the examples/zkp/sumcheck files, the README.md has been prepared.

changtong9 · 2025-10-21T07:39:48Z

把代码整体移到 yacl/crypto/experimental目录，解决下 CI 的问题

代码格式有问题，可以通过 VS code 里的 clang-format\bazel 插件格式化下代码
签一下 CLA

SaaRaaS-1300 · 2025-10-21T09:08:17Z

I have read the CLA Document and I hereby sign the CLA

changtong9 · 2025-10-22T08:34:18Z

examples/zkp/sumcheck/matmul_check.h

+  virtual FieldElem evaluate(const std::vector<FieldElem>& point) const = 0;
+};
+
+FieldElem mat_mat_multiplication(


统一使用驼峰命名，类似的都修改下

changtong9 · 2025-10-22T08:37:21Z

examples/zkp/sumcheck/sumcheck.h

+
+using yacl::math::MPInt;
+using FieldElem = MPInt;
+using MultiLinearPolynomial = std::vector<FieldElem>;


建议换个名字，和 logup 中的类同名

changtong9 · 2025-10-22T09:01:31Z

examples/zkp/sumcheck/matmul_check.h

+using yacl::math::MPInt;
+using FieldElem = MPInt;
+
+class MultivariatePolynomial {


MultivariatePolynomial和MultilinearPolynomial的区别是什么，sumcheck 中只需要处理MultilinearPolynomial？
DenseMultilinearPolynomial 这几个 class 用一个就可以表示？

changtong9 · 2025-10-22T09:02:54Z

examples/zkp/sumcheck/matmul_check_test.cc

+
+namespace examples::zkp {
+
+FieldElem EvaluateMultilinearTest(const std::vector<FieldElem>& g,


与 logup.cc 中 Evaluate 的实现类似，可以提取出一个共用的函数？

Update sumcheck and matrix-multiplication-check in zkp examples

752f8d5

gemini-code-assist bot reviewed Sep 25, 2025

View reviewed changes

Niko-Zeng added this to 隐语SecretFlow激励活动 Oct 16, 2025

Niko-Zeng removed this from 隐语SecretFlow激励活动 Oct 16, 2025

SaaRaaS-1300 added 2 commits October 20, 2025 23:25

Merge branch 'secretflow:main' into main

7139566

Update Logup Lookup & Zerocheck

307f2c4

SaaRaaS-1300 changed the title ~~update sumcheck and matrix-multiplication-check~~ update zkp-based Sumcheck Algorithm-Component Oct 20, 2025

SaaRaaS-1300 added 2 commits October 21, 2025 19:58

Update Code & Files

a830ba3

Recheck

3330fd1

changtong9 reviewed Oct 22, 2025

View reviewed changes

	using yacl::math::MPInt;
	using FieldElem = MPInt;
	using FieldElem = yacl::math::MPInt;


		namespace examples::zkp {

		FieldElem EvaluateMultilinearTest(const std::vector<FieldElem>& g,


		#include "yacl/base/exception.h"

		#include <cmath>


		#include <cmath>

		#include <numeric>


		#include "yacl/base/exception.h"

		#include <iostream>

update zkp-based Sumcheck Algorithm-Component #572

Are you sure you want to change the base?

update zkp-based Sumcheck Algorithm-Component #572

Conversation

SaaRaaS-1300 commented Sep 25, 2025

Uh oh!

gemini-code-assist bot commented Sep 25, 2025

Summary of Changes

Highlights

Footnotes

Uh oh!

github-actions bot commented Sep 25, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

gemini-code-assist bot left a comment

Choose a reason for hiding this comment

Code Review

Uh oh!

gemini-code-assist bot Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

gemini-code-assist bot Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

gemini-code-assist bot Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

gemini-code-assist bot Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

gemini-code-assist bot Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

gemini-code-assist bot Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

gemini-code-assist bot Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

gemini-code-assist bot Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

gemini-code-assist bot Sep 25, 2025

Choose a reason for hiding this comment

Uh oh!

SaaRaaS-1300 commented Oct 20, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

changtong9 commented Oct 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

SaaRaaS-1300 commented Oct 21, 2025

Uh oh!

changtong9 Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

changtong9 Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

changtong9 Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

changtong9 Oct 22, 2025

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

github-actions bot commented Sep 25, 2025 •

edited

Loading

SaaRaaS-1300 commented Oct 20, 2025 •

edited

Loading

changtong9 commented Oct 21, 2025 •

edited

Loading