playing with uniqueness


by arya dradjica on 2024-08-31 updated 2024-09-08

Daniel J. Bernstein has created a vast number of high-quality cryptographic primitives that have been accepted as state of the art, especially in pre-quantum cryptography. I was reading about the Ed25519 signature scheme when I noticed something interesting.

Ed25519 relies on a per-signature secret nonce, which is deterministically derived from the signer's key and the message being signed. The rationale for not using a randomly generated nonce is that any collision (the signing of two different messages with the same nonce) will immediately reveal the secret key and compromise the system. Rather than trying to avoid this property, I'd like to examine it as a feature: there is at most one message for every nonce.

Suppose that nonces were not derived from the message being signed, but rather from a sequence of increasing integers. For a particular integer in the sequence, only a single message can be signed. The signer is forced to make a cryptographically verifiable promise that this property holds, at the risk of losing their key. If each message includes a hash from the previous message(s), then messages can only be added in order. In effect, this is a cryptographically secure append-only log.

I think this concept could possibly be (ab)used to define some kind of simple digital ledger. An account is defined by an Ed25519 keypair, and is associated with an append-only log of transactions. Each transaction specifies the change in the account, the source/destination of the change, and a hash of the previous transactions. A ledger consisting of these accounts should be verifiable by anybody.

Performing a transaction between two accounts requires both sides to show each other they have signed new entries in their transaction logs, simultaneously. If an account A reveals their signed transaction entry earlier than B, then B can save the signature and halt communication. A cannot remove their entry in the transaction log, since B can reveal it publicly at any time. But without proof that B completed the transaction, A's transaction log is left in an inconsistent state.

Cryptographic contract signing protocols are designed to overcome this issue. When there is no trusted third party to mediate the communication, both sides gradually reveal their signatures over time (i.e. bit by bit). If communication fails at any point, both sides have similar amounts of information about each other's signatures, so neither side has an undue advantage. By leveraging the knowledge that each bit is part of an elliptic-curve signature, it is possible to verify them one by one.