Cécile Pierrot

Benjamin Wesolowski

Malleability of the blockchain's entropy

Keywords: Random number generation, Blockchain, Random Beacon, Bitcoin, Dyck language

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Randomness is a key concept in cryptography. Even though random numbers are often meant to be kept secret in cryptographic protocols, a number of applications require a form of publicly available randomness which cannot be predicted or manipulated. Some straightforward examples include draws of national lotteries, sampling of assemblies or citizen juries, or tie-breaking in sports or elections. This concept also appears in more technical settings, where a secure public source of randomness can be used to provide trust between communicating parties while implementing contract signing, confidential disclosures, or certified mail in an electronic mail system. These examples were first proposed by Rabin in [START_REF] Michael | Transaction protection by beacons[END_REF], where he defines the source of randomness as a random beacon: an online service that broadcasts allegedly unpredictable numbers at regular intervals.

In these situations the randomness should be generated in such a way that no one can willingly bias the outcome to anyone's advantage or disadvantage. Simple methods hardly provide any strong guarantee, like a skilled prestidigitator can fool entire crowds while tossing a coin. The existing online services that make available fresh random numbers at regular intervals such as [START_REF]NIST randomness beacon[END_REF]RAN98] can at best be considered as trusted third parties: despite extensive documentation and audits, they do not provide users with any mechanism that allows to verify the freshness and correct generation of the published numbers.

A line of research aims at developing and analysing methods to provide trustworthy public randomness. Clark and Hengartner proposed in [START_REF] Clark | On the use of financial data as a random beacon[END_REF] a beacon based on stock market prices, whose security relies on a presumed unmalleability of published financial data -hardly sufficient to convince the most skeptical users. In [START_REF] Arjen | A random zoo: sloth, unicorn, and trx[END_REF], Lenstra and Wesolowski constructed and proved the security of a verifiable beacon that anyone can influence, but no one can bias or predict, by feeding some public input data to a slow hash function.

In another attempt to build a decentralised beacon with no trusted parties, it has been suggested to exploit the inherent unpredictability of blockchains, in particular that of the Bitcoin protocol [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]. In addition to the applications mentioned above, a source of randomness internal to Bitcoin -or any other blockchain based currency -allows that randomness to be used by the currency's scripting language. This extends the range of implementable smart contracts considerably. There is currently no possibility in the Bitcoin scripting language to allow any form of random execution. It is still not the case in cryptocurrencies with more powerful scripting languages such as Ethereum [START_REF] Wood | Ethereum: A secure decentralized transaction ledger[END_REF]. A few Bitcoin protocols [BCG15,BNM + 14,GGMR14,MGGR13] are however already relying on the blockchain as a source of randomness.

This idea becoming widespread together with the lack of a security model for the blockchain's unpredictibility motivated Bonneau, Clark and Goldfeder [START_REF] Bonneau | On bitcoin as a public randomness source[END_REF] to propose an analysis of the method. They consider a model where the attacker controls all the miners, and suffers a monetary penalty whenever a miner finds a valid block that the attacker does not want to see included in the blockchain (see Paragraph 2.1 for a presentation of the notions of miners and valid blocks). This penalty is meant to compensate for the loss of the reward going to a miner finding a valid block. This reward currently consists of 25 B (25 bitcoins3 ) per block plus some transaction fees in the case of the Bitcoin protocol. The amount of this reward decays over time: it started at 50 B, and is divided by two every 210 000 blocks. In [START_REF] Bonneau | On bitcoin as a public randomness source[END_REF], the authors derive that if the next block is used to define a single random bit -presumably unbiased -, an attacker can force the bit to 1 by having the miners drop the valid blocks that give a 0, and this attacker would suffer an expected cost of 50 B at the moment the paper was published.

We aim in the present paper at overcoming the limitations of this model. First, we measure the adversary in terms of computational resources rather than monetary. An associated cost in bitcoins as in [START_REF] Bonneau | On bitcoin as a public randomness source[END_REF] can then be derived, but is not the primary focus. It makes sense indeed to investigate computational limitations when not only money is at stake in the random number generation. Also, it allows us to analyse adversaries that do not have control over the entire pool of miners: it seems unrealistic to assume that the adversary can bribe any miner, who would systematically and silently cooperate. We also account for adversaries with limited resources: whereas in the original analysis the adversary keeps spending money in bribes as long as its goal is not achieved (e.g., obtaining a bit 1 in the example above), our analysis can measure the extent to which the adversary can bias the outcome if they have a limited budget. It also accounts for more general strategies, where the adversary can take advantage of non canonical phenomenons on the blockchain such as forking.

Whereas the authors of [START_REF] Bonneau | On bitcoin as a public randomness source[END_REF] concluded from their analysis that the method is secure enough to be used in practice, we show that an attacker, even when not controlling the entire pool of miners and when limited by a budget, can still significantly bias the probability distribution of the outcome. For instance, again when the blockchain is applied to generate a single unbiased bit, we show that an adversary controlling only a quarter of the total mining power can increase the probability of having a 1 from 0.5 to 0.6 approximately, for an expected cost of around 25 B, i.e. US$9400. With the same parameters we also propose a cheaper strategy that permits to increase the probability from 0.5 to about 0.57, with an expected cost of 3.6 B ≈ US$1320. We also show how this probability can be further improved by preparing the attack in advance: a head start of a day increases the probability to 0.74. Also, the security properties that we define and analyse might be relevant beyond the problem of generating public random numbers, as a more general measure of the security of the blockchain construction. Namely, we study the malleability of the blockchain, a formalisation of the capacity of a party to influence the probability distribution of some bits in the chain. Even though unmalleability is not the primary goal of a secure public ledger, it comes as a desirable property of an ideal instantiation of the blockchain.

The details of the model, together with a brief introduction to blockchain protocols, are presented in Section 2. In Section 3, we study the simple case where the adversary simply wants to influence the next published block with immediate effect, as an example and a warm-up. The more complex setting is analysed in Section 4. Adversaries limited by a financial budget are analysed in Section 5 whereas adversaries preparing themselves in advance are studied in Section 6.

A model for the network and the miners

Blockchains

A blockchain is a form of distributed database, introduced in [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] as the backbone of the Bitcoin protocol. The protocol involves a set of active participants, called miners, distributed over a network, whose job consists in maintaining the blockchain: a global ledger of the history of the system. In the case of Bitcoin, this history is the set of all transactions that happened. At regular time intervals, a new block is added to the chain, testifying for the latest transactions or events. A block is called valid if its hash has a certain number d of leading zeros4 . Only valid blocks can be added to the blockchain. The process of finding a valid block is called mining, and it simply consists in hashing a block a tremendous amount of times with slight modifications until a valid version is found.

In addition to the list of new transactions, a block also contains the hash of the previous valid block. The set of all broadcast blocks thus forms a tree, whose longest chain is the valid blockchain on which there is a consensus. In the case of Bitcoin, each block on that longest chain comes with a reward (some bitcoins) to the miner who mined it. This mechanism encourages the miners to always work on increasing the longest chain they are aware of, in order to keep a mostly linear tree: a tree that consists in the longest chain itself and a few small branches, that quickly stop growing. When such a branching occurs at the tail of the blockchain, it is called a fork. Miners might work on a different branch of the fork at a given moment, but if they keep agreeing to work on the longest one, only the branch with a majority of miners will survive, and consensus is quickly reached again.

It is justified in [BCG15, Paragraph 3.1] that assuming the underlying hash function is secure, each valid block found via the mining process contains at least d bits of computational min-entropy, and therefore d/2 near-uniform bits can securely be extracted by a cryptographic extractor [DGH + 04]. An extractor is a function that transforms a random variable with sufficient entropy into an almost uniformly distributed variable in a smaller domain, which we call the extract. In this paper we consider an extractor Ext that maps valid blocks to elements of E, the set of binary strings of length d/2 . Assuming the hash function used for mining is secure, we can consider the extract Ext(B) of a freshly generated valid block B to be uniformly distributed in E.

Game model

We consider a single instance of a blockchain protocol executed in isolation. The quite detailed abstraction proposed in [GKL15, Section 2] fits our needs, yet we will not detail it here. Indeed, such a precise network diffusion model is not necessary as we will not be dealing with network adversaries: they will not be able to tamper with messages on transit in the network, or with the network's structure itself. This weaker adversary receives and broadcasts messages over the network, and its power will only be measured in terms of its computational resources.

