Proof of work (PoW) is a fundamental part of Nakamoto Consensus. It has two functions: It is a Sybil resistance mechanism used to select block producers, and it also provides a baseline and always increasing cost for reverting the blockchain. That’s why it is said that PoW secures the Bitcoin blockchain.

Merged mining is a technique to re-use the work spent in securing one blockchain to simultaneously secure another blockchain. In the same way as PoW powers Nakamoto Consensus, merge-mining can power the consensus of different blockchain. The consensus protocol of the merged mined chain can also be Nakamoto, or it may be a variant of it, such as GHOST or DECOR. The action of applying the merged mining technique is often called “to merge-mine”. The only requirement to merge-mine two blockchains is that they use the same block header hashing function (and difficulty check) to obtain the PoW.

The way merged mining works is simple. First, let’s assume there is a primary blockchain (let it be Bitcoin) and a secondary blockchain S. Let h_B and h_S be two new block headers of Bitcoin and S respectively. Let H be an arbitrary cryptographic hash function. To start mining, the merged miner must build the template for h_B such that it references H(h_S) univocally. The mining process changes very little. When mining, miners try to find the nonce that results in the proof of work for h_B that satisfies the difficulty established by the Bitcoin network as usual (i.e SHA256D(h_B) < target_B). However, if the miner finds a Bitcoin block header with proof of work that matches the difficulty of the merge-mined chain (SHA256D(h_B) < target_S), then h_B, h_S, together with some additional header linking information, becomes a valid proof of work of the merge-mined block. The full merge-mined block would contain the PoW and other remaining chain-specific data (i.e. the transactions referenced by h_S). The block is sent to the secondary blockchain network to be appended to the secondary blockchain. With merged mining, two different proofs of work can be created for the price of one.

History

Merged mining is almost as old as Bitcoin. In 2010 Satoshi himself proposed the use of merged mining to secure an hypothetical BitDNS sidechain that would store decentralized domain names. The idea was soon implemented and launched as the Namecoin altcoin. Namecoin began merge-mining with Bitcoin in 2011 to achieve higher security.

During that period, other blockchains followed this trend and began merge-mining with Bitcoin. But it was not all roses. In 2012 LukeJr performed a 51% attack on Coiledcoin, which at that time was merge-mining with Bitcoin. That event showed that merge-mining is not the security panacea for every blockchain, and there must be a high incentive alignment between the new merged mined chain and the previous ones for this mechanism to be secure.

During 2014, another important event took place. Dogecoin and Litecoin where using the same mining function and miners started switching en mass between the two blockchains. When Dogecoin was more profitable, they would all switch to mine Dogecoin, accelerating block production. When the Dogecoin difficulty adjustment kicked in and made it too difficult to mine profitably, they would switch en mass to Litecoin to maximize profitability, and the cycle would repeat. This caused hashrate instability, erratic block rates and token issuance. Afterwards, Dogecoin hashrate became too low to be considered secure. Dogecoin community decided to begin accepting blocks merged mined with Litecoin. As of today, there was no attempt by any miner in one community to attack the other. There are several reasons why no attack was perpetrated: first, merge-mining was beneficial to both communities because with merged mining the block difficulty and block rates could stabilize again. Second, it was also beneficial for miners, who could temporarily double their revenue (until blockchain upward difficulty adjustments ended this grace period). Third, having comparable hashrates, no single miner could easily attack the other chain. Fourth, there was no ideological dispute between Litecoin and Dogecoin communities (we can ask ourselves if there was any sense of belonging in those communities). Miners would just mine the most profitable chain.

Independence

One of the reasons merged mining was historically preferred is that it enables the creation of fully independent blockchains. By independent we mean that those secondary chains can continue to live even if the primary chain pauses due to a technical problem or simply dies out without support by its community. The secondary chain can still continue getting work from the merge miners without a primary chain. In early years, not even Bitcoin had a future assured. One of the reasons the Rootstock sidechain chose merge mining for its consensus protocol (instead of a federated consensus like Liquid) is that Rootstock was created during the Block Size wars, and there was a real risk of Bitcoin being disrupted by attackers or torn apart by a divided community.

Block Rates

An important reason to prefer merged mining over other alternative ways to inherit Bitcoin security is that merged mining lets the secondary chain have a higher block rate.

After Bitcoin, all blockchains created were designed to support higher block rates (lower inter-block times). This is believed to negatively affect decentralization as it can lead to solo miners generating more orphan blocks, forcing them to join larger pools to stay competitive. High block rates have several benefits, the evident one being that user transactions are confirmed faster. A paradoxical benefit of higher block rates is that the reward payout variance is reduced: this in turn reduces the incentives to join large mining pools, which improves decentralization. The block rate represents a usability-decentralization tradeoff and the ideal rate is difficult to find.

Therefore, designers of merged mined blockchains that want to merge-mine with Bitcoin should be very careful with block rates. An average block interval below 10 seconds without adopting more inclusive consensus protocols can put an additional bandwidth stress on merged mining pools, increasing costs, which may put them in disadvantage with non-merged mined pools.

Contenders To Merged Mining

Similar to Nakamoto merged mining, there are other ways to inherit security from other chains. The first known method was implemented by the Mastercoin/OMNI protocol, and was followed by the Counterparty protocol. New projects such as RGB also adopted this method. The method is based on the embedding of the transaction data of an alternate ledger in Bitcoin transactions. In RGB, this embedding still exists, but it is completely hidden inside the Taproot tree. However, neither the Mastercoin/Counterparty/RGB ledger history forms a separate blockchain. The ledger history is simply the sequential list of special transactions embedded in Bitcoin blocks. There are other ways to create separate blockchains that inherit security from a primary chain, generally by trying to fully or partially synchronize the two blockchains. All are based on publishing data in OP_RETURN outputs. Some examples are Veriblock, PoX and Syncchains. With these “synchronized” chains, the reversal of a primary chain block automatically reverses the secondary chain blocks that came afterward. One disadvantage is that they force secondary blockchain nodes to run also primary chain nodes. While linked blockchains can provide shared security (and fast cross-chain transfers), synchronous consensus cannot provide faster block rates for the secondary blockchain without introducing another switched consensus protocol (i.e. Bitcoin NG‘s microblocks). On the contrary, a merged mined chain can use any block rate, although, as mentioned before, there is a threshold that if surpassed merged mining becomes uneconomical due to high bandwidth requirements.

Criticism and Evolution

Merged mined in Nakamoto consensus has been analyzed, and both supported and criticized in research papers. However, all existent research has focused on the practical effects of merged mining on decentralization while there is still a lack of formalization of the method. Academic research has not gone past the Namecoin merged mining method. But this method has been been vastly improved. The launch of the Rootstock Bitcoin merged mined sidechain in 2018 revived research, which led to the discovery of more secure merged mining protocols, such that the fork-aware variants. Some of these improvements were implemented in Rootstock in successive network upgrades. However, the new theoretical research is still scattered in online articles and RSKIPs (Rootstock improvement proposal) and it deserves better documentation. The new variants of merged mining, which will be discussed in a following article, can resist some known attacks. For example, it is generally believed that a merge-mined sidechain can’t be secure against double-spend attacks when the merge-mining hashrate is low (i.e. <10% of the primary chain hashrate), while with some new protocol variants it can (under slightly different security and liveness assumptions).

The Namecoin Merged mining Design

The way Namecoin merge-mines with Bitcoin is simple. At the end of the coinbase field of the generation transaction the miner writes 4 bytes that indicate that an AuxPow record follows. These 4 bytes are called magic bytes and are used by Namecoin to find the AuxPow record easily. Next we find the AuxPow record where the miners must store the root hash digest of a Merkle tree containing the block hashes of the different blockchains that are being merge-mined. Then the treeSize field follows, which specifies the number of merge-mined blocks of distinct blockchains included in the tree, and a treeNonce field that is supposed to help avoid collisions of chain ids, but the design is flawed and this value is unused. The following diagram depicts a Bitcoin block carrying an AuxPow record linking to 4 blocks (W,X,Y, and Z) from 4 different merge-mined blockchains:

For Namecoin nodes to verify the proof of work of a Namecoin block, the block must include data fields containing:

• A Merkle path to prove the inclusion of the Coinbase transaction in the Bitcoin block transaction tree
• The coinbase transaction itself, containing the AuxPow tree root.
• A Merkle path to find the Namecoin block hash in the AuxPow tree.

Namecoin consensus has a rule to verify the merge-mining proof, and the proof of work of the Bitcoin header (ignoring all other fields).

Primary/Secondary Chain Distinction

We generally distinguish a single primary blockchain from all merge-mined secondary blockchains because the secondary blockchains blocks need an additional Merkle proof to allow the verification of the proof-of-work. But from a game theoretic perspective, there is no primary blockchain. All of them contribute to the security budget. If the primary blockchain hashrate went down to 10% of the total merge-mined hashrate, one would be tempted to say that the secondary blockchain has become the primary one, because now that blockchain will probably be the one that paying for most of the security budget. The distinction can be even more confusing because a merge-mined “secondary” blockchain can grab work from more than one “primary” chain, as is the case of Rootstock. While most of the Rootstock hashrate comes from Bitcoin miners, there were times where a small portion of the hashrate came from Bitcoin Cash miners, therefore Rootstock inherited hashrate from two primary chains.

Even if for philosophical reasons one would not want getting hashrate from, for example, Bitcoin SV, this cannot be easily prevented. From the Rootstock consensus perspective Bitcoin and Bitcoin SV block headers look identical (the parent block or difficulty fields could be used to heuristically distinguish them based on the block difficulty, but this wouldn’t be precise). It is therefore possible for Rootstock to have a higher hashrate than Bitcoin by combining the hashrate of all SHA256D based blockchains, including Bitcoin.

Therefore, we stick to a syntactical definition: the primary chains are the ones with shorter merged mining proofs normally having a single block header, and the secondary chains are those requiring an additional block header and its hash embedded in the first.

Blockchain Neutrality

During the 2011–2013 period there were several proposals published in bitcointalk.org forum to perform a Bitcoin hard-fork to abstract out the Bitcoin proof of work in a separate “master” header-chain, and make all merge-mined blockchains’ blocks (including Bitcoin’s) derive from this master header-chain. All blockchains blocks hashes would be part of a single Pow Merkle Tree. However, these proposals didn’t get traction (in general, no Bitcoin hard-forking proposal ever got traction).

In fact, the master header does not need to be part of a chain at all. The header can be tiny and simply specify a Merkle tree root of chain block hashes and the nonce required to mutate the header to find the PoW. As we’ll see in a follow up article, having a timestamp field in this tiny header can improve the security of all merge-mined chains, This imaginary tiny header is depicted in the following figure where X and Y refer to some other merge-mined blockchains:

If this data structure had been adopted, there wouldn’t be any primary blockchain in Bitcoin merged mining.

When we analyze the incentives for miners to secure more than one blockchain with the same proof of work, we must analyze all of them as equal chains. To analyze merge-mining incentives we should think about SHA256D miners (the actual hash function used) instead of Bitcoin miners. We must analyze all merge-mined blockchains and the incentives that blockchains provide to miners.

Merge-mined Sidechains

Bitcoin sidechains increase Bitcoin’s utility and therefore they contribute to Bitcoin’s value. Using sidechains, bitcoiners can perform private payments, create DAOs, and explore innovative use cases without trading their bitcoins for other more volatile coins (sometimes called shitcoins by Bitcoin maximalists). There are currently two Bitcoin sidechains in existence: Liquid (federated consensus) and Rootstock (merged mined).

The Rootstock sidechain offers cheaper payments and Decentralized Finance (DeFi) applications. One of the useful decentralized applications for bitcoiners is self-loans in stablecoin collateralized by rBTC. This solution allows bitcoiners to use fiat denominated tokens and not be forced to sell their bitcoins for their everyday spendings.

It is widely believed that DeFi on Bitcoin will grow significantly in the upcoming years, and new unforeseen use cases will be unraveled in the future. That’s why the majority of bitcoiners support Rootstock and are eager to see it grow faster.

The Rootstock sidechain was specially designed to provide incentives to the Bitcoin community. It incentivizes the participation of bitcoiners, and specially Bitcoin miners by using a merged mining consensus protocol. Bitcoin and Rootstock can successfully be merged mined because of the shared incentives and shared communities.

In the following article I’ll present the Rootstock merge-mining consensus model and I’ll also show several innovations created by the Rootstock community that substantially increase the security of merged mining. I’ll also show how merged mining can benefit Bitcoin by increasing its security budget in the long term.

Summary

Merged mining is a key part of a PoW based consensus protocol that enables a blockchain to inherit security from a primary chain without duplicating the mining costs. Nakamoto consensus using merged mining can lead to a higher decentralization than consensus protocols based on proof-of-authority or proof-of-stake. However, the primary chain security will only be shared with merged mined chains if the association is mutually beneficial. Therefore, merged mining is ideal for Bitcoin sidechains that can add tremendous value to the Bitcoin network. Rootstock, the first Turing complete Bitcoin smart contract sidechain, is merged mined by more than 50% of the current Bitcoin hashrate, and its hashrate grows every year, making it one of the most secure smart contract networks in existence. Rootstock uses a fork-aware variant of the protocol, which will be discussed in the next article.

