가장 정교한 ZK 애플리케이션: 토네이도 캐시의 원리와 비즈니스 논리 되돌아보기

작성자: Faust, 극한의 web3

서문: 최근 Vitalik과 일부 학자들이 공동으로 새로운 논문을 발표했으며, 그 안에서 Tornado Cash가 어떻게 반 자금 세탁 계획을 구현하는지에 대해 언급했습니다(사실 이는 출금자가 자신의 입금 기록이 불법 자금이 포함되지 않은 집합에 속한다는 것을 증명하는 것입니다). 하지만 문서에서는 Tornado Cash의 비즈니스 논리와 원리에 대한 세밀한 해석이 부족하여 이해하기 어려운 부분이 있습니다.

또한, Tornado가 대표하는 프라이버시 프로젝트가 진정으로 ZK-SNARK 알고리즘의 제로 지식성을 활용하고 있으며, ZK라는 이름을 내건 대부분의 롤업은 ZK-SNARK의 간결성만을 사용하고 있다는 점도 주목할 만합니다. 많은 경우 사람들은 Validity Proof와 ZK의 차이를 혼동하는 경향이 있으며, Tornado는 ZK 응용을 이해하는 데 있어 훌륭한 사례입니다.

본 문서의 저자는 2022년에 Web3 Caff Research에서 Tornado 원리에 대한 기사를 작성한 적이 있으며, 오늘은 그 일부 단락을 발췌하고 확장하여 정리하여 독자들이 Tornado Cash를 체계적으로 이해할 수 있도록 하겠습니다.

「토네이도」의 원리

Tornado Cash는 제로 지식 증명을 이용한 믹서 프로토콜로, 구 버전은 2019년에 사용되기 시작했으며, 신 버전은 2021년 말에 베타 버전이 시작되었습니다. Tornado의 구 버전은 기본적으로 탈중앙화를 실현했으며, 체인 상의 계약은 오픈 소스이고 다중 서명 제어가 없습니다. 프론트엔드 코드는 오픈 소스이며 IPFS 네트워크에 백업되어 있습니다. 구 버전 Tornado의 전체 구조가 더 간단하고 이해하기 쉬워서 본 문서에서는 구 버전에 대한 해석을 진행하겠습니다.

Tornado의 주요 아이디어는: 많은 입출금 행동을 혼합하여, 입금자가 Tornado에 토큰을 입금한 후 ZK Proof를 제시하여 자신이 입금한 기록이 있음을 증명하고, 새로운 주소로 출금하여 입출금 주소 간의 연관성을 차단하는 것입니다.

더 구체적으로 요약하자면, Tornado는 많은 사람들이 넣은 동전이 혼합된 유리 상자와 같습니다. 우리는 동전을 넣은 사람들이 누구인지 볼 수 있지만, 이 동전들은 고도로 동질화되어 있어, 생소한 사람이 유리 상자에서 동전을 하나 가져가면, 우리가 그 동전이 처음에 누구에 의해 넣어졌는지 알기 어렵습니다.

（사진 출처: rareskills）

이런 장면은 흔히 볼 수 있습니다: 우리가 Uniswap 풀에서 몇 개의 ETH를 SWAP할 때, 도대체 누가 제공한 ETH인지 전혀 알 수 없습니다. 왜냐하면 Uniswap에 유동성을 제공한 사람이 너무 많기 때문입니다. 하지만 다른 점은, Uniswap에서 토큰을 인출할 때마다 우리는 다른 토큰을 동등한 비용으로 사용해야 하며, 자금을 "비공식적으로" 다른 사람에게 양도할 수 없다는 것입니다. 반면 믹서는 출금자가 입금 증명서만 제시하면 됩니다.

입출금 행동이 동질적으로 보이도록 하기 위해, Tornado 풀의 입금 주소는 매번 입금되는 자금과 출금 주소는 매번 출금되는 자금이 일치하도록 유지됩니다. 예를 들어, 어떤 풀의 100명의 입금자와 100명의 출금자가 공개적으로 보이지만, 서로 아무런 연관이 없어 보이며, 각자가 입금한 금액과 출금한 금액이 동일합니다. 이때 시선을 혼란스럽게 하여 입출금 금액으로 연관성을 판단할 수 없게 만들고, 자금 이동의 흔적을 차단할 수 있습니다. 이는 자금 세탁 행위에 자연스러운 편리를 제공합니다.

