R1CS 변환 과정 예시

R1CS로 바꾸는 과정 예시(a,b,c 벡터 변환 과정)

회로를 제약 조건으로 변환 예를 들어, 간단한 두 변수를 더한 다음 결과를 곱하는 회로가 있습니다. 입력: x,y 연산: z1=x+y (덧셈) z=z1×y (곱셈) 이러한 연산 조합을 R1CS로 변환하면 다음과 같습니다: 1. 덧셈 게이트 제약 조건: * 첫 번째 게이트에서 되기를 원하는 연산은 x+y=z1입니다. 이는

a=[1,1,0,0,0]

b=[0,0,1,0,0]

c=[0,0,0,1,0]

한 벡터들로 시스템을 정의할 수 있습니다. 이는 모든 s를 곱했을 때,

a⋅s⋅b⋅s−c⋅s=0

혹은,

(s0⋅1+s1⋅1+s2⋅0)2−s2⋅1=0

과 같은 조건이 됩니다. 2. 곱셈 게이트 제약 조건: 두 번째 게이트에서 이루어지는 연산은 z1×y=z입니다. (이는 곱셈 게이트로 변환) a=[0,0,1,0,0]

b=[0,1,0,0,0]

c=[0,0,0,1,0]

위와 같은 구조로 올바른 연산을 정의할 수 있으며, 이러한 형태로 조건식이 전환됩니다. 보통 a,b,c 벡터들을 활용해 게이트의 제약 조건을 구성하면, 숫자 연산의 결과를 하나로 묶어 간소화된 다항식을 만들어낼 수 있습니다.

a,b,c벡터가 나오게 되는 원리

이 벡터들은 회로의 구조와 연산을 수학적으로 정확하게 표현합니다.

1. 벡터의 구조: 각 벡터 a, b, c는 회로의 모든 변수(입력, 중간 값, 출력)에 대응하는 원소를 가집니다. 벡터의 길이 = 전체 변수의 개수
2. 벡터의 의미:
   • a: 좌항의 첫 번째 인자를 나타냅니다.
   • b: 좌항의 두 번째 인자를 나타냅니다.
   • c: 우항의 결과를 나타냅니다.
3. 제약 조건의 형태: (a · s) * (b · s) = c · s 여기서 s는 모든 변수 값을 포함하는 벡터입니다(해답 벡터).
4. 벡터 구성 원리:
   • 연산에 사용되는 변수 위치에 1을 넣습니다.
   • 사용되지 않는 변수 위치에는 0을 넣습니다.

예시를 통해 더 자세히 설명해 드리겠습니다:

덧셈 게이트 (x + y = z1)의 경우:

1. 변수 순서를 정의: [x, y, z1, z, 1] (1은 상수항)
2. a 벡터 구성:
   • x와 y를 더하므로, x와 y에 해당하는 위치에 1을 넣습니다.
   • a = [1, 1, 0, 0, 0]
3. b 벡터 구성:
   • 덧셈은 단순히 두 값을 더하는 것이므로, 상수항 1을 사용합니다.
   • b = [0, 0, 0, 0, 1]
4. c 벡터 구성:
   • 결과 z1에 해당하는 위치에 1을 넣습니다.
   • c = [0, 0, 1, 0, 0]

이렇게 구성하면 (a · s) (b · s) = c · s는 다음과 같이 해석됩니다: (x + y) 1 = z1

곱셈 게이트 (z1 * y = z)의 경우:

1. 같은 변수 순서 사용: [x, y, z1, z, 1]
2. a 벡터 구성:
   • z1에 해당하는 위치에 1을 넣습니다.
   • a = [0, 0, 1, 0, 0]
3. b 벡터 구성:
   • y에 해당하는 위치에 1을 넣습니다.
   • b = [0, 1, 0, 0, 0]
4. c 벡터 구성:
   • 결과 z에 해당하는 위치에 1을 넣습니다.
   • c = [0, 0, 0, 1, 0]

이렇게 구성하면 (a · s) (b · s) = c · s는 다음과 같이 해석됩니다: z1 y = z