KZG in code view

code view

pub fn new(g1: E::G1, g2: E::G2, degree: usize) -> Self {
    Self {
        g1,
        g2,
        g2_tau: g2.mul(E::ScalarField::ZERO),
        degree,
        crs_g1: vec![],
        crs_g2: vec![],
    }
}

구조체를 초기화하는 역할을 합니다.

• 입력값: g1과 g2는 각각 그룹 $G1$과 $G2$에서의 기본 생성자입니다. 이 값들은 셋업 과정에서 그룹 원소들의 여러 지수 승을 구할 때 기본이 됩니다. degree는 다항식의 차수입니다.
• 출력값: 구조체에 기본값들을 설정해주고, 나중에 셋업을 통해 채워질 참조 문자열(CRS)에 대한 두 개의 벡터 crs_g1과 crs_g2를 빈 값으로 초기화합니다.
• g2_tau는 아직 비밀 값이 없기 때문에 $g2$​에 비밀 값 대신 0을 곱한 값을 설정합니다.

pub fn setup(&mut self, secret: E::ScalarField) {
    for i in 0..self.degree+1 {
        self.crs_g1.push(self.g1.mul(secret.pow(&[i as u64])));
        self.crs_g2.push(self.g2.mul(secret.pow(&[i as u64])));
    }
    self.g2_tau = self.g2.mul(secret);
}

이 함수는 실제로 KZG 셋업 과정을 수행합니다. 비밀 값(secret)을 기반으로 참조 문자열(CRS)을 생성합니다.

• 입력값: secret은 셋업에서 사용하는 비밀 값 sss입니다. 이 값은 셋업 과정에서 매우 중요하며 절대로 공개되지 않아야 합니다.
• 출력값: crs_g1과 crs_g2 벡터에 비밀 값과 그 거듭제곱을 곱한 그룹 원소들이 채워집니다.

세부 설명:

• for i in 0..self.degree+1: 다항식의 차수가 degree이기 때문에 000부터 degree까지의 거듭제곱을 다룹니다.

  • self.crs_g1.push(self.g1.mul(secret.pow(&[i as u64]))): 이 부분은 $g_1^{s^i}$를 계산해 crs_g1 벡터에 저장하는 과정입니다.

  • self.crs_g2.push(self.g2.mul(secret.pow(&[i as u64]))): 마찬가지로 $g_2^{s^i}$를 계산해 crs_g2 벡터에 저장합니다.

    이 과정에서 비밀 값의 거듭제곱을 각각 $g_1^{s^i}$과 $g_2^{s^i}$에서 계산하여 참조 문자열(CRS)을 만들게 됩니다.

• 마지막으로 self.g2_tau = self.g2.mul(secret);는 비밀 값 $s$와 $g_2​$를 곱하여 $g_2^s$​ 값을 저장합니다. 이 값은 검증 단계에서 필요한 요소입니다.

Commit

pub fn commit(&self, poly: &[E::ScalarField]) -> E::G1 {
    let mut commitment = self.g1.mul(E::ScalarField::ZERO);
    for i in 0..self.degree+1 {
        commitment += self.crs_g1[i] * poly[i];
    }
    commitment
}

commit 함수

• 이 함수는 다항식 P(x)P(x)P(x)의 계수 배열(poly)을 입력으로 받아, 이를 타원곡선 상의 한 점 $C$로 변환합니다. 이 과정에서 만들어진 점은 다항식 커밋(commitment)으로 불리며, 이를 통해 나중에 다항식 평가값을 증명하고 검증할 수 있게 됩니다.
• E::G1은 타원 곡선 그룹 $G1$을 의미하며, commit 함수는 결국 $G1$ 상의 한 점을 반환합니다. 이 점이 다항식에 대한 커밋입니다.

2. commitment = self.g1.mul(E::ScalarField::ZERO)

• 이 줄은 $G1$ 상에서 초기값을 설정하는 부분입니다. 이 값은 $G1$ 에 0을 곱한 값이므로,$G1$ 상에서의 중립 요소(identity element)가 됩니다. 이는 이후에 다항식 계수들을 기반으로 값을 누적하기 위한 초기값입니다.

3. for 루프: 계수를 기반으로 커밋 생성

• 이 부분이 핵심입니다. 루프에서 다항식의 각 계수와 셋업에서 미리 계산한 g1s,g1s2,…g_1^s, g_1^{s^2}, \dotsg1s​,g1s2​,… 값을 활용하여 커밋을 만듭니다.

오픈

pub fn open(&self, poly: &[E::ScalarField], point: E::ScalarField) -> E::G1 {
// evaluate the polynomial at point|
let value = evaluate(poly, point);

// initialize denominator|
let denominator = [-point, E::ScalarField::ONE];
// initialize numerator|

let first = poly[0] - value;
let rest = &poly[1..];
let temp: Vec<E::ScalarField> = std::iter::once(first).chain(rest.iter().cloned()).collect();
let numerator: &[E::ScalarField] = &temp;

// get quotient by dividing numerator by denominator|
let quotient = div(numerator, &denominator).unwrap();
// calculate pi as proof (quotient multiplied by CRS)
let mut pi = self.g1.mul(E::ScalarField::ZERO);
for i in 0..quotient.len() {
pi += self.crs_g1[i] * quotient[i];
}
// return pi
pi
}

