trailofbits/quantum-zk-proof-pocGoogle의 ZK 증명을 무력화하는 양자 암호 분석 개념 증명 코드
이 저장소는 Trail of Bits 블로그 게시물의 리소스를 포함하며, Google이 타원 곡선 암호분석을 위한 고효율 양자 회로를 가지고 있다는 영지식 증명을 어떻게 깨뜨렸는지 상세히 설명합니다. 여기에는 우리가 위조한 증명, 검증 지침, 그리고 패치되지 않은 zkVM 시뮬레이터 코드의 취약점을 악용하는 양자 회로를 생성하는 코드가 포함되어 있습니다.
전체 증명 바이너리는 여기에 있으며, Google의 증명과 우리의 증명을 비교한 결과는 아래와 같습니다.
| Resource Type | Google’s Low-Gate | Google’s Low-Qubit | Our Proof |
|---|
| Total Operations | 17,000,000 | 17,000,000 | 8,300,000 |
| Number of Qubits | 1,425 | 1,175 | 1,164 |
| Toffoli Count | 2,100,000 | 2,700,000 | 0 |
증명 요약은 다음과 같습니다.
회로 SHA-256 해시: 0x7efe1f62bb14a978322ab9ed41d670fc0fe0f211331032615c910df5a540e999
Groth16 증명 바이트: 0x0e78f4db0000000000000000000000000000000000000000000000000000000000000000008cd56e10c2fe24795cff1e1d1f40d3a324528d315674da45d26afb376e8670000000000000000000000000000000000000000000000000000000000000000024ac7f8dd6b1de6279bcce54e8840d8eb20d522bf27dedd776046f6590f33add217db465201c63724e6b460641985543d2b79c3c54daeea688581676a786aafc1dba8604a361acdd9809e268b6d8bc73943a713bb0ed0d96221f73d26def6ea4041d05b077523d9351a48b2ecd984c686b6473df69d20a24296d0a1cba3cdbe92eb13a7cc0ecd92f27f7bf23f9ac859d4293e17216dcbd85d1c7f60a52f65a9d02faef077336acd39e845d534200b575b029d6e3f0afb4f90815557233eab70b0fe88919834dd9beb90d47241f1490dc202e0dce44e4894982b07073c8d4426513732d79e9af9913b254aa29471e1a98fa1b43a1886afb5dbd36988153217aa2
검증 키: 0x00ca4af6cb15dbd83ec3eaab3a0664023828d90a98e650d2d340712f5f3eb0d4
Google은 Zenodo 데이터셋에서 ZK 증명을 검증하기 위한 스크립트를 제공했습니다. 우리의 공격은 버전 1을 대상으로 하며, 버전 2에는 패치가 포함되어 있습니다. 의존성 설치 지침은 docs/getting_started.md에 있습니다. 환경에는 Rust, Go 및 선택적으로 Docker가 필요합니다. 검증 명령은 run_proofs.sh 끝부분에 제공됩니다. Google의 증명 아티팩트는 proofs/ 디렉토리에 있고, 우리의 증명 아티팩트는 proof_trailofbits.bin에 있습니다.
# Verify Google's proofs
cargo run --release -p verifier -- \
--vkey proofs/vkey.bin --proof proofs/low_toffoli/proof_9024.bin
cargo run --release -p verifier -- \
--vkey proofs/vkey.bin --proof proofs/low_qubits/proof_9024.bin
# Verify our proof
cargo run --release -p verifier -- \
--vkey proofs/vkey.bin --proof proof_trailofbits.bin
마지막 명령의 출력에는 다음이 포함됩니다.
Successfully verified Groth16 SNARK proof.
Circuit hash commitment: 0x7efe1f62bb14a978322ab9ed41d670fc0fe0f211331032615c910df5a540e999
Demanded Number of tests: 9024
Demanded Qubit count: 1164
Demanded Average non-Clifford count: 0
Demanded Total ops: 8300000
검증 명령은 ZK 증명을 검증 키(zkVM 게스트 프로그램의 간결한 암호학적 표현)와 대조하여 확인합니다. 또는 --elf proofs/zkp_ecc-program을 사용하여 검증기에 게스트 프로그램 ELF 바이너리를 제공할 수 있습니다. 이 플래그를 완전히 생략하면 검증기는 Docker 컨테이너를 사용하여 program/의 소스 코드에서 게스트 프로그램 바이너리를 다시 빌드합니다.
gen_secp256k1_tob.py를 실행하면 ec_secp256k1_add_into.kmx라는 142MB 크기의 kickmix 스크립트가 생성됩니다. 0-토폴리 증명을 달성하려면 prove.rs.diff를 사용하여 Zenodo 저장소의 prover/prove.rs를 패치하십시오. 이는 zkVM 외부에서 실행되는 신뢰할 수 없는 코드를 수정하여 kickmix 회로의 직렬화를 조작합니다.
증명 생성 지침은 Zenodo 저장소에 있습니다. 우리는 4개의 NVIDIA H100 GPU가 있는 클라우드 머신에서 docs/sp1_cluster_deployment_guide.md의 지침을 따라 증명을 생성하기 위해 다음 명령을 실행했습니다.
./run_proofs.sh --num-tests 9024 --kmx "ec_secp256k1_add_into.kmx" --qubit-counts 1164 --toffoli-counts 0 --total-ops 8300000 --proving-mode "multi-gpu" > proofs/ec_secp256k1_add/log_run.out 2>&1 &
위조 증명을 생성하는 데 약 4시간이 걸렸습니다.