/**

 * 生日攻击概率计算器

 * 计算 k 次独立采样在 N = 2^n 空间中的碰撞概率

 */

function birthdayCollisionProb(n: number, k: number): number {

  const N = 2 ** n;

  // 精确公式: P(collision) = 1 - e^(-k*(k-1)/(2*N))

  const exp = -(k * (k - 1)) / (2 * N);

  return 1 - Math.exp(exp);

}



// 演示：SHA-256 输出空间 n=256，不同 k 值

console.log("=== 生日攻击概率分析 ===");

console.log(`n=256, k=2^100: P ≈ ${birthdayCollisionProb(256, 2**100).toExponential(2)}`);

console.log(`n=256, k=2^128: P ≈ ${birthdayCollisionProb(256, 2**128).toExponential(2)}`);

console.log(`n=256, k=2^140: P ≈ ${birthdayCollisionProb(256, 2**140).toExponential(2)}`);



// 类比：经典的 365 人生日问题

function birthdayClassic(people: number): number {

  return birthdayCollisionProb(Math.log2(365), people);

}

console.log("\n=== 经典生日悖论 ===");

[10, 23, 40, 50, 100].forEach(k => {

  console.log(`${k} 人中至少一对同生日的概率:${birthdayClassic(k).toFixed(4)}`);

});

=== 生日攻击概率分析 ===

n=256, k=2^100: P ≈ 4.17e-48

n=256, k=2^128: P ≈ 0.39

n=256, k=2^140: P ≈ 1.00e+00



=== 经典生日悖论 ===

10 人中至少一对同生日的概率: 0.1169

23 人中至少一对同生日的概率: 0.5073

40 人中至少一对同生日的概率: 0.8912

/**

 * 密码学承诺机制（Commitment Scheme）

 * 演示绑定性与隐藏性

 */

class CommitmentScheme {

  private salt: Uint8Array | null = null;

  private committedValue: string | null = null;

  private commitmentHash: string | null = null;



  // 承诺阶段：生成随机盐 + 计算 H(salt || value)

  commit(value: string, entropy: Uint8Array): string {

    // 真实的随机盐应由 CSPRNG 生成；这里用参数传入模拟

    this.salt = entropy;

    this.committedValue = value;

    this.commitmentHash = this._hash(this.salt, value);

    return this.commitmentHash;

  }



  // 揭晓阶段：公开 (salt, value)，验证方重算哈希比对

  reveal(): { salt: string; value: string; commitment: string } | null {

    if (!this.salt || !this.committedValue || !this.commitmentHash) return null;

    return {

      salt: this._bytesToHex(this.salt),

      value: this.committedValue,

      commitment: this.commitmentHash,

    };

  }



  // 验证承诺

  verify(saltHex: string, value: string, commitment: string): boolean {

    const salt = this._hexToBytes(saltHex);

    const recomputed = this._hash(salt, value);

    return recomputed === commitment;

  }



  // 简化的 SHA-256-like 32-byte hash (演示用，非安全实现)

  // 真实环境使用 2.2 节的完整实现或 crypto.subtle

  private _hash(salt: Uint8Array, value: string): string {

    const data = new TextEncoder().encode(this._bytesToHex(salt) + ":" + value);

    // 演示：用多个 round 的简单哈希模拟安全属性

    let h = 0x6a09e667;

    const k = [0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5];

    for (let i = 0; i < data.length; i++) {

      h = (h ^ data[i]) + k[i % 4] | 0;

      h = ((h << 7) | (h >>> 25)) + ((h << 15) | (h >>> 17));

    }

    // 扩展到 32 字节模拟

    let result = '';

    for (let i = 0; i < 8; i++) {

      const v = (h + i * 0x9e3779b9 | 0) >>> 0;

      result += v.toString(16).padStart(8, '0');

    }

    return result;

  }



  private _bytesToHex(bytes: Uint8Array): string {

    return Array.from(bytes).map(b => b.toString(16).padStart(2, '0')).join('');

  }

  private _hexToBytes(hex: string): Uint8Array {

    const bytes = new Uint8Array(hex.length / 2);

    for (let i = 0; i < bytes.length; i++) {

      bytes[i] = parseInt(hex.slice(i * 2, i * 2 + 2), 16);

    }

    return bytes;

  }

}



// --- 演示：Alice 承诺一个预测 ---

const scheme = new CommitmentScheme();

const prediction = "Bitcoin_price_over_100k_2025";

const salt = new Uint8Array([0x8a, 0x3f, 0x12, 0x9d, 0x54, 0xe7, 0x88, 0x01]); // 应随机生成



const commitment = scheme.commit(prediction, salt);

console.log(`承诺值: ${commitment}`);

// 验证方无法从 commitment 反推 prediction（隐藏性）



// 揭晓时

const reveal = scheme.reveal();

console.log(`\n揭晓: salt=${reveal!.salt}, value=${reveal!.value}`);



// 验证

const isValid = scheme.verify(reveal!.salt, reveal!.value, commitment);

console.log(`验证结果: ${isValid}`);



// 尝试作弊：改变值

const isCheating = scheme.verify(reveal!.salt, "Different_value", commitment);

console.log(`作弊检测: ${isCheating}`);

消息 M

  └─ 填充 → 512-bit 对齐的消息 M' = M₁ || M₂ || ... || Mₙ

      ├─ M₁ ──→ [H₀=IV] + 压缩函数 ──→ H₁

      ├─ M₂ ──→ [H₁] + 压缩函数 ──→ H₂

      └─ Mₙ ──→ [Hₙ₋₁] + 压缩函数 ──→ Hₙ = 最终哈希

/**

 * SHA-256 消息填充

 * 返回填充后的字节数组，其长度是 64 的整数倍（512-bit = 64 字节）

 */

function sha256Pad(message: Uint8Array): Uint8Array {

  const bitLen = message.length * 8;

  const msgLen = message.length;

  // 计算需要多少填充字节：1 (0x80) + zeros + 8 (length)

  const padLen = ((64 - ((msgLen + 9) % 64)) % 64);

  const totalLen = msgLen + 1 + padLen + 8;

  const padded = new Uint8Array(totalLen);

  

  // 1. 复制原始消息

  padded.set(message, 0);

  // 2. 追加 0x80

  padded[msgLen] = 0x80;

  // 3. zeros 已在初始化时默认填充

  // 4. 追加 64-bit 大端消息长度

  const dv = new DataView(padded.buffer);

  dv.setUint32(totalLen - 4, bitLen, false); // 大端序

  dv.setUint32(totalLen - 8, (bitLen / 0x100000000) >>> 0, false); // 高 32 位

  

  return padded;

}

// SHA-256 的 64 个轮常数 K[0..63]

const K = [

  0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,

  0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,

  0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,

  0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,

  0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,

  0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,

  0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,

  0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2

];



// 8 个初始哈希值（前 8 个质数的平方根的小数部分前 32 位）

const H0 = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19];



/**

 * SHA-256 完整实现（教学版）

 * 不依赖外部库，纯 TypeScript 位运算实现

 */