(this article was originally published in 2020 in the IOV Labs Research Publications. It is republished here with only minor updates to reflect new RSKIPs).

In this article I argue that the 1/64 CALL gas reduction in EIP150 is problematic and I suggest Ethereum 2.0 implement the 1/64 CALL gas lock slightly differently as specified in RSKIP209. Because we identified these problems on time, RSK implemented EIP150, but excluded the 1/64 rule. In this post I explain what I think was the real objective of the 1/64 gas reduction for CALL/CREATE, first described as the “Option A” in EIP114 and later activated in Ethereum Tangerine Whistle hard fork. I argue that the reasons to merge EIP114 in Ethereum were not correctly communicated to the community. The 1/64 rule brings problems to the Ethereum 1.0 platform, and the problems could aggravate in Ethereum 2.0 if not corrected in time.

The History of the 1/64 rule

EIP114 was written by Vitalik in 2016. To understand why Ethereum adopted EIP114 we must first discover the original motivation. EIP114 seems to have a connection with EIP90, but that’s only superficial. Some developers seem to believe that the reasons EIP114 was adopted are related with the repricing of the CALL opcode. However I think EIP114 hides the most probable reason for the change. A glimpse of this reason for EIP114 is hidden in one sentence of EIP150 itself. Let’s review EIP114:

For blocks where block.number >= METROPOLIS_HARDFORK_BLKNUM, make the following changes:

The 1024 call stack limit no longer exists

Still keep track of the call stack depth; however, if the call stack depth is at least 1024 (ie. in and only in those execution environments which would never be reachable in the current Ethereum implementation because they would trigger the max call stack depth exception), a CALL, CALLCODE, CREATE or DELEGATECALL can allocate a maximum of (g * 63) // 64 gas to the child, where g is the remaining gas in the message at the time the call is made, after subtracting gas costs for the call and for memory expansion.

… with this mechanism for enforcing a maximum call stack depth, contracts no longer have to worry about the remaining call stack depth in the execution environment they are running in, and possible attacks or bugs if the depth is too low, and instead only need to worry about the single limiting variable of gas. (emphasis is mine)

The last comment of Vitalik is interesting: having a single limiting element (gas) is better than having two (gas + call depth). This is completely true. But is this the main reason? I think the main reason for the push of 1/64 rule was hidden until EIP150 was published.

The safety reasons for the 1/64 rule

EIP150 (initially committed in April 2017) includes the 1/64 change to the consensus and points to EIP114. The comment in EIP150 about EIP114 is the following:

EIP 114 is introduced because, given that we are making the cost of a call higher and less predictable, we have an opportunity to do it at no extra cost to currently available guarantees, and so we also achieve the benefit of replacing the call stack depth limit with a “softer” gas-based restriction, thereby eliminating call stack depth attacks as a class of attack that contract developers have to worry about and hence increasing contract programming safety. Note that with the given parameters, the de-facto maximum call stack depth is limited to ~340 (down from ~1024), mitigating the harm caused by any further potential quadratic-complexity DoS attacks that rely on calls. (emphasis is mine)

This paragraph argues that the 1/64 reduction increases programming safety because of stack depth attacks, but by the time the EIP was published the Solidity compiler had already adopted the necessary protections for CALLs. EIP150 states that the 1/64 rule makes the CALL cost less predictable. It however does not attempt to measure how unpredictable it may become or how complex for wallets would be to estimate it. A new algorithm to compute the gas estimation was written and merged into geth here a few months before the publication of the EIP. The difficulty of estimating the gas limit of a transaction is a big limiting factor for the adoption of the platform, as I’ll discuss in the following section.

The preference of Vitalik for the 1/64 change must be put in context: when EIP114 was created (June 2016) developers still used the Solidity keywords send() and call() in their contracts. The Solidity compiler did not warn about unchecked send() return value, and often contract authors forgot to manually perform the checks. Therefore it was possible to force a contract to silently fail on send() or call() by reducing the available stack size. Therefore the 1/64 was a protection for already deployed contracts against stack-depth attacks. One of the main reasons for the change wasn’t to improve the platform for future contracts, but to protect developers from their own past mistakes (which could have been induced by a lack of proper documentation). In fact a research estimated that about 1500 already deployed contracts had that vulnerability. This is one of he warnings added in 2016 to the Solidity documentation after several successful attacks on deployed contracts:

Soon the Solidity compiler was improved to emit warnings if the programmer forgot to check a send() or call() return code.

With the warnings and a change in programming habits, the risks of future bugs were reduced considerably. RSK was launched in January 2018, and it probably doesn’t have a single relevant contract vulnerable to this attack. Why should RSK carry the burden of a decision made to protect old contracts? Should Ethereum 2.0 do?

If you’re writing code in EVM assembly, then checking return codes would be one of many many safety checks you would need to consider: it is just a drop in the ocean. It must be noted that Solidity always checked error conditions of contract method calls. Here is how the latest version of Solidity checks for stack-overflow and reverts in method calls:

The other important reason is briefly referred to as “quadratic-complexity DoS attacks that rely on calls”. There is no explanation of what this is so I tried to analyze the possible problems that can lead to quadratic behaviour and found the following: the state cache is a data structure that many Ethereum implementations use to temporarily store the modifications that need to be performed to the state if a contract call does not revert (or rises a OOG exception). It is used by Parity (now OpenEthereum) (storage and accounts), Pantheon (storage and accounts) and Ethereumj (storage and accounts). The original Ethereum design yellow paper did not take into account nor suggested which data structure should be used for this cache. It was left to the implementer to decide. But not all data structures can match the designed gas costs. If a contract performs 1000 nested CALLs, then a single BALANCE query must traverse all 1000 caches until reaching the original state trie, because any of the intermediate call frames could have modified account balances. We can assume that a cache lookup costs approximately 20 gas units because BLOCKHASH, which accesses an in-memory array, costs 20. Then a BALANCE query that travels through 1000 caches should have cost 20K gas instead of 400. The same happens for SLOAD, EXTCODESIZE, and EXTCODEHASH opcodes, but BALANCE and EXTCODEHASH have lower costs. Even if the cost of accessing the cache is low, clearly it wasn’t considered in the design of Ethereum or in some implementations. For example, to perform a BALANCE operation at stack depth 1024, execution has to reach depth 1024 with at least 400 gas left. Before EIP150, BALANCE cost was 20. If a transaction gas limit was 8M gas, it could reach depth 1024 consuming 750K gas, and use the remaining gas to perform about 300K pseudo-random BALANCE calls, which results in more than 300M internal dictionary lookups! After EIP150, with the same amount of gas you can perform a single BALANCE at a depth of 600 approximately. A more efficient attack would be to perform 7000 BALANCE queries at depth 66, resulting in 462K cache queries, possibly taking no more than a few hundred milliseconds. You can see that the same attack before EIP150 forces 665 times more process. Assuming standard SSD access times, if each BALANCE operation ends up in two SSD accesses, then that transaction would take 1400 milliseconds to execute, which is high, but it’s not a realistic attack.

Geth is the only implementation that avoids this extra lookup cost using a journal instead of a cache. For every change made to the state, the journal stores the previous value and the key in an in-memory dictionary. The new value is directly written to the global state. If the same storage cell is modified several times within the same contract call frame, only the first journal entry needs to persist. The only downside of using a journal is that reversion (REVERT or OOG) may result in a non-constant number of operations. However, because each operation can only be reversed only once, we can assume this cost has already been prepaid by state-modifying opcodes, such as SSTORE, CALLs with value and CREATEs. A key/value reversal, which is performed always in-memory and does not require SSD access, should cost about 40 gas, doubling the cost of a BLOCKHASH opcode. This represents, in the worst case, 10% of the cost of BALANCE, 0.8% of the cost of SSTORE, 1.3% of the cost of CALL with value, and 0.1% of the cost of CREATE.

We conclude that the 1/64 change main objective was to increase the locked gas in nested calls, so that the gas to perform state queries runs out quickly. Was the 1/64 rule a good solution?

Gas estimation is important because Ethereum throws the OOG exception too easily in error situations, consuming all transaction gas, which puts the user at a higher risk than strictly necessary. If transactions executed REVERT on errors, maybe users would be willing to set the transaction gas limit equal to the block gas limit, and forget about it. Gas estimation wouldn’t be a problem. When designing RSK I considered changing that behavior, but maintaining compatibility was considered too important.

Gas Estimation in Ethereum

Wallets need to estimate the gas limit required to set for the transaction to be correctly executed. For most wallets the estimation is performed by calling a web3 method named estimateGas. The method name is confusing, because this method does not estimate the amount of gas consumed, but returns the amount of gas that must be paid up-front for the transaction to execute correctly. The real amount consumed may be a lot lower. Ganache is one exception, because it performs its own estimation. But estimateGas works differently in Ethereum and RSK.

The Ethereum’s estimateGas method locally executes the transaction against the state of the best block and returns a viable gas limit with the maximum possible precision. There are at least five obstacles for estimating the gas limit of a transaction:

1. When the transaction is finally included in a block, the state of the system will be different. Called contracts may have changed their internal storage cells and account balances could also be different. Therefore the transaction may fail, consuming all passed gas.
2. Because of the 1/64 rule, a transaction that performs recursive calls will require much more gas paid up-front than the amount it will consume, because each CALL reserves 1/64th of the gas passed. For example, to perform 44 recursive CALLs and execute a contract X in the 44rd level, the Ethereum EVM requires the double amount of the gas paid up-front to be locked by each nested CALL. While the locked gas is returned to the sender, it still needs to be paid up-front. This is especially problematic for the GSN 2.0 that allows the payment of transaction gas in ERC-20 tokens by swapping tokens for ether on a onchain exchange. The unused gas locked in CALLs forces reimbursements by swaping back ether for tokens, and transferring back tokens to the user. The gas overhead of reimbursements and onchain exchange are high.
3. A transaction may remove one or more contracts, if they execute the SELFDESTRUCT opcode. Each destroyed contract refunds 24000 gas. A transaction may require to pay up-front almost twice the gas consumed.
4. Every storage cell that is freed by storing the value zero pays 5000 in gas in advance, but refunds 15000 gas. Again, a transaction may require an up-front payment twice as necessary.
5. A CALL that transfers value requires passing 2300 gas to the callee in advance, even if this gas won’t be consumed.

SELFDESTRUCT and SSTORE refunds (3 and 4) are capped to 50% of the spent gas, and therefore the gas limit has an upper bound that depends on the gas spent. The CALL stipend (5) is similar to the 1/64 rule, but since it’s constant, it’s easier to calculate. Since the same gas amount can be passed from parent to child, and it’s not locked at every call frame, the limit becomes the previous gas consumed plus 2300. But the 1/64 rule (2) is much more difficult to compute and could raise the transaction gas limit to over 100 times more than the gas consumed, in the worst case.

Most Ethereum full nodes perform a binary search to find the minimum gas limit that executes the transaction without reaching a OOG exception. This involves executing the contract multiple times.

Gas estimation in Ethereum requires a binary search

This algorithm is based on two assumptions on the bounds: the transaction will successfully execute with the maximum possible transaction gas limit, and that it will finish with OOG when the gas limit is set below 21K. You can see how this binary search is performed here and here. Because an Ethereum transaction can currently consume up to 12.5 million gas units, in the average case the program will be executed log2(12M) times, which is 23 times. In 2019 I tried to find the worst case for estimateGas, and I created a specific contract using the worst opcodes in terms of time/gas that forces estimateGas to run for 38 seconds in my standard PC. This varies between different nodes (geth, OpenEthereum, etc.) and nodes have evolved but I think this has not changed. I’m assuming the user can be tricked into estimating the gas for a contract created by an attacker. In the Ethereum ecosystem, most users currently rely on centralized Infura nodes for gas estimation. Infura nodes provide this service for free, but they probably had a time-up of a few seconds before aborting. However Infura nodes will need to handle higher and higher loads for gas estimation, because the block gas limit has been steadily rising.

It is possible but cumbersome to compute the gas limit based on the number of nested calls and the gas passed to each, therefore performing a single execution. It seems that Ganache has solved this analytically here, However this requires instrumenting the VM with special code to extract this additional information, and no Ethereum full node does it.

Stateless nodes of Ethereum 2.0 running the EVM runtime will have a hard time estimating gas cost in the worst case. This is because the EVM can query the current gas with the GAS opcode, and can generate a completely different set of pseudo-random addresses to query balance with the BALANCE opcode on each call in the binary search. Therefore the node would need to fetch data from archive nodes from sparsely generated addresses, and return long Merkle membership proofs for each. In the end, stateless nodes will need to rely on centralized nodes for worst case gas estimation.

Gas Estimation in RSK

Since RSK does not implement the 1/64 reduction, gas estimation in RSK can be much simpler. However currently rskj’s estimateGas is imperfect, as it returns the gas consumed rather than the gas limit. However, fixing it is easy, and a pull request to fix it is waiting for approval. It requires instrumenting the VM with minimal code to extract one additional bit of information. It is an exactimator.

Gas Exactimator for RSK

