mutual-exclusion Documentation

1. Project Overview & Quickstart (QuipNetwork/mutual-exclusion) Copy Chapter

Technical Documentation: QuipNetwork/mutual-exclusion

ℹ️ Provenance: Multi-Tier Ingestion · CodeWiki Reference

mutual-exclusion

Agent Skills & Rules Copy Section

• Discovered 21 agent rule(s) and prompt configurations.

--- METRICS ---

• Files Extracted: 1
• Estimated Token Budget: ~26 tokens
• Canonical Reference: https://codewiki.google/github.com/QuipNetwork/mutual-exclusion

2. Official Technical Reference & Guides (QuipNetwork/docs) Copy Chapter

File: README.md Copy Chapter

Repository Documentation

This folder contains high-level documentation for our repositories. Each file documents a single repository.

General Documentation links and websites:

• https://developers.quip.network/docs - Published docs site
• https://gitlab.com/piqued/gitbook - the git repo backing the published docs site.
• https://quip.network/ - the website
• https://quip.locker/ and https://vault.quip.network/ - the smart wallet app
• https://quantumdoomclock.com/ - QDC newsletter site
• [TODO: add others as needed]

File Naming Convention Copy Chapter

Each documentation file should be named after the repository it describes:

{repository-name}.md

For example, a repository named hashsigs-rs would have a documentation file named hashsigs-rs.md.

Document Format Copy Chapter

Each documentation file should follow this structure:

Header Table Copy Section

Start with a level-1 heading (the repository name) followed by a metadata table:

# repository-name

| Field | Value |
|-------|-------|
| **Clone** | `git clone [email protected]:org/repository-name.git` |
| **URL** | https://gitlab.com/org/repository-name |

## Description

A high-level description of what this repository does...

Required Fields Copy Section

Description Section Copy Section

The ## Description section should contain a high-level overview of:

• What the repository does
• Its primary purpose
• Key functionality

Keep descriptions concise but informative. Avoid implementation details.

Adding New Documentation Copy Chapter

1. Create a new file named {repository-name}.md
2. Copy the header table template above
3. Fill in the Clone and URL fields with the correct GitLab paths
4. Write a high-level description of the repository

Example Copy Chapter

See below for a complete example:

# hashsigs-rs

| Field | Value |
|-------|-------|
| **Clone** | `git clone [email protected]:piqued/hashsigs-rs.git` |
| **URL** | https://gitlab.com/piqued/hashsigs-rs |

## Description

A Rust implementation of WOTS+ (Winternitz One-Time Signature) scheme, with Solana program support.

NOTE: Automation (LLM generation) is totally encouraged but PLEASE do your best to make sure it's concise and accurate. The whole point of this is to save people time. If you run across something that is not doing it, highlight it so we can fix it.

File: hashsig.md Copy Chapter

hashsig

Description Copy Chapter

The hashsig project provides a family of consistent WOTS+ implementations across multiple languages (TypeScript, Solidity, Rust, C++, and Python), with the TypeScript version serving as the reference implementation. While inspired by the standardized WOTS+ construction in RFC 8391 [3] (as used in XMSS), these implementations intentionally follow a lighter-weight design closer to the original 2017 WOTS+ paper [2], simplifying PRF inputs, address handling, and mask derivation to better fit practical constraints such as smart contracts and cross-platform portability, while preserving the core cryptographic structure and correctness of WOTS+ signing and verification.

Table of Contents Copy Chapter

• 1. Overview

• 2. Entities

  • 2.1. Constants
  • 2.2. PublicKey
  • 2.3. WOTSPlus
    • prf(seed, index)
    • xor(a, b)
    • chain(prev_chain_out, randomization_elements, index, step)
    • compute_message_hash_chain_indexes(message)
    • generate_key_pair(private_seed)
    • get_public_key(private_key)
    • get_public_key_with_public_seed(private_key, public_seed)
    • generate_randomization_elements(public_seed)
    • sign(private_key, message)
    • verify()
    • verify_with_randomization_elements()

• 3. Comparison

  • 3.1. Constants
  • 3.2. Message Processing (Base-w conversion)
  • 3.3. PRF
  • 3.4. Randomization Elements (Masks)
  • 3.5. Chain Function
  • 3.6. Public Key Construction
  • 3.7. Signature Generation & Verification

• 4. Future Improvements

  • 4.1. Synchronization and Cleanup
  • 4.2. Toward a Formal Proof
  • 4.3. Replay Attack Prevention in Blockchain Contexts
    • Scenario 1
    • Scenario 2
    • Scenario 3
    • Scenario 4

