https://upsidezkp.gitbook.io/upside-zkp-docs

Cairo에서는 “제약식을 직접 설계”하지 않는다. VM(Cairo CPU)의 AIR(=고정된 제약)가 이미 있고, 일반 함수를 작성한 뒤 그 안에서 assert(...) 등으로 “원하는 명제가 참이어야만 실행이 성공”하도록 만든다. 그 실행 트레이스가 STARK로 증명된다.

1. What is Cairo

“Cairo — 튜링 완전한 STARK 친화적 CPU 아키텍처”

• 튜링 완전 : 어떤 종류의 연산이던 전부 수행할 수 있음을 의미
• STARK 친화적 :  Cairo는 STARK 기반의 증명 생성을 프로그래밍으로 대체할 수 있도록 해주는 언어 - 효율적으로 proof를 생성할 수 있게 해줌
• CPU 아키텍처 : 컴퓨터의 아키텍처 수준에서 긴밀하게 소통하는 저수준 언어

proof 생성 시에는 2가지로 인해 비효율성이 발생한다.

• Statement의 다항방정식 표현으로 인한 비효율 : 새로운 변수 및 연산의 증가: 증명하고자 하는 일반적인 계산(statement)을 ZK-STARKs나 ZK-SNARKs가 요구하는 형식인 다항방정식(Polynomial Equation) 형태로 변환(R1CS 등)할 때, 원래의 연산에는 없던 새로운 임의의 변수가 추가되거나 필요한 연산의 개수가 늘어남 → Proof를 생성하는 증명자(Prover)의 부담을 가중시키고, 결과적으로 증명 생성의 속도를 늦춤
• 제어 흐름(Control Flow)으로 인한 비효율 : Loop나 Branch (조건문)와 같은 제어 흐름 구조를 다항방정식으로 표현하는 과정에서, 실제로 필요한 연산 횟수보다 훨씬 많은 횟수의 연산을 강제로 수행해야 하는 비효율이 발생

Cairo는 이 비효율을 해소하기 위해 CPU 아키텍처 수준에서 설계된 저수준 언어를 선택했다. Proof 생성을 위해 최적화된 CPU 아키텍처와 Instruction Set(명령어 집합)을 새로 만들어, 이 집합을 만족하는 방식으로 프로그램을 작성하면, 애초에 다항방정식으로의 변환이 필요 없거나 또는 변환이 매우 효율적으로 이루어지게 되어, 불필요한 변수와 연산의 수를 근본적으로 줄일 수 있게 된다.

2. Deep Dive to Cairo

Cairo = CPU + AIR

Cairo를 좀 더 어렵게 이야기 하면 다음과 같다.

“계산의 무결성(Computational Integrity)을 증명하는 다항방정식 형태의 Proof인 AIR(Algebraic Intermediate Representation)을 쉽고 효율적으로 생성하기 위해 CPU 아키텍처단부터 새로 설계하여 만든 폰-노이만 아키텍처”

이전에 STRAK를 공부했을 때, “AIR”를 볼 수 있었는데, AIR는 쉽게 말하면 우리가 증명하려고 하는 statement가 지켜야 할 규칙(제약 조건)을 다항식 형태로 나타낸 것이다. Cairo는 Proof 생성에 최적화된 폰-노이만 아키텍처와 Instruction Set(명령어 집합)을 새로 설계하여 프로그램의 한 상태(행 Rowi)에서 다음 상태(행 Rowi+1)로 넘어갈 때 발생하는 변화가 가장 단순하고 적은 수의 다항식 제약 조건(AIR)으로 표현되도록 구성되어 있다.

즉, 복잡한 Statement를 처음부터 다항식으로 변환하기 쉬운 저수준 Assembly로 작성하도록 유도하여, 불필요한 변수(Trace Table}의 크기와 연산(Constraint의 차수)의 증가를 최소화한다.

Cairo의 설계

특이한 메모리 구조

Cairo의 메모리 구조는 다소 특이한데, Nondeterministic Continuous Read-Only Random Access Memory 구조를 지닌다. 이는 매우 경직된 메모리 구조로 execution 도중에 memory의 수정이 불가하다. 다만 이러한 제한을 통해서 AIR을 활용의 효율성이 극대화된다.

public memory의 효율성을 재고

Zk proof의 특성 상 code + output이 공유되어야 하므로 memory cell은 verifier에게 공유되어야 한다. Cairo의 경우 이러한 공유를 위해 일반적인 연산이 아니라 boundary를 제한하는 방식을 채택해 verifier가 이러한 공유 과정에 4개의 산술만이 필요하도록 만들었다.

연산 최적화

Cairo는 증명의 검증을 위해 자주 사용되는 Permutation Range check 등의 연산을 최적화한다. Cairo 상에서는 3개의 trace cell만으로 [0,2¹⁶) 범위 내에 trace가 존재하는지 확인할 수 있다.(일반적인 binary approach는 16개의 trace cell이 필요)

Cairo CPU

• 최적화된 Instruction Set 제공
  • 모든 명령어가 작고 단순한 (15 bit flags + 3 integers) RISC 형태로 구성되어, 타의 추종을 불허하는 수준으로 trace cell을 적게 사용하여 증명 생성(최적화).

• 실용적인 기능 제공
  • Conditional branch, memory, function call, 재귀(Recursion) 등 개발에 필요한 기능을 충분히 지원.
  • Nondeterministic 특성 덕분에 Recursive proof 및 병렬 연산 지원.
• Built-in 최적화
  • Cryptographic hash function 등 자주 쓰이는 중요한 연산에 대해 최적화된 built-in을 제공하여 편의성과 효율성을 동시에 높임.
• Product Level 표준 제시
  • Cairo 기반으로 생성된 모든 오프체인 증명은 동일한 Ethereum 스마트 컨트랙트에서 검증될 수 있는 단일 프레임워크를 제공하여, 생태계 확장에 기여.

3. Simple Example

3 * 4 = 12 증명

prover

use core::hash::HashStateTrait;
use core::poseidon::PoseidonTrait;

pub fn create_commitment(a: felt252, b: felt252, nonce: felt252) -> felt252 {
    let mut state = PoseidonTrait::new();
    state = state.update(a);
    state = state.update(b);
    state = state.update(nonce);
    let commitment = state.finalize();

    commitment
}

pub fn generate_zk_proof(a: felt252, b: felt252, c: felt252, commitment: felt252) -> felt252 {
    let computed_c = a * b;
    assert(computed_c == c, 'Multiplication mismatch');

    let mut proof_state = PoseidonTrait::new();
    proof_state = proof_state.update(commitment);
    proof_state = proof_state.update(c);
    let zk_proof = proof_state.finalize();

    zk_proof
}

#[executable]
fn main(a: felt252, b: felt252, c: felt252, nonce: felt252) -> (felt252, felt252) {
    let commitment = create_commitment(a, b, nonce);
    let zk_proof = generate_zk_proof(a, b, c, commitment);

    println!("commitment: {}", commitment);
    println!("zk_proof: {}", zk_proof);

    (commitment, zk_proof)
}

verifier

#[starknet::interface]
pub trait IMultiplicationVerifier<TContractState> {
    fn verify_zk_proof(
        ref self: TContractState, commitment: felt252, zk_proof: felt252, c: felt252,
    ) -> bool;
}

#[starknet::contract]
mod MultiplicationVerifier {
    use core::hash::HashStateTrait;
    use core::poseidon::PoseidonTrait;

    #[storage]
    struct Storage {}

    #[abi(embed_v0)]
    impl AgeVerifierImpl of super::IMultiplicationVerifier<ContractState> {
        fn verify_zk_proof(
            ref self: ContractState, commitment: felt252, zk_proof: felt252, c: felt252,
        ) -> bool {
            let mut proof_state = PoseidonTrait::new();
            proof_state = proof_state.update(commitment);
            proof_state = proof_state.update(c);
            let calculated_proof = proof_state.finalize();

            zk_proof == calculated_proof
        }
    }
}

a. 먼저 prover에서 zk proof 생성

scarb execute --print-program-output --arguments 3,4,12,12345

b. verifier에서 contract 배포

declare

sncast --account=sepolia declare \                    
    --contract-name=MultiplicationVerifier \
    --network=sepolia

deploy

sncast --account=sepolia deploy \                
    --class-hash=0x495bea3bbb205d321f11e05311705de016ce02354c0c6e1cc0263f379823467 \
    --network=sepolia

c. test

sncast call --network sepolia \              
  --contract-address 0x04707bca34bc2ce4d7e9e7aa82bab4d702472d3686915837e72be81264a5f3e7 \
  --function verify_zk_proof \
  --calldata \
  3383298923621555134881407750558353577883516115305139938260704789276607526339 \
  110104513817474511716189280977084708273832431304331938192148989180448298497 \
  12

4. Challenges

맨 처음에는 아래와 같이 코드를 작성한 후에, execute를 실행했다.

pub fn mul(a: u32, b: u32) -> u32 {
    a * b
}

pub fn is_correct(a: u32, b: u32, c: u32) -> bool {
    let mut is_correct = false;
    if (mul(a, b) == c) {
        is_correct = true;
    }
    is_correct
}

#[executable]
fn main(input: (u32, u32, u32)) -> bool {
    let (a, b, c) = input;
    is_correct(a, b, c)
}

그런데 해당 코드의 경우에는 execution-id 1에 대해서는 잘 작동했지만(proof 생성과 verify가 가능), execution-id 2에서부터는 잘 작동하지 않았다.

이러한 오류는 Trace의 길이가 짧기 때문에 발생하는 오류였다.. Cairo 코드가 mul(3, 4)처럼 매우 단순한 계산만 수행할 경우, Execution Trace(AET)의 행(Row) 수가 10~20개 정도로 짧게 기록된다. 이 짧은 Trace는 STARK Prover가 요구하는 두 가지 최소 안전성 조건을 충족하지 못하기 때문에 오류가 발생한다.

• STARK 안전성을 위한 최소 길이 요구

  STARK 프로토콜은 통계적 건전성(Soundness)을 확보하기 위해 Trace Table의 길이가 일정 크기 이상이어야 한다.

  이 과정의 핵심은 LDE(Low-Degree Extension)이다. LDE는 Trace Table을 나타내는 다항식을 더 넓은 정의역으로 확장하는 과정인데, Trace의 길이가 너무 짧으면 다항식 확장을 수행할 여유가 없거나 알고리즘 자체가 실행되지 못한다.

  결과적으로 Prover는 log_size >= LOG_N_LANES와 같은 최소 크기 요구 조건을 만족하지 못해 증명 생성이 중단된다.

• Built-in 함수의 Trace 기록 요구 사항

  이 오류는 u32와 같은 정수 타입의 오버플로우 검사를 위해 Cairo가 사용하는 Range Check Built-in 함수와 관련이 있다.

  Cairo는 u32 타입을 사용할 때 자동으로 Range Check 코드를 CASM에 추가하며, 이 Built-in 함수는 자신의 Proof를 생성하기 위해 Trace Table에 특정 구조를 기록해야 한다.

  그러나 매우 단순한 연산만 수행할 경우, 이러한 구조를 완성하기 위한 최소한의 Trace 행(Row) 수가 확보되지 않아 증명 생성이 실패한다.

5. Reference

https://eprint.iacr.org/2021/1063.pdf

https://www.starknet.io/cairo-book/ch01-03-proving-a-prime-number.html?highlight=prime#proving-that-a-number-is-prime

https://velog.io/@0xmuang/ZK-ZK-Programming

https://blog.tetedo.com/385?category=1058574

https://www.certik.com/resources/blog/an-introduction-to-the-cairo-programming-language

Maximum distance vs average distance to a linear code

영지식 증명 시스템의 핵심 목표는 증명자가 거짓말을 할 때 이를 잡아내는 것이다. 증명자가 제출한 데이터가 저차항 다항식에 가깝다고 주장하지만 실제로는 멀리 떨어져 있을 수 있다. 이때 검증자는 무작위로 한 지점을 선택하여 이 주장이 사실인지 검사한다. 만약 무작위로 선택된 지점이 코드에서 멀리 떨어져 있다면, 증명자는 올바른 답변을 줄 수 없으므로 거짓말이 들통난다.

기존 방식에서는 데이터가 코드에서 멀리 떨어져 있더라도, 무작위 변형들의 평균 거리가 생각보다 가까울 수 있다. 그러면 검증자가 운 좋게 코드에 가까운 지점을 선택할 가능성이 생겨, 거짓말하는 증명자가 들통나지 않을 수 있다. 그러나 DEEP 기법은 무작위 변형들의 평균 거리($E[δx]$)가 최악의 경우($δ{max}$)와 거의 같은 수준으로 멀리 떨어져 있음을 증명한다. 이로써 부적절한 식에 대해서 Verifier가 어떤 무작위 지점을 선택하든, 그 지점은 코드에서 멀리 떨어져 있을 확률이 매우 높아진다.

결론적으로, '평균 거리가 최대 거리에 가깝다'는 것은 거짓말을 잡아내는 테스트의 건전성(soundness)이 매우 높다는 것을 의미한다.

Domain Extension for Eliminating Pretenders (DEEP)

기존 영지식 증명 시스템에서 증명자는 자신이 가진 데이터가 "특정 규칙을 따르는 저차항 다항식"의 평가값이라고 주장한다. 하지만 증명자가 거짓말을 할 경우, 즉 데이터가 실제로는 저차항 다항식과 거리가 먼 경우라도 검증자가 이를 쉽게 알아채지 못할 수 있다.

검증자는 다항식의 원래 평가 도메인 $D$보다 더 큰 $\overline{D}$를 인위적으로 생성한다. 검증자는 이 확장된 도메인 $\overline{D}$에서 무작위로 점 z를 선택하고, 증명자에게 해당 지점에서의 다항식 평가값을 요청한다.

증명자가 답변을 제공하면, 검증자는 이 정보를 이용해 거짓말을 하는 증명자들이 내놓을 수 있는 '가짜' 다항식 목록을 정리(prune down)한다. 이 과정을 통해 증명자가 주장하는 다항식이 정말로 저차항 다항식에 가까운지, 아니면 거짓말인지 훨씬 더 쉽게 구별할 수 있게 된다.(가짜 다항식에 해당 prover가 보낸 다항식이 없으면 통과)

그러나 실제 증명 시스템에서는 이 "목록 정리"를 수학적으로 엄밀하게 증명해야 한다. 여기서 '거리 보존'과'가중 버전' 같은 개념이 등장한다. 이는 "목록을 정리했다"는 직관을 "거짓 다항식이 올바른 코드에서 여전히 멀리 떨어져 있음($δ_{max}$)"이라는 정량적이고 증명 가능한 사실로 변환하는 과정이다.

DEEP 기법의 핵심 논리는 다음과 같다.

DEEP 기법은 증명자가 제출한 함수($u^∗,u$)가 올바른 다항식이 아니라고 가정하는 것에서 시작된다. 이러한 경우, $u^$와 $u$는 다항식 코드에서 멀리 떨어져 있다. 이 문제를 해결하기 위해, 검증자는 원래 도메인 밖의 점 $z$를 질의하여, 증명자의 답변과 일치하는 '가짜' 다항식들을 줄여 나간다. 이 정리 과정이 ‘거리 보존’으로 이어진다. 즉, 몫 연산과 같은 연산을 통해 얻은 새로운 함수($u_x$)는 여전히 올바른 코드에서 멀리 떨어져 있다. 여기서 이 거리가 얼마나 멀리 떨어져 있는지는 '*1.5-존슨 함수**'로 정량화된다.

이러한 DEEP 기법의 원리는 다양한 상황에 맞게 확장되어 실용성을 높인다. weighted version과 general linear codes이 그 방법이다. weighted version은 모든 데이터 지점이 동일한 중요도를 갖지 않는 실제 시나리오에서도 작동함을 보여준다. 또한 general linear codes은 리드-솔로몬 코드에만 국한되지 않고, 더 넓은 범위의 코드에 적용될 수 있음을 증명한다.

DEEP-FRI

DEEP-FRI에 대해 공부하기 전에 FRI를 다시 한번 짚고 넘어가 보자.

FRI

FRI는 차수를 줄이는 과정(COMMIT 단계)와 그 결과가 정확한지 확인하는 과정(QUERY 단계)으로 구성된다.

COMMIT 단계

Prover와 Verifier가 여러 라운드에 걸쳐 상호작용하며 문제를 점진적으로 축소하는 과정이다. Prover는 $f^{(0)}$라는 함수가 리드-솔로몬 코드에 가깝다고 주장하며, Verifier는 이를 검증하기 위해 무작위 값 $x^{(i)}$를 보낸다. Prover는 이 값을 이용해 $f^{(i)}$를 '대수적 해시'하여 새로운 함수 $f^{(i+1)}$을 만든다. 이 과정은 다항식의 차수와 데이터 크기를 절반으로 줄이며, 여러 라운드 반복을 통해 복잡한 문제를 상수 크기의 간단한 문제로 축소한다.

STARK에서는 이러한 COMMIT 단계를 Split-and-Fold를 통해 수행한다. Split의 경우에는 짝수항과 홀수항으로 쪼갠다.

만약 $f_0​(x)=19+56x+34x^2+48x^3+43x^4+37x^5+10x^6+0x^7$라는 식을 Split한다고 할 때, 짝수와 홀수 차수를 가진 것들나눈다.

$f_{0,even​}(x)=19+34x+43x^2+10x^3$

$f_{0,odd}​(x)=56x+48x^3+37x^5+0x^7$

그리고 이후에 Fold 과정을 거친다. 이 식을 $f_{0,mid}= 19+34x^2+43x^4+10x^6 + x(56+48x^2+37x^4+0x^6)$ 으로 합친다.

그 후 어떤 x 대신에 random한 값 r을 사용해서 두 식을 하나의 식으로 합쳐서 $f_1$을 생성한다.

$f_1​(x)=f_e​(x^2)+r⋅f_o​(x^2)$

$f_1​(x) = 19+34x+43x^2+10x^3 + 12⋅(56+48x+37x^2+0x^3)$

$f_1​(x)=12+28x+2x^2+10x^3$ (mod 97)

최종적으로 Split-and-Fold를 거치면서 차수가 원래보다 1/2이 된 것을 확인할 수 있다.

QUERY 단계

COMMIT 단계에서 다항식 $f^{(0)}$를 'Split-and-Fold'를 통해 $f^{(1)}, f^{(2)}, ...$로 변환한 것이 올바른지 검증자는 확인해야 한다. 검증자는 프로토콜의 locality 속성을 사용하여 이를 수행한다

1. 무작위 지점 선택: Verifier는 $L(0)$ 도메인에서 $s(0)$라는 무작위 지점을 선택한다.

2. 폴딩 경로 추적: Verifier는 이 $s(0)$를 사용하여 COMMIT 단계에서 일어난 폴딩 과정을 역으로 추적한다.

3. 정확성 검증:

   • 검증자는 $f^{(i)}$에 대한 두 번의 질의를 통해 $H_xf(i)$ 값을 직접 계산한다.

   • 그리고 증명자가 제출한 $f(i+1)$의 값($f(i+1)(s(i+1))$)과 자신이 계산한 값이 일치하는지 비교한다.

   • 만약 단 한 번이라도 불일치가 발생하면, 검증자는 REJECT한다. 모든 라운드의 검사를 통과하면

     ACCEPT한다.

이 과정을 통해 검증자는 매 라운드마다 증명자가 올바른 다항식 폴딩을 수행했는지를 효과적으로 확인할 수 있다.

DEEP-FRI

DEEP-FRI는 기존 FRI 프로토콜에 몫 연산(quotienting)이라는 새로운 개념을 도입하여 건전성(soundness)을 개선한 프로토콜이다.

몫 연산 (Quotienting)

몫 연산은 특정 지점에서 특정 값을 가지는 다항식에 초점을 맞추는 연산이다. 함수 f가 주어졌을 때, 몫 연산은 z에서 b 값을 갖는 새로운 함수 $g(y) = \frac{f(y)-b}{y-z}$를 정의한다.

보조정리 5.3

$L⊆F_q$이고, $z∈F_q$이며 $z∉L$이라고 하자.

$d≥1$은 정수라고 하자.

함수 $f:L→F_q$이고 $b∈F_q$라고 하자. $g = QUOTIENT(f, z, b)$라고 하자. 다음은 동치(equivalent)이다.

위의 정리는 다음과 같은 사실을 보장한다.

• $Δ(g,Q)<δ$(차수 d−1 이하의 다항식 Q가 g와 가깝다면), 차수 d 이하의 다항식 R이 존재하여 f와 가깝고 $R(z)=b$를 만족한다.
• 반대로, $Δ(f,R)<δ(R(z)=b$를 만족하는 차수 d 이하의 다항식 R이 f와 가깝다면), $Q=(R−b)/Z$로 정의된 다항식 Q는 g와 가깝다.

COMMIT 단계

기존 FRI 프로토콜은 Prover가$f^{(0)}$가 리드-솔로몬 코드에 가깝다고 주장하면, Verifier가 무작위 값 $x^{(i)}$를 보내고 Prover가 이를 이용해 $f^{(i+1)}$를 만들어 문제를 점진적으로 축소한다.

하지만 DEEP-FRI는 이 과정에 다음 단계를 추가한다.

1. '도메인 밖' 질의: Verifier는 다항식의 원래 평가 도메인 밖의 무작위 지점 $z^{(i)}$를 샘플링하고, Prover에게 해당 다항식의 평가값을 요청한다.
2. 몫 연산 적용: Verifier는 검증자가 보낸 $x^{(i)}$와 $z^{(i)}$를 이용하여, 몫 연산을 적용한 새로운 함수 $f^{(i+1)}$를 작성한다. 이 함수는 $QUOTIENT(H_{x^{(i)}}[f^{(i)}], z^{(i)}, B^{(i)}_{z^{(i)}}(x))$와 같다고 추정되는 함수이다.
3. '악의적인 prover' 제거: 이 몫 연산은 가짜 다항식 목록을 걸러내는(prune down) 역할을 한다. 증명자가 거짓말을 하고 있다면, 도메인 밖의 지점 $z^{(i)}$에서 올바른 값을 제공하는 가짜 다항식은 극히 드물다.

이 과정을 통해 DEEP-FRI는 차수를 줄이기 전에 거짓 증명을 선제적으로 제거하여, FRI 프로토콜의 건전성을 획기적으로 향상시킨다.

이를 포함한 전체적인 COMMIT 과정을 정리하면 다음과 같다.

