롤업간 Atomic Execution을 달성하기 위한 단계

들어가기 전에, 2년간 업로드가 거의 없었는데 여전히 종종 찾아와주셔서 감사합니다. 저는 Radius 창업 이후, 모듈러 블록체인의 중심에서 더 나은 롤업 기술을 위한 프로토콜을 연구하고 있습니다. 연구 내용을 블로그와 트위터에 자주 공유하겠습니다. 매우 재밌으니, 즐겨주세요 :)

참고: Radius는 하이어링 중입니다. tariz@theradius.xyz로 연락주세요.

아티클의 피드백을 이더리서치 포럼에 남기시면, 훌륭한 리서처들과 더 많은 대화를 나눌 수 있습니다: https://ethresear.ch/t/steps-to-achieve-atomic-execution-in-rollups/18776

들어가며

롤업은 DApp의 거래 속도와 비용을 개선할 수 있는 효과적인 기술이다. 그럼에도 불구하고, 아직 롤업으로 서비스를 배포한 팀은 많지 않다. 왜냐하면 이더리움의 smart contract가 제공하는 강력한 서비스 운영 경험을 포기해야하기 때문이다. 다시말해, 그들은 롤업을 선택한 순간 censorship resistance, liquidity composability, liveness guarantee, transaction execution 등을 고민해야한다.

우리는 DApp이 롤업의 확장성과 smart contract의 서비스 운영 경험을 얻기 위한 방법을 지속적으로 탐구하고 이를 공유해 방법을 개선하고자 한다.

첫 번째는 Atomic Execution 달성이다.

롤업의 신뢰 가정

롤업 간 Atomic Execution을 달성하기 어려운 이유는 롤업 간에 신뢰 가정을 셋팅하기 어렵기 때문이다. 사용자 관점에서 롤업은 smart contract을 뛰어넘는 사용자 경험을 제공한다. 이는 사용자와 롤업의 Sequencer간의 신뢰 가정 덕분이다 (미리 밝히지만, 신뢰 가정으로 얻은 확장성은 허구다).

Sequencer는 사용자의 트랜잭션 처리 결과(state)를 전달하고, 사용자는 그 state가 유효하다고 믿은 채 다음 트랜잭션을 생성한다.

위와 같은 신뢰 가정은 롤업 간에 만들어지기 어렵다. 왜냐하면, 롤업은 운영하는 회사가 다르기 때문이다. 그래서 롤업간 거래의 사용성이 smart contract보다 현저히 떨어져 유동성 분열이 발생하는 것이다. 여기서 알 수 있는 것은, 신뢰 가정이 없어지는 순간 우리는 scalability느끼게 해주는 ux를 쉽게 잃는 다는 것이다.

Concept: Atomic Execution

이제 Atomic Execution을 위해 검증가능하게 만들어야하는 가정을 살펴보자. Atomic Execution은 각 롤업의 블록에 포함된 번들 트랜잭션이 모두 성공적으로 실행되거나 모두 실행되지 않는 것을 의미한다. 이더리움의 플래시론은 이에 대한 대표적인 예시이다. 플래시론은 이더리움 상의 다수의 스마트컨트랙트에서 실행되는 트랜잭션 집합(번들)이다.

플래시론에 Uniswap과 AAVE의 smart contract에서 실행되는 2개의 트랜잭션이 있다고 가정하자: 1) Uniswap — transaction A, 2) AAVE — transaction B. 플래시론의 atomic execution의 달성 과정과 trustless assumptions은 다음과 같다:

• trustless assumption: 상호간에 믿을 필요 없는 가정을 의미한다. Uniswap은 AAVE의 smart contract의 동작을 믿을 필요 없다.

우리의 설계 목표는 롤업이 Uniswap의 trustless assumption을 갖도록 하는 것이다. 이를 위한 요구사항은 다음과 같다:

1. 모든 롤업의 블록에 번들 트랜잭션이 포함되었음을 검증가능하게 한다.
2. 모든 롤업이 트랜잭션을 유효하게 실행했음을 검증가능하게 한다.
3. 모든 롤업이 블록을 올바르게 재구성했음을 검증가능하게 한다.

