Bitcoin Forum
May 29, 2017, 01:41:09 PM *
News: Latest stable version of Bitcoin Core: 0.14.1  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: 1 2 3 4 5 6 [All]
  Print  
Author Topic: New Attack Vector  (Read 39481 times)
Enochian
Full Member
***
Offline Offline

Activity: 126


View Profile
May 15, 2011, 05:00:58 PM
 #1

I was surprised to see that Bitcoin passes untrusted signature data received from the outside world to openssl without doing any checking on it.  This leaves bitcoin open to the Litttle Bobby Tables (http://xkcd.com/327/) attack.

Each signature has exactly one DER-encoded ASN.1 octet representation, but openssl doesn't enforce this, and as long as a signature isn't horribly malformed, it will be accepted.

So you can sit on the network, watch for transactions, and echo them with the signatures slightly tweeked, but still valid.  These new transactions will have different hashes, and will compete with the original transactions for inclusion in a block.  When a cloned transaction beats out the original for block inclusion, it will leave the original in the owners wallet unconfirmable forever, resulting in inconvenience and unspendable coins.  Quick echoing and network latency gives this a finite chance of happening.

Of course, you can't create or destroy coins with this, and the money still winds up at the right destination. However, the typical user isn't going to know how to restore an old wallet and rescan the block chain to get his bitcoin client back to working condition.

It might be a good idea to patch this before some enterprising person with excess time on their hands (cough) makes a cloned transaction echobot.

1496065269
Hero Member
*
Offline Offline

Posts: 1496065269

View Profile Personal Message (Offline)

Ignore
1496065269
Reply with quote  #2

1496065269
Report to moderator
1496065269
Hero Member
*
Offline Offline

Posts: 1496065269

View Profile Personal Message (Offline)

Ignore
1496065269
Reply with quote  #2

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

Posts: 1496065269

View Profile Personal Message (Offline)

Ignore
1496065269
Reply with quote  #2

1496065269
Report to moderator
1496065269
Hero Member
*
Offline Offline

Posts: 1496065269

View Profile Personal Message (Offline)

Ignore
1496065269
Reply with quote  #2

1496065269
Report to moderator
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
May 15, 2011, 05:36:54 PM
 #2

I believe the attack you describe is possible and real, but the effect is less troublesome. As soon as a modified echo of the transaction is included in a block, both sender and receiver will see this transaction too. The old transaction will linger on however, unconfirmed.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
May 15, 2011, 06:05:11 PM
 #3

I think sipa is right-- it will just look like a weird double-spend.

Probably a good idea to reject transactions with non-canonical signatures (reject if encode(decode(tx)) != tx ).

I assume the DER-encoded ASN.1 octet representation is the same between different ECDSA implementations (so if a non-openssl-based implementation creates transactions its transactions would be accepted), is that a good assumption?

How often do you get the chance to work on a potentially world-changing project?
Enochian
Full Member
***
Offline Offline

Activity: 126


View Profile
May 15, 2011, 06:22:23 PM
 #4

I assume the DER-encoded ASN.1 octet representation is the same between different ECDSA implementations (so if a non-openssl-based implementation creates transactions its transactions would be accepted), is that a good assumption?

Yes.  DER is, by design, unique across all implementations.

ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
May 15, 2011, 07:27:45 PM
 #5

Yes.  DER is, by design, unique across all implementations.

I presume you actually meant the exact opposite of what you said.

DER is "common" or "the same" across all implementations.

Edit your post and I will delete this one.

ByteCoin
Enochian
Full Member
***
Offline Offline

Activity: 126


View Profile
May 15, 2011, 07:52:55 PM
 #6

I presume you actually meant the exact opposite of what you said.

DER is "common" or "the same" across all implementations.

DER is BER with uniqueness enforced.  However, I see what I said lends itself to misinterpretation.

Objects have only a single unique correct DER encoding.  If it's not that encoding, it's wrong.







Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
May 16, 2011, 09:21:12 AM
 #7

So let me get this straight: bitcoin's signatures are always in DER encoding, but it will accept any BER-encoded signature?

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Enochian
Full Member
***
Offline Offline

Activity: 126


View Profile
May 16, 2011, 01:41:49 PM
 #8

So let me get this straight: bitcoin's signatures are always in DER encoding, but it will accept any BER-encoded signature?

To encode a positive integer in DER, you convert it to a big endian sequence of octets, using the minimum necessary, and if the sign bit on the leading one is set, you prepend a zero octet so it won't be interpreted as a negative number.  You then prepend an "02", which indicates "integer", and an octet count which is a single byte for lengths up to 127, and 0x80 plus an octet count followed by the length octets for lengths greater than 127.  This maps every integer onto a unique octet sequence.

A signature is a pair of bignum integers, (r,s), so it consists of 0x30, which indicates a sequence of one or more things, an octet count of what follows, followed by two encoded integers.  In addition, bitcoin appends the hashtype, which is always "1", to the end.

Here is a sample bitcoin sig, broken up into the relevant fields.

3046
0221
00c352d3dd993a981beba4a63ad15c209275ca9470abfcd57da93b58e4eb5dce82
0221
00840792bc1f456062819f15d33ee7055cf7b5ee1af1ebcc6028d9cdb1c3af7748
01

openssl doesn't enforce the rule that the leading octet can't be 0x00 or 0xff if it is an extension of the sign bit on the following octet.  So you can prepend any number of 0x00 octets to a positive integer, and 0xff octets to a negative integer, and it is still considered legal.  Thus you can make an unlimited number of working signatures given one of them.

eamon
Newbie
*
Offline Offline

Activity: 10



View Profile WWW
May 17, 2011, 05:30:35 PM
 #9

This actually is quite similar to another "corner case" that I've been wondering about.  Consider the following scenario:

User downloads installs bitcoin into a windows virtual machine, the copies the virtual machine to multiple locations.

Each of the virtual machines attempt to engage in transactions (receiving, sending, or even mining and block verification.)

What function is mitigating the collisions between clients, and which client becomes most authorative?  While I see how this could result in issues in transaction confirmation, wouldn't confirmations by those cloned entities result in confirmation corruption?
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
May 17, 2011, 05:44:52 PM
 #10

This actually is quite similar to another "corner case" that I've been wondering about.  Consider the following scenario:

User downloads installs bitcoin into a windows virtual machine, the copies the virtual machine to multiple locations.

Each of the virtual machines attempt to engage in transactions (receiving, sending, or even mining and block verification.)

What function is mitigating the collisions between clients, and which client becomes most authorative?  While I see how this could result in issues in transaction confirmation, wouldn't confirmations by those cloned entities result in confirmation corruption?
1. none of them.
2. no.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
Enochian
Full Member
***
Offline Offline

Activity: 126


View Profile
May 18, 2011, 04:03:38 PM
 #11

I believe the attack you describe is possible and real, but the effect is less troublesome. As soon as a modified echo of the transaction is included in a block, both sender and receiver will see this transaction too. The old transaction will linger on however, unconfirmed.


You're right.

I got curious and tried it this morning.  I created two transactions that did the same thing.  The first I let my client see, but didn't let it get broadcast.  The second I broadcast, but didn't let my client see.  Then I waited to see what would happen when the latter transaction arrived back in a block, double spending the earlier unconfirmable one in the wallet.

It added the second transaction to the wallet quite gracefully, and correctly computed the balance.  So this is less of a problem than I originally thought.

I should point out, however, that it used to be possible to segfault the ASN.1 parser in openssl by giving it garbage to decode.  The last such known bug was patched a number of revs back, but it not beyond the realm of possibility that another similar bug might be discovered at some time in the future.

So it's probably a good idea not to pass stuff that comes in over the wire to openssl without checking it first, just in case.

BitcoinStars.com
Full Member
***
Offline Offline

Activity: 140


View Profile
May 18, 2011, 04:08:18 PM
 #12

good job guys we need this sort of check and balance on the regular
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
May 18, 2011, 04:09:28 PM
 #13

I don't like the idea of openssl segfaulting on garbage data.

Is there an easy way for checking (by looking at the bytes ourselves, not by passing it to openssl and request to encode it again) that the input is a valid DER-encoded signature?

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
May 18, 2011, 04:17:27 PM
 #14

What function is mitigating the collisions between clients, and which client becomes most authorative?  While I see how this could result in issues in transaction confirmation, wouldn't confirmations by those cloned entities result in confirmation corruption?

It's possible to get a corrupted wallet today by doing that, where by "corrupted" I mean is out of sync with the state of the block chain and so can't reliably create spends.

Sipa is working on patches that can resolve this kind of thing, but until the work is complete it's not safe to do what you are suggesting. Bitcoin assumes that you don't copy your wallet around today.

Note that it doesn't undermine the security of the system though. The block chain will always be consistent.
Enochian
Full Member
***
Offline Offline

Activity: 126


View Profile
May 18, 2011, 04:30:49 PM
 #15

I don't like the idea of openssl segfaulting on garbage data.

Is there an easy way for checking (by looking at the bytes ourselves, not by passing it to openssl and request to encode it again) that the input is a valid DER-encoded signature?


Well, you know a valid bitcoin signature (r,s) is going to look like

<30><len><02><len><r bytes><02><len><s bytes><01>

where the r and s values are non-negative, and don't exceed 33 bytes including a possible padding zero byte.

One way to check would be to just create a little function

bool IsValidSig(char *sig, int siglen)

Containing an appropriate stack of if statements.

Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 534


View Profile WWW
August 22, 2012, 01:46:33 PM
 #16

I'm re-investigating this past problem because I think there are some other possibilities for this attack vector.

Did Sipa implemented a patch back on MAY 2011 to check the uniqueness and correctness of signatures?

I don't see a IsValidSig() method in the source code.

Bet regards, Sergio.
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
August 22, 2012, 02:21:31 PM
 #17

I'm re-investigating this past problem because I think there are some other possibilities for this attack vector.

Did Sipa implemented a patch back on MAY 2011 to check the uniqueness and correctness of signatures?

I don't see a IsValidSig() method in the source code.

Bet regards, Sergio.

No, this was never fixed. Doing it now would at first making transactions which use non-standard but valid encodings non-standard, and then fixing a policy for a transition point after which it becomes illegal.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
August 22, 2012, 02:22:50 PM
 #18

Making transactions with non-DER-encoded (aka BER encoded) signatures non-standard has been on my TODO list for over a year now, but has never been the highest priority.  That's the first step to making non-DER-encoded signatures completely illegal.

Note that if there is a core-dumping bug in OpenSSL's decoding code then it needs to get fixed in OpenSSL. Writing a BER decoder just for Bitcoin is a bad idea, it is much more likely our new code would have a crashing bug.

How often do you get the chance to work on a potentially world-changing project?
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 534


View Profile WWW
August 22, 2012, 03:31:44 PM
 #19

Thank you Sipa and Gavin, I'll keep researching on this..
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 534


View Profile WWW
October 04, 2012, 09:26:46 PM
 #20

For the record, there is another possibility of signature malleability.

For every ECDSA signature (r,s), the signature (r, -s (mod N)) is a valid signature of the same message. Note that the new signature has the same size as the original, as opposite as the malleabillity of padding.
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
October 05, 2012, 02:40:39 AM
 #21

For every ECDSA signature (r,s), the signature (r, -s (mod N)) is a valid signature of the same message. Note that the new signature has the same size as the original, as opposite as the malleabillity of padding.
Now that this is well known, I have to point out the following:

If some subset of clients rebroadcast transactions while flipping the sign of s then the transactions have different ids (because currently the signatures are included when hashing to find the transaction ID) and there may be some problems if the flipped version makes it into the block instead of the vanilla version as I believe the originator wouldn't recognise the flipped transaction has spent his coins.

ByteCoin
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2198



View Profile
October 05, 2012, 04:43:44 AM
 #22

Now that this is well known, I have to point out the following:

Transaction malleability has been known and discussed many times— including padding and other encoding differences. Is there some reason that you believe the s-flip to have distinct implications from all of the other signature encoding differences?

The understood risk of this in prior discussions has primarily been that troublemakers could create confusion by changing the transaction ID of confirmed transactions to be something different than the transaction participants were expecting (so, e.g. they'd see two transactions doing the same thing, one which never confirms). There is a secondary risk that parasites could 'hijack' other people's transaction to pay the way to embed data in the blockchain for them.

Quote
I believe the originator wouldn't recognise the flipped transaction has spent his coins.

In the reference client the spent-ness of candidate inputs when drafting a transaction are checked with IsSpent(), the txid of the spending transaction should be irrelevant. Can you elaborate on what you're thinking here?

Bitcoin will not be compromised
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 01:03:28 PM
 #23

BITCOIN IS SHIT, it does not accept signatures from the most well know implementation of crypto algorithms: openssl.

Code:
ThreadRPCServer method=sendrawtransaction
ERROR: Non-canonical signature: wrong length marker
ERROR: CScriptCheck() : f57a2c4d3b8f9653eaee0d5611fcf7c918bcc8903894e148c5b56486fb3f8eaa VerifySignature failed
ERROR: CTxMemPool::accept() : ConnectInputs failed f57a2c4d3b8f9653eaee0d5611fcf7c918bcc8903894e148c5b56486fb3f8eaa

why the fuck is this stuff implemented the way it is?

bitcoin and especially the satoshi client is a stinking pile faulty patches on other patches of bad and stupidly written code!

All main developers is bad at coding, and should feel bad about it.

/rant over

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 17, 2013, 01:18:50 PM
 #24

BITCOIN IS SHIT, it does not accept signatures from the most well know implementation of crypto algorithms: openssl.

Code:
ThreadRPCServer method=sendrawtransaction
ERROR: Non-canonical signature: wrong length marker
ERROR: CScriptCheck() : f57a2c4d3b8f9653eaee0d5611fcf7c918bcc8903894e148c5b56486fb3f8eaa VerifySignature failed
ERROR: CTxMemPool::accept() : ConnectInputs failed f57a2c4d3b8f9653eaee0d5611fcf7c918bcc8903894e148c5b56486fb3f8eaa

why the fuck is this stuff implemented the way it is?

bitcoin and especially the satoshi client is a stinking pile faulty patches on other patches of bad and stupidly written code!

All main developers is bad at coding, and should feel bad about it.

/rant over

What's funny is that this very thread explains why non-canonical signatures are bad, and why we stopped accepting them.

Just out of curiosity, is openssl giving you a padded signature under normal circumstances, or are you going out of your way to make it give you garbage?

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 01:19:37 PM
 #25

blockchain.info accepts my transaction vis pushtx, but bitcoind does not find it aesthetically pleasing enough.

if bitcoin fails, the blame goes to the developers for not having a standard to implement, but making shit up as you go along.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 01:23:16 PM
 #26

What's funny is that this very thread explains why non-canonical signatures are bad, and why we stopped accepting them.

Just out of curiosity, is openssl giving you a padded signature under normal circumstances, or are you going out of your way to make it give you garbage?
nope not at all, i give it the key(generated by the satoshi client, btw) and the transaction hash, it gives me the signature and i append hashtype.

blockchain.info accepts but bitcoind rejects.

you people should really stop implementing features, and sit down create a standard and start fix bitcoin instead.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 17, 2013, 01:43:47 PM
 #27

Would you mind posting the hex of the signed raw transaction?

I was just looking in script.spp, and this error is caused by an incorrect length.  When you attach your hashtype, are you changing the total length?

0x30  <total_length> 0x02 <length_of_R> <R> 0x02 <length_of_S> <S> <hashtype>

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 01:50:47 PM
 #28

there is actually an issue that not everyone is aware of, though I don't know if it is the reason of your problem.

the hashtype byte is not taken using this format:
Code:
0x30  <total_length> 0x02 <length_of_R> <R> 0x02 <length_of_S> <S> <hashtype>

it is taken using this expression:
Code:
unsigned char nHashType = vchSig[vchSig.size() - 1] & (~(SIGHASH_ANYONECANPAY));

and you cannot fix it - it's buried deep inside the chain.
https://blockchain.info/tx/67e758b27df26ad609f943b30e5bbb270d835b737c8b3df1a7944ba08df8b9a2

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 17, 2013, 02:00:25 PM
 #29

there is actually an issue that not everyone is aware of, though I don't know if it is the reason of your problem.

the hashtype byte is not taken using this format:
Code:
0x30  <total_length> 0x02 <length_of_R> <R> 0x02 <length_of_S> <S> <hashtype>

it is taken using this expression:
Code:
unsigned char nHashType = vchSig[vchSig.size() - 1] & (~(SIGHASH_ANYONECANPAY));

This distinction is only meaningful when the signature is not canonical.  When the signature is in the proper form, the last bye is the last byte.


I'm having a hard time understanding what you are talking about here.  The SIGHASH values apply to signatures.  The txout being redeemed has no bearing on them.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 02:05:18 PM
 #30

there is actually an issue that not everyone is aware of, though I don't know if it is the reason of your problem.

the hashtype byte is not taken using this format:
Code:
0x30  <total_length> 0x02 <length_of_R> <R> 0x02 <length_of_S> <S> <hashtype>

it is taken using this expression:
Code:
unsigned char nHashType = vchSig[vchSig.size() - 1] & (~(SIGHASH_ANYONECANPAY));

This distinction is only meaningful when the signature is not canonical.  When the signature is in the proper form, the last bye is the last byte.


I'm having a hard time understan what you are talking about here.  The SIGHASH values apply to signatures.  The txout being redeemed has no bearing on them.

Check this - it's a real signature from tx 67e758b27df26ad609f943b30e5bbb270d835b737c8b3df1a7944ba08df8b9a2:

Code:
3045022052538ceefdadef44696559b5b135e48218403f10120bcf592825b924af804821022100ed30a2a2218ad85438fd6a38f909b5ac55bc322033b63ddf17b3b9db11cd61800001

Following the format, the hashtype should be 00, while in fact it is 01.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 02:13:10 PM
 #31

Would you mind posting the hex of the signed raw transaction?

I was just looking in script.spp, and this error is caused by an incorrect length.  When you attach your hashtype, are you changing the total length?

0x30  <total_length> 0x02 <length_of_R> <R> 0x02 <length_of_S> <S> <hashtype>
Code:
0100000001fd31efbac93daa8743525898e81ebcfc69988484ede77537369117112b03dfb5000000006c49304402203ccac0d763cea96b7eefcc8bb77083312d5f74f19f3f38a2ef7c09a56303ec37022014247484bc2e6f979ea783753b92751deff8ea69f488483c18349c92ee8c517300000121020c04fd79c0de8acaf84cf68c92b5a64357b83c7e8c5115ee17ca5179b2516b95ffffffff01e41f0100000000001976a914b110cace3b1d8181df64854ddcf85bc635d10de888ac00000000


why would i change the length, are bitcoin in the business of messing with other people's standard?

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 02:17:41 PM
 #32

0100000001fd31efbac93daa8743525898e81ebcfc69988484ede77537369117112b03dfb500000 0006c49304402203ccac0d763cea96b7eefcc8bb77083312d5f74f19f3f38a2ef7c09a56303ec37 022014247484bc2e6f979ea783753b92751deff8ea69f488483c18349c92ee8c517300000121020 c04fd79c0de8acaf84cf68c92b5a64357b83c7e8c5115ee17ca5179b2516b95ffffffff01e41f01 00000000001976a914b110cace3b1d8181df64854ddcf85bc635d10de888ac00000000
this one works for me as well, so its definitely a different issue than I had mentioned before.

maybe bitcoind just does not like your low 0.00000071 BTC fee?

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
jackjack
Legendary
*
Offline Offline

Activity: 1036


May Bitcoin be touched by his Noodly Appendage


View Profile
July 17, 2013, 02:21:58 PM
 #33

0100000001fd31efbac93daa8743525898e81ebcfc69988484ede77537369117112b03dfb500000 0006c49304402203ccac0d763cea96b7eefcc8bb77083312d5f74f19f3f38a2ef7c09a56303ec37 022014247484bc2e6f979ea783753b92751deff8ea69f488483c18349c92ee8c517300000121020 c04fd79c0de8acaf84cf68c92b5a64357b83c7e8c5115ee17ca5179b2516b95ffffffff01e41f01 00000000001976a914b110cace3b1d8181df64854ddcf85bc635d10de888ac00000000
this one works for me as well, so its definitely a different issue than I had mentioned before.

maybe bitcoind just does not like your low 0.00000071 BTC fee?

Returning
Code:
ThreadRPCServer method=sendrawtransaction
ERROR: Non-canonical signature: wrong length marker
ERROR: CScriptCheck() : f57a2c4d3b8f9653eaee0d5611fcf7c918bcc8903894e148c5b56486fb3f8eaa VerifySignature failed
ERROR: CTxMemPool::accept() : ConnectInputs failed f57a2c4d3b8f9653eaee0d5611fcf7c918bcc8903894e148c5b56486fb3f8eaa
because of a too low fee is rather strange

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 02:25:54 PM
 #34

Returning
Code:
ThreadRPCServer method=sendrawtransaction
ERROR: Non-canonical signature: wrong length marker
ERROR: CScriptCheck() : f57a2c4d3b8f9653eaee0d5611fcf7c918bcc8903894e148c5b56486fb3f8eaa VerifySignature failed
ERROR: CTxMemPool::accept() : ConnectInputs failed f57a2c4d3b8f9653eaee0d5611fcf7c918bcc8903894e148c5b56486fb3f8eaa
because of a too low fee is rather strange
that makes sense.
so blockchain.info does not use bitcoind - I was always wondering..

@kokjo your tx won't get mined.
it does not like the fact that the 44 (<total_length> field) in your sig is not the actual sig length minus 3.
Code:
    if (vchSig[1] != vchSig.size()-3)
        return error("Non-canonical signature: wrong length marker");

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 17, 2013, 02:44:27 PM
 #35

You have two bytes of padding in there.

You may want to look at the bitcoind code to see how it gets unpadded signatures.

Code:
6c - script length
49 - signature length - should be 47 once the padding is removed
30 - marker
44 - rs length <total_length>
02 - marker
20 - R length
3ccac0d763cea96b7eefcc8bb77083312d5f74f19f3f38a2ef7c09a56303ec37 - R
02 - marker
20 - S length
14247484bc2e6f979ea783753b92751deff8ea69f488483c18349c92ee8c5173 - S
00 - garbage - invalid
00 - garbage - invalid
01 - SIGHASH flag
21 - pubkey length
02 - pubkey is compressed and even
0c04fd79c0de8acaf84cf68c92b5a64357b83c7e8c5115ee17ca5179b2516b95 - pubkey

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 02:58:03 PM
 #36

you don't have to tell my where my perfectly valid transaction fails bitcoind's beauty check, you need to remove the check from the satoshi client and stop adding useless crap to it.

the signature was generated with openssl, and is perfectly valid, my client and blockchain.org agrees.
The satoshi client should not be the protocol standard, of cource i could fix my transaction and give you people a free pass to fuck around more with bitcoin.

I will not allow this, and i object to the elitist culture among the main developers.

fix bitcoin, go make a standard and stick to it.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 17, 2013, 03:03:41 PM
 #37

you don't have to tell my where my perfectly valid transaction fails bitcoind's beauty check, you need to remove the check from the satoshi client and stop adding useless crap to it.

the signature was generated with openssl, and is perfectly valid, my client and blockchain.org agrees.
The satoshi client should not be the protocol standard, of cource i could fix my transaction and give you people a free pass to fuck around more with bitcoin.

I will not allow this, and i object to the elitist culture among the main developers.

fix bitcoin, go make a standard and stick to it.

Well, good luck with that, I guess.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 03:11:37 PM
 #38

Well, good luck with that, I guess.
so you are okay with that the developers is destroying bitcoin by trying to make it better?

prediction:
in a few years bitcoin will be worth nothing and a altcoin not based on the satoshi source with a solid standard will thrive.
because developers fucked bitcoin up, with all kind of insane checking and worse coding skills. bitcoin will nothing more then a bunch of dirty hacks.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 03:14:04 PM
 #39

Well, good luck with that, I guess.
so you are okay with that the developers is destroying bitcoin by trying to make it better?
this code if very old.
if they "fix" it now, it would surely create a hard fork soon - you don't really want it.
better change your code, adapting it to the beauty checks.
that is the reality all the new emerging bitcoin implementation will need to live in.
no altcoin can also be perfect from the first release, and they all are going to face similar issues in a future.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 03:20:11 PM
 #40

Well, good luck with that, I guess.
so you are okay with that the developers is destroying bitcoin by trying to make it better?
this code if very old.
if they "fix" it now, it would surely create a hard fork soon - you don't really want it.
better change your code, adapting it to the beauty checks.
that is the reality all the new emerging bitcoin implementation will need to live in.
no altcoin can also be perfect from the first release, and they all are going to meet exactly the same issues.
Fuck you liar! sipa added the check only 11 months ago.

Source:
https://github.com/bitcoin/bitcoin/blame/master/src/script.cpp
https://github.com/bitcoin/bitcoin/commit/58bc86e37fda1aec270bccb3df6c20fbd2a6591c

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 17, 2013, 03:22:35 PM
 #41

Well, good luck with that, I guess.
so you are okay with that the developers is destroying bitcoin by trying to make it better?

Destroying?  Nonsense.

Leave your hyperbole at home and go read up on why non-canonical encodings are bad, and why the developers decided to mark them as non-standard.  (That the satoshi client refuses to emit anything it considers to be nonstandard should be obvious.)

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
TierNolan
Legendary
*
Offline Offline

Activity: 1078


View Profile
July 17, 2013, 03:24:14 PM
 #42

go make a standard and stick to it.

Oh, the irony Smiley.

You basically want openSSL to be the standard.  That makes it harder for clients to be sure they are compatible.  

With the "beauty" checks, a script parser can be sure that it covers every valid signature.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 03:25:26 PM
 #43

Fuck you liar! sipa added the check only 11 months ago.
Don't talk to me like this - I only tried to help you, but I can swear as well.
11 months ago is long enough to cause a hard fork, if they revert the change now.

You should have mined your ugly tx before this change - that would surely prevent it Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
desired_username
Hero Member
*****
Offline Offline

Activity: 867


View Profile
July 17, 2013, 03:31:15 PM
 #44

BITCOIN IS SHIT, it does not accept signatures from the most well know implementation of crypto algorithms: openssl.

Code:
ThreadRPCServer method=sendrawtransaction
ERROR: Non-canonical signature: wrong length marker
ERROR: CScriptCheck() : f57a2c4d3b8f9653eaee0d5611fcf7c918bcc8903894e148c5b56486fb3f8eaa VerifySignature failed
ERROR: CTxMemPool::accept() : ConnectInputs failed f57a2c4d3b8f9653eaee0d5611fcf7c918bcc8903894e148c5b56486fb3f8eaa

why the fuck is this stuff implemented the way it is?

bitcoin and especially the satoshi client is a stinking pile faulty patches on other patches of bad and stupidly written code!

All main developers is bad at coding, and should feel bad about it.

/rant over

Is there a kokjo-coin available? Cheesy
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
July 17, 2013, 03:32:50 PM
 #45

kokjo, what was the OpenSSL command/code you used to generate that signature?

There are reasons canonical checks were adopted (it will fix a variety of attacks and sharp edges in the protocol). However if your OpenSSL is generating non canonical sigs, we'd very much like to find out why.
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 03:35:19 PM
 #46

Fuck you liar! sipa added the check only 11 months ago.
Don't talk to me like this - I only tried to help you, but I can swear as well.
11 months ago is long enough to cause a hard fork, if they revert the change now.
no its not. there already exist transactions that violates the beauty checks, and other clients accept these transactions too.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 03:36:40 PM
 #47

Is there a kokjo-coin available? Cheesy
No. But it will certainly come if the devs continue to behave like tards

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 03:37:03 PM
 #48

Fuck you liar! sipa added the check only 11 months ago.
Don't talk to me like this - I only tried to help you, but I can swear as well.
11 months ago is long enough to cause a hard fork, if they revert the change now.
no its not. there already exist transactions that violates the beauty checks, and other clients accept these transactions too.
no. such transactions don't exist. not in the blockchain.
it doesn't matter what other clients accept - it only matters what miners accept, and 99% of them are already at satoshi 0.8.x

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
July 17, 2013, 03:38:10 PM
 #49

fix bitcoin, go make a standard and stick to it.

No offence, but all this work is being done to actually make it comply to the standard.

The problem was that even though OpenSSL always created transactions that were compliant, it accepts signatures in non-standard encodings. This is bad, as every alternate implementation is required to implement the rules exactly as OpenSSL is. We've known this issue for a while, brought it up several times on the development mailing list and on this forum, investigated who was creating such transactions and gotten them to upgrade, until the frequency of such transactions was low enough. Then finally we added a rule to make bitcoind not relay or mine such transaction - without making them invalid even.

In this case, if the signature created made by bitcoind is non-standard, then we have a serious bug in the signature creation code. AFAIK, no bitcoin(d/qt) ever has ever created signatures that are currently considered non-standard however. If you're creating them yourself, it's possible to create valid transactions that are being rejected now. I'm sure you prefer your bitcoin node to reject the transaction immediately over only have the network reject it with you wondering why it doesn't confirm.

There is no risk for a hard fork at all right now, by the way. This is just local client policy about which transactions are relayed.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2198



View Profile
July 17, 2013, 03:42:37 PM
 #50

As this thread politely explains, OpenSSL violates the ASN.1/DER standard and will accept encoding which are invalid in a multitude of ways.  Because of this any implementation of the Bitcoin protocol— no matter what library it used— have to be bug for bug compatible with OpenSSL.  Worse, the behavior creates malleability of signatures which create the attack describe in this thread and which actually turns out to be even somewhat worse than described here.

Malleability  was being actively employed on the network in order to double spend and dos attack.  To close the attacks a strict, canonical, valid encoding must be enforced. As a bonus, if the enforcement is eventually made a network rule alternative implementations will not have to emulate OpenSSL's signature handling bugs.

It's interesting to hear that it's _creating_ these signatures: IIRC, we did not need to change Bitcoin in any way to avoid creating signatures with non-canonical encoding, OpenSSL's weird behavior is on the decoding side. It would be useful to know how you're (ab)using OpenSSL to accomplish this and/or what version of it you're using. It would be concerning, indeed, if there were some way to get the reference software to produce such a thing— but it's certainly not done so on normal systems in the past.

In any case, this was tested for months, deployed in the codebase as non-enforced for months prior to activation, announced widely. Bitcoin will not remain vulnerable to attack just so you can be lazy and produce sloppy inefficiently encoded signatures. If you are unwilling to take the effort to understand this and get it right it seems unlikely that you'll get the rest of the protocol right. Cryptographic distributed consensus systems may not be rocket surgery, but perhaps they're a little too complicated for some people— perhaps the kind of people whos first recourse is to start slinging insults at people for correcting a security vulnerability— to safely implement.

Piotr_n, this is not yet a network rule. Presumably someday it will be. Today this signature correctness is not enforced against blocks, just against free transactions. This means that miners can still perform the related malleability attacks but other users cannot, and it still means that alternative implementations must remain bug for bug compatible with OpenSSL's buggy validation. This is also why it's not a forking-anything to change.

Bitcoin will not be compromised
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 03:43:26 PM
 #51

There is no risk for a hard fork at all right now, by the way. This is just local client policy about which transactions are relayed.
Are you sure?
From what I see, the only place where IsCanonicalSignature is called from is EvalScript - the same function the blockchain parser uses.
Code:
bool fSuccess = (!fStrictEncodings || (IsCanonicalSignature(vchSig) && IsCanonicalPubKey(vchPubKey)));
if (fSuccess)
    fSuccess = CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType, flags);

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 03:44:17 PM
 #52

kokjo, what was the OpenSSL command/code you used to generate that signature?

There are reasons canonical checks were adopted (it will fix a variety of attacks and sharp edges in the protocol). However if your OpenSSL is generating non canonical sigs, we'd very much like to find out why.

Code:
ssl = ctypes.cdll.LoadLibrary(ctypes.util.find_library('ssl'))
NID_secp256k1 = 714 # from openssl/obj_mac.h

def check_result (val, func, args):
    if val == 0:
        raise ValueError
    else:
        return ctypes.c_void_p (val)

ssl.EC_KEY_new_by_curve_name.restype = ctypes.c_void_p
ssl.EC_KEY_new_by_curve_name.errcheck = check_result

...

    def __init__(self):
        self.k = ssl.EC_KEY_new_by_curve_name(NID_secp256k1)

...

    def sign(self, hash):
        sig_size = ssl.ECDSA_size(self.k)
        mb_sig = ctypes.create_string_buffer(sig_size)
        sig_size0 = ctypes.POINTER(ctypes.c_int)()
        assert 1 == ssl.ECDSA_sign(0, hash, len(hash), mb_sig, ctypes.byref(sig_size0), self.k)
        return mb_sig.raw

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 03:46:51 PM
 #53

There is no risk for a hard fork at all right now, by the way. This is just local client policy about which transactions are relayed.
Are you sure?
From what I see, the only place where IsCanonicalSignature is called from is EvalScript - the same function the blockchain parser uses.
Code:
bool fSuccess = (!fStrictEncodings || (IsCanonicalSignature(vchSig) && IsCanonicalPubKey(vchPubKey)));
if (fSuccess)
    fSuccess = CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType, flags);
