algorand 알고리즘 학습 노트

6995 단어
비밀번호 추첨
암호 추출 알고리즘 은 다음 block 을 검증 할 사람 을 결정 하 는 데 사 용 됩 니 다.
비밀번호 추첨 은 두 개의 단 서 를 누 르 면 실 행 됩 니 다.
  • '검증 자' 와 '지도자' 를 선출한다.
  • 은 '피 드' 인 자 를 만 들 고 계속 보완 하 는 것 이다.

  • 1. '검증 자' 와 '지도자' 를 선출한다.
  • 시스템 이 독립 된 파 라 메 터 를 만 들 고 계속 업데이트 합 니 다. '피 드' 라 고 부 르 며 Q ^ {r - 1} 이 라 고 기록 합 니 다.r 라운드 피 드 의 매개 변 수 는 256 비트 길이 의 문자열 입 니 다. 입 참 은 r - k 라운드 가 끝 난 후에 활성 화 된 사용자 의 공개 키 집합 입 니 다. PK ^ {r - k} 로 기록 합 니 다.k 는 역 추적 매개 변수 나 안전 매개 변수 라 고 불 린 다. 예 를 들 어 = 1 은 지난 라운드 가 끝 난 후의 사용자 집합 을 나타 낸다.위의 두 개의 매개 변 수 는 공공 지식 에 속한다.
  • 현재 '피 드' 를 기반 으로 랜 덤 알고리즘 을 구축 하고 발표 합 니 다. '검증 가능 한 랜 덤 함수 (verifiable random functions)' 라 고 합 니 다. 이 랜 덤 알고리즘 중 하 나 는 사용자 의 비밀 키 입 니 다. 이 비밀 키 는 사용자 본인 만 알 수 있 습 니 다.
  • 모든 사용자 가 자신의 비밀 키 를 사용 하여 '피 드' 에 서명 하고 함수 SIGI 로 표시 합 니 다. 이 를 매개 변수 로 시스템 에서 발표 한 랜 덤 알고리즘 을 실행 하고 함수 H () 로 표시 하 며 자신의 증빙 (credential) = H (SIGI (r, 1, Q ^ {r - 1}) (함수 SIGI 에 여러 개의 입력 매개 변수 가 있 을 때 이 매개 변 수 를 간단하게 연결 한 다음 에 전자 서명 을 하 겠 다 고 표시 합 니 다). 3.1. 증빙 은 무 작위 에 가 깝 고 0 과 1 로 구 성 된 길이 가 256 에 가 까 운 문자열 이 며 사용자 마다 증빙 이 거의 같 지 않 습 니 다. 3.2. 증빙 으로 구 축 된 2 진 소수 0. H (SIGI (r, 1, Q ^ {r - 1}) (즉, 증빙 문자열 을 소수점 까지 쓴 후) 는 0 과 1 사이 에 고 르 게 분포 되 어 있 습 니 다.
  • 증빙 가치 가 일정한 조건 을 만족 시 키 는 사용 자 는 바로 이번 라운드 의 '검증 자' (verifiers) 이다. 4.1. 조건 은 0 과 1 사이 의 한 수, 0. H (SIGI (r, 1, Q ^ {r - 1}) ≤ p 가 발생 할 확률 은 p 로 이 조건 을 만족 시 키 는 모든 사용 자 를 '검증 자' 라 고 한다. 4.2. 1 - 10 ^ {- 18} 의 확률 은 모든 '검증 자' 중에서 적어도 하 나 는 성실 하 다 는 것 을 보증한다.
  • '검증 자' 는 새로운 구역 블록 을 조립 하여 자신의 증빙 과 함께 대외 적 으로 보낸다. r 차 s 단계 (s > 1) 의 '검증 자' 의 생 성 절 차 는 상기 와 유사 하 다. 그 중에서 첫 번 째 단계 에서 증빙 치가 가장 작은 (사전 에 따라 정렬) '검증 자' 의 위 치 는 비교적 특수 하여 '지도자' 라 고 부른다.
  • 모든 '검증 자' 가 '리더' 를 바탕 으로 조립 한 새로운 블록 운영 비 잔 틴 협의 BA.
  • BA 의 모든 순환 에서 선 택 된 '검증 자' 는 다 릅 니 다. 이렇게 하면 검증 권한 이 일부 사용자 에 게 집중 되 는 것 을 효과적으로 방지 하고 '적대 자' 가 이러한 사용 자 를 부패 시 켜 블록 체인 을 공격 하지 않도록 합 니 다.
  • 상기 과정의 특징 은:
  • '검증 자' 는 비밀 상황 에서 자신 이 뽑 혔 다 는 것 을 알 게 되 었 으 나 그들 은 증 거 를 발표 해야만 자신의 '검증 자' 자격 을 증명 할 수 있다. '적대 자' 는 신분 공개 의 '검증 자' 를 순식간에 부패 시 킬 수 있 지만 이미 대외 적 으로 보 낸 소식 을 왜곡 하거나 철회 할 수 없다.
  • 모든 '검증 자' 가 자신의 증 거 를 발표 하고 비교 한 후에 야 누가 '지도자' 인지 확인 할 수 있다. 즉, '지도자' 는 공공 선거 로 볼 수 있다.
  • 랜 덤 알고리즘 의 성질 은 누가 '검증 자' 로 선 정 될 지 사전에 판단 하기 어렵 기 때문에 '검증 자' 의 선택 과정 이 조작 되 거나 예측 되 기 어렵다.
  • 비록 '적대 자' 가 사전에 거래 를 삽입 하여 현재 의 공공 장부 에 영향 을 줄 수 있 지만 '씨앗' 매개 변수 가 존재 하기 때문에 그 는 '검증 자' (특히 그 중의 '지도자') 에 영향 을 주 는 선택 을 통 해 알 고 랜 드 를 공격 할 수 없다.
  • 2. 피 드 업데이트
    Br 로 2 차 종료 후 비 잔 틴 협의 BA ★ 출력 블록 을 표시 합 니 다.
    "피 드" 의 업데이트 과정 은 Q ^ r = H (SIGlr (Q ^ {r - 1}, r) 입 니 다. B ^ r 가 빈 블록 이 아니라면 Q ^ r = H (Q ^ {r - 1}, r), B ^ r 가 빈 블록 이 라면.
    만약 알 고 랜 드 가 r 라운드 에서 "적대 자" 의 공격 을 받 았 다 면 B ^ r 는 비어 있 었 을 것 입 니 다.
    3. Algorand 의 비 잔 틴 협의 BA ★
    비 잔 틴 협정 BA ★ 는 2 단계 투표 체제 에 해당 한다.
  • 1 단계 에서 '검증 자' 는 자신 이 받 은 후보 블록 (통신 비용 을 통제 하기 위해 실제 후보 블록 인 해시 요약) 에 대해 등급 별 공감 대 프로 토 콜 (graded consensus) 을 운영 하고 '검증 자' 의 공감 대가 가장 많은 후보 블록 을 선정 했다.
  • 2 단계 에 서 는 '검증 자' 가 1 단계 에 선 정 된 후보 블록 에 대해 이원 비 잔 틴 프로 토 콜 (binary Byzantine Agreement) 을 운영 한다. 즉, 이 를 받 아들 이거 나 빈 블록 을 받 아들 이 는 것 이다. 각 단계 의 하위 단계 마다 알 고 랜 드 는 완전히 다른 '검증 자' 를 사용 할 수 있다 는 점 을 강조해 야 한다.
  • 다음은 서술 이 편리 하고 가설 이다.
  • 시스템 은 r 라운드 에 있 습 니 다.
  • 모든 단계 에서 n 명의 '검증 자' 를 선택한다. 그 중에서 악의 적 인 '검증 자' 는 t 를 초과 하지 않 고 n ≥ 3t + 1 (즉, 성실 '검증 자' 가 2 / 3 이상 을 차지한다). 또한 계수 함수 #si(v) 를 도입 하여 s 단계 에서 '검증 자' i 가 받 은 메시지 v 의 횟수 (같은 발송 자 에서 온 것 은 1 회 만 계산 할 수 있다) 를 나타 낸다.
  • 3.1 1 단계: 등급 별 공감 대 협의
  • 비밀번호 추첨 절 차 를 실행 하여 '지도자' lr 와 이 단계 의 '검증 자' 를 선정 합 니 다. vi 로 '검증 자' i 가 받 은 것 을 표시 하고 '지도자' lr 의 후보 블록 임 을 알 고 있 습 니 다.
  • vir 는 반드시 '지도자' lr 가 구축 한 후보 블록 과 같 지 않 습 니 다.
  • '검증 자' i 가 '지도자' 를 식별 하 는 방법 은 그 가 받 은 모든 '검증 자' 증빙 에서 사전 에 따라 가장 작은 자 를 찾 는 것 이다. 그러나 인터넷 통신 원인 으로 인해 '지도자' lr 가 보 낸 메 시 지 는 '검증 자' i 에 도착 하지 못 했 을 것 이다.
  • '지도자' lr 는 마침 '적대 자' 에 의 해 부패 되 어 서로 다른 '검증 자' 에 대해 서로 다른 후보 블록 을 보 냈 다.
  • '검증 자' i 자체 가 악의 적일 수 있다.
  • '검증 자' i 는 받 은 vi 를 다른 사용자 에 게 방송 할 것 이다. 정확 한 vi 대 표 는 그 가 다른 검증 자 에 게 이 vi 에 동의 한다 고 말 했다.
  • '검증 자' i 가 절차 2 에서 메 시 지 를 받 은 횟수 가 2t + 1 회 (즉 #2i(x)≥2t+1 를 초과 하면 그 는 메시지 x 를 다른 사용자 에 게 보 냈 다. '검증 자' i 는 다음 과 같은 규칙 에 따라 출력 (vi, gi):
  • 만약 에 x 가 존재 하면 \ # 3i (x) ≥ 2t + 1 이 존재 하면 vi = x, gi = 2; / 2 라운드 가 모두 투표 에 성공 하고 x 가 존재 하면 \ # 3i (x) ≥ t + 1 이 존재 하면 vi = x, gi = 1; / 1 라운드 만 투표 에 성공 하지 않 으 면 vi = Ø, gi = 1 이 고 그 중에서 Ø 는 빈 블록 을 대표 합 니 다.
    뜻 은:
  • 만약 에 성실 '검증 자' i 가 존재 한다 면 gi = 2 는 임 의 다른 '검증 자' j 에 대해 gj ≥ 1, vj = vi 가 있어 야 한다. 이때 모든 성실 '검증 자' 가 수출 한 후보 블록 은 같다. 물론 처음에 '검증 자' 가 받 은 후보 블록 이 모두 v 라면 마지막 '검증 자' 가 수출 한 것 도 모두 v 가 될 것 이다.
  • 모든 성실 '검증 자' i, gi ≤ 1 에 대해 그들 이 수출 한 후보 블록 이 반드시 같 지 않다.
  • 2 단계: 이원 비 잔 틴 협의
    등급 별 공감 대 프로 토 콜 기반 출력 {(vi, gi): i = 1, 2, K... n} 모든 성실 '검증 자' 에 대한 할당:
  • gi = 2 이면 bi = 0;
  • 기타 상황, bi = 1.
  • 이 bi 들 은 바로 이원 비 잔 틴 협의의 입력 이다.
  • 첫 번 째 '검증 자' i 는 bi 를 보 냅 니 다. 만약 에 \ # 1i (0) ≥ 2t + 1 이면 '검증 자' i 는 bi = 0, 수출 outi = 0 을 설정 하고 협의 집행 을 중단 합 니 다 (그 가 앞으로 bi = 0 을 계속 보 낼 것 이 라 고 생각 할 수도 있 습 니 다). 만약 에 \ # 1i (1) ≥ 2t + 1 이면 '검증 자' i 는 bi = 1 을 설정 합 니 다. 그렇지 않 으 면 '검증 자' i 는 bi = 0 을 설정 합 니 다.
  • 두 번 째 단계 인 '검증 자' i 는 bi 를 보 냅 니 다. 만약 에 \ # 2i (1) ≥ 2t + 1 이면 '검증 자' i 는 bi = 1 을 설정 하고 outi = 1 을 수출 하 며 협의 집행 을 중단 합 니 다 (그 가 앞으로 bi = 1 을 계속 보 낼 것 이 라 고 생각 할 수도 있 습 니 다). 만약 에 \ # 2i (0) ≥ 2t + 1 이면 '검증 자' i 는 bi = 0 을 설정 합 니 다. 그렇지 않 으 면 '검증 자' i 는 bi = 1 을 설정 합 니 다.
  • 세 번 째 단계 인 '검증 자' i 는 bi 와 SIGI (Qr - 1, rj) 를 보 냅 니 다. 만약 에 \ # 3i (0) ≥ 2t + 1 이면 '검증 자' i 는 bi = 0 을 설정 하고 \ # 3i (1) ≥ 2t + 1 이면 '검증 자' i 는 bi = 1 을 설정 합 니 다. 그렇지 않 으 면 Si 로 '검증 자' 에 게 메 시 지 를 보 낸 다른 '검증 자' 의 집합 을 표시 합 니 다.
  • 결론.
  • 매번 n 명의 검증 자 를 무 작위 로 선출한다. 확률 에 따라 누가 검증 자인 지 결정 하기 때문에 n 의 값 은 모든 검증 자가 그의 증명 서 를 방송 한 후에 만 노드 가 n 의 값 이 얼마 인지 알 수 있 고 ≤ 진정한 검증 자의 수량 은 네트워크 등 문제 가 존재 하기 때문이다. 그러면 이런 상호작용 의 과정 은 동기 적 인 상호작용 의 과정 으로 블록 시간 에 영향 을 줄 것 이다.
  • 모든 라운드 의 공 통 된 상호작용 횟수 가 너무 많 고 매번 의 상호작용 은 수 동적 인 동기 화 지연 을 의미 하 며 성능 에 적지 않 은 영향 을 미친다.
  • algorand 의 성능 은 비트 코 인의 125 배 에 달 합 니 다. 논문 에서 제시 한 데이터 에 따 르 면 시간 당 공감 할 수 있 는 거래 인지 750 M 바이트 인지 시간 당 계산 해 보 세 요 (매 거래 길이 100 바이트 로 계산): 75010241024 / 60 / 60 / 100 = 214.5 TPS 는 실제 환경의 운행 을 고려 하면 1000 TPS 정도 에 이 를 것 으로 추정 합 니 다.
  • 참고 문헌:https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf https://www.leiphone.com/news/201802/D835Yu95sY7ihrAp.html

    좋은 웹페이지 즐겨찾기