• 5. References

1. Overview Copy Chapter

Winternitz One-Time Signature Plus (WOTS+) [2] is a hash-based, post-quantum digital signature scheme that achieves security solely from the assumed one-wayness and collision resistance of cryptographic hash functions. It operates by encoding a message into base-w digits, extending it with a checksum, and signing each digit using truncated hash chains derived from a secret seed; verification recompletes the remaining steps of each chain to reconstruct the public key.

In this document, we describe the core entities and design choices underlying the hashsig implementations and provide a detailed comparison against the RFC 8391 specification [3]. We conclude by outlining potential future improvements aimed at strengthening formal security guarantees, improving cross-implementation consistency, and mitigating corner-case replay attacks in practical deployment scenarios.

2. Entities Copy Chapter

2.1. Constants Copy Section

This module set the constraints to default Winternitz+ parameters mentioned in the RFC-8391 document.

2.2. PublicKey Copy Section

pub public_seed: [u8; constants::HASH_LEN],
    pub public_key_hash: [u8; constants::HASH_LEN],

provides serialization/deserialization functions. to_byte() and from_byte().

2.3. WOTSPlus Copy Section

The main flow of the Winternitz protocol happens here.

```prf(seed, index) -> [u8; constants::HASH_LEN]```

Given a seed and index generates an input in the form of

input[0] = 0x03; // prefix to domain separate
input[1..33].copy_from_slice(seed); // the seed input
input[33..].copy_from_slice(&index.to_be_bytes());

and then will hash it and returns

out <- H(input)

```xor(a,b)```

• Outputs the element-wise binary XOR of two Vec with the size HASH_LEN.

```chain(prev_chain_out, randomization_elements, index, step)```

"
This is the core of WOTS+, implementing the hash chain with randomization
The chain function takes the previous chain output, XORs it with a randomization element, and then hashes the result. This is repeated 'steps' times.
"
The flow of this function has been described in sign() function.

```compute_message_hash_chain_indexes(message) -> chain_segment_indexes```

Given the message

• converts message into base-CHAIN_LEN chain_segment_indexes

• Computes checksum of the chain_segment_indexes by

checksum = SUM(CHAIN_LEN - 1 - chain_segment_indexes[i])

• Converts the checksum to base-CHAIN_LEN

• Append checksum to chain_segment_indexes

```generate_key_pair(private_seed)```

• Generates private_key from private_seed.

private_key = H(private_seed)

```get_public_key(private_key) -> PublicKey```

• Generates public_seed from private_key:

public_seed = prf(private_key, 0)

• Generates public_key by

public_key = get_public_key_with_public_seed(private_key, public_seed)

```get_public_key_with_public_seed(private_key, public_seed)```

• Generates randomization elements by

elements = generate_randomization_elements(public_seed)

• Assigns function_key to the first element of elements.

function_key = elements[0]

• Creates public_key_segments with the capacity of signature size.

• Converts message to chain indexes including checksum.

• For each chain index

  • Generates the secret key segment
  • Run the function to the index position.

```generate_randomization_elements(public_seed) -> randomization_elements```

• Creates a Vec with the size of number of signature chucks (NUM_SIGNATURE_CHUNKS)

• Fills out each element with

randomization_elements[i] = prf(public_seed, i)

```sign(private_key, message) -> signature```

• Generates public_seed from private_key by

public_seed = prf(private_key, 0)

• Generates randomization_elements from public_seed by

randomization_elements[i] = prf(public_seed, i)

• Computes the indexes on the chains given the message by

chain_segments = compute_message_hash_chain_indexes(message)

• Iterates through chain_segments

  • Constructs to_hash by
  text Copy

  to_hash[0:HASH_LEN] = prf(public_seed, 0)
      to_hash[HASH_LEN: 2 * HASH_LEN] = prf(private_key, i + 1)

  • Constructs secret_key_segment, first element of i-th hash chain

  • Traverse through the chain chain_segments[i] times, by

  text Copy

  next_item = H(prev_item XOR prf(public_seed, j))

  where j is in [0, chain_segments[i]].

  • append the last item to signature

• Returns the signature

```verify(public_key, message, signature)```

• Reconstructs randomization_elements based on public_seed
• Reconstructs public_key based on message_chunks and signature_chunks by

pk_i = chain(sig_i, w−1−a_i)

• Exactly mirroring signing flow and checking if it matches

computed_hash = H(pk_0 || pk_1 || ... || pk_(len−1))

3. Comparison Copy Chapter

