The most repeated R value on the blockchain

[johoe]

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.

[amaclin]

Code:

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

[HeadsOrTails]

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?

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

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?

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]

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?  

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 Z_N. Then you can simply write

Code:

s = 1/k * (z + r*priv)

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.

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!

[amaclin]

Do you want to say that you updated your code and do not use

Code:

k=0x7add48f07237a85230be8fe44e1f7e36feaf649672aeefaa0f5abbad1721a994

any more?  

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]

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]

...people would use it for themselves even after being told that it would leak their private key.

Natural selection
Darwin Awards

[XMRChina]

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]

Some people need to be protected from themselves

... by third parties, governments, banks and centralization? 
Yes, agreed

[gmaxwell]

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

Natural selection
Darwin Awards

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]

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

Natural selection
Darwin Awards

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]

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.

[HeadsOrTails]

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]

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

[amaclin]

I wonder why f2pool does not use SIGHASH_NONE | SIGHASH_ANYONECANPAY instead of SIGHASH_SINGLE

[TierNolan]

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

[amaclin]

there is no important reason to fix this.

[HeadsOrTails]

SIGHASH_SINGLE just signs the output that corresponds to the input.  There is a bug (or a feature ) 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]

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

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

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: