So, I think figured out today how the attack worked.

Throughout the day, the chain was spammed with "mimic" pool payout transactions. This was to enlarge the median blocksize.

Then, when the block size hit the required size for the attack, the merkle tree hashing code was overflowed by including >511 tx (these were tiny tx with one input and no outputs) followed by two unique transactions with inputs and outputs. The last two transaction hashes in the tx merkle tree (512, 513) could be replaced with anything so long as they were valid tx hashes, as they didn't actually factor into the block hash. This was due to a bug in tree-hash.c. This was block 202612.

The net effect of this was that you could swap in any tx into the block at positions 512 and 513 so long as they were the same size and were valid.

Here's the interesting part: When the attacker mined 202612, he transmitted two different blocks to the network, both of which had valid block headers, and both of which contained different transactions in index 512 and 513.

Block 202612
Fork 1 (monerochain):

Fork 2 (chainradar, minergate):

Note that both of these above blocks have the same header hash, because the merkle tree code simply ignored including these tx into the tree. If it had, the block header hash would have been different.

So, now half the network had one block, and half had the other, but they both thought they were valid and exactly the same even though they weren't.

Now, here's how the attacker forked the network. Two blocks later, at height 202614, the attacker generated and submitted two new blocks. These blocks contained the transactions below:

Block 202614
Fork 1 (monerochain):

Fork 2 (chainradar, minergate):

Noticed that these two new blocks both contain tx which the other chain already had -- at this point the network forked, because for each network one of these blocks would be invalid because it contained a doublespend of transactions that were already included.

Here's some output from a daemon on the forked network (fork 1, monerochain), from exactly when it hit the fork point:

This has been the most elaborate attack on a cryptocurrency I've ever seen -- it required incredible coordination and took great lengths to hide itself from being see from casual users of the network until it was too late. Of course, we were watching and could tell something was up, so we caught the fork immediately and were able to protect our users by notifying them and the exchanges of it. Still, I'm frankly amazed at the lengths the attackers went to to conduct this attack, and the complexity of it.

We have published an official solution, which is in testing.

https://github.com/rfree2monero/bitmonero/commit/8f17999a87f4f1025e46cc940900a7bdea9747ce

I agree that the C in the codebase in insane and dangerous. In the least, we need to refactor to C++ and comment the code.

The fix is to stop coding in C, which should never be used for distributed consensus, and to refactor the codebase.

1) yes, it's an overflow bug in C.
2) yes, once the nodes all update no more corrupted blocks should be generated. the corrupted block now needs to be hardcoded into the software.

Nah, it was a simple overflow bug, the basic fix is the same, to just fix the horrible C code line that caused it.

The long term fix is just tossing all the horribly dangerous C code that contains naked pointers and moving to something somewhat less terrible like C++.

We're just cranky because most of us haven't slept much 

And I caught the section of code with the problem last night:
https://bitcointalk.org/index.php?topic=583449.msg8665829#msg8665829

Good morning.

It looks like the code I called into question within an hour after this happened last night was indeed the problem code. So, within an hour or so of the attack, I'd narrowed it down to about a page of code, and it looks like we have the first fix this morning.

Now the CN "saviours" have flown in and magically have a similar fix, who knew? The code was obviously orchestrated by someone with an intimate knowledge of the codebase, to the point where:
1) Txs to expand the blockchain were made to emulate pool payout tx so not to raise suspicion.
2) The tx used as inputs for the block that broke consensus was 4 days old so we couldn't find it easily.
3) The mempool was not filled up so as to also give the impression a spam attack was not going on.

There are more notes here:
https://bitcointalk.org/index.php?topic=583449.msg8665829#msg8665829

Here's what happened with us:
We caught the bullshit going on in the network despite efforts to conceal it and caught the fork immediately. We had Poloniex shut down deposit withdrawal as soon as the fork arose, so no one lost their money.

I need to crash. Fluffypony and the other devs will be up soon and will continue diagnosing it.

