본문으로 이동
Financial Context Wiki

암호학적 누산기

RSA 및 해시 기반 설계, 멤버십과 비멤버십 증인, 동적 업데이트, 블록체인 활용과 운영 위험을 다루는 검증 중심의 암호학적 누산기 안내서입니다.

업데이트

교육 목적으로만 제공되며 투자 조언이나 암호 구현 조언이 아닙니다. 누산기 증명은 하나의 커밋먼트에 대한 주장을 인증할 뿐, 기초 데이터나 합의 상태 또는 데이터 가용성 자체를 인증하지 않습니다.

바로 답하기

암호학적 누산기는 집합을 짧은 값으로 커밋하고, 어떤 원소가 커밋된 집합에 속하는지를 간결한 증인으로 검증할 수 있게 합니다. 일부 방식은 비멤버십도 증명합니다. 검증자에게는 누산기 값, 원소, 증인, 방식의 공개 매개변수가 필요하지만 집합의 다른 모든 원소는 필요하지 않습니다.

집합이 바뀐 뒤 다시 만들어야 하는 누산기는 정적, 원소를 추가하거나 삭제할 때 누산기와 증인을 효율적으로 갱신할 수 있으면 동적, 멤버십과 비멤버십 증명을 모두 지원하면 범용 누산기입니다. 이 명칭들은 서로 별개의 기능을 가리키므로 동적 방식이 자동으로 범용 방식이 되는 것은 아닙니다.

블록체인은 거래, 미사용 출력, 계정, 검증자 또는 폐기 기록에 커밋할 수 있습니다. 커밋먼트가 작으면 일부 참여자가 보관하는 상태를 줄일 수 있지만, 시스템은 여전히 기초 데이터와 최신 증인을 배포하고, 업데이트를 인증하며, 체인 재구성을 처리하고, 누가 집합을 변경할 수 있는지 정해야 합니다.

작동 원리

  1. 집합을 정확히 명시합니다. 원소의 정규 인코딩, 중복 처리, 필요한 경우의 정렬 규칙, 도메인 분리, 정확한 커밋먼트 버전을 정의합니다. 한 인코딩이나 상태 루트에 대한 증명은 다른 것에 관해 아무것도 보장하지 않습니다.

  2. 방식의 설정 절차를 실행합니다. 해시 기반 누산기는 공개 해시 매개변수만 사용할 수 있습니다. RSA 누산기는 일반적으로 RSA 모듈러스 N 에서 구성한 미지 차수 군을 사용하며, 권한 없는 당사자가 그 인수분해를 악용할 수 없어야 안전합니다. 다른 방식은 서로 다른 신뢰 가정 아래 페어링, 유군, 격자 또는 추가 공개 매개변수를 사용할 수 있습니다.

  3. 원소를 대수 구조에 매핑합니다. 단순화한 RSA 구성에서는 각 원소 x_i 를 서로 다른 소수 대표값 p_i 로 결정론적으로 매핑합니다. 밑을 g 라고 하면 누산기는 다음과 같습니다.

    A = g^(p_1 * p_2 * ... * p_n) mod N

  4. 멤버십 증인을 만듭니다. p_i 로 표현한 원소에 대해서는 지수에서 해당 인수를 제외합니다.

    w_i = g^(product of p_j for all j != i) mod N

  5. 정확한 누산기를 기준으로 검증합니다. 검증자는 입력이 정규 형식인지 확인하고 다음 식을 계산합니다.

    w_i^(p_i) mod N = A

    이 방식의 보안 가정 아래에서는 누산된 집합 밖의 원소로 이 등식을 성립시키는 것이 현실적으로 불가능해야 합니다. 그러나 이 등식은 원소 자체가 사실이거나 허가되었음을 입증하지 않습니다.

  6. 업데이트와 비멤버십을 별도로 처리합니다. 동적 방식은 추가와 삭제가 A 를 어떻게 바꾸고 영향받은 증인을 어떻게 갱신하는지 정의합니다. 범용 방식은 별도의 비멤버십 증인과 검증 알고리즘을 추가합니다. 구현은 오래된 증인과 다른 상태에 연결된 업데이트를 거부해야 합니다.

  7. 해시 기반 구조는 실제 비용으로 비교합니다. 넓은 의미에서 머클 트리도 해시 기반 누산기입니다. 루트는 짧지만 멤버십 증명에는 경로상의 형제 해시가 들어가므로 잎 개수에 따라 로그 규모로 커집니다. RSA 계열 방식은 개별 증인의 크기를 일정하게 유지할 수 있지만 증명 생성, 증인 유지, 설정, 계산에는 서로 다른 비용이 듭니다.

