2023-09-13 Audit Report Celestia rsmt2d library

Security Audit Report

Celestia: Q2 2023

Authors: Ivan Gavran, Andrija Mitrovic

Table of Contents Audit overview............................................................................................................. 1 The Project 1 Conclusions 1 Further Increasing Confidence 1 Disclaimer 1 Audit dashboard.......................................................................................................... 3 Target Summary 3 Engagement Summary 3 Severity Summary 3 System overview ......................................................................................................... 4 Abstract 4 Data Structure 4 Extending data 5 Reconstruction of data 6 Identified Threats and Audit Plan .............................................................................. 8 Threats 8 Audit Plan 8 Findings ....................................................................................................................... 9 ErrByzantineData.Shares are not filled 11 OR instead AND should be used in the test check 13 Check chunk size 14 Position and dimensions of row/column slice is not checked 15 Good coding practice 16 Unnecessary index calculation 17 Code duplication 18 Wrong comment for ErrByzabtineData 19 Good naming practice 20 Unused attribute in test 21 Comments about extending data are wrong 22 Naming of test cases is confusing 23 © 2023 Informal Systems Celestia: Q2 2023

Use ErrUnevenChunks error 24 Unnecessary usage of errors.As instead errors.Is 25 Introduce a new variable for clarity 26 Appendix: Vulnerability Classification ..................................................................... 27 Impact Score 27 Exploitability Score 27 Severity Score 28 © 2023 Informal Systems Celestia: Q2 2023

Audit overview

The Project In June 2023, Informal Systems has conducted a security audit for Celestia of the library rsmt2d. The main focus of the audit was the correctness and functionality of the library and its integration with other repositories of Celestia (celastia-node and celestia-app). The audited commit hash is 6515446b. The audit took place from June 1, 2023 through June 29, 2023 by the following personnel: • Ivan Gavran • Andrija Mitrovic

Conclusions In general, we found the codebase to be of very high quality: the code is well structured and easy to follow, and all functions contain good unit-tests. Repository does not have adequate specs, so those should be added. In the audit, we found 15 issues: most of them informational and one high severity, which was promptly addressed.

Further Increasing Confidence For increasing confidence further, we would suggest enumerating all possible scenarios of the rsmt2d workflow and adding a test for each of them. Those tests go beyond unit tests as they need to include the interplay between different functions. (For instance, a scenario describing the situation in which an encoding error is detected in columns while rebuilding rows would have detected one of the problems found in this audit.)

Disclaimer This report is subject to the terms and conditions (including without limitation, description of services, confidentiality, disclaimer and limitation of liability, etc.) set forth in the associated Services Agreement. This report provided in connection with the Services set forth in the Services Agreement shall be used by the Company only to the extent permitted under the terms and conditions set forth in the Agreement. This audit report is provided on an “as is” basis, with no guarantee of the completeness, accuracy, timeliness or of the results obtained by use of the information provided. Informal has relied upon information and data provided by the client, and is not responsible for any errors or omissions in such information and data or results obtained from the use of that information or conclusions in this report. Informal makes no warranty of any kind, express or implied, regarding the accuracy, adequacy, validity, reliability, availability or completeness of this report. This report should not be considered or utilized as a complete assessment of the overall utility, security or bug free status of the code. This audit report contains confidential information and is only intended for use by the client. Reuse or republication of the audit report other than as authorized by the client is prohibited. This report is not, nor should it be considered, an “endorsement”, “approval” or “disapproval” of any particular project or team. This report is not, nor should it be considered, an indication of the economics or value of any “product” or “asset” created by any team or project that contracts with Informal to perform a security assessment. This report does not provide any warranty or guarantee regarding the absolute bug-free nature of the technology analyzed, nor does it provide any indication of the client’s business, business model or legal compliance. This report should not be used in any way to make decisions around investment or involvement with any particular project. This report in no way provides investment advice, nor should it be leveraged as investment advice of any sort.

Blockchain technology and cryptographic assets in general and by definition present a high level of ongoing risk. Client is responsible for its own due diligence and continuing security in this regard.

Audit dashboard Target Summary • Type: Specification and Implementation • Platform: Golang • Artifacts: • rsmt2d

