AuditableRandom 1.2609.1

AuditableRandom

AuditableRandom — ChaCha20 기반 감사 가능(재현 가능) 난수 생성기와 그 벤치마크.

각 난수 추출은 고유한 tick을 함께 산출하며, (seed, userId, tick) 세 값만 있으면 키스트림 블록을 바이트 단위로 동일하게 재현할 수 있다. 추첨·배정처럼 사후에 "정말 공정했는지"를 검증해야 하는 곳에서, 결과를 감사 로그로 남겼다가 그대로 다시 계산해 대조할 수 있다.

특징

• 재현성: 비밀 seed + userId + 발급 tick → 동일 keystream. 감사 로그로 추첨 결과를 사후 검증. 셔플을 포함해 tick을 발급하는 모든 추출 경로가 재현 가능하며, 각 경로에 out tick 오버로드가 있다. 외부 감사자가 독립 구현으로 재현하기 위한 전체 명세는 docs/AUDIT.md 참조.
• 암호학적 품질: RFC 8439 ChaCha20(20 라운드) keystream. 표준 적합성은 §2.3.2·Appendix A.1 테스트 벡터와, 스펙에서 직접 옮긴 스칼라 참조 구현과의 차등 비교(counter 경계 + 랜덤 입력)로 검증. 분포 균등성은 카이제곱 검정으로 검증.
• 편향 없는 범위 추출: Lemire multiply-shift 거부 표본추출로 modulo bias 제거 — 모든 결과값이 동일 확률. 일반 경로는 곱셈 1회뿐이라 나눗셈 기반 방식보다 빠르다.
• SIMD 최적화: 블록 함수는 Vector128<uint> 기반이며, 회전 16/8비트는 바이트 셔플 1연산으로 처리.
• 스레드 안전 + 확장성: 정적 메서드는 동시 호출에 안전하다. tick 발급은 원자적이면서, 전역 카운터 하나가 아니라 64개 슬롯 카운터로 분할되어 있어 슬롯 수까지는 거의 선형으로 확장된다. 동시 실행 스레드가 64개를 넘으면 일부가 슬롯을 공유해 그 카운터에서 직렬화된다.
• tick ≈ 대략적 타임스탬프: tick은 시각 기준값(프로세스 시작 시각(UTC) + 경과분, DateTime.Ticks 100ns 단위)과 발급마다 무조건 오르는 슬롯 카운터 중 큰 쪽이다. 그래서 추출 시각을 대략 역산할 수 있지만 정밀한 시각원은 아니다 — 하위 6비트가 슬롯 번호라 실제보다 최대 6.4µs 이르고, 추출이 몰리면 슬롯 카운터가 시각 기준값을 앞질러 실제보다 상한 없이 늦어진다.
• tick 순서: tick은 프로세스 전역에서 유일하지만, 대소가 발급 순서와 일치하는 것은 같은 스레드 안에서만이다. 스레드가 다르면 tick만으로 어느 추출이 먼저였는지 판단할 수 없다. 재현과 resumeAfterTick은 tick 값 자체와 최댓값만 쓰므로 영향이 없다.

빠른 시작

using System.Security.Cryptography;
using Witness;

// 1) 프로세스 시작 시 단 한 번, 32바이트 seed를 등록한다.
byte[] seed = RandomNumberGenerator.GetBytes(32);
AuditableRandom.Initialize(seed);

// 2) 난수 추출 — tick을 함께 받아 (userId, tick)을 감사 로그에 저장한다.
Int32 dice = AuditableRandom.NextInt32("user-123", 1, 7, out Int64 tick); // [1, 7)
// → dice와 (userId="user-123", tick)을 저장.

// 3) 사후 재현(감사) — 동일 (userId, tick)으로 keystream 블록을 다시 만들어 검증한다.
byte[] block = AuditableRandom.GetBlockChaCha20("user-123", tick);
// 저장 당시와 동일한 추출 로직을 block에 적용하면 dice가 그대로 나온다.

// 과거 seed로 재현해야 하면 명시적인 seed 오버로드를 쓴다(Initialize와 무관하게 동작).
byte[] past = AuditableRandom.GetBlockChaCha20(oldSeed, "user-123", tick);

