/*! noble-ed25519 - MIT License (c) 2019 Paul Miller (paulmillr.com) */
/**
 * 5KB JS implementation of ed25519 EdDSA signatures.
 * Compliant with RFC8032, FIPS 186-5 & ZIP215.
 * @module
 * @example
 * ```js
import * as ed from '@noble/ed25519';
(async () => {
  const secretKey = ed.utils.randomSecretKey();
  const message = Uint8Array.from([0xab, 0xbc, 0xcd, 0xde]);
  const pubKey = await ed.getPublicKeyAsync(secretKey); // Sync methods are also present
  const signature = await ed.signAsync(message, secretKey);
  const isValid = await ed.verifyAsync(signature, message, pubKey);
})();
```
 */
/**
 * Curve params. ed25519 is twisted edwards curve. Equation is −x² + y² = -a + dx²y².
 * * P = `2n**255n - 19n` // field over which calculations are done
 * * N = `2n**252n + 27742317777372353535851937790883648493n` // group order, amount of curve points
 * * h = 8 // cofactor
 * * a = `Fp.create(BigInt(-1))` // equation param
 * * d = -121665/121666 a.k.a. `Fp.neg(121665 * Fp.inv(121666))` // equation param
 * * Gx, Gy are coordinates of Generator / base point
 */
const ed25519_CURVE: EdwardsOpts = {
  p: 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffedn,
  n: 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3edn,
  h: 8n,
  a: 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffecn,
  d: 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3n,
  Gx: 0x216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51an,
  Gy: 0x6666666666666666666666666666666666666666666666666666666666666658n,
};
const { p: P, n: N, Gx, Gy, a: _a, d: _d, h } = ed25519_CURVE;
const L = 32; // field / group byte length
/** Alias to Uint8Array. */
export type Bytes = Uint8Array;
/** Hex-encoded string or Uint8Array. */
/** Edwards elliptic curve options. */
export type EdwardsOpts = Readonly<{
  p: bigint;
  n: bigint;
  h: bigint;
  a: bigint;
  d: bigint;
  Gx: bigint;
  Gy: bigint;
}>;

// Helpers and Precomputes sections are reused between libraries

// ## Helpers
// ----------
const captureTrace = (...args: Parameters<typeof Error.captureStackTrace>): void => {
  if ('captureStackTrace' in Error && typeof Error.captureStackTrace === 'function') {
    Error.captureStackTrace(...args);
  }
};
const err = (message = ''): never => {
  const e = new Error(message);
  captureTrace(e, err);
  throw e;
};
const isBig = (n: unknown): n is bigint => typeof n === 'bigint'; // is big integer
const isStr = (s: unknown): s is string => typeof s === 'string'; // is string
const isBytes = (a: unknown): a is Bytes =>
  a instanceof Uint8Array || (ArrayBuffer.isView(a) && a.constructor.name === 'Uint8Array');
/** Asserts something is Uint8Array. */
const abytes = (value: Bytes, length?: number, title: string = ''): Bytes => {
  const bytes = isBytes(value);
  const len = value?.length;
  const needsLen = length !== undefined;
  if (!bytes || (needsLen && len !== length)) {
    const prefix = title && `"${title}" `;
    const ofLen = needsLen ? ` of length ${length}` : '';
    const got = bytes ? `length=${len}` : `type=${typeof value}`;
    err(prefix + 'expected Uint8Array' + ofLen + ', got ' + got);
  }
  return value;
};
/** create Uint8Array */
const u8n = (len: number) => new Uint8Array(len);
const u8fr = (buf: ArrayLike<number>) => Uint8Array.from(buf);
const padh = (n: number | bigint, pad: number) => n.toString(16).padStart(pad, '0');
const bytesToHex = (b: Bytes): string =>
  Array.from(abytes(b))
    .map((e) => padh(e, 2))
    .join('');