When there is a top level call that consumes less than 2300 gas and does transfer value, we add 2300 gas to the gas limit estimation. This is because, apart from the 9000 gas units consumed when a call transfers value, the call is forced to pass at least 2300 gas units to the calle. In addition, the gas refunds for SSTORE and SUICIDE executions must be either skipped, or re-added by the estimation code. The simplicity of RSK gas estimation means that in the future stateless clients can easily compute transaction gas costs, and the network can remain decentralized.

To remove the stack depth problem without making gas estimation difficult I created RSKIP209. This RSKIP introduces a 1/64 gas lock at each call depth but the locked amount is not immediately refunded, but it is refunded at the end of transaction processing. This allows to easily compute the transaction gas limit as the gas consumed without locks, plus the amount consumed and refunded in locks.

Gas Limit Estimation in The Future

While Ethereum plans to turn its beacon chain in a stateless system to prevent state growth RSK plans to implement storage rent to handle state more efficiently. Storage rent does not need SSTORE/SUICIDE refunds, because the rent system could automatically remove from low latency storage information infrequently accessed. It could either move unused data to a cheaper and slower storage device or remove it completely (a technique called hibernation). Transactions with SSTORE/SELFDESTRUCT refunds may be problematic to users at the current high price of gas, because they may need to pre-pay almost 100% more than the actual consumed amount. Finally, although miners select transactions by higher gas price, transactions with high refunds may be problematic to miners since they can consume twice the CPU gas, and therefore they can delay block generation. Finally, refunds have shown to be useless for the reduction of state size, because few users actively generate contracts that can be cleaned nor transactions with the sole objective of freeing data cells. Newer contracts rarely provide a selfDestruct() method. This is because large refunds can only be monetized through gas tokens with low efficiency. Gas arbitration (acquiring empty cells at low cost to sell them at a higher cost later) has been growing since gas prices in Ethereum skyrocketed. However, gas arbitration is prejudicial to users when used for speculation. Therefore RSK should remove intra-transaction gas refunds in the future and gas prediction will be even simpler. I created the RSKIP243 proposal to remove inter-transaction gas refunds.

This is aligned with the strategic objectives laid on RSK white paper. The main objective being enabling financial inclusion, which requires simplicity, scalability and safety. Compatibility with Ethereum is not RSK’s main objective. Compatibility simplifies the life of developers, but clearly it won’t last forever, since both platforms will diverge when Ethereum 2.0 is launched.

Many Ethereum tests depend heavily on the amount of gas consumed (for example, they execute until OOG). A test that is based on gas consumption, rather than on known and planned data transformations, should not be regarded as a good functional test. EVM compatibility should not be measured by opcode gas costs.

How RSK handles EVM CALLs

An EVM CALL in RSK has a basic cost of 700 (as post EIP-150) but does not restrict the gas passed to callee by 1/64th of the available amount. To reduce the impact of quadratic-complexity attacks to the state cache, it limits the stack depth to 400. Because RSK unitrie data structure stores accounts very efficiently in memory, and because RSK contains a much lower number of accounts than Ethereum, this class of attacks are not currently a problem in RSK. However it would be prudent to change the internal state cache data structure to a journal, as in geth. But introducing a journal is a major change and it would require thorough testing and review.

Preventing Stack Depth Attacks in Meta-transaction Systems

In a meta-transaction system, a user and a relayer can settle a dispute on whether a transaction was correctly executed or not using an on-chain contract. For this to happen, both parties must agree on what is “correctly executed”. Generally they will agree on the call destination address, the call arguments and the gas limit that will be used for the call. In Ethereum, that’s enough, but in RSK, they may have to agree on the maximum call stack free space that the destination contract will expect to work correctly. This is generally enforced by both parties trusting a contract that can only be called externally (checking msg-sender==msg.origin), so the call depth is fixed and known. It would be advantageous in some cases that the instruction set contained a STACKDEPTH opcode, or a precompiled contract existed that could return such value. I created two proposals to overcome this problem: RSKIP203 and RSKIP208. However, if EIP209 is implemented, there won’t be any necessity to check the stack depth anymore.

Summary

The 1/64 rule in EIP150 currently serves two purposes: increases the safety of EVM programs written in assembly, and solves an implementation problem (cache vs journal) at the expense of increasing the complexity of the system in EVM CALLs, and increasing an order of magnitude the cost of gas estimation by wallets and nodes. Also it increases the dependency of light nodes and stateless clients on centralized infura-like servers. Contrary to what is believed, it does not improve security if contracts are written with the latest version of Solidity.

RSK did not implement the 1/64 rule, and therefore it can benefit from an efficient gas estimator (known as exactimator). RSK can in the future improve its cache data structure to prevent quadratic-complexity attacks. It can also provide the same functionality of EIP150 but without harming gas estimation by delaying the CALL refunds until the end of the transaction, as specified in RSKIP209.

We argue that compatibility with Ethereum should focus on the Solidity and web3 interface, which enable easily porting Ethereum dApps to RSK, but not necessarily opcode gas costs. We think that simpler gas estimation will pay back in the upcoming years. Finally we think Ethereum 2.0 should revert the 1/64 rule in EIP150 and implement it as defined in RSKIP209, and also remove iner-transaction gas refunds from the EVM design. This will help for the long term continuity of the platform.

Special thanks to Shreemoy Mishra for the useful suggestions

Me in March 2020. Very little was known about Covid19 back then.

During the pandemic I wrote 27 RSK Improvement proposals totaling 111 technical specifications! That’s so many documents that once I wrote a proposal twice because I didn’t remember I had already written it years before. I also wrote more than 20 articles about RSK, sidechains, merge-mining and blockchain scaling. However, most of this content was spread over different third party blogs, including IOV Labs RSK Blog and IOV Research Labs News site. But Bitslog was the blog that started this journey in crypto, the wick that lit my passion to share Bitcoin and blockchain design ideas. But during these last 2 years I left Bitslog unattended. While in 2013 I posted more than 20 articles, I didn’t post anything in 2021.

To compensate, I decided that I should consolidate all the articles that I have written in the past 2 years in a single place, and therefore I will be re-posting old content in this blog. If you have already read them, then you may skip them. If you haven’t read them, this is your chance to do it.

One of the topics that has been debated endlessly is what kind of hardware Satoshi used for mining. Some people argue he only needed a single computer using the latest generation of Intel processors available in 2009, using a CPU miner with SSE2-optimizations and multi-threading. Others argue that he had about 50 low-end networked computers. In this article, I will shed some light into this topic with some new discoveries. 

But first, a disclaimer: all we know about how Satoshi mined blocks we know from the Patoshi pattern research and the relation between this pattern and Satoshi through some known public transactions between early Bitcoin devs and Satoshi. Because the relation is based on unsigned emails and not math, we’ll never be sure. In this article, to sidestep that debate, we’ll only talk about Patoshi. 

Before we dive into the technical details, the reader has to accept that a single high-end server in 2009 could have mined all Patoshi blocks if running an optimized version of a Bitcoin CPU miner from 2010. We could debate if Patoshi was aware of these optimizations, but from the technical perspective, it’s a solved issue. Some optimizations Patoshi could have easily spotted. For example,  an optimized  SHA256 hasher existed in cryptopp (an open-source and widely known cryptographic library) a year before Bitcoin was created. It would also need some other optimizations that appeared in the Bitcoin code months later of its launch, such as not recomputing the mid-state, and mining in multiple simultaneous threads. But both of them are pretty obvious. Mining multiple 4 nonces simultaneously with SSE2 instructions (also known as 4-way data-level parallelism or SIMD), would be not so easy to code, yet the idea is very old. The latest CPU miners used circa 2012 could scan 8 nonces simultaneously (8-way) with AVX instruction extension. But the AVX opcodes did not exist in 2009, but only SSE2 extensions existed in the latest Intel processors. If you take the Bitcoin source code from late 2010, all the optimizations combined represent a speedup of 10X compared to the public reference miner in Bitcoin v0.1 (approximately 1.5X from starting with mid-state, 4X from multi-threading, and 1.6X from SSE2). In 2010 it’s well documented that a single computer from 2009 could mine all blocks at difficulty 1 to keep the network stable, using only 60% of the CPU.

Here I show the performances of a multi-threaded CPU-miner (4 threads), using SSE2 2-way, 4-way, and AVX 8-way instruction sets. All measurements were performed on the same machine (my intel core i5-4460S @ 2.90GHz).

My computer, the  Intel core i5-4460S, has a performance that is approximately the same as the Intel Core i7-965 Extreme chip,  which was state-of-the-art in 2009. I did my own performance measurements to be sure that the Intel core i7 micro in 2009 could have mined steadily all blocks at difficulty 1. It could even have mined all blocks at difficulty 2. 

Strangely, an implementation of SHA512 using SSE2 optimizations was present in the Bitcoin 0.1 codebase itself, but not one for SHA256. The SHA512 does not implement 4-WAY scan because SHA512 is not used for mining. 

From Speculation to Evidence

Patoshi’s pattern research revealed that Patoshi only scanned a subset of the nonces. We can describe this restriction as a reduction of a single sequential scan interval, the parallelization of 5 sequential intervals, or as the combination of a “selector byte” and a smaller 24-bit sequential scan space (the selector is positioned in the LSB of the nonce). The first two interpretations fit better with the idea of a single computer scanning the nonce space with one or multiple threads. The second interpretation, first proposed by user Eyal0, has given birth to other more sophisticated hypotheses, such as that Patoshi had many networked computers connected in a kind of mining pool. The explanation of the selector byte is also compatible with Patoshi using a rare single parallel computer, such as a TILE64 board, where each processor scans a reduced range. It’s also compatible with using a GPU. To summarize, he could have used any of these machines, and speculation without evidence will lead us nowhere. That’s why a month ago I decided to explore the blockchain to find a definitive answer.

I started by analyzing nonce histograms of the first 18K blocks mined. I chose to analyze only the first 18K blocks because it’s known that Patoshi used a fixed nonce distribution on those blocks. Afterward, Patoshi starts reducing his hashrate by removing parts of the nonce range scanned, and that would ruin the histograms.  The following histograms show the nonce distribution of the 2^32 possible nonce values over 128 buckets for all non-Patoshi blocks in the first 18K blocks, and in the first 50K blocks.

You can see that the probability decays exponentially. The mining difficulty during this period was 1, which means that the whole network finds a block solution after testing 2^32 nonces on average. Why is it that most non-Patoshi miners, which mine much slower than Patoshi, find blocks so “quickly” that it seems that they are scanning 10% of the space? The explanation is simple: all individual miners, on average, find solutions after the same number of nonce tries. However, the histogram of non-Patoshi block nonces combines the output of several individual miners, and therefore the probability that any of them finds a block before reaching the average number of nonces is much greater than each one individually. Keep in mind that the nonce is reset for every new block. As an example, the average number of times you need to throw a dice to obtain the number one is 6, and if after getting a one you restart (a following “round”), then the average number of tries is still 6. But if you throw 3 dices simultaneously, then on average you will be throwing each dice only 2.37 times per round until you find the number “one”.

The following two histograms show the real nonce distribution over in the first 10% of the nonce space, and the distribution obtained by a discrete-event simulation where each individual mining machine has only 4% of the network hashrate.

You can see that both distributions look alike. Can we do the same with Patoshi blocks? We know that Patoshi used one byte of the nonce in a strange way, either mining over a restricted range or mining in parallel over many ranges. Therefore we could ask how the nonce should be distributed if Patoshi scanned the space sequentially or used a selector byte and scanned the remaining 24 bits, as an unsigned integer. Will any of these histograms show a clear decay in probability?

The Mysterious 19

In a recent article, user TechMix discusses the strange behavior of the value 19 in the Patoshi nonce range. Today we’ll reveal this mystery. TechMix, along with user OrganOfCorti identified several subranges in the Patoshi range. These subranges are mined with the same hashrate. The subranges are: [0..9],[19..28],[29..38],[39..48],and [49..58].  Between 9 and 19 there is a nonce gap. We’ll call each individual range of size 2^24 associated with a certain LSB byte a unit range, and therefore each subrange contains 10 unit ranges. The Patoshi subrange boundaries with the nonces outside the Patoshi range (9, 19 and 58) look diffuse in the histogram: the probability of mining on these unit ranges is lower than the rest of the subrange. TechMix was perplexed about the reason. Finding the answer requires abandoning the idea that the pattern comprises a selector byte and a unit range. Here I present the histograms of the nonce unit ranges 9,  19, and 58:

We see clearly that the reduction in probability is just that Patoshi didn’t establish his ranges in terms of unit ranges. The exact positions of the subrange bounds are 163840000, 327680000, and 983040000. The size of the last contiguous range is 655360000. Of course, these are beautiful round numbers obtained by the formula N * 0x4000 * 10^4. To simplify our explanations, we can define a punit to be 0x4000 * 10^4. The punit range is slightly larger than the unit range.  Each Patoshi subranges is composed of 10 punit ranges. For simplicity, we’ll still name the subranges [0..9], [19..28] and so on, even if that naming convention is inexact.          

Scanning by incrementing the Inner or Outer Nonces

