// ==================== 配置区域 ====================
// 密钥目录获取配置
const KEY_DIRECTORY_CONFIG = {
  // 是否启用缓存（默认启用）
  enableCache: true,
  // 是否遵循源站的 Cache-Control 头（默认遵循）
  respectCacheControl: true,
  // 请求超时时间，单位：毫秒（默认5秒）
  timeout: 5000,
  // 默认的密钥目录路径
  defaultPath: '/.well-known/http-message-signatures-directory'
};

// ==================== 常量 ====================

// HTTP 消息签名目录的媒体类型（RFC 9421）
const MEDIA_TYPE_DIRECTORY = 'application/http-message-signatures-directory+json';

// ==================== 边缘函数入口 ====================

addEventListener('fetch', (event) => {
  handleRequest(event);
});

async function handleRequest(event) {  
  const request = event.request;

  try {
    // 所有路径均需要进行签名验证
    const status = await verifySignature(request, event);
    
    if (status === 'valid') {
      // 签名有效，转发到源站
      return;
    } else {
      // 拒绝无签名或无效签名的请求
      const errorMessage = status === 'neutral' 
        ? 'Missing signature headers' 
        : status.replace('invalid: ', '');
      
      return event.respondWith(
        new Response(JSON.stringify({
          error: 'authentication_failed',
          message: errorMessage,
          timestamp: new Date().toISOString()
        }), {
          status: 401,
          headers: {
            'Content-Type': 'application/json',
            'Cache-Control': 'no-cache, no-store, must-revalidate'
          }
        })
      );
    }
  } catch (error) {
    console.error(`[handleRequest] ${error.stack}`);

    return event.respondWith(
      new Response(JSON.stringify({
        error: 'internal_server_error',
        message: error.message || 'An internal error occurred',
        timestamp: new Date().toISOString()
      }), {
        status: 500,
        headers: { 'Content-Type': 'application/json' }
      })
    );
  }
}

// ==================== 签名验证核心逻辑 ====================

/**
 * 验证请求签名
 * @param {Request} request - 请求对象
 * @returns {Promise<string>} 验证状态: 'valid' | 'neutral' | 'invalid: <reason>'
 */
async function verifySignature(request, event) {
  try {
    // 无签名头，返回 'neutral'
    if (!request.headers.has('Signature')) {
      return 'neutral';
    }

    // 获取签名请求头
    const signature = request.headers.get('Signature');
    const signatureInput = request.headers.get('Signature-Input');
    
    if (!signature || !signatureInput) {
      return 'invalid: Missing signature headers';
    }

    // 解析 Signature-Input 请求头
    const parsedSignatureInput = parseSignatureInput(signatureInput);
    if (!!parsedSignatureInput.error) {
      return `invalid: ${parsedSignatureInput.error}`;
    }

    // 解析 Signature 请求头
    const parsedSignature = parseSignature(signature, parsedSignatureInput.signatureId);
    if (!!parsedSignature.error) {
      return `invalid: ${parsedSignature.error}`;
    };
    const signatureBytes = parsedSignature.bytes;
    
    // 验证参数
    const signatureParamsValidation = validateSignatureParams(parsedSignatureInput.params);
    if (!!signatureParamsValidation.error) {
      return `invalid: ${signatureParamsValidation.error}`;
    }
    
    // 获取密钥目录 URL
    const keyDirectoryUrlResult = getKeyDirectoryUrl(request);
    if (keyDirectoryUrlResult.error) {
      return `invalid: ${keyDirectoryUrlResult.error}`;
    }
    const keyDirectoryUrl = keyDirectoryUrlResult.url;
    
    // 获取密钥目录数据，传入预期 keyid 进行一致性验证
    const keyDirectoryResult = await fetchKeyDirectory(keyDirectoryUrl, event, parsedSignatureInput.params.keyid);
    if (keyDirectoryResult.error) {
      return `invalid: ${keyDirectoryResult.error}`;
    }
    const keyDirectory = keyDirectoryResult.directory;
    const verifiedKeyId = keyDirectoryResult.verifiedKeyId;
    
    // 查找公钥（使用已验证的 keyid）
    const jwk = findPublicKey(keyDirectory.keys, verifiedKeyId);
    if (!jwk) {
      return `invalid: Public key not found for keyid: ${verifiedKeyId}`;
    }

    // 构建签名基础字符串
    const signatureBase = buildSignatureBase(request, parsedSignatureInput.components, parsedSignatureInput.signatureParams);
    console.log(`[verifySignature] signatureBase: ${signatureBase}`);
    
    // 验证 Ed25519 签名
    const [isValid, reason] = await verifyEd25519(signatureBase, signatureBytes, jwk);
    
    if (isValid) {
      return 'valid';
    } else {
      return !!reason ? `invalid: ${reason}` : 'invalid: Signature verification failed';
    }
  } catch (error) {
    console.error(`[verifySignature] ${error.stack}`);

    return `invalid: ${error.message}`;
  }
}