Initialize는 프로세스 수명 동안 한 번만 성공한다(이중 호출 시 예외). seed는 정확히 32바이트여야 한다.

동시에 실행되는 인스턴스마다 seed가 달라야 한다. tick은 프로세스 안에서만 유일하므로, 같은 seed를 쓰는 서버 여러 대는 같은 tick을 발급해 결과가 그대로 겹칠 수 있다. 감사 로그에는 어느 seed(인스턴스)로 추출했는지도 함께 기록한다. (아래 "재시작 간 nonce 유일성 보장" 참조.)

API 요약

collection은 IList<T> / Span<T> / T[]를 받는다(제자리 셔플).

정수·부동소수 메서드와 Shuffle은 모두 다음 오버로드를 공유한다.

• userId 생략(빈 사용자) / userId 지정 — userId는 결과를 사용자에 바인딩한다. xxHash3(userId) 64비트를 쪼개 상위 32비트는 nonce 뒤쪽 4바이트, 하위 32비트는 ChaCha20 초기 counter로 쓴다 (정확한 레이아웃은 docs/AUDIT.md §2.2). userId는 UTF-16 코드 단위 그대로 해싱되므로 감사 로그에 정규화 없이 원본 그대로 저장해야 한다. 짝이 맞지 않는 서로게이트가 든 userId는 저장 중 치환되어 재현이 깨지므로 생성 경로에서 ArgumentException으로 거부한다(재현 경로는 받아들인다).
• out Int64 tick 생략 / 지정 — 감사 로그 저장용 tick을 받는다.

AuditableRandom.NextDouble();                          // 빈 userId, tick 버림
AuditableRandom.NextDouble(out Int64 tick);            // 빈 userId, tick 받음
AuditableRandom.NextInt32(1, 7);                       // [1,7), 빈 userId
AuditableRandom.NextInt32("user-1", 1, 7, out Int64 tick); // [1,7), userId + tick
AuditableRandom.NextUInt64("user-1", 1000UL);          // [0,1000)
AuditableRandom.Hits("user-1", 3000, 10000);           // 30.00% 명중 여부(bool)

// 셔플: tick 하나를 소비하며, 그 tick으로 순열을 그대로 재현한다.
List<Int32> items = Enumerable.Range(0, 100).ToList();
AuditableRandom.Shuffle("user-1", items, out Int64 shuffleTick);   // 생성 — shuffleTick을 저장
List<Int32> audit = Enumerable.Range(0, 100).ToList();             // 생성 당시와 같은 시작 순서
AuditableRandom.Shuffle("user-1", shuffleTick, audit);             // 재현 — items와 동일한 순열

System.Random에서 이식할 때

인자 없는 전 범위 오버로드는 System.Random과 반환 범위가 다르다.

NextInt64()는 이름과 시그니처가 완전히 같아 컴파일 오류 없이 동작만 달라진다. Next()는 이름이 달라 컴파일러가 한 번 걸러주지만, Next → NextInt32로 기계적으로 치환하면 마찬가지로 조용히 음수가 섞인다.

음이 아닌 값이 필요하면 상한을 명시한다.

random.Next();                              // [0, Int32.MaxValue)
AuditableRandom.NextInt32(Int32.MaxValue);  // 동일한 범위
AuditableRandom.NextInt32();                // ✗ [Int32.MinValue, Int32.MaxValue] — 음수 포함

random.NextInt64();                         // [0, Int64.MaxValue)
AuditableRandom.NextInt64(Int64.MaxValue);  // 동일한 범위
AuditableRandom.NextInt64();                // ✗ 이름이 같지만 음수를 반환한다

NextDouble / NextSingle / Shuffle 및 상한·범위를 명시하는 오버로드는 System.Random과 시맨틱이 같다.

재시작 간 nonce 유일성 보장

(seed, nonce) 묶음을 재사용하지 않아야 한다. nonce에는 tick이 들어간다. system clock은 뒤로 갈 수 있어, 같은 seed를 재사용하면서 재시작 하는 사이에 tick이 겹칠 위험이 있다. 직전 실행에서 발급한 최대 tick을 내구성 있게 저장했다가 다음 시작 시 넘기면, 이후 모든 tick이 그 값을 초과하도록 보장된다.

