Monero.門羅幣 隱匿交易的基礎介紹

-

今天要來簡單介紹一下，門羅幣是怎麼達到匿名交易的。本篇文章會牽涉到橢圓曲線的原理，如果不懂，可以先參考「加密技术核心算法之安全快捷的ECC算法」。簡單來說就是要知道這樣的關係： 
p = k*G , 
    p：公鑰    
    k：私鑰
    G：曲線上的基準點


門羅隱匿交易包含了三個技術：Ring Signature（環簽章）, Ring Confidential Transactions （RingCT, 環保密交易）跟Stealth Address（隱匿位址）。在Digital Asset Research 的文章中這張圖解釋了各個技術所使用的地方，本篇文章，就是要介紹這三個技術。

source: https://medium.com/digitalassetresearch/monero-becomes-bulletproof-f98c6408babf


在介紹之前，先了解門羅鏈有些基本概念。在門羅中有兩把key（其實是4把，因為各有私鑰跟公鑰），一把是view key另一把是spend key。顧名思義，一把是拿來看的自己餘額的（在鏈上找隱匿位址），一把是拿來花的（做環簽章）。由spend key可以產生key image（金鑰映像），用來做預防雙花的證明，有點像zcash的nullifier。


Ring Signature（環簽章）

環簽章有點像混幣，就是把好幾筆交易混在一起，不過還是有差異，可以參考「What are the technical advantages of Ring Signatures (CryptoNote) compared to CoinJoin?」

那實際上怎麼做呢？！ 假設一個初始值v，跟一串隨機數$(y_1, y_2, ..., y_n)$，然後把v跟隨機數經由$E_k$做加密，再把加密過的值跟下一個隨機數做運算(xor)再加密，如：$E_k(y_{n-1} {\oplus} E_k(y_n{\oplus}v))$，所以函數如下
$$C_{k,v}(y_1, y_2, ..., y_n) = E_k(y_1 \oplus E_k(y_2 \oplus ... E_k(y_n \oplus v)))$$
接著使 $C_{k,v}(y_1, y_2, ..., y_n) = v$，也就是v經過一連串的計算後，最後會等於自己，這就是環簽章的基本概念，如下圖形成一個環

實際應用場景會像這樣
m：訊息
$P_1, P_2, ..., P_n$：為任意的一組公鑰

1. 計算加密金鑰$k = Hash(m)$
2. 選擇隨機數v
3. 為所有的公鑰選擇隨機數 $(x_1, x_2, ..., x_n)$（不包含自己$x_s$），接著計算$y_i = g_i(x_i)$。
（ $g_i = x_i^{P_i} mod N_i$ ）
  * 也就是上述的隨機數 $y_i$，使用公鑰來產生
4. 藉由 $C_{k,v}(y_1, y_2, ..., y_n)$ 來求得自己的 $y_s$
5. 接著利用自己的私鑰算出 $x_s$，$x_s = g_s^{-1}(y_s)$
6. 最終，輸出環簽章 $σ = (x_1, x_2, ..., x_s, ..., x_n, v)$

驗證
1. 計算 $y_i = g_i(x_i)$, i = 1, 2, ..., n
2. 計算加密金鑰$k = Hash(m)$
3. 驗證 $C_{k,v}(y_1, y_2, ..., y_n) ?= v$

因為v跟$y_s$是相關的，而只有擁有私鑰的人才能從$y_s$算出$x_s$，因此其他人無法假造簽章。而環簽章有個特性，就是少了某一項，可以用其他項來算出少的那一項。因為簽章被混合過了，所以礦工無法直接驗證交易是否花過了，要怎麼確保雙花的問題？就要借助到金鑰映像（key image）的幫助，實際怎麼運作，後面的隱匿位址一起介紹。


Ring Confidential Transactions（環保密交易）

在RingCT（環保密交易）出現之前，因為環簽章的限制，混合環簽章的金額必須一樣，所以交易金額都必須被拆成固定面額，例如要交易12.5XMR，就需要拆成10, 2, 0.5三種面額，雖然發送方的資訊有環簽章做保護，但是交易的金額就暴露給所有人了。
環保密交易出現後（新版的環簽章"A Multi-layered Linkable Spontaneous Anonymous Group signature"所支援），金額將會被遮罩住，因此不必拆成已知面額，進而可以達到隱匿的作用。

Stealth Address（隱匿位址）