To fully understand how Bitcoin mining evolved we need to dig deeper into how SHA256 works and how Bitcoin v0.1, the first public release, was coded. The Satoshi client v0.1 was compiled first for Windows machines, and almost surely for an Intel x86 chip. The x86 architecture is little-endian. SHA256 is defined without a reference to a specific endianness, but making use of uint32 types. SHA256 can be implemented in C language without messing with machine endianness: constants are expressed as uint32 numbers, additions and even bit-shifting operations can be performed on full uint32 types, without ever casting a uint32 pointer to an unsigned char pointer. However, the input of SHA256, the Bitcoin header, is not a list of uint32 values, but an array of bytes. Therefore the SHA256 standard must specify how a list of bytes is converted into a list of uint32s, and how the last internal state of SHA256, which is a list of uint32 values, is converted back to a list of bytes. The SHA256 standard states that the input bytes are considered as if they were read unaltered by a big-endian machine, so the first byte of the Bitcoin header will be the highest significant byte of the first uint32. In a little-endian machine, the first byte is not the MSB of an uint32, so the first 4 bytes must be reversed prior to being processed by SHA256. The same happens for all groups of 4 bytes (20 uint32 in total). Because all fields in the Bitcoin header have sizes that are multiple of 4, one of these groups maps directly to the nonce field. The following diagram shows how the different fields are mapped into uint32s. 

The bitcoin header comprises two 64-byte chunks, split into 16 uint32s. The diagrams names these uint32s from 0 to 15. The Bitcoin client v0.1 incremented the nonce field as little-endian prior hashing, which means that just before hashing, the nonce (and all remaining uint32s) were reversed in memory. The following code in the Bitcoin client shows how it was performed:

Since mining consists mostly of incrementing the nonce and hashing twice repeatedly, it’s clear that the continuous reversal of the nonce and the rest of the fields in the header is unnecessary, because almost all fields except the nonce do not change often. Regarding the nonce, Bitcoin is indifferent to the internal format of the nonce: you can increment it or decrement it, or even rotate it over all possible values using an 32-bit gray code. Therefore the miner can increment the nonce in little-endian or big-endian format and still cover the whole nonce space after 2^32 steps. 

We’ll say that the miner is mining with an outer positive (OP) algorithm, if it increments the nonce before reversal. We say the miner algorithm is inner negative (IN), if it decrements the nonce after reversal of the header fields. The other options are also possible (outer negative (ON) and inner positive (IP)). The first version of Bitcoin was outer positive, in version 0.3.22 (2010) the node adopted an inner positive algorithm to optimize mining.

Since Patoshi was mining with a special software different from the public version, we can hypothesize that he scanned the inner nonce. Under this assumption, we obtain the following histogram. The nonce is reversed and the outer nonce LSB now becomes the MSB of a 32 bit unsigned integer. Because we’ve analyzed the outer nonce LSB before, we already know how the inner nonce histogram would look like:

The histogram shows a slightly increased probability for higher nonces within the Patoshi range. There are two main continuous ranges, [0..9] and [19..58], but we’ll assume that the second continuous range contains 4 subranges, as defined before. We’ll assume that each of the five resulting subranges was scanned in parallel by Patoshi. To test this hypothesis, we show here the nonce histogram of the range [19..58] expanded. Each bucket is only about 2^22 nonces:

The Patoshi inner nonce histogram looked like there was a higher probability for higher nonces, but in this histogram of the range [19..58] I can’t see a clear bias. This is compatible with our hypothesis of a parallel search. To test the hypothesis we can produce an histogram where we subtract to each nonce the lower bound of the subrange it belongs. This is the result:

I can’t see a clear tendency towards higher or lower probability for higher nonces. I needed to be sure what I should expect from this histogram, and therefore I decided to simulate Patoshi mining.

Simulating Mining

I simulated mining a large part of Patoshi nonce space scanning sequentially in the range [19..58] (assuming 64% of hashrate), a subrange [0..9] (assuming 16% of the hashrate), and finally a single unit or punit range (assuming 1.6% of the hashrate). In all cases the miner increments the inner nonce. These are the results of the simulations:

We can see in the first histogram that the last nonce has 25% less chance of being selected than the first nonce. In the second histogram the chances are reduced about 20%. For the unit range histogram, I increased the number of simulation events to get a more precise histogram. Again, the chance decayed 20% in the highest nonces. It seems that Patoshi was not resetting the nonce on new blocks. A new mystery? I needed a new method to analyze the histogram that was independent of the nonce starting point.

Re-Mining Comes to the Rescue

In 2014 I played with the concept of re-mining: searching for other solutions in the same space early miners found one. What can we learn from re-mining? Let’s imagine we find two solutions for the same block header. Let’s momentaneously assume that the miner does not update the block header timestamp nor the transactions contained in it until the blockchain grows by one more block and a new fresh header is created. We also assume that once the nonce hits zero or the maximum value, it wraps-around. When wrap-around happens, the extranonce is incremented and a new block header is built, producing a new nonce search space. The solution chosen by the miner,  the one that exists in the blockchain, will be called the real solution. Let’s assume that the real solution is always the one with lower nonce compared to any other solutions found by re-mining. Then that would be  strong evidence that the miner scanned the nonce space by incrementing the nonce and that the nonce was reset to zero at every new block. If the nonce found was always the highest one, then that would indicate that the nonce space was scanned by decrementing the nonce. Under the assumption that the header is not periodically updated and that we can find enough blocks with more than one solution to achieve statistical significance, it would be easy to detect the nonce scanning direction.

But the stated assumptions do not hold for the whole time required to scan the nonce space, but only for a short time, a short nonce range. This is because miners periodically increment the nTime field, which leads to the creation of a new block header. In the Bitcoin reference client version 0.1, the nTime field is updated every 0x40000 increments, as shown by the following code extract:

Each nonce interval where the block header is unchanged will be called a “nTime slot”. When sampling many blocks with multiple solutions, and looking at a nonce histogram, the percentage of lower nonces picked by the miner vs higher nonces found in multi-solutions can give us information about the size of the nTime slot size. When two solutions lie on different subranges, the percentage can also give us information regarding the parallel sequential relation of the two subranges: a percentage too high or too low would indicate a sequential relation, while a percentage close to 50% indicates a parallel search.

Let’s say we collect a large sample of blocks (i.e. >1000) with multiple solutions, and then we count, for each consecutive pair of multi solutions, how many cases the one with lower nonce is the real solution. We then divide this number by the total number of multi-solution pairs to get a percentage. Let’s call this percentage L. We define H as (100-L). If L is close to 50%, then that indicates the nonce is neither being clearly incremented nor decremented on a single sequence. It may indicate that the nonce was scanned using a non-standard method, such as a pseudo-random order, or a parallel search from different starting points. If L has a noticeable bias towards 0%  or towards 100%, then we have credible evidence of a certain type of mining direction. The closer is L to 0% or 100%, the larger the nTime slot is. Note that if the nonce is never reset between blocks, so it restarts where it stopped, then L still provides the same information. This new method is invariant to the starting point! 

We can make two assumptions regarding wrap-around-zero when scanning the Patoshi nonce range. If there is no wrap-around-zero, and a new header is created when the nonce reaches the subrange boundaries, then the block headers having a low nonce real solution have much higher probability to have an additional solution with higher nonce, while blocks having high nonce real solutions have much higher probability of having additional solutions with lower nonces. However, if the distribution of real nonces over the subrange is uniform, then these two cases would cancel each other and L would be unaltered by the boundary phenomenon. If L is biased towards 0% or 100%, then the boundary phenomenon will amplify the bias, because the bias close to the boundaries will not cancel out. Therefore L is a strong indicator of a sequential mining direction when there is one. If we assume Patoshi started mining at a random initial nonce, and only updated the header when he circularily reaches the starting point again after wrap-around a boundary,, then there is no bias amplification but still L is a good indicator of a sequential mining direction. If you’re are anxious to know the experiment result, just stay one more paragraph with me.

Some Useful Definitions 

We introduce some more definitions to be able to present the results. As previously stated, the real solution of a specific block header is defined as the nonce that exists in the Bitcoin blockchain for that block header. Any other nonce that makes the same block header pass the difficulty test will be defined as an additional solution. Now suppose that we identify all non-Patoshi blocks that have more than one solution for the same block header (at least two distinct nonces that result in hashes below the difficulty target). We define this event as a  multi-solution. Because in Bitcoin v0.1 the slot size is small compared to the nonce space, it’s highly probable that the solutions of a random multi-solution do not lie in the same nTime slot. If solutions lie on different slots, then there is no information we can extract from a multi-solution. For non-Patoshi blocks once every 16384 times (2^32/0x40000) an additional solution lies in the same slot of the real solution, and nTime will not be incremented in-between. Because a miner will on average scan half of a slot of the same block header, we can assure that, on average, a fraction of 1/(2*16384) of the nonce space of every block header does not contain an additional solution. Because in 2009 the block difficulty was 1, and because the number of solutions to be found is directly proportional to the number nonces tested, if we remine blocks scanning the full nonce space, we can expect to find an additional solution of any block with probability 32767/32768.

If we re-mine N blocks, we should find N * 32767/32768 additional solutions. For non-Patoshi blocks, it means that almost all blocks contain a second solution. Of course, some blocks will contain more than two, and some just one. 

Here is the result of re-mining the first 18K blocks, and plotting the non-Patoshi multi-solutions found:

• Total non-Patoshi block: 1405
• Additional Solutions: 1176
• Multi-solutions: 793
• Lower nonce is real solution: 749 (H=94%)
• Higher nonce is real solution:  44 (L=5%)

These results confirm what the nonce histogram taught as: all non-Patoshi blocks are mined with an outer positive algorithm, such as the one existent in the Bitcoin public code. But what happens when we re-ming Patoshi blocks? 

Surprise!

A month ago I started re-mining with a standard CPU. I don’t have access to a GPU nor an ASIC right now. I re-mined all non-Patoshi blocks in the first 18K block only to check that the theory matched the reality (It does). But things became not so clear when I re-mined Patoshi blocks. These are the results I got when re-mining all Patoshi blocks in the first 13.2K blocks of the Bitcoin blockchain. I’m searching the whole Patoshi range [0..9] plus [19..58] to scan for additional solutions.

• Total Patoshi blocks : 10025
• Additional solutions: 1075

Results for inner nonce 

• Lower nonce is real solution: 222 (L=21%)
• Higher nonce is real solution: 789 (H=78%)

Results for outer nonce

• Lower nonce is real solution: 526 (L=51%)
• Higher nonce is real solution: 499 (H=48%)

If nonces were mined uniformly on the Patoshi range,  and Patoshi was scanning the inner nonce, we get L=21%, so there seems to be a clear bias towards picking the highest nonce. This implies Patoshi was using an IN (Inner negative) scanning algorithm. I don’t have a sufficiently convincing explanation which Patoshi was decrementing the nonce instead of incrementing it. 

If Pasohi was in fact decrementing the nonce, then the bias towards high real solution would increase if I reduce the range that I’m searching around the real solution. In fact, our initial assumption was that Patoshi scanned the subranges in parallel. Here are the results obtained for the different subranges:

Whenever I test a range which lies in the middle of the subrange boundaries (i.e. [25..34]), H moves towards 50%. It never reaches 50%  because when two solutions lie in the same subrange, they are still dependent and show the preference for the highest nonce being the real one.

I also tested the cross-interval solution dependence between the range [0..9] and the range [19..28]. There are not so many multi-solution cases which have one solution in the upper range and another in the lower range (only 75). The result was L=38%, which indicates there could be certain dependence, but it’s not sufficient due to the small sample size.  

Because the bias towards picking the highest nonce is significant, we can conclude there is a high dependency in multi-solutions. This suggest two things:

• Patoshi updated the nTime field infrequently during mining (as infrequent as once a minute). 
• Patoshi scanned each subrange in parallel, but within each subrange, he scanned each subrange sequentially. 

The theory that Satoshi had 50 networked seems to contradict the results.

While it’s possible to use the multi-solution distribution to estimate Patoshi nTime slot size or even try to guess the number of sequential ranges scanned, I leave that research for a future article. 

Since reversing the header fields in software takes very little time compared to double hashing the header,  I suspect Patoshi had optimized the miner a lot more than previously thought.  You would only perform the nonce increment close to the SHA256 assembly code if it provides a meaningful advantage. Another reason may be that the scanning was performed on special programmable hardware, such as an FPGA, so wasting gates to reverse the nonce is pointless, and those gates can be used to add more hashers. However, the hashers must have been mining consecutive block nonces (“pipelining” like CPU-miners do with SSE2) and not scanning multiple intervals in parallel. This theory is plausible since SHA256 implementations for FPGAs have been available since 2005. In my opinion, it’s plausible that Patoshi had already performed other more evident optimizations, such as removing the hashing of the first chunk (which stays constant) and start mining from the SHA256 mid-state, and parallelizing the hashing with multiple-threads or SSE2 pipelining.

Flawed Estimations

I missed the opportunity to test re-mining in 2014. My conclusion in 2014 was that I could learn very little from re-mining because the nTime would be changing too fast to expect more than one solution belonging to the same nTime slot.  But it turned out I was wrong, for two reasons. First, I knew that Patoshi mined with a different software than the reference code but I was still assuming his code would be using an nTime slot of size of 0x40000. He was clearly not. Second, I didn’t take into account that even if the nTime were to be updated in sub-second intervals, the resolution of the nTime is just 1 second, so sometimes the updated value would be the same value that existed before.