우리는 여기에 중요한 요구사항을 한 가지 추가한다: Trustless Sequencing. 이는 앞서 소개한 Sequencing 가정을 Trustless하게 만드는 것이다. 즉, 검열, 샌드위치, 프론트러닝 없이 블록을 결정하도록 보장하여 사용자와 롤업간의 Trustless를 강화한다.

설계안 설명에 앞서 우리는 롤업이 다음과 같은 구조를 가지고 있다 가정한다:

1. 롤업은 효율성을 위해 Block Sequencing과 Execution레이어가 분리된다.
   a. (Shared) Sequencer: stateless node로 블록의 시퀀싱만 담당한다.
   b. Executor: Full node로 블록의 실행만 담당한다.
2. 롤업들은 상호 운용성을 위해 하나의 sequencer를 공유하며, 이를 shared sequencer라 부른다.

Architecture Overview

Phase 1. Proposal Block Sequencing

Proposal Block은 shared sequencer가 executor에게 실행을 요청하기 위해 만든 초기 블록이다. 이 블록에는 약속된 사용자의 번들에 있는 트랜잭션이 관련된 모든 롤업의 블록에 포함된다.이 과정에서 모든 블록은 검열, 프론트러닝, 샌드위치 공격 없이 구성된다. 이 단계는 Atomic Inclusion을 보장한다.

1. Commit: 암호화된 트랜잭션의 실행 순서를 약속
2. Reveal: 트랜잭션 복호화
3. Sequencing: 약속한 순서대로 트랜잭션을 정렬하여 Proposal Block 생성
4. Proving: Proposal Block의 유효성 증명 — Shared Sequencer가 번들 내의 모든 트랜잭션을 관련된 블록에 약속한 순서대로 포함했다.

Phase 2. State Execution

State는 Executor가 실행한 Proposal Block의 실행 결과이다. 이 단계의 Proving은 실행의 유효성 증명과 번들의 revert 여부를 결정하는 근거가 된다.

1. Execute: Proposal Block을 실행하여 executed state를 계산
2. Proving: State의 유효성 증명 — Executor가 Proposal Block을 유효하게 실행했다.

Phase 3. Finalized Block Sequencing

Finalized Block은 Proposal Block을 실행 결과를 기반으로 재구성된 블록이다. 실패한 번들의 트랜잭션은 모두 제외(revert)되고, 최종으로 실행된 트랜잭션만 포함한다. 이 블록은 Proposal Block의 검열, 샌드위치, 프론트러닝 저항성이 상속된다. 이 단계는 Atomic Execution을 보장한다.

1. Sequencing: 최종 블록은 제안 블록에서 실패한 모든 거래를 제외하여 생성되며, 이는 실패한 번들의 거래도 포함한다.
2. Proving: Finalized Block의 유효성 증명 — 실패한 트랜잭션이 Finalized Block에 제외었으며, 남겨진 트랜잭션은 약속된 순서대로 나열되었다.

Phase 1. Proposal Block Sequenicng

1. Trustless Sequencing

Trustless seuqencing은 shared sequencer를 신뢰할 필요없이 블록이 결정되는 기능을 의미한다. 핵심은 sequencer가 블록에 포함할 트랜잭션을 preconfirm할 때, 암호화된 상태에서 이를 한다는 것이다.

이는 트랜잭션 내용을 미리 알아야 가능한 검열, 프론트러닝, 샌드위치와 같은 공격을 사실상 불가능하게 만든다. 즉, 롤업들 중 누가 shared sequencer가 되더라도, 블록 생성 권한을 이용하여 개인과 집단의 불공정한 이득을 취하는 것을 방지할 수 있어 가장 중립적인 참여자가 된다.

이 과정은 다음과 같은 순서로 진행된다:

1. Encrypt: 사용자는 Timelock puzzle을 기반으로 트랜잭션을 암호화한다.
2. Commit: Sequencer가 암호화된 트랜잭션에 대한 preconfirm을 한다.
   - Pre-confirmation: Proposal Block에 포함될 트랜잭션 순서이다.
   - enc_tx, order, sequencer_signature을 포함한다.
   - 개별 사용자에게 preconfirm_tx를 전송하거나 DA에 저장한다.