記得上面提到，每個人有兩把key（view key跟spend key）。假設Alice要轉錢給Bob，首先，Alice要利用Bob的public view key跟public spend key組成一次性的公鑰，計算如下
$$P = H(rA)G + B$$
r： Alice選的隨機數
A：Bob's public view key
B：Bob's public spend key
G：橢圓曲線中的基準點
H：hash function

然後計算 $R = rG$。接著把交易送到P所產生的位址，並將R值放入交易的內容。所以整個網路都會知道P跟R。
因為r是隨機數，每次產生出的一次性公鑰P都會是不同的，而由公鑰P產生出門羅的地址就叫做隱匿位址（stealth address）。Alice把交易送到隱匿地址後，Bob要怎麼知道這筆交易呢？

Bob有view key跟spend key對應的私鑰(a, b)，Bob計算
$$P' = H(aR) + B$$
因為$aR = arG = rA$，所以可得$P' = H(aR) + B = H(rA) + B = P$
所以若$P' == P$就代表這筆交易是給自己的，而這個計算需要a: private view key，所以也就只有Bob可以計算得出來。Bob找到交易後可以算出對應的私鑰$x = H(aR) + b$，就可以動用這筆交易了！而這種方式，對於收款人來說是麻煩的，因為要隨時掃描鏈上的交易，才知道有沒有自己的。（有一種方式，是把自己的view key給第三方，由第三方幫你掃描，不過你的資產就會曝光，但是依然只有自己能動用）

回到雙花的問題上，上面有提到金鑰映像，先來看金鑰映像的算法
$$I = xH(P)$$
基本上是由一次性的公鑰P跟私鑰x組成，每一筆交易P只會對應到一把私鑰x，所以對於每筆交易P其金鑰映像I都是固定的，因此礦工只需要去驗證I是否有重複，就可以驗證是否雙花。


門羅的最新協議Bulletproof，是一種range proof，主要用於環保密交易（RingCT），藉由Bulletproof可以大大減少了驗證資料的大小，讓交易資料變小，而手續費得以減少，有機會再來深入探討Bulletproof。

擴展性（scalability）是門羅的一個大問題，主要是保密交易使用的rang proof的資料量龐大，使得交易的資料量很大，約是比特幣的10倍（使用bulletproof後），每次交易也都會有新的金鑰映像提供查詢，所有歷史交易的紀錄都需要保留，無法像比特幣有些技巧可以省略某些交易。這或許對門羅幣是個挑戰，但是另一派的說法，門羅幣的交易量不是重點，而是他提供的隱私性。各位覺得如何呢？

這是門羅非官方的台灣社群，裡面有很多門羅的介紹.技術文章跟最新進展等


若文章有誤或是解釋不清的，歡迎指正

reference:

留言

張貼留言

這個網誌中的熱門文章

What's New in Ethereum Serenity (2.0)

-
圖片
Ethereum 2.0 已經正式改名為Ethereum Serenity 原本預計在今年(2018)上線的Hybrid POS(Casper FFG)跟sharding，因為遇到一些技術上的困難，所以把Hybrid POS改成單純POS，然後因為sharding跟POS有部份技術是重疊的，所以把POS跟sharding併在一起做（本來是分成兩個team作開發） Beacon Chain 在Ethereum Serenity的規劃中，在原本的POW chain之外多一個鏈叫做 Beacon chain ，是一個POS chain。在Beacon chain中有兩種角色 proposer 跟 attester ，proposer就是產塊的人，attester是驗證的人。而在POW chain上存入32 ETH，可以成為Beacon chain上的 validator ，而validator有權利產塊(proposer)，也會有機會被選attester。此外，延續了Casper FFG finality這個概念，也就是在finality之後的狀態就是正確的狀態（不可回復），不像POW一般需要6個塊的時間才能確認交易是不會被更改的（POW的狀態確認是機率，六個塊之後有"很高的機率"是無法被改變的，而finality就像是0跟1一樣，沒有中間）。 聽到這，好像覺得很簡單，但是在實作上會遇到幾個問題，首先，怎麼決定誰是proposer誰是attester，如果亂數的隨機性不夠，就很容易被遭到操控。接下來是，每次驗證都需要做一次簽名，因為32個ETH就可以當validator/attester，每次驗證可能會有10~20幾萬的簽章（ 簽章數量的預估方法 ），驗完簽章天都黑了 ＸＤ。 ＲＮＧ 針對亂數產生（ RNG , Random Number Generator），使用 RANDAO 跟 VDF ，RANDAO是個利用經濟獎勵的機制來產生亂數，原始的設計是在smart contract上，而在Beacin chain會直接實作這個邏輯。而VDF是一個delay function，因為速度的關係，基金會打算自己開發ASIC晶片。關於這RNG之後會再寫一篇 詳細解釋 。 Signature Aggregatio...
閱讀完整內容

