PRIME: Efficient Algorithm for Token Graph Routing Problem

이 논문은 블록체인 기반 자산 교환의 비선형 가중치 문제를 해결하기 위해 가지치기 탐색과 적응형 부호 경사법을 결합한 PRIME 알고리즘을 제안하며, 실제 이더리움 데이터에서 기존 Uniswap 라우팅보다 더 높은 실행 가격과 계산 효율성을 입증했습니다.

Haotian Xu, Yuqing Zhu, Yuming Huang, Jing Tang

게시일 Tue, 10 Ma
📖 3 분 읽기☕ 가벼운 읽기

Each language version is independently generated for its own context, not a direct translation.

🚗 1. 문제 상황: 왜 돈이 사라질까요? (The Problem)

블록체인에는 수많은 '거래소' (예: Uniswap) 가 있습니다. 여기서 A 코인을 B 코인으로 바꾸려면, 보통 여러 경로를 거쳐야 합니다.

  • 직접 가는 길: A → B
  • 우회하는 길: A → C → B

하지만 여기서 함정이 있습니다.
차량이 많을수록 (거래 금액이 클수록) 도로가 막히듯, 코인을 많이 바꾸면 **가격이 떨어지는 현상 (슬리피지)**이 발생합니다. 마치 택시를 10 명 태우면 1 명 태울 때보다 승객 1 인당 요금이 비싸지는 것과 비슷합니다.

기존의 방법들은 이 복잡한 '도로 상황'을 실시간으로 계산하기엔 너무 느리거나, 비싼 도로를 피하지 못해 사용자가 잃어야 할 돈 (수수료) 을 제대로 계산하지 못했습니다.

💡 2. PRIME 의 등장: 똑똑한 내비게이션 (The Solution)

저자들은 PRIME이라는 새로운 알고리즘을 개발했습니다. 이는 마치 초고속 내비게이션처럼 작동합니다. PRIME 은 두 가지 핵심 전략을 사용합니다.

🗺️ 전략 1: "핵심 도로"만 먼저 살펴보기 (Core Graph & Shortcuts)

전 세계 모든 도로를 다 검색하면 시간이 너무 오래 걸립니다. PRIME 은 먼저 **가장 붐비는 주요 도로 (핵심 자산)**만 모아서 지도를 만듭니다.

  • 핵심 그래프: 비트코인, 이더리움, 달러 스테이블코인처럼 거래가 가장 활발한 '메인 도로'만 먼저 봅니다.
  • 숏컷 (Shortcut): 메인 도로에 없는 작은 길들 중, 갑자기 좋은 가격이 나오는 '비밀 지름길'이 있다면 미리 메모해 둡니다.
  • 효과: 모든 길을 다 뒤지지 않고, 가장 유력한 길들만 빠르게 추려냅니다.

📐 전략 2: "물량 분배"의 달인 (Adaptive Sign Gradient Method)

가장 좋은 경로를 찾았다고 해서 그 길로 전체 금액을 몰아넣는 게 정답은 아닙니다.

  • 비유: 100 만 원을 투자할 때, 한 곳에만 다 넣으면 그 곳이 비싸집니다. 하지만 30% 는 A 길, 50% 는 B 길, 20% 는 C 길로 나누어 보내면 전체적으로 더 이득을 봅니다.
  • PRIME 의 역할: PRIME 은 이 물량을 어떻게 나누어야 가장 이득인지를 수학적으로 계산합니다. 기존 방법들은 숫자가 너무 크거나 작아서 (비트코인 vs 치킨 코인) 계산이 꼬였지만, PRIME 은 숫자의 크기에 상관없이 '방향'만 보고 계산하는 특별한 방법 (ASGM) 을 써서 빠르고 정확하게 최적의 비율을 찾아냅니다.

🏆 3. 결과: 기존 방법보다 얼마나 좋을까요? (The Results)

이 알고리즘을 실제 이더리움 네트워크 데이터로 테스트한 결과는 놀라웠습니다.

  • 더 많은 수익: 기존에 쓰이던 Uniswap 의 자동 내비게이션 (SOR) 보다 거래 가격이 더 좋았습니다. 특히 큰 금액을 거래할 때, 수수료로 잃는 돈이 **8.42 bps(0.0842%)**만큼 더 적었습니다. 이는 매일 수천만 원의 거래를 하는 기관 투자자에게는 엄청난 차이입니다.
  • 엄청난 속도: 계산 속도가 최대 96.7% 빨라졌습니다. 기존에 1 초 걸리던 계산이 0.03 초 만에 끝난 셈입니다.
  • 실제 적용: 이미 헤지펀드 같은 전문 투자 기관에서 실제로 이 기술을 써서 돈을 더 많이 벌고 있습니다.

🌟 4. 한 줄 요약

PRIME은 블록체인이라는 거대한 미로에서, **가장 붐비는 주요 도로를 먼저 보고, 비싼 도로를 피하며, 물량을 똑똑하게 나누어 보내는 '초고속 최적 경로 찾기 알고리즘'**입니다.

기존의 느리고 비효율적인 방법 대신, 더 빠르고 더 저렴하게 코인을 교환할 수 있게 해주는 혁신적인 기술입니다.