LP-4106: Threshold Lamport Protocol

Abstract

This LP specifies a public, coordinatorless, 2-round threshold protocol that outputs a standard Lamport one-time signature verifiable by LP-4105. Signers never deliver plaintext shares to a trusted "MPC box". Instead, they post commitments and encrypted contributions to the LUX chain (bulletin board). After ≥t participants contribute for a session, the chain finalizes a Lamport signature for a canonical on-chain WithdrawalIntentHash, which can be relayed and verified on an EVM chain with exactly one Lamport verification.

Important correction: the Lamport signature is a set of preimages. Those preimages necessarily become public at finalization. The security goal is that no party learns both branches (0/1 secrets) for a leaf unless ≥t parties collude, and that signers cannot be tricked into signing different messages for the same session.

Motivation

LP-4105 defines Lamport OTS for Lux Safe but assumes a single signer. Production deployments require threshold control where:

T-of-N parties must cooperate
No trusted assembler collects plaintext shares
Anti-equivocation: a malicious leader/block producer cannot show different messages to different signers
On-chain coordination: chain acts as bulletin board and enforces session rules
Post-quantum authorization on destination chains (hash-based)

Threat Model and Security Goals

Assume an adversary can:

control/DoS some signers,
attempt equivocation (show different messages to different signers),
attempt to learn enough information to forge signatures for new messages.

Goals

G1 (Anti-equivocation): the only signable digest is derived from finalized on-chain state, so all honest signers necessarily bind to the same message.

G2 (Threshold unforgeability for a leaf): with < t corrupt signers, the adversary cannot compute a valid Lamport signature for any message other than the one finalized by the protocol for that leaf.

G3 (No trusted assembler): no single party receives all plaintext contributions; only the final Lamport signature is revealed publicly.

G4 (Accountability): parties that commit but fail to contribute (or contribute garbage) can be identified and penalized.

Definitions and Notation

Symbol	Description
`n`	committee size (epoch validator set or configured signer set)
`t`	threshold required to finalize
`i`	Lamport bit index (0..255)
`b`	bit value (0 or 1)
`j`	signer index / validator
`r[j][i][b]`	signer j's secret share for bit i, branch b (32 bytes)
`S[i][b]`	leaf secret preimage for bit i, branch b
`PK[i][b]`	Lamport public key element = `H(S[i][b])`
`H()`	keccak256 (or another LP-4105-approved hash)
`leafIndex`	Lamport leaf number (single-use)
`epoch`	LUX epoch that defines committee membership
`PKH`	hash commitment to the Lamport public key (`H(PK[...])`)

Canonical Message to Sign (required)

To prevent "different message per signer" attacks, the signable digest MUST be derived from a finalized on-chain withdrawal intent:

WithdrawalIntentHash = keccak256(abi.encode(
    bytes32("LUX-WITHDRAW-V1"),
    srcChainId,
    dstChainId,
    burnTxHash,
    burnLogIndex,
    token,
    amount,
    recipient,
    nonce,
    epoch,
    leafIndex,
    nextPKH
));

epoch, leafIndex, nextPKH are enforced by the LUX contract.
No signer signs an off-chain "txHash" or leader-proposed blob.

Setup Phase (per leaf)

Each Lamport leaf has secrets:

S[i][b] = Σ_j r[j][i][b]  mod 2^256
PK[i][b] = H(S[i][b])

Each signer j samples r[j][i][b] ← random(32 bytes) for all i,b and stores only their own shares.

Publishing PKH (required)

The system MUST publish a commitment to the Lamport public key (or a Merkle/XMSS root committing to many leaves). Two acceptable approaches:

Option A (practical, small committees): MPC ceremony among signers to compute PK[i][b] (or PKH) without revealing S[i][b].

Option B (chain-coordinated): signers post commitments to their shares and the protocol includes an audit/dispute mechanism; publication may reveal some data if disputes occur.

This LP standardizes signing/finalization; key-generation ceremony details may be specified in an accompanying implementation note.

Protocol (2 rounds on LUX chain)

The protocol is implemented by a LUX contract (the "Coordinator" in the on-chain sense, not a trusted party). Any account can relay transactions; the contract enforces correctness.

Session Creation

A session is created for a specific WithdrawalIntentHash:

sessionId = keccak256(abi.encode(
    bytes32("LUX-LAMPORT-SESSION-V1"),
    WithdrawalIntentHash
));

The contract verifies the referenced withdrawal intent exists and is finalized.

Round 1 — Commit (bind signer + bind session)

Each signer j submits:

commit_j = H(
    bytes32("LUX-LAMPORT-COMMIT-V1") ||
    sessionId ||
    epoch || leafIndex ||
    WithdrawalIntentHash ||
    sharesRoot_j ||
    nonce_j
)

Where:

sharesRoot_j = H( r[j][*][*] for this leaf ) or a Merkle root over (i,b)→H(r[j][i][b])
nonce_j is signer-chosen randomness

Contract rules:

Accept commits only from the epoch committee.
Lock the participant set when ≥t commits are posted (or at a deadline).
Require a bond per signer to deter DoS.

Round 2 — Contribute (message-dependent, encrypted)

Let b_i = bit(WithdrawalIntentHash, i).

Each signer j posts ciphertexts:

ct_j[i] = ENC_to_committee( r[j][i][b_i], sessionId, i )

