Saeid Sahraei

Saeid Sahraei, Salman Avestimehr, Ramy E. Ali

We introduce Info-Commit, an information-theoretic protocol for polynomial commitment and verification. With the help of a trusted initializer, a succinct commitment to a private polynomial $f$ is provided to the user. The user then queries the server to obtain evaluations of $f$ at several inputs chosen by the user. The server provides the evaluations along with proofs of correctness which the user can verify against the initial commitment. Info-Commit has four main features. Firstly, the user is able to detect, with high probability, if the server has responded with evaluations of the same polynomial initially committed to. Secondly, Info-Commit provides rigorous privacy guarantees for the server: upon observing the initial commitment and the response provided by the server to $m$ evaluation queries, the user only learns $O(m^2)$ symbols about the coefficients of $f$. Thirdly, the verifiability and the privacy guarantees are unconditional regardless of the computational power of the two parties. Lastly, Info-Commit is doubly-efficient in the sense that in the evaluation phase, the user runs in $O(\sqrt{d})$ time and the server runs in $ O(d)$ time, where $d-1$ is the degree of the polynomial $f$.

Mingchao Yu, Saeid Sahraei, Songze Li et al.

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 $Θ(1)$ byte block hash commitment and randomly sampling $Θ(\log b)$ 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 $Θ(\log b)$ bytes. We provide a modular library for CMT in Rust and Python and demonstrate its efficacy inside the Parity Bitcoin client.

Saeid Sahraei, Mohammad Ali Maddah-Ali, Salman Avestimehr

Cloud computing platforms have created the possibility for computationally limited users to delegate demanding tasks to strong but untrusted servers. Verifiable computing algorithms help build trust in such interactions by enabling the server to provide a proof of correctness of his results which the user can check very efficiently. In this paper, we present a doubly-efficient interactive algorithm for verifiable polynomial evaluation. Unlike the mainstream literature on verifiable computing, the soundness of our algorithm is information-theoretic and cannot be broken by a computationally unbounded server. By relying on basic properties of error correcting codes, our algorithm enforces a dishonest server to provide false results to problems which become progressively easier to verify. After roughly $\log d$ rounds, the user can verify the response of the server against a look-up table that has been pre-computed during an initialization phase. For a polynomial of degree $d$, we achieve a user complexity of $O(d^ε)$, a server complexity of $O(d^{1+ε})$, a round complexity of $O(\log d)$ and an initialization complexity of $O(d^{1+ε})$.

Songze Li, Saeid Sahraei, Mingchao Yu et al.

We introduce an information-theoretic framework, named Coded State Machine (CSM), to securely and efficiently execute multiple state machines on untrusted network nodes, some of which are Byzantine. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. We propose CSM, which achieves the optimal linear scaling in storage efficiency, throughput, and security simultaneously with the size of the network. The storage efficiency is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest. Using INTERMIX, the network nodes securely delegate their coding operations to a single worker node, and a small group of randomly selected auditor nodes verify its correctness, so that computational efficiency can scale almost linearly with the network size, without compromising on security.

Saeid Sahraei, A. Salman Avestimehr

We study the problem of verifiable polynomial evaluation in the user-server and multi-party setups. We propose {INTERPOL}, an information-theoretically verifiable algorithm that allows a user to delegate the evaluation of a polynomial to a server, and verify the correctness of the results with high probability and in sublinear complexity. Compared to the existing approaches which typically rely on cryptographic assumptions, {INTERPOL} stands out in that it does not assume any computational limitation on the server. {INTERPOL} relies on decomposition of polynomial evaluation into two matrix multiplications, and injection of computation redundancy in the form of locally computed parities with secret coefficients for verification. We show that {INTERPOL} has several desirable properties such as adaptivity and public verifiability. Furthermore, by generalizing {INTERPOL} to a multi-party setting consisting of a network of $n$ untrusted nodes, where each node is interested in evaluating the same polynomial, we demonstrate that we can achieve an overall computational complexity comparable to a trusted setup, while guaranteeing information-theoretic verification at each node.