const C = { _0: 48, _9: 57, A: 65, F: 70, a: 97, f: 102 } as const; // ASCII characters
const _ch = (ch: number): number | undefined => {
  if (ch >= C._0 && ch <= C._9) return ch - C._0; // '2' => 50-48
  if (ch >= C.A && ch <= C.F) return ch - (C.A - 10); // 'B' => 66-(65-10)
  if (ch >= C.a && ch <= C.f) return ch - (C.a - 10); // 'b' => 98-(97-10)
  return;
};
const hexToBytes = (hex: string): Bytes => {
  const e = 'hex invalid';
  if (!isStr(hex)) return err(e);
  const hl = hex.length;
  const al = hl / 2;
  if (hl % 2) return err(e);
  const array = u8n(al);
  for (let ai = 0, hi = 0; ai < al; ai++, hi += 2) {
    // treat each char as ASCII
    const n1 = _ch(hex.charCodeAt(hi)); // parse first char, multiply it by 16
    const n2 = _ch(hex.charCodeAt(hi + 1)); // parse second char
    if (n1 === undefined || n2 === undefined) return err(e);
    array[ai] = n1 * 16 + n2; // example: 'A9' => 10*16 + 9
  }
  return array;
};
declare const globalThis: Record<string, any> | undefined; // Typescript symbol present in browsers
const cr = () => globalThis?.crypto; // WebCrypto is available in all modern environments
const subtle = () => cr()?.subtle ?? err('crypto.subtle must be defined, consider polyfill');
// prettier-ignore
const concatBytes = (...arrs: Bytes[]): Bytes => {
  const r = u8n(arrs.reduce((sum, a) => sum + abytes(a).length, 0)); // create u8a of summed length
  let pad = 0; // walk through each array,
  arrs.forEach(a => { r.set(a, pad); pad += a.length; }); // ensure they have proper type
  return r;
};
/** WebCrypto OS-level CSPRNG (random number generator). Will throw when not available. */
const randomBytes = (len: number = L): Bytes => {
  const c = cr();
  return c.getRandomValues(u8n(len));
};
const big = BigInt;
const assertRange = (
  n: bigint,
  min: bigint,
  max: bigint,
  msg = 'bad number: out of range'
): bigint => (isBig(n) && min <= n && n < max ? n : err(msg));
/** modular division */
const M = (a: bigint, b: bigint = P): bigint => {
  const r = a % b;
  return r >= 0n ? r : b + r;
};
const P_MASK = (1n << 255n) - 1n;
const modP = (num: bigint): bigint => {
  // return M(num, P);
  if (num < 0n) err('negative coordinate');
  let r = (num >> 255n) * 19n + (num & P_MASK);
  r = (r >> 255n) * 19n + (r & P_MASK);
  return r % P;
};
const modN = (a: bigint) => M(a, N);
/** Modular inversion using euclidean GCD (non-CT). No negative exponent for now. */
// prettier-ignore
const invert = (num: bigint, md: bigint): bigint => {
  if (num === 0n || md <= 0n) err('no inverse n=' + num + ' mod=' + md);
  let a = M(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;
  }
  return b === 1n ? M(x, md) : err('no inverse'); // b is gcd at this point
};
const callHash = (name: string) => {
  // @ts-ignore
  const fn = hashes[name];
  if (typeof fn !== 'function') err('hashes.' + name + ' not set');
  return fn;
};
const hash = (msg: Bytes): Bytes => callHash('sha512')(msg);
const apoint = (p: unknown) => (p instanceof Point ? p : err('Point expected'));
/** Point in 2d xy affine coordinates. */
export type AffinePoint = {
  x: bigint;
  y: bigint;
};
// ## End of Helpers
// -----------------

