This repository contains a TypeScript implementation of the Linkable Spontaneous Anonymous Group (LSAG) signature algorithm, built on Elliptic Curve Cryptography (ECC) for secure key generation and message signing. The implementation follows the LSAG algorithm as detailed in the SAG paper and takes inspiration from Zero to Monero (p.36).
- Alice's Ring LSAG-ts
Linkable Spontaneous Anonymous Group (LSAG) signatures are an advanced cryptographic technique designed to provide both anonymity and linkability in a set of public keys (referred to as a "ring"). They extend the concept of ring signatures by allowing the detection of whether multiple signatures were created by the same signer, without revealing the signer's identity.
-
Anonymity: LSAG ensures that the identity of the signer is concealed among a group of participants. This is achieved by constructing a "ring" of public keys, where the actual signer’s key is indistinguishable from the others. As a result, an external observer cannot determine which member of the ring actually signed the message.
-
Linkability: While the signer’s identity remains hidden, LSAG signatures introduce a "linkability" feature that allows anyone to check if two signatures were made by the same private key. This is done through the creation of a key image, which is derived from the private key but cannot be used to reveal the private key itself. If the same key image appears in multiple signatures, those signatures can be linked to the same signer.
-
Unlinkability in Different Contexts: To prevent key image reuse from leaking information across multiple contexts, LSAG allows the use of a linkability flag, a unique identifier for each context in which the signature is used. By changing the linkability flag, the signer can ensure that the key image is valid only within a specific context, providing unlinkability across different scenarios.
When 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:
- 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.
- 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.
Let
Let
Let
Let
Let
Let
Let
The signer computes the following:
- Computes their key image:
$\tilde{K} = k * H_p(K_{\pi})$ - Generates a random integer
$\alpha$ in the range [1, N-1] - 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]$ - Computes
$c_{\pi+1} = H(R, m, [\alpha G], [\alpha H_p(K_{\pi})])$ - For
$j$ in$[\pi + 1, l + \pi]$ computes the following:-
$i = mod(j, l)$ -> allows to loop over the group members -
$s = i - 1$ if$i > 0$ else$l - 1$ ->$s = i - 1$ except when$i = 0$ . In this case,$s = l - 1$ $c_{i+1} = H(R, m, [r_{s}G + c_{s}K_{s}], [r_{s}H_p(K_{s}) + c_{s}\tilde{K}])$
-
- Define the signer's response to verify
$\alpha = r_{\pi} + c_{\pi}k$ ($mod$ $N$ )
The signature contains the following:
- the ring of public keys
$R$ - the challenge
$c_{1}$ - the responses
$r$ = {$r_{0}$ ,$r_{1}$ , ... ,$r_{n}$ }
Known data:
- the ring of public keys
$R$ - the seed
$c_{0}$ - the responses
$r$ = {$r_{0}$ ,$r_{1}$ , ... ,$r_{n}$ } - the message
$m$
The signature is valid if and only if the signature has been generated using one of the group member's private keys.
The verifier computes the following:
- For
$i = 2$ to$n$ , with$i$ wrapping around to 1 after$n$ :-
$c_{i}$ ' =$H( R, m, [ r_{i-1} G + c_{i-1}' K_{i-1}], [r_{i-1}H_p(K_{i-1}) + c_{i-1}\tilde{K}])$ if$i ≠ 1$ else$c_{i}$ ' =$H(R, m, [r_{1}G + c_{1}K_{1}], [r_{1}H_p(K_{1}) + c_{1}\tilde{K}])$
-
- If
$c_{1}$ ' =$c_{1}$ then the signature is valid, else it is invalid.
Note: It’s important to use the hash that returns curve points directly, rather than computing some integer that is then multiplied by
$G$ .$H_p$ would be broken if someone discovered a way to find$n_x$ such that$n_xG = H_p(x)$ .
To install the LSAG-ts library, use either npm or yarn:
npm install @cypher-laboratory/alicesring-lsagor
yarn add @cypher-laboratory/alicesring-lsagTo get started, import the required classes from the LSAG-ts library:
import { RingSignature, Curve, CurveName, Point } from '@cypher-laboratory/alicesring-lsag';Select the elliptic curve that matches your keys, such as SECP256K1 (for Bitcoin/Ethereum) or ED25519:
const curve = new Curve(CurveName.SECP256K1);Create a ring of public keys to form the anonymous signing group:
const publicKeys = [
'030066ba293cc22d0eadbe494e9bd4d6d05c3e09d74dff0e991075de74b2359678',
'0316d7da70ba247a6a40bb310187e8789b80c45fa6dc0061abb8ced49cbe7f887f',
'0221869ca3ae33be3a7327e9a0272203afa72c52a5460ceb9f4a50930531bd926a',
];
const ring: Point[] = publicKeys.map(compressed => Point.deserialize(compressed));To sign a message, use your private key and optionally a linkability flag to prevent signature leakage across contexts:
const signerPrivateKey = BigInt('0x...');
const message = 'Hello, Alice\'s Ring with LSAG!';
const linkabilityFlag = 'unique-context-string';
const signature = RingSignature.sign(ring, signerPrivateKey, message, curve, linkabilityFlag);To verify the signature:
const isValid = signature.verify();
console.log('Is the signature valid?', isValid); // Outputs: true or falseYou can serialize and deserialize signatures as JSON or Base64:
const jsonString = signature.toJsonString();
const importedSignature = RingSignature.fromJson(jsonString);import { RingSignature, Curve, CurveName, Point } from '@cypher-laboratory/alicesring-lsag';
const curve = new Curve(CurveName.SECP256K1);
const ring = [new Point(curve, [BigInt('0x1...'), BigInt('0x2...')])];
const signerPrivateKey = BigInt('0x5...');
const message = 'Confidential message with LSAG';
const linkabilityFlag = 'transaction-context';
const signature = RingSignature.sign(ring, signerPrivateKey, message, curve, linkabilityFlag);
console.log('Is signature valid?', signature.verify());
const signatureJson = signature.toJsonString();
const importedSignature = RingSignature.fromJson(signatureJson);
console.log('Is the imported signature valid?', importedSignature.verify());Represents a point on an elliptic curve. Key methods include:
mult(scalar: bigint): Pointadd(point: Point): Pointequals(point: Point): booleanserialize(): stringstatic deserialize(compressed: string): Point
Represents an elliptic curve. Key properties include:
name: Name of the curve (SECP256K1,ED25519).G: Generator point.isOnCurve(point: Point): boolean: Validates if a point is on the curve.
Handles signing and verifying LSAG signatures. Key methods include:
static sign(ring: Point[], signerPrivateKey: bigint, message: string, curve: Curve, linkabilityFlag: string): RingSignatureverify(): booleantoJsonString(): stringstatic fromJson(json: string | object): RingSignature
- Private Key Security: Ensure the safe handling of private keys.
- Random Number Generation: Use secure random number generators.
- Ring Size: A larger ring increases anonymity.
- Key Image Uniqueness: Avoid using the same key image in different contexts by utilizing the linkability flag.
We welcome contributions. Please open issues or submit pull requests on our GitHub repository.
For further reference on SAG and LSAG, see the Zero to Monero document, which served as a guide for this implementation.