Skip to content

Add verification #18

Description

@tcoratger

Depends on the message encoding, the one-time signature and the Merkle tree landing first.

A public key is a 16-byte Merkle root plus a 16-byte public parameter. A signature is 42 chain values, a 24-byte randomizer, and 32 Merkle siblings. Verification takes those, a 32-byte message and an epoch, and answers yes or no:

  1. Recompute the 42 digits from the public parameter, the message, the signature's randomizer and the epoch. Reject if the digest is inadmissible.
  2. For each chain i, walk 7 - x_i steps from the signature's i-th value. That gives the claimed public value of chain i.
  3. Hash the 42 claimed public values into a leaf.
  4. Climb 32 levels. At level l, if bit l of the epoch is zero the current node is the left child and the signature's l-th sibling is the right one; otherwise the other way round. The parent is Th(P, tweak(type 3, l+1, epoch >>> (l+1)), left || right).
  5. Accept if and only if the result equals the root in the public key.

The cost is a constant 133 hashes: 1 for the encoding, 99 for the chains, 1 for the leaf, 32 for the climb. Constant because the digits always sum to 195, which is what makes the aggregation circuit a fixed size.

Two interface points. Verification should return a Bool, not a result type: bytes that fail to parse are the serialization layer's error, and which step of a well-formed signature failed first carries no consensus meaning, so exposing it only invites callers to branch on it. And nothing here needs to be constant-time — every value it touches is public.

Goes in EthCryptographySpecs/Xmss/Verify.lean. Reference implementation: verify in crates/xmss/src/xmss.rs.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions