论比特币“大O扩容”

在计算机科学中，有一种东西叫做“大O符号”（念“oh”，不念零）。它是算法在面临更大的问题需要去解决时，描述它表现的一种方式。

在比特币区块扩容争论中，很多人声称“比特币O(n^2)的扩展方式是不可行的”，N平方的扩容是不可持续的，如果是双倍N，那你需要的资源就是四倍（内存或CPU）。

在蒙特利尔的比特币扩展性大会上，我有幸和一些与会者进行了交谈，我问他们究竟在谈论些什么。结果发现，他们是在谈论一些不同的东西。

其中一些人是在谈论梅特卡夫定律（“电信网络的价值，与联网的用户数的平方成正比”）， 把它应用到比特币交易中时，假设有N个人会使用比特币网络，那么他们将产生N^2笔交易。这是愚蠢的，因为即使所有人在理论上会使用比特币和其他人进行交 易，他们也不会这样去做。在过去五年里，我可能已经大约和100个人或公司进行了比特币交易；交易的需求，它是随着使用它的人，而线性增长的。

再有就是，假设交易数“n”随着时间的推移而增长，整个交易历史会增长O(n^2)（见Patrick Strateman最近的谈话）。这样的增长速度快于CPU power或硬盘空间的增长，最终将没有新人会去验证整个区块链。

如果你出于信念，成为一个真正的比特人（Bitcoiner），是必须要从创始区块开始来验证整个区块链，这其实是一个问题。这是一个不必要的狭隘观点，在我看来，我觉得人们能够自由地进行信任／便利的交易。例如，一个新用户，是可以通过获取区块链账本最近一些区块（取UTXO集） 快照的方式，那样就可以避免下载整个历史区块链。这种方式要比获取整个区块链历史，更快更方便，并且它的安全性几乎是完美的，即使你搞到的是一个坏了的账 本副本，出现最为糟糕的事情，也就是账本中会出现多余的帐目（可能会是攻击者赠予你100万比特币，但实际上它们是并不存在的），又或者帐本中会丢失一些 帐目。如果出现额外的帐目，那么攻击者可以向您发送无效的交易，但这些交易永远都不会得到确认。他们可以通过发送你一笔交易，并发送给网络其余人一笔双花 交易，其实两者是同样的事情，双花交易并不会被确认。

如果缺失了帐目，那么你的钱包可能会出现一种情况，认为一笔有效的交易将是无效的。一旦交易在区块链被验证了，它会发现它的错误，并通过一个更为可靠的对等节点来恢复账本。

最后，还有一个的争论：

假设我们有’n'个用户，其中固定比例（比如1％）的用户会运行完整节点，并且每个用户每天生成一定数量的交易……然后由所有完整节点所做的总审定工作是 O(n^2)。（事实上，应该是O((n/100)^2)，但持续性因素在大O符号规则里是被忽略的）

这种说法有两件事是错误的：

首先，随着网络的发展，假设恒定比例的用户会运行完整节点, 这可能是不正确的。事实情况很可能是，越来越多比重的人，会选择运行部分验证节点。在未来，可能会出现10亿人使用比特币，而运行完整节点的人却仅有数万 人的情况，而不是预计中的千万人。而那，将是比特币一个光明、成功、去中心化并且安全的未来。

第二点不正确的是，虽然整个网络可能确实要执行O(n^2)笔验证工作， 但n个个体节点中的每一个，可能只会执行O(n) 笔验证工作，这是一个重要的指标，因为每一个个体并不关心网络其余节点会做多少验证工作，他们只关心自己的电脑必须要做多少的工作。

－－－－

声明：此文出于传递更多信息之目的，并不意味着赞同其观点或证实其描述。本网站所提供的信息，只供参考之用。