Follow

What's the purpose of having the nonce commitment, R, in the challenge of of a Schnorr signature?

The only reason I can come up with is malleability. if R isn't part of the challenge and (R,s) is valid for a message m and key P, then (R+xG,s+x) is also valid for m and P.

Are there other issues than this?

say he knows P but not the private key p. Then he can choose s and e at random, and "choose" R as sG -eP and claim that (R, s) "proves he knows p" when it obviously doesn't.

The idea of the Fiat Shamir transform is something like this: given an interactive proving protocol, you can essentially "make the challenge step be a non-backdatable transcript of the commit step", such that there is no longer a need for interactivity. ... (2/n)

@kalle

You go: commit step(s), (challenge=hash(commit step(s))), response all in one without involving the verifier.

Because the hash is one-way, nobody can calculate a challenge e without knowing what the choice of R (the commit) is first, so they cannot re-calculate it as sG -eP (in this specific schnorr case, but it generalises). (3/3)

You might find interesting:

Boneh-Shoup chapter 19 (academic for sure but very thorough and good)

Section 4.1 of my writeup here (I'm trying to give the reader an intuition of what is going on in sigma protocols): https://github.com/AdamISZ/from0k2bp/blob/master/from0k2bp.pdf

Last (sorry for self-advertise) I think this is the best talk I gave by a long way, but few if any people saw it and unfortunately the filming isn't great: https://www.youtube.com/watch?v=mLZ7qVwKalE (most of first hour is about exactly what we're discussing).

@kalle occurs to me also, didactically, to avoid a bunch of waffle you could just say:

"we include R in the challenge so the signer can't modify it after they made the commitment".

Probably enough intuition in that brief phrase, for an intelligent reader to get the point.

@kalle Thanks for writing this up!

I've dm'd you a few days ago on the birdsite, but I think it doesn't show a notification for you. Would you be interested in cross-posting your Schnorr Basics post to https://bitcoin-dev.blog ?

waxwing@[email protected]@kalle

I find it helps to start from the Schnorr identity protocol itself. There, the challenge e is sent by the verifier to the prover, *after* he has made the commitment R.

Then providing an s which satisfies sG = R + eP proves that you know an x such that s = r + ep.

(That this is a proof can be deduced using the concept of an 'extractor' from ZKPs).

However if the prover invents his own e, clearly this is useless: (1/n)