// 직전 실행에서 저장한 최대 tick을 넘겨 재시작 간 nonce 겹침을 막는다.
AuditableRandom.Initialize(seed, resumeAfterTick: maxIssuedTick);

효과를 보려면 호출자(앱) 가 발급 tick의 최댓값을 영속화했다가 재시작 시 넘겨줘야 한다. 라이브러리는 메커니즘만 제공한다. 0이면 시간 기준만 사용한다.

멀티스레드로 추출한다면 가장 마지막에 관측한 tick이 아니라 최댓값을 기록해야 한다. tick의 대소는 같은 스레드 안에서만 발급 순서와 일치하므로, 나중에 발급된 tick이 더 작을 수 있다.

최댓값에는 tick을 발급하는 모든 경로를 포함해야 한다 — Next* / GetBlockChaCha20 / Fill뿐 아니라 Shuffle도 호출마다 tick을 하나 소비한다. 이들 모두 out tick 오버로드가 있으므로, 그 오버로드만 쓰면 발급된 tick을 빠짐없이 관측할 수 있다.

resumeAfterTick은 음수이거나 DateTime.MaxValue.Ticks를 넘으면 ArgumentOutOfRangeException으로 거부된다. 정상 발급 tick은 프로세스 시작 시각에서 출발해 발급 1회당 64씩만 오르므로 그 상한에 닿지 않는다 — 초과 값은 손상된 기록으로 본다(검사가 없으면 슬롯 카운터가 오버플로해 보장이 조용히 무효화된다).

resumeAfterTick은 같은 seed의 순차 재시작만 보호한다. 같은 seed로 동시에 도는 다른 프로세스와의 tick 겹침은 막지 못하므로, 동시에 실행되는 인스턴스에는 서로 다른 seed를 등록해야 한다.

주의

• 리틀엔디안 전용: 성능을 위해 ① 키·논스 적재, ② 블록 출력 기록, ③ userId의 UTF-16 바이트 해싱을 모두 LE 메모리 표현에 의존해 처리한다(.NET 실행 환경은 사실상 전부 LE). 빅엔디안에서는 조용히 다른 keystream이 나와 재현이 깨지므로, 타입 초기화 시점에 PlatformNotSupportedException을 던져 명시적으로 실패한다.
• Shuffle 재현은 시작 순서에 의존한다: 셔플은 (seed, userId, tick, 원소 수)로 순열을 재현하지만 (Shuffle(userId, tick, collection) 또는 과거 seed용 Shuffle(seed, userId, tick, collection)), Fisher-Yates는 시작 배열에 순열을 적용하는 것이라 원소를 생성 당시와 같은 순서로 넣어야 한다. 재현 규격은 docs/AUDIT.md §4 참조. 원소가 1개 이하면 스왑이 없어 tick을 발급하지 않고 0을 돌려준다(발급된 tick은 항상 양수다).

보안

ChaCha20을 직접 구현한 라이브러리로 독립적인 외부 암호 감사를 받지 않았다. 비밀 seed가 유일한 보안 경계이며, seed가 노출되면 (userId, tick)만으로 모든 출력을 재현할 수 있다. 보안 모델·전제와 취약점 신고 절차는 SECURITY.md 참조.

통계 시뮬레이션: 1% 당첨과 연속 미당첨(TOP 3)

테스트 NoWinStreakTests는 사용자 10명에게 당첨 확률 1%(Hits(userId, 1, 100))인 추첨을 사용자당 N회 반복하며, 각 사용자의 연속 미당첨(streak) 길이 상위 3개(TOP 3)를 수집한다. 명시적인 seed 경로를 쓰므로 아래 결과는 결정론적으로 재현된다.

