What good is a pre-signed header when each signature is only good for one nonce? 

Actually opensource ecc code for the GPU would be pretty nice, and possibly worthwhile.

But mostly, what was going on with that was that I was trying to insure that nobody who didn't have the ability to spend the txOut would be finding the hash.

Pool mining is an existential threat to the future of cryptocurrency.  I understand why people do it, but putting that much control (more specifically putting everyone that much closer to a 51% attack) into the hands of a pool admin is dangerous.

The other 'ringer' is the root of the merkle tree of unspent txOuts.  That allows "rolling root" block chain compression where the oldest blocks can be allowed to fall off the end of the block chain after long enough.

Coinbase txOut is not spendable until more than 100 blocks have passed since it was mined.  Ah, I think I get the attack.  You're saying that *NEXT* time the miner gets a block, he can spend the 1-satoshi txOut from the current coinbase and claim the rest as 'mining fee?'  

Good point.  I'll go make sure it can't happen. coinbase can only have one txOut and it must be the full amount.

EDIT:  I'm editing this thing a lot....

Actually, nope.  It suffices to ensure that the coinbase has only one txOut.  If the miner doesn't make it for the full amount he's due, that's tough toenails; the rest isn't going to appear out of nowhere when he spends his undersized txOut.

How so?  It is my objective to ensure that the person who finds the winning hash is able to spend the txOut.  What better way than ensuring that he needs the Privkey in the first place to form the block that must be hashed? 

Consider how you'd index a search for "triplets" with a hash collision in 35 bits -- except that any 4 of those 35 bits MUST be different between hash A and hash B, and a different 4 bits MUST be different between hash B and hash C.  

Suddenly, you are either trying to write nonces into many buckets of your table (use too much memory) or trying to read from
about ten-thousand different unpredicted places in a simple hash-indexed table (cache abuse).  Of course, you may be able to do that by the time you calculate another signature over the next subnonce....  

I figured out the solution to another problem; unfortunately this solution will completely screw with fine distinctions among hashing algorithms.  Pretty much the only meaningful parameter remaining to tweak is the amount of memory it'll take, because no matter what happens, mining will be CPU-bound by the rate at which miners can calculate signatures.

And yes, that can be parallelized, and GPU'd, and ASIC'd.  I can screw with momentum hash badly enough to make it remain memory size bound, and maybe even somewhat memory bandwidth bound.  But it's gonna be ugly.

You guys want a laugh?  Here's the current block header structure. See if you can spot the ringer.  Hint:  I regard mining pools as an existential threat to the stability of any cryptocurrency.


offset   bytes    block
0        4        0   block version
4        4        0   block height
12       8        0   UNIX timestamp
20       4        0   current target (of this algm, compressed form)
24       4        0   current hash algm
28       4        0   zero, do not use (future update space)
32      32        0   merkle root of current tx tree

0       32        1   hash of prev block
32      32        1   merkle root of current unspent txout set

