为什么 Facebook 的 GlobalCoin 如此重要

为什么 GlobalCoin 如此重要,因为它做了很多币圈人想做但暂时还做不到的事。

进入 2019 以来,我们似乎已经习惯了周围越来越多的知名互联网公司开始 —— 已经不是布局了 —— 而是跑步进入区块链时代。从蚂蚁金服的区块链创新大赛1,腾讯的《一起来捉妖》2,再到亚马逊的 Amazon Managed Blockchain3,Microsoft 的 ION4。一直到上周,Chainlink 宣布与 Google 合作,将 BigQuery 带进以太坊5

但毋庸置疑的是,在所有这些的事件中,最具有深远影响的还是 Facebook 的 GlobalCoin,这方面 昨天孟岩老师的文章 已经做了非常好的讨论,这里我会稍微进行一些补充。
(顺便一提,今天还有 Facebook Hackercup 资格赛。)

ゆっくり読んでください …

我的区块链价值观

原文发表在我的独立博客
链闻有授权转载

上文说到,这周末要去北京打 TCO Onsite,考虑到有越来越多的 OIer/ACMer 已经开始参与或者正在考虑参与到 Blockchain Industry 之中(IOST、Tezos、Conflux、etcs),感觉有必要写篇文章以备不时之需。顺便也给最近这段时间对行业的理解做个阶段性总结。

归纳的态度 Inductive Attitude

区块链是一个很多学科交叉汇集的地方,她的快速演化使得我们必须要以谦卑的姿态虚心的更新着自己的认知。按照波利亚的话说,我们应该抱有归纳的态度1来理解正在发生的事情。

这其中自然也包括货币化与自由市场。亚当·斯密(Adam Smith)使用 看不见的手(Invisible Hand)来隐喻其中所隐含的秩序。虽然她 偶尔也会失效,但是我们今天绝大部分的世界仍旧依照着她的指引运行并演化着,有兴趣的读者可以去读《致命的自负》,这里不再赘述。

所以当这个圈子隔三差五出现,某某是不是骗子,某某盘是不是骗局2这样的讨论时,我应该抛给你的是一个概率分布 —— 我分别是有百分之多少的概率认为它是有百分之多少的骗局(革命)成分的。

作为裁判的自由市场 Free market as a Judgementor

而最后判断我们的猜想正确与否的唯一 Criteria,就是币价和市值。资金盘之所以为资金盘,就是她有一天会崩盘。显然我们应该参考所有人用真金白银做出的判断。下面这副颇为有趣的名为「区块链又革命了」的迷因(Meme)之所以能够广为流传,就是反映了上面所说的观点。

最近有人提议 港人进行大规模的换汇冲击联系汇率以抵抗某条例,如果真的能够被执行,那其中所蕴含的力量将会是十分惊人的。咳咳,Out of topic 了。3

商业能够创造财富,劳动则未必。人们通过交易实际上将自己所掌握的信息通过自由市场广播出去,市场则会给予正确的信息予以恰当的激励。自由市场足够的复杂,被教做人的故事屡见不鲜4。虽然她将每个 individual 所掌握的零零碎碎的信息汇集成一个 indicator,但这个 indicator 同时也会包含诸如市场的情绪、假新闻、贪婪或恐惧、Hype or Fear 等噪音。仅仅通过市场去寻求真理显然会落入缘木求鱼的圈套,但市场至少是一个好的裁判,币价不会说谎,她诚实的反应了群体5所掌握的所有信息。而当我们动态的审视这个指标变化的过程时,我们有理由相信自己已经取得了某些进展。

当我们的知识不足以让我们进行判断时,不妨求助于集体的智慧,以自由市场来作为我们的 Single Source of Truth。

Right. Otherwise we couldn’t have a finite limit of 21 million coins, because there would always need to be some minimum reward for generating. In a few decades when the reward gets too small, the transaction fee will become the main compensation for mining nodes. I’m sure that in 20 years there will either be very large transaction volume or no volume.
—— Either… Or!, 21 Wise and Funny Bitcoin Quotes by Satoshi Nakamoto

所以就连中本聪自己也不能判断 Bitcoin 究竟是不是革命,但自由市场可以。

ゆっくり読んでください …

GCJ 2019 Round3 B

Problem B. Pancake Pyramid

Brief Description

给定长度为 n 的序列 h[i]。
每次你可以选择一段连续子序列 [l, r],你可以给其中某些项执行 +1 操作,使得操作后形成一个金字塔形状(先递增再递减)。
问遍历所有的子序列,总操作次数最少是多少。

Analysis

相同元素可能会带来重复计数,我们统一先认为相同的元素出现时,左边的更大。

