Fail-stop signature scheme with bottom-up tree authentication

Thin black arrows denote the relation between a one-time secret key and the corresponding one-time main public key, broad grey arrows denote one-time signatures, and the tree is constructed by repeatedly hashing pairs of values. Values skjemp are abbreviated as sk. 

For instance, the complete correct signature j on m3 consists of the encircled nodes. To test it, the recipient s entity reconstructs the nodes in squares. 

Signing For any j N, the complete correct new signature 5 on the y-th message, ntj, contains 

Test To test a new signature s of the form described above, one first tests the one-time signature sj with respect to the claimed value mkj. Then one reconstructs the values on the path to the root and tests if this path ends at the correct main public key mk. (That is, one starts by hashing mkj and its claimed neighbour, and iteratively hashes each intermediate result with its claimed neighbour until one obtains a value mk that should be the root value this is compared with mk. ) 

To make the components polynomial-time in the interface inputs alone, each value mkj that is received in a signature is first tested with mk test, and it is verified that each value that should be an inner node of the tree, and thus a hash value, is of length len° k). Similarly, a collision in a valid proof of forgery must either consist of acceptable one-time main public keys or values of length len°(k).  

---

Figure 10.1. Fail-stop signature scheme with bottom-up tree authentication.

---