The most repeated R value on the blockchain

amaclin

legendary

Activity: 1260

Merit: 1019

Quote from: HeadsOrTails on July 16, 2015, 12:32:03 AM

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:

HeadsOrTails

full member

Activity: 233

Merit: 102

Quote from: johoe

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~~soft 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

Activity: 1260

Merit: 1019

Quote from: johoe on July 13, 2015, 04:01:18 AM

there is no important reason to fix this.

TierNolan

legendary

Activity: 1232

Merit: 1094

Quote from: gmaxwell on July 12, 2015, 03:05:17 PM

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?

Quote from: johoe on July 13, 2015, 04:01:18 AM

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

legendary

Activity: 1260

Merit: 1019

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

johoe

full member

Activity: 217

Merit: 259

Quote from: HeadsOrTails on July 13, 2015, 01:22:37 AM

Quote from: gmaxwell on July 12, 2015, 10:50:32 PM

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

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

HeadsOrTails

full member

Activity: 233

Merit: 102

Quote from: gmaxwell on July 12, 2015, 10:50:32 PM

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

gmaxwell

staff

Activity: 4284

Merit: 8808

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

Activity: 233

Merit: 102

Quote from: gmaxwell on July 12, 2015, 06:06:15 PM

Quote from: amaclin on July 12, 2015, 02:17:25 PM

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

Quote from: amaclin on July 12, 2015, 03:47:19 PM

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

staff

Activity: 4284

Merit: 8808

Quote from: amaclin on July 12, 2015, 02:17:25 PM

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

Quote from: amaclin on July 12, 2015, 03:47:19 PM

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.

amaclin

legendary

Activity: 1260

Merit: 1019

Quote from: XMRChina on July 12, 2015, 03:57:16 PM

Some people need to be protected from themselves

... by third parties, governments, banks and centralization? Grin

Yes, agreed

XMRChina

full member

Activity: 122

Merit: 100

Quote from: gmaxwell on July 12, 2015, 03:05:17 PM

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

Activity: 1260

Merit: 1019

Quote from: gmaxwell on July 12, 2015, 03:05:17 PM

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

Natural selection
Darwin Awards

gmaxwell

staff

Activity: 4284

Merit: 8808

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

Activity: 1260

Merit: 1019

Quote from: johoe on July 12, 2015, 01:26:31 PM

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

johoe

full member

Activity: 217

Merit: 259

Quote from: amaclin on July 12, 2015, 04:47:22 AM

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?

Quote from: HeadsOrTails on July 12, 2015, 11:59:57 AM

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.

Quote from: HeadsOrTails on July 12, 2015, 11:59:57 AM

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)

Quote from: HeadsOrTails on July 12, 2015, 11:59:57 AM

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!

HeadsOrTails

full member

Activity: 233

Merit: 102

Quote from: johoe on July 12, 2015, 01:54:18 AM

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!

amaclin

legendary

Activity: 1260

Merit: 1019

Code:

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

johoe

full member

Activity: 217

Merit: 259

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.

Topic: The most repeated R value on the blockchain (Read 3537 times)