📜 [專欄新文章] Fraud and Data Availability Proofs
✍️ Brian Po-han Chen
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
這篇文章是被Kimi啟發,所以去研讀並且節錄一些重點還有我對這篇paper的理解
輕節點(Light clients, SPV clients)在整個區塊鏈網路中只下載少部分的資料來驗證區塊是否合法,而這個做法相比於全節點驗證全部資料來說,必須假設共識演算法中只有包含有效的區塊資料同時也假設大部分的全節點是誠實的.
如果讓全節點能夠產生 Fraud Proofs 來證明區塊確實違反了共識協定的規則同時搭配概率抽樣的方法來驗證全部的區塊資料可供下載,就可以大大的降低誠實節點的數量假設;藉由能夠保證鏈上資料都是可得並且有效,Fraud and Data Availability Proofs會是擴容技術(e.g., sharding, bigger blocks)的一大重點.
Erasure code and Reed-Solomon Codes
糾刪碼是將原來長度為k的訊息編碼成為長度為k+m的訊息,而原來的訊息可取編碼後的訊息子集來還原,也就是說這個技術可以容忍m個分散式節點故障,這邊就不詳述了,可參考Kimi的文章
Fraud Proofs
Block Structure
一個block header應該要包含以下元素
prevHash: 前一個block header的hash
dataRoot: 資料(e.g., transactions)組成Merkle tree的root hash
dataLength: 資料樹的葉節點數量
stateRoot: 狀態樹的root hash
additionalData: 額外的任意資料,像是nonce或是難度等等
2. State Root and Execution Trace Construction
transition function: 給一個state S並且去執行transaction T,成功則返回新的state S’ , 或者失敗了返回error
state witness: state tree中只有部分被transaction讀取或者改變的merkle proofs
rootTransition: 使用Merkle proofs來有效地表達一個子樹(root hash會跟整棵狀態樹一樣)
interRoot: rootTransition在一個區塊中執行每個transaction時產生暫時的state root,denote成trace
3. Data Root and Periods
shares: 資料樹的葉節點,包含一個完整個transaction, 部分的前一個transaction跟後一個transaction以及完整的transaction,這樣做法的好處是message parser不需要全部的message就可以建立message boundaries
利用parser將transactions取出之後就可以去驗證state transition是否正確
4. Proof of Invalid State Transition
一個不正常或者惡意的礦工可能會給出一個不正確的stateRoot,我們可以利用dataRoot下的資料(包含trace)來驗證部分的執行是有問題的;一個Fraud Proof 包含不正確state transition相關的shares, 這些shares的merkle proofs, 以及shares中的state witnesses
Verify function要檢查1. block hash跟client端存的是一樣的. 2. 每一個shares都在dataRoot底下. 3. parseShare執行完是整個區塊transition的子集. 4. 確認執行transaction後,trace_x會變成 trace_(x+1),執行無誤
Data Availability Proofs
惡意的區塊產生者為了避免全節點產生Fraud Proof,可能會扣留著資料而只送出block header,等到過了很久之後才送出資料,這樣可能會造成未來的transactions rollback,所以對於輕節點來說,高度保證正確的資料可得性是非常必要的
這篇paper提出一個基於Reed-Solomon erasure coding的data availability scheme,這個scheme假設網路上有足夠多的輕節點可以產生足夠數量shares來恢復完整資料
Strawman 1D Reed-Solomon Availability Scheme
首先,block producer將區塊資料編碼成k個shares並且利用RS編碼將資料擴展成2k個new_shares,在前面的RS coding中得知我們只需要隨機取得k個new_shares就可以恢復原來的資料.
如果block producer沒有正確的利用RS coding來擴展資料,則就算new_shares資料都可得,也無法正確的恢復原來的資料,也就是說客戶端必須把所有的資料重新編碼一次來判斷block producer有沒有正確產生dataRoot,也因此需要區塊大小的空間O(n)資料.
PS: 我認為要讓其他的全節點做驗證,因為輕節點沒有全部transaction資料
如果使用多維度的編碼則可以將proof size降到O(n^(1/d)),d為維度大小,簡單用2維空間來做解釋,但是實際的scheme是可以用到更高維
2. 2D Reed-Solomon Encoded Merkle Tree Construction
首先,將raw data 切成 k * k 個 new_shares
利用RS coding 將原來的資料水平以及垂直擴展,再將垂直擴展的shares再做一次RS coding就像fig 4.圖示,最後產生一個Matrix M_i for block i
計算每一個row, column所組成Merkle tree的root hash
最後計算rowRoot跟columnRoot的hash
最後資料樹的資料長度會是 2 * (2k)² 元素(經過編碼的new_shares),前半段的葉子點路徑包含row root,而後面一半則是包含column root;輕節點或是全節點可以透過所有的row root跟column root 去驗證 data root 是否正確,為了獲得資料可得性的保證,所有的輕節點都至少要下載區塊所有的row 及 column root,這樣才有辦法產生Fraud Proof
3. Random Sampling and Network Block Recovery
輕節點跟全節點協定如下
輕節點收到block header 以及 raw roots, column roots,驗證data root 是否正確,否則reject header
輕節點隨機取幾組座標(x, y),並且寄給一個或多個全節點
全節點如果有這組座標的shares以及相關的merkle proof就回傳給輕節點
輕節點檢查這個shares 以及相應的 merkle proof是否屬於相應的row root樹或者是 column樹
輕節點把shares 跟相應的merkle proof gossip給其他與他相連並且沒有這些shares資料的全節點
如果所有的proofs 都通過檢驗,則這個block被認為是可得的
4. Selectively Share Disclosure
如果區塊產生者有選擇性的釋出shares,儘管這些shares是unrecoverable,但是這個區塊還是會被認為是available;所以可以藉由假設網路上有足夠多的誠實節點並且有超過(k+1)²個shares 會被匿名的sample request呼叫來解決這個問題,也可以利用enhanced network model來強制不同sample的request不能給同一個client,請求順序也是隨機分布的.
5. Fraud Proofs of Incorrectly Generated Extended Data
如果一個全節點拿到足夠多的shares去recover特定的row或是column,並且發現recovered data不正確,那他就必須提出一個merkle proof包含足夠的shares可以recover那個data.(包含每個shares的merkle proof)
結論
這篇paper提出了一個data availabilty的方法,在額外的一些假設下(至少有一個誠實的節點會提出Fraud Proof,一定數量的輕節點會共同來恢復區塊),來讓輕節點的安全保證幾乎跟全節點一樣
Fraud and Data Availability Proofs was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
同時也有1部Youtube影片,追蹤數超過162的網紅SNOWSTORM,也在其Youtube影片中提到,Lyrics: Sarah Koay Li Ming Melody: 518 Arrangement: 518 Electric Guitarist: Chuah Shao Ren Pianist: Ng Ken Kit Drums: Javelin Yu Jun Lin EDM Keyboardi...
「matrix trace」的推薦目錄:
- 關於matrix trace 在 Taipei Ethereum Meetup Facebook 的最讚貼文
- 關於matrix trace 在 農民教主碎碎念 Facebook 的最讚貼文
- 關於matrix trace 在 SNOWSTORM Youtube 的最佳貼文
- 關於matrix trace 在 How to calculate the trace of a matrix in Keras backend? 的評價
- 關於matrix trace 在 Trace of a Matrix: when to use? what is trace trick? - Math ... 的評價
- 關於matrix trace 在 Deep Learning Book Series · 2.10 The Trace Operator - Posts 的評價
- 關於matrix trace 在 matrix-trace-canary模块帧率检测在renderthread下的使用场景 ... 的評價
- 關於matrix trace 在 Trace Matrix, Inc - Home | Facebook 的評價
matrix trace 在 農民教主碎碎念 Facebook 的最讚貼文
等一下坐車時再讀。 C15 C17 很有趣。
C15 :(Wiki)
Pentadecanoic acid is a saturated fatty acid. Its molecular formula is CH3(CH2)13COOH. It is rare in nature, being found at the level of 1.2% in the milk fat from cows.[2] The butterfat in cows milk is its major dietary source[3]
C17:(Wiki)
Heptadecanoic acid, or margaric acid, is a saturated fatty acid. Its molecular formula is CH3(CH2)15COOH. It occurs as a trace component of the fat and milkfat of ruminants,[2] but it does not occur in any natural animal or vegetable fat at high concentrations.
心血管代謝疾病:超越卡路里的影響
高糖加上高脂飲食,或許才是增加心血管代謝疾病風險最主要的原因.
高糖加上高脂飲食透過影響大腦相關
獎勵系統(reward system)及腸道菌態平衡(gut microbiome),擾亂能源平衡系統(Energy balance).
Pathways and mechanisms linking dietary components to cardiometabolic disease: thinking beyond calories.
obesity reviews:2018 May 14.
doi: 10.1111/obr.12699.
Conclusion
1.Evidence suggests that consumption of n-6 fatty acids
results in lower cardiometabolic risk factors/risk compared
with isocaloric amounts of SFA. However, differences
exist between individual SFA, and the food matrix needs to be considered; e.g. dairy foods such
as cheese and yogurts are associated with reduced cardiometabolic risk. More research is needed to clarify the differences among the individual SFA and SFAcontaining
foods.
2.Evidence strongly suggests that consumption of
fructose-sweetened, HFCS-sweetened or sucrosesweetened beverages increases cardiometabolic risk factors/risk compared with isocaloric amounts of
starch. More research is needed comparing the metabolic
effects of SSB versus sugar in solid food and sugar
in solid food versus refined or whole grain starch.
3.There is currently insufficient evidence that a highCHO
diet affects weight gain or weight loss to a different
extent than a high-fat diet. Susceptibility to weight
gain when consuming diets high in refined CHO/glycaemic load may be affected by the metabolic status of the individual (i.e. glucose tolerance/insulin
sensitivity). More studies focused on strategies to prevent
weight regain in weight-reduced subjects are
needed.
4.RCTs ranging from 4 weeks to 3 years in duration
demonstrate that consumption of aspartame does not
promote body weight gain in adults. Well-controlled
and long-term RCTs in adults are warranted to assess
the effects of saccharin, acesulfame K and steviol glycosides on body weight and other health outcomes. More
studies to assess the effects of all types of NNSs in children
are needed.
a• Continued research on the following topics could provide
important insights and strategies for slowing the
obesity epidemic.
b• The high-sugar, high-fat palatable Western diet
could be perturbing both sides of the energy balance
equation through effects on brain regions associated
with reward and/or on the gut microbiome.
c• Susceptibility to weight gain may be affected by exposure
to sugar and/or NSS during critical periods
of development from pre-conception to adult life
matrix trace 在 SNOWSTORM Youtube 的最佳貼文
Lyrics: Sarah Koay Li Ming
Melody: 518
Arrangement: 518
Electric Guitarist: Chuah Shao Ren
Pianist: Ng Ken Kit
Drums: Javelin Yu Jun Lin
EDM Keyboardist: Edwin Chin Yan Yin
Vocals: Sarah Koay Li Ming, Edwin Chin Yan Yin
Mixing: Edwin Chin Yan Yin
Cover Picture: Matrix
Lyrics:
Verse
They’re telling me to give up on you
The harder I try, the more i become attached to you
You’re becoming the drug that I’m getting used to
If there was a chance, I would stay and wait for you
Chorus
So tell me you will come back maybe
I’ll be here waiting for you baby
Sing my anthem oh oh
Watching by the windowsill everyday you pass
I would sit there patiently waiting
Do you know how long i’ll be giving
It’s just my youth oh oh
Hold my hand and don’t let go
Just give me the keys that bring me back to you
So pull me closer to you baby
I’ll be right here with you i promise
I’ll stay right here and never let you go
I’ll be the one
Rap Verse
Do you know how much it hurts for me to just look at you again
Do you know how sick it is to see you in his arms
I was so close, so in love, so desperate to see you in every way
You were my light, you were my soul, and i love you everyday
You made me throw tables and chairs when we didn’t work out in the end
I see you happy right there but all alone going crazy about
When I said I loved you you blamed me for thinking out loud
How much do i have to go through? All of this to see your smile
You pulled me in your arms and said you would be alright
You told me you would be the moon and stars in my night
You held my hand, ran your fingers through my hair, said you would hold me tight
But turns out that it was all just a lie
I loved you for one second and you made me felt true
You hurt me and broke me like all the other play boys do
I thought you were different and i really loved you
So someone just come on bring me back to you
Chorus
Tell me you won’t come back maybe
I’ll be lost you won’t be able to trace me
Ooh
I would sit there patiently waiting
Do you know how long i’d be giving
Hold my hand and don’t let go
Just give me the keys that bring me back to you
Oh bring me back to you
So pull me closer to you baby
I’ll be right here with you i promise
I’ll stay right here and never let you go
I’ll be the one
![post-title](https://i.ytimg.com/vi/JdsmG95aK6E/hqdefault.jpg)
matrix trace 在 Trace of a Matrix: when to use? what is trace trick? - Math ... 的推薦與評價
On calculating log-likelihood function for some multivariate distributions, such as multivariate Normal, I see some examples where the matrices ... ... <看更多>
相關內容
matrix trace 在 Deep Learning Book Series · 2.10 The Trace Operator - Posts 的推薦與評價
This short post introduces you to the trace operator. We will see what is the Trace of a matrix and how to compute it. ... <看更多>
matrix trace 在 How to calculate the trace of a matrix in Keras backend? 的推薦與評價
... <看更多>
相關內容