“파이프라인 모드”로 생성 증명의 효율성을 어떻게 높일 수 있을까요?

작성자：강수跃, Fox Tech CEO; 맹현제, Fox Tech 수석 과학자

교정：림언희, Fox Tech CTO

서론

오늘날 디지털 시대에 블록체인 기술의 급속한 발전과 함께 데이터 프라이버시와 보안에 대한 관심이 높아지고 있습니다. 보다 효율적이고 확장 가능한 블록체인 애플리케이션을 실현하기 위해 여러 가지 솔루션이 제안되었으며, 그 중 하나가 제로 지식 증명(Zero-Knowledge Proof) 기술입니다. 제로 지식 증명은 민감한 정보를 누출하지 않고도 특정 진술의 진위를 검증할 수 있는 강력한 암호학적 도구입니다.

최근 몇 년 동안 zkRollup은 블록체인 확장 기술의 중요한 혁신 중 하나로 널리 주목받고 있습니다. zkRollup은 많은 거래를 패키징하여 오프체인에서 실행하고 제로 지식 증명의 특성을 활용하여 이러한 거래의 정확성을 검증함으로써 블록체인의 처리량과 확장성을 크게 향상시킵니다. zkRollup의 구현에서 거래를 어떻게 분배하고 패키징하며 증명을 생성하는지가 zkRollup 시스템의 중요한 구성 요소가 되었습니다.

Layer1 시스템에서는 거래가 블록 형태로 패키징되고 채굴자에 의해 계산됩니다. 반면 Layer2 시스템에서는 거래를 어떻게 패키징할 것인지, 즉 Layer2 블록을 어떻게 생성할 것인지에 대한 별도의 고려가 필요합니다.

FOX는 zkEVM 기반의 Layer2 zkRollup 확장 프로젝트로, 이 문제에 대해 FOX는 파이프라인 형태의 처리 방식을 사용하여 거래를 배치 처리하는 방법을 탐색하고 있으며, 이는 효율성을 크게 향상시킬 것으로 기대하고 있습니다.

본 문서에서는 zkRollup에서 제로 지식 증명을 생성하는 파이프라인 방식의 응용을 깊이 탐구할 것입니다. 먼저 기본적인 거래 패키징 방식을 분석하고, 이후 파이프라인 방식으로 제로 지식 증명을 생성하는 기술에 중점을 두어 그 원리와 응용 사례를 자세히 분석하겠습니다.

일반적인 거래 패키징 방식

전통적인 블록체인 시스템에서 거래의 확인과 패키징은 시간 소모가 크고 자원 집약적인 과정입니다. 일반적으로 거래는 하나씩 검증되어 블록에 추가되고, 이후 합의 알고리즘을 통해 일치를 이루어 블록체인의 상태가 업데이트됩니다. 그러나 이러한 하나씩 검증하고 패키징하는 방식은 낮은 처리량과 높은 지연 시간 등 명백한 한계를 가지고 있습니다.

일반적인 거래 패키징 과정에서는 먼저 처리할 거래가 수집됩니다. 이는 사용자 제출 거래 또는 다른 체인에서 온 거래일 수 있습니다. 그런 다음 이러한 거래는 합법성과 유효성을 보장하기 위해 검증됩니다. 이러한 검증에는 거래 서명 확인, 거래 유효성 및 일관성 검증 등이 포함됩니다. 거래가 검증을 통과하면, 거래는 패키징되어 제출 대기 중인 블록을 형성합니다.

zkRollup 시스템에서는 사용자 제출 거래가 거래 풀에 대기하게 되며, FOX 시스템에서는 Sequencer가 정기적으로 거래 풀에서 거래를 가져와 로컬에서 실행하고 정렬하여 거래 패키지, 즉 블록을 형성합니다. 이때 거래 실행 결과는 Layer1에 제출되며, 이 결과와 거래 데이터는 증명을 생성하는 Folder 노드에 제출됩니다.

제로 지식 증명 알고리즘에 대한 기본적인 이해에 따르면(독자는 이전 FOX의 시리즈 기사를 참조할 수 있습니다), Folder가 증명을 생성하려면 입력과 실행 결과를 얻어야 하므로, 일반적인 방식으로 진행할 경우 Sequencer가 모든 거래를 실행 완료한 후에야 Folder에 전달해야 합니다. 계산 자원을 보다 효율적으로 활용하기 위해, 우리는 Sequencer가 일부 거래를 실행한 후 즉시 Folder에 증명 생성을 위해 전달하기를 원합니다.

