中本聪在密码学邮件组的发言

注：选译自 Satoshi Nakamoto Institute 编辑整理的版本。仅作收录。

---------------------------------------------------------------------

Cryptography Mailing List
Bitcoin P2P e-cash paper
2008-10-31 18:10:00 UTC - Original Email - View in Thread

我一直在研究一种新电子现金系统，完全点对点，无受信第三方。

The paper is available at:
http://www.bitcoin.org/bitcoin.pdf

主要特性：

• 以点对点网络防止双重花费。
• 无铸币厂或其他受信方。
• 参与者可为匿名。
• 新币由 Hashcash style proof-of-work 制成。
• 用以新币生产过程的 proof-of-work ，也用以驱动网络防止双重花费。

比特币：一个点对点电子现金系统

概要.一个纯粹的点对点电子现金版本，将允许在线支付，直接从一方发送到另一方，无需通过金融机构。数字签名提供部分解决方案，但是，如果仍然需要受信第三方来防止双重花费，此类解决方案的主要优势则失去。我们提出双重花费问题的一个解决方案：使用一个点对点网络。通过将交易哈希到不断进行的基于哈希的 proof-of-work 链中，网络对交易打上时间戳，从而形成一个记录，如果不重做该 proof-of-work，这个记录便无法被更改。最长链，不仅可作为所被见证的事件序列的证明，还可证明它来自最大的 CPU 算力集合。只要大多数 CPU 算力由不合作攻击网络的节点控制，这些算力就将生成最长链，并超过攻击者。网络本身需要最小结构。消息被尽力传播，节点可随意离开，也可随意重新加入网络，接受最长 proof-of-work 链，作为这些节点离开时所曾发生事件的证明。

Full paper at:
http://www.bitcoin.org/bitcoin.pdf

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List
Bitcoin P2P e-cash paper
2008-11-03 01:37:43 UTC - Original Email - View in Thread

>Satoshi Nakamoto wrote:
>> I've been working on a new electronic cash system that's fully
>> peer-to-peer, with no trusted third party.
>>
>> The paper is available at:
>> http://www.bitcoin.org/bitcoin.pdf
>
>We very, very much need such a system, but the way I understand your
>proposal, it does not seem to scale to the required size.
>
>For transferable proof of work tokens to have value, they must have
>monetary value. To have monetary value, they must be transferred within
>a very large network - for example a file trading network akin to
>bittorrent.
>
>To detect and reject a double spending event in a timely manner, one
>must have most past transactions of the coins in the transaction, which,
> naively implemented, requires each peer to have most past
>transactions, or most past transactions that occurred recently. If
>hundreds of millions of people are doing transactions, that is a lot of
>bandwidth - each must know all, or a substantial part thereof.
>

远在网络接近这么大规模之前，对于用户而言，使用 Simplified Payment Verification (section 8) 来 check for 双重花费，是安全的，Simplified Payment Verification 只需要有 the chain of block headers ，约相当于 12KB / 天。只有尝试创建新币的人才需要运行网络节点。起初，大多数用户会运行网络节点，但随着网络增长超过某一特定点，运行节点将越来越依赖 specialists with server farms of specialized hardware （ it would be left more and more to specialists with server farms of specialized hardware ）。A server farm 只需要在网络上有一个节点， the LAN 的其余部分与该节点连接 ( A server farm would only need to have one node on the network and the rest of the LAN connects with that one node )。

带宽可能不会如你所想那么高得令人却步（ prohibitive ）。一笔典型交易大约是 400 bytes ( ECC is nicely compact) 。每个交易必须广播两次，所以，每笔交易 为 1KB 。Visa 在 2008 财年处理了 370 亿笔交易，平均每天处理 1 亿笔交易。这么多的交易，需要 100GB 带宽，或相当于 12 DVD 或 2 HD quality movies 大小，或以当前价格计约价值 18 美元的带宽。

如果网络变得那么大规模，那将需要几年时间，到那时，通过互联网发送 2 HD movies 可能看起来不是什么大问题。

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-03 16:23:49 UTC - Original Email - View in Thread

>> As long as honest nodes control the most CPU power on the network,
>> they can generate the longest chain and outpace any attackers.
>
>But they don't. Bad guys routinely control zombie farms of 100,000
>machines or more. People I know who run a blacklist of spam sending
>zombies tell me they often see a million new zombies a day.
>
>This is the same reason that hashcash can't work on today's Internet
>-- the good guys have vastly less computational firepower than the bad
>guys.

谢谢你提出这一点。

我强调得还不够。要求是，good guys 共同拥有的 CPU 算力，多于任何一单一攻击者（ any single attacker ）。

会有许多较小 zombie farms，其规模不足以制服网络，他们仍然可以通过生成 bitcoins 来赚钱。那么，这些规模较小的 farms 就是“诚实节点”。（我需要一个比“诚实”更好的术语）越多较小 farms 致力生成 bitcoins ，制服网络的门槛就越高，使更大的 farms 也因为自身太小而无法制服网络，这样，这些更大的 farms 也可能致力生产 bitcoins 。据长尾理论，小型，中型和仅仅大型 farms 的组合，加起来，应该比最大的 zombie farm 大得多。

