@cypher-laboratory/alicesring-sag-starknet NPM

Alice's-Ring-Starknet-SAG-TS

This repository contains a TypeScript implementation of the Ring Signature algorithm using Spontaneous Anonymous Group (SAG). This implementation is tailored to be verified on Starknet.

About the implementation

The implementation is based on the SAG algorithm and uses the Elliptic Curve Cryptography (ECC) to generate the keys and sign the message.

We used the implementation proposed in Zero to Monero (p.36) as a reference.

Modifications from the Basic SAG Scheme

This implementation includes several modifications compared to the basic SAG scheme:

Hashing Algorithm:
- Uses Poseidon instead of Keccak
- Reduces steps needed for verification on Starknet
- Efficiency: 0.08 gas/application for Poseidon vs 5.2 gas/application for Keccak
Verification Optimization:
- Utilizes Garaga for precomputation in MultiScalarMultiplication (MSM)
- Significantly improves performance
ED25519 Curve Adaptation:
- Points are converted to Weierstrass form for Garaga compatibility
Hashed Data comparaison:
- As Garaga uses u384, all the data that are hashed are being cast to this type.
- Allowing simple interaction between the ts and the smart-contract.

Usage

import { RingSignature , Curve , CurveName , Point } from '@cypher-laboratory/alicesring-sag';

const curve: Curve = new Curve(CurveName.SECP256K1);
const ring: Point[] = []; // your ring of public keys
const message = 'Hello World!';

const signerPrivateKey = BigInt('your private key');

// Sign
const signature: RingSignature = RingSignature.sign(
  ring,
  signerPrivateKey,
  message,
  curve,
);

// Verify
console.log(
  "Is signature verified? ", signature.verify()
);

// Get callData
const callData = await signature.getCallData(); 
console.log(callData); 
// Export to jsonString
const jsonString = signature.toJsonString();

// Import from jsonString
const retrievedFromJson = RingSignature.fromJson(jsonString);

Spontaneous Anonymous Group (SAG) Signatures

Group Setup

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.

Signature Generation

Let $l$ be the number of members in the group.
Let $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$).
Let $m$ be the digest of the message to be signed.
Let $H$ be a hash function.
Let $k$ be a random integer in the range $1, N-1$. This is the private key of the signer.
Let $\pi$ be the signer position in the group. This is a random integer in the range $0, n$.

The signer computes the following:

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)$
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}])$
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}$ }

Signature Verification

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}$]) if $i ≠ 1$ else $c{i}$' = $H(R, m, [r{1}G + c{1}K{1}])$
If $c{1}$' = $c{1}$ then the signature is valid, else it is invalid.

Detailed implementation

RingSignature.sign

This 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.

1. Sort the ring by x ascending (and y ascending if x is equal)

Let $\pi$ be the signer position in the group. This is an integer in the range $0, n$.

2. Generate Random Number $\alpha$

It will be use as the nonce.

Function: randomBigint
Location: src/utils/randomNumber.ts
Description: Generates a random bigint in the range [1, max[.

export function randomBigint(max: bigint): bigint

3. Compute $c_{\pi+1}$

$c_{\pi+1} = H(R, m, \alpha G)$

Function: computeC
Location: src/ringSignatures.ts
Description: Compute a c value.
Remarks:
- This function is used to compute the c value of a ring-signature.
- Either 'alpha' or all the other keys of 'params' must be set..

  private static computeC(
    ring: Point[],
    messageDigest: bigint,
    params: {
      previousR?: bigint;
      previousC?: bigint;
      previousPubKey?: Point;
      alpha?: bigint;
    },
    curve: Curve,
  ): bigint

4. Compute the challenges.

Generates 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$
For i = ${\pi+1}$, ${\pi+2}$ , ..., n, 1, 2, ..., ${\pi-1}$ calculate, replacing n + 1 → 1,

$c{i+1} = H(R, m, [r{s}G - c{s}K{s}])$

Function: RingSignature.signature
Location: src/ringSignature.ts
Description: Generate an incomplete ring signature.

  private static signature(
    curve: Curve,
    ring: Point[],
    ceePiPlusOne: bigint,
    signerIndex: number,
    messageDigest: bigint,
  ): {
    ring: Point[];
    cees: bigint[];
    signerIndex: number;
    responses: bigint[];
  }

5. Compute the signer response $r_{\pi}$

$r{\pi}$ such that $\alpha = r{\pi} - c_{\pi}k$ ($mod$ $N$).

Function: piSignature
Location: src/signature/piSignature.ts
Description: Compute the signature from the actual signer.

export function piSignature(
  alpha: bigint,
  c: bigint,
  signerPrivKey: bigint,
  curve: Curve,
): bigint

6. Return the ring signature

Return the ring-signature.

Function: constructor
Location: src/ringSignature.ts
Description: Ring signature class constructor.

  constructor(
    message: string,
    ring: Point[],
    c: bigint,
    responses: bigint[],
    curve: Curve,
    config?: SignatureConfig,
  )

RingSignature.verify

This method verifies if a ring signature is valid.

1. Verify the ring signature

Function: RingSignature.verify.ts
Location: src/ringSignature.ts
Description: Verify a RingSignature.

  verify(): boolean

RingSignature.getCallData()

This method verifies if the ring signature is valid. And if so return the raw callData to use on Starknet.

1. Verify the ring signature

Function: RingSignature.getCallData
Location: src/ringSignature.ts
Description: Verify a RingSignature and return the raw callData if valid.

  getCallData(): biging[]

@cypher-laboratory/ring-sig-utils @noble/hashes @scure/starknet crypto-browserify garaga js-sha3 starknet ts-node

0.2.1

8 months ago