---
# System prepended metadata

title: ternary-signing-scheme
tags: [' draft', RFC]

---

---
title: ternary-signing-scheme
tags: RFC, draft
---

+ Feature name: `ternary-signing-scheme`
+ Start date: 2020-07-13
+ RFC PR: [iotaledger/bee-rfcs#00](https://github.com/iotaledger/bee-rfcs/pull/00)
+ Bee issue: [iotaledger/bee#00](https://github.com/iotaledger/bee/issues/00)

# Summary

Following the principles of asymmetric cryptography and Hierarchical Deterministic Wallets, this RFC establishes a
signing scheme for the IOTA protocol.

## Asymmetric cryptography

Asymmetric cryptography is a system that makes use of a pair of keys to allow:

+ **Confidentiality**: a message is encrypted by anyone with a public key and only the owner of the matching private key
  is able to decrypt it;
+ **Authenticity**: a message is signed with a private key by its owner and the signature can be verified by anyone with
  the matching public key;

This RFC only focuses on the authenticity aspect of asymmetric cryptography and defines `signing scheme` as being the set of data structures and algorithms allowing authenticity of a message.

In the IOTA protocol, asymmetric cryptography is used to authenticate the transfer of tokens. To move tokens out of an
address - which is a public key - one has to show a proof that he actually is the owner of the tokens. This proof is
the digital signature of the transfer, has been created with the private key associated to that address and the
signature is verifiable by anyone with the address.

Useful links:

+ [Asymmetric cryptography](https://en.wikipedia.org/wiki/Public-key_cryptography)
+ [Digital signature](https://en.wikipedia.org/wiki/Digital_signature)
+ [IOTA signatures](https://docs.iota.org/docs/getting-started/0.1/clients/signatures)

## Hierarchical Deterministic Wallets

<!-- TODO -->

Useful links:

+ [BIP32](https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki)
+ [IOTA seeds](https://docs.iota.org/docs/getting-started/0.1/clients/seeds)
+ [IOTA addresses](https://docs.iota.org/docs/getting-started/0.1/clients/addresses)

# Motivation

At the time of writing, the following signing schemes are being used in the IOTA network:

+ the ledger uses a Winternitz One-Time Signature (WOTS) scheme;
+ the coordinator uses a Merkle Signature Scheme (MSS) scheme on top of WOTS to enable reusable addresses;
+ both iterations of MAM use another WOTS scheme;
+ both iterations of MAM use another MSS scheme on top of WOTS to enable reusable addresses;

Other schemes, like Ed25519, are being investigated for the ledger.

Even though these schemes are very different on an implementation point of view, they all share the same basic behaviour justifying the existence of the following proposed design.

Useful links:

+ [Lamport signature](https://en.wikipedia.org/wiki/Lamport_signature)
+ [On the Security of the Winternitz One-Time Signature Scheme](https://eprint.iacr.org/2011/191.pdf)
+ [Merkle signature scheme](https://en.wikipedia.org/wiki/Merkle_signature_scheme)
+ [EdDSA](https://en.wikipedia.org/wiki/EdDSA)

# Detailed design

<!-- TODO -->

The proposed design is at the very core of asymmetric cryptography in which a pair of private and public keys are used
to create and verify digital signatures. Public keys and signatures are public while private keys remain secret.

The [IOTA Signing Scheme](https://github.com/iotaledger/iri/blob/dev/src/main/java/com/iota/iri/crypto/ISS.java) as
implemented in IRI and most libraries can be cumbersome and different from what one could expect from an asymmetric
cryptography API. This RFC then propose to replace the existing methods with a more traditional set of traits enforcing
a shared and expected behaviour.

## Seed

As explained earlier, the seed is the root of the hierarchical deterministic wallet and all public/private keys can be
derived from it. **It must then be kept secret**. In the IOTA protocol, a seed is sequence of 81 trytes like `"PUEOTSEITFEVEWCWBTSIZM9NKRGJEIMXTULBACGFRQK9IMGICLBKW9TTEVSDQMGWKBXPVCBMMCXWMNPDX"` (**DO NOT USE THIS SEED**).

The seed is a critical component of the signing scheme. Everywhere a seed is needed as input, the following `Seed`
type must be used only and no other representation like string, bytes or trits. This is why the following design only allows valid and verified instantiation of the `Seed` type.

```rust
// TODO documentation
pub struct Seed([i8; 243]);

// TODO documentation
#[derive(Debug, PartialEq)]
pub enum SeedError {
    InvalidLength(usize),
    InvalidTrit(i8),
}

// TODO documentation
impl Seed {
    // TODO documentation
    pub fn new() -> Self {
      unimplemented!();
    }

    // TODO documentation
    pub fn subseed<S: Sponge + Default>(&self, index: u64) -> Self {
      unimplemented!();
    }

    // TODO documentation
    pub fn from_bytes(bytes: &[i8]) -> Result<Self, SeedError> {
      unimplemented!();
    }

    // TODO documentation
    pub fn to_bytes(&self) -> &[i8] {
      unimplemented!();
    }
}
```

## Sponge

Even though the following design doesn't depend on a sponge construction, the main signing scheme implementations
currently being used by the IOTA protocol - WOTS and MSS - heavily relies on it. For this reason, this RFC doesn't
directly rely on a `Sponge` trait but the example implementations shown below does.

<!-- TODO: provide a link when merged -->
The `Sponge` trait is detailed in the Hash RFC.

## Traits

This RFC proposes the traits `PrivateKeyGenerator`, `PrivateKey`, `PublicKey`, `Signature` and `RecoverableSignature`
together enforcing the following features: private key generation, public key generation, signing, signature
verification and public key recovery.

Associated types are being used to bind implementations of these traits together within a signing scheme as, for
example, a `PrivateKey` implementation of a signing scheme shouldn't be used with a `PublicKey` implementation of
another signing scheme.

Some signing schemes like `Ed25519` benefit from faster batch verification, justifying a later introduction of a batch
verifier trait, probably as a separate RFC.

### `PrivateKeyGenerator` trait

The creation of a private key differs a lot from a signing scheme to another in terms of parameters so there is no
consistent way of building one with a method enforced by the `PrivateKey` trait. Instead, the private key generation is
delegated to a specific `PrivateKeyGenerator` trait which has `PrivateKey` as an associated type.

A `PrivateKeyGenerator` implementation is expected to have all the specific parameters needed for the private key
generation (e.g. security level, depth, ...) embedded as attributes. It would usually itself be built with a builder
pattern. Once it is built, the `generate` method can be used, only requiring consistent parameters seed and index.

```rust
// TODO documentation
pub trait PrivateKeyGenerator {
    // TODO documentation
    type PrivateKey;

    // TODO documentation
    fn generate(&self, seed: &Seed, index: u64) -> Self::PrivateKey;
}
```

<!-- Reviewed -->

### `PrivateKey` trait

A private key is responsible for generating its public counterpart and signing messages; hence, having `PublicKey` and
`Signature` as associated types.

**A private key should remain secret.**

```rust
// TODO documentation
pub trait PrivateKey {
    // TODO documentation
    type PublicKey;
    // TODO documentation
    type Signature;

    // TODO documentation
    fn generate_public_key(&self) -> Self::PublicKey;

    // TODO documentation
    fn sign(&mut self, message: &[i8]) -> Self::Signature;
}
```

<!-- TODO Note on mut self -->

### `PublicKey` trait

A public key is responsible for verifying the authenticity of a message signature; hence, having `Signature` as
associated type. It should also be able to serialise it to bytes.

```rust
// TODO documentation
pub trait PublicKey {
    // TODO documentation
    type Signature;

    /// Verifies the authenticity of a message signature
    ///
    /// # Parameters
    ///
    /// * `message` - A slice that holds the message to verify the signature of
    /// * `signature` - A signature to verify
    ///
    /// # Example
    ///
    /// ```
    /// let valid = public_key.verify(message, &signature);
    /// ```
    fn verify(&self, message: &[i8], signature: &Self::Signature) -> bool;

    // TODO documentation
    fn from_bytes(bytes: &[i8]) -> Self;

    /// Serialises a public key to a slice of bytes
    ///
    /// # Example
    ///
    /// ```
    /// let bytes = public_key.to_bytes();
    /// ```
    fn to_bytes(&self) -> &[i8];
}
```

### `Signature` trait

<!-- TODO -->

```rust
// TODO documentation
pub trait Signature {
    // TODO documentation
    fn size(&self) -> usize;

    // TODO documentation
    fn from_bytes(bytes: &[i8]) -> Self;

    // TODO documentation
    fn to_bytes(&self) -> &[i8];
}
```

### `RecoverableSignature` trait

<!-- TODO -->

```rust
// TODO documentation
pub trait RecoverableSignature {
    // TODO documentation
    type PublicKey;

    // TODO documentation
    fn recover_public_key(&self, message: &[i8]) -> Self::PublicKey;
}
```

## Implementation & workflow

This section gives example skeleton implementations of these traits and workflows for WOTS and MSS.

### WOTS example

#### Structures and implementations

<!-- TODO WotsError -->

```rust
#[derive(Default)]
pub struct WotsPrivateKeyGeneratorBuilder<S> {
    security_level: Option<u8>,
    _sponge: PhantomData<S>,
}

#[derive(Default, Debug)]
pub struct WotsPrivateKeyGenerator<S> {
    security_level: u8,
    _sponge: PhantomData<S>,
}

pub struct WotsPrivateKey<S> {
    state: Vec<i8>,
    _sponge: PhantomData<S>,
}

pub struct WotsPublicKey<S> {
    state: Vec<i8>,
    _sponge: PhantomData<S>,
}

pub struct WotsSignature<S> {
    state: Vec<i8>,
    _sponge: PhantomData<S>,
}

impl<S: Sponge + Default> WotsPrivateKeyGeneratorBuilder<S> {
    pub fn security_level(&mut self, security_level: u8) -> &mut Self {
        unimplemented!();
    }

    pub fn build(&mut self) -> Result<WotsPrivateKeyGenerator<S>, String> {
        unimplemented!();
    }
}

impl<S: Sponge + Default> crate::PrivateKeyGenerator for WotsPrivateKeyGenerator<S> {
    type PrivateKey = WotsPrivateKey<S>;

    fn generate(&self, seed: &Seed, index: u64) -> Self::PrivateKey {
        unimplemented!();
    }
}

impl<S: Sponge + Default> crate::PrivateKey for WotsPrivateKey<S> {
    type PublicKey = WotsPublicKey<S>;
    type Signature = WotsSignature<S>;

    fn generate_public_key(&self) -> Self::PublicKey {
        unimplemented!();
    }

    fn sign(&mut self, message: &[i8]) -> Self::Signature {
        unimplemented!();
    }
}

impl<S: Sponge + Default> crate::PublicKey for WotsPublicKey<S> {
    type Signature = WotsSignature<S>;

    fn verify(&self, message: &[i8], signature: &Self::Signature) -> bool {
        unimplemented!();
    }

    fn from_bytes(bytes: &[i8]) -> Self {
        unimplemented!();
    }

    fn to_bytes(&self) -> &[i8] {
        unimplemented!();
    }
}

impl<S: Sponge + Default> crate::Signature for WotsSignature<S> {
    fn size(&self) -> usize {
        unimplemented!();
    }

    fn from_bytes(bytes: &[i8]) -> Self {
        unimplemented!();
    }

    fn to_bytes(&self) -> &[i8] {
        unimplemented!();
    }
}

impl<S: Sponge + Default> crate::RecoverableSignature for WotsSignature<S> {
    type PublicKey = WotsPublicKey<S>;

    fn recover_public_key(&self, message: &[i8]) -> Self::PublicKey {
        unimplemented!();
    }
}
```

#### Workflow

<!-- TODO Different kind of workflows -->
<!-- TODO Workflow all  the funcs -->
<!-- TODO new seed -->

```rust
let private_key_generator = WotsPrivateKeyGeneratorBuilder::<Kerl>::default().security_level(2).build().unwrap();
let mut private_key = private_key_generator.generate(seed, 0);
let public_key = private_key.generate_public_key();
let signature = private_key.sign(message);
let recovered_public_key = signature.recover_public_key(message);
let valid = public_key.verify(message, &signature);
```

### MSS example

#### Structures and implementations

```rust
#[derive(Default)]
pub struct MssPrivateKeyGeneratorBuilder<S, G> {
    depth: Option<u8>,
    generator: Option<G>,
    _sponge: PhantomData<S>,
}

pub struct MssPrivateKeyGenerator<S, G> {
    depth: u8,
    generator: G,
    _sponge: PhantomData<S>,
}

pub struct MssPrivateKey<S, K> {
    depth: u8,
    index: u64,
    keys: Vec<K>,
    tree: Vec<i8>,
    _sponge: PhantomData<S>,
}

pub struct MssPublicKey<S, K> {
    state: Vec<i8>,
    depth: u8,
    _sponge: PhantomData<S>,
    _key: PhantomData<K>,
}

pub struct MssSignature<S> {
    state: Vec<i8>,
    index: u64,
    _sponge: PhantomData<S>,
}

impl<S, G> MssPrivateKeyGeneratorBuilder<S, G>
where
    S: Sponge + Default,
    G: PrivateKeyGenerator,
{
    pub fn depth(&mut self, depth: u8) -> &mut Self {
        unimplemented!();
    }

    pub fn generator(&mut self, generator: G) -> &mut Self {
        unimplemented!();
    }

    pub fn build(&mut self) -> MssPrivateKeyGenerator<S, G> {
        unimplemented!();
    }
}

impl<S, G> crate::PrivateKeyGenerator for MssPrivateKeyGenerator<S, G>
where
    S: Sponge + Default,
    G: PrivateKeyGenerator,
    <G as PrivateKeyGenerator>::PrivateKey: PrivateKey,
    <<G as PrivateKeyGenerator>::PrivateKey as PrivateKey>::PublicKey: PublicKey,
{
    type PrivateKey = MssPrivateKey<S, G::PrivateKey>;

    fn generate(&self, seed: &Seed, index: u64) -> Self::PrivateKey {
        unimplemented!();
    }
}

impl<S, K> crate::PrivateKey for MssPrivateKey<S, K>
where
    S: Sponge + Default,
    K: PrivateKey,
    <K as PrivateKey>::PublicKey: PublicKey,
    <K as PrivateKey>::Signature: Signature,
    <<K as PrivateKey>::PublicKey as PublicKey>::Signature: Signature + RecoverableSignature,
    <<<K as PrivateKey>::PublicKey as PublicKey>::Signature as RecoverableSignature>::PublicKey:
        PublicKey,
{
    type PublicKey = MssPublicKey<S, K::PublicKey>;
    type Signature = MssSignature<S>;

    fn generate_public_key(&self) -> Self::PublicKey {
        unimplemented!();
    }

    fn sign(&mut self, message: &[i8]) -> Self::Signature {
        unimplemented!();
    }
}

impl<S, K> MssPublicKey<S, K>
where
    S: Sponge + Default,
    K: PublicKey,
{
    pub fn depth(mut self, depth: u8) -> Self {
        unimplemented!();
    }
}

impl<S, K> crate::PublicKey for MssPublicKey<S, K>
where
    S: Sponge + Default,
    K: PublicKey,
    <K as PublicKey>::Signature: Signature + RecoverableSignature,
    <<K as PublicKey>::Signature as RecoverableSignature>::PublicKey: PublicKey,
{
    type Signature = MssSignature<S>;

    fn verify(&self, message: &[i8], signature: &Self::Signature) -> bool {
        unimplemented!();
    }

    fn from_bytes(bytes: &[i8]) -> Self {
        unimplemented!();
    }

    fn to_bytes(&self) -> &[i8] {
        unimplemented!();
    }
}

impl<S: Sponge + Default> MssSignature<S> {
    pub fn index(mut self, index: u64) -> Self {
        unimplemented!();
    }
}

impl<S: Sponge + Default> crate::Signature for MssSignature<S> {
    fn size(&self) -> usize {
        unimplemented!();
    }

    fn from_bytes(bytes: &[i8]) -> Self {
        unimplemented!();
    }

    fn to_bytes(&self) -> &[i8] {
        unimplemented!();
    }
}
```

#### Workflow

<!-- TODO Different kind of workflows -->
<!-- TODO Workflow all  the funcs -->

```rust
let wots_private_key_generator = WotsPrivateKeyGeneratorBuilder::<Kerl>::default().security_level(2).build().unwrap();
let mss_private_key_generator = MssPrivateKeyGeneratorBuilder::<Kerl, WotsPrivateKeyGenerator<Kerl>>::default().depth(7).generator(wots_private_key_generator).build().unwrap();
let mut private_key = mss_private_key_generator.generate(seed, 0);
let public_key = private_key.generate_public_key();
let signature = private_key.sign(message);
let valid = public_key.verify(message, &signature);
```

# Drawbacks

<!-- TODO -->

# Rationale and alternatives

<!-- TODO -->

+ This design fits the standards and expected APIs;
+ The main alternative is the current implementation of ISS as in IRI and most libraries;

# Unresolved questions

<!-- TODO -->

+ Should `PrivateKey` and `PublicKey` traits be prefixed with `Signing` since encryption keys are expected to be
developed at some point (e.g. NTRU for MAM) ?
+ Should the generator generate a pair of keys ? Is this always possible to generate the public key from the private
key ?
+ The proposed design relies on the sponges implementing `Default` which for example doesn't allow different number of
rounds for Curl unless Curl27 and Curl81 are types.
+ How should serialisation/deserialisation be handled ? `to_bytes` ? `From`/`Into` ? `Serde` ?
+ Should return values always be wrapped in Result ?
+ Should signature be padded ?