Engagement Summary • Dates: 01.06.2023 to 29.06.2023 • Method: Manual code review, protocol analysis • Employees Engaged: 2

Severity Summary Finding Severity #

Critical 0

High 1

Medium 0

Low 1

Informational 13

Total 15

System overview Abstract Rsmt2d is a library utilized for the erasure coding of data in Celestia. It serves as a specialized package offering functionalities to reorganize data into a square shape, expand it, and apply erasure coding to the original square data. Additionally, it incorporates the capacity to repair or restore incomplete data based on the underlying erasure coding technique. Furthermore, it provides proofs of tampered data, which play a vital role in ensuring data availability within the Celestia platform. The Leopard codec serves as the underlying coding mechanism for Reed-Solomon erasure coding. Originally implemented in the C++ library, Leopard is now utilized by Rsmt2d through a Go port of the C++ library. For shards of 256 or less, the Leopard codec uses an 8-bit implementation, whereas shards exceeding 256 employ a 16-bit version of Leopard.

Data Structure The Rsmt2d library is designed around a squared data structure for efficient data availability workflow. It uses two main structures: dataSquare and extendedDataSquare . The dataSquare structure serves as the foundation and provides the necessary functionality for storing data in a square format. On the other hand, the extendedDataSquare structure inherits from dataSquare and adds extra capabilities to provide necessary functionality for rsmt2d library.

Data Square (DS) As a base data structure used for storing data, a data square is utilized. This data square is implemented by a struct dataSquare which is as follows:

