TY - GEN
T1 - Brief Announcement
T2 - 41st ACM Symposium on Principles of Distributed Computing, PODC 2022
AU - Alhaddad, Nicolas
AU - Das, Sourav
AU - Duan, Sisi
AU - Ren, Ling
AU - Varia, Mayank
AU - Xiang, Zhuolun
AU - Zhang, Haibin
N1 - Funding Information:
resultin(2)communicationcost.Weaddressthisbyfirstletting the client retrieve the vector of hashes, and then use the retrieved vector for the rest of the retrieval phase. Design of AVID. In the dispersal phase, first, the dispersing client encodes the message using a (, + 1) Reed-Solomon code (line 2) and computes a hash vector for the encoded message (line 3). The dispersing client then sends the -th symbol to the -th node, and reliably broadcasts using a balanced reliable broadcast protocol BalBRB from [2] (line 4). During the BalBRB, as per the predicate, the -th node checks whether the -th element of the hash vector that is being reliably broadcast, is equal to the hash of the symbol it received from the dispersing client (line 5-7). Let be the output of the validated RBC. Each node then encodes and compute ℎ = hash(). At the end of the dispersal phase, the -thnodeoutputs⟨,ℎ′,ℎ⟩where=⊥ifthe-thnodedidnot receive a valid symbol from the dispersing client, and ℎ′ is the -th encoding symbol of . The main idea of the retrieval phase is to let the retrieving client first recover the vector and then use it to validate symbols sent by nodes. More specifically, during the retrieval phase, the retrieving client sends RETRIEVE request to all nodes (line 13). Upon receiving RETRIEVE request from the retrieving client, each node waits till the dispersal phase terminates (line 30). The -th node then sends the message ⟨HASH,ℎ′,ℎ⟩ to the retrieving client (line 31). Additionally, if node received a symbol during the dispersal phase such that hash() = [], it sends a ⟨SYMBOL,⟩ to the retrieving client (line 32-33). The retrieving client upon receiving messages stores the symbols in ℎ and . The retrieving client then uses ℎ and the standard online error correction to recover (line 17-18). After recovering , the retrieving client uses it to retrieve the message. In particular, for every tuple (,) ∈ , it first checks whether hash() = [] and adds the tuple (,) to the set (line 19-21). The retrieving client waits till | |= + 1 and then interpolates the tuples in into a polynomial of degree at most (line 22-23). Let ′ be the interpolated polynomial. The client then checks if there exists any ∈ [] such that hash([]) ̸ []. If such exists, then the client outputs ⊥ and returns. Otherwise, the client outputs the Reed-Solomon decoding of ′ (line 28). Correctness. The proof can be found in the full version [1]. Lower bounds. In [1], we also prove that any deterministic protocol that solves AVID must incur a communication cost of Ω(||+2) during the dispersal phase in at least one execution, and Ω(||+) during retrieval in at least one execution. Acknowledgments. This work is supported by NSF (1718135, 1801564, 1915763, 1931714, 2143058), DARPA (HR00112020021, N66001-15-C-4071), Tsinghua Independent Research Program, National Key Research and Development Program of China (2018YFA0704701), National Financial Cryptography Research Center, Shandong Provincial Key Research and Development Program (2021CXGC010106), and Teli Youth Scholarship.
Publisher Copyright:
© 2022 Owner/Author.
PY - 2022/7/20
Y1 - 2022/7/20
N2 - We present a near-optimal asynchronous verifiable information dispersal (AVID) protocol. The total dispersal cost of our AVID protocol is O(|M| + κ n^2), and the retrieval cost per client is O(|M| + κ n). Unlike prior works, our AVID protocol only assumes the existence of collision-resistant hash functions. Also, in our AVID protocol, the dispersing client incurs a communication cost of O(|M|+κ n) in comparison to O(|M|+κ n łog n) of prior best. Moreover, each node in our AVID protocol incurs a storage cost of O(|M|/n + κ) bits, in comparison to O(|M|/n + κ łog n) bits of prior best. Finally, we present lower bound results on communication cost and show that our AVID protocol has near-optimal communication costs - only a factor of O(κ) gap from the lower bounds.
AB - We present a near-optimal asynchronous verifiable information dispersal (AVID) protocol. The total dispersal cost of our AVID protocol is O(|M| + κ n^2), and the retrieval cost per client is O(|M| + κ n). Unlike prior works, our AVID protocol only assumes the existence of collision-resistant hash functions. Also, in our AVID protocol, the dispersing client incurs a communication cost of O(|M|+κ n) in comparison to O(|M|+κ n łog n) of prior best. Moreover, each node in our AVID protocol incurs a storage cost of O(|M|/n + κ) bits, in comparison to O(|M|/n + κ łog n) bits of prior best. Finally, we present lower bound results on communication cost and show that our AVID protocol has near-optimal communication costs - only a factor of O(κ) gap from the lower bounds.
KW - asynchronous networks
KW - asynchronous verifiable information dispersal
KW - communication complexity
KW - lower bounds
UR - http://www.scopus.com/inward/record.url?scp=85135302521&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85135302521&partnerID=8YFLogxK
U2 - 10.1145/3519270.3538476
DO - 10.1145/3519270.3538476
M3 - Conference contribution
AN - SCOPUS:85135302521
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 418
EP - 420
BT - PODC 2022 - Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
Y2 - 25 July 2022 through 29 July 2022
ER -