Web Bot Auth

// ==================== Configure region ====================
// Get configuration for key directory
const KEY_DIRECTORY_CONFIG = {
  // Whether to enable cache (enabled by default)
  enableCache: true,
  // Whether to follow the origin server's Cache-Control header (follow by default)
  respectCacheControl: true,
  // Request timeout in ms (5s by default)
  timeout: 5000,
  // Default key directory path
  defaultPath: '/.well-known/http-message-signatures-directory'
};

// ==================== Constants ====================

// Media type for HTTP message signatures directory (RFC 9421)
const MEDIA_TYPE_DIRECTORY = 'application/http-message-signatures-directory+json';

// ==================== Edge Function Entry ====================

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

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

  try {
    // ALL paths need to verify signature
    const status = await verifySignature(request, event);
    
    if (status === 'valid') {
      // Signature valid, forward to origin server
      return;
    } else {
      // Deny unsigned or invalid signature requests
      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' }
      })
    );
  }
}

// ==================== Core Logic of Signature Verification ====================

/**
 * Verify the request signature
 * @param {Request} request - request object
 * @returns {Promise<string>} Verification status: 'valid' | 'neutral' | 'invalid: <reason>'
 */
async function verifySignature(request, event) {
  try {
    // No signature header, return 'neutral'
    if (!request.headers.has('Signature')) {
      return 'neutral';
    }

    // Get the signed request header
    const signature = request.headers.get('Signature');
    const signatureInput = request.headers.get('Signature-Input');
    
    if (!signature || !signatureInput) {
      return 'invalid: Missing signature headers';
    }

    // Parse the Signature-Input request header
    const parsedSignatureInput = parseSignatureInput(signatureInput);
    if (!!parsedSignatureInput.error) {
      return `invalid: ${parsedSignatureInput.error}`;
    }

    // Parse the Signature request header
    const parsedSignature = parseSignature(signature, parsedSignatureInput.signatureId);
    if (!!parsedSignature.error) {
      return `invalid: ${parsedSignature.error}`;
    };
    const signatureBytes = parsedSignature.bytes;
    
    // Verify parameters
    const signatureParamsValidation = validateSignatureParams(parsedSignatureInput.params);
    if (!!signatureParamsValidation.error) {
      return `invalid: ${signatureParamsValidation.error}`;
    }
    
    // Get key directory URL
    const keyDirectoryUrlResult = getKeyDirectoryUrl(request);
    if (keyDirectoryUrlResult.error) {
      return `invalid: ${keyDirectoryUrlResult.error}`;
    }
    const keyDirectoryUrl = keyDirectoryUrlResult.url;
    
    // Get key directory data, import expected keyid to verify consistency
    const keyDirectoryResult = await fetchKeyDirectory(keyDirectoryUrl, event, parsedSignatureInput.params.keyid);
    if (keyDirectoryResult.error) {
      return `invalid: ${keyDirectoryResult.error}`;
    }
    const keyDirectory = keyDirectoryResult.directory;
    const verifiedKeyId = keyDirectoryResult.verifiedKeyId;
    
    // Search for public key (use verified keyid)
    const jwk = findPublicKey(keyDirectory.keys, verifiedKeyId);
    if (!jwk) {
      return `invalid: Public key not found for keyid: ${verifiedKeyId}`;
    }

    // Build the signature base string
    const signatureBase = buildSignatureBase(request, parsedSignatureInput.components, parsedSignatureInput.signatureParams);
    console.log(`[verifySignature] signatureBase: ${signatureBase}`);
    
    // Verify the Ed25519 signature
    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}`;
  }
}

/**
 * Extract key directory URL from request header
 * @param {Request} request - request object
 * @returns {{ error?: string; url?: string }} parsing result
 */
function getKeyDirectoryUrl(request) {
  try {
    const signatureAgent = request.headers.get('Signature-Agent');
    if (!signatureAgent) {
      return { error: 'Missing Signature-Agent header' };
    }
    
    // The value must be surrounded by double quotes
    if (!signatureAgent.startsWith('"') || !signatureAgent.endsWith('"')) {
      return { error: 'Signature-Agent header value must be enclosed in double quotes' };
    }
    
    // Remove double quotes
    const urlValue = signatureAgent.slice(1, -1);
    
    // must be HTTPS protocol
    if (!urlValue.startsWith('https://')) {
      return { error: 'Signature-Agent header value must be a valid HTTPS URL' };
    }
    
    // Verify URL format
    let url;
    try {
      url = new URL(urlValue);
    } catch (error) {
      return { error: `Invalid URL in Signature-Agent header: ${error.message}` };
    }
    
    // Ensure the URL points to the correct key directory path
    // If the URL does not end with the default path, add automatically
    if (!url.pathname.endsWith(KEY_DIRECTORY_CONFIG.defaultPath)) {
      // If the path is not the default path, check whether it is the domain name root path
      if (url.pathname === '/' || url.pathname === '') {
        url.pathname = KEY_DIRECTORY_CONFIG.defaultPath;
      } else {
        // Otherwise keep the original path, but log a warning
        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}` };
  }
}

