AuditableRandom 1.2608.2

AuditableRandom

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

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

특징

• 재현성: 비밀 seed + userId + 발급 tick → 동일 keystream. 감사 로그로 추첨 결과를 사후 검증. 외부 감사자가 독립 구현으로 재현하기 위한 전체 명세는 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바이트여야 한다.

API 요약

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

• userId 생략(빈 사용자) / userId 지정 — userId는 결과를 사용자에 바인딩한다. xxHash3(userId) 64비트를 쪼개 상위 32비트는 nonce 뒤쪽 4바이트, 하위 32비트는 ChaCha20 초기 counter로 쓴다 (정확한 레이아웃은 docs/AUDIT.md §2.2).
• 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)

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이 더 작을 수 있다.

주의

• 리틀엔디안 전용: 성능을 위해 ① 키·논스 적재, ② 블록 출력 기록, ③ userId의 UTF-16 바이트 해싱을 모두 LE 메모리 표현에 의존해 처리한다(.NET 실행 환경은 사실상 전부 LE). 빅엔디안에서는 조용히 다른 keystream이 나와 재현이 깨지므로, 타입 초기화 시점에 PlatformNotSupportedException을 던져 명시적으로 실패한다.
• Shuffle은 감사 대상이 아니다: 내부적으로 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*