瑞士滑雪分享2 - 策馬特

-
圖片
本篇同 上一篇 ，只介紹滑雪資訊，關於觀光資訊，就不在這裡詳述 一樣，我們先來介紹策馬特/馬特洪峰，這裡一樣是分兩區，Zermatt跟International，如下圖，左邊紅色框是 Zermatt ，而 International 是Zermatt+Italy，也就是 全山卷 ，在Zermatt賣的就這兩種票 在這我一樣只有滑兩天，就只買了Zermatt的票，所以不要再問我買International需要不要護照之類的問題，我不知道阿~~ XD 我住在Zermatt，這個鎮還滿大的，所以在挑住宿的時候需要注意一下，Zermatt的住宿非常的貴，比Grindelwald貴上許多，所以也有人選擇住下面的小鎮，再坐火車到Zermatt，至於住哪個小鎮或是便宜多少，我沒有研究，就不知道了。Zermatt火車站一出來，就有往山上的小火車，所以住下面的小鎮要上山滑雪，也算滿方便的。 Zermatt雪場分三區，最左邊Rothorn，中間Gornergrat，最右邊Matterhorn Glacier Paradise。 Rothorn ：要搭小火車上山，滿特別的，詳細介紹可參考 這篇網誌 ，離Zermatt火車站約10分鐘的路程。 Gornergrat ：一出火車站，對面就是車站了，小火車直接拉到山頂，相當方便 Gornergrat車站 Matterhorn Glacier Paradise ：上山纜車離市區相當遠，走路大約要20-25分鐘（有接駁巴士），需要轉2次纜車才能到山頂，要花不少時間，山頂非常冷，滑道很平緩，又冷又不好玩 三座山基本上可以互通，不需要回到小鎮再上山。這裡高度大都在2000-3000公尺，所以雪況比少女峰好很多，不過相當多的平路，對snowborders相當不友善....。 完整的地圖可參考： Zermatt ski map 雪票價格如下，這裡的雪票是用磁卡，所以會有5CHF的押金，最後記得去退（像我就忘了...@@） Zermatt/International ski pass (2014/15) ： Zermatt International (Zermatt - Cervinia) Days Adults You...
閱讀完整內容

動手實做零知識 - circom

-
圖片
零知識證明在過去一年越來越廣為人知，去年(2019)也有越來越多的專案是基於零知識證明。前年底提出的 zk rollup，目前由  Matter Labs  在開發，Matter Labs更在上個月（2019/12）發表了  ZK Sync ，解決了因為產生證明（proof）而延伸的延遲問題。此外  Iden3  跟 ConsenSys  也有 zk rollup 的專案。在以太坊研究論壇有基於 zk rollup 所衍生的 匿名 zk rollup 。 Semaphore 是一個基於零知識證明的一個訊號系統，發送者可以不揭露身份的狀況下廣播任何訊息(an arbitrary string)。 Semaphorejs 延續 Semaphore 的核心概念，並將整個概念更加完整化，從前端網頁到後端服務。這兩年才發表的 zk-STARKs，也在去年年初跟 0x 合作，推出基於 zk-STARKs 的 去中心化交易所 。 在技術上，去年下半年有新的論文，使用 DARK compiler 可以讓 SNARKs 達到公開性（Transparent）。還有 MARLIN, SONIC, PLONK 等可通用且可更新的可信設定（trusted setup）。STARKs 的 FRI 驗證方式也默默地跟 SNARKs 做結合。（東西越來越多，根本看不完 QQ） 這篇文章沒有要談高深的技術，只會介紹實做所需的知識。這篇會使用到 Iden3 所開發語言  circom  來幫助寫算數迴路 。藉由 circom，可以更輕鬆地實做零知識證明的程式。但在開始之前，先介紹一些基本觀念。 算數迴路 在實做零知識程式跟一般撰寫程式不同，需要先把問題轉成迴路，才去執行（實際上是把 問題 轉成 多項式 再轉成 迴路 ）。舉例來說，一個多項式 $x^3 + x +5$，會轉成像這樣的迴路 sym_1 = x * x // sym_1 = x^2 sym_2 = sym_1 * x // sym_2 = x^3 y = sym_2 + x // y = x^3 + x ~out = y + 5 ...
閱讀完整內容