TY - GEN
T1 - Coded Merkle Tree
T2 - 24th International Conference on Financial Cryptography and Data Security, FC 2020
AU - Yu, Mingchao
AU - Sahraei, Saeid
AU - Li, Songze
AU - Avestimehr, Salman
AU - Kannan, Sreeram
AU - Viswanath, Pramod
N1 - Publisher Copyright:
© 2020, International Financial Cryptography Association.
PY - 2020
Y1 - 2020
N2 - In this paper, we propose coded Merkle tree (CMT), a novel hash accumulator that offers a constant-cost protection against data availability attacks in blockchains, even if the majority of the network nodes are malicious. A CMT is constructed using a family of sparse erasure codes on each layer, and is recovered by iteratively applying a peeling-decoding technique that enables a compact proof for data availability attack on any layer. Our algorithm enables any node to verify the full availability of any data block generated by the system by just downloading a byte block hash commitment and randomly sampling bytes, where b is the size of the data block. With the help of only one connected honest node in the system, our method also allows any node to verify any tampering of the coded Merkle tree by just downloading bytes. We provide a modular library for CMT in Rust and Python and demonstrate its efficacy inside the Parity Bitcoin client.
AB - In this paper, we propose coded Merkle tree (CMT), a novel hash accumulator that offers a constant-cost protection against data availability attacks in blockchains, even if the majority of the network nodes are malicious. A CMT is constructed using a family of sparse erasure codes on each layer, and is recovered by iteratively applying a peeling-decoding technique that enables a compact proof for data availability attack on any layer. Our algorithm enables any node to verify the full availability of any data block generated by the system by just downloading a byte block hash commitment and randomly sampling bytes, where b is the size of the data block. With the help of only one connected honest node in the system, our method also allows any node to verify any tampering of the coded Merkle tree by just downloading bytes. We provide a modular library for CMT in Rust and Python and demonstrate its efficacy inside the Parity Bitcoin client.
UR - http://www.scopus.com/inward/record.url?scp=85089214172&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089214172&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-51280-4_8
DO - 10.1007/978-3-030-51280-4_8
M3 - Conference contribution
AN - SCOPUS:85089214172
SN - 9783030512798
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 114
EP - 134
BT - Financial Cryptography and Data Security - 24th International Conference, FC 2020, Revised Selected Papers
A2 - Bonneau, Joseph
A2 - Heninger, Nadia
PB - Springer
Y2 - 10 February 2020 through 14 February 2020
ER -