포세이돈 해시 (Poseidon Hash)

포세이돈(Poseidon)은 영지식 증명 회로 안에서 적은 제약 조건으로 계산되도록 설계된 '산술화 친화(arithmetization-oriented)' 해시 함수입니다. 2019년 로렌초 그라시(Lorenzo Grassi), 드미트리 호브라토비치(Dmitry Khovratovich) 등이 발표했고 2021년 USENIX Security에 게재되었습니다.

자세히 알아보기

SHA-256이나 Keccak은 비트 단위 연산(XOR, 회전)으로 이루어져 일반 CPU에서는 빠르지만, 소수체 위의 덧셈·곱셈으로 표현해야 하는 SNARK 회로에서는 수만 개의 제약이 필요합니다. 포세이돈은 처음부터 소수체 원소를 입력과 상태로 사용하고, 덧셈·곱셈만으로 구성되어 같은 보안 수준에서 제약 수가 수십 배 이상 적습니다.

구조는 스펀지(sponge) 방식 위에 HADES 설계를 적용한 것입니다. 각 라운드는 라운드 상수 더하기 → S-박스(xᵅ, 예: BN254에서는 α = 5) → MDS 행렬 곱의 세 단계로 이루어집니다. 처음과 마지막의 '전체 라운드'에서는 모든 상태 원소에 S-박스를 적용하고, 가운데 '부분 라운드'에서는 한 원소에만 적용해 비용을 줄이면서 대수적 공격에 대한 안전 여유를 확보합니다. 2023년에는 성능을 개선한 Poseidon2가 발표되었습니다.

포세이돈은 SHA-2 계열에 비해 역사가 짧고, 대수적 구조를 노리는 새로운 분석이 계속 발표되고 있습니다. 따라서 표준 파라미터(체, 라운드 수, 상수)를 그대로 쓰고, 회로 밖의 일반 용도에는 SHA-256·SHA-3 같은 검증된 해시를 쓰는 것이 바람직합니다. 체와 파라미터가 다르면 출력도 달라지므로, 같은 '포세이돈'이라도 구현 간 호환성을 반드시 확인해야 합니다.

블록체인·암호화폐에서는

Starknet(Cairo 내장 함수), 여러 zk 롤업과 Circom 기반 애플리케이션이 머클 트리 구성, 커밋먼트, 무효화 값(nullifier) 계산에 포세이돈을 사용합니다. Zcash의 Orchard 풀도 무효화 값 유도에 포세이돈을 쓰지만, 노트 커밋먼트와 머클 트리에는 별도의 Sinsemilla 해시를 사용합니다. 회로 안에서 해시를 많이 계산해야 하는 프라이버시 프로토콜과 상태 증명에서 증명 생성 시간을 크게 줄여 줍니다.

쉽게 말하면

영지식 증명이라는 특수한 '계산기'에서 가장 빨리 돌아가도록 맞춤 제작한 해시 함수입니다. 일반 컴퓨터용 해시를 그 계산기에서 쓰면 훨씬 느립니다.

예시

2-입력 해시 하나를 R1CS 회로로 만들 때 SHA-256 압축 함수는 수만 개의 제약이 필요하지만 포세이돈은 수백 개 수준입니다. 깊이 20인 머클 경로를 증명하는 회로라면 해시를 20번 계산해야 하므로, 이 차이가 증명 생성 시간에 그대로 반영됩니다.