interpreter.rs

use std::{cmp, mem};
use bytes::Bytes;
use keys::{Signature, Public};
use chain::constants::SEQUENCE_LOCKTIME_DISABLE_FLAG;
use crypto::{sha1, sha256, dhash160, dhash256, ripemd160};
use sign::{SignatureVersion, Sighash};
use script::MAX_SCRIPT_ELEMENT_SIZE;
use {
	script, Builder, Script, ScriptWitness, Num, VerificationFlags, Opcode, Error, SignatureChecker, Stack
};

/// Helper function.
fn check_signature(
	checker: &SignatureChecker,
	mut script_sig: Vec<u8>,
	public: Vec<u8>,
	script_code: &Script,
	version: SignatureVersion
) -> bool {
	let public = match Public::from_slice(&public) {
		Ok(public) => public,
		_ => return false,
	};

	if script_sig.is_empty() {
		return false;
	}

	let hash_type = script_sig.pop().unwrap() as u32;
	let signature = script_sig.into();

	checker.check_signature(&signature, &public, script_code, hash_type, version)
}

fn is_public_key(v: &[u8]) -> bool {
	match v.len() {
		33 if v[0] == 2 || v[0] == 3 => true,
		65 if v[0] == 4 => true,
		_ => false,
	}
}

/// A canonical signature exists of: <30> <total len> <02> <len R> <R> <02> <len S> <S> <hashtype>
/// Where R and S are not negative (their first byte has its highest bit not set), and not
/// excessively padded (do not start with a 0 byte, unless an otherwise negative number follows,
/// in which case a single 0 byte is necessary and even required).
///
/// See https://bitcointalk.org/index.php?topic=8392.msg127623#msg127623
///
/// This function is consensus-critical since BIP66.
fn is_valid_signature_encoding(sig: &[u8]) -> bool {
	// Format: 0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash]
	// * total-length: 1-byte length descriptor of everything that follows,
	//   excluding the sighash byte.
	// * R-length: 1-byte length descriptor of the R value that follows.
	// * R: arbitrary-length big-endian encoded R value. It must use the shortest
	//   possible encoding for a positive integers (which means no null bytes at
	//   the start, except a single one when the next byte has its highest bit set).
	// * S-length: 1-byte length descriptor of the S value that follows.
	// * S: arbitrary-length big-endian encoded S value. The same rules apply.
	// * sighash: 1-byte value indicating what data is hashed (not part of the DER
	//   signature)

	// Minimum and maximum size constraints
	if sig.len() < 9 || sig.len() > 73 {
		return false;
	}

	// A signature is of type 0x30 (compound)
	if sig[0] != 0x30 {
		return false;
	}

	// Make sure the length covers the entire signature.
	if sig[1] as usize != sig.len() - 3 {
		return false;
	}

	// Extract the length of the R element.
	let len_r = sig[3] as usize;

	// Make sure the length of the S element is still inside the signature.
	if len_r + 5 >= sig.len() {
		return false;
	}

	// Extract the length of the S element.
	let len_s = sig[len_r + 5] as usize;

	// Verify that the length of the signature matches the sum of the length
	if len_r + len_s + 7 != sig.len() {
		return false;
	}

	// Check whether the R element is an integer.
	if sig[2] != 2 {
		return false;
	}

	// Zero-length integers are not allowed for R.
	if len_r == 0 {
		return false;
	}

	// Negative numbers are not allowed for R.
	if (sig[4] & 0x80) != 0 {
		return false;
	}

	// Null bytes at the start of R are not allowed, unless R would
	// otherwise be interpreted as a negative number.
	if len_r > 1 && sig[4] == 0 && (sig[5] & 0x80) == 0 {
		return false;
	}

	// Check whether the S element is an integer.
	if sig[len_r + 4] != 2 {
		return false;
	}

	// Zero-length integers are not allowed for S.
	if len_s == 0 {
		return false;
	}

	// Negative numbers are not allowed for S.
	if (sig[len_r + 6] & 0x80) != 0 {
		return false;
	}

	// Null bytes at the start of S are not allowed, unless S would otherwise be
	// interpreted as a negative number.
	if len_s > 1 && (sig[len_r + 6] == 0) && (sig[len_r + 7] & 0x80) == 0 {
		return false;
	}

	true
}