const B256 = 2n ** 256n;
/** Point in XYZT extended coordinates. */
class Point {
  static BASE: Point;
  static ZERO: Point;
  readonly X: bigint;
  readonly Y: bigint;
  readonly Z: bigint;
  readonly T: bigint;
  constructor(X: bigint, Y: bigint, Z: bigint, T: bigint) {
    const max = B256;
    this.X = assertRange(X, 0n, max);
    this.Y = assertRange(Y, 0n, max);
    this.Z = assertRange(Z, 1n, max);
    this.T = assertRange(T, 0n, max);
    Object.freeze(this);
  }
  static CURVE(): EdwardsOpts {
    return ed25519_CURVE;
  }
  static fromAffine(p: AffinePoint): Point {
    return new Point(p.x, p.y, 1n, modP(p.x * p.y));
  }
  /** RFC8032 5.1.3: Uint8Array to Point. */
  static fromBytes(hex: Bytes, zip215 = false): Point {
    const d = _d;
    // Copy array to not mess it up.
    const normed = u8fr(abytes(hex, L));
    // adjust first LE byte = last BE byte
    const lastByte = hex[31];
    normed[31] = lastByte & ~0x80;
    const y = bytesToNumberLE(normed);
    // zip215=true:           0 <= y < 2^256
    // zip215=false, RFC8032: 0 <= y < 2^255-19
    const max = zip215 ? B256 : P;
    assertRange(y, 0n, max);

    const y2 = modP(y * y); // y²
    const u = M(y2 - 1n); // u=y²-1
    const v = modP(d * y2 + 1n); // v=dy²+1
    let { isValid, value: x } = uvRatio(u, v); // (uv³)(uv⁷)^(p-5)/8; square root
    if (!isValid) err('bad point: y not sqrt'); // not square root: bad point
    const isXOdd = (x & 1n) === 1n; // adjust sign of x coordinate
    const isLastByteOdd = (lastByte & 0x80) !== 0; // x_0, last bit
    if (!zip215 && x === 0n && isLastByteOdd) err('bad point: x==0, isLastByteOdd'); // x=0, x_0=1
    if (isLastByteOdd !== isXOdd) x = M(-x);
    return new Point(x, y, 1n, modP(x * y)); // Z=1, T=xy
  }
  static fromHex(hex: string, zip215?: boolean): Point {
    return Point.fromBytes(hexToBytes(hex), zip215);
  }
  get x(): bigint {
    return this.toAffine().x;
  }
  get y(): bigint {
    return this.toAffine().y;
  }
  /** Checks if the point is valid and on-curve. */
  assertValidity(): this {
    const a = _a;
    const d = _d;
    const p = this;
    if (p.is0()) return err('bad point: ZERO'); // TODO: optimize, with vars below?
    // Equation in affine coordinates: ax² + y² = 1 + dx²y²
    // Equation in projective coordinates (X/Z, Y/Z, Z):  (aX² + Y²)Z² = Z⁴ + dX²Y²
    const { X, Y, Z, T } = p;
    const X2 = modP(X * X); // X²
    const Y2 = modP(Y * Y); // Y²
    const Z2 = modP(Z * Z); // Z²
    const Z4 = modP(Z2 * Z2); // Z⁴
    const aX2 = modP(X2 * a); // aX²
    const left = modP(Z2 * (aX2 + Y2)); // (aX² + Y²)Z²
    const right = M(Z4 + modP(d * modP(X2 * Y2))); // Z⁴ + dX²Y²
    if (left !== right) return err('bad point: equation left != right (1)');
    // In Extended coordinates we also have T, which is x*y=T/Z: check X*Y == Z*T
    const XY = modP(X * Y);
    const ZT = modP(Z * T);
    if (XY !== ZT) return err('bad point: equation left != right (2)');
    return this;
  }
  /** Equality check: compare points P&Q. */
  equals(other: Point): boolean {
    const { X: X1, Y: Y1, Z: Z1 } = this;
    const { X: X2, Y: Y2, Z: Z2 } = apoint(other); // checks class equality
    const X1Z2 = modP(X1 * Z2);
    const X2Z1 = modP(X2 * Z1);
    const Y1Z2 = modP(Y1 * Z2);
    const Y2Z1 = modP(Y2 * Z1);
    return X1Z2 === X2Z1 && Y1Z2 === Y2Z1;
  }
  is0(): boolean {
    return this.equals(I);
  }
  /** Flip point over y coordinate. */
  negate(): Point {
    return new Point(M(-this.X), this.Y, this.Z, M(-this.T));
  }
  /** Point doubling. Complete formula. Cost: `4M + 4S + 1*a + 6add + 1*2`. */
  double(): Point {
    const { X: X1, Y: Y1, Z: Z1 } = this;
    const a = _a;
    // https://hyperelliptic.org/EFD/g1p/auto-twisted-extended.html#doubling-dbl-2008-hwcd
    const A = modP(X1 * X1);
    const B = modP(Y1 * Y1);
    const C = modP(2n * Z1 * Z1);
    const D = modP(a * A);
    const x1y1 = M(X1 + Y1);
    const E = M(modP(x1y1 * x1y1) - A - B);
    const G = M(D + B);
    const F = M(G - C);
    const H = M(D - B);
    const X3 = modP(E * F);
    const Y3 = modP(G * H);
    const T3 = modP(E * H);
    const Z3 = modP(F * G);
    return new Point(X3, Y3, Z3, T3);
  }
  /** Point addition. Complete formula. Cost: `8M + 1*k + 8add + 1*2`. */
  add(other: Point): Point {
    const { X: X1, Y: Y1, Z: Z1, T: T1 } = this;
    const { X: X2, Y: Y2, Z: Z2, T: T2 } = apoint(other); // doesn't check if other on-curve
    const a = _a;
    const d = _d;
    // https://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#addition-add-2008-hwcd-3
    const A = modP(X1 * X2);
    const B = modP(Y1 * Y2);
    const C = modP(modP(T1 * d) * T2);
    const D = modP(Z1 * Z2);
    const E = M(modP(M(X1 + Y1) * M(X2 + Y2)) - A - B);
    const F = M(D - C);
    const G = M(D + C);
    const H = M(B - modP(a * A));
    const X3 = modP(E * F);
    const Y3 = modP(G * H);
    const T3 = modP(E * H);
    const Z3 = modP(F * G);
    return new Point(X3, Y3, Z3, T3);
  }
  subtract(other: Point): Point {
    return this.add(apoint(other).negate());
  }
  /**
   * Point-by-scalar multiplication. Scalar must be in range 1 <= n < CURVE.n.
   * Uses {@link wNAF} for base point.
   * Uses fake point to mitigate side-channel leakage.
   * @param n scalar by which point is multiplied
   * @param safe safe mode guards against timing attacks; unsafe mode is faster
   */
  multiply(n: bigint, safe = true): Point {
    if (!safe && (n === 0n || this.is0())) return I;
    assertRange(n, 1n, N);
    if (n === 1n) return this;
    if (this.equals(G)) return wNAF(n).p;
    // init result point & fake point
    let p = I;
    let f = G;
    for (let d: Point = this; n > 0n; d = d.double(), n >>= 1n) {
      // if bit is present, add to point
      // if not present, add to fake, for timing safety
      if (n & 1n) p = p.add(d);
      else if (safe) f = f.add(d);
    }
    return p;
  }
  multiplyUnsafe(scalar: bigint): Point {
    return this.multiply(scalar, false);
  }
  /** Convert point to 2d xy affine point. (X, Y, Z) ∋ (x=X/Z, y=Y/Z) */
  toAffine(): AffinePoint {
    const { X, Y, Z } = this;
    // fast-paths for ZERO point OR Z=1
    if (this.equals(I)) return { x: 0n, y: 1n };
    const iz = invert(Z, P);
    // (Z * Z^-1) must be 1, otherwise bad math
    if (modP(Z * iz) !== 1n) err('invalid inverse');
    // x = X*Z^-1; y = Y*Z^-1
    const x = modP(X * iz);
    const y = modP(Y * iz);
    return { x, y };
  }
  toBytes(): Bytes {
    const { x, y } = this.toAffine();
    const b = numTo32bLE(y);
    // store sign in first LE byte
    b[31] |= x & 1n ? 0x80 : 0;
    return b;
  }
  toHex(): string {
    return bytesToHex(this.toBytes());
  }

