PaperlayerView exact revision on arXiv

Source-linked AI summary

SoK of Used Cryptography in Blockchain

Mayank Raikwar, Danilo Gligoroski, Katina Kralevska

arXiv:1906.08609v3cs.CRcs.ITcs.NImath.IT

TL;DR

Few studies systematize the cryptographic concepts used or potentially usable in blockchain, despite their role in blockchain solutions. This paper reviews and classifies those concepts, describes instantiations, and identifies 21 research challenges. It aims to help researchers choose problems and practitioners choose concepts for particular use cases.

  • Problem

    Few studies scrutinize blockchain cryptography, and the authors identify no SoK giving a complete picture of concepts deployed or potentially deployable in blockchain.

    Source: §1 · p. 5

  • Method

    The paper classifies cryptographic concepts by their blockchain use, describes applied concepts and instantiations, and lists promising concepts and research challenges.

    Source: §1.1 · p. 5

  • Results

    The SoK systematizes cryptographic concepts already used in blockchain, identifies concepts that may be beneficial if applied, and formulates 21 research challenges.

    Source: §1.1 · p. 5, §7 · p. 40

  • Takeaways & Limitations

    The authors intend the review to help cryptographers choose research problems and practitioners select concepts for particular blockchain use cases.

    Source: §7 · p. 40

    The authors do not claim exhaustive coverage, instead selecting concepts they consider propitious for blockchain.

    Source: §1.1 · p. 5

Abstract

from arXiv · show

The underlying fundaments of blockchain are cryptography and cryptographic concepts that provide reliable and secure decentralized solutions. Although many recent papers study the use-cases of blockchain in different industrial areas, such as finance, health care, legal relations, IoT, information security, and consensus building systems, only few studies scrutinize the cryptographic concepts used in blockchain. To the best of our knowledge, there is no Systematization of Knowledge (SoK) that gives a complete picture of the existing cryptographic concepts which have been deployed or have the potential to be deployed in blockchain. In this paper, we thoroughly review and systematize all cryptographic concepts which are already used in blockchain. Additionally, we give a list of cryptographic concepts which have not yet been applied but have big potentials to improve the current blockchain solutions. We also include possible instantiations of these cryptographic concepts in the blockchain domain. Last but not least, we explicitly postulate 21 challenging problems that cryptographers interested in blockchain can work on.

1 Introduction

Blockchain builds on cryptographic ideas developed for secure transactions and decentralized currencies, while its network, consensus, and cryptographic design raise challenges including security, privacy, key management, and scalability. The paper systematizes cryptographic concepts used or potentially applicable in blockchain, describes their instantiations, and identifies research challenges.

1 Introduction

  • Earlier cryptographic proposals including hashcash, b-money, and Bitgold helped form the basis of Bitcoin’s decentralized cryptocurrency.The paper traces these ideas to the Cypherpunk community and earlier proposals for eCash and computational puzzles.Source: §1 · p. 4
  • Blockchain is a shared ledger of confirmed transaction blocks, and its network, consensus, and cryptographic schemes underpin challenges such as security, privacy, key management, and scalability.The paper also identifies attack analysis, smart contract management, and incremental introduction of cryptographic features as challenges.Source: §1 · p. 4
  • The paper presents a systematization intended to give a complete picture of blockchain-related cryptographic concepts, complementing reviews focused on security, privacy, consensus, or existing cryptocurrencies.It notes that a prior analysis of primitives based only on existing cryptocurrencies lacks many protocols used in blockchain.Source: §1 · p. 5

1.1 Our Contribution

  • The authors classify concepts as already used or promising but not yet implemented, while noting that the boundary between categories is not clear-cut.The promising category calls for further research and scrutiny before deployment.Source: §1.1 · p. 5
  • The SoK describes applied cryptographic concepts and their blockchain instantiations, and lists rarely used or unused concepts with potential applications.The authors say these prospective concepts may open research directions across blockchain applications.Source: §1.1 · p. 5
  • The paper identifies 21 research challenges, some rephrased from prior literature and others newly formulated, and also summarizes enabling concepts and blockchain architecture.Its unified overview includes hash functions, consensus protocols, network architecture, layered architecture, and major challenges.Source: §1.1 · pp. 5–6

