{"_id":"@cypher-laboratory/alicesring-sag-starknet","name":"@cypher-laboratory/alicesring-sag-starknet","dist-tags":{"latest":"0.2.1"},"versions":{"0.2.1":{"name":"@cypher-laboratory/alicesring-sag-starknet","version":"0.2.1","description":"A TypeScript implementation of SAG ring signatures tailored for verification on starknet.","main":"dist/starknet-sag-ts/src/index.js","module":"dist/starknet-sag-ts/src/index.js","types":"dist/starknet-sag-ts/src/index.d.js","repository":{"type":"git","url":"git+https://github.com/Cypher-Laboratory/Alice-s-Ring.git"},"scripts":{"build":"npm run fmt && rimraf ./dist && mkdir -p ./dist && tsc","clean":"rimraf ./dist && rimraf ./node_modules","test":"jest","lint":"eslint .","lint:fix":"eslint . --fix","prettier":"prettier --check .","prettier:fix":"prettier --write .","fmt:check":"npm run prettier && npm run lint","fmt":"npm run prettier:fix && npm run fmt:check"},"author":{"name":"Elli610 && LeJamon && maximedgr"},"license":"MIT","dependencies":{"@cypher-laboratory/ring-sig-utils":"^0.0.1","@noble/hashes":"^1.3.2","@scure/starknet":"^1.0.0","crypto-browserify":"^3.12.0","garaga":"^0.13.3","js-sha3":"^0.9.3","starknet":"^6.11.0","ts-node":"^10.9.1"},"devDependencies":{"@types/jest":"^29.5.7","@types/node":"^20.8.7","@typescript-eslint/eslint-plugin":"^5.61.0","@typescript-eslint/parser":"^5.61.0","eslint":"^8.44.0","jest":"^29.7.0","prettier":"^3.0.0","ts-jest":"^29.1.1"},"_id":"@cypher-laboratory/alicesring-sag-starknet@0.2.1","gitHead":"8e1631979ec85820bd2bec4da001841e9349282d","bugs":{"url":"https://github.com/Cypher-Laboratory/Alice-s-Ring/issues"},"homepage":"https://github.com/Cypher-Laboratory/Alice-s-Ring#readme","_nodeVersion":"20.11.1","_npmVersion":"10.2.4","dist":{"integrity":"sha512-gHqE0QOeIFSFKiGZD0mZ5RHL8MzrXea/QLPHTrroezcu+fRt+tj1rl/wuT0NZo7//8xkfRuy3raL0TApxXaCZw==","shasum":"2d58d021ca7b999206b8a6140e7a976d557a2e3a","tarball":"https://registry.npmjs.org/@cypher-laboratory/alicesring-sag-starknet/-/alicesring-sag-starknet-0.2.1.tgz","fileCount":39,"unpackedSize":161294,"signatures":[{"keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U","sig":"MEUCIQDEC2+S3qy2JiBPy2muxnwxqxh18R6yf061g57gATSV0wIgJ2w2K7UaVrYYHMKrroj4KNkOAdVp/j6NnptrdTh6tJM="}]},"_npmUser":{"name":"lejamon","email":"lejamon.c@protonmail.com"},"directories":{},"maintainers":[{"name":"lejamon","email":"lejamon.c@protonmail.com"},{"name":"cypherlaboratory","email":"cypherlabsas@gmail.com"},{"name":"elli610","email":"niktoua256@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/alicesring-sag-starknet_0.2.1_1743541615527_0.9515295133926303"},"_hasShrinkwrap":false}},"time":{"created":"2025-04-01T21:06:55.391Z","0.2.1":"2025-04-01T21:06:55.728Z","modified":"2025-04-01T21:06:56.134Z"},"maintainers":[{"name":"lejamon","email":"lejamon.c@protonmail.com"},{"name":"cypherlaboratory","email":"cypherlabsas@gmail.com"},{"name":"elli610","email":"niktoua256@gmail.com"}],"description":"A TypeScript implementation of SAG ring signatures tailored for verification on starknet.","homepage":"https://github.com/Cypher-Laboratory/Alice-s-Ring#readme","repository":{"type":"git","url":"git+https://github.com/Cypher-Laboratory/Alice-s-Ring.git"},"author":{"name":"Elli610 && LeJamon && maximedgr"},"bugs":{"url":"https://github.com/Cypher-Laboratory/Alice-s-Ring/issues"},"license":"MIT","readme":"# Alice's-Ring-Starknet-SAG-TS\n\nThis repository contains a TypeScript implementation of the [Ring Signature](https://en.wikipedia.org/wiki/Ring_signature) algorithm using Spontaneous Anonymous Group (SAG).\nThis implementation is tailored to be verified on Starknet. \n\n\n## About the implementation\n\nThe implementation is based on the SAG algorithm and uses the [Elliptic Curve Cryptography](https://en.wikipedia.org/wiki/Elliptic-curve_cryptography) (ECC) to generate the keys and sign the message.\n\nWe used the implementation proposed in [Zero to Monero](https://www.getmonero.org/library/Zero-to-Monero-2-0-0.pdf) (p.36) as a reference.\n\n### Modifications from the Basic SAG Scheme\n\nThis implementation includes several modifications compared to the basic SAG scheme:\n\n1. **Hashing Algorithm**: \n   - Uses Poseidon instead of Keccak\n   - Reduces steps needed for verification on Starknet\n   - Efficiency: 0.08 gas/application for Poseidon vs 5.2 gas/application for Keccak\n\n2. **Verification Optimization**:\n   - Utilizes [Garaga](https://github.com/keep-starknet-strange/garaga/) for precomputation in MultiScalarMultiplication (MSM)\n   - Significantly improves performance\n\n3. **ED25519 Curve Adaptation**:\n   - Points are converted to Weierstrass form for Garaga compatibility\n\n4. **Hashed Data comparaison**:\n    - As Garaga uses u384, all the data that are hashed are being cast to this type.\n    - Allowing simple interaction between the ts and the smart-contract.\n\n## Usage\n\n```typescript\nimport { RingSignature , Curve , CurveName , Point } from '@cypher-laboratory/alicesring-sag';\n\nconst curve: Curve = new Curve(CurveName.SECP256K1);\nconst ring: Point[] = []; // your ring of public keys\nconst message = 'Hello World!';\n\nconst signerPrivateKey = BigInt('your private key');\n\n// Sign\nconst signature: RingSignature = RingSignature.sign(\n  ring,\n  signerPrivateKey,\n  message,\n  curve,\n);\n\n// Verify\nconsole.log(\n  \"Is signature verified? \", signature.verify()\n);\n\n// Get callData\nconst callData = await signature.getCallData(); \nconsole.log(callData); \n// Export to jsonString\nconst jsonString = signature.toJsonString();\n\n// Import from jsonString\nconst retrievedFromJson = RingSignature.fromJson(jsonString);\n```\n\n## Spontaneous Anonymous Group (SAG) Signatures\n### Group Setup\nWhen setting up a group for cryptographic purposes, such as for a Spontaneous Anonymous Group (SAG) signature scheme, there are two primary methods to establish the group members' public keys: \n\n- **using existing public keys** of the members from publicly available data such as blockchains. This method is suitable for scenarios where the group members have a common caracteristics, such as being part of the same organization or having a specific role. For example, a group of members of a company's board of directors can be identified by their public keys, which are publicly available on the company's website.\n- **using a group key generation algorithm** to generate the public keys of the members. This method is suitable for scenarios where the group members are not known in advance, such as in a voting system. For example, a group of voters can be identified by their public keys, which are generated by the voting system's key generation algorithm.\n\n### Signature Generation\nLet $l$ be the number of members in the group.  \nLet $R$ be a set of public keys of the group members such as $R$ = { $K_{0}$ , $K_{1}$ , ..., $K_{n}$ } where n be the number of members in the group minus 1 ($l = n + 1$).   \nLet $m$ be the digest of the message to be signed.   \nLet $H$ be a hash function.   \nLet $k$ be a random integer in the range $[1, N-1]$. This is the private key of the signer.  \nLet $\\pi$ be the signer position in the group. This is a random integer in the range $[0, n]$.  \n\nThe signer computes the following:\n- Generates a random integer $\\alpha$ in the range [1, N-1]\n- Generates random responses *r* = { $r_{0}$ , $r_{1}$ , ... , $r_{\\pi-1}$, $r_{\\pi+1}$, ... , $r_{n}$ } where $r_{i}$ ($0 <= i <= n$ excluding $\\pi$) is a random integer in the range $[1, N-1]$\n- Computes $c_{\\pi+1} = H(R, m, [\\alpha G])$\n- For $j$ in $[\\pi + 1, l + \\pi]$ computes the following:\n    - $i = mod(j, l)$ -> allows to loop over the group members\n    - $s = i - 1$ if $i > 0$ else $l - 1$ -> $s = i - 1$ except when $i = 0$. In this case, $s = l - 1$\n    - $c_{i+1} = H(R, m, [r_{s}G + c_{s}K_{s}])$\n- Define the signer's response to verify $\\alpha = r_{\\pi} + c_{\\pi}k$ ($mod$ $N$)\n\nThe signature contains the following:\n- the ring of public keys $R$\n- the challenge $c_{1}$\n- the responses $r$ = { $r_{0}$ , $r_{1}$ , ... , $r_{n}$ }\n  \n\n### Signature Verification\nKnown data:\n- the ring of public keys $R$\n- the seed $c_{0}$\n- the responses $r$ = { $r_{0}$ , $r_{1}$ , ... , $r_{n}$ }\n- the message $m$\n\nThe signature is valid if and only if the signature has been generated using one of the group member's private keys.\n\nThe verifier computes the following:\n- For $i = 2$ to $n$, with $i$ wrapping around to 1 after $n$:\n    - $c_{i}$' = $H( R, m, [ r_{i-1} G$  + $c_{i-1}$' $K_{i-1}$]) if $i ≠ 1$ else $c_{i}$' = $H(R, m, [r_{1}G + c_{1}K_{1}])$\n- If $c_{1}$' = $c_{1}$ then the signature is valid, else it is invalid.\n\n\n## Detailed implementation \n\n### RingSignature.sign\n\nThis method is designed to compute a ring signature by directly utilizing a private key as input. It's tailored for scenarios where you do not use a wallet for key management. The RingSignature.sign function needs the private key to generate the ring signature.\n\n#### 1. Sort the ring by x ascending (and y ascending if x is equal)\nLet $\\pi$ be the signer position in the group. This is an integer in the range $[0, n]$.\n\n#### 2. Generate Random Number $\\alpha$\nIt will be use as the nonce.\n- **Function:** `randomBigint`\n- **Location:** `src/utils/randomNumber.ts`\n- **Description:** Generates a random bigint in the range [1, max[.\n\n```typescript\nexport function randomBigint(max: bigint): bigint\n```\n\n#### 3. Compute $c_{\\pi+1}$\n $c_{\\pi+1} = H(R, m, [\\alpha G])$\n- **Function:** `computeC`\n- **Location:** `src/ringSignatures.ts`\n- **Description:** Compute a c value.\n- **Remarks:**\n   * This function is used to compute the c value of a ring-signature.\n   * Either 'alpha' or all the other keys of 'params' must be set..\n\n```typescript\n  private static computeC(\n    ring: Point[],\n    messageDigest: bigint,\n    params: {\n      previousR?: bigint;\n      previousC?: bigint;\n      previousPubKey?: Point;\n      alpha?: bigint;\n    },\n    curve: Curve,\n  ): bigint \n```\n#### 4. Compute the challenges.\nGenerates random responses *r* = {$r_{1}$, ... , $r_{\\pi-1}$, $r_{\\pi+1}$, ... , $r_{n}$ } where $r_{i}$ ($0 <= i <= n$ excluding $\\pi$) is a random integer in the range $[1, N-1]$  \nFor i = ${\\pi+1}$, ${\\pi+2}$ , ..., n, 1, 2, ..., ${\\pi-1}$ calculate, replacing n + 1 → 1,\n\n$c_{i+1} = H(R, m, [r_{s}G - c_{s}K_{s}])$\n\n- **Function:** `RingSignature.signature`\n- **Location:** `src/ringSignature.ts`\n- **Description:** Generate an incomplete ring signature.\n\n```typescript\n  private static signature(\n    curve: Curve,\n    ring: Point[],\n    ceePiPlusOne: bigint,\n    signerIndex: number,\n    messageDigest: bigint,\n  ): {\n    ring: Point[];\n    cees: bigint[];\n    signerIndex: number;\n    responses: bigint[];\n  }\n```\n\n#### 5. Compute the signer response $r_{\\pi}$\n$r_{\\pi}$ such that $\\alpha = r_{\\pi} - c_{\\pi}k$ ($mod$ $N$).\n- **Function:** `piSignature`\n- **Location:** `src/signature/piSignature.ts`\n- **Description:** Compute the signature from the actual signer.\n\n```typescript\nexport function piSignature(\n  alpha: bigint,\n  c: bigint,\n  signerPrivKey: bigint,\n  curve: Curve,\n): bigint \n```\n\n#### 6. Return the ring signature\nReturn the ring-signature.\n- **Function:** `constructor`\n- **Location:** `src/ringSignature.ts`\n- **Description:** Ring signature class constructor.\n\n```typescript\n  constructor(\n    message: string,\n    ring: Point[],\n    c: bigint,\n    responses: bigint[],\n    curve: Curve,\n    config?: SignatureConfig,\n  ) \n```\n\n### RingSignature.verify\nThis method verifies if a ring signature is valid.\n\n#### 1. Verify the ring signature\n- **Function:** `RingSignature.verify.ts`\n- **Location:** `src/ringSignature.ts`\n- **Description:** Verify a RingSignature.\n\n```typescript\n  verify(): boolean\n```\n\n### RingSignature.getCallData()\nThis method verifies if the ring signature is valid. And if so return the raw callData to use on Starknet. \n\n#### 1. Verify the ring signature\n- **Function:** `RingSignature.getCallData`\n- **Location:** `src/ringSignature.ts`\n- **Description:** Verify a RingSignature and return the raw callData if valid.\n\n```typescript\n  getCallData(): biging[]\n```\n\n","readmeFilename":"README.md","_rev":"1-b96b7691703f47265131072e17b6f289"}