Rsmt2d - Go implementation of two dimensional Reed-Solomon merkle tree data availability scheme

Sharding
1

I’ve written an experimental Go library, rsmt2d, that implements a two dimensional Reed-Solomon merkle tree data availability scheme. It has a reparation algorithm with the ability to repair squares in a byzantine setting, detecting byzantine rows and columns and inconsistencies between rows and columns, and allows for the generation of fraud proofs.

Feel free to use for experimentation or pick it apart. I plan to experiment with this as a data availability proof layer for fraud proof-supporting blockchain data structures.

I did discover some intricacies around designing a square repair algorithm: for example, it is important to verify that the original data of each row/column matches the extended data, even if the whole row/column is available, because otherwise other clients might reject the block if they receive different pieces of a row/column than you, causing a fork.

2 Likes
2

@musalbas Can you explain more what this is, or point to some resources for me? What’s a Reed-Solomon merkle tree, just a merkle tree encoding a Reed-Solomon codeword? How does that make an availability scheme?

3

@josephjohnston Check out https://github.com/ethereum/research/wiki/A-note-on-data-availability-and-erasure-coding. Sorry, should’ve probably linked to that in the original post.

4

Talk to Geth-sharding. Pinging @rauljordan and @prestonvanloon.

Rust can be used with Go and other programming languages and vice versa.

https://doc.rust-lang.org/book/second-edition/ch19-01-unsafe-rust.html#using-extern-functions-to-call-external-code

I will consider this for Diamond Drops when we get up to data availability proofs.

5

Definitely interested in this. Thanks!