2 Research Methodology

The authors use a systematic process to identify, screen, and assess literature on cryptographic concepts related to blockchain. Their criteria consider usefulness, properties, instantiations or potential, and publication quality.

2 Research Methodology

  • The review defines inclusion criteria, a search strategy, data collection, screening, and a final quality assessment before adding publications to the systematization.The authors describe this sequence as their methodology for reviewing the growing body of blockchain literature.Source: §2 · p. 6
  • The search uses concept-and-blockchain keyword combinations, with Google Scholar as the primary source and five additional scholarly databases.The additional sources are IACR eprint, IEEE Xplore, ACM Digital Library, ScienceDirect, and Springer Link.Source: §2 · p. 6
  • Inclusion depends on a concept’s usefulness, achievable properties, and existing or potential blockchain instantiation; quality assessment checks implementation or feasibility, security analysis, and adequate description.The study excludes informal discussion and claims of use that offer no guarantees about feasibility or implementation prospects.Source: §2 · pp. 6–7

3 Supporting and enabling concepts of Blockchain

This section outlines blockchain’s supporting concepts, from hash-linked blocks and transaction representations to the cryptographic, consensus, network, and access-design choices used in blockchain systems. It presents essential functionality rather than a detailed technical treatment of each concept.

3.1 Cryptographic Hash Function

  • Cryptographic hash functions support proof-of-work puzzles, address generation and shortening, and message digests in signatures; SHA-2 and SHA-3-family functions are common choices.Bitcoin uses SHA256 twice in the SHA256d construction.Source: §3.1 · p. 8
  • Litecoin’s Scrypt, QuarkCoin’s cascaded hashes, and DASH’s X11 aimed to resist ASIC mining, but ASIC miners became commercially available; ProgPoW aims to make ASIC mining less efficient.Litecoin uses Scrypt, a memory-intensive construction involving HMAC instantiated with SHA256 and Salsa20/8.Source: §3.1 · pp. 9–10

3.2 Consensus Mechanisms

  • Consensus protocols select a leader to propose a block, then use explicit voting rounds or implicit acceptance; PoW leader election with implicit voting is called Nakamoto Consensus.The section also distinguishes proof-of-concept consensus protocols from Byzantine fault-tolerant replication and notes that protocols affect finality, throughput, scalability, and robustness.Source: §3.2 · pp. 10–11
  • Permissionless networks commonly use a longest-chain rule to maintain a canonical state, while permissioned networks typically use Byzantine fault-tolerant protocols.Examples of permissioned protocols include PBFT, Proof of Elapsed Time, and Ripple consensus.Source: §3.2 · p. 11

Mining, Pool Mining and Incentive Mechanisms

  • PoW mining repeatedly hashes candidate blocks with different nonces; the first miner to solve the puzzle receives an incentive, and miners may work solo or in pools.Mining is resource-intensive, drawing on computational power and memory; pool techniques and incentive mechanisms can vary.Source: Mining, Pool Mining and Incentive… · p. 12

3.3 Network Infrastructure

  • Blockchain P2P networks need to disseminate new blocks quickly for synchronization; unstructured networks predominate, while structured networks use identifiers and routing tables, as in Ethereum’s Kademlia adoption.Propagation delays can disrupt consensus and the network’s consistent global view; described attacks include eclipse, routing, and denial-of-service attacks.Source: §3.3 · pp. 13–14

3.4 Types of Blockchain

  • The paper distinguishes public/private access from permissioned/permissionless participation and describes four combinations; consortium blockchains combine permissioned public and permissionless private designs.Consortium systems are partially decentralized, with consensus reached by a selected group of participants.Source: §3.4 · pp. 14–15

4 Challenges in Blockchain

Blockchain challenges span security and privacy, scalability, consensus, throughput, energy use, and dependencies across infrastructure layers. The section formulates research problems addressing these constraints, including secure interoperability and systems able to support billions of IoT devices.