fn is_low_der_signature(sig: &[u8]) -> Result<(), Error> {
	if !is_valid_signature_encoding(sig) {
		return Err(Error::SignatureDer);
	}

	let signature: Signature = sig.into();
	if !signature.check_low_s() {
		return Err(Error::SignatureHighS);
	}

	Ok(())
}

fn is_defined_hashtype_signature(version: SignatureVersion, sig: &[u8]) -> bool {
	if sig.is_empty() {
		return false;
	}

	Sighash::is_defined(version, sig[sig.len() - 1] as u32)
}

fn parse_hash_type(version: SignatureVersion, sig: &[u8]) -> Sighash {
	Sighash::from_u32(version, if sig.is_empty() { 0 } else { sig[sig.len() - 1] as u32 })
}

fn check_signature_encoding(sig: &[u8], flags: &VerificationFlags, version: SignatureVersion) -> Result<(), Error> {
	// Empty signature. Not strictly DER encoded, but allowed to provide a
	// compact way to provide an invalid signature for use with CHECK(MULTI)SIG

	if sig.is_empty() {
		return Ok(());
	}

	if (flags.verify_dersig || flags.verify_low_s || flags.verify_strictenc) && !is_valid_signature_encoding(sig) {
		return Err(Error::SignatureDer);
	}

	if flags.verify_low_s {
		is_low_der_signature(sig)?;
	}

	if flags.verify_strictenc && !is_defined_hashtype_signature(version, sig) {
		return Err(Error::SignatureHashtype)
	}

	// verify_strictenc is currently enabled for BitcoinCash only
	if flags.verify_strictenc {
		let uses_fork_id = parse_hash_type(version, sig).fork_id;
		let enabled_fork_id = version == SignatureVersion::ForkId;
		if uses_fork_id && !enabled_fork_id {
			return Err(Error::SignatureIllegalForkId)
		} else if !uses_fork_id && enabled_fork_id {
			return Err(Error::SignatureMustUseForkId);
		}
	}

	Ok(())
}

fn check_pubkey_encoding(v: &[u8], flags: &VerificationFlags) -> Result<(), Error> {
	if flags.verify_strictenc && !is_public_key(v) {
		return Err(Error::PubkeyType);
	}

	Ok(())
}

fn check_minimal_push(data: &[u8], opcode: Opcode) -> bool {
	if data.is_empty() {
		// Could have used OP_0.
		opcode == Opcode::OP_0
	} else if data.len() == 1 && data[0] >= 1 && data[0] <= 16 {
		// Could have used OP_1 .. OP_16.
		opcode as u8 == Opcode::OP_1 as u8 + (data[0] - 1)
	} else if data.len() == 1 && data[0] == 0x81 {
		// Could have used OP_1NEGATE
		opcode == Opcode::OP_1NEGATE
	} else if data.len() <= 75 {
		// Could have used a direct push (opcode indicating number of bytes pushed + those bytes).
		opcode as usize == data.len()
	} else if data.len() <= 255 {
		// Could have used OP_PUSHDATA.
		opcode == Opcode::OP_PUSHDATA1
	} else if data.len() <= 65535 {
		// Could have used OP_PUSHDATA2.
		opcode == Opcode::OP_PUSHDATA2
	} else {
		true
	}
}

fn cast_to_bool(data: &[u8]) -> bool {
	if data.is_empty() {
		return false;
	}

	if data[..data.len() - 1].iter().any(|x| x != &0) {
		return true;
	}

	let last = data[data.len() - 1];
	!(last == 0 || last == 0x80)
}