1. Split-and-Fold (대수적 해시 생성):

   Prover는 $f^{(i)}$를 짝수 차수 항과 홀수 차수 항으로 분리한다. Verifier가 보낸 무작위 값 $x^{(i)}$를 사용해 이 두 다항식을 하나로 합칩니다(Fold). 이 Split-and-Fold 과정을 거쳐 생성된 다항식이 바로 대수적 해시 함수 $H_{x^{(i)}}[f^{(i)}]$이다.

2. DEEP 기법 적용 (몫 연산):

   $H_{x^{(i)}}[f^{(i)}]$라는 단일 다항식이 생성된 후, DEEP 기법이 적용된다. Verifier는 다항식의 원래 평가 도메인 밖의 무작위 지점 $z^{(i)}$를 선택하고, 증명자에게 $H_{x^{(i)}}f^{(i)}$의 값을 요청한다. Prover는 이 정보를 바탕으로 몫 연산(QUOTIENT)을 적용하여, 거짓 증명을 걸러낸 새로운 다항식을 만든다.

3. 다음 라운드 다항식 생성:

   몫 연산의 최종 결과물이 다음 라운드에서 사용될 다항식 $f^{(i+1)}$이 된다.

QUERY 단계

COMMIT 단계에서 제출된 함수들이 올바르게 '몫 연산'을 거쳤는지 확인하는 과정이다. 검증자는 보조정리 5.3을 기반으로 대수적 해시와 몫 연산의 관계를 검증한다.

1. 무작위 지점 선택: 검증자는 $L^{(0)}$ 도메인에서 무작위 지점 $s^{(0)}$를 선택한다.

2. 계산 경로 추적: 검증자는 각 라운드 i마다 $s^{(i+1)}$를 계산한다. 그리고 $f^{(i)}$에 대한 2번의 질의를 통해 $H_xf^{(i)}$ 값을 직접 계산한다.

3. 몫 연산 검증: 검증자는 $H_x[f^{(i)}]$에 몫 연산을 역으로 적용한 값과 증명자가 제출한 $f^{(i+1)}$ 값이 일치하는지 확인한다.

   이 검증 과정은 FRI 프로토콜의 국소성(locality)과 몫 연산(quotienting)이라는 두 가지 핵심 원리에 기반을 둔다.

   $$ H_xf^{(i)} ? = f^{(i+1)}(s^{(i+1)}) * (s^{(i+1)}-z^{(i)}) + B^{(i)}[z^{(i)]}(x^{(i)}) $$

   • 우변 : 증명자가 제출한 값에 몫 연산을 역으로 적용한 결과이다.

   • 좌변 : 검증자가 직접 계산한 $H_x[f^(i)]$의 값.

   • 만약 두 값이 일치하지 않으면, 이는 증명자가 몫 연산을 올바르게 적용하지 않았음을 의미하므로, 검증자는 거부(REJECT)한다.

     이처럼 극소적 일관성만을 활용해서 전체 거리를 확인할 수 있는 이유는 극소적 확인이 전체 속성인 거리 보존을 확률적으로 보장하기에 충분하기 때문이다. 만약 Prover가 속이기 위해 나쁜 다항식을 제공했다면, COMMIT과정을 거치면서 다항식이 많이 변하기 때문에 높은 확률로 원래의 코드에서 멀리 떠러져도록 설계된다.

DEEP-FRI Analysis

• 완전성(Completeness): 증명자가 정직하게 올바른 다항식을 제출하면, 검증자는 확률 1로 수락(ACCEPT)한다.
• 효율성: DEEP-FRI는 기존 FRI의 효율성을 그대로 유지한다.
  • 증명자 복잡도: O(n) 산술 연산
  • 검증자 복잡도: O(logn) 산술 연산
• 건전성(Soundness): 만약 증명자가 거짓말을 해서 $f^{(0)}$가 리드-솔로몬 코드에서 멀리 떨어져 있다면, 검증자는 높은 확률로 이를 감지하고 거부(REJECT)한다.
  • 오류 확률: 검증자가 거짓 증명을 수락할 확률(errQUERY)은 매우 낮으며, $(1−δ^∗+(logn)⋅ϵ)ℓ$로 표현된다. 여기서 $\delta^*$는 실제 거리이고, ℓ은 반복 횟수이다.

DEEP 기법을 통해 건전성 오류(err)를 획기적으로 낮췄다는 것이 중요하다. DEEP-FRI는 one-and-a-half-Johnson Function을 활용한 ‘존슨 경계’를 사용하여, 거짓 증명에 대한 수락 확률을 $(max(1−δ(0),ρ)+o(1))^ℓ$까지 낮출 수 있다.

DEEP-ALI

DEEP 기법을 대수적 연결 IOP(ALI) 프로토콜에 적용하여 건전성을 개선하는 방법이다.

영지식 증명 시스템은 복잡한 계산 문제를 다항식의 근접성 문제로 변환한다(Arithmetization). 이러한 변환의 목표는 거짓된 입력에 대해(거짓된 prover에 대해) 다항식이 코드로부터 매우 멀리 떨어져 있음을 보장하는 것이다. 이러한 간극($γ)$이 클수록, FRI와 같은 근접성 프로토콜의 건전성이 높아진다.

그런데 기존의 ALI 프로토콜은 이 근접성 간극($γ$)이 1/8보다 작다. 이 간격이 작으면 거짓 증명을 잡아내기 어려워지므로 이를 좀 더 키우는 것이 필요하다.

DEEP-ALI는 기존의 ALI가 가지는 한계를 “몫 연산(quotienting)”을 활용하여 해결한다. 프로토콜의 전체적인 진행 과정을 다음과 같다.

1. 증명자 입력: Prover는 증인 다항식의 평가값인 함수 $f$를 제출한다.
2. 무작위 계수: Verifier는 무작위 계수 α를 증명자에게 보낸다.
3. 제약 함수 생성: Prover는 $α$와 $f$를 이용해 제약 조건들을 결합한 새로운 함수 $g_α$를 생성한다.
4. '도메인 밖' 질의: 검증자는 무작위 값 $z$를 선택하여 $f$의 평가값과 $g_α$의 추정값 $b_{\alpha,z}$를 요청한다.
5. 몫 연산: 검증자는 몫 연산을 적용하여 새로운 함수 $h_1$과 $h_2$를 만든다.
6. 근접성 테스트: 검증자는 RPT(리드-솔로몬 근접성 테스트) 프로토콜을 사용하여 $h_1$이 $RS[F_q, D, \dots]$에 가깝고, $h_2$가 $RS[F_q, D', \dots]$에 가깝다는 것을 증명한다

DEEP-ALI의 속성

DEEP-ALI는 기존 ALI 프로토콜에 비해 여러 가지 이점을 제공한다.

• 건전성: 기존 ALI 프로토콜의 근접성 간극(proximity gap)은 1/8보다 작았지만 , DEEP-ALI는 몫 연산을 통해 이 간극을 $1−ρ$까지 향상시킨다.

• 질의 복잡도: 검증자가 질의하는 필드 원소의 수가 $∣M∣[citestart]⋅Q$에서 $O(∣M∣+Q)$로 줄어들어 효율성이 향상된다.

• 검증자 복잡도: 검증자의 산술 복잡도가 $\Omega(Q \cdot T_{arith})$에서 $O(Q+T_{arith})$로 개선된다.

Reference

DEEP FRI

STARK(Scalable Transparent ARgument of Knowledge)는 trusted setup이 필요 없는 영지식 증명 기술이다. STARK는 타원 곡선이나 복잡한 암호화 가정을 사용하지 않고, 해시 함수와 정보 이론을 기반으로 하기 때문에 더 투명하다.

STARK는 Succinctness과 Transparency을 제공하지만, 증명 크기가 수백 킬로바이트로 ZK-SNARK보다 크다는 트레이드오프가 존재한다. 그러나 이는 신뢰가 중요한 블록체인 환경에서 매우 유용하다.

STARK는 크게 3단계를 통해서 이뤄진다. 해당 과정에 대해 알아보자.

1단계 : Arithmetization

우리가 증명하고자 하는 복잡한 계산의 무결성을 증명하기 위해, 계산 과정을 다항식으로 변환하는 Arithmetization 단계를 거친다.

Execution Trace를 통해서 머신에서 실행되는 모든 단계를 기록한다.

• 데이터 열(Data Columns): 각 클럭 주기에서 레지스터의 내부 상태를 기록(계산의 중간 결과값을 담는 곳)
• 제어 열(Control Columns): 초기화와 종료 지점을 표시하는 데 사용( 계산의 흐름을 제어)
• 누산기 열(Accumulator Columns): 전체 RISC Zero 프로토콜에서 메모리 에뮬레이션을 처리

그리고 각 단계에서 계산의 유효성을 검증하기 위한 규칙을 도입한다. 이는 계산 과정이 올바른지 확인하는 것이다. 각 규칙은 다항식으로 작성되고, 다항식이 만족되면 0으로 처리된다. 이러한 계산 규칙은 항상 사용되는 것이 아니라 특정 부분에서만 사용되므로 selector와 결합되어 사용된다. 예를 들어 $(s)(a+b-c)$를 살펴볼 때, 규칙이 적용되어 s가 1이라면, $(1)(a+b-c)$되어 $a+b-c=0$인지 확인한다. 반대로, 규칙이 적용되지 않아 s가 0이면 해당 규칙을 무시된다.

여기서 중간 결과들을 Algebraic Execution Trace(AET)라고 부르며 제약 조건들의 집합을 Algebraic Intermediate Representation (AIR)이라고 한다.

이후에 영지식 프로토콜을 구현하기 위해 증명 과정에서 사용자의 실제 데이터를 숨기기 위한 엔트로피를 추가한다.

Trace Polynomial은 실행 흔적의 데이터 열을 압축한 대수적 표현이다. INTT(Inverse Number Theoretic Transform)를 흔적 column 데이터에 실행하여 이 다항식의 계수를 얻는다

예시의 표는 8개의 column으로 구성되어 있으므로, 최대 차수가 7인 다항식이 나오고, 특정 지점에서의 평가값이 원래의 데이터와 정확히 일치한다.

Trace polynomial이 생성된 이후, 보안을 위해 더 넓은 도메인의 데이터를 활용해서 Reed-solomon encoding을 진행한다. 기존의 점들이$5^{12∗i} \pmod{97}$로 이루어진 8개의 점이었다면, $5^{3∗i} \pmod{97}$ 인 32개의 점으로 확대하는 저차 다항식 확장(Low-Degree Extension)을 실행한다. 이러한 Reed-solomon encoding은 중복성을 추가하여 작동한다.. 만약 원래 실행 흔적에 오류가 있었다면, 이 오류는 더 큰 점 집합에 걸쳐 증폭된다. 이는 검증자가 오류를 훨씬 쉽게 감지하게 하고 프로토콜의 건전성을 향상시킨다.

2단계: Commitment

이전 1단계에서 얻은 Trace Polynomial을 통해서 다항식이 바뀌지 않음을 증명하는 Commit을 진행해야한다. RS 확장이 영지식과 잘 작동하도록 하기 위해, 우리는 trace domain과 commitment domain이 겹치지 않도록 해야한다. 따라서 prover는 shift 연산을 통해서 각 trace polynomial을 평가한다.

이러한 shift 연산을 통해서 모든 trace 데이터를 변장한다.(숨긴다) 우리는 변장된 흔적에 대한 정보만 공개하며, 우리가 추가한 무작위 패딩은 공격자가 변장된 흔적과 실제 흔적 사이의 어떤 연결도 추론할 수 없다.

그리고 이 다항식을 Commit하기 위해 각 값들을 해시해서 머클 트리의 리프 노드로 만든다. 그리고 리프 노드들을 짝지어 연결하는 과젖을 통해 최종 머클 루트를 생성하고, 이 머클 루트를 제출해 commitment를 만든다. $d_1$의 경우 column에 있는 값들을 각각 해시하여 leaf로 만들어 $d_1$의 머클루트를 구하는 것이다.

우리는 다수의 제약 조건을 하나로 압축하여 계산 부담을 줄일 수 있다. 이를 위해, 우리는 하나의 새로운 열을 추가하여 우리의 제약 다항식을 단일한 혼합 제약 다항식(mixed constraint polynomial)으로 혼합한다.

Prover가 제어 다항식과 데이터 다항식에 대한 머클 루트를 커밋한 후, 이 머클 루트들은 엔트로피로 사용되어 무작위로 제약 혼합 매개변수 α1을 생성한다.

$c_i$를 제약 다항식이라고 하면, 우리는 $C(x)=\alpha_{1}^0*c_0(x)+\alpha_{1}^1c_1(x)+ \dots + \alpha_{1}^5c_5(x)$로 하나의 제약 다항식을 생성한다. $c_i$가 어떤 입력 $x$에서 0으로 평가된다면, C 또한 0으로 평가될 것이다.

모든 제약 조건을 만족하는 다항식을 넣었을 때, 제약 다항식의 값이 0이 되어야하기 때문에 Vanishing Polynomial(Z(x))을 만들어 몫 다항식(Q(x))를 만든다. 그럼 아래와 같은 식이 성립한다.

$$ C(x) = Z(x) ⋅ Q(x) $$

이 과정을 통해 Prover는 여러개의 제약 다항식을 trace data가 만족한다는 걸 증명하는 것이 아니라, 하나의 혼합 제약 다항식이 몫 다항식으로 분리되고, 그 몫 다항식이 저차 다항식이다라는 것을 증명하는 것으로 바뀐다.

3단계: FRI

결국 우리의 목표는 $Q(x)$가 저차다항식이라는 것을 증명해야한다. 이를 위해 $Q(x)$를 Reed-solomon encoding으로 저차식 확장하여 머클트리를 만들고 특정점에서의 확인을 통해서 올바른지 확인한다.

이 과정은 크게 Commit과 Query 2단계로 구분된다.

Commit

Commit 단계에서는 “Split-and-Fold”라는 기법으로 차수를 재귀적으로 줄여가며 결국 상수항의 커밋을 제공한다.

Split의 경우에는 짝수항과 홀수항으로 쪼갠다.

만약 $f_0​(x)=19+56x+34x^2+48x^3+43x^4+37x^5+10x^6+0x^7$라는 식을 Split한다고 할 때, 짝수와 홀수 차수를 가진 것들나눈다.

$f_{0,even​}(x)=19+34x+43x^2+10x^3$

$f_{0,odd}​(x)=56x+48x^3+37x^5+0x^7$

그리고 이후에 Fold 과정을 거친다. 이 식을 $f_{0,mid}= 19+34x^2+43x^4+10x^6 + x(56+48x^2+37x^4+0x^6)$ 으로 합친다.

그 후 어떤 x 대신에 random한 값 r을 사용해서 두 식을 하나의 식으로 합쳐서 $f_1$을 생성한다.

$f_1​(x)=f_e​(x^2)+r⋅f_o​(x^2)$

$f_1​(x) = 19+34x+43x^2+10x^3 + 12⋅(56+48x+37x^2+0x^3)$

$f_1​(x)=12+28x+2x^2+10x^3$

최종적으로 Split-and-Fold를 거치면서 차수가 원래보다 1/2이 된 것을 확인할 수 있다.

이 과정을 결과가 상수항이 나올 때까지 진행한다.

Query

Verifier는 무작위로 지점($g$)를 선택하여 prover에게 각 라운드의 다항식 평가값($f_i(g^{2^i}),f_i(−g^{2^i})$)을 요청한다. Verifier는 locality라는 핵심 속성을 활용하여, 한 라운드의 평가값이 이전 라운드의 두 평가값과 일관적인지 확인한다. 즉, $f_i(x^2)$가 $f_{i-1}(x)$와 $f_{i-1}(-x)$로 계산한 값과 같은지 비교한다.

$$ {f_i(x^2) = \frac{r_i + x}{2x} f_{i-1}(x) + \frac{r_i - x}{2(-x)} f_{i-1}(-x)} $$

만약 모든 지점에서 일관성이 확인되면, 검증자는 ACCEPT한다. 단 한 번이라도 불일치가 발견되면 REJECT한다.

STARK의 활용

STARKnet

STARKnet은 복잡한 계산을 이더리움 메인넷에서 분리하여 실행함으로써 이더리움의 확장성을 높이는 레이어 2 솔루션이다. 특히, STARKnet은 ZK-Rollup이라는 기술을 사용하여 이더리움의 확장성 문제를 해결한다.

ZK-Rollup은 수많은 오프체인 트랜잭션을 하나로 묶어, 그 유효성을 수학적으로 증명하는 영지식 증명(ZK-Proof)을 생성하여 온체인에 제출하는 기술이다. STARKnet은 이 영지식 증명을 생성하기 위해 STARK 기법을 사용한다.

STARKnet에서 STARK의 사용

STARKnet은 트랜잭션을 처리하고 증명을 생성하는 데 다음과 같은 방식으로 STARK 기술을 사용한다.

1. 계산의 다항식화: STARKnet은 수십만 건의 트랜잭션과 그 실행 과정을 대수적 실행 추적(AET)이라는 데이터 목록으로 변환한다. 이 AET는 다시 하나의 거대한 추적 다항식으로 변환된다.
2. 논리적 증명: 추적 다항식이 트랜잭션 규칙(제약 조건)을 올바르게 따랐는지 확인하기 위해, STARK는 $c(x) = Z(x) ⋅ q(x)$와 같은 다항식 등식으로 논리를 검증한다.
3. 효율적인 압축: STARKnet의 핵심은 이 모든 계산을 매우 간결한 증명으로 압축하는 것이다. 여기서 Split-and-Fold와 Reed-Solomon 기법이 활용됩니다.

Reed-Solomon과 Split-and-Fold의 활용

Reed-Solomon: 오류 증폭과 확률적 검증

STARKnet은 수십만 건의 트랜잭션에 대한 추적 다항식을 생성한다. 만약 트랜잭션 중 단 하나라도 오류가 있다면, 그 오류는 다항식 전체에 걸쳐 오류 증폭을 일으킨다. Reed-Solomon의 원리는 이 증폭된 오류를 감지하는 데 사용된다.

검증자는 수십만 개의 트랜잭션이 담긴 다항식의 모든 지점을 확인할 필요 없이, 무작위로 소수의 지점(예: 16개)만 검사한다. 만약 이 지점들 중 하나라도 오류가 있다면, 전체 계산이 잘못되었음을 높은 확률로 확신할 수 있다.

Split-and-Fold: 다항식의 차수 감소

STARKnet에서 트랜잭션의 수가 늘어날수록 다항식의 차수는 기하급수적으로 커진다. Split-and-Fold는 이 거대한 다항식의 차수를 획기적으로 줄여 검증을 간결하게 만든다.

Split-and-Fold는 추적 다항식의 차수를 매 라운드마다 절반씩 줄여나갑니다. 이 과정을 반복하여 원래의 복잡한 다항식을 최종적으로는 매우 낮은 차수의 다항식으로 압축합니다. 검증자는 이 최종 다항식만 확인하면 되므로, 검증에 필요한 시간과 자원이 획기적으로 줄어듭니다.

StarkWare의 StarkEx 플랫폼을 통해 구현된 프로젝트

dYdX

dYdX는 이더리움 기반의 탈중앙화 파생상품 거래소. 거래량이 매우 많고 빠른 처리가 필수적인 서비스

• STARK 활용: dYdX는 StarkEx를 이용해 오프체인에서 모든 거래를 처리하고, 그 유효성을 STARK 증명으로 묶어 이더리움에 정산한다다. 이를 통해 수십만 건의 거래를 낮은 비용으로 빠르게 처리할 수 있다.

Immutable X

Immutable X는 이더리움에서 NFT(대체 불가능 토큰) 및 웹3 게임을 위한 확장성 솔루션

• STARK 활용: Immutable X는 STARK를 활용해 사용자들이 수수료(gas fee) 없이 NFT를 민팅하고 거래할 수 있도록 한다. 수많은 민팅 및 거래 데이터를 하나의 STARK 증명으로 압축하여 이더리움에 제출함으로써, 네트워크 혼잡을 피하고 대규모 게임 경제를 가능하게 한다.

Sorare

Sorare는 유명 축구선수 NFT를 기반으로 한 판타지 스포츠 게임이다.

• STARK 활용: Sorare는 STARK를 사용해 선수 카드 민팅, 카드 거래 등 게임 내 주요 온체인 작업을 처리한다. 플레이어들은 이더리움 메인넷의 높은 수수료와 느린 속도에 구애받지 않고 게임을 즐길 수 있다.

Reference

BSBHR18b: Scalable, transparent, and post-quantum secure computational integrity STARK by Hand Anatomy of a STARK

“코드 한 줄을 고쳤을 뿐인데, 전 세계 수백 명의 사람을 다시 모아 ‘Ceremony’을 치러야 한다면 믿으시겠습니까?”

불과 몇 년 전, 초기 영지식 증명(ZK) 프로젝트들이 겪었던 악몽 같은 현실이었다. 당시 ZK의 표준이었던 Groth16은 압도적인 성능을 자랑했지만, 한 번 설계하면 수정이 불가능했다. 버그를 고치거나 기능을 추가하려면 수개월의 시간과 막대한 비용을 들여 보안 설정(Trusted Setup)을 처음부터 다시 해야만 했다.

이러한 경직성은 블록체인의 핵심 가치인 ‘빠른 업데이트’와 ‘확장성’을 가로막는 가장 큰 장벽이었다. 이에 따라 개발자들은 생각했다. “그냥 소프트웨어 업데이트하듯이, 한 번 세팅해놓고 프로그램만 갈아 끼울 수는 없을까?”

PlonK는 바로 이 질문에서 탄생했다. ZK의 패러다임을 ‘하드웨어’에서 ‘소프트웨어’로 전환시킨 이 혁신적인 프로토콜이 어떻게 영지식 증명의 대중화를 이끌었는지, 그 작동 원리를 파헤쳐 보겠다.

1. PlonK란 무엇인가: 범용성을 향한 도약

PlonK는 “한 번의 설정으로 다양한 회로를 커버할 수 있다”는 범용성(Universality)을 핵심 무기로 하는 영지식 증명 프로토콜이다. 이름조차 복잡한 약어(Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge)로 되어 있지만, 핵심은 ‘Oecumenical(보편적인, 범용적인)’이라는 단어에 있다. 기존 방식들은 회로의 로직이 조금만 바뀌어도 암호학적 설정을 처음부터 다시 해야 하는 ‘회로 종속적(Circuit-specific)’ 구조였지만, PlonK는 충분히 큰 범위의 SRS를 한 번 생성해두면 그 안에서 회로가 달라져도 재설정이 필요 없는 ‘범용적(Universal)’ 구조를 갖추고 있다.

이 때문에 개발자들이 회로를 훨씬 자유롭게 구성할 수 있게 되었고, 2019년 Aztec 팀이 제안한 이후 zkSync, Polygon zkEVM, Scroll 등 현재 대부분의 ZK 롤업 프로젝트들이 Plonkish 계열 프로토콜을 기반으로 사용하고 있다.

2. Groth16과의 차이점

그렇다면 PlonK가 Groth16과 비교해 어떤 차이를 갖는지 살펴보자.

Groth16의 근본적인 한계는 회로 종속적(Circuit-specific)인 신뢰 설정이었다.

Groth16은 증명 크기가 매우 작고 검증 속도도 가장 빠른 축에 속한다는 강점이 있다. 그러나 회로의 로직이 조금만 달라져도 매번 새로운 SRS(Structured Reference String)를 생성해야 한다는 치명적인 제약을 가지고 있다. 이 SRS를 만드는 과정이 바로 ‘Trusted Setup’이며, 이때 생성되는 비밀 값, 즉 ‘독성 폐기물(Toxic Waste)’이 유출되면 시스템 전체의 보안성이 붕괴된다.

따라서 프로젝트가 업데이트될 때마다 전 세계의 참가자들을 모아 안전한 생성·파기 과정을 수행하는 복잡한 “의식(ceremony)”을 반복해야 했고, 이는 유지보수를 심각하게 어렵게 만드는 족쇄였다.

PlonK는 이 문제를 범용적이고 업데이트 가능한(Universal & Updatable) 신뢰 설정으로 해결했다.

PlonK는 충분히 큰 최대 차수(max degree)를 가진 ‘Universal SRS’를 한 번 생성해두면, 그 범위 안에서는 회로가 변경되더라도 SRS를 다시 만들 필요가 없다. 즉, 새로운 기능을 추가하거나 로직을 수정하더라도 매번 의식을 치를 필요 없이 단지 회로를 다시 컴파일하고 배포하면 된다.

비록 증명 크기와 검증 비용이 Groth16보다 약간 증가하는 트레이드오프가 있지만, 개발자가 다양한 회로를 유연하게 설계하고 반복적으로 업데이트할 수 있다는 점에서 훨씬 실용적이다. 이러한 특성 덕분에 PlonK는 ZK 기술이 연구 단계에서 벗어나 산업 현장에서 실질적으로 활용되는 기반이 되었다.

3. PlonK가 증명하려는 것: 다항식을 통한 무결성

PlonK의 목표는 단순하다.

“Prover가 어떤 계산을 올바르게 수행했다는 사실을, 입력값을 공개하지 않고도 증명하는 것.”

그리고 그 접근 방식은 Groth16과 유사하게, 모든 계산 조건을 다항식(polynomial)으로 변환해 검증 가능한 형태로 만드는 데서 출발한다. 하지만 PlonK는 Groth16이 고정된 회로 구조만을 다루는 한계를 넘어서기 위해, 게이트·와이어·연결 관계 전체를 훨씬 유연한 방식으로 다항식화한다.

어떤 프로그램에서 아래와 같은 계산을 수행했다고 주장한다고 한다.

$$ C(w) = y $$

PlonK 역시 이 계산 전체를 산술 회로(Arithmetic Circuit)로 변환하며, 모든 연산은 하나의 게이트(Gate), 게이트 간 데이터 전달은 와이어(Wires)로 나타난다. 다만 PlonK는 Groth16보다 훨씬 일반화된 단일 게이트 형태를 사용해 더 다양한 회로 구조를 단 하나의 방정식으로 처리할 수 있도록 설계되어 있다.

아래 그림은 $(x \cdot y) + x = z$라는 단순한 계산을 회로 형태로 나타낸 것이다. Gate1을 자세히 살펴보면,

와이어 $w_1(x)$ 와 $w_2(x)$가 입력값 $x$와 $y$를 전달하고, 출력 와이어 $w_3(x)$가 $x\cdot y$ 값을 다음 게이트로 넘긴다. 와이어를 통해 값이 흐르고, 각 게이트가 정확한 연산을 하는지를 보여주는 것이다.

이를 좀 더 일반화해서 표현하면, PlonK는 모든 게이트 연산을

$$ q_L a + q_R b + q_O c + q_M(ab) + q_C = 0 $$

라는 하나의 통합된 방정식으로 표현한다. 곱셈이면 $ab - c = 0$, 덧셈이면 $a + b - c = 0$같은 형태가 되어, Prover는 각 게이트가 정확한 연산을 수행했다는 사실을 증명해야 한다.

하지만 개별 게이트의 연산이 올바르다고 해서 전체 계산이 정확하다고 말할 수는 없다. 와이어의 값이 잘 전달되는지 확인해야 한다. 게이트 1의 출력이 게이트 2의 입력으로 정확히 연결되어야 하고, 동일한 입력이 여러 게이트에서 재사용될 때는 값이 완전히 동일해야 한다. 예컨대 $w_3 = a_2, w_1 = w_4$ 같은 연결 규칙들이 모두 보장되어야 한다. Groth16도 이런 동일성 제약을 다항식으로 표현했지만, PlonK는 이보다 더 강력한 구조를 도입한다. 즉, 수많은 wiring 관계를 하나하나 제약으로 기록하는 대신, 전체 wiring을 하나의 순열(permutation)로 추상화해버리는 것이다.

예를 들어, 와이어값이 ($w_1, w_2, w_3, w_4$) 순서로 배치되어 있고, 실제 회로 wiring에 따라 ($w_4, w_3, w_2, w_1$)로 대응된다고 하자. PlonK는 이러한 값의 자리 이동 전체를 단일 순열 σ로 표현하고, 이를 검증하기 위해 Grand Product Polynomial $z(X)$를 사용한다.

$$ \sigma(1) = 4 \\sigma(2) = 3 \ \sigma(3) = 2 \ \sigma(4)=1 $$

원래 값 목록을 $f(i)$, 순열 적용 뒤의 값 목록을 $g(\sigma(i))$ 라 하고, 여기에 치팅 방지를 위해 $\beta, \gamma$로 랜덤화한$f'(i), g'(\sigma(i))$ 를 사용한다. 그러면 PlonK가 최종적으로 확인하고 싶은 것은 다음 하나의 조건뿐이다:

$$ \prod_{i=1}^{n} \frac{f'(i)}{g'(\sigma(i))} = 1. $$

이 식은 사실 매우 직관적이다. 모든 대응 위치에서 값이 정확히 일치했다면 비율 $f'(i)/g'(\sigma(i))$는 모두 1이 되고, 전체 곱 역시 1이 된다. 반대로 하나라도 mismatching이 생기면 곱은 절대 1이 될 수 없다. 이 누적 비율을 관리하는 것이 바로 Grand Product Polynomial Z(X)이다.

$$ Z(1) = 1,\qquad Z(i+1) = Z(i)\cdot \frac{f'(i)}{g'(\sigma(i))} $$

즉, $Z$는 각 단계에서의 비율을 계속 곱해가며 누적한 값을 담는 다항식이다. 만약 wiring이 전부 올바르다면 마지막 점에서 $Z(n+1)=1$이 성립하게 된다. 이 하나의 보조 다항식만으로 회로 전체 wiring consistency를 검증할 수 있게 되며, 결과적으로 복잡한 복사·연결 제약들이 하나의 “순열 항등식”으로 압축된다. 이 부분이 PlonK가 Groth16보다 훨씬 더 범용적 회로를 다룰 수 있게 해주는 기술적 핵심이다.

이처럼 PlonK는 회로 전체를 단 몇 개의 다항식으로 요약한다. 모든 게이트의 왼쪽 입력 값은 $a(X)$, 오른쪽 입력 값은 $b(X)$, 출력 값은 $c(X)$라는 세 개의 긴 다항식으로 인코딩된다. 겉보기에는 Groth16과 비슷해 보이지만, PlonK는 고정된 회로에 묶이지 않고 자유로운 wiring과 다양한 게이트 구성을 수용할 수 있도록 이 구조를 훨씬 더 유연하게 확장한다.

4. PLONK prover 1-5 Round

이제 증명자가 최종 증명 $\pi_{SNARK}$를 생성하기 위해 수행하는 구체적인 5개 라운드(Rounds)에 대해 설명한다. 각 라운드는 검증자(Verifier)로부터 받은 챌린지에 응답하고, 다음 라운드에 필요한 증명 구성 요소를 구축하는 과정을 포함한다. (PlonK는 비상호작용 영지식 증명이므로 실제로는 검증자로 부터 챌린지를 받지 않고 피아트-샤미르 휴리스틱을 통해 생성된 챌린지를 사용한다.)

Round 1 : Wire Polynomial Commitment 생성

증명자(Prover)는 알려진 모든 와이어 값(위트니스)을 수학적으로 다루기 쉬운 형태로 변환하는 것으로 시작한다. 이 단계의 목표는 회로의 전체 실행 상태를 세 개의 다항식으로 압축하고, 검증자에게 이를 비밀리에 커밋(commit)하는 것이다.

증명자는 회로의 왼쪽, 오른쪽, 출력 와이어에 해당하는 값들 $(a_i,b_i,c_i)_{i=1}^n$을 보간(interpolate)하여 세 개의 Wire polynomial) $a(X),b(X),c(X)$를 만든다. wire polynomial 를 다음과 같이 계산한다. 이때, 영지식을 위해, 랜덤한 블라인딩 스칼라 $b_1,...,b_6$를 선택한다.