There are a few modifications to the standardized version of Winternitz+ that has been described in RFC-8391.

3.1. Constants Copy Section

🟢 Complete Match

RFC 8391

n = hash output length (commonly 32 bytes)
    w in {4, 16} (Winternitz parameter)
    len_1 = ceil(8n / log₂(w))
    len_2 = floor(log₂(len_1 (w−1)) / log₂(w)) + 1
    len = len_1 + len_2

Quip

HASH_LEN = 32
    CHAIN_LEN = 16 (w = 16)
    LG_CHAIN_LEN = 4
    NUM_MESSAGE_CHUNKS = 64
    NUM_CHECKSUM_CHUNKS = 3
    NUM_SIGNATURE_CHUNKS = 67

3.2. Message Processing (Base-w conversion) Copy Section

• 🟢 Correct base-16 expansion
• 🟢 Correct checksum definition
• 🟢 Correct left-aligned checksum expansion

RFC 8391

Message digest M is converted to base-w representation

Each symbol in [0, w−1]
Checksum = Sum(w − 1 − msg[i])

Checksum is also base-w encoded, most significant digit first

Quip

chain_segments_indexes[idx]     = byte >> 4;
chain_segments_indexes[idx + 1] = byte & 0x0f;

3.3. PRF Copy Section

🟡 We rely on W-OTS+ 2017 paper [2] proofs and constructions.

RFC 8391

Each WOTS+ secret key element is derived as:

sk[i] = PRF(SK_seed, ADRS)

Where PRF is a keyed hash, ADRS is a structured address containing:

{chain index, hash index}

Quip

In Quip we have:

secret_key_segment = H(
    function_key || PRF(private_key, i+1)
)

3.4. Randomization Elements (Masks) Copy Section

• 🟢 provides basic masking
• 🟡 loses collision resistance guarantees expected by XMSS proofs

RFC 8391

For each chain step:

tmp = F(tmp ⊕ bitmask)

Where:

bitmask = PRF(PUB_seed, ADRS)

and ADRS includes chain index and hash index

Quip

randomization_elements[i] = PRF(public_seed, i)

Used as:

xored = chain_out ⊕ randomization_elements[i + index]

3.5. Chain Function Copy Section

• 🟢 Functionally equivalent hash-chain behavior.
• 🟡 Mask derivation is weaker than XMSS proofs.

RFC 8391

c_k^i(x) = F(x ⊕ bitmask(i,k))

Quip

for i in 1..=steps {
    xored = chain_out ⊕ randomization_elements[i + index]
    chain_out = H(xored)
}

3.6. Public Key Construction Copy Section

• 🟢 Correct structure
• 🟢 Publickey construction matches WOTS+ 2017 paper [2]

RFC 8391

• Each chain runs to w−1
• All chain outputs are concatenated
• Final public key = H(concat(pk_i))

Quip

segment = chain(sk_i, ..., w-1)
public_key_hash = H(all_segments)

3.7. Signature Generation & Verification Copy Section

• 🟢 Matching Message encoding
• 🟢 Mathematically correct
• 🟢 Verifies correctly

RFC 8391

• Converts M into base-w digits and appends a checksum:

a_0, a_1, ..., a_(len−1)   where each a_i ∈ [0, w−1]

• Each secret key element is derived as:

sk_i = PRF(SK_seed, ADRS(chain=i))

• Each signature element is computed as:

sig_i = chain(sk_i, a_i)

Where the chain function is:

chain(x, t):
    for j = 0 to t−1:
        x = F(x ⊕ PRF(PUB_seed, ADRS(chain=i, hash=j)))
    return x

Quip

• Message encoding

Same as RFC:

a_0, a_1, ..., a_(len−1)

• Secret key element derivation

public_seed = PRF(private_key, 0)
function_key = randomization_elements[0]

sk_i = H(
    function_key || PRF(private_key, i+1)
)

• Signature generation

sig_i = chain(sk_i, a_i)

Where:

chain(x, t):
    for j = 1..t:
        x = H(x ⊕ randomization_elements[j])

4. Future improvements Copy Chapter

4.1. Synchronization and cleanup Copy Section

Hashsig codebase has a few similar but not identical implementations of WOTS+ [2] specifically

• relations between private_key and public_seed and public_key.
• parameter encoding in prf across our multiple implementations of hashsig library.

It is recommended to

• have a ground truth implementation and sync all the other implementation with it
• add more comments throughout the code
• Make module encapsulation match the WOTS+ 2017 paper.

4.2. Toward a Formal Proof Copy Section