即使一个 bad guy 确实制服了网络，也不会让他立即变得富有。他所能完成的就是，拿回他自己所花费掉的钱，就像 bouncing a check 。为了利用这一点，他将不得不从一个商家处购买某些东西，等到发货，然后制服网络，试图取回他的钱。我认为，他通过试图 pull a carding scheme 所赚取的钱，不会比他通过生成 bitcoins 所赚取的更多。有这么大的 zombie farm ，他可以生成的 bitcoins ，比其他所有人加起来生成的都更多。

Bitcoin 网络可能实际上通过将 zombie farms 转向生成 bitcoins 来减少 spam 。

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-06 20:15:40 UTC - Original Email - View in Thread

>[Lengthy exposition of vulnerability of a systm to use-of-force
>monopolies ellided.]
>
>You will not find a solution to political problems in cryptography.

是的，但我们可以在军备竞赛中赢得一场重大战役，并在几年内获得一个新的自由领域 。

政府擅长切断中心化控制网络的源头，如 Napster ，但像 Gnutella 和 Tor 这样的纯粹 P2P 网络似乎表现坚挺。

Satoshi

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-08 18:54:38 UTC - Original Email - View in Thread

Ray Dillinger:
> the "currency" is inflationary at about 35%
> as that's how much faster computers get annually
> ... the inflation rate of 35% is almost guaranteed
> by the technology

日益增长的硬件速度问题已解决：“为了弥补随着时间推移，硬件速度的提高及运行节点所带来的利益的变化，proof-of-work 难度由 a moving average targeting an average number of blocks per hour 确定。如果区块生成得太快，难度会提升。”

随着计算机变得更快，用于创建 bitcoins 的总算力增长，难度相应增长，以保持总的新产量不变。因此，在未来，每年有多少新 bitcoins 将创建，这是预先已知的。

新币生成，这个事实意味着货币供应按计划量增加了，但这并不必然导致通胀。如果货币供应增加速率与使用此货币的人数增加速率相同，价格保持稳定。如果货币供应不如需求增长快，就会出现通缩，货币的早期持有者将会看到其价值增加。

币必须以某种方式进行最初分配，一个恒定速率（ a constant rate ）似乎是最佳方案。

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-09 01:58:48 UTC - Original Email - View in Thread

Hal Finney wrote：
> it is mentioned that if a broadcast transaction does not reach all nodes,
> it is OK, as it will get into the block chain before long. How does this
> happen - what if the node that creates the "next" block (the first node
> to find the hashcash collision) did not hear about the transaction,
> and then a few more blocks get added also by nodes that did not hear
> about that transaction? Do all the nodes that did hear it keep that
> transaction around, hoping to incorporate it into a block once they get
> lucky enough to be the one which finds the next collision?

Right, nodes keep transactions in their working set until they get into a block. If a transaction reaches 90% of nodes, then each time a new block is found, it has a 90% chance of being in it.

> Or for example, what if a node is keeping two or more chains around as
> it waits to see which grows fastest, and a block comes in for chain A
> which would include a double-spend of a coin that is in chain B? Is that
> checked for or not? (This might happen if someone double-spent and two
> different sets of nodes heard about the two different transactions with
> the same coin)

That does not need to be checked for. The transaction in whichever branch ends up getting ahead becomes the valid one, the other is invalid. If someone tries to double spend like that, one and only one spend will always become valid, the others invalid.

Receivers of transactions will normally need to hold transactions for perhaps an hour or more to allow time for this kind of possibility to be resolved. They can still re-spend the coins immediately, but they should wait before taking an action such as shipping goods.

> I also don't understand exactly how double-spending, or cancelling
> transactions, is accomplished by a superior attacker who is able to muster
> more computing power than all the honest participants. I see that he can
> create new blocks and add them to create the longest chain, but how can
> he erase or add old transactions in the chain? As the attacker sends out
> his new blocks, aren't there consistency checks which honest nodes can
> perform, to make sure that nothing got erased? More explanation of this
> attack would be helpful, in order to judge the gains to an attacker from
> this, versus simply using his computing power to mint new coins honestly.

攻击者不是添加区块到末端。他必须转回头，重做他的交易所在区块，以及之后的所有区块，以及当他如此做的同时，该网络所持续添加到末端的新区块。他在重写历史。一旦他的分支更长，这条分支就成为新的有效链。

这触及到一个关键点。尽管在场的每个人可能看到恶作剧在发生， there's no way to take advantage of that fact（ This touches on a key point. Even though everyone present may see the shenanigans going on, there's no way to take advantage of that fact ）。

