Double Auction Meets Blockchain: Consensus from Scored Bid-Assignment

Xiangyu Su; Xavier Défago; Mario Larangeira; Kazuyuki Mori; Takuya Oda; Yasumasa Tamura; Keisuke Tanaka

Paper 2022/1471

Double Auction Meets Blockchain: Consensus from Scored Bid-Assignment

Xiangyu Su

, Institute of Science Tokyo

Xavier Défago, Institute of Science Tokyo

Mario Larangeira, Institute of Science Tokyo, Input Output, Global

Kazuyuki Mori, Mitsubishi Electric Corporation

Takuya Oda, Institute of Science Tokyo, The University of Kitakyushu

Yasumasa Tamura, Institute of Science Tokyo, Hokkaido University

Keisuke Tanaka, Institute of Science Tokyo

Abstract

A double auction system, where buyers and sellers trade through bids, requires a transparent and immutable mechanism to record allocation results. This demand can be met with robust ledgers that ensure persistence and liveness, as exemplified by the Bitcoin blockchain (EuroCrypt {'}15). While existing blockchain-aided auction systems often rely on secure smart contracts or layer- techniques, this work proposes a more fundamental approach by constructing a provably secure blockchain protocol directly from the computation of bid allocations. The core component is an alternative proof-of-work (PoW) scheme based on a scored generalized multiple assignment problem (SGMAP), integrated into a tailored blockchain protocol. Unlike conventional PoW-based protocols, our leader selection is driven by block scores derived from the SGMAP scoring function, which is designed to be flexible enough to define the difficulty level and accommodate real-life requirements of the underlying double auction system. We prove persistence and a modified liveness property for our design, and present implementation results to validate its robustness and practicality.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. 23nd International Conference on Applied Cryptography and Network Security (ACNS '25)
Keywords: Double Auctions Generalized Multiple Assignment Problem Alternative Proof-of-Work Blockchain Consensus.
Contact author(s): su x 4029 @ m isct ac jp
mario larangeira @ iohk io
keisuke @ comp isct ac jp
History: 2025-01-27: last of 3 revisions; 2022-10-27: received; See all versions
Short URL: https://ia.cr/2022/1471
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1471,
      author = {Xiangyu Su and Xavier Défago and Mario Larangeira and Kazuyuki Mori and Takuya Oda and Yasumasa Tamura and Keisuke Tanaka},
      title = {Double Auction Meets Blockchain: Consensus from Scored Bid-Assignment},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1471},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1471}
}