$a(X) = (b_1 X + b_2) Z_H(X) + \sum_{i=1}^{n} w_i L_i(X)$

$b(X) = (b_3 X + b_4) Z_H(X) + \sum_{i=1}^{n} w_{n+i} L_i(X)$

$c(X) = (b_5 X + b_6) Z_H(X) + \sum_{i=1}^{n} w_{2n+i} L_i(X)$

• $\sum_{i=1}^{n} w_i L_i(X)$ : 와이어 값들을 다항식 평가값으로 인코딩 라그랑주 기저 다항식 $L_i(X)$는 특정 점($i$)에서만 1이되고 나머지에서는 0이되는 다항식이다. 라그랑주 기저 다항식을 활용하여 $H$의 각 지점에서 순서대로 정확히 $w_1, w_2, ...$ 값을 갖게 한다.

• $(b_1 X + b_2) Z_H(X)$ : 영지식성 추가

  소멸 다항식(vanishing polynomial) $Z_H(X)=X^n−1$ 을 곱해준다. $Z_H(X)$는 우리가 관심 있는 영역(도메인 H)에서는 값이 0이 되는 다항식이다. 이를 활용해서 $H$에서 증명의 유효성(soundness)에는 영향을 주지 않으면서, $H$밖에서의 다항식 값을 무작위화한다. 이는 비밀 와이어 값 $w_i$이 노출되는 것을 방지한다.

이렇게 블라인딩 처리된 최종 다항식들을 Kate-Zaverucha-Goldberg (KZG) 다항식 커밋먼트 스킴을 사용하여 커밋한다. 즉, 신뢰할 수 있는 설정(SRS) 값 $[s_i]_1$을 이용해 아래의 커밋먼트를 계산한다.

$$ [a]:=[a(s)]_1,[b]:=[b(s)]_1,[c]:=[c(s)]_1 $$

최종적으로 블라인딩 처리된 증명 다항식의 커밋먼트 $[a],[b],[c]$를 verifier에게 보내고,

Round 2 : Permutation Polynomial Commitment 생성

모든 와이어들이 올바르게 연결되었다는 제약(copy constraint)을 단일 다항식 Z(X)으로 압축하고, 이 다항식을 블라인딩 처리하여 커밋한다.

모든 와이어 연결 정보를 담고 있는 순열 다항식(permutation polynomial) $Z(X)$를 구성한다. 이 다항식은 “누적 곱(running product)” 방식으로 만들어지며 모든 와이어 연결이 올바른지를 확인하는 역할을 하게 된다.

Z(X)의 시작점은 $Z(g_1)=1$로 정의한다. 이후 $i=1,…,n$에 대해, 다음과 같은 재귀적인 관계로 $Z(g_{i+1})$ 값을 계산하여 $Z(X)$를 구성한다.

$Z(g_{i+1}) := Z(g_i)\cdot \frac{(a_i + \beta g_i + \gamma)(b_i + \beta k_1 g_i + \gamma)(c_i + \beta k_2 g_i + \gamma)}{(a_i + \beta S_{\sigma_1}(g_i) + \gamma)(b_i + \beta S_{\sigma_2}(g_i) + \gamma)(c_i + \beta S_{\sigma_3}(g_i) + \gamma)}$

이 수식은 두 다중집합이 서로의 순열 관계인지 확인하는 과정이다.

• 분자: 게이트에 연결된 각 와이어의 값($a_i,b_i,c_i$)과 원래 위치 정보를 결합하여 하나의 항으로 만든다.

  $g_i,k_1g_i,k_2g_i$는 각각 $a, b, c$ 와이어의 원래 위치 인덱스를 나타낸다.

• 분모 : 게이트에 연결된 각 와이어의 과 순열 후 위치 정보를 결합한다. 여기서 $S_{σ1}(g_i),S_{σ2}(g_i),S_{σ3}(g_i)$는 실제 순열 $\sigma$를 인코딩한 다항식으로, 와이어 값들이 연결되어 이동한 후의 위치 인덱스를 나타낸다.

• $\beta, \gamma$: 이 무작위 챌린지들은 증명자가 순열 관계를 속이는 것을 방지하고, 각 와이어 값을 위치 정보와 강력하게 묶어준다.

최종적으로 $Z(X)$를 유형별로 묶어서 정리하면 다음과 같다:

$z(X) = \underbrace{(b_7X^2 + b_8X + b_9)Z_H(X)}{\text{Part 1}} + \underbrace{L_1(X)}{\text{Part 2}} + \underbrace{\sum_{i=1}^{n-1} \left( L_{i+1}(X) \prod_{j=1}^{i} \frac{f(\omega^{j-1})}{g(\omega^{j-1})} \right)}_{\text{Part 3}}$

• Part 1 (블라인딩) : 무작위 값을 결합하여 영지식성을 보장

  Round 1과 마찬가지로, 영지식을 위해 랜덤 스칼라 $b_7,b_8,b_9$를 선택하여 $Z(X)$를 블라인딩 처리한다.

• Part 2 : 초기 조건 설정

  누적 곱(Accumulated Product)이 반드시 1에서 시작하도록 강제하는 역할을 한다. $X=1$일 때, Part1은 $Z_H(X)$에 의해 0이 되고, Part3는 라그랑주 선형 방정식의 성질로 인해 0이 된다. 이를 통해 순열 다항식 $Z(X)$의 초기 조건이 1이 되는 것을 확인한다.

• Part 3 : 누적 곱 확인

  모든 와이어의 연결이 올바르다면, 분자에 있는 모든 항의 다중집합과 분모에 있는 모든 항의 다중 집합은 순서만 다를 뿐 정확히 동일하다. 따라서 누적 곱을 계속해 나가면 분자와 분모가 서로 상쇄되어 최종적으로 $Z(g_{n+1})=1$이 된다. (Schwartz-Zippel 보조정리에 기반한 확률적 검증 방법)

증명자(Prover)는 이렇게 얻어진 순열 다항식 $Z(X)$에 대해 KZG 커밋먼트를 수행하여, 그룹 원소 $[z]_1$을 계산하고, 이를 검증자(Verifier)에게 보낸다.

$$ [Z]:=[Z(s)]_1 $$

Round 3 : 몫 다항식 커밋먼트 (Quotient Polynomial Commitment)

증명자는 피아트-샤미르 휴리스틱을 통해 새로운 무작위 챌린지 $\alpha$를 받는다. 이 $\alpha$를 사용하여 지금까지의 모든 gate constraint와 copy constraint를 단일 다항식으로 통합하고, 이를 소멸 다항식 $Z_H(X)$로 나눈다. 그 결과가 몫 다항식 $t(X)$이다.

$$ t(X) = \frac{f(X)}{Z_H(X)} $$

여기서 분자 f(X)는 다음과 같이 구성된다.

$\begin{aligned} f(X) &:= \underbrace{\Big( a(X) q_L(X)+ b(X) q_R(X)+ a(X) b(X) q_M(X)+ c(X) q_O(X)+ PI(X)+ q_C(X) \Big)}{\text{Part1 Gate Constraints}} \ \ &\quad + \alpha \cdot \underbrace{\Bigg( \begin{aligned} &\big(a(X) + \beta X + \gamma\big)\big(b(X) + \beta k_1 X + \gamma\big)\big(c(X) + \beta k_2 X + \gamma\big)Z(X) \ -&\big(a(X) + \beta S{\sigma_1}(X) + \gamma\big)\big(b(X) + \beta S_{\sigma_2}(X) + \gamma\big)\big(c(X) + \beta S_{\sigma_3}(X) + \gamma\big)Z(X\omega) \end{aligned} \Bigg)}{\text{Part2 Permutation Constraints}} \ \ &\quad + \alpha^2 \cdot \underbrace{\Big(L_1(X)(Z(X)-1) \Big)}{\text{Part3 Permutation Start Constraints}} \end{aligned}$

• Part1 : 게이트 제한조건 PlonK의 게이트 방정식이다. 모든 연산이 모든 게이트에서 올바르게 수행되었다면, 이 다항식은 $H$의 모든 지점에서 0이어야 한다. $PI(X)$는 공개 입력을 처리하는 항으로, 상수항 $q_C(X)$를 더하는 것을 포함한다.
• Part2 : 와이어 값 제한조건 라운드 2의 재귀 관계식 $z(X\omega) = z(X) \cdot f(X)/g(X)$를 $f(X)z(X) - g(X)z(X\omega) = 0$ 형태로 변환한 것이다.
• Part3 : 초기 조건 확인 $z(X)$가 1에서 시작해야 한다는 제약($z(1)=1$)을 강제한다. $L_1(X)$는 $X=1$에서만 1이고 $H$의 다른 모든 지점에서는 0이므로, 이 항은 $z(1)-1=0$이라는 제약을 $H$ 전체로 확장한다.

이렇게 계산된 t(X)는 차수가 매우 높기 때문에(3n 이상), 효율적인 처리를 위해 이를 n−1차 다항식 세 개로 분할한다.

$$ t(X) = t_{lo}(X) + X^n t_{mid}(X) + X^{2n} t_{hi}(X) $$

이 세 조각 각각에 대해 KZG 커밋먼트를 수행하여, 그룹 원소 $[t_{low}]1, [t{mid}]1, [t{high}]1$을 계산하고 분할된 몫 다항식들의 커밋먼트 $[t{lo}], [t_{mid}], [t_{hi}]$를 검증자에게 보낸다.

$$ [t_{lo}] := [t_{lo}(s)]1,\qquad[t{mid}] := [t_{mid}(s)]1,\qquad[t{hi}] := [t_{hi}(s)]_1 $$

Round 4 : Polynomial Evaluation

지금까지 증명자는 자신의 주장을 여러 다항식($a, b, c, z, t$)으로 공식화하고 이에 대해 암호학적으로 커밋했다. 검증자는 이 다항식들이 특정 항등식을 만족하는지 검증해야 하지만, 다항식 전체를 전송받아 확인할 수는 없다. 이 문제를 해결하기 위해 PlonK는 슈워츠-지펠 보조정리(Schwartz-Zippel Lemma)를 활용한다.

여기서 슈워츠-지펠 보조정리는 서로 다른 두 다항식이 존재할 때, 이 두 다항식이 무작위로 선택된 한 점에서 만날 확률이 0에 가깝다는 것이다. 이 보조정리를 활용하여, 다항식 전체를 비교하는 대신 무작위로 한 점을 선택하여 그 점에서 방정식이 성립하는지 여부를 검증한다. 라운드 4는 이 무작위 지점에서 필요한 모든 다항식 평가값을 계산하고 공개한다.

증명자는 피아트-샤미르 휴리스틱을 통해 이전의 모든 정보를 바탕으로 새로운 무작위 챌린지 $\zeta$를 생성한다. 이 $\zeta$는 모든 다항식이 평가될 무작위 평가 지점이다. 증명자는 $\zeta$와 그 "이웃" 지점인 $\zeta\omega$에서 자신의 다항식들을 평가하여 다음 값들을 계산하고 검증자에게 전송한다.:

• $a(ζ),b(ζ),c(ζ)$ : 세 개의 wire 다항식
• $S_{σ1}(ζ),S_{σ2}(ζ)$ : 두 개의 permutation 다항식
• $z(\zeta\omega)$ : permutation constrain 검증에 필요한 Z(X)다항식은 ζ의 shifted point인 $ζw$에서 평가한다.

$\zeta$와 $\zeta\omega$ 지점에서의 각 다항식 평가 값(evaluation)들을 $(\overline{a}, \overline{b}, \overline{c}, \overline{s_{\sigma 1}}, \overline{s_{\sigma 2}}, \bar{z}_{\omega})$을 검증자에게 보낸다. 검증자에게 보낸다.

Round 5 : 선형화 다항식 계산 및 최종 평가

라운드 4에서 증명자는 여러 값에 대한 평가값을 공개했다. 그런데 검증자는 이 값들이 라운드 1-3에서 커밋된 다항식들의 실제 평가값인지 아직 알 수 없다. 라운드 5는 이 모든 평가 주장들을 하나의 효율적인 증명으로 일괄 처리(batch)하여, 공개된 값들의 유효성을 최종적으로 입증하는 것이다.

증명자는 피아트-샤미르 휴리스틱을 통해 두 개의 새로운 무작위 챌린지 $v$와 $u$를 생성한다. $v$는 동일한 지점($\zeta$)에서의 평가들을 일괄 처리하는 데 사용되며, $u$는 서로 다른 지점($\zeta$와 $\zeta\omega$)에서의 평가들을 일괄 처리하는 데 사용된다. 이 챌린지들을 사용하여, 증명자는 두 개의 오프닝 증명 다항식 $W_\zeta(X)$와 $W_{\zeta\omega}(X)$를 구성한다:

첫 번째 Opening Proof Polynomial $W_ζ(X)$계산

첫 번째로 계산하는 Opening Proof Polynomial은 $W_ζ(X)$이다. 이는 여러 다항식들의 무작위 선형 결합이다. 각 다항식은 특정 평가 지점인 ζ에서 평가된 값들과 결합된다.

