A look at SHRINCS

[Patrick Cerri]

Good Day,

I would like to chip in.

I designed, wrote and work on a blockchain that implements WOTS sigs as standard so have some real-world knowledge of how this plays out in a live environment.

'SHRINCS' uses a ladder of WOTS keys that grows one level every time you use it. I think a tree of keys works better. This way you can have a set amount of slots/keys at a constant sig size.

Using a tree you can sign the root of another tree with a leaf key and have tree-of-tree keys (XMSS). This is what we do. This gives _potentially_ millions of signatures from a single address at the cost of signature size. How big the tree-of-trees is, how deep in trees and how many leaf nodes per tree, does not need to be hard coded and can be user defined. More potential sigs > signature size.

The only thing a verifier needs to be able to do is check a merkle branch and a WOTS sig. This covers all possible tree sizes.

With basic parameters you can create a WOTS-Tree sig in anywhere from 2-4k ( less if you use 128bit hash ) and have > 100,000 signatures. Still much larger than BTC sigs but manageable.

I do like the SPHINCS+ tree path SHRINCS uses to allow either system to be used.

Problems :

First - keeping the state is non-trivial. This is MUCH harder for Users than I expected.  

The idea that you can reset your node JUST from a seed is deeply embedded.. asking Users to keep track of even a single digit - the number of 'slots' used - has proved a stumbling block. Key slot reuse and ergo insecure keys happens.

If the proposed changes assume that any reset of your node would then require you to use SPHINCS+ to sweep remaining coins and send them to a new address this would work.. but that in and of itself is not great.

- You lose your old addresses.
- You may have a lot of coins and the sweep transactions may cost a lot - especially given the size of a SPHINCS sig.
- You need a NEW phrase.. all your cold wallets are no good. All your carefully hidden BIP39 seeds are useless and need to be remade.

If you choose to just use SPHINCS .. this also has issues.

We have implemented a SPHINCS+ scheme that runs in the base txn scripting.. so you can use that instead of the base WOTS scheme.

- Creating SPHINCS sigs is a lot more resource intensive than WOTS.
- RAM usage is 100x more ( not soo bad )
- SPHINCS sigs are BIG. ~20kb. Bigger than a regular WOTS sig and MUCH bigger than regular BTC sigs .
- Real issue is that on a phone the SPHINCS sig can take 20-30 seconds to create. Verification is still fast - just checking some merkle branches and WOTS sigs.

I do think a system like SHRINCS is the way to go but with some lee-way to choose the exact construction of your tree of keys.

What you need is :

- An OP_ for general Merkle branch checking. You need to use a HASH-SUM tree for SPHINCS.. so you can tell which HORS set you are using (technical point).
- An OP_ for WOTS check
..
- An OP_ for SPHINCS checking - which you _could_ actually create in script using the first 2 ops but a single OP_ would be cleaner/faster.

Then you have the freedom to create a SHRINCS style keys with variable parameters that allow signature size to be sacrificed for greater potential key uses. 

Regards,
spartacusrex

[conduition]

Hi spartacusrex, thanks for raising this point. 

The current published version of SHRINCS (described here) is not the version which we'll end up proposing for Bitcoin. As you point out, SHRINCS v1 doesn't give signers any flexibility in the stateful signing path to handle alternative use-cases. Since I started working with the blockstream folks, I think we've all come to agree this is a potentially important feature for some use-cases, that ought to be available. Some use cases would prefer constant-size signatures with higher stateful signing budgets. We don't want to force signers who can keep track of state to use the stateless path and waste blockspace unnecessarily.

Our current working design (unpublished) uses a flexible XMSS structure where signers can choose to use a balanced or an unbalanced XMSS tree structure in their stateful signing path, with the consensus-verifier being flexible enough to accept either format without distinguishing (i.e. a signature from a balanced depth 8 XMSS tree is indistinguishable from the 8th signature of an unbalanced tree).

As for multi-tree support, that is still uncertain. The main use-case for multi-tree XMSS would be lightning - nobody else ever needs to sign so much that they'd need multiple stateful trees, and if they do they can use the stateless path. We're still too early in the design process to say for sure if multi-tree is necessary, but I personally suspect it'd be better implemented as an entirely separate scheme from SHRINCS.

For now we're still writing the spec and putting in the work to make sure it's secure, but stay tuned for updates. We'll publish the new & improved SHRINCS scheme here and on DelvingBitcoin when it's ready for public review :)

I designed, wrote and work on a blockchain that implements WOTS sigs as standard so have some real-world knowledge of how this plays out in a live environment.

First - keeping the state is non-trivial. This is MUCH harder for Users than I expected.

I'd love to hear more about your experience with this. You mentioned wallet restoration as the main pain point, but are there any other issues you've run into deploying stateful signatures in the wild? 

If possible, would you be able to share the docs/specs/standards that you worked on?

- Creating SPHINCS sigs is a lot more resource intensive than WOTS.

- RAM usage is 100x more ( not soo bad )

- SPHINCS sigs are BIG. ~20kb. Bigger than a regular WOTS sig and MUCH bigger than regular BTC sigs .

- Real issue is that on a phone the SPHINCS sig can take 20-30 seconds to create. Verification is still fast - just checking some merkle branches and WOTS sigs.

Sounds like you might have some places to optimize. 

• SPHINCS+ signatures with a 128-bit security level can be as small as 3-5 kilobytes if you adjust parameter sets properly for your security and performance tolerances. Given the fact you referenced HORS in your message, are you using the legacy first version of SPHINCS?
  
• RAM usage can be reduced to almost nothing with streaming techniques. 
• Signing should definitely not take 20-30 seconds. My SLH-DSA-SHA2-128s implementation can make an SLH-DSA-SHA2-128s signature in 10 to 12 milliseconds on my desktop CPU, or a bit slower on a mobile CPU. With a GPU you can go even faster. Scott Fluhrer also has this awesome multithreading+AVX implementation which goes pretty fast too.
• The big performance pain point for SPHINCS is hardware wallets and other embedded systems. The current gen of hardware takes 60s+ to sign with SLH-DSA-SHA2-128s; longer if using a secure-element like Ledger. But there are still ways to optimize even that use case.

What you need is :

- An OP_ for general Merkle branch checking. You need to use a HASH-SUM tree for SPHINCS.. so you can tell which HORS set you are using (technical point).

- An OP_ for WOTS check

..

- An OP_ for SPHINCS checking - which you _could_ actually create in script using the first 2 ops but a single OP_ would be cleaner/faster.

We considered the option of implementing different SHRINCS sub-components as distinct opcodes/schemes in script. We decided not to, because of how challenging it would be to implement secure multisignature scripts. You'd have to handle the combinatorial explosion that occurs if different signers want to use different signing paths in the same witness. It's better if we have one unified standardized scheme which signers can customize on the client-side if they need to. Scripts should be kept clean and any new signature scheme should be compartmentalized.

Regarding the opcode for merkle branch checking... Maybe have a look at the OP_PAIRCOMMIT proposal.

regards,

conduition

--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAOWv0%2BUx1AiLbUagF8eWsmvMQ-xvu438WsOJ%2Br0MzsqbHWerOQ%40mail.gmail.com.