严格而言，最长链总是被认为是有效链，这是必须的。在场节点们可能记得，其中一条分支是首先到达，然后被另一条取代，但他们无法说服不在场的那些节点（ there would be no way for them to convince those who were not present of this ）。我们无法依赖于这样的事实：依附于其中一条分支的一小派节点，这些节点认为这条分支才是先到达的；其他一小派节点看到另一条分支首先到达；后加入的其他节点，从未看到曾发生过什么。CPU 算力 proof-of-work 投票拥有最终话语权。对于每个人而言，取得一致的唯一方式是，无论如何，相信最长链总是有效的那条（ The only way for everyone to stay on the same page is to believe that the longest chain is always the valid one, no matter what ）。

> As far as the spending transactions, what checks does the recipient of a
> coin have to perform? Does she need to go back through the coin's entire
> history of transfers, and make sure that every transaction on the list is
> indeed linked into the "timestamp" block chain? Or can she just do the
> latest one?

The recipient just needs to verify it back to a depth that is sufficiently far back in the block chain, which will often only require a depth of 2 transactions. All transactions before that can be discarded.

> Do the timestamp nodes check transactions, making sure that
> the previous transaction on a coin is in the chain, thereby enforcing
> the rule that all transactions in the chain represent valid coins?

Right, exactly. When a node receives a block, it checks the signatures of every transaction in it against previous transactions in blocks. Blocks can only contain transactions that depend on valid transactions in previous blocks or the same block. Transaction C could depend on transaction B in the same block and B depends on transaction A in an earlier block.

> Sorry about all the questions, but as I said this does seem to be a
> very promising and original idea, and I am looking forward to seeing
> how the concept is further developed. It would be helpful to see a more
> process oriented description of the idea, with concrete details of the
> data structures for the various objects (coins, blocks, transactions),
> the data which is included in messages, and algorithmic descriptions
> of the procedures for handling the various events which would occur in
> this system. You mentioned that you are working on an implementation,
> but I think a more formal, text description of the system would be a
> helpful next step.

I appreciate your questions. I actually did this kind of backwards. I had to write all the code before I could convince myself that I could solve every problem, then I wrote the paper. I think I will be able to release the code sooner than I could write a detailed spec. You're already right about most of your assumptions where you filled in the blanks.

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-09 03:09:49 UTC - Original Email - View in Thread

James A. Donald wrote:
> The core concept is that lots of entities keep complete and consistent
> information as to who owns which bitcoins.
>
> But maintaining consistency is tricky. It is not clear to me what
> happens when someone reports one transaction to one maintainer, and
> someone else transports another transaction to another maintainer. The
> transaction cannot be known to be valid until it has been incorporated
> into a globally shared view of all past transactions, and no one can
> know that a globally shared view of all past transactions is globally
> shared until after some time has passed, and after many new
> transactions have arrived.
>
> Did you explain how to do this, and it just passed over my head, or
> were you confident it could be done, and a bit vague as to the details?

proof-of-work 链是此同步问题的解决方案，也是 “ 在不必须信任任何人的情况下，就可确知 globally shared view ” 的解决方案。

一笔交易将很快传达网络，所以，如果同笔交易的两个版本几乎同时被广播，拥有 the head start 的那个版本，在首先到达更多得多的节点方面，拥有优势。节点们将只接受他们看到的第一个版本，拒绝第二个到达的版本，所以，更早的那笔交易将有更多得多的节点致力将其纳入 the next proof-of-work 。实际上，每个节点投票给其 viewpoint——通过将一笔交易包含入其 proof-of-work effort，以此表达它看到哪笔交易首先到达。

如果各笔交易几乎同时到达，将有一个均匀分裂（ even split ），这是一项艰难选择，基于哪一笔交易最先进入 a proof-of-work ，由此决定哪一条链是有效的。

当一个节点发现 a proof-of-work ，该新区块传达至网络，每个人将其添加至链，开始致力于这个区块之后下一个区块。拥有另一笔交易的任意节点将停止尝试将另一笔交易包含入一个区块，因为，根据被接受的链，这笔交易现在是无效的。

proof-of-work 链本身是不证自明的证明，它来自 globally shared view 。只有网络大多数共同，才拥有足够 CPU 算力，来生成这样一条具有难度的 proof-of-work 链。接受该 proof-of-work 链的任意用户，可看到网络的大多数已经批准了什么。一旦一笔交易被哈希进一条链中的 a link ，其之后有一些 links ，这笔交易就稳固地蚀刻进 the global history。

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-09 16:31:26 UTC - Original Email - View in Thread

James A. Donald wrote:
>OK, suppose one node incorporates a bunch of
>transactions in its proof of work, all of them honest
>legitimate single spends and another node incorporates a
>different bunch of transactions in its proof of
>work, all of them equally honest legitimate single
>spends, and both proofs are generated at about the same
>time.
>
>What happens then?

They both broadcast their blocks. All nodes receive them and keep both, but only work on the one they received first. We'll suppose exactly half received one first, half the other.

In a short time, all the transactions will finish propagating so that everyone has the full set. The nodes working on each side will be trying to add the transactions that are missing from their side. When the next proof-of-work is found, whichever previous block that node was working on, that branch becomes longer and the tie is broken. Whichever side it is, the new block will contain the other half of the transactions, so in either case, the branch will contain all transactions. Even in the unlikely event that a split happened twice in a row, both sides of the second split would contain the full set of transactions anyway.

