Algorand丨图灵奖得主Micali算法创新,解决“不可能三角”难题

2017年12月比特币创出19,875美元新高后一路走低,2018一个回调年,熊市凡事都艰难,可实力团队还是香喷喷。今年大热项目Algorand就在二月份风险融资了400万美元,投资方为硅谷知名风投Pillar和联合广场USV。为何被追捧?牛掰的密码学家加上共识算法的创新。

Algorand项目的创始人是麻省理工学院MIT教授希尔维奥·米卡利Silvio Micali,因在密码学和复杂理论领域的贡献获得2012年图灵奖(号称“计算机界的诺贝尔奖”)。

Silvio Micali于1954年意大利出生,1978年获得罗马Sapienza大学数学本科学位,1982年在加州大学伯克利分校获得数学博士学位。职业生涯比较简单,1982-1983年在多伦多大学任博士后研究员,1983年7月加入麻省理工学院任教至今。但所做贡献和所获荣誉却不简单,1993年与团队一同获得哥德尔理论计算机科学奖,2003年获得美国艺术与科学院院士,2004年获得密码学奖,2007年获得美国国家科学院和国家工程院双院士,同期成为国际密码学研究协会IACR研究员,2012年获得图灵奖以及加州大学伯克利分校计算机科学与工程杰出校友奖。

Silvio Micali从事的工作是研究密码学的数学基础,进而推动计算理论。Micali与Goldwasser(长期合作者,图灵奖的共同获奖者)合作创建的数学结构,包括隐私概念,伪随机性,交互式证据,零知识证明等等。(PS:零知识证明的共识机制已被隐私币和大零币采用。)

最近几年,Micalii将注意力转到博弈论,致力于开发更强大的机制,思考设计共谋和隐私。 这次Algorand区块链项目就是对这方面研究的实践。

Micali提出了新的共识算法BA★,希望能解决“去中心化”、“可扩展性”和“安全性”这三者无法同时满足的难题,号称解决“不可能三角”问题。这个新算法,是基于实用拜占庭协议PBFT的改进,特别强调区块打包者的随机产生,引入“可验证随机函数VRF”。

可验证随机函数VRF,相当于一个抽签算法,改变区块打包的方式,不再需要通过矿工算力竞争。随机抽取节点打包,中奖结果和区块同时全网广播,导致作恶节点无法提前发起攻击,篡改交易记录。

每个节点会在本地计算机上运行一个抽签程序,中奖的概率跟所持代币数量成正比,跟账户数量无关,代币不需要抵押和锁定。

备选节点会得到一个凭证,凭证和区块会一起广播出去,其他节点使用该节点的一次性公钥加上凭证可以算出随机数,随机数最小者则为中奖节点。抽签算法计算量很小,毫秒级别广播,基本不存在延时,中奖节点不存在被贿赂的情况,保证安全性。这里,区块打包节点称为领导者。

同理,网络中随机选取“验证者”,采用三分之二节点有效签名的规则,一轮轮验证消息直至确认区块。整个过程大概是,在收到备选领导节点生产的区块后,验证节点第一步验证备选区块,第二步收集验证结果,第三步进行0/1投票(即二元拜占庭协议),最后完成区块签名生效。这几个步骤,每次验证者都不一样,验证者只进行一次性工作,这样能有效防止验证权力集中在某些节点手中,避免作恶者腐化这些节点来攻击区块链。

从上述可知,Algorand的区块产生机制,采用的是DPOS和BFT相结合,节点分类,分层共识的方式。 Micali证明了BA★满足拜占庭协议的要求:

  1. (共识性)最后一批诚实“验证者”输出的区块是相同的;
  2. (一致性)如果一开始“验证者”收到的备选区块都是v,那么最终输出也是v。

而Algorand被设计的目标是满足如下的要求:

1.能耗低,不管系统有多少用户,大约每1500名用户中只有1名会被系统抽中执行长达几秒的计算。
2.民主化,不会出现类似比特币系统的“矿工”群体。
3.出现分叉的概率极低,无需等待六个区块确认交易。
4.可拓展性好。

当然,Algorand并非完美无瑕,Micali设计经济模型时没有引入激励机制,甚至表示不需要代币。对此很多质疑声,没有代币奖励怎么吸引更多用户参与?节点用户打包区块的动力何在?Micali教授面对质疑声在9月杭州见面会上回复,后续将提出新的设计思路。同时,他也曾表示过“激励机制是最难的”,他的解释是:当系统加入激励机制,人们就会尝试利用激励机制赚钱,会想出各种意想不到的方法钻空子。中本聪肯定不会想到POW会导致出现规模化的挖矿产业。

目前,项目还属于论文阶段,没有实际的代码和具体的开发进展。但是依据Micali的描绘,我们似乎看到了未来一个去中心化、不可篡改、无法屏蔽的公共账本,一个民主化、可进化、运转高效的网络基础设施。对未来已来的新技术,既期待又兴奋,眼前的熊市遮挡不住未来的美好。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,133评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,682评论 3 390
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,784评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,508评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,603评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,607评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,604评论 3 415
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,359评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,805评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,121评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,280评论 1 344
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,959评论 5 339
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,588评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,206评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,442评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,193评论 2 367
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,144评论 2 352