function sha256(message: string): string {

  const msgBytes = new TextEncoder().encode(message);

  const padded = sha256Pad(msgBytes);

  const dv = new DataView(padded.buffer);

  

  // 初始化工作寄存器

  let [a, b, c, d, e, f, g, h] = [...H0];

  

  // 消息分块处理（每块 64 字节 = 512 位）

  for (let block = 0; block < padded.length / 64; block++) {

    // --- 消息调度：将 64 字节消息块扩展为 64 个 32 位字 ---

    const W = new Uint32Array(64);

    for (let t = 0; t < 16; t++) {

      W[t] = dv.getUint32(block * 64 + t * 4, false); // 大端读取

    }

    for (let t = 16; t < 64; t++) {

      const s0 = rotr(W[t - 15], 7) ^ rotr(W[t - 15], 18) ^ (W[t - 15] >>> 3);

      const s1 = rotr(W[t - 2], 17) ^ rotr(W[t - 2], 19) ^ (W[t - 2] >>> 10);

      W[t] = (W[t - 16] + s0 + W[t - 7] + s1) & 0xFFFFFFFF;

    }

    

    // --- 64 轮压缩 ---

    let [A, B, C, D, E, F, G, H] = [a, b, c, d, e, f, g, h];

    for (let t = 0; t < 64; t++) {

      const S1 = rotr(E, 6) ^ rotr(E, 11) ^ rotr(E, 25);

      const ch = (E & F) ^ ((~E) & G);

      const temp1 = (H + S1 + ch + K[t] + W[t]) & 0xFFFFFFFF;

      const S0 = rotr(A, 2) ^ rotr(A, 13) ^ rotr(A, 22);

      const maj = (A & B) ^ (A & C) ^ (B & C);

      const temp2 = (S0 + maj) & 0xFFFFFFFF;

      

      H = G;

      G = F;

      F = E;

      E = (D + temp1) & 0xFFFFFFFF;

      D = C;

      C = B;

      B = A;

      A = (temp1 + temp2) & 0xFFFFFFFF;

    }

    

    // --- 累加到状态寄存器 ---

    a = (a + A) & 0xFFFFFFFF;

    b = (b + B) & 0xFFFFFFFF;

    c = (c + C) & 0xFFFFFFFF;

    d = (d + D) & 0xFFFFFFFF;

    e = (e + E) & 0xFFFFFFFF;

    f = (f + F) & 0xFFFFFFFF;

    g = (g + G) & 0xFFFFFFFF;

    h = (h + H) & 0xFFFFFFFF;

  }

  

  // 输出 256-bit 摘要（8 个 32-bit 字拼接）

  const toHex8 = (x: number) => (x >>> 0).toString(16).padStart(8, '0');

  return toHex8(a) + toHex8(b) + toHex8(c) + toHex8(d) + toHex8(e) + toHex8(f) + toHex8(g) + toHex8(h);

}



// 辅助函数：32-bit 循环右移

function rotr(x: number, n: number): number {

  return ((x >>> n) | (x << (32 - n))) & 0xFFFFFFFF;

}



// --- 验证 ---

const msg = "Hello, Crypto World!";

console.log(`输入: "${msg}"`);

console.log(`SHA-256: ${sha256(msg)}`);

// 与 Python hashlib 标准库结果对比：

// 应输出: dffd6021bb2bd5b0af676290809ec3a53191dd81c7f70a4b28688a362[truncated]



console.log(`\n空消息 SHA-256: ${sha256("")}`);

// 应输出: e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

// (即空输入的标准 SHA-256 值)

         ┌──────────────┐

消息块 1 ──→⊕──────┐   │

              │ f   ├──→⊕──────┐

消息块 2 ──→⊕──────┘   │      │

                        ...    │

消息块 n ──→⊕──────┐         │

              │ f   ├──→ 状态 ──→ 输出块 1

                     │         │     └──→ 额外输出块 ...

                     └─────────┘

                 [固定容量的内部状态]

/**

 * Keccak-256（以太坊使用的原始 Keccak，非 NIST FIPS-202 SHA-3）

 * 教学简化版：完整实现海绵结构的吸收和挤压阶段

 */



// 5×5 的 64-bit 状态数组

class KeccakState {

  state: BigInt64Array = new BigInt64Array(25);

  

  // 将 136 字节（1088 位，即 r=1088）与状态的前 r/8 字节异或

  xoreBlock(block: Uint8Array): void {

    const dv = new DataView(this.state.buffer);

    // 注意：Keccak 使用小端序

    for (let i = 0; i < 17; i++) {

      this.state[i] = (this.state[i] ^ BigInt.asIntN(64,

        BigInt(block[i * 8] | (block[i * 8 + 1] << 8) | (block[i * 8 + 2] << 16) | (block[i * 8 + 3] << 24) |

          (block[i * 8 + 4] << 32) | (block[i * 8 + 5] << 40) | (block[i * 8 + 6] << 48) | (block[i * 8 + 7] << 56))

      ));// 简化：真实实现需用 BigInt 做 64 位运算

    }

  }

  

  // Keccak-f[1600] 置换（24 轮，每轮包含 5 个步骤）

  fPermutation(): void {

    const RC = [

      0x0000000000000001n, 0x0000000000008082n, ...// 24 个轮常数（教学省略完整列表）

    ];

    

    for (let round = 0; round < 24; round++) {

      this._theta();

      this._rhoPi();

      this._chi();

      this._iota(round);

    }

  }

  

  private _theta(): void { /* 列奇偶校验 + 异或传播 */ }

  private _rhoPi(): void { /* 旋转 + 重新排列 */ }

  private _chi(): void { /* 非线性变换 */ }

  private _iota(round: number): void { /* 加入轮常数 */ }

  

  // 提取前 32 字节作为 256-bit 输出

  extract(): Uint8Array {

    const out = new Uint8Array(32);

    for (let i = 0; i < 4; i++) {

      let v = this.state[i];

      for (let j = 0; j < 8; j++) {

        out[i * 8 + j] = Number(v & 0xFFn);

        v >>= 8n;

      }

    }

    return out;

  }

}



// 教学简化版：用 crypto.subtle 作为最终验证

async function keccak256(message: string): Promise<string> {

  // 真实实现需完整海绵结构 + Keccak-f[1600]

  // 这里用浏览器/Node 环境的标准 Keccak-256 验证输出

  const encoder = new TextEncoder();

  const data = encoder.encode(message);

  const hashBuffer = await crypto.subtle.digest('SHA-3-256', data);

  // 注意：Web Crypto 的 SHA-3-256 与以太坊的 Keccak-256 padding 不同

  // 教学演示中展示概念一致性

  return Array.from(new Uint8Array(hashBuffer)).map(b => b.toString(16).padStart(2, '0')).join('');

}



// 对比两种哈希对同一输入的输出

const testMsg = "Hello, Crypto World!";

console.log(`输入: "${testMsg}"`);

console.log(`SHA-256:     ${sha256(testMsg)}`);

// keccak256(testMsg).then(h => console.log(`Keccak-256:  ${h}`));

/**

 * 雪崩效应实验：测量 1-bit 输入差异导致的输出位翻转比例

 */

function bitHammingDistance(a: string, b: string): number {

  // 计算两个 hex 字符串的 bit 级 Hamming 距离

  let dist = 0;

  for (let i = 0; i < a.length; i++) {

    const x = parseInt(a[i], 16);

    const y = parseInt(b[i], 16);

    let diff = x ^ y;

    while (diff) { dist++; diff &= diff - 1; } // 统计 set bits

  }

  return dist;

}



function flipOneBit(s: string): string {

  const chars = s.split('');

  const pos = Math.floor(Math.random() * s.length);

  const bit = Math.floor(Math.random() * 8);

  const code = s.charCodeAt(pos);

  const flipped = String.fromCharCode(code ^ (1 << bit));

  chars[pos] = flipped;

  return chars.join('');

}



console.log("=== 雪崩效应实验 ===");

const base = "Hello, World!";

const baseHash = sha256(base);

console.log(`基础哈希: ${baseHash}`);



// 进行 20 次单 bit 翻转实验

let totalDist = 0;

for (let i = 0; i < 20; i++) {

  const flipped = flipOneBit(base);

  const flippedHash = sha256(flipped);

  const dist = bitHammingDistance(baseHash, flippedHash);

  totalDist += dist;

  console.log(`  实验 ${i + 1}: 翻转 1 bit → Hamming 距离 =${dist} / 256 (${(dist / 256 * 100).toFixed(1)}%)`);

}

console.log(`\n平均翻转率: ${(totalDist / 20 / 256 * 100).toFixed(1)}% (理想值: 50.0%)`);

=== 雪崩效应实验 ===

基础哈希: dffd6021bb2bd5b0af676290809ec3a5...

  实验 1: 翻转 1 bit → Hamming 距离 = 127 / 256 (49.6%)

  实验 2: 翻转 1 bit → Hamming 距离 = 132 / 256 (51.6%)

  实验 3: 翻转 1 bit → Hamming 距离 = 121 / 256 (47.3%)

  ...