4 Challenges in Blockchain

  • Consensus research problems seek lower energy use, more efficient agreement, and stronger security, while sustainability proposals ask for provable resistance to mining advantages for ASIC or GPU miners.The section also calls for a platform-independent tool to test security and privacy requirements at every blockchain layer.Source: §4 · pp. 15–16

4.1 Security and Privacy

  • Blockchain security and privacy challenges motivate a platform-independent penetration-testing tool for requirements at every layer.Security comprises confidentiality, integrity, and availability; privacy includes data privacy and user anonymity.Source: §4.1 · p. 17

4.2 Scalability Issues

  • Growing ledger size and limited node capacity constrain scalability; proposed directions include ledger pruning that preserves asset state and secure interoperability protocols.SPV verifies transactions without downloading the full ledger, while erasure coding can reduce storage and communication costs.Source: §4.2 · pp. 17–18

4.3 Forking

  • The section calls for a forking-free consensus mechanism for permissionless public blockchains, noting that near-simultaneous blocks or software incompatibility can produce forks.Hard forks are not backward-compatible, while soft forks are.Source: §4.3 · p. 18

4.4 Throughput

  • High throughput is difficult because it depends on consensus, network structure, node behavior, block parameters, and contract complexity; research problems call for private multi-hop payments and secure, private state channels.The section describes Lightning as processing transactions off the main ledger and cites Bitcoin's 7 transactions per second against up to 50,000 for Visa and MasterCard during peak holiday periods.Source: §4.4 · pp. 18–19

4.5 Energy Consumption

  • Blockchain energy use includes both mining and network communication, so the section calls for energy-aware cryptographic choices and identifies PoS-like consensus and IoT energy management as approaches.It contrasts Bitcoin's PoW energy use with alternatives including Proof of Stake, Equihash, and PBFT.Source: §4.5 · p. 20

4.6 Infrastructure Dependencies

  • Blockchain layers depend on one another's inputs and outputs, so a comprehensive framework must account for those dependencies; the section calls for scalable systems that securely manage up to billions of IoT devices over 5G.Examples include smart-contract data feeding transactions and network data passing to database storage.Source: §4.6 · p. 20

5 Overview of used cryptographic concepts in blockchain

The overview presents a reference systematization of cryptographic concepts used in blockchain. It describes signature schemes' roles in authentication and integrity, as well as open problems around legal recognition and theft recovery.

5 Overview of used cryptographic concepts in blockchain

  • Table 5 provides a comprehensive quick reference to the cryptographic concepts covered in the systematization.The paper distinguishes concepts already used in blockchain from promising concepts not yet implemented, while noting that the categories do not have a clear boundary.Source: §5 · p. 20

5.1 Signature Scheme

  • Blockchain signatures authenticate transaction senders and support integrity and non-repudiation, with variants used for anonymity, unlinkability, multi-party signing, and aggregation.Examples include M-of-N signatures, blind and ring signatures, and threshold signatures; Schnorr signatures are described as used in Bitcoin for scalability.Source: §5.1 · pp. 21–23
  • The section identifies legal recognition of blockchain signatures and recovery of stolen assets as unresolved problems, proposing PKI integration and an anti-theft system.The Vault proposal aims to shield Bitcoin wallets from theft without a hard fork, but the passage says no such proposal or solution exists for other blockchain systems.Source: §5.1 · p. 23

5.2 Zero-Knowledge Proofs

Zero-knowledge proofs let a prover establish a statement without revealing other information, supporting confidential blockchain transactions. The section also describes access-control models that restrict blockchain data and actions according to roles or attributes.

5.2 Zero-Knowledge Proofs

  • Zero-knowledge proofs can establish that an asset transfer is valid without revealing information about the asset, enabling confidentiality and unlinkable transactions.Zerocoin protects the link between a Zerocoin and its user, but is costly because of high complexity and large proof size; zk-SNARKs reduce proof size and computational effort compared with basic zero-knowledge proofs.Source: §5.2 · pp. 23–24