/// Verifies script signature and pubkey
pub fn verify_script(
	script_sig: &Script,
	script_pubkey: &Script,
	witness: &ScriptWitness,
	flags: &VerificationFlags,
	checker: &SignatureChecker,
	version: SignatureVersion,
) -> Result<(), Error> {
	if flags.verify_sigpushonly && !script_sig.is_push_only() {
		return Err(Error::SignaturePushOnly);
	}

	let mut stack = Stack::new();
	let mut stack_copy = Stack::new();
	let mut had_witness = false;

	eval_script(&mut stack, script_sig, flags, checker, version)?;

	if flags.verify_p2sh {
		stack_copy = stack.clone();
	}

	let res = eval_script(&mut stack, script_pubkey, flags, checker, version)?;
	if !res {
		return Err(Error::EvalFalse);
	}

	// Verify witness program
	let mut verify_cleanstack = flags.verify_cleanstack;
	if flags.verify_witness {
		if let Some((witness_version, witness_program)) = script_pubkey.parse_witness_program() {
			if !script_sig.is_empty() {
				return Err(Error::WitnessMalleated);
			}

			had_witness = true;
			verify_cleanstack = false;
			if !verify_witness_program(witness, witness_version, witness_program, flags, checker)? {
				return Err(Error::EvalFalse);
			}
		}
	}

	// Additional validation for spend-to-script-hash transactions:
	if flags.verify_p2sh && script_pubkey.is_pay_to_script_hash() {
		if !script_sig.is_push_only() {
			return Err(Error::SignaturePushOnly);
		}

		mem::swap(&mut stack, &mut stack_copy);

		// stack cannot be empty here, because if it was the
		// P2SH  HASH <> EQUAL  scriptPubKey would be evaluated with
		// an empty stack and the EvalScript above would return false.
		assert!(!stack.is_empty());

		let pubkey2: Script = stack.pop()?.into();

		let res = eval_script(&mut stack, &pubkey2, flags, checker, version)?;
		if !res {
			return Err(Error::EvalFalse);
		}

		if flags.verify_witness {
			if let Some((witness_version, witness_program)) = pubkey2.parse_witness_program() {
				if script_sig != &Builder::default().push_data(&pubkey2).into_script() {
					return Err(Error::WitnessMalleatedP2SH);
				}

				had_witness = true;
				verify_cleanstack = false;
				if !verify_witness_program(witness, witness_version, witness_program, flags, checker)? {
					return Err(Error::EvalFalse);
				}
			}
		}
	}

    // The CLEANSTACK check is only performed after potential P2SH evaluation,
    // as the non-P2SH evaluation of a P2SH script will obviously not result in
    // a clean stack (the P2SH inputs remain). The same holds for witness evaluation.
	if verify_cleanstack {
        // Disallow CLEANSTACK without P2SH, as otherwise a switch CLEANSTACK->P2SH+CLEANSTACK
        // would be possible, which is not a softfork (and P2SH should be one).
		assert!(flags.verify_p2sh);
		assert!(flags.verify_witness);
		if stack.len() != 1 {
			return Err(Error::Cleanstack);
		}
	}

	if flags.verify_witness {
		// We can't check for correct unexpected witness data if P2SH was off, so require
		// that WITNESS implies P2SH. Otherwise, going from WITNESS->P2SH+WITNESS would be
		// possible, which is not a softfork.
		assert!(flags.verify_p2sh);
		if !had_witness && !witness.is_empty() {
			return Err(Error::WitnessUnexpected);
		}
	}

	Ok(())
}

fn verify_witness_program(
	witness: &ScriptWitness,
	witness_version: u8,
	witness_program: &[u8],
	flags: &VerificationFlags,
	checker: &SignatureChecker,
) -> Result<bool, Error> {
	if witness_version != 0 {
		if flags.verify_discourage_upgradable_witness_program {
			return Err(Error::DiscourageUpgradableWitnessProgram);
		}

		return Ok(true);
	}

	let witness_stack = witness;
	let witness_stack_len = witness_stack.len();
	let (mut stack, script_pubkey): (Stack<_>, Script) = match witness_program.len() {
		32 => {
			if witness_stack_len == 0 {
				return Err(Error::WitnessProgramWitnessEmpty);
			}

			let script_pubkey = &witness_stack[witness_stack_len - 1];
			let stack = &witness_stack[0..witness_stack_len - 1];
			let script_pubkey_hash = sha256(script_pubkey);

			if script_pubkey_hash != witness_program[0..32].into() {
				return Err(Error::WitnessProgramMismatch);
			}

			(stack.iter().cloned().collect::<Vec<_>>().into(), Script::new(script_pubkey.clone()))
		},
		20 => {
			if witness_stack_len != 2 {
				return Err(Error::WitnessProgramMismatch);
			}

			let script_pubkey = Builder::default()
				.push_opcode(Opcode::OP_DUP)
				.push_opcode(Opcode::OP_HASH160)
				.push_data(witness_program)
				.push_opcode(Opcode::OP_EQUALVERIFY)
				.push_opcode(Opcode::OP_CHECKSIG)
				.into_script();

			(witness_stack.clone().into(), script_pubkey)
		},
		_ => return Err(Error::WitnessProgramWrongLength),
	};

	if stack.iter().any(|s| s.len() > MAX_SCRIPT_ELEMENT_SIZE) {
		return Err(Error::PushSize);
	}

	if !eval_script(&mut stack, &script_pubkey, flags, checker, SignatureVersion::WitnessV0)? {
		return Ok(false);
	}

	if stack.len() != 1 {
		return Err(Error::EvalFalse);
	}

	let success = cast_to_bool(stack.last().expect("stack.len() == 1; last() only returns errors when stack is empty; qed"));
	Ok(success)
}