Requirements:

Ciphertexts MUST be addressed to a decryption committee corresponding to the epoch (e.g., threshold decryption key held by validators).
Plaintext shares MUST NOT be posted unless in a dispute.

Finalization — Threshold Reveal of the Lamport signature

When the contract has ≥t valid contributions for all 256 bits, the committee performs threshold decryption/reveal and publishes:

sig[i] = Σ_j r[j][i][b_i]  mod 2^256
Signature = sig[0..255]

The contract then emits:

event SignatureFinalized(
    bytes32 indexed sessionId,
    bytes32 indexed WithdrawalIntentHash,
    uint256 epoch,
    uint256 leafIndex,
    bytes32 nextPKH,
    bytes32[256] sig,
    bytes32 signersBitmap
);

Lamport verification condition (LP-4105 compatible):

∀i: H(sig[i]) == PK[i][b_i]

Accountability (required)

Encrypted contributions can be garbage. The protocol MUST include an enforceable mechanism to punish non-cooperative or dishonest signers.

A) Slash-on-failure with forced plaintext reveal (recommended default)

If finalization fails (missing bits / invalid signature / decryption failure), the contract opens a dispute window.

For any failing index i, a signer j can reveal:

plaintext r[j][i][b_i]
opening data proving it matches sharesRoot_j (Merkle branch or precommitted hash)
the nonce/opening that binds to commit_j

The contract verifies the reveal against commit_j material and:

slashes signers who did not contribute, or
slashes signers whose ciphertext cannot correspond to a valid committed share.

This is slow but implementable and enforceable.

B) ZK proof of well-formed encryption (optional)

Each ct_j[i] includes a proof that it encrypts a 32-byte value consistent with sharesRoot_j. This reduces disputes but increases complexity.

Key Rotation (required)

Lamport leaves are one-time. Each finalized signature commits to nextPKH.

Rules:

leafIndex MUST be single-use and monotonically increasing.
On finalization, the LUX contract updates currentPKH = nextPKH atomically.
Destination chain enforces the same rotation when verifying a withdrawal.

Recommended: use an XMSS/Merkle root committing to many Lamport leaves so destination stores one root and each withdrawal carries a Merkle proof for the leaf.

Message Format for Safe / Bridge Use

This LP does not sign arbitrary Safe tx bytes. It signs the canonical on-chain intent hash (anti-equivocation).

If integrating with Safe, the Safe module's "action" MUST be embedded into the intent (e.g., recipient/module/amount fields), and the intent hash is what gets signed.

Rationale / Notes

"No node ever reconstructs a Lamport preimage" is false if interpreted literally: the final Lamport signature is itself a set of preimages. The correct claim is: no single party learns both branch secrets for the leaf, and no trusted party receives all plaintext inputs.
The canonical intent hash is the decisive fix for the classic "leader sends different messages to different signers" attack.
Large validator sets should treat encryption/decryption as epoch infrastructure; small signer sets can run the same protocol off-chain (still 2 rounds) without posting ciphertexts on-chain.

Backwards Compatibility

This protocol produces standard Lamport signatures as defined in LP-4105. The on-chain verifier is unchanged:

// Same verification as single-signer Lamport
LamportLib.verify(message, signature, publicKey)

Only the off-chain signing process differs.

Test Cases

Test 1: 2-of-3 Signing

Setup:
  - 3 signers generate independent shares
  - Public key computed via MPC

Signing:
  - Two signers commit
  - Two signers contribute
  - Signature finalized via threshold reveal

Verification:
  - Standard Lamport verify on EVM with LP-4105 verifier returns true

Test 2: DoS - Missing Contribution

Setup:
  - Signer commits but doesn't contribute

Expected:
  - Timeout triggers dispute window
  - Non-contributing signer slashed after timeout
  - Remaining signers can restart if ≥ t

Test 3: Garbage Contribution

Setup:
  - Signer contributes malformed ciphertext

Expected:
  - Dispute reveal proves mismatch
  - Signer slashed
  - Session can restart with honest signers

Test 4: Equivocation Attempt

Setup:
  - Attacker attempts to show different messages to different signers

Expected:
  - Impossible: signers only sign WithdrawalIntentHash derived from finalized on-chain state
  - No off-chain message proposal accepted

Security Considerations

Preimage Revelation

The final Lamport signature is a set of preimages—these necessarily become public. The security goal is that:

No party learns both branch secrets (0/1) for any leaf position unless ≥t parties collude
Signers cannot be tricked into signing different messages for the same session

Threshold Security

With t-of-n threshold:

Any t parties can produce a valid signature
Fewer than t parties cannot forge a signature
Compromising t-1 parties reveals insufficient information for forgery

Anti-Equivocation

The canonical on-chain intent hash prevents the classic attack where a malicious leader shows different messages to different signers. All honest signers bind to the same finalized on-chain state.

Quantum Resistance

Security relies only on:

Preimage resistance of keccak256
Security of the threshold protocol

Both are believed quantum-resistant (keccak256 provides 128-bit security against Grover's algorithm).

Accountability and DoS Mitigation

Bonds required per signer to deter commit-but-don't-contribute attacks
Dispute mechanism allows identification and slashing of malicious signers
Session restart possible with different participant set

Threshold Lamport Protocol