Oh, I get it - its the fStrictEncodings.
Thanks for explaining Wink

Yeah, it would not have caused a hard fork - sorry for messing up.
I once analyzed the <hashtype> byte problem (I mentioned before) and then realized that fixing it would require a hard fork. And this mislead me. Wink

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2198



View Profile
July 17, 2013, 03:48:24 PM
 #54

Oh, I get it - its the fStrictEncodings.
Thanks for explaining Wink
Yup. The chain is stuffed full of old violations too. You can rig it to always be strict and reindex the chain and watch it reject it if you're bored. Smiley

Bitcoin will not be compromised
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
July 17, 2013, 03:49:46 PM
 #55

@kokjo: mind sharing the code how to embed the OpenSSL-created signature into a sigScript? I expect the problem is caused by how you wrap/pad it, rather than with the signature itself.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 03:54:09 PM
 #56

but the bottom line is: your transaction might get mined after all.
send it to luke-jr - he seems to be running the most liberal mining node out there.
or mine it yourself, if the copper feeding electricity to your house is thick enough Smiley

as long as the blockchain protocol allows it, I don't mind any software to reject relaying any transaction, by its own subjective rules.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
jackjack
Legendary
*
Offline Offline

Activity: 1036


May Bitcoin be touched by his Noodly Appendage


