verifier.py (9540B)
1 # Electrum - Lightweight Bitcoin Client 2 # Copyright (c) 2012 Thomas Voegtlin 3 # 4 # Permission is hereby granted, free of charge, to any person 5 # obtaining a copy of this software and associated documentation files 6 # (the "Software"), to deal in the Software without restriction, 7 # including without limitation the rights to use, copy, modify, merge, 8 # publish, distribute, sublicense, and/or sell copies of the Software, 9 # and to permit persons to whom the Software is furnished to do so, 10 # subject to the following conditions: 11 # 12 # The above copyright notice and this permission notice shall be 13 # included in all copies or substantial portions of the Software. 14 # 15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 16 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 17 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 18 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 19 # BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 20 # ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 21 # CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 # SOFTWARE. 23 24 import asyncio 25 from typing import Sequence, Optional, TYPE_CHECKING 26 27 import aiorpcx 28 29 from .util import bh2u, TxMinedInfo, NetworkJobOnDefaultServer 30 from .crypto import sha256d 31 from .bitcoin import hash_decode, hash_encode 32 from .transaction import Transaction 33 from .blockchain import hash_header 34 from .interface import GracefulDisconnect 35 from .network import UntrustedServerReturnedError 36 from . import constants 37 38 if TYPE_CHECKING: 39 from .network import Network 40 from .address_synchronizer import AddressSynchronizer 41 42 43 class MerkleVerificationFailure(Exception): pass 44 class MissingBlockHeader(MerkleVerificationFailure): pass 45 class MerkleRootMismatch(MerkleVerificationFailure): pass 46 class InnerNodeOfSpvProofIsValidTx(MerkleVerificationFailure): pass 47 48 49 class SPV(NetworkJobOnDefaultServer): 50 """ Simple Payment Verification """ 51 52 def __init__(self, network: 'Network', wallet: 'AddressSynchronizer'): 53 self.wallet = wallet 54 NetworkJobOnDefaultServer.__init__(self, network) 55 56 def _reset(self): 57 super()._reset() 58 self.merkle_roots = {} # txid -> merkle root (once it has been verified) 59 self.requested_merkle = set() # txid set of pending requests 60 61 async def _run_tasks(self, *, taskgroup): 62 await super()._run_tasks(taskgroup=taskgroup) 63 async with taskgroup as group: 64 await group.spawn(self.main) 65 66 def diagnostic_name(self): 67 return self.wallet.diagnostic_name() 68 69 async def main(self): 70 self.blockchain = self.network.blockchain() 71 while True: 72 await self._maybe_undo_verifications() 73 await self._request_proofs() 74 await asyncio.sleep(0.1) 75 76 async def _request_proofs(self): 77 local_height = self.blockchain.height() 78 unverified = self.wallet.get_unverified_txs() 79 80 for tx_hash, tx_height in unverified.items(): 81 # do not request merkle branch if we already requested it 82 if tx_hash in self.requested_merkle or tx_hash in self.merkle_roots: 83 continue 84 # or before headers are available 85 if tx_height <= 0 or tx_height > local_height: 86 continue 87 # if it's in the checkpoint region, we still might not have the header 88 header = self.blockchain.read_header(tx_height) 89 if header is None: 90 if tx_height < constants.net.max_checkpoint(): 91 await self.taskgroup.spawn(self.network.request_chunk(tx_height, None, can_return_early=True)) 92 continue 93 # request now 94 self.logger.info(f'requested merkle {tx_hash}') 95 self.requested_merkle.add(tx_hash) 96 await self.taskgroup.spawn(self._request_and_verify_single_proof, tx_hash, tx_height) 97 98 async def _request_and_verify_single_proof(self, tx_hash, tx_height): 99 try: 100 async with self._network_request_semaphore: 101 merkle = await self.network.get_merkle_for_transaction(tx_hash, tx_height) 102 except UntrustedServerReturnedError as e: 103 if not isinstance(e.original_exception, aiorpcx.jsonrpc.RPCError): 104 raise 105 self.logger.info(f'tx {tx_hash} not at height {tx_height}') 106 self.wallet.remove_unverified_tx(tx_hash, tx_height) 107 self.requested_merkle.discard(tx_hash) 108 return 109 # Verify the hash of the server-provided merkle branch to a 110 # transaction matches the merkle root of its block 111 if tx_height != merkle.get('block_height'): 112 self.logger.info('requested tx_height {} differs from received tx_height {} for txid {}' 113 .format(tx_height, merkle.get('block_height'), tx_hash)) 114 tx_height = merkle.get('block_height') 115 pos = merkle.get('pos') 116 merkle_branch = merkle.get('merkle') 117 # we need to wait if header sync/reorg is still ongoing, hence lock: 118 async with self.network.bhi_lock: 119 header = self.network.blockchain().read_header(tx_height) 120 try: 121 verify_tx_is_in_block(tx_hash, merkle_branch, pos, header, tx_height) 122 except MerkleVerificationFailure as e: 123 if self.network.config.get("skipmerklecheck"): 124 self.logger.info(f"skipping merkle proof check {tx_hash}") 125 else: 126 self.logger.info(repr(e)) 127 raise GracefulDisconnect(e) from e 128 # we passed all the tests 129 self.merkle_roots[tx_hash] = header.get('merkle_root') 130 self.requested_merkle.discard(tx_hash) 131 self.logger.info(f"verified {tx_hash}") 132 header_hash = hash_header(header) 133 tx_info = TxMinedInfo(height=tx_height, 134 timestamp=header.get('timestamp'), 135 txpos=pos, 136 header_hash=header_hash) 137 self.wallet.add_verified_tx(tx_hash, tx_info) 138 139 @classmethod 140 def hash_merkle_root(cls, merkle_branch: Sequence[str], tx_hash: str, leaf_pos_in_tree: int): 141 """Return calculated merkle root.""" 142 try: 143 h = hash_decode(tx_hash) 144 merkle_branch_bytes = [hash_decode(item) for item in merkle_branch] 145 leaf_pos_in_tree = int(leaf_pos_in_tree) # raise if invalid 146 except Exception as e: 147 raise MerkleVerificationFailure(e) 148 if leaf_pos_in_tree < 0: 149 raise MerkleVerificationFailure('leaf_pos_in_tree must be non-negative') 150 index = leaf_pos_in_tree 151 for item in merkle_branch_bytes: 152 if len(item) != 32: 153 raise MerkleVerificationFailure('all merkle branch items have to 32 bytes long') 154 inner_node = (item + h) if (index & 1) else (h + item) 155 cls._raise_if_valid_tx(bh2u(inner_node)) 156 h = sha256d(inner_node) 157 index >>= 1 158 if index != 0: 159 raise MerkleVerificationFailure(f'leaf_pos_in_tree too large for branch') 160 return hash_encode(h) 161 162 @classmethod 163 def _raise_if_valid_tx(cls, raw_tx: str): 164 # If an inner node of the merkle proof is also a valid tx, chances are, this is an attack. 165 # https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016105.html 166 # https://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180609/9f4f5b1f/attachment-0001.pdf 167 # https://bitcoin.stackexchange.com/questions/76121/how-is-the-leaf-node-weakness-in-merkle-trees-exploitable/76122#76122 168 tx = Transaction(raw_tx) 169 try: 170 tx.deserialize() 171 except: 172 pass 173 else: 174 raise InnerNodeOfSpvProofIsValidTx() 175 176 async def _maybe_undo_verifications(self): 177 old_chain = self.blockchain 178 cur_chain = self.network.blockchain() 179 if cur_chain != old_chain: 180 self.blockchain = cur_chain 181 above_height = cur_chain.get_height_of_last_common_block_with_chain(old_chain) 182 self.logger.info(f"undoing verifications above height {above_height}") 183 tx_hashes = self.wallet.undo_verifications(self.blockchain, above_height) 184 for tx_hash in tx_hashes: 185 self.logger.info(f"redoing {tx_hash}") 186 self.remove_spv_proof_for_tx(tx_hash) 187 188 def remove_spv_proof_for_tx(self, tx_hash): 189 self.merkle_roots.pop(tx_hash, None) 190 self.requested_merkle.discard(tx_hash) 191 192 def is_up_to_date(self): 193 return not self.requested_merkle 194 195 196 def verify_tx_is_in_block(tx_hash: str, merkle_branch: Sequence[str], 197 leaf_pos_in_tree: int, block_header: Optional[dict], 198 block_height: int) -> None: 199 """Raise MerkleVerificationFailure if verification fails.""" 200 if not block_header: 201 raise MissingBlockHeader("merkle verification failed for {} (missing header {})" 202 .format(tx_hash, block_height)) 203 if len(merkle_branch) > 30: 204 raise MerkleVerificationFailure(f"merkle branch too long: {len(merkle_branch)}") 205 calc_merkle_root = SPV.hash_merkle_root(merkle_branch, tx_hash, leaf_pos_in_tree) 206 if block_header.get('merkle_root') != calc_merkle_root: 207 raise MerkleRootMismatch("merkle verification failed for {} ({} != {})".format( 208 tx_hash, block_header.get('merkle_root'), calc_merkle_root))