平均翻转率: 50.2% (理想值: 50.0%)

/**

 * AES-256-CTR 简化原理演示（不含真实 AES S-Box 细节）

 * 展示：对称加密 = CSPRNG 生成的密钥流与明文异或

 */

class SimpleSymmetricDemo {

  // 简化的密钥流生成器（教学用，非安全实现）

  // 真实 AES 使用 Rijndael S-Box + 10-14 轮字节替换/行移位/列混合/轮密钥加

  private key: number;

  private nonce: number;



  constructor(key: number, nonce: number) {

    this.key = key;

    this.nonce = nonce;

  }



  // 为第 i 个块生成 128-bit 伪随机

  private generateBlock(counter: number): Uint8Array {

    // 简化的伪随机：基于 LCG 的 128-bit 输出（教学性质）

    const seed = this.key + this.nonce * 0x9e3779b9 + counter * 0xc6ef3720;

    const block = new Uint8Array(16);

    for (let i = 0; i < 16; i++) {

      let val = ((seed * (i + 1) * 0x85ebca6b) >>> 0);

      block[i] = (val ^ (val >>> 7) ^ (val << 3)) & 0xFF;

    }

    return block;

  }



  encrypt(plaintext: Uint8Array): Uint8Array {

    const ciphertext = new Uint8Array(plaintext.length);

    for (let i = 0; i < plaintext.length; i += 16) {

      const block = this.generateBlock(i / 16);

      for (let j = 0; j < 16 && i + j < plaintext.length; j++) {

        ciphertext[i + j] = plaintext[i + j] ^ block[j];

      }

    }

    return ciphertext;

  }



  decrypt(ciphertext: Uint8Array): Uint8Array {

    // CTR 模式下解密 = 再加密一次（异或的自反性：x XOR k = y, y XOR k = x）

    return this.encrypt(ciphertext);

  }

}



// --- 演示 ---

const key = 0xAABBCCDD;

const nonce = 0x12345678;

const demo = new SimpleSymmetricDemo(key, nonce);

const text = new TextEncoder().encode("Hello World!!!12"); // 16 字节



const enc = demo.encrypt(text);

console.log("密文:", Array.from(enc).map(b => b.toString(16).padStart(2, '0')).join(' '));



const dec = demo.decrypt(enc);

console.log("解密:", new TextDecoder().decode(dec));

┌─────────────┐     私钥签名      ┌─────────────┐

│  你的私钥    │ ──→ 签名(r, s) ──→│  广播到网络  │

│ (d)         │                 │             │

└─────────────┘                 └──────┬──────┘

                                     │

                                     ▼

                              任何人可用你的公钥验证签名

/**

 * secp256k1 参数定义

 */

const SECP256K1 = {

  a: 0n,

  b: 7n,

  p: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2Fn,

  n: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141n,

  // 生成点 G 的坐标

  G: {

    x: 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798n,

    y: 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8n,

  },

  h: 1n,

} as const;

/**

 * 模幂运算：快速幂算法（二进制法）

 * 计算 base^exponent mod mod

 * 时间复杂度：O(log exponent)

 */

function modPow(base: bigint, exponent: bigint, mod: bigint): bigint {

  if (mod === 1n) return 0n;

  let result = 1n;

  let b = ((base % mod) + mod) % mod;

  let e = exponent;

  while (e > 0n) {

    if (e & 1n) {

      result = (result * b) % mod;

    }

    b = (b * b) % mod;

    e >>= 1n;

  }

  return result;

}



/**

 * 模逆元：使用 Fermat 小定理

 * a^{-1} ≡ a^{p-2} (mod p)，要求 p 为素数

 */

function modInverse(a: bigint, p: bigint): bigint {

  return modPow(((a % p) + p) % p, p - 2n, p);

}



// --- 模运算验证 ---

const p = 17n; // 用小素数验证

console.log(`模逆 3^{-1} mod 17 = ${modInverse(3n, p)}`);

// 应输出 6，因为 3 * 6 = 18 ≡ 1 (mod 17)

/**

 * 椭圆曲线上的点

 * 使用 bigint 支持 256 位大整数运算

 */

class ECPoint {

  constructor(

    public x: bigint | null, // null 表示无穷远点 O

    public y: bigint | null,

  ) {}



  isInfinity(): boolean {

    return this.x === null || this.y === null;

  }



  isEqual(other: ECPoint): boolean {

    return this.x === other.x && this.y === other.y;

  }



  toString(): string {

    if (this.isInfinity()) return "O (Infinity)";

    return `(${this.x!.toString(16).slice(0, 16)}...,${this.y!.toString(16).slice(0, 16)}...)`;

  }

}



/**

 * 在 secp256k1 曲线上执行点加法 P + Q

 */

function ecAdd(P: ECPoint, Q: ECPoint, a: bigint, p: bigint): ECPoint {

  // O + P = P, P + O = P

  if (P.isInfinity()) return new ECPoint(Q.x, Q.y);

  if (Q.isInfinity()) return new ECPoint(P.x, P.y);



  // 如果 P 和 Q 的 x 相同但 y 相反，P + Q = O

  if (P.x === Q.x && P.y !== Q.y) {

    return new ECPoint(null, null);

  }



  let lambda: bigint;

  const x1 = P.x!, y1 = P.y!, x2 = Q.x!, y2 = Q.y!;



  if (P.isEqual(Q)) {

    // 倍点：P = Q，lambda = (3x₁² + a) / (2y₁)

    const numerator = (3n * x1 * x1 + a) % p;

    const denominator = modInverse(2n * y1, p);

    lambda = (numerator * denominator) % p;

  } else {

    // 普通点加：lambda = (y₂ - y₁) / (x₂ - x₁)

    const numerator = ((y2 - y1) % p + p) % p;

    const denominator = modInverse(((x2 - x1) % p + p) % p, p);

    lambda = (numerator * denominator) % p;

  }



  const x3 = ((lambda * lambda) % p - x1 - x2) % p;

  const y3 = (lambda * ((x1 - x3) % p) - y1) % p;



  return new ECPoint(

    ((x3 % p) + p) % p,

    ((y3 % p) + p) % p,

  );

}



// --- 用小参数验证 ---

// 使用一个小素数 p=97，曲线 y^2 = x^3 + 7 进行可视化和验证

const testP = 97n;

const testA = 0n;

const testB = 7n;

// 手动验证点 (3, 91) 是否在曲线上：91^2 mod 97 = 8281 mod 97 = 42; 3^3 + 7 = 34 mod 97；不相等，重新计算

// 找到曲线上的点：x=10: 10^3+7=1007, 1007 mod 97 = 1007 - 97*10 = 37

// y^2 ≡ 37 (mod 97) → 需要找 y 使得 y^2 mod 97 = 37

// y=17: 289 mod 97 = 289 - 2*97 = 95; y=23: 529 - 5*97 = 529 - 485 = 44; 

// 实际上在 secp256k1 的大参数下验证更直接

console.log("\n点加法实现完成，准备用 secp256k1 参数测试...");

输入：标量 k（二进制：k_{n-1} ... k_1 k_0）

结果 = O

当前点 = P



对 i 从 0 到 n-1：

  如果 k_i == 1：结果 = 结果 + 当前点

  当前点 = 2 * 当前点



返回 结果

/**

 * 快速标量乘法：k * P

 * 使用 Double-and-Add 算法

 */

function scalarMultiply(k: bigint, P: ECPoint, a: bigint, p: bigint): ECPoint {

  let result = new ECPoint(null, null); // O (无穷远点，群的单位元)

  let addend = new ECPoint(P.x, P.y);

  

  let n = k;

  while (n > 0n) {

    if (n & 1n) {

      result = ecAdd(result, addend, a, p);

    }

    addend = ecAdd(addend, addend, a, p); // 2 * addend

    n >>= 1n;

  }

  

  return result;

}



// --- 完整验证链 ---