Summary

In this article I solved the mystery of the Patoshi range boundaries, showing that the boundaries are not aligned with powers of 2, but with multiples of 0x4000 * 10^4. I presented several histograms that do not show a clear exponentially decaying (or exponentially increasing) probability of nonces in Patoshi blocks. I simulated different standard nonce scanning algorithms and realized that all of them produce certain imbalance in the nonce histograms, yet the real Patoshi nonces do not present a clear imbalance. The reason for this mismatch could be that Patoshi’s mining machine did not reset the nonce between blocks, spreading the solutions more uniformly over his mining range, but I couldn’t find evidence of this property. Finally I executed a new experiment: I re-mined Patoshi blocks in order to find additional solutions. I had proposed this experiment in 2014, but I wrongly disregarded it as ineffective. However, it turned out that re-mining reveals a strong tendency of the Patoshi mining algorithm to choose higher nonces when scanning the inner nonce. This tendency suggests the nonce was being decremented, which is the opposite that the Satoshi client version 0.1 does. Since the nonce imbalance decreases when analyzing two subranges together, this suggests Patoshi was scanning the 5 subranges in parallel, but each subrange internally sequentially. This contradicts a theory that Patoshi deployed the first mining farm of 50 independent computers (or any other highly decoupled system) and supports the theory that Patoshi was simply multi-threading in a high-end CPU.

Special thanks to Raul Laprida for helping me with the article. 

Edit: Kim Nilsson found the real Patoshi boundary before me. He sent me an email in January stating that “Patoshi’s nonce is a big-endian number partitioned into ranges of 163840000 values, where only certain partitions are searched while mining.”. Sadly I didn’t pay enough attention that 163840000 was not exactly 2^24*10, nor I understood what he meant by big-endian, and so I had to spent time coding and researching myself I wish I had understood. 
Thanks Kim Nilsson for letting me know and I apologize for not citing your work before! 

about 1.1M bitcoins, and that some people associate with Satoshi Nakamoto. Last time I wrote about Patoshi was in April, 2019. At that time, I posted in order to clarify what we know, technically, about how Patoshi mined. Impossible was for me to foresee that one of the early coinbase being spent recently would cause such an impact in the crazy and uninformed market and the Patoshi pattern would be on the news. Nor I could foresee that a anonymous person would be signing 145 of the early coinbase keys to show a US court how Faketoshi committed fraud, and again everyone would go to check if those coinbases belonged to the Patoshi set. These events triggered an impressive number of tweets, posts and videos about Satoshi. A new wave of Satoshi hunters appeared. But how many people actually pay attention to the technical details? How many computer scientists read my blog? How many paparazzi?

Back in April I posted the following table showing the events where the timestamps of two consecutive blocks were reversed, and by how much time, in average, during the first years of Bitcoin mining:

You can see that the average timestamps deltas (when timestamps are inverted) largely differ between Patoshi and non-Patoshi blocks. I realized in 2019 this was far from normal, but I waited for somebody else to notice the oddity. In 2014, I published about the strange timestamp gaps. Well, it seems that few people reads my post until the end Only one person (that preferred to remain anonymous) also detected the anomaly in Patoshi’s timestamps. Now enough time has passed, and still I don’t have a good explanation for the strange way Patoshi timestamped his blocks. Therefore in this post I will expand that research so that more people can think on this. I’ll also summarize possible (some maybe surprising) explanations. This is yet another mystery about Patoshi blocks, and I only pretend to leave you with more questions than answers.

Let’s begin with an histogram of how timestamps differences (or “deltas”) are distributed between consecutive blocks in the first 50K blocks, when none of the blocks belong to the Patoshi pattern. In the X-axis we show buckets of 10 seconds each, so the labels on the X-axis show time in seconds divided by 10. In the Y-axis, we show the number of events counted for that slot.

Curved traced by the bar graph looks like an exponential distribution, as it should. There curve may not be a perfect exponential, as distributed timestamps are not fetched from an unique global clock, and also timestamps in nodes are not updated in a continued basis during mining, but only every few seconds. Nevertheless the graph looks as one would expect, and the average timestamp delta is 654 seconds.

Now let’s look what happens between Patoshi blocks:

It seems that most block timestamps generally start 312 (about 5 minutes) s seconds after the previous timestamp. Also it appears as if Patoshi refused to mine many blocks after 25 minutes (1500 seconds). This strange pattern is a new way to distinguish the Patoshi pattern from all other coinbase sets. We had three methods already (steep fast extranonce increment, reduced nonce LSB range, no timestamp reversals), and now we add a fourth (and in a next post I will show a fifth!). So why timestamp deltas are oddly distributed is a new unsolved mystery for our large collection. In my opinion, the existence of so many distinguishers is an indicator that Patoshi wanted his/her blocks to be identified.

If you look carefully at the timestamp delta distribution, there are a high number of timestamp deltas before 312 seconds that make for me even more difficult to explain the steep cliff shape. Luckily this one puzzle we can unravel with some information we already know. The reason of this “noise” is a segment in the Patoshi pattern that I named “Double Helix”, because it looks graphically as DNA. Here is a graph of this segment:

You can explore this pattern in SatoshiBlocks website. The double-helix pattern was probably caused by two instances of the Patoshi software/hardware running in parallel. We don’t know if this was a mistake made by Patoshi or it was intended for testing an improved mining setup. But the timestamps between blocks of the two Patoshi lines of the double-helix do not show the same delta distribution, as if internally, maybe due to physical proximity, there was no delay between blocks. Here is the histogram without considering the blocks in the double-helix:

Now it looks much cleaner! The remaining complementary graphs, being timestamps deltas between Patoshi blocks and non-Patoshi blocks and vice-versa, look quite normal, so I’ll omit them.

One may think that Patoshi may have decided to discard blocks when they were mined too close, not to overload the early and frail network, since very few transactions were included in early blocks. However, if we look at the distribution of extranonces between consecutive Patoshi blocks, we can see the curve is still exponential, meaning that no blocks were discarded:

Still it’s possible that Patoshi just turned off his mining equipment for about 5 minutes after mining a block. Is that plausible? How can we explain the differences in timestamp deltas? We provide several hypothesis to the reader:

• Patoshi turned off his mining equipment for about 5 minutes after mining a block. Maybe this was required in order to broadcast the block. Or maybe he was doing it to let other miners mine following blocks. The fact that Patoshi reduced his hashrate in several steps during the first year indicates that he may well be able to do it also at the block granularity. It’s even possible that the increased his hashrate if a block was delayed longer than 12 minutes, which could explain the strange timestamp delta distribution.
• Patoshi software avoided two blocks having the same timestamp. Therefore if a block was mined locally and immediately the mining of a following block began, then the following block timestamp would be artificially incremented a random number not less than 300 seconds.

The artificial addition time to the timestamp seems to be a better overall explanation, because it could also explain why after 25 minutes it seems that Patoshi reduces the number of mined blocks. The correct interpretation of the graph would be that the previous intervals are artificially incremented, and the tail in the exponential probability after 25 minutes is correctly represented.

Because we’re living difficult times, and since science without joy is too boring, I give you some far-fetched and fun explanations of the timestamp delta phenomenon:

• Patoshi was mining from outer space, somewhere in our solar system. It took approximately 150 seconds for the radio signals to travel to his spaceship. To compensate for the delay, and avoid being detected, he/she/it used a real-time clock being 300 seconds ahead of time in earth. His timestamps were faked but that was not noticed on earth. That worked well when mining on top of a block he didn’t create. However, Patoshi didn’t realize that the round-trip time of transmission of his own blocks to and from earth would generate a gap in the timestamps, if not specifically compensated. That’s why we see the gap only between his own blocks.
• Although timestamp LSB (nor the byte with mask 0xff00) in Patoshi blocks have uniform distributions, somehow grinding the timestamp was used to obtain blocks that were more favorable to find solutions for.

That all for today. I encourage you not to trust any of my graphs, and to do the computations yourself. Do not trust any third partes There is always some (low) probability that my software is buggy.

If you find additional (possibly better) explanations, leave me a message here or better ping me in twitter at @SDLerner.

By Sergio Lerner.

Something amazing happened to me. I was leaving a meeting to enter another, disappointed for not being able to gather time to write and preparing for the adrenaline rush that I get when entering a meeting without any notion of the subject in question, when the secretary approached and warned me that someone was looking for me. It was a good excuse to skip the meeting and I slipped into a room where a person was waiting, looking back at the inner courtyard. I closed the door while getting comfortable in an armchair. The man turned a quarter, looking at the wall. “My name is Sandler” – he hurried.

He was old, but something on his face seemed familiar. He spoke quickly and went to the point: “You’re going to be Satoshi Nakamoto.” “Sorry what did you say?” – I answered confused. In the past someone had suggested that I could be Satoshi for a few rare coincidences, but this man talked about the future, not the past. “On August 7th of 2008 you will arrive from the future with the aim of creating Bitcoin” and while saying this he took from his pocket and placed a strange object on the table, a small box that seemed to have been red hot. I had seen many time travel movies, so space-time jump quizzes were fun for me. I immediately ruled out the possibility that he was lying or trying to con me. If something as strange as this happens to you, it must be real, I thought. Sandler seemed not to be surprised by my silence. 

The possibility of creating Bitcoin, having carefully reviewed its source code hundreds of times, seemed an easy and even fun task for me. So, he wanted me to do it, and clearly there were facts about the future and the past that were totally unbelievable. Even stranger than the mysteries about Satoshi I had posted about. I restrained myself from asking “Why me?” before the words reached my lips. That would not have been useful: we both knew I was someone who would accept the challenge. Instead I asked: “Why in this universe?”. Sandler eyes shone. Then, he sighed and leaded in a sentence: “Not in this universe, in all universes.” “That’s ridiculous!” – I exclaimed. “It’s enough to create Bitcoin in our past for Bitcoin to exists in our future.”. Sandler for the first time relaxed. He sat down and I looked straight ahead: he was a very old man and I estimated he was around 90 years old. A man who had never been tall, but strangely preserved the erect shoulder. A man with ruthless irony and tragic logic. “You know what happens in the universe where Bitcoin does not exist?” – he questioned.

I live in Argentina, and I remembered the last bank run where people banged the glass of the banks with pans and the savings that my father lost overnight.  Well, my family had survived. It was not so terrible. I had not spoken a word, but Sandler suddenly shook his head and with his index finger hit the table abruptly. The dry noise reminded me of the hammering of a typewriter and immediately transported me to the movie “Brazil”, the fly that changes a letter on the sheet, and an individual who is nullified, persecuted, through pervasive control of a state almighty. The dystopian world that we may enter any day. How many databases I did not know today contained my name? How many times had they been hacked or misused? Maybe Orwell was wrong for only 50 years. However, I didn’t get carried away by fear. I looked Sandler in the eye and released something pragmatic, worthy of a Chief Scientist of a Bitcoin company as I was at the time: “we cannot take care of all the universes, it is enough for me to be in the correct universe. It is a matter of resource economics.”. But as soon as I said that I felt that it was kind of selfish to say, and I was unconvinced, so I dropped lazy on the couch. “How many are they?” I asked. “There are infinite” – he responded. “Are they countable at least?” I asked again. “Yes. But in every universe where Bitcoin does not exist the suffering is eternal. “. As soon as he spoke these words, I felt that Sandler had abandoned logic to fall into sentimentality. I had found a sore to attack. “If Bitcoin fails in a universe then surely someone will create a next iteration of technology, using Proof-Of- Space-Time or Avalanche. There is no limit to science.” – I reproached him. That was a mistake in his reasoning, I thought. He looked at me with a hint of fury and then he was relentless: “Apparently that doesn’t happen, and I’m not going to risk everything for a weak promise. Bitcoin was an anomaly. It didn’t have to happen, but it happened. Now Bitcoin must be defended. I keep track of the number of universes where I have planted Bitcoin and it is astronomical. Well, not myself, but my person. It is a bit depressing, but what comforts me is the amount of universes that I leave behind where Bitcoin is the universal currency for savings and payments, and ample prosperity is lived. ”

So it was true what Theymos said. We had all the probabilities against. I didn’t know whether to laugh for the achievement or cry for impoverished universes. But I gather forces to try to unravel the problem: “If so, you should go directly to 2008 and look for me then. And not be making unnecessary temporal jumps, wasting energy that you could very well turn into bitcoins. That has more logic. ”- I lashed out. “But in 2008 you were an uneducated slacker! “ – he replied. “You would not have believed me. It took you 5 years to believe in the potential of Bitcoin”- he said. He was right, I had missed all the opportunities to buy cheap Bitcoin because of my insatiable distrust.  “But my time is finite and is running out, and this is a game of coaching inn.” – he added. And then I knew what it was. The purpose of Sandler’s trip was then clear to me. Sandler would make a single temporal jump, and I had to make the next jump, to August 2008, but in another universe. And then I would have to create Bitcoin and disappear without a trace, just like Sandler would do today. 