$W_\zeta(X) = \frac{1}{X - \zeta} \left( \underbrace{r(X)}{\text{Part 1}} + \underbrace{v(a(X) - \bar{a}) + v^2(b(X) - \bar{b}) + v^3(c(X) - \bar{c}) + v^4(S{\sigma1}(X) - \bar{s}{\sigma1}) + v^5(S{\sigma2}(X) - \bar{s}{\sigma2})}{\text{Part 2}} \right)$

• Part1 : 선형화 다항식

  $$ r(X) = [\bar{a}\bar{b}q_M(X) + \bar{a}q_L(X) + \bar{b}q_R(X) + \bar{c}q_O(X) + PI(\zeta) + q_C(X)] \

  • \alpha [ (\bar{a} + \beta\zeta + \gamma)(\bar{b} + \beta k_1\zeta + \gamma)(\bar{c} + \beta k_2\zeta + \gamma)z(X) \

  • (\bar{a} + \beta\bar{s}{\sigma 1} + \gamma)(\bar{b} + \beta\bar{s}{\sigma 2} + \gamma)(\bar{c} + \beta S_{\sigma 3}(X) + \gamma)\bar{z}_\omega ] \

  • \alpha^2 [ (z(X) - 1)L_1(\zeta) ] \

  • Z_H(\zeta) ( t_{lo}(X) + \zeta^n t_{mid}(X) + \zeta^{2n} t_{hi}(X) ) $$

    이 다항식은 라운드 3의 $t(X)$와 관련된 복잡한 항등식을 $\zeta$에 대해 선형화(linearizing)한 결과이다. 즉, $\zeta$에서의 평가값들($\bar{a}, \bar{b}, \dots$)을 상수로 취급한다. $r(X)$는 라운드 3에서 커밋된 $t_{low}, t_{mid}, t_{high}$와 라운드 4에서 공개된 평가값들 간의 일관성을 검증한다.

• Part2 : 배치 평가된 값들

  이것은 $a(\zeta)=\bar{a}, b(\zeta)=\bar{b}$ 등과 같은 지점 $\zeta$에서의 모든 평가 주장들을 무작위 가중치 $v$의 거듭제곱을 사용하여 하나의 다항식으로 결합한다.

• $(X-\zeta)$로 나눗셈: 만약 모든 주장이 사실이라면, 괄호 안의 다항식은 $X=\zeta$일 때 0이 되어야 gks다. 따라서 $(X-\zeta)$로 나누어떨어지며, 그 몫이 바로 $W_\zeta(X)$가 된다.

두 번째 Opening Proof Polynomial $W_{ζω}(X)$계산

$$ W_{\zeta\omega}(X) = \frac{z(X) - \overline{z_{\omega}}}{X-\zeta\omega} $$

여기서 z(X)는 copy constraint를 나타내는 다항식이고, $\overline{z_{\omega}}$는 이 다항식이 평가된 값이다. 또한 $\zeta\omega$는 무작위 평가점이다. Plonk에서는 copy constraint를 한 칸씩 전진하며 점검하는데, 현재점 $ζ$에서의 관계가 다음점 $ζω$에서도 맞는지 확인해야 하기에 두 곳에서 값을 열어보는 절차가 필요한 것이다. 즉, 이 다항식은 copy constraint가 올바르게 성립하는지 확인하기 위해 사용된다. Plonk Prover Algorithm의 최종 결과는 아래와 같다.

최종적으로 증명자는 마지막으로 두 오프닝 증명 다항식 $W_\zeta(X)$와 $W_{\zeta\omega}(X)$에 대해 KZG 커밋먼트를 수행하여, 그룹 원소 $[W_\zeta]_1$ **와 $[W{\zeta\omega}]_1$을 계산하여 검증자에게 전송한다.

이제 라운드 1부터 5까지 생성된 모든 구성 요소(커밋먼트, 평가값, 오프닝 증명)를 모아, 최종 증명 $\pi_{SNARK}$가 완성되어 검증자에게 전송된다.

$$ \pi_{SNARK} = \left( [a]1,[b]_1,[c]_1,[z]_1,[t{lo}]1,[t{mid}]1,[t{hi}]1,[W{\zeta}]1,[W{\zeta\omega}]1, \overline{a},\overline{b},\overline{c},\overline{s{\sigma1}},\overline{s_{\sigma2}},\overline{z_{\omega}} \right) $$

5. PLONK Verifier : 모든 것을 검증하는 하나의 방정식

증명자(Prover)가 생성한 최종 증명 $\pi_{SNARK}$는 여러 커밋먼트(commitments), 평가값(evaluation values), 오프닝 증명(opening proofs)을 포함하여 구성된다. 검증자의 역할은 이 증명을 사용하여 증명자가 실제로 유효한 연산을 수행했는지 검증한다. 이때 증명자의 비밀 정보(witness) 없이, 매우 효율적인 방식으로 검증을 수행해야 한다.

PlonK 검증자는 모든 것을 한 번에 검증할 수 있는 단일 최종 방정식을 구성하고, 단순히 이 방정식이 성립하는지 여부만 확인한다.

검증자가 증명의 유효성을 확인하기 위해 수행하는 일련의 연산 과정을 순서대로 살펴보자.

과정

검증자는 증명 $\pi_{SNARK}$와 공개 입력값 $(w_i)_{i \in [\ell]}$을 수신하고, 다음 단계를 통해 검증을 수행한다.

1. 증명 유효성 확인 및 챌린지 복구

   • 다음과 같이 두 문장으로 깔끔하게 정리할 수 있습니다.수신된 증명 $\pi_{SNARK}$를 구성하는 모든 데이터가 유효한 형식을 갖추었는지 검증한다. 구체적으로 9개의 그룹 요소와 6개의 필드 요소가 각각 정의된 공간인 $\mathbb{G}_1^9$과 $\mathbb{F}^6$에 올바르게 속해 있는지 확인한다.
   • Prover가 전송한 각 공개 입력 값($w_i$)이 정의된 필드 $\mathbb{F}$의 범위 내에 존재하는지 유효성을 검사한다. 이후 증명자와 동일한 방식으로 공개 입력과 증명 요소를 순차적으로 해시(Hash)하여 트랜스크립트를 재구성하고, 이를 통해 모든 무작위 챌린지($\beta, \gamma, \alpha, \zeta, \nu, u$)를 복구한다

2. 소멸 다항식 및 라그랑주 다항식 평가

   • 무작위 챌린지 $\zeta$에서 소멸 다항식을 평가한다. : $Z_H(ζ)=ζ^n−1$

     소멸 다항식은 부분군 $H$의 모든 원소에서 0이 되는 성질을 가지며, 슈워츠-지펠 보조정리에 의해 무작위 점 $\zeta$에서 증명자의 다항식이 $Z_H(\zeta)$로 나누어떨어지는지 확인하는 것만으로 전체 도메인에서의 유효성을 확률적으로 보장한다. 즉, 이 값이 0이 됨을 확인함으로써 증명자가 생성한 제약 조건이 모든 지점에서 올바르게 만족됨을 효율적으로 검증할 수 있다.

   • 무작위 챌린지 $\zeta$에서 라그랑주 다항식을 평가한다. : $L_1(\zeta) = \frac{\omega(\zeta^n - 1)}{n(\zeta - \omega)}$

     $L_1(X)$는 첫 번째 지점(X=1)에서만 1이 되고 나머지에서는 0이 되는 특수한 다항식으로, 순열 다항식 $z(X)$의 시작점이 1이어야 한다는 경계 조건($z(1)=1$)을 강제하는 역할을 한다. 만약 시작값이 올바르지 않다면 $L_1(\zeta)$가 포함된 항이 소멸하지 않아 전체 검증이 실패하게 되므로, 이를 통해 누적 곱 연산의 무결성을 확인한다.

   • 무작위 챌린지 $\zeta$에서 공개 입력 다항식 $PI(X)$를 평가한다. : $PI(\zeta) = \sum_{i \in [\ell]} w_iL_i(\zeta)$

     $PI(X)$는 검증자가 각 공개 입력값 $w_i$에 라그랑주 기저 다항식을 결합하여 직접 재구성하는 다항식으로, 증명자가 공개 입력값을 임의로 조작하는 것을 원천적으로 방지한다. 이 다항식을 $\zeta$에서 평가하여 최종 검증식에 반영함으로써, 약속된 공개 입력값들이 회로 연산에 올바르게 포함되었는지 확실하게 인증한다.

1. 일괄 선형 다항식 구성

   검증자는 스칼라 곱셈을 절약하기 위해, r을 상수항과 비-상수항으로 나눈다. : $r(X)=r_0+r^′(X)$

   • 상수항 $r_0$계산 : $r_0 := PI(\zeta) - L_1(\zeta)\alpha^2 - \alpha(\overline{a} + \beta\overline{s_{\sigma1}} + \gamma)(\overline{b} + \beta\overline{s_{\sigma2}} + \gamma)(\overline{c} + \gamma)\overline{z_{\omega}}$

   • 비상수항 계산 : Prover가 제출한 모든 증명 다항식들의 커밋먼트를 하나의 값으로 합친다.

     • 챌린지 $u$를 사용하여 $r(X)$의 비상수 부분과 $z(X)$를 결합한 커밋먼트인 $[D]_1:=[r^′]_1+u⋅[z]_1$을 계산한다

       $\begin{aligned}[D]1 := ;& \underbrace{\Big( \overline{a}\overline{b}\cdot [q_M]_1 + \overline{a}\cdot [q_L]_1 + \overline{b}\cdot [q_R]_1 + \overline{c}\cdot [q_O]_1 + [q_C]_1 \Big)}{\text{Part 1: 게이트 논리 확인}} \\&+ \underbrace{\Bigg( \begin{aligned} &\Big( (\overline{a}+\beta\zeta+\gamma)(\overline{b}+\beta k_1\zeta+\gamma)(\overline{c}+\beta k_2\zeta+\gamma)\alpha + L_1(\zeta)\alpha^2 + u \Big)\cdot [z]1 \ &- (\overline{a}+\beta\overline{s{\sigma1}}+\gamma)(\overline{b}+\beta\overline{s_{\sigma2}}+\gamma)\alpha\beta\overline{z_{\omega}}\cdot [s_{\sigma3}]1 \end{aligned} \Bigg)}{\text{Part 2: 순열 제약 확인}} \\&+ \underbrace{\Bigg( - Z_H(\zeta)\Big([t_{lo}]1 + \zeta^n [t{mid}]1 + \zeta^{2n}[t{hi}]1\Big) \Bigg)}{\text{Part 3: 몫 다항식 확인}}\end{aligned}$

       • 게이트 논리 확인 : 회로의 각 게이트가 올바른 연산을 수행했는지를 확인하는 식

         $$ \overline{a}\overline{b} \cdot [q_M]_1 + \overline{a} \cdot [q_L]_1 + \overline{b} \cdot [q_R]_1 + \overline{c} \cdot [q_O]_1 + [q_C]_1 $$

       • 순열 제약 확인 : 회로의 와이어 연결이 올바른지를 확인하는 순열 확인 논리를 담은 식

         $$ \begin{aligned} &\Big( (\overline{a}+\beta\zeta+\gamma) (\overline{b}+\beta k_1\zeta+\gamma) (\overline{c}+\beta k_2\zeta+\gamma)\alpha \ &\qquad + L_1(\zeta)\alpha^2 + u \Big)\cdot [z]1 \ &;- (\overline{a}+\beta\overline{s{\sigma1}}+\gamma) (\overline{b}+\beta\overline{s_{\sigma2}}+\gamma) \alpha\beta\overline{z_{\omega}}\cdot [s_{\sigma3}]_1 \end{aligned} $$

       • 몫 다항식 확인 : 증명자가 보낸 몫 다항식($t(X)$)이 영 다항식($Z_H(X)$)으로 나누어떨어짐을 증명

         $$ -Z_H(\zeta)([t_{lo}]1 + \zeta^n \cdot [t{mid}]1 + \zeta^{2n} \cdot [t{hi}]_1) $$

     • 챌린지 $v$를 사용하여 $[D]_1$과 $\zeta$에서 평가된 모든 다항식 커밋먼트를 함께 배치 처리한 최종 결합 커밋먼트인 전체 일괄 다항식 커밋먼트 $[F]_1$을 계산한다.

       $$ [F]1 := [D]_1 + \nu \cdot [a]_1 + \nu^2 \cdot [b]_1 + \nu^3 \cdot [c]1 + \nu^4 \cdot [s{\sigma2}]_1 $$

       • $[D]_1$: 앞서 계산한 값으로, 게이트 제약, 순열 제약, 그리고 몫 다항식 제약이 모두 결합된 다항식 커밋먼트. 이 자체로 이미 프로토콜의 핵심적인 논리를 담고 있다.
       • $ν,ν^2,ν^3,ν^4$: 이들은 검증자가 라운드 5에서 계산한 무작위 챌린지 ν의 거듭제곱. 이 무작위 값들은 증명자가 특정 항에만 맞춰서 속이는 것을 방지하는 역할을 한다.
       • $[a]_1,[b]_1,[c]_1$: 라운드 1에서 증명자가 보낸 와이어 다항식의 커밋먼트.
       • $[sσ_2]_1$: 순열 제약 확인에 사용되는 순열 다항식의 커밋먼트.

2. 일괄 평가값 계산

   그룹-인코딩된 일괄 평가($[E]1$)를 계산한다.

   $$ [E]1 := -r_0 + \nu\overline{a} + \nu^2\overline{b} + \nu^3\overline{c} + \nu^4\overline{s{\sigma1}} + \nu^5\overline{s{\sigma2}} + u\overline{z{\omega}} $$

   증명자가 보낸 평가값들을 무작위 챌린지($ν,u$)를 이용하여 하나의 그룹 원소로 선형 결합한다. $[E]_1$는 모든 평가값들을 하나의 값으로 합친 뒤, 최종 검증식(12단계)에 사용되어 증명자의 주장들이 올바르게 '개봉(open)'되었는지 확인하는 역할을 한다.

3. 모든 평가들을 일괄적으로 검증

   결국 verifier가 검증하는 것은 ‘증명자가 제출한 정보가 검증자가 재구성한 정보와 일치한다'는 것이다. 검증자는 모든 것을 결합하여 단일 페어링 방정식을 확인한다. 이 방정식은 배치된 KZG 오프닝 증명이 유효한지 검증한다.

   아래의 식에서 좌변은 증명자가 주장하는 ‘압축된 다항식 정보’이고, 우변은 증명자가 제출한 평가값들($[F]_1, [E]_1$)을 기반으로 검증자가 재구성한 것이다.

   $e([W_\zeta]_1 + u \cdot [W{\zeta\omega}]_1, [x]_2) \stackrel{?}{=} e(\zeta \cdot [W\zeta]_1 + u\zeta\omega \cdot [W{\zeta\omega}]_1 + [F]_1 - [E]_1, [1]_2)$

왜 이 디자인인가?

전체 검증자(Verifier) 과정은 효율성에 초점을 맞추고 있다.

• 간결성 (Succinctness): 검증자는 회로의 크기(n)에 비례하는 연산을 수행하지 않는다. 모든 계산은 증명의 크기에만 의존하며, 이는 거의 상수 시간(near-constant time)에 가깝다.
• 비상호작용성 (Non-interactive): 검증은 제출된 증명만으로 완료될 수 있으며, 증명자와 상호작용할 필요가 없다
• 일괄 처리 (Batching): 여러 개의 KZG 개봉 증명들이 압축되어 단 두 번의 페어링 연산만으로 검증된다. 이것이 바로 PlonK의 빠른 검증 속도를 가능하게 하는 핵심적인 최적화 기술이다.

Reference

1. PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge
2. ZKP MOOC Lecture 5: The Plonk SNARK
3. PLONK by hand
4. EXPLORING PLONK

ECC의 수학적 기반 및 이론

1. 실수체에서의 타원 곡선

실수체 $\mathbb{R}$에서의 타원 곡선은 Weierstrass(바이어슈트라스) 표준형으로 정의된다.

$$ 𝑦^2=𝑥^3+𝑎𝑥+𝑏 $$ 여기서 $a, b \in \mathbb{R}$이며, 다음 판별식 조건을 만족해야 한다.

$$ Δ=−16(4𝑎^3+27𝑏^2) \neq 0 $$ 이 조건은 곡선이 특이점(singular point)을 가지지 않도록 보장한다.

• 곡선이 자기 자신과 교차하지 않음
• 뾰족한 점(cusp)이 없음
• 모든 점에서 접선이 정의됨

2. 유한체에서의 타원 곡선

암호학에서는 계산 효율성과 보안성을 모두 확보하기 위해 실수체 대신 유한체(finite field) 위에서 타원 곡선을 정의한다.

소수체 $\mathrm{GF}(p)$에서의 타원 곡선 $$ y^2≡x^3+ax+b \pmod{n} $$

• $p$는 소수
• $a, b \in \mathrm{GF}(p)$

특이점이 없을 조건: $$ 4a^3+27b^2\neq0 \pmod{n} $$ $p > 16$일 때 위 조건은 $\Delta \not\equiv 0 \pmod{p}$와 동일하며, $p \leq 16$인 경우는 $p = 2$만 고려하면 된다.

3. 타원 곡선 상의 군 구조

군의 성질 타원 곡선 상의 점들과 덧셈 연산은 아벨군(Abelian group)을 형성한다. 아벨군의 조건은 아래의 그림과 같다. 아벨군은 연산에 대해 닫힘, 결합법칙, 항등원, 역원, 교환법칙을 모두 만족하는 대수적 구조를 가진 집합이다. 이 조건들을 충족한다는 것은, 집합 내의 어떤 두 원소를 연산해도 결과가 다시 집합 안에 있으며(닫힘), 연산 순서를 바꿔도 결과가 같고(교환법칙), 괄호의 위치를 바꿔도 결과가 동일하며(결합법칙), 연산에 영향을 주지 않는 특별한 원소(항등원)가 존재하고, 모든 원소에 대해 연산 결과를 항등원으로 만드는 짝(역원)이 존재한다는 것을 의미한다.

점의 덧셈 연산

1) $P \neq Q$인 경우(점의 덧셈)

1. 기울기 계산 $$ m = \frac{y_2 - y_1}{x_2 - x_1} $$
2. 새로운 점 계산 $$ x_3 = m^2 - x_1 - x_2 $$ $$ y_3 = m(x_1 - x_3) - y_1 $$

2) $P = Q$인 경우 (점의 곱셈)

1. 기울기 계산 $$ m = \frac{3x_1^2 + a}{2y_1} $$
2. 새로운 점 계산 $$ x_3 = m^2 - 2x_1 $$ $$ y_3 = m(x_1 - x_3) - y_1 $$

스칼라 곱셈과 이산 로그 문제

1) 스칼라 곱셈 타원 곡선 위 점 P에 정수 k를 곱하는 연산은 점 P를 k번 더하는 것을 의미한다. $$ kP = \underbrace{P + P + \cdots + P}_{k\text{번}} $$ 2) 음수 연산 점 P의 역원인 −P는 P의 y좌표에 부호를 바꾸어 얻을 수 있다. $$ −P=(P_x,−P_y) $$ 3) 관련 보안 문제 스칼라 곱셈의 역연산은 ECC 보안의 핵심 기반이다. 타원 곡선 위 점 $P$와 $Q=kP$가 주어졌을 때, 정수 k를 찾는 문제는 타원 곡선 이산 로그 문제(ECDLP, Elliptic Curve Discrete Logarithm Problem)라고 불린다. 이 문제가 계산적으로 매우 어렵기 때문에 ECC의 보안성이 보장된다.

타원 곡선 이산 로그 문제 (ECDLP)

ECDLP(Elliptic Curve Discrete Logarithm Problem)는 타원 곡선 암호 시스템(ECC)의 보안을 지탱하는 핵심적인 문제이다.

• 입력: 타원 곡선 E 위에서 정의된 기준점 P와 P를 여러 번 더해 얻은 점 Q (Q=kP).

• 출력: Q=kP를 만족하는 정수 k를 찾는 것이다.

• 어려움: 점 P와 Q가 주어졌을 때 k를 찾는 것은 매우 어렵지만, P와 k가 주어졌을 때 Q를 계산하는 것은 상대적으로 쉽다.

현재 보안 수준 ECDLP의 난이도는 곡선의 비트 수에 따라 결정된다. 256비트 타원 곡선의 경우, 공격 복잡도는 약 $O(2^{128})$이다. 이는 현재 기술로는 계산이 불가능한 수준이다.

실제 사용 예시:

• 비트코인: secp256k1 (256비트)
• 이더리움: secp256k1 (256비트)
• TLS/SSL: P-256 (256비트)

ECDLP는 일반적인 이산 로그 문제(DLP)보다 더 높은 보안 효율성을 제공한다. 예를 들어, 256비트 ECC 키는 약 3072비트 RSA 키와 동등한 보안 수준을 갖는다. 이는 더 짧은 키를 사용하면서도 높은 보안을 유지할 수 있다는 장점이 있다.

주요 타원 곡선 암호 시스템

ECDSA (Elliptic Curve Digital Signature Algorithm)

ECDSA는 타원 곡선 암호(ECC)를 기반으로 하는 디지털 서명 알고리즘이다.

키 생성 과정

1. 타원 곡선 $E$와 생성원 $G$를 선택한다.
2. 타원 곡선 위의 유한한 점들의 총 개수인 위수 n을 계산한다.
3. $1<d<n$ 범위의 정수 d를 프라이빗 키로 선택한다.
4. $Q=dG$를 계산하여 점 $Q$를 퍼블릭 키로 설정한다.
5. $(Q, E, G, n)$을 공개하고, d는 비공개로 보관한다.

서명 생성 알고리즘

입력: 메시지 m, 프라이빗 키 d 출력: 서명 (r,s)

1. 메시지 m을 해시하여 $h = H(m)$를 계산한다.
2. $1<k<n$ 범위의 임의의 정수 k를 선택한다.
3. 점 $R=kG$를 계산한다.
4. $r=R$의 x좌표 $\pmod {n}$을 계산한다.($r=P_x \pmod{n}$ 계산)
5. $s=k^{−1}(h+dr) \pmod {n}$을 계산한다.
6. $r\neq0$이고 $s\neq0$인지 확인하고, 그렇지 않으면 2단계로 돌아간다.
7. 서명 $(r, s)$를 반환한다.