View Profile
July 17, 2013, 03:58:35 PM
 #57

Why should Bitcoin protocol accept all openssl formats?

What we need is a protocol, not mad people whining in a forum. That sure won't make them change.

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 04:04:31 PM
 #58

@kokjo: mind sharing the code how to embed the OpenSSL-created signature into a sigScript? I expect the problem is caused by how you wrap/pad it, rather than with the signature itself.
Code:
sc = [script.OP_PUSH(sig+"\x01"), script.OP_PUSH(key.publickey)]
tx.inputs[0].script = script.encode_script(sc)

as said before its the statoshi clients problem, not me generating bad(wrongly padded) signatures. i already have tracked down the problem in the satoshi client.

but the bottom line is: your transaction might get mined after all.
send it to luke-jr - he seems to be running the most liberal mining node out there. or mine it yourself Smiley

wasn't that the guy that put prayers in the blockchain?

I think i have trolled him a bit too much to ask him to accept my transaction with out appropriate fees, and the satoshi client will not accept the transaction unless its over 11 months old.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2198



View Profile
July 17, 2013, 04:05:06 PM
 #59

What we need is a protocol, not mad people whining in a forum. That sure won't make them change.
There is a formal specification for the signature encoding being used. That didn't stop OpenSSL from accepting weirdly encoded signatures. In most kinds of applications it doesn't matter— in the context of a distributed consensus algorithm being overly permissive in what you accept can be a devistaing global consensus failure producing vulnerability.  Practically every blockchain behavior which you'd normally specify has this kind of tight bounding. It's a fairly unusual challenge— the coupling in Bitcoin is much tighter than other protocols, even network routing protocols.