考虑暴力做法。注意到我们这里 只有 +1 操作,所以可以直接贪心。
每次枚举区间,设:
– M[l][r] 表示 [l, r] 区间最大的数的位置。
– L[l][r] 表示把 [l, r] 这个区间处理成递增序列的最小代价。
– R[l][r] 表示把 [l, r] 这个区间处理成递减序列的最小代价。

那么我们枚举所有的区间,统计所有 L[l][m] + R[m][r] 就是答案,可以预处理这些数组,复杂度 O(n2),可以过小数据。

考虑大数据,其实题目里已经疯狂暗示你了要用单调栈(stack)。。。
回忆 POJ 2559. Largest Rectangle in a Histogram

我们发现之前是要处理出,以 h[i] 为最低点,左右两边分别可以延伸多远。
这里恰好是求,以 h[i] 为最高点,左右两边分别可以延伸多远,假设就是 Dl[i] 和 Dr[i]。
这样唯一不同的是,我们还需要一个累计代价数组 Sl[i] 和 Sr[i],分别表示以 h[i] 为最高点,往左和往右累计的代价。
因为最后答案就是:
$$\Sigma_{i=1}^n Dl[i] * Sr[i] + Dr[i] * Sl[i]$$

我们可以在维护单调栈的过程中,顺路求 Sl 出 Sr。不放考察从左往右扫描求 Dl 的过程。
设当前扫描到位置 i,将要被弹出的栈顶元素为 sp,这个位置右边一直到 i 这个区间现在都至少需要是 h[sp] 的高度才符合要求。
记这个代价为小写的 sl,我们预处理部分和后可以 O(1) 的求出 sl。记新的栈顶元素的位置与刚才被我们弹出的栈顶元素的位置之间的距离为 sp – s.top(),
sl 需要被统计 sp – s.top() 次。最后加上这个区间本身的代价 Sl[sp]。

stack<int> s; s.push(0); REP_1(i, n) {
    Sl[i] = 0;
    while (h[i] > h[s.top()]) {
        int sp = s.top(); s.pop();
        Int sl = Int(h[sp]) * (i-sp-1) - (hh[i-1]-hh[sp]);
        Sl[i] += sl * (sp - s.top()) + Sl[sp];
    }
    Dl[i] = i - s.top();
    s.push(i);
}

TCO 2019 2B

Beijing Onsite 的热身,不过居然晋级了,下一场还是好好打(受虐)一下吧。。。

250 MedianFaking

Brief Description

给定 n 个人,每个人有 m 个测量结果。取所有人所有测量结果的中位数(偶数时下去整)为最终结果。
已知测量结果应该是 goal,问至少修改几个测量结果可以使得结果恰好为 goal,在这种情况下最少需要参与修改的人数又是多少。

Analysis

如果要让结果恰好为 goal,那么比 goal 小的数和比 goal 大的数都不能超过一半,显然这两边只会有一边不符合。
于是我们只要关心这一边需要修改几个数就好了,并且现在只需要考虑一边,第二问只要统计出每个人可以带来的贡献,排序贪心即可。

500 DivisorSequences

Brief Description

给定 n,我们将 n 拆分成若干个整数相加的形式:n = a1 + a2 + … + am。
要求 a 序列严格递增且 a_i 整除 a_{i+1},问 m 最大可以是多少。

Analysis

观察 15 = 1 + 2 + 4 + 8…
我们发现如果把 1 去掉的话,有 14 = 2(1 + 2 + 4)…
这样我们就发现了一个子问题!
定义 f(n) 表示将 n 分解,并且第一个数是 1 的方案数,每次减去 1 后枚举约数递归即可。那么实际的答案可能第一个数不为 1,所以开始再额外枚举一次约数就好。
复杂度虽然不太容易估计,但貌似不记忆化也能过。

1000 SlightlyBigger

Brief Description

Alice 和 Bob 报数,从 1 到 oo,目标是比对方报的数只大一点。
– 如果恰好差小于等于 maxDiff,那么大的一方获胜,并得到 ifNear 分。
– 否则,小的一方获胜,并得到 ifFar 分。

双方都采取最优策略时,问 Alice 报的数恰好为 query 的概率。
(ifNear < ifFar <= 2×ifNear)

Analysis

第一眼感觉这个题很神,看了一下大家后来都是高斯消元做的。但是不知道怎么列方程。后来请教了一下毕克老师,毕老师说其实这个问题跟剪刀石头布是一样的,就你想象一个剪刀石头布游戏,然后给你一个收益矩阵。
对方把自己的策略的概率分布向量已经告诉你了,在最优情况下,你发现你即便知道这个向量也并不能让你取得任何优势。
这就是传说中的 纳什均衡,于是只要设表示报 x_i 的概率,根据上面这些关系,列出线性方程组,高斯消元即可。

纳什均衡虽然提供了 n 组方程,但是 rank 似乎是 n-1 的,最后别忘了加上所有概率分布之和等于 1。
可以预计答案不会很大,可以带极限数据跑一下看看边界。