서명 검증 알고리즘

입력: 메시지 m, 서명 (r,s), 퍼블릭 키 Q 출력: 서명의 유효성

1. $r$과 $s$가 $[1,n−1]$ 범위에 있는지 확인한다.
2. 메시지 m을 해시하여 $h = H(m)$를 계산한다.
3. $w=s^{−1} \pmod{n}$, $u_1=hw\pmod{n}$, $u_2=rw\pmod{n}$을 계산한다.
4. 점 $P=u_1G+u_2Q$를 계산한다.
5. $v=P$의 x좌표 $\pmod{n}$을 계산한다.($x = X_x \pmod{n}$)
6. $v=r$이면 서명이 유효하고, 아니면 무효하다.

보안 고려사항

랜덤성의 중요성: 서명 생성 시 사용되는 랜덤 정수 k가 재사용되면 프라이빗 키 d가 노출될 수 있다.

Sony PlayStation 3 사례: ECDSA 구현 시 k 값을 고정적으로 사용하여 프라이빗 키가 노출되는 보안 취약점이 발생한 사례가 있다. 이는 k의 랜덤성이 ECDSA의 보안에 얼마나 중요한지 보여준다.

package ecdsa

import (
    "errors"
    "github.com/decred/dcrd/dcrec/secp256k1/v4"
    "github.com/ffddz/upside-homework/crypto"
    "math/big"
)

var (
    order     = new(big.Int).Set(secp256k1.S256().N)
    halforder = new(big.Int).Rsh(order, 1)
    // 안전하지 않게 k를 동일한 것을 사용
    k = new(big.Int).SetUint64(0x123456789abcdef)
)

func Sign(privateKey *secp256k1.PrivateKey, hash []byte) (*big.Int, *big.Int, error) {
    privkey := privateKey.ToECDSA()
    N := order
    inv := new(big.Int).ModInverse(k, N)
    r, _ := privkey.Curve.ScalarBaseMult(k.Bytes())
    r.Mod(r, N)

    if r.Sign() == 0 {
        return nil, nil, errors.New("calculated R is zero")
    }

    e := crypto.HashToInt(hash)
    s := new(big.Int).Mul(privkey.D, r)
    s.Add(s, e)
    s.Mul(s, inv)
    s.Mod(s, N)

    // enforce low S values, see bip62
    // bip62을 반영하지 않은 ECDSA 서명을 만들기 위해 주석처리
    //if s.Cmp(halforder) == 1 {
    //    s.Sub(N, s)
    //}

    if s.Sign() == 0 {
        return nil, nil, errors.New("calculated S is zero")
    }
    return r, s, nil
}

다음과 같이 k값을 고정하였을 경우, 같은 k값을 이용한 서명 두개를 이용하여 프라이빗 키 획득할 수 있다.

package ecdsa

import (
    "math/big"

    "github.com/decred/dcrd/dcrec/secp256k1/v4"
    "github.com/ffddz/upside-homework/crypto"
)

func AttackGetPrivateKey(r1, s1, r2, s2 *big.Int, msg1, msg2 []byte) (*secp256k1.PrivateKey, error) {
    n := new(big.Int).Set(secp256k1.S256().N)
    hash1 := crypto.HashToInt(msg1)
    hash2 := crypto.HashToInt(msg2)
    t1 := new(big.Int).Mul(s2, hash1)
    t2 := new(big.Int).Mul(s1, hash2)
    t3 := new(big.Int).Sub(t1, t2)
    r_inv := new(big.Int).ModInverse(r1, n)
    t4 := new(big.Int).Sub(s1, s2)
    t4 = new(big.Int).ModInverse(t4, n)
    tp := new(big.Int).Mul(t3, r_inv)
    tp.Mul(tp, t4)
    tp.Mod(tp, n)
    var modNScalar secp256k1.ModNScalar
    modNScalar.SetByteSlice(tp.Bytes())
    p := secp256k1.NewPrivateKey(&modNScalar)

    return p, nil

}

ECDH (Elliptic Curve Diffie-Hellman)

키 교환 프로토콜

그림은 Alice와 Bob이 퍼블릭 키를 교환하여 공유 비밀키를 생성하는 ECDH 프로토콜을 나타냄
출처 : SADDLE: Secure Aerial Data Delivery with Lightweight Encryption

1. Alice와 Bob이 공통 타원 곡선 $E$와 생성원 $G$ 합의
2. Alice: 프라이빗 키 a 선택, 퍼블릭 키 $A = aG$ 계산
3. Bob: 프라이빗 키 b 선택, 퍼블릭 키 $B = bG$ 계산
4. Alice와 Bob이 퍼블릭 키 교환
5. Alice: 공유 프라이빗 키 $K = aB = abG$ 계산
6. Bob: 공유 프라이빗 키 $K = bA = baG$ 계산
7. K를 대칭키 암호의 키로 사용

Reference

1. https://developer-mac.tistory.com/83
2. https://www.themoonlight.io/ko/review/ecdsa-cracking-methods
3. https://alpha.velog.io/@dohoon8/Cryptography-3.-Elliptic-Curve%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC
4. https://alpha.velog.io/@dohoon8/Cryptography-4.-ECDH%EC%99%80-ECDSA%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC-pgbr3e5a

커밋먼트는 암호학에서 사용되는 중요한 개념으로, 특정 값이나 메시지에 '잠금'을 걸어 상대방에게 전달하고, 필요할 때만 그 내용을 공개할 수 있게 해주는 원시 요소(primitive)이다.

정의: 송신자가 메시지 m을 잠긴 상태로 수신자에게 보내면, 수신자는 상자 안의 내용을 알 수 없다. 송신자만이 나중에 '열쇠(opening information)'를 제공하여 메시지를 공개할 수 있다.

활용 예시 하나를 살펴보면, 이전에 보았던 Schnorr Signature에서 Prover는 무작위 r을 사용하여 $A=g^r$을 미리 commit해 둔다. 이 과정을 통해 증명자는 챌린지-응답 단계에서 메시지가 변조되지 않았음을 보장한다. 이는 특정 값을 고정해두고, 그 다음 challenge-response 과정을 통해 특정 값을 자신이 알고 있음을 증명하는 것이다.

Why Commitment

Commitment는 영지식 증명, 디지털 서명, 검증 가능한 비밀 공유를 통한 MPC(다자간 연산) 등 다양한 암호화 프로토콜에서 중요한 역할을 한다. 특히 영지식 증명에서는 다음의 두 가지 목적으로 사용된다.

1. 선택형 증명(Cut-and-Choose): 증명자가 여러 증명 후보에 커밋하고, 검증자가 이 중 일부를 선택하여 검증하도록 함으로써 효율성을 높인다.

2. 병렬화: 검증자가 자신의 선택 사항을 커밋먼트로 미리 명시하여, 증명자에게 추가 정보를 노출하지 않고도 증명 과정을 병렬로 진행할 수 있게 한다.

커밋먼트 프로토콜 단계

일반적으로 커밋먼트는 세 단계로 이루어진다.

• 셋업(Setup): 증명자와 검증자가 공통 시스템 매개변수에 합의한다.

• 커밋(Commit): 증명자는 메시지 m과 무작위 값 r을 이용해 커밋먼트 c를 계산한 후 검증자에게 보낸다.

• 오픈/검증(Open/Verify): 증명자가 $(m, r)$을 공개하면, 검증자는 이를 받아 커밋먼트 c가 올바른지 확인한다.

(보통 셋업을 제외하고, 커밋과 오픈/검증의 두 단계로 한다.)

커밋먼트 스킴의 주요 특성

커밋먼트 스킴은 아래와 같은 2가지 특성을 지닌다.

1. 은닉성(hiding) 또는 기밀성(confidentiality): open되기 전, 공격자가 커밋먼트 c를 보더라도 커밋 값에 대한 어떠한 정보도 알 수 없어야 한다. 즉, 공개 전에 m을 추측할 수 없어야 한다.

2. 결속성(binding): 당사자가 커밋 후 m을 다른 값으로 변경할 수 없다.

Pederson commitments scheme

     그림은 Pederson Commitments의 과정을 보여준다.
출처 : Formalising Σ-Protocols and Commitment Schemes Using CryptHOL

Pedersen Commitments은 이산 로그 문제(DLP)의 난이도에 기반한 간단하면서도 강력한 커밋먼트 스킴이다.

수학적 정의

매개변수 설정

• 소수 차수 q를 가진 유한군 G를 선택한다.
• G의 두 생성자 g,h를 선택한다. 이때 g에 대한 h의 이산 로그 $\log_g(h)$는 알려져 있지 않다.
• 시스템 매개변수는 $(G, q, g, h)$입니다.

커밋(Commit) 과정

• 0<s<q 인 비밀 정수 s에 대한 커밋먼트 c∈G 를 생성하려면, t ←$Z_q를 랜덤하게 샘플링하고 다음을 계산한다.(랜덤 값 t를 선택한다.)
• $c=C_{g,h}(s,t)=g^sh^t$

오픈(Open) 과정

• s와 t를 공개하면, 검증자는 $c=g^sh^t$를 확인하여 유효성을 검증한다.

Pedersen Commitments의 속성

• 결속성 (Computational Binding): 만약 송신자가 s와 다른 값 $s'$에 대해 동일한 커밋먼트 c를 만들 수 있다면, 즉 $g^s h^t = g^{s'} h^{t'}$이 성립한다면, 이는 $\log_g(h)$를 계산하는 것과 동등해진다. 결국 이산 로그 문제를 푸는 것과 같으므로, 페더슨 커밋먼트는 계산적 결속성을 가진다.

• 은닉성 (Perfect/Statistical Hiding): 랜덤 값 t는 $Z_q$에서 균등하게 샘플링된다. 커밋먼트 $c=g^sh^t$에서 $h^t$는 G의 균등한 랜덤 원소와 같다. 따라서 어떤 $s$와 $s'$에 대해서도 적절한 $t$와 $t'$를 선택하면 동일한 c를 만들 수 있다. 즉, 커밋먼트 c만으로는 s에 대한 어떠한 정보도 얻을 수 없다.(영지식 증명의 zero-knowledge(영지식성)과 유사한 개념) 따라서 페더슨 커밋먼트는 완전 은닉성을 가진다.

덧셈 동형성(Additive Homomorphism)

Pedersen Commitments가 가지는 특이한 속성에 대해 알아보자. Pedersen Commitments는 두 커밋먼트를 곱하면 커밋된 값들의 합에 대한 새로운 커밋먼트가 되는 특별한 성질을 가지고 있다. $$ c_1=g^{s_1}h^{t_1} $$ $$ c_2=g^{s_2}h^{t_2} $$ $$ c_1 * c_2=g^{s_1+s_2}h^{t_1+t_2} = C(s_1+s_2,t_1+t_2) $$

이러한 특성 덕분에, 커밋된 값들을 공개하기 전에 다양한 연산을 수행할 수 있어 영지식 증명 등에서 매우 유용하게 활용된다.

페더슨 커밋먼트의 유용한 속성들

페더슨 커밋먼트는 몇 가지 증명 프로토콜과 함께 사용될 수 있다.

비밀의 지식 증명(Proof of Knowledge of a Secret)

커밋먼트 $A=C_{g,h}(x,y)=g^xh^y$가 주어졌을 때, A는 x와 y 중 어느 것도 공개하지 않고 B에게 자신이 x와 y를 알고 있다는 것을 증명할 수 있다. 이는 페더슨 커밋먼트의 덧셈 속성이 악용되는 것을 방지하는 데 유용한 프로토콜이다.

$$ g^{s_1}h^{s_2}=g^{xk+t_1}h^{yk+t_2}=g^{xk}h^{yk}g^{t_1}h^{t_2}=(g^xh^y)^kT=A^kT $$ 이는 B를 속이기 위해서는 A가 이산 로그 문제를 풀어야 한다는 것을 의미하므로 안전하다.

동일 메시지 증명(Equal Opening)

같은 생성자 집합을 사용하여 비밀 $s$에 대한 두 커밋먼트 $$ c_{1} = C(s, t_{1}), \quad c_{2} = C(s, t_{2}) \quad (t_{2} \neq t_{1}) $$ A는 $c_{1}$과 $c_{2}$ 모두 같은 값 $m$에 커밋했다는 것을 증명할 수 있다. 페더슨이 제시한 가장 간단한 방법은 A가 $r = t_{1} - t_{2} \pmod{q}$를 Bob에게 공개하는 것이다. 이는 아래 식으로 인해 만족한다. $$ c_{1} c_{2}^{-1} = g^{s} h^{t_{1}} \cdot g^{-s} h^{-t_{2}} = g^{s-s} h^{t_{1} - t_{2}} = h^{t_{1} - t_{2}} = h^{r} $$

Reference

1. [Pedersen91] Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing (1991).
2. https://www.zkdocs.com/docs/zkdocs/commitments/pedersen/
3. https://www.cs.cornell.edu/courses/cs754/2001fa/129.PDF
4. https://www.zkdocs.com/docs/zkdocs/commitments/pedersen/
5. https://medium.com/@icostan/commitment-schemes-8b523d48aa1e
6. https://cseweb.ucsd.edu/classes/fa19/cse206A-a/LecCommit.pdf

해당 아티클은 J. Groth, "On the Size of Pairing-based Non-interactive Arguments."를 읽고 정리한 내용이다

Groth16은 zk-SNARK(영지식 간결 비대화형 지식 증명)의 한 종류로, 영지식 증명 시스템 중 가장 널리 사용되고 효율적인 프로토콜 중 하나이다. Groth16은 복잡한 계산의 유효성 증명을 하나의 다항식 방정식 문제로 변환한 후, 페어링(pairing) 연산을 사용하여 이 방정식의 해가 존재함을 간결하게 증명하는 방식으로 작동한다. (피노키오 프로토콜과 마찬가지로 A*B-C=HT를 증명하려고 하는데, 이때 사용하는 그룹을 3개로 줄여서 간결하게 작동한다.)

Groth16의 전체적인 과정은, 주어진 계산을 게이트 단위로 분해(Flattening) 하고, 이를 Rank-1 Constraint System(R1CS) 형태로 변환한 뒤, QAP을 이용해 모든 제약을

$A(x) \cdot B(x) - C(x) = H(x) \cdot Z(x)$

형태의 하나의 다항식 식으로 묶는다. 이후 페어링 기반 연산을 통해 이 식이 특정 점에서 성립함을 효율적으로 증명하고 검증한다.

Groth16의 알고리즘

Groth16도 NIZK 중 하나이므로 위에서 설명했던 4가지 알고리즘으로 구성된다.(Simulation의 경우에는 NIZK의 영지식을 증명하기 위한 이론적인 도구이므로 따로 설명하지 않는다.)

신뢰 설정(Trusted Setup)

증명자(Prover)가 증명에 필요한 요소들을 지수에서의 선형성만으로 구성하고, 검증자(Verifier)는 하나의 페어링 연산으로 검증할 수 있도록 공통된 기준점을 제공한다. 이를 위해 아무도 모르는 비밀 값(α,β,γ,δ,x)을 무작위로 선택한다. 이 비밀 값들이 '독성 폐기물(toxic waste)'이며, 이 값을 아는 사람은 위조 증명을 만들 수 있다. 따라서 이 값들은 즉시 파기되어야 한다.

CRS 구성:

• G1 그룹 원소:
  • [$x_i$]1 (다항식의 평가점)
  • $[γβu_i(x)+αv_i(x)+w_i(x)]_1$ (공개 입력)
  • $[δβu_i(x)+αv_i(x)+w_i(x)]_1$ (증인(witness) 등)
  • $[t(x)x_j]_1$ (t(x) 다항식)
• G2 그룹 원소:
  • $[x_i]_2$
  • $[β]_2,[γ]_2,[δ]_2$

Proof 구성

$$ π=([A]_1,[C]_1,[B]_2) $$

Groth16 증명 시스템에서 A,B,C는 Prover가 생성하는 최종 증명의 핵심 구성 요소이다. 이들은 단순한 행렬이 아니라, 증명에 사용된 witness를 숨기면서도 그 증거의 유효성을 검증자에게 확신시켜주는 암호학적 객체들이다. 이 객체들을 만드는 데에는 α, β, r, s와 같은 특별한 값들이 중요한 역할을 한다. 각각의 요소들의 역할에 대해 알아보자.

$$ [A]_1=[α+∑a_iu_i(x)+rδ]_1 $$

$$ [B]_2=[β+∑a_iv_i(x)+sδ]_2 $$

$$ [C]1 = \left[ \frac{\sum{i=l+1}^{m} a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)}{\delta} + As + rB - rs\delta \right]_1 $$

A,B,C의 역할: 여기서 말하는 A,B,C는 증명자가 생성하는 최종 증명(Proof)의 세 가지 핵심 원소이다. 이들은 계산 문제를 다항식 문제로 변환하는 QAP(Quadratic Arithmetic Program)의 결과물인 A(x),B(x),C(x) 다항식과 깊이 연관되어 있다. Prover는 자신만 알고 있는 값($a_i$)와 공통 참조 문자열(CRS)에 담긴 값들을 이용해 이 세 개의 원소를 계산한다. 결국, 이 A,B,C는 '내가 이 계산을 올바르게 수행했다'는 것을 검증자에게 보여주는 압축된 증거가 된다.

$\alpha$, $\beta$의 역할: α와 β는 마치 '암호학적 서명'과 같은 역할을 한다. 이 값들은 CRS를 생성할 때 만들어져 공개되는데, 검증자는 A와 B가 동일한 witness를 사용해 일관성 있게 만들어졌는지를 확인하는 데 αβ라는 특별한 항을 사용한다. 만약 Prover가 다른 witness를 사용해 A와 B를 만들려고 시도하면, 이 αβ 항이 검증 방정식에서 불일치를 일으키면서 검증이 실패한다.

어떻게 일관성을 강제하나? 검증자는 다음 형태의 pairing 검증식을 사용한다: 여기서 $e([\alpha]_1, [\beta]_2)$는 α와 β가 동시에 들어가야만 만족하는 고유한 항이다. A와 B가 동일한 witness로부터 만들어졌을 때만 이 pairing 식이 성립한다. 왜냐하면 A와 B의 상수항에 각각 α, β를 포함시키고, αβ 항이 곱으로 pairing에 등장하도록 함으로써, 둘 다 동일한 witness 기반 구조여야 αβ 조합이 QAP 나머지 항과 정확히 맞아떨어지게 한다. 만약 다른 witness 집합을 사용하면 αβ 항이 QAP 잔차와 맞지 않아 검증이 실패하도록 한다.

r,s 의 역할: r과 s는 증명에 '무작위성'을 불어넣는 값이다. Prover는 증명을 생성할 때마다 새로운 r과 s를 무작위로 선택하여 사용한다. 따라서 동일한 비밀 증거를 사용하더라도 매번 다른 형태의 증명(A,B,C 원소들의 값이 달라짐)이 생성될 수 있다. 이는 제3자가 증명 자체만으로 어떤 증거가 사용되었는지 추론할 수 없도록 만들어 영지식성(Zero-knowledge)을 보장한다.

Proof 최종 정리

1. $π_A∈G_1$: u(x)의 커밋

• $A=α+∑_{i=0}^ma_iu_i(x)+rδ$
  • $u(x)$ 다항식을 CRS의 선형 결합으로 지수에서 구성
  • $[α]_1$는 검증식 상수항
  • $r[δ]_1$는 영지식성(zero-knowledge)을 위한 블라인딩(blinding) 항, 같은 입력에 대해서도 매번 다른 증명을 생성하게 한다.

2. $π_B∈G_2$: v(x)의 커밋

• $B=β+∑_{i=0}^ma_iv_i(x)+sδ$
  • v(x) 다항식을 구성
  • 검증식 $e([A]_1, [B]_2)$에서 u(x)v(x) 항을 만들기 위해 πA와 짝을 이루도록 G2 그룹에 위치.
  • [β]2는 [α]1과 함께 상수항을 형성
  • s[δ]2는 영지식성을 위한 또 다른 블라인딩 항

3. $π_C∈G_1$: 제약 만족 + 블라인딩 상쇄

• $C_1 = \left[ \frac{\sum_{i=l+1}^{m} a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)}{\delta} + As + rB - rs\delta \right]_1$

  • $\frac{h(x)t(x)}{\delta}$: 핵심 제약식인 $u(x)v(x) - y(x) = h(x)t(x)$가 정확히 성립함을 인코딩
  • $\sum_{i>\ell} a_i \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta}$: 증인(witness)에 해당하는 와이어 값 $a_{i}$가 u,v,w 다항식에 일관되게 사용되었음을 강제
  • $As+rB−rsδ$: πA와 πB에 들어간 블라인딩 항 r,s가 검증식에서 정확하게 상쇄되도록 보정하는 역할

Verification

Groth16에서 verification의 핵심은 QAP 다항식 등식이 성립하는지를 확인하는 것이다. 이 등식은 다음과 같다.

$A(x)⋅B(x)−C(x)=H(x)⋅T(x)$

이 등식이 모든 게이트(제약 조건)에서 성립한다면, Prover가 올바른 witness를 사용했다는 것을 증명할 수 있다. 하지만 이 등식을 그대로 검증하기에는 너무 복잡하다. 따라서 Groth16은 이 등식을 페어링을 이용해 간단하게 만든다.

Verifier는 페어링의 성질 $e(g^a, g^b) = e(g, g)^{ab}$를 이용해 등식을 다음과 같이 변환한다.

$e([A(x)]_1,[B(x)]_2)⋅e([C(x)]_1,[1]_2)^{−1}=e([H(x)]_1,[T(x)]_2)$

이 복잡한 식에 α,β,γ,δ 같은 값들을 이용해 정리하고 압축한다. 페어링의 특성을 활용해 A,B,C 원소들이 witness와 public inputs에 대한 올바른 조합으로 만들어졌는지를 한 번에 검증할 수 있도록 설계된 것이다. 이 과정은 다음과 같은 최종적인 검증식으로 귀결되고, 아래의 식이 성립하면 증명을 통과한다.

$e(A,B)=e(\alpha,\beta) \cdot e(\sum_{i=1}^{l}P_i,\gamma) \cdot e(C,\delta)$

이 식에서는 총 4개의 페어링 연산이 사용된다.

1. $e(A,B)$: 증명 원소 A와 B에 대한 페어링
2. $e(α,β)$: CRS의 α와 β에 대한 페어링
3. $e(∑^{i=1}_lPi,γ)$: 공개 입력과 γ에 대한 페어링
4. $e(C,δ)$: 증명 원소 C와 δ에 대한 페어링

