Load evaluation of Proof-of-Verification [1]

blochchain 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) implementation of a cryptocurrency using blockchain. cryptocurrency anonymous (by alias). decentralized no trustded third party (bank, mint). parties connecting by P2P network. wallet transaction

mechanism of blockchain 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). miscellaneous If an ancestor TX of a validity checking TX is in mempool, bitcoind becomes so heavy. in TX validation check, block generation.

notices 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.