Script micro optimisations

[ajtowns]

https://github.com/jonasnick/GreatRSI/blob/664be9d7f0de4df5c56e91c5a1f8c13ccde12eec/GreatRSI/ScriptBuilder.lean#L50-L55

I think this should be 1ADD <G> TUCK SWAP CAT SWAP CHECKSIGVERIFY rather than pushing G twice?

[jonasnick]

Oh, yes, thanks!

[ajtowns]

Oh, could also do a cumulative hash of the calculated pubkeys and only check the result, to save ~1900 bytes of script code.

[jonasnick]

Ah, nice idea! So instead of computing each expected_pk[i] and comparing it with pk[i], you'd compute hash(expected_pk[0], ..., expected_pk[n-1]) and compare with some hash(pk[0], ..., pk[n-1], which you can obviously compute outside the script.

[ajtowns]

Yeah. Same suggestion is made at https://conduition.io/cryptography/quantum-hbs/#Modifications-1 fwiw. Or something like pksum[0] = sha256(expected_pk[0]); pksum[n+1] = sha256(expected_pk[n+1] ++ pksum[n]) if you don't have streaming sha, and prefer computation to stack space usage.

[ajtowns]

Generating the randomizers by hashing the seed should also be reasonable, as far as I can see? Can't avoid hardcoding the seed and the pksum separately though, afaics.

[jonasnick]

Same suggestion is made at https://conduition.io/cryptography/quantum-hbs/#Modifications-1 fwiw.

Thanks I didn't know about that blog post.

Generating the randomizers by hashing the seed should also be reasonable, as far as I can see?

My immediate thought was that if it was reasonable, why wasn't it done in the W-OTS+ paper or RFC 8391.

I had a superficial look at the proof of the W-OTS+ paper and it seems to me that generating the randomizers as hashes from public inputs would not work. The proof relies on manipulating the randomizers in a way that is indistinguishable for the adversary from honestly chosen randomizers (i.e., drawn uniformly at random). However, if randomizer[i] = SHA256(seed,i), then the adversary could easily check whether it's seeing a regular or manipulated randomizer and just abort in the latter case.

However, I'm not really sure about the purpose of the randomizers in our case. It seems that they allow that the security of W-OTS+ is not relying on the collision resistance of the hash function. But we're relying on the collision resistance of SHA256 anyway when computing the transaction sighash. Note how the W-OTS+ paper assumes exactly n-byte messages. RFC 8391 uses a "randomized message hashing/digest" to prevent relying on collision resistance of the message hash. As far as I can see, the randomized hash is essentially just hash(r, m), where r is unknown to the adversary.

IIUC, if we don't care about the collision resistance of SHA256, we can get rid of the randomizers. If we do care, then we need to consider in what scenarios sighashing is randomized. There's this classic paper that shows that quantum computers are not better at finding collisions (and I don't know a rebuttal of that). But OTOH RFC 8391 did seem to consider that quantum computers may be better at collisions.

[ajtowns]

I had a superficial look at the proof of the W-OTS+ paper and it seems to me that generating the randomizers as hashes from public inputs would not work. The proof relies on manipulating the randomizers in a way that is indistinguishable for the adversary from honestly chosen randomizers

I don't think that makes sense? The manipulated randomizer is used in a proof-by-contradiction to leverage a successful attacker of the protocol into an attack against the hash function; it seems fine for the manipulated randomizer to be out of protocol?

It looks to me like RFC 8391 section 4.1.4 describes generating the randomizers (BM_0 and BM_1) by hashing the SEED, fwiw, and section 4.1.7 seems to describe having the public key be just the two elements, what we called pksum above (calculated as a merkle root) and SEED? Couldn't guarantee I'm reading that correctly though.

[jonasnick]

it seems fine for the manipulated randomizer to be out of protocol?

Can you elaborate? If the randomizer is out of the protocol and the adversary can compute it by themselves, it cannot be manipulated.

It looks to me like RFC 8391 section 4.1.4 describes generating the randomizers (BM_0 and BM_1) by hashing the SEED

I would expect that the input to the hash algorithm includes some data that is secret to the verifier.