5.3 Access Control

  • Access control can restrict blockchain reads, writes, or participation, with RBAC assigning rights by role and ABAC applying user, environment, or object attributes.In the healthcare example, patients can request their records, but only their associated doctor can enter or modify them; research companies can request disease-related data.Source: §5.3 · pp. 24–25

5.4 Encryption Scheme

The section surveys encryption options for blockchain confidentiality and describes secure multi-party computation as a way for parties to compute without disclosing their inputs. Examples include private storage and cross-chain asset transfers.

5.4 Encryption Scheme

  • Encryption can provide confidentiality for blockchain data, but searching and computing over encrypted data remain challenges; Monero's homomorphic encryption supports value transactions only.The paper also describes searchable encryption in permissioned blockchain and notes that, as of June 2019, none of the six CAESAR authenticated-encryption ciphers had been deployed in a blockchain system.Source: §5.4 · p. 26

5.5 Secure Multi-party Computation (SMPC)

  • SMPC lets parties jointly compute over inputs without disclosing them, and Enigma combines a blockchain holding hashes with an SMPC network holding data split among nodes [117].Hawk uses SMPC to minimize trust in generating a common reference string for SNARK proofs, while Keep provides decentralized data containers accessible from Ethereum smart contracts.Source: §5.5 · pp. 26–27
  • Wanchain uses Storeman nodes to jointly lock and unlock cross-chain assets, with M out of N nodes contributing private-key shares to generate the unlocking signature.The transfer locks ETH on its original chain, issues equivalent WETH on Wanchain, and burns that WETH when ETH is released.Source: §5.5 · p. 27

5.6 Secret Sharing

Secret sharing distributes secret information as participant-specific shares that can be recombined from a sufficient subset, with blockchain uses including wallet-key protection and decentralized state storage. Commitment schemes hide a secret until opening while binding the sender to the committed value.

5.6 Secret Sharing

  • Secret sharing divides a secret into participant-specific shares and reconstructs it using a minimum number of shares.The paper describes possible DAO use in which nodes store shares of system state rather than the full state.Source: §5.6 · p. 28
  • A 2-of-3 wallet scheme lets any two people reconstruct the key, while individual shares reveal no information about it.Secret sharing is also used in SHARVOT and a cryptocurrency based on mini blockchain.Source: §5.6 · p. 28, Figure 10 · p. 28

5.7 Commitment Scheme

  • A commitment scheme has commit and open phases: the sender hides and binds a secret, then proves they did not change it.Hiding prevents the receiver from seeing the message before opening; binding prevents the sender from changing it afterward.Source: §5.7 · pp. 28–29
  • In the binding example, finding another value that produces the same commitment is computationally hard, while a supplied secret lets anyone verify it.Zerocoin uses Pedersen commitments to bind a serial number to a coin; Pedersen commitments also appear in Bulletproof and Monero.Source: §5.7 · p. 29

5.8 Accumulator

Accumulators support membership proofs and appear in blockchain structures and applications, including Zerocoin and stateless blockchains. Oblivious transfer lets a receiver obtain selected messages without revealing which ones were received, and has blockchain applications including private and verifiable smart contracts.

5.8 Accumulator

  • Merkle trees are space- and time-efficient accumulators used in cryptocurrencies, with transaction leaves represented under a Merkle root stored in the block.Accumulators can also support membership proofs without revealing individual identity.Source: §5.8 · p. 29, Figure 11 · p. 30
  • In Zerocoin, the network computes an accumulator over coin commitments, and a user uses a membership witness to prove knowledge of a coin when spending.The witness and accumulator are publicly verifiable without a trusted third party.Source: §5.8 · pp. 29–30
  • Accumulators are used for range proofs and in a stateless blockchain design where consensus participation requires only constant storage.Source: §5.8 · p. 30

5.9 Oblivious Transfer (OT)

  • In k-out-of-n oblivious transfer (k < n), a sender holds n messages, and the receiver simultaneously retrieves k of them without the sender learning which k were received.Source: §5.9 · p. 30
  • Oblivious transfer supports secure multiparty computation and has been used to create private and verifiable blockchain smart contracts [158].The paper also names Searchain and APDB as blockchain applications of oblivious transfer.Source: §5.9 · p. 31