하지만 하나의 중요한 문제가 있습니다: 출금자가 출금할 때, 어떻게 자신이 입금한 기록이 있음을 증명할까요? 믹서에 출금 요청을 하는 주소는 모든 입금 주소와 연관이 없으므로, 그의 출금 자격을 어떻게 판단할 수 있을까요? 가장 직접적인 방법은 출금자가 자신의 입금 기록이 어떤 것인지 직접 공개하는 것이지만, 이는 신원을 직접적으로 노출하는 것입니다. 이때 제로 지식 증명이 필요합니다.

출금자는 ZK Proof를 제시하여 Tornado 계약에 입금 기록이 있으며, 해당 입금이 아직 인출되지 않았음을 증명하면 출금을 원활하게 진행할 수 있습니다. 제로 지식 증명 자체가 프라이버시 보호를 실현하므로, 외부에서는 출금자가 실제로 자금 풀에 입금한 적이 있다는 것만 알 수 있고, 그가 어떤 입금자와 연관되어 있는지는 알 수 없습니다.

"내가 Tornado 자금 풀에 입금한 적이 있다"는 것을 증명하는 것은 "내 입금 기록이 Tornado 계약에서 찾을 수 있다"로 변환될 수 있습니다. 만약 Cn이 입금 기록을 나타낸다면, 문제는 다음과 같이 요약될 수 있습니다:

Tornado의 입금 기록 집합이 {C1, C2, … C100…}로 주어졌을 때, 출금자 Bob은 자신의 키를 사용하여 입금 기록 중 하나인 Cn을 생성했음을 증명하지만, ZK를 통해 Cn이 구체적으로 어떤 것인지 누설하지 않아야 합니다.

여기서는 Merkle Proof의 특별한 성질을 사용해야 합니다. Tornado의 모든 입금 기록은 체인 상에 구성된 Merkle Tree에 저장되며, 이는 가장 하위의 리프 노드로 사용됩니다. 리프의 총 수는 약 2의 20제곱 > 100만이며, 대부분은 빈 상태입니다(초기값이 부여됨). 새로운 입금 행동이 발생할 때마다 계약은 해당 특성값 Commitment를 리프 중 하나에 기록하고 Merkle Tree의 root를 업데이트합니다.

예를 들어, Bob의 입금 작업이 Tornado 역사상 10,000번째라면, 이 입금과 관련된 특성값 Cn은 Merkle Tree의 10,000번째 리프 노드에 기록됩니다. 즉, C10000 = Cn입니다. 그런 다음 계약은 자동으로 새로운 Root를 계산하고 업데이트합니다. (ps: 계산량을 절약하기 위해, Tornado 계약은 이전에 변화가 있었던 노드의 데이터를 캐시합니다. 예를 들어 아래 그림의 Fs1, Fs2, Fs0)

（사진 출처: RareSkills）

Merkle Proof는 본질적으로 간단하고 가벼우며, 트리 구조를 이용한 검색/추적 과정에서의 간결성을 활용합니다. 특정 거래 TD가 Merkle Tree에 존재함을 외부에 증명하려면, Root에 해당하는 Merkle Proof(아래 그림의 오른쪽 부분)를 제공하면 됩니다. 이는 매우 간단합니다. Merkle Tree가 특히 거대하고, 하위 리프가 2의 20제곱 개, 즉 100만 개의 입금 기록을 포함하더라도, Merkle Proof는 단 21개의 노드 값만 포함하면 됩니다.

특정 거래 H3가 Merkle Tree에 실제로 포함되어 있음을 증명하려면, H3와 Merkle Tree의 다른 부분 데이터를 사용하여 Root를 생성할 수 있음을 증명해야 하며, Root를 생성하는 데 필요한 데이터(여기에는 Td 포함)가 Merkle Proof를 구성합니다.

Bob은 출금 시 자신이 가진 증명이 Merkle Tree에 기록된 특정 입금 해시 Cn에 해당함을 증명해야 합니다. 즉, 그는 두 가지를 증명해야 합니다:

• Cn이 체인 상의 Tornado 계약의 Merkle Tree에 존재하며, 구체적으로 Cn을 포함하는 Merkle Proof를 구성할 수 있습니다;
• Cn이 Bob이 가진 입금 증명과 연관되어 있습니다.

Tornado 비즈니스 논리 상세 해설

Tornado 사용자 인터페이스의 프론트엔드 코드에는 많은 기능이 사전에 구현되어 있습니다. 입금자가 Tornado Cash 웹페이지를 열고 입금 버튼을 클릭하면, 프론트엔드 코드에 포함된 프로그램이 로컬에서 두 개의 랜덤 숫자 K와 r을 생성한 후, Cn = Hash(K, r)의 값을 계산하고, Cn(아래 그림의 commitment)을 Tornado 계약에 전달하여 후자의 Merkle Tree에 삽입합니다. 간단히 말해, K와 r은 개인 키와 같습니다. 이들은 매우 중요하며, 시스템은 사용자에게 안전하게 보관하라고 알립니다. 이후 출금 시에도 K와 r을 사용해야 합니다.

