Tendermint plus 1

   我们首先从论文的角度来深度解析下此类BFT-POS算法,这是一个很有意思的提法。虽然在Tendermint自己的官网上写到自己是BFT算法,但业内认为是一个带有BFT特性的POS算法,到底是如何,所有现在从论文的角度来解析。
   《最新的gossip基于BFT共识》
   一句话介绍一下Tendermint协议:其通过依赖节点间的点对点gossip协议,对该主题的经典学术工作进行了现代化,并简化了BFT算法的设计。
   先从它的模型说起:
   A.模型
   网络层是gossip协议,所有节点不是对等连接,这点与比特币类似。
   半同步系统模型:如果一个正确进程P在t时刻收到一些消息m,所有正确的进程将在max{t, GST } + ∆之前收到m。

   B.状态机器复制
   复制协调。所有非故障副本接受和处理一样的请求序列。仅仅只有被客户端提出的请求被执行,Tendermint进程将询问服务是否请求合法的并仅处理合法的请求。

   C.共识算法
    •协议:没有两个正确的进程决定不同的值。
    •终止:所有正确的进程最终决定一个值。
    •有效性:决定的值是有效的,即它满足表示为valid()的预定义谓词。

   第三部分是具体算法
   1.提议者在每轮的映射对于所有节点来说都是已知的,可以通过函数proposer(h,round)来获得。提议者选择函数是加权循环法,其中过程与其投票权成比例地旋转。
   2.三种超时机制:提议超时、预投票超时和预提交超时。每一轮超时时间:timeoutX(r) = initT imeoutX +r ∗ timeoutDelta,在每一个新的高度重置。
   3.一共3轮通讯2轮投票:PROPOSAL消息是唯一携带交易集合区块信息的,PREVOTE和PRECOMMIT消息则携带一个小的恒定大小的值id。
   4. 每个进程在算法1中维护以下变量:step,lockedValue,lockedRound,validValue和validRound。
      step表示内部Tendermint状态机的当前状态。 
      lockedValue存储已发送PRECOMMIT消息的最新值(相对于轮数)。 
      lockedRound是进程发送PRECOMMIT消息的最后一轮,该消息非nil。正确的进程通过在发送id(v)的PRECOMMIT消息之前设置lockedValue = v和lockedRound = r来锁定轮r中的值v。
      validValue变量的作用是存储最新的可能决策值; 
      validRound是更新validValue的最后一轮。除了这些变量之外,进程还存储当前的共识实例(h_p,在Tendermint中称为height)和当前的轮数(round_p)并将它们附加到每个消息。最后,一个过程还存储了一系列decisions,decision_p(Tendermint假定一系列共识实例,每个高度一个)。
   5.共识过程
   如果外部有效函数对值v返回true,并且如果p未锁定任何值(lockedRound = -1)或p具有正确的进程p,则接受值v的提议(对于id(v)发送PREVOTE)锁定值v(lockedValue = v);如果建议的对是(v,vr≥0)并且正确的进程p锁定了某个值,则它将接受v,如果它是更新的可能决策值8,vr> lockedRoundp,或者如果是lockV alue = v(见第29行)。否则,正确的进程将通过发送带有nil值的PREVOTE消息来拒绝该提议。正确的进程将发送带有nil值的PREVOTE消息,以防timeoutP ropose到期(当正确的进程开始新一轮时触发)并且进程尚未在当前轮次中发送PREVOTE消息(参见第57行)。
   如果正确的进程收到针对id(v)的某些值v和2f + 1 PREVOTE消息的PROPOSAL消息,则它发送带有id(v)的PRECOMMIT消息。否则,它发送PRECOMMIT为零。正确的进程将发送带有nil值的PRECOMMIT消息,以防超时Prevote到期(当正确的进程发送PREVOTE消息并收到任何2f + 1 PREVOTE消息时启动)并且进程尚未在当前轮次中发送PRECOMMIT消息(见第65行)。正确的过程决定某个值v,如果它在某个轮次的r PROPOSAL消息中收到v和2f + 1 PRECOMMIT消息的id(v)(参见第51行)。为了防止算法阻塞并永远等待此条件成立,算法1依赖于超时Precommit。在进程收到当前轮次的任何2f + 1个PRECOMMIT消息集后触发。如果超时Precommit到期并且进程尚未确定,则该过程开始下一轮(参见第65行)。当正确的过程p决定时,它开始下一个共识实例(对于下一个高度)。 Gossip通信属性确保导致p决定的PROPOSAL和2f + 1 PREVOTE消息最终被所有正确的进程接收,因此他们也将决定。

   A.终止机制
   主要通过两个值来决定:validValue = v和validRound = r。由提议者使用,验证者收到提议和2/3+的预投票后修改这些值
   在好周期里,如果一个正确进程p在相同的round r中锁定一个值v,所有正确进程将更新validValue = v和validRound = r在此轮结束之前。

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

推荐阅读更多精彩内容