As in Garay et al.'s formal analysis of the Bitcoin backbone protocol [START_REF] Garay | The bitcoin backbone protocol: Analysis and applications[END_REF], the problem is made tractable by assuming that communications over the network are instantaneous. Honest miners are always working with the longest blockchain that they know of, and the broadcast messages are always received by all the miners. Therefore forks can appear when a valid block is found simultaneously by two miners, but the fork will disappear as soon as one of the branches will be lengthened before the other. This matches the real world situation, where the notion of simultaneity is loosened to take into account communication and processing delays: a fork only survives as long as new blocks are added simultaneously to both branches, which cannot happen for very long. We argue that in a model where new valid blocks are never found simultaneously an adversary is not advantaged compared to a model where such accidental forks occur. Therefore we make the latter assumption for the rest of this paper. Even without accidental forks, malicious forks are still possible: an adversary can secretly work on a branch longer than the public one, and once this branch is revealed, it will completely replace the old one as the new longest chain.

The game involves a set of honest miners and an adversary A. Honest miners simply aim at growing the blockchain, by broadcasting valid blocks to get the associated reward. Meanwhile, the goal of the adversary is to bias the probability distribution of the extract of an upcoming block in the chain, which we call the decisive block. For illustration, say that the extract x of that decisive block is a lottery draw: the adversary wins whenever x falls in a given subset of E, the "winning tickets". Let χ : E → {0, 1} be the characteristic function of that subset of the set of possible extract values. The adversary A wins if, at the end of the game, χ(x) = 1 where x is the extract of the decisive block, which we call pleasant in this case. Note that it does not matter whether that decisive block was broadcast by the adversary or by a honest miner. We denote by PA the probability that A wins.

The game starts at the round where a fixed initial block indexed by 0 is received and ends when the blockchain reaches a length of n + ∆, for some predefined integers n and ∆. The n-th block is the decisive block, whose extract determines whether or not the adversary wins. Since that block determines the outcome of the game, it might first seem surprising to continue for ∆ additional blocks. But the value of any specific block can be changed via forking: in blockchain protocols, consensus does not go to the version of a block that arrived first, but to the version of the block that belongs to the longest chain. An adversary could try to take advantage of that by attempting to create a fork to modify an unpleasant decisive block. The positive parameter ∆ takes into account the possibility that the decisive block can still be modified until the blockchain has been lengthened by ∆ blocks.

Finally we denote by µ the probability for a uniformly distributed extract value x ∈ E to satisfy χ(x) = 1. We clearly have µ

= |{χ(x) = 1 | x ∈ E}|/|E|.

Adversary model

We consider a weak adversary that cannot change the content of the messages traveling around the network nor prevent them from being delivered. The adversary can mine on the blockchain and, unlike honest miners, they are not assumed to always work on extending the longest chain, nor to broadcast all the valid blocks they find. Thus, in this context, the critical property of the adversary is their computing power, or more precisely, their relative power with respect to the total power of the miners. Concretely, this power is measured as a number sA (respectively s) of hashes per second that the adversary (respectively the total set of miners, including A), is able to compute. Let λ = sA s measure the relative power of A. Such hash computations can be modelled as calls to a random oracle. The number of random oracle calls to be done before finding a valid block follows a Poisson distribution, and at any point in time, λ can be interpreted as the probability that the next oracle request giving a valid block has been done by the adversary.

Remark 1. The adversary could be a single entity as well as a set of colluding, corrupted miners. It therefore extends the model of [START_REF] Bonneau | On bitcoin as a public randomness source[END_REF], where all the miners are ready to accept bribes to collaborate: this corresponds to λ = 1 in our setting. We can still account for the money it takes to corrupt the miners, via the notion of virtual cost (see Paragraph 3.4), yet it is not the only metric available anymore.

A warm-up: manipulating the next published block

Delay-free games

As a first example, let us look at the simple case where n = 1 and ∆ = 0. The adversary aims at manipulating the next broadcast block, without bothering whether it will survive potential future forks. This case occurs whenever the extracted randomness is meant to be used immediately, such as a random beacon that broadcasts the random numbers as soon as they are available, or a simple national lottery. Indeed, a random beacon is meant to be unpredictable, and its output cannot be changed in the future -unlike a blockchain where forks can "change the past". The beacon must broadcast a number as soon as it is available, which does not permit to wait for a safety delay ∆ > 0 before outputting the numbers.

Strategy

The adversary's strategy here is straightforward: they will focus all their computational power on mining the next block. Whenever they find an unpleasant valid block B such that χ(Ext(B)) = 0, they throw it away and continue to mine. The game ends whenever a honest miner finds a valid block or the adversary finds one that satisfies χ(Ext(B)) = 1, which they immediately broadcast. In this context, it is clearly an optimal strategy as valid blocks can only be found by mining (which is a classical assumption for blockchains, and can be enforced by the random oracle model), and an adversary who would themselves publish a block such that χ(Ext(B)) = 0 would only decrease their winning probability, as well as an adversary who would not publish instantly a valid block such that χ(Ext(B)) = 1.

The winning probability P A

Let us compute the probability PA that the adversary wins that game. The event that they win the game is denoted w. The possible outcomes can be split into the infinite family of disjoint events ea, for any a ≥ 0, that the adversary found and threw away exactly a valid blocks. The event ea ∧ w further requires that the final block B, i.e. the (a + 1)-th block that is found, satisfies χ(hB) = 1 (and it does not matter who found that last one). The winning probability can now be expressed as:

PA = a≥0 Pr(ea ∧ w) = a≥0 (λ(1 -µ)) a µ = µ 1 -λ(1 -µ) .
Since λ ≥ 0 and µ ≤ 1 this is clearly better than µ. For instance, when µ = 1/2, and λ = 1/4, the probability that A wins is increased from 0.5 to 4/7 ≈ 0.57. Note that λ = 1/4 is a realistic assumption: for instance, the relative computational power λ of the four actual most influent mining pools Antpool, F2Pool, BitFury, and BTCChinaPool vary between 13% and 27% each, depending on sources and dates.

Virtual cost expectation for the adversary

The virtual cost refers to the number of blocks the adversary has to drop, thereby giving up the associated reward. We emphasise that this virtual cost does not take into account potential profits related to the outcome of the game. It is only a measure of the amount of mining power they sacrificed to play the game: namely, the difference between the expected reward they would have had by behaving as a honest miner, and the reward resulting from playing the described strategy. For each event ea, exactly a blocks are dropped, therefore the expected virtual cost E is:

E = a≥0 a Pr(ea) = a≥0 a(λ(1 -µ)) a (1 -λ(1 -µ)) = λ(1 -µ) 1 -λ(1 -µ) .
Again, to illustrate this virtual cost we look at the example where µ = 1/2 and λ = 1/4. It gives 1/7 expected lost blocks. In terms of money, the actual reward at the time of writing is 25 B. Thus this strategy can be approximately evaluated to have an expected cost of US$1320.

The case where λ = 1 ensures the victory as long as µ > 0, for an expected cost of (1 -µ)/µ. This is the situation in [START_REF] Bonneau | On bitcoin as a public randomness source[END_REF] where all the miners are assumed to collude with the adversary, and they indeed found the same expected cost.

4 Reaching consensus

Games with delay

We now deal with the case where n = 1 and ∆ > 0. Delaying the end of the game later than the broadcast of the decisive block is necessary to measure the security of protocols involving several parties that would base an agreement on the extract value of this decisive block. Smart contracts are a good example for such worries. Indeed, unlike in our first naive delay-free games model, forking can interfere and change the initial execution of the contract, therefore modifying the outcome of the contract itself after its execution. Here, the random value is only considered valid when it is deep enough in the chain. More precisely, choosing a sufficiently large ∆ helps to reach consensus, when it is considered impossible to create a fork of length strictly larger than ∆.

Then the parties involved in the contract gain confidence that the outcome is definitive.

Relevant values for ∆

Relevant values for the delay ∆ can be deduced from the analysis performed in [START_REF] Garay | The bitcoin backbone protocol: Analysis and applications[END_REF] where the authors evaluate the probability to have a fork of two branches of a given length. From a practical point of view, a look back to the history of broadcast Bitcoin blocks permits to find all the accidental forks that have ever been observed. For instance, from [Blo16] we see that 540 forks were noticed since the block number5 142 257: two branches of length 4, four of length 3, fourteen of length 2, and what remains are orphan blocks. Thus, keeping a safety margin, ∆ = 6 seems sufficient to make sure that no fork will alter the decisive block after the end of the game.

Strategy

The adversary's strategy begins as previously: they first focus all their computational power on mining the first block (that is also the decisive block since n = 1) and throw away all valid blocks B they find as long as χ(Ext(B)) = 0. At the first broadcast of the decisive block B d two cases can occur. If it satisfies χ(Ext(B d )) = 1 then A starts to act as a honest miner. Namely, they continue to mine on this chain and the game ends when the (1 + ∆)-th valid block is found, leading to the success of A. Otherwise, if one honest miner broadcasts a decisive block satisfying χ(Ext(B d )) = 0, A continues to secretly mine on the previous block as if they received nothing. Again, they throw away all valid decisive blocks that would lead to their failure. If they find one such that χ(Ext(B d )) = 1 they keep it secret, create a fork and continue to mine on their new chain, hoping to develop a branch longer than the current public one containing the unpleasant decisive block. If they manage to do so, they broadcast their fork, and all miners switch to that new longest chain and proceed to mine on that one, thereby including the cheated pleasant decisive block in the new consensus chain. The game ends when a miner finds a valid final block, whether it is on the original chain, or on the branch later appeared.