수식의 우변에 있는 세 개의 페어링 연산 결과들은 일반 곱셈 연산으로 결합되어 최종적으로 좌변의 결과와 비교된다.

페어링과 선형 방정식 페어링 연산은 다음과 같은 성질을 가진다. $e(g^a,h^b)=e(g,h)^{ab}$ 이 성질 덕분에, 페어링은 그룹에서의 지수 연산(덧셈)을 타겟 그룹에서의 곱셈으로 바꿀 수 있다. 이러한 성질을 활용해서 곱셈 형태의 연산을 덧셈 형태로 변환하여 복잡한 검증을 단순화할 수 있다.

상세과정

1. 좌변

$$ A=α+u(x)+rδ $$

$$ B=β+v(x)+sδ $$

따라서 pairing $e([A]_1,[B]_2)$ 에는 다음 항들이 포함된다.

• 핵심 상수항: e([α]₁, [β]₂)

• QAP 핵심항: e([u(x)]₁, [v(x)]₂)

• 블라인딩 교차항: $e([r\delta]_1, [s\delta]_2)$, $e([A]₁,[s\delta]_2)$, $e([r\delta]_1,[B]₂)$ 등 블라인딩 항과 QAP 항의 교차항

*2. 우변 *

1) 핵심 상수항: e([α]₁, [β]₂) 프로토콜의 규칙을 정의하는 고정된 값. 신뢰 설정(Trusted Setup)에서 미리 계산되어 검증 키(Verification Key)에 포함된다. 이는 증명자가 임의로 조작할 수 없는 구조적 앵커 역할을 한다.

2) 공개 입력 부분: e(Q_pub, [γ]₂) 공개 입력($a_i$)이 올바른지 확인하는 부분. Verifier는 공개된 입력 값들($a_0​,…,a_l​$)과 CRS의 일부인 $γ$관련 항들을 결합하여 $Q_{pub}$을 직접 계산한다. 이후 $[ \gamma ]_2$와 페어링하여, 공개 입력이 증명과 일치하는지를 확인한다.

3) 제약 조건 및 블라인딩 상쇄 부분: e([C]₁, [δ]₂) 증명([C]₁)과 검증 키([δ]₂)의 페어링을 통해, QAP의 제약 조건을 검증하고 좌변의 블라인딩 교차항을 제거한다. [C]₁ 안에는 다음 세 가지가 포함되어 있다.

① QAP 나머지 항 복구: $\frac{h(x)t(x)}{\delta}$항이 $$[\delta]_2$$와 만나 페어링 되면서 QAP의 핵심 조건인 $h(x)t(x)$가 복구된다.

② 증인(witness) 부분 검증: 증명자가 사용한 비밀 증인 값들이 일관성 있게 사용되었는지 확인하는 항이 포함되어 있다.

③ 블라인딩 상쇄 항: $As + rB - rsδ$ 항이 좌변에서 발생했던 모든 블라인딩 교차항과 정확히 반대 부호를 가지고 있어서, 최종적으로 모든 블라인딩 관련 항들이 완벽하게 상쇄된다.

3. 최종 결과

최종적으로 남는 것은:

1. $e([\alpha]_1, [\beta]_2)$상수항
2. 공개 입력 블록
3. $h(x)t(x)$를 통해 보장되는 $u(x)v(x)−y(x)=h(x)t(x)$ 성립 조건

결론 : $\pi_C$의 $+As+rB−rsδ$ 항은 단순한 꾸밈이 아니라, $\pi_A, \pi_B$의 블라인딩으로 인해 좌변에 생기는 잔여항을 우변에서 정확히 상쇄시키기 위한 필수 구성 요소이다.

Groth16을 이용한 Prover/Verify 과정

Prover

1. 입력: 공개 $a1,…,aℓ$, 증인 $aℓ+1,…,am$

2. 무작위 $r,s←Z_p$ 선택.

3. CRS 선형결합으로 $u(x)=∑_ia_iu_i(x), v(x)=∑_ia_iv_i(x), y(x)=∑_ia_iw_i(x)$ 를 지수에서 조립.

4. $A=α+u(x)+rδ,B=β+v(x)+sδ$ 계산.

5. $h(X)=(uv−y)/t$ 계산 → $δh(x)t(x)$ 조립.

6. $∑_{i>ℓ}a_iδβu_i(x)+αv_i(x)+w_i(x)$ 조립.

7. C=(5,6 결과)+$As+rB−rsδ$

8. 증명 출력:

   $π=([A]_1, [C]_1, [B]_2)$

Verifier

1. 공개 입력으로 $Q_{pub} := ∑_{i=0}^ℓa_i[γβu_i(x)+αv_i(x)+w_i(x)]_1$ 을 $G_1$에서 조립.

2. 세 pairing 계산

   $t_1=e([A]1,[B]_2),t_2=e(Q{pub},[γ]_2),t_3=e([C]_1,[δ]_2)$.

3. 사전저장 상수 $t_0=e([α]_1,[β]_2)$와 비교

4. 검사 $t_1 =? t_0⋅t_2⋅t_3.$

Reference

1. Quadratic Arithmetic Programs: from Zero to Hero
2. 영지식 증명: Linear PCP (QAP, R1CS, 피노키오, Groth16)
3. Groth16: On the Size of Pairing-based Non-interactive Arguments

사실, 우리가 현재 사용하고 있는 대부분의 중앙화된 온라인 서비스에서도 비슷한 문제가 발생한다. 특정 서비스를 이용하기 위해 주민등록번호, 주소, 전화번호와 같은 민감한 개인 정보를 직접 입력해야 한다. 이는 서비스 제공자에게 우리가 '정당한 사용자'임을 증명하는 가장 손쉬운 방법이지만, 이 과정에서 우리의 데이터는 위험에 노출된다.

이러한 문제점을 해결하기 위해 등장한 개념이 바로 영지식 증명(Zero-Knowledge Proof, ZK Proof)이다. 영지식 증명은 내가 어떤 정보를 알고 있다는 사실을 직접적으로 보여주지 않고도, 그 정보가 맞다는 것을 상대방에게 증명하는 암호학적 기술이다.

해당 아티클은 J. Groth, "On the Size of Pairing-based Non-interactive Arguments."를 읽고 정리한 내용이다

영지식 증명

영지식 증명은 다음 세 가지 핵심 속성을 가진다.

• 완전성(Completeness): 명제와 증거(witness)가 주어졌을 때, 정직한 증명자는 검증자를 설득할 수 있다.
• 건전성(Soundness): 악의적인 증명자는 거짓 명제에 대해 검증자를 설득할 수 없다.
• 영지식성(Zero-knowledge): 증명은 명제가 참이라는 사실 외에 어떤 것도 드러내지 않는다. 특히, 증명자가 사용한 증거를 노출하지 않는다.

영지식 증명은 증명 절차에 따라 크게 두가지로 나뉜다. 첫째는 증명자와 검증자가 상호작용하는 대화형 영지식 증명(IZK, Interactive Zero-Knowledge), 둘째는 상호작용이 없이 검증을 하는 비대화형 영지식 증명(NIZK, Non-Interactive Zero-Knowledge)이다.

IZK(대화형 영지식증명)

기존의 대화형 영지식 증명(IZK)은 증명자와 검증자가 여러 차례 질의응답을 주고받으며 증거에 대한 지식을 증명하는 방식으로 이루어졌다. 이는 다음과 같은 기본적인 단계를 따랐다.(뭔가 Digital Signature에서 identification의 과정과 유사)

1. 첫 번째 메시지 (Commitment)

Prover는 자신이 알고 있는 witness를 바탕으로 어떤 메시지를 생성한다. 이 메시지는 증명자가 추후에 자신의 주장을 변경하지 못하도록 하는 '약속' 또는 '커밋먼트' 역할을 한다. 그리고 prover는 이 메시지를 verifier에게 보낸다.

2. 무작위 질문 (Challenge)

Verifier는 첫 번째 메시지를 받은 후, prover에게 witness와 관련된 무작위 질문(challenge)을 던진다.

3. 답변 (Response)

Prover는 verifier의 질문에 대해 자신의 witness를 사용하여 답변(response)을 생성한다.

4. 반복 및 확신

Verifier는 prover의 답변을 확인하고, 여러 번에 걸쳐 이 질의응답 과정을 반복했다. 이 과정을 충분히 반복하면, verifier는 prover가 우연히 정답을 맞혔을 가능성이 무시할 수 있을 만큼 낮아졌다고 확신하게 된다. 이 과정을 통해 verifier는 prover가 실제로 witness를 알고 있었다고 결론 내리지만, verifier가 얻는 정보는 '정답'뿐이며, witness 그 자체는 알 수 없다.

NIZK (비대화형 영지식 증명)

NIZK(Non-interactive Zero-knowledge, 비대화형 영지식 증명)는 증명자가 검증자에게 어떤 명제가 참임을 설득할 수 있게 해주는 암호학적 기법이다. NIZK는 공통 참조 문자열(common reference string, CRS) 모델에서 영지식 증명(zero-knowledge proof) 개념을 확장한 것이다.

NIZK 프로토콜의 구성 요소

NIZK 프로토콜은 네 가지 확률적 다항식 시간 알고리즘으로 구성된다.

1. Setup(셋업): Trusted setup을 통해 τ를 생성하고, τ를 이용해 σ(CRS)와 Proving Key, Verification Key를 생성한다.
   • 신뢰할 수 있는 셋업 절차는 무작위 비밀 값들을(τ) 사용하여 증명과 검증에 필요한 공통 참조 문자열(σ)을 생성한다.
   • Proving Key와 Verification Key는 모두 이 공개된 σ의 일부입니다. Proving Key는 증명자가, Verification Key는 검증자가 사용한다.
   • τ는 σ를 만드는 데 사용된 비밀 값들의 집합이며, 시뮬레이션 함정문(simulation trapdoor)으로 사용됩니다. σ를 만든 이후, τ는 폐기되어야 한다.
     • 만약 이 비밀값들이 안전하게 파기되지 않고 누군가에게 유출된다면 그 사람은 시스템의 암호학적 제약을 우회하여 거짓 증명(fake proof)을 생성할 수 있다. 이 때문에 CRS를 생성하는 과정은 반드시 신뢰할 수 있어야 하며 생성 후에는 해당 파라미터를 반드시 제거해야한다.

>**CRS란?**
**CRS(공통 참조 문자열, Common Reference String)**는 NIZK(비대화형 영지식 증명)에서 검증자의 무작위 챌린지 역할을 대신 수행한다.
상호작용 증명에서는 검증자가 무작위 값을 전송하여 증명자를 시험하지만, NIZK에서는 CRS가 그 무작위성을 미리 준비해둠으로써 상호작용 없이 검증을 가능하게 한다.
CRS는 **신뢰 설정(Trusted Setup)**이라는 특별한 과정을 통해 생성된 다수의 군 원소(group element) 집합으로 표현한다.
이 과정에서 α,β,γ,δ,x와 같은 아무도 모르는 비밀값(“toxic waste”)을 무작위로 선택하고, CRS는 이 비밀값들을 암호화된 형태로 포함하도록 한다.
CRS의 핵심 목적은 **증명과 검증 과정에서 동일한 고정된 참조값을 제공하여, 증명자가 임의로 검증 과정을 조작하지 못하게 하는 것**이다.
이때, 신뢰 설정을 올바르게 수행하지 않으면, 해당 비밀값을 아는 자가 임의의 잘못된 증명을 만들어도 검증을 통과시키는 공격이 가능해지므로, 시스템 전체의 보안을 심각하게 해친다.
따라서 신뢰 설정은 시스템의 규칙이 담긴 ‘암호화된 약속’을 만드는 과정이며, 이 약속이 올바르게 만들어졌다는 전제하에만 zk-SNARK 시스템이 안전하게 동작하도록 한다.

2. Prove(증명): Prover는 Proving Key를 이용해 proof π(A, B, C)를 생성한다.
   • Prover는 Proving Key를 포함하는 σ와 자신의 witness를 사용해서 증명(Proof)을 생성힌다.
   • 이 증명은A, B, C와 같은 3개의 그룹 요소로 구성된다.
3. Vfy(검증): Verifier는 Verification Key, σ(CRS), proof(A, B, C)를 이용해 검증한다.
   • Verifier는 Verification Key를 포함하는 σ, Proof, 그리고 공개된 입력(public inputs)만을 사용해서 증명이 유효한지 확인한다.
   • Verifier는 witness를 모르고도 검증을 수행할 수 있다. Verifier는Vfy 알고리즘을 통해 Proof가 유효한지 확인하고 0(거절) 또는 1(수락)을 반환한다.
4. Sim(시뮬레이션): 시뮬레이터는 τ와 명제를 입력으로 받아 증명을 반환한다. 이 알고리즘은 실제 프로토콜의 일부가 아니라, NIZK의 영지식성을 증명하기 위한 이론적 도구이다.

NIZK의 핵심 원리

기존의 영지식 증명(ZK)은 증명자와 검증자가 여러 차례 질문과 응답을 주고받으며(interactive), 증명자가 증거를 알고 있음을 증명했다. 하지만 NIZK는 이 과정을 단 한 번의 메시지 전달로 줄인다.

1. 신뢰할 수 있는 셋업 (Trusted Setup)의 역할:
   • 이 과정에서 Proofing Key와 Verification Key를 포함하는 공통 참조 문자열(CRS)이 생성된다. 이 CRS는 증명자와 검증자 모두가 사용하는 공개된 매개변수 역할을 한다.
   • CRS는 프로토콜의 '규칙'을 정의하고, 복잡한 검증 과정을 효율적으로 압축할 수 있게 해준다.
2. 비대화형 증명:
   • 증명자는 CRS와 자신의 witness를 사용하여 단 한 번의 계산으로 증명(π)을 생성한다.
   • 검증자는 증명자가 보낸 증명(π)과 CRS를 사용하여 단 한 번의 검증을 수행한다.

이러한 방식은 상호작용이 필요한 프로토콜에서 발생할 수 있는 잠재적인 문제를 해결한다. 예를 들어, 인터넷 연결이 불안정하거나 증명자가 오프라인 상태일 때도 증명이 가능해지며, 블록체인과 같이 모두가 검증자 역할을 해야 하는 환경에 적합하다. 즉, NIZK는 셋업 단계에서 미리 합의된 규칙(CRS) 덕분에 증명자와 검증자가 실시간으로 소통하지 않아도 된다.

Pinocchio Protocol

Pinocchio Protocol은 zk-SNARK(영지식 간결 비대화형 지식 증명)의 선구적인 프로토콜 중 하나이다.

Pinocchio는 동형 암호(Homomorphic Hiding)와 KoE(Knowledge of Exponent)등의 암호학적 기술을 활용한다. 이를 통해 증명자는 자신이 알고 있는 witness를 공개하지 않고도, $A(x)⋅B(x)−C(x)=H(x)⋅T(x)$와 같은 다항식 방정식의 해를 알고 있음을 간결하게 증명한다.

진행 순서

1. 평탄화 (Flattening) 임의의 복잡한 constraint를 하나의 연산을 처리하는 간단한 식으로 바꾼다.

   예시

   원래 식 : $out = x^3 + x + 5$

   평탄화 과정(총 4개의 게이트로 표현 가능):

   Step	게이트 표현	설명
   1	sym_1 = x * x	$x^2$ 계산
   2	y = sym_1 * x	$x^3$ 계산
   3	sym_2 = y + x	$x^3+x$ 계산
   4	~out = sym_2 + 5	최종 출력

2. Gates to R1CS

   R1CS (Rank-1 Constraint System) 부분은 모든 계산을 L * R = O (좌항 * 우항 = 출력) 형태의 제약으로 변환하는 것이 핵심이다. 회로에 사용되는 모든 변수를 하나의 벡터(s)로 매핑한다.

   각 게이트를 A(좌항) * B(우항) = C(출력)의 형태로 만들고, 각각에서 A는 A끼리, B는 B끼리, C는 C끼리 모아 메트릭스를 구성한다.

   2-1 벡터 생성

   순서 규칙

   1. 항상 값이 1인 변수 one (상수항 처리를 위해 필요)

   2. 공개 입력 변수 (public inputs)

   3. 출력 변수 (예: ~out)

   4. 중간 변수 (평탄화에서 생성된 sym 계열)

      예시 0: one → 항상 1 1: x → 공개 입력 2: ~out → 최종 출력 3: sym_1 → x² 4: y → x³ 5: sym_2 → x³ + x

      최종 벡터 : [one, x, ~out, sym_1, y, sym_2]

2-2 Gate → R1CS 제약 변환

각 게이트는 `(s·a) * (s·b) = (s·c)` 꼴로 표현된다. (여기서 `a,b,c`는 s 길이와 같은 계수벡터)

#### Gate별 a, b, c 및 검증

| 게이트 | 수식 | a (L) | b (R) | c (O) |
| --- | --- | --- | --- | --- |
| G1 | `sym_1 = x * x` | `[0,1,0,0,0,0]` | `[0,1,0,0,0,0]` | `[0,0,0,1,0,0]` |
| G2 | `y = sym_1 * x` | `[0,0,0,1,0,0]` | `[0,1,0,0,0,0]` | `[0,0,0,0,1,0]` |
| G3 | `sym_2 = y + x` → `(y + x)*1 = sym_2` | `[0,1,0,0,1,0]` | `[1,0,0,0,0,0]` | `[0,0,0,0,0,1]` |
| G4 | `~out = sym_2 + 5` → `(sym_2 + 5*1)*1 = ~out` | `[5,0,0,0,0,1]` | `[1,0,0,0,0,0]` | `[0,0,1,0,0,0]` |


![](https://velog.velcdn.com/images/omin_00/post/a22b772f-0d17-4dbb-b860-31e5cf972fbe/image.png)

3. R1CS to QAP

   지금까지는 각 gate에 대한 검증을 $A(x) * B(x) - C(x) =0$을 통해서 검증한다. 그러나 암호학적으로 수많은 지점에서의 등식 만족 여부를 하나하나 검증하는 것은 비효율적이다. 따라서 groth16은 제약조건을 일일이 계산하지 않기 위해 QAP를 이용해서 각 벡터를 다항식으로 변환한다.

   QAP 변환은 Lagrange interpolation을 이용하며, Lagrange interpolation은 특정한 점들을 모두 지나는 다항식을 구할 수 있다.

   Lagrange interpolation은 다음과 같이 수행된다.

• 얻고자 하는 y 좌표가 있는 점 한 개를 정한다.
• 해당 점을 제외한 나머지 점은 y좌표를 0으로 설정하며, 나머지 점을 지나는 다항식을 만든다. (y가 0이므로 쉽게 구할 수 있다.)
• 구한 다항식에 얻고자 하는 y좌표를 다항식에 곱해주고 현재 다항식에 얻고자 하는 y좌표에 대한 x값을 넣었을 때 나오는 값으로 나눠준다.
• 모든 점들에 대해 수행 후 도출된 다항식을 모두 더해준다.

과정만 봤을 때는 쉽게 이해가 되지 않을 수 있다. 따라서 (1, 3), (2, 2), (3, 4)를 예시로 Lagrange interpolation를 이해해보자.

(1, 3)을 얻고 싶은 좌표로 정하고 나머지를 좌표로 기저 다항식을 만든다.

그렇다면 (1, 3), (2, 0), (3, 0)로 점을 설정하고, 아래와 같이 식을 만들 수 있다.

• $(x-2)(x-3)$

• $(x-2)(x-3)$ * $(3) /(1-2)(1-3)$

• $1.5 * x^2 - 7.5 * x + 9$

  구한 다항식에 대한 그래프는 다음과 같이 나온다.

  

  나머지 두 점에 대해 반복하면 총 다항식들은 다음과 같다.

  • 1.5 * $x^2$ - 7.5 * $x$ + 9
  • 2*$x^2$ + 8$x$ - 6
  • 2*$x^2$ - 6$x$ + 4

  세 다항식을 모두 더 하면 최종적으로 1.5* $x^2$ - 5.5 * $x$ + 7이 나오게 된다.

  

  구한 다항식은 세 점을 모두 지나는 것을 확인할 수 있다.

  라그랑주 보건법에서 각 점이 n개 존재할 때 한 개의 기저 다항식을 구할 때 n-1개의 1차 다항식을 곱하기 때문에 O($n^2$) 만큼의 시간 복잡도가 걸리며, 총 n개의 점이 존재하기 때문에 전체 시간 복잡도는 $n$ * O($n^2$)를 만족한다. 즉, 라그랑주 보건법은 O($n^3$)의 시간 복잡도를 갖는다. (Fourier transform algorithms을 사용할 경우 더 단축할 수 있다.) 우리가 위에 구한 R1CS에 대해 라그랑주 보건법을 사용하는 방법은 다음과 같다. 아래와 같이 우리가 R1CS를 통해 정리한 식에서 행과 열은 각각 다음과 같은 의미를 지닌다

  • 행 (Row) : 좌표 할당 R1CS 행렬(A, B, C)의 각 행은 하나의 게이트(제약)를 나타내며, 순서대로 x=1, x=2, x=3,…, x=m과 같은 고유한 x좌표를 할당한다.

  • 열 (Column) : 다항식 생성 각 행렬(A, B, C)의 각 열은 하나의 다항식($A_i(x), B_i(x), C_i(x)$)을 생성한다.

각 열을 대상으로 라그랑주 보간법을 적용하여 다항식을 정의한다.

사진에서 A의 첫번째 열을 예시로 들면 해당 다항식은 (1,0), (2,0), (3,0), (4,5)를 지난다. 이걸 바탕으로 3차 다항식을 생성하면 $0.833x^3 -5x^2+9.166x -5$라는 다항식을 얻을 수 있다. 이를 A,B,C의 각 열에 대해서 진행한다.

결과는 다음과 같으며, 상수부터 오름차순 정렬되어 값들만 적혀 있다.

  A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]
B polynomials
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
C polynomials
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]

A 벡터의 다항식으로 첫 번째 제약 조건(x=1에서의 제약조건)을 도출해보면 다음과 같다.

결과적으로 01000이 나오므로 벡터 a의 첫 번째 제약조건과 맞아떨이짐을 확인할 수 있다.

이제 다항식이 저절하게 도출되었으므로 A, B, C를 s(솔루션 벡터)와 내적을 통해 검증다항식(T(x))를 생성할 수 있다. (여기서 솔루션 벡터는 해당 제약조건을 만족하는 임의의 값)

