Re: [bitcoindev] A look at SHRINCS

[Patrick Cerri <patrickcerri@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 14415 bytes --]

Just to add :

We are thinking about storing this information ON the chain itself - in
some way.

Knowing the value does not make the signatures any less secure so sharing
publicy does not seem to be an issue.

- The simplest way is to just count the number of times an address has been
used by scanning the entire blockchain and all transactions.. and then use
that value as your current key uses. This unfortunately does not work for
pruned nodes. But you could ask a non-pruning node to give you this number.
Resyncing from genesis on your pruned node works. This could be optimised a
lot though.
- You could add the value ( somehow ) to every transaction you send and
then you would only need to check your very latest transaction from a
certain address to retrieve the value.
- This on-chain system does not work for any off-chain signatures you may
have performed - say to prove ownership of coins ( which we do in one of
our ticketing apps ). And would not work for lightning addresses - you'd
need some other way to keep track.



On Wed, 10 Jun 2026 at 09:58, Patrick Cerri <patrickcerri@gmail.com> wrote:

> Yo.
>
> WRT to
>
> | Keeping state is not trivial. This is MUCH harder for Users than I
> expected.
>
> In our system Users can obviously restart/reset their node and at that
> point a seed-phrase is required. We also ask them to provide a KEY_USES
> value for how many slots they have used.
>
> The 'KEY USES' value can easily be obtained from their original node but
> this has proved a sticking point. We are a mobile first blockchain so
> phones play a big part of our system.
>
> - The node is lost/wiped and they do not know what their key uses was when
> they lost their node. In "best case" a User should know this value after
> every transaction - AND REMEMBER / STORE IT - so that they are ready should
> their node be lost to them. This is asking A LOT. The main issue imho.
> - Even Users who have simply wiped their node through choice did not think
> to check that final value before starting up a fresh node - and cannot
> retrieve it after the fact.
> - Some Users use multiple devices - with the same seed - and these do not
> synchronise so slots overlap. Although I did see there was some talk of
> creating separate tree paths for separate devices which may help. All
> though then you would need to keep track of more than 1 number, 1 for each
> device - even harder.
> - Normal / non-techie Users (through no fault of their own - smart people
> just not technical ) simply do not comprehend what this is and confuse it
> for how many times they want to use their address.
> - Even though we have tried to explain this as fully and comprehensively
> as we can, this information has just not percolated through the ecosystem
> as we would have liked. Some really have no idea that it is required at all
> and are just confused when we ask them for the value on resync. Like I said
> - people _expect_ their seed to be enough.
>
> We tried to change it so we ask them 'How many times have you resynced
> ?'.. and whatever number they give we just multiply by 10,000 but this is
> also not great as - again - they need to remember how many times they have
> done this. You'd think it was easy but we have seen people get even this
> wrong. It is possible to tell from the merkle branch in the signature which
> key is being used - so we can tell when it happens. And some do not realise
> how important this is and always say this is their first time to reduce
> information leakage - incorrectly thinking we are harvesting information or
> something.
>
> Some have used an address MORE than 10,000 times.. this especially applies
> to Exchanges or more business oriented accounts that send a lot of
> transactions from a single address. It's a crude approximation that has
> pros and cons. Certainly not infallible.
>
> As for our current implementation of SPHINCS.. this was done in house with
> the scraps of information we managed to extract from the 'inter-web' -
> SPHINCS is really quite a simple and elegant system. No optimisation and no
> hardware support so am pleased to see you have a solution to the resource
> issues I raised. Yes - on a phone our pure java version takes 20-30 seconds
> to build a key and sign.. but that is probably the slowest it will ever be!
> The verification at least is still fast. This may be something to think
> about though as anyone else trying to create an implementation may also
> create a working-but-much-slower version than the nice, clean, optimised
> this-is-how-to-do-it-correctly version.
>
> On Tue, 9 Jun 2026 at 18:38, conduition <conduition@proton.me> wrote:
>
>> Hi spartacusrex, thanks for raising this point.
>>
>> The current published version of SHRINCS (described here
>> <https://delvingbitcoin.org/t/shrincs-324-byte-stateful-post-quantum-signatures-with-static-backups/2158/>)
>> 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
>>    <https://eprint.iacr.org/2014/795>?
>>    - 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 <https://github.com/conduition/slhvk>
>>    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 <https://github.com/sphincs/parallel-sphincsplus>
>>    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
>>    <https://conduition.io/cryptography/hypertree-pruning/>.
>>
>>
>> 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
>> <https://github.com/bitcoin/bips/blob/master/bip-0442.md>.
>>
>> regards,
>> conduition
>> On Tuesday, June 9th, 2026 at 5:35 AM, Patrick Cerri <
>> patrickcerri@gmail.com> wrote:
>>
>> 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
>>
>> --
>> 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+unsubscribe@googlegroups.com.
>> To view this discussion visit
>> https://groups.google.com/d/msgid/bitcoindev/CAOWv0%2BUx1AiLbUagF8eWsmvMQ-xvu438WsOJ%2Br0MzsqbHWerOQ%40mail.gmail.com
>> .
>>
>>
>>

-- 
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+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAOWv0%2BXTFgWLZ9AwSJouyoy8gZ0iGwcKpUBMmXTWLoKehZ%2BfzA%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 18604 bytes --]