# r255b3: schnorr signatures using ristretto255 and blake3.

This crate provides short [Schnorr signatures][Schnorr] based on [Ristretto255] and [Blake3].

[Schnorr]: https://en.wikipedia.org/wiki/Schnorr_signature
[Curve25519]: https://en.wikipedia.org/wiki/Curve25519
[Ristretto255]: https://ristretto.group
[Blake3]: https://github.com/BLAKE3-team/BLAKE3

Note: This is not [Ed25519], if you want Ed25519, please use the excellent [ed25519-dalek] crate.

[Ed25519]: https://en.wikipedia.org/wiki/Ed25519
[ed25519-dalek]: https://crates.io/crates/ed25519-dalek

Warning! This is a slightly novel cryptographic primitive.
It has not been audited! Use at your own (not others') risk!

The API and cryptographic construction may change in response to an audit,
but may be considered relatively stable starting with version 0.3.0.

## Why?

The initial motivation was to provide a minimal footprint for embedded versions of [converge].
It already used the Blake3 hash function extensively,
and that wasn't going to change to SHA512 just for Ed25519 signatures.

That said, there are other benefits over Ed25519:

- smaller keys using the Schnorr signature formulation.
- proper (and enforced) support for domain separation.
- well specified secret keys, and no malleability in the public keys, or signatures.
- the default mode supports streaming, and signing data with a single pass.
- uses the [*much* faster][Blake3] hash function, *much* faster for large inputs.

[converge]: https://adpt.dev/tools/converge

## How?

The Schnorr signature scheme has accumulated many variations, this one:

- provides built-in domain separation
- uses a scalar as the secret key and the group generator times that scalar as the public key
- uses a small scalar, large scalar tuple as the signature
- derives a deterministic random nonce from the domain, message, secret key, and public key
- mixes the public key into the message hash

### Key Generation

r255b3 uses Ristretto255 scalars as secret keys.
These are generated by sampling 256 bits of secure randomness then reducing by the group order.
This group order is *relatively* slightly more than 2²⁵²,
which limits the total deviation from a uniform distribution to roughly 2⁻¹²⁶.

```
sk ←ᴿ Scalars
pk := sk*B
```

### Message Hash Preparation

We first derive a keyed hash from the domain, using Blake3's context hashing:

```
hk := Blake3Ctx("Schnorr-Ristretto255-Blake3", domain)
```

### Signing

Next we generate a scalar nonce, `k`, either by sampling a random value or deterministically:

```
k := Blake3Keyed(hk, message || "Secret Nonce for Schnorr-Ristretto255-Blake3" || sk || pk)
```

Now `k` scales the generator to get the Ristretto255 point `r`.
`r` is compressed, concatenated with the message and public key, and fed to Blake3 to used to derive the short scalar `e`.

```
r = k*B
e = Blake3(hk, message || "Message Hash for Schnorr-Ristretto255-Blake3" || pk || r)
```

`e` here is the first 128 bits of the hash, the second 128 bits are discarded.

Note that the hashes for `k` and `e` share a common prefix,
this enables us to duplicate the hash state before feeding the context strings, keys, and points used once into the hash.

Finally, we multiply `e` by the secret key, and subtract their product from `k`, yielding the (full size) scalar `s`.
This produces our signature, which is the tuple of `e` and `s`.

```
s = k - sk * e
sig = (e, s)
```

`e` is 16 bytes, and `s` is 32 bytes, resulting in a 48 byte signature.

### Verifying

Verification proceeds by reconstructing `r`.

```
rᵥ = s*B + e*pk = (k - sk*e)*B + (e*sk*B) = k*B - sk*e*B + e*sk*B = k*B
```

Now that we have `rᵥ`, we hash the message with our keyed Blake3 exactly as was done during signing.
This yields another copy of `e`, which we call `eᵥ`.

```
eᵥ = Blake3(hk, message || "Message Hash for Schnorr-Ristretto255-Blake3" || pk || r)
```

Finally, we can compare `eᵥ` with the `e` from the signature, and if they match we have a valid signature.

## Test Vectors

Secret Key: "Did gyre and gimble in the wabe\n"
Public Key: 161bf5685cfbb674ad88dbbb266e15ec5aa93406135ec471704acb79cd246564
On Domain: "All mimsy were the borogroves,"
On Message: "And the mome raths outgrabe"
Signature: 9028a67bf5ca00771b15ab30535bba69d4991415d864503cd87e589712d0e0186d4c03629416d51e639817ba9009520c

## License

This project is dedicated to the public domain, see the [UNLICENSE](./UNLICENSE) for details.