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 演化论
【天下大义,当混为一】(下)算力战

可分叉性的意义

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

零知识证明与区块链扩容 Zero Knowledge && Blockchain Scalability

年前我报名了 03 月 25 日 在台北举办的 SITCON,正好看到 Changwu 分享 Vitalik 03 月 15 日会来 Taipei Ethereum Meetup 的活动,于是就决定提前动身。Vitalik 当天在台北的行程也安排的很满,一共会出席三个活动 [1]。但根据我以往的经验,最重要的活动当然是晚上的 Taipei Ethereum Meetup,每次 Vitalik 来 Taipei 都会带来一些新的 idea[2],这次果然也是如此。

zKSnarks 和 Layer2 我们都不陌生,但是 zKSnarks 可以用来做扩容[3],很多人包括我就是第一次听说了。再把这个结合进 Layer2,知道的人恐怕就更少了。

在这次的演讲中,Vitalik 首次提出了自己对这一问题的一系列想法,以及其 Layer2 中数据可用性问题(Data Availability Problem)的联系。下面是这次演讲相关的资料,其中 Trenton Van Epps 在 Medium 上忠实的记录了这次 Tech Talk 的 Transcript,并且包含了许多相关的资料和历史记录,强烈推荐大家阅读。

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

Created with Highstock 6.0.7Market CapPrice (USD)Price (BTC)24h VolChart context menuLog ScaleLinear ScaleBitcoin Charts25. Mar19. Mar20. Mar21. Mar22. Mar23. Mar24. MarZoom1d7d1m3m1yYTDALLFromMar 18, 2019ToMar 25, 2019Market CapPrice (USD)Price (BTC)24h Vol201420162018$72B$69B$70B$71B$73B$4,000.00$4,025.00$4,050.00$4,075.00$4,100.00012BMonday, Mar 25 2019, 01:14:00 UTC+08:00 Market Cap: 70,835,529,745 USD Price (USD): 4,022.99 24h Vol: 8,928,768,737 USDcoinmarketcap.com