Computing the probability P A

To compute the probability that A wins we consider a partition of our universe as follows. Let w1, f0, f01 and w01 (w implicitly stands for A wins and f for A fails) be the events defined as:

- So the event that A wins, denoted w, is the union of w1 and w01. Note that the probability of w1 has already been computed in Section 3, as:

Pr(w1) = µ 1 -λ(1 -µ) . (1)
For convenience we also define e0 as e0 = f0 ∨ f01 ∨ w01.

Probability of f 0 . Since f0 is a sub-event of e0, its probability can be expressed as:

Pr(f0) = Pre 0 (f0) × Pr(e0) = Pre 0 (f0) × (1 -Pr(w1)),
where we denote by PrB(A) the conditional probability of event A given that event B occurred.

0 0 0 0 0 0 0 0 0 0 0 0 0 Decisive block

Final block

Fig. 1. Secret and public blocks mined during the event f0. Green blocks represent the blockchain integrally mined by honest miners whereas red ones correspond to the k valid decisive blocks (secretly) found by A, all such that χ(Ext(B)) = 0. A bit inside a block indicates the value of χ for its extract. It is only indicated on blocks that are meant to be decisive: here, the first broadcast block, and the adversary's failed attempts at finding a pleasant one. In this example, a = 12 and ∆ = 6.

Figure 1 represents the situation for a fixed number a of valid blocks mined by A. The probability that A fails precisely a times knowing e0 is given by the product:

a + ∆ -1 a (λ(1 -µ)) a (1 -λ) ∆-1 (1 -λ).
Thus the formula for Pre 0 (f0) is:

(1 -λ) ∆ a∈N k + ∆ -1 a (λ(1 -µ)) a .
The summation over a can be simplified using the fact that for any positive integer h, and any x = 1:

a∈N a + h a x a = 1 (1 -x) h+1 .
(2)

From Equation (2) we get the final value of the probability of f0 knowing e0:

Pre 0 (f0) = 1 -λ 1 -λ(1 -µ) ∆ .
(3)

Probability of f 01 . Again we compute Pre 0 (f01) the probability of f01 knowing e0 in order to find the probability of f01 that satisfies:

Pr(f01) = Pre 0 (f01) × (1 -Pr(w1)).
Figure 2 represents the situation and gives an indication of the various parameters we need to express this probability. We define:

-a2 as the number of valid decisive blocks mined by A after the first decisive block is broadcast by a honest miner and before A finds a valid decisive block verifying χ(Ext(B d )) = 1. -h2 as the number of valid blocks mined by all honest miners in the blockchain in the meantime, namely after the first decisive block is broadcast by a honest miner, and before the adversary manages to find a decisive block verifying χ(Ext(B d )) = 1. -a3 as the number of valid blocks mined by A on its chain after A finds a valid decisive block verifying χ(Ext(B d )) = 1 and before the last block is mined.

With this in hands, we see that the number of valid blocks mined by all honest miners, after A finds a pleasant valid decisive block, and before the last block is mined, is given by ∆ -1 -h2.

Besides, some parameters are upper bounded: we have h2 < ∆ and a3 < ∆.

0 0 0 0 0 1

Decisive block

Adversary's cheated decisive block

Final block

Fig. 2. Secret and public blocks mined during the event f0. Green blocks represent the blockchain integrally mined by honest miners whereas red ones correspond to the a2 + 1 + a3 valid blocks (secretly) found by A. Again a number inside a block corresponds to the value of χ for its extract, when the block is meant to be a decisive one. In this example ∆ = 6, a2 = 4, h2 = 1 and a3 = 5.

The probability, knowing e0, that A finds a pleasant valid decisive block exactly after a2 trials that failed, and to get h2 blocks mined by the honest miners before this new decisive block is:

a2 + h2 a2 λ a 2 +1 (1 -λ) h 2 (1 -µ) a 2 µ.
To complete the computation of Pre 0 (f01) we need to count the number of possible cases in which A mines a3 valid blocks but fails to ever create a chain longer that the main one. This number in hand, it will only remain to sum over the possible values of the three variables a2, a3 and h2. Fixing these parameters, an outcome where the adversary fails to replace the main blockchain with its own corresponds to a sequence where at every point in time, the adversary's chain is shorter that the main one. The insightful reader might have observed that this situation shares similarities with Dyck words. A word in two letters H and A is a Dyck word if no initial segment contains more A's than H's. Here the situation is slightly different as the honest main chain (whose blocks correspond to the letter H) starts growing as soon as a honest miner finds a first valid block, while the adversary's chain (the A's) starts growing only when the adversary finds a first valid block such that χ(Ext(B)) = 1. Therefore we define generalised Dyck words as follows.

Definition 1. Let ∆, a and h be three non-negative integers such that a < ∆ and h < ∆. We call generalised Dyck words (for the parameters ∆, a, and h) words with a + h letters formed with exactly a letters A and h letters H that verify the following property: for any prefix of the word, we have #A ≤ #H + ∆ -h -1 where #H (respectively #A) represents the number of H's (respectively A's) in that prefix.

Lemma 1. Let ∆, a and h be three non-negative integers, and suppose a < ∆ and h < ∆. Defining D(∆, a, h) as the number of generalised Dyck words we exactly have:

D(∆, a, h) = a + h a - a + h ∆ .
Proof. The proof follows a classical idea developed to count Dyck words. We first look at words with exactly a letters A and h letters H that are not generalised Dyck words. For each such word, there exists a first A that breaks the property. Changing each A into an H and each H into an A strictly after this special A leads to write a word6 with exactly a -∆ + h letters H and ∆ letters A. Thus for a fixed ∆ this process describes an injection:

f : E -→ F
that sends E (the set of all the words with a letters A, h letters H that are not generalised Dyck words) into F (the set of words with a -∆ + h letters H, ∆ letters A). Besides, the map f is surjective. Indeed, let us consider a word w in F . From a < ∆ we see that ∆ > (a -∆ + h) + ∆ -h -1, which means that w breaks the condition #A ≤ #H + ∆ -h -1. Hence considering the first letter A in w that breaks the condition, and changing each A into an H and each H into an A strictly after this special A, we obtain a word in E such that the image of this word is exactly w. The bijection f yields #E = a+h ∆ , and at the end:

D(∆, a, h) = a + h a - a + h ∆ .
Summing over the possible values of the three variables a2, a3 and h2, we obtain: where D is the function in 3 variables defined in Lemma 1 that counts the number of possible cases in which the chain mined by A never overtakes the honest one. The probability Pre 0 (f01) can be rewritten as:

Pre 0 (f01) = λµ(1 -λ) ∆ 0≤a 2 0≤a 3 ,h 2 <∆ (λ(1 -µ)) a 2 a2 + h2 a2 λ a 3 D(∆, a3, ∆ -1 -h2),
Pre 0 (f01) = λµ(1 -λ) ∆ 0≤a 3 ,h 2 <∆ λ a 3 D(∆, a3, ∆ -1 -h2) 0≤a 2 a2 + h2 a2 (λ(1 -µ)) a 2 .
We can simplify the inner sum using Formula (2) and get:

Pre 0 (f01) = λµ(1 -λ) ∆ 1 -λ(1 -µ) 0≤a 3 ,h 2 <∆ λ a 3 (1 -λ(1 -µ)) h 2 D(∆, a3, ∆ -1 -h2). (4)
To conclude, we can put everything together using PA = 1 -Pr(f0) -Pr(f01), with the formula

PA = 1 -(1 -Pr(w1)) • (Pre 0 (f0) + Pre 0 (f01)), (5)
where Pr(w1), Pre 0 (f0) and Pre 0 (f01) are functions in λ, µ and ∆ respectively given in Equations (1), ( 3) and (4). To compare again with µ we plot several of these probabilities. Figure 3 gives the probability that A wins as a function of their relative computational power λ, for a fixed value of µ = 1/2 on the left or µ = 1/16 on the right. For instance, if µ = 1/2, λ = 1/4 and ∆ = 6 -which are three arguably realistic parameters -then the probability that the adversary wins is increased from 50% to approximately 60%. Figure 4 takes the other point of view and considers how the probability PA varies with µ when λ is fixed to 1/4.

Virtual cost expectation for the adversary

Again, the virtual cost refers to the number of blocks the adversary has to drop, thereby giving up the associated reward. To compute the expected virtual cost E we consider three cases. In the event w1, such blocks only appear before the first decisive block is mined. Thus the expected number of dropped blocks that correspond to this case is:

E1 = a≥0 a Pr(ea ∧ w) = a≥0 a(λ(1 -µ)) a µ = µλ(1 -µ) (1 -λ(1 -µ)) 2 . ( 6
)
Besides, considering the union of f0 and f01, we see that in both cases the chain making the consensus at the end has entirely been mined by honest miners and consists in ∆ + 1 valid blocks. Since the relative computing power of A is λ, it yields that A dropped in average (∆+1)λ/(1-λ) valid blocks. So the expected number of lost blocks related to those two events is:

E2 = (1 -PA) • (∆ + 1)λ 1 -λ . ( 7
)
where PA is given in Equation (5). Last but not least, we can see the event w01 as the union of all ea for a ∈ N where ea is the event: A finds precisely a valid blocks with an unpleasant extract, then mines a pleasant decisive block and manages to mine a chain longer than the current honest one. The expected number of dropped blocks related to this last case is:

E3 = a≥0
a Pr(ea).

To compute Pr(ea) we denote by h2 the number of honest valid blocks broadcast (strictly) between the two decisive blocks and by h3 the number of honest valid blocks broadcast after the pleasant decisive one is mined by A. We get:

Pr(ea) = λ a (1 -µ)) a+1 µ 0≤h 2 <∆ a + h2 h2 (1 -λ) h 2 +1 0≤h 3 ≤∆ D(h2 + h3 + 1, ∆, h3)λ ∆ (1 -λ) h 3
where D(h2 + h3 + 1, ∆, h3) is the number of words with ∆ letters A and h3 letters H that are not generalised Dyck words (with the correspontding parameters). Since we have the equality

