재귀란 무엇인가?

재귀는 수학, 통계 및 컴퓨터 과학 분야에서 가장 일반적으로 사용되지만 언어학, 논리학, 인공 지능 및 게임의 실제 응용 프로그램을 포함한 다양한 다른 분야에서도 널리 사용됩니다.

재귀는 함수가 순환 루프에서 직접 또는 간접적으로 자신을 호출하는 경우를 나타냅니다.

재귀를 사용하면 계산의 정확성을 개선하고 필요한 전체 계산 부하를 줄일 수 있습니다. 더 크고 더 복잡한 문제를 더 작은 조각으로 쪼개는 방식(“분할 및 정복”이라고도 함)을 통해 재귀는 작업을 더 빠르고 실현 가능하게 만듭니다. 주요 특징은 함수가 기본 사례 및 재귀 단계 측면에서 정의된 재귀를 달성하기 위해 연속해서 반복적으로 자신을 호출한다는 것입니다.

기본 사례는 출력을 계산하는 모든 입력에 대한 문제의 가장 간단한 인스턴스를 나타냅니다. 재귀 단계는 동일한 함수를 호출하지만 입력의 크기 및/또는 복잡성이 감소합니다.

반복 알고리즘과 재귀 알고리즘은 모두 문제를 더 작은 문제로 분류하지만 전자는 알고리즘의 순서를 관리하기 위해 명시적인 제어 논리가 필요합니다. 재귀 함수의 순서는 벡터 데이터와 재귀 함수의 상호 작용에 의해 결정됩니다. 이는 미리 명시적으로 정의할 수 없는 데이터 구조를 처리할 때 더 큰 유연성을 제공합니다.

재귀는 블록체인 기술에 어떻게 적용됩니까?

재귀는 블록체인에서 증명을 생성하는 방법입니다. 이제 Ethereum 메인넷에서 여러 생산 시스템을 제공합니다. 예를 들어 Arbitrum은 분쟁 해결 프로세스에 재귀 이등분 알고리즘을 사용하는 반면 StarkWare와 zkSync는 모두 재귀를 사용하여 향상된 확장 기능을 달성합니다.

재귀적 기술이 없으면 증명에 포함할 수 있는 거래의 상한선이 있으며 이는 단일 블록의 계산 용량에 따라 결정됩니다. 재귀를 사용하면 수십만 개의 기본 트랜잭션이 포함된 여러 검증된 증명에서 단일 증명을 생성할 수 있습니다. 즉, 이제 우리는 재귀적 확장이라고도 알려진 단일 증명으로 더 많은 트랜잭션을 처리할 수 있습니다.

영지식증명에 적용되는 재귀적 기술은 블록체인의 확장성을 해결하는 솔루션의 핵심 부분으로 간주되기 때문에 특히 중요합니다. 예를 들어 Ethereum의 주요 zk-rollup 확장 솔루션 중 하나인 StarkWare의 StarkNet을 사용하면 SHARP(SHARed Prover)는 StarkNet의 별도 애플리케이션에서 트랜잭션을 가져와 일괄 처리하고 이를 하나의 ZK-STARK 증명(또는 그냥 STARK 증명)으로 압축합니다. 그런 다음 증명자는 검증자에게 증명을 전달하고 레이어 1의 상태 변경을 검증하고 등록하는 것은 검증자의 역할입니다. 필요한 계산 리소스에 따라 누가 증명자가 될 수 있는지에 대한 제한이 있습니다.

이제 그림에 재귀를 추가해 보겠습니다. 여러 트랜잭션(또는 명령문)이 SHARP로 전송되어 병렬로 입증됩니다. 그런 다음 각 증명은 STARK 검증자에 의해 검증됩니다. 일단 확인되면 Recursive Verifier 문에 의해 다시 병합됩니다. 이 프로세스는 하나의 최종 증거가 Solidity 검증자 스마트 계약의 레이어 1에 제출될 때까지 반복될 수 있습니다. 따라서 이 증명은 모든 원본 진술을 증명하므로 단일 증명으로 여러 온체인 거래를 처리할 수 있습니다. 이론적으로 재귀 루프는 무한정 반복될 수 있으므로 "하이퍼스케일링" 기능이 가능해집니다.

따라서 재귀는 롤업 기술과 레이어 2 확장의 잠재력을 더욱 활용합니다.