3. Decrypt: Sequencer가 Timelock puzzle을 풀어 트랜잭션을 복호화한다.
4. Sequencing: 약속한 순서대로 트랜잭션이 정렬하여 블록을 만든다.

Trustless sequencing에는 여러 가지 암호화 기술이 결합될 수 있다. 암호화 기술을 선택할 때 우리는 다음 두 가지 핵심 속성을 고려한다:

1. Delay Encryption: 이 속성은 Sequencer가 거래에 대한 약속을 공개할 때까지 복호화를 지연시킬 수 있는 능력을 의미한다.
2. In-protocol: Sequencer는 사용자를 포함한 제3자에 의존하지 않고 스스로 거래를 복호화할 수 있는 능력을 가져야한다.

이러한 속성을 실현하기 위해 ‘Timelock puzzle’을 사용한다. Timelock puzzle은 지정된 시간이 지난 후에만 복호화 키를 찾을 수 있도록 보장하는 암호학 메커니즘으로, 거래의 암호화에 대한 보장을 강화하고, Sequencer의 순서 결정 행위에 대한 신뢰가 필요없는 환경을 조성한다.

Timelock Puzzle 기반 암호화는 악의적인 사용자에 의해 시퀀싱 딜레이가 발생할 수 있다. Sequencing Liveness를 위해 Radius의 Practical Verifiable Delay Encryption (PVDE)은 사용자가 복호화 키에 대한 zkp를 생성할 수 있게 하여, Sequencer가 시퀀서가 복호화 실패로 이어질 수 있는 거래를 식별할 수 있도록 하여 이를 방지한다. 이에 대한 자세한 내용은 이더리서치 포럼에서 확인할 수 있으며, Curie Testnet을 통해 구현 세부사항과 사용성을 확인할 수 있다.

우리가 앞서 공개한 Encrypted Mempool Open Source는 Trustless Sequencing의 기능을 모두 담고있다. 이에 대한 자세한 내용은 아티클을 참고하라.

2. Bundle Sequencing

Atomic Inclusion을 위해 shared sequencer가 bundle을 모든 블록에 포함하는 방법을 설명한다. shared sequencer가 사용자의 번들을 preconfirm하는 것은 번들에 포함된 모든 트랜잭션을 롤업의 블록에 포함하겠다는 약속이다. 즉, 사용자와 롤업의 Executors는 shared sequencer와의 통신만으로 다수의 블록에서 실행될 트랜잭션에 대한 inclusion promise를 얻을 수 있다.

Bundle Sequencing은 앞서 설명한 Transaction Sequenicng과 같은 순서로 진행되어, 검열, 샌드위치, 프론트러닝 저항성을 갖는다.

1. Encrypt: 사용자는 개별 트랜잭션을 암호화하고, 이를 묶어 번들 형태로 만든다.
2. Commit: shared sequencer는 암호화된 트랜잭션에 대한 개별 preconfirmation을 만든다. 이후 preconfirmation을 묶어, 하나의 Bundle Preoconfirmation을 만든다.
   - Bundle Pre-confirmation: {preconfirm_tx_A, preconfirm_tx_B, sequencer_signature}
   - 이는 bundle과 트랜잭션 간의 관계에 대한 증명으로 사용된다.
3. Reveal: Shared Sequencer는 Timelock puzzle을 풀어 개별 트랜잭션을 복호화한다.
4. Sequencing: 각 롤업의 블록에 약속한 순서대로 정렬한다. 이때 번들 트랜잭션을 식별하기 위해 트랜잭션과 함께 bundle preconfirmation의 commitment도 함께 포함한다.

3. Proposal Block Proving

Proposal Block Proving은 shared sequencer가 preconfirm한 번들의 모든 트랜잭션이 롤업 블록에 포함되었음을 Executor가 확인할 수 있게 하기 때문에 중요하다.

Shared Sequencer는 commit 단계에서 bundle preconfirmation을 모두 DA에 저장한다. 그리고 Sequencing 단계에서 Proposal Block을 DA에 저장하고, Proposal Block의 commitment를 이더리움에 저장한다. Executor는 DA와 이더리움에 저장된 정보를 비교하여 Proposal Block의 유효성을 확인할 수 있다.