/**
 * 从请求头中提取密钥目录URL
 * @param {Request} request - 请求对象
 * @returns {{ error?: string; url?: string }} 解析结果
 */
function getKeyDirectoryUrl(request) {
  try {
    const signatureAgent = request.headers.get('Signature-Agent');
    if (!signatureAgent) {
      return { error: 'Missing Signature-Agent header' };
    }
    
    // 值必须用双引号包围
    if (!signatureAgent.startsWith('"') || !signatureAgent.endsWith('"')) {
      return { error: 'Signature-Agent header value must be enclosed in double quotes' };
    }
    
    // 去除双引号
    const urlValue = signatureAgent.slice(1, -1);
    
    // 必须是 HTTPS 协议
    if (!urlValue.startsWith('https://')) {
      return { error: 'Signature-Agent header value must be a valid HTTPS URL' };
    }
    
    // 验证URL格式
    let url;
    try {
      url = new URL(urlValue);
    } catch (error) {
      return { error: `Invalid URL in Signature-Agent header: ${error.message}` };
    }
    
    // 确保 URL 指向正确的密钥目录路径
    // 如果 URL 不以默认路径结尾，自动添加
    if (!url.pathname.endsWith(KEY_DIRECTORY_CONFIG.defaultPath)) {
      // 如果路径不是默认路径，检查是否是域名根路径
      if (url.pathname === '/' || url.pathname === '') {
        url.pathname = KEY_DIRECTORY_CONFIG.defaultPath;
      } else {
        // 否则保持原始路径，但记录警告
        console.warn(`[getKeyDirectoryUrl] URL path may not be standard key directory: ${url.pathname}`);
      }
    }
    
    return { url: url.toString() };
  } catch (error) {
    console.error(`[getKeyDirectoryUrl] ${error.stack}`);
    return { error: `Failed to extract key directory URL: ${error.message}` };
  }
}

/**
 * 获取密钥目录数据，支持缓存
 * @param {string} url - 密钥目录URL
 * @param {any} event - 事件对象，用于缓存写入
 * @param {string|null} expectedKeyId - 预期的keyid，用于验证响应一致性（可选）
 * @returns {Promise<{ error?: string; directory?: { keys: Array }, verifiedKeyId?: string }>} 获取结果，包含已验证的keyid
 */
