천천히, 제대로

컴퓨터로 다항식의 나눗셈을 수행하는 대표적인 알고리즘은 다항식 장제법(Polynomial Long Division)과 조립제법(Synthetic Division)을 컴퓨터 코드로 구현하는 것입니다. 이 중 장제법은 일반적인 경우에 모두 사용될 수 있는 범용적인 방법이며, 조립제법은 나누는 식이 1차식일 때 매우 효율적입니다. 다항식 장제법 (Polynomial Long Division) 다항식 장제법은 우리가 손으로 다항식을 나누는 방법과 동일한 원리를 컴퓨터로 구현한 것입니다. 이 알고리즘의 핵심은 최고차항을 반복적으로 소거하는 것입니다. 알고리즘 순서 두 다항식 A(x) (피제수)와 B(x) (제수)가 주어졌을 때, 몫 Q(x)와 나머지 R(x)를 구하는 과정은 다음과 같습니다. (A(x) = B(x)Q(x) + R(x)) 초기화: 몫 Q(x)와 나머지 R(x)를 0으로 초기화합니다. 나머지 R(x)는 피제수 A(x)와 같다고 설정하고 시작합니다. 반복 조건 확인: 나머지 R(x)의 차수가 제수 B(x)의 차수보다 크거나 같은 동안 아래 과정을 반복합니다. 최고차항 비교 및 몫 계산: 나머지 R(x)의 최고차항을 제수 B(x)의 최고차항으로 나눕니다. 이 결과가 몫의 새로운 항(t(x))이 됩니다. 예: R(x) = 5x^3 + 2x^2 + …이고 B(x) = x^2 + …이면, t(x) = 5x^3/x^2 = 5x가 됩니다. 몫 누적: 계산된 항 t(x)를 전체 몫 Q(x)에 더합니다. (Q(x) = Q(x) + t(x)) 나머지 갱신: 현재 나머지 R(x)에서 t(x) · B(x)를 뺍니다. 이 과정을 통해 R(x)의 최고차항이 소거됩니다. (R(x) = R(x) - t(x) · B(x)) 종료: 반복이 끝나면, 그때의 Q(x)가 최종 몫이고 R(x)가 최종 나머지가 됩니다. 예시 A(x) = x^3 - 2x^2 + x - 5를 B(x) = x - 2로 나누는 경우: 1단계: R(x) = x^3 - 2x^2 + x - 5, Q(x) = 0 ...

타원 곡선 암호(Elliptic Curve Cryptography, ECC)는 현대 디지털 보안의 핵심 기술입니다. 비트코인과 같은 암호화폐는 물론, 우리가 매일 사용하는 메시징 앱의 종단간 암호화, 웹사이트 접속에 쓰이는 HTTPS 통신 등 수많은 곳에서 데이터를 안전하게 지키고 있죠. 이 기술의 심장에는 '타원 곡선'이라는 특별한 수학적 구조와 그것이 이루는 '순환 그룹(Cyclic Group)'이라는 특성이 자리 잡고 있습니다. 1. 타원 곡선: 점들의 특별한 덧셈 규칙 타원 곡선은 특정 방정식(보통 y² = x³ + ax + b 형태)을 만족하는 점(x, y)들의 집합입니다. 이 곡선 위의 점들은 매우 독특하고 강력한 덧셈 규칙을 가지고 있습니다. 타원 곡선 위에서 두 점의 덧셈 (출처: desmos ) 점 덧셈 (P + Q = R): 곡선 위의 서로 다른 두 점 P와 Q를 지나는 직선을 긋습니다. 이 직선은 곡선과 또 다른 한 점(-R)에서 만나게 됩니다. 이 점을 x축에 대해 대칭시킨 점이 바로 R, 즉 P와 Q의 합입니다. 점 두 배 (P + P = 2P): 한 점 P에서 곡선에 접선을 긋습니다. 이 접선은 곡선과 또 다른 한 점(-R)에서 만납니다. 이 점을 x축에 대칭시킨 점 R이 P를 두 배 한 결과(2P)입니다. 이 연산에는 중요한 '무한점(Point at Infinity)'이라는 항등원(숫자 0과 같은 역할)이 존재하여, 어떤 점 P와 그 역원(-P)을 더하면 무한점이 됩니다. 이러한 덧셈 규칙 덕분에, 타원 곡선 위의 점들은 '아벨 그룹(Abelian Group)', 즉 교환법칙이 성립하는 그룹을 형성합니다. 2. 순환 그룹: 생성점 G로 모든 것을 만들다 타원 곡선 그룹의 가장 중요한 특징은 바로 순환 그룹이라는 점입니다. 순환 그룹이란? 그룹 내의 생성점(Generator, G)이라는 특별한 점 하나를 반복해서 더하는 것만으로 그룹 안의 모든 점들을 만들어낼 수 있는 그룹...

