이더리움 재단, 암호화 연구 팀: Gottfried Herold, George Kadianakis, Dmitry Khovratovich, Mary Maller, Mark Simkin, Antonio Sanso, Arantxa Zapico, Zhenfei Zhang
MinRoot 보고서 분석: https://crypto.ethereum.org/events/minrootanalytic2023.pdf
이더리움에는 RANDAO로 알려진 효율적이고 간단한 임의성 비콘이 있습니다. 이 비콘의 무작위성은 어느 정도 편향될 수 있다는 것이 인정됩니다. 우리가 아는 한, 이 편견은 현재 이더리움의 합의 프로토콜에서 악용되지 않습니다(출처: https://eth2book.info/capella/part2/building_blocks/randomness/ ). 이더리움 재단에서는 2019년 암호화 연구팀이 설립된 이후 기능적인 VDF를 구축하는 데 어느 정도 어려움을 겪어 왔습니다. 목표는 항상 공유 무작위성을 생성하기 위해 RANDAO보다 더 나은 솔루션을 찾는 것이었습니다.
VDF를 구축하려는 초기 시도에는 RSA 기반 접근 방식이 포함되어 신뢰할 수 있는 설정이 필요했습니다. 그러나 ZenGo가 실시한 감사 중에 설정을 위해 계획된 보안 다자간 계산이 공격을 받았습니다. 결과적으로 우리는 MinRoot VDF로 전환했습니다. VDF의 경우 공격자가 정직한 사용자보다 훨씬 빠르게 함수를 계산할 수 없도록 하는 것이 중요합니다. 결과적으로 정직한 사용자는 빠른 기준선을 설정하기 위해 고급 ASIC을 사용해야 합니다. RSA 솔루션을 기능적으로 만들려고 시도하면서 우리는 하드웨어의 중요성을 인식했습니다. 따라서 MinRoot는 하드웨어의 단순성을 최우선 고려 사항으로 설계되었습니다. MinRoot가 RSA 기반 시간 잠금 가정과 같은 이전 가정과 동일한 수준의 정밀 조사를 거치지 않았다는 점은 주목할 가치가 있습니다.
MinRoot는 초기에 대규모 병렬 처리를 사용하는 경우에도 공격자가 참조 구현보다 c=2배 더 빠르게 함수를 계산할 수 없어야 한다는 보안 목표를 가지고 VDF로 설계되었습니다. 보고서에 언급된 공격은 세계 최고의 암호 분석가와 암호 전문가들이 3일간 수행한 노력의 정점을 나타냅니다. MinRoot(2021)의 라운드 기능과 Sloth++(Boneh et al., 2018) 및 VeeDo(StarkWare, 2020)의 라운드 기능이 병렬화될 수 없다는 가정이 반박되었습니다. 특히, 소수 필드의 구조 덕분에 라운드 함수의 지수 부분이 병렬화될 수 있으므로 정수에 대한 이산 로그를 계산하는 데 사용되는 것과 동일한 인덱스 미적분 공격에 취약해집니다. 이 공격은 256비트 필드의 루트 계산이 단일 프로세서를 사용하는 것보다 2^25 프로세서와 2^40 메모리를 사용하여 더 빠르게 달성될 수 있음을 보여줍니다. 가속 정도는 선택한 대기 시간 통신 모델에 따라 달라집니다. 이 특정 공격은 이론적으로 프라임 필드의 크기를 늘려 대응할 수 있지만 그럼에도 불구하고 VDF를 설계할 때 찾아야 할 공격에 대한 이해가 부족하다는 점을 강조합니다.
실용적인 관점에서 볼 때 구체적으로 효율적인 VDF를 구축하기 위해 시도하고 테스트한 설계 패턴이 거의 없으며 마찬가지로 새로운 후보 구성의 보안을 안정적으로 평가하는 데 사용할 수 있는 공격 청사진도 많지 않다는 것이 분명해졌습니다. 이 상황은 실제 해시 함수 및 대칭 암호화 체계와 다릅니다. 우리는 SHA-3 및 AES를 개발하기 위해 수십 년간의 연구 노력을 기울여 왔으며 설계 패턴을 보유하고 있으며 새로운 후보를 효율적으로 평가하는 데 도움이 되는 다양한 공격 도구를 보유하고 있습니다. 지연 및 충돌 방지 해시 함수의 속성은 서로 관련이 없기 때문에 이러한 도구는 VDF의 보안을 평가하는 데 도움이 되지 않습니다.
실제로 MinRoot는 해시 함수 및 암호화 체계를 위해 개발된 기존 공격이 VDF의 보안도 평가하는 데 적합하다는 가정을 기반으로 안전한 것으로 간주되었습니다. VDF 워크숍에서는 VDF가 아직 철저하게 조사되지 않은 매우 다양한 종류의 공격에 취약하다는 사실을 보여주었습니다.
워크샵에서 발견된 공격을 포함하여 공격 표면의 관련 부분은 대규모 병렬 처리를 통해 기본 계산까지 약간의 속도를 높일 수 있는 가능성에서 비롯됩니다. 이는 병렬 리소스를 낭비적으로 사용하기 때문에 이러한 사용에 대한 조사가 부족하고 후보 VDF에 미치는 영향을 평가하는 데 필요한 경험이 부족합니다.
암호화 연구 팀은 이 설계 방식을 계속 진행하려면 VDF에 대한 더 나은 이해가 필수적이라는 데 동의합니다. 현재 우리는 Ethereum 내에서 VDF를 사용하는 것을 권장하지 않습니다. 지속적인 연구와 실질적인 개선은 향후 이 주제에 대한 우리의 관점을 잠재적으로 수정하는 데 중요한 요소입니다.
