A deserialized script probably could not contain following nodes:

Inputs
Outputs
Self
Height
LastBlockUtxoRootHash
TaggedVariable[_]

as this nodes are to be rewritten in the same bottom-up rewrite, which is to be executed once.

Is this limitation serious? Should we do something with it, or just document it?

See todos in the following tests in ErgoInterpreterSpecification:

• prove keys from registers
• Along with a brother

Append(coll1, coll2)
Slice(coll1, start, end)

1. Check that cost() everywhere includes costs of node's children
2. Add some argument to cost to define cost of involved parts of the box and context, in TaggedVariable[] and Extract[] families

Now it is formatted incorrectly in a lot of places. Better to do it at some point, with no PR to avoid merging

Think about colored coins example and implement.
Some ideas:

• Use special output and AVL tree with coin state
• Use special data type to define a coin color. Ergo may not be a special case.
• Predefine all possible coins in genesis block, allow anyone to take them with increasing fee

This is needed for #43:

• Sigma type, so that ProveDlog and ProveDiffieHellmanTuple are subclasses of Sigma

Right now proposition ins't fully immutable, cause some leaf could substitute by their final value, it means this OR(EQ(IntConstant(1),IntConstant(1), EQ(IntConstant(1),IntConstant(2))) will appear as OR(TrueLeaf,FalseLeaf)

In the following line of ProverInterpreter.prove

val step4 = simulations(step3).get.asInstanceOf[UnprovenTree]

when simulations is executing the following case:

case su: UnprovenSchnorr =>
     if (su.simulated) {
       assert(su.challengeOpt.isDefined)
       SchnorrSigner(su.proposition, None).prove(su.challengeOpt.get)
     } else {
       val (r, commitment) = DLogInteractiveProver.firstMessage(su.proposition)
       su.copy(commitmentOpt = Some(commitment), randomnessOpt = Some(r))
     }

if su.simulated == true, prove will return UncheckedTree, and there will be type cast error

Make a test which is a show-case of an oracle usage scenario

Check more rows from http://mathworld.wolfram.com/Rule110.html, check invalid cases

We may want to parameterise ErgoScript with another script, given as serialised Array[Byte].
However we cannot allow user to manipulate script bytes, so we cannot just provide generic execute[T](bytes) function because it will be impossible to implement cost function in general case.
Actual script representation should be hidden from the user.
However we can assume that some Context variables and Box registers may be executed as scripts, which may look like this

let x = execute[Int](24)  // execute context variable 24 as script returning Int
let y = box.executeRegister[Boolean](5)

The location of script bytes is different in these cases, but the execution procedure in similar.
Execution is performed before cost estimation and have the following steps:

1. Deserialize bytes to Value[T] for some T, which become known after deserialization
2. Check that T is equal to parameter type (Int or Boolean in the examples above)
3. Insert deserialized tree instead of function invocation

Subtasks:

• add class ExecuteContextScript
• implement execute as global function
• add class ExecuteRegisterScript
• implement executeRegister as method of Box

There are quite a lot of forward references, found by code inspection. Looks like there are even cyclic references, e.g. sigmastate.lang.Type and sigmastate.lang.TypeBounds

Subtasks:

• refactoring of the interpreter to handle Sigma values

As SCAPI is no longer supported, and the dependency carried in the form of binaries located in the "lib/" folder is pretty problematic, there is a need to remove the dependency.

To get ORs and thresholds (what SCAPI calls ORMultiple) to work securely, we must make sure the space of possible challenges fits within modulo q. The current implementation does not do that and IS INSECURE AGAINST MALICIOUS PROVERS FOR THE CASE OF MULTIPLE ORS.

• index should not be Scala Int. Value[SInt.type] expected
• default value may me useful

relates to #87, #88, #98

This is required to implement Where.function() method.
Subtasks:

• add ctx: Context parameter to Transformer.function()

We need for serializers for many more classes, including Transformer descendants family (MapCollection, ForAll, Exists etc). Tests (similar to which are already exist in "sigmastate.serialization" package) are also needed

I can't find an example of collection extraction from a register, and expected way to do this like ExtractRegisterAs[SCollection[Boolean]](Self, R4)(SCollection[Boolean]) does not work

For example, compare CalcSha256 results with test vectors from the standard

• Choose concrete curve
• Check DDH
• Points serialization
• Insecure Fiat-shamir

Similarly to "apply many blocks" test, implement benchmark which is measuring total time of "applyBlock" operations for simulated series of blocks.

This is required for #98, #88.
Currently we have family of classes TaggedInt, TaggedBox, etc to access context variables.
This is problematic for extensions, in particular for implementation of #98.

We need to do the following changes:

• rename TaggedVariable -> ContextVariable
• instead of all TaggedXXX classes implement one class

  case class TaggedVariable[T <: SType](override val id: Byte, override val tpe: T) 
    extends ContextVariable[T]
       with NotReadyValue[T]

• instead of functions like taggedInt(23) we need one generic function getVariable[Int](23), which will access tagged parameter in the context and check its type. In particular taggedByteArray(23) can be replaced with getVariable[Array[Byte]](23)

• Check sha1 collision
• Check how secure blake2b is with 192 (?) bits

Use EcPointSerializer to (de)serialize group element(and let test fail for now)

Currently SCAPI is using old version 1.46 of the BouncyCastle. Newer versions are causing an exception. Update for the BouncyCastle version is needed after removing the SCAPI dependency ( #13 ).

Fix various code inspection errors and warnings. Relates to #74

• proof of non-existance
• proof of modification

Now it's not possible to work with SByteArray as with collection, e.g. this code does not compile:

EQ(SizeOf(ExtractRegisterAs[SByteArray.type](Self, R4)), bitsInString)

Relates to #71

We need more examples of collection usages in CollectionOperationsSpecification

• Examples with custom collections
• Examples with Slice, Append, Where, etc.

relates to #87, #88, #98, #99

Not conjecture is really problematic, as you can use it with sigma-statements, e.g. Not/If example could be rewritten in the following way:

EQ(ByteArrayConstant(hash),
CalcBlake2b256(
If(Not(pubkey),
ExtractRegisterAs[SByteArray.type](ByIndex(Inputs, 1), R3),
ExtractRegisterAs[SByteArray.type](ByIndex(Inputs, 2), R3))))

which does not make sense and causing interpreter to crash

• Implement operations on top of BigInt
• (?) Unsigned int type
• Type casts

Implement this new test in BlockchainSimulationSpecification.scala

Byte type is needed for this
relates to #87, #88

@ergomorphic :

By design, a verifier is making one non-circular phase named "specificTransformations" and then estimating cost of the script. All rewrites after the phase should not increase the tree.

Based on that, invocation of specificTransformations in following code in Interpreter is problematic:

val rules: Strategy = strategy[Value[_ <: SType]] { case node =>
  var rewritten = evaluateNode(context, node)
  if (rewritten == null) {
    rewritten = specificTransformations(context, node)
  }
  if (rewritten != null) {
    wasRewritten = true
    Some(rewritten)
  }
  else
    None
}

Instead of println / return, do real asserts

• check that decodePoint(bytestring).getEncoded(true) == bytestring, for any bytestring of a proper size

• convert to a test current contents of SecP521R1 class