async function fetchKeyDirectory(url, event, expectedKeyId = null) {
  try {
    const cache = caches.default;
    const cacheKey = new Request(url, { eo: { cacheKey: url } });
    
    // 如果启用缓存，先尝试从缓存读取
    if (KEY_DIRECTORY_CONFIG.enableCache) {
      const cachedResponse = await cache.match(cacheKey);
      if (cachedResponse) {
        console.log(`[fetchKeyDirectory] Cache hit for ${url}`);
        try {
          // 验证缓存响应是否包含必要的 Signature-Input 头
          const cachedSignatureInput = cachedResponse.headers.get('Signature-Input');
          if (!cachedSignatureInput) {
            console.warn(`[fetchKeyDirectory] Cached response missing Signature-Input header, skipping cache`);
            // 跳过缓存，继续网络获取
          } else {
            // 解析响应头中的 keyid 参数
            const parsedCachedInput = parseSignatureInput(cachedSignatureInput);
            if (parsedCachedInput.error) {
              console.warn(`[fetchKeyDirectory] Failed to parse cached Signature-Input header: ${parsedCachedInput.error}, skipping cache`);
            } else {
              const cachedKeyId = parsedCachedInput.params.keyid;
              if (!cachedKeyId) {
                console.warn(`[fetchKeyDirectory] Cached response missing keyid parameter, skipping cache`);
              } else if (expectedKeyId !== null && cachedKeyId !== expectedKeyId) {
                console.warn(`[fetchKeyDirectory] Cached response keyid mismatch: expected ${expectedKeyId}, got ${cachedKeyId}, skipping cache`);
              } else {
                // 缓存验证通过，返回目录和已验证的 keyid
                const directory = await cachedResponse.json();
                return { directory, verifiedKeyId: cachedKeyId };
              }
            }
          }
        } catch (error) {
          console.error(`[fetchKeyDirectory] Failed to process cached response: ${error.message}`);
          // 缓存处理失败，继续网络获取
        }
      }
    }
    
    // 构造请求选项，设置超时
    const fetchOptions = {
      redirect: 'manual',
      eo: {
        timeoutSetting: {
          connectTimeout: KEY_DIRECTORY_CONFIG.timeout,
          readTimeout: KEY_DIRECTORY_CONFIG.timeout,
          writeTimeout: KEY_DIRECTORY_CONFIG.timeout
        }
      }
    };
    
    // 发起请求
    const response = await fetch(url, fetchOptions);
    
    if (!response.ok) {
      return { error: `HTTP ${response.status} fetching key directory from ${url}` };
    }
    
    // 验证 Content-Type
    const contentType = response.headers.get('Content-Type');
    if (!contentType || !contentType.includes(MEDIA_TYPE_DIRECTORY)) {
      return { error: `Invalid Content-Type: ${contentType}, expected ${MEDIA_TYPE_DIRECTORY}` };
    }
    
    // 验证 Signature-Input 响应头
    const responseSignatureInput = response.headers.get('Signature-Input');
    if (!responseSignatureInput) {
      return { error: 'Key directory response missing required Signature-Input header' };
    }
    
    // 解析响应头中的 keyid 参数
    const parsedResponseInput = parseSignatureInput(responseSignatureInput);
    if (parsedResponseInput.error) {
      return { error: `Failed to parse response Signature-Input header: ${parsedResponseInput.error}` };
    }
    
    const responseKeyId = parsedResponseInput.params.keyid;
    if (!responseKeyId) {
      return { error: 'Key directory response Signature-Input missing keyid parameter' };
    }
    
    // 如果提供了预期 keyid，验证一致性
    if (expectedKeyId !== null && responseKeyId !== expectedKeyId) {
      return { error: `Key directory response keyid mismatch: expected ${expectedKeyId}, got ${responseKeyId}` };
    }
    
    // 解析响应体
    let directory;
    try {
      if (KEY_DIRECTORY_CONFIG.enableCache) {
        directory = await response.clone().json();
      } else {
        directory = await response.json();
      }
    } catch (error) {
      return { error: `Failed to parse key directory response as JSON: ${error.message}` };
    }
    
    // 验证目录结构
    if (!directory || !Array.isArray(directory.keys)) {
      return { error: 'Invalid key directory structure: missing or invalid "keys" array' };
    }
    
    // 如果启用缓存且响应可缓存，写入缓存
    if (KEY_DIRECTORY_CONFIG.enableCache) {
      // 检查是否需要遵循源站 Cache-Control
      let shouldCache = true;
      if (KEY_DIRECTORY_CONFIG.respectCacheControl) {
        const cacheControl = response.headers.get('Cache-Control');
        if (cacheControl && cacheControl.includes('no-store')) {
          shouldCache = false;
        }
      }
      
      if (shouldCache) {
        event.waitUntil(cache.put(cacheKey, response.clone()));
        console.log(`[fetchKeyDirectory] Cached response for ${url}`);
      }
    }
    
    return { directory, verifiedKeyId: responseKeyId };
  } catch (error) {
    console.error(`[fetchKeyDirectory] Error fetching ${url}:`, error);
    return { error: `Failed to fetch key directory: ${error.message}` };
  }
}

