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?

ping @waxwing x0f.org/@waxwing/1074861756703

@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)

@kalle

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)

@kalle

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): github.com/AdamISZ/from0k2bp/b

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: youtube.com/watch?v=mLZ7qVwKal (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 @waxwing if you make the validation function sG=R+H(P,m)P (not committing to R) you don't need the private key to sign - just choose s arbitrarily and calculate R=sG-H(P,m)P

@ajtowns @kalle well, I did say that, but you could be forgiven for falling asleep before I got there :)

@waxwing @ajtowns Guys, huge thanks to both of you for you help here! I've now updated my post (scroll to the "What's with the commitment" section). popeller.io/schnorr-basics

@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 bitcoin-dev.blog ?

@0xb10c Oh sorry. I did see that, but forgot about it. Sure I can cross-post. I'll DM here on mastodon.

Sign in to participate in the conversation
Bitcoin Mastodon

Bitcoin Maston Instance