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
Branch
markmerge1
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 4594
Build 7251: Bitcoin ABC Buildbot (legacy)
Build 7250: arc lint + arc unit

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.