1. Executor A는 Block A에 담긴 preconfirm_bundle을 확인한다.
2. preconfirm_bundle을 DA에서 search하여 번들에 preconfirmed transaction을 확인한다.
3. Block B의 블록에 preconfirmed tx_B가 포함되었는지 확인한다.

Executor는 preconfirmation을 사용해 이를 이더리움에서 직접 검증할 수 있다. 우리는 이를 위해 vector commitment를 사용한다. 이는 index-value 쌍으로 이루어진 데이터를 커밋하는 알고리즘으로, 커밋된 데이터의 index와 value 간의 integrity를 보장할 수 있다. preconfirmed tx_B의 약속된 order가 i 라 하자. preconfirmed tx_B를 포함하는 vector commitment C 가 거래 검증 시점 이전에 이더리움 상에 게시된다고 가정하면, Executor는 다음과 같은 과정으로 tx_B가 약속된 순서로 블록에 포함되었는지 여부를 확인할 수 있다.

1. Executor A는 tx_B에 대한 proof (pi)를 shared sequencer에게 요청하여 받는다. 이때, pi 는 vector commitment의 index i 에 tx_B값이 커밋되어 있다는 것을 검증할 수 있는 proof 이다.
2. Executor A는 {pi, i, tx_B}를 vector commitment의 검증을 수행하도록 구현된 이더리움 smart contract에 전송한다.
3. Smart contract는 정해진 검증 로직을 따라서 한 번의 pairing 연산을 통해 tx_B가 Block B의 i 번째 순서로 커밋되어 있음을 검증한다.
4. 검증 결과가 fail 이라면, shared sequencer는 slashing 된다.

Phase 2. State Executing

State는 Proposal Block의 실행 결과이다. 이는 상대 롤업이 트랜잭션을 유효하게 실행했음을 검증하여, 번들의 취소 여부를 결정하는 근거가 되기 때문에 중요하다.

Proposal Block과 State가 공개되어 있다면, 참여자는 이를재실행하여 검증할 수 있다. 하지만, 이를 매 블록마다 재실행을 한다면, 검증을 위한 연산 비용이 과중될 수 있다. State의 유효성을 검증하기 위해 참여자가 무엇을 해야하는 지 생각해보자.

1. Proposal Block를 commit하여 이더리움에 게시된 vector commitment와 일치하는지 비교해야한다.
2. 유효한 Proposal Block을 실행하여 State와 일치하는지 비교해야한다.

State는 모두 연결되어 있기 때문에, 참여자는 State #100의 유효성 검증을 위해, 위 과정을 #0부터 #100까지 반복적으로 수행해야한다.

검증의 복잡성을 줄일 수 있는 한 가지 아이디어는 Recursive Proof를 사용하는 것이다. 매 State 마다, 두 가지 statement를 검증할 수 있는 recursive proof를 만든다면, 참여자는 100번째 state 검증에 앞서, 가장 최근의 recursive proof만 검증하면 된다.

한편, 오프체인 재연산과 recurisve proof 증명 생성 비용을 고려해보았을 때, 오프체인 재연산이 저렴할 수 있다. 하지만, 이 recurisve proof는 이후, finalized phase에서 최종 state를 검증하는데 활용되어, 해당 슬롯에서 발생한 모든 블록을 온체인에서 검증하는 데 있어 효과적으로 비용을 절감할 수 있다고 기대된다.

Phase 3. Finalized Block Sequencing

Finalized Block은 각 롤업의 Proposal Block 실행 결과를 바탕으로 재구성한 블록이다. 아래 시나리오에서는 Block A에서 tx_A가 실패했다고 가정한다. 이 때, Block B에서 tx_B를 제외하여 블록을 재구성하는 방법과 이를 검증하는 방법을 설명한다.

1. Finalized Block Sequencing

Finalized Block은 다음과 같은 규칙으로 Sequencing되어, Proposal Block의 검열, 샌드위치, 프론트러닝 저항성을 상속받는다.

1. Proposal Block에서 실패한 트랜잭션은 모두 블록에서 제외된다.
2. Proposal Block의 Pre-confirmation이 유지된다.
3. 번들에 포함된 트랜잭션 중 하나라도 실패하면 관련 트랜잭션이 모두 블록에서 제외된다.