/**
 * 解析 Signature-Input 请求头
 * @param {string} signatureInput - Signature-Input 请求头值
 * @returns {{ error?: string; signatureId: string; components: string[]; params: Record<string, string|number>; signatureParams: string;}} 解析结果
 */
function parseSignatureInput(signatureInput) {
  try {
    const match = signatureInput.match(/^(\\w+)=(.+)$/);
    if (!match) {
      return { error: 'Failed to parse Signature-Input - invalid Signature-Input format' };
    }

    const [, signatureId, paramString] = match;
    
    // 解析组件列表
    const componentsMatch = paramString.match(/^\\(([^)]+)\\)/);
    if (!componentsMatch) {
      return { error: 'Failed to parse Signature-Input - missing components list' };
    }

    const componentsStr = componentsMatch[1];
    const components = componentsStr.split(/\\s+/).map(comp => comp.replace(/"/g, ''));

    // 解析参数
    const paramsStr = paramString.substring(componentsMatch[0].length);
    const params = {};
    const paramRegex = /;(\\w+)=([^;]+)/g;
    let paramMatch;

    while ((paramMatch = paramRegex.exec(paramsStr)) !== null) {
      const [, key, value] = paramMatch;
      
      if (value.startsWith('"') && value.endsWith('"')) {
        params[key] = value.slice(1, -1);
      } else if (/^\\d+$/.test(value)) {
        params[key] = parseInt(value, 10);
      } else {
        params[key] = value;
      }
    }

    // 重构参数字符串
    const signatureParams = `(${components.map(c => `"${c}"`).join(' ')})` +
      Object.entries(params).map(([key, value]) => {
        return typeof value === 'string' ? `;${key}="${value}"` : `;${key}=${value}`;
      }).join('');

    return { signatureId, components, params, signatureParams };
  } catch (error) {
    console.error(`[parseSignatureInput] ${error.stack}`);

    return { error: `Failed to parse Signature-Input: ${error.message}` }
  }
}

/**
 * 解析 Signature 请求头
 * @param {string} signature - Signature 请求头值
 * @param {string} signatureId - 签名 ID
 * @returns {{ error?: string; bytes: Uint8Array }} 解析结果
 */
function parseSignature(signature, signatureId) {
  try {
    const pattern = new RegExp(`${signatureId}=:([A-Za-z0-9+/=_-]+):`);
    const match = signature.match(pattern);

    if (!match) {
      return { error: `Failed to parse Signature - signature for ${signatureId} not found` };
    }

    let signatureB64 = match[1];
    // 转换 base64url 到标准 base64
    signatureB64 = signatureB64.replace(/-/g, '+').replace(/_/g, '/');
    while (signatureB64.length % 4 !== 0) {
      signatureB64 += '=';
    }

    // 解码为字节数组
    const binaryString = atob(signatureB64);
    const bytes = new Uint8Array(binaryString.length);
    for (let i = 0; i < binaryString.length; i++) {
      bytes[i] = binaryString.charCodeAt(i);
    }

    return { bytes };
  } catch (error) {
    console.error(`[parseSignature] ${error.stack}`);

    return { error: `Failed to parse Signature: ${error.message}` };
  }
}

/**
 * 验证签名参数
 * @param {Record<string, string|number>} params - 签名参数
 * @returns {{ error?: string }} 验证结果
 */
function validateSignatureParams(params) {
  console.log(`[validateSignatureParams] ${JSON.stringify(params)}`);
  
  try {
    if (!params.keyid) {
      return { error: 'Failed to validate signature parameters - missing keyid parameter' };
    }
    
    if (!params.alg || params.alg !== 'ed25519') {
      return { error: 'Failed to validate signature parameters - invalid or missing algorithm parameter' };
    }
    
    if (!params.tag || params.tag !== 'web-bot-auth') {
      return { error: 'Failed to validate signature parameters - invalid or missing tag parameter' };
    }
    
    if (!params.created || !params.expires) {
      return { error: 'Failed to validate signature parameters - missing created or expires parameter' };
    }

    const now = Math.floor(Date.now() / 1000);
    const clockSkew = 300; // 5 分钟时钟偏移容忍度
    
    if (params.created > now + clockSkew) {
      return { error: 'Failed to validate signature parameters - created time is in the future' };
    }

    if (params.expires < now - clockSkew) {
      return { error: 'Failed to validate signature parameters - signature has expired' };
    }

    const maxAge = 3600; // 1 小时最大有效期
    if (params.expires - params.created > maxAge) {
      return { error: 'Failed to validate signature parameters - signature validity period too long' };
    }

    return {};
  } catch (error) {
    console.error(`[validateSignatureParams] ${error.stack}`);

    return { error: `Failed to validate signature parameters - ${error.message}` };
  }
}

/**
 * 查找公钥
 * @param {Array} keys - 密钥目录中的公钥数组
 * @param {string} keyid - 公钥 ID
 * @returns {{ kid: string; kty: string; crv: string; x: string; }|undefined} 公钥
 */
function findPublicKey(keys, keyid) {
  for (const key of keys) {
    if (key.kid === keyid) {
      return key;
    }
  }
  return null;
}

/**
 * 构建签名基础字符串
 * @param {Request} request - 请求对象
 * @param {string[]} components - 组件列表
 * @param {string} signatureParams - 签名参数
 * @returns {string} 签名基础字符串
 */
function buildSignatureBase(request, components, signatureParams) {
  const lines = [];
  
  for (const component of components) {
    const value = extractComponent(request, component);
    lines.push(`"${component.toLowerCase()}": ${value}`);
  }
  
  lines.push(`"@signature-params": ${signatureParams}`);
  
  return lines.join('\\n');
}

/**
 * Ed25519 签名验证
 * @param {string} signatureBase - 签名基础字符串
 * @param {Uint8Array} signature - 签名字节数组
 * @param {{ kid: string; kty: string; crv: string; x: string; }} jwk - 公钥 JWK
 * @returns {Promise<[boolean, string]>} 验证结果，[是否验证通过, 错误信息]
 */
async function verifyEd25519(signatureBase, signature, jwk) {
  try {
    // 验证 JWK 格式
    if (!jwk || jwk.kty !== 'OKP' || jwk.crv !== 'Ed25519') {
      return [false, 'Failed to verify Ed25519 signature - invalid JWK format'];
    }
    
    // 验证签名长度
    if (!signature || signature.length !== 64) {
      return [false, `Failed to verify Ed25519 signature - invalid signature length (${signature?.length || 'null'}), expected 64`];
    }

    // 解码公钥
    const publicKeyBytes = base64UrlDecode(jwk.x);
    if (publicKeyBytes.length !== 32) {
      return [false, `Failed to verify Ed25519 signature - invalid public key length (${publicKeyBytes.length}), expected 32`];
    }

    // 编码消息
    const message = new TextEncoder().encode(signatureBase);

    const result = await _verifyEd25519(signature, message, publicKeyBytes);

    return [result];
  } catch (error) {
    console.error(`[verifyEd25519] ${error.stack}`);
    return [false, `Failed to verify Ed25519 signature - ${error.message}`];
  }
}

/**
 * Ed25519 校验核心逻辑
 * @param {Uint8Array} signature - 64 字节签名
 * @param {Uint8Array} message - 消息
 * @param {Uint8Array} publicKey - 32 字节公钥
 * @returns {Promise<boolean>} 验证结果
 */
async function _verifyEd25519(signature, message, publicKey) {
  if (signature.length !== 64) throw new Error('Signature must be 64 bytes');
  if (publicKey.length !== 32) throw new Error('Public key must be 32 bytes');

  try {
    const POINT_G = Point.BASE;
    
    // 解析公钥点 A
    const A = Point.fromBytes(publicKey);
    
    // 解析签名的 R 部分
    const R = Point.fromBytes(signature.slice(0, 32));
    
    // 解析签名的 S 部分
    const S = Ed25519.bytesToNumLE(signature.slice(32, 64));
    if (S >= Ed25519.N) throw new Error('S out of range');
    
    // 计算 k = H(R || A || M)
    const hashable = concatBytes(R.toBytes(), A.toBytes(), message);
    const hashed = await sha512(hashable);
    const k = Ed25519.mod(Ed25519.bytesToNumLE(hashed), Ed25519.N);
    
    // 验证等式: [8][S]B = [8]R + [8][k]A
    // 等价于: ([8]R + [8][k]A) - [8][S]B = 0
    const SB = POINT_G.multiply(S);
    const kA = A.multiply(k);
    const RkA = R.add(kA);
    
    // 计算 RkA - SB 并清除辅因子，检查是否为零点
    const diff = RkA.add(SB.negate()).clearCofactor();
    
    return diff.isZero();
  } catch (error) {
    console.error(`[Ed25519] ${error.stack}`);
    return false;
  }
}

// ==================== 辅助函数 ====================

/**
 * 提取组件值
 * @param {Request} request - 请求对象
 * @param {string} component - 组件
 * @returns {string} 组件值
 */
function extractComponent(request, component) {
  if (component.startsWith('@')) {
    // 派生组件
    const url = new URL(request.url);
    
    switch (component) {
      case '@method':
        return request.method.toUpperCase();
      case '@authority':
        return url.host;
      case '@scheme':
        return url.protocol.slice(0, -1);
      case '@target-uri':
        return request.url;
      case '@request-target':
        return `${url.pathname}${url.search}`;
      case '@path':
        return url.pathname;
      case '@query':
        return url.search.slice(1);
      default:
        throw new Error(`Failed to extract component - component ${component} is not supported`);
    }
  } else {
    // HTTP 头部
    const value = request.headers.get(component.toLowerCase());
    return value || '';
  }
}

/**
 * Base64URL 解码
 * @param {string} str - Base64URL 编码的字符串
 * @returns {Uint8Array} 解码后的字节数组
 */
function base64UrlDecode(str) {
  // 转换 base64url 到标准 base64
  let base64 = str.replace(/-/g, '+').replace(/_/g, '/');
  const padding = base64.length % 4;
  if (padding) {
    base64 += '='.repeat(4 - padding);
  }

  // 解码
  const binaryString = atob(base64);
  const bytes = new Uint8Array(binaryString.length);
  for (let i = 0; i < binaryString.length; i++) {
    bytes[i] = binaryString.charCodeAt(i);
  }

  return bytes;
}

// SHA-512 哈希
async function sha512(message) {
  const msgBuffer = message instanceof Uint8Array ? message : new Uint8Array(message);
  const hashBuffer = await crypto.subtle.digest('SHA-512', msgBuffer);
  return new Uint8Array(hashBuffer);
}

// 拼接字节数组
function concatBytes(...arrays) {
  const totalLength = arrays.reduce((sum, arr) => sum + arr.length, 0);
  const result = new Uint8Array(totalLength);
  let offset = 0;
  for (const arr of arrays) {
    result.set(arr, offset);
    offset += arr.length;
  }
  return result;
}

// ==================== 辅助类 ====================

// Ed25519 工具类 - 封装所有曲线参数和数学函数
class Ed25519 {
  // Ed25519 曲线参数（静态属性）
  static P = BigInt('0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed');
  static N = BigInt('0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed');
  static Gx = BigInt('0x216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a');
  static Gy = BigInt('0x6666666666666666666666666666666666666666666666666666666666666658');
  static D = BigInt('0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3');
  static RM1 = BigInt('0x2b8324804fc1df0b2b4d00993dfbd7a72f431806ad2fe478c4ee1b274a0ea0b0');
  static B256 = BigInt(2) ** BigInt(256);

  // 模运算
  static mod(a, b = Ed25519.P) {
    const r = a % b;
    return r >= 0n ? r : b + r;
  }

  // 模逆
  static invert(num, md = Ed25519.P) {
    if (num === 0n || md <= 0n) throw new Error('Invalid inverse');
    let a = Ed25519.mod(num, md), b = md, x = 0n, y = 1n, u = 1n, v = 0n;
    while (a !== 0n) {
      const q = b / a, r = b % a;
      const m = x - u * q, n = y - v * q;
      b = a, a = r, x = u, y = v, u = m, v = n;
    }
    if (b !== 1n) throw new Error('No inverse');
    return Ed25519.mod(x, md);
  }

  // 字节转大整数（小端序）
  static bytesToNumLE(bytes) {
    let result = 0n;
    for (let i = 0; i < bytes.length; i++) {
      result += BigInt(bytes[i]) << (8n * BigInt(i));
    }
    return result;
  }

  // 大整数转字节（小端序）
  static numTo32bLE(num) {
    const bytes = new Uint8Array(32);
    let n = num;
    for (let i = 0; i < 32; i++) {
      bytes[i] = Number(n & 0xFFn);
      n >>= 8n;
    }
    return bytes;
  }

  // pow2(x, k) = x^(2^k) mod P
  static pow2(x, power) {
    let r = x;
    while (power-- > 0n) {
      r = (r * r) % Ed25519.P;
    }
    return r;
  }

  // 计算 (p+3)/8 次幂
  static pow_2_252_3(x) {
    const x2 = (x * x) % Ed25519.P;
    const b2 = (x2 * x) % Ed25519.P;
    const b4 = (Ed25519.pow2(b2, 2n) * b2) % Ed25519.P;
    const b5 = (Ed25519.pow2(b4, 1n) * x) % Ed25519.P;
    const b10 = (Ed25519.pow2(b5, 5n) * b5) % Ed25519.P;
    const b20 = (Ed25519.pow2(b10, 10n) * b10) % Ed25519.P;
    const b40 = (Ed25519.pow2(b20, 20n) * b20) % Ed25519.P;
    const b80 = (Ed25519.pow2(b40, 40n) * b40) % Ed25519.P;
    const b160 = (Ed25519.pow2(b80, 80n) * b80) % Ed25519.P;
    const b240 = (Ed25519.pow2(b160, 80n) * b80) % Ed25519.P;
    const b250 = (Ed25519.pow2(b240, 10n) * b10) % Ed25519.P;
    const pow_p_5_8 = (Ed25519.pow2(b250, 2n) * x) % Ed25519.P;
    return { pow_p_5_8, b2 };
  }

  // 平方根计算
  static uvRatio(u, v) {
    const v3 = Ed25519.mod(v * v * v);
    const v7 = Ed25519.mod(v3 * v3 * v);
    const pow = Ed25519.pow_2_252_3(u * v7).pow_p_5_8;
    let x = Ed25519.mod(u * v3 * pow);
    const vx2 = Ed25519.mod(v * x * x);
    const root1 = x;
    const root2 = Ed25519.mod(x * Ed25519.RM1);
    const useRoot1 = vx2 === u;
    const useRoot2 = vx2 === Ed25519.mod(-u);
    const noRoot = vx2 === Ed25519.mod(-u * Ed25519.RM1);
    if (useRoot1) x = root1;
    if (useRoot2 || noRoot) x = root2;
    if ((Ed25519.mod(x) & 1n) === 1n) x = Ed25519.mod(-x);
    return { isValid: useRoot1 || useRoot2, value: x };
  }
}

// 扩展坐标点类
class Point {
  constructor(X, Y, Z, T) {
    this.X = X;
    this.Y = Y;
    this.Z = Z;
    this.T = T;
  }

  // 从字节解码
  static fromBytes(bytes) {
    if (bytes.length !== 32) throw new Error('Invalid point bytes length');
    
    const normed = new Uint8Array(bytes);
    const lastByte = bytes[31];
    normed[31] = lastByte & ~0x80;
    
    const y = Ed25519.bytesToNumLE(normed);
    if (y >= Ed25519.P) throw new Error('Y coordinate out of range');
    
    const y2 = Ed25519.mod(y * y);
    const u = Ed25519.mod(y2 - 1n);
    const v = Ed25519.mod(Ed25519.D * y2 + 1n);
    
    let { isValid, value: x } = Ed25519.uvRatio(u, v);
    if (!isValid) throw new Error('Invalid point: y is not a square root');
    
    const isXOdd = (x & 1n) === 1n;
    const isLastByteOdd = (lastByte & 0x80) !== 0;
    if (isLastByteOdd !== isXOdd) x = Ed25519.mod(-x);
    
    return new Point(x, y, 1n, Ed25519.mod(x * y));
  }

  // 点加法
  add(other) {
    const A = Ed25519.mod(this.X * other.X);
    const B = Ed25519.mod(this.Y * other.Y);
    const C = Ed25519.mod(this.T * Ed25519.D * other.T);
    const D2 = Ed25519.mod(this.Z * other.Z);
    const E = Ed25519.mod((this.X + this.Y) * (other.X + other.Y) - A - B);
    const F = Ed25519.mod(D2 - C);
    const G = Ed25519.mod(D2 + C);
    const H = Ed25519.mod(B + A);
    const X3 = Ed25519.mod(E * F);
    const Y3 = Ed25519.mod(G * H);
    const T3 = Ed25519.mod(E * H);
    const Z3 = Ed25519.mod(F * G);
    return new Point(X3, Y3, Z3, T3);
  }

  // 点倍乘
  double() {
    const A = Ed25519.mod(this.X * this.X);
    const B = Ed25519.mod(this.Y * this.Y);
    const C = Ed25519.mod(2n * Ed25519.mod(this.Z * this.Z));
    const D = Ed25519.mod(-A);
    const E = Ed25519.mod((this.X + this.Y) * (this.X + this.Y) - A - B);
    const G = D + B;
    const F = G - C;
    const H = D - B;
    const X3 = Ed25519.mod(E * F);
    const Y3 = Ed25519.mod(G * H);
    const T3 = Ed25519.mod(E * H);
    const Z3 = Ed25519.mod(F * G);
    return new Point(X3, Y3, Z3, T3);
  }

  // 标量乘法
  multiply(scalar) {
    const POINT_ZERO = Point.ZERO;
    let p = POINT_ZERO;
    let d = this;
    let n = scalar;
    while (n > 0n) {
      if (n & 1n) p = p.add(d);
      d = d.double();
      n >>= 1n;
    }
    return p;
  }

  // 取负
  negate() {
    return new Point(Ed25519.mod(-this.X), this.Y, this.Z, Ed25519.mod(-this.T));
  }

  // 判断是否为零点
  isZero() {
    return this.X === 0n && this.Y === this.Z;
  }

  // 清除辅因子
  clearCofactor() {
    return this.double().double().double();
  }

  // 转换为字节
  toBytes() {
    const iz = Ed25519.invert(this.Z);
    const x = Ed25519.mod(this.X * iz);
    const y = Ed25519.mod(this.Y * iz);
    const bytes = Ed25519.numTo32bLE(y);
    bytes[31] |= (x & 1n) ? 0x80 : 0;
    return bytes;
  }

  // 基点（惰性初始化）
  static get BASE() {
    if (!this._BASE) {
      this._BASE = new Point(Ed25519.Gx, Ed25519.Gy, 1n, Ed25519.mod(Ed25519.Gx * Ed25519.Gy));
    }
    return this._BASE;
  }

  // 零点（惰性初始化）
  static get ZERO() {
    if (!this._ZERO) {
      this._ZERO = new Point(0n, 1n, 1n, 0n);
    }
    return this._ZERO;
  }
}