Bitcoin will not be compromised
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 04:05:39 PM
 #60

wasn't that the guy that put prayers in the blockchain?

I think i have trolled him a bit too much to ask him to accept my transaction with out appropriate fees, and the satoshi client will not accept the transaction unless its over 11 months old.
No - then don't ask him. Just find the IP of his node and send it there...

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 17, 2013, 04:07:39 PM
 #61

@kokjo: mind sharing the code how to embed the OpenSSL-created signature into a sigScript? I expect the problem is caused by how you wrap/pad it, rather than with the signature itself.
Code:
sc = [script.OP_PUSH(sig+"\x01"), script.OP_PUSH(key.publickey)]
tx.inputs[0].script = script.encode_script(sc)

as said before its the statoshi clients problem, not me generating bad(wrongly padded) signatures. i already have tracked down the problem in the satoshi client.

I decoded the transaction you provided by hand.  It is wrong, and I told you where it was wrong.

The satoshi client is only broken if you got that hex as the output of signrawtransaction.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 04:08:32 PM
 #62

Why should Bitcoin protocol accept all openssl formats?

What we need is a protocol, not mad people whining in a forum. That sure won't make them change.

the fix in the satoshi client includes this:
Code:
   // See https://bitcointalk.org/index.php?topic=8392.msg127623#msg127623
    // A canonical signature exists of: <30> <total len> <02> <len R> <R> <02> <len S> <S> <hashtype>
    // Where R and S are not negative (their first byte has its highest bit not set), and not
    // excessively padded (do not start with a 0 byte, unless an otherwise negative number follows,
    // in which case a single 0 byte is necessary and even required).