  clearCofactor(): Point {
    return this.multiply(big(h), false);
  }
  isSmallOrder(): boolean {
    return this.clearCofactor().is0();
  }
  isTorsionFree(): boolean {
    // Multiply by big number N. We can't `mul(N)` because of checks. Instead, we `mul(N/2)*2+1`
    let p = this.multiply(N / 2n, false).double();
    if (N % 2n) p = p.add(this);
    return p.is0();
  }
}
/** Generator / base point */
const G: Point = new Point(Gx, Gy, 1n, M(Gx * Gy));
/** Identity / zero point */
const I: Point = new Point(0n, 1n, 1n, 0n);
// Static aliases
Point.BASE = G;
Point.ZERO = I;

const numTo32bLE = (num: bigint): Bytes =>
  hexToBytes(padh(assertRange(num, 0n, B256), 64)).reverse();
const bytesToNumberLE = (b: Bytes): bigint => big('0x' + bytesToHex(u8fr(abytes(b)).reverse()));

const pow2 = (x: bigint, power: bigint): bigint => {
  // pow2(x, 4) == x^(2^4)
  let r = x;
  while (power-- > 0n) {
    r = modP(r * r);
  }
  return r;
};

// prettier-ignore
const pow_2_252_3 = (x: bigint) => {                    // x^(2^252-3) unrolled util for square root
  const x2 = modP(x * x);                               // x^2,       bits 1
  const b2 = modP(x2 * x);                              // x^3,       bits 11
  const b4 = modP(pow2(b2, 2n) * b2);                   // x^(2^4-1), bits 1111
  const b5 = modP(pow2(b4, 1n) * x);                    // x^(2^5-1), bits 11111
  const b10 = modP(pow2(b5, 5n) * b5);                  // x^(2^10)
  const b20 = modP(pow2(b10, 10n) * b10);               // x^(2^20)
  const b40 = modP(pow2(b20, 20n) * b20);               // x^(2^40)
  const b80 = modP(pow2(b40, 40n) * b40);               // x^(2^80)
  const b160 = modP(pow2(b80, 80n) * b80);              // x^(2^160)
  const b240 = modP(pow2(b160, 80n) * b80);             // x^(2^240)
  const b250 = modP(pow2(b240, 10n) * b10);             // x^(2^250)
  const pow_p_5_8 = modP(pow2(b250, 2n) * x); // < To pow to (p+3)/8, multiply it by x.
  return { pow_p_5_8, b2 };
}
const RM1 = 0x2b8324804fc1df0b2b4d00993dfbd7a72f431806ad2fe478c4ee1b274a0ea0b0n; // √-1
// for sqrt comp
// prettier-ignore
const uvRatio = (u: bigint, v: bigint): { isValid: boolean, value: bigint } => {
  const v3 = modP(v * modP(v * v));                              // v³
  const v7 = modP(modP(v3 * v3) * v);                            // v⁷
  const pow = pow_2_252_3(modP(u * v7)).pow_p_5_8;            // (uv⁷)^(p-5)/8
  let x = modP(u * modP(v3 * pow));                              // (uv³)(uv⁷)^(p-5)/8
  const vx2 = modP(v * modP(x * x));                             // vx²
  const root1 = x;                                      // First root candidate
  const root2 = modP(x * RM1);                             // Second root candidate; RM1 is √-1
  const useRoot1 = vx2 === u;                           // If vx² = u (mod p), x is a square root
  const useRoot2 = vx2 === M(-u);                       // If vx² = -u, set x <-- x * 2^((p-1)/4)
  const noRoot = vx2 === M(-u * RM1);                   // There is no valid root, vx² = -u√-1
  if (useRoot1) x = root1;
  if (useRoot2 || noRoot) x = root2;                    // We return root2 anyway, for const-time
  if ((M(x) & 1n) === 1n) x = M(-x);                    // edIsNegative
  return { isValid: useRoot1 || useRoot2, value: x };
}
// N == L, just weird naming
const modL_LE = (hash: Bytes): bigint => modN(bytesToNumberLE(hash)); // modulo L; but little-endian
/** hashes.sha512 should conform to the interface. */
// TODO: rename
const sha512a = (...m: Bytes[]) => hashes.sha512Async(concatBytes(...m)); // Async SHA512
const sha512s = (...m: Bytes[]) => callHash('sha512')(concatBytes(...m));
type ExtK = { head: Bytes; prefix: Bytes; scalar: bigint; point: Point; pointBytes: Bytes };

