사용자가 전송할 수 있는 객체가 매우 많고, 이러한 객체들(유효한 경우)은 모두 최종 빌더 노드에서 검색 및 포함될 수 있도록 브로드캐스팅되어야 한다고 가정해 보겠습니다. 또한 유효성 조건은 STARK로 표현될 수 있으며, 양자 컴퓨팅 이후 환경에서는 타원 곡선 SNARK가 작동하지 않는다고 가정해 보겠습니다.
이는 이더리움의 최소 세 가지 사용 사례에 적용됩니다.
- 특히 사용자가 개인 정보 보호 프로토콜을 사용하는 경우, 양자 후 실행 계층 서명 집계가 필요합니다.
- 다수의 검증자를 처리하기 위한 양자 후 합의 계층 서명 집계
- 분산 블록 구성 모델에서 전체 블롭 수가 너무 많아 빌더가 전체를 다운로드할 수 없다고 가정할 때, 블롭 루트를 브로드캐스팅하는 것은 빌더가 블롭 제출자로부터 루트를 다운로드한 다음 DAS를 사용하여 가용성을 검증해야 합니다. STARK는 소거 코딩이 올바르게 계산되었는지 검증합니다.
문제는 STARK가 비용이 많이 든다는 점입니다. 크기를 최적화한 구현에서도 128kB의 용량을 차지합니다. 사용자가 전송하는 각 객체가 128kB의 STARK 오버헤드와 함께 모든 사용자에게 브로드캐스트된다면, 중간 멤풀 노드와 빌더 모두에 필요한 대역폭이 감당할 수 없을 정도로 커질 것입니다.
이 문제를 해결하는 방법은 다음과 같습니다.
사용자가 멤풀에 객체를 보낼 때, 해당 객체와 함께 유효성을 직접 증명하는 자료(예: 하나 이상의 서명, 유효성 검사 함수를 통과하는 EVM 호출 데이터) 또는 STARK 검증 자료를 사용하여 유효성을 증명할 수 있습니다.
멤풀 노드는 다음 알고리즘을 따릅니다.
- 이들은 수동적으로 기다리며 사용자로부터 객체를 수신합니다. 객체를 발견하면 해당 객체의 증명을 검증합니다. 증명이 유효하면 객체를 수락합니다.
- 매 틱(예: 500ms)마다, 이들은 자신들이 알고 있는 모든 유효한 객체의 유효성을 증명하는 재귀적 STARK 검증을 생성합니다. 그리고 이 검증 결과를 다른 피어들에게 전달하며, 아직 해당 피어에게 보내지 않은 객체들(검증 정보 제외)도 함께 전송합니다.
재귀적 STARK 검증의 논리는 다음과 같습니다. 공개 입력은 비트 필드 또는 해시 리스트이며, 이는 검증 대상이 되는 객체들의 집합을 나타냅니다. 검증은 다음과 같은 입력을 기대합니다.
- 0개 이상의 객체와 그 유효성을 입증하는 증거(직접 증거 또는 STARK 증거)
- 동일한 유형의 다른 재귀적 STARK가 0개 이상 있습니다.
- 폐기할 객체의 해시 리스트를 담은 비트 필드 (이를 통해 만료된 객체를 폐기할 수 있습니다)
그러면 이 증명은 재귀 스타크에 입력된 모든 객체와 모든 공개 입력의 합집합의 유효성을 입증하며, 이때 버려지는 객체는 제외됩니다.
다이어그램 형태로 나타내면 다음과 같습니다(여기서는 실행 계층 서명 집계 사용 사례를 보여줍니다).
이 예시에서 첫 번째 멤풀 노드는 Tx 1과 Tx 2(직접 증명 포함)를 수신하고, {Tx 1, Tx 2} 가 유효함을 증명하는 재귀적 STARK를 생성합니다. 두 번째 멤풀 노드는 첫 번째 노드에서 보낸 메시지(Tx 1과 Tx 2(직접 증명 제외) 및 STARK 포함)와 Tx 3(직접 증명 포함)을 수신하고, {Tx 1, Tx 2, Tx 3} 이 유효함을 증명하는 재귀적 STARK를 생성합니다. 이 메시지를 피어 노드들에게 전송하는데, 그중 하나가 빌더 노드이고, 빌더 노드는 이를 수신하여 멤풀에 포함시킵니다.
빌더가 완전히 겹치지 않는 객체 집합을 포함하는 여러 메시지를 수신하고 두 집합 모두를 포함시키려는 경우, 빌더는 재귀적인 STARK 연산을 통해 직접 객체들을 결합할 수 있습니다. 또한 빌더는 더 이상 포함할 수 없는 객체(여기서는 트랜잭션)를 버리기 위해 discard 명령을 사용할 수도 있습니다.
이 계획의 총 간접비는 다음과 같습니다.
- 증명 정보가 없는 각 객체는 모든 노드로 브로드캐스트됩니다. 이는 현재 방식과 동일한 대역폭을 사용하지만, 서명을 제거할 수 있다는 장점이 있습니다.
- 각 노드는 틱당 STARK 하나 크기에 해당하는 추가 인바운드 및 아웃바운드 대역폭을 가지며, 이는 해당 노드에 연결된 피어 수에 곱해집니다(예: 피어가 8개이고 틱이 500ms인 경우 128kB * 8 / 0.5 = 2MB/초). 이 값은 일정하며, 사용자가 전송하는 객체 수가 증가하더라도 늘어나지 않습니다.
