CompactChain: an efficient stateless chain for UTXO-model blockchain

doi:10.1007/s11704-023-2365-9

Front. Comput. Sci.

2024, Vol. 18

Issue (2) : 182806 https://doi.org/10.1007/s11704-023-2365-9

Information Security

CompactChain: an efficient stateless chain for UTXO-model blockchain

B Swaroopa REDDY, T Uday Kiran REDDY(

)

Department of Electrical Engineering, Indian Institute of Technology Hyderabad, Hyderabad, Telangana 502285, India

Download: PDF(8422 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

In this work, we propose a stateless blockchain called CompactChain, which compacts the entire state of the UTXO (Unspent Transaction Output) based blockchain systems into two RSA accumulators. The first accumulator is called Transaction Output (TXO) commitment which represents the TXO set. The second one is called Spent Transaction Output (STXO) commitment which represents the STXO set. In this work, we discuss three algorithms: (i) To update the TXO and STXO commitments by the miner. The miner also provides the proofs for the correctness of the updated commitments; (ii) To prove the transaction’s validity by providing a membership witness in TXO commitment and non-membership witness against STXO commitment for a coin being spent by a user; (iii) To update the witness for the coin that is not yet spent; The experimental results evaluate the performance of the CompactChain in terms of time taken by a miner to update the commitments and time taken by a validator to verify the commitments and validate the transactions. We compare the performance of CompactChain with the existing state-of-the-art works on stateless blockchains. CompactChain shows a reduction in commitments update complexity and transaction witness size which inturn reduces the mempool size and propagation latency without compromising the system throughput (Transactions per second (TPS)).

Keywords stateless blockchain RSA Accumulator STXO commitment TXO commitment UTXO Non-interactive Proof of Exponentiation (NI-PoE) Transactions per second (TPS)

Corresponding Author(s): T Uday Kiran REDDY

Just Accepted Date: 02 February 2023 Issue Date: 13 April 2023

Cite this article:

B Swaroopa REDDY,T Uday Kiran REDDY. CompactChain: an efficient stateless chain for UTXO-model blockchain[J]. Front. Comput. Sci., 2024, 18(2): 182806.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-023-2365-9
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I2/182806

Symbols	Description
$B n$	Block at height $n$
$T n$	Set of all transactions in $B n$
TXO set	Set of all transaction outputs
STXO set	Set of all spent transaction outputs
$T X O n$	Transaction outputs (TXOs) in $B n$
$S T X O n$	Spent Transaction outputs (STXOs) in $B n$
$T X O k : n$	All TXOs from block $B k$ to block $B n$
$S T X O k : n$	All STXOs from block $B k$ to block $B n$
$T X O_C n$	Commitment to TXO set in block $B n$
$S T X O_C n$	Commitment to STXO set in block $B n$
$Π T X O$	NI-PoE proof for $T X O_C n$
$Π S T X O$	NI-PoE proof for $S T X O_C n$
$w n (x)$	Membership witness to prove $x ∈$ TXO set
$u n (x)$	Non-membership witness to prove
	$x ∉$ STXO set

Tab.1 Parameters used in CompactChain

Fig.1 Block header composition mainly contains two RSA accumulators -

T X O_C

(TXO commitment) and

S T X O_C

(STXO commitment)

Fig.2 Block validation procedure

	Boneh’s	Minichain	CompactChain
Accumulator type	RSA(UTXO)	MMR(TXO) $+$ RSA(STXO)	RSA(TXO) $+$ RSA(STXO)
Commitment Update	$O (m 2)$	$O (m)$	$O (m)$
Tx Proof generation	$O (k + d)$	$O (l o g (m)) + O (l o g (L)) + O (d)$	$O (k + d)$
Tx Proof verification	$O (1)$	$O (l o g (m)) + O (l o g (L)) + O (1)$	$O (1)$
Tx Proof size	$O (1)$	$O (l o g (m)) + O (l o g (L)) + O (1)$	$O (1)$
Tx Proof update	$O (k + d)$	$O (d)$	$O (k + d)$

Tab.2 Comparison of CompactChain with Boneh’s and Minichain protocols

Fig.3 Performance of the commitments update

Fig.4 Performance of the commitments verification

	Existence proof	Unspent proof	Verification time per Tx	Verification time for 1000 Txs
	(per Tx)	(per Tx)	(parallel execution)	(Parallel execution with 16 threads)
Boneh	–	$384$ [0.00067]	0.00067 s	0.193 s
Minichain	$960$ [0.000025]	$400$ [0.0011]	0.00117 s	0.306 s
CompactChain	$384$ [0.00056]	$400$ [0.0010]	0.00115 s	0.303 s

Tab.3 Comparison of Transaction witness size (in bytes) [verification time (s)]

Fig.5 Performance of the transaction witness update

Fig.6 Comparison of RAM Usage

Fig.7 Comparison of Disk Usage

Fig.8 Comparison of Memory Pool Usage

Fig.9 Performance of propagation latency of a block in the network

Tab.4 Comparison of maximum TPS

1	S Nakamoto . Bitcoin: a peer-to-peer electronic cash system. See Nakamotoinstitute.org/bitcoin/website, 2008
2	G Wood . Ethereum: a secure decentralised generalized transaction ledger. Ethereum Project Yellow Paper, 2014, 151: 1–32
3	E, Androulaki A, Barger V, Bortnikov C, Cachin K, Christidis Caro A, De D, Enyeart C, Ferris G, Laventman Y, Manevich S, Muralidharan C, Murthy B, Nguyen M, Sethi G, Singh K, Smith A, Sorniotti C, Stathakopoulou M, Vukolić S W, Cocco J Yellick . Hyperledger fabric: a distributed operating system for permissioned blockchains. In: Proceedings of the 13th EuroSys Conference. 2018, 30
4	A, Dorri S S, Kanhere R, Jurdak P Gauravaram . Blockchain for IoT security and privacy: the case study of a smart home. In: Proceedings of 2017 IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops). 2017, 618−623
5	J M, Song J, Sung T Park . Applications of blockchain to improve supply chain traceability. Procedia Computer Science, 2019, 162: 119–122
6	A, Azaria A, Ekblaw T, Vieira A Lippman . MedRec: using blockchain for medical data access and permission management. In: Proceedings of the 2nd International Conference on Open and Big Data (OBD). 2016, 25−30
7	M, Pincheira M, Vecchio R, Giaffreda S S Kanhere . Cost-effective IoT devices as trustworthy data sources for a blockchain-based water management system in precision agriculture. Computers and Electronics in Agriculture, 2021, 180: 105889
8	S J, Pee E S, Kang J G, Song J W Jang . Blockchain based smart energy trading platform using smart contract. In: Proceedings of 2019 International Conference on Artificial Intelligence in Information and Communication (ICAIIC). 2019, 322−325
9	Bitcoin. Full node. See Bitcoin.org/en/full-node website, 2023
10	S, Delgado-Segura C, Pérez-Solà G, Navarro-Arribas J Herrera-Joancomartí . Analysis of the bitcoin UTXO set. Financial Cryptography and Data Security. 2019, 78−91
11	Bitcoin. Bitcoin repository. See GitHub.com/bitcoin/bitcoin website, 2023
12	Blockchain. Block-size and UTXO charts. See Blockchain.com/explorer/charts website, 2023
13	N, Barić B Pfitzmann . Collision-free accumulators and fail-stop signature schemes without trees. In: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques Konstanz on Advances in Cryptology. 1997, 480−494
14	J, Camenisch A Lysyanskaya . Dynamic accumulators and application to efficient revocation of anonymous credentials. In: Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology. 2002, 61−76
15	J, Li N, Li R Xue . Universal accumulators with efficient nonmembership proofs. In: Proceedings of the 5th International Conference on Applied Cryptography and Network Security. 2007, 253−269
16	D, Boneh B, Bünz B Fisch . Batching techniques for accumulators with applications to IOPs and stateless blockchains. In: Proceedings of the 39th Annual International Cryptology Conference on Advances in Cryptology. 2019, 561−586
17	E Tremel . Real-world performance of cryptographic accumulators. See cs.brown.edu/research/pubs/theses/ugrad/2013/tremel website, 2013
18	H, Chen Y Wang MiniChain: a lightweight protocol to combat the UTXO growth in public blockchain. Journal of Parallel and Distributed Computing, 2020, 143: 67−76
19	P. Making UTXO set growth irrelevant with low-latency delayed TXO commitments. See Petertodd.org/2016/delayed-txo-commitments website, Todd Shamir, 2016 A. How to share a secret. Communications of the ACM, 1979, 22( 11): 612–613
20	D, Perard J, Lacan Y, Bachy J Detchart . Erasure code-based low storage blockchain node. In: Proceedings of 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). 2018, 1622−1627
21	S, Kadhe J, Chung K Ramchandran . SeF: a secure fountain architecture for slashing storage costs in blockchains. 2019, arXiv preprint arXiv: 1906.12140
22	R K, Raman L R Varshney . Dynamic distributed storage for scaling blockchains. 2017, arXiv preprint arXiv: 1711.07617
23	A Shamir, . How to share a secret. Communications of the ACM, 1979, 22(11): 612−613
24	K V, Rashmi N B, Shah P V, Kumar K Ramchandran . Explicit construction of optimal exact regenerating codes for distributed storage. In: Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing. 2009, 1243−1249
25	A S, Rawat O O, Koyluoglu N Silberstein , Vishwanath S Optimal locally repairable and secure codes for distributed storage systems. IEEE Transactions on Information Theory, 2014, 60(1): 212−236
26	R, Matzutt B, Kalde J, Pennekamp A, Drichel M, Henze K Wehrle . How to securely prune bitcoin’s blockchain. In: Proceedings of 2020 IFIP Networking Conference (Networking). 2020, 298−306
27	A, Chepurnoy M, Larangeira A Ojiganov . Rollerchain, a blockchain with safely pruneable full blocks. 2016, arXiv preprint arXiv: 1603.07926
28	V Buterin . The stateless client concept. See Ethresear.ch/t/the-stateless-client-concept/172 website, 2017
29	A, Chepurnoy C, Papamanthou S, Srinivasan Y Zhang . Edrax: a cryptocurrency with stateless transaction validation. IACR Cryptol. ePrint Arch. 2018/968. 2018
30	R, Dahlberg T, Pulls R Peeters . Efficient sparse Merkle trees: caching strategies and secure (non-)membership proofs. In: Proceedings of the 21st Nordic Workshop on Secure Computer Systems, 2016
31	A J, Menezes K H, Rosen Oorschot P C, van S A Vanstone . Handbook of Applied Cryptography. Boca Raton: CRC Press, 1997
32	H Lipmaa . Secure accumulators from Euclidean rings without trusted setup. In: Proceedings of the 10th International Conference on Applied Cryptography and Network Security. 2012, 224−240
33	B Wesolowski . Efficient verifiable delay functions. In: Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology. 2019, 379−407
34	D Z, Sun Z F, Cao Y Sun . How to compute modular exponentiation with large operators based on the right-to-left binary algorithm. Applied Mathematics and Computation, 2006, 176 (1): 280−292
35	A, Fiat A Shamir . How to prove yourself: practical solutions to identification and signature problems. In: Proceedings of Advances in Cryptology. 1987, 186−194
36	Etremel. Crypto-accumulators. See Github.com/etremel/crypto-accumulators/blob/master/lib/flint/BigInt website, 2013
37	B S, Reddy T U K Reddy . See Github.com/TUdayKiranReddy/CompactChain website, 2023
38	C, Decker R Wattenhofer . Information propagation in the bitcoin network. In: Proceedings of IEEE P2P 2013 Proceedings. 2013, 1−10
39	B S, Reddy G V V Sharma . Optimal transaction throughput in proof-of-work based blockchain networks. Proceedings, 2019, 28(1): 6
40	B S, Reddy G V V Sharma . UL-blockDAG: unsupervised learning based consensus protocol for blockchain. In: Proceedings of the 40th IEEE International Conference on Distributed Computing Systems (ICDCS). 2020, 1243−1248
41	B S, Reddy G V V Sharma . Scalable consensus protocols for PoW based blockchain and blockDAG. 2020, arXiv preprint arXiv: 2010.05447
42	Bitnodes. See Bitnodes.io website, 2023
43	Speedtest. Global-index. See Speedtest.net/global-index website, 2021

[1]

FCS-22365-OF-BSR_suppl_1

Download

Viewed

Full text

Abstract

Cited

Shared

Discussed