Load evaluation of Proof-of-Verification [1]

[1] K. Matsuura, "Proof-of-Verification for Proof-of-Work: Miners Must Verify the Signatures on Bitcoin Transactions", Scaling Bitcoin 2019 (September 2019)
blockchain network
  • distributed ledger
    • block : each page of the ledger
    • chain : ledger of binded pages
  • shared information (ledger) by all parties
    • "consensus" among parties.
  • periodic update of ledger
    • collecting new data,
    • generating a block periodically,
    • appending it to the chain.
[2] J. Bonneau, A. Miller, J. Clark, A. Narayanan, J. A. Kroll, E. W. Felten, "SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies", In 2015 IEEE Symposium on Security and Privacy, pp.104-121 (May 2015)
Bitcoin [3]
[3] Satoshi Nakamoto, "Bitcoin: A peer-to-peer electronic cash system", https://bitcoin.org/bitcoin.pdf (2009)
cryptocurrency based on blind signature
  • implementation of a cryptocurrency using blockchain.
    • cryptocurrency
      • anonymous (by alias).
    • decentralized
      • no trustded third party (bank, mint).
  • parties connecting by P2P network.
  • wallet
  • transaction
bitcoin network
mechanism of blockchain
blockchain as a hash chain
  • data sharing among all participating parties
    • transmitting new data form/to one another.
  • update by new data collection
    • generating a block periodically by new data collection.
      • if succeeded, the block will be broadcasted.
    • sharing and updating in a reliable manner.
      • slection method of a party of block generation.
      • accepting only a block with valid data.
  • attainable security (sound blockchain)
    • consensus on a single valid chain.
      • In case one party evaluate one data in a chain as valid, others also do so.
      • A valid data settles in a chain in a certain period of time.
how to generate a block in Bitcoin ([2], etc.)
  • "proof-of-work" type
    • calculating a partial inversion of hash function.
      • evidence : nonce with which the block hash is less than the assigned value.
      • all the paricipating nodes can generate a block (probabilistically).
  • "miner"
    • a node, who found a successful nonce, earns some "coin"
      (: mining reward, transaction fees).
      ... called a "miner" (mining node).
    • competing among miners for earning coins.
data structure in Bitcoin [4]
  • chain
    • a hash chain of blocks.
  • block
    • TX (data) container.
    • ctr (proof) (... not easy to make)
  • TX ("transaction").
    • transaction of coins.
  • mempool
    • a pool of TXs.
      • created, but not in the chain.
  • UTXO table
    • unspent transaction output table of TX output in the chain, which is unspent.
[4] BitcoinCore, https://github.com/bitcoin/bitcoin/
workload of a miner in Bitcoin [3,4]
  • (as a node in P2P network)
    • receiving TXs.
      • validity check of them
        (checking with UTXO table, mempool).
      • updating UTXO table, mempool.
    • receiving blocks.
      • validity check of them
        (checking with a chain, UTXO table, mempool).
      • updating a chain, UTXO table, mempool.
    • creating and sending TXs (if necessary).
  • (in the node)
    • trial on proof-of-work
      • many hash calculation.

  • TX validity check
    • checking if valid format.
    • finding corresponding outputs in UTXO table (and mempool) to its inputs.
    • checking if not double-spending.
    • script verification.
      • reading and checking all scripts in TX.
      • signature verification.
        ... cryptographic computation (maybe heavy).
  • block validity check
    • checking on proof-of-work.
    • checking if valid format.
    • checking timestamp.
    • checking TXs in it.

  • Rushing miners have an incentive to skip validity checks.
    • (pros)
      • shifting computational power into proof-of-work trials.
      • no need to maintain UTXO table.
    • (cons)
      • possibility of accepting invalid TXs (and blocks).
      • ... possibility of generating a block with invalid TXs.