// RFC8032 5.1.5
const hash2extK = (hashed: Bytes): ExtK => {
  // slice creates a copy, unlike subarray
  const head = hashed.slice(0, 32);
  head[0] &= 248; // Clamp bits: 0b1111_1000
  head[31] &= 127; // 0b0111_1111
  head[31] |= 64; // 0b0100_0000
  const prefix = hashed.slice(32, 64); // secret key "prefix"
  const scalar = modL_LE(head); // modular division over curve order
  const point = G.multiply(scalar); // public key point
  const pointBytes = point.toBytes(); // point serialized to Uint8Array
  return { head, prefix, scalar, point, pointBytes };
};

// RFC8032 5.1.5; getPublicKey async, sync. Hash priv key and extract point.
const getExtendedPublicKeyAsync = (secretKey: Bytes): Promise<ExtK> =>
  sha512a(abytes(secretKey, L)).then(hash2extK);
const getExtendedPublicKey = (secretKey: Bytes): ExtK => hash2extK(sha512s(abytes(secretKey, L)));
/** Creates 32-byte ed25519 public key from 32-byte secret key. Async. */
const getPublicKeyAsync = (secretKey: Bytes): Promise<Bytes> =>
  getExtendedPublicKeyAsync(secretKey).then((p) => p.pointBytes);