/**
 Get key directory data, support cache
 * @param {string} url - Key directory URL
 * @param {any} event - Event object, used for cache write
 * @param {string|null} expectedKeyId - Expected key ID to verify response consistency (optional)
 * @returns {Promise<{ error?: string; directory?: { keys: Array }, verifiedKeyId?: string }>} Obtain result, including verified keyid
 */
async function fetchKeyDirectory(url, event, expectedKeyId = null) {
  try {
    const cache = caches.default;
    const cacheKey = new Request(url, { eo: { cacheKey: url } });
    
    // If enabled, read from cache first
    if (KEY_DIRECTORY_CONFIG.enableCache) {
      const cachedResponse = await cache.match(cacheKey);
      if (cachedResponse) {
        console.log(`[fetchKeyDirectory] Cache hit for ${url}`);
        try {
          // Verify whether the cache response contains the required Signature-Input header
          const cachedSignatureInput = cachedResponse.headers.get('Signature-Input');
          if (!cachedSignatureInput) {
            console.warn(`[fetchKeyDirectory] Cached response missing Signature-Input header, skipping cache`);
            // Skip cache and proceed with network retrieval
          } else {
            // Parse the keyid parameter in the response header
            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 {
                // Cache verified, return directory and verified keyid
                const directory = await cachedResponse.json();
                return { directory, verifiedKeyId: cachedKeyId };
              }
            }
          }
        } catch (error) {
          console.error(`[fetchKeyDirectory] Failed to process cached response: ${error.message}`);
          // Cache processing failure, proceed with network retrieval
        }
      }
    }
    
    // Construct request options and set timeout
    const fetchOptions = {
      redirect: 'manual',
      eo: {
        timeoutSetting: {
          connectTimeout: KEY_DIRECTORY_CONFIG.timeout,
          readTimeout: KEY_DIRECTORY_CONFIG.timeout,
          writeTimeout: KEY_DIRECTORY_CONFIG.timeout
        }
      }
    };
    
    // Initiate a request
    const response = await fetch(url, fetchOptions);
    
    if (!response.ok) {
      return { error: `HTTP ${response.status} fetching key directory from ${url}` };
    }
    
    // Verify 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}` };
    }
    
    // Verify the Signature-Input response header
    const responseSignatureInput = response.headers.get('Signature-Input');
    if (!responseSignatureInput) {
      return { error: 'Key directory response missing required Signature-Input header' };
    }
    
    // Parse the keyid parameter in the response header
    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' };
    }
    
    // If expected keyid is provided, verify consistency
    if (expectedKeyId !== null && responseKeyId !== expectedKeyId) {
      return { error: `Key directory response keyid mismatch: expected ${expectedKeyId}, got ${responseKeyId}` };
    }
    
    // Parse the response body
    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}` };
    }
    
    // Verify directory structure
    if (!directory || !Array.isArray(directory.keys)) {
      return { error: 'Invalid key directory structure: missing or invalid "keys" array' };
    }
    
    // If enabled and the response is cacheable, write cache
    if (KEY_DIRECTORY_CONFIG.enableCache) {
      // Check whether required to follow the origin server 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}` };
  }
}

/**
 // Parse the Signature-Input request header
 * @param {string} signatureInput - Signature-Input request header value
 * @returns {{ error?: string; signatureId: string; components: string[]; params: Record<string, string|number>; signatureParams: string;}} parsing result
 */
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;
    
    // Parse the component list
    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, ''));

    // Parse parameters
    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;
      }
    }

    // Reconstruct the parameter string
    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}` }
  }
}

/**
 Parse the Signature request header
 * @param {string} signature - Signature request header value
 * @param {string} signatureId - Signature ID
 * @returns {{ error?: string; bytes: Uint8Array }} parsing result
 */
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];
    // Switch base64url to standard base64
    signatureB64 = signatureB64.replace(/-/g, '+').replace(/_/g, '/');
    while (signatureB64.length % 4 !== 0) {
      signatureB64 += '=';
    }

    // decode to byte[]
    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}` };
  }
}