a link to this thread, is not the way of creating a good protocol standard.
Again:
bitcoin is a big hack job, create a standard and stick too it.

btw. would you please include my transaction in a block?

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 04:11:25 PM
 #63

The satoshi client is only broken if you got that hex as the output of signrawtransaction.
So the satoshi client can just troll around and smash things up, so no other client gets a fair chance to be able to create transactions.
https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp#L261 <-- this is where the satoshi client fail. the client is bad, and sipa(the dev who commited this) should feel bad.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 04:14:20 PM
 #64

The satoshi client is only broken if you got that hex as the output of signrawtransaction.
So the satoshi client can just troll around and smash things up, so no other client gets a fair chance to be able to create transactions.
https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp#L261 <-- this is where the satoshi client fail. the client is bad, and sipa(the dev who commited this) should feel bad.
I disagree that he should feel bad.
Your signature  is inconsistent - one length clearly does not match the other.
IMHO, he's right treating it like he does; a probably broken signature.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
July 17, 2013, 04:23:40 PM
 #65

The standard was using DER-encoded signatures, we're not making anything up - we're just enforcing a correct encoding rule that should have been there all along. The code comment is just a nice summary of the rules. This was announced several times on the development list and on this forum, and in release notes. We did wait until only a minority of transactions with non-canonical encodings remained, but it's impossible to find every possible (future) misbehaving client code.

If you disagree that standard-conforming signatures should be enforced on the network, we have little to talk about.

In any case, kjj is right - there are 2 weird padding bytes there, and I don't understand why your code is adding them. In any case, it's clearly wrong - go find why and fix it.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2198



View Profile
July 17, 2013, 04:23:48 PM
 #66

Quote
Code:
       assert 1 == ssl.ECDSA_sign(0, hash, len(hash), mb_sig, ctypes.byref(sig_size0), self.k)
        return mb_sig.raw
I believe this code is wrong.

ECDSA_sign takes a pointer siglen for the length of the buffer. The reason it passes a reference there and not a value is because it writes the resulting length back to it. Otherwise there would be no way to know the length other than the maximum since, obviously, char * doesn't encode a size.  Your code appears to do nothing with the returned size. This is wrong, and it means you're reading past the end of the destination array. Be glad the additional space contains only zeros and not your private key.

Bitcoin will not be compromised
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 04:29:29 PM
 #67

Be glad the additional space contains only zeros and not your private key.
Smiley
It could have, indeed.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 17, 2013, 04:30:32 PM
 #68

Quote
Code:
       assert 1 == ssl.ECDSA_sign(0, hash, len(hash), mb_sig, ctypes.byref(sig_size0), self.k)
        return mb_sig.raw
I believe this code is wrong.

ECDSA_sign takes a pointer siglen for the length of the buffer. The reason it passes a reference there and not a value is because it writes the resulting length back to it. Otherwise there would be no way to know the length other than the maximum since, obviously, char * doesn't encode a size.  Your code appears to do nothing with the returned size. This is wrong, and it means you're reading past the end of the destination array. Be glad the additional space contains only zeros and not your private key.

pwn3d

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 04:35:42 PM
 #69

Quote
Code:
       assert 1 == ssl.ECDSA_sign(0, hash, len(hash), mb_sig, ctypes.byref(sig_size0), self.k)
        return mb_sig.raw
I believe this code is wrong.

ECDSA_sign takes a pointer siglen for the length of the buffer. The reason it passes a reference there and not a value is because it writes the resulting length back to it. Otherwise there would be no way to know the length other than the maximum since, obviously, char * doesn't encode a size.  Your code appears to do nothing with the returned size. This is wrong, and it means you're reading past the end of the destination array. Be glad the additional space contains only zeros and not your private key.
+1 you are right, and i have broadcasted a double spend. Thank you.

pwn3d
I accept defeat, but still thinks that we need a standard, and that the satoshi client a bunch of hacks.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 04:42:24 PM
 #70

yeah, we need a standard. the only question is: who is going to develop a voting system that will decide about the standard?
thank god, we have a primitive bitcoin mining concept, backed with a billion dollar stability fund.
because if the future of this currency was based only on getting together the people developing its IT infrastructure, it would have been pretty fucking doomed.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2198



View Profile
July 17, 2013, 04:50:49 PM
 #71

+1 you are right, and i have broadcasted a double spend. Thank you.
Perhaps you're competent to review this change? https://github.com/jgarzik/python-bitcoinlib/pull/6  I am not.

Bitcoin will not be compromised
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 05:37:29 PM
 #72

yeah, we need a standard. the only question is: who is going to develop a voting system that will decide about the standard?
thank god, we have a primitive bitcoin mining concept, backed with a billion dollar stability fund.
because if the future of this currency was based only on getting together the people developing its IT infrastructure, it would have been pretty fucking doomed.
voting is not needed. we just need a guy with some balls to act as a dictator for a short period of time, and an army of typing monkeys implementing the standard.

what is done at https://en.bitcoin.it/wiki/Protocol_specification is usable, but most is yanked out of the satoshi client and lots of stuff have changed so the wiki is not up to date either. again: make a standard and implement it.

+1 you are right, and i have broadcasted a double spend. Thank you.
Perhaps you're competent to review this change? https://github.com/jgarzik/python-bitcoinlib/pull/6  I am not.
looks good enough... i have already committed a similar change to my code.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 05:41:04 PM
 #73

yeah, we need a standard. the only question is: who is going to develop a voting system that will decide about the standard?
thank god, we have a primitive bitcoin mining concept, backed with a billion dollar stability fund.
because if the future of this currency was based only on getting together the people developing its IT infrastructure, it would have been pretty fucking doomed.
voting is not needed. we just need a guy with some balls to act as a dictator for a short period of time, and an army of typing monkeys implementing the standard.

what is done at https://en.bitcoin.it/wiki/Protocol_specification is usable, but most is yanked out of the satoshi client and lots of stuff have changed so the wiki is not up to date either. again: make a standard and implement it.
from my experience, the only standard there is, is the satoshi source code.
the wiki is very helpful though and it almost nowhere contradicts the actual protocol, but the standard is in the code.
and maybe its not such a bad idea for a standard to be in a code.
as long as this code is not stupid Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 06:01:48 PM
 #74

yeah, we need a standard. the only question is: who is going to develop a voting system that will decide about the standard?
thank god, we have a primitive bitcoin mining concept, backed with a billion dollar stability fund.
because if the future of this currency was based only on getting together the people developing its IT infrastructure, it would have been pretty fucking doomed.
voting is not needed. we just need a guy with some balls to act as a dictator for a short period of time, and an army of typing monkeys implementing the standard.

what is done at https://en.bitcoin.it/wiki/Protocol_specification is usable, but most is yanked out of the satoshi client and lots of stuff have changed so the wiki is not up to date either. again: make a standard and implement it.
from my experience, the only standard there is, is the satoshi source code.
the wiki is very helpful though and it almost nowhere contradicts the actual protocol, but the standard is in the code.
and maybe its not such a bad idea for a standard to be in a code.
as long as this code is not stupid Smiley
it makes it nearly impossible to create a alternative client, when the "standard" mutates all the time. bitcoin needs diversity in clients.
Would you like to only be able to use internet explore? sure it would work good. but really?

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
jgarzik
Legendary
*
qt
Offline Offline

Activity: 1470


View Profile
July 17, 2013, 06:11:49 PM
 #75

it makes it nearly impossible to create a alternative client, when the "standard" mutates all the time. bitcoin needs diversity in clients.
Would you like to only be able to use internet explore? sure it would work good. but really?

The standard does not mutate all the time (though I do agree client diversity is a good thing).