It's not a problem if transactions have to wait one or a few extra cycles to get into a block.

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-10 02:14:30 UTC - Original Email - View in Thread

James A. Donald wrote:
> Furthermore, it cannot be made to work, as in the
> proposed system the work of tracking who owns what coins
> is paid for by seigniorage, which requires inflation.

If you're having trouble with the inflation issue, it's easy to tweak it for transaction fees instead. It's as simple as this: let the output value from any transaction be 1 cent less than the input value. Either the client software automatically writes transactions for 1 cent more than the intended payment value, or it could come out of the payee's side. The incentive value when a node finds a proof-of-work for a block could be the total of the fees in the block.

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-10 22:18:20 UTC - Original Email - View in Thread

James A. Donald wrote:
> So what happened to the coin that lost the race?
>
> ... it is a bit harsh if the guy who came second
> is likely to lose his coin.

When there are multiple double-spent versions of the same transaction, one and only one will become valid.

The receiver of a payment must wait an hour or so before believing that it's valid. The network will resolve any possible double-spend races by then.

The guy who received the double-spend that became invalid never thought he had it in the first place. His software would have shown the transaction go from "unconfirmed" to "invalid". If necessary, the UI can be made to hide transactions until they're sufficiently deep in the block chain.

> Further, your description of events implies restrictions
> on timing and coin generation - that the entire network
> generates coins slowly compared to the time required for
> news of a new coin to flood the network

Sorry if I didn't make that clear. The target time between blocks will probably be 10 minutes.

Every block includes its creation time. If the time is off by more than 36 hours, other nodes won't work on it. If the timespan over the last 6*24*30 blocks is less than 15 days, blocks are being generated too fast and the proof-of-work difficulty doubles. Everyone does the same calculation with the same chain data, so they all get the same result at the same link in the chain.

> We want spenders to have certainty that their
> transaction is valid at the time it takes a spend to
> flood the network, not at the time it takes for branch
> races to be resolved.

Instantant non-repudiability is not a feature, but it's still much faster than existing systems. Paper cheques can bounce up to a week or two later. Credit card transactions can be contested up to 60 to 180 days later. Bitcoin transactions can be sufficiently irreversible in an hour or two.

> If one node is ignoring all spends that it does not
> care about, it suffers no adverse consequences.

通过我最近发布的基于 transaction fee 的激励系统，节点将受到激励，包含所有他们所接收到的 the paying transactions ( With the transaction fee based incentive system I recently posted, nodes would have an incentive to include all the paying transactions they receive )。

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-13 22:56:55 UTC - Original Email - View in Thread

James A. Donald wrote:
> It is not sufficient that everyone knows X. We also
> need everyone to know that everyone knows X, and that
> everyone knows that everyone knows that everyone knows X
> - which, as in the Byzantine Generals problem, is the
> classic hard problem of distributed data processing.