Circom은 영지식 증명에 사용되는 '산술 회로'를 설계하기 위한 언어입니다. 이 회로를 통해 증명하고 싶은 논리나 규칙을 코드로 표현할 수 있습니다. 조금 어렵게 들릴 수 있지만, "어떤 비밀 정보(private input)를 공개하지 않으면서, 내가 그 비밀 정보를 알고 있다는 사실을 증명하는 프로그램"을 만드는 언어라고 생각하면 쉽습니다. 1. 핵심 개념: 회로, 신호, 제약 조건 Circom 코드는 3가지 핵심 요소로 이루어집니다. 회로 (Circuit) Circom의 가장 기본 단위입니다. 우리는 템플릿(template)이라는 키워드를 사용해서 회로를 정의합니다. 마치 다른 언어의 함수나 클래스처럼, 재사용 가능한 로직의 묶음이라고 생각할 수 있습니다. 신호 (Signal) 회로의 입력(input)과 출력(output), 그리고 그 사이에서 계산되는 중간값들을 신호라고 부릅니다. 신호는 회로를 통해 흐르는 데이터입니다. input: 회로에 입력되는 신호입니다. public input: 증명을 검증하는 사람에게도 공개되는 입력값입니다. (예: 문제) private input: 증명하는 사람만 알고 있는 비밀 입력값입니다. (예: 문제의 해답) output: 회로의 계산 결과로 나오는 신호입니다. 보통 public으로 간주되어 공개됩니다. var: 회로 내부에서만 사용되는 중간 신호입니다. 일반 프로그래밍 언어의 변수와 달리, Circom의 모든 신호(var 포함)는 최종적으로 제약 조건 시스템의 일부가 되어 증명 과정에 영향을 줍니다. 제약 조건 (Constraint) Circom의 심장과도 같은 가장 중요한 개념입니다. 제약 조건은 신호들 사이에 반드시 성립해야 하는 수학적 관계(방정식)를 정의합니다. 증명(proof)을 생성한다는 것은, 이 모든 제약 조건을 만족하는 신호값들을 찾았다는 것을 의미합니다. A === B: A와 B의 값이 반드시 같아야 한다는 제약 조건을 추가합니다. 이 연산자는 두 신호가 ...

Circom 예제로 영지식 증명 시작하기 (1) Circom 2 Getting started 문서를 따라하면서 작성한 문서입니다. 실습 환경: Windows 11 Node.js v20.18.0 circom compiler 2.1.9 snarkjs@0.7.5 1. 소프트웨어 설치 Downloads 페이지에서 circom Windows binary 를 클릭하고 파일 circom-windows-amd64.exe 를 원하는 디렉토리에 저장합니다. 파일 크기는 약 10MB입니다. 여기서는 파일 이름을 circom.exe 로 바꾸고 아래 경로에 저장합니다. C:\DevTools\circom.exe snarkjs 를 설치합니다. npm install -g snarkjs 2. 회로 생성하기 아래 내용을 multiplier2.circom 에 저장합니다. pragma circom 2.0.0; /*This circuit template checks that c is the multiplication of a and b.*/ template Multiplier2 () { // Declaration of signals. signal input a; signal input b; signal output c; // Constraints. c <== a * b; } component main = Multiplier2(); 3. 회로 컴파일하기 multiplier2.circom 파일을 컴파일합니다. circom multiplier2.circom --r1cs --wasm --sym --c 컴파일 결과 다음과 같은 파일들이 생성됩니다. multiplier2.r1cs multiplier2.sym multiplier2_cpp\ calcwit.cpp calcwit.hpp circom.hpp fr.asm fr.cpp ...