D(h2 + h3 + 1, ∆, h3) = h 2 +h 3 +1 ∆+h 3
we can write:

E3 = λ ∆ (1 -λ)(1 -µ)µ × a≥0 a(λ(1 -µ)) a 0≤h 2 <∆ a + h2 h2 (1 -λ) h 2 0≤h 3 ≤∆ h2 + h3 + 1 ∆ + h3 (1 -λ) h 3 (8)
Therefore the expected virtual cost E is given by:

E = E1 + E2 + E3,
where E1, E2 and E3 are respectively given in Equations ( 6), ( 7) and (8). To illustrate this virtual cost we plot in Figure 5 the expected number of blocks that are dropped by the adversary as a function of their relative computational power λ, in the case where µ = 1/2. For instance, when λ = 1/4 and considering ∆ = 6 it gives roughly 1.017 expected lost blocks. Thus this strategy can be approximately evaluated to have an expected cost of US$9400.

Fig. 5. Expected number of dropped blocks as functions of the relative computational power λ, when µ = 1/2. The black curve corresponds to the basic case with no delay, i.e. ∆ = 0. The other curves correspond to values of ∆ that vary from 1 to 7.

Adversaries with a virtual budget

A virtual budget is the amount of money the adversary is ready to lose by not publishing valid blocks they found. An adversary with a virtual budget enforces a bound on the virtual cost, and thereby on the number of abandoned blocks. The analysis is similar to the previous case, but now, when the adversary runs out of budget, they must stop mining blocks that do not directly contribute to the longest chain. Let b be the maximal number of blocks the adversary can drop, i.e., its budget. Then, the probability of w1 becomes:

Pr(w1) = b a=0 (λ(1 -µ)) a µ = µ(1 -(λ(1 -µ)) b+1 ) 1 -λ(1 -µ) .
This is the probability to win when ∆ = 0, generalising the results of [START_REF] Bonneau | On bitcoin as a public randomness source[END_REF] to adversaries with a budget. Let us compute the winning probability for ∆ > 0. Now, we cannot forget about what happened before the publication of the first decisive block as we did previously by conditioning over e0, as we need to keep track of how many blocks the adversary dropped during that period.

Let f be the event that A fails the game, b the event that A used its full budget during the game, and o be the event that the blocks found by the adversary within their budget are all unpleasant. The event f is partitioned into four disjoint events:

Pr(f) = Pr(f ∧ b ∧ o) + Pr(f ∧ ¬b ∧ o) + Pr(f ∧ ¬b ∧ ¬o) + Pr(f ∧ b ∧ ¬o).
Let us first focus on the event f ∧ b ∧ o. Look at the prefix of the sequence of found blocks up to the point where the adversary went out of budget. If b = 0, that prefix is empty and the probability of failure is 1 -µ; otherwise, the last block of that prefix is the bth block found by A. Let h denote the number of blocks honestly mined during that period. Then:

Pr(f ∧ b ∧ o) = 1 -µ if b = 0, (1 -µ)(λ(1 -µ)) b ∆ h=0 b+h-1 b-1 (1 -λ) h otherwise. (9)
Now, let us compute the probability of f ∧ ¬b ∧ o. Look at the full sequence of found blocks, ∆ + 1 of which are honestly mined, and a < b are found by the adversary. The probability can then be written as:

Pr(f ∧ ¬b ∧ o) = (1 -µ)(1 -λ) ∆+1 b-1 a=0 ∆ + a a (λ(1 -µ)) a . (10)
We now look at f ∧ ¬b ∧ ¬o. Split the sequence of found blocks into two parts: the initial segment up to the pleasant block found by the adversary, and the rest of the sequence until the end. Let a1 be the number of blocks found by A during the initial part, excluding the last one (i.e., only the unpleasant blocks), and h1 the number of blocks honestly mined in the meantime, including the unpleasant broadcast decisive block. Let a2 be the number of blocks found by A during the second phase. Since we suppose ¬b, we have a1 + 1 + a2 < b. The number of blocks honestly mined in the second phase is ∆ + 1 -h1, including the final block. Observe that since A loses, the second part is a generalised Dyck word. Then, the probability can be computed as:

Pr(f∧¬b∧¬o) = (1-µ)λµ(1-λ) ∆+1 0≤a 1 <b-1 1≤h 1 ≤∆ 0≤a 2 <b-a 1 a1 + h1 a1 (λ(1-µ)) a 1 D(∆, a2, ∆-h1)λ a 1 . (11)
The last event f ∧ b ∧ ¬o needs to be further split into two events: the case u where the pleasant decisive block found by A is the last block in there budget, and the case v where A still has some budget after that pleasant block was found. Then, Pr(f ∧ b ∧ ¬o) = Pr(u) + Pr(v). We first focus on u. Look at the prefix of the sequence of blocks up to the pleasant decisive block. That prefix contains exactly b blocks found by A (including the last one), and a number h ≤ ∆ of blocks honestly mined (including the unpleasant decisive block). The probability is then:

Pr(u) = λ b µ(1 -µ) b ∆ h=1 b + h -1 h (1 -λ) h . (12)
Fig. 6. Probabilities as functions of the budget (number of blocks that can be dropped), when λ = 1/4 and µ = 1/2. The two highest curves correspond to PA in the delay-free case (∆ = 0) and when ∆ = 6. The lowest curves are the four components that permit to compute PA when ∆ = 6: the purple curve corresponds to Pr(f ∧ b ∧ o), the orange one to Pr(f ∧ ¬b ∧ o), the blue one to Pr(f ∧ ¬b ∧ ¬o), and the yellow one to Pr(f ∧ b ∧ ¬o).

It only remains to compute Pr(v). Again, focus on the prefix of the sequence of found blocks which stops when the adversary runs out of budget, i.e. when they mine their bth block. Split that prefix into two parts: the initial part up to the pleasant decisive block found by the adversary, and the second part, from that pleasant block to the end, i.e., the bth block of A. Let a1 be the number of blocks found by the adversary during the first part, excluding the last one (i.e., only the unpleasant blocks), h1 the number of blocks honestly mined in the meantime, including again the unpleasant decisive block, and h2 the number of blocks honestly mined in the second part. The number of blocks found by A in that part is b -a1 -1. The probability is then:

Pr(v) = (1 -µ)λ b µ 0≤a 1 <b-1 1≤h 1 ≤∆ 0≤h 2 ≤∆-h 1 a1 + h1 a1 (1 -µ) a 1 (1 -λ) h 1 +h 2 D(h1 + h2, b -a1 -2, h2). (13)
Finally, the winning probability is computed by subtracting all the possible failure probabilities:

PA = 1 -Pr(f ∧ b ∧ o) -Pr(f ∧ ¬b ∧ o) -Pr(f ∧ ¬b ∧ ¬o) -Pr(u) -Pr(v),
where Pr(f ∧ b ∧ o), Pr(f ∧ ¬b ∧ o), Pr(f ∧ ¬b ∧ ¬o), Pr(u) and Pr(v) are respectively given in Equations ( 9), ( 10), ( 11), ( 12) and (13). Figure 6 details how PA varies as a function of the number of blocks that can be dropped in the two cases ∆ = 0 (no delay) and ∆ = 6. Note that these probabilities tend to 0.57 (resp. 0.6) which were the probabilities previously found in Section 3.3 (resp. Section 4.4), when the budget was unlimited. Moreover, we can see that the winning probability converges fast enough so that even a small budget is sufficient to significantly cheat the game.