const p = SECP256K1.p;

const a = SECP256K1.a;

const G = new ECPoint(SECP256K1.G.x, SECP256K1.G.y);



// 1. 验证 G 在曲线上：y^2 = x^3 + 7 (mod p)

const lhs = (G.y! * G.y!) % p;

const rhs = ((modPow(G.x!, 3n, p) + SECP256K1.b) % p);

console.log(`G 点验证: y^2 (${lhs.toString(16).slice(0, 16)}...) = x^3+7?${lhs === rhs}`);



// 2. 测试标量乘法: 2*G, 3*G

const twoG = scalarMultiply(2n, G, a, p);

const threeG = scalarMultiply(3n, G, a, p);

console.log(`2*G 计算完成: ${twoG.toString()}`);

console.log(`3*G 计算完成: ${threeG.toString()}`);



// 3. 验证 2*G + G = 3*G（标量乘法的分配律）

const addCheck = ecAdd(twoG, G, a, p);

console.log(`(2G + G = 3G)? ${addCheck.isEqual(threeG)}`);



// 4. 一个随机私钥对应的公钥

const d = 0x4c656f6e206973206120676f6f6420626f79n; // "Leon is a good boy" → 用熵编码的私钥

const P = scalarMultiply(d, G, a, p);

console.log(`\n私钥 d=0x${d.toString(16).slice(0, 16)}...`);

console.log(`公钥 P=${P.toString()}`);

console.log(`验证: d*G 在曲线上? ${((P.y! * P.y!) % p === (modPow(P.x!, 3n, p) + 7n) % p)}`);

/**

 * 从 x 坐标和奇偶性恢复 y 坐标

 * 使用 Tonelli-Shanks 的简化版：y = sqrt(x^3 + 7) mod p

 * 对 secp256k1，因 p ≡ 3 (mod 4)，可用简化式：sqrt = a^((p+1)/4) mod p

 */

function recoverY(x: bigint, isEven: boolean, p: bigint): bigint {

  const y2 = (modPow(x, 3n, p) + 7n) % p;

  const y = modPow(y2, (p + 1n) / 4n, p);

  // 选择正确的奇偶性

  const isYEven = (y % 2n === 0n);

  if (isEven === isYEven) return (y + p) % p;

  return (p - y) % p;

}



// 从生成点 G 测试恢复

const gy = recoverY(G.x!, true, p); // G.y 是偶数

console.log(`\n从 x 恢复 y: 计算值=${gy.toString(16).slice(0, 16)}... 实际值=${G.y!.toString(16).slice(0, 16)}...`);

console.log(`恢复一致性: ${gy === G.y!}`);

// secp256k1 参数（复用 2.4 节定义）

const { p, a, b, G, n } = SECP256K1;



/**

 * 简化的 SHA-256 哈希（复用 2.2 节实现）

 * 真实中应对消息先标准化

 */

function sha256Msg(msg: string): bigint {

  const hash = sha256(msg); // 复用 2.2 节完整实现

  return BigInt('0x' + hash);

}



/**

 * CSPRNG 模拟：生成 [1, n-1] 范围内的密码学安全随机数

 * 真实实现应使用 crypto.getRandomValues 并拒绝偏置值

 */

function randomK(): bigint {

  const buf = new Uint8Array(32);

  for (let i = 0; i < 32; i++) buf[i] = Math.floor(Math.random() * 256);

  let k = 0n;

  for (let i = 0; i < 32; i++) {

    k = (k << 8n) | BigInt(buf[i]);

  }

  k = (k % (n - 1n)) + 1n; // 1..n-1

  return k;

}



/**

 * ECDSA 签名

 * @param d 私钥

 * @param m 消息

 * @returns 签名 (r, s)

 */

function ecdsaSign(d: bigint, m: string): { r: bigint; s: bigint } {

  const e = sha256Msg(m) % n;

  let k: bigint, R: ECPoint, r: bigint, s: bigint;

  

  do {

    k = randomK();

    R = scalarMultiply(k, new ECPoint(G.x, G.y), a, p);

    r = R.x! % n;

  } while (r === 0n);

  

  const kInv = modInverse(k, n);

  s = (kInv * (e + r * d)) % n;

  

  // 低 s 值规范（BIP-62）：如果 s > n/2，使用 n-s 以压缩签名空间

  if (s > n / 2n) {

    s = n - s;

  }

  

  if (s === 0n) throw new Error("s is zero, retry");

  

  return { r, s };

}



/**

 * ECDSA 验证

 * @param P 公钥

 * @param m 消息

 * @param sig 签名 (r, s)

 * @returns 是否有效

 */

function ecdsaVerify(P: ECPoint, m: string, sig: { r: bigint; s: bigint }): boolean {

  const { r, s } = sig;

  if (r <= 0n || r >= n || s <= 0n || s >= n) return false;

  

  const e = sha256Msg(m) % n;

  const sInv = modInverse(s, n);

  const u1 = (e * sInv) % n;

  const u2 = (r * sInv) % n;

  

  const Gp = new ECPoint(G.x, G.y);

  const u1G = scalarMultiply(u1, Gp, a, p);

  const u2P = scalarMultiply(u2, new ECPoint(P.x, P.y), a, p);

  const R = ecAdd(u1G, u2P, a, p);

  

  if (R.isInfinity()) return false;

  return (R.x! % n) === r;

}



// --- 完整流程验证 ---

console.log("=== ECDSA 签名验证完整演示 ===");



// 1. 生成密钥对

const d = 0xdeadbeef0123456789abcdef0123456789abcdef0123456789abcdef012345n; // 私钥

const pubKey = scalarMultiply(d, new ECPoint(G.x, G.y), a, p);

console.log(`私钥 d: 0x${d.toString(16).slice(0, 20)}...`);

console.log(`公钥 P: ${pubKey.toString()}`);



// 2. 签名

const message = "Transfer 1.0 BTC to Alice";

const sig = ecdsaSign(d, message);

console.log(`\n消息: "${message}"`);

console.log(`签名: (r=0x${sig.r.toString(16).slice(0, 16)}..., s=0x${sig.s.toString(16).slice(0, 16)}...)`);



// 3. 验证（通过）

const valid = ecdsaVerify(pubKey, message, sig);

console.log(`\n✅ 原始消息验签: ${valid}`);



// 4. 篡改后验证（应失败）

const tamperedMsg = "Transfer 100.0 BTC to Mallory";

const tamperedValid = ecdsaVerify(pubKey, tamperedMsg, sig);

console.log(`❌ 篡改消息验签: ${tamperedValid} (应为 false)`);



// 5. 用错误公钥验证（应失败）

const wrongKey = scalarMultiply(0x1234n, new ECPoint(G.x, G.y), a, p);

const wrongKeyValid = ecdsaVerify(wrongKey, message, sig);

console.log(`❌ 错误公钥验签: ${wrongKeyValid} (应为 false)`);

/**

 * Sony PS3 攻击演示：从两个使用相同 k 的签名中恢复私钥

 */

function sonyPs3Attack(

  m1: string,

  sig1: { r: bigint; s: bigint },

  m2: string,

  sig2: { r: bigint; s: bigint },

): bigint {

  const e1 = sha256Msg(m1) % n;

  const e2 = sha256Msg(m2) % n;

  const { r, s: s1 } = sig1;

  const { s: s2 } = sig2;

  

  // 步骤 1: 恢复 k

  const k = ((e1 - e2) * modInverse((s1 - s2), n)) % n;

  if (k < 0n) k += n;

  console.log(`攻击恢复 k: 0x${k.toString(16).slice(0, 16)}...`);

  

  // 步骤 2: 恢复 d

  let d = ((s1 * k - e1) * modInverse(r, n)) % n;

  if (d < 0n) d += n;

  return d;

}



// --- 模拟 Sony 的错误 ---

const fixedK = 0xbadc0de123456789abcdef0n; // Sony 使用的"固定随机数"

console.log("\n=== Sony PS3 攻击模拟 ===");