0       20        2   current nonce (yes damnit, that's huge)
20      32        2   sig of all the above (including nonce) with privkey of coinbase txOut
52      12        2   reserved for SHA2 endbit & length field (it actually uses 8 bytes)

How is this not a request for NNTP?

One of the ways to do momentum hashing is to search for a triplet birthday; that is, find three nonces such that when the block is hashed with each of them, the resulting hashes match (to a certain width). 

There are variations on the theme, some of which work by making it deliberately harder to construct an efficiently searchable compact index (forcing more table searching for each sub-nonce considered).  But the idea is that in order to form any kind of valid *whole* momentum nonce you have find to some number of sub-nonces that have some particular mathematical relationship which you can only find by comparing their results, meaning you have to keep an indexed table of the intermediate results.  The twin paradox says you can find pairs with some related property fairly quickly, but efficiently finding triplets require either lotsa luck or a pretty full table. 

Aw crap, you're absolutely right.  Bitcoin (and pretty much every alt) is using a non-standard variation of Merkle trees which is subject to malleability.   Under some circumstances sequences of transactions could be repeated in a block without changing the Merkle root.  If there are clients that respond differently (reprocess, ignore, or reject block) to the repeated sequence of tx, and somebody puts an attack block out there that contains such a repeated sequence, that could cause a chain fork.  

I can answer some of that.  

Double SHA256 was chosen over single SHA256 to thwart block boundary extension attacks.  

With single SHA256, the mid-state (basis, along with the last block, on which the final hash is calculated) would depend only on the data in the first block.  If this were the case, an adversary finding a collision for just the final block of the header could  substitute bogus data for the last block.  This would result in a fake header having the same hash (although the second block is different).  Finding a one-block collision, in this case, isn't as difficult as you'd hope, because the bitcoin header varies only 12 bytes of the final block.  

By using SHA256D, the final mid state (AND the final block which is hashed starting from that mid-state) depends on every bit of the header, including the bits in the last block.

This makes finding a collision on the whole header much, much harder.

That's why Satoshi picked SHA256D rather than plain SHA256.  

And from that fact alone I knew he must be a crypto pro.  Most beginners, or even talented, interested programmers who haven't done a lot of crypto already, would never have considered the possibility of an extension attack and modified the application of SHA256 to counter it.  The usual thing for everybody except old hands, is that people think of SHA256 as a bulletproof primitive.  But it isn't.  It's sequential, and its state when it comes to any block depends only on the earlier blocks.  

That said, I have absolutely no idea why Satoshi picked secp256k1 for the elliptic-curve stuff.  

And I have no idea what attack Sergio is talking about.  I was pretty sure that with the doubled construction to stop extension attacks, bitcoin's application of SHA256 was flawless.  

Okay...  What's visible in the block is the nonce presented in the block header, which, when the block header is hashed, yields a hash that meets the difficulty target.  You take *that* nonce and deconstruct it into a (64-bit) base nonce and two (smaller, depends on table size) offsets.  The 64-bit nonce being one of the three momentum nonces,  The 64-bit nonce minus the first of the two offsets being the second momentum nonce, and the 64-bit nonce plus the second of the two offsets being the third momentum nonce (and yes, I have made the nonce field in the header much wider to accommodate real memory-hard algorithms.)

Next you take the header and hash it three times - once with each of the three momentum nonces, instead of the original presented nonce.  If the resulting hashes have the required degree of collision, then the presented nonce is valid.  Meaning, it is one of the very few possible presentable nonces among billions which satisfies the triplet property required by momentum hashing.

Nothing that's hard for a small node to check; it has to do a hash, check the difficulty, separate the fields of the presented nonce, do one addition and one subtraction, then do three more hashes and compare the results for collision.

The trick is that because the two offsets are limited in width, the three momentum nonces must all be found in a narrow subrange of the 64-bit search space.  That means that, once you have populated your table with two collisions per hash  target, you can't just start hashing at top speed presenting whatever's in the table along with the new value as a triplet; because if you do, your hashing will rapidly overshoot the subrange and then you won't be able to form triplets that can be encoded that way because you'd have to use offsets that are too big to fit in the limited offset bit width.  

Instead, you have to keep updating your table.  Every time you find a new nonce, you have to evict the oldest nonce found in its table location (the one nearest, or past, the trailing edge of the subrange you're currently searching) and replace it with the new nonce (which is on the absolute leading edge of the subrange you're currently searching).  That way, when you find the next nonce whose hash matches that target, you don't have the too-old entry in your table (now past the trailing edge of the subrange) preventing you from forming a valid presentable hash.  And this means that you have to do a table read and a table write with every new nonce, instead of just a table read.  Writes are much slower, and mean that hashing can't be parallelized much because table contention.


Oh?  I haven't heard of anything dodgy or suspect about the Merkle tree implementation.  What's better about something else?  

It is not necessary that something should actually be more efficient for home CPU's; in fact, if something is truly efficient for ordinary run-of-the-mill home CPU's, that's like a pledge to feed all the poor starving botnet operators. 

And botnet operators are the scum of the earth and I would rather kick them in the face than feed them, so I really and truly don't want anything that wouldn't enable a better class of machine to absolutely run circles around truly ordinary home machines.

What meets my criterion is that different classes of machines, if arranging the various hashing algorithms in order of expected revenue per minute  of hashing, should all end up with a different sequence - and preferably with a different *first* algorithm of the sequence.

I may be misreading the source, but: there is definitely an observable difference between a DoS ban and a penny-flooding disconnection with a rejected transaction.  

And those 1-satoshi transactions, AFAIK, are still getting mined and into the block chain somehow; I would presume that either some node operated by the attacker is mining them, or they are taking advantage of some bug in the security of one of the existing pools.

And it looks to me like a node that repeatedly sends tiny transactions with no fees, at a high rate, eventually gets disconnected due to a "penny flooding rule" - but not DoS banned.  The transaction is rejected, the sender is disconnected, but if the sender tries to reconnect, say, six hours later, they won't be rejected.

And it looks to me like a node that repeatedly sends a tx with an invalid transaction, gets disconnected AND DoS banned, and if the sender tries to reconnect any time in during the next 24 hours, the connection gets rejected.

If this has been fixed, which of these things am I wrong about? Is it not the case any more that the client identifies an incoming tx with a bad signature as an invalid tx?  

It's a good reason to use the new capability in 0.10 bitcoin core client for running with the wallet offline.  

And I think most implementations of the protocol follow the core client's lead about when to disconnect misbehaving nodes and when to reject tx due to penny flooding, but I don't actually know about other clients because I'm not elbows-deep in their code.

While we're discussing ways to make it harder to link IP address to txn creator, I have a related issue. 

How can we make it harder to link IP address to both creator (whose wallet still contains the address of the spent txOut) and recipient (whose wallet contains the address of the newly created unspent txOut)? 

Anytime somebody wants to know who owns a particular txOut (or for that matter who owned it and spent it a long time ago, since the wallet doesn't throw old addresses away)  they can easily find out.

You know those weird one-satoshi transactions that people have been getting spammed with for months and months now?

I knew it was an effort to track users, but today I was elbows-deep in the source code and I just figured out exactly how it works. 

Somebody is using this to figure out who (which IP address) owns (or owned) what txOuts.

Here's what's going on. 

• First, they send a tiny txOut to the address on the block chain whose owner (or former owner) they want to know.
• Second, they connect to a bunch of different nodes and send them bogus transactions that spend that txOut without fees.  Repeatedly.
• They don't know the address's private key, so they can't provide a good signature for that tx.  But they don't need to.
         
  • If they've connected to a machine that has the wallet containing the key of the original txOut whose owner they're trying to find, that node will disconnect them as a misbehaving node, because the keys they provide don't match.
  • If they've connected to a machine that doesn't have the wallet containing the key to the original txOut, That node will just reject the transaction due to penny-flooding prevention and no fees.
       
• Because they can tell which thing happened, they can tell whether the node at this IP address owns, or owned, the address corresponding to the original txOut.

 I knew it was an effort to track users, but today I was elbows-deep in the source code and I just figured out exactly how it works. 

Somebody is using this to figure out who (which IP address) owns (or once owned, since the wallet doesn't throw away old addresses) what txOuts.

Here's what's going on. 

• First, they send a tiny txOut to the address on the block chain whose owner (or former owner) they want to know.
• Second, they connect to a bunch of different nodes and send them bogus transactions that spend that txOut without fees.  Repeatedly.
• They don't know the address's private key, so they can't provide a good signature for that tx.  But they don't need to.
         
  • If they've connected to a machine that has the wallet containing the original txOut whose owner they're trying to find, that node will disconnect them as a misbehaving node, because the keys provided don't match.
  • If they've connected to a machine that doesn't have the wallet containing the original txOut, That node will just reject the transaction due to penny-flooding prevention and no fees.
       
• Because they can tell which thing happened, they can tell whether the node at this IP address owns the original txOut.

Oh crap.  I knew it was an effort to track users, but today I was elbows-deep in the source code and I just figured out exactly how it works.  

Somebody is using this to figure out who (which IP address) owns (or once owned, since the wallet doesn't throw away old addresses) what txOuts.

Here's what's going on.  

• First, they send a tiny txOut to the address on the block chain whose owner (or former owner) they want to know.
• Second, they connect to a bunch of different nodes and send them bogus transactions that spend that txOut without fees.  Repeatedly.
• They don't know the address's private key, so they can't provide a good signature for that tx.  But they don't need to.
          
  • If they've connected to a machine that has the wallet containing the original txOut whose owner they're trying to find, that node will disconnect them as a misbehaving node, because the keys provided don't match.
  • If they've connected to a machine that doesn't have the wallet containing the original txOut, That node will just reject the transaction due to penny-flooding prevention and no fees.
     
• Because they can tell which thing happened, they can tell whether the node at this IP address owns the original txOut.

and THAT , I'm pretty sure, would be why Satoshi said to use an address once and discard it.

Dr. Curtois has a point about secp256k1.  It's more serious than the choice of one of multiple hash functions, which will just get kicked to the curb by difficulty adjustments if it gets broken: Secp256k1 is what actually secures people's coins in Bitcoin and every altcoin I've ever heard of.  There is no known attack, but it isn't as well studied and well vetted as some other curves, and at least one theoretical weakness (which could eventually turn into an attack) has been found.  It doesn't affect mining/block chain security, but if there actually is a viable attack it HORRIBLY affects the security of the coins in the block chain against theft.

I haven't done a damn thing about it yet in the code I'm working on, but that's a pointed reminder that I really need to before I release.  

I'm nervous about it though; as a rule of thumb the more things you change the more chances you're taking on breaking it.  And I'm changing a lot of stuff.

I've discovered a couple ways to "tweak" momentum hash.

I can force contention for the table (1 read and 1 write at an unpredicted location, per hash performed) by using a representation trick, so GPU hashing parallelism gets crushed by a bandwidth-to-main-memory requirement.   So I can prevent pipelined hashing from being done without a need to read and write the table.

The representation trick is rather simple, really:  the "nonce" presented for the final hashing against the difficulty function is presented as a full-width collision nonce plus two n-bit offsets, where your table size (and collision requirement) is 2ⁿ.  If you don't update the table for every hash, evicting old values and inserting new ones, the things stored in the table will get too old to be within the range of offsets.  This also reduces the effectiveness of the Bloom filter implementation by at least 50%; Bloom filter users will have to throw away their filter/tables every so often, losing their momentum, and build new ones.

Thanks for the pointers to Ramhog and Whirlpool.  It's fairly easy to target several memory sizes for Memory-intensive and CPU algorithms, and the ASIC-able algorithms are also easy to find.  But I'm really sort of at a loss to figure out what hashes are better for which families of graphics cards. 

Anyway, GPUs are going to own a lot of the hashing power on this thing for quite a while; aside from the seriously memory-intensive things I'm putting together, GPUs are going to be getting both their own share and the ASIC-able share for the foreseeable future.   And because of awarding an equal number of coins per algorithm, developing an ASIC will only net people 1/algorithms coins anyway; I'm hoping that the prospect of getting 1/10 (or less) of the coins for the effort of developing ASICs will make them a poor business proposition for a long-ish time. But hopefully not forever.   

It's weird to think that if some hash function gets completely broken, the difficulty adjustments will immediately kick it to the curb and after a few quick blocks are awarded to it, life will continue as though it hadn't been broken at all.