{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T05:38:02Z","timestamp":1770356282377,"version":"3.49.0"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031477508","type":"print"},{"value":"9783031477515","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,1]],"date-time":"2023-12-01T00:00:00Z","timestamp":1701388800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Blockchain-based payment systems utilize an append-only log of transactions whose correctness can be verified by any observer. Classically, verification costs grow linearly in either the number of transactions or blocks in the blockchain (often both). Incrementally Verifiable Computation (IVC) can be used to enable constant-time verification, but generating the necessary proofs is expensive. We introduce the notion of Proof of Necessary Work (PoNW), in which proof generation is an integral part of the proof-of-work used in Nakamoto consensus, producing proofs using energy that would otherwise be wasted. We implement and benchmark a prototype of our system, enabling stateless clients to verify the entire blockchain history in about 40 milliseconds.<\/jats:p>","DOI":"10.1007\/978-3-031-47751-5_2","type":"book-chapter","created":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T17:02:23Z","timestamp":1701363743000},"page":"18-35","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Proof of\u00a0Necessary Work: Succinct State Verification with\u00a0Fairness Guarantees"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-5042-9023","authenticated-orcid":false,"given":"Assimakis","family":"Kattis","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6349-0145","authenticated-orcid":false,"given":"Joseph","family":"Bonneau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,1]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Abusalah, H., Fuchsbauer, G., Ga\u017ei, P., Klein, K.: SNACKs: leveraging proofs of sequential work for blockchain light clients. Cryptology ePrint Archive, Paper 2022\/240 (2022)","DOI":"10.1007\/978-3-031-22963-3_27"},{"key":"2_CR2","unstructured":"Announcing the ZPrize Competition. https:\/\/www.aleo.org\/post\/announcing-the-zprize-competition (2022). Accessed: 09 Aug 2022"},{"key":"2_CR3","unstructured":"Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von neumann architecture. In: USENIX Security (2014)"},{"issue":"4","key":"2_CR4","doi-asserted-by":"publisher","first-page":"1102","DOI":"10.1007\/s00453-016-0221-0","volume":"79","author":"E Ben-Sasson","year":"2017","unstructured":"Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Scalable zero knowledge via cycles of elliptic curves. Algorithmica 79(4), 1102\u20131160 (2017)","journal-title":"Algorithmica"},{"key":"2_CR5","unstructured":"Bonneau, J., Meckler, I., Rao, V., Shapiro, E.: Mina: decentralized cryptocurrency at scale. https:\/\/docs.minaprotocol.com\/static\/pdf\/technicalWhitepaper.pdf (2020). Accessed: 09 Aug 2022"},{"key":"2_CR6","unstructured":"Bowe, S., Chiesa, A., Green, M., Miers, I., Mishra, P., Wu, H.: ZEXE: enabling decentralized private computation. Cryptology ePrint Archive, Report 2018\/962 (2018)"},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-030-51280-4_23","volume-title":"Financial Cryptography and Data Security","author":"B B\u00fcnz","year":"2020","unstructured":"B\u00fcnz, B., Agrawal, S., Zamani, M., Boneh, D.: Zether: towards privacy in a smart contract world. In: Bonneau, J., Heninger, N. (eds.) FC 2020. LNCS, vol. 12059, pp. 423\u2013443. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51280-4_23"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"B\u00fcnz, B., Kiffer, L., Luu, L., Zamani, M.: Flyclient: super-light clients for cryptocurrencies. cryptology ePrint Archive, Report 2019\/226 (2019)","DOI":"10.1109\/SP40000.2020.00049"},{"key":"2_CR9","unstructured":"Chatzigiannis, P., Baldimtsi, F., Chalkias, K.: SoK: Blockchain Light Clients. Cryptology ePrint Archive, Paper 2021\/1657 (2021)"},{"key":"2_CR10","unstructured":"Chen, W., Chiesa, A., Dauterman, E., Ward, N.P.: Reducing participation costs via incremental verification for ledger systems. Cryptology ePrint Archive, Paper 2020\/1522 (2020)"},{"key":"2_CR11","unstructured":"Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, P., Ward, N.: Marlin: preprocessing zksnarks with universal and updatable SRS. Cryptology ePrint Archive, Paper 2019\/1047 (2019). https:\/\/eprint.iacr.org\/2019\/1047"},{"key":"2_CR12","unstructured":"Dahari, H., Lindell, Y.: Deterministic-prover zero-knowledge proofs. Cryptology ePrint Archive, Paper 2020\/141 (2020)"},{"key":"2_CR13","unstructured":"Damg\u00e5rd, I.B., Pedersen, T.P., Pfitzmann, B.: On the existence of statistically hiding bit commitment schemes and fail-stop signatures. In: CRYPTO (1993)"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"77","DOI":"10.4064\/aa-6-1-77-81","volume":"6","author":"P Erd\u00f6s","year":"1960","unstructured":"Erd\u00f6s, P.: Remarks on number theory III. On addition chains. Acta Arithmetica 6, 77\u201381 (1960)","journal-title":"Acta Arithmetica"},{"key":"2_CR15","unstructured":"Fisch, B., Bonneau, J., Greco, N., Benet, J.: Scaling proof-of-replication for Filecoin mining. Stanford University, Technical Report (2018)"},{"issue":"1","key":"2_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jagm.1997.0913","volume":"27","author":"DM Gordon","year":"1998","unstructured":"Gordon, D.M.: A survey of fast exponentiation methods. J. Algorithms 27(1), 129\u2013146 (1998)","journal-title":"J. Algorithms"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Groth, J.: On the size of pairing-based non-interactive arguments. In: Eurocrypt (2016)","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Hegde, P., Streit, R., Georghiades, Y., Ganesh, C., Vishwanath, S.: Achieving almost all blockchain functionalities with polylogarithmic storage. arXiv preprint arXiv:2207.05869 (2022)","DOI":"10.1007\/978-3-031-18283-9_32"},{"key":"2_CR19","unstructured":"Henry, R.: Pippenger\u2019s multiproduct and multiexponentiation algorithms. University of Waterloo, Technical Report (2010)"},{"key":"2_CR20","unstructured":"Kamvar, S., Olszewski, M., Reinsberg, R.: CELO: a multi-asset cryptographic protocol for decentralized social payments. https:\/\/celo.org\/papers\/whitepaper (2019)"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Asiacrypt (2010)","DOI":"10.1007\/978-3-642-17373-8_11"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Kiayias, A., Lamprou, N., Stouka, A.P.: Proofs of proofs of work with sublinear complexity. In: Financial Crypto (2016)","DOI":"10.1007\/978-3-662-53357-4_5"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: CRYPTO (2017)","DOI":"10.1007\/978-3-319-63688-7_12"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Leung, D., Suhl, A., Gilad, Y., Zeldovich, N.: Vault: fast bootstrapping for the algorand cryptocurrency. In: NDSS (2018)","DOI":"10.14722\/ndss.2019.23313"},{"key":"2_CR25","doi-asserted-by":"crossref","unstructured":"Maurer, U.: Abstract models of computation in cryptography. In: IMA International Conference on Cryptography and Coding (2005)","DOI":"10.1007\/11586821_1"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Miller, A., Kosba, A., Katz, J., Shi, E.: Nonoutsourceable scratch-off puzzles to discourage bitcoin mining coalitions. In: ACM CCS (2015)","DOI":"10.1145\/2810103.2813621"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Parno, B., Gentry, C., Howell, J., Raykova, M.: Pinocchio: nearly practical verifiable computation. Cryptology ePrint Archive, Report 2013\/279 (2013)","DOI":"10.1109\/SP.2013.47"},{"issue":"2","key":"2_CR28","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1137\/0209022","volume":"9","author":"N Pippenger","year":"1980","unstructured":"Pippenger, N.: On the evaluation of powers and monomials. SIAM J. Comput. 9(2), 230\u2013250 (1980)","journal-title":"SIAM J. Comput."},{"key":"2_CR29","unstructured":"Poelstra, A.: Mimblewimble. https:\/\/download.wpsoftware.net\/bitcoin\/wizardry\/mimblewimble.pdf (2016). Accessed 09 Aug 2022"},{"key":"2_CR30","unstructured":"Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Eurocrypt (1989)"},{"key":"2_CR31","unstructured":"SCIPRLab: libsnark: a c++ library for zksnark proofs. https:\/\/github.com\/scipr-lab\/libsnark (2017)"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Eurocrypt (1997)","DOI":"10.1007\/3-540-69053-0_18"},{"key":"2_CR33","unstructured":"Vesely, P., et al.: Plumo: an ultralight blockchain client. Cryptology ePrint Archive, Paper 2021\/1361 (2021)"},{"key":"2_CR34","unstructured":"Wu, H., Zheng, W., Chiesa, A., Popa, R.A., Stoica, I.: DIZK: a distributed zero knowledge proof system. In: USENIX Security (2018)"},{"key":"2_CR35","doi-asserted-by":"crossref","unstructured":"Zhandry, M.: To label, or not to label (in generic groups). Cryptology ePrint Archive, Paper 2022\/226 (2022)","DOI":"10.1007\/978-3-031-15982-4_3"}],"container-title":["Lecture Notes in Computer Science","Financial Cryptography and Data Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-47751-5_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T17:04:47Z","timestamp":1701363887000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-47751-5_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,1]]},"ISBN":["9783031477508","9783031477515"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-47751-5_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,1]]},"assertion":[{"value":"1 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Financial Cryptography and Data Security","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bol, Bra\u010d","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Croatia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 May 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 May 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fc2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/fc23.ifca.ai\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"182","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.5","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"For the workshops 7 full papers have been accepted from 18 submissions.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}