(여기서 enc r yptedNote는 선택 사항으로, 사용자가 K와 r을 개인 키로 암호화하여 체인에 저장할 수 있도록 하여 잊어버리는 것을 방지합니다.)

중요한 점은, 위의 모든 작업이 체인 외부에서 발생한다는 것입니다. 즉, Tornado 계약과 외부 관찰자는 K와 r을 알지 못합니다. K와 r이 유출되면, 이는 지갑 개인 키가 도난당한 것과 유사합니다.

Tornado 계약은 사용자의 입금을 받고, 사용자가 제출한 Cn = Hash(K, r)를 받은 후, Cn을 Merkle Tree의 가장 하위에 삽입하여 새로운 리프 노드로 만들고, Root 값을 업데이트합니다. 따라서 Cn과 사용자의 입금 행동은 일대일로 연관되며, 외부에서는 각 Cn이 어떤 사용자와 연관되어 있는지, 누가 믹서에 토큰을 입금했는지, 각 입금자에 해당하는 입금 기록 Cn을 알 수 있습니다.

출금 단계에서 출금자는 프론트엔드 웹페이지에 증명서/개인 키(입금 시 생성된 랜덤 숫자 K와 r)를 입력합니다. Tornado Cash 프론트엔드 코드의 프로그램은 K와 r, Cn = Hash(K, r), Cn에 해당하는 Merkle Proof를 입력 매개변수로 사용하여 ZK Proof를 생성합니다. 이는 Cn이 Merkle Tree에 존재하는 특정 입금 기록임을 증명하며, K와 r은 Cn에 해당하는 증명입니다.

이 단계는 "나는 Merkle Tree에 있는 특정 입금 기록에 해당하는 키를 알고 있다"는 것을 증명하는 것과 같습니다. ZK Proof가 Tornado 계약에 제출될 때, 위의 4개 매개변수는 모두 숨겨지며, 외부(토네이도 계약 포함)는 이를 알 수 없으므로 프라이버시가 보장됩니다.

ZK Proof 생성에 관련된 다른 매개변수는 다음과 같습니다: 출금 시 Tornado 계약의 Merkle Tree의 루트 root, 사용자 정의 수취 주소 A, 재전송 공격을 방지하기 위한 식별자 nf(후에 설명할 예정)입니다. 이 3개 매개변수는 체인에 공개되지만, 프라이버시에는 영향을 미치지 않습니다.

여기서 세부 사항은, 입금 작업이 Cn을 생성할 때 두 개의 랜덤 숫자 K와 r을 사용하여 Cn을 생성하며, 단일 랜덤 숫자가 아닌 이유는 단일 랜덤 숫자가 충분히 안전하지 않기 때문입니다. 충돌이 발생할 확률이 있기 때문입니다. 예를 들어, 단일 랜덤 숫자를 사용하면 두 명의 서로 다른 입금자가 우연히 동일한 랜덤 숫자를 사용하여 생성된 Cn이 충돌할 수 있습니다.

위 그림의 A는 출금 받을 주소를 나타내며, 출금자가 직접 입력합니다. nf는 재전송 공격을 방지하기 위한 식별자입니다. nf의 값은 nf=Hash(K)이며, K는 입금 시 Cn을 생성하는 단계에서 사용된 두 개의 랜덤 숫자 중 하나입니다(K와 r). 이렇게 하면 nf가 Cn과 연관되며, 다시 말해 각 Cn은 해당 nf와 일대일로 연관됩니다.

왜 재전송 공격을 방지해야 할까요? 믹서의 설계 특성상, 출금 시 사용자가 인출한 자금이 Merkle Tree의 어떤 리프 Cn에 해당하는지 알 수 없으므로, 출금자와 어떤 입금자와의 연관성을 알 수 없으며, 출금자가 몇 번의 입금을 했는지 알 수 없습니다. 출금자는 이 특성을 이용하여 빈번하게 출금하고 재전송 공격을 시작하여 믹서 풀에서 여러 번 토큰을 인출할 수 있습니다. 결국 자금 풀을 고갈시킬 수 있습니다.

