Bitcoin Forum
February 20, 2020, 05:47:19 PM *
News: Latest Bitcoin Core release: 0.19.0.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: The most repeated R value on the blockchain  (Read 2957 times)
johoe
Full Member
***
Offline Offline

Activity: 217
Merit: 141


View Profile
July 12, 2015, 06:54:18 AM
Last edit: July 12, 2015, 07:05:07 AM by johoe
 #1

The number 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 is now the most repeated R value on the blockchain (>70000 uses this morning, all other repeated R values are together used about 7000 times).

I saw on the IRC logs that gmaxwell suggested to use this R value for sweeping dust transactions, since it saves 11 bytes of encoding (leading zeros can be omitted) and since the private keys are publicly known, so there is no harm in doing this.  Some time ago, he also posed a challenge to explain this.

The corresponding private key is 1/2  (in modular arithmetic, so its numeric value is (order+1)/2).  It indicates that the generator G of secp256k1 was chosen such that 1/2G has this x coordinate (this cannot be a coincidence, that would be as likely as if the lottery winning numbers would be the same five times in a row).  In principle the generator G could have been chosen such that 1/2G is any valid point (almost every second 256-bit number corresponds to a valid point), so why did the creators of secp256k1 choose this particular number?  What else is so special about this number?

The document describing the SEC elliptic curves seems to avoid this topic altogether.  It doesn't describe how G was generated.

Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3
1582220839
Hero Member
*
Offline Offline

Posts: 1582220839

View Profile Personal Message (Offline)

Ignore
1582220839
Reply with quote  #2

1582220839
Report to moderator
1582220839
Hero Member
*
Offline Offline

Posts: 1582220839

View Profile Personal Message (Offline)

Ignore
1582220839
Reply with quote  #2

1582220839
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1002


View Profile
July 12, 2015, 09:47:22 AM
 #2

Code:
      static const QByteArray k ( QByteArray::fromHex ( "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0" ));
      BN_bin2bn ( k.constPtr ( ), 32, bn_kinv );
HeadsOrTails
Full Member
***
Offline Offline

Activity: 233
Merit: 100



View Profile
July 12, 2015, 04:59:57 PM
 #3

The number 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 is now the most repeated R value on the blockchain (>70000 uses this morning, all other repeated R values are together used about 7000 times)

I'm curious...

Are you referring to the
Code:
r
value from the DER signature? Have you got an example Tx?

Quote
The corresponding private key is 1/2  (in modular arithmetic, so its numeric value is (order+1)/2). 

So, the private key is 86918276961810349294276103416548851884759982251107 ??

(ie  (115792089237316195423570985008687907852837564279074904382605163141518161494337 + 1)/2 = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1  ??)


Quote
I saw on the IRC logs that gmaxwell suggested to use this R value for sweeping dust transactions, since it saves 11 bytes of encoding (leading zeros can be omitted) and since the private keys are publicly known, so there is no harm in doing this.  Some time ago, he also posed a challenge to explain this.

OK, so how does this work?

Code:
s = inv(k, N) * (z + r * priv) % N


where N is the curve order,
priv = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1,
r = 86918276961810349294276103416548851884759982251107,
z = base 10 value of msg_hash,
k = random number(??) or rfc6979, which requires msghash and privkey


So how would the
Code:
r
value be useful here?

Quote
It indicates that the generator G of secp256k1 was chosen such that 1/2G has this x coordinate (this cannot be a coincidence, that would be as likely as if the lottery winning numbers would be the same five times in a row).  In principle the generator G could have been chosen such that 1/2G is any valid point (almost every second 256-bit number corresponds to a valid point), so why did the creators of secp256k1 choose this particular number?  What else is so special about this number?

I'm curious about this as well!
johoe
Full Member
***
Offline Offline

Activity: 217
Merit: 141


View Profile
July 12, 2015, 06:26:31 PM
 #4

Code:
     static const QByteArray k ( QByteArray::fromHex ( "7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0" ));
      BN_bin2bn ( k.constPtr ( ), 32, bn_kinv );

Do you want to say that you updated your code and do not use
Code:
k=0x7add48f07237a85230be8fe44e1f7e36feaf649672aeefaa0f5abbad1721a994
any more?  Wink


Are you referring to the r value from the DER signature? Have you got an example Tx?

Yes.  Small example: c6c25c2955bab88d68a5fe9e1c4f357c49b053b37812aacb2f6deba701462de1
There are also some 900 kb+ transactions.

OK, so how does this work?

Code:
s = inv(k, N) * (z + r * priv) % N

where N is the curve order,

I prefer using the field ZN. Then you can simply write
Code:
s = 1/k * (z + r*priv)

Quote
priv = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1,
r = 86918276961810349294276103416548851884759982251107,
z = base 10 value of msg_hash,
k = random number(??) or rfc6979, which requires msghash and privkey

ECDSA signature is as follows:
Code:
R = k*G
r = R.x  (x coordinate of point)
and the rest as you wrote.