/**
 * Verify the signature parameters
 * @param {Record<string, string|number>} params - Signature parameters
 * @returns {{ error?: string }} verification result
 */
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 minutes clock skew tolerance
    
    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 hr maximum duration
    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}` };
  }
}

/**
 * Search for public key
 * @param {Array} keys - Array of public keys in the key directory
 * @param {string} keyid - Public key ID
 * @returns {{ kid: string; kty: string; crv: string; x: string; }|undefined} Public key
 */
function findPublicKey(keys, keyid) {
  for (const key of keys) {
    if (key.kid === keyid) {
      return key;
    }
  }
  return null;
}

/**
 * Build the signature base string
 * @param {Request} request - request object
 * @param {string[]} components - Component list
 * @param {string} signatureParams - Signature parameters
 * @returns {string} signature base 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 signature verification
 * @param {string} signatureBase - Signature base string
 * @param {Uint8Array} signature - Signature byte[]
 * @param {{ kid: string; kty: string; crv: string; x: string; }} jwk - Public key JWK
 * @returns {Promise<[boolean, string]>} verification result, [whether verified, error information]
 */
async function verifyEd25519(signatureBase, signature, jwk) {
  try {
    // Verify JWK format
    if (!jwk || jwk.kty !== 'OKP' || jwk.crv !== 'Ed25519') {
      return [false, 'Failed to verify Ed25519 signature - invalid JWK format'];
    }
    
    // Verify the signature length
    if (!signature || signature.length !== 64) {
      return [false, `Failed to verify Ed25519 signature - invalid signature length (${signature?.length || 'null'}), expected 64`];
    }

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

    // Encode message
    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 core logic validation
 * @param {Uint8Array} signature - 64-byte signature
 * @param {Uint8Array} message - Message
 * @param {Uint8Array} publicKey - 32-byte public key
 * @returns {Promise<boolean>} verification result
 */
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;
    
    // Parse public key point A
    const A = Point.fromBytes(publicKey);
    
    // Parse the R part of the signature
    const R = Point.fromBytes(signature.slice(0, 32));
    
    // Parse the S part of the signature
    const S = Ed25519.bytesToNumLE(signature.slice(32, 64));
    if (S >= Ed25519.N) throw new Error('S out of range');
    
    // Compute 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);
    
    // Verify the equation: [8][S]B = [8]R + [8][k]A
    // Equivalent to: ([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);
    
    // Calculate RkA - SB and clear the cofactor, check whether it is zero
    const diff = RkA.add(SB.negate()).clearCofactor();
    
    return diff.isZero();
  } catch (error) {
    console.error(`[Ed25519] ${error.stack}`);
    return false;
  }
}

// ==================== Helper functions ====================

/**
 * Extract component value
 * @param {Request} request - request object
 * @param {string} component - component
 * @returns {string} component value
 */
function extractComponent(request, component) {
  if (component.startsWith('@')) {
    // Derivative component
    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 header
    const value = request.headers.get(component.toLowerCase());
    return value || '';
  }
}

/**
 * Base64URL decode
 * @param {string} str - Base64URL encoded string
 * @returns {Uint8Array} Decoded byte[]
 */
function base64UrlDecode(str) {
  // Switch base64url to standard base64
  let base64 = str.replace(/-/g, '+').replace(/_/g, '/');
  const padding = base64.length % 4;
  if (padding) {
    base64 += '='.repeat(4 - padding);
  }

  // Decode
  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 hash
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);
}

// Concatenate byte[]
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;
}

// ==================== Auxiliary class ====================

// Ed25519 utility class - encapsulates all curve parameters and mathematical functions
class Ed25519 {
  // Ed25519 curve parameters (static property)
  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);

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

  // Modular inverse
  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);
  }

  // Convert bytes to large integer (little endian)
  static bytesToNumLE(bytes) {
    let result = 0n;
    for (let i = 0; i < bytes.length; i++) {
      result += BigInt(bytes[i]) << (8n * BigInt(i));
    }
    return result;
  }

  // Convert large integer to bytes (little endian)
  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;
  }

  // Compute (p+3)/8 power
  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 };
  }

  // square root calculation
  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 };
  }
}

// Extend the coordinate point class
class Point {
  constructor(X, Y, Z, T) {
    this.X = X;
    this.Y = Y;
    this.Z = Z;
    this.T = T;
  }

  // decode from byte
  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));
  }

  // Point addition
  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);
  }

  // Point multiplication
  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);
  }

  // scalar multiplication
  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()
  negate() {
    return new Point(Ed25519.mod(-this.X), this.Y, this.Z, Ed25519.mod(-this.T));
  }

  // determine whether it is zero
  isZero() {
    return this.X === 0n && this.Y === this.Z;
  }

  clearCofactor()
  clearCofactor() {
    return this.double().double().double();
  }

  // convert to byte
  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;
  }

  // Base point (inert initialization)
  static get BASE() {
    if (!this._BASE) {
      this._BASE = new Point(Ed25519.Gx, Ed25519.Gy, 1n, Ed25519.mod(Ed25519.Gx * Ed25519.Gy));
    }
    return this._BASE;
  }

  // Zero point (inert initialization)
  static get ZERO() {
    if (!this._ZERO) {
      this._ZERO = new Point(0n, 1n, 1n, 0n);
    }
    return this._ZERO;
  }
}