Who created the Genesis Block?

Where in the world was the computer that mined it running ?

How many computers did Satoshi used to mine the genesis block?

Why did it take 6 days to be created? Did Satoshi rested for one day afterwards?

If you keep reading, I will lead you to a quest to find the answers to these questions using software archeology.

The Genesis Block

Genesis block header hash is this (hex):
 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f
 
Note that it starts with 43 zero bits. Why? The block target difficulty was much lower (around 32 bits), so we can assume Satoshi did this on purpose.

At that time (2009) GPU mining was probably not already implemented (although maybe Satoshi did think about it). GPU mining began to be used around 2011. The first Google trends reference is on April 2011 (http://www.google.com/trends/explore?hl=en#q=GPU%20mine%20Bitcoin)
 
So Satoshi was doing mining on a CPU.
How many CPUs did Satoshi used to mine the first block?

The Genesis Miner

The Satoshi client source code version 0.1 does not have a special routine nor a command line switch to mine a Genesis block. In fact, the Genesis block was hard-coded, which probably means it was generated by another application whose source code is unknown. Nevertheless, since BTCs were essentially worthless at that time, and there was no competition between miners, we can assume he was mining with his own (and just one) personal computer.

The Satoshi PC

A good PC CPU in 2009 could do approximately 2^22 double-hashes/second.
(Taking into account NUMBER_OF_PROCESSORS=2, so two threads mine together). Satoshi client 0.1 did not have an optimization of these double-hashes, by backing up and restoring the intermediate state of the second hash application, so we can assume that the routine that created the genesis block did not had such optimization.

Lets estimate how much time it takes for Satoshi PC to solve the genesis block with 43 zeros:
Initial 22 bits (nonce test/second)
Add approximately 16 bits for a whole day  (86400 ~= 2^16)
Add approximately 2.5 bits to make it 6 days
Total bits: 41.5

So after 6 days there is approximately 17% change he may have found the genesis block. Was he lucky?

So did he let the miner working for 6 days on purpose?

The day Satoshi rested

Let's check the genesis block date/time and block 1 date/time

Block 0:    2009-01-03 18:15:05
Block 1:     2009-01-09 02:54:25 (6 days later!)

Did Satoshi intent was to relate the six days the miner "worked" to create the genesis block to the time God took to create the world in the Genesis book of the old testament? I don't think so, but the relation is interesting!

One thing that we must note is that the block time seems to have been fixed, instead of being continuously updated, as the Satoshi client does. Since the coinbase transaction in the genesis block relates to this date
(by the embedded message: The Times 03/Jan/2009 Chancellor on brink of second bailout for banks), I assume that Satoshi wanted the block date to be identical than the news on The Times.

The nonce mismatch

Now we'll try to check all these conjectures by analyzing the nonce size.
The nonce size in the block header is only 32 bits. Too short to try 2^43  possibilities. Then to achieve 43 bits zero bits in the block header hash, the miner app must have overflowed the nonce approximately 2^11 times, incrementing the bnExtraNonce each time the 32 bit nonce overflowed.

Now let's look at the scriptsig in the coinbase:

04 ff ff 00 1d  (1d00ffff, the Compact representation of Difficulty or nBits)
01 04  (Extra nonce)
45 5468652054696d6573203....

So the extra nonce is only 4, which means that the block was found only after 4 overflows, which means the genesis miner worked for only 4.2 minutes (estimated mean time).

I haven't the slightest idea why these two values (2^11 and 4) differ by 500x.

The explanation that Satoshi did have 500 computers while mining the genesis block is unsatisfactory, since the the number of initial zero bits in block 1 is only 32. Why acquire such computing power to and then never use it again?

One of the possible explanations is that the Genesis Miner did not increment the extra nonce when the nonce overflowed, but changed the destination address of the coinbase transaction. This in turn could mean that the destination  address 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa is not a valid address, but a nonce.

Can you solve the mystery?

Best regards,
 Sergio.

I think this post belongs to the technical group also. Check the original post: https://bitcointalk.org/index.php?topic=170298

Good paper.

There are two other heuristics that can be added to track users,

Let x = sum of the input amounts, minus the amount in the lowest input, minus the fee

1. the "change" address always receives less money than x
2. the "payee" address always receives more money than x

It's interesting that generally anonymity requires a lot of additional resources. Goes against space, performance, bandwidth.

No.  OP_COPY_SCRIPTSIG does not degrade anonymity, since generally (but not always) a single transaction means that all the previns are owned by the same person.

On the contrary OP_COPY_SCRIPTPUB does degrade anonymity, but why not let the users choose the level of anonymity they want?

So we just implement OP_COPY_SCRIPTSIG and make a trailing OP_CODESEPARATOR standard.

For example, the 465k transaction:

https://blockchain.info/tx/659135664894e50040830edb516a76f704fd2be409ecd8d1ea9916c002ab28a2

Would end up using about 150 Kbytes on the wire.

In this thread (https://bitcointalk.org/index.php?topic=164072.0) I showed a strange feature of Bitcoin signature checks. This "feature" can be used to compress transactions while being transferred (more than 95% in some extreme cases)

The idea is to create a new pseudo opcode OP_COPY_SCRIPTSIG. OP_COPY_SCRIPTSIG has a single argument which is the index of the input whose signature script must be copied.
OP_COPY_SCRIPTSIG must be interpreted by the Satoshi client and must be replaced by the exact signature when the Tx is received. so it's transparent to the script verification routines. When the transaction needs to be forwarded, it's compressed again. The use of this pseudo-opcode does not change any transaction verification rule nor it implies a hard fork.

How does it work?

Suppose Alice wish to compress her transactions. She asks the users who send her bitcoins to send her money with a trailing OP_CODESEPARATOR in the output scripts. The Satoshi client is modified to consider this scripts as standard.

Now if she wants to collect a hundred unspent outputs, she just sign the first input scriptSig and fill the remaining scriptSigs with { OP_COPY_SCRIPTSIG,0 }. The same signature can be used in every input, as long as all of them were sent to the same address and have a trailing  OP_CODESEPARATOR in their output scripts.

Since each scriptSig uses normally about 100 bytes, she uses two bytes instead for almost all of them, saving 98% of the scriptSig space.

The output script normally used for "change" can also be compressed, but with lost of anonymity. The idea is to use the pseudo-opcode OP_COPY_SCRIPTPUB that copies the script of one of the output scripts of the previns.  

E.g: A transaction with two inputs and two outputs (one is  returned to the sender as change) looks like this:

Input 0: Previous tx: f5d8ee39a430901c91a5917b9f2dc19d6d1a0e9cea205b009ca73dd04470b9a6, Index: 0,  
  scriptSig: 304502206e21798a42fae0e854281abd38bacd1aeed3ee3738d9e1446618c4571d1
  90db022100e2ac980643b0b82c0e88ffdfec6b64e3e6ba35e7ba5fdd7d5d6cc8d25c6b241501

Input 1: Previous tx:e2ac980643b0b82c0e88ffdfec6b64e2ac980643b0b82c0e88ffdfec6b649f2dc, Index: 0,  
  scriptSig:  { OP_COPY_SCRIPTSIG,0 }.

Output 0:
  Value: 5000000000
  scriptPubKey: OP_DUP OP_HASH160 404371705fa9bd789a2fcd52d2c580b65d35549d OP_EQUALVERIFY OP_CHECKSIG

Output 1:
  Value: 134
  scriptPubKey: { OP_COPY_SCRIPTPUB,0 }.


Best regards, Sergio.

(disclaimer: this post has not been verified by exploit code or even test code. I've relied on code inspection only, so I may be wrong)

There was some discussion (e.g. https://bitcointalk.org/index.php?topic=93390.0) regarding possible coin mixing schemes. I don't any of them have been implemented, but many people have risen such proposals.

Straightforward solution is to combine multiple transactions from different owners into a single one, by combining the inputs and the outputs (possibly changing the output amounts, and adding additional outputs). We suppose here that the scheme does not make use of SIGHASH_ANYONECANPAY. The simplified protocol is this: first all parties build a big mixing transaction, then all parties sign their inputs in turns.

There is a subtle "bug" in the Bitcoin protocol that allows two different inputs of the same transaction to be signed by the same signature. If the parent output contains a trailing OP_CODESEPARATOR, then the subscript inserted into the transaction to be hashed will be empty.
(https://en.bitcoin.it/w/images/en/7/70/Bitcoin_OpCheckSig_InDetail.png seems not to agree with it and I think it is mistaken)

Then any transaction input whose parent output scripts ends with OP_CODESEPARATOR will compute the same hash, and so they will require signatures of the same message. Identical signatures will work.

Attack

Suppose Alice always mixes her coins with random people with the p2p protocol described above. Each time she wants to resend some previously received coins X, she mixes X with a random group.

Suppose Mallory has to pay Alice some amounts x and y.  She builds two transactions Tx and Ty, to be sent to an addresses given by Alice. But in each output script, the last opcode is a OP_CODESEPARATOR. I suppose these transactions will be non-standard, but Mallory manages to send them to a miner or mine a block with them herself.

Alice receives these transactions (*) and now she wants to spend Tx. She start building a big mixing transaction with some people that, among other inputs, spends Tx.

Mallory takes also part of the mixing, but instead of providing her own previous outputs, she provides the output of Ty as an input, and an output address that she controls. When all parties sign the mixing Tx, she first listens to Alice signature, and then replicates it.

Now, Alice has stolen the coins in Ty.

Some time ago I posted about possible problems with the complexity of the script signing method, and I suggested just inserting '*' in the script to be signed, instead of the subscript mess.

(*) I wonder if the Satoshi client will recognize them as for herself.


Best regards,
 Sergio.

I think there is a group of people actively monitoring Bitcoin security: Gavin, Mike, Pieter, Gregory, Luke-jr, and me (Sergio). This list is not exhaustive, of course, as there may be a hundred other people doing it with less involvement. Although I don't work with the core devs, we collaborate. When I found something, I talked with the core devs and then we worked together to diagnose the problem. If you have an idea of a vulnerability, first do some research yourself, better if you write code to exploit it, and then if you still think it is worth investigating further, talk with Gavin. He's will listen to you.

The fact that thieves have failed only mean they didn't tried enough. Think about the vulnerability https://en.bitcoin.it/wiki/CVE-2012-4684. There was a time window where an attacker could have taken the whole network down for days.
Did this happened? No. Why? Because we found the vulnerability before the attackers did.

We've spent so much time thinking about Bitcoin security than we think we're a step ahead of the attackers. This is a game we can generally win, but eventually loose.


Best regards, Sergio.

You're "disappointed".
What kind of i@!@t are you?
Just don't read my damn posts!

Please understand that I'm not trying to go against the core dev team.
I KNOW the did not order anything.

I just want to analyze if there is any piece of evidence that can be used against them.

I suggest everybody willing to read a thriller take a look at the chat log in Bitcoin-dev while the chain fork was taking please and a miners and developers tried hard to agree on what to do. Every line is chilling...

Read it at http://bitcoinstats.com/irc/bitcoin-dev/logs/2013/03/12

Have fun! Best regards, Sergio.

Check this ...

http://bitcoinstats.com/irc/bitcoin-dev/logs/2013/03/12

...
00:22    gavinandresen    the 0.8 fork is longer, yes? So majority hashpower is 0.8....
..
00:23  gavinandresen    first rule of bitcoin: majority hashpower wins
(Gavin wants NOT to take the decision)
..
00:23    Luke-Jr    gavinandresen: majority hashpower has never ruled on a hardfork before
...
00:28    sipa    gavinandresen, Luke-Jr, jgarzik, MagicalTux, Eleuthria: i don't think we can choose the 0.8 fork at this point, there is too much risk
(Sipa uses the word "choose")
...
00:53    sipa    we have ~decided that getting miners temporarily back on 0.7 is the best solution now
(Again Sipa uses the word "decided", but "we" is not clear)
...
01:12    gavinandresen    Everybody mining on version 0.8 should stop mining for now. When you start again in a few hours, you should set your maxblocksize to 500k or less.
(Gavin tells people they "should" stop mining with 0.8 )

Now check this:

http://sourceforge.net/mailarchive/message.php?msg_id=30587843

[Bitcoin-development] Warning: many 0.7 nodes break on large number of tx/block; fork risk
From: Pieter Wuille <pieter.wuille@gm...> - 2013-03-12 00:18

...
Immediate solution is upgrading to 0.8, or manually setting the number of
lock objects higher in your database. I'll follow up with more concrete
instructions.

If you're unsure, please stop processing transactions.

(here Sipa is talking about "instructions"). This word has many meanings, but one of them is "An authoritative direction to be obeyed")(http://www.thefreedictionary.com/instruction)

But the worst part is the alarm itself because it's SIGNED by the dev team:


CAlert(
nVersion = 1
nRelayUntil = 1363051236
nExpiration = 1363064736
nID = 1030
nCancel = 1001
setCancel =
nMinVer = 70001
nMaxVer = 70001
setSubVer = "Satoshi/0.8.0/"
nPriority = 5000
strComment = ""
strStatusBar = "URGENT: chain fork, stop mining on version 0.8"
)

Now that's clearly an order.

En Spanish there is a proverb: "el pez por la boca muere" which means "fish die by the mouth".

http://bitcoin.org/chainfork.html says:

"What is being done: Large mining pools running version 0.8.0 were asked to switch back to version 0.7, to create a single block chain compatible with all bitcoin software."

Yes, I will change the original message to soften that.

The block chain fork has left us with many interesting technical teachings but maybe the most important consequence is legal:

The core developers, made a coordinated and centralized effort to convince control the miners. During this event, more than 51% of the mining hashing power obeyed the advise commands of the core developers. So they have proved they are (at least to some extend) in control of the network. The same argument Patrick Murck used in https://bitcoinfoundation.org/blog/?p=131 can now be used against the code dev team.

Has anybody thought about the legal consequences of this ?

Can the core devs now bear "the legal liability for managing and providing an unlicensed, unregistered pre-paid access program that allows private and unlimited peer-to-peer transactions"?.

Obviously is up to discussion if the core devs suggested to downgrade the version or they commanded to do so. I think the FinCEN will be reading the chat transcripts right now, looking for incriminating words.

Best regards,
 Sergio.
    

There is the command line switch -limitfreerelay to change that.

CVE-2012-4684: Network-wide DoS using malleable signatures in alerts (fixed in 0.7.0)

Private Release Date: 24-AGO-2012
Public Release Date: 01-MAR-2013

Systems Affected

- Satoshi Bitcoin Client (Bitcoin-Qt, bitcoind)
- All Bitcoin clients that mimic the behavior related to the alert system of Satoshi client versions prior 0.6.3

Affected Versions

- Bitcoin version 0.6.3 released 2012-06-25
- Bitcoin version 0.6.2 released 2012-05-08
- Bitcoin version 0.6.1 released 2012-05-04
- Bitcoin version 0.6.0 released 2012-03-30
- Bitcoin version 0.5.3.1 released 2012-03-16
- Bitcoin version 0.5.3 released 2012-03-14
- Bitcoin version 0.5.2 released 2012-01-09
- Bitcoin version 0.5.1 released 2011-12-15
- Bitcoin version 0.5.0 released 2011-11-21
- Bitcoin version 0.4.0 released 2011-09-23
- Bitcoin version 0.3.24 released 2011-07-08
- Bitcoin version 0.3.23 released 2011-06-14
- Bitcoin version 0.3.22 released 2011-06-05
- Bitcoin version 0.3.21 released 2011-04-27

Fixed in version

- Bitcoin version 0.7.0 released 2012-09-17

Overview

Bitcoin protocol has an alert system to spread important news regarding the digital currency. Alerts are signed with a private ECDA key, so only the development team can issue new alerts. Nevertheless, prior version 0.7.0, alerts were identified by the hash of the message, which includes the signature. Bitcoin accepts BED-encoded signatures, which are malleable.
An attacker build new signatures at a high rate by changing the signature of an alert still in circulation and therefore increasing dramatically the number of valid alerts spreading across the network. This leads to halting all Bitcoin nodes in the network by RAM exhaustion in approximately 4 hours. The attack is persistent, since if a nodes restarted get flooded again by online peers.

Details

There different ways an attacker can abuse the malleability of alert signatures:

1.  An attacker may try to fill the RAM of all the nodes by sending 2000 modified alerts, each of 1 Mbyte size, using padding zeros. Such 1 Mbyte alerts would slowly spread through the network, and finally reach every node.

2. An attacker may use the fact that an ECDSA signature consist of two numbers (r,s), and each one can be padded by zeros. By interleaving and extending the zero padding of s and r, the attacker can build a stream of correct signatures whose sizes grows with the square root of the number of signatures generated.
(for example, for X bytes of zero-padding you can generate X different modified signature alerts whose sizes are size(r)=72+i, size(s)=72+X-i for  0 <= i <= X)

This attack can try to exhaust GUI resources. For example, running the attack for 1 hour over a 64 Kbytes/sec link, the attacker is able to produce 321446 alerts. We have not evaluated how Qt responds in each platform to 321446  calls to QMessageBox::critical() without user interaction, but it's plausible that the application halts.

3. An attacker can try to exhaust the victim's computer CPU by:

3.1. Forcing excessive signature verification time (this only happens with the very first small alerts sent, and for old CPUs )

3.2. Forcing excessive iterations of the loop : for (map<uint256, CAlert>::iterator mi = mapAlerts.begin(); mi != mapAlerts.end()

As an example, in the first hour an attacker is able to send 321446 small alerts. The following hour the attacker is able to send 207757 alerts, starting at size 1218. With a 64 Kbytes/sec link, the attacker can send this last alerts at 52 alerts/second. The code block inside the for loop will be executed 321446*52 = 16,890,430 times, and that takes more than a second to process on an average computer, so CPU is exhausted in the loop.

To maximize the damage of an attack, an attacker requires an existing alert that is relevant for all versions of the protocol, and one that will not have expired and is still in the relay interval.  With such alert, the attacker can reach the maximum number of nodes. Because of this, the vulnerability should not be notified to users by using the alert system. By doing so the attacker may receive the tool required to mount the best possible attack.

Attack Scenario

The best attack is to harm the entire network and possibly generate a rush to the coin. To simplify the analysis, we assume that an average connection bandwidth is 64 Kbytes/sec and that each node has 2 GB of RAM, plus 2 GB of swap space. We assume the attacker executes the attack 1 described in the previous section, which tries to exhaust RAM, but leaves the CPU resources intact to keep spreading the fake alerts. If the such an attack is executed, every node in the network will start trashing after 1.5 hours approximately, as Bitcoin application will be using more than 1.5 GB of RAM. After 2 hours, every node running in Windows 32-bits will halt, since the address space of 2 Gb will be filled. After 8.7 hours, every 64-bit node still alive will fill both the 2 Gb of RAM and the 4 gigabytes of hard disk swap space assumed, and the Bitcoin application will halt.

It is supposed that, in Bitcoin-Qt application, QMessageBox::critical() with modal=false will be called for each alert, so the application may crash much sooner due to lack of Windows or whatever GUI resources Qt uses. This is only relevant to Bitcoin-qt and not Bitcoind releases.

Suggested Solutions for the 0.7.0 release

1. Change the way the hash of alerts is computed: exclude the signature from the hash.
2. Reject alert signatures that are not DER-encoded.
3. Check setKnown before checking signatures.
4. Support a special fixed alert message that cancels all previous alerts. This would be a damage control measure if all other protections are violated.

Solutions 1,3 and 4 were implemented in Bitcoin version 0.7.0.

Disclosure Time-line

2012-08-24 - Vulnerability reported to Gavin Andressen and other core devs.
2012-08-24 - Gavin Andressen acknowledges report
2012-08-26 – Private discussions of Gavin Andressen, Gregory Maxwell and Sergio Lerner on how to address the vulnerability.
2012-08-26 – Fix finally scheduled for the 0.7.0 release
2012-09-17 - Bitcoin version 0.7.0 released
2013-03-01 - Patched Bitcoin versions reach 80% of the network nodes upgraded.
2013-03-01 - Vulnerability disclosure

Credit

This vulnerability was discovered by Sergio Demian Lerner, from Certimix.com
Bitcointalk user Enochian was the first to publish BER/DER encoding problems of Bitcoin signatures in this thread: https://bitcointalk.org/index.php?topic=8392.0.
This report was written by SDL.

CVE-2012-4683: Targeted DoS by CPU exhaustion using alerts (fixed in 0.7.0)

Private Release Date: 23-AGO-2012
Public Release Date: 01-MAR-2013

Systems Affected

- Satoshi Bitcoin Client (Bitcoin-Qt, bitcoind)
- All Bitcoin clients that mimic the behavior related to the alert system of Satoshi client versions prior 0.6.3

Affected Versions

- Bitcoin version 0.6.3 released 2012-06-25
- Bitcoin version 0.6.2 released 2012-05-08
- Bitcoin version 0.6.1 released 2012-05-04
- Bitcoin version 0.6.0 released 2012-03-30
- Bitcoin version 0.5.3.1 released 2012-03-16
- Bitcoin version 0.5.3 released 2012-03-14
- Bitcoin version 0.5.2 released 2012-01-09
- Bitcoin version 0.5.1 released 2011-12-15
- Bitcoin version 0.5.0 released 2011-11-21
- Bitcoin version 0.4.0 released 2011-09-23
- Bitcoin version 0.3.24 released 2011-07-08
- Bitcoin version 0.3.23 released 2011-06-14
- Bitcoin version 0.3.22 released 2011-06-05
- Bitcoin version 0.3.21 released 2011-04-27

Fixed in version

- Bitcoin version 0.7.0 released 2012-09-17

Overview

Bitcoin protocol has an alert system to spread important news regarding the digital currency. Alerts are signed with a private ECDA key, so only the development team can issue new alerts. Alerts signatures are checked for every alert that is received. Each check takes some time, usually between 1 and 4 msecs. The verification time does not depend on the correctness of the signature. Therefore an attacker may flood a node with invalid alerts generated on-the-fly at no cost, and exhaust the victim's node CPU.

Details

The Satoshi client prior version 0.7.0 does not define an alert signature verification failure as a DoS attack (using  return DoS(...); ).

A malicious client app can start sending invalid alerts at a rate of almost 3000 alerts/second for a 64 Kbytes/sec link. The victim's computer will reach 100% CPU utilization for the core associated with the ThreadMessageHandler2() thread. Although that thread has priority THREAD_PRIORITY_BELOW_NORMAL, the computer will suffer a noticeable slowdown. The attack works even with a 3 Kbytes/sec bandwidth usage, so even a slow network link can be used for the attack.

Alerts can be as short as 10 bytes. Here is a complete alert (without network message headers) that has an incorrect signature:

    [0, 8, 48, 6, 2, 1, 10, 2, 1, 10]

It has zero length payload and (r,s) = (10,10)

The problem is still present even if you send the attacker sends correct alerts, previously received, since CheckSignature() is called before the signature is checked against mapAlerts. It was verified that, in an average computer, sending a 188-bytes correct alert continuously on a 64 Kbytes/sec link still rises the victim's CPU usage to 100%.

Possible Attack Scenarios

- An attacker has a direct connection to the victim's node.
- An attacker has a direct connections to a set of nodes that, if put off-line, could cut the network in two unconnected components. The attacker may try then to double-spend in each of the components. Since the attack requires very few resources for the attacker, he may try to attack all those nodes at once from a single computer.

Suggested Solutions for the 0.7.0 version

1- Disconnect from any node that sends a bad alert (return DoS(...))
2- Check that an alert is not verified more than once by checking the existence of the alert in mapAlerts before doing a CheckSignature()

Both solutions were adopted in version 0.7.0, although a lower penalty is given to nodes for sending single incorrect alerts.


Disclosure Timeline

2012-08-23 - Vulnerability reported to Gavin Andressen and other core devs.
2012-08-23 - Gavin Andressen acknowledges report and asserts that version 0.7 will be patched against these problems.
2012-09-17 - Bitcoin version 0.7.0 released
2013-03-01 - Patched Bitcoin version reach 80% of the network nodes upgraded.
2013-03-01 - Vulnerability disclosure

Credit

This vulnerability was discovered by Sergio Demian Lerner, from Certimix.com
This report was written by SDL.