pub fn open(&self, poly: &[E::ScalarField], point: E::ScalarField) -> E::G1 {

이 함수는 두 가지 입력을 받습니다:

1. poly: 다항식의 계수 배열입니다.
2. point: 다항식을 평가할 특정 점 $x0$​입니다.

결과적으로, 이 함수는 $P(x_0)$ 에 대한 증명 값 $\pi$를 반환합니다.

1. 다항식 평가

let value = evaluate(poly, point);

먼저, 다항식 P(x)를 입력된 점 $x_0$에서 평가하여 $P(x_0)$ 값을 계산합니다. evaluate 함수는 다항식의 계수 배열과 점을 입력받아 $P(x_0)$을 반환합니다.

2. 분자와 분모 설정

2.1 분모 설정

let denominator = [-point, E::ScalarField::ONE];

$x-x_0$가 분모 역할을 합니다. $x_0$는 point로 주어졌으며, 분모는 타원곡선 그룹에서의 차수에 해당하는 두 요소 $[−point,1]$로 표현됩니다.

2.2 분자 설정

let first = poly[0] - value;
let rest = &poly[1..];
let temp: Vec<E::ScalarField> = std::iter::once(first).chain(rest.iter().cloned()).collect();
let numerator: &[E::ScalarField] = &temp;

분자는 $P(x)−P(x0)$입니다.
이를 위해 $P(x0)$ 값을 다항식의 상수항에서 빼주고, 나머지 항은 그대로 복사합니다.
이 작업을 통해 $P(x)−P(x0)$의 계수를 만들어냅니다.

3. 다항식 나눗셈

let quotient = div(numerator, &denominator).unwrap();

$P(x)−P(x0)$를 $x−x0​$로 나누는 과정입니다.
이를 통해 몫 다항식이 생성됩니다.
몫 다항식은 KZG에서 중요한 역할을 하며, 이를 기반으로 증명(proof)을 만듭니다.

4. CRS를 사용하여 증명 생성

let mut pi = self.g1.mul(E::ScalarField::ZERO);
for i in 0..quotient.len() {
    pi += self.crs_g1[i] * quotient[i];
}

여기서는 KZG 셋업에서 미리 생성된 CRS(공통 참조 문자열, crs_g1)를 사용해 증명 값 π를 계산합니다. 몫 다항식의 각 계수에 해당하는 $g_1^{s_i}$와 곱해서 누적한 값을 통해 타원 곡선 상의 한 점 π가 만들어집니다.

5. 검증

pub fn verify( &self, point: E::ScalarField, value: E::ScalarField, commitment: E::G1, pi: E::G1 ) 
-> bool
{ 
	let lhs = E::pairing(pi, self.g2_tau - self.g2.mul(point));
	let rhs = E::pairing(commitment - self.g1.mul(value), self.g2);
		lhs == rhs 
}

함수 매개변수

• point: E::ScalarField: 검증할 특정 점 aaa.
• value: E::ScalarField: 다항식이 이 점에서 평가된 값, 즉 f(a).
• commitment: E::G1: 다항식의 약속 값, 즉 다항식에 대한 KZG commitment.
• pi: E::G1: 검증자에게 제공된 증명 값.

다음 두 개의 쌍선형 페어링의 결과가 같은지를 비교하여 증명을 검증합니다.

좌변 (lhs):

let lhs = E::pairing(pi, self.g2_tau - self.g2.mul(point));

• 여기서 pi는 증명 값이며, $g2_tau$는 KZG 셋업 과정에서 계산된 값입니다.
• self.g2.mul(point)는 약속의 그룹 요소에 대해 특정 점 a를 곱한 값입니다. 이 값은 $g_2$​ 그룹에서 다항식의 점을 나타냅니다.
• 좌변은 pi와 $g2_tau−g2⋅a$ 간의 페어링을 통해 계산됩니다. 이 페어링은 $f(s)−y$의 관계를 나타내며, 증명 값이 다항식의 평가값과 일치하는지를 확인하는 역할을 합니다.

우변 (rhs):

let rhs = E::pairing(commitment - self.g1.mul(value), self.g2);

• commitment는 다항식에 대한 KZG commitment이며, g1그룹의 요소입니다.
• self.g1.mul(value)는 평가된 값 y를 약속에 대해 곱한 것입니다. 이 값은 다항식의 평가 결과를 나타냅니다.
• 우변은 $commitment−g1$와 $g_2$ 간의 페어링을 통해 계산됩니다. 이 페어링은 다항식의 평가가 올바른지를 확인하는 또 다른 방법입니다.

lhs == rhs

• 검증자는 좌변과 우변의 결과가 같은지를 비교합니다.
• 이 두 결과가 같다면, 다항식 $f(x)$가 특정 점 a에서 평가된 값이 y가 맞다는 것을 증명합니다. 즉, 약속된 다항식과 평가값 간의 관계가 일치함을 확인하는 것입니다.

---

mathmatical view

[[KZG Polynomial Commitment]]