5.10 Oblivious RAM (ORAM)

Oblivious RAM hides remote memory access patterns and is used in blockchain protocols for confidential transactions and account-balance verification. Proof of retrievability verifies that stored data remains intact and recoverable, with blockchain applications including storage-oriented cryptocurrencies.

5.10 Oblivious RAM (ORAM)

  • Oblivious RAM hides a client’s read/write access pattern from an untrusted server while supporting remote data operations.In Solidus, a publicly verifiable ORAM machine lets banks store account balances and verify valid transaction sets.Source: §5.10 · p. 31
  • Solidus uses ORAM for confidential public-blockchain transactions, while an externally verifiable ORAM protocol uses Ethereum contracts to adjudicate disputes by penalizing malicious servers.Source: §5.10 · p. 31

5.11 Proof of Retrievability (POR)

  • Proof of retrievability lets a server give a compact proof that client data is intact and recoverable, but client verification requires computation and network access.Outsource proof of retrievability uses external auditors to verify on behalf of clients and uses Bitcoin functionalities as building blocks.Source: §5.11 · p. 31
  • Permacoin invests storage alongside computation for archival data, but incurs storage overhead and high bandwidth consumption.Retricoin repurposes mining work to ensure large-file retrievability and proposes collective mining; Storj uses POR to prove a fresh shard copy exists.Source: §5.11 · p. 31

5.12 Post-Quantum Cryptography

The paper discusses cryptographic approaches to quantum threats, resource-constrained devices, and verifiable randomness in blockchain. It identifies a post-quantum design challenge: retain comparably efficient addresses and small signatures, while VRFs are used for secret sortition in proof-of-stake systems.

5.12 Post-Quantum Cryptography

  • A quantum computer using a variant of Shor’s algorithm can forge ECC signatures that underpin blockchain transactions, threatening keys and digital signatures.The paper notes that ECC is widely used in blockchain applications.Source: §5.12 · p. 32
  • Hash-based BPQS uses one-time signatures that rely on secure hash functions rather than number-theoretic hard problems, and is described as not vulnerable to Shor’s algorithm.The paper also describes post-quantum blockchains and cryptocurrency using one-time signature chains.Source: §5.12 · p. 32
  • Research Problem 11 asks for post-quantum blockchain mechanisms with public-key addresses and digital signatures comparably efficient and small to those currently used.The paper identifies orders-of-magnitude larger public keys or signatures in developed post-quantum primitives as a research challenge.Source: §5.12 · p. 32

5.13 Lightweight Cryptography

  • Lightweight cryptography targets constrained devices such as IoT end nodes and RFID tags, reducing communication, memory, and power burdens while remaining less secure.The paper describes blockchain as a possible companion to sensor networks for better security.Source: §5.13 · p. 32

5.14 Verifiable Random Function (VRF)

  • A verifiable random function maps inputs to verifiable pseudorandom outputs, and proof-of-stake blockchains use it for secret leader or committee selection.Examples include Algorand, Witnet [170], and Ouroboros Praos.Source: §5.14 · p. 33

5.15 Obfuscation

Obfuscation preserves a program’s functionality while making its internal logic difficult to recover, and the section discusses its use in smart contracts and blockchain systems.

5.15 Obfuscation

  • Obfuscation can make a smart contract a black box while preserving its functionality, and the contract can hold a private key for decrypting encrypted input.The paper also lists witness encryption, functional encryption, and restricted software as potential obfuscation applications.Source: §5.15 · pp. 33–34
  • Figure 12 depicts an obfuscated smart contract that stores the private key corresponding to the public key used to encrypt transaction data.The paper says the private key is hard to obtain from the obfuscated contract.Source: Figure 12 · p. 34, §5.15 · p. 34
  • P2SH was an early limited obfuscation variant: spending funds requires a script matching the script hash, and its adoption without a Bitcoin hard fork signaled interest in the approach.P2SH sends Bitcoin amounts to a script hash rather than a public-key hash.Source: §5.15 · p. 34
  • Obfuscation has also been used for power-grid consumption data by adding noise and dividing the data into random and non-random obfuscated parts.Source: §5.15 · p. 34
  • Blockchain scripting languages remain an open target for studying obfuscation difficulty and whether techniques developed for C, C++, Java, and Perl can be applied to them.The paper notes that those four languages offer easier program obfuscation.Source: §5.15 · p. 34