예를 들어, Proposal Block의 두 번째 트랜잭션이 실패했다고 가정하자. 그럼 Finalized Block은 아래와 같이 결정된다. Pre-confirmation은 유지되었기 때문에, 검열, 샌드위치, 프론트러닝 저항성을 상속받는다.

번들 트랜잭션에 대한 Finalized Block Sequencing은 다음과 같이 이루어진다:

1. Shared Sequencer는 Executor A로부터 executed state A를 받는다.
2. tx_A가 실패한 경우, Executor B에게 tx_B를 제외한 Second Proposal Block을 전달한다.
   - tx_A가 실패했음을 증명하는 proof도 함께 전달한다.
   - Second Proposal Block도 Finalize Block Sequencing 규칙과 동일하게 Sequening 된다.
3. Executor B는 Finalize Block B를 실행한 state B’를 shared sequencer에게 전달한다.
4. Shared sequencer는 롤업 A와 B의 Finalized Block을 확정한다.

Rollup B는 기존 Proposal Block에서 성공했던 tx_B를 제외해야하기 때문에, state가 변경되어 연쇄적으로 이후 트랜잭션이 실패할 수 있다. 하지만, 이는 의도적인 실행 실패가 아님을 기억하자. 또한, Finalized Block Sequencing 룰에 의해 트랜잭션을 재조합하지 않아야한다. 따라서, 위 시나리오에서는 한 번의 추가 커뮤니케이션으로 Finalized Block을 결정할 수 있다.

2. Finalized Block Proving

롤업이 블록을 올바르게 재구성했음을 검증가능하기 때문에 중요하다. 재구성된 블록은 롤업의 오프체인에서 최종 실행된, 그리고 이더리움에서 최종 검증될 트랜잭션의 집합이다. 따라서, 이 단계의 Proving은 Atomic Execution을 보장한다.

위 예시에 이어서 Block A의 tx_A가 실패했다고 가정하자. Atomic Execution을 위해 Shared Sequencer는 tx_A가 ‘state proving’단계에서 유효하게 실패했음을 확인하고, Block B에서 tx_B를 제거하여 Executor B에게 전달한다. Executor B는 tx_A가 실패했음을 검증하고, Finalized Block을 실행하여 state B’와 이에 대한 proof’를 생성한다. Block B의 commitment는 이더리움에 게시되어 있고, Block B, state B, state B’, proof, proof’ 그리고 Finalized Block은 DA에 게시되었다.

Executor A는 이 정보를 기반으로 Block B에 tx_B가 유효하게 제거되었고, 이더리움의 Finalization에서는 tx_B가 포함되지 않음을 알 수 있다.

위 과정은 작년에 발간했던 ‘Efficiency-Improved Inter-Rollup Transfer System Leveraging Batch Settlement Methods’ 와 결합되어 효율적인 검증이 가능하다. 이는 롤업 간의 자산 전송 효율성 증가를 위해 배치 정산과 zkp를 사용하는 시스템이다. 이 설계는 다음 게시글에서 다룰 것이다.

Conclusion

우리는 롤업이 DApp의 거래 속도와 비용을 개선할 수 있는 중요한 기술임을 인정하면서도, smart contract를 뛰어넘는 사용자 경험을 위해 셋팅된 신뢰 가정에 대하여 언급했다. 이에 따라, 롤업의 원활한 상호작용을 위해 롤업간 신뢰 가정을 최소화하면서도 롤업의 독립된 실행환경을 유지할 수 있는 설계 방안을 제시했다. 이 설계는 초기 모델이며, 우리는 롤업의 비용 효율성과 속도 개선이 유지될 수 있는 방안을 지속적으로 탐색하고 있다.

우리는 이후 게시글에서 앞서 언급한 롤업의 중요한 요구사항인 Trustless Sequencing에 대해서 소개할 것이다. 이는 검열, 샌드위치, 프론트러닝 가능성을 없애는 것 뿐만 아니라, 롤업의 노드 누구나 기술적으로 가장 중립적인 shared sequencer가 될 수 있게 하여 중요하다.

우리는 롤업으로 만들어진 DApp이 smart contract가 제공하는 강력한 서비스 운영 경험을 얻길 바란다. 관련된 모든 피드백과 연구 협업을 언제나 환영한다.