Page MenuHomePhabricator

Add CKey::SignSchnorr and CPubKey::VerifySchnorr
ClosedPublic

Authored by markblundeberg on Jan 19 2019, 20:10.

Details

Summary

This is coded for 64-byte schnorr sigs (no flag byte).

Depends on D2345 and D2169 .

Test Plan
  • Tests added that mimic those used for SignECDSA/VerifyECDSA.
  • Test that nonce reuse does not occur for ECDSA and Schnorr.

Diff Detail

Repository
rABC Bitcoin ABC
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

markblundeberg created this revision.Jan 19 2019, 20:10
Herald added a reviewer: Restricted Project. · View Herald TranscriptJan 19 2019, 20:10
Herald added a subscriber: schancel. · View Herald Transcript

Added tests

markblundeberg retitled this revision from WIP - add CKey::SignSchnorr and CPubKey::VerifySchnorr to Add CKey::SignSchnorr and CPubKey::VerifySchnorr.Jan 19 2019, 21:20
markblundeberg edited the test plan for this revision. (Show Details)
deadalnix requested changes to this revision.Jan 20 2019, 00:46
deadalnix added inline comments.
src/key.cpp
207 ↗(On Diff #6754)

Braces

219 ↗(On Diff #6754)

Is there a reason why the nonce generation function is passed explicitly ?

Reusing k between ECDSA and Schnorr would leak the private key, so we we should have a test case that sign with both ECDSA and schnorr and ensure they private key extraction fails.

220 ↗(On Diff #6754)

I'm not sure wy these assert rather than return false.

This revision now requires changes to proceed.Jan 20 2019, 00:46
markblundeberg added inline comments.Jan 20 2019, 01:33
src/key.cpp
207 ↗(On Diff #6754)

k :-)

219 ↗(On Diff #6754)

Just copying SignECDSA(). No other reason, indeed it doesn't seem necessary.

Yes, the reused-k check is indirectly done in the last two tests of deterministic signing. You can see that for the same key signing the same message, ECDSA deterministically produces r=c6ab5f8acfccc114da39dd5ad0b1ef4d39df6a721e824c22e00b7bc7944a1f78 and Schnorr produces r=e7167ae0afbba6019b4c7fcfe6de79165d555e8295bd72da1b8aa1a5b5430588. But this can definitely be tested more explicitly.

220 ↗(On Diff #6754)

Yep, I dunno, just copying SignECDSA() :-)

improve tests to check against ECDSA-Schnorr nonce reuse ; also fix braces

oops, messed that up. trying again...

markblundeberg edited the test plan for this revision. (Show Details)Jan 20 2019, 03:17
deadalnix accepted this revision.Jan 20 2019, 14:53
deadalnix added inline comments.
src/test/key_tests.cpp
46 ↗(On Diff #6756)

You should use .data() here rather than .begin() .

This revision is now accepted and ready to land.Jan 20 2019, 14:53

switched a few begin() to data(), strengthened internal sanity tests

oops, missed some .begin()s, now all changed to .data()

markblundeberg added inline comments.Jan 20 2019, 20:09
src/test/key_tests.cpp
46 ↗(On Diff #6756)

OK, changed -- I'm curious what's the reasoning by the way? It sounds like most C++ people prefer iterators to pointers. e.g. https://stackoverflow.com/questions/25393431/c-vector-iterators-vs-pointers

(My C++ is very rusty, I haven't used it in like 15 years.)

jasonbcox accepted this revision.Jan 30 2019, 22:27
jasonbcox added a subscriber: jasonbcox.
jasonbcox added inline comments.
src/test/key_tests.cpp
46 ↗(On Diff #6756)

Iterators have better null safety. "not found" situations tend to return container::end() rather than null.

deadalnix added inline comments.Jan 30 2019, 22:57
src/test/key_tests.cpp
46 ↗(On Diff #6756)

data provides you a pointer to the storage. begin provides you an iterator, that can anything.

For completeness, &sig[0] is undefined when sig.size() == 0 .

But actually in that case you aren't using memcpy or anything, so iterators are the way to go with std::copy.

OK so I was an idiot and begin is the way to go with std::copy. Most of the code use memcpy so I was confused. Either way it's fine as std::copy knows about pointers.

OK so I was an idiot and begin is the way to go with std::copy. Most of the code use memcpy so I was confused. Either way it's fine as std::copy knows about pointers.

Should I change them back to begin() ? Fine either way for me ...

rebase & fix

  • remove pubkey generation from SignSchnorr()
  • switch from data() to begin() in key_tests
markblundeberg marked 3 inline comments as done.Jan 31 2019, 15:04

Note: this python code reproduces the first Schnorr deterministic signature

#!/usr/bin/env python3
# Reproduce Bitcoin ABC's deterministic Schnorr signature near end of key_tests.cpp

from ecdsa.numbertheory import jacobi
from ecdsa import SECP256k1
import hashlib
import hmac

G = SECP256k1.generator
p = SECP256k1.curve.p()
n = SECP256k1.order

def sha(b):
    return hashlib.sha256(b).digest()

msg = b"Very deterministic message"
msghash = sha(sha(msg))
assert msghash == bytes.fromhex("5255683da567900bfd3e786ed8836a4e7763c221bf1ac20ece2a5171b9199e8a")
print("msg = "+repr(msg))
print("msghash = "+msghash.hex())

# 5HxWvvfubhXpYYpS3tJkw6fq9jE9j18THftkZjHHfmFiWtmAbrj
# Kwr371tjA9u2rFSMZjTNun2PXXP3WPZu2afRHTcta6KxEUdm1vEw
privkey = 0x12b004fff7f4b69ef8650e767f18f11ede158148b425660723b9f9a66e61f747
print("privkey = "+hex(privkey))
# pubkey point
P = privkey*G
comppub = (b'\x03' if (P.y()&1) else b'\x02') + P.x().to_bytes(32,'big')
assert comppub == bytes.fromhex("030b4c866585dd868a9d62348a9cd008d6a312937048fff31670e7e920cfc7a744")


### Validate the signature found in the code
sig = bytes.fromhex("2c56731ac2f7a7e7f11518fc7722a166b02438924ca9d8b4d1113"
                    "47b81d0717571846de67ad3d913a8fdf9d8f3f73161a4c48ae81c"
                    "b183b214765feb86e255ce")
r = int.from_bytes(sig[:32],'big')
s = int.from_bytes(sig[32:],'big')
print("sig.r = " + hex(r))
print("sig.s = " + hex(s))

e = int.from_bytes(sha(r.to_bytes(32, 'big') + comppub + msghash), 'big') % n
print("e = " + hex(e))

checkR = s*G + (n-e)*P
print("chk.rx = " + hex(checkR.x()))
print("chk.ry = " + hex(checkR.y()))
print("jacobi(chk.y) = %+d"%(jacobi(checkR.y(),p)))
assert checkR.x() == r


### Now try to reconstruct the deterministic nonce
# see secp256k1_schnorr_sig_generate_k() in schnorr_impl.h
# and nonce_function_rfc6979() in secp256k1.c
algo16 = b"Schnorr+SHA256  "
ndata = b''
V = b'\x01'*32
K = b'\x00'*32
buf = privkey.to_bytes(32,'big') + msghash + ndata + algo16
# initialize
K = hmac.HMAC(K, V+b'\x00'+buf, 'sha256').digest()
V = hmac.HMAC(K, V, 'sha256').digest()
K = hmac.HMAC(K, V+b'\x01'+buf, 'sha256').digest()
V = hmac.HMAC(K, V, 'sha256').digest()
# generate once
V = hmac.HMAC(K, V, 'sha256').digest()
T = b''

k = int.from_bytes(V, 'big')
print("nonce k = " + hex(k))
R = k*G
print(" (kG).x = " + hex(R.x()))
print("+(kG).y = " + hex(R.y()))
print("jacobi((kG).y) = %+d"%(jacobi(R.y(),p)))
print("-(kG).y = " + hex(p-R.y()))
This revision was automatically updated to reflect the committed changes.