/** Creates 32-byte ed25519 public key from 32-byte secret key. To use, set `hashes.sha512` first. */
const getPublicKey = (priv: Bytes): Bytes => getExtendedPublicKey(priv).pointBytes;
type Finishable<T> = {
  // Reduces logic duplication between
  hashable: Bytes;
  finish: (hashed: Bytes) => T; // sync & async versions of sign(), verify()
};
const hashFinishA = <T>(res: Finishable<T>): Promise<T> => sha512a(res.hashable).then(res.finish);
const hashFinishS = <T>(res: Finishable<T>): T => res.finish(sha512s(res.hashable));
// Code, shared between sync & async sign
const _sign = (e: ExtK, rBytes: Bytes, msg: Bytes): Finishable<Bytes> => {
  const { pointBytes: P, scalar: s } = e;
  const r = modL_LE(rBytes); // r was created outside, reduce it modulo L
  const R = G.multiply(r).toBytes(); // R = [r]B
  const hashable = concatBytes(R, P, msg); // dom2(F, C) || R || A || PH(M)
  const finish = (hashed: Bytes): Bytes => {
    // k = SHA512(dom2(F, C) || R || A || PH(M))
    const S = modN(r + modL_LE(hashed) * s); // S = (r + k * s) mod L; 0 <= s < l
    return abytes(concatBytes(R, numTo32bLE(S)), 64); // 64-byte sig: 32b R.x + 32b LE(S)
  };
  return { hashable, finish };
};
/**
 * Signs message using secret key. Async.
 * Follows RFC8032 5.1.6.
 */
const signAsync = async (message: Bytes, secretKey: Bytes): Promise<Bytes> => {
  const m = abytes(message);
  const e = await getExtendedPublicKeyAsync(secretKey);
  const rBytes = await sha512a(e.prefix, m); // r = SHA512(dom2(F, C) || prefix || PH(M))
  return hashFinishA(_sign(e, rBytes, m)); // gen R, k, S, then 64-byte signature
};
/**
 * Signs message using secret key. To use, set `hashes.sha512` first.
 * Follows RFC8032 5.1.6.
 */
const sign = (message: Bytes, secretKey: Bytes): Bytes => {
  const m = abytes(message);
  const e = getExtendedPublicKey(secretKey);
  const rBytes = sha512s(e.prefix, m); // r = SHA512(dom2(F, C) || prefix || PH(M))
  return hashFinishS(_sign(e, rBytes, m)); // gen R, k, S, then 64-byte signature
};
/**
 * Verification options. zip215: true (default) follows ZIP215 spec. false would follow RFC8032.
 *
 * Any message with pubkey from `ED25519_TORSION_SUBGROUP` would be valid in sigs under ZIP215.
 */