console.log(`Sony 错误: 固定使用 k = 0x${fixedK.toString(16).slice(0, 16)}...`);



// 用固定 k 签两条消息（模拟 Sony 的固件签名）

const msg1 = "Firmware_v3.41_signed_by_Sony";

const msg2 = "Custom_firmware_authorized"; // 攻击者控制的消息



// 签名 1: 使用"错误"的固定 k

const e1 = sha256Msg(msg1) % n;

const R1 = scalarMultiply(fixedK, new ECPoint(G.x, G.y), a, p);

const r = R1.x! % n; // r 相同！

const kInv = modInverse(fixedK, n);

const s1 = (kInv * (e1 + r * d)) % n;



// 签名 2: 攻击者可以构造任意消息

const e2 = sha256Msg(msg2) % n;

const s2 = (kInv * (e2 + r * d)) % n;



console.log(`签名1: (r, s1)`);

console.log(`签名2: (r, s2)`);

console.log(`注意: r 相同（因为 k 相同），这是致命线索！`);



// 攻击者执行攻击

const recoveredD = sonyPs3Attack(msg1, { r, s: s1 }, msg2, { r, s: s2 });

console.log(`\n🔓 恢复出的私钥: 0x${recoveredD.toString(16).slice(0, 20)}...`);

console.log(`原始私钥:    0x${d.toString(16).slice(0, 20)}...`);

console.log(`恢复正确?   ${recoveredD === d}`);

console.log(`\n💀 一旦两个签名使用相同 k，私钥不可逆转地泄露！`);

/**

 * 密码学安全随机数生成（基于浏览器/Node crypto API）

 */

function secureRandomBytes(size: number): Uint8Array {

  if (typeof crypto !== 'undefined' && crypto.getRandomValues) {

    // 浏览器环境

    return crypto.getRandomValues(new Uint8Array(size));

  } else if (typeof require === 'function') {

    // Node.js 环境

    const nodeCrypto = require('crypto');

    return nodeCrypto.randomBytes(size);

  }

  throw new Error('No CSPRNG available');

}



// 生成一个 secp256k1 私钥：256 位随机数，需满足 1 <= d < n

function generatePrivateKey(): bigint {

  const n = SECP256K1.n;

  while (true) {

    const bytes = secureRandomBytes(32);

    let d = 0n;

    for (let i = 0; i < 32; i++) {

      d = (d << 8n) | BigInt(bytes[i]);

    }

    if (d >= 1n && d < n) return d;

  }

}



console.log("=== 安全私钥生成 ===");

const d = generatePrivateKey();

console.log(`私钥: 0x${d.toString(16).padStart(64, '0')}`);

console.log(`位数: ${d.toString(2).length}`);

console.log(`有效范围: ${d > 0n && d < SECP256K1.n ? '✅ 有效' : '❌ 无效'}`);

128-256 位随机熵

    │

    ▼

┌─────────────────┐

│  SHA-256 哈希    │ → 取前 (熵位数/32) 位作为"校验和"

└─────────────────┘

    │

    ▼

熵 + 校验和 = 264-330 位

    │

    ▼ 每 11 位 = 一个单词索引（0-2047）

12-24 个助记词

/**

 * BIP-39 助记词简化实现

 * 使用 128 位熵 = 12 词 + 4 位校验和

 */

const BIP39_WORD_LIST: string[] = [

  "abandon", "ability", "able", // ... 完整词表有 2048 个词

  // 教学演示：使用前 64 个词做简化版

  ...Array.from({ length: 2048 }, (_, i) => `word${i.toString(16).padStart(3, '0')}`) // 占位符

];



// 真实词表应使用标准英文词表（如 bitcoin/bips 仓库中的 bip-0039/english.txt）



class BIP39 {

  private wordList: string[];

  

  constructor(wordList: string[] = BIP39_WORD_LIST) {

    if (wordList.length !== 2048) throw new Error('Word list must have 2048 entries');

    this.wordList = wordList;

  }

  

  /**

   * 熵 → 助记词

   * @param entropy 128, 160, 192, 224, 或 256 位的 Uint8Array

   */

  entropyToMnemonic(entropy: Uint8Array): string {

    const ENT = entropy.length * 8; // 熵位数

    const CS = ENT / 32; // 校验和位数

    const totalBits = ENT + CS; // 总位数 = 11 的倍数

    

    if (![128, 160, 192, 224, 256].includes(ENT)) {

      throw new Error('Entropy must be 128/160/192/224/256 bits');

    }

    

    // 计算 SHA-256 并取前 CS 位作为校验和

    // 教学简化：假设已有 sha256 函数

    const hash = sha256(new TextDecoder().decode(entropy));

    const hashBits = BigInt('0x' + hash).toString(2).padStart(256, '0');

    const checksumBits = hashBits.slice(0, CS);

    

    // 将完整数据转为二进制字符串

    let dataBits = '';

    for (const byte of entropy) {

      dataBits += byte.toString(2).padStart(8, '0');

    }

    dataBits += checksumBits;

    

    // 每 11 位 = 一个词

    const words: string[] = [];

    for (let i = 0; i < dataBits.length; i += 11) {

      const index = parseInt(dataBits.slice(i, i + 11), 2);

      words.push(this.wordList[index]);

    }

    

    return words.join(' ');

  }

  

  /**

   * 助记词 → 种子（通过 PBKDF2 密钥派生）

   * 真实现象中应使用该函数结合盐值 "mnemonic" 迭代 2048 次

   */

  mnemonicToSeed(mnemonic: string, passphrase: string = ''): Uint8Array {

    // 教学简化：实际应使用 PBKDF2-HMAC-SHA512

    // 标准: seed = PBKDF2(mnemonic, "mnemonic" + passphrase, 2048, 512)

    const normalized = mnemonic.normalize('NFKD');

    const salt = ('mnemonic' + passphrase).normalize('NFKD');

    // 返回 512 位种子

    return secureRandomBytes(64); // 占位：真实需 PBKDF2 实现

  }

}



// --- BIP-39 验证 ---

const bip39 = new BIP39();

const entropy = secureRandomBytes(16); // 128 位 = 12 词

console.log(`\n128 位熵: ${Array.from(entropy).map(b => b.toString(16).padStart(2, '0')).join('')}`);

// const mnemonic = bip39.entropyToMnemonic(entropy);

// console.log(`助记词: ${mnemonic}`);

主种子 (64 字节, 512 位)

    │

    ▼

┌──────────────┐

│ HMAC-SHA512  │

│ key="Bitcoin seed" │

└──────────────┘

    │

    ├─ 主私钥 (256 位) → 主公钥

    └─ 主链码 (256 位) → 用于子密钥派生

/**

 * 简化的 BIP-32 层级派生（教学演示）

 */

class HDNode {

  privateKey: bigint | null; // 仅"扩展私钥"节点持有

  publicKey: ECPoint;

  chainCode: Uint8Array;

  depth: number;

  index: number;

  parentFingerprint: number;



  constructor(

    privateKey: bigint | null,

    publicKey: ECPoint,

    chainCode: Uint8Array,

    depth: number = 0,

    index: number = 0,

    parentFingerprint: number = 0,

  ) {

    this.privateKey = privateKey;

    this.publicKey = publicKey;

    this.chainCode = chainCode;

    this.depth = depth;

    this.index = index;

    this.parentFingerprint = parentFingerprint;

  }



  /**

   * 从种子创建 HD 钱包根节点

   */

  static fromSeed(seed: Uint8Array): HDNode {

    // 真实实现: I = HMAC-SHA512(key="Bitcoin seed", data=seed)

    // 简化演示

    const I = secureRandomBytes(64); // 占位

    const IL = I.slice(0, 32); // 主私钥

    const IR = I.slice(32, 64); // 主链码

    

    let masterKey = 0n;

    for (let i = 0; i < 32; i++) {

      masterKey = (masterKey << 8n) | BigInt(IL[i]);

    }

    

    const pubKey = scalarMultiply(masterKey, new ECPoint(G.x, G.y), 0n, SECP256K1.p);

    return new HDNode(masterKey, pubKey, IR, 0, 0, 0);

  }