여기서 nf 식별자의 역할은 각 이더리움 주소에 있는 거래 카운터 nonce와 유사합니다. 이는 특정 거래가 재전송되는 것을 방지하기 위해 설정된 것입니다. 출금이 발생할 때, 출금자는 nf를 제출해야 하며, 이 nf가 이미 사용되었는지(기록됨)를 확인합니다: 만약 사용되었다면, 이번 출금은 무효입니다. 사용되지 않았다면, 해당 nf는 아직 사용되지 않은 것으로 간주되며, 출금이 유효하고 해당 nf는 기록됩니다. 다음에 누군가 이 nf를 제출하면, 해당 출금 행동은 무효로 판단됩니다.

누군가 임의로 생성한 계약에 기록되지 않은 nf가 가능할까요? 물론 불가능합니다. 출금자가 ZK Proof를 생성할 때 nf=Hash(K)를 보장해야 하며, 랜덤 숫자 K는 입금 기록 Cn과 연관되어 있습니다. 즉, nf는 특정 기록된 입금 Cn과 연관되어 있습니다. 임의로 nf를 조작하면, 이 nf는 입금 기록의 모든 입금과 일치하지 않으므로 유효한 ZK Proof를 생성할 수 없고, 이후 작업이 원활하게 진행되지 않으며, 출금 작업이 성공하지 않을 것입니다.

또한 누군가는 질문할 수 있습니다: nf 없이 진행할 수 있을까요? 출금자가 출금할 때 ZK 증명을 제출하여 자신과 특정 Cn이 연관되어 있음을 증명해야 하므로, 출금 행동이 발생할 때마다 해당 ZK Proof가 체인에 제출되었는지 확인하면 되지 않나요?

하지만 사실 이렇게 하는 것은 비용이 매우 높습니다. Tornado Cash 계약은 과거에 제출된 ZK Proof를 영구적으로 저장하지 않기 때문입니다. 이는 저장 공간을 심각하게 낭비하게 됩니다. 각 새로운 ZK Proof와 기존 Proof를 비교하는 것보다, 차지하는 공간이 매우 작은 식별자 nf를 설정하고 이를 영구적으로 저장하는 것이 더 경제적입니다.

출금 함수의 코드 예시에서 필요한 매개변수와 비즈니스 논리는 다음과 같습니다:

사용자는 ZK Proof, nf(Nullifier Hash) = Hash(K), 사용자 정의 수취 주소 recipient를 제출하며, ZK Proof는 Cn과 K, r의 값을 숨겨 외부에서 사용자의 신원을 판단할 수 없도록 합니다. recipient는 종종 깨끗한 새 주소를 입력하며, 개인 정보를 유출하지 않습니다.

하지만 여기서 작은 문제가 있습니다. 사용자가 출금할 때, 추적 불가능성을 위해 종종 새로 신청한 주소로 출금 거래를 시작합니다. 이때 새 주소에는 가스 비용을 지불할 ETH가 없습니다. 따라서 출금 주소가 출금을 시작할 때, 중계자(relayer)를 명시적으로 선언해야 하며, 이 중계자가 가스 비용을 대신 지불합니다. 이후 믹서 계약은 사용자 출금에서 일부를 중계자에게 보상으로 차감합니다.

결론적으로, Tornado Cash는 출금자와 입금자 간의 연관성을 숨길 수 있으며, 사용자가 많은 경우 마치 혼잡한 도심과 같아서 범인이 군중에 섞여 경찰이 추적하기 어려워집니다. 출금 과정에서 ZK-SNARK가 필요하며, 숨겨진 witness 부분은 출금자의 중요한 정보를 포함하고 있습니다. 이는 전체 믹서의 가장 중요한 점입니다. 현재로서는 Tornado가 ZK와 관련된 가장 기발한 응용 프로그램 중 하나일 가능성이 높습니다.

참고 자료 1.https://etherscan.io/address/0xa160cdab225685da1d56aa342ad8841c3b53f291#codeTornado 계약 소스 코드 2.https://mirror.xyz/mazemax.eth/BTbTOrEKzGkc-XoDcFtLPfJPtQ1Mt96BZYsW83m33IUTornado.cash 신구 버전 메커니즘 비교 3.https://www.youtube.com/watch?v=Z0s4W3UBxM8AnonymousPayments 4.https://medium.com/taipei-ethereum-meetup/zkp-study-group-tornado-cash-fdbb84d44b93[ZKP 독서 모임]TornadoCash 5.https://medium.com/taipei-ethereum-meetup/tornado-cash-%E5%AF%A6%E4%BE%8B%E8%A7%A3%E6%9E%90-eb84db35de04TornadoCash 사례 분석