proof-of-work 链是拜占庭将军问题的一个解决方案( The proof-of-work chain is a solution to the Byzantine Generals' Problem )。我将尝试在此语境中 rephrase 它。

有许多拜占庭将军，每位都有一台计算机，想通过暴力破解密码来攻击国王的 Wi-Fi ，他们已知密码是 一定长度的字符串 。一旦他们刺激网络生成数据包，他们必须在有限时间内破解密码以 break in 以及 erase the logs，否则他们将被发现并陷入困境。只有他们中的大多数同时攻击，才能获得足够 CPU 算力以足够快地破解密码。

他们并不特别关心攻击时间，只要他们达成共识。已经决定的是，任何人，只要喜欢，都可宣布一次时间；首次被听到的那个时间，将成为正式攻击时间。问题在于，网络不是即时的，如果两位将军几乎同一时间宣布不同的攻击时间，有些人可能先听到其中一个，其他人先听到另一个。

他们使用 proof-of-work 链来解决这个问题。一旦每个将军收到他首先听到的任何攻击时间，他就会安置他的计算机以解决一个极其困难的 proof-of-work 问题，这个问题将攻击时间包含入其哈希。The proof-of-work 是如此困难，预计他们所有人一次花费 10 分钟致力于此，直到他们中的一个发现了一个解决方案。一旦其中一位将军找到 a proof-of-work，他将其广播到网络，每个人都改变他们当前的 proof-of-work 计算，以将此 proof-of-work 包含入他们所正致力于的哈希中。如果有人在致力于一个不同的攻击时间，这些人会切换到这个攻击时间，因为其 proof-of-work 链现在更长。

两个小时后，一个攻击时间应该被 a chain of 12 proofs-of-work 进行哈希处理（ one attack time should be hashed by a chain of 12 proofs-of-work ）。每个将军只需通过验证 the proof-of-work 链的难度，可估计每小时有多少并行 CPU 算力花费于此，看到它必须要求大多数计算机在规定时间内才能产出这么多的 proof-of-work 。必须所有人都看到这一条链，因为 the proof-of-work 证明了他们致力于此。如果该 proof-of-work 链所显示的 CPU 算力足以破解密码，他们可以在约定的时间实施安全的攻击。

proof-of-work 链是你所问的同步，分布式数据库以及 global view 问题的解决方案（ The proof-of-work chain is how all the synchronisation, distributed database and global view problems you've asked about are solved ）。

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-14 18:55:35 UTC - Original Email - View in Thread

Hal Finney wrote:
> I think it is necessary that nodes keep a separate
> pending-transaction list associated with each candidate chain.
> ... One might also ask ... how many candidate chains must
> a given node keep track of at one time, on average?

Fortunately, it's only necessary to keep a pending-transaction pool for the current best branch. When a new block arrives for the best branch, ConnectBlock removes the block's transactions from the pending-tx pool. If a different branch becomes longer, it calls DisconnectBlock on the main branch down to the fork, returning the block transactions to the pending-tx pool, and calls ConnectBlock on the new branch, sopping back up any transactions that were in both branches. It's expected that reorgs like this would be rare and shallow.

With this optimisation, candidate branches are not really any burden. They just sit on the disk and don't require attention unless they ever become the main chain.

> Or as James raised earlier, if the network broadcast
> is reliable but depends on a potentially slow flooding
> algorithm, how does that impact performance?

Broadcasts will probably be almost completely reliable. TCP transmissions are rarely ever dropped these days, and the broadcast protocol has a retry mechanism to get the data from other nodes after a while. If broadcasts turn out to be slower in practice than expected, the target time between blocks may have to be increased to avoid wasting resources. We want blocks to usually propagate in much less time than it takes to generate them, otherwise nodes would spend too much time working on obsolete blocks.

I'm planning to run an automated test with computers randomly sending payments to each other and randomly dropping packets.

> 3. The bitcoin system turns out to be socially useful and valuable, so
> that node operators feel that they are making a beneficial contribution
> to the world by their efforts (similar to the various "@Home" compute
> projects where people volunteer their compute resources for good causes).
>
> In this case it seems to me that simple altruism can suffice to keep the
> network running properly.

It's very attractive to the libertarian viewpoint if we can explain it properly. I'm better with code than with words though.

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-15 04:43:00 UTC - Original Email - View in Thread

I'll try and hurry up and release the sourcecode as soon as possible to serve as a reference to help clear up all these implementation questions.

Ray Dillinger (Bear) wrote:
> When a coin is spent, the buyer and seller digitally sign a (blinded)
> transaction record.

Only the buyer signs, and there's no blinding.

> If someone double spends, then the transaction record
> can be unblinded revealing the identity of the cheater.

Identities are not used, and there's no reliance on recourse. It's all prevention.

> This is done via a fairly standard cut-and-choose
> algorithm where the buyer responds to several challenges
> with secret shares

No challenges or secret shares. A basic transaction is just what you see in the figure in section 2. A signature (of the buyer) satisfying the public key of the previous transaction, and a new public key (of the seller) that must be satisfied to spend it the next time.

> They may also receive chains as long as the one they're trying to
> extend while they work, in which the last few "links" are links
> that are *not* in common with the chain on which they're working.
> These they ignore.

Right, if it's equal in length, ties are broken by keeping the earliest one received.

> If it contains a double spend, then they create a "transaction"
> which is a proof of double spending, add it to their pool A,
> broadcast it, and continue work.

There's no need for reporting of "proof of double spending" like that. If the same chain contains both spends, then the block is invalid and rejected.

Same if a block didn't have enough proof-of-work. That block is invalid and rejected. There's no need to circulate a report about it. Every node could see that and reject it before relaying it.

If there are two competing chains, each containing a different version of the same transaction, with one trying to give money to one person and the other trying to give the same money to someone else, resolving which of the spends is valid is what the whole proof-of-work chain is about.

We're not "on the lookout" for double spends to sound the alarm and catch the cheater. We merely adjudicate which one of the spends is valid. Receivers of transactions must wait a few blocks to make sure that resolution has had time to complete. Would be cheaters can try and simultaneously double-spend all they want, and all they accomplish is that within a few blocks, one of the spends becomes valid and the others become invalid. Any later double-spends are immediately rejected once there's already a spend in the main chain.

Even if an earlier spend wasn't in the chain yet, if it was already in all the nodes' pools, then the second spend would be turned away by all those nodes that already have the first spend.

> If the new chain is accepted, then they give up on adding their
> current link, dump all the transactions from pool L back into pool
> A (along with transactions they've received or created since
> starting work), eliminate from pool A those transaction records
> which are already part of a link in the new chain, and start work
> again trying to extend the new chain.

Right. They also refresh whenever a new transaction comes in, so L pretty much contains everything in A all the time.

> CPU-intensive digital signature algorithm to
> sign the chain including the new block L.

It's a Hashcash style SHA-256 proof-of-work (partial pre-image of zero), not a signature.

> Is there a mechanism to make sure that the "chain" does not consist
> solely of links added by just the 3 or 4 fastest nodes? 'Cause a
> broadcast transaction record could easily miss those 3 or 4 nodes
> and if it does, and those nodes continue to dominate the chain, the
> transaction might never get added.

If you're thinking of it as a CPU-intensive digital signing, then you may be thinking of a race to finish a long operation first and the fastest always winning.

The proof-of-work is a Hashcash style SHA-256 collision finding. It's a memoryless process where you do millions of hashes a second, with a small chance of finding one each time. The 3 or 4 fastest nodes' dominance would only be proportional to their share of the total CPU power. Anyone's chance of finding a solution at any time is proportional to their CPU power.

There will be transaction fees, so nodes will have an incentive to receive and include all the transactions they can. Nodes will eventually be compensated by transaction fees alone when the total coins created hits the pre-determined ceiling.

> Also, the work requirement for adding a link to the chain should
> vary (again exponentially) with the number of links added to that
> chain in the previous week, causing the rate of coin generation
> (and therefore inflation) to be strictly controlled.

Right.

> You need coin aggregation for this to scale. There needs to be
> a "provable" transaction where someone retires ten single coins
> and creates a new coin with denomination ten, etc.

Every transaction is one of these. Section 9, Combining and Splitting Value.

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-15 18:02:00 UTC - Original Email - View in Thread

Ray Dillinger wrote:
> One way to do this would be
> to have the person recieving the coin generate an asymmetric
> key pair, and then have half of it published with the
> transaction. In order to spend the coin later, s/he must
> demonstrate posession of the other half of the asymmetric
> key pair, probably by using it to sign the key provided by
> the new seller.

Right, it's ECC digital signatures. A new key pair is used for every
transaction.

It's not pseudonymous in the sense of nyms identifying people, but it
is at least a little pseudonymous in that the next action on a coin
can be identified as being from the owner of that coin.

> Mmmm. I don't know if I'm comfortable with that. You're saying
> there's no effort to identify and exclude nodes that don't
> cooperate? I suspect this will lead to trouble and possible DOS
> attacks.

There is no reliance on identifying anyone. As you've said, it's
futile and can be trivially defeated with sock puppets.

The credential that establishes someone as real is the ability to
supply CPU power.

> Until.... until what? How does anybody know when a transaction
> has become irrevocable? Is "a few" blocks three? Thirty? A
> hundred? Does it depend on the number of nodes? Is it logarithmic
> or linear in number of nodes?

Section 11 calculates the worst case under attack. Typically, 5 or
10 blocks is enough for that. If you're selling something that
doesn't merit a network-scale attack to steal it, in practice you
could cut it closer.

> But in the absence of identity, there's no downside to them
> if spends become invalid, if they've already received the
> goods they double-spent for (access to website, download,
> whatever). The merchants are left holding the bag with
> "invalid" coins, unless they wait that magical "few blocks"
> (and how can they know how many?) before treating the spender
> as having paid.
>
> The consumers won't do this if they spend their coin and it takes
> an hour to clear before they can do what they spent their coin on.
> The merchants won't do it if there's no way to charge back a
> customer when they find the that their coin is invalid because
> the customer has doublespent.

This is a version 2 problem that I believe can be solved fairly
satisfactorily for most applications.

The race is to spread your transaction on the network first. Think 6
degrees of freedom -- it spreads exponentially. It would only take
something like 2 minutes for a transaction to spread widely enough
that a competitor starting late would have little chance of grabbing
very many nodes before the first one is overtaking the whole network.
During those 2 minutes, the merchant's nodes can be watching for a
double-spent transaction. The double-spender would not be able to
blast his alternate transaction out to the world without the merchant
getting it, so he has to wait before starting.

If the real transaction reaches 90% and the double-spent tx reaches
10%, the double-spender only gets a 10% chance of not paying, and 90%
chance his money gets spent. For almost any type of goods, that's
not going to be worth it for the scammer.

Information based goods like access to website or downloads are
non-fencible. Nobody is going to be able to make a living off
stealing access to websites or downloads. They can go to the file
sharing networks to steal that. Most instant-access products aren't
going to have a huge incentive to steal.

If a merchant actually has a problem with theft, they can make the
customer wait 2 minutes, or wait for something in e-mail, which many
already do. If they really want to optimize, and it's a large
download, they could cancel the download in the middle if the
transaction comes back double-spent. If it's website access,
typically it wouldn't be a big deal to let the customer have access
for 5 minutes and then cut off access if it's rejected. Many such
sites have a free trial anyway.

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin P2P e-cash paper

2008-11-17 17:24:43 UTC - Original Email - View in Thread

James A. Donald wrote:
> > Fortunately, it's only necessary to keep a
> > pending-transaction pool for the current best branch.
>
> This requires that we know, that is to say an honest
> well behaved peer whose communications and data storage
> is working well knows, what the current best branch is -

I mean a node only needs the pending-tx pool for the best branch it
has. The branch that it currently thinks is the best branch.
That's the branch it'll be trying to make a block out of, which is
all it needs the pool for.

> > Broadcasts will probably be almost completely
> > reliable.
>
> Rather than assuming that each message arrives at least
> once, we have to make a mechanism such that the
> information arrives even though conveyed by messages
> that frequently fail to arrive.

I think I've got the peer networking broadcast mechanism covered.

Each node sends its neighbours an inventory list of hashes of the
new blocks and transactions it has. The neighbours request the
items they don't have yet. If the item never comes through after a
timeout, they request it from another neighbour that had it. Since
all or most of the neighbours should eventually have each item,
even if the coms get fumbled up with one, they can get it from any
of the others, trying one at a time.

The inventory-request-data scheme introduces a little latency, but
it ultimately helps speed more by keeping extra data blocks off the
transmit queues and conserving bandwidth.

> You have an outline
> and proposal for such a design, which is a big step
> forward, but the devil is in the little details.

I believe I've worked through all those little details over the
last year and a half while coding it, and there were a lot of them.
The functional details are not covered in the paper, but the
sourcecode is coming soon. I sent you the main files.
(available by request at the moment, full release soon)

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin v0.1 released

2009-01-08 19:27:40 UTC - Original Email - View in Thread

宣布第一版 Bitcoin，一种新的电子现金系统，使用点对点网络防止双重花费。它是完全去中心化，无服务器或中心权威体（ It's completely decentralized with no server or central authority ）。

See bitcoin.org for screenshots.

See bitcoin.org for screenshots.

Download link:
http://downloads.sourceforge.net/bitcoin/bitcoin-0.1.0.rar

Windows only for now. Open source C++ code is included.

- Unpack the files into a directory
- Run BITCOIN.EXE
- It automatically connects to other nodes

If you can keep a node running that accepts incoming connections,
you'll really be helping the network a lot. Port 8333 on your
firewall needs to be open to receive incoming connections.

The software is still alpha and experimental. There's no guarantee
the system's state won't have to be restarted at some point if it
becomes necessary, although I've done everything I can to build in
extensibility and versioning.

You can get coins by getting someone to send you some, or turn on
Options->Generate Coins to run a node and generate blocks. I made
the proof-of-work difficulty ridiculously easy to start with, so
for a little while in the beginning a typical PC will be able to
generate coins in just a few hours. It'll get a lot harder when
competition makes the automatic adjustment drive up the difficulty.
Generated coins must wait 120 blocks to mature before they can be
spent.

There are two ways to send money. If the recipient is online, you
can enter their IP address and it will connect, get a new public
key and send the transaction with comments. If the recipient is
not online, it is possible to send to their Bitcoin address, which
is a hash of their public key that they give you. They'll receive
the transaction the next time they connect and get the block it's
in. This method has the disadvantage that no comment information
is sent, and a bit of privacy may be lost if the address is used
multiple times, but it is a useful alternative if both users can't
be online at the same time or the recipient can't receive incoming
connections.

Total circulation will be 21,000,000 coins. It'll be distributed
to network nodes when they make blocks, with the amount cut in half
every 4 years.

first 4 years: 10,500,000 coins
next 4 years: 5,250,000 coins
next 4 years: 2,625,000 coins
next 4 years: 1,312,500 coins
etc...

When that runs out, the system can support transaction fees if
needed. It's based on open market competition, and there will
probably always be nodes willing to process transactions for free.

Satoshi Nakamoto

---------------------------------------------------------------------

bitcoin-list

[bitcoin-list] Bitcoin v0.1.2 now available

2009-01-11 22:32:18 UTC - Original Email - View in Thread

Bitcoin v0.1.2 is now available for download.

See http://www.bitcoin.org for the download link.

All the problems I've been finding are in the code that
automatically finds and connects to other nodes, since I wasn't
able to test it in the wild until now. There are many more ways
for connections to get screwed up on the real Internet.

Bugs fixed:
- Fixed various problems that were making it hard for new nodes to
see other nodes to connect to.
- If you're behind a firewall, it could only receive one
connection, and the second connection would constantly disconnect
and reconnect.

These problems are kind of screwing up the network and will get
worse as more users arrive, so please make sure to upgrade.

Satoshi Nakamoto

---------------------------------------------------------------------

bitcoin-list

[bitcoin-list] Bitcoin v0.1.3

2009-01-12 22:48:23 UTC - Original Email - View in Thread

It looks like we're through with the worst of the Internet
connection issues. 0.1.3 fixed a problem where your node's
communications could go dead after a while. The network is
running much more smoothly now with this version.

If you've successfully generated a block, you've seen it has a
maturation countdown before you can spend it. Once it matures,
the Credit column will change from 0.00 to 50.00. For a block to
be valid, it has to be broadcasted to the network and get into the
block chain, which is why Generate does not run if you're not
connected. If you generated a block without being connected, the
network wouldn't know about it and would continue building the
chain without it, leaving it behind, and the maturation countdown
would change to "(not accepted)" when your node sees that it
wasn't used. If you subtract 1 from the status column, that's how
many blocks have been chained after yours.

Satoshi Nakamoto

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin v0.1 released

2009-01-16 16:03:14 UTC - Original Email - View in Thread

> Dustin D. Trammell wrote:
> > Satoshi Nakamoto wrote:
> > You know, I think there were a lot more people interested in the 90's,
> > but after more than a decade of failed Trusted Third Party based systems
> > (Digicash, etc), they see it as a lost cause. I hope they can make the
> > distinction that this is the first time I know of that we're trying a
> > non-trust-based system.
>
> Yea, that was the primary feature that caught my eye. The real trick
> will be to get people to actually value the BitCoins so that they become
> currency.

I would be surprised if 10 years from now we're not using
electronic currency in some way, now that we know a way to do it
that won't inevitably get dumbed down when the trusted third party
gets cold feet.

It could get started in a narrow niche like reward points,
donation tokens, currency for a game or micropayments for adult
sites. Initially it can be used in proof-of-work applications
for services that could almost be free but not quite.

It can already be used for pay-to-send e-mail. The send dialog is
resizeable and you can enter as long of a message as you like.
It's sent directly when it connects. The recipient doubleclicks
on the transaction to see the full message. If someone famous is
getting more e-mail than they can read, but would still like to
have a way for fans to contact them, they could set up Bitcoin and
give out the IP address on their website. "Send X bitcoins to my
priority hotline at this IP and I'll read the message personally."

Subscription sites that need some extra proof-of-work for their
free trial so it doesn't cannibalize subscriptions could charge
bitcoins for the trial.

It might make sense just to get some in case it catches on. If
enough people think the same way, that becomes a self fulfilling
prophecy. Once it gets bootstrapped, there are so many
applications if you could effortlessly pay a few cents to a
website as easily as dropping coins in a vending machine.

Satoshi Nakamoto
http://www.bitcoin.org

---------------------------------------------------------------------

Cryptography Mailing List

Bitcoin v0.1 released

2009-01-25 15:47:10 UTC - Original Email - View in Thread

> > * Spammer botnets could burn through pay-per-send email filters
> > trivially
> If POW tokens do become useful, and especially if they become money,
> machines will no longer sit idle. Users will expect their computers to
> be earning them money (assuming the reward is greater than the cost to
> operate). A computer whose earnings are being stolen by a botnet will
> be more noticeable to its owner than is the case today, hence we might
> expect that in that world, users will work harder to maintain their
> computers and clean them of botnet infestations.

Another factor that would mitigate spam if POW tokens have value:
there would be a profit motive for people to set up massive
quantities of fake e-mail accounts to harvest POW tokens from
spam. They'd essentially be reverse-spamming the spammers with
automated mailboxes that collect their POW and don't read the
message. The ratio of fake mailboxes to real people could become
too high for spam to be cost effective.

The process has the potential to establish the POW token's value
in the first place, since spammers that don't have a botnet could
buy tokens from harvesters. While the buying back would
temporarily let more spam through, it would only hasten the
self-defeating cycle leading to too many harvesters exploiting the
spammers.

Interestingly, one of the e-gold systems already has a form of
spam called "dusting". Spammers send a tiny amount of gold dust
in order to put a spam message in the transaction's comment field.
If the system let users configure the minimum payment they're
willing to receive, or at least the minimum that can have a
message with it, users could set how much they're willing to get
paid to receive spam.

Satoshi Nakamoto

---------------------------------------------------------------------

bitcoin-list

Re: [bitcoin-list] Bitcoin v0.1.5 released

2009-03-04 16:59:12 UTC - Original Email - View in Thread

Hal Finney wrote:
> That sounds good. I'd also like to be able to run multiple coin/block
> generators on multiple machines, all behind a single NAT address. I
> haven't tried this yet so I don't know if it works on the current
> software.

> BTW I don't remember if we talked about this, but the other day some
> people were mentioning secure timestamping. You want to be able to
> prove that a certain document existed at a certain time in the past.
> Seems to me that bitcoin's stack of blocks would be perfect for this.

> > > Later I want to add interfaces to make it really easy to integrate
> > > into websites from any server side language.
>
> Right, and I'd like to see more of a library interface that could be
> called from programming or scripting languages, on the client side as
> well.

Liberty Standard wrote:
> Do you Windows users experience occasional Bitcoin crashes?
> Lately Bitcoin running in wine-1.0.1 has been crashing frequently. I was
> just wondering whether this is a Wine issue or a Bitcoin issue.

> The following four lines print from the terminal when I start Bitcoin.
> fixme:toolhelp:CreateToolhelp32Snapshot Unimplemented: heap list snapshot
> fixme:toolhelp:Heap32ListFirst : stub
> fixme:toolhelp:CreateToolhelp32Snapshot Unimplemented: heap list snapshot
> fixme:toolhelp:Heap32ListFirst : stub

> I previously wasn't starting Bitcoin from the terminal, so I don't know what
> gets printed out when it crashes, but I'll reply with the results the next
> time it crashes.
>
> While Bitcoin first downloads previously completed blocks, the file
> debug.log grows grows to 17.4 MB and then stops growing. I imagine it will
> continue to grow as more bitcoins are completed.