📜 [專欄新文章] 區塊鏈管線化的效能增進與瓶頸
✍️ Ping Chen
📥 歡迎投稿： https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
使用管線化（Pipeline）技術可以提升區塊鏈的處理效能，但也可能會產生相應的代價。
Photo by tian kuan on Unsplash
區塊鏈的擴容方案
說到區塊鏈的效能問題，目前討論度最高的應該是分片（sharding）技術，藉由將驗證者分成多組的方式，可以同時分別處理鏈上的交易需求，即使單分片效能不變，總交易量可以隨著分片/驗證者集的數量線性增加。
除了分片，另一個常用來提升程式效能的方案是將計算步驟拆解，以流水線的方式將複雜的運算攤平，降低系統的閒置時間，並大幅提升工作效率。為了達到管線化預期的目的，會需要先知道系統的瓶頸在哪。
區塊鏈的效能瓶頸
熟悉工作量證明設計哲學的人應該會知道，區塊鏈之所以需要挖礦，並不是為了驗證交易的正確性，而是要決定交易的先後順序，從而避免雙花和帳本分裂的發生。可以說，區塊鏈使用低效率的單線程設計，並付給礦工高額的成本，都只為了一件事，就是對交易的全局排序產生共識。
在這樣的基礎之上，區塊鏈在一段時間內可以處理的交易數量是有限的，這之中包含許多方面的限制，包括 CPU 效能、硬碟空間、網路速度等。其中，關於 TPS(每秒交易數) 提升和對硬體的要求大致上是線性增加的，但在設計共識演算法時，通訊複雜度常是平方甚至三次方的關係。
以現在的目標 TPS 來說，處理交易和生成一個合法的區塊並不困難，只是因為區塊鏈的特性，新區塊需要透過洪水法的方式擴散到全網路，每個節點在收到更新請求的時候都要先執行/驗證過區塊內的交易，等於整個廣播的延時會是「驗證區塊時間×經過的 hop 數量」這麼多。似乎網路越分散、節點越多，我們反而會需要降低計算量，以免讓共識不穩定。
管線化的共識機制
使用權益證明取代工作量證明算是行業發展的趨勢，除了環保或安全這些比較顯然的好處之外，權益證明對產生共識的穩定性也很有幫助。首先，權益證明在同一時間參與共識的節點數是已知的，比較容易控制數量級的邊界；其次，權益證明的出塊時間相較工作量證明固定很多，可以降低計算資源不足或閒置的機率。
相較於工作量證明是單一節點出塊，其餘節點驗證，權益證明的出塊本身就需要很多節點共同參與，瓶頸很像是從驗證轉移到通訊上。
以 PBFT 為例，每次產新區塊都需要經過 pre-prepare, prepare, commit 三個階段，你要對同意驗證的區塊簽名，還要對「你有收到某人的簽名」這件事簽名，再對「你有收到 A 說他有收到 B 的簽名」這件事簽名，過程中會有很多簽名飛來飛去，最後才能把一個區塊敲定。
為了降低每兩個區塊間都需要三輪簽名造成的延遲，後來的共識演算法包括 HotStuff 和 Casper FFG 採用了管線化的區塊驗證過程。也就是對區塊 T 的 pre-prepare 同時是對 T-1 的 prepare 和對 T-2 的 commit。再加上簽名聚合技術，出塊的開銷在複雜度等級和係數等級都降低許多。
然而，要保持管線化的區塊生產順利，需要驗證者集合固定不變，且網路通訊狀況良好。如果會經常更動驗證者集合或變換出塊的領導者，前後區塊間的相依性會是個大問題，也就是 T 的驗證者集合取決於 T-1 裡有沒有會導致刪除或新增驗證者的交易，T-1 的合法性又相依於 T-2，以此類推。
當激烈的分叉出現的時候，出塊跟共識的流水線式耦合就從優雅變成災難了。為了避免這種災難，更新的共識演算法會限制驗證者變更的時機，有些叫 epoch 有些叫 checkpoint，每隔一段時間會把前面的區塊徹底敲定，才統一讓驗證者加入或退出。到這些檢查點的時候，出塊的作業流程就會退化成原本的三階段驗證，但在大部分時候還是有加速的效果。
管線化的狀態更新
另一個可以用管線化加速的是區塊鏈的狀態更新。如前所述，現在公鏈的瓶頸在於提高 TPS 會讓區塊廣播變慢，進而導致共識不穩定，這點在區塊時間短的以太坊上尤其明顯。可是如果單看執行一個區塊內的交易所花的時間的話，實際上是遠遠低於區塊間隔的。
只有在收到新區塊的時候，節點才會執行狀態轉移函數，並根據執行結果是否合法來決定要不要把區塊資訊再廣播出去。不過其實只要給定了交易集合，新的狀態 s’ = STF(s, tx) 應該是確定性的。
於是我們有了一個大膽的想法：何不乾脆將交易執行結果移出共識外呢？反正只要大家有對這個區塊要打包哪些交易有共識，計算的結果完全可以當作業留給大家自己算吧。如果真的不放心，我們也可以晚點再一起對個答案，也就是把這個區塊執行後的新狀態根包在下個區塊頭裡面。
這就是對狀態更新的管線化，在區塊 T 中敲定交易順序但暫不執行，區塊 T+1 的時候才更新狀態（以及下一批交易）。這麼做的好處十分顯而易見，就是將原本最緊繃的狀態計算時間攤平了，從原本毫秒必爭的廣播期移出來，變成只要在下個塊出來之前算完就好，有好幾秒的時間可以慢慢來。新區塊在廣播的每個 hop 之間只要驗證交易格式合法（簽名正確，有足夠的錢付手續費）就可以放行了，甚至有些更激進的方案連驗簽名都省略了，如果真的有不合法交易混進去就在下個區塊處罰礦工/提案者便是。
把負擔最重的交易執行移出共識，光用想的就覺得效能要飛天，那代價呢？代價是區塊的使用程度會變得不穩定。因為我們省略了執行，所以對於一筆交易實際用掉多少 gas 是未知的。本來礦工會完整的執行所有交易，並盡可能的塞滿區塊空間，然而在沒有執行的情況下，只能以使用者設定的 gas limit 當作它的用量，能打包的交易會比實際的上限少。
緊接著，下一個問題是退費困難。如果我們仍然將沒用完的手續費退還給使用者，惡意的攻擊者可以透過發送 gas limit 超大，實際用量很小的交易，以接近零的成本「霸佔」區塊空間。所以像已故區塊鏈 DEXON 就直接取消 gas refund，杜絕濫用的可能。但顯然這在使用者體驗和區塊空間效率上都是次優的。
而最近推出的 smartBCH 嘗試擬了一套複雜的退款規則：交易執行後剩餘的 gas 如果小於 gas limit 的一半（代表不是故意的）就退款；如果剩餘量介於 50%-75% 可以退一半；超過 75% 推斷為惡意，不退款。乍看是個合理的方案，仔細一想會發現製造的問題似乎比解決的還多。無論如何，沒用掉的空間終究是浪費了，而根據殘氣比例決定是否退款也不會是個好政策，對於有條件判斷的程式，可能要實際執行才知道走哪條路，gas limit 一定是以高的情況去設定，萬一進到 gas 用量少的分支，反而會噴更多錢，怎麼想都不太合理。
安全考量，退費大概是沒希望了。不過呢，最近以太坊剛上線的 EIP1559 似乎給了一點方向，如果區塊的使用程度能以某種回授控制的方式調節，即使偶爾挖出比較空的區塊似乎也無傷大雅，也許能研究看怎麼把兩者融合吧。
管線化方案的發展性
考慮到以太坊已經堅定地選擇了分片的路線，比較激進的單鏈高 TPS 管線化改造方案應該不太有機會出線，不過管線化畢竟是種歷史悠久的軟體最佳化技巧，還是很有機會被使用在其他地方的，也許是 VDF 之於信標鏈，也許是 rollup 的狀態轉換證明，可以坐等開發者們表演。
倒是那些比較中心化的 EVM fork/sidechain，尤其是專門只 for DeFi 的鏈，管線化加速可以在不破壞交易原子性的前提下擴容，確實是有一些比分片優秀的地方可以說嘴，值得研究研究，但這就要看那些機房鏈們有沒有上進心，願不願意在分叉之餘也投資發展自己的新技術了。
給我錢
ping.eth
區塊鏈管線化的效能增進與瓶頸 was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
導函數題目 在 [心得] 微積分考前略整- 精華區trans_math 的推薦與評價
這幾天把要考的學校題目都稍稍寫過了，
順便藉由這篇文章做一些考前的統整，
或許也可以幫助到一些版友。
※章節分類
(1) 基礎知識
(2) 極限
(3) 連續
(4) 導函數
(5) 微分應用
(6) 不定積分
(7) 積分應用
(8) 多變函數
(9) 重積分
(10) 數列與級數
(11) 向量微積分
(12) 微分方程
A.基礎知識
這部分的內容就簡述一些在微積分中頻繁或可能用到的高中數學知識。
(a) 函數概念：奇偶函數、函數有理化、配方法、根與係數
牛頓一次因式檢驗、公式解、反函數、合成函數
(b) 三角函數：平方關係、商式關係、和差角公式、倍半角公式
和差化積、積化和差、餘弦定理、正弦定理
(c) 數列級數：無窮等比、等差數列、級數求和公式
(d) 其他：Euler Formula（三角函數、雙曲函數）
B.極限篇
這部份則用題型來做分類：
(a) 利用極限的柯西定義式去證明一極限式（少考）
(b) 極限求值 - 三角極限 （極限等價式、L'Hospital或採級數解）
極限求值 - 無窮極限 （若出現負無窮，先做代換，避免出錯，
由分式上下領導係數求解）
極限求值 - 夾擠定理 （此型形式明顯，但小心可能與黎曼和搞混）
極限求值 - 高斯函數 （熟記高斯函數概念，小心分段點，
善用討論左右及代換法）
(c) 漸近線
(1)水平漸近: 即解無窮極限
(2)鉛直漸近: 分式型時常令分母為0 ( 因其定義需 -> 無窮 )
(3)斜漸進線: 先求斜率再找截距
註: 以上僅簡述分式型, 小心指對數之漸近.
有時將函式化做代分式可快速判得
C.連續篇
這邊主要是緊扣連續的概念：(1)極限值存在
(2)函數值存在
(3)極限值與函數值相等
其餘則為定理記憶和應用，
比如固定點 Fixed Point 之證明（中原期中、清大研究所）
D.導函數篇
(a) 導函數定義
(b) Chain Rule （注意對數微分法、指數微分法）
(c) 反函數的微分、參數式表示下的微分 （ 即Chain Rule應用 ）
E.微分應用
(a) 洛爾均值、均值定理（拉格朗日均值）、柯西均值
需會其證明，並得以利用上述定理證明不等式或求近似值
(b) 單變函數極值
緊扣臨界點（Critical Point）概念，求得後（端點、平穩點、奇異點），
若判相對，考慮一階導數判別（增減性改變與否？）
或二階導數判別（凹口向上或向下？）
若求絕對則直接代入臨界點求值比較大小
(c) 反曲點（Inflection Point）概念
二階導數為零，三階導數不為零之點（此為Adams之定義）
廣義些，只需左右凹性不同，不需具二階導數存在（Larson之定義）
(d) L'Hospital
標準不定型（零分之零，無窮分之無窮）時可用，
常見於分式型，指數型，可配合等價式簡化運算。
(E) 作圖
綜合凹性增減性判斷、極值判斷、函數奇偶性判斷
反曲點概念、漸進線求法，善會表格後依表作圖
F.不定積分
沒什麼重點，因為全部是重點…熟悉基本積分運算！
(a) 變數變換法
(b) 分部積分（IBP）
(c) 全角代換法（常用於平方和平方差帶有根號）
(d) 半角代換法（常用於sin, cos與多項式並於分母項）
(e) 其他：積分漸化式
E.積分應用
(a) 微積分基本定理之證明及內涵
(b) Lebniz微積分式（可經化簡為微積分基本定理）
(c) 積分求面積（由函數型態判斷假設方向）
(1)顯函數 f(x), g(y)型
(2)參數表示 x = f(t), y = g(t)型
(3)極座標型
首要畫略圖，求交點，判斷函式大小後，
可能分段積分，莫忘由交點判別上下限，
其餘則是不定積分功力的熟稔。
註：此型題目有時可以Green's Theorem轉為線積分做運算
(d) 旋轉體體積（圓盤法、殼層法、Pappus's Theorem）
同上，需由函數型態判斷列式方向，
小心題給函數無法以顯函式表示時，圓盤法無法得解，
需用殼層法求得（相關例題可見99台大微乙期中）
(e) 形心、重心
熟記定義，列式求解
(f) 旋轉表面積（重點同c,d）
(g) 積分求弧長（重點同c,d）
(h) 瑕積分
熟記各種判別方式和瑕點分類判別，
常見 P 積分、 P 級數斂散和收斂值可背儘量背。
需小心奇函數斂散特性，若單邊發散，則發散，
不會有因為奇函數對原點對稱而必收斂至 0 之現象。
(i) 黎曼和
依循黎曼和的概念：分割、取樣、求和。
並配合高中級數公式求解。
G.多變函數
(a) 求極限值
儘量往極限不存在做思考，善用線性代換、極座標代換、球座標代換
(b) 連續性（同單變數概念）
若具連續性，則有 f = f
xy yx
(c) 偏微分、全微分
善用函數關係樹狀圖以便於 Chain Rule 應用，
此處有個概念：可偏微未必具連續性，但可全微分必連續
(d) 梯度、旋度、散度、方向導數
梯度和方向導數概念務必瞭解，切莫混淆，
此為求解多變數極值、切平面方程式重要基礎，
旋度和散度則需瞭解其定義及物理意義。
(e) 多變函數極值
通常有以下四種方法
(1)極值理論
利用有極值的必要條件 df = 0 求得臨界點（同單變數極值）
再利用 Hessian Matrix 判別極大極小或鞍點，
雙變數則直接套用判別式 D = f f - f ^2 做判別
xx yy xy
(2)柯西不等式
(3)算幾不等式
(4)拉格朗日乘子法（Lagrange Multipier）
若題目含有限制條件時優先考慮，
注意目標函數、限制函數、拉格朗日函數的選取與假設。
註：有題目需討論邊界點及內部點，需注意！
H.重積分
(a) Fubini's Theorem
(b) Jacobian 座標轉換（球座標、極座標、廣義座標，有時須轉換多次）
需熟稔的是變換積分次序後的上下限該如何判別，
善用繪圖和不等式運算。
I.數列與級數
(a) 數列
數列收斂和發散之定義，可配合極限一併研讀，
可稍稍閱讀高中等比數列和等差數列。
(b) 級數斂散
正項級數，熟練各種判斷方法。（熟記 P 級數）
交錯級數，同上，並需知曉萊布尼茲收斂條件
(c) 收斂區間、收斂半徑
由級數型式配合根式檢驗、比值檢驗法求收斂半徑，
依此可得初步收斂區間，再代入邊界點檢驗斂散，
可得真正斂散區間。
(d) 級數求值
(e) Taylor's Theorem, Maclaurin Series
記憶泰勒展開型式，並瞭解馬克勞林級數與其關係（展開點 x = 0）
此處有求近似值和求其級數展開，
需熟記常見之級數，證明則由定義出發，
或採已知級數做四則運算（如tanx = sixx/cosx）
或採無窮等比級數展開配合積分（如arctan x）
或採二項式展開配合積分（如arcsin x）
J.向量微積分
(a)線積分
純量函數線積分，向量函數線積分（可拆為多項純量函數線積分求解）
(b)積分路徑相關性
即函數是否具保守性（利用旋度是否為 0 判斷）
配合路徑變形原理的應用（挖洞與否？）
(c)Green's Theorem, Stoke's Theorem, Gauss Divergence Theorem
熟記其公式，題目多為基礎公式，
並需瞭解其物理意義，和使用條件
註：此處可一併和微分方程、全微分單元閱讀
瞭解恰當型（Exact）微分方程之求解方法
K.微分方程式
(a)分離變數型
(b)正合恰當型( Exact )
(c)非正合，求積分因子，乘回為正合，再求解
(d)線性標準型，代公式
(e)白努利變換型，轉為標準型後代公式
(f)Cauchy - Euler型
註：此處仍有一小觀念，即齊次函數定義。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.163.90.174
是打錯了XD 順便修一些錯字~
... <看更多>