比特币分叉史(WIP)

比特币分叉史 (WIP)

https://hackmd.io/@E-5gxTGiSByBOKpvsaKa_g/SyGtjw_qN/edit

想要取得近未来世界之一瞥,必须认识加密货币,想要认识加密货币,一定要理解比特币。2017 年夏天我在 Google Shanghai Cryptocurrency Study Group 里分享过 一篇介绍比特币历史的 Slide,但是现在回顾起来,当时还是太年轻了。原因是我忽视了比特币社区内部那些反对派的声音。

前几天 Vitalik 撰文论及言论自由时,就讨论了最近的币安下架 BSV 事件与当年 /r/bitcoin 上对大区块的言论审查之间的联系。这篇文章试图带你回顾比特币分叉的历史。想对比特币分叉的历史有一个清晰直观的鸟瞰,可以看 Bitcoin Magazine 最近仿照 地铁地图 制作的 比特币分叉地图

立场与偏见

This perception demonstration also shows how powerfully our paradigms affect the way we interact with other people. As clearly and objectively as we think we see things, we begin to realize that others see them differently from their own apparently equally clear and objective point of view. “Where we stand depends on where we sit.”
—— The 7 habits of highly effective people: restoring the character ethic, Stephen R. Covey

值得一提的是我们在阅读下面的观点 —— 以及日后形成自己的观点时 —— 都需要了解这些观点背后的立场。立场有时会加剧我们的偏见,从而使得我们远离真相。一个例子是,ConsenSys 在 2018 年关于 EOS 的报告,普遍被 EOS 社区认为是偏见并带有敌意的。而对于 Bitcoin 社区,因为大家都会自称自己继承了 Bitcoin 的正统,所以尤其要区分这些频道之后的立场。最著名的例子可能要数 名为 Bitcoin 的 Twitter 账号,这是一个明显带有 BCH 倾向的频道1。这种偏见普遍存在,在这个 后真相时代,当你看到你想要看到、愿意相信的消息时,就要提高警惕

比特币的迭代与治理

Social progress means a checking of the cosmic process at every step and the substitution for it of another, which may be called the ethical process; the end of which is not the survival of those who may happen to be the fittest, in respect of the whole of the conditions which obtain, but of those who are ethically the best.
—— Evolution and Ethics, Thomas Henry Huxley

关于比特币的简短历史和年表,包括可以参考 比特币十年回顾 —— 什么是比特币,她会成为什么。关于比特币更早期历史,可以看 Nicholas Mross 2014 年拍摄的纪录片 —— The Rise and Rise of Bitcoin,第一手的资料,可以去考古 The Cryptography and Cryptography Policy Mailing List 以及 Bitcointalk 上 Satoshi Nakamoto 的发言。更多纪录片可以搜 这里

早期的比特币源代码 托管于 SourceForge 的服务器之上,开发者用电邮跟中本聪交换代码补丁。随后 Sirius 改用 Subversion 进行代码管理。2011 年,比特币项目从 SourceForge 迁移到 GitHub,2014 年,比特币项目更名「Bitcoin Core」(比特币核心),2015 年 SourceForge 的代码仓库逐渐被弃用。

比特币白皮书先于比特币代码诞生,比特币代码最早是中本聪用来验证,比特币白皮书中所描述的 P2P 电子货币能否真正成立的 实验。超出绝大多数人的意料,她成功了。早期的比特币代码质量并不很高,只有 Windows 客户端,也没有协作和开发协议的标准。当 有人向中本聪报告 了一个比特币代码库会引起双花攻击的漏洞时,中本聪立即对比特币协议进行了更新,并告诉网络上的每个人升级他们的客户端,而没有解释原因。这就是已知的第一次比特币分叉。

在软件开发中,一个项目最少失去多少关键成员,会使得项目陷入混乱、瘫痪的状态,被称之为 巴士系数。让一个 Payment 系统建立在一个巴士系数为 1 的工程之上显然是极其危险的,这也是中本聪从比特币项目中退出的一个原因。

进化才能生存。比特币改进提案(BIPs)为贡献者们提供了标准化流程,以便为协议提出新想法、测试这些想法以及对其进行同行评审(Peer Review)。这个系统旨在允许对协议进行持续的创新,同时确保通过共识和协作来实现这些改进。

BIPs 源自 Python 改进提案(PIPs)。最早由 Amir Taaki 2011 在 BIP 0001 中提出并在 BIP 0002 中由 Luke Dash Jr. 扩展并改进。BIP 的目标是给所有人参与到改进比特币协议,并在实际动手编写代码之前审查提案的安全性,达成初步的共识(Rough Consensus)。这一协作的标准也被推广到了其他区块链项目之中,例如以太坊改进提案(EIPs)。