I spent some minutes trying to imagine what the future would look like: “But at least I’ll have Satoshi’s bitcoins,” I said with some hope. “Those are mined by this capsule, and it will never give you the private keys” he responded. And the time capsule will only turn on again when the blockchain reaches 2 million blocks. “It’s for your own protection” he said, and then Sandler smiled, and his smile was mine, and he was me and we were joined by a bond of resignation and sad pride. And so, we said goodbye. I wanted to ask him who had invented Bitcoin in the first universe, but he was already gone, leaving me the little time capsule on the table. In it, a small display showed an endless number indicating the temporal jumps already made, with unstoppable scrolling like a Ledger wallet display. In another, it showed the hash of the genesis block, waiting for the moment to begin mining. The destination universe, date and time had already been set. Sandler’s project was pharaonic, and I had a small part, a negligible part on it. A point on a line. I had to invent Bitcoin not in this universe, but in another one, and then disappear like Satoshi. Sandler, who was none other than the personality that I would take upon disappearing, would look for another version of myself not in this or that one, but in a third universe, thus spreading Bitcoin among all possible ones, one by one, in a perpetual loop, forming a chain, until eternity.

Inspired on the time-traveler bitcoiner.

Thermodynamic, Game-Theoretic and Cryptographic Security

Nakamoto consensus can be analyzed from three different security angles: thermodynamic[2], game-theoretic, and cryptographic security. Thermodynamic security means that an external attacker who wishes to revert the blockchain must pay a high cost in electricity. Game-theoretic security means that a new non-Bitcoin miner has to invest an enormous amount in hardware and an existing Bitcoin miner that is trying to maximize profit would prefer to stay honest rather than to become malicious (below the selfish-mining threshold).  Cryptographic security sometimes means that under some assumptions it is practically infeasible for an attacker to break the protocol, and other times means that some information is perfectly hidden, meaning no computational power will ever uncover it. But Nakamoto Consensus weakest angle is not cryptographic, so we’ll focus on the first two. Merge-mining is not different in this regard. Between 30% and 51% of Bitcoin miners have been merge-mining RSK, which makes RSK the most secure smart-contract platform on the planet in “thermodynamic” security. Still, before the last network upgrade the game-theoretic security of RSK was quite lower. The reason is that RSK, as a native sidechain, lacks coin issuance and therefore depends solely on transaction fees, which are growing but are still low compared to Bitcoin subsidy. This shortcoming would still exist even if 100% of Bitcoin hash rate were mining RSK. RSK relies on the alignment of long term incentives between RSK and Bitcoin: the fact that RSK adds functionality to Bitcoin, and reduces the value of competing cryptocurrencies.

A previous (and probably broken) “solution”

One “solution”, that pops up in forums and blockchain designs[3] over and over again, is to assign a score to the best chain based on the time the blocks were received. The older the chained blocks are, the higher the score.  When two branches are compared not only the accumulated PoW is used, but this score is also taken into consideration to decide which one is the “right” best chain. The underlying idea is that when the attacker reveals his hidden branch, even if longer, the network will reject it. But this is not a minor change to Nakamoto Consensus: it changes the consensus protocol completely! Without more assumptions on the network topology and synchronicity, it’s very difficult to prove that this method converges to consensus as it depends on the relative times the blocks are received by individual nodes. In fact, if the attacker is strategically positioned in the network, he or she may be able to cheat a specific node, or even split the network into two disconnected components that will never be in consensus again.

Armadillo

Armadillo is the code-name of a solution to the problem of hidden hashing power in merge-mining, and I designed it specifically for RSK in RSKIP110. A fundamental problem of merge-mining is solved with Armadillo. Before, all merge-mining was subsidized, both honest miners and malicious ones were. After Armadillo is fully implemented, malicious miners will be automatically detected and not subsidized. However, Armadillo has a downside: 51% of malicious miners will be able to prevent the RSK network from confirming transactions. The trade-off is nevertheless very positive.

In a nutshell, the old merge-mining tag is replaced by a new tag that contains some ordered bytes of the Bitcoin block ids related to 7 previous RSK blocks, at fixed RSK block heights that are multiples of 64, in a packed field called Commit to Parents Vector (CPV). We’ll call each of these referenced blocks a “milestone”. Some sample milestones are the blocks at heights 64,128,192,256, etc. Milestones can be reversed as any other block, and they don’t affect how nodes choose the best chain. By checking the existence of overlapping milestones in different tags, an observer can discover blocks that belong to the same branch. More precisely, the shared milestones are detected as overlapping segments in the CPV vector. The following diagram depicts the relation between Bitcoin blocks, RSK merge-mining tags, and RSK blocks (milestones and others) during a double-spend attack that attempts a long reorg.

Figure 1. The timeline of a double-spend attack attempt

Figure 1 represents a period of RSK merge-mining, performed by 50% of the Bitcoin hash rate. The attacker, having 25% of Bitcoin hash rate, will solve, on average, one every 4 Bitcoin blocks. The victim is an RSK Instant Exchange that will exchange RBTC for BTC. Let’s analyze the different events. First, an honest Bitcoin block is mined at height 1000, which refers to an RSK block at height 64, which becomes a milestone. Then, the attacker pays the Instant Exchange 10 RBTC in a transaction T that gets included in RSK block 65 (not shown in the figure). The Instant Exchange is supposed to send the BTC to the attacker after 120 RSK block confirmations (approximately 1 hour later, past the RSK block 185). Right after T gets included in RSK block 65,  the attacker tries to build a hidden branch of the RSK blockchain starting from a different RSK block 65 not including the transaction T. While merge-mining, he solves the Bitcoin block 1001, and therefore reveals the RSK merge-mining tag for block 128. The tag doesn’t show a mismatch in milestones because it’s too recent or it represents blocks that are in RSK’s future, but it’s already suspicious because it references a block number (128) that the RSK network has not yet reached. However, the RSK network doesn’t have enough information to signal this as an attack, because it doesn’t reference any non-shared milestone. 

In Bitcoin block 1002 there is another merge-mining tag. This time it is a block mined by an honest merge-miner. Since it’s related to RSK block 128, it establishes another milestone. Now the attacker keeps mining his own RSK branch, but, by chance, he doesn’t solve any Bitcoin block. While the attacker is trying to mine a Bitcoin block at height 1003, he mines an RSK milestone at height 192. None of the RSK blocks privately mined between height 65 and height 128 are published. Then the honest merge-miners mine blocks between 129 and 192, including the milestone 192, but none of Bitcoin headers associated with them reach Bitcoin PoW target so they are not included in the Bitcoin blockchain. Now the attacker keeps mining private RSK blocks until block 210. This time the block header (1005) is a valid Bitcoin block. He has the choice to:

• Discard the Bitcoin block and lose the 12.5 BTC (approximately 125K USD at the current rate) in order to keep building a private RSK branch longer than 210 blocks. Keep his RSK private branch.
• Discard the private RSK branch and desist to carry on with the attack.
• Publish the Bitcoin block, hoping that he mines all remaining confirmation blocks required for the attack before nodes are notified about the anomaly exposed by his tags.

The double-spend attack could be profitable if the double-spent amount were  greater than 125K USD (setting aside the legal and reputational costs for the Bitcoin miner to be exposed by such attack). Therefore,  the Instant Exchange could improve its algorithm to decide how many blocks to wait for confirmation depending on the transacted amount. It could wait for N RSK blocks, plus one additional block per thousand dollars exchanged. Note that this generally works, but it doesn’t take into account composed (simultaneous) attacks, such as concurrent atomic swaps.

In the example, the attacker publishes the Bitcoin block but continues with the attack, hoping that the nodes won’t be notified on time about the anomaly exposed by his tags. But monitoring nodes see the anomaly of two milestones stated in the Block’s CPV field (blocks 128 and 192) that were not shared with the RSK best-chain. This represents a malicious fork of length between 82 and 125 blocks, therefore nodes will stop confirming transactions until the risk dissipates. The attacker will never receive the BTC he originally paid for, so the double-spend attack is neutralized. The anomaly disappears when block 211 is revealed. At RSK block 211, the attacker, who has already outperformed the honest best chain and has mined more than the 120 blocks required by the Instant Exchange, decides to give up, because he doesn’t receive the BTC. He reveals the hidden branch in order to get at least some transaction fees and the RSK network switches to the attacker’s branch, where the transaction T is missing and the RBTC was never sent to the Exchange. During the attack, nodes will be in a “Safe Safe mode” (explained later) and will have paused any economic activity, so they won’t be affected by the reorg.

While the full potential of Armadillo will be reached in following project milestones, the core change to the merge-mining tags that enable the whole system has already been activated. In the future, RSK security could match or even surpass Bitcoin’s security[4].  We must note that Armadillo is not bulletproof: it works well for economic nodes that require a high number of RSK block confirmations (i.e. 120, or about 1 hour), such as two-way pegs and exchanges, but it doesn’t improve security for nodes that accept payments with few confirmations. 

New Monitoring Nodes

The full system requires at least a node in the network to be connected to both the RSK network and the Bitcoin network, running a special software module in the RSK node that monitors and detects malicious RSK forks by inspecting the Bitcoin blockchain. The members of the RSK federation are already connected to both networks, so they can easily perform this function cheaply and automatically for the benefit of the network. However, any user can take the role. 

To understand what the monitor module does, I’ll first explain the consensus changes that occurred. New data was added to the RSK tag that enables an observer to associate the tags that belong to the same RSK blockchain branch. An attempt to create a parallel chain of RSK blocks can then be detected with high probability by monitoring the tags and reconstructing the graph representing transitive parent-child relations. Even if the RSK blocks mined are never sent to the RSK network, the tags contain enough information to build the probabilistic graph of RSK block parents.

Decentralized Alerts and the “Safe Safe Mode”

A monitoring node recreates the graph of RSK block relations on the arrival of every new Bitcoin block[5]. The first monitoring node to create this graph will be the first to detect a malicious fork, and it will create and broadcast a decentralized alert called Malicious Fork Proof (MFP). An MFP consists of multiple SPV proofs containing interconnected block headers together with the associated RSK tags (via Merkle membership proofs), and additional confirmation headers if needed. All headers serve as proof of work, and set a minimum cost for the creation of fake proofs. This prevents alerts spam. An MFP can prove the existence of a non-best branch consisting of a high number of RSK blocks. Figure 2 shows how an MFP is built by a monitor node. As soon as the node detects a fork, an alert will be broadcast. Also, a new MFP will be distributed every time the attacker mines another Bitcoin block and the fork persists. The Instant Exchange node will remain in Safe Safe Mode and refuse to accept the RBTC deposit (and any other transaction) until the alert automatically clears after the honest best-chain has outpaced the attacker’s branch or otherwise. The following diagram depicts how alerts are propagated.

Figure 2. Alert messages (MFPs) are propagated thought the RSK network

All RSK nodes are able to verify a received MFP and, if it’s correct, forward it to all connected peers, even without being connected to the Bitcoin Network. RSK nodes that receive valid MFPs can extract information about when the attack will take place (block numbers) and enter a Safe Safe Mode during this interval. 

Historically, Bitcoin had a “Safe Mode”. A Bitcoin node would enter this mode upon reception of a valid alert message, and in this mode it would not confirm any transactions through the UI nor through the RPC interface. The problem with Bitcoin’s Safe Mode is that it was centralized: alerts were centrally issued and signed by a private key that too many developers had access to. But RSK MFPs are fully decentralized and self-verifiable. They can be produced anywhere and producing a fake proof carries a high cost in PoW. This means that an attacker that wants to hide a selfish RSK branch must renounce to mine Bitcoin during the attack. A back-of-the-envelope calculation yields that a 200 RSK block (1.5 hours) reorg attack costs about 300K USD, for a mining pool having 25% of Bitcoin’s hashrate, while the same attack in Ethereum costs 200K according to crypto51.app.

The New Tag Format

The 32-byte block header hash is replaced by a 32-byte byte array with the following format:

• 20-byte prefix of the hash-for-merge-mining (PREFIX)
• 7-byte Commit-to-Parents-Vector (CPV)
• 1-byte number of uncles in the last 32 blocks (NU), limited by 255.
• 4-byte Block Number (BN)

Figure 3 shows the transformation of the tag.

Figure 3. The old and new merge-mining tags

The four fields must be checked in consensus. The hash of the RSK header is truncated to 20 bytes so that the tag still occupies 32 bytes, therefore maintaining compatibility with poolservers software. The NU value is used to predict the difficulty of the attacker’s branch, because in RSK difficulty depends on the number of uncles per block.

The Security of the New Tag

We’ve set our goal that RSK merge-mining be safe from any rational attacker and also from an irrational attacker with the capability of computing 2^80 hash operations in not less than 30 seconds. We ensure that the rational attacker would prefer to behave honestly and merge-mine an RSK block requiring only about 2^69 operations (the current difficulty of an RSK block) and being fully subsidized by Bitcoin, rather than to carry on the costly attacks. We do not consider the possibility of the composability of this attack with other merge-mined systems (which apart from namecoin, do not yet exist).

An irrational attacker that attempts to perform 2^80 hashing operations would need to invest 2000 times more hardware than the rational miner, and its electricity consumption would not be subsidized. The investment would amount about five trillion dollars (5e12), assuming the attacker uses hardware similar to state-of-the-art Bitcoin ASICs. But things are even worse for the irrational attacker, as it can produce one or more blocks that share the proof of work for the same RSK block height, and we’ll see later that this does not generally provide any monetary gain to the attacker [6]. So that’s five trillion dollars wasted. Therefore the 80-bit-security is well balanced across all components, and there is no component with substantially weaker security that can be a target of attack. To justify this, we’ll shortly and informally review possible targets of attack.