재귀의 이점

유효성 증명을 위한 재귀의 이점에는 여러 증명을 하나로 "압축"하여 거래당 비용을 절감함으로써 가스 비용을 낮추는 것이 포함됩니다. 이를 통해 L1에 제출된 단일 증명 내에서 더 많은 거래를 분할하여 거래당 가스 비용을 분할할 수 있습니다. 한 번에 매우 큰 진술을 증명할 필요가 없기 때문에 증명 크기를 제한하는 계산 리소스 장벽도 더 이상 제약이 아닙니다.

또한 대기 시간도 줄어듭니다. 소규모 트랜잭션이 포함된 명령문은 병렬로 입증될 수 있으며 다른 트랜잭션이 들어올 때까지 기다릴 필요가 없습니다. 증명자는 더 이상 오프체인에서 대규모 계산을 수행할 필요가 없으므로 증명자가 되기 위한 장벽이 낮아져 분산형 트랜잭션이 활성화됩니다. 네트워크의 처리 능력을 향상시키기 위한 증명자 네트워크.

또한 사용자는 STARK를 사용하여 "로그 압축"의 이점을 누릴 수 있습니다. 여기서 진술을 증명하는 데 T 시간이 걸리고 증명을 확인하는 데 대략 log(T) 시간이 걸립니다. 올바른 실행에 대한 두 가지 증명이 포함된 증명을 확인하려면 log(2log(T)) 단계가 필요하기 때문에 로그 압축이 중요합니다. 즉, 재귀적 증명을 생성하고 검증하는 데 소요되는 대기 시간이 로그 단위로 감소합니다.

재귀를 통해 플랫폼과 애플리케이션은 비용과 성능을 더욱 확장할 수 있는 기회를 갖게 됩니다.

레이어 2 이후의 재귀 사용

재귀는 레이어 3 사용 사례의 단계를 설정합니다. 지금까지 초점은 재귀를 사용하여 최종적으로 레이어 1에 정착하는 레이어 2에서 증명을 생성하는 데 있었습니다. 그러나 새로운 레이어에서는 실행이 최상위 레이어에서 수행되는 레이어 3에서 레이어 2로 트랜잭션 증명을 제출할 가능성도 열립니다. , 그리고 증거는 궁극적으로 레이어 2에서 검증되므로 성능 최적화와 비용 이점을 더욱 높일 수 있습니다. 레이어 3과 레이어 2 사이의 상호 작용은 레이어 2 및 레이어 1과 유사하며 모든 트랜잭션 무결성과 보안이 유지됩니다.

특히, 프라이빗 레이어 3 네트워크는 고도로 사용자 정의 가능하므로 프로토콜은 트랜잭션 비용과 속도의 균형을 맞추기 위해 트랜잭션 배치 크기를 설정하거나 개인정보 보호 기능을 구현하는 등 자체 운영 매개변수를 설정할 수 있습니다. 재귀의 향상된 처리 기능과 함께 다양한 사용 사례에 맞는 맞춤형 레이어 3 품질을 통해 맞춤형 체인 경험을 제공하는 동시에 성능 및 비용 최적화 도구를 쉽게 사용할 수 있습니다. 레이어 3의 이점은 재귀 증명의 곱셈 효과, 개인 정보 보호 및 레이어 2와 레이어 3 간의 향상된 상호 운용성을 활용한 결과로 인한 하이퍼 확장성입니다.

시간이 지남에 따라 블록체인 개발에 대한 재귀의 더 많은 사용 사례와 이점이 실현될 것입니다. 병렬화 프로세스를 잠금 해제함으로써 하이퍼스케일링이 가능해지며 대기 시간이 개선되고 가스 요금이 절감됩니다.

작가

Jane Ma, zk-rollup 확장성, 뛰어난 거래 속도 및 비용 절감을 Ethereum의 보안과 결합하여 StarkNet을 기반으로 구축된 L2 머니 마켓 프로토콜인 zkLend의 공동 창립자이자 공동 프로젝트 리더입니다. 이 프로토콜은 기관 고객을 위한 허가형 및 규정 준수 중심 솔루션과 DeFi 사용자를 위한 무허가형 서비스라는 이중 솔루션을 제공합니다. 모두 분산화를 희생하지 않고 가능합니다.