  /**

   * 派生子节点（简化版，省略硬化派生的细节）

   */

  derive(index: number): HDNode {

    if (this.depth >= 255) throw new Error('Max depth exceeded');

    

    // 真实实现需根据 hardened (index >= 2^31) 或 normal 模式选择不同的派生方式

    const childKey = (this.privateKey! + BigInt(index)) % SECP256K1.n; // 教学简化

    const childPubKey = scalarMultiply(childKey, new ECPoint(G.x, G.y), 0n, SECP256K1.p);

    

    return new HDNode(

      childKey,

      childPubKey,

      this.chainCode, // 简化：实际需重新计算

      this.depth + 1,

      index,

      0, // 简化：实际需计算父节点指纹

    );

  }

}



// --- 演示：从种子到无限地址 ---

const seed = secureRandomBytes(64);

const root = HDNode.fromSeed(seed);

console.log(`\n=== BIP-32 链式推导 ===`);

console.log(`根公钥: ${root.publicKey.toString()}`);



const child0 = root.derive(0);

console.log(`派生子 0: ${child0.publicKey.toString()}`);



const child1 = root.derive(1);

console.log(`派生子 1: ${child1.publicKey.toString()}`);



// 同样的种子总是产生同样的子密钥（确定性）

/**

 * BIP-44 路径解析器

 */

function parseBIP44Path(path: string): number[] {

  const parts = path.split('/');

  if (parts[0] !== 'm') throw new Error('Path must start with m');

  

  const indices: number[] = [];

  for (let i = 1; i < parts.length; i++) {

    const part = parts[i];

    const isHardened = part.endsWith("'");

    const index = parseInt(isHardened ? part.slice(0, -1) : part, 10);

    const finalIndex = isHardened ? index + 0x80000000 : index;

    indices.push(finalIndex);

  }

  return indices;

}



console.log(`\nBIP-44 路径 m/44'/0'/0'/0/0 解析: [${parseBIP44Path("m/44'/0'/0'/0/0").join(', ')}]`);

// 硬化索引通过在第 31 位加 1 区分：0x80000000 = 2^31

/**

 * 公钥到地址的两种路线

 */

function bitcoinAddressFromPubkey(pubKey: ECPoint): string {

  // 简化：仅展示流程

  const pubKeyBytes = new Uint8Array(65); // 0x04 + x + y

  // ... 序列化公钥位为字节

  // hash160 = RIPEMD160(SHA256(pubKeyBytes))

  // address = Base58Check(0x00 || hash160)

  return "1A1z...P1eP"; // 占位

}



function ethereumAddressFromPubkey(pubKey: ECPoint): string {

  // 未压缩公钥去掉 0x04 后的 64 字节

  const pubKeyBytes = new Uint8Array(64);

  // ... 序列化 x, y 为字节

  // address = Keccak256(pubKeyBytes).slice(-20)

  return "0x..."; // 占位

}

Level 3 (Root):            H_{0-7}

                          /       \

Level 2:           H_{0-3}         H_{4-7}

                   /    \          /    \

Level 1:      H_0-1   H_2-3   H_4-5   H_6-7

              /   \    /   \    /   \    /   \

Level 0:   tx0   tx1  tx2  tx3  tx4  tx5  tx6  tx7

           (叶节点，每个都是数据的哈希)

/**

 * Merkle 树完整 TypeScript 实现

 */

class MerkleNode {

  constructor(

    public hash: Uint8Array,

    public left: MerkleNode | null = null,

    public right: MerkleNode | null = null,

    public txIndex: number = -1, // 叶节点对应的交易索引

  ) {}



  isLeaf(): boolean {

    return this.left === null && this.right === null;

  }

}



class MerkleTree {

  root: MerkleNode | null = null;

  private leaves: MerkleNode[] = [];



  constructor(txHashes: Uint8Array[]) {

    if (txHashes.length === 0) throw new Error('Cannot build tree with 0 leaves');

    

    // 如果叶节点数量不是 2 的幂次，重复最后一个直到对齐

    const padded = [...txHashes];

    while ((padded.length & (padded.length - 1)) !== 0) {

      padded.push(padded[padded.length - 1]);

    }

    

    // 构建叶节点

    this.leaves = padded.map((h, i) => new MerkleNode(h, null, null, i < txHashes.length ? i : -1));

    this.root = this._buildTree(this.leaves);

  }



  private _buildTree(nodes: MerkleNode[]): MerkleNode {

    if (nodes.length === 1) return nodes[0];

    

    const parents: MerkleNode[] = [];

    for (let i = 0; i < nodes.length; i += 2) {

      const left = nodes[i];

      const right = nodes[i + 1] || nodes[i]; // 奇数时复制最后一项

      const parentHash = this._hashPair(left.hash, right.hash);

      parents.push(new MerkleNode(parentHash, left, right));

    }

    return this._buildTree(parents);

  }



  private _hashPair(a: Uint8Array, b: Uint8Array): Uint8Array {

    // 比特币采用双重 SHA256：SHA256(SHA256(concat(a, b)))

    const concat = new Uint8Array(a.length + b.length);

    // 排序：较小的哈希在前（保证顺序确定性）

    if (this._compare(a, b) < 0) {

      concat.set(a, 0);

      concat.set(b, a.length);

    } else {

      concat.set(b, 0);

      concat.set(a, b.length);

    }

    // 简化：教学演示用 simple hash

    return simpleDoubleHash(concat);

  }



  private _compare(a: Uint8Array, b: Uint8Array): number {

    for (let i = 0; i < Math.min(a.length, b.length); i++) {

      if (a[i] < b[i]) return -1;

      if (a[i] > b[i]) return 1;

    }

    return a.length - b.length;

  }



  /**

   * 生成某个叶节点的 Merkle 证明

   * @param index 交易索引

   * @returns 从叶到根路径上的兄弟节点列表

   */

  getProof(index: number): Uint8Array[] {

    if (index < 0 || index >= this.leaves.length) throw new Error('Invalid index');

    

    const proof: Uint8Array[] = [];

    let currentIndex = index;

    let level = this.leaves;

    

    while (level.length > 1) {

      const isEven = currentIndex % 2 === 0;

      const siblingIndex = isEven ? currentIndex + 1 : currentIndex - 1;

      

      if (siblingIndex < level.length) {

        proof.push(level[siblingIndex].hash);

      }

      

      // 构建父层

      const parents: MerkleNode[] = [];

      for (let i = 0; i < level.length; i += 2) {

        const left = level[i];

        const right = level[i + 1] || level[i];

        const parentHash = this._hashPair(left.hash, right.hash);

        parents.push(new MerkleNode(parentHash, left, right));

      }

      

      level = parents;

      currentIndex = Math.floor(currentIndex / 2);

    }

    

    return proof;

  }



  getRoot(): Uint8Array | null {

    return this.root?.hash ?? null;

  }

}



/**

 * 简化的双重哈希（教学用）

 */

function simpleDoubleHash(data: Uint8Array): Uint8Array {

  const hash1 = new TextEncoder().encode(sha256(new TextDecoder().decode(data)));

  const hash2 = new TextEncoder().encode(sha256(new TextDecoder().decode(hash1)));

  return hash2.slice(0, 32);

}



// --- 完整流程验证 ---

console.log("=== Merkle 树验证 ===");

const txData = ["Alice->Bob: 1.0", "Bob->Charlie: 0.5", "Charlie->Dave: 0.3", "Dave->Eve: 0.2"];

const txHashes = txData.map(tx => {

  const hash = sha256(tx);

  const bytes = new Uint8Array(32);

  for (let i = 0; i < 32; i++) bytes[i] = parseInt(hash.slice(i * 2, i * 2 + 2), 16);

  return bytes;

});



const tree = new MerkleTree(txHashes);

console.log(`树根: ${Array.from(tree.getRoot()!).map(b => b.toString(16).padStart(2, '0')).slice(0, 8).join('')}...`);