I called k the "private key" of R, since R = k * G. Sorry for the confusion.  So k = 1/2 (or 0x7ffff...a1).
The private key of the signature is still the private key of the address that is spend, e.g., of the brain wallet "cat".  

The reason why k=1/2 is chosen is that it leads to a shorter r.   Note that choosing k=1/2 allows everyone to compute the private key.  But since the private key is already known  (it's the brainwallet of cat or dog or password, etc.) this doesn't hurt in this case.

Quote
It indicates that the generator G of secp256k1 was chosen such that 1/2G has this x coordinate (this cannot be a coincidence, that would be as likely as if the lottery winning numbers would be the same five times in a row).  In principle the generator G could have been chosen such that 1/2G is any valid point (almost every second 256-bit number corresponds to a valid point), so why did the creators of secp256k1 choose this particular number?  What else is so special about this number?

I'm curious about this as well!

Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1002


View Profile
July 12, 2015, 07:17:25 PM
 #5

Do you want to say that you updated your code and do not use
Code:
k=0x7add48f07237a85230be8fe44e1f7e36feaf649672aeefaa0f5abbad1721a994
any more?  Wink
http://bitcoin.stackexchange.com/questions/38513/the-shortest-ecdsa-signature
f2pool uses very short signature. Why cannot I use it also?
OK, my math/programming skills are very poor. I do not understand why the G/2 produces such pretty pubkey
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2968
Merit: 3232



View Profile
July 12, 2015, 08:05:17 PM
Last edit: July 12, 2015, 08:17:24 PM by gmaxwell
 #6

Using this K value will leak your private key.

I intentionally did not publish the patch I gave F2Pool that allowed them to do this because I knew that people would use it for themselves even after being told that it would leak their private key.

SECP224K1 and SECP256K1 share the same 166 bit string doubled to produce the generator. Doubling a short string is an "obvious" enough way to choose a generator that I thought to halve the existing generator. Folklore is that some curves use SHA1 outputs to produce their generators.

As mentioned, I put up a puzzle based on this previously:  https://www.blockstream.com/half-a-puzzle/
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1002


View Profile
July 12, 2015, 08:47:19 PM
 #7

...people would use it for themselves even after being told that it would leak their private key.
Natural selection
Darwin Awards
XMRChina
Full Member
***
Offline Offline

Activity: 122
Merit: 100


View Profile
July 12, 2015, 08:57:16 PM
 #8

Using this K value will leak your private key.

I intentionally did not publish the patch I gave F2Pool that allowed them to do this because I knew that people would use it for themselves even after being told that it would leak their private key.

SECP224K1 and SECP256K1 share the same 166 bit string doubled to produce the generator. Doubling a short string is an "obvious" enough way to choose a generator that I thought to halve the existing generator. Folklore is that some curves use SHA1 outputs to produce their generators.

As mentioned, I put up a puzzle based on this previously:  https://www.blockstream.com/half-a-puzzle/

Sounds like a wise decision on your part.

Some people need to be protected from themselves
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1002


View Profile
July 12, 2015, 09:32:56 PM
 #9

Some people need to be protected from themselves
... by third parties, governments, banks and centralization?  Grin
Yes, agreed
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2968
Merit: 3232



View Profile
July 12, 2015, 11:06:15 PM
 #10

f2pool uses very short signature. Why cannot I use it also?
OK, my math/programming skills are very poor. I do not understand why the G/2 produces such pretty pubkey

But seriously. If I don't personally want to facilitate someone shooting their foot of (where undoubtly some will blame me and attack my reputation), then thats my call-- not yours.  And whining about it is offtopic for this thread and subforum.
HeadsOrTails
Full Member
***
Offline Offline

Activity: 233
Merit: 100



View Profile
July 13, 2015, 03:33:47 AM
 #11

f2pool uses very short signature. Why cannot I use it also?
OK, my math/programming skills are very poor. I do not understand why the G/2 produces such pretty pubkey

But seriously. If I don't personally want to facilitate someone shooting their foot of (where undoubtly some will blame me and attack my reputation), then thats my call-- not yours.  And whining about it is offtopic for this thread and subforum.

Fair enough, it is your call. But I'm not asking any of these questions for anything other than testnet and to learn how ECDSA works. I'd think anyone learning ECDSA, like myself, who finds a private key online and then proceeds to use it....well, they have absolutely no right to blame you.

can you clarify the f2pool patch you mentioned? Was the "patch" the small r value, ie, facilitating the large transactions to fit in a block?
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2968
Merit: 3232



View Profile
July 13, 2015, 03:50:32 AM
Last edit: July 13, 2015, 06:26:16 AM by gmaxwell
 #12

Quote
can you clarify the f2pool patch you mentioned? Was the "patch" the small r value, ie, facilitating the large transactions to fit in a block?

And exploiting the SIGHASH single ... odd behavior, so that all the signatures past the first are just signing the value "1" instead of having to hash the transaction.

This makes the signed data after index 0 identical for all transactions, so if you compress the block data it will be MUCH MUCH smaller, perhaps only taking a few bytes per signature.

unfortunately they switched back to a scheme which creates seperate transactions for each coin, which undermines the compression gains and just takes a lot more space to begin with. Sad
HeadsOrTails
Full Member
***
Offline Offline

Activity: 233
Merit: 100



View Profile
July 13, 2015, 06:22:37 AM
 #13

Quote
can you clarify the f2pool patch you mentioned? Was the "patch" the small r value, ie, facilitating the large transactions to fit in a block?

And exploiting the SIGHASH single ... odd behavior, so that all the signatures past the first are just signing the value "1" instead of having to hash the transaction.

Hey! That's really clever!

With SIGHASH_SINGLE (0x03) signing, it's deleting all outputs after the signed index, and setting the indexes up to and including to be value = 2**64-1 and script = '', right?

I guess I'll have to play around with SIGHASH_SINGLE, as I haven't strayed too far from SIGHASH_ALL
johoe
Full Member
***
Offline Offline

Activity: 217
Merit: 141


View Profile
July 13, 2015, 09:01:18 AM
Last edit: July 13, 2015, 10:26:42 AM by johoe
 #14

Quote
can you clarify the f2pool patch you mentioned? Was the "patch" the small r value, ie, facilitating the large transactions to fit in a block?

And exploiting the SIGHASH single ... odd behavior, so that all the signatures past the first are just signing the value "1" instead of having to hash the transaction.

Hey! That's really clever!

With SIGHASH_SINGLE (0x03) signing, it's deleting all outputs after the signed index, and setting the indexes up to and including to be value = 2**64-1 and script = '', right?

I guess I'll have to play around with SIGHASH_SINGLE, as I haven't strayed too far from SIGHASH_ALL

SIGHASH_SINGLE just signs the output that corresponds to the input.  There is a bug (or a feature Smiley) in SIGHASH_SINGLE that the function computing the hash returns 1, if there is no corresponding output.  The 1 was probably meant as error indicator, but it is interpreted as the hash.  Since this is consensus critical it can only be changed by a hardsoft fork and there is no important reason to fix this.

The signatures of some 1mb transactions use this feature to avoid computing the 7500 hashes (one for each input) of the transaction and shortening verification time and therefore propagation time.  Don't use broken SIGHASH_SINGLE signatures for important addresses.  Once you publish a signature for the hash 1, everyone can spend this address using the same signature.

Donations to 1CF62UFWXiKqFUmgQMUby9DpEW5LXjypU3
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1002


View Profile
July 13, 2015, 09:14:45 AM
 #15

I wonder why f2pool does not use SIGHASH_NONE | SIGHASH_ANYONECANPAY instead of SIGHASH_SINGLE
TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1005


View Profile
July 13, 2015, 09:36:34 AM
 #16

SECP224K1 and SECP256K1 share the same 166 bit string doubled to produce the generator.

In the thread about how the various parameters for secp256k1 were picked, the process for selecting the generator was unknown.  I guess someone figured it out?

SIGHASH_SINGLE just signs the output that corresponds to the input.  There is a bug (or a feature Smiley) in SIGHASH_SINGLE that the function computing the hash returns 1, if there is no corresponding output.  The 1 was probably meant as error indicator, but it is interpreted as the hash.  Since this is consensus critical it can only be changed by a hard fork and there is no important reason to fix this.

It would be a soft fork, I think.  You would reject any transaction that uses SIGHASH_SINGLE if there was no corresponding output.

Given that is can't be exploited, there is little point.  Though it removes an edge case for those re-implementing the consensus code.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1002


View Profile
July 13, 2015, 10:05:26 AM
 #17

there is no important reason to fix this.
HeadsOrTails
Full Member
***
Offline Offline

Activity: 233
Merit: 100



View Profile
July 16, 2015, 05:32:03 AM
 #18

Quote from: johoe

SIGHASH_SINGLE just signs the output that corresponds to the input.  There is a bug (or a feature Smiley) in SIGHASH_SINGLE that the function computing the hash returns 1, if there is no corresponding output.  The 1 was probably meant as error indicator, but it is interpreted as the hash.  Since this is consensus critical it can only be changed by a hardsoft fork and there is no important reason to fix this.

The signatures of some 1mb transactions use this feature to avoid computing the 7500 hashes (one for each input) of the transaction and shortening verification time and therefore propagation time.  Don't use broken SIGHASH_SINGLE signatures for important addresses.  Once you publish a signature for the hash 1, everyone can spend this address using the same signature.


Ahhh, ok. So it's returning 1 which is the same as True in the script?
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1002


View Profile
July 17, 2015, 06:34:19 AM
 #19

Ahhh, ok. So it's returning 1 which is the same as True in the script?

http://lmgtfy.com/?q=SIGHASH_SINGLE

Quote
It turns out that, due to a bug, if an output with the same index does not exist then the integer value one will be returned as the hash of the transaction. This appears to have been first described by Peter Todd on the bitcointalk forum. We can verify this behaviour in a Python shell:
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!