Skip to content
This repository has been archived by the owner on Jun 6, 2024. It is now read-only.

Latest commit

 

History

History
126 lines (92 loc) · 3.81 KB

spec.md

File metadata and controls

126 lines (92 loc) · 3.81 KB

Starsig specification

This is a technical specification for single-message Schnorr signature protocol implemented with Ristretto and Merlin transcripts.

Scalar

A scalar is an integer modulo Ristretto group order |G| = 2^252 + 27742317777372353535851937790883648493.

Scalars are encoded as 32-byte strings using little-endian convention.

Every scalar is required to be in a canonical (reduced) form.

Point

A point is an element in the Ristretto group.

Points are encoded as compressed Ristretto points (32-byte strings).

Base point

Ristretto base point in compressed form:

B = e2f2ae0a6abc4e71a884a961c500515f58e30b6aa582dd8db6a65945e08d2d76

Verification key

A point representing a key against which a signature is verified.

Verification key is computed by multiplying the base point B by the secret scalar x.

P = x·B

Verification key is encoded as a 32-byte string using Ristretto compression.

Signature

A pair of a point R and scalar s that proves the knowledge of the secret key for a given message and a verification key. Signature is bound to the message and the verification key, but they are not the part of the signature data.

(R,s)

Signature is encoded as a 64-byte string using Ristretto compression for R and little-endian notation for 256-bit integer s.

Transcript

Transcript is an instance of the Merlin construction, which is itself based on STROBE and Keccak-f with 128-bit security parameter.

Transcript is used in the signature protocols to perform Fiat-Shamir technique.

Transcripts have the following operations, each taking a label for domain separation:

  1. Initialize transcript: 
    T := Transcript(label)
  2. Append bytes of arbitrary length prefixed with a label: 
    T.append(label, bytes)
  3. Challenge bytes 
    T.challenge_bytes<size>(label) -> bytes
  4. Challenge scalar is defined as generating 64 challenge bytes and reducing the 512-bit little-endian integer modulo Ristretto group order |G|: 
    T.challenge_scalar(label) -> scalar
T.challenge_scalar(label) == T.challenge_bytes<64>(label) mod |G|

Signature protocol

Single-message signature is a Schnorr proof of knowledge of a secret scalar x corresponding to some verification key in a context of some message.

The protocol is the following:

  1. Prover and verifier obtain a transcript T that is assumed to be already bound to the message being signed.
  2. Prover and verifier both commit the verification key X (computed by the prover as X = x·B): 
    T.append("dom-sep", "starsig v1")
T.append("X", X)
  3. Prover creates a secret nonce: a randomly sampled scalar r.
  4. Prover commits to its nonce: 
    R = r·B
  5. Prover sends R to the verifier.
  6. Prover and verifier write the nonce commitment R to the transcript: 
    T.append("R", R)
  7. Prover and verifier compute a Fiat-Shamir challenge scalar c using the transcript: 
    c = T.challenge_scalar("c")
  8. Prover blinds the secret scalar x using the nonce and the challenge: 
    s = r + c·x
  9. Prover sends s to the verifier.
  10. Verifier checks the relation: 
    s·B  ==  R + c·X