6 Promising but yet not employed cryptographic primitives in blockchain

This section surveys cryptographic concepts that are promising for blockchain but remain insufficiently studied or not yet implemented, describing potential uses and associated research problems.

6.1 Aggregate Signature

  • Aggregate signatures compress signatures on distinct messages from distinct signers, potentially reducing blockchain storage and computation; the paper calls for an efficient scheme tailored to blockchain transactions.General aggregation combines signatures after signing, while sequential aggregation occurs during signing; aggregate signatures have been proposed for Bitcoin.Source: §6.1 · p. 35

6.2 Identity-Based Encryption (IBE)

  • IBE uses a recipient’s identity as a public key and a trusted Private Key Generator to issue the matching private key; the paper proposes a permissioned blockchain using this model.A consortium of trusted parties or a smart-contract layer could take the PKG role; the paper identifies an existing blockchain use and supply-chain use.Source: §6.2 · pp. 35–36

6.3 Verifiable Delay Function (VDF)

  • A VDF takes prescribed sequential steps to compute but is easily verifiable, with proposed uses including leader election, randomness beacons, and proofs of replication.The paper notes prototype and industry activity and poses finding a simple post-quantum-secure VDF as a research problem.Source: §6.3 · p. 36

6.4 Private Information Retrieval (PIR)

  • Private information retrieval can let users query transaction data or SPV clients without exposing their query terms or responses, but it requires substantial processing.The section poses challenges in unlinkable publishing, private transaction retrieval, and efficient anonymous publishing on permissioned blockchains.Source: §6.4 · p. 37

6.5 Decentralized Authorization

  • Decentralized authorization avoids a centralized authorization server’s single point of failure, but auditing and enforcement are difficult to implement efficiently in a decentralized manner.The paper cites smart-contract systems such as BlendCAC and WAVE and calls for a permissioned-blockchain protocol supporting privileges and delegation.Source: §6.5 · p. 37

6.6 White-Box Cryptography; 6.7 Incremental Cryptography

  • White-box cryptography aims to keep keys concealed during software execution, while incremental cryptography updates a hash or signature in time proportional to the document change.The paper describes white-box key storage in blockchain and proposes using incremental hashing to update the distributed ledger.Source: §6.6 · p. 38, §6.7 · p. 38

6.8 Identity-based Broadcast Encryption (IBBE)

  • Identity-based broadcast encryption can secure data for multiple recipients, and revocable variants can support permissioned-blockchain membership logs.The paper proposes protocols to certify blocks of membership-operation logs.Source: §6.8 · pp. 38–39

6.9 Other Techniques:

  • Other candidates include MACs for integrity, NIWI proofs, position-based credentials, ECDHM addresses for private communication, and verifiable shuffles for mixing.The section notes NIWI applications and an initial Ethereum mixing-service proposal for verifiable shuffles.Source: §6.9 · pp. 39–40

7 Conclusion

The paper systematizes cryptographic concepts used or potentially useful in blockchain, identifies research directions, and relates blockchain building blocks to one another.

7 Conclusion

  • The review aims to help cryptographers select research problems and practitioners select concepts for particular use cases.Source: §7 · p. 40
  • The paper systematizes cryptographic concepts already used in blockchain, describes their instantiations, and identifies concepts not yet used that may be beneficial.It also presents basic blockchain building blocks and explains their dependencies.Source: §7 · p. 40
  • Table 5 summarizes the cryptographic concepts presented in the paper, including those used in blockchain and those with potential for use.Source: §7 · p. 40

Related papers

Loading 1906.08609v3…