Q:

How is SPHINCS Hash-based signature "stateless"?

I really hope someone can help me with these questions related to SPHINCS.
I am trying to understand the concept of “stateless” vs. “stateful” signature scheme which is the basis of SPHINCS. I went to read Chapter 6.4 of Goldreich’s Foundations of Cryptography, Volume 2. In page 546, image attached with this question, he gives a small example of one parent node x authenticating two children nodes, x_0 and x_1.

Here are my questions:
Q1: node x generates (S_x, V_x) pair where S_x is the Secret Key and V_x is the Public Key. Then node x generates two additional pairs (S_x0,V_x0 )  and (S_x1,V_x1) for nodes x_0  and x_1, respectively. Is there is any relationship between S_x  and S_x0,S_x1 other than the fact that they use the same G(1^n) ?
Q2: the public key is only V_x?
Q3: signing only occurs with children nodes. Say I sign α with S_x0, thus the signature is going to be σ=f_Sx0(α),V_x0,auth_x0  where auth_x0= f_Sx(V_x0) ?
Q4: In SPHINCS, can we assume that all private keys are also generated with the same G(1^n) ? and thus we are always going to generate the same private keys given the same seed? Thus the “stateless” came from?
Thank you very much 

A:

I don't have Goldreich in front of me, however it would appear that he is discussing something rather different from a Merkle tree (at least, as it appears in a hash based signature method).
In those Merkle trees, the trees are built bottom-up, not top-down.  That is, the top nodes don't define the values that the child nodes hold; instead, the top node value is a (oneway) function of the child nodes.  In addition, the value that a node has is potentially public (that is, we don't mind if someone learns it); there is no secret component to it.  The only secrets are the private keys to the one time (or few time) signatures at the bottom of each Merkle tree.
As for the difference between stateful and stateless based based signature methods:

Stateful schemes have a Merkle tree (or tree of trees) with a number of one-time signatures at the bottom; each one-time signature can be used (you guessed it) once; hence the signer needs to keep track of which ones he has used; that is, when he uses a one-time signature to sign a message, he must update his state.
Stateless schemes (such as Sphincs) has a large tree-of-trees; but at the bottom, they have a number of few time signatures (Sphincs uses HORST); each such few time signature can sign several messages.  So, when Sphincs signs a message, the signer picks a random few-time-signature, uses that to sign the message, and then authenticates that through the Merkle trees up to the root (which is the public key).  Since we are using a few-time signature, we don't mind if we pick the same few-time signature multiple times on occasion; the few time signature scheme can handle it.  And, since we don't need to update any state when generating a signature, this is considered "stateless".

