query.rs 13.8 KB
Newer Older
1
use bitcoin::blockdata::block::Block;
2
use bitcoin::blockdata::transaction::Transaction;
Roman Zeyde's avatar
Roman Zeyde committed
3
use bitcoin::network::serialize::deserialize;
4
use bitcoin::util::hash::Sha256dHash;
5 6 7
use crypto::digest::Digest;
use crypto::sha2::Sha256;
use std::collections::HashMap;
8
use std::sync::{Arc, RwLock};
9

10 11
use app::App;
use index::{compute_script_hash, TxInRow, TxOutRow, TxRow};
12
use mempool::Tracker;
13
use metrics::Metrics;
14
use serde_json::Value;
15
use store::{ReadStore, Row};
16
use util::{FullHash, HashPrefix, HeaderEntry};
17

Roman Zeyde's avatar
Roman Zeyde committed
18
use errors::*;
Roman Zeyde's avatar
Roman Zeyde committed
19

20 21 22 23 24
pub struct FundingOutput {
    pub txn_id: Sha256dHash,
    pub height: u32,
    pub output_index: usize,
    pub value: u64,
Roman Zeyde's avatar
Roman Zeyde committed
25 26
}

27 28
type OutPoint = (Sha256dHash, usize); // (txid, output_index)

29 30
struct SpendingInput {
    txn_id: Sha256dHash,
31
    height: u32,
32
    funding_output: OutPoint,
33
    value: u64,
Roman Zeyde's avatar
Roman Zeyde committed
34 35 36
}

pub struct Status {
37 38 39 40
    confirmed: (Vec<FundingOutput>, Vec<SpendingInput>),
    mempool: (Vec<FundingOutput>, Vec<SpendingInput>),
}

41 42 43 44
fn calc_balance((funding, spending): &(Vec<FundingOutput>, Vec<SpendingInput>)) -> i64 {
    let funded: u64 = funding.iter().map(|output| output.value).sum();
    let spent: u64 = spending.iter().map(|input| input.value).sum();
    funded as i64 - spent as i64
Roman Zeyde's avatar
Roman Zeyde committed
45 46
}

47
impl Status {
48 49 50 51 52 53 54 55
    fn funding(&self) -> impl Iterator<Item = &FundingOutput> {
        self.confirmed.0.iter().chain(self.mempool.0.iter())
    }

    fn spending(&self) -> impl Iterator<Item = &SpendingInput> {
        self.confirmed.1.iter().chain(self.mempool.1.iter())
    }

56
    pub fn confirmed_balance(&self) -> i64 {
57 58 59
        calc_balance(&self.confirmed)
    }

60
    pub fn mempool_balance(&self) -> i64 {
61
        calc_balance(&self.mempool)
62 63
    }

64 65
    pub fn history(&self) -> Vec<(i32, Sha256dHash)> {
        let mut txns_map = HashMap::<Sha256dHash, i32>::new();
66
        for f in self.funding() {
67
            txns_map.insert(f.txn_id, f.height as i32);
68
        }
69
        for s in self.spending() {
70
            txns_map.insert(s.txn_id, s.height as i32);
71 72 73
        }
        let mut txns: Vec<(i32, Sha256dHash)> =
            txns_map.into_iter().map(|item| (item.1, item.0)).collect();
74
        txns.sort_unstable();
75 76 77
        txns
    }

78 79 80 81 82 83 84 85 86 87
    pub fn unspent(&self) -> Vec<&FundingOutput> {
        let mut outputs_map = HashMap::<OutPoint, &FundingOutput>::new();
        for f in self.funding() {
            outputs_map.insert((f.txn_id, f.output_index), f);
        }
        for s in self.spending() {
            if let None = outputs_map.remove(&s.funding_output) {
                warn!("failed to remove {:?}", s.funding_output);
            }
        }
88
        let mut outputs = outputs_map
89 90
            .into_iter()
            .map(|item| item.1) // a reference to unspent output
91 92 93
            .collect::<Vec<&FundingOutput>>();
        outputs.sort_unstable_by_key(|out| out.height);
        outputs
94 95
    }

96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
    pub fn hash(&self) -> Option<FullHash> {
        let txns = self.history();
        if txns.is_empty() {
            None
        } else {
            let mut hash = FullHash::default();
            let mut sha2 = Sha256::new();
            for (height, txn_id) in txns {
                let part = format!("{}:{}:", txn_id.be_hex_string(), height);
                sha2.input(part.as_bytes());
            }
            sha2.result(&mut hash);
            Some(hash)
        }
    }
}

