How SPHINCS+ Hash Signature ADRS structure define

Question

can anyone help me to elaborate the structure of ADRS with example ( tree ADRS, layer ADRS, keypair ADRS etc)used to generate root SPHINCS+ signature. Also can some one help me to describe tree hash process used in SPHINCS+ with example.

Answer 1

Well, the ADRS structure is an 32 byte structure, organized as 8 4-byte words. It looks like:

  +--------------------+
  |   Layer address    |
  +--------------------+
  |    Tree address    |
  |      (3 words)     |
  |                    |
  +--------------------+
  |        Type        |
  +--------------------+
  |  Keypair address   |
  +--------------------+
  | Chain/Tree Height  |
  +--------------------+
  | Hash addr/Tree Idx |
  +--------------------+

The idea behind the ADRS structure is that every single hash computation within Sphincs+ gets a separate ADRS structure. Because the ADRS structure is an input to the hash, someone brute-forcing the hash computation would need to select the ADRS structure, which means that their brute-force search cannot take advantage of any multitarget attacks.

As for what the various fields within the ADR structure designate:

Layer address - Which Merkle tree level we are working on (0 is the lowest); also 0 if we're working within the FORS tree

Tree address - Which Merkle tree (counting from the left) in this level we are working on. This is used for FORS, WOTS and Merkle tree hashes.

Type - An indication of why we are doing this hash in the first place; this ensures that, say a hash we do for the FORS does not collide with a hash we're doing for the WOTS

Keypair address - Which WOTS leaf are we working on (counting from the left of the Merkle tree). Not used during a Merkle tree hash.

Chain/Tree Height - During WOTS, which Winternitz chain we are working on. During FORS, what height we are in the FORS tree (1 being the bottom). Unused during a Merkle tree hash.

Hash addr/Tree Idx - During WOTS, where in the Winternitz chain are we (with 0 being the first node in the chain). During FORS, the horizontal position of the node we're computing (counting all the FORS trees under the current WOTS leaf); the later includes both "where in the FORS tree we are hortizontally", as well as "which FORS tree this is". Unused during a Merkle tree hash.