6 Provident adversaries

Games with early start and delay

Let us consider the more general case where not only there is a final delay ∆ ≥ 1 as previously, but the game also starts early, i.e. the decisive block is not the next one, but the n-th one, where n > 1. This corresponds to the real world situation where an attacker knows in advance which future block will be decisive for the goal he tries to achieve. This case is relevant when a far-sighted adversary may get ahead of the game to manipulate an upcoming decisive block. In truth, nothing prevents adversaries that already cheat from preparing themselves several blocks in advance, without waiting for the beginning of the game to start mining in secret. The analysis of this situation is essential to applications where some parties commit on an upcoming random number. In a lottery, the ticket seller should announce in advance which (future) block will determine the winner, giving the adversary a head start to manipulate that precise block. It is also crucial in electronic voting systems, where unpredictable, verifiable, public randomness is required for the security of the random auditing after the election [CCC + 08].

Strategy

For the adversary, the goal will be to obtain a chain of length n -1 as soon as possible. If they can obtain such a branch before the honest miners -and keeps it secret -, they can start mining for a pleasant n-th block (the decisive one) while the honest miners are still working on building the initial segment of the chain. The adversary tries to build a chain longer than the honest one as follows: on one hand there is the public, honestly mined chain, and on the other hand there is the secret branch of the adversary. The adversary only mined on their own secret branch. At any point, if the honest chain becomes longer than the adversary's branch, the latter is thrown away and replaced by the longer honest chain. With this strategy, the adversary's branch is never shorter than the public one.

When an n -1-th block has finally been found (either by A, or by the honest miners if A has not been fast enough) the adversary starts following the same strategy as in the previous game -see Section 4.3. Again, they focus all their computational power on mining the decisive block and throw away all valid but unpleasant blocks. At the first broadcast of the decisive block B d two cases can occur. If it satisfies χ(Ext(B d )) = 1 then A starts to act as a honest miner. Otherwise, if one honest miner broadcasts a decisive block satisfying χ(Ext(B d )) = 0, A continues to secretly mine on the previous block as if they received nothing. Again, they throw away all valid decisive blocks that would lead to their failure. If they find a pleasant one, they keep it secret, create a fork and continue to mine on their new chain, hoping to develop a branch longer than the current public one containing the unpleasant decisive block. If they manage to do so, they broadcast their fork, and all miners switch to that new longest chain and proceed to mine on that one, thereby including the cheated pleasant decisive block in the new consensus chain. The game ends when a miner finds a valid final block, whether it is on the original chain, or on the branch later appeared.

Computing the probability P A

To evaluate the probability that A wins, we consider again the event e0 that the first decisive broadcast block is an unpleasant one. As in Equation (5), PA is given by: PA = 1 -Pr(e0) • (Pre 0 (f0) + Pre 0 (f01)), (

where Pre 0 (f0) and Pre 0 (f01) are functions given in Equations ( 3) and ( 4). Yet in this far-sighted adversary case, the analysis differs when computing the probability of e0.

Let us consider the family of disjoint events a k that A finds an n -1-th block with an advantage of k blocks over the public branch, where k varies from 0 (meaning that the n -1-th block is mined by a honest miner) to n -1 (when A has computed the entire chain from blocks 1 to n -1 while the honest miners did not find a single valid block). This leads to:

Pr(e0) = n-1 k=0 Pra k (e0) • Pr(a k ).
If a denotes the number of blocks dropped by A while the honest miners broadcast all the blocks needed to complete their chain up to the unpleasant decisive block, Pra k (e0) is given by the sum (1 -λ) k+1 (1 -µ) a≥0 a+k a (λ(1 -µ)) a . Using Equation (2) we find:

Pra k (e0) = (1 -µ) • 1 -λ 1 -λ(1 -µ) k+1 . ( 15
)
Thus it suffices now to evaluate the probabilities Pr(a k ).

Probability Pr(a k ) for a fixed k. Let k be an integer between 0 and n -1. The different outcomes that lead the adversary to obtain an advantage of k blocks can be modelled as paths on an (n -1) × (n -1) grid of blocks from the point (0, 0) to the point (n -1, n -1 -k) as in Figure 7. Following certain constraints. Each point (a, h) of a path corresponds to the moment at which A has a valid branch from block 0 to block a whereas the honest chain only goes up to the block h. The adversary's strategy enforces h ≤ a, i.e. the path never overpasses the diagonal line. The short arrows forming the (0, 0) (n -1, 0)

  w1: the first broadcast decisive block B d is such that χ(Ext(B d )) = 1. -f0: the first broadcast decisive block B d is such that χ(Ext(B d )) = 0 and A fails to find any decisive block B d such that χ(Ext(B d )) = 1. -f01: the first broadcast decisive block B d is such that χ(Ext(B d )) = 0, A manages to find a decisive block B d such that χ(Ext(B d )) = 1 but not to compute a branch sufficiently long to replace the main one. -w01: the first broadcast decisive block B d is such that χ(Ext(B d )) = 0 but the adversary manages to find one B d verifying χ(Ext(B d )) = 1, and to have it replace the original one.

Fig. 3 .

 3 Fig.3. Probabilities PA as functions of λ when µ = 1/2 (first graph) and µ = 1/16 (second graph). The corresponding values for ∆, ranging from 0 to 12, are indicated on the curves. For information purposes, the red curves correspond to Pr(f01) and the purple ones to Pr(f0), both with ∆ = 12.

Fig. 4 .

 4 Fig. 4. Probabilities PA as functions of µ when λ = 1/4. Values for ∆ are indicated on the curves. Again the red curve corresponds to Pr(f01) and the purple one to Pr(f0) both with ∆ = 12. The black line indicates the probability that a honest player wins.

Fig. 7 .

 7 Fig.7. Secret and public blocks mined during the event a k . Green blocks (or arrows) represent the blockchain integrally mined by honest miners whereas red blocks (or arrows) are those secretly mined by A. On this example, n = 17 and A finds the block number n -1 with a head start of k = 6 blocks. The number inside each block (or near each arrow) indicates the order in which the corresponding block was mined, irrespective of whether it was broadcast or kept secret.

Fig. 8 .

 8 Fig.8. Probability PA as a function of λ when µ = 1/2 and n = 144 (in the case of Bitcoin, 144 blocks are found in an expected time of one day). The corresponding values of ∆ are 0, 1, 3, 6 and 12 as suggested on the curves. The lower curves represent the inner probability Pr(e0) as a function of λ for µ = 1/2 and various choices of n. The black one corresponds to Pr(e0) when n = 6 (corresponding, in Bitcoin, to an expected time of one hour), the blue one when n = 36 (six hours), the purple one when n = 144 (one day) and the red one when n = 1008 (one week).

Note that 1 B roughly equals US$370 at the time of writing this article, keeping in mind that the Bitcoin exchange rate still fluctuates a lot.

At the time of writing this article, the value of d for Bitcoin was approximately 66. This parameter is continuously adjusted so that it takes an expected time of 10 minutes for the worldwide mining effort to find a valid block.

At the time of writing the last blocks are around number 400 000.

For instance, if h = 3, a = 5 and ∆ = 6 the word HAAAAHHA becomes HAAAAAAH that has 6 letters A and 5 -6 + 3 = 2 letters H.

Acknowledgement

We would like to thank Arjen Lenstra for his comments and Antoine Joux for both his technical and financial support. A special thanks goes to Direction Générale de l'Armement and CNRS for funding the first author, and to the Swiss National Science Foundation for supporting the second author via grant number 200021-156420.

path represent the events that a new valid block has been found. The arrow is red if the block was found by A and green if it was found by a honest miner. There are only three kinds of arrows:

1. Red arrows to the right: when A finds a block, it only increases their own secret branch. 2. Green arrows that go up, without overpassing the diagonal: when a honest miner finds a new block but A's chain is longer, this block only increases the honest branch. 3. Green arrows on the diagonal: when a honest miner finds a new block and A's branch coincides with the honest chain, this block increases both chains.

Also, the path never follows the blue line: once the blue line has been reached, the next phase of A's strategy begins. To determine the probability of a k , the strategy will consist in computing the number of such paths to (n -1, n -1 -k) for any specified number of red arrows. Let Cx,y,r denote the number of paths from (0, 0) to (x, y) that follow all the previous requirements and go through r red segments precisely. Cx,y,r can be computed thanks to the following recursive formulae:

At the end, since the number r of red arrows to go to (n -1, n -1 -k) varies between k and n -1, the probability of a k is given by:

Together with Equation (15), we find:

The probability PA that A wins is so computed thanks to Equation (14), using Equations (3), ( 4) and ( 16) as explicit formulae for the inner probabilities Pre 0 (f0), Pre 0 (f01) and Pr(e0). Figure 8 shows how PA varies with λ, for µ = 1/2 and a fixed value of n = 144 that roughly corresponds to an adversary that starts mining with a day in advance. Note that with a relative computational power λ = 1/4, the probability that a provident adversary wins takes off from 50% to 74% in the realistic case when ∆ = 6. Figure 8 also suggests that being too provident is not necessary. Indeed, Pr(e0) is the only parameter that governs the variations of the probability PA when the adversary mines more or less in advance. We note that this probability stabilises very quickly, as mining with half-a-day, a day or a week in advance is roughly the same in terms of success.


P Fraundorf

Piecewise-Continuous Nano-Worlds Online

The familiar 1D barrier-tunneling problem, when converted to a trough-scattering problem instead, leads us to the strong-phase-object deBroglie phase-lag. This in turn reminds us of the exact Coulomb-scattering solution to the Schrödinger equation, and opens the door to real-time online electron-optic simulations with which students may discover: (a) ways to acquire and interpret data from modern multi-million dollar tools of electron-optics, (b) nano-characterization of matter on the atomic scale, (c) visualizations intermediate between direct and reciprocal space for harmonic-analysis of spatial-periodicities, and (d) important modern uses for crystal defects, including crystal surfaces themselves. CONTENTS I. Introduction 1 II. The deBroglie phase-lag 1 III. Coulomb/Rutherford scattering 2 IV. Electron-optics simulation 2 V. Nano-worlds online 3 VI. Discussion 5 A. underlying math 5 1. phase-lag and projected potential 6 2. point-charge scattering 6 3. electron-optics phase/amplitude contrast 7

I. INTRODUCTION

The one-dimensional barrier-tunneling problem is very popular in modern physics texts because it is: (a) analytically solvable, (b) connected to practical problems like alpha-decay, and (c) a beautiful illustration of the role of uncertainty in behaviors that would be classically disallowed. What is seldom mentioned, however, is that the same piecewise-constant potential setup, using a potential trough instead of a barrier, also makes contact with emerging science and technology. We show further that the exact Schrödinger-equation solution to the Coulombscattering problem (approximated classically by Rutherford) can similarly be inverted to reinforce this result.

In this note, in particular, we describe how that piecewise-constant potential-trough calculation gives rise to the strong-phase-object deBroglie phase-lag. We then show how calculations using this phase-lag are being used a) Electronic mail: pfraundorf@umsl.edu (with help from modern electronic technology) to provide students with a real-time window on the world of nanomaterials, as well as on ways currently under development for exploring that world with help from high-speed electrons.