Roman Zeyde's avatar
Roman Zeyde committed
113 114
struct TxnHeight {
    txn: Transaction,
115
    height: u32,
Roman Zeyde's avatar
Roman Zeyde committed
116 117
}

Roman Zeyde's avatar
Roman Zeyde committed
118 119 120 121 122
fn merklize(left: Sha256dHash, right: Sha256dHash) -> Sha256dHash {
    let data = [&left[..], &right[..]].concat();
    Sha256dHash::from_data(&data)
}

123 124 125 126 127 128 129
// TODO: the functions below can be part of ReadStore.
fn txrow_by_txid(store: &ReadStore, txid: &Sha256dHash) -> Option<TxRow> {
    let key = TxRow::filter_full(&txid);
    let value = store.get(&key)?;
    Some(TxRow::from_row(&Row { key, value }))
}

130
fn txrows_by_prefix(store: &ReadStore, txid_prefix: &HashPrefix) -> Vec<TxRow> {
131
    store
132
        .scan(&TxRow::filter_prefix(&txid_prefix))
133 134 135 136
        .iter()
        .map(|row| TxRow::from_row(row))
        .collect()
}
137

138
fn txids_by_script_hash(store: &ReadStore, script_hash: &[u8]) -> Vec<HashPrefix> {
139 140 141 142 143 144
    store
        .scan(&TxOutRow::filter(script_hash))
        .iter()
        .map(|row| TxOutRow::from_row(row).txid_prefix)
        .collect()
}
145

146
fn txids_by_funding_output(
147
    store: &ReadStore,
148 149 150 151 152 153 154 155
    txn_id: &Sha256dHash,
    output_index: usize,
) -> Vec<HashPrefix> {
    store
        .scan(&TxInRow::filter(&txn_id, output_index))
        .iter()
        .map(|row| TxInRow::from_row(row).txid_prefix)
        .collect()
156 157
}

158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
struct TransactionCache {
    map: RwLock<HashMap<Sha256dHash, Transaction>>,
}

impl TransactionCache {
    fn new() -> TransactionCache {
        TransactionCache {
            map: RwLock::new(HashMap::new()),
        }
    }

    fn get_or_else<F>(&self, txid: &Sha256dHash, load_txn_func: F) -> Result<Transaction>
    where
        F: FnOnce() -> Result<Transaction>,
    {
        if let Some(txn) = self.map.read().unwrap().get(txid) {
            return Ok(txn.clone());
        }
        let txn = load_txn_func()?;
        self.map.write().unwrap().insert(*txid, txn.clone());
        Ok(txn)
    }
}

182 183
pub struct Query {
    app: Arc<App>,
184
    tracker: RwLock<Tracker>,
185
    tx_cache: TransactionCache,
186 187
}