FOX가 탐색 중인 파이프라인 처리 모델

위의 목표를 달성하기 위해, 우리는 Sequencer가 거래를 배치로 실행하고 한 배치를 실행한 후 즉시 중간 결과를 Folder에 전송하도록 해야 합니다.

구체적으로, 거래 패키지의 거래 총 수가 100이고, 단일 배치 거래 수가 10이라면, 파이프라인 처리 방식은 아래 그림으로 나타낼 수 있습니다.

다음으로 두 가지 방식의 시간 소모를 간단히 분석하고, 어떤 경우에 파이프라인 방식을 사용하는 것이 더 높은 효율을 가져오는지 논의하겠습니다. 간단화를 위해, 여기서 논의는 Sequencer가 데이터를 Folder에 전송하는 시간을 고려하지 않습니다.

거래 패키지의 거래 수를 n, 배치 수를 k, Sequencer의 실행 시간 함수를 exe(), Folder의 증명 생성 시간 함수를 prove(), 집계 증명 시간 함수를 aggr()라고 할 때, 일반 방식의 총 시간은 Sum1, 파이프라인 방식의 총 시간은 Sum2입니다.

따라서 위의 과정에 따라, 일반 방식은 Sequencer가 먼저 실행한 후 Folder가 증명을 생성하는 데 필요한 총 시간은

Sum1=exe(n)+prove(n)

반면 파이프라인 방식의 시간은 Sequencer가 첫 번째 배치 거래를 실행하는 시간과 이후 증명 생성 시간 및 후속 배치 실행 시간 중 더 큰 값을 포함해야 하며, 마지막 집계 시간도 포함됩니다.

Sum2=exe(n/k)+max{k*prove(n/k),(k-1)*exe(n/k)}+aggr(k)

따라서 두 가지 총 소요 시간을 비교할 때, 실행 시간 함수 exe()는 기본적으로 선형 함수에 근사할 수 있으며, prove()는 FOX 시스템의 증명 알고리즘의 증명 생성 시간이 선형 함수이므로 prove()도 선형 함수입니다.

결론을 도출할 수 있습니다:

• 만약 exe(n)>prove(n)이라면, prove(n)>aggr(k)일 때 Sum1>Sum2입니다.
• 만약 exe(n)\<prove(n)이라면, (k-1)exe(n/k)>aggr(k)일 때 Sum1>Sum2입니다.

따라서 집계 시간 aggr(k)가 충분히 작고 증명 생성 시간이 선형 함수라면, 파이프라인 방식을 채택하는 것이 시스템 효율성을 높이고 총 증명 생성 시간을 줄이는 데 매우 유리합니다.

위의 분석은 선형 시간 증명 알고리즘에 대해서만 성립하며, 이 점에서 FOX가 선형 시간 증명 알고리즘을 채택하는 것이 중요함을 알 수 있습니다.

파이프라인 방식이 탐색 중인 상태라고 말하는 이유는 이러한 모델을 분석함으로써 각 거래 패키지가 분할되는 배치가 많아질수록 Sequencer가 Folder에 기록하고 전송해야 하는 데이터가 많아져서 오버헤드가 커지지만, Folder 측에서는 단일 처리의 계산량이 줄어들고 집계 과정이 더 복잡해지기 때문입니다. 따라서 구체적으로 어떻게 분할할지는 균형을 고려해야 하는 문제이며, Sequencer와 Folder의 계산 성능에 따라 달라집니다.

거래를 효율적으로 분배하고 패키징하여 배치로 증명을 생성하는 것이 핵심 최적화 포인트

zkRollup 구현에서 거래를 효율적으로 분배하고 패키징하여 증명을 생성하는 것은 핵심 최적화 포인트입니다. FOX는 지속적으로 모델을 최적화하고 더 효율적인 솔루션을 찾고 있습니다. 아래는 FOX가 채택한 기본 프로세스입니다:

