這篇文章最初發表於 中等的.
這是一個實現 nChain的解決方案¹。
回到創世紀的問題
比特幣上的代幣通常存儲在 UTXO. 當收到假定的令牌交易時,用戶需要一種有效且快速地檢查其真實性的方法。一個主要部分是決定它是否鏈接到某個創世交易,在哪裡發行代幣。
在基本形式中,Back-to-Genesis (B2G) 問題歸結為:給定一筆交易,它是否與完整交易鏈中的某個創世交易相關聯?
全部 比特幣上的代幣 今天不得不依靠一些受信任的第三方來解決這個問題,因為當鏈過長時,輕量級用戶驗證自己變得在計算上具有挑戰性²。例如,打點錢包的 徽章 令牌使用令牌索引器和 明智的 令牌使用預言機。這種第三方依賴阻礙了比特幣的代幣採用,因為它的可擴展性和 特殊目的公司– 與原生比特幣一樣友好。
我們之前的提議 試圖在沒有任何第三方的情況下解決問題。然而,隨著鏈的增長,代幣交易的規模呈指數增長,嚴重限制了其在實踐中的使用。
遞歸SNARK
召回 遞歸的SNARK,特別是增量可驗證計算(IVC),我們想證明函數F 對初始輸入z₀ 應用n 次會產生zₙ。
在每一步, zᵢ 是公共輸入和 wᵢ 私人輸入(即見證人)。
每一步都會產生一個新的證明。在步驟 一世,證明者算法計算𝛑ᵢ 證明所有步驟 一世 是正確的,僅使用上一步和當前步驟中的本地信息,如下所示。至關重要的是,它不會全部追溯到步驟0,同時仍然能夠驗證自步驟0 正確執行以來的所有步驟。
證明者算法:增量計算證明
將遞歸SNARK 應用於B2G
IVC 自然地導致了B2G 問題的優雅解決方案。
B2G 中的IVC
具體來說,IVC實例化如下:
- zᵢ: txidᵢ,鏈中第i 個交易的交易id
- wᵢ: 第i 個交易的剩餘部分。我們將它分為兩部分:prefixᵢ 和postfixᵢ,代表txidᵢ 之前和之後的內容。
- 功能 F: 交易的txid 是它的雙SHA256 和 (i+1)-th 交易花費 第i 個 交易,它的txid,因此 F 計算如下:
txid 是紅框部分, 前綴/後綴 分別是它之前/之後的所有內容。 || 是串聯。
現在,無論交易鏈的長度如何,我們都可以通過驗證單個簡短證明來證明交易源自給定交易,而無需一直追溯。
一個簡單的NFT 代幣協議
讓我們構建一個簡單的 NFT 代幣 使用上述方法。 NFT 是在發行交易中鑄造的,也就是創世交易。為簡單起見,讓我們在每個轉賬交易中只使用一個輸入和一個輸出³。
當Alice 將NFT 轉移給Bob 時,她構建了一個以Bob 作為接收方的交易,並將其直接從鏈下交給Bob。由於比特幣的點對點性質,她還隨交易發送了一個SNARK 證明。正如我們之前解釋的那樣,Alice 可以在不追踪創世交易的情況下生成證明。
Bob 僅在兩項檢查都通過時才接受NFT:
- 他使用驗證交易 特殊目的公司,類似於普通的比特幣支付
- 他驗證了證明⁴。
如果沒有第一次檢查,攻擊者可以創建源自創世交易的替代交易鏈,但是 不是 在比特幣區塊鏈上。如果沒有第二次檢查,代幣交易可能不會鏈接到創世交易。
證明的大小恆定,只有幾個KB,無論鍊長如何,都可以在幾秒鐘內驗證,產生的開銷可以忽略不計。代幣轉移實際上是即時的,就像普通的比特幣支付一樣。
證明時間
遞歸最耗時的部分 SNARK 正在生成一個證明,在資源受限的設備上最多可能需要一分鐘。為了啟用即時令牌轉移,可以在Bob 收到令牌後立即預先計算證明,以便在Bob 將其轉移給下一個所有者時準備好。如果Bob 需要在從Alice 收到令牌後立即將其發送給Charlie,他可以發送從Alice 收到的舊證明,並讓Charlie 驗證交易鏈中的最後兩個鏈接,而無需生成新證明作為後備。
執行
我們已經使用實現了遞歸SNARK snarkyjs 如下。
首先,我們需要先編譯程序以獲取驗證密鑰。請注意,有 不 受信任的設置。
密鑰可以在與創世交易相關的中央註冊表中公開,也可以放置在創世交易的另一個輸出中。
這 創世紀 調用從第5 行開始的方法來生成初始證明,它只是檢查 txid0 是第9 行的創世交易id。
這 轉移 調用從第13 行開始的方法以生成新的證明,以證明:
- 最後一個證明在第17 行有效
- 當前交易在第18 行和第19 行花費了最後一筆交易。
最後,我們可以根據驗證密鑰驗證證明。
完整的代碼可以在 這個Github 倉庫.
概括
我們只展示一個使用遞歸SNARK 的簡單NFT 示例。它可以擴展到有向無環圖(DAG),而不是交易鏈。它還可以擴展到可替代令牌或用戶需要有效確保交易可以鏈接到某些祖先交易的任何其他用例。
致謝
我們感謝nChain 分享了將遞歸SNARK 應用於B2G 問題的最初想法。我們也感謝Gregor Mitscha-Baude O(1) 實驗室 幫助實現SHA256 電路。
***
筆記:
[1] WP1590 交易鏈證明,MS Kiraz 和O. Vaughan,正在申請專利GB2200400.6。
[2] 在更一般的形式中,事務形成有向無環圖(DAG),使得解決B2G 的計算更加密集。
[3] 這可以在智能合約或SNARK 電路中強制執行,或兩者兼而有之。在前者中,我們可以使用 OP_PUSH_TX 限制從創世交易下降的所有交易中的輸入和輸出數量的技術。例如,我們可以強制任何NFT 交易有兩個輸入和一個輸出。第二個輸入包括交易費用。
[4] 可選地,證明驗證可以在鏈上完成。它只需要在 snarkyjs 證明系統類似於 Groth16 驗證器 我們已經實施。
觀看:BSV 全球區塊鏈大會演示、BSV 上的智能合約和計算
比特幣新手?查看CoinGeek 的 初學者的比特幣 部分,了解更多關於比特幣(中本聰最初設想)和區塊鏈的終極資源指南。