My guess it that it's a buffer underflow/overflow code relating to the merkle tree code, but I'm not entirely sure. The crazy block that broke the network had the following idiosyncrasies:
- Normal coinbase
- 510 tx with 0.0000000000001 inputs and 0.000000000000 outputs (effective fee 0.000000000001)
- 2 tx at the end of the block with 2.0 inputs and 1.9999999999999 outputs

--> 513 tx total included, possibly overflowing a value related to the merkle tree tx calculation somewhere (for instance, if a binary merkle tree has two branches which are allowed to contain 256 tx each, and then when you get over 512 something bad happens, eg memory access somewhere there shouldn't be)

Now, the outputs of 0.0000000000001 that were used were produced 4 days ago, so it looks like the attackers were well aware of the bug, but needed to expand the block size to get all these outputs into a single block. To do so, they emulated normal pool payout transactions but added high mixin and tx_extra content to bloat the tx. These transactions were otherwise indistinguishable from pool tx payouts, aside from occasionally using strangely large inputs. To not raise suspicion, the tx mempool was not flooded by tx, but rather 4-10 new tx were submitted whenever a new block entered the network (so that the mempool didn't look suspiciously large). Our course, we recognized these as bizarre ealier in the day and were watching the blockchain like a hawk.

Overall, it appears it was an extremely well coordinated attack to exploit an unexpected engineering flaw in the handling of merkle trees. I still don't understand why it happened, but I'm already up way too late and I need to get some sleep.

Someone will pick up where I left off.

Network is forked. Do not move funds, do not spend, we're likely going to have to apply an emergency patch and roll back to before the corrupted block.

Successful attack achieved by including a corrupted block, we're trying to figure out what happened now.

Ah, yes, correct, I'll fix it up above.

Yup, the math/crypto guys that have been hired have gone over it a lot. Unfortunately, it's a rather large change in terms of core code that we'd have to make and right now we're still trying to figure out why even basic stuff in the codebase like network propagation/syncing is dysfunctional. Large, likely hardfork changes like that will be a while off to implement, although it is a really cool idea.

Yes, this is correct. Here is a test pubkey from me:

I will sign using this keyring:

(The first is andytoshi, the second is me, and the third is Satoshi (from the genesis block).)

This is the message:

Using the verify text feature, here's the returned signature for you to validate:

This signature is from either me, or andytoshi, or Satoshi.

If you check the key file, you will also see that generated keys include mainnet V1 addresses (although these aren't used by the program itself).

Thanks! Admittedly I don't follow 100% of the ring signature crypto code that Hein wrote, but the usage and verification is as expected. One thing I did add was sorting to the key ring input based on the public key X and Y values, so that ordering of the keyring did not impact signature generation/verification.

The output for signatures is in Base58, in the format:

I am involved with Monero as a (volunteer) member of the core team, although most of what I do is higher level consulting on how to maintain anonymity using the stock ring signature code. This has been kind of a "rabbit hole" problem of endlessly more things to consider in terms of deanonymization attack vectors, but we should have some publications and proposals out soon that further investigate this that you and gmaxwell will probably be interested in.

As part of ongoing efforts of the Monero Project, a small program has been generated that allows you to do 1-of-N ring signatures using a secp256k1 keypair and a keyring of public keys. The program signs both binaries and text files.

https://github.com/monero-project/urs

To build and install, use this command after installation of Go:

According to the paper, unique ring signatures are anonymous except in the case of signing the same message multiple times (in which case X and Y in the signature appear to be the same).

http://csiflabs.cs.ucdavis.edu/~hbzhang/romring.pdf

A potential usage might be to sign gitian asserts from a trusted keyring anonymously that contains well known members of the Bitcoin project. Another usage would be for members of a trusted community of Bitcoin users to anonymously vote for some proposal by signing it separately and publishing their signatures.

Thanks to Hein Meling for the initial URS implementation, Conformal Systems for their immensely useful libraries, and gmaxwell for inspiration.

Decentralized development means different people will have different opinions, see Mike Hearn versus Peter Todd versus sipa in Bitcoin.

If you can't handle other people having different opinions about the monetary systems of the world, you might be fascist.

It should build pretty much anywhere as it's written in Golang. Initial daemon/wallet will be command line.