1. 거래 수집: 처리할 거래를 수집하고 거래 풀에 저장합니다. 이러한 거래는 사용자 제출 거래이거나 다른 시스템 또는 계약에서 생성된 거래일 수 있습니다.
2. 거래 정렬: 거래 풀의 거래를 정렬하여 패키징 순서를 결정합니다. 일반적으로 우선순위, 타임스탬프 또는 기타 요소를 기반으로 한 정렬 알고리즘을 사용할 수 있습니다. 정렬의 목표는 거래의 전체 처리량과 효율성을 극대화하는 것입니다.
3. 거래 분배: 정렬된 거래를 적절한 블록에 분배합니다. zkRollup에서는 일반적으로 일정 수의 거래를 수용하기 위해 새로운 블록을 생성합니다. 분배 과정은 탐욕 알고리즘 또는 기타 분배 전략을 사용하여 각 블록의 용량 활용률을 극대화할 수 있습니다.
4. 블록 패키징: 할당된 거래를 패키징하여 완전한 블록을 형성합니다. FOX의 Layer2 아키텍처에서 이 블록은 실제로 거래의 요약 정보만 포함하며, 이 요약 정보는 거래의 해시 또는 기타 형태의 압축 표현일 수 있으며, 거래의 상세 내용은 FOX의 Ringer에 저장되어 데이터 가용성(DA)을 실현합니다.
5. 증명 생성: 패키징된 블록에 대해 해당 증명을 생성합니다. 이 증명은 블록 내 각 거래의 유효성과 전체 블록의 일관성을 증명할 수 있어야 합니다. FOX의 파이프라인 모델은 이 단계에서 주로 적용되어 Folder의 계산 능력을 보다 효율적으로 활용하고, 블록 내 거래를 배치로 Folder에 전송하여 증명을 생성합니다. Folder는 각 배치 거래에 대해 정확성 증명을 계산한 후 최종적으로 집계합니다. 일반적으로 이 증명은 FOAKS와 같은 빠르고 특정한 제로 지식 증명 알고리즘을 기반으로 하며, 블록 내 거래와 상태 전환 규칙을 비교하여 시스템의 규칙과 제약을 준수하는지 검증합니다.
6. 증명 검증: 수신자는 증명을 사용하여 블록의 유효성을 검증할 수 있으며, 전체 블록을 다시 계산할 필요가 없습니다. 이 검증 과정은 증명 검토만 포함되므로 매우 효율적일 수 있습니다.

FOX의 "파이프라인 모델"은 주로 증명 생성 단계에서 발생합니다. 거래 수집 및 정렬 단계에서 Sequencer는 처리할 거래를 수집하고 특정 규칙에 따라 정렬하여 실행 순서를 결정합니다. 이후 거래를 배치로 실행하는 과정에서 Sequencer는 정렬된 거래를 배치로 실행합니다. 각 배치의 거래 그룹은 실행 엔진에 전송되어 처리됩니다. 각 배치의 거래 실행이 완료된 후, Sequencer는 중간 결과를 Folder에 전송합니다.

이는 중간 결과를 상태 업데이트, 거래 해시 등의 형태로 배치로 Folder에 전송하는 통신 채널을 통해 완료될 수 있습니다. Folder는 각 배치의 중간 결과를 수신한 후 이 결과를 사용하여 배치별로 해당 증명을 생성합니다. 이러한 증명의 생성은 FOX가 자체 개발한 FOAKS 제로 지식 증명 알고리즘을 기반으로 하며, 중간 결과를 입력으로 사용하여 거래의 유효성과 전체 블록의 일관성을 증명합니다.

마지막 단계는 증명 검증입니다. 생성된 증명은 검증자에게 전송되어, Ethereum에 배포된 스마트 계약 Verifier가 블록의 유효성을 검증합니다. Verifier는 검증 알고리즘을 사용하여 증명을 검사하여 그 정확성과 합법성을 보장합니다.

이러한 파이프라인 방식을 통해 Sequencer는 거래를 실행하는 동시에 중간 결과를 Folder에 지속적으로 전송하여 배치별로 증명을 생성할 수 있습니다. 이는 전체 시스템의 효율성과 처리량을 향상시키고, 증명 생성의 지연을 줄이는 데 기여합니다.

결론

본 문서에서는 zkRollup에서 거래를 배치 처리하여 증명을 생성하는 비교적 새로운 방안인 파이프라인 방식에 대해 소개하고, 이 방식의 시간 소모를 자세히 분석하였습니다. 선형 증명 알고리즘에 대해 파이프라인 방식을 합리적으로 사용하면 총 증명 생성 시간을 줄이는 데 도움이 될 수 있습니다. FOX가 채택한 증명 시스템은 선형 증명 시간을 구현하여 빠른 증명 생성과 사용자 경험 향상에 큰 도움이 됩니다. FOX 팀은 이 솔루션을 지속적으로 탐색하고 최적화할 것입니다.