STARK 알고리즘 분석

• 파트 0: 소개

• 1부: STARK 바라보기

• 파트 2: 유용한 "도구"

• 파트 3: 금

• 파트 4: STARK 다항식 IOP

• 파트 5: 구조 프라임 STARK

• 파트 6: 전체 프로세스 속도 향상

1. STARK란?

최근 암호 증명 시스템 분야에서 가장 흥미로운 개발 중 하나는 STARK의 개발이었습니다. 그것은 호황을 누리고있는 블록 체인 산업 이후에 나옵니다. 전반적으로 증명 시스템은 그들에게 맞춤화된 것으로 보입니다. 블록체인 네트워크는 종종 비밀 정보를 사용하여 거래하거나 상태 진화 규칙에 따라 집단 상태를 업데이트하려는 상호 불신 당사자들로 구성됩니다. 참가자는 상호 불신하기 때문에 동료가 제안한 트랜잭션(또는 상태 업데이트)의 유효성을 확인할 방법이 필요합니다.

zk-SNARK의 다음 속성으로 인해 자연스럽게 이 환경에서 계산 무결성 보장을 제공할 수 있습니다.

• zk-SNARK는 일반적으로 일반적입니다. 즉, 모든 계산의 무결성을 증명할 수 있습니다.

• zk-SNARK는 비대화형입니다. 즉, 전체 무결성 증명이 단일 메시지로 구성됩니다.

• zk-SNARK의 검증은 효율적입니다. 즉, 검증기의 작업량은 단순히 계산을 다시 실행하는 것보다 훨씬 적습니다(번역자 주: 몇 가지 크기도 가능함).

• zk-SNARK는 영지식이므로 비밀 입력 컴퓨팅에 대한 정보를 공개하지 않습니다.

"저는 zk-SNARK가 향후 10~20년 안에 주류 세계에 침투하여 주요 혁명을 이끌 것으로 기대합니다."—— "브이갓" 2021.9.2

zk-SNARK는 한동안 사용되어 왔지만 STARK 증명 시스템은 비교적 새로운 것입니다. 여러 가지 이유로 눈에 띕니다.

• 기존의 zk-SNARK는 정교한 암호화 퍼즐과 가정에 의존하지만 STARK 증명 시스템의 유일한 암호화 구성 요소는 충돌 방지 해시 함수입니다. 따라서 이상화된 해시 함수 모델 하에서 증명 시스템의 반양자 보안을 증명할 수 있습니다(문헌에서는 이러한 이상화를 "양자 랜덤 오라클 모델" 양자 랜덤 오라클 모델이라고 함). 이는 쌍선형 맵을 사용하고 위조할 수 없는 가정 하에서만 보안이 입증된 1세대 SNARK와 극명한 대조를 이룹니다.

• STARK의 산술화는 암호학적으로 어려운 문제와 무관하므로 성능을 최적화하기 위해 이 도메인을 특별히 선택할 수 있습니다. 따라서 STARK는 실제 빠른 증명(Prover)을 가능하게 합니다.

• 전통적인 zk-SNARK는 신뢰할 수 있는 설정 방식에 의존하여 공개 매개변수를 생성합니다. 의식이 끝난 후에는 사용된 임의의 매개변수를 안전하게 잊어버려야 합니다. 참가자가 이 암호화된 "위험한 쓰레기"를 삭제하는 것을 거부하거나 잊는 경우에도 증명을 위조할 수 있는 능력을 유지하기 때문에 의식 자체는 신뢰할 수 없습니다. 반대로 STARK에는 신뢰할 수 있는 설정이 없으므로 암호화가 없습니다."유해 폐기물".



"저는 일반적으로 다음 두 가지 사항에 대해 유보한다는 점에 동의합니다.

1) SNARK가 아닌 STARK가 지배할 것입니다.

2) 3-5년은 주류 세계에 침투할 것입니다.

지금부터 4년 후에 해당 단어를 테스트하도록 내 달력에 미리 알림을 설정합니다. ——엘리 벤-사손 2021.9.2

이 자습서에서는 이러한 부품 중 몇 개가 함께 작동하는지 설명합니다. 이 리터럴 설명은 Rescue-Prime 해시 함수를 기반으로 간단한 계산을 증명하고 확인하는 Python 구현에 의해 지원됩니다. 이 튜토리얼을 읽거나 따른 후에는 선택한 계산을 위해 자신만의 영지식 STARK 증명기 및 검증기를 작성할 수 있어야 합니다.

2. 이 글을 쓰는 이유는?

STARK 학습의 여러 소스가 있다는 것을 일찍 지적해야 합니다. 다음은 불완전한 목록입니다.

• FRI, STARK, DEEP-FRI에 관한 논문 및 FRI의 최신 신뢰성 분석

• Vitalik Buterin의 여러 부분으로 구성된 자습서(1/2/3부).

• StarkWare의 일련의 블로그 게시물(파트 1, 2, 3, 4, 5).

• StarkWare의 STARK@Home 웹캐스트

• StarkWare의 STARK 101 온라인 과정

• StarkWare의 EthStark 설명서

• 일반적으로 StarkWare가 내놓는 모든 것은

학습 리소스가 너무 많은데 왜 다른 자습서를 작성해야 합니까?