Jeff Garzik, bitcoin core dev team and BitPay engineer; opinions are my own, not my employer.
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 06:13:49 PM
 #76

it makes it nearly impossible to create a alternative client, when the "standard" mutates all the time. bitcoin needs diversity in clients.
Would you like to only be able to use internet explore? sure it would work good. but really?

The standard does not mutate all the time (though I do agree client diversity is a good thing).

It mutates with every commit to the satoshi client repo. Code is not a standard.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 06:15:00 PM
 #77

so what do you propose?

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 06:23:29 PM
 #78

so what do you propose?
stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.

Just like the rfc's describe what the protocol look like down to the smallest detail, and then don't change it. Describe how clients interact with keyword defined in http://www.ietf.org/rfc/rfc2119.txt.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 17, 2013, 06:28:52 PM
 #79

it makes it nearly impossible to create a alternative client, when the "standard" mutates all the time. bitcoin needs diversity in clients.
Would you like to only be able to use internet explore? sure it would work good. but really?

The standard does not mutate all the time (though I do agree client diversity is a good thing).

It mutates with every commit to the satoshi client repo. Code is not a standard.

No, it really doesn't.

Sipa's patch last year changed how this particular implementation behaves, only.  It was not a change in the protocol.  The change was not binding on anyone else.

P.S.  The standardization thing is discussed in endless detail in many other threads.  Please read some of those before posting again.  You have contributed nothing new to the debate; even your pointless personal attacks are reruns.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 06:32:49 PM
 #80

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
They don't strike me like people who like to write code Smiley
And I guess you never tried to describe what a code does, in a human readable language.
Otherwise you would know that it's impossible.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 06:35:26 PM
 #81

Sipa's patch last year changed how this particular implementation behaves, only.  It was not a change in the protocol.  The change was not binding on anyone else.
... and that is why we need: http://www.ietf.org/rfc/rfc2119.txt

To be able to know what we can except from other clients and the rest of the network.

bitcoin need standardization or the crappy satoshi client will continue to dictate the path of bitcoin

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 06:36:42 PM
 #82

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
They don't strike me like people who like to write code Smiley
And I guess you never tried to describe what a code does, in a human readable language.
Otherwise you would know that it's impossible.

if you can't describe what your code does, you should stop writing it.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2198



View Profile
July 17, 2013, 06:40:57 PM
 #83

It mutates with every commit to the satoshi client repo. Code is not a standard.
Prior versions do not mutate with commits to GIT. Those prior versions deployed in the network are the reference against which future compatibility is compared.