A, B, C를 솔루션 벡터와 내적한 A.s, B.s, C.s는 다음과 같다. (여기서 솔루션 벡터는 s = [1, 3, 35, 9, 27, 30])

A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]

A . s * B . s — C . s 결과는 다음과 같다.

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

다항식 t는 특정 제약 조건의 x 값에 대해 0을 만족하면 된다. 때문에 다른 점들에서는 0이 아닌 다른 값을 가질 수 있다.

위 전제를 기반으로 제약 조건의 x 값에 대해 항상 0을 갖는 다항식 Z를 정의하고, 이를 t와 나누었을 때 나머지가 0이면 다항식 t는 제약 조건의 x 값에 대해 항상 0임을 증명할 수 있다.

즉, Z을 증명할 수 있다.

해당 논리 게이트에 존재하는 하는 x 좌표들 중 y가 0인 다항식 Z는 $(x - 1) * (x - 2) * (x - 3) * (x - 4)$과 같다.

 Z = [24, -50, 35, -10, 1]

이제 t를 Z로 나누면 딱 떨이지게 되어 다음과 같은 다항식이 나오며 t는 Z의 배수임을 알 수 있다.

 h = t / Z = [-3.666, 17.055, -3.444]

즉, witness s를 사용하여 구성된 다항식 A(x)B(x) - C(x)가, 모든 제약 조건의 좌표를 근(root)으로 가지는 다항식 Z(x)로 나누어 떨어진다면, 해당 witness s는 모든 계산 제약 조건을 만족시킨다는 것을 증명한다. QAP를 통해 하나의 식을 통해 하나의 식으로 모든 제약 조건을 확인할 수 있게 되는 것이다.

4. Pinocchio 프로토콜

   무작위 점 s($\tau$)에서 다항식의 평가값을 비교하면 두 다항식의 동일함을 높은 확률로 확인할 수 있다는 Schwartz-Zippel 보조정리를 활용한다. 이를 통해 거대한 다항식 전체를 보내는 대신, 특정 점에서의 계산 값만 검증함으로써 증명 크기를 상수(constant) 크기로 줄이고 검증 연산을 효율화한다.

   그러나 Pinocchio는 zk-SNARK(비대화형)이므로 검증자가 실시간으로 무작위 값을 줄 수 없다. 대신 사전에 신뢰 설정(Trusted Setup) 과정을 통해 비밀 값($\tau$, $\alpha$ 등)을 생성하고, 이를 타원곡선 상의 점으로 암호화하여 CRS(Common Reference String) 형태로 공개한다.

   동일한 Witness 사용 증명 (Variable Consistency Check) Prover가 $A(x), B(x), C(x)$를 생성할 때 서로 다른 witness를 섞어 쓰지 않고, 동일한 witness 벡터 s를 사용했음을 증명해야 한다. 이를 위해 Pinocchio는 선형 결합 검증(Linear Combination Check)과 Shifted Polynomial 기법을 사용한다.

   1. Setup: CRS에는 기본 다항식 값들뿐만 아니라, 비밀 값 $\alpha$가 곱해진 Shifted 요소($g^{\alpha x^i}$ 등)들이 포함된다.

   2. Proving: 증명자는 다항식의 결과값 $g^{P(\tau)}$뿐만 아니라, 해당 witness들에 $\alpha$가 적용된 $g^{\alpha P(\tau)}$값도 함께 계산하여 제출한다.

   3. Verifying (Pairing): 검증자는 쌍선형 페어링(Bilinear Pairing) 함수 $e$를 사용하여 아래와 같은 등식이 성립하는지 확인한다.

      $$ e(Proof, g^\alpha) = e(Proof_{shifted}, g) $$

      이 등식이 성립하면, 증명자가 위조 없이 동일한 witness 계수를 사용하여 다항식을 생성했음이 수학적으로 증명된다. 즉, 상호작용 없이도 Pairing을 통해 $A(x) \cdot B(x) - C(x) = H(x) \cdot Z(x)$의 성립 여부(QAP)와 Witness의 일관성을 동시에 검증할 수 있게 된다.

Groth16으로의 확장

Pinocchio는 증명 구조가 8개의 그룹 원소로 되어 있고,Prover가 A,B,C 다항식에 동일한 witness를 사용했는지를 검증하기 위해 복잡한 과정을 거친다. Verifier는 무작위 값을 제공하고, Prover는 이 값을 기반으로 F라는 다항식에 대한 계산을 수행하여 일관성을 증명했다. Groth16은 이러한 Pinocchio의 문제를 아래와 같은 방법으로 발전시켰다.

• Groth16은 Pinocchio의 증명 구조를 3개의 그룹 원소로 압축.
  • $A', B', C'$ 3개만으로 pairing 검증 가능.
• $π_K$와 여러 보정항을 $π_C$ 내부로 통합.
  • 증명 크기와 검증 속도를 대폭 개선.

Reference

1. Quadratic Arithmetic Programs: from Zero to Hero
2. 영지식 증명: Linear PCP (QAP, R1CS, 피노키오, Groth16)
3. Groth16: [On the Size of Pairing-based Non-interactive Arguments]

암호학의 출발점은 이산 로그 문제(Discrete Logarithm Problem, DLP)라는 수학적 난제이다. 이 문제가 어렵기 때문에 이후의 모든 암호 시스템이 안전할 수 있다.

문제 정의: 순환군 G에서 g와 a가 주어졌을 때, $g^x \equiv a \pmod{p}$를 만족하는 x를 찾는 것은 매우 어렵다.

• 쉬운 방향: g, x, p를 알면 a를 계산하는 것은 쉽다. (지수 연산)
• 어려운 방향: g, a, p를 알면 x를 찾는 것은 매우 어렵다. (이산 로그) 이는 값을 알았을 때 계산을 하는 것은 쉽지만, 결과를 통해서 어떤 값들을 사용했는지는 알기 힘들다

난이도의 이유: p가 매우 큰 소수일 때, $g^x$의 값들이 예측 불가능한 순서로 나타나기 때문에, x와 a 사이에 규칙적인 관계를 찾을 수 없다.(현재 가장 빠른 알고리즘으로도 해결하는 데 천문학적인 시간이 걸린다.)

Diffie-Hellman 키 교환 (Diffie-Hellman key exchange)

Secure한 channel이 아닌 public한 환경에서 두 사용자가 동일한 비밀키를 공유할 수 있도록 하는 최초의 공개키 암호 시스템이다. Diffie-Hellman 키 교환은 DLP의 어려움을 활용하여 공개키를 교환하고, 이를 통해 비밀키를 생성한다.

1. group 생성 알고리즘 g를 이용해서 순환군 $G$, prime order q, generator g를 생성한다. 그리고 $Z_q$에서 임의의 원소 x를 뽑고, $g^x$ 를 통해 h1을 생성한다.
2. $G, q, g, h_1$을 보낸다.
3. 수신자는 $Z_q$에서 임의의 원소 y를 뽑고, $g^y$ 를 계산해서 $h_2$를 구한다.
4. 그 후, 송신자에게 $h_2$값을 보낸다.
5. 이렇게 되면 두 당사자들은 $(h_2)^x$ , $(h_1)^y$ 를 통해서 $g^{xy}$ 라는 동일한 키를 공유하게 된다.

여기서 위의 그림에서는 $G,q,g$를 그룹 생성 알고리즘에 의해 생성하고 있지만, 실제로는 $G, q, g$와 같은 그룹 매개변수는 통신 시스템 전체의 기반이 되는 공개 값으로, 한 번 설정되면 매 키 교환 세션마다 새롭게 생성할 필요 없이 재사용될 수 있으며, 이는 보안에 영향을 주지 않는다.

도청자는 공개된 $g,g^x,g^y$값을 알지만, DLP의 어려움 때문에 x나 y를 계산할 수 없다. 따라서 공통 비밀키인 $g^{xy}$를 알아내는 것이 불가능하다. 이 문제를 Diffie-Hellman 문제라고 하며, DLP를 해결할 수 있다면 Diffie-Hellman 문제도 풀 수 있다.

El Gamal 암호화

Diffie-Hellman 키 교환을 기반으로 하는 공개키 암호화 스킴을 El Gamal 암호화라고 한다.

키 생성 및 공개키 공유 A (수신자) 측: 먼저 $G,q,g$라는 공개 매개변수를 설정한다. 여기서 G는 순환군, q는 G의 위수(order), g는 생성자(generator)이다.

A는 임의의 개인키 $x$를 선택한다. A는 공개키 $h_1=g^x$를 계산하고, $G,q,g,h_1$을 송신자B에게 전달한다.

메시지 암호화 B (송신자) 측: B는 A의 공개키 $h_1$을 사용해 암호화를 진행한다.B는 임의의 난수 $y$를 선택한다. B는 $h_2=g^y$와 $k=(h_1)^y$를 계산한다. 여기서 k는 일회성 암호화 키이다.

B는 평문 m에 이 일회성 키 k를 곱해 암호문 $c_2=k⋅m$을 만든다.B는 암호문 쌍인 $h_2와c2$를 A에게 전송한다

메시지 복호화 A (수신자) 측: A는 B가 보낸 $h_2$와 $c_2$를 받는다.

A는 자신의 개인키 x를 사용해 일회성 암호화 키 k를 계산한다: $k=(h_2)^x=(g^y)^x=g^{xy}$ 이 k는 B가 계산한 $k = (h_1)^y = (g^x)^y = g^{xy}$와 동일하다. 마지막으로, A는 $c_2$를 k로 나누어 평문 $m=c_2/k$를 복원한다.

보안 문제 A가 만약 랜덤값 r을 중복으로 사용하여 메세지를 암호화 하였을 때 생기는 경우이다. 만약 메세지 중 하나가 유출된다면 다른 메세지를 복호화 할 수 있기 때문에 랜덤 키 재사용을 권장하진 않는다.

Reference

1. The Discrete Logarithm Problem, KEVIN S. McCURLEY, Proceedings of the Symposia in Applied Mathematics, vol. 42, 1990, pp. 49-74.
2. New Directions in Cryptography, Whitfield Diffie and Martin E. Hellman, IEEE Transactions on Information Theory, Vol. IT-22, No. 6, 1976, pp. 644-655.
3. A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS, Taher ElGamal, IEEE Transactions on Information Theory, Vol. 31, No. 4, 1985, pp. 469-472.

암호화와 복호화에 동일한 키를 사용하는 방식이다. 비대칭키에 비해 연산 속도가 빠르고 구현이 간단하다는 장점이 있지만, 키를 안전하게 주고받는 키 교환 과정이 필수적이며 키가 유출되면 보안에 취약해진다.

특징

• 빠른 연산 속도: 대규모 데이터 암호화에 유리
• 간단한 구현: 연산이 비교적 단순함
• 키 교환 필요: 보안 취약점

대표 알고리즘: AES, DES 등

분류

• 스트림 (Stream): 데이터의 비트/바이트 단위로 연속적으로 암호화하는 방식. 블록 방식보다 빠르며 하드웨어 복잡성이 낮지만, 평문의 패턴이 노출될 수 있어 보안에 취약할 수 있다.

• 블록 (Block): 데이터를 일정한 크기의 블록으로 나누어 암호화하는 방식. 블록 크기에 따라 속도 차이가 발생하며, 데이터가 블록 크기 미만일 경우 패딩이 필요하다.

Notion에 정리하기 좋게 대칭키와 비대칭키, 그리고 대표적인 알고리즘인 AES와 RSA에 대해 명확하게 구분하여 정리해 드릴게요.

비대칭키 (Asymmetric Key)

암호화와 복호화에 서로 다른 키를 사용하는 방식이다. 공개키(Public Key)와 개인키(Private Key) 한 쌍으로 구성된다. 공개키는 누구나 가질 수 있으며, 개인키는 소유자만 가질 수 있다.

특징

• 높은 보안성: 키 교환이 안전함
• 느린 연산 속도: 대칭키에 비해 처리 속도가 느림
• 인증 및 암호화 동시 수행: 공개키로 암호화한 데이터는 개인키로만 복호화 가능

대표 알고리즘: RSA, ECC 등

활용

• 안전한 키 교환: 대칭키를 안전하게 공유하기 위해 비대칭키를 사용한다.

대표적인 암호화 알고리즘 상세 설명

AES (Advanced Encryption Standard)

AES는 대칭키 블록 암호화 알고리즘의 대표적인 표준이다. 암호화와 복호화에 동일한 키를 사용하며, 데이터를 일정한 크기의 블록으로 나누어 처리한다.

• 키 길이: 128, 192, 256비트를 지원한다.
• 블록 크기: 키 길이와 마찬가지로 128, 192, 256비트를 지원하지만, 128비트가 표준으로 사용된다.
• 구조: 기존 DES와 달리 비-페이스텔(Non-Feistel) 구조를 가진다.
• 패딩: 블록 크기에 맞지 않는 데이터는 패딩을 추가하여 블록을 채운다.
• 상태 행렬: 입력된 한 블록은 4×4 크기의 1바이트 원소를 가진 상태 행렬(State Matrix)로 변환되어 연산에 사용된다.
• 라운드 수: 키 길이에 따라 128비트는 10회, 192비트는 12회, 256비트는 14회 라운드 연산을 반복한다.

AES의 라운드 함수 (Round Function)

AES는 암호화 과정에서 각 라운드마다 동일한 4개의 함수를 반복적으로 수행한다.

SubBytes (바이트 치환)

상태 행렬의 각 바이트를 S-box(Substitution-box)라는 고정된 치환 테이블을 이용해 다른 값으로 바꾼다. 이 과정은 다음과 같이 진행된다.

1. 바이트 값을 $GF(2^8)$에서 곱셈 역원으로 변환한다.
2. 아핀 변환이라는 선형 변환을 적용한다.
3. 결과적으로, 입력 바이트의 왼쪽 4비트는 S-box의 행을, 오른쪽 4비트는 열을 나타내어 새로운 바이트 값을 선택한다.

이 과정을 통해 AES는 비선형성을 강화하여 암호의 보안을 높인다. 예를 들어, 0x19는 S-box를 통해 0xD4로 변환된다.

ShiftRows (행 이동)

상태 행렬의 각 행을 정해진 규칙에 따라 왼쪽으로 순환 이동(Circular Shift)한다.

• 1행: 이동 없음 (0 바이트)
• 2행: 1 바이트 왼쪽 이동
• 3행: 2 바이트 왼쪽 이동
• 4행: 3 바이트 왼쪽 이동

MixColumns (열 섞기)

상태 행렬의 각 열에 대해 고정된 4×4 행렬을 곱하여 값을 섞는다. 이 과정은 갈루아 필드(Galois Field, $GF(2^8))$ 상에서 연산되며, 열 단위의 확산(Diffusion)을 일으켜 보안성을 높인다. $$ \begin{pmatrix} 2 & 3 & 1 & 1 \ 1 & 2 & 3 & 1 \ 1 & 1 & 2 & 3 \ 3 & 1 & 1 & 2 \end{pmatrix} $$

AddRoundKey (라운드 키 추가)

키 스케줄을 통해 생성된 라운드 키를 현재 상태 행렬과 XOR 연산한다. 이는 암호화 키를 연산에 직접적으로 섞는 단계이다.

RSA

RSA(Rivest-Shamir-Adleman) 알고리즘은 큰 정수의 소인수분해가 어렵다는 수학적 원리를 기반으로 한 비대칭키 암호화 방식이다. 공개키와 개인키를 한 쌍으로 사용하며, 공개키로 암호화한 메시지는 개인키로만 복호화할 수 있다. 예시를 통해서 RSA의 키 설정 및 암/복호화에 대해 알아보자.

키 생성 과정

두 개의 서로 다른 소수 p와 q를 선택한다.

예시: p=7, q=13

모듈러 n을 계산한다. n은 공개키와 개인키의 일부가 된다. $$ n=p×q $$ 예시: n=7×13=91

오일러 피 함수 ϕ(n) 값을 계산한다. $$ ϕ(n)=(p−1)×(q−1) $$ 예시: ϕ(91)=(7−1)×(13−1)=6×12=72

$\phi(n)$보다 작고 $\phi(n)$과 서로소(coprime)인 정수 e를 선택한다. e는 공개키의 지수가 된다.

예시: e=5

개인키의 지수 d를 계산한다. d는 $e \times d \equiv 1 \pmod{\phi(n)}$을 만족하는 값이다. 이 값은 확장 유클리드 호제법으로 구할 수 있다.

예시: $5d \equiv 1 \pmod{72}$를 만족하는 d=29

최종 키:

공개키 (Public Key): (n,e) → (91,5)

개인키 (Private Key): (n,d) → (91,29)

암호화 및 복호화 과정

평문(Plaintext): m 공개키: (n,e) 개인키: (n,d)

암호화 (Encryption) 평문 m을 공개키 $(n, e)$를 이용해 암호화하여 암호문 c를 만든다.

$$ c=m^e\pmod n $$

예시: 평문 m=9를 암호화하면 $c=9^5 \mod 91=81$

복호화 (Decryption)

암호문 c를 개인키 $(n, d)$를 이용해 복호화하여 평문 m을 언는다. $$ m=c^d \mod n $$

예시: 암호문 c=81을 복호화하면 $m=81^29 \mod 91=9$

복호화 원리 (오일러 정리)