export type EdDSAVerifyOpts = { zip215?: boolean };
const defaultVerifyOpts: EdDSAVerifyOpts = { zip215: true };
const _verify = (
  sig: Bytes,
  msg: Bytes,
  publicKey: Bytes,
  options: EdDSAVerifyOpts = defaultVerifyOpts
): Finishable<boolean> => {
  sig = abytes(sig, 64); // Signature hex str/Bytes, must be 64 bytes
  msg = abytes(msg); // Message hex str/Bytes
  publicKey = abytes(publicKey, L);
  const { zip215 } = options; // switch between zip215 and rfc8032 verif

  const r = sig.subarray(0, L);
  const s = bytesToNumberLE(sig.subarray(L, L * 2)); // Decode second half as an integer S;
  let A: Point, R: Point, SB: Point;
  let hashable: Bytes = Uint8Array.of();
  let finished = false;
  try {
    // zip215=true is good for consensus-critical apps. =false follows RFC8032 / NIST186-5.
    // zip215=true:  0 <= y < MASK (2^256 for ed25519)
    // zip215=false: 0 <= y < P (2^255-19 for ed25519)
    A = Point.fromBytes(publicKey, zip215);
    R = Point.fromBytes(r, zip215);
    SB = G.multiply(s, false); // 0 <= s < l is done inside
    hashable = concatBytes(R.toBytes(), A.toBytes(), msg); // dom2(F, C) || R || A || PH(M)
    finished = true;
  } catch (error) {}
  const finish = (hashed: Bytes): boolean => {
    if (!finished) return false;
    if (!zip215 && A.isSmallOrder()) return false; // zip215 allows public keys of small order

    // k = SHA512(dom2(F, C) || R || A || PH(M))
    const k = modL_LE(hashed);
    const RkA = R.add(A.multiply(k, false));
    // Extended group equation
    // [8][S]B = [8]R + [8][k]A'
    return RkA.subtract(SB).clearCofactor().is0();
  };
  return { hashable, finish };
};

/** Verifies signature on message and public key. Async. Follows RFC8032 5.1.7. */
const verifyAsync = async (
  signature: Bytes,
  message: Bytes,
  publicKey: Bytes,
  opts: EdDSAVerifyOpts = defaultVerifyOpts
): Promise<boolean> => hashFinishA(_verify(signature, message, publicKey, opts));
/** Verifies signature on message and public key. To use, set `hashes.sha512` first. Follows RFC8032 5.1.7. */
const verify = (
  signature: Bytes,
  message: Bytes,
  publicKey: Bytes,
  opts: EdDSAVerifyOpts = defaultVerifyOpts
): boolean => hashFinishS(_verify(signature, message, publicKey, opts));

/** Math, hex, byte helpers. Not in `utils` because utils share API with noble-curves. */
const etc = {
  bytesToHex: bytesToHex as typeof bytesToHex,
  hexToBytes: hexToBytes as typeof hexToBytes,
  concatBytes: concatBytes as typeof concatBytes,
  mod: M as typeof M,
  invert: invert as typeof invert,
  randomBytes: randomBytes as typeof randomBytes,
};
const hashes = {
  sha512Async: async (message: Bytes): Promise<Bytes> => {
    const s = subtle();
    const m = concatBytes(message);
    return u8n(await s.digest('SHA-512', m.buffer));
  },
  sha512: undefined as undefined | ((message: Bytes) => Bytes),
};

// FIPS 186 B.4.1 compliant key generation produces private keys
// with modulo bias being neglible. takes >N+16 bytes, returns (hash mod n-1)+1
const randomSecretKey = (seed: Bytes = randomBytes(L)): Bytes => seed;

type KeysSecPub = { secretKey: Bytes; publicKey: Bytes };
const keygen = (seed?: Bytes): KeysSecPub => {
  const secretKey = randomSecretKey(seed);
  const publicKey = getPublicKey(secretKey);
  return { secretKey, publicKey };
};
const keygenAsync = async (seed?: Bytes): Promise<KeysSecPub> => {
  const secretKey = randomSecretKey(seed);
  const publicKey = await getPublicKeyAsync(secretKey);
  return { secretKey, publicKey };
};

