1use std::borrow::Cow;
2use std::sync::Arc;
3
4use bitcoin_cash::{
5 encoding_utils::{encode_bool, encode_int, vec_to_int},
6 Function, Hashed, Integer, Op, Opcode, Ops, Script, SigHashFlags, StackItemData,
7 StackItemDelta, TaggedOp, Tx,
8};
9use bitcoin_cash::{error, ByteArray, Hash160, Ripemd160, Sha1, Sha256, Sha256d, ECC};
10use std::convert::TryInto;
11
12pub struct ScriptInterpreter<E: ECC> {
13 stack: Vec<StackItem>,
14 alt_stack: Vec<StackItem>,
15 tx: Arc<Tx>,
16 lock_script: Script,
17 instruction_pointer: usize,
18 exec_stack: Vec<bool>,
19 ecc: Arc<E>,
20 input_idx: usize,
21}
22
23#[derive(Clone, Debug)]
24pub enum ScriptError {
25 InvalidPubKey(ByteArray),
26 InvalidSignatureFormat(ByteArray),
27 InvalidSignature(ByteArray, ByteArray),
28 EqualVerifyFailed(ByteArray, ByteArray),
29 VerifyFailed,
30 NotImplemented,
31 ScriptFinished,
32 InvalidDataType,
33 StackEmpty,
34 OpcodeMsg(Opcode, Cow<'static, str>),
35 UnbalancedConditionals(Opcode),
36 InvalidOpcode(u8),
37 InvalidDepth(Integer),
38}
39
40#[derive(Clone, Debug, PartialEq, Eq)]
41pub struct StackItem {
42 pub data: StackItemData,
43 pub name: Option<Arc<Cow<'static, str>>>,
44 pub delta: StackItemDelta,
45}
46impl StackItem {
47 pub fn to_bool(&self) -> bool {
48 match self.data {
49 StackItemData::Integer(int) => int != 0,
50 StackItemData::Boolean(boolean) => boolean,
51 StackItemData::ByteArray(ref array) => array.len() > 0,
52 }
53 }
54}
55
56impl<E: ECC> ScriptInterpreter<E> {
57 pub fn new(tx: Arc<Tx>, input_idx: usize, ecc: Arc<E>) -> Self {
58 ScriptInterpreter {
59 stack: Vec::new(),
60 alt_stack: Vec::new(),
61 instruction_pointer: 0,
62 lock_script: tx.inputs()[input_idx]
63 .lock_script
64 .clone()
65 .expect("Input must have lock_script"),
66 tx,
67 input_idx,
68 exec_stack: Vec::new(),
69 ecc,
70 }
71 }
72
73 fn pop(&mut self) -> Result<StackItem, ScriptError> {
74 if let Some(item) = self.stack.pop() {
75 return Ok(item);
76 }
77 return Err(ScriptError::StackEmpty);
78 }
79
80 fn pop_bool(&mut self) -> Result<bool, ScriptError> {
81 match self.pop()?.data {
82 StackItemData::ByteArray(_) => Err(ScriptError::InvalidDataType),
83 StackItemData::Integer(int) => Ok(int != 0),
84 StackItemData::Boolean(boolean) => Ok(boolean),
85 }
86 }
87
88 fn pop_int(&mut self) -> Result<Integer, ScriptError> {
89 match self.pop()?.data {
90 StackItemData::ByteArray(_) => Err(ScriptError::InvalidDataType),
91 StackItemData::Integer(int) => Ok(int),
92 StackItemData::Boolean(boolean) => Ok(if boolean { 1 } else { 0 }),
93 }
94 }
95
96 fn pop_byte_array(&mut self) -> Result<ByteArray, ScriptError> {
97 match self.pop()?.data {
98 StackItemData::ByteArray(byte_array) => Ok(byte_array),
99 StackItemData::Integer(int) => Ok(encode_int(int).into()),
100 StackItemData::Boolean(boolean) => Ok(encode_bool(boolean).into()),
101 }
102 }
103
104 pub fn run(&mut self) -> Result<bool, ScriptError> {
105 while !self.is_finished() {
106 self.run_next_op()?;
107 }
108 Ok(self.stack[0].to_bool())
109 }
110
111 pub fn push_input_data(&mut self) -> Result<(), ScriptError> {
112 let input_script = Arc::clone(self.tx.inputs()[self.input_idx].script.ops_arc());
113 for op in &input_script[..input_script.len() - 1] {
114 self.run_op(op)?;
115 }
116 Ok(())
117 }
118
119 pub fn is_finished(&self) -> bool {
120 self.instruction_pointer >= self.lock_script.ops().len()
121 }
122
123 pub fn instruction_pointer(&self) -> usize {
124 self.instruction_pointer
125 }
126
127 pub fn run_next_op(&mut self) -> Result<(), ScriptError> {
128 if self.instruction_pointer >= self.lock_script.ops().len() {
129 return Err(ScriptError::ScriptFinished);
130 }
131 let ops = Arc::clone(self.lock_script.ops_arc());
132 self.run_op(&ops[self.instruction_pointer])?;
133 self.instruction_pointer += 1;
134 Ok(())
135 }
136
137 pub fn stack(&self) -> &[StackItem] {
138 &self.stack
139 }
140
141 pub fn alt_stack(&self) -> &[StackItem] {
142 &self.alt_stack
143 }
144
145 pub fn exec_stack(&self) -> &[bool] {
146 &self.exec_stack
147 }
148
149 fn push_tagged_data(&mut self, op: &TaggedOp, data: StackItemData) {
150 self.push_tagged_data_idx(op, data, 0);
151 }
152
153 fn push_tagged_data_idx(&mut self, op: &TaggedOp, mut data: StackItemData, idx: usize) {
154 let name = op
155 .pushed_names
156 .as_ref()
157 .and_then(|names| names.get(idx).cloned())
158 .flatten()
159 .map(Arc::new);
160 if let StackItemData::ByteArray(array) = data {
161 data = StackItemData::ByteArray(array.named_option(name.clone()));
162 }
163 let delta = match &op.op {
164 Op::Code(opcode) => *opcode.behavior().delta.get(idx).unwrap_or(&StackItemDelta::Removed),
165 Op::PushBoolean(_) | Op::PushByteArray { .. } | Op::PushInteger(_) => {
166 StackItemDelta::Added
167 }
168 Op::Invalid(_) => StackItemDelta::Untouched,
169 };
170 self.stack.push(StackItem { data, name, delta })
171 }
172
173 fn run_op(&mut self, op: &TaggedOp) -> Result<(), ScriptError> {
174 self.stack
175 .iter_mut()
176 .for_each(|stack| stack.delta = StackItemDelta::Untouched);
177
178 let is_executed = self.exec_stack.iter().all(|&x| x);
179 use Opcode::*;
180 if let Op::Code(OP_IF) | Op::Code(OP_ELSE) | Op::Code(OP_ENDIF) = &op.op {
181 } else {
182 if !is_executed {
183 return Ok(());
184 }
185 }
186 match op.op {
187 Op::PushBoolean(data) => {
188 self.push_tagged_data(op, StackItemData::Boolean(data));
189 Ok(())
190 }
191 Op::PushInteger(data) => {
192 self.push_tagged_data(op, StackItemData::Integer(data));
193 Ok(())
194 }
195 Op::PushByteArray { ref array, .. } => {
196 self.push_tagged_data(op, StackItemData::ByteArray(array.clone()));
197 Ok(())
198 }
199 Op::Code(code) => self.run_opcode(op, code, is_executed),
200 Op::Invalid(code) => Err(ScriptError::InvalidOpcode(code)),
201 }
202 }
203
204 fn pop_depth_to_idx(&mut self) -> Result<usize, ScriptError> {
205 let depth = self.pop_int()?;
206 let depth = depth.try_into().map_err(|_| ScriptError::InvalidDepth(depth))?;
207 self.stack.len()
208 .checked_sub(depth)
209 .and_then(|x| x.checked_sub(1))
210 .ok_or(ScriptError::InvalidDepth(depth as Integer))
211 }
212
213 fn run_opcode(
214 &mut self,
215 op: &TaggedOp,
216 opcode: Opcode,
217 is_executed: bool,
218 ) -> Result<(), ScriptError> {
219 use self::ScriptError::*;
220 use Opcode::*;
221
222 match opcode {
223 OP_PICK => {
224 let item_idx = self.pop_depth_to_idx()?;
225 let mut item = self.stack[item_idx].clone();
226 item.delta = StackItemDelta::Added;
227 self.stack.push(item);
228 }
229 OP_ROLL => {
230 let item_idx = self.pop_depth_to_idx()?;
231 self.stack[item_idx..]
232 .iter_mut()
233 .for_each(|item| item.delta = StackItemDelta::MovedIndirectly);
234 let mut item = self.stack.remove(item_idx);
235 item.delta = StackItemDelta::Moved;
236 self.stack.push(item);
237 }
238 OP_TOALTSTACK => {
239 let top = self.stack.remove(self.stack.len() - 1);
240 self.alt_stack.push(top);
241 }
242 OP_FROMALTSTACK => {
243 let top = self.alt_stack.remove(self.alt_stack.len() - 1);
244 self.push_tagged_data(op, top.data);
245 }
246 OP_CAT => {
247 let first = self.pop_byte_array()?;
248 let second = self.pop_byte_array()?;
249 self.push_tagged_data(op, StackItemData::ByteArray(second.concat(first)));
250 }
251 OP_SPLIT => {
252 let split_idx = self.pop_int()? as usize;
253 let top = self.pop_byte_array()?;
254 let (left, right) = top
255 .split(split_idx)
256 .map_err(|err| ScriptError::OpcodeMsg(OP_SPLIT, err.into()))?;
257 self.push_tagged_data_idx(op, StackItemData::ByteArray(left), 0);
258 self.push_tagged_data_idx(op, StackItemData::ByteArray(right), 1);
259 }
260 OP_NUM2BIN => {
261 let n_bytes = self.pop_int()?;
262 let int = self.pop_int()?;
263 self.push_tagged_data(
264 op,
265 StackItemData::ByteArray(
266 ByteArray::from_int(int, n_bytes)
267 .map_err(|err| ScriptError::OpcodeMsg(OP_NUM2BIN, err.into()))?,
268 ),
269 );
270 }
271 OP_BIN2NUM => {
272 let array = self.pop_byte_array()?;
273 self.push_tagged_data(op, StackItemData::Integer(vec_to_int(&array)));
274 }
275 OP_SIZE => {
276 let array = &self.stack[self.stack.len() - 1].data;
277 if let StackItemData::ByteArray(array) = array {
278 let len = array.len() as Integer;
279 self.push_tagged_data(op, StackItemData::Integer(len));
280 } else {
281 return Err(ScriptError::InvalidDataType);
282 }
283 }
284 OP_SHA1 => {
285 let array = self.pop_byte_array()?;
286 self.push_tagged_data(
287 op,
288 StackItemData::ByteArray(Sha1::digest(array).into_byte_array()),
289 );
290 }
291 OP_RIPEMD160 => {
292 let array = self.pop_byte_array()?;
293 self.push_tagged_data(
294 op,
295 StackItemData::ByteArray(Ripemd160::digest(array).into_byte_array()),
296 );
297 }
298 OP_HASH256 => {
299 let array = self.pop_byte_array()?;
300 self.push_tagged_data(
301 op,
302 StackItemData::ByteArray(Sha256d::digest(array).into_byte_array()),
303 );
304 }
305 OP_SHA256 => {
306 let array = self.pop_byte_array()?;
307 self.push_tagged_data(
308 op,
309 StackItemData::ByteArray(Sha256::digest(array).into_byte_array()),
310 );
311 }
312 OP_HASH160 => {
313 let array = self.pop_byte_array()?;
314 self.push_tagged_data(
315 op,
316 StackItemData::ByteArray(Hash160::digest(array).into_byte_array()),
317 );
318 }
319 OP_EQUAL | OP_EQUALVERIFY => {
320 let first = self.pop_byte_array()?;
321 let second = self.pop_byte_array()?;
322 let equal = &first == &second;
323 if opcode == OP_EQUALVERIFY {
324 if !equal {
325 return Err(EqualVerifyFailed(first, second));
326 }
327 } else {
328 self.push_tagged_data(op, StackItemData::Boolean(equal));
329 }
330 }
331 OP_NUMEQUALVERIFY => {
332 let first = self.pop_int()?;
333 let second = self.pop_int()?;
334 if first != second {
335 return Err(VerifyFailed);
336 }
337 }
338 OP_NOT => {
339 let boolean = self.pop_bool()?;
340 self.push_tagged_data(op, StackItemData::Boolean(!boolean));
341 }
342 OP_GREATERTHAN => {
343 let first = self.pop_int()?;
344 let second = self.pop_int()?;
345 self.push_tagged_data(op, StackItemData::Boolean(second > first));
346 }
347 OP_GREATERTHANOREQUAL => {
348 let first = self.pop_int()?;
349 let second = self.pop_int()?;
350 self.push_tagged_data(op, StackItemData::Boolean(second >= first));
351 }
352 OP_LESSTHANOREQUAL => {
353 let first = self.pop_int()?;
354 let second = self.pop_int()?;
355 self.push_tagged_data(op, StackItemData::Boolean(second <= first));
356 }
357 OP_LESSTHAN => {
358 let first = self.pop_int()?;
359 let second = self.pop_int()?;
360 self.push_tagged_data(op, StackItemData::Boolean(second < first));
361 }
362 OP_MIN => {
363 let first = self.pop_int()?;
364 let second = self.pop_int()?;
365 self.push_tagged_data(op, StackItemData::Integer(second.min(first)));
366 }
367 OP_MAX => {
368 let first = self.pop_int()?;
369 let second = self.pop_int()?;
370 self.push_tagged_data(op, StackItemData::Integer(second.max(first)));
371 }
372 OP_0NOTEQUAL => {
373 let top = self.pop_int()?;
374 self.push_tagged_data(op, StackItemData::Boolean(top != 0));
375 }
376 OP_ADD => {
377 let b = self.pop_int()?;
378 let a = self.pop_int()?;
379 self.push_tagged_data(op, StackItemData::Integer(a + b));
380 }
381 OP_SUB => {
382 let b = self.pop_int()?;
383 let a = self.pop_int()?;
384 self.push_tagged_data(op, StackItemData::Integer(a - b));
385 }
386 OP_DIV => {
387 let b = self.pop_int()?;
388 let a = self.pop_int()?;
389 if b == 0 {
390 return Err(ScriptError::OpcodeMsg(opcode, "Division by 0".into()));
391 }
392 self.push_tagged_data(op, StackItemData::Integer(a / b));
393 }
394 OP_MOD => {
395 let b = self.pop_int()?;
396 let a = self.pop_int()?;
397 if b == 0 {
398 return Err(ScriptError::OpcodeMsg(opcode, "Modulo by 0".into()));
399 }
400 self.push_tagged_data(op, StackItemData::Integer(a % b));
401 }
402 OP_IF => {
403 let top = if is_executed { self.pop_bool()? } else { false };
404 self.exec_stack.push(top);
405 }
406 OP_ELSE => {
407 let top_exec = self
408 .exec_stack
409 .last_mut()
410 .ok_or(ScriptError::UnbalancedConditionals(OP_ELSE))?;
411 *top_exec = !*top_exec;
412 }
413 OP_ENDIF => {
414 self.exec_stack
415 .pop()
416 .ok_or(ScriptError::UnbalancedConditionals(OP_ENDIF))?;
417 }
418 OP_VERIFY => {
419 let top = self.pop()?;
420 if !top.to_bool() {
421 return Err(VerifyFailed);
422 }
423 }
424 OP_CHECKSIG | OP_CHECKSIGVERIFY | OP_CHECKDATASIG | OP_CHECKDATASIGVERIFY => {
425 let pubkey = self.pop_byte_array()?;
426 let (msg, sig_ser) = match opcode {
427 OP_CHECKSIG | OP_CHECKSIGVERIFY => {
428 let sig = self.pop_byte_array()?;
429 let mut sig_ser = sig.to_vec();
430 let sig_hash_flags = if sig_ser.len() > 0 {
431 [SigHashFlags::from_u8(sig_ser.remove(sig_ser.len() - 1))]
432 } else {
433 [SigHashFlags::DEFAULT]
434 };
435 let preimages =
436 self.tx.preimages(&sig_hash_flags)[self.input_idx][0].to_byte_array();
437 let sig = sig.apply_function(sig_ser, Function::ToDataSig);
438 (Sha256d::digest(preimages).into_byte_array(), sig)
439 }
440 OP_CHECKDATASIG | OP_CHECKDATASIGVERIFY => {
441 let msg = Sha256::digest(self.pop_byte_array()?).into_byte_array();
442 (msg, self.pop_byte_array()?)
443 }
444 _ => unreachable!(),
445 };
446 let validity = match self.ecc.verify(&pubkey, &msg, &sig_ser) {
447 Ok(validity) => validity,
448 Err(error::Error(error::ErrorKind::InvalidPubkey, _)) => {
449 return Err(ScriptError::InvalidPubKey(pubkey))
450 }
451 Err(error::Error(error::ErrorKind::InvalidSignatureFormat, _)) => {
452 return Err(ScriptError::InvalidSignatureFormat(sig_ser))
453 }
454 Err(err) => return Err(ScriptError::OpcodeMsg(opcode, err.to_string().into())),
455 };
456 if opcode == OP_CHECKSIG || opcode == OP_CHECKDATASIG {
457 if sig_ser.len() > 0 && !validity {
458 return Err(InvalidSignature(msg, sig_ser));
459 }
460 self.push_tagged_data(op, StackItemData::Boolean(validity));
461 } else {
462 if !validity {
463 return Err(InvalidSignature(msg, sig_ser));
464 }
465 }
466 }
467 OP_REVERSEBYTES => {
468 let array = self.pop_byte_array()?;
469 let mut reversed = array.to_vec();
470 reversed.reverse();
471 self.push_tagged_data(
472 op,
473 StackItemData::ByteArray(array.apply_function(reversed, Function::Reverse)),
474 );
475 }
476 OP_CODESEPARATOR => {}
477 OP_CHECKLOCKTIMEVERIFY => {
478 let lock_time = self.pop_int()?;
479 if self.tx.lock_time() < lock_time as u32 {
480 return Err(VerifyFailed);
481 }
482 self.push_tagged_data(op, StackItemData::Integer(lock_time));
483 }
484 _ => {
485 let behavior = opcode.behavior();
486 let input_items = self
487 .stack
488 .drain(self.stack.len() - behavior.input_types.len()..)
489 .collect::<Vec<_>>();
490 if let Some(output_order) = behavior.output_order {
491 for (&new_idx, &delta) in output_order.iter().zip(behavior.delta) {
492 self.stack.push(StackItem {
493 delta,
494 ..input_items[new_idx].clone()
495 });
496 }
497 } else {
498 return Err(ScriptError::NotImplemented);
499 }
500 }
501 };
502 Ok(())
503 }
504}