기존 튜토리얼은 상대적으로 얕습니다. 이 자습서는 이러한 기술이 어떻게 작동하는지 높은 수준에서 설명하고 STARK가 작동하는 이유에 대한 직관을 전달합니다. 그러나 완전한 배포 가능한 시스템을 설명하지는 않습니다. 예를 들어 튜토리얼 중 어느 것도 영지식을 구현하는 방법, 다양한 저수준 증명을 일괄 처리하는 방법 또는 결과 보안 수준을 결정하는 방법을 설명하지 않습니다. EthSTARK 문서는 이러한 대부분의 질문에 대한 답변을 제공하는 완전한 참조를 제공하지만 특정 계산에만 해당되며 지식이 전혀 포함되지 않으며 접근 가능하고 직관적인 설명을 제공하지 않습니다.

이 논문들은 이해하기 어렵습니다. 안타깝게도 과학 출판의 인센티브는 일반 독자가 과학 논문을 읽기 어렵게 만들기 위해 마련되었습니다. 따라서 더 많은 사람들이 이러한 문서를 이해할 수 있도록 하려면 이 문서와 같은 자습서가 필요합니다.

정보가 오래되었습니다. 이후 다양한 자습서에서 설명하는 많은 기술이 개선되었습니다. 예를 들어, EthSTARK 문서(위에서 인용한 최신 문서)는 제한된 차수의 다항식에 대한 올바른 평가에 대한 요구 사항을 줄이기 위해 DEEP 보간 기술을 설명합니다. 이 기술은 이러한 소스가 기술보다 선행하기 때문에 이러한 소스에서 언급되지 않습니다.

나는 내 스타일을 선호한다. 나는 많은 기호와 이름에 동의하지 않으며 사람들이 올바른 기호와 이름을 사용하기를 바랍니다. 특히 증명 시스템의 가장 기본적인 대상인 다항식에 집중하는 것을 좋아합니다. 대조적으로, 다른 모든 소스는 Reed-Solomon 코드워드에 대한 작업 측면에서 증명 시스템의 메커니즘을 설명합니다.

이 튜토리얼은 STARK를 더 잘 이해하는 데 도움이 되었습니다. 이 자습서를 작성하면 내 지식을 체계화하고 지식이 얕거나 완전히 부족한 부분을 찾는 데 도움이 되었습니다.

3. 필요한 배경지식

이 자습서는 필요에 따라 일부 배경 지식을 정리합니다. 그러나 여기 소개가 익숙하지 않은 경우 너무 조밀할 수 있으므로 모든 독자가 다음 주제를 이해하고 연구하는 것이 좋습니다.

• 유한 필드 및 해당 확장 필드

• 단변량 및 다변량 다항식을 포함한 유한 필드에 대한 다항식

• 해시 함수

• 해시 함수

4. 시리즈 마법사

• 파트 1: STARK 살펴보기는 높은 수준에서 개념과 워크플로를 설명합니다.

• 파트 2: 유용한 "도구"는 증명 시스템을 구축할 기본 수학 및 암호화 도구를 소개합니다.

• 3부: FRI는 증명 시스템의 암호화 핵심인 저수준 테스트를 다룹니다.

• Part 4: STARK Polynomial IOP（IOP,Interactive oracle proof) 임의의 계산 요구 사항에서 추상적 증명 시스템을 생성하기 위한 정보 이론을 설명합니다.

• 파트 5: Rescue-Prime STARK는 이러한 도구를 함께 사용하여 간단한 계산을 위한 투명한 영지식 증명 시스템을 구축합니다.

• 6부: 전체 프로세스 가속화 전체 프로세스를 더 빠르고 효과적으로 만드는 알고리즘과 기술 도입"S "(간결, 간결) STARK에 넣어

  5. 감사의 말

저자는 Bobbin Threadbare, Thorkil Værge 및 Eli Ben-Sasson의 유용한 피드백과 의견에 감사하고 Nervos 재단의 재정적 지원에 감사드립니다. alan@nervos.org로 이메일을 보내거나 twitter 또는 Github에서 aszepieniec을 팔로우하세요.

번역자 주: 원문에 링크된 문서가 많아 공식 계정의 한계로 인해 첨부할 수 없는 부분이 있으니 원문의 문서 링크를 참고하시기 바랍니다.

About zCloak Network

zCloak Network는 Polkadot 생태계를 기반으로 하는 사설 컴퓨팅 서비스 플랫폼으로 zk-STARK 가상 머신을 사용하여 일반 컴퓨팅을 위한 영지식 증명을 생성하고 검증합니다. 독자적인 자율 데이터와 자체 인증 컴퓨팅 기술을 기반으로 사용자는 데이터를 외부로 보내지 않고도 데이터를 분석하고 계산할 수 있습니다. Polkadot 크로스 체인 메시징 메커니즘을 통해 Polkadot 생태계의 다른 병렬 체인 및 기타 퍼블릭 체인에 데이터 개인 정보 보호 지원을 제공할 수 있습니다. 이 프로젝트는 원스톱 다중 체인 프라이버시 컴퓨팅 인프라를 구축하기 위해 "서비스로서의 영지식 증명" 비즈니스 모델을 채택할 것입니다.