/** ed25519-specific key utilities. */
const utils = {
  getExtendedPublicKeyAsync: getExtendedPublicKeyAsync as typeof getExtendedPublicKeyAsync,
  getExtendedPublicKey: getExtendedPublicKey as typeof getExtendedPublicKey,
  randomSecretKey: randomSecretKey as typeof randomSecretKey,
};

// ## Precomputes
// --------------

const W = 8; // W is window size
const scalarBits = 256;
const pwindows = Math.ceil(scalarBits / W) + 1; // 33 for W=8, NOT 32 - see wNAF loop
const pwindowSize = 2 ** (W - 1); // 128 for W=8
const precompute = () => {
  const points: Point[] = [];
  let p = G;
  let b = p;
  for (let w = 0; w < pwindows; w++) {
    b = p;
    points.push(b);
    for (let i = 1; i < pwindowSize; i++) {
      b = b.add(p);
      points.push(b);
    } // i=1, bc we skip 0
    p = b.double();
  }
  return points;
};
let Gpows: Point[] | undefined = undefined; // precomputes for base point G
// const-time negate
const ctneg = (cnd: boolean, p: Point) => {
  const n = p.negate();
  return cnd ? n : p;
};

/**
 * Precomputes give 12x faster getPublicKey(), 10x sign(), 2x verify() by
 * caching multiples of G (base point). Cache is stored in 32MB of RAM.
 * Any time `G.multiply` is done, precomputes are used.
 * Not used for getSharedSecret, which instead multiplies random pubkey `P.multiply`.
 *
 * w-ary non-adjacent form (wNAF) precomputation method is 10% slower than windowed method,
 * but takes 2x less RAM. RAM reduction is possible by utilizing `.subtract`.
 *
 * !! Precomputes can be disabled by commenting-out call of the wNAF() inside Point#multiply().
 */
const wNAF = (n: bigint): { p: Point; f: Point } => {
  const comp = Gpows || (Gpows = precompute());
  let p = I;
  let f = G; // f must be G, or could become I in the end
  const pow_2_w = 2 ** W; // 256 for W=8
  const maxNum = pow_2_w; // 256 for W=8
  const mask = big(pow_2_w - 1); // 255 for W=8 == mask 0b11111111
  const shiftBy = big(W); // 8 for W=8
  for (let w = 0; w < pwindows; w++) {
    let wbits = Number(n & mask); // extract W bits.
    n >>= shiftBy; // shift number by W bits.
    // We use negative indexes to reduce size of precomputed table by 2x.
    // Instead of needing precomputes 0..256, we only calculate them for 0..128.
    // If an index > 128 is found, we do (256-index) - where 256 is next window.
    // Naive: index +127 => 127, +224 => 224
    // Optimized: index +127 => 127, +224 => 256-32
    if (wbits > pwindowSize) {
      wbits -= maxNum;
      n += 1n;
    }
    const off = w * pwindowSize;
    const offF = off; // offsets, evaluate both
    const offP = off + Math.abs(wbits) - 1;
    const isEven = w % 2 !== 0; // conditions, evaluate both
    const isNeg = wbits < 0;
    if (wbits === 0) {
      // off == I: can't add it. Adding random offF instead.
      f = f.add(ctneg(isEven, comp[offF])); // bits are 0: add garbage to fake point
    } else {
      p = p.add(ctneg(isNeg, comp[offP])); // bits are 1: add to result point
    }
  }
  if (n !== 0n) err('invalid wnaf');
  return { p, f }; // return both real and fake points for JIT
};

// !! Remove the export to easily use in REPL / browser console
export {
  etc,
  getPublicKey,
  getPublicKeyAsync,
  hash,
  hashes,
  keygen,
  keygenAsync,
  Point,
  sign,
  signAsync,
  utils,
  verify,
  verifyAsync,
};