SNARK(Succinct Non-interactive Argument of Knowledge)는 특히 분산 설정에서 시스템 설계에서 흥미로운 새로운 가능성을 열어주는 암호화 도구입니다. SNARK를 사용하면 신뢰할 수 없는 엔터티가 데이터를 처리할 수 있으며 해당 엔터티는 데이터가 유효하고 올바르게 처리되었음을 증명할 수 있습니다. 이를 증명하는 순진한 방법은 데이터를 게시하여 유효성을 확인하고 직접 처리할 수 있도록 하는 것입니다.
SNARK는 동일한 효과를 달성하지만 더 나은 비용으로검증인에게. 예를 들어, L2(레이어 XNUMX) 검증 가능한 롤업에서 롤업 서비스는 블록체인 트랜잭션을 처리합니다. 서비스는 주기적으로 사용자의 계정 잔액을 레이어 XNUMX 블록체인에 게시합니다. 잔고에 대한 업데이트를 게시할 때마다 이전 계정 잔고를 업데이트된 것으로 변경한 일련의 유효한 거래를 알고 있다는 SNARK 증거를 추가합니다. 이러한 방식으로 블록체인 검증자는 트랜잭션 유효성을 확인하는 힘든 작업(예: 각 트랜잭션에 대한 디지털 서명 확인)을 수행하거나 업데이트된 잔액을 계산하기 위해 트랜잭션을 명시적으로 처리할 필요가 없습니다.
My 이전 게시물 SNARK 적용 가능성의 주요 결정 요인인 SNARK 증명자의 성능에 중점을 둡니다. SNARK 증명자를 실행하는 것은 계산 집약적일 수 있지만 대규모 계산에 대한 증명을 생성하는 것이 불가능할 수 있는 정도까지 SNARK 검증은 일반적으로 데이터를 직접 확인하고 처리하는 것보다 훨씬 저렴합니다. 그러나 SNARK 검증 비용은 상당히 다양합니다. 이 게시물은 이러한 비용을 풀고 다양한 SNARK의 보안 속성을 비교합니다.
특히 PQ-SNARK(plausible post-quantum security)가 있는 실용적인 SNARK에서는 보안과 검증 비용 사이에 상당한 긴장이 있다고 설명합니다. 더욱이 어떤 경우에는 현재 이 긴장이 보안보다 검증 비용으로 해결되고 있습니다.
SNARK가 잠재력을 실현하려면 배포된 시스템이 안전해야 하고 사용자가 보안에 대해 확신해야 합니다. 나는 web3 커뮤니티가 이러한 속성을 장기적으로 유지하는 데 도움을 줄 수 있는 간단한 조치를 제안하는 것으로 게시물을 마무리합니다.
양적 보안 조치
SNARK는 거짓 진술에 대한 설득력 있는 증거를 생성하는 것이 계산적으로 실행 불가능한 경우 안전합니다. 예를 들어, L2 롤업의 맥락에서 내 자금을 훔치려는 공격자는 "저는 Justin의 모든 자산을 내 계정으로 전송하는 디지털 서명된 거래를 알고 있습니다."라는 형식의 거짓 진술을 증명하기를 원할 것입니다.
SNARK의 보안 수준은 거짓 진술에 대한 설득력 있는 증거를 찾기 위해 수행해야 하는 작업의 양으로 측정됩니다. 디지털 서명과 같은 다른 암호화 기본 형식과 유사하게 이 작업량의 로그를 "보안 비트"라고 합니다. 예를 들어 30비트 보안은 2를 의미합니다.30 ≈ SNARK를 공격하려면 1억 개의 "작업 단계"가 필요합니다. 한 작업 단계의 개념이 다를 수 있고 메모리 요구 사항이나 병렬 처리 기회와 같은 실질적인 고려 사항은 고려되지 않기 때문에 이것은 본질적으로 실제 보안의 대략적인 측정입니다.
그리고 질적인 것들
약간의 보안은 정량적 인 SNARK의 보안 측정. SNARK는 또한 성질의 보안 속성.
예를 들어, 일부 SNARK는 구조화된 증명 키를 생성하기 위해 신뢰할 수 있는 설정 방식이 필요합니다. 신뢰할 수 있는 설정이 전혀 필요하지 않은 SNARK는 투명한.
투명하지 않은 SNARK가 안전하려면 일반적으로 의식에 참석한 적어도 한 명의 참가자가 정직하게 행동해야 합니다. 즉, 다른 모든 참가자의 트랩도어와 결합하면 쉽게 만들 수 있는 "트랩도어"를 생성한 다음 폐기했습니다. 거짓 진술에 대한 설득력 있는 SNARK "증거"를 찾기 위해. 신뢰할 수 있는 설정은 존재 운영 이 가정을 가능한 한 가볍게 만들기 위해 수백 또는 수천 명의 참가자와 함께.
SNARK는 양자 공격에 대한 취약성도 다릅니다. 특히, 많은 SNARK(예: 그로스16, 플롱케이, 돛새치과의 큰 물고기, 방탄, 신성) 이산 로그는 계산하기 어렵다는 가정에 의존합니다(경우에 따라 추가 가정도 포함). 이산 로그를 계산하는 것은 양자 컴퓨터가 효율적으로 수행할 수 있는 것입니다. 따라서 이러한 SNARK는 사후 양자 보안(비PQ)이 아닙니다.
포스트 퀀텀으로의 전환이 시급한 가운데 암호화 체계, 이는 주로 암호화된 메시지를 향후 수십 년 동안 비밀로 유지해야 할 필요성에 의해 주도됩니다. 도청된 메시지를 오늘 저장하고 양자 컴퓨터가 XNUMX년 후에 도착하기를 기다리는 공격자는 컴퓨터를 사용하여 XNUMX년 된 메시지를 해독할 수 있습니다. SNARK의 상황은 상당히 다릅니다. 현재 PQ가 아닌 SNARK를 사용한다고 해서 XNUMX년 후의 블록체인 보안이 손상되어서는 안 됩니다. 그 시기에 양자 컴퓨터가 도착하더라도 말입니다.
다항식 약정
모든 SNARK는 다항식 확약 방식, 이 구성 요소는 종종 성능 병목 현상이 됩니다.. (자세한 내용은 내 이전 게시물.) 또한 SNARK의 투명성과 그럴듯한 사후 양자 보안은 사용하는 다항식 확약 방식에 의해서만 결정됩니다.
대표적인 예가 이른바 KZG 다항식 약정, 에 의해 사용되는 플롱케이, 돛새치과의 큰 물고기, 그리고 많은 다른 사람들. KZG 약속은 투명하지도 않고 양자 이후에 안전하지도 않습니다. 다음을 포함한 기타 공약 계획은 투명하지만 사후 양자화되지 않습니다. 방탄, 하이락스및 평저 어선.
또 다른 계획은 투명하고 그럴듯하게 포스트 퀀텀(post-quantum)입니다. 여기에는 다음이 포함됩니다. 무료, 리게로, 리게로++, 분류및 오리온. 이러한 체계는 모두 오류 수정 코드를 기반으로 합니다. 해싱은 그들이 사용하는 유일한 암호화 프리미티브입니다. 그들은 또한 다음과 같은 속성을 공유합니다. 검증 비용(해시 평가 및 현장 작업 수로 측정)은 보안 비트 수에 따라 선형적으로 증가합니다.
대략적으로 말하자면, 이러한 양자 후 다항식 약속의 단일 "반복"은 적은 수(예: 2-4) 비트의 보안만 달성합니다. 따라서 보안 수준을 "증폭"하려면 프로토콜을 여러 번 반복해야 하며 반복할 때마다 검증 비용이 증가합니다. 따라서 PQ-SNARK의 검증 비용(따라서 블록체인 애플리케이션의 가스 비용)을 제어하기 위해 프로토콜 설계자는 보안 수준을 낮게 유지하도록 장려됩니다.
희귀 예외, 구체적인 보안과 검증 비용 사이의 이러한 긴장은 PQ가 아닌 SNARK(투명 및 불투명 모두)에서는 발생하지 않습니다. 비 PQ-SNARK는 이산 로그를 계산하기 어려운 것으로 추정되는 타원 곡선 그룹을 사용하고 보안 수준은 사용된 그룹에 의해 결정됩니다. 적절한 타원 곡선 그룹의 크기와 그에 따른 각 그룹 작업의 비용은 원하는 보안 수준에 따라 증가합니다. 그러나, 그 번호 증명에서 그룹 요소의 수는 그룹 선택과 무관합니다.
PQ-SNARK에서 해시 평가의 크기는 원하는 보안 수준에 따라 선형적으로 증가할 뿐만 아니라 증명에 포함되고 검증자가 수행하는 평가의 수도 증가합니다.
배포된 SNARK의 구체적인 검증자 비용 및 보안
배치된 SNARK의 구체적인 검증자 비용과 보안 수준은 상당히 다양합니다. 다음은 몇 가지 예시입니다.
검증인 비용
My 이전 게시물 구체적인 검증 비용의 두 가지 예를 언급했습니다. 플롱케이 증명 비용 아래에 300,000 가스 이더리움에서 검증하는데 StarkWare의 증명 비용은 약 5백만 가스입니다. StarkWare의 증명은 투명하고 그럴듯하게 포스트 퀀텀인 반면 PlonK는 그렇지 않습니다. 그러나 다음에 자세히 설명하는 것처럼 StarkWare의 증명은 Ethereum에서 PlonK 증명보다 훨씬 낮은 보안 수준에서 실행되고 있습니다.
구체적인 보안
이더리움 사전 컴파일이 포함된 유일한 타원 곡선은 altbn128입니다. 따라서 이 곡선은 다음을 포함하여 이더리움 사용에 배포된 모든 비 PQ SNARK입니다. 아즈텍'모래 zkSync'에스. 이 곡선과 이를 사용하는 배포된 SNARK는 원래 대략 128비트의 보안을 제공하는 것으로 믿어졌습니다. 그러나 때문에 향상된 공격 (정확한 런타임은 결정하기 어렵다.), 이제 곡선은 100~110비트의 보안을 제공하는 것으로 널리 알려져 있습니다.
EIP가 있습니다. 아래에 고려 여전히 128비트에 가까운 보안을 제공하는 것으로 여겨지는 다양한 곡선에 대한 사전 컴파일을 도입합니다. 이러한 곡선은 이미 사용 된 ZCash, Algorand, Dfinity, Filecoin 및 Aleo를 포함한 비 이더리움 프로젝트의 SNARK에서.
대조적으로, 온체인 데이터에 따르면 StarkWare의 PQ-SNARK(소위 SHARP 시스템에서 SHARed Prover의 약어)는 80비트 보안을 목표로 구성되었습니다. 이 보안 수준은 FRI의 통계적 건전성에 대한 특정 추측에 따라 유지됩니다(이 게시물의 뒷부분에서 다루겠습니다).
"80비트 보안"이라는 용어는 이 맥락에서 모호하므로 풀어보도록 하겠습니다. 대략적으로 말하자면, 공격자가 해시 함수 2를 평가하여 거짓 진술에 대한 설득력 있는 증거를 생성할 수 있음을 의미합니다.80 시간(즉, 이더리움에서 사용하는 해시 함수인 KECCAK-256). 좀 더 정확히 말하자면 2번을 수행할 의향이 있는 공격자는k 해시 평가는 대략 2의 확률로 설득력 있는 증거를 생성할 수 있습니다.k-80. 예를 들어 270 해시 평가에서 약 2의 확률로 거짓 진술의 SNARK "증거"를 찾을 수 있습니다.-10 = 1/1024.
이 개념은 "80비트 보안"이라는 용어가 다른 컨텍스트에서 의미하는 것보다 약합니다. 예를 들어, 80비트 보안으로 구성된 충돌 방지 해시 함수(CRHF)는 160비트 출력을 생성합니다. 해시 함수가 잘 설계된 경우 가장 빠른 충돌 찾기 절차는 생일 공격, 약 2와 충돌을 찾을 수 있는 무차별 대입 절차160/2 = 280 해시 평가. 그러나 2와k 해시 평가, Birthday 공격은 2의 확률로 충돌을 찾습니다.2k-160.
예 : 270 해시 평가는 2의 확률로 충돌을 생성합니다.-20 ≈ 1/1,000,000 이는 공격자가 1비트 보안으로 구성된 PQ-SNARK 증명을 위조할 확률의 1,000/80보다 훨씬 작습니다.
이 차이는 공격 수행의 매력을 크게 바꿀 수 있습니다. 설명을 위해 공격자가 $100의 예산을 가지고 있다고 가정해 보겠습니다.70 해시 평가. 그리고 공격자가 성공할 경우 그 결과는 200억 달러라고 가정합니다. 80비트 보안으로 구성된 PQ-SNARK에 대한 공격의 예상 가치는 (1/1,000) * $200억 또는 $200K - 비용의 두 배입니다. CRHF와 같이 성공 확률이 1/1,000,000인 경우 공격의 예상 가치는 $200에 불과합니다.
"80비트 보안"이라는 두 가지 개념은 독립적인 공격에 대한 견고성에서도 크게 다릅니다. 예를 들어, 1,000개의 독립 당사자가 각각 2를 수행하여 PQ-SNARK를 공격한다고 가정합니다.70 해시 평가. 각각 약 1/1,000의 확률로 성공하기 때문에 적어도 하나는 성공할 가능성이 큽니다. 각각이 1/1,000,000의 확률로 성공했다면 그렇지 않을 것입니다.
잘 설계된 타원 곡선 그룹은 CRHF와 유사하게 동작할 것으로 예상되며, 다음과 같은 생일 같은 공격이 있습니다. Pollard의 rho 알고리즘 가장 잘 알려져 있습니다. 이는 128비트 보안을 제공하는 그룹에서 2k 그룹 연산은 확률이 2인 이산 로그 문제의 인스턴스에 대한 솔루션을 산출해야 합니다.2k-256. 예 : 270 그룹 연산은 천문학적으로 작은 확률이 2인 이산 로그를 찾습니다.-116. 또한 각 그룹 작업은 CRHF 평가보다 느립니다.
오늘날 얼마나 많은 해시 평가가 가능합니까?
2020년 2월에는 컴퓨팅 비용이 XNUMX에 불과합니다.64 GPU를 사용한 SHA-1 평가는 $45,000. 이것은 2의 비용을 넣습니다.70 GPU에 대한 SHA-1 평가는 수백만 달러(이더리움 병합 후 더 낮아질 수 있음, GPU가 지배하는 작업 증명 마이닝에서 전환이 GPU 컴퓨팅에 대한 수요를 감소시켜 비용을 낮출 가능성이 있음)할 수 있기 때문입니다.
유효성 롤업이 이미 사용자 자금에 수억 달러를 저장하고 있는 상황에서 허위 진술에 대한 설득력 있는 증거를 찾는 것은 수백만 달러의 이익을 가져올 수 있습니다. 공격적인 추측에서 80비트 보안으로 PQ-SNARK를 구성하면 수익성 있는 공격과 PQ-SNARK의 추측된 보안 사이에 10비트 미만의 흔들림 공간이 남습니다.
또 다른 데이터 포인트로 비트코인의 네트워크 해시율은 현재 약 264 초당 해시 평가, 즉 비트코인 광부 전체가 2를 수행합니다.80 256시간마다 SHA-18 평가. 물론 이 놀라운 수치는 비트코인 채굴을 위한 ASIC에 대한 막대한 투자 때문입니다.
가정 여섯 개의 비트코인 블록 시간당 생성되고 블록당 6.25비트코인의 현재 블록 보상을 감안할 때 이 2개80 SHA-256 평가 비용은 $22,000 * 18 * 6 * 6.25 ≈ $15만 미만인 것으로 추정됩니다. 그렇지 않으면 비트코인 채굴은 현재 가격으로 수익성이 없을 것입니다.
건강한 생태계를 위한 제안된 조치
롤업에서 SNARK를 사용하는 요점은 사용자가 롤업 서비스를 맹목적으로 신뢰할 필요 없이 블록체인 확장성을 달성하는 것입니다. 롤업 서비스는 SNARK 검증자 역할을 하는 스마트 계약을 작성했기 때문에 대중은 계약을 검사하고 해당 진술의 SNARK 증명을 실제로 검증하고 있는지 확인할 수 있어야 합니다. 롤업 서비스가 자체 사용자를 검열할 수 없도록 하기 위해 스마트 계약에 대한 공개 조사가 필요할 수도 있습니다. 검열 저항을 위해 제안된 방법은 롤업 서비스가 거래를 처리하지 못하는 경우 사용자가 자금을 강제로 인출할 수 있도록 하는 롤업의 스마트 계약을 요구합니다.
이러한 프로토콜의 정교한 특성을 감안할 때 이러한 공개 조사 패러다임은 배포된 계약의 보안을 공개적이고 솔직하게 논의해야 하는 전문가에게 약간의 부담을 줍니다.
그러나 PQ-SNARK를 사용하면 이러한 SNARK에 대한 보안 및 검증자 성능이 긴장되는 것과 같은 이유로 전문가라도 배포된 프로토콜의 보안 수준을 확인하기 어려울 수 있습니다. 보안 수준(및 검증자 비용)은 내부 매개변수에 따라 다릅니다. 스나크. 그리고 적어도 StarkWare의 경우 현명한 계약, 이러한 매개변수를 호출합니다.d logBlowupFactor, proofOfWorkBits 및 n_Queries는 스마트 계약의 코드에 직접 지정되지 않고 공개 데이터로 스마트 계약에 전달됩니다. 내가 아는 한, 온체인 정보에서 이러한 매개변수를 식별하는 가장 쉬운 방법은 XNUMX단계 프로세스를 사용하는 것입니다.
- 보기 적절한 스마트 계약 Etherscan과 같은 블록 익스플로러에서
- 클릭 적절한 "증거 확인" 거래,
- 트랜잭션의 입력 데이터를 디코딩하고
- 방법을 알아 내다 해석하다 디코딩된 입력 데이터를 사용하여 보안 수준을 함께 결정하는 주요 SNARK 매개변수를 학습합니다.
이 마지막 단계에서는 트랜잭션을 구현하는 적절한 Solidity 코드를 찾아야 하며, 이는 그 자체로 혼란스러운 작업일 수 있습니다. (제가 준비할 때 측량 협의 이번 여름 롤업에서 Etherscan은 위의 2단계에 따라 관련 입력 데이터를 SHARP 검증자 트랜잭션으로 디코딩할 수 있었습니다. 그러나 더 이상 작동하지 않는 것 같습니다.)
제안 1: 조사
이를 염두에 두고 web3 커뮤니티에 대한 저의 첫 번째 제안은 배포된 포스트 퀀텀 SNARK의 보안 수준을 훨씬 더 쉽게 조사할 수 있도록 하는 것입니다. 여기에는 온체인 데이터를 이해하기 위한 더 나은 도구와 이러한 매개변수를 알리는 프로젝트 자체의 투명성 증가가 포함될 수 있습니다.
제안 2: 더 강력한 규범
80비트 보안은 너무 낮습니다. 특히 270 해시 평가는 약 1/1000의 확률로 성공적으로 공격하기에 충분합니다. 암호화 기본 요소에 대한 놀라운 공격의 오랜 역사를 고려할 때 더욱 그렇습니다. 위에서 언급한 하나는 altbn128과 같이 짝짓기 친화적 타원 곡선에 대한 더 나은 공격입니다. 더 유명한 예는 1비트 보안으로 표준화되었지만 결국 약 80비트만 달성하는 것으로 나타난 SHA-60입니다. 이러한 역사를 염두에 두고 PQ-SNARK 설계자는 보안 수준을 구성할 때 10비트 이상의 흔들림의 여지를 남겨 두어야 합니다. 특히 보안 분석에 FRI와 같은 비교적 새로운 프로토콜의 통계적 보안에 대한 강력한 추측이 포함되는 경우에는 더욱 그렇습니다.
PQ-SNARK의 경우에도 단순히 검증 비용을 증가시키는 것만으로 적절한 보안 수준을 항상 달성할 수 있습니다. 예를 들어, SHARP의 검증기의 보안을 80에서 128비트로 높이면(FRI의 통계적 건전성에 대한 추측에 따라) 가스 비용이 5백만에서 10천만 약간으로 대략 20배 증가합니다. FRI에 대한 추측이 없다면 가스 비용은 또 다른 XNUMX배 증가한 XNUMX천만 달러 이상으로 증가할 것입니다.
내 다음 제안은 web3 커뮤니티가 배포된 SNARK에 대한 적절한 보안 수준에 대해 더 강력한 규범을 개발해야 한다는 것입니다. 내 개인적인 권장 사항은 최소 100비트이고 SNARK의 보안이 비표준 가정을 기반으로 하는 경우 최소 128비트입니다. 나는 처음이 아니다. 그런 제안을 하다.
여기에서 나는 기꺼이 "표준 가정"의 무조건적 보안으로 분류하고 싶습니다. 랜덤 오라클 모델, 배포된 SNARK의 임의 오라클이 KECCAK-256과 같은 표준 해시 함수로 인스턴스화되는 경우. 임의의 오라클 모델은 잘 설계된 암호화 해시 함수의 동작을 캡처하기 위한 이상적인 설정입니다. PQ-SNARK의 보안을 분석하는 데 자주 사용됩니다.
비표준 가정의 예로는 FRI와 같은 프로토콜의 양적 건전성에 관한 추측(아래 설명)이 있습니다.
SNARK 디자이너는 많은 흥미로운 방식으로 혁신하고 있으며, 그 중 일부는 보안 측면에서 한계를 뛰어 넘을 수 있습니다. 예를 들어 더 많은 표준 해시 함수만큼 많은 암호 분석을 거치지 않은 SNARK 친화적인 해시 함수를 사용합니다. 나는 그러한 노력의 끝을 요구하는 것이 아닙니다. 그러나 이러한 기본 요소는 알려진 가능한 공격을 10비트 이상 초과하는 보안 수준에서 인스턴스화해야 합니다.
SNARK를 사용하는 롤업은 일반적으로 L1의 보안을 상속하는 것으로 설명됩니다. 그러나 L1에서 사용하는 암호화 기본 요소보다 훨씬 낮은 보안 수준으로 구성된 경우에는 어려운 경우입니다. SNARK의 채택이 증가함에 따라 SNARK에 대해 이야기하는 방식과 일관된 방식으로 SNARK를 배포해야 합니다. SNARK가 주의 깊게 분석되고, 적절하게 구성되고, 올바르게 구현되는 한, 오늘날 사용되는 모든 암호화 기본 요소만큼 안전합니다.
제쳐두고: PQ-SNARK 보안에 대해 더 자세히 알아보기
StarkWare의 PQ-SNARK의 80비트 보안은 다음과 같이 설명됩니다. 이러한 PQ-SNARK는 다항식 확약 방식을 사용합니다. 무료, 그리고 StarkWare의 SHARP 검증기는 추측하에 48비트 보안에서 FRI를 실행합니다. 대략적으로 말하면 FRI의 건전성에 대한 단순한 공격이 최적이라는 추측이다. 이 공격에서 부정 행위 증명자는 적은 노력으로 검증자가 무작위로 선택한 검사를 확률 2로 통과하는 "FRI 증명"을 생성합니다.-48.
StarkWare는 FRI와 "연삭"이라는 기술을 결합합니다. 이를 위해서는 정직한 증명자가 FRI 증명을 생성하기 전에 32비트 작업 증명을 생성해야 합니다. 그라인딩의 장점은 부정행위 증명자가 위에서 언급한 FRI에 대한 단순 공격을 수행하는 데 필요한 작업을 약 2로 대폭 증가시킨다는 것입니다.32 해시 평가.
(기대에) 2 이후48 단순 공격 시도는 그 중 하나가 성공하기 전에 필요합니다. 부정 행위 증명자가 FRI 증명을 위조하기 위해 수행해야 하는 총 작업량은 대략 2입니다.48 * 232 = 280 해시 평가.
마지막으로 FRI를 위한 48비트 보안이 어떻게 발생하는지 살펴보겠습니다. FRI 검증자는 커밋된 다항식에 "쿼리"를 수행합니다. FRI 검증 비용은 쿼리 수에 따라 선형적으로 증가합니다. 예를 들어, 36개의 FRI 검증자 쿼리는 4개의 쿼리보다 약 9배 비용이 많이 듭니다. 그러나 더 많은 쿼리는 더 많은 보안을 의미합니다. "쿼리당 보안 비트"의 수는 코드 속도라고 하는 FRI의 다른 매개변수에 따라 다릅니다.
특히, FRI는 Reed-Solomon code of rate라는 것을 사용합니다. r어디로 r 항상 0과 1 사이의 숫자입니다. FRI 증명자의 비용은 에 반비례합니다. r, 따라서 1/16의 비율은 ¼의 비율보다 약 XNUMX배 느리고 공간 집약적인 증명자가 됩니다.
SHARP 검증자는 1/16의 코드율과 12개의 검증자 쿼리로 FRI를 실행했습니다.
StarkWare는 각 FRI 검증자 쿼리가 로그를 추가한다고 추측합니다.2(1 /r) 약간의 보안. 이 추측에 따르면 12개의 검증자 쿼리는 12 * log를 생성합니다.2(16) = 48비트 보안.
그러나 현재 분석에서는 각 검증자 쿼리가 로그보다 약간 적게 추가한다는 사실만 확인했습니다.2(1/r1/2) 약간의 보안. 따라서 12개의 FRI 검증자 쿼리는 12 * log 미만만 산출합니다.2(4) = "증명 가능한" 보안의 24비트.
보안과 성능 간의 긴장 완화를 위한 제안
실용적인 PQ-SNARK에는 원하는 보안 비트 수에 따라 선형적으로 증가하는 검증자 비용이 있습니다. 이 긴장을 완화하기 위한 한 가지 유망한 기술은 SNARK 구성입니다. 이전 게시물에서 증명자와 검증자 비용 간의 긴장을 해결하는 수단으로 설명했지만 보안 문제도 해결할 수 있습니다.
두 가지 예
폴리곤 헤르메즈는 PlonK로 PQ-SNARK 구성. 아이디어는 증명자가 먼저 PQ-SNARK 증명 π를 생성한다는 것입니다. PQ-SNARK가 빠른 증명자와 적절한 보안 수준을 갖도록 구성되면 π가 커집니다. 따라서 증명자는 π를 검증자에게 보내지 않습니다. 대신 PlonK를 사용하여 π를 알고 있음을 증명합니다.
이는 π를 입력으로 사용하고 PQ-SNARK 검증기가 π를 수용하는지 확인하는 회로에 PlonK를 적용하는 것을 의미합니다. PQ-SNARK는 다대수 검증 비용이 있기 때문에 PlonK를 작은 회로에 적용하므로 PlonK Prover가 빠릅니다. PlonK 증명은 작고 검증 비용이 저렴하기 때문에 검증 비용이 저렴합니다.
불행히도 PlonK를 사용하면 투명성과 사후 양자 보안이 파괴됩니다. 대신 PlonK 대신 PQ-SNARK 자체를 사용하여 π에 대한 지식을 증명할 수 있습니다(실제로 Polygon에서 사용하는 PQ-SNARK은 이러한 방식으로 자체 구성됨).
PQ-SNARK의 두 번째 응용 프로그램에서 π에 대한 지식을 증명하기 위해 시스템은 예를 들어 FRI에서 사용하기 위해 매우 작은 코드 속도를 선택하여 합리적인 크기의 증명으로 적절한 보안을 달성하도록 구성할 수 있습니다. 요점은 이 작은 코드율이 Prover 시간에 좋지 않지만 PQ-SNARK의 두 번째 적용은 작은 회로에만 적용되므로 전체 Prover 시간은 여전히 작아야 한다는 것입니다.
구성된 SNARK의 보안에 대한 우리의 이론적 이해는 많이 부족합니다. 그러나 구성 SNARK 중 하나를 개별적으로 공격하는 것보다 빠른 공격은 알려져 있지 않습니다. 예를 들어, PlonK로 PQ-SNARK를 구성하는 경우 PQ-SNARK를 공격하거나(즉, 거짓 진술의 PQ-SNARK 증명 π 찾기) PlonK를 공격하는 것(즉, "검증자가 수락했을 PQ-SNARK 증명 π를 알고 있습니다."라는 잘못된 진술에 대한 PlonK 증명을 찾습니다.)
이러한 방식으로 SNARK를 구성하는 것은 성능을 개선하기 위해 점점 더 인기 있는 방법입니다. 프로토콜 설계자도 이를 사용하여 보안을 개선하기를 바랍니다.
***
저스틴 탈러 조지타운 대학교의 부교수입니다. Georgetown에 합류하기 전에 그는 뉴욕에 있는 Yahoo Labs에서 연구원으로 XNUMX년을 보냈으며 그 전에는 시몬스 컴퓨팅 이론 연구소 UC Be에서르켈리.
편집자: 팀 설리반 @tim_org
***
여기에 표현된 견해는 인용된 개별 AH Capital Management, LLC("a16z") 직원의 견해이며 16z 또는 그 계열사의 견해가 아닙니다. 여기에 포함된 특정 정보는 16z가 관리하는 펀드의 포트폴리오 회사를 포함하여 제16자 출처에서 얻은 것입니다. 신뢰할 수 있다고 여겨지는 출처에서 가져왔지만 16z는 그러한 정보를 독립적으로 검증하지 않았으며 정보의 지속적인 정확성이나 주어진 상황에 대한 적절성에 대해 어떠한 진술도 하지 않습니다. 또한 이 콘텐츠에는 타사 광고가 포함될 수 있습니다. XNUMXz는 그러한 광고를 검토하지 않았으며 여기에 포함된 광고 콘텐츠를 보증하지 않습니다.
이 콘텐츠는 정보 제공의 목적으로만 제공되며 법률, 비즈니스, 투자 또는 세금 관련 조언에 의존해서는 안 됩니다. 그러한 문제에 관해서는 자신의 고문과 상의해야 합니다. 증권 또는 디지털 자산에 대한 언급은 설명을 위한 것일 뿐이며 투자 추천이나 투자 자문 서비스 제공을 의미하지 않습니다. 또한, 이 콘텐츠는 투자자 또는 예비 투자자를 대상으로 하거나 사용하도록 의도되지 않았으며, 어떤 상황에서도 a16z가 관리하는 펀드에 투자하기로 결정할 때 의존할 수 없습니다. (16z 펀드에 대한 투자 제안은 사모 투자 각서, 청약 계약서 및 해당 펀드의 기타 관련 문서에 의해서만 이루어지며 전체 내용을 읽어야 합니다.) 언급되거나 언급된 모든 투자 또는 포트폴리오 회사 설명된 내용은 16z가 관리하는 차량에 대한 모든 투자를 대표하는 것은 아니며 투자가 수익성이 있거나 미래에 수행되는 다른 투자가 유사한 특성 또는 결과를 가질 것이라는 보장이 없습니다. Andreessen Horowitz가 관리하는 펀드의 투자 목록(발행자가 16z가 공개적으로 공개하도록 허가하지 않은 투자 및 공개적으로 거래되는 디지털 자산에 대한 미고지 투자 제외)은 https://a16z.com/investments에서 볼 수 있습니다. /.
내부에 제공된 차트와 그래프는 정보 제공의 목적으로만 사용되며 투자 결정을 내릴 때 의존해서는 안 됩니다. 과거의 성과는 미래의 결과를 나타내지 않습니다. 내용은 표시된 날짜 현재만 말합니다. 이 자료에 표현된 모든 예측, 추정, 예측, 목표, 전망 및/또는 의견은 예고 없이 변경될 수 있으며 다른 사람이 표현한 의견과 다르거나 반대될 수 있습니다. 추가 중요 정보는 https://a16z.com/disclosures를 참조하십시오.