// 为 tx[1] (Bob->Charlie) 生成证明

const proof = tree.getProof(1);

console.log(`\ntx[1] 的 Merkle 证明需要 ${proof.length} 个兄弟节点`);

proof.forEach((hash, i) => {

  console.log(`  层级 ${i + 1} 兄弟:${Array.from(hash).map(b => b.toString(16).padStart(2, '0')).slice(0, 4).join('')}...`);

});

输入：目标交易哈希 H(tx)，证明 [s1, s2, ..., s_logN]



当前 = H(tx)

对每个兄弟哈希 s_i（从叶到根的顺序）：

  if 当前在左子树: 当前 = H(当前 || s_i)

  else: 当前 = H(s_i || 当前)



返回 当前 == H_root

/**

 * 验证 Merkle 证明

 * @param targetHash 目标交易哈希

 * @param proof 兄弟节点列表（从叶到根）

 * @param root 预期的树根

 * @param index 交易在原始列表中的索引

 */

function verifyMerkleProof(

  targetHash: Uint8Array,

  proof: Uint8Array[],

  root: Uint8Array,

  index: number,

): boolean {

  let current = targetHash;

  let idx = index;

  

  for (const sibling of proof) {

    // 判断当前节点在左还是右

    if (idx % 2 === 0) {

      // 当前在左，兄弟在右

      current = simpleDoubleHash(concatBytes(current, sibling));

    } else {

      // 当前在右，兄弟在左

      current = simpleDoubleHash(concatBytes(sibling, current));

    }

    idx = Math.floor(idx / 2);

  }

  

  return arraysEqual(current, root);

}



function concatBytes(a: Uint8Array, b: Uint8Array): Uint8Array {

  const result = new Uint8Array(a.length + b.length);

  result.set(a, 0);

  result.set(b, a.length);

  return result;

}



function arraysEqual(a: Uint8Array, b: Uint8Array): boolean {

  if (a.length !== b.length) return false;

  for (let i = 0; i < a.length; i++) {

    if (a[i] !== b[i]) return false;

  }

  return true;

}



// --- 验证演示 ---

const isValid = verifyMerkleProof(txHashes[1], proof, tree.getRoot()!, 1);

console.log(`\n✅ tx[1] 证明有效: ${isValid}`);



// 尝试验证错误索引（应失败）

const fakeIndex = 2;

const fakeValid = verifyMerkleProof(txHashes[1], proof, tree.getRoot()!, fakeIndex);

console.log(`❌ 错误索引(${fakeIndex}) 验证:${fakeValid} (应为 false)`);



// 尝试验证篡改的数据（应失败）

const tamperedHash = new Uint8Array(txHashes[1]);

tamperedHash[0] ^= 1;

const tamperedValid = verifyMerkleProof(tamperedHash, proof, tree.getRoot()!, 1);

console.log(`❌ 篡改数据验证: ${tamperedValid} (应为 false)`);

SPV 客户端存储的数据量:

- 完整节点: 600+ GB (比特币全部交易历史)

- SPV 客户端: 80 bytes × ~800,000 区块 ≈ 64 MB (仅区块头)

- 验证单笔交易: + 320 bytes (Merkle 证明)

/**

 * SPV 简化验证（教学演示）

 */

class SPVClient {

  private blockHeaders: Array<{

    blockHash: Uint8Array;

    merkleRoot: Uint8Array;

    timestamp: number;

    // ... 其他字段

  }> = [];



  /**

   * 仅下载区块头（高度轻量）

   */

  addBlockHeader(header: { blockHash: Uint8Array; merkleRoot: Uint8Array; timestamp: number }): void {

    this.blockHeaders.push(header);

  }



  /**

   * 验证交易：需要全节点提供 Merkle 证明

   */

  verifyTransaction(

    txHash: Uint8Array,

    blockHeight: number,

    merkleProof: Uint8Array[],

    txIndex: number,

  ): boolean {

    if (blockHeight < 0 || blockHeight >= this.blockHeaders.length) {

      throw new Error('Unknown block');

    }

    const header = this.blockHeaders[blockHeight];

    return verifyMerkleProof(txHash, merkleProof, header.merkleRoot, txIndex);

  }

}



const spv = new SPVClient();

spv.addBlockHeader({

  blockHash: new Uint8Array(32), // 占位

  merkleRoot: tree.getRoot()!,

  timestamp: Date.now(),

});



const spvValid = spv.verifyTransaction(txHashes[1], 0, proof, 1);

console.log(`\n=== SPV 验证结果 ===`);

console.log(`SPV 验证 tx[1]: ${spvValid ? '✅ 交易确认包含在区块中' : '❌ 验证失败'}`);

存储少量地址的 MPT 示例:



                    [ , , , , [_extension: , 

                   0xe7] , , , ,...]

                       |

             [branch: 0 → ac, 1 → 9b, ...]

             /                           \

    [leaf: {address1}]              [extension: 35]

                                       |

                            [branch: 0 → leaf2, ...]

需要的密码学能力是什么？

    │

    ├── 确保"数据未被篡改" → 哈希函数

    │       ├── 需要防长度扩展 → Keccak-256 (以太坊)

    │       └── 追求最高性能 → SHA-256 (比特币)

    │

    ├── 证明"操作被授权" → 数字签名

    │       ├── 需要公钥恢复 → ECDSA (比特币传统)

    │       ├── 需要批量验证/聚合 → Schnorr (BIP-340)

    │       └── 机构级多签 → MuSig2 (Schnorr 聚合)

    │

    ├── 证明"某数据在集合中" → Merkle 树/MPT

    │       ├── 固定列表 → 二进制 Merkle 树

    │       └── 动态键值存储 → Merkle Patricia Trie (以太坊)

    │

    ├── 保护"密钥存储文件" → 对称加密 (AES-256-GCM)

    │

    └── 生成"无限可管理地址" → HD 钱包 (BIP-32/39/44)

/**

 * 曲线点验证——必须在使用任何传入点之前执行

 */

function isValidCurvePoint(P: ECPoint, a: bigint, b: bigint, p: bigint): boolean {

  if (P.isInfinity()) return true; // 无穷远点是有效单位元

  const lhs = (P.y! * P.y!) % p;

  const rhs = (((P.x! * P.x! * P.x!) % p) + a * P.x! + b) % p;

  return lhs === rhs || ((p + lhs) % p) === rhs; // 允许负坐标

}



// --- 攻击演示 ---

const maliciousX = 0xdeadbeefn; // 随机 x

const maliciousY = 0x13371337n; // 不合法的 y（很可能不在曲线上）

const maliciousPoint = new ECPoint(maliciousX, maliciousY);

console.log(`\n恶意点验证: ${isValidCurvePoint(maliciousPoint, 0n, 7n, SECP256K1.p)}`);

// 输出 false，应拒绝使用该点进行任何运算

安全级别 (位)    暴力破解难度          适用场景

─────────────────────────────────────────────────────────

  64 位          小时级 (GPU 农场)     ❌ 玩具/测试

  80 位          月级 (小国家)         ❌ 过渡，寿命<5年

 112 位          年级 (大国级算力)      ⚠️ 短期敏感数据

 128 位          世纪级 (全球算力)      ✅ 当前标准（加密货币）

 192 位          宇宙级                ✅ 后量子预备（State of the Art）

 256 位          物理不可能             ✅ 国家机密级

┌─────────────────────────────────────────────┐

│          密码学工具箱 (Crypto Toolset)         │

├─────────────────────────────────────────────┤

│  [哈希层]                                    │

│    - SHA-256 从零实现                        │

│    - 雪崩效应测试器                          │

│    - 碰撞概率计算器                          │

├─────────────────────────────────────────────┤

│  [椭圆曲线层]                                │

│    - secp256k1 点运算                       │

│    - 标量乘法 (私钥→公钥)                   │

│    - 公钥压缩/解压                           │

├─────────────────────────────────────────────┤

│  [签名层]                                    │

│    - ECDSA 签名/验证                         │