First, RSK compresses the generation transaction with a non-standard cryptographic trick. Instead of providing the full generation transaction, it transmits only the tail. To still be able to produce the right cryptographic hash of this message, it starts hashing from a midstate of the Merkle–Damgård construction, instead of the initial state. This 64-byte midstate is transmitted along the tail. 

Figure 4 shows the merge-mining proof. The blue boxes represent the data that is actually included in the proof.

Figure 4. The merge-mining proof (blue) comprising only the tail of the generation (or coinbase) transaction.

Securely using this trick requires assuming a property from SHA256 that is stronger than collision and pre-image resistance, known as “freestart collision” resistance, and we need this to be at least as secure as brute-forcing 80 bits, which is our target security threshold. SHA-1 (an already broken hash function) has a best known free-start attack that requires brute-forcing about 80 bits. No freestart collision has been found in SHA256, and the best results[7] correspond to finding semi-free-start collisions in a reduced-round version of SHA256 (38 of the 64 rounds, at a cost of 2^65 operations), so we can conclude that RSK merge-mining is safe. It must be noted that a supposed free-start attack on SHA256 requiring 2^80 operations would be devastating for SHA256 and would render it useless as a secure standard hash function, and Bitcoin would be in trouble anyway. But if such attack is ever discovered, the RSK platform could be easily protected by a network upgrade not to use this cryptographic trick for merge-mining proof compression, at the expense of a small increase in block size.  However, as we stated before, even if the attack would cost less than merge-mining in terms of bit-security, it would not be cost-efficient.

Second, with respect to the truncation of the hash digest activated in the 1.0.0 release, the new scheme provides the equivalent of 80-bit security for tag collisions. However, the attack is theoretically, economically, and computationally irrational. From the computational complexity point of view, an 80-bit collision attack would require the use of an unrealistic amount of memory [8]. Also, the CPU cost of the collision attack is more than 2000 times higher than the cost of solving the RSK PoW puzzle (69 vs 80 bits).

From the theoretical point of view and due to the DECOR+ consensus used in RSK, because the collision can only occur at the same RSK block height, the colliding blocks would share the block reward, so there is no benefit to find new siblings of past blocks if the past block reward is approximately equal to the reward of a new block. The attacker would be mainly competing against himself. For the same reason, there is no benefit to find collisions for new blocks, with the added difficulty that it must be performed within 30 seconds on average, instead of 5 minutes available to reference uncles.

From the economic point of view, an honest merge-miner earns Bitcoin transaction fees, so merge-mining is subsidized by Bitcoin, while the attacker has to pay the full cost of the collision attack. This makes almost any attack on the PoW linkage not cost-efficient. This is valid for both, hash digest collisions on the RSK block hash and the free-start collisions on the coinbase transaction hash.

Therefore we think the tag is secure for the next 10 years, even considering a breakthrough in computing efficiency. However, if computing trends radically change, a future network upgrade could easily expand back the size of the hash to the full 32 bytes and we could also add more block references to the CPV field.

Summary

Almost half of the Bitcoin hashrate is currently merge-mining RSK. However, until the 1.0.0 release, the security of RSK was lower than Bitcoin’s. This is because RSK, as a native sidechain,  lacks coin issuance and therefore depends solely on transaction fees. Without block subsidy, the incentives to follow the rules vs to double-spend are lower. With Armadillo, a feature already available, RSK can become as secure as Bitcoin for transactions requiring at least a hundred confirmations, with the only downside of slightly reducing network liveness under active attacks.

References

[1] This article also reproduces some parts of the original article.

[2]  Once a transaction is confirmed in a block it can’t be reversed without someone expending a minimum amount of energy to rewrite the chain. This energy is known as the “thermodynamic” security of a PoW-based blockchain.

[3] https://www.horizen.global/assets/files/A-Penalty-System-for-Delayed-Block-Submission-by-Horizen.pdf and https://hal.archives-ouvertes.fr/hal-01310088v1/document 

[4] RSK receives hashing power not only from Bitcoin, but also some from Bitcoin Cash! If RSK received all hashing power from Bitcoin plus some from Bitcoin Cash, it would surpass Bitcoin hashing rate.

[5] Note that the Bitcoin blocks processed don’t need to be part of the same branch if they are close to the tip, but due to the low number of orphans in Bitcoin, it makes sense to process only the best chain.

[6] Another interesting attack would be to use  tag collisions to create blocks for several competing chains in parallel, all with the same accumulated difficulty, and feed each other miner with a different “best chain” in order to prevent them to work in the same best chain. It requires having direct peer-to-peer connections with the other miners. It could work if the attacker has less hashing power than the remaining miners together but vast more hashing power than the remaining miners separated. Still, this attack would be much more costly than just performing a 51% attack to ignore other miner’s blocks.

[7] https://eprint.iacr.org/2015/350.pdf

[8] The RAM memory required by a simple collision attack is 2^80 hash digests (32 million exabytes). Using the Oorschot/Wiener algorithm, and assuming a single processor can perform 2^40 sequential hash operations in less than 30 seconds, the RAM memory requirement could be reduced to 32 terabytes.

The last time I wrote about Satoshi I thought it would be the last. But here I am, again. Let me bring some context. It all began in a discussion in 2013, in bitcointalk forum, where a plausible reasoning led me to believe that Satoshi would have mined one million bitcoins during 2009-2010. As you know, plausive reasoning doesn’t let you prove anything mathematically, however it gives incredibly good results when applied correctly to solving real real-world problems, where information is imperfect or missing. The original argument about Satoshi coins can be simply stated like this:

Supposition: Anyone who took the time and effort to create Bitcoin would not risk letting the network to halt due to lack of miners. He would run at least a miner himself.

During 2009 the mining activity was so low that it was kept active on the minimum accepted difficulty, and blocks were created at a lower rate than one every 10 minutes. It’s plausible that even if Satoshi wanted to turn off his miner after a while, he may have finally decided to let it run until seeing more activity.

The Patoshi Pattern

In March 2013 I was able to turn the plausible reasoning into a probabilistically falsifiable argument, which means it it’s highly improbable to be false. By reading the original Satoshi client v0.1 source code, I discovered three privacy-related flaws that, together, enable anyone to correlate the blocks mined during the first years and uncover a common origin. Also, it allows anyone to compute the approximate mining hash rate of each of the early miners. If one of these flaws had been absent, it would not have been possible to recognize a very special miner track and the tracks of the remaining miners. But first, a little technical background. The ExtraNonce field, located in the coinbase transaction, increments every time the nonce fields overflows, meaning the search space is exhausted.  As the nonce field is 32 bits in length, and the Bitcoin initial difficulty was tuned to require scanning 32 bits on average, the nonce would sometimes, but not always, overflow. Now let’s present the three flaws present in the original Bitcoin code:

1. The ExtraNonce works as a “free running counter”, without resetting to zero between blocks mined.
2. The rate a certain miner increments the ExtraNonce is much faster than its actual hashrate would indicate, based on the original Bitcoin source code. We’ll call this miner Patoshi.
3. Every few seconds during mining, the best block is checked. If the best block changes, the ExtraNonce is additionally incremented. Normally every external block received will increment the ExtraNonce, except for the exceptional miner Patoshi, which doesn’t seem to follow this rule.

Together these flaws enable the visualization of the Patoshi Pattern. Blocks in the Patoshi pattern will be elements of the Patoshi set (or P set).

The Patoshi Pattern (blue) and the Remaining Miners Patterns (green)

The first flaw is that the ExtraNonce field was handled in a non-privacy preserving way. By not being reset each time a new block is mined, it works as a free-run counter or timestamp.

The second is that for a reason that was only uncovered a year later, the rate this timestamp is incremented by Patoshi was higher than the number of blocks solved would suggest, so even if his mining equipment was not so much faster, it looked so. This flaw alone let you very easily separate Patoshi from the rest of the miners. We lack information about how Patoshi mining software operated: for instance, it’s seems that the Patoshi miner didn’t followed the rule in flaw 3, but it can be the case that it checked the change in the best block less frequently and this invalidates any attempt to measure if flaw 3 was present or not in his software.

The third flaw enables anyone to follow the tracks of the remaining miners. If this flaw had not been present, most blocks of the remaining miners would be indistinguishable from “noise”, having ExtraNonce values that are too close to zero, because the ExtraNonce would hardly ever increment. The nonce values of the remaining miners almost never overflow. In fact, because of this, in the blocks of the remaining miners the ExtraNonce counter behaves more like a global block counter, and therefore the ExtraNonce patterns of different miners appear with similar slope.  If two blocks A and B are mined by the same miner, then the ExtraNonce delta between them would almost equal to the number of blocks mined between A and B. The moment in which the miner starts mining from a zero ExtraNonce value establishes a unique point the in the line created by every non-Patoshi miner.

When Patoshi stops mining, the remaining miners increment the ExtraNonce at a lower rate due to privacy flaw 3.

An exceptional case is when several blocks are mined in a very short time: or if the mining process is paused and resumed after a few minutes, then the ExtraNonce will be incremented only once for many blocks in a row. However, this doesn’t seem to happen often. Last, it seems that the Patoshi miner doesn’t follow this rule: there are many cases where the distance between his blocks is lower than the number of blocks in-between. While the absence of this flaw is yet another way of distinguishing Patoshi blocks from the rest, we’ll focus on other more interesting distinguishers.

Together, the 3 privacy flaws enable the ExtraNonce in early blocks “links to” the last block mined by the same miner, for all miners. This link is based on a coarse timestamping, it’s imperfect, but it can be shown, by simple statistical analysis, that is highly precise for linking blocks. There is a perfect match between the observed behavior of non-Patoshi blocks and the Satoshi client v0.1 source code. Many people hold this historical source code. It’s published in several places in the Internet. If you doubt the authenticity of such source code, you can convince yourself easily that there are some rules governing the ExtraNonce pattern: the probability that the pattern was created by chance is astonishingly low.

Bitcoin Client 0.1 Mining Loop

As soon as you look as the ExtraNonce/Time patterns you realize that the Patoshi chain of linked blocks is outstanding: about 22k blocks in total, high slope, dense chain. Both the naked eye and slope-tracking algorithms pinpoints this pattern immediately. The slopes break at some points, where extranonces restart from zero. The slope (the apparent mining rate) of blocks in this pattern is very different from any other chain of blocks and is quite stable except for three fast changes in two years. While there is a small probability that some blocks are incorrectly tagged by the algorithm, most of the blocks can be tagged without dispute. I estimate the tagging error is 0.1%.

The probability that the Patoshi pattern is formed by multiple miners with the same hardware (slope), each starting exactly when the previous one stopped is also astonishingly low (assuming miners can start mining at any random time). Also take into consideration that the pattern slope does not represent its underlying hashrate.  Therefore, the Patoshi pattern is “one thing”, not the concatenations of many separate things.

Patoshi Pauses Mining for 10 days, his longest pause.

There is Only One Patoshi

Some people accepted the existence of the Patoshi pattern, but at the same time refused the argument that a single entity mined the whole P set. Let’s review their arguments:

Main argument against single Patoshi: The pattern is not created by a single miner but by many miners somehow synchronized.

There are four strong reasons to reject this argument:

1. 99.9% of all Patoshi blocks are unspent. While only 10% of all non-Patoshi blocks are unspent. This means that the “synchronized” miners decided to spend only 0.1% of their bitcoins, while the remaining miners decided to spent 90% of them (or alternatively each spent 90% of their bitcoins, or each block has a 0.9 probability of being spent). Assuming no correlation between blocks, the probability that only 0.1% of Patoshi blocks being spent is close to 2^-76000. But we can assume high correlation: a miner either sells all his coins or no coin at all. The number of other miners went from 0 to about 25 by March 2010. But the number of synchronized miners in Patoshi pattern would have stayed almost intact, because the hashrate of the Patoshi pattern mostly decreases over time. If we assume the synchronized miners were 6, then the chance they didn’t sell their coins by chance is one in a million.
2. Each Patoshi block “links” to a block in the P set, but not to any of the remaining blocks. Somehow the information if a previous block was part or P or not needs to have been communicated along the block. How was this communicated? Early blocks are all look similar. There is no pool signature, as there is today. For what reason would miners do this selective linking? What would they gain? Occam Razor would reject the existence of such system.
3. There are some time intervals where the Patoshi pattern interrupts abruptly (i.e. 07-18-2009 for a full day) and then continues from the point it has interrupted. How did all these separate miners coordinate the interruption, while other continued mining without problems? It may be the case that they were running the same version of the client, which failed. But there is no evidence of a special version of the software being distributed.

Second argument against single Patoshi: There was a kind of heterogeneous mining pool formed since Genesis, and many independent users joined the pool.

Strong rejections to this argument:

1. Mining pools were invented several years later
2. How was the existence of this mining pool secretly communicated before the Genesis block was even created? The Patoshi pattern starts right at Genesis.
3. Mining pools were created to reduce reward variance due to the low individual probability of solving a block, but during 2009 single miners could easily solve blocks frequently. Why to pool resources? There is no reason.
4. There weren’t enough miners to incentivize pooling, as the Patoshi hashrate corresponds to one to six miners (depending on the assumed efficiency of the involved PCs).
5. It would have required specific software (that was never made public) to manage the pool and more software to use it.
6. All these being done in secrecy would imply some kind of conspiration, which seems ridiculous.

There is no technical reason, no software developed, no operational expertise at that time, no monetary gain, and no benefit at all for the creation of a mining pool when Bitcoin was launched. Therefore, we can assume there was no mining pool at Genesis time.

Based on the assumption that the pattern comes from a single entity you can directly conclude that this party was using a special mining software and/or hardware: fast as one or more state-of-the-art servers in 2009, and with slightly different rules governing how to mine.

Nonce Restriction in all Patoshi Blocks

Even if most people were convinced the Patoshi pattern was real, some people still weren’t. But by the end of 2013 things got more interesting: I found proof, beyond any doubt, that the pattern was real, using a completely different method. I discovered that all Patoshi blocks were marked by a reduction of the range of nonces used in published blocks, to a specific range R. We can define R by restricting the least significant byte of the nonce field. This byte normally increments from 0 to 255, but in the Patoshi blocks is reduced to the range [0..9] U [19.. 58].

An Histogram of the LSB Byte of the Nonce Value in the Block Header

The fact that Patoshi nonces are in this range does not imply the miner of the Patoshi pattern only scanned nonces within this range. It could be the case that the network rejected the solved blocks having nonces out of this range, or the same Patoshi mining software did. This is not the case, as there is a direct relationship between the number of nonces scanned and the average time Patoshi took to solve a block. And the relation suggests the nonce space was reduced to R to create blocks at the rate Patoshi blocks were created.  The nonces space scanned is about 1/5^th of the full range, and the ExtraNonce increments about 5 times faster.

If you collect the set of blocks whose nonce is in range R, you’ll find it contains 27.68k blocks.  I call this set M. The blocks that are in M have the nonce in the R range. The set M is far bigger than one would expect from normal mining. The chances M contains 27.68k blocks assuming uniform nonces is negligible (less than 2^-36000). From the 50k blocks analyzed you would expect that only 10K blocks belong to M, not 28k. But we’ll see this perfectly matches the anomaly of the Patoshi set.

If Q blocks had been marked by restricting the nonce range when scanning, and the remaining elements of M had nonces in R just by chance, then we could compute Q from the following equation (isolating Q):  Q + (50-Q)/5 ~= 27.6. The solution is Q=~22k, exactly the size of the Patoshi set. It also indicates there are no other blocks were scanned within the restricted range R except those from Patoshi.

If you re-analyze the common arguments against single-miner for the Patoshi pattern considering this new discovery, the original arguments can’t resist any probabilistic justification. Chances get far lower of what people consider just impossible.

Regarding why the nonce was restricted to the range R, I didn’t know, and I still don’t. These are some of the possible arguments I came up with:

1. The restricted range was part of a “trapdoor” to mine blocks with higher probability of obtaining a hash digest below the target. There is a plausible strong reason this to be false: mining faster by restricting the nonce range implies partially breaking SHA256 pre-image resistance. No scientific paper has ever mentioned such a devastating attack, neither for SHA256 nor for standardized hashing functions using the same Merkle–Damgård construction. Any party with the capability to find SHA256 partial pre-images would probably be able to break most commercial communications, from TLS to VPNs, and earn billions. But there is another reason which is mathematical: if you re-mine all Patoshi blocks, trying to find other solutions to the same block templates, will find that the amount of solutions in the R range compared to the amount of solutions out of that range matches the relation of relative range sizes. It was no “better” to mine within that range. The Patoshi set was simply marked to identify something. What? We don’t know.
2. The restricted range is user to indicate ownership. If Patoshi were two people, maybe they agreed to give 80% of the block rewards to one of them, and 20% to the other. Then the final owner was marked by specific LSB of the nonce, before scanning the rest of the nonce. This can be proven false, as it would imply Patoshi miners had to increase the extra nonce 256 times more often, which doesn’t happen during the first years. Maybe the restricted range is used to indicate probabilistic ownership: the range R is split into sub-ranges, and it’s fully scanned. The party who gets the bitcoins is the one whose sub-range is randomly picked in the solved block.
3. Sub-ranges of R were used to identify different mining hardware cores, where each core would scan a reduced nonce space. This means that Patoshi created the first private homogeneous mining pool. By homogeneous I mean that either all mining machines were setup by a single entity, or a small group of people agreed to use the same type of hardware to fairly distribute earnings. This hypothesis has not been falsified.

At this point I’ve said just a little more from my previous research articles. And from 2014 to early 2019 I didn’t have anything else to say (or to research) about early blocks. Several following studies repeated my research and arrived at similar conclusions. OrganOfConti’s famous blog post contains even more data about Satoshi, describing how he reduced his hashrate in four steps. The last known study, by BitMex Research, comes to the conclusion that Satoshi probably mined 700k coins during 2009-2010. Sadly, they miss the LSB argument entirely (which is the strongest of all known).

But there are people, like nullc, that every now and then go public challenging all this research with old arguments. In a nutshell, I would say that nullc argues a Null Hypothesis: nothing is real. Which is silly because the research was validated by many independent academics.

Null hypothesis: (in a statistical test) the hypothesis that there is no significant difference between specified populations, any observed difference being due to sampling or experimental error.

The reasons why nullc argues this continuously escape my imagination. It’s completely unscientific. The data is there in the blockchain. It doesn’t need rocket science to collect and analyze it. All you need is to grab a Bitcoin blockchain parser. When some weeks ago I read the comments on reddit I felt compelled to refute him again, because … well, because I can. So here I am.  Nullc argues that the Patoshi pattern is just the result of some kind of sampling trick. A human interpretation, like shapes in the clouds. He states:

“The million coins being discussed are all unspent coins from the first year, there is fairly strong evidence that they were not mined by a single party (because their nonce incrementing was consistent with multiple parties). If you refer to the lines on the left side of the graph on the page the involved coins there are more like 200k.”. Nullc, 2019.

Of course, he doesn’t give any “strong argument” and the “nonce incrementing” is perfectly consistent with multiple parties plus a single party mining most of the blocks. The argument is just silly.

I have three new strong arguments that Satoshi mined close to 1.1M coins (even more than the initial 1M I discovered). I have a more precise figure now because I coded a more accurate pattern-following algorithm. But it’s too much information for a single post, so I’ll just present one argument here. Stay with me just a few more paragraphs. Let’s focus on the first 50k blocks of Bitcoin, from January 2009 to April 2010.

A New Argument Based on Computer Clocks

I’ll prove with overwhelming probability that only a single miner has mined all coins in the Patoshi pattern. If you’ve studied the Bitcoin protocol, you’ll know that block timestamps are not necessarily monotonically increasing. The miner uses its local computer clock to timestamp the blocks. This is true from the Bitcoin source code 0.1.0 to the latest version of Bitcoin Core that had an internal miner (before mining pools were created). There are three things that can affect block timestamps:

1. Computer clocks can be unsynchronized from each other. The computer clock is adjusted by most operating systems by slowing down or accelerating the clock increments, but it doesn’t go back spontaneously. A computer that synchronizes with an Internet clock source (a time server) would never lag more than a few seconds.
2. Timestamps were not updated continuously during mining. They were only recomputed every 0x40000 nonces in the Satoshi client v0.1 (approximately once every 10 seconds). This means that a timestamp can lag. However, timestamps are always updated when a new best block arrives.
3. Block timestamps are adjusted by the Bitcoin software to match the median time of the peers that are connected to a node. The adjustment can be positive or negative. Negative adjustments could imply that future blocks may have prior timestamps. The algorithm used is a bit awkward, as it doesn’t recompute the measurements after a correction. But as time passes, and more nodes have connected in the past, the effect of this adjustment diminishes (the vTimeOffsets vector grows). Therefore, after some time the full node internal time should stay without significative adjustments. Also, the peer to peer network, if highly connected, would converge to a global “median time”.

Because of the reasons expressed in (1) and (3), the same computer will almost never reverse its own timestamps. If a miner creates a block with lower timestamp than its parent, and the time difference between the blocks is D, a small portion of D (such a few seconds) may be caused by (3) but the most part of D is an indirect measurement of the time it took the parent miner to complete the last (unfinished) nonce range scan of 0x40000 elements (~10 seconds), corresponding to the lag introduced by (2). In a way, the delta between inverted block timestamps indirectly measures the hashrate of the parent block miner (if all ExtraNonces were incremented at the same rate). Later we’ll say more about these deltas.

If we scan the first 50k blocks to find blocks whose timestamps are lower than their parents’, we should almost never find a case of two consecutive blocks mined by the same miner. If we found many, then that’s an indication we were wrong to think they were from the same miner. And if we found too few compared to the average number of reversals, it would be an indication it’s the same miner indeed.

I run a program to find such time inversions and to print when they happened between blocks in the Patoshi pattern, both blocks out of the Patoshi pattern, and between the Patoshi blocks and the remaining blocks. All the data and new nice graphs of every inversion event has been loaded into the new site satoshiblocks.info.

Some cases of Timestamp Inversions (1=Parent / 2=Child)

To see the complete list of timestamp inversions, go to the satoshiblocks website and click in the “Annotations” checkbox. Each parent is labeled “1”. The corresponding child, which should be the next block, is labelled “2”.

Here is the summary of all classified inversion events:

There are no time inversions between Patoshi blocks. Zero. This result is very relevant considering the Patoshi blocks account for 43% of all the blocks in the first 50k. I’m open to consider other explanations, but for me this can only mean one thing. There is a single PC clock whose time is stamped in the Patoshi blocks. A single software that controls how block templates are created. A single miner.

So who is Patoshi? The single miner that mined ~1.1M bitcoins?

There is evidence that links the Patoshi patterns to Satoshi, based on public information sources and the blockchain, of course. But I would prefer to stop here. Leave Patoshi alone once for all. I have too many things to build for Bitcoin, like RSK.

But I expect more denial posts in Bitcoin forums. And if that happens, then it’s my call.

You can find more information about Satoshi blocks in the following articles:

• The Well Deserved Fortune of Satoshi Nakamoto, Bitcoin creator, Visionary and Genius (SDL, 2013)
  
• Satoshi’s Fortune: a more accurate figure (SDL, 2013)
  
• A new mystery about Satoshi hidden in the Bitcoin block-chain (SDL, 2013)
  
• Satoshi’s Machine: One Mystery is solved and another one opens (SDL, 2013)
  
• Reawaken interest in Chain-Archeology (SDL, 2014)
  
• July 2009 Mystery Solved (SDL, 2014)
  
• How you will not uncover Satoshi (SDL, 2014)
  
• Satoshi’s hashrate (OrganOfCorti, 2014)
  
• A little more on Satoshi’s blocks (OrganOfCorti, 2014)
  
• Another short post on mapping the historical hashrate distribution (OrganOfCorti, 2014)
  
• Does Satoshi have a million bitcoin? (BitMEX Reseach, 2018)
  

While I was reviewing the code  I came up with an idea to fix any Bitcoin SPV proof verifier by changing the member proof format. The new partial-Merkle-tree format can fix Bitcoin’s MERKLEBLOCK command to prevent rogue peers from attacking SPV peers using the weakness.

The old idea to soft-fork Bitcoin to invalidate 64-byte transactions is attractive, but also a coordination problem that could be avoided with this new proposal.

My idea is simple, and it’s not a fork, but a network protocol improvement.

Let A be the hash digest that must be combined with the hash digest B, such that the upper node hash is SHA256(SHA256(A | B)).

Therefore A = SHA256(SHA256(X)) and B = SHA256(SHA256(Y)), and X and Y are either Bitcoin transactions or other inner nodes.

Instead of storing A, the merkleblock structure should store a pre-image of A, or SHA256(X).

If the block only has the coinbase, nothing is done.

The pre-image change could be done to both left and right hashes, but it’s enough to do it to all left-side hashes that do not have children in the partial Merkle tree structure (let’s call them terminal hashes. to avoid confusion with leaf hashes).

Verifiers (SPV nodes) would apply a single SHA256() operation to the left-sided terminal hashes before combining them. The cost to the verifier is in the worse case only 33% more.

This basically limits the attacker’s ability to supply chosen-hash digests in order to build a transaction. Because the left side contains most of the previn hash, the attacker would need to brute-force a huge space (about 208 bits) in order to come up with a pre-image that maps to a owned previn. Meet-in-the-middle attacks would be expensive as UTXOs are not free.

The following figure exemplifies the construction. Normally, for a membership proof for transaction 4, the hashes N(0) and N(1,0) would need to be transmitted. With this new scheme, the intermediate hashes P(0) and P(1,0) (in red and circled) must be transmitted.

To implement this change, a new command MERKLEBLOCK2 could be implemented or the protocol version could be used to differentiate between the two modes of the MERKLEBLOCK command.

If the idea gets community support, I may write the BIP/code or invite anyone to do it. Last week I posted the idea in the bitcoin-dev mailing list but nobody cared to comment on it. It seems that bitcoiners are not fond of supporting lightweight SPV nodes now. The debate about SPV node security is still ongoing.