188
impl Query {
189
    pub fn new(app: Arc<App>, metrics: &Metrics) -> Arc<Query> {
190
        Arc::new(Query {
191
            app,
192
            tracker: RwLock::new(Tracker::new(metrics)),
193
            tx_cache: TransactionCache::new(),
194
        })
195 196
    }

197 198 199 200 201
    fn load_txns_by_prefix(
        &self,
        store: &ReadStore,
        prefixes: Vec<HashPrefix>,
    ) -> Result<Vec<TxnHeight>> {
Roman Zeyde's avatar
Roman Zeyde committed
202
        let mut txns = vec![];
203
        for txid_prefix in prefixes {
204
            for tx_row in txrows_by_prefix(store, &txid_prefix) {
205
                let txid: Sha256dHash = deserialize(&tx_row.key.txid).unwrap();
Roman Zeyde's avatar
Roman Zeyde committed
206 207
                let txn = self
                    .tx_cache
208
                    .get_or_else(&txid, || self.load_txn(&txid, tx_row.height))?;
209 210
                txns.push(TxnHeight {
                    txn,
211
                    height: tx_row.height,
212
                })
213 214
            }
        }
215
        Ok(txns)
216 217
    }

218 219 220 221
    fn find_spending_input(
        &self,
        store: &ReadStore,
        funding: &FundingOutput,
222
    ) -> Result<Option<SpendingInput>> {
223
        let spending_txns: Vec<TxnHeight> = self.load_txns_by_prefix(
224
            store,
225
            txids_by_funding_output(store, &funding.txn_id, funding.output_index),
226
        )?;
Roman Zeyde's avatar
Roman Zeyde committed
227
        let mut spending_inputs = vec![];
Roman Zeyde's avatar
Roman Zeyde committed
228
        for t in &spending_txns {
229
            for input in t.txn.input.iter() {
230 231
                if input.previous_output.txid == funding.txn_id
                    && input.previous_output.vout == funding.output_index as u32
Roman Zeyde's avatar
Roman Zeyde committed
232 233 234 235
                {
                    spending_inputs.push(SpendingInput {
                        txn_id: t.txn.txid(),
                        height: t.height,
236
                        funding_output: (funding.txn_id, funding.output_index),
237
                        value: funding.value,
Roman Zeyde's avatar
Roman Zeyde committed
238 239 240 241 242
                    })
                }
            }
        }
        assert!(spending_inputs.len() <= 1);
243
        Ok(if spending_inputs.len() == 1 {
Roman Zeyde's avatar
Roman Zeyde committed
244
            Some(spending_inputs.remove(0))
245 246
        } else {
            None
247
        })
248 249
    }

250
    fn find_funding_outputs(&self, t: &TxnHeight, script_hash: &[u8]) -> Vec<FundingOutput> {
Roman Zeyde's avatar
Roman Zeyde committed
251
        let mut result = vec![];
252
        let txn_id = t.txn.txid();
Roman Zeyde's avatar
Roman Zeyde committed
253
        for (index, output) in t.txn.output.iter().enumerate() {
254 255 256 257 258 259 260 261 262 263 264 265
            if compute_script_hash(&output.script_pubkey[..]) == script_hash {
                result.push(FundingOutput {
                    txn_id: txn_id,
                    height: t.height,
                    output_index: index,
                    value: output.value,
                })
            }
        }
        result
    }

266 267 268 269
    fn confirmed_status(
        &self,
        script_hash: &[u8],
    ) -> Result<(Vec<FundingOutput>, Vec<SpendingInput>)> {
270 271
        let mut funding = vec![];
        let mut spending = vec![];
272
        for t in self.load_txns_by_prefix(
273 274
            self.app.read_store(),
            txids_by_script_hash(self.app.read_store(), script_hash),
275
        )? {
276
            funding.extend(self.find_funding_outputs(&t, script_hash));
277
        }
278
        for funding_output in &funding {
279
            if let Some(spent) = self.find_spending_input(self.app.read_store(), &funding_output)? {
280
                spending.push(spent);
281 282
            }
        }
283
        Ok((funding, spending))
284 285
    }

286 287 288 289
    fn mempool_status(
        &self,
        script_hash: &[u8],
        confirmed_funding: &[FundingOutput],
290
    ) -> Result<(Vec<FundingOutput>, Vec<SpendingInput>)> {
291 292
        let mut funding = vec![];
        let mut spending = vec![];
293
        let tracker = self.tracker.read().unwrap();
294
        for t in self.load_txns_by_prefix(
295 296
            tracker.index(),
            txids_by_script_hash(tracker.index(), script_hash),
297
        )? {
298
            funding.extend(self.find_funding_outputs(&t, script_hash));
299
        }
300
        // // TODO: dedup outputs (somehow) both confirmed and in mempool (e.g. reorg?)
301
        for funding_output in funding.iter().chain(confirmed_funding.iter()) {
302
            if let Some(spent) = self.find_spending_input(tracker.index(), &funding_output)? {
303
                spending.push(spent);
Roman Zeyde's avatar
Roman Zeyde committed
304 305
            }
        }
306
        Ok((funding, spending))
307
    }
308

309
    pub fn status(&self, script_hash: &[u8]) -> Result<Status> {
Roman Zeyde's avatar
Roman Zeyde committed
310 311
        let confirmed = self
            .confirmed_status(script_hash)
312
            .chain_err(|| "failed to get confirmed status")?;
Roman Zeyde's avatar
Roman Zeyde committed
313 314
        let mempool = self
            .mempool_status(script_hash, &confirmed.0)
315
            .chain_err(|| "failed to get mempool status")?;
316
        Ok(Status { confirmed, mempool })
317 318
    }

319
    fn lookup_confirmed_blockhash(
320 321 322
        &self,
        tx_hash: &Sha256dHash,
        block_height: Option<u32>,
323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341
    ) -> Result<Option<Sha256dHash>> {
        let blockhash = if self.tracker.read().unwrap().get_txn(&tx_hash).is_some() {
            None // found in mempool (as unconfirmed transaction)
        } else {
            // Lookup in confirmed transactions' index
            let height = match block_height {
                Some(height) => height,
                None => {
                    txrow_by_txid(self.app.read_store(), &tx_hash)
                        .chain_err(|| format!("not indexed tx {}", tx_hash))?
                        .height
                }
            };
            let header = self
                .app
                .index()
                .get_header(height as usize)
                .chain_err(|| format!("missing header at height {}", height))?;
            Some(*header.hash())
342
        };
343 344 345 346 347 348 349 350 351 352 353 354 355 356 357
        Ok(blockhash)
    }