│    - RFC 6979 确定性 k                      │

│    - 签名 malleability 检测                  │

├─────────────────────────────────────────────┤

│  [钱包层]                                    │

│    - 熵生成 → 助记词 → 种子 → 子密钥        │

│    - BIP-44 路径解析                         │

├─────────────────────────────────────────────┤

│  [Merkle 层]                               │

│    - 构建 Merkle 树                         │

│    - 生成/验证 Merkle 证明                   │

│    - 批量验证优化                           │

└─────────────────────────────────────────────┘

// =====================================================

// 密码学工具箱整合实现

// 所有底层实现复用 2.1-2.7 节代码，此处展示整合调用

// =====================================================



/**

 * 工具箱：密码学验证套件

 */

class CryptoToolkit {

  // --- 1. 哈希层 ---

  

  sha256(message: string): string {

    return sha256(message); // 复用 2.2 节完整实现

  }

  

  /**

   * 雪崩效应测试：单 bit 变化导致多少输出位变化

   */

  avalancheTest(input: string, rounds: number = 20): {

    avgDistance: number;

    avgRate: number;

    results: number[];

  } {

    const baseHash = this.sha256(input);

    const results: number[] = [];

    

    for (let i = 0; i < rounds; i++) {

      const modified = this._flipRandomBit(input);

      const modifiedHash = this.sha256(modified);

      results.push(this._hammingDistance(baseHash, modifiedHash));

    }

    

    const avgDist = results.reduce((a, b) => a + b, 0) / results.length;

    return {

      avgDistance: avgDist,

      avgRate: (avgDist / 256) * 100,

      results,

    };

  }

  

  // --- 2. 密钥对生成层 ---

  

  generateKeyPair(): { privateKey: bigint; publicKey: ECPoint } {

    const d = generatePrivateKey(); // CSPRNG 生成

    const pub = scalarMultiply(d, new ECPoint(G.x, G.y), 0n, SECP256K1.p);

    return { privateKey: d, publicKey: pub };

  }

  

  /**

   * 公钥压缩：65 字节 → 33 字节

   */

  compressPublicKey(pubKey: ECPoint): Uint8Array {

    const isEven = (pubKey.y! % 2n) === 0n;

    const prefix = isEven ? 0x02 : 0x03;

    const bytes = new Uint8Array(33);

    bytes[0] = prefix;

    // ... 将 x 写入后 32 字节

    return bytes;

  }

  

  // --- 3. 签名层 ---

  

  sign(privateKey: bigint, message: string): { r: bigint; s: bigint } {

    return ecdsaSign(privateKey, message); // 复用 2.5 节实现

  }

  

  verify(

    publicKey: ECPoint,

    message: string,

    signature: { r: bigint; s: bigint },

  ): boolean {

    return ecdsaVerify(publicKey, message, signature); // 复用 2.5 节实现

  }

  

  /**

   * 检测签名可锻性（malleability）

   * 如果 s > n/2，攻击者可用 n-s 构造等价但不同的签名

   */

  isSignatureMalleable(signature: { r: bigint; s: bigint }): boolean {

    return signature.s > SECP256K1.n / 2n;

  }

  

  normalizeSignature(signature: { r: bigint; s: bigint }): { r: bigint; s: bigint } {

    if (this.isSignatureMalleable(signature)) {

      return { r: signature.r, s: SECP256K1.n - signature.s };

    }

    return signature;

  }

  

  // --- 4. Merkle 层 ---

  

  buildMerkleTree(txHashes: Uint8Array[]): MerkleTree {

    return new MerkleTree(txHashes); // 复用 2.7 节实现

  }

  

  // --- 私有辅助 ---

  

  private _flipRandomBit(s: string): string {

    const chars = s.split('');

    const pos = Math.floor(Math.random() * s.length);

    const bit = Math.floor(Math.random() * 8);

    const code = s.charCodeAt(pos);

    chars[pos] = String.fromCharCode(code ^ (1 << bit));

    return chars.join('');

  }

  

  private _hammingDistance(a: string, b: string): number {

    let dist = 0;

    for (let i = 0; i < a.length && i < b.length; i++) {

      const x = parseInt(a[i], 16);

      const y = parseInt(b[i], 16);

      let diff = x ^ y;

      while (diff) { dist++; diff &= diff - 1; }

    }

    return dist;

  }

}



// =====================================================

// 验证测试套件

// =====================================================



function runTests() {

  const kit = new CryptoToolkit();

  console.log("╔════════════════════════════════════════╗");

  console.log("║    密码学工具箱验证套件                ║");

  console.log("╚════════════════════════════════════════╝\n");

  

  // Test 1: 哈希雪崩效应

  console.log("[Test 1] 雪崩效应测试");

  const avalanche = kit.avalancheTest("Blockchain Crypto Toolkit v1.0", 10);

  console.log(`  平均翻转: ${avalanche.avgRate.toFixed(1)}% (目标: 50%)`);

  console.log(`  结果: ${avalanche.avgRate > 45 && avalanche.avgRate < 55 ? '✅ 通过' : '❌ 异常'}`);

  

  // Test 2: 密钥对生成

  console.log("\n[Test 2] 密钥对生成与验证");

  const { privateKey, publicKey } = kit.generateKeyPair();

  console.log(`  私钥位数: ${privateKey.toString(2).length} (目标: 256)`);

  console.log(`  公钥有效性: ${isValidCurvePoint(publicKey, 0n, 7n, SECP256K1.p) ? '✅ 在曲线上' : '❌ 无效'}`);

  

  // Test 3: ECDSA 全流程

  console.log("\n[Test 3] ECDSA 签名验证循环");

  const msg = "Transfer 1.0 BTC to 1A1z...";

  const sig = kit.sign(privateKey, msg);

  const valid = kit.verify(publicKey, msg, sig);

  console.log(`  原始消息: ${valid ? '✅ 验证通过' : '❌ 失败'}`);

  

  const tampered = kit.verify(publicKey, msg + "_tampered", sig);

  console.log(`  篡改消息: ${tampered ? '❌ 未检测出篡改' : '✅ 正确拒绝'}`);

  

  // Test 4: 签名规范化

  console.log("\n[Test 4] 签名可锻性检测");

  const highS = { r: sig.r, s: SECP256K1.n - sig.s };

  console.log(`  高 s 值: ${kit.isSignatureMalleable(highS) ? '✅ 检测到可锻性' : '❌ 未检测'}`);

  const normalized = kit.normalizeSignature(highS);

  console.log(`  规范化后: ${kit.isSignatureMalleable(normalized) ? '❌ 仍有问题' : '✅ 安全'}`);

  console.log(`  等价验证: ${kit.verify(publicKey, msg, normalized) ? '✅ 仍有效' : '❌ 被破坏'}`);

  

  // Test 5: Merkle 证明

  console.log("\n[Test 5] Merkle 树构建与验证");

  const txData = Array.from({ length: 8 }, (_, i) => `tx_${i}_data`);

  const txHashes = txData.map(tx => {

    const hex = kit.sha256(tx);

    const bytes = new Uint8Array(32);

    for (let j = 0; j < 32; j++) bytes[j] = parseInt(hex.slice(j * 2, j * 2 + 2), 16);

    return bytes;

  });

  

  const tree = kit.buildMerkleTree(txHashes);

  const root = tree.getRoot();

  if (root) {

    console.log(`  树根: ${Array.from(root).slice(0, 4).map(b => b.toString(16).padStart(2, '0')).join('')}...`);

    const proof = tree.getProof(3);

    const verified = verifyMerkleProof(txHashes[3], proof, root, 3);

    console.log(`  证明大小: ${proof.length} 个哈希 × 32 字节 =${proof.length * 32} 字节`);

    console.log(`  验证结果: ${verified ? '✅ 通过' : '❌ 失败'}`);

  }

  

  console.log("\n╔════════════════════════════════════════╗");

  console.log("║    全部测试完成                       ║");

  console.log("╚════════════════════════════════════════╝");

}



// 执行测试

runTests();