II. THE DEBROGLIE PHASE-LAG

This is the classic one-dimensional problem: Define the vacuum wavevector k = 2π/λ v = √ 2mU / and the specimen wavevector K = 2π/λ s = 2m(U -V )/ , where U is the incident particle energy and V is potentialenergy associated with our particle in the "specimenregion" e.g. of width L.

In the barrier-tunneling case 0 < U < V , so as to make the wave classically disallowed in the specimen region. In the trough-scattering case, V < 0 < U so that wave-vector (hence momentum p = k = h/λ) of our particle actually increases in the specimen-region, and therefore our particle's wavelength (e.g. in [meters per cycle]) decreases. It's not surprising then that the size of this wavelength decrease is directly related to the number of deBroglie phase cycles which take place in traversing a specimen-region of thickness L.

One can of course also calculate the various reflected and transmitted wave amplitudes (relative the amplitude incident from the left) by equating wavefunctions and wavefunction spatial 1st-derivatives at specimen-region entry and exit points. This has been done for a wide range of V /U values in Figure 1. The diagonal bands in the lower right quadrant show clearly the deBroglie phase-lag running in the negative z-direction roughly in proportion to V /U for V < 0.

For application to high energy (U = 60 to 300 [keV]) electrons, condensed-matter attractive-potentials (like work functions) are in the negative tens of Volts so that |V /U | ≪ 1. The exact phase shift relative to V = 0 case is plotted (solid line) for unit-arguments in Fig. 2, along with two approximations. The first approximation (dashed) is simply the difference in wave-numbers (e.g. in [radians per meter]) times the "specimen-thickness" L, which assumes that the first order effect on the transmit-FIG. 1. One-dimensional wavefunctions (in logarithmic complex-color online) of an energy U wave incident from the left on a variable-V/U barrier/trough between 0 < z < 1. In each of these panels, the horizontal axis runs (left to right) from -6 ≤ z ≤ +6; if we set particle mass and Planck's constant to 1, while the vertical axis shows step-potentials ranging (bottom up) from -6 ≤ V /U ≤ +6. In the rightmost panel, the dotted horizontal-band is the region of positive barrier still lower than the particle energy (transmission still classically allowed), while the dotted vertical-band marks the barrier/trough region itself.

ted phase is simply the wavelength shift during traversal.

This in turn can be Taylor-expanded around the high particle-energy U limit of V /U → 0 to get the phaseshift of ∆φ ≃ -(V /U ) mU/2L/ . This gives us the straight line (dot-dashed) in Fig. 2 which is proportional to "projected-potential" Φ = V L e.g. in [eV-m].

For a specimen-potential which varies along a beampath in the z-direction, this might be written as Φ = L 0 V [z]dz. This prompts us to ask, however, whether such a phase-lag (with lateral variation in x and y) will also emerge if the trough for a plane-wave flowing through a three-dimensional solid is not flat, but instead shaped like the attractive Coulomb-potential for electrons passing through a set of atomic-nuclei. Amazingly, another of the rare classical exact-solutions to the Schrdinger equation, with a potential appropriately inverted, comes to the rescue once again.

III. COULOMB/RUTHERFORD SCATTERING

It's often forgotten that the classical Rutherford scattering problem is connected to an exact quantummechanical solution to the Schrödinger equation in threedimensions, which perhaps by accident 1 gives the same result as the classical calculation e.g. for atomic-number (Z) dependent nuclear back-scatttering. As in the case of the tunneling example discussed above, however, this problem is generally framed as a barrier-problem i.e. for predicting what happens when a positive-ion encounters a positively-charged atomic nucleus.

Once again, something also interesting emerges when we look at the "attractive" or "potential-well" version of the same calculation. As shown in Fig. 3, just as in the 1D case the interaction e.g. of an incoming electron with a localized positive charge also gives rise to a deBroglie FIG. 2. Phase-shift estimates using (solid) an exact piecewisecontinuous potential example, (dashed) the wavenumberdifference approximation, and (dot-dashed) the first term in the approximation's Taylor series around the V /U ≃ 0 or "high-energy U particle" approximation. phase-lag. Of course the Coulomb potential of atomic nuclei in condensed matter is screened at Ångström distances by the field of the electron cloud, but the principle underlying the observed phase-lag none-the-less remains that seen in our trough-scattering calculation above.

IV. ELECTRON-OPTICS SIMULATION

Thus introductory quantum-mechanics predicts an exit-surface deBroglie phase-lag, which varies depending on the projected-potential of atoms along the electrontrajectory, when an electron passes through a thin slice of condensed matter. Several issues remain, however. First, how can we convert that phase lag into a '"detected" map of projected-potential across the transverse coherencewidth of an '"individual" electron's wave-packet! Secondly, how does this projected-potential model fare both qualitatively and quantitatively as the specimen's thickness increases?

The answers to these questions are well established in the technical literature [START_REF] Spence | Experimental high-resolution electron microscopy[END_REF][START_REF] Reimer | Transmission electron microscopy: Physics of image formation and microanalysis[END_REF][START_REF] Kirkland | Advanced Computing in Electron Microscopy[END_REF] , so we won't elaborate on them here except to illustrate the "Scherzer defocus" condition 6 (Fig. 4) for converting the phase-lag map at the exit surface into an intensity-map downstream, and then to mention two calculations that physics undergraduates might enjoy.

The "Scherzer strategy" yields useful image intensities for spatial-frequencies out to the "point-resolution maximum". It does this primarily by moving the first dark/light intensity Fourier-phase inversion away from the origin in frequency-space (the "DC-peak"), associated with "spherical-aberration transfer-function zeros" of a convex magnetic lens, until a new pair of transferfunction zeros begins to insert itself into the region between DC-peak and that first-zero.

For sufficiently thin (weak phase-object) specimens, where the deBroglie phase lag is much less than 2π, Scherzer-defocus yields intensities that are inversely proportional to projected-potential i.e. where openings between atoms are bright and columns of atoms in projection look dark. The strong phase-object (arbitrary phase-lag) analysis discussed in addition shows a subset of thickness effects, but only incompletely considers multiple scattering.