|It is important to note that the current implementation is conceptually based on the original WOTS+ construction introduced in the 2017 WOTS+ paper, rather than being a strict implementation of the RFC 8391 instantiation used in XMSS. While the core ideas such as hash chains, base-w message encoding, and checksums are preserved, some proof-oriented design constraints introduced in RFC 8391 are not fully carried over.|

The security proof of RFC 8391 (WOTS+/XMSS) relies on a small set of well-defined assumptions:

• One-wayness of the hash function
• Security of the PRF
• Strict address (domain) separation

Under these assumptions, the proof can reduce existential forgery to standard cryptographic primitives. In RFC 8391, the PRF is invoked as:

PRF(seed, ADRS)

where ADRS is a structured address encoding: the role (e.g., chain, mask, key derivation), the chain index, and the hash step index. This structure guarantees that each PRF call is unique and role-separated, allowing the proof to treat PRF outputs as independent random values.

In the current implementation:

• We do not have this addressing format, however, we are using simpler and more efficient version that has been described in WOTS+ 2017. Additionally the same PRF construction is reused across different roles.

• PRF outputs are chained into the same hash function:

sk_i = H(function_key || PRF(private_key, i))

This coupling prevents the standard hybrid argument used in RFC 8391, where PRF outputs can be replaced by random values without affecting the adversary’s view.

To go toward a a formal proof, it is recommended to

• Introduce a structured address format (ADRS) with explicit role, chain, and step separation suitable to out WOTS+ implementation.
• Apply strict domain separation for all PRF and hash invocations.
• Ensure that masks and PRF outputs are NEVER reused across logical domains.
• Avoid feeding PRF outputs directly into the same hash oracle without separation.

4.3. Replay Attack Prevention in Blockchain Contexts Copy Section

When used in Quip, Web3, or smart contract contexts, the same considerations discussed above can lead to potential replay attacks. While the current implementation makes reasonable security trade-offs, we document them here and note that there is clear room for improvement to better align the security guarantees with the proofs in [2], [4].

scenario 1

Same signature valid across:

• Different chains
• Different contracts
• Different message domains

This behavior is intentional for certain flows, such as the swap protocol. In the swap protocol, we explicitly want the same signatures to be valid across different chains. However, it may still be desirable to restrict their validity to the swap context only, rather than allowing them to be reused arbitrarily.

scenario 2

1. Same private key signs two different messages M₁, M₂
2. Attacker observes two signatures
3. For each chain index i, attacker sees:

sig_i(M₁) = c^a(sk_i)
sig_i(M₂) = c^b(sk_i)

If a ≠ b, attacker can compute:

c^max(a,b)(sk_i)

4. Over enough indices, attacker reconstructs full public key chains

5. Attacker forges a signature on arbitrary messages

scenario 3

1. Developer reuses the same private seed for:

   • This WOTS+ scheme
   • Another hash-based construction (e.g., PRF, commitment, MAC)

2. Attacker observes outputs from both protocols.

3. Attacker correlates:

   • PRF(seed, i) ↔ H(seed || i)

Cross-protocol leakage reduces entropy of secret material

scenario 4

1. Attacker collects many signatures

2. Observes that:

   • Same mask reused across different chains
   • Same mask reused across different messages

3. Attacker computes:

H(x ⊕ m) ⊕ H(y ⊕ m)

It leads to structural relations leak:

• Relative chain positions
• Differences between secret key segments

and eventually and through time it will reduced security margin and enables future cryptanalysis.

To mitigate these problems, it is recommended to

• Introduce a structured address format (ADRS) with explicit role, chain, and step separation.
• Apply strict domain separation for all PRF and hash invocations.
• Ensure that masks and PRF outputs are NEVER reused across logical domains.
• Avoid feeding PRF outputs directly into the same hash oracle without separation.

5. References Copy Chapter

1. XMSS — A Practical Forward-Secure Signature Scheme Based on Minimal Security Assumptions (2011)
   Johannes Buchmann, Erik Dahmen, Andreas Hülsing.
   Post-Quantum Cryptography (PQCrypto 2011).

2. W-OTS+ — Shorter Signatures for Hash-Based Signature Schemes (2017)
   Andreas Hülsing.

3. RFC 8391 — XMSS: eXtended Merkle Signature Scheme (2018)
   Andreas Hülsing, Denis Butin, Shay Gueron, et al.
   IETF RFC 8391, May 2018.

4. A Tight Security Proof for SPHINCS+, Formally Verified (2024)
   Manuel Barbosa, François Dupressoir, Andreas Hülsing, Matthias Meijers, and Pierre-Yves Strub.