type dataSquare struct { squareRow [][][]byte // row-major squareCol [][][]byte // col-major dataMutex sync.Mutex width uint chunkSize uint rowRoots [][]byte colRoots [][]byte createTreeFn TreeConstructorFn }

DS is a matrix where each cell is a byte array. It contains duplicated data arranged in both row-major and column- major order. This duplication allows for zero-allocation column slices to be provided. It also stores data about the width of the square, chunk size, roots by rows and columns and a delegate to tree constructor that is used for root calculation. All chunks/cells within the data square must be of the same size. The provided functionality of the Data square is as follows:

• Creation of Data Square ( newDataSquare ): Rearranges the given data array into a square and creates a dataSquare object. • Extending Data Square ( extendSquare ): Extends the original square horizontally and vertically by a predefined number of rows/columns and fills it with the same fillerChunk . • Accessing Cells ( GetCell , SetCell , setCell ): Allows reading/writing data from/into cells.

• Accessing Row/Column Slices ( rowSlice , row , setRowSlice , colSlice, col, setColSlice ) : Enables reading/writing data from/into row/column slices. • Accessing Roots ( resetRoots , computeRoots , getRowRoots , getRowRoot , getColRoots, getColRoot ): Provides functionality for resetting, computing, and reading row/column roots.

Extended Data Square (EDS) The Extended data square is a data structure that inherits the DS (data square) data type and represents an extended portion of data. Its structure is as follows:

type ExtendedDataSquare struct { *dataSquare codec Codec originalDataWidth uint }

It includes a pointer to the DS struct and introduces additional attributes, codec and originalDataWidth . The codec attribute represents the codec used for encoding/decoding data (as mention, rsmt2d library uses the Leopard codec). The originalDataWidth field is used to store information about the width of the original data square. The provided functionality of the Extended data square is as follows:

• Compute EDS ( ComputeExtendedDataSquare ): This function computes the extended data square for a given set of data chunks. • Import EDS ( ImportExtendedDataSquare ): This function imports an extended data square that is represented as flattened chunks of data. • Gets row/column ( Row , Col ): These functions return a copy of the internal slice, which represents a row or column slice of the extended data square. • Gets row/column roots ( RowRoots , ColRoots ): These functions return the Merkle roots of all the rows or columns within the extended data square.

Extending data Extending data is a part of the Reed Solomon encoding process. The original data square, named Q0, is extended to three more parity data squares: Q1, Q2, and Q3. These squares are filled with encoded original data. The functionality for this process is provided in the function called ComputeExtendedDataSquare .

The process of computing the extended data square with an array of data chunks is as follows (see figure for Erasure extending of the original data square):

Create a new data square ( ds ) from the provided array of data. This serves as the original data square.
Create an extended data square ( eds ) from the created ds in the previous step.
Perform erasure extending on the created eds : a. Extend the original data square to Q1, Q2, and Q3, filling them with empty data chunks. b. Fill Q1 and Q2 with erasure coded data. Q1 is the result of erasure coding Q0 row by row, and Q2 is the result of erasure coding Q0 column by column. c. Fill Q3 with erasure coded data. Q3 is the result of erasure coding Q2 row by row (it will be the same if Q3 is the result of erasure coding Q1 column by column).

Note that while the data is laid out in a two-dimensional square, the rows and columns are erasure coded using a standard one-dimensional encoding.

original data parity data

parity data parity data

Erasure extending of original data square

Reconstruction of data The reconstruction of the incomplete extended data square (EDS) is performed in the function Repair. This function continuously compares the repaired rows and columns against the expected Merkle roots. To ensure proper functioning, the missing shares must be set to nil .

The process of repairing is as follows:

A sanity check is performed ( prerepairSanityCheck ), which includes the following checks: a. Verify that the row/column roots from EDS are equal to the expected row/column roots. b. Check if the encoded original data from the row/column is equal to the extended erasure data from EDS.
Iterative solving of crossword ( solveCrossword ).

Solving the crossword involves looping through each row and column in an attempt to rebuild any incomplete rows or columns. This process is repeated until one of the following conditions is met:

The square is solved.
An error is returned from solving rows or columns.
No progress is made. When solving a row/column, if it is completed, a check is performed against the expected Merkle roots (check for rows, check for columns). Additionally, a check for a completed orthogonal column/row is also performed. If the

calculated root for a newly completed row/column does not match the expected Merkle root, an ErrByzantineData error is returned.

This error is defined as follows:

type ErrByzantineData struct { Axis Axis // Axis of the data. Index uint // Row/Col index. Shares [][]byte // Pre-repaired shares. Missing shares are nil. }

Identified Threats and Audit Plan In this audit of the rsmt2d library, we were looking at the library from two angles:

logic within the library itself
usages of the library functions in the broader Celestia context (be it in celestia-node or celestia- app )

Threats We identified the following threats to the chain stemming from the rsmt2d library:

Wrong usage of the encoding library, resulting in the extended data that does not have the desired recoverability properties.
Problems in the logic for recovering shares from pieces of data. If those problems exist, this would result in full nodes not being able to recover existing data, violating security assumptions of light-nodes.
Problems in sending and validating bad encoding proofs. If this is not done correctly, it could result in a) mistakenly blacklisting an honest peer, or b) accepting a fraudulent bad encoding proof.

Audit Plan We set out to explore the following:

Inspection of how the data square is extended.
Inspection of updates of squareRow and squareCol , two independent variables that are referring to the same data. They have to be updated in sync.
A special attention is given to the function solveCrossword , inspecting termination and correctness of a rebuild process
Review of construction of ErrByzantineData , its transformation into a BadEncodingProof , and its validation in the Validate function.
Making sure that data is never changed without changing the corresponding roots.
Making sure that all assumptions are checked at all relevant places (e.g., chunk size, row/column indices within bounds, etc.)

Findings Title Type Severity Issue

ErrByzantineData.Shares are not filled PROTOCOL 3 HIGH https://github.com/ celestiaorg/rsmt2d/ issues/178

OR instead AND should be used IMPLEMENTATION 1 LOW https://github.com/ in the test check celestiaorg/rsmt2d/ issues/162

Use ErrUnevenChunks error IMPLEMENTATION 0 INFORMATIONAL https://github.com/ celestiaorg/rsmt2d/ issues/163

Unnecessary index calculation IMPLEMENTATION 0 INFORMATIONAL https://github.com/ celestiaorg/rsmt2d/ issues/164

Position and dimensions of row/ IMPLEMENTATION 0 INFORMATIONAL https://github.com/ column slice is not checked celestiaorg/rsmt2d/ issues/169

Check chunk size IMPLEMENTATION 0 INFORMATIONAL https://github.com/ celestiaorg/rsmt2d/ issues/170

