I'm experimenting with MPC for SHRINCS and I got some impressive results for the stateful part: about 3 minutes to set up a 2/2 public key, and about 1 second to make a signature. The prototype is still vibe-coded, so it needs deeper verification, but overall it looks promising.
The hard part is the stateless fallback. I generated the top tree for it in MPC and it took about 1.5 hours. That is not impossible, but it is too expensive if it has to be done separately for each address. My idea is: could we reuse the same stateless tree across many addresses, so this work is done once per wallet rather than once per address?
One thing to take into account is that with this optimization all addresses in a wallet would share one stateless usage budget. Today that budget is per address. But if the budget is high enough and the stateless path is truly fallback-only, that may be acceptable.
There is one more problem, though: pk_seed is public and currently ties the stateful and stateless parts together.
As I understand it, the total public key today is PK = (pk_seed, pk_root). The same public pk_seed is used in both halves of the construction. It is used when building and verifying the stateful UXMSS/WOTS side, and it is also used when building and verifying the stateless FORS/XMSS side. The current global pk_root is also fed back into both sides. So I can't reuse one without reusing the other.
I propose making the main PK = Merkle_root(stateful_part, stateless_part), where each part includes its own pk_seed and pk_root. Then the stateful side would use only (pk_seed_sf, pk_root_sf), and the stateless side would use only (pk_seed_sl, pk_root_sl). The top-level Merkle root would be only the outer binding key. When spending via the stateful path, one would have to provide only the hash of the stateless_part, not the entire part, so this seems to preserve efficiency for the stateful path in terms of blockchain footprint.
An additional issue is privacy and linkability. I found a way to make stateful-only spends unlinkable: we can add a random component to the stateless_part struct (just a random nonce) or shuffle the order of its top-tree elements. Then the hash of stateless_part will be different for each address, making them unlinkable if only stateful spends are made from them.
But I haven't found a non-ZK way to make stateless spends unlinkable, even partially. My original idea was to rely on shuffling the stateless top-tree elements. This works to some extent if the stateless path is not reused too many times. But the main privacy leak is the reused pk_seed_sl. We can't change it, because it defines the whole stateless setup work sharing per wallet (the main point of this issue). I don't want to introduce ZK here. Maybe you know a way to do it?
But even without a solution to the privacy issue, I still see value in decoupling the stateless and stateful parts, as proposed above. The stateless path is seen as a fallback to rescue the funds. I see a parallel with Taproot: if everything goes well, one uses key spend and gets great privacy; if something goes wrong and a fallback script stored in some tapleaf is used, this leaks some privacy (i.e. that the address is a multi-sig or HTLC, etc.), but this is acceptable, because this is an unlikely situation where the priority is to save the funds, not to preserve privacy.
I'm experimenting with MPC for SHRINCS and I got some impressive results for the stateful part: about 3 minutes to set up a 2/2 public key, and about 1 second to make a signature. The prototype is still vibe-coded, so it needs deeper verification, but overall it looks promising.
The hard part is the stateless fallback. I generated the top tree for it in MPC and it took about 1.5 hours. That is not impossible, but it is too expensive if it has to be done separately for each address. My idea is: could we reuse the same stateless tree across many addresses, so this work is done once per wallet rather than once per address?
One thing to take into account is that with this optimization all addresses in a wallet would share one stateless usage budget. Today that budget is per address. But if the budget is high enough and the stateless path is truly fallback-only, that may be acceptable.
There is one more problem, though:
pk_seedis public and currently ties the stateful and stateless parts together.As I understand it, the total public key today is
PK = (pk_seed, pk_root). The same publicpk_seedis used in both halves of the construction. It is used when building and verifying the stateful UXMSS/WOTS side, and it is also used when building and verifying the stateless FORS/XMSS side. The current globalpk_rootis also fed back into both sides. So I can't reuse one without reusing the other.I propose making the main
PK = Merkle_root(stateful_part, stateless_part), where each part includes its ownpk_seedandpk_root. Then the stateful side would use only(pk_seed_sf, pk_root_sf), and the stateless side would use only(pk_seed_sl, pk_root_sl). The top-level Merkle root would be only the outer binding key. When spending via the stateful path, one would have to provide only the hash of thestateless_part, not the entire part, so this seems to preserve efficiency for the stateful path in terms of blockchain footprint.An additional issue is privacy and linkability. I found a way to make stateful-only spends unlinkable: we can add a random component to the
stateless_partstruct (just a random nonce) or shuffle the order of its top-tree elements. Then the hash ofstateless_partwill be different for each address, making them unlinkable if only stateful spends are made from them.But I haven't found a non-ZK way to make stateless spends unlinkable, even partially. My original idea was to rely on shuffling the stateless top-tree elements. This works to some extent if the stateless path is not reused too many times. But the main privacy leak is the reused
pk_seed_sl. We can't change it, because it defines the whole stateless setup work sharing per wallet (the main point of this issue). I don't want to introduce ZK here. Maybe you know a way to do it?But even without a solution to the privacy issue, I still see value in decoupling the stateless and stateful parts, as proposed above. The stateless path is seen as a fallback to rescue the funds. I see a parallel with Taproot: if everything goes well, one uses key spend and gets great privacy; if something goes wrong and a fallback script stored in some tapleaf is used, this leaks some privacy (i.e. that the address is a multi-sig or HTLC, etc.), but this is acceptable, because this is an unlikely situation where the priority is to save the funds, not to preserve privacy.