복호화가 성공적으로 이루어지는 이유는 오일러 정리(Euler's Theorem)를 통해 증명할 수 있다. 오일러 정리는 a와 m이 서로소일 때 $a^{\phi(m)} \equiv 1 \pmod{m}$임을 밝혀진다.

RSA의 복호화 과정은 다음과 같습니다. $$ m≡(m^e) ^d \mod n $$ $$ m≡m^{ed} \mod n $$

키 생성 과정에서 ed≡1(modϕ(n)) 이므로, ed는 1+kϕ(n) 형태로 표현할 수 있습니다. 이를 복호화 식에 대입하면: $$ m≡m^{1+kϕ(n)} \mod n $$ $$ m≡m⋅m^{kϕ(n)} \mod n $$ $$ m≡m⋅(m^{ϕ(n)}) ^k \mod n $$

여기서 오일러 정리에 따라 $m^{ϕ(n)} ≡1 \mod n$이므로, $$ m≡m⋅(1)^k \mod n $$ $$ m≡m \mod n $$

따라서 개인키 d를 사용하여 암호문 c를 복호화하면 원래 평문 m이 올바르게 복원된다.

Reference

1. https://junstar92.tistory.com/192
2. https://en.wikipedia.org/wiki/Rijndael_S-box
3. https://ko.wikipedia.org/wiki/%EA%B3%A0%EA%B8%89_%EC%95%94%ED%98%B8%ED%99%94_%ED%91%9C%EC%A4%80

Digital Signature란?

디지털 문서의 진정성(authenticity)과 무결성(integrity)을 암호학적으로 보장하기 위한 기술

→ Private Key Encprytion(Symmetric-key Cryptography)에서는 MAC을 통해서 authenticity과integrity를 보장(송신자와 수신자만 공유된 비밀키를 가지고 있고, 이를 통해서 MAC을 생성 ⇒ 자연스럽게 authentication과 integrity 보장가능)

→ Public Key Encryption(Asymmetric-key Cryptograph)에서는 Digital Signature를 통해서 authenticity과 integrity를 보장(Public key encryption의 경우에는 공개키가 누구에게나 공개되어 있기 때문에, 송신자의 신원을 바로 보장할 수 없음 ⇒ 따라서 identification+signature)

Digital Signature의 과정

그림처럼 두 당사자가 있을 때, 발신자가 pk를 공개된 저장소에 올려서 누구나 접근할 수 있게 한다. 발신자와 통신하고 싶은 사람은 누구나 pk를 얻을 수 있다. 발신자가 수신자에게 메시지 m을 보내려고 할 때, 발신자는 본인이 해당 m을 만들었다는 것을 증명하기 위해 $Sign_{sk}(m)=σ$를 함께 보낸다. Bob은 σ에 대해서 $Verify_{pk}(m,σ)$ 알고리즘을 통해 발신자 Alice로부터 왔고 중간에 변조되지 않았음을 검증할 수 있다.

Digital Signature의 활용

Digital signatures(전자서명) 프로토타입을 소프트웨어 프로그램에 적용해자. 위 그림에서 Alice는 소프트웨어를 배포하려는 entity이고, Bob은 소프트웨어의 pk를 알고 있는 client이다. Alice는 프로그램을 개선할 때마다 업데이트를 위한 패치를 유저에게 발행하는데, 중간에 패치가 공격자에 의해 위조되지 않도록 $Sign_{sk}(patch)=σ$와 patch를 함께 전송한다. Bob은 signature를 통해 전송받은 패치가 Alice로부터 온 것인지 확인한다.

Comparison to MACs?

Digital signatures(전자서명)의 방법은 MACs(메시지 인증 코드)의 운용방식과 매우 유사해보인다. 그렇다면 둘의 차이점은 무엇일까? Digital signatures(전자서명) 대신 MACs의 알고리즘을 이용하여 σ를 생성해보자.

| Method 1 : 동일한 키를 모두 공유하는 경우 → 모든 사용자들이 key를 가지므로 임의의 사용자가 patch와 t를 생성할 수 있다.

위 그림에서 모든 사람들은 동일한 키 k를 공유한다. 발신자 Alice는 $t=MAC_k(patch)$를 이용하여 key k에 대한 tag를 생성하여 Bob에게 전달한다.

그러나 위 방법은 결함이 있다. 위처럼 수신자 Bob은 key k를 알고 있기 때문에, $MAC_k(patch^′)$를 통해 새로운 tag를 만들어낼 수 있다. 만약 수신자들 중 한 명이 악의적인 목적으로 이상한 패치 patch′와 이에 해당하는 tag t′를 전송한다면, 이를 전송받은 수신자는 이상한 tag t′를 올바른 패치로 인식할 수 있다.

| Method 2 : 각각 다른 키를 공유하고, 이를 통해서 MAC을 보내는 경우 → 수신자가 많아질수록 많은 키를 배포하고 관리해야 한다는 문제

위 방법은 모든 수신자가 동일한 key k를 공유하고 있기 때문에 문제가 생겼다. 이를 해결하고자 이번엔 수신자마다 서로 다른 key들을 Alice와 공유하도록 해보자.

위 그림처럼 tag를 생성하여 전송하면, 수신자들 간에 악의적인 공격을 충분히 막아낼 수 있다. 하지만 Alice 입장에선 수신자들마다 서로 다른 key를 이용하여 tag를 만들어야하기 때문에, 수신자가 많아질수록 많은 키를 배포하고 관리해야 한다는 문제가 생긴다.

Digital Signature는 공개키 암호화(Public-key Cryptography) 방식을 사용하며, MAC이 해결하지 못하는 중요한 보안 속성들을 제공한다.

• Public verifiability(공개검증가능성): 누구나 서명을 검증(verify)할 수 있어야 한다. → MAC은 키를 공유하지 않는 제3자는 MAC의 유효성을 확인할 수 없다.

• Transferability(양도가능성): 다른 사람에게 서명을 양도할 수 있다. → 물론 MAC도 그냥 중간에서 사람이 넘길 수 있긴하지만 키를 공유하지 않는 제3자는 MAC의 유효성을 독립적으로 검증할 수단이 없다. 그런데 signature는 가능하다!

• Non-repudiation(부인방지성): 송신자는 수신자에게 보낸 정보를 부인할 수 없다.

  MAC과 non-repuditation에 대한 성질을 비교해보면, MAC은 key에 대한 엑세스 권한이 없으면 tag의 진위여부를 확인할 수 없으므로 부인방지까지는 보장할 수 없다. Key는 해당 송신자만 지니고 있기 때문에, 그 key가 정확한지 검증할 방법이 없기 때문이다.

  (MAC의 경우에는 key가 옳은지 아닌지 알 수 없다.(개인만 가지고 있기 때문에) 그러나 PK는 DB에 저장되어 있으므로 판단할 수 있다)

Signature schemes

Digital signature의 signature scheme을 정의해보면, Signature scheme은 세 개의 PPT 알고리즘으로 구성되어 있다.

• $Gen(1^n)$ : output pk, sk (키 생성)(input : $1^n$, output : pk,sk)
• σ←$Sign_{sk}(m)$ : output σ (서명 생성) (input : sk, m output : σ)
• $Vrfy_{pk}(m,σ)$ : output 1 or 0 (증명) (input : pk, m, σ output : 1 or 0)

이때 모든 메시지 m과 Gen 알고리즘을 거친 키 pk,sk에 대하여, 아래 식을 만족한다.

$Vrfy_{sk}(m,Sign_{sk}(m))=1$

Security(MAC의 security와 유사)

| Threat model

위 signature scheme에서의 공격자는 Adaptive chosen-message attack이라는 공격모델을 사용한다. 위 공격은 공격자가 선택한 메시지에 대한 sign을 얻을 수 있는 방식이다.(공격자가 보낸사람으로 하여금 공격자가 선택한 메시지에 서명하도록 유도할 수 있다.)

| Security goal

공격자는 송신자에 의해 sign이 완료되지 않은 어떤 메시지에 대해서도 유효한 signature를 위조할 수 없어야 한다. 이때 공격자는 송신자의 public key를 알고 있는 상태이다. 이는 완전히 위조가 불가능하다는 점에서 Existential unforgeability를 만족해야 security goal에 도달한다는 말이다. → 유효한 서명을 생성할 수 없다!

Formal definition

위에서 정의한 security에 따라 scheme을 정의해보자.

Scheme:  $Π$/ Attacker: A

Forge $A,Π(n)$:

1. $pk,sk←Gen(1^n)$
2. $\text { A interacts with oracle } Sign_{sk}(⋅) \text { (M is the set of messages)}$
3. $\text { A output (m,σ) }$
4. $\text { A succeeds, and the experiment evaluates to 1,}$ $\text{if } Vrfy_{pk}(m, \sigma) = 1 \text{ and } m \notin M$ (새로운 메시지에 대해 유효한 서명을 도출하면 1)

Signature에 대한 security는 아래와 같다.

Replay attacks

위 정의로 replay attack까지 막을 수 있는 것은 아니다. 가령, Alice가 Bob에게 새로운 소프트웨어 패치를 보내는 과정에서 공격자가 작년에 Alice가 보냈던 패치와 서명을 그대로 보낸다면, 유효한 서명이므로 Bob 입장에서는 이를 걸러낼 방법이 없다. → 서명만으로는 replay attack을 막을 수 없고, 더 높은 매커니즘을 사용해 처리해야 한다.(예를 들면 날짜)

Hash-and-sign paradigm

MAC을 공부할 때 Hash and MAC을 공부했었는데, Digital Signature도 Hash and sign이 존재한다. 이 방식은 메시지에 대한 서명을 바로 만드는 것이 아니라 메시지를 해시함수에 넣은 다이제스트 H(m)을 이용해 서명을 만드는 기법이다. 지금까지는 특정 길이 n에 대해서 알아봤다면(짧은 길이의 메시지 인 경우), 이를 좀 더 확장할 수 있다.

Hash-and-sign paradigm

$Π' = (Gen, Sign', Vrfy')$

$Sgin'{sk}(m) = Sign{sk}(H(m))$

$Vrfy'{pk}(m,σ)=Vrfy{sk}(H(m),σ)$

$H:{0,1}^∗→{0,1}^n$인 해시함수에 대하여 위와 같이 정의한다. 달라진 것은 메시지 m에 대하여 해시함수를 넣은 다이제스트를 서명 알고리즘에 대입하는 것이다. 위 방식처럼 해시함수를 이용하여 서명을 만든다면, HMAC처럼 임의의 길이의 메시지에 대해서도 signature를 만들 수 있다. 따라서 굳이 메시지 입력의 길이를 맞출 필요가 없다.

(그 전에는 짧은 길이의 메시지만 가능했었다. 그런데 더 긴 길이의 메시지를 hash해서 길이를 n으로 맞춘 다음에 이거에 서명을 한다.)

Security

그럼 위 알고리즘의 안전성을 살펴보자. 안전성을 증명하는 방식은 HMAC에서와 동일하게 진행된다.

Theorem 만약 $Π$가 안전하고 해시함수 H가 collision-resistant라면, $Π'$도 안전하다.

Proof 송신자가 $m1,m2,...,mi$ 에 대하여 메시지 인증을 하려고 한다.

$\text{Let } h_i=H(m_i)$ 이때 공격자는 위조한 (m,σ)를 만드는데, 위조하려는 message는 그 어떤 mi와 같은 값이면 안됩니다. 이 때 두 가지 경우가 생긴다.

$\text{1. } H(m) = H(m_i) \text{ for some i }$ 첫 번째는 공격자가 위조로 만든 해시가 mi의 어떤 해시값과 같을 때이다. 즉, collision이 일어났을 때이다. 하지만 앞서 전제에서 해시함수가 collision-resistance라고 가정했으므로, m과 mi의 해시가 같은 쌍을 찾는 것은 불가능하다.

$\text{2. }H(M) \neq h_i \text{ for all } i$ 두 번째는 m의 해시 다이제스트가 모든 i에 대해 $h_i$와 같지 않은 경우이다. 즉 공격자가 만들어낸 위조문이 유효하다면, 이전에 송신자로부터 받은 h에서 어떠한 단서를 찾았다는 것이다. 하지만 이는 서명 알고리즘이 안전하다는 가정이 전제되었기 때문에 h로부터 유효한 단서를 얻는 것은 실현 불가능하다.

Hash-and-sign은 hybrid와 유사하다. 긴 메시지를 서명한다면, 긴 메시지를 해시하는데 걸리는 시간에 영향을 받는다. → 속도(cost)는 symmetric-key encryption과 비슷한데, key management는 public key encryption을 따름

Identification scheme

디지털 서명의 기반이 되는 중요한 개념인 식별 체계(Identification Scheme)에 대해 알아보자.

Digital Signature는 메시지의 무결성과 서명자의 신원 인증을 보장하는 암호학적 기법이다. 이러한 디지털 서명의 기저에는 '자신만이 아는 비밀 정보(예: 개인키)를 소유하고 있음을 증명하는' 원리가 깔려 있으며, 바로 이 '비밀 정보 소유 증명' 과정을 상호작용적으로 다루는 것이 Identification Scheme이다.

Identification Scheme은 '나는 이 비밀 정보를 알고 있다는 것을 상대방에게 보여주고 싶지만, 그 비밀 정보 자체는 노출하고 싶지 않을 때' 사용하는 상호작용적인 프로토콜이다.

과정

Key 공유

1. prover가 pk,sk인 key pair를 생성하고, 자신의 pk를 공개적으로 배포하거나 접근 가능하게 한다
2. verifier는 prover의 pk에 접근한다.

Identification

1. Prover가 A라는 commitment 메시지를 생성하고 Verifier에게 보낸다.
2. verifier는 임의의 challnege를 생성하고 이를 prover에게 보낸다.
3. prover는 A와 sk를 기반으로 s를 만들고 verifier에게 보낸다.
4. verifier는 pk, c, s를 이용해서 검증한다.

Fiat-Shamir transform

Identification scheme이 상호작용적이라고 했는데, 디지털 서명은 보통 "비상호작용적(Non-Interactive)"이어야 한다. 즉, 서명자가 서명을 만들어서 보내면 검증자가 혼자서 검증할 수 있어야 한다는 것이다.. 그렇다면 어떻게 상호작용적인 식별 체계를 비상호작용적인 서명으로 만들 수 있을까? 바로 이때 등장하는 것이 Fiat-Shamir Transform이다.

Fiat-Shamir Transform은 상호작용적인 식별 체계를 비상호작용적인 디지털 서명 스킴으로 변환하는 일반적인 방법이다.

방법은 다음과 같다. 원래 상호작용적인 식별 체계에서는 Verifier가 무작위 'Challenge'을 생성하여 Prover에게 보내야 한다. 하지만 Fiat-Shamir Transform은 이 Challenge를 암호학적 해시 함수를 사용하여 생성하도록 한다.

다시 말해, Prover가 서명할 메시지와 커밋먼트를 해시 함수에 넣어 스스로 질문을 만들고, 그 질문에 대한 응답을 계산하여 서명으로 제출하는 방식이다. 이렇게 하면 검증자가 직접 질문을 보낼 필요가 없어지므로, 한 번의 전송으로 서명과 검증이 모두 가능해진다.(커밋먼트가 랜덤하게 생성되므로 challenge도 랜덤!)

이렇게 Fiat-Shamir Transform을 통해서 Identification을 하면서 Digital Signature가 가능해졌다.

Security

만약 passive attack 에 대하여 identification scheme이 안전하고 해시함수 H가 랜덤 함수처럼 모델링되어있다면, 여기에서 파생된 signature scheme 또한 안전하다.

Schnorr Signature

Schnorr identification scheme은 앞선 identification scheme에서 DLog가 hard problem임에 착안해 만든 프로토콜이다.

과정

1. 먼저 prover가 Group-generation 알고리즘을 이용해 G와 q, 그리고 generator g를 생성한다. 그룹 내에 랜덤한 값 x를 뽑아 자신의 private key로 세팅한다. 그리고 h를 gx로 만들어, G, q, g, h를 public key로 만든다.
2. 이제 interaction proof protocol을 본격적으로 진행한다. Verifier에게 $A = g^r$ (r은 랜덤한 값)을 전달한다.
3. Verifier가 public key를 이용해 c를 랜덤하게 뽑고 prover에게 전송한다.
4. 이를 받은 prover는 c와 자신의 private key, 그리고 메시지에 대한 정보 r을 이용해 서명 s를 만든다. 이때 s는 $s=[cx+r \mod q]$를 만족한다.
5. s를 전송받은 verifier는 public key에 존재하는 g와 자신이 랜덤하게 준 값 c, 그리고 서명 s를 이용해 인증이 됐는지 확인한다. 이때 아래 식에 의해 $g^sh^{−c}=A$가 성립해야 한다.

이제 해당 scheme을 Prover와 Verifier가 malicious한 경우를 가정해서 안정성을 증명해보겠습니다.

Prover가 malicious한 경우

이 그림은 증명자가 만약 비밀키 x를 모른 채로도 두 번의 서명 시도(Fiat-Shamir 변환에서 c와 c’ 두 가지 challenge에 대한 s와 s응답)를 통해 검증을 통과한다면, 이는 이산 로그 문제(DLP)를 풀 수 있음을 의미한다.

만약 악의적인 증명자가 $g^s h^{-c}=A$와 $g^{s'}h{-c'}=A$라는 두 가지 유효한 등식을 만들어낼 수 있다면, 이 두 등식을 결합하여 $g^s h^{-c} = g^{s'}h{-c'}$ 이라는 관계가 성립하게 된다. 이 관계를 조작하면 결국 x를 알아낼 수 있는 수식이 도출된다. 따라서 만약 악의적인 Prover가 비밀키 x를 모르면서 검증을 통과한다면, 그들은 DLP라는 매우 어려운 암호학적 문제를 풀 수 있다는 것을 의미한다.

이는 현재까지 알려진 효율적인 방법이 없기 때문에, 이러한 상황은 발생하기 어렵다고 가정하며, 이는 곧 “증명자가 실제로 비밀키 x를 알고 있어야만 이 증명 과정을 성공시킬 수 있다”는 soundness(건전성)를 강력하게 뒷받침한다.

Verifier가 malicious한 경우

그림의 왼쪽은 정직한 증명자(Prover)와 정직한 검증자(Verifier) 간의 실제 프로토콜 상호작용을 나타낸다.

1. 증명자는 자신의 비밀키 x와 랜덤 값 r을 사용하여 첫 메시지 $A=g^r$를 계산하여 검증자에게 보낸디.
2. 검증자는 이에 대한 무작위 도전값(Challenge) c를 생성하여 증명자에게 보낸다.
3. 증명자는 이 c와 자신의 비밀키 x, 그리고 r을 사용하여 응답 $s=cx+r$를 계산하여 보낸다.
4. 검증자는 최종적으로 $g^sh^{−c}=A$가 성립하는지 확인한다 (여기서 $h=g^x$는 증명자의 공개키이다).

이제 그림의 오른쪽은 공격자(악의적인 검증자)가 증명자의 비밀키 x를 전혀 모르는 상태에서 transcript를 스스로 시뮬레이션하는 과정을 보여준다. 여기서 중요한 점은, 공격자는 x를 모른 채로도 다음 순서로 값을 생성한다.

1. 먼저, 공격자는 도전값 c를 $Z_q$에서 균등하게 선택하고, 응답 값 s 또한 $Z_q$에서 균등하게 선택한다.
2. 그런 다음, 이 두 값을 사용하여 프로토콜의 첫 메시지 A를 $A=g^sh^{-c}$로 역으로 계산한다.

오른쪽에서 공격자가 임의로 만들어낸 (A,c,s) 세 값의 transcript는 왼쪽에서 정직한 증명자와 검증자가 실제로 상호작용한 (A,c,s) transcript와 동일한 분포를 가진다.

• 도전값 c: 왼쪽과 오른쪽 모두에서 Zq에서 균등하게 분포하는 무작위 값
• 응답 s
  • 오른쪽에서는 s를 직접 $Z_q$에서 균등하게 선택
  • 왼쪽에서는 $s=cx+r$인데, r (첫 메시지 A를 만들 때 사용한 랜덤 값)이 $Z_q$에서 균등 분포를 따르는 무작위 값이므로, 결과적으로 s 또한 $Z_q$에서 균등 분포를 따르게 됨 (이산 로그 그룹에서 랜덤 값을 더하거나 곱해도 균등 분포는 유지됩니다.)
• 첫 메시지 A: c와 s의 분포가 같으므로, 이들로부터 계산되는 A의 분포도 결국 동일

이 결론이 의미하는 바는 매우 중요하다.

만약 공격자가 비밀키 x를 전혀 모르는 상태에서 정직한 프로토콜과 구별할 수 없는 성공적인 transcript를 스스로 생성할 수 있다면, 이는 공격자가 프로토콜의 정직한 실행을 관찰하거나 수동적으로 도청하더라도 비밀키 x에 대한 어떠한 정보도 추가적으로 얻을 수 없다는 것을 의미한다. 검증자는 프로토콜을 관찰함으로써 얻는 정보가, 자신이 x 없이 임의로 생성할 수 있는 정보와 동일하기 때문이다.

따라서 이 그림은 Schnorr Identification이 zero knowledge(영지식성)이라는 강력한 보안 속성을 가지고 있음을 증명하는 핵심적인 개념이며, 이는 비밀 정보를 노출하지 않고도 신원을 증명할 수 있게 해주는 기초가 된다.

이러한 Schnorr Identification scheme에 Fiat-Shamir transform을 적용하면 Schnorr Signature scheme이 된다.

Security

이 내용을 바탕으로 security를 정의하면

• 만약 이산 로그 가정(DLP)이 성립한다면, Schnorr 식별 스킴은 수동적 공격에 대해 안전하다.

그리고 해당 scheme에 Fiat-Shamir 변환을 적용하면(identification을 signature로 변환)

• 만약 이산 로그 가정이 성립하고, H가 랜덤 함수로 모델링된다면, Schnorr 서명 스킴은 안전하다.

Reference

1. https://www.coursera.org/learn/cryptography/home/module/2

‘임의의 길이의 데이터’를 ‘고정된 길이의 데이터’로 매핑하는 함수 → 데이터의 길이에 상관없이 항상 동일한 길이의 출력을 생성

해시함수의 특성

1. Efficiency

   Hash function은 주어진 입력에 대해서 효율적으로 hash 값을 계산해야 한다.

2. Pre-image resistance

   주어진 hash 값으로부터 원래의 입력 데이터를 알아내기 어려워야 한다.

3. Second pre-image resistance

   특정 입력 데이터가 주어질 때, 해당 입력 데이터의 hash 값과 동일한 hash 값을 갖는 다른 입력 데이터를 찾아내기 어려워야 한다.

4. Collision-resistance

   동일한 hash 값을 가지는 입력 데이터 쌍을 찾아내기 어려워야 한다.

   • collision : 서로 다른 두 입력값(데이터) x와 x'가 동일한 해시 값을 생성하는 경우

     ($H(x) = H(x')$)

   • 만약 어떤 해시 함수에서 충돌을 찾는 것이 계산적으로 거의 불가능하다면 충돌 저항성을 가진다 한다.

  >- **Second Pre-image Resistance:** 특정 x이 주어져 있고, 그 기준점과 같은 해시 값을 갖는 다른 x′를 찾기 어려운 특성 (1대1 공격)

• Collision Resistance: 기준점 없이, 해시 값이 같은 임의의 두 쌍(x, x′)을 찾기 어려운 특성(무작위 2개 찾기)

해시함수의 필요성

해시 함수는 데이터의 무결성을 검증하는 데 핵심적으로 사용된다.

• 이는 입력 데이터의 극히 작은 변화에도 최종 해시 값이 크게 달라지는 Avalanche Effect 덕분이다.
• 이러한 특성으로 인해 Collision-resistance과 Second Pre-image resistance이 보장되어, 데이터의 위조나 변조를 사실상 불가능하게 만든다.

즉, 특정 파일이나 메시지를 배포하거나 전송할 때, 원본 데이터의 해시 값을 함께 제공함으로써 수신자는 해당 데이터가 중간에서 변경되지 않았음을 확신할 수 있다. (Integrity 보장)

Example of Hash function

• MD5
  • 1991년에 개발
  • 128 bit의 output → collsion이 2004년 발견되어 더 이상 사용되지 않음
• SHA-1
  • 1995년 처음 소개
  • 160 bit의 Output → 이론적 분석으로 오류가 있음이 확인되었고 SHA-2로 발전
• SHA-2
  • 256 bit 또는 512 bit의 output → 약점이 발견되지 않음
• SHA-3
  • SHA 계열과는 매우 다른 설계 방식 → 기존의 SHA는 Merkle–Damgård 구조라는 유사한 구조를 가지는데 Keccak은 근본적으로 다른 접근 방식인 sponge construction를 사용
  • 224, 256, 384, 512 bit의 output

해시 함수의 응용: Merkle Tree

만약 검증해야 할 데이터가 수십, 수백만 개에 달하는 대규모 집합이라면 어떨까?

모든 개별 데이터의 해시 값을 일일이 비교하는 것은 매우 비효율적일 것이다.

⇒ 이러한 문제를 해결하고 대규모 데이터 집합의 무결성을 효율적으로 검증하기 위해 '머클 트리(Merkle Tree)'라는 자료구조가 해시 함수를 기반으로 활용된다.

머클 트리의 구성 요소 및 작동 원리

머클 트리는 해시 함수를 기반으로 계층적으로 구성된다. 주요 구성 요소는 다음과 같다.

• 리프 노드 (Leaf Nodes): 가장 하위 레벨에 위치한 노드들이다. 각 리프 노드는 원본 데이터 블록(또는 트랜잭션 등)의 개별 해시 값을 저장한다. 예를 들어, 여러 개의 트랜잭션이 있다면 각 트랜잭션의 해시 값이 하나의 리프 노드가 된다.
• 비-리프 노드 (Non-Leaf Nodes): 리프 노드 위에 있는 중간 노드들이다. 각 비-리프 노드는 자신이 가진 자식 노드들의 해시 값을 합쳐서 다시 해시(Concatenation & Hashing)한 결과를 저장한다. 예를 들어, 두 자식 노드의 해시 값이 H1과 H2라면, 부모 노드는 Hash(H1 + H2) 값을 가지게 된다.
• 머클 루트 (Merkle Root): 가장 최상위에 위치한 단일 노드이다. 트리 구조의 꼭대기에 있으며, 모든 하위 데이터 블록의 해시 값이 재귀적으로 결합되어 생성된 최종 해시 값이다. 이 머클 루트 값 하나로 전체 데이터 집합의 무결성을 대표할 수 있다.

데이터 블록들을 해시하여 리프 노드를 만들고, 이웃하는 두 리프 노드의 해시 값을 합쳐서 다시 해시하는 과정을 반복하여 상위 노드를 생성한다. 이 과정을 최종적으로 하나의 머클 루트가 나올 때까지 반복한다.

이처럼 머클 트리는 특정 트랜잭션의 유효성을 검증하기 위해 전체 블록을 확인할 필요 없이, 해당 트랜잭션의 리프 노드부터 머클 루트까지의 머클 증명(Merkle proof) 경로와 형제 노드의 해시값만을 사용하여 효율적이고 암호학적으로 안전하게 검증할 수 있도록 돕는다.

Reference

1. https://www.helius.dev/blog/cryptographic-tools-101-hash-functions-and-merkle-trees-explained

2. https://velog.io/@dohoon8/Cryptography-5.-Hash-function%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC

3. https://www.coursera.org/learn/cryptography/home/module/4