Code duplication PRACTICE 0 INFORMATIONAL https://github.com/ celestiaorg/rsmt2d/ issues/171

Wrong comment for ErrByzabtineData DOCUMENTATION 0 INFORMATIONAL https://github.com/ celestiaorg/rsmt2d/ issues/173

Good coding practice PRACTICE 0 INFORMATIONAL https://github.com/ celestiaorg/rsmt2d/ issues/177

Good naming practice PRACTICE 0 INFORMATIONAL https://github.com/ celestiaorg/rsmt2d/ issues/179

Unused attribute in test IMPLEMENTATION 0 INFORMATIONAL https://github.com/ celestiaorg/rsmt2d/ issues/180

Title Type Severity Issue

Comments about extending data are DOCUMENTATION 0 INFORMATIONAL https://github.com/ wrong celestiaorg/rsmt2d/ issues/192

Naming of test cases is confusing DOCUMENTATION 0 INFORMATIONAL https://github.com/ celestiaorg/rsmt2d/ issues/194

Unnecessary usage of errors.As IMPLEMENTATION 0 INFORMATIONAL https://github.com/ instead errors.Is celestiaorg/celestia- node/issues/2391

Introduce a new variable for clarity PRACTICE 0 INFORMATIONAL https://github.com/ celestiaorg/celestia- node/issues/2392

ErrByzantineData.Shares are not filled Title ErrByzantineData.Shares are not filled

Project Celestia: Q2 2023

Type PROTOCOL

Severity 3 HIGH

Impact 2 MEDIUM

Exploitability 3 HIGH

Issue https://github.com/celestiaorg/rsmt2d/issues/178

Involved artifacts • rsmt2d/extendeddatacrossword.go

Description When ErrByznatineData is raised it is propagated through solveCrossword , Repair , Reconstruct , and Retrieve , where a new ErrByzantine is created. If the ErrByzantineData.Shares field is not filled, GetProofsForShares will return an empty sequence of sharesWithProof , and ErrByzantine is created with that empty sequence sharesWithProof . This is further propagated through GetEDS, SharesAvailable, sample; until a new BadEncodingProof is created, and which will end up propagated (the byzantine error is captured in SharesAvailable) to other nodes. Finally, when such a proof is received by other nodes, they call Validate on it. Since p.Shares is an empty array, an error will be raised upon checking the size of p.Shares , here.

ErrByzantineData.Shares are not set when verification of newly completed orthogonal vectors returns a ErrByzantineData error (first place and second place) that will lead to the previously mentioned flow. On the contrary, these shares are set if a verification of newly completed row or column returns ErrByzantineData error.

Problem Scenarios The byzantine error for data will not be processed properly even if proven. Furthermore, honest peers can get blacklisted.

Recommendation Fill in the shares with corresponding column or row data if the verification of that newly completed orthogonal column or row returns an ErrByzantineData .

Status Resolved.

OR instead AND should be used in the test check Title OR instead AND should be used in the test check

Project Celestia: Q2 2023

Type IMPLEMENTATION

Severity 1 LOW

Impact 2 MEDIUM

Exploitability 1 LOW

Issue https://github.com/celestiaorg/rsmt2d/issues/162

Involved artifacts • rsmt2d/datasquare_test.go

Description The test TestLazyRootGeneration calculates root by root for each row and column and appends those to local arrays of roots. In the end, it compares these arrays with those that are calculated by extendedDataSquare function computeRoots . Test is supposed to fail if at least one of the root arrays is not equal to the expected value, but the check at the end of the test will lead to failure only if both of root arrays are not equal to the ones from EDS.

Problem Scenarios Test will pass if one of the root arrays does not fit the criteria, but it should fail.

Recommendation At the end of test if statement should check if any of the root arrays has changed and then return an error. Thus or instead of and should be used.

Status Resolved.

Check chunk size Title Check chunk size

Project Celestia: Q2 2023

Type IMPLEMENTATION

Severity 0 INFORMATIONAL

Impact 2 MEDIUM

Exploitability 0 NONE

Excerpt (19997 of 37699 characters). Read the whole page on informalsystems/audits ↗

← Back to Documentation