如果算上中本聪,Bitcoin Core 目前有过三任领导班子,他们分别是:

关于我们从外部观察 Bitcoin Core 的人来说,一个常见的误解是认为 Core 团队是一个大一统的实体。这是错误的,事实上在 Bitcoin Core 的贡献者之间 也会有分歧,而且就算那些最多产的贡献者,也写了很多代码,从没有合并入核心项目。

关于 Bitcoin Core 可以阅读下面的文章:

关于比特币改进协议(BIP)如何工作,可以参考:
Bitcoin Governance: What are BIPs and how do they work? | 中译,比特币的治理:什么是比特币改进协议以及它们如何工作

当然,对于比特币的治理模式,也有人不以为然。反对的声音可参考:
Bitcoin 的权力皇冠 —— CORE

扩容路线之争

Consensus is the path, not the destination.
—— On Consensus and Humming in the IETF

比特币的分叉源自扩容,准确的说,是扩容路线之争。

扩容是比特币能够真正成为世界货币,达到 Massive Adoption 的必由之路。但如何扩容,按照什么样的路线实施,却成了悬而未决的问题。扩容之争的复杂之处在于,它涉及到长期与短期的考量、风险与效率的权衡,甚至理性与情感的纠结。这不仅仅是一个技术问题,还是一个经济问题、政治问题,甚至意识形态问题。全面系统地考察和分析不是一件容易的事情。

关于扩容的讨论事实上伴随着比特币的整个生命周期。早在 2010 年,关于 中本聪与 BM 的那段名对话

If you don’t believe me or don’t get it, I don’t have time to try to convince you, sorry.

出现的上下文就是扩容。其他币也会遇到扩容问题,但很少会像比特币这样产生如此大的分歧。新的项目经常会宣称他们自己解决了三难悖论。

从 2015 年开始,每年比特币都会举办 扩容工作坊(Scaling Bitcoin Workshops),来自世界各地的比特币爱好者会聚集一堂,讨论比特币扩容的问题。

比特币的分叉

让我们提纲挈领,忽略那些早期的紧急修复,实验性质的分叉以及各种「空投」,比特币历史上实质性的分叉发生过两次。分别是 2017 年 Bitcoin Core 与 Bitcoin Cash 的分叉,以及 2018 年 Bitcoin Cash 与 Bitcoin Satoshi Version 的分叉。

自由分叉(Permissionless Forking)原本就是 自由软件的重要组成部分,但在 Bitcoin 这一开源软件中,自由分叉的意义却显得格外的不同。一个原因是,比特币本身是具有实际利益输送的项目。矿工,用户,钱包,开发者,布道者,交易所… 众多的角色参与其中,使得这一问题变得更加复杂。比特币的使命是成为 A Peer-to-Peer Electronic Cash System,给世界提供另一种可能,但是对于 P2P Electronic Cash System 的实现路径上,各方的观点却可能又有所不同。而货币的成功与否,很大程度是建立在系统的网络效应之上,所以各个参与方对于分叉比特币之一行为都格外谨慎和严格,也只有到参与的双方的利益无法调和时,分叉才会成为最后的选项。

Bitcoin Core 与 Bitcoin Cash 分叉

The current system where every user is a network node is not the intended configuration for large scale. That would be like every Usenet user runs their own NNTP server. The design supports letting users just be users. The more burden it is to run a node, the fewer nodes there will be. Those few nodes will be big server farms. The rest will be client nodes that only do transactions and don’t generate.

和 BM 的对话中 中本聪提到比特币本身的设计就不是为了扩容而存在的,这就像是要求每个阅读新闻的用户自己都起一个网络新闻传播协议(NNTP)的服务器差不多。接着中本聪提到自己在 自动贩卖机 的贴文中,已经讨论了自己所设想的扩容方案 —— 支付通道。

UASF 只是这次分叉的导火索,实际上围绕着扩容的争议,在比特币社区的内部演化成了长达四年的争吵、敌视,才最终导致社区一分为二。

香港共识

纽约共识

硬分叉

余波 —— Initial Fork Offer

Bitcoin Cash 与 Bitcoin Satoshi Version 分叉

这里我推荐下面几篇文章:
【天下大义,当混为一】(上)谈 Hash Vote & Market Vote
【天下大义,当混为一】(中)稳定论 vs 演化论
【天下大义,当混为一】(下)算力战

可分叉性的意义

可分叉是开源软件的重要特性,因而很少有商用软件或者可盈利的软件选择开源,因为允许分叉意味着任何人都可以创建这一软件的副本,从而侵占原本开发团队的市场份额。例如,很少有游戏公司,将自己正在运营中游戏选择开源。从这个角度看,比特币不仅仅创造出了一种电子货币,也创造出了一种文化,一个标准,一个关于协作的未来的标准。