{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T09:27:54Z","timestamp":1775035674996,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Strategic Priority Research Program of Chinese Academy of Sciences","award":["XDB0690200"],"award-info":[{"award-number":["XDB0690200"]}]},{"name":"National Key Research and Development Program of China","award":["2023YFB4503203"],"award-info":[{"award-number":["2023YFB4503203"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62372447"],"award-info":[{"award-number":["62372447"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Data Availability Sampling (DAS) is a pivotal paradigm for addressing scalability challenges in blockchains. However, the predominant DAS schemes rely on KZG commitments, which necessitate a trusted setup. While the recently proposed FRIDA (Crypto\u201924) offers a transparent, FRI-based alternative, it suffers from large commitment sizes due to its restriction to the unique decoding radius. In this work, we generalize the protocol to the list decoding radius by leveraging the DEEP (Domain Extension for Eliminating Pretenders) technique. We provide a formal proof of the opening-consistency of the DEEP-FRI, established via the notion of\n                    <jats:italic>mutual correlated agreement<\/jats:italic>\n                    , instead of the weighted correlated agreement in the original DEEP-FRI protocol. In terms of efficiency, our scheme reduces the commitment size by a factor of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$1.2 \\sim 1.8\\times$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mn>1.2<\/mml:mn>\n                            <mml:mo>\u223c<\/mml:mo>\n                            <mml:mn>1.8<\/mml:mn>\n                            <mml:mo>\u00d7<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    while preserving the computational efficiency of both the prover and the verifier.\n                  <\/jats:p>","DOI":"10.1186\/s42400-026-00564-9","type":"journal-article","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T06:37:16Z","timestamp":1775025436000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deep-frida: transparent data availability sampling with smaller size"],"prefix":"10.1186","volume":"9","author":[{"given":"Ming","family":"Yang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2739-7656","authenticated-orcid":false,"given":"Xinxuan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Deng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,1]]},"reference":[{"key":"564_CR1","doi-asserted-by":"publisher","unstructured":"Al-Bassam M, Sonnino A, Buterin V, Khoffi I (2021) Fraud and data availability proofs: detecting invalid blocks in light clients. In: Borisov N, D\u00edaz C (eds.) FC 2021, Part II. LNCS, 12675, 279\u2013298. Springer, Virtual Event. https:\/\/doi.org\/10.1007\/978-3-662-64331-0_15","DOI":"10.1007\/978-3-662-64331-0_15"},{"key":"564_CR2","doi-asserted-by":"publisher","unstructured":"Arnon G, Chiesa A, Fenzi G, Yogev E (2025) WHIR: reed-solomon proximity testing with super-fast verification. In: Fehr S, Fouque P-A (eds.) EUROCRYPT 2025, Part IV. LNCS, 15604, 214\u2013243. Springer, Madrid, Spain . https:\/\/doi.org\/10.1007\/978-3-031-91134-7_8","DOI":"10.1007\/978-3-031-91134-7_8"},{"key":"564_CR3","doi-asserted-by":"publisher","unstructured":"Arnon G, Chiesa A, Fenzi G, Yogev E (2024) STIR: Reed-solomon proximity testing with fewer queries. In: Reyzin L, Stebila D (eds.) CRYPTO 2024, Part X. LNCS, 14929, 380\u2013413. Springer, Santa Barbara, CA, USA . DOI: https:\/\/doi.org\/10.1007\/978-3-031-68403-6_12","DOI":"10.1007\/978-3-031-68403-6_12"},{"key":"564_CR4","doi-asserted-by":"publisher","unstructured":"Arnon G, Chiesa A, Yogev E (2023) IOPs with inverse polynomial soundness error. In: 64th FOCS, pp. 752\u2013761. IEEE computer society press, Santa Cruz, CA, USA . https:\/\/doi.org\/10.1109\/FOCS57990.2023.00050","DOI":"10.1109\/FOCS57990.2023.00050"},{"key":"564_CR5","doi-asserted-by":"publisher","unstructured":"Ben-Sasson E, Goldberg L, Kopparty S, Saraf S (2020) DEEP-FRI: sampling outside the box improves soundness. In: Vidick T (ed.) ITCS 2020, 151, 5\u20131532. LIPIcs, Seattle, WA, USA . https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2020.5","DOI":"10.4230\/LIPIcs.ITCS.2020.5"},{"key":"564_CR6","doi-asserted-by":"publisher","unstructured":"Ben-Sasson E, Carmon D, Ishai Y, Kopparty S, Saraf S (2020) Proximity gaps for reed-solomon codes. In: 61st FOCS, 900\u2013909. IEEE computer society press, Durham, NC, USA . https:\/\/doi.org\/10.1109\/FOCS46700.2020.00088","DOI":"10.1109\/FOCS46700.2020.00088"},{"key":"564_CR7","unstructured":"Ben-Sasson E, Carmon D, Hab\u00f6ck U, Kopparty S, Saraf S (2025) On proximity gaps for reed-solomon codes. Cryptology ePrint archive, Paper 2025\/2055 . https:\/\/eprint.iacr.org\/2025\/2055"},{"key":"564_CR8","doi-asserted-by":"publisher","unstructured":"Ben-Sasson E, Chiesa A, Spooner N (2016) Interactive oracle proofs. In: Hirt M, Smith AD (eds.) TCC 2016-B, Part II. LNCS, 9986, 31\u201360. Springer, Beijing, China . DOI: https:\/\/doi.org\/10.1007\/978-3-662-53644-5_2","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"564_CR9","doi-asserted-by":"publisher","unstructured":"Ben-Sasson E, Bentov I, Horesh Y, Riabzev M (2018) Fast reed-solomon interactive oracle proofs of proximity. In: Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D (eds.) ICALP 2018. LIPIcs, 107, 14\u201311417. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Prague, Czech Republic . https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.14","DOI":"10.4230\/LIPIcs.ICALP.2018.14"},{"key":"564_CR10","unstructured":"Boneh D, Neu J, Nikolaenko V, Partap A (2025) Data availability sampling with repair. Cryptology ePrint archive, Report 2025\/1414 . https:\/\/eprint.iacr.org\/2025\/1414"},{"key":"564_CR11","unstructured":"Bordage S, Chiesa A, Guan Z, Manzur I (2025) All polynomial generators preserve distance with mutual correlated agreement. Cryptology ePrint archive, Paper 2025\/2051 . https:\/\/eprint.iacr.org\/2025\/2051"},{"key":"564_CR12","unstructured":"Crites E, Stewart A (2025) On reed-solomon proximity gaps conjectures. Cryptology ePrint archive, Paper 2025\/2046 . https:\/\/eprint.iacr.org\/2025\/2046"},{"key":"564_CR13","unstructured":"Diamond BE, Gruen A (2025) On the distribution of the distances of random words. Cryptology ePrint archive, Paper 2025\/2010 . https:\/\/eprint.iacr.org\/2025\/2010"},{"key":"564_CR14","unstructured":"Evans A, Mohnblatt N, Angeris G (2025) ZODA: Zero-overhead data availability. Cryptology ePrint archive, Report 2025\/034 . https:\/\/eprint.iacr.org\/2025\/034"},{"key":"564_CR15","unstructured":"Garreta A, Mohnblatt N, Wagner B (2025) A simplified round-by-round soundness proof of FRI. Cryptology ePrint archive, Paper 2025\/1993 . https:\/\/eprint.iacr.org\/2025\/1993"},{"key":"564_CR16","unstructured":"Goyal R, Guruswami V (2025) Optimal proximity gaps for subspace-design codes and (random) reed-solomon codes. Cryptology ePrint archive, Paper 2025\/2054 . https:\/\/eprint.iacr.org\/2025\/2054"},{"key":"564_CR17","unstructured":"Guo Y, Xiong AL, Qu W, Zhang J (2025) Data availability for thousands of nodes. Cryptology ePrint archive, Report 2025\/865 . https:\/\/eprint.iacr.org\/2025\/865"},{"key":"564_CR18","unstructured":"Hab\u00f6ck U (2025) A note on mutual correlated agreement for Reed-Solomon codes. Cryptology ePrint Archive, Paper 2025\/2110 . https:\/\/eprint.iacr.org\/2025\/2110"},{"key":"564_CR19","unstructured":"Hab\u00f6ck U (2022) A summary on the FRI low degree test. Cryptology ePrint archive, Paper 2022\/1216 . https:\/\/eprint.iacr.org\/2022\/1216"},{"issue":"4","key":"564_CR20","doi-asserted-by":"publisher","first-page":"34","DOI":"10.62056\/a09qudhdj","volume":"1","author":"M Hall-Andersen","year":"2024","unstructured":"Hall-Andersen M, Simkin M, Wagner B (2024b) Foundations of data availability sampling. CiC 1(4):34. https:\/\/doi.org\/10.62056\/a09qudhdj","journal-title":"CiC"},{"key":"564_CR21","doi-asserted-by":"publisher","unstructured":"Hall-Andersen M, Simkin M, Wagner B (2024a) FRIDA: data availability sampling from FRI. In: Reyzin L, Stebila D (eds.) CRYPTO 2024, Part VI. LNCS, 14925, 289\u2013324. Springer, Santa Barbara, CA, USA . https:\/\/doi.org\/10.1007\/978-3-031-68391-6_9","DOI":"10.1007\/978-3-031-68391-6_9"},{"key":"564_CR22","doi-asserted-by":"publisher","unstructured":"Kate A, Zaverucha GM, Goldberg I (2010) Constant-size commitments to polynomials and their applications. In: Abe M (ed.) ASIACRYPT 2010. LNCS, 6477, 177\u2013194. Springer, Singapore . https:\/\/doi.org\/10.1007\/978-3-642-17373-8_11","DOI":"10.1007\/978-3-642-17373-8_11"},{"key":"564_CR23","doi-asserted-by":"crossref","unstructured":"Minzer D, Zheng KZ (2025) Improved round-by-round soundness IOPs via Reed-Muller codes. Cryptology ePrint archive, Report 2025\/600 . https:\/\/eprint.iacr.org\/2025\/600","DOI":"10.1109\/FOCS63196.2025.00067"},{"issue":"2","key":"564_CR24","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0108018","volume":"8","author":"IS Reed","year":"1960","unstructured":"Reed IS, Solomon G (1960) Polynomial codes over certain finite fields. J Soc Ind Appl Math 8(2):300\u2013304. https:\/\/doi.org\/10.1137\/0108018","journal-title":"J Soc Ind Appl Math"},{"key":"564_CR25","unstructured":"Roadmap E (2025)(2025) Danksharding . https:\/\/ethereum.org\/roadmap\/danksharding\/"},{"key":"564_CR26","unstructured":"Ryan D (2023) PeerDAS: a simpler das approach using battle-tested p2p components . https:\/\/ethresear.ch\/t\/peerdas-a-simpler-das-approach-using-battle-tested-p2p-components\/16541"},{"key":"564_CR27","unstructured":"Yu M, Sahraei S, Li S, Avestimehr S, Kannan S, Viswanath P (2019) Coded Merkle tree: solving data availability attacks in blockchains. Cryptology ePrint archive, Report 2019\/1139 . https:\/\/eprint.iacr.org\/2019\/1139"},{"key":"564_CR28","doi-asserted-by":"publisher","unstructured":"Yu M, Sahraei S, Li S, Avestimehr S, Kannan S, Viswanath P (2020) Coded merkle tree: solving data availability attacks in blockchains. In: Bonneau J, Heninger N (eds.) FC 2020. LNCS, 12059, 114\u2013134. Springer, Kota Kinabalu, Malaysia. https:\/\/doi.org\/10.1007\/978-3-030-51280-4_8","DOI":"10.1007\/978-3-030-51280-4_8"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-026-00564-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-026-00564-9","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-026-00564-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T06:37:23Z","timestamp":1775025443000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s42400-026-00564-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,1]]},"references-count":28,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["564"],"URL":"https:\/\/doi.org\/10.1186\/s42400-026-00564-9","relation":{},"ISSN":["2523-3246"],"issn-type":[{"value":"2523-3246","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,1]]},"assertion":[{"value":"11 December 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interest"}}],"article-number":"145"}}