[發(fā)明專利]一種用?ztürk低延時模平方算法提高區(qū)塊鏈吞吐量的方法

有效

• 申請?zhí)枺?/td>: 202011251780.9
• 申請日: 2020-11-11
• 公開（公告）號: CN112346708B
• 公開（公告）日: 2023-07-21
• 發(fā)明（設(shè)計）人: 劉靜;張良峰
• 申請（專利權(quán)）人: 上海科技大學(xué)
• 主分類號: G06F7/556
• 分類號: G06F7/556;G06F7/523;H04L9/06;G06F16/27
• 代理公司: 上海申匯專利代理有限公司 31001
• 代理人: 徐俊

本發(fā)明要解決的技術(shù)問題是：算法在8位機(jī)上最多能夠?qū)崿F(xiàn)1016比特整數(shù)的模平方運(yùn)算，無法實(shí)現(xiàn)區(qū)塊鏈所要求的更大規(guī)模的模平方運(yùn)算。為了解決上述技術(shù)問題，本發(fā)明的技術(shù)方案是提供了一種用低延時模平方算法提高區(qū)塊鏈吞吐量的方法。本發(fā)明擴(kuò)展了算法在8位機(jī)上的處理能力，使其能夠滿足區(qū)塊鏈領(lǐng)導(dǎo)者選舉對模平方運(yùn)算的要求。通過使用8位超導(dǎo)集成電路運(yùn)行擴(kuò)展后的算法，可以加快VDF的運(yùn)算，減少達(dá)成共識的時間，提高區(qū)塊鏈的吞吐量。

技術(shù)領(lǐng)域

本發(fā)明涉及一種用低延時模平方算法提高區(qū)塊鏈吞吐量的方法。

背景技術(shù)

在區(qū)塊鏈共識協(xié)議中，領(lǐng)導(dǎo)者選取(Leader?Election)常被用于決定出塊權(quán)和出塊獎勵的歸屬，一度采用工作量證明機(jī)制(PoW)。由于PoW需要消耗大量計算資源并造成環(huán)境污染，區(qū)塊鏈共識協(xié)議中的領(lǐng)導(dǎo)者選舉正在由PoW方案過渡到空間證明(PoSpace)和可驗證延遲函數(shù)(VDF)相結(jié)合的新方案。使用新方案的區(qū)塊鏈節(jié)能環(huán)保，但仍面臨著吞吐量這一性能瓶頸。為了提高吞吐量，加快VDF的計算速度是亟待解決的問題。

可驗證延遲函數(shù)(VDF)是一種計算過程無法并行，且計算結(jié)果可以被快速驗證的函數(shù)。基于模指數(shù)運(yùn)算的VDF是目前使用最廣泛的構(gòu)造。該VDF構(gòu)造的核心是模指數(shù)運(yùn)算在M的素因子分解不可知的情況下，該運(yùn)算只能通過T次串行的模平方運(yùn)算實(shí)現(xiàn)，不能并行。因此，構(gòu)造高效的低延時模平方算法是加快此類VDF運(yùn)算的關(guān)鍵。

Montgomery算法是目前最常用的模平方算法之一，但是它需要大量額外的預(yù)處理和后處理開銷。Barrett算法在計算單個模平方運(yùn)算時效率較高，在處理多個模平方運(yùn)算時效率較低。此外，Montgomery算法和Barrett算法所涉及的乘法運(yùn)算都沒有高效的低延時硬件實(shí)現(xiàn)。提出了一個實(shí)用的低延時模平方算法，該算法將大整數(shù)表示為多項式，通過對多項式系數(shù)進(jìn)行運(yùn)算大大降低了進(jìn)位鏈(Carry?Chain)的長度，實(shí)現(xiàn)了高效的低延時乘法運(yùn)算；通過查表實(shí)現(xiàn)模運(yùn)算，適合執(zhí)行VDF所需要的串行模平方運(yùn)算。

VDF實(shí)際計算速度不僅依賴于所采用的算法，而且依賴于機(jī)器性能。與半導(dǎo)體集成電路相比，單核處理頻率高達(dá)50GHz的超導(dǎo)集成電路運(yùn)行速度更快、延時更短、功耗更低，對提高VDF的計算速度有著重大意義。在超導(dǎo)集成電路發(fā)展的初級階段，受超導(dǎo)集成工藝限制，實(shí)現(xiàn)低至8位的算術(shù)運(yùn)算是重要的階段性成果。在8位超導(dǎo)集成電路上實(shí)現(xiàn)VDF運(yùn)算具有重要的應(yīng)用價值。

發(fā)明內(nèi)容

本發(fā)明要解決的技術(shù)問題是：算法在8位機(jī)上最多能夠?qū)崿F(xiàn)1016比特整數(shù)的模平方運(yùn)算，無法實(shí)現(xiàn)區(qū)塊鏈所要求的更大規(guī)模的模平方運(yùn)算。

為了解決上述技術(shù)問題，本發(fā)明的技術(shù)方案是提供了一種用低延時模平方算法提高區(qū)塊鏈吞吐量的方法，其特征在于，包括以下步驟：

步驟1、區(qū)塊鏈上的每個節(jié)點(diǎn)從各自所擁有的若干個空間中生成空間證明；一個空間對應(yīng)一個空間證明，節(jié)點(diǎn)的空間證明數(shù)量等于節(jié)點(diǎn)所擁有的空間數(shù)量；

步驟2、每個節(jié)點(diǎn)將各自的空間證明輸入統(tǒng)一的哈希函數(shù)H(·)計算分別得到每個空間證明對應(yīng)的哈希值；

步驟3、每個節(jié)點(diǎn)從所擁有的空間證明的哈希值中取最小值T_z進(jìn)行模指數(shù)運(yùn)算其中，a表示輸入，mod表示模運(yùn)算，M表示模數(shù)；

最快完成模指數(shù)運(yùn)算的節(jié)點(diǎn)成為領(lǐng)導(dǎo)者，贏得出塊權(quán)和出塊獎勵；

每個節(jié)點(diǎn)進(jìn)行模指數(shù)運(yùn)算時，在8位超導(dǎo)集成電路上連續(xù)T_z次串行運(yùn)行模平方運(yùn)算a²mod?M，則任意一個節(jié)點(diǎn)每次運(yùn)行一次模平方運(yùn)算a²mod?M包括以下步驟：

步驟301、將參與乘法運(yùn)算的大整數(shù)a表示成對應(yīng)的多項式形式，有：