/// Evaluautes the script
#[cfg_attr(feature="cargo-clippy", allow(match_same_arms))]
pub fn eval_script(
	stack: &mut Stack<Bytes>,
	script: &Script,
	flags: &VerificationFlags,
	checker: &SignatureChecker,
	version: SignatureVersion
) -> Result<bool, Error> {
	if script.len() > script::MAX_SCRIPT_SIZE {
		return Err(Error::ScriptSize);
	}

	let mut pc = 0;
	let mut op_count = 0;
	let mut begincode = 0;
	let mut exec_stack = Vec::<bool>::new();
	let mut altstack = Stack::<Bytes>::new();

	while pc < script.len() {
		let executing = exec_stack.iter().all(|x| *x);
		let instruction = match script.get_instruction(pc) {
			Ok(i) => i,
			Err(Error::BadOpcode) if !executing => {
				pc += 1;
				continue;
			},
			Err(err) => return Err(err),
		};
		let opcode = instruction.opcode;

		if let Some(data) = instruction.data {
			if data.len() > script::MAX_SCRIPT_ELEMENT_SIZE {
				return Err(Error::PushSize);
			}

			if executing && flags.verify_minimaldata && !check_minimal_push(data, opcode) {
				return Err(Error::Minimaldata);
			}
		}

		if opcode.is_countable() {
			op_count += 1;
			if op_count > script::MAX_OPS_PER_SCRIPT {
				return Err(Error::OpCount);
			}
		}

		if opcode.is_disabled(flags) {
			return Err(Error::DisabledOpcode(opcode));
		}

		pc += instruction.step;
		if !(executing || (Opcode::OP_IF <= opcode && opcode <= Opcode::OP_ENDIF)) {
			continue;
		}

		match opcode {
			Opcode::OP_PUSHDATA1 |
			Opcode::OP_PUSHDATA2 |
			Opcode::OP_PUSHDATA4 |
			Opcode::OP_0 |
			Opcode::OP_PUSHBYTES_1 |
			Opcode::OP_PUSHBYTES_2 |
			Opcode::OP_PUSHBYTES_3 |
			Opcode::OP_PUSHBYTES_4 |
			Opcode::OP_PUSHBYTES_5 |
			Opcode::OP_PUSHBYTES_6 |
			Opcode::OP_PUSHBYTES_7 |
			Opcode::OP_PUSHBYTES_8 |
			Opcode::OP_PUSHBYTES_9 |
			Opcode::OP_PUSHBYTES_10 |
			Opcode::OP_PUSHBYTES_11 |
			Opcode::OP_PUSHBYTES_12 |
			Opcode::OP_PUSHBYTES_13 |
			Opcode::OP_PUSHBYTES_14 |
			Opcode::OP_PUSHBYTES_15 |
			Opcode::OP_PUSHBYTES_16 |
			Opcode::OP_PUSHBYTES_17 |
			Opcode::OP_PUSHBYTES_18 |
			Opcode::OP_PUSHBYTES_19 |
			Opcode::OP_PUSHBYTES_20 |
			Opcode::OP_PUSHBYTES_21 |
			Opcode::OP_PUSHBYTES_22 |
			Opcode::OP_PUSHBYTES_23 |
			Opcode::OP_PUSHBYTES_24 |
			Opcode::OP_PUSHBYTES_25 |
			Opcode::OP_PUSHBYTES_26 |
			Opcode::OP_PUSHBYTES_27 |
			Opcode::OP_PUSHBYTES_28 |
			Opcode::OP_PUSHBYTES_29 |
			Opcode::OP_PUSHBYTES_30 |
			Opcode::OP_PUSHBYTES_31 |
			Opcode::OP_PUSHBYTES_32 |
			Opcode::OP_PUSHBYTES_33 |
			Opcode::OP_PUSHBYTES_34 |
			Opcode::OP_PUSHBYTES_35 |
			Opcode::OP_PUSHBYTES_36 |
			Opcode::OP_PUSHBYTES_37 |
			Opcode::OP_PUSHBYTES_38 |
			Opcode::OP_PUSHBYTES_39 |
			Opcode::OP_PUSHBYTES_40 |
			Opcode::OP_PUSHBYTES_41 |
			Opcode::OP_PUSHBYTES_42 |
			Opcode::OP_PUSHBYTES_43 |
			Opcode::OP_PUSHBYTES_44 |
			Opcode::OP_PUSHBYTES_45 |
			Opcode::OP_PUSHBYTES_46 |
			Opcode::OP_PUSHBYTES_47 |
			Opcode::OP_PUSHBYTES_48 |
			Opcode::OP_PUSHBYTES_49 |
			Opcode::OP_PUSHBYTES_50 |
			Opcode::OP_PUSHBYTES_51 |
			Opcode::OP_PUSHBYTES_52 |
			Opcode::OP_PUSHBYTES_53 |
			Opcode::OP_PUSHBYTES_54 |
			Opcode::OP_PUSHBYTES_55 |
			Opcode::OP_PUSHBYTES_56 |
			Opcode::OP_PUSHBYTES_57 |
			Opcode::OP_PUSHBYTES_58 |
			Opcode::OP_PUSHBYTES_59 |
			Opcode::OP_PUSHBYTES_60 |
			Opcode::OP_PUSHBYTES_61 |
			Opcode::OP_PUSHBYTES_62 |
			Opcode::OP_PUSHBYTES_63 |
			Opcode::OP_PUSHBYTES_64 |
			Opcode::OP_PUSHBYTES_65 |
			Opcode::OP_PUSHBYTES_66 |
			Opcode::OP_PUSHBYTES_67 |
			Opcode::OP_PUSHBYTES_68 |
			Opcode::OP_PUSHBYTES_69 |
			Opcode::OP_PUSHBYTES_70 |
			Opcode::OP_PUSHBYTES_71 |
			Opcode::OP_PUSHBYTES_72 |
			Opcode::OP_PUSHBYTES_73 |
			Opcode::OP_PUSHBYTES_74 |
			Opcode::OP_PUSHBYTES_75 => {
				if let Some(data) = instruction.data {
					stack.push(data.to_vec().into());
				}
			},
			Opcode::OP_1NEGATE |
			Opcode::OP_1 |
			Opcode::OP_2 |
			Opcode::OP_3 |
			Opcode::OP_4 |
			Opcode::OP_5 |
			Opcode::OP_6 |
			Opcode::OP_7 |
			Opcode::OP_8 |
			Opcode::OP_9 |
			Opcode::OP_10 |
			Opcode::OP_11 |
			Opcode::OP_12 |
			Opcode::OP_13 |
			Opcode::OP_14 |
			Opcode::OP_15 |
			Opcode::OP_16 => {
				let value = (opcode as i32).wrapping_sub(Opcode::OP_1 as i32 - 1);
				stack.push(Num::from(value).to_bytes());
			},
			Opcode::OP_CAT if flags.verify_concat => {
				let mut value_to_append = stack.pop()?;
				let value_to_update = stack.last_mut()?;
				if value_to_update.len() + value_to_append.len() > script::MAX_SCRIPT_ELEMENT_SIZE {
					return Err(Error::PushSize);
				}
				value_to_update.append(&mut value_to_append);
			},
			Opcode::OP_CAT | Opcode::OP_SUBSTR | Opcode::OP_LEFT | Opcode::OP_RIGHT |
			Opcode::OP_INVERT | Opcode::OP_AND | Opcode::OP_OR | Opcode::OP_XOR |
			Opcode::OP_2MUL | Opcode::OP_2DIV | Opcode::OP_MUL | Opcode::OP_DIV |
			Opcode::OP_MOD | Opcode::OP_LSHIFT | Opcode::OP_RSHIFT => {
				return Err(Error::DisabledOpcode(opcode));
			},
			Opcode::OP_NOP => (),
			Opcode::OP_CHECKLOCKTIMEVERIFY => {
				if flags.verify_locktime {
					// Note that elsewhere numeric opcodes are limited to
					// operands in the range -2**31+1 to 2**31-1, however it is
					// legal for opcodes to produce results exceeding that
					// range. This limitation is implemented by CScriptNum's
					// default 4-byte limit.
					//
					// If we kept to that limit we'd have a year 2038 problem,
					// even though the nLockTime field in transactions
					// themselves is uint32 which only becomes meaningless
					// after the year 2106.
					//
					// Thus as a special case we tell CScriptNum to accept up
					// to 5-byte bignums, which are good until 2**39-1, well
					// beyond the 2**32-1 limit of the nLockTime field itself.
					let lock_time = Num::from_slice(stack.last()?, flags.verify_minimaldata, 5)?;

					// In the rare event that the argument may be < 0 due to
					// some arithmetic being done first, you can always use
					// 0 MAX CHECKLOCKTIMEVERIFY.
					if lock_time.is_negative() {
						return Err(Error::NegativeLocktime);
					}

					if !checker.check_lock_time(lock_time) {
						return Err(Error::UnsatisfiedLocktime);
					}
				} else if flags.verify_discourage_upgradable_nops {
					return Err(Error::DiscourageUpgradableNops);
				}
			},
			Opcode::OP_CHECKSEQUENCEVERIFY => {
				if flags.verify_checksequence {
					let sequence = Num::from_slice(stack.last()?, flags.verify_minimaldata, 5)?;

					if sequence.is_negative() {
						return Err(Error::NegativeLocktime);
					}

					if (sequence & (SEQUENCE_LOCKTIME_DISABLE_FLAG as i64).into()).is_zero() && !checker.check_sequence(sequence) {
						return Err(Error::UnsatisfiedLocktime);
					}

				} else if flags.verify_discourage_upgradable_nops {
					return Err(Error::DiscourageUpgradableNops);
				}
			},
			Opcode::OP_NOP1 |
			Opcode::OP_NOP4 |
			Opcode::OP_NOP5 |
			Opcode::OP_NOP6 |
			Opcode::OP_NOP7 |
			Opcode::OP_NOP8 |
			Opcode::OP_NOP9 |
			Opcode::OP_NOP10 => {
				if flags.verify_discourage_upgradable_nops {
					return Err(Error::DiscourageUpgradableNops);
				}
			},
			Opcode::OP_IF | Opcode::OP_NOTIF => {
				let mut exec_value = false;
				if executing {
					exec_value = cast_to_bool(&stack.pop().map_err(|_| Error::UnbalancedConditional)?);
					if opcode == Opcode::OP_NOTIF {
						exec_value = !exec_value;
					}
				}
				exec_stack.push(exec_value);
			},
			Opcode::OP_ELSE => {
				if exec_stack.is_empty() {
					return Err(Error::UnbalancedConditional);
				}
				let last_index = exec_stack.len() - 1;
				let last = exec_stack[last_index];
				exec_stack[last_index] = !last;
			},
			Opcode::OP_ENDIF => {
				if exec_stack.is_empty() {
					return Err(Error::UnbalancedConditional);
				}
				exec_stack.pop();
			},
			Opcode::OP_VERIFY => {
				let exec_value = cast_to_bool(&stack.pop()?);
				if !exec_value {
					return Err(Error::Verify);
				}
			},
			Opcode::OP_RETURN => {
				return Err(Error::ReturnOpcode);
			},
			Opcode::OP_TOALTSTACK => {
				altstack.push(stack.pop()?);
			},
			Opcode::OP_FROMALTSTACK => {
				stack.push(altstack.pop().map_err(|_| Error::InvalidAltstackOperation)?);
			},
			Opcode::OP_2DROP => {
				stack.drop(2)?;
			},
			Opcode::OP_2DUP => {
				stack.dup(2)?;
			},
			Opcode::OP_3DUP => {
				stack.dup(3)?;
			},
			Opcode::OP_2OVER => {
				stack.over(2)?;
			},
			Opcode::OP_2ROT => {
				stack.rot(2)?;
			},
			Opcode::OP_2SWAP => {
				stack.swap(2)?;
			},
			Opcode::OP_IFDUP => {
				if cast_to_bool(stack.last()?) {
					stack.dup(1)?;
				}
			},
			Opcode::OP_DEPTH => {
				let depth = Num::from(stack.len());
				stack.push(depth.to_bytes());
			},
			Opcode::OP_DROP => {
				stack.pop()?;
			},
			Opcode::OP_DUP => {
				stack.dup(1)?;
			},
			Opcode::OP_NIP => {
				stack.nip()?;
			},
			Opcode::OP_OVER => {
				stack.over(1)?;
			},
			Opcode::OP_PICK | Opcode::OP_ROLL => {
				let n: i64 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?.into();
				if n < 0 || n >= stack.len() as i64 {
					return Err(Error::InvalidStackOperation);
				}

				let v = match opcode {
					Opcode::OP_PICK => stack.top(n as usize)?.clone(),
					_ => stack.remove(n as usize)?,
				};

				stack.push(v);
			},
			Opcode::OP_ROT => {
				stack.rot(1)?;
			},
			Opcode::OP_SWAP => {
				stack.swap(1)?;
			},
			Opcode::OP_TUCK => {
				stack.tuck()?;
			},
			Opcode::OP_SIZE => {
				let n = Num::from(stack.last()?.len());
				stack.push(n.to_bytes());
			},
			Opcode::OP_EQUAL => {
				let v1 = stack.pop()?;
				let v2 = stack.pop()?;
				if v1 == v2 {
					stack.push(vec![1].into());
				} else {
					stack.push(vec![0].into());
				}
			},
			Opcode::OP_EQUALVERIFY => {
				let equal = stack.pop()? == stack.pop()?;
				if !equal {
					return Err(Error::EqualVerify);
				}
			},
			Opcode::OP_1ADD => {
				let n = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)? + 1.into();
				stack.push(n.to_bytes());
			},
			Opcode::OP_1SUB => {
				let n = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)? - 1.into();
				stack.push(n.to_bytes());
			},
			Opcode::OP_NEGATE => {
				let n = -Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				stack.push(n.to_bytes());
			},
			Opcode::OP_ABS => {
				let n = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?.abs();
				stack.push(n.to_bytes());
			},
			Opcode::OP_NOT => {
				let n = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?.is_zero();
				let n = Num::from(n);
				stack.push(n.to_bytes());
			},
			Opcode::OP_0NOTEQUAL => {
				let n = !Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?.is_zero();
				let n = Num::from(n);
				stack.push(n.to_bytes());
			},
			Opcode::OP_ADD => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				stack.push((v1 + v2).to_bytes());
			},
			Opcode::OP_SUB => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				stack.push((v2 - v1).to_bytes());
			},
			Opcode::OP_BOOLAND => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v = Num::from(!v1.is_zero() && !v2.is_zero());
				stack.push(v.to_bytes());
			},
			Opcode::OP_BOOLOR => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v = Num::from(!v1.is_zero() || !v2.is_zero());
				stack.push(v.to_bytes());
			},
			Opcode::OP_NUMEQUAL => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v = Num::from(v1 == v2);
				stack.push(v.to_bytes());
			},
			Opcode::OP_NUMEQUALVERIFY => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				if v1 != v2 {
					return Err(Error::NumEqualVerify);
				}
			},
			Opcode::OP_NUMNOTEQUAL => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v = Num::from(v1 != v2);
				stack.push(v.to_bytes());
			},
			Opcode::OP_LESSTHAN => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v = Num::from(v1 > v2);
				stack.push(v.to_bytes());
			},
			Opcode::OP_GREATERTHAN => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v = Num::from(v1 < v2);
				stack.push(v.to_bytes());
			},
			Opcode::OP_LESSTHANOREQUAL => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v = Num::from(v1 >= v2);
				stack.push(v.to_bytes());
			},
			Opcode::OP_GREATERTHANOREQUAL => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v = Num::from(v1 <= v2);
				stack.push(v.to_bytes());
			},
			Opcode::OP_MIN => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				stack.push(cmp::min(v1, v2).to_bytes());
			},
			Opcode::OP_MAX => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				stack.push(cmp::max(v1, v2).to_bytes());
			},
			Opcode::OP_WITHIN => {
				let v1 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v2 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				let v3 = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				if v2 <= v3 && v3 < v1 {
					stack.push(vec![1].into());
				} else {
					stack.push(vec![0].into());
				}
			},
			Opcode::OP_RIPEMD160 => {
				let v = ripemd160(&stack.pop()?);
				stack.push(v.to_vec().into());
			},
			Opcode::OP_SHA1 => {
				let v = sha1(&stack.pop()?);
				stack.push(v.to_vec().into());
			},
			Opcode::OP_SHA256 => {
				let v = sha256(&stack.pop()?);
				stack.push(v.to_vec().into());
			},
			Opcode::OP_HASH160 => {
				let v = dhash160(&stack.pop()?);
				stack.push(v.to_vec().into());
			},
			Opcode::OP_HASH256 => {
				let v = dhash256(&stack.pop()?);
				stack.push(v.to_vec().into());
			},
			Opcode::OP_CODESEPARATOR => {
				begincode = pc;
			},
			Opcode::OP_CHECKSIG | Opcode::OP_CHECKSIGVERIFY => {
				let pubkey = stack.pop()?;
				let signature = stack.pop()?;
				let sighash = parse_hash_type(version, &signature);
				let mut subscript = script.subscript(begincode);
				match version {
					SignatureVersion::ForkId if sighash.fork_id => (),
					SignatureVersion::WitnessV0 => (),
					SignatureVersion::Base | SignatureVersion::ForkId => {
						let signature_script = Builder::default().push_data(&*signature).into_script();
						subscript = subscript.find_and_delete(&*signature_script);
					},
				}

				check_signature_encoding(&signature, flags, version)?;
				check_pubkey_encoding(&pubkey, flags)?;

				let success = check_signature(checker, signature.into(), pubkey.into(), &subscript, version);
				match opcode {
					Opcode::OP_CHECKSIG => {
						if success {
							stack.push(vec![1].into());
						} else {
							stack.push(vec![0].into());
						}
					},
					Opcode::OP_CHECKSIGVERIFY if !success => {
						return Err(Error::CheckSigVerify);
					},
					_ => {},
				}
			},
			Opcode::OP_CHECKMULTISIG | Opcode::OP_CHECKMULTISIGVERIFY => {
				let keys_count = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				if keys_count < 0.into() || keys_count > script::MAX_PUBKEYS_PER_MULTISIG.into() {
					return Err(Error::PubkeyCount);
				}

				let keys_count: usize = keys_count.into();
				let keys = (0..keys_count).into_iter().map(|_| stack.pop()).collect::<Result<Vec<_>, _>>()?;

				let sigs_count = Num::from_slice(&stack.pop()?, flags.verify_minimaldata, 4)?;
				if sigs_count < 0.into() || sigs_count > keys_count.into() {
					return Err(Error::SigCount);
				}

				let sigs_count: usize = sigs_count.into();
				let sigs = (0..sigs_count).into_iter().map(|_| stack.pop()).collect::<Result<Vec<_>, _>>()?;

				let mut subscript = script.subscript(begincode);

				for signature in &sigs {
					let sighash = parse_hash_type(version, &signature);
					match version {
						SignatureVersion::ForkId if sighash.fork_id => (),
						SignatureVersion::WitnessV0 => (),
						SignatureVersion::Base | SignatureVersion::ForkId => {
							let signature_script = Builder::default().push_data(&*signature).into_script();
							subscript = subscript.find_and_delete(&*signature_script);
						},
					}
				}

				let mut success = true;
				let mut k = 0;
				let mut s = 0;
				while s < sigs.len() && success {
					// TODO: remove redundant copying
					let key = keys[k].clone();
					let sig = sigs[s].clone();

					check_signature_encoding(&sig, flags, version)?;
					check_pubkey_encoding(&key, flags)?;

					let ok = check_signature(checker, sig.into(), key.into(), &subscript, version);
					if ok {
						s += 1;
					}
					k += 1;

					success = sigs.len() - s <= keys.len() - k;
				}

				if !stack.pop()?.is_empty() && flags.verify_nulldummy {
					return Err(Error::SignatureNullDummy);
				}

				match opcode {
					Opcode::OP_CHECKMULTISIG => {
						if success {
							stack.push(vec![1].into());
						} else {
							stack.push(vec![0].into());
						}
					},
					Opcode::OP_CHECKMULTISIGVERIFY if !success => {