proof-of-verification [1]
  • issue
    • The more invalid TXs (and invalid blocks) are propagated in the system,
      the less soundness the system attains.
  • desired functionality
    • checking if a block is generated by validity-checked TXs.
    • light-weight (for block verifiers).
    • little additional workload (for miners).
      In signature verification process, there is a value such that ...
      • an inevitably-calculated intermediate variable,
      • not pre-computable,
      • requiring some computation
        (not too light compared to total computation of signature verification).
      ... employed as a PoV data of the TX.
  • PoV-related data in a block
    • (method 1)
      A block hash value is calculated with a hash value(s) of PoV data of all TXs.
      • Then the block hash depends on all PoV data.
      • (variation 1-1)
        • All hash values of TX PoV data are contained in the block.
        • (Hash(All PoV data) can be stored in the block header.)
      • (variation 1-2)
        • No PoV data of TXs are contained in the block.
        • "Hash(All PoV data)" is stored in the block header.
      • For easy (and fast) validity check on proof-of-work, it is necessary that some PoV-related data is included in the block.
    • (method 2)
      A hash value(s) of PoV data of all TXs in the block is just concatenated to the block.
      • (variation 2-1)
        • All hash values of TX PoV data are attached to the block.
      • (variation 2-2)
        • Only "Hash(All PoV data)" is attached to the block.
      • For proof-of-verification functionality (checking a block of skipping validity checks), it is necessary that some PoV-related data is attached to the block.
    • There can be many variations how PoV data are connected to the block
      (above variations, and intermediate variations between them).
  • no additional computation in miners.
    • except for hash calculation of each PoV data.
  • additional communication (and stored) data.
    • more in "variation ?-1" compared to "variation ?-2".
  • the same (or less) computation in nodes checking the block validity.
    • In "variation ?-1", validity checks of some randomly selected TXs might be enough.
      ... less computation than in original Bitcoin.
example of a PoV data of a TX
  • in ECDSA [5]
    • public parameters :
      • CURVE (: elliptic curve)
      • G : base point of order n (: prime)
    • key pair :
      • d : (secret) signature generation key
      • random integer, [1, n-1]
      • Q : (open) verification key ( Q = d * G )
    • signature :
      • ( r , s ) := Sig( message , d )
    • verification :
      • key check (Q is a point on CURVE, n * Q = O : identity)
      • e = Hash(message)
      • c = (s)-1 mod n ,
        u1 = e c mod n ,
        u2 = r c mod n
      • ( x , y ) = u1 * G + u2 * Q
      • valid if r == x mod n .
    • ... u1 (and u2) can be used as PoV data.
[5] Accredited Standards Committee X9, "American National Standard X9.62-2020, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)", (September 10, 2020)
load evaluation (plan)
  • evaluation method
    • experimentally measuring the workload by the processing time.
    • environment : "bitcoind" ver.0.18, on Ubuntu 18.0.4 LTS (64bit).
  • comparison between ...
    • (N) a normal miner (original "bitcoind"),
    • (S) an alt-miner who skips signature verification.
      ... There can be some variations in implementation of (S),
      in addition to variations in PoV data treatment in a block.
      • just skipping signature verifications,
      • skipping all checks in TX (no use of mempool, UTXO table),
      • ...
    • (V) an alt-miner implemented proof-of-verification.
  • some results so far ...
    • TX validation check workload
      • 32768 TX check ... 2.4% less in (S) than (N).
    • block generation workload
      • 5 block generation filled with above TXs ... 3.8% less in (S) than (N).
  • If an ancestor TX of a validity checking TX is in mempool, bitcoind becomes so heavy.
    • in TX validation check, block generation.
  • more efficient, in case large blocks are allowed.
    • In "variation ?-1", TX validity check of a block by random sampling might be acceptable.
    • Then fixed number of TX validation check is allowed,
      even in case the number of TXs in one block is increased.
    • On the contrary, the number of TX validity check in block validity check process will be increased in original Bitcoin.
  • no concern on mining pools.
    • In mining pool, it is possible to maintain the pool system such that the pool manager collects TXs, checks their validity and distributes a (candidate) block to participants in the pool. Then each participating node can try on proof-of-work of the block without checking validity by itself.
† These terms does not strictly mean the same things in existing terminology.

IIS Open House 2021, Matsuura Lab.