사용자: 10명  추첨: 100회  당첨 확률: 1% (Hits(userId, 1, 100))
----------------------------------------------------------------
user-00  당첨   1회  TOP3 연속 미당첨: [ 97,   2,   0]
user-01  당첨   6회  TOP3 연속 미당첨: [ 36,  24,  18]
user-02  당첨   1회  TOP3 연속 미당첨: [ 59,  40,   0]
user-03  당첨   1회  TOP3 연속 미당첨: [ 51,  48,   0]
user-04  당첨   0회  TOP3 연속 미당첨: [100,   0,   0]
user-05  당첨   2회  TOP3 연속 미당첨: [ 52,  39,   7]
user-06  당첨   1회  TOP3 연속 미당첨: [ 97,   2,   0]
user-07  당첨   1회  TOP3 연속 미당첨: [ 87,  12,   0]
user-08  당첨   1회  TOP3 연속 미당첨: [ 59,  40,   0]
user-09  당첨   2회  TOP3 연속 미당첨: [ 48,  37,  13]

사용자: 10명  추첨: 200회  당첨 확률: 1% (Hits(userId, 1, 100))
----------------------------------------------------------------
user-00  당첨   2회  TOP3 연속 미당첨: [ 97,  85,  16]
user-01  당첨   6회  TOP3 연속 미당첨: [136,  24,  18]
user-02  당첨   1회  TOP3 연속 미당첨: [159,  40,   0]
user-03  당첨   3회  TOP3 연속 미당첨: [139,  48,   8]
user-04  당첨   0회  TOP3 연속 미당첨: [200,   0,   0]
user-05  당첨   4회  TOP3 연속 미당첨: [ 93,  52,  44]
user-06  당첨   4회  TOP3 연속 미당첨: [145,  21,  18]
user-07  당첨   2회  TOP3 연속 미당첨: [109,  87,   2]
user-08  당첨   2회  TOP3 연속 미당첨: [139,  40,  19]
user-09  당첨   4회  TOP3 연속 미당첨: [ 84,  38,  37]

사용자: 10명  추첨: 300회  당첨 확률: 1% (Hits(userId, 1, 100))
----------------------------------------------------------------
user-00  당첨   3회  TOP3 연속 미당첨: [ 97,  92,  85]
user-01  당첨   8회  TOP3 연속 미당첨: [191,  24,  24]
user-02  당첨   2회  TOP3 연속 미당첨: [189,  69,  40]
user-03  당첨   4회  TOP3 연속 미당첨: [139,  80,  48]
user-04  당첨   1회  TOP3 연속 미당첨: [284,  15,   0]
user-05  당첨   5회  TOP3 연속 미당첨: [ 93,  68,  52]
user-06  당첨   6회  TOP3 연속 미당첨: [145,  56,  42]
user-07  당첨   3회  TOP3 연속 미당첨: [109,  87,  72]
user-08  당첨   2회  TOP3 연속 미당첨: [139, 119,  40]
user-09  당첨   4회  TOP3 연속 미당첨: [138,  84,  37]

사용자: 10명  추첨: 400회  당첨 확률: 1% (Hits(userId, 1, 100))
----------------------------------------------------------------
user-00  당첨   4회  TOP3 연속 미당첨: [159,  97,  85]
user-01  당첨   9회  TOP3 연속 미당첨: [191,  98,  24]
user-02  당첨   3회  TOP3 연속 미당첨: [189, 110,  58]
user-03  당첨   6회  TOP3 연속 미당첨: [139,  90,  83]
user-04  당첨   3회  TOP3 연속 미당첨: [284,  69,  39]
user-05  당첨   5회  TOP3 연속 미당첨: [131,  93,  68]
user-06  당첨  10회  TOP3 연속 미당첨: [145,  59,  51]
user-07  당첨   4회  TOP3 연속 미당첨: [121, 109,  87]
user-08  당첨   4회  TOP3 연속 미당첨: [143, 139,  65]
user-09  당첨   4회  TOP3 연속 미당첨: [238,  84,  37]

사용자: 10명  추첨: 100,000회  당첨 확률: 1% (Hits(userId, 1, 100))
----------------------------------------------------------------
user-00  당첨 1048회  TOP3 연속 미당첨: [697, 642, 633]
user-01  당첨 1003회  TOP3 연속 미당첨: [991, 972, 676]
user-02  당첨  993회  TOP3 연속 미당첨: [906, 570, 564]
user-03  당첨  988회  TOP3 연속 미당첨: [718, 710, 707]
user-04  당첨 1027회  TOP3 연속 미당첨: [666, 633, 613]
user-05  당첨  989회  TOP3 연속 미당첨: [661, 644, 624]
user-06  당첨 1011회  TOP3 연속 미당첨: [819, 625, 562]
user-07  당첨 1021회  TOP3 연속 미당첨: [606, 548, 523]
user-08  당첨 1049회  TOP3 연속 미당첨: [517, 498, 466]
user-09  당첨  957회  TOP3 연속 미당첨: [680, 611, 603]

