하나의 기사에서 Ethereum 2.0의 셔플링 알고리즘 읽기
저자 |Ben Edgington
소개
저자 |소개배우고 싶다면
고스트 스텝 댄스
(셔플 댄스), 당신은 잘못된 장소에 있습니다. 하지만 저를 믿으세요. Eth2의 셔플도 마찬가지로 흥미진진합니다.셔플 목록은 Ethereum 2.0의 기본 작업입니다. 주로 12초 슬롯마다 위원회를 구성할 검증자를 의사 무작위로 선택하고 슬롯마다 비콘 체인 블록에 대한 제안자를 선택하는 데 사용됩니다.셔플은 상당히 간단해 보입니다. 그것은 약간을 가지고 있지만Fisher-Yeats shuffle숨겨진 위험
위로. 그렇다면 Eth2에서 사용하지 않는 이유는 무엇입니까? 기사 끝 부분에서 자세히 설명하지만 간단히 설명하겠습니다.종이종이Teku가운데. 나는 최근에 Eth2 클라이언트에 있습니다가운데
고쳐 쓰기
우리의 구현이므로 아직 뜨거울 때 작성하고 싶었습니다.
Swap-or-Not 셔플링 알고리즘
운영 라운드
셔플은 라운드로 수행됩니다. 과정은 각 회차마다 동일하므로 보기보다 훨씬 간단한 1회차 과정만 아래에서 보여드리겠습니다.
먼저 라운드 및 기타 시드 데이터를 기반으로 의사 무작위로 선택되는 피벗 인덱스 p를 선택합니다. 축을 선택하면 라운드에서 고정됩니다.
이 피벗 포인트를 기준으로 p와 0 사이의 중간 포인트, 즉 m1=p/2에서 미러 인덱스 m1을 선택합니다. (설명을 위해 번거로운 one-by-one 오류 반올림 문제는 무시하겠습니다)
이미지 설명
피벗 포인트 및 첫 번째 미러 인덱스
2. 첫 번째 미러 인덱스에서 피벗 포인트까지 교체 여부
미러 인덱스 m1과 피벗 인덱스 p 사이의 각 인덱스에 대해 해당 요소를 교체할지 여부를 무작위로 결정합니다.
교체하기로 결정하면 i1의 목록 요소를 미러 인덱스의 이미지인 i1'의 요소로 교체합니다. 즉, i1을 i1'=m1-(i1-m1)로 치환하여 i1과 i1'에서 m1까지의 거리가 동일하도록 한다.
우리는 m1과 p 사이의 각 인덱스에 대해 동일한 교환 여부 결정을 내립니다.
이미지 설명
3. 두 번째 미러 인덱스 계산
m1에서 p까지의 모든 인덱스 결정을 내린 후 이제 m2를 중간점, 즉 p에서 등거리에 있는 지점과 목록의 끝으로 두 번째 미러 인덱스를 찾습니다. 즉 m2=m1+n/2입니다.
이미지 설명
4. 피벗 포인트에서 두 번째 미러까지 교체 여부
마지막으로 모든 점 대 피벗 p 교체 결정, 즉 p에서 두 번째 미러 m2로의 결정을 고려하여 교체 여부 프로세스를 반복합니다. 교체하지 않기로 선택하면 다음 교체로 넘어갑니다. 교체를 선택하면 j1의 요소를 미러 인덱스 m2에서 j1'의 미러 이미지로 교체합니다.
이미지 설명
피벗에서 두 번째 미러 인덱스로 교환 여부 결정
라운드가 끝날 때 우리는 m1과 m2 사이의 모든 인덱스, 즉 모든 인덱스의 절반을 고려했으며 각 인덱스는 대체 여부에 관계없이 나머지 절반에 특정 인덱스를 갖습니다. 따라서 교체 여부와 관련하여 모든 인덱스가 한 번 고려되었습니다.
다음 라운드는 라운드 증가(또는 감소)로 시작하여 새로운 피벗 인덱스를 얻은 다음 위에서 설명한 프로세스를 통해 순환을 시작합니다.
이미지 설명
같은 라운드에서 한 거울에서 다른 거울로 이동하는 과정
기발한 장소성취하다교체 여부를 결정할 때 알고리즘은 후보 인덱스 또는 미러 이미지 중 더 높은 것을 현명하게 선택합니다. 즉, 축 아래에 있으면 i_1' 대신 i_1이 선택되고 축 위에 있으면 i_k 대신 i_k'가 선택됩니다. 즉, 목록의 인덱스를 유연하게 반복할 수 있습니다. 위에서 설명한 것처럼 0에서 m1로, p에서 m2로 두 개의 별도 루프로 분리하거나 동일한 루프에서 m1에서 m2로 둘을 결합할 수 있습니다. (그리고
성취하다
)의. 결과는 양쪽 모두 동일합니다: i_1을 고려하든 i_1'을 미러링하든 상관 없습니다. 대체 여부는 동일한 결과를 생성합니다.라운드Eth2에서는 위의 과정을 90번 수행하게 됩니다.원본 용지"선택적 암호 공격(CCA)에서 좋은 보안 마진을 보여주기 시작"하는 데 6lgN 라운드가 걸린다고 언급되어 있습니다. 여기서 N은 목록의 길이입니다. 비탈릭에서
주석 사양
에서 그는 "암호화 전문가들은 충분한 보안을 제공하기 위해 4log2N 라운드가 있다고 제안합니다"라고 말했습니다. 목록을 섞는 데 필요한 최대 횟수인 Eth2의 절대 최대 유효성 검사기 수는 약 222(420만)입니다. Vitalik이 제시한 추정 값은 88라운드이고 논문의 추정 값은 92라운드입니다(lg를 자연 로그라고 가정). 따라서 우리는 이제 대략적으로 올바른 범위에 있습니다. 특히 이렇게 많은 활성 유효성 검사기로 끝나지 않을 가능성이 높기 때문입니다.Issue F목록 길이를 기준으로 라운드를 조정하면 흥미로운 결과를 얻을 수 있지만 그렇게 하지 않을 것입니다. 불필요한 최적화일 수 있습니다.
흥미롭게도, Least Authority가 Beacon Chain 사양을 감사했을 때 처음에 블록 제안자를 선택하는 셔플링에 편향이 있음을 발견했습니다(참조:
). 그러나 그들은 실수로 10라운드만 있는 셔플 구성을 사용한 것으로 밝혀졌습니다. 셔플 구성을 90라운드(메인넷에서 사용하는 수)로 늘렸을 때 편견이 사라졌습니다.
(의사)무작위
셔플링 알고리즘에서는 각 라운드에서 피벗 포인트를 무작위로 선택하고 각 라운드에서 각 요소를 교체할지 여부를 무작위로 선택해야 합니다.
Eth2에서는 확실히 시드 값에서 임의성을 생성하므로 동일한 시드가 항상 동일한 셔플링 결과를 생성합니다.
피벗 표시기는 라운드와 연결된 시드의 8바이트 SHA2 해싱에 의해 생성됩니다.
피벗 인덱스는 라운드로 연결된 시드 값의 SHA2 해시 8바이트에서 생성되므로 일반적으로 라운드마다 변경됩니다.
요소 교체 여부를 결정하는 데 사용되는 결정적인 비트는 다음 요소에서 추출됩니다. 시드의 SHA256 해시, 라운드, 목록에 있는 요소의 인덱스.
능률
이 셔플링 알고리즘은 Fisher-Yates 알고리즘보다 훨씬 느립니다. Fisher-Yates 알고리즘에 N 셔플이 필요한 경우 알고리즘에는 평균 90N/4 셔플이 필요합니다. 또한 알고리즘에서 가장 비용이 많이 드는 부분인 pseudo-randomness 생성도 고려해야 합니다. Fisher-Yates는 Nlog2N 자리수에 가까운 임의성을 필요로 하고 90(log2N+N/2) 자리수가 필요합니다 Eth2에서 필요한 N 값의 범위에 따라 초과 자릿수가 상당히 많습니다(N이 100만일 때) , Eth2는 N)의 두 배 정도 필요합니다.
교환 여부 알고리즘을 선택하는 이유는 무엇입니까?
효율적이지 않다면 왜 이 구현을 선택하겠습니까?
단일 요소 섞기
따라서 인덱스 217의 요소가 어디에서 섞였는지 알고 싶다면 전체 목록을 섞지 않고 해당 인덱스에 대해서만 알고리즘을 실행할 수 있습니다. 또한 반대로 어떤 요소가 인덱스 217로 섞였는지 알고 싶다면 알고리즘을 역으로 실행하여 요소 217을 찾을 수 있습니다(역순이란 낮음에서 높음이 아니라 높음에서 낮음으로 라운드를 실행하는 것을 의미합니다).
Eth2 사양
단일 인덱스 셔플링에 알고리즘을 적용하는 방법에 대한 내용입니다. 사실, 전체 목록을 한 번에 섞는 것은 최적화일 뿐입니다! 원하는 경우 목록의 한 요소만 순서대로 섞을 수 있습니다. (역순) 셔플을 실행하여 인덱스 0에 도달한 요소를 찾고, 또 다른 셔플을 실행하여 인덱스 1에 도달한 요소를 찾는 식으로 진행합니다. 우리가 그렇게 하지 않는 이유는 단순히 스왑 여부가 한 번에 256비트 해시를 생성해야 하고 그렇게 255비트를 버리는 것은 낭비라는 결정 때문입니다. 1비트 해시 또는 오라클을 사용하는 경우 목록의 한 요소를 섞는 것은 전체 목록을 섞는 것만큼 효율적입니다.
진정한 "가벼운" 고객이 되십시오
역사여기여기여기Eth2의 셔플 알고리즘에 대한 원래 탐구에 대한 토론을 확인하십시오.
여기다른 각도에서 교환 여부 섞기 알고리즘을 보고 싶다면 Protolambda에서 게시한 알고리즘을 살펴볼 수 있습니다.。
마침내
마침내
고지 사항: ECN의 번역 작업은 중국 이더리움 커뮤니티에 고품질 정보 및 학습 리소스를 제공하는 것을 목표로 합니다.기사의 저작권은 원저자에게 있습니다.재인쇄는 원문의 출처와 ethereum.cn을 표시해야 합니다.장기적으로 재인쇄는 ethereumcn@gmail.com으로 연락주세요.