계산 예시

  • 머클 증명 크기. 잎이 1,048,576 = 2^20 개인 균형 이진 머클 트리는 하나의 포함 경로에 20 개의 형제 해시가 필요합니다. 해시가 32바이트라면 잎 데이터, 위치 비트, 직렬화 오버헤드를 제외하고 20 * 32 = 640 bytes 입니다. 루트는 32바이트로 유지됩니다.
  • 일정한 크기가 일정한 작업량을 뜻하지는 않습니다. 단순화한 RSA 구성에서는 집합이 커져도 A 와 하나의 w_i 는 각각 하나의 군 원소로 유지됩니다. 그래도 곱 지수, 소수 대표값 생성, 일괄 업데이트, 갱신된 증인 배포에는 상당한 계산이나 보조 데이터가 필요할 수 있습니다.
  • UTXO 누산기는 누가 무엇을 저장하는지를 바꿉니다. 압축 상태 노드는 미사용 출력의 누산기를 보관하고, 출력과 최신 멤버십 증명을 함께 받았을 때만 지출을 검증할 수 있습니다. 다른 참여자는 그런 증명을 만들기에 충분한 상태를 계속 보관해야 하며, 업데이트 시에는 사용한 출력을 제거하고 새로 생성된 출력을 추가해야 합니다.
  • 폐기에도 같은 경계가 적용됩니다. 자격 증명 보유자는 식별자가 유효 회원 누산기에 남아 있음을 증명하거나, 범용 설계를 사용해 폐기 집합에 없음을 증명할 수 있습니다. 증명은 발급자가 커밋한 집합을 인증할 뿐, 발급자가 공정하거나 올바른 폐기 정책을 적용했음을 입증하지 않습니다.

위험

  • 모호하거나 비정규적인 원소 인코딩을 사용해 논리적으로 같은 항목이 서로 다르게 매핑되도록 허용하는 것.
  • 원소를 소수 대표값으로 잘못 매핑하거나 방식에서 요구하는 충돌 제어를 적용하지 않는 것.
  • 설정 당사자나 공격자가 인수분해를 알고 있을 수 있는 RSA 모듈러스를 신뢰하는 것.
  • 기록, 참여자 가정, 매개변수 결합을 확인하지 않고 다자간 설정 행사를 안전하다고 보는 것.
  • 인증된 이전 규칙 없이 관리자가 공개 매개변수나 누산기 버전을 교체하도록 허용하는 것.
  • 오래되었거나 최종 확정되지 않았거나 공격자가 선택한 누산기 값을 기준으로 증인을 검증하는 것.
  • 잘못된 블록, 포크, 에포크 또는 집합 버전의 추가, 삭제, 증인 업데이트를 적용하는 것.
  • 멤버십 증인이 원소의 유효성, 소유권, 권한 또는 경제적 가치까지 증명한다고 가정하는 것.
  • 짧은 커밋먼트가 기초 집합을 가용하거나 복구 가능하게 만든다고 가정하는 것.
  • 최신 증인을 만드는 데 필요한 데이터나 서비스를 잃어 유효한 상태를 사용할 수 없게 만드는 것.
  • 애플리케이션이 부재 증명에 암묵적으로 의존하는데도 비멤버십 지원을 빼는 것.
  • 머클 경로, RSA 증인, 다항식 오프닝, 유효성 증명을 서로 바꿔 쓸 수 있는 객체로 혼동하는 것.
  • 삭제 비용, 증인 갱신 트래픽, 증명 생성 지연 또는 서비스 거부 입력을 무시하는 것.
  • 증명을 프로토콜, 체인, 계약, 상태 루트, 도메인, 직렬화 버전에 결합하지 않는 것.
  • 독립된 테스트 벡터 없이 감사받지 않은 단일 구현이나 자체 산술에 의존하는 것.
  • 고전 RSA, 페어링 또는 이산 로그 보안이 암호학적으로 유의미한 양자 컴퓨터에도 안전하다고 가정하는 것.

흔한 오해

  • 누산기에 집합의 압축 사본이 들어 있다. 누산기는 결합성 커밋먼트이지 되돌릴 수 있는 보관소가 아닙니다.
  • 모든 누산기가 부재를 증명한다. 비멤버십에는 그 기능을 위해 설계되고 검증된 방식이 필요합니다.
  • 일정한 크기의 증인은 전체 비용도 일정하게 만든다. 설정, 증명 생성, 업데이트, 저장, 증인 배포는 각각 별도의 비용으로 남습니다.
  • 무상태란 아무도 상태를 저장하지 않는다는 뜻이다. 일부 주체는 원소, 업데이트, 증인을 만들기에 충분한 데이터를 보관하거나 재구성해야 합니다.
  • 유효한 증명은 커밋된 항목이 사실임을 뜻한다. 정해진 가정 아래에서 그 항목을 인증된 하나의 커밋먼트에 연결할 뿐입니다.
  • 머클 트리와 RSA 누산기는 신뢰 및 성능 특성이 같다. 집합 커밋먼트라는 목적은 같지만 서로 다른 가정, 증명 크기, 업데이트 절차, 장애 형태를 사용합니다.

관련 주제

출처

탐색

위키 검색...