Refactoring the code to eventually make a better executable specification out of it, isolating out the bitcoin rules from the low level aspects of their implementation and building a great test framwork around all of it would be a very useful goal that would make this more powerful.

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
Just like the rfc's describe what the protocol look like down to the smallest detail, and then don't change it. Describe how clients interact with keyword defined in http://www.ietf.org/rfc/rfc2119.txt.
Having worked on RFCs (Perhaps I'll see you in Berlin in a couple weeks? Will you be at the IETF meeting? I will be speaking in the Technical Plenary.), I don't agree.  Not that I disagree that having a Bitcoin RFC would be a good thing— but I don't actually believe it would usefully solve any of the concerns you wish to solve.  When the behavior must be _exact_ it is exceptionally difficult to write a specification that is correct, and the end result ends up being— effectively— code, though it may be a kind of odd quasi English pseudo-code where no tools exist to actually execute it, analyze it, or test it. Behavior specified in standards is only infrequently tightly bound, in the blockchain rules most of the behavior is tightly bound— there is very little implementation freedom available.

Say we were to have written an RFC for Bitcoin in 2010.  It wouldn't have documented that weird invalid DER signatures were accepted, because we didn't know about that then.  Someone who implemented according to the specification might accept them, or might not, depending on how they implemented their code.  When a block arose that exposed the inconsistency the network would suffer an irreparable fork.  What behavior would win?  That would depend on a lot of things— technical, political, and economic. Most likely the most restrictive behavior would win— since restrictions are only soft-forking from the perspective of the permissive implementation, even if the spec said you must be permissive.  What it _wouldn't_ depend on is what the text of the RFC said.

A non-executable specification is a dead letter in a consensus system. It may be informative. It may be helpful.  But what it cannot be is normative: Normative behavior arises out of participating in the consensus and a non-executable specification cannot participate in the consensus.

Bitcoin will not be compromised
piotr_n
Legendary
*
Offline Offline

Activity: 1652


aka tonikt


View Profile WWW
July 17, 2013, 06:46:02 PM
 #84

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
They don't strike me like people who like to write code Smiley
And I guess you never tried to describe what a code does, in a human readable language.
Otherwise you would know that it's impossible.

if you can't describe what your code does, you should stop writing it.
not, if you still understand what it does.
if the human readable language is not able to express the real meaning of C, why would anyone who knows C limit his further lexical possibilities? Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 07:04:40 PM
 #85

It mutates with every commit to the satoshi client repo. Code is not a standard.
Prior versions do not mutate with commits to GIT. Those prior versions deployed in the network are the reference against which future compatibility is compared.
just because the mutation are compatible to older versions of the satoshi client, does not mean that they are nonexistent. its much better to have a fixed protocol, instaed of just working code.

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
They don't strike me like people who like to write code Smiley
And I guess you never tried to describe what a code does, in a human readable language.
Otherwise you would know that it's impossible.

if you can't describe what your code does, you should stop writing it.
not, if you still understand what it does.
if the human readable language is not able to express the real meaning of C, why would anyone who knows C limit his further lexical possibilities? Smiley
natural language have extremely flexible usages. Natural languages can express c code, but c code cannot express natural language, it works the other way around.

also if you write too complex and super optimized code the first time around, you are properly doing it wrong. write simple and easily understandable code.

i dare you give me a piece of c code(10-20 lines) that i can't explain.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2198



View Profile
July 17, 2013, 07:25:44 PM
 #86

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?

Code:
uint32_t f(int l, uint32_t val) {
  if (l > 16) {
    val = (val >> (l - 16)) + (((val&((1<<(l - 16)) - 1)) + (1<<(l - 16)) - 1)>>(l - 16));
  } else val <<= 16-l;
  return val;
}
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

Bitcoin will not be compromised
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
July 17, 2013, 07:36:59 PM
 #87

Having worked on RFCs (Perhaps I'll see you in Berlin in a couple weeks? Will you be at the IETF meeting? I will be speaking in the Technical Plenary.), I don't agree.  Not that I disagree that having a Bitcoin RFC would be a good thing— but I don't actually believe it would usefully solve any of the concerns you wish to solve.  When the behavior must be _exact_ it is exceptionally difficult to write a specification that is correct, and the end result ends up being— effectively— code, though it may be a kind of odd quasi English pseudo-code where no tools exist to actually execute it, analyze it, or test it. Behavior specified in standards is only infrequently tightly bound, in the blockchain rules most of the behavior is tightly bound— there is very little implementation freedom available.

Say we were to have written an RFC for Bitcoin in 2010.  It wouldn't have documented that weird invalid DER signatures were accepted, because we didn't know about that then.  Someone who implemented according to the specification might accept them, or might not, depending on how they implemented their code.  When a block arose that exposed the inconsistency the network would suffer an irreparable fork.  What behavior would win?  That would depend on a lot of things— technical, political, and economic. Most likely the most restrictive behavior would win— since restrictions are only soft-forking from the perspective of the permissive implementation, even if the spec said you must be permissive.  What it _wouldn't_ depend on is what the text of the RFC said.

Very good summary.  That said the protocol should be better documented.  The client specific features should also be better documented and indicated as such.  I am not blaming anyone but the fact that the code is the spec doesn't mean that the spec "as we understand it" can't be written down outside of the code.  If nothing else it will help to highlight areas of concern "tricky issues", and areas where the spec didn't match execution in the past. 

As time goes on the spec would encapsulate a lot of trial and error, issues, etc.  For people like kokjo they still won't be happy because the spec will need to be updated over time to better reflect the actual expectation of nodes in the wild (which is the "real" protocol).  It won't be possible to say "nope the spec says X so we do X going forward even if it means a catastrophic hard fork because all existing nodes don't do X they do X'".  Still having it all in black and white makes it easier for new developers to get up to speed. 

Plus putting something in black and white allows knowledgable people to spot omissions or inaccuracies.  The spec can include both required behavior and best hehavior going forward (i.e. non-standard signatures are accepted however all nodes should implement checks to ensure that only canonical signatures along with some test examples).

kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 07:59:41 PM
 #88

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?

Code:
uint32_t f(int l, uint32_t val) {
  if (l > 16) {
    val = (val >> (l - 16)) + (((val&((1<<(l - 16)) - 1)) + (1<<(l - 16)) - 1)>>(l - 16));
  } else val <<= 16-l;
  return val;
}
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

a function f is given 2 arguments, one integer named l and and a 32-bit unsigned integer named val and returns a 32 bit unsigned integer.
if the value of l is strictly larger then 16 we reassign the variable val to the sum of:
val shifted l minus 16 to the left(or is it right? im left-right confused!)
the lower l minus 16 bits of val plus 2 to the l - 16 power minus 1, shifted l - 16 times to the left
if the value of l is less or equal to 16 set val to itself shifted 16  - l times to the right
return val

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 08:06:38 PM
 #89

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?

Code:
uint32_t f(int l, uint32_t val) {
  if (l > 16) {
    val = (val >> (l - 16)) + (((val&((1<<(l - 16)) - 1)) + (1<<(l - 16)) - 1)>>(l - 16));
  } else val <<= 16-l;
  return val;
}
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

but no i have no idea of what the code is doing, but it seems like some insanely optimized bit twiddling computation, its probably a estimation of some mathematical function. I really dislike bit twiddling magic, its just as incomprehensible as brainfuck or APL.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
grue
Global Moderator
Legendary
*
Offline Offline

Activity: 1974



View Profile
July 17, 2013, 08:24:46 PM
 #90

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

a function f is given 2 arguments, one integer named l and and a 32-bit unsigned integer named val and returns a 32 bit unsigned integer.
if the value of l is strictly larger then 16 we reassign the variable val to the sum of:
val shifted l minus 16 to the left(or is it right? im left-right confused!)
the lower l minus 16 bits of val plus 2 to the l - 16 power minus 1, shifted l - 16 times to the left
if the value of l is less or equal to 16 set val to itself shifted 16  - l times to the right
return val
But what you're not understanding the function. All you're doing is repeating it word for word. He meant you couldn't explain it colloquially.

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

but no i have no idea of what the code is doing, but it seems like some insanely optimized bit twiddling computation, its probably a estimation of some mathematical function. I really dislike bit twiddling magic, its just as incomprehensible as brainfuck or APL.
hey look, gmaxwell delivered and you failed.

It is pitch black. You are likely to be eaten by a grue.

Tired of annoying signature ads? Ad block for signatures
kokjo
Legendary
*
Offline Offline

Activity: 1050

You are WRONG!


View Profile
July 17, 2013, 09:13:33 PM
 #91

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

a function f is given 2 arguments, one integer named l and and a 32-bit unsigned integer named val and returns a 32 bit unsigned integer.
if the value of l is strictly larger then 16 we reassign the variable val to the sum of:
val shifted l minus 16 to the left(or is it right? im left-right confused!)
the lower l minus 16 bits of val plus 2 to the l - 16 power minus 1, shifted l - 16 times to the left
if the value of l is less or equal to 16 set val to itself shifted 16  - l times to the right
return val
But what you're not understanding the function. All you're doing is repeating it word for word. He meant you couldn't explain it colloquially.

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

but no i have no idea of what the code is doing, but it seems like some insanely optimized bit twiddling computation, its probably a estimation of some mathematical function. I really dislike bit twiddling magic, its just as incomprehensible as brainfuck or APL.
hey look, gmaxwell delivered and you failed.
its a part of a code that computed a overestimate of log_2

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
razorfishsl
Sr. Member
****
Offline Offline

Activity: 406


View Profile WWW
July 18, 2013, 03:37:09 AM
 #92

stop writing code, and sit down and make a standard. Its not that hard, nobody just wants to do it because they are lazy bastard who like to code crap code, instead of doing things the right way.
They don't strike me like people who like to write code Smiley
And I guess you never tried to describe what a code does, in a human readable language.
Otherwise you would know that it's impossible.

if you can't describe what your code does, you should stop writing it.
not, if you still understand what it does.
if the human readable language is not able to express the real meaning of C, why would anyone who knows C limit his further lexical possibilities? Smiley

If you cannot explain something in a simple language.. then the truth is , that you  are only fooling yourself and just don't understand it....


High Quality USB Hubs for Bitcoin miners
https://bitcointalk.org/index.php?topic=560003
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
July 18, 2013, 05:21:49 AM
 #93

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

a function f is given 2 arguments, one integer named l and and a 32-bit unsigned integer named val and returns a 32 bit unsigned integer.
if the value of l is strictly larger then 16 we reassign the variable val to the sum of:
val shifted l minus 16 to the left(or is it right? im left-right confused!)
the lower l minus 16 bits of val plus 2 to the l - 16 power minus 1, shifted l - 16 times to the left
if the value of l is less or equal to 16 set val to itself shifted 16  - l times to the right
return val
But what you're not understanding the function. All you're doing is repeating it word for word. He meant you couldn't explain it colloquially.

i dare you give me a piece of c code(10-20 lines) that i can't explain.

Okay, I'll give you an easy one. How about two statements?
[...]
An implementation of f() constructed from your English description must produce identical results for all possible val and l on the range 0-31 inclusive.

but no i have no idea of what the code is doing, but it seems like some insanely optimized bit twiddling computation, its probably a estimation of some mathematical function. I really dislike bit twiddling magic, its just as incomprehensible as brainfuck or APL.
hey look, gmaxwell delivered and you failed.
its a part of a code that computed a overestimate of log_2

An overestimate of log2 is easy.  It doesn't need two parameters...

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2198



View Profile
July 18, 2013, 06:29:50 AM
 #94

An overestimate of log2 is easy.  It doesn't need two parameters...
He went and found the origin of the code, these particular lines are not a log2 (obviously) but they're used as part of an integer implementation of a log2.

He didn't actually describe what those lines do, which is amusing since there is actually a comment that explains them right above them in the code they came from.

I thought it was a fun example because I know that an adequate programmer can, in fact, understand it purely from the code— since I was given an algebraic simplification of that code (taking advantage of the fact that in the calling enviroment case it's never used with val==0) by a random OSS contributor, and I think that was even before it had a comment explaining what it was doing.

A detailed description of this code ends up being an opaque transliteration which people will convert back to $language incorrectly (noting that kokjo actually did have trouble figuring out what computation it was performing and doubted his understanding of the mere behavior).  While, a high level description "This is (val>>(l-16)), but guaranteed to round up, even if adding a bias before the shift would cause overflow (e.g., for 0xFFFFxxxx)." would almost certainly be implemented incorrectly, as you can see it's a bit tricky and joe-random-programmer doesn't generally know how to make fixed point division round up even before you worry about overflow.  (How many people know about the truncation vs floor behavior of >> and / operators, and that they're not the same in, e.g. C and python or how you convert one to another, or would even realize that they had to take special care— even if the spec called it out?)

I'm sure a sufficiently deft drafter could write a spec that handles this... but this is two lines.  Getting exact behavior when you need to worry about things like overflow and correct performance over the entire range of a machine number is simply hard and a lot of programmers are not mentally prepared for it. Writing spec text which doesn't create hazards can be tricky.

Bitcoin will not be compromised
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
July 19, 2013, 05:05:55 PM
 #95

it makes it nearly impossible to create a alternative client, when the "standard" mutates all the time. bitcoin needs diversity in clients.

Do you have any idea what you're talking about?

The DER encoding for signatures is the most standard one that exists. We've been discussing enforcing the standard for a _year_ before implementing it - because, unfortunately, not everyone was following the same rules.

Do you know why we want to enforce this standard? To make sure Bitcoin can be implemented without relying on OpenSSL.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
hydrogenesis
Newbie
*
Offline Offline

Activity: 17

hydrogen genesis


View Profile
February 10, 2014, 01:36:04 PM
 #96

FYI this issue is re-opened by mtgox and gmaxwell.

https://www.mtgox.com/press_release_20140210.html
https://en.bitcoin.it/wiki/Transaction_Malleability
http://www.cryptocoinsnews.com/2014/02/10/mt-gox-blames-bitcoin-core-developer-greg-maxwell-responds/

Wir müssen wissen. Wir werden wissen.

Trading reputation thread:
https://bitcointalk.org/index.php?topic=448993
mccoyspace
Full Member
***
Offline Offline

Activity: 237


View Profile WWW
February 10, 2014, 01:54:47 PM
 #97

great thread reboot.
a very interesting read.
this issue has been know about for a long time, but it's still here and now it's causing problems.
Zzzack
Full Member
***
Offline Offline

Activity: 168


View Profile
February 10, 2014, 05:17:45 PM
 #98

I was wondering how block intervals relate to this issue.

Would a coin with a 30 minute block interval be more susceptible to such a problem?

Producer
metacoin
Sr. Member
****
Offline Offline

Activity: 304


live free


View Profile WWW
February 10, 2014, 07:08:15 PM
 #99

I was wondering how block intervals relate to this issue.

Would a coin with a 30 minute block interval be more susceptible to such a problem?
The coin itself isn't affected by transaction malleability, as one of the transactions will eventually be mined and at some point the coins will successfully be sent to their destination address as the sender intended. Software written to rely on tracking a txid alone is susceptible to such a problem. A solution would be tracking coins by their confirmed (immutable) outputs rather than tracking the txid that contains those outputs.

Block time specifically, or any function of time, does not have much to do with this.

Florin block explorer: http://florincoin.info
David Rabahy
Hero Member
*****
Offline Offline

Activity: 690



View Profile
February 10, 2014, 09:39:27 PM
 #100

Is there concrete evidence in the block chain?  Are there indeed altered transactions in the pool?  Is Mt. Gox blowing smoke?
usabitcoinbuyer
Jr. Member
*
Offline Offline

Activity: 57


View Profile
February 11, 2014, 05:51:21 AM
 #101

Is there concrete evidence in the block chain?  Are there indeed altered transactions in the pool?  Is Mt. Gox blowing smoke?
In my opinion, the answers are no, possibly, and yes. 

The issue is that I create and broadcast a transaction with TxId "X".  Someone can tweak it to an equivalent (same send and receive addresses) transaction with TxId "Y".  Assuming everything else about the transactions are valid, either one (but not both) might get pulled into the blockchain.  I say there's no concrete evidence in the blockchain because the TxId only has an unambiguous meaning once it's incorporated into a block.  At any given time, it's possible that both "X" and "Y" flavors of a transaction could be floating around in different unmined tx pools, but any given miner should only accept one.  I think Mt. Gox is blowing smoke because everyone else seems to be able to deal with this issue satisfactorily, and the issue by itself doesn't explain all the problems folks are seeing at Gox.

BTC: 1KdiXcLutkEd4X8kqv9oLXnSYfkE2K7tK7
kano
Legendary
*
Offline Offline

Activity: 2100


Linux since 1997 RedHat 4


View Profile
February 11, 2014, 08:46:41 PM
 #102

Interestingly other exchanges are having problems today also ...
Bitstamp and BTC-E
https://bitcointalk.org/index.php?topic=459836.0

Pool: https://kano.is Here on Bitcointalk: Forum BTC: 1KanoPb8cKYqNrswjaA8cRDk4FAS9eDMLU
FreeNode IRC: irc.freenode.net channel #kano.is
Help keep Bitcoin secure by mining on pools with full block verification on all blocks - and NO empty blocks!
roy7
Sr. Member
****
Offline Offline

Activity: 434


View Profile
February 12, 2014, 03:08:41 AM
 #103

Interestingly other exchanges are having problems today also ...
Bitstamp and BTC-E
https://bitcointalk.org/index.php?topic=459836.0

Bter also suspended BTC withdrawals.

RoyalMiningCo: Pools retired. Was fun!
hozer
Sr. Member
****
Offline Offline

Activity: 270


View Profile WWW
February 14, 2014, 02:45:55 PM
 #104

Is there concrete evidence in the block chain?  Are there indeed altered transactions in the pool?  Is Mt. Gox blowing smoke?
In my opinion, the answers are no, possibly, and yes. 

The issue is that I create and broadcast a transaction with TxId "X".  Someone can tweak it to an equivalent (same send and receive addresses) transaction with TxId "Y".  Assuming everything else about the transactions are valid, either one (but not both) might get pulled into the blockchain.  I say there's no concrete evidence in the blockchain because the TxId only has an unambiguous meaning once it's incorporated into a block.  At any given time, it's possible that both "X" and "Y" flavors of a transaction could be floating around in different unmined tx pools, but any given miner should only accept one.  I think Mt. Gox is blowing smoke because everyone else seems to be able to deal with this issue satisfactorily, and the issue by itself doesn't explain all the problems folks are seeing at Gox.

Do you work for Gox?

Have you seen their code?

If not, then you are blowing smoke, and contributing a smokescreen to a market-manipulation coin-robbery of epic proportions.

If any exchange wants an independent review of their code, and a productive environment in which to fix any problems found,  I will do it at no cost for code that will be disclosed to the public. If you have proprietary exchange code, my retainer for an NDA starts at $5000.

We have a bunch of guys with NDAs and 'secret proprietary code' all running around issuing press releases about how the other guy sucks, while the handlers that pay their bills are scooping up all the bitcoins they can before the heroic developers, who have been working on this day and night, issue a magical fix and the price of bitcoin doubles.

If broadcasting transactions to the entire network was a good idea for bitcoin, it's probably a good idea to broadcast the code that runs exchanges too. Unless you like handing your money over to the banksters, in which case I guess I can take your money too.
roy7
Sr. Member
****
Offline Offline

Activity: 434


View Profile
February 14, 2014, 03:07:56 PM
 #105

It might be a good idea to patch this before some enterprising person with excess time on their hands (cough) makes a cloned transaction echobot.

Gotta say Enochian gets props for seeing this so far ahead of time. It's almost too bad someone didn't make an echo bot to force the issue 2 years ago, so it'd have been fixed one way or another before bitcoin was so massive.

RoyalMiningCo: Pools retired. Was fun!
hozer
Sr. Member
****
Offline Offline

Activity: 270


View Profile WWW
February 14, 2014, 04:13:17 PM
 #106

It might be a good idea to patch this before some enterprising person with excess time on their hands (cough) makes a cloned transaction echobot.

Gotta say Enochian gets props for seeing this so far ahead of time. It's almost too bad someone didn't make an echo bot to force the issue 2 years ago, so it'd have been fixed one way or another before bitcoin was so massive.

While Bitcoin is brilliant in that it makes mining significantly more profitable than cracking passwords, we do not yet have an altcoin that creates currency from proof-of-exploit.

So while it's easy to see some of these holes, there are perverse financial incentives that make it significantly more profitable for news media to make superheros and villians of the developers and hackers, depending on which side of the market you are on. In the meantime they have shell companies that tie up all the people who DO see the holes with non-disclosure agreements, and exploit insider access to that information to take the unsuspecting public's money.

The first step is admitting you have a problem.

The second step is charging a retainer any time someone uses the word 'confidential', 'proprietary' or 'shareholder value'
samson
Legendary
*
Offline Offline

Activity: 1106


View Profile
February 14, 2014, 04:44:23 PM
 #107

Well this really came back as a big issue didn't it.
Rampion
Legendary
*
Offline Offline

Activity: 1106


View Profile
February 14, 2014, 05:11:35 PM
 #108

It might be a good idea to patch this before some enterprising person with excess time on their hands (cough) makes a cloned transaction echobot.

Yep, that might have been a good idea

Cheesy

vineyard
Hero Member
*****
Offline Offline

Activity: 504


Win Bitcoin Playing Android Games!


View Profile WWW
February 15, 2014, 12:14:18 AM
 #109

This actually is quite similar to another "corner case" that I've been wondering about.  Consider the following scenario:

User downloads installs bitcoin into a windows virtual machine, the copies the virtual machine to multiple locations.

Each of the virtual machines attempt to engage in transactions (receiving, sending, or even mining and block verification.)

What function is mitigating the collisions between clients, and which client becomes most authorative?  While I see how this could result in issues in transaction confirmation, wouldn't confirmations by those cloned entities result in confirmation corruption?
Collisions are handled by the Bitcoin protocol. When you submit a transaction to the network, miners will begin to try to add it to the block chain. When a miner successfully mines a block, it is added to the block chain and other miners see this and begin working off of the new top block. There is a chance that two blocks are submitted nearly at the same time - and some miners see one block and other see the other block. This results in a fork of the block chain. Some miners will be working on one prong of the fork, while others work on the other prong. At each new block, miners will always begin working on the longest prong. Eventually, the longer prong becomes so long that all mining stops on the shorter prong, and it is orphaned - never to surface again.

DobZombie
Hero Member
*****
Offline Offline

Activity: 756


TheBitcoinMuseum.com


View Profile
February 15, 2014, 01:30:45 PM
 #110

I believe the attack you describe is possible and real, but the effect is less troublesome. As soon as a modified echo of the transaction is included in a block, both sender and receiver will see this transaction too. The old transaction will linger on however, unconfirmed.


Ouch. I don't think he took all the variables when be made this call   Roll Eyes

The Bitcoin Museum is back under my control, but I still need to go through all the code. DO NOT PURCHASE ANYTHING FROM IT

The Biggest Collection of Bitcoin Memorabilia The Bitcoin Museum
Series 2 BitcoinNerd 1g Silver coin thread!
Discount Jewellery! Noella Jean Jewellery



Buy premium Champanges, Spirits & Wines in Australia! My Bitmit Items

Tip Me if you Hate Justin Bieber 1DobZomBiE2gngvy6zDFKY5b76yvDbqRra
TiagoTiago
Hero Member
*****
Offline Offline

Activity: 616


Firstbits.com/1fg4i                :Ƀ


View Profile
February 19, 2014, 07:25:32 PM
 #111

Perhaps i didn't read it right; does malleability cause any issues in the real world for anyone that only deals with confirmed transactions?

(I dont always get new reply notifications, pls send a pm when you think it has happened)

Wanna gimme some BTC for any or no reason? 1FmvtS66LFh6ycrXDwKRQTexGJw4UWiqDX Smiley

The more you believe in Bitcoin, and the more you show you do to other people, the faster the real value will soar!

Do you like mmmBananas?!
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
February 19, 2014, 07:32:00 PM
 #112

Perhaps i didn't read it right; does malleability cause any issues in the real world for anyone that only deals with confirmed transactions?

Potentially.

https://bitcointalk.org/index.php?topic=460944.0

The two issues that would face a user using a stock client would be incorrect reporting of duplicate tx and problems with spending unconfirmed change output.  Both are described in the linked thread. 

There are pull requests to provide better handling of both issues and eventually they will be included in the mainline client. These "fixes" don't make tx id immutable (that will require a protocol enhancement) but they will cause wallets to behave in a more expected manner when they encounter duplicate transactions. The long term solution is to make tx ids immutable (or at least immutable by third party) but that will take a lot longer as it may require a hard fork.
Pages: 1 2 3 4 5 6 [All]
  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!