    // Internal API for transaction retrieval
    fn load_txn(&self, tx_hash: &Sha256dHash, block_height: u32) -> Result<Transaction> {
        let blockhash = self.lookup_confirmed_blockhash(tx_hash, Some(block_height))?;
        self.app.daemon().gettransaction(tx_hash, blockhash)
    }

    // Public API for transaction retrieval (for Electrum RPC)
    pub fn get_transaction(&self, tx_hash: &Sha256dHash, verbose: bool) -> Result<Value> {
        let blockhash = self.lookup_confirmed_blockhash(tx_hash, /*block_height*/ None)?;
        self.app
            .daemon()
            .gettransaction_raw(tx_hash, blockhash, verbose)
358
    }
359

360 361 362 363 364 365
    pub fn get_headers(&self, heights: &[usize]) -> Vec<HeaderEntry> {
        let index = self.app.index();
        heights
            .iter()
            .filter_map(|height| index.get_header(*height))
            .collect()
366
    }
Roman Zeyde's avatar
Roman Zeyde committed
367

368
    pub fn get_best_header(&self) -> Result<HeaderEntry> {
369
        let last_header = self.app.index().best_header();
370
        Ok(last_header.chain_err(|| "no headers indexed")?.clone())
Roman Zeyde's avatar
Roman Zeyde committed
371
    }
Roman Zeyde's avatar
Roman Zeyde committed
372 373 374 375 376

    pub fn get_merkle_proof(
        &self,
        tx_hash: &Sha256dHash,
        height: usize,
377
    ) -> Result<(Vec<Sha256dHash>, usize)> {
Roman Zeyde's avatar
Roman Zeyde committed
378 379
        let header_entry = self
            .app
380 381 382 383
            .index()
            .get_header(height)
            .chain_err(|| format!("missing block #{}", height))?;
        let block: Block = self.app.daemon().getblock(&header_entry.hash())?;
Roman Zeyde's avatar
Roman Zeyde committed
384
        let mut txids: Vec<Sha256dHash> = block.txdata.iter().map(|tx| tx.txid()).collect();
385 386 387 388
        let pos = txids
            .iter()
            .position(|txid| txid == tx_hash)
            .chain_err(|| format!("missing txid {}", tx_hash))?;
Roman Zeyde's avatar
Roman Zeyde committed
389
        let mut merkle = vec![];
Roman Zeyde's avatar
Roman Zeyde committed
390 391 392 393 394 395 396 397 398 399 400 401 402 403
        let mut index = pos;
        while txids.len() > 1 {
            if txids.len() % 2 != 0 {
                let last = txids.last().unwrap().clone();
                txids.push(last);
            }
            index = if index % 2 == 0 { index + 1 } else { index - 1 };
            merkle.push(txids[index]);
            index = index / 2;
            txids = txids
                .chunks(2)
                .map(|pair| merklize(pair[0], pair[1]))
                .collect()
        }
404
        Ok((merkle, pos))
Roman Zeyde's avatar
Roman Zeyde committed
405
    }
406

407
    pub fn broadcast(&self, txn: &Transaction) -> Result<Sha256dHash> {
408
        self.app.daemon().broadcast(txn)
409 410
    }

Roman Zeyde's avatar
Roman Zeyde committed
411
    pub fn update_mempool(&self) -> Result<()> {
Roman Zeyde's avatar
Roman Zeyde committed
412
        self.tracker.write().unwrap().update(self.app.daemon())
413
    }
414

415
    /// Returns [vsize, fee_rate] pairs (measured in vbytes and satoshis).
416
    pub fn get_fee_histogram(&self) -> Vec<(f32, u32)> {
417 418 419
        self.tracker.read().unwrap().fee_histogram().clone()
    }

420 421 422 423 424 425 426 427 428 429 430 431 432
    // Fee rate [BTC/kB] to be confirmed in `blocks` from now.
    pub fn estimate_fee(&self, blocks: usize) -> f32 {
        let mut total_vsize = 0u32;
        let mut last_fee_rate = 0.0;
        let blocks_in_vbytes = (blocks * 1_000_000) as u32; // assume ~1MB blocks
        for (fee_rate, vsize) in self.tracker.read().unwrap().fee_histogram() {
            last_fee_rate = *fee_rate;
            total_vsize += vsize;
            if total_vsize >= blocks_in_vbytes {
                break; // under-estimate the fee rate a bit
            }
        }
        last_fee_rate * 1e-5 // [BTC/kB] = 10^5 [sat/B]
433
    }
434
}