How to verify the validity of a transaction

redPanda

member

Activity: 65

Merit: 16

Quote

It seems that you swapped r and s

Yes, you're right, I think, my error came from http://www.royalforkblog.com/2014/09/04/ecc/ (with small numbers)
where they give "signature = 22,13" (with 22 = s and 13 = r: reverse order). I should have checked twice.
And thanks a lot for reading my long question.

johoe

full member

Activity: 217

Merit: 259

You don't need RNy to check validity.

Compute txHash/s * G + r/s * (X,Y), which should give you RN * G = (RNx, RNy). Then just check if r = RNX.

EDIT: Your notation is somewhat non-standard. RN is usually called k. What I called r,s above is the ECDSA signature. r is RNx, and s is (txHash + r*d)/k, where d is the private key. It seems that you swapped r and s.

redPanda

member

Activity: 65

Merit: 16

Thanks a lot

and what about the random number RNy from s = RNx ?

DannyHamilton

legendary

Activity: 3472

Merit: 4801

Quote from: redPanda on April 28, 2015, 10:56:19 AM

- snip -
BUT in a Bitcoin transaction sometimes X and Y are given: 04 X Y
and sometimes only X is given: 02 X or 03 X
- snip -

Exactly. And the 02 or 03 that you've mentioned is there because Y could have two different values. The 02 or 03 let you know which of the two values you should be using.

Quote from: redPanda on April 28, 2015, 10:56:19 AM

If I only have X = 17 I have 2 choices for Y: (17,9) or (17,20)

Fortunately you shouldn't only have X = 17.

You should either have
02 X = 17
or
03 X = 17

redPanda

member

Activity: 65

Merit: 16

I want to verify the validity of a transaction

Signing a tx

In order to sign a tx, I need:
- , Random Number = RN and the hash of tx = txHash

To sign the tx I must publish the = * G = (X, Y)
where G is the Generator point

and I also must publish a signature = = (r,s)
where s is a random number:
generate a random number RN, and compute s = RNx like this:
RN * G = (RNx, RNy)
and r is a signature factor built with txHash, RNx, and RN

then the signature script = + = (r,s) + (X,Y)

Verify a tx

If I have all infos r, s = RNx, RNy, X, Y, I can sign a tx and verify its validity with my script

BUT in a Bitcoin transaction sometimes X and Y are given: 04 X Y
and sometimes only X is given: 02 X or 03 X

also only s = RNx is given and not RNy.

So in order to verify a tx, I need to compute Y and RNy
Question 1) is there a way to do it without Y and/or RNy ?

question 2) There is a simplify algorithm to find Y when
computing square roots mod p when p = 3 (mod 4).
I checked that this condition is satisfied with the p used in Bitcoin.
Am I correct ? Can I use this algorithm ?

if p = 3 (mod 4) the solution of y^2 = x^3 + 4 = a (mod p)
has the form y = a^(k+1)
proof: if p = 4k+3 then set y=a^(k+1) mod p then
y^2 = a^(2k+2) = a^(2k+1) a = a^((p-1)/2) a = a (mod p)
by Euler's Criterion. So y = a^(k+1) is a solution.

Question 3) Is there a risk of collision when finding Y or RNy?
In a simple example (http://www.royalforkblog.com/2014/09/04/ecc/)
p = 29 and privKey = 7 => 7 * G = (17,9)
If I only have X = 17 I have 2 choices for Y: (17,9) or (17,20)

Thanks

Topic: How to verify the validity of a transaction (Read 1323 times)