The first enjoyable calculation may be to verify that electron-phase contrast is obtained from individual electrons. Not only are electrons fermions that obey Pauli exclusion, making them unwilling to share a single coherent state like photons do in a LASER, but typi-cal high-energy transmission-electron-microscope (TEM) specimen-currents are quite low i.e. in the nano-Ampere range.

Students might in that context use electron-energy to determine the speed of e.g. typical 100[keV] microscope electrons, and show that individual electrons in a nano-Ampere beam will be something like an inch apart in the direction of propagation. An electron-energy spread and hence energy-uncertainty at the parts-per-million level will increase the longitudinal coherence-length' of these electrons, but not nearly enough to allow them to overlap in the specimen even if we had a way to get them to share a common deBroglie phase. Hence on average there is only one electron traversing the specimen at a time, so all wave-interference (including diffraction effects) is being done with a single quantum-particle.

In order to map projected-potential laterally across multiple atom-columns in a condensed-matter specimen, of course, the transverse coherence-width of individual electrons must be expanded to many times the distance between atoms as well. This is done in modern electronoptical systems by reducing the transverse-momentum uncertainty of electrons at the specimen, largely by choice of a locally bright electron-source (like a LaB 6 or fieldemission gun) to begin with.

The second calculation involves the difference in calculation-time between strong-phase-object and morequantitative "multi-slice" image simulation. The strongphase-object approach, as we'll see, simulates a wide range of phenomena qualitatively. For quantitative simulation, however, one must propagate the incident beam through multiple slices of the specimen.

For an n × n pixel image field this is generally done in an n × n complex-coefficient "reciprocal space". This means that each slice past the first requires that one do n 2 more strong-phase-object calculations. For a minimally useful 256 × 256 pixel field, this means that simulations will take some integral multiple of 65, 536 times longer, and hence be difficult to do in real time even on systems with relatively fast processors.

V. NANO-WORLDS ONLINE

The simplicity of the deBroglie phase-lag and the power of the resulting strong-phase-object approximation, combined with the speed of fast-Fourier-transform (FFT) algorithms implemented in javascript on modern processors, gives us an ability to simulate online in realtime the exploration of nanomaterials with high energy electrons. This article is not the place to detail the many types of explorations that are now possible online, in part because they make contact (beyond the worlds of electron scattering and electron optics) with condensed matter topics like: (a) crystallography and bulk/surface defect-crystallography, (b) pair and pair-pair correlations in non-crystalline materials, as well as (c) the behavior of individual molecules in the neighborhood of surfaces, FIG. 4. Electron phase contrast transfer function and wavefield image analysis: At left find maps of contrast-transfer versus spatial-frequency without (left-half) and with (right-half) spherical aberration, as a function of imaging-system defocus in the vertical direction. At right find images (left-half) and image power-spectra (right-half) showing contrast transfer zeros at Gaussian and Scherzer defocus. In the thin-specimen limit, cyan bands (color online) in the panel at left show specimen-regions of increased projected-potential as darker, while red bands show contrast as reversed. FIG. 5. Fig. 5: Brightfield high-resolution TEM (phase) and darkfield scanning-TEM (amplitude) screenshots of an "unknown" specimen in an online simulator 2 , with the same defocus, orientation, and darkfield-aperture. FIG. 6. A hemoglobin molecule in an online simulator, with a likely alpha-helix (circle at top) viewed end on in the absence of the vacuum re-arrangement, beam damage, and the need for a "support" that might get "in the way" experimentally.

of vacuum, of high energy electrons. Such explorations will be discussed by ourselves and others under separate cover.

However this does not make these developments irrelevant to undergraduate physics students and teachers. Far from it, since such simulators give students phenomenological access (at least qualitatively) to a wide range of phenomena, including small-wavelength (flat Ewaldsphere) diffraction from three-dimensional single and poly crystalline unknowns, strain imaging tools (including both diffraction contrast and digital darkfield interferometry), an ability to form darkfield images of selected periodicities, to switch between deBroglie phase-contrast and Z-contrast imaging modes, to get 2D "Fourier-phase information" about specimens that is impossible to obtain directly from diffraction, etc. Figure 5, for example, shows two-screen shots of a near-Scherzer-focused online simulator examining an Au/ZnO 2 bi-crystal tilted so that the phase-interface is side-on. The left-half of the figure provides a strongphase-object approximation deBroglie phase-contrast image of atom columns in projection down that orientation (top-left), and diffraction pattern of the crystal (topright), a power-spectrum of the phase-contrast image (bottom-right), and the complex-color digital-darkfield image (obtained from the image Fourier transform) of periodicities selected by an aperture (white circle) in the power spectrum.

The right-half of the figure in effect reverses the path of electrons through the electron-optic system, which by reciprocity allows us to record (with comparable resolution) an incoherently-illuminated high-angle annular darkfield image of the same specimen. The physics of this type of image is somewhat different, and not the topic of this paper here. Nonetheless students and teachers can get a visceral feel for the qualitative differences between these imaging modes, whether or not they later learn to understand, and/or apply, such tools for nanoworld detective work of their own downstream.

VI. DISCUSSION

As discussed above, the piecewise-constant potential calculation used in undergraduate physics courses to explain quantum tunneling can also yield for us insight into the deBroglie phase-lag which is central to modern electron-based tools for experimental study of condensed matter. We try to make this connection here so that teachers, and textbook authors in the future, can put the connection to use.

There is also an exciting future in physics education for the kinds of electron-image simulators to which this deBroglie phase-lag connects. Students already get some visceral experience with electron-diffraction and electronimaging as it is used today to provide insight into a wide range of condensed matter challenges in the physical and life sciences. In the latter context Fig. 6 shows what the alpha-helix in a hemoglobin molecule might look like edge-on, if we can find a way to either average over or lessen the effects of vacuum and ionization damage in real electron microscopes.

A wide range of other interesting "nano-specimens" remain yet to be assembled. In addition to specimentilting, future incarnations of these online simulators will allow for other imaging and analysis modes, specimen translation, and even zooming from nanometer to millimeter field-widths on procedurally-generated specimens.

Today's physics teachers and students can help apply their own skills to these developments, which mainly require access to the internet through a web-browser. In fact, these developments in turn will help with development of improved-interfaces to the modern multi-million dollar aberration-corrected instruments now available at selected facilities for researchers with interesting nanoworld puzzles to solve. FIG. 7. Plots of electron potential V [x, y, z] for electron trajectories along two different "columns" through the specimen.

phase-lag and projected potential

This is a standard homework exercise e.g. for modern physics, but it might not hurt to outline some details here. Consider a one-dimensional potential of the form:

V [z] =      0 if z < 0 (region 1: upstream) -eΦ if 0 ≤ z ≤ T (region 2: specimen) 0
if z > T (region 3: downstream) (A1) where Φ is an average projected-potential in the specimen column of interest. This average potential (cf. Fig. 7) depends strongly on the proximity of atomic nuclei in the specimen to the selected column, and will e.g. be much less if the column follows a tunnel between atoms through the structure. Our objective is to examine ways that the transmitted wave reflects changes, from columnto-column, in this projected-potential.

For incident plane waves of the form Ψ[z, t] = Ae ı(kz-ωt) in the positive z-direction with electron kinetic energy E r = eV r , write out the Schrödinger equation for regions 1, 2 and 3 with parameters specified in terms of the quantities given above. The one-dimensional non-relativistic free-particle Schrödinger wave equation, for instance, may be written:

- 2 2m ∂ 2 ψ ∂z 2 + V [z]ψ = ı ∂ψ ∂t , ( A2
)
where ψ is the wave function whose amplitude squared yields a probability density as a function of position and time, the expression ı ∂/∂t on the right is the "energy operator", and the first term on the left represents the classical kinetic-energy operator i.e. the "momentum operator" ı ∂/∂z squared over 2m. The Schrödinger equation basically differs from region to region here only by the addition of the negative but piecewise-constant workfunction potential energy -eΦ which multiplies the wavefunction in region 2.

Next write out the form for wavefunction solutions of that equation in each of these regions, in terms of some yet undetermined constants. The high-energy electron wave in the first two regions might be described for region 1 (upstream) as ψ 1 [z] = Ae ıkz + Be -ıkz , and for region 2 (specimen) as ψ 1 [z] = Ce ıkz + De -ıkz . Here the "'vacuum wavevector" k = 2π/λ v = √ 2meV r / while the "specimen wavevector" K = 2π/λ s = 2me(Φ + V r )/ is larger (implying a smaller electron wavelength λ s in the specimen) because the solid attracts electrons. We'll leave it as an exercise for the reader to do the same for region 3 (downstream), using say F and G for the forward and reverse wave coefficients in each case.