왜 "100번 추첨하면 1번 당첨"이 안 되나

"당첨 확률 1% = 100번에 1번 당첨"이라는 직관은 틀린 전제다. 1%는 한 번의 추첨이 가지는 확률일 뿐이고, 추첨은 서로 독립이라 과거 미당첨이 다음 당첨 확률을 높이지 않는다(도박사의 오류). 따라서 N회 동안 한 번도 당첨되지 않을 확률이 0이 아니다.

매 추첨의 미당첨 확률은 1 - 0.01 = 0.99이고, N회 모두 미당첨일 확률은 독립이므로 곱으로:

P(N회 동안 0회 당첨) = 0.99^N

• 기댓값 ≠ 보장: N=100일 때 기대 당첨 수는 1.0이지만, 이는 평균일 뿐이다. 실제로는 P(최소 1회 당첨) = 1 - 0.99¹⁰⁰ ≈ 63.4%, 즉 약 36.6%는 100번을 뽑고도 0회 당첨이다. 위 표의 "0회 기대 인원"이 N이 커질수록 줄어드는 것이, 실측에서 0회 당첨 사용자(user-04)가 100·200회에 나타나고 300회부터 사라지는 흐름과 일치한다. 반대로 user-04의 최장 연속 미당첨 284회처럼, 한 번 당첨된 뒤에도 긴 미당첨 구간은 얼마든지 나온다.
• 표본이 커지면 1%로 수렴: 같은 테스트의 100,000회 실행에서는 사용자별 당첨이 약 1,000회 (합계 1.01%)로, 확률 자체는 정확히 1%다. 소표본에서 0회가 보이는 건 RNG의 불공정이 아니라 이항분포의 자연스러운 분산이다.

모든 사용자가 N회 안에 반드시 1회 이상 당첨되게 하려면 이는 난수로 만들 수 없고, 연속 미당첨 횟수를 세어 임계값에서 강제 당첨시키는 천장(pity) 시스템을 별도 설계로 얹어야 한다.

빌드 / 배포

배포용 빌드는 Release 구성으로 한다. Release 빌드는 GeneratePackageOnBuild 설정에 따라 .nupkg와 심볼 패키지 .snupkg를 AuditableRandom/bin/Release/에 자동 생성한다(별도 dotnet pack 불필요).

dotnet build -c Release

게시 전 변경사항을 커밋·푸시해야 SourceLink가 가리키는 커밋과 패키지에 담긴 소스가 일치한다. 버전은 version.json의 major와 빌드 시점(연·월·월간 커밋수)으로 자동 결정된다.

벤치마크

dotnet run --project Benchmarks -c Release

System.Random·RandomNumberGenerator와 대비한 주요 API의 처리량을 측정한다.

부가 벤치마크는 --filter로 고른다.

ShuffleIntrinsicBenchmarks는 ChaCha20 블록 함수의 셔플을 Vector128.Shuffle로 할 때와 ShuffleNative로 할 때를 비교한다(x86-64에서는 JIT이 이미 단일 명령으로 접어 차이가 없음을 확인했다. ARM64는 코드 생성이 달라 재측정할 가치가 있다).

dotnet run --project Benchmarks -c Release -- --filter *ShuffleIntrinsic*

TickContentionBenchmarks는 tick 발급의 멀티스레드 경합을 1~32스레드에서 측정한다. 총 연산 수를 스레드 수와 무관하게 고정해 리포트의 Mean이 곧 연산 1회당 ns가 되므로, 스레드가 늘 때 이 값이 줄어드는지(확장) 커지는지(경합)를 바로 읽을 수 있다. 현재 구현(슬롯 분할)과 함께 그 이전 단계였던 전역 CAS 카운터 변형들을 기준선으로 남겨 두어, 각 단계가 얼마를 벌었는지 한 표에서 비교된다.

dotnet run --project Benchmarks -c Release -- --filter *TickContention*