Following this, write out boundary conditions that these constants obey at the boundaries between region 1, 2, and 3. For instance at the z = 0 boundary between regions 1 and 2, equating ψ values gives A + B = C + D while equating ∂ψ/∂z values gives ık(A -B) = ıK(C -D). Do the same thing then for the z=T boundary between regions 2 and 3, and then solve for the "amplitude" of the transmitted wave at z = T as a function of the incident amplitude A, and wave vectors k and K in regions 1 and 2. Also show how this simplifies when V r ≫ Φ. The results are discussed in the text.

At relativistic speeds, electron momentum goes from

p ≃ √ 2m e E k to p = 2E k (E o + E k )/c.
Here rest energy E o ≡ m e c 2 , where c and m e are lightspeed and electron rest-mass, respectively. Hence wavenumber k = 2π λ is changed via the dependence of wavelength on momentum λ = h/p. Also, the ratio between wavelength outside the specimen to wavelength inside the specimen (i.e. the specimen's refractive index) changes subtly as well. Therefore the factor of 1 2Vr , which multiplies projected potential to get the optical path difference, becomes 1

Vr

Eo+E k 2Eo+E k . Otherwise, the above analysis of phase shift remains intact 3,4 .

point-charge scattering

Following e.g. Messiah's Chapter XI on the Coulomb Interactiont 1 , a naked-charge wavefield model may be obtained if the 1/r Coulomb potential term is inserted into Schrödinger's partial differential equation:

- 2 2m ∇ 2 + Z 1 Z 2 e 2 r ψ[ r] = Eψ[ r]. (A3)
This is of course the hydrogen atom potential, but here we'd like the solution in a form that can be broken down into incident and scattered plane wave components. Such a solution may be expressed in terms of the threeargument confluent hypergeometric function 1 F 1 [u|v|w] as:

ψ c = Ae ıkz 1 F 1 - ı ka |1| ık(r -z) , (A4)
where A is an adjustable constant and a ≡ 2 /(Z 1 Z 2 me 2 ) is inversely proportional to the interaction strength. This wave function is the one that is plotted in Fig. 3. The above differential equation might be modified for addition of a neutralizing charge sphere at radius R, by merely stepping the potential for r > R down to zero. Solutions for no potential of course generally look something like Ae ıkz . Since the solutions for both potentials in standalone form are known, one might take the next step with a composite wave model for the neutralized charge by simply joining those two solutions up at the spherical r = R boundary.

Spherically-symmetric atomic-scattering-factors are often used instead to propagate a planar (or convergent/divergent) wavefront though the specimen. For quantitative work, multislice strategies 5 consider the sequential evolution of a scattered wave through atomically thin slices of specimen in sequence.

Regardless, to first order the electron wavefunction (whose transverse coherence is many atoms in width) will exhibit a deBroglie phase-shift (relative to nearby columns) which is from section A 1 proportional to the projected-potential at the exit surface of the specimen. The problem is that an image of the phase-contrast in the exit wave-function cannot be detected directly, and so in the next section we turn to electron optics for a solution to that problem.

For sufficiently thick specimens and/or with incoherent illumination, atomic columns will also exhibit an amplitude decrease due to scattering which is a monotone increasing-function of projected potential. Given the projected-potential this too is relatively easy to approximate roughly.

electron-optics phase/amplitude contrast

Scattering in quantum mechanics results in an electron wave which is both phase shifted, and changed in direction. A classic use of the Born approximation, the WKB method, and partial wave analyses has been calculating the angular dependence of scattering from single atoms, based on the details of charge distribution within -Rutherford's famous discovery of the nucleus was an early consequence thereof. Fortunately for the electrons discussed here, these angular issues are less important because scattering angles are well under 10 milliradians.

If one uses apertures which are large enough to include both scattered and unscattered beams (e.g. in the back focal plane of the objective lens, where exit surface waves are separated according to direction rather than amplitude), then one can imagine imaging the amplitudeadded unscattered and scattered wavefields together (at least over specimen distances less than the transverse coherence width of incident electrons). Hence the first practical requirements for electron phase contrast imaging are thin specimens, moderate coherence width illumination, and large objective apertures.

Under these conditions, the imaged exit surface wave from a thin crystal looks like the incident wave, multiplied by e +iσ , where σ[x, y] ≃ k 2Vr Φ[x, y] varies with lateral coordinate values x and y across the specimen. If the phase angle is small (i.e. much less than π), the multiplying factor can be approximated by e +iσ ≃ 1+iσ.

Imagine a one dimensional specimen with only spatial frequency q = 1/Λ, where Λ is the repeat distance, e.g. so that σ[x] = σ o cos[2πqx]. At the exit surface, the wavefield will have been multiplied by ψ

[x] = 1+iσ o cos[2πqx].
Note that, as long as σ o << 1, the amplitude of the composite wave field is hardly affected by the specimen's periodicity. In light microscopy, this problem is overcome by inserting a Zernike phase plate 4 for shifting the scattered beam only by an additional π/2, resulting (when recombined) in first order amplitude effects.

In the absence of a suitable phase plate, one can instead defocus one's imaging optics so as to sample the wavefield downstream (or virtually, upstream as well) from the exit surface of the specimen, at a point where phase differences at the exit surface interfere with one another to create ripples in intensity which may be photographed. What defocus setting is appropriate depends on the spatial frequencies of interest.

Physically, the scattered wavefield evolves by convolution with the Fresnel propagator, which is oft written (apart from a constant factor 3 ) as e iπ(x 2 +y 2 ) λ∆z

. Here ∆z is the distance from the exit-surface along the beam direction, or the "defocus setting", defined so as to be positive in the downstream (underfocus) direction. In frequency space, this is equivalent to multiplying the wavefield by the propagator's Fourier transform, the transfer function e -iW defined here in terms of the "defocus function" W [∆z] = πλ∆z(q 2 x + q 2 y ). For our single frequency specimen, the imaged amplitude is thus modulated by

ψ = 1 + ie -iW σ o cos[2πqx]. The intensity found in the image becomes I ≡ ψ * ψ = 1 + 2sin[W ]σ o cos[2πqx].
The factor sin[W ], a function of both defocus ∆z and spatial frequency q, thus determines both the strength and sign of intensity ripples corresponding to specimen structure, in the captured image. It predicts dark spots in the neighborhood of large phase shifts (e.g. atom columns), for example when W is near -π/2. We also might want to choose defocus ∆z so that the images are simplest to interpret, e.g. so that sin[W ] is finite and constant for as wide a range of frequencies as possible. To assist with this, we've plotted sin[W ] a function of transverse spatial frequency q, and defocus ∆z, for unit wavelength on the left hand side of Figure 4.

Spherical aberration in the objective lens also affects the image. The effect is shown graphically on the right hand side of Figure 4. Since zeros in sin[W ] correspond to phase reversals for the corresponding periodicity, a traditional goal has been to select a defocus for which these zero's are moved outward to as high a frequency as possible. As illustrated in the diagram, Scherzer defocus is the setting of choice in this regard.

Recent work has concentrated on focussed-probe illumination in which the aberrations occur upstream of the specimen, which probe in "scanning transmission" (STEM) is rastered across the specimen, resulting generally in more amplitude rather than phase contrast, and on "aberration-correction" which uses controllable aberrations to correct uncorrectable aberrations (like spherical) in one focus plane only. The latter requires more work in focusing, but has allowed sub-Angstrom lateral resolutions, even at beam voltages which are below the knock-on threshold from important light atoms like carbon [START_REF] Krivanek | Atomby-atom structural and chemical analysis by annular dark-field electron microscopy[END_REF] .

For quantitative microscopy of thicker specimens in real microscopes, of course, other issues must be considered as well: e.g. vibration and electrical instabilities, knowledge of specimen thickness, astigmatism, and the range of illumination angles in the beam. Even then the theory remains quite elegant, and except for the effects of specimen thickness can be visualized by changes in the fingerprint of Fig 4. Of course, this analysis might seem abstract. Au contraire! Recall that amorphous materials in projection are, unlike crystals, likely to show a uniform distribution of periodicities. As a result, the zeros of the imaginary part of the Fresnel transfer function, for the current defocus setting in the right side of Fig 4, show up as rings in the power spectrum from amorphous material in every HREM image.

FIG. 3 .

 3 FIG. 3. Coulomb scattering (in complex-color online) of a negative charge's deBroglie extended wavefield by a fixed positive charge, from one of those rare regular solutions of the Schrödinger equation.

FIG. 8 .

 8 FIG.8. An electron phase contrast image of the internal structure of a 15 wall carbon nanotube, the innermost 6 atomic layers of which form an internal closure.

ACKNOWLEDGMENTS

Thanks to industry and university collaborators across the region for related projects.

Appendix A: underlying math

In order to increase assessibility, in the main body of this paper we've tried to illustrate using quantitative graphical techniques like complex-color, which lets us show the amplitude and phase of a complex number with a single pixel. In this appendix, however, we attempt to connect interested readers to the underlying models and approximations.