Smart contracts design

[garious]

Some thoughts on the current state of the smart contract language. We currently have a minimal language suitable for little more than today's needs. As we move towards supporting atomic swaps, we'll need to choose whether to incrementally extend this language or make a bigger jump to a more general solution. Note that this decision is independent of the language's interpreter targeting BPF, as described in the Loom whitepaper. Below is a walk down the path of incrementally extending today's contract language into a general purpose one:

Here's an example spending plan we can write today:

Or((Timestamp(dt), Payment(tokens, to)), (Signature(sig), Payment(tokens, from)))

where the parameters to Payment are of type i64 and PublicKey and Or is of type Plan. In Haskell DSLs, Plan would traditionally be called Expr and Or is the unbiased choice operator sometimes denoted with Alternative's <|>. Likewise, instead of the Condition/Payment tuple, Haskellers would probably use Applicative's *> to say "Timestamp then Payment". In Haskell, we'd look to express the same spending plan as:

Timestamp dt *> Payment tokens to <|> Signature sig *> Payment tokens from

where each function returns an Expr, or maybe a nicely typed Expr GADT. In this form, we see the duplication of Payment tokens, and in fact, can rewrite the same expression as:

Payment tokens <$> (Timestamp dt *> pure to <|> Signature sig *> pure from)

Translated back to Rust, we'd want something like:

Payment(Lit(tokens), Or((Timestamp(dt), Lit(to)), (Signature(sig), Lit(from))))

But unlike Haskell, Rust isn't going to heap-allocate each of those nodes, so it'd actually be more like:

Payment(Box::new(Lit(tokens)), Box::new(Or((Box::new(Timestamp(dt)), Box::new(Lit(to))), (Box::new(Signature(sig)), Box::new(Lit(from))))))

Next, we can remove all those Boxes with a top-level [Plan] instead of a Plan, and replace every Box<Plan> with a &Plan pointing to a slot in the top-level array. Effectively, we'd be translating our heap-allocated recursive expression into a stack of expressions. We'd end up with:

let dt = Timestamp(dt);
let to = Lit(to);
let sig = Signature(sig);
let from = Lit(from);
let or = Or((&dt, &to), (&sig, &from));
let tokens = Lit(tokens);
let payment = Payment(&tokens, &or);
[dt, to, sig, from, or, tokens, payment]

That last line looks so similar to Reverse Polish Notation, it begs the question, what would that look like? Maybe:

(Signature(sig), Lit(from)) (Timestamp(dt), Lit(to)) Or Lit(tokens) Payment

tldr; The walk above shows us that incrementally taking our existing contract language to a general-purpose one takes us down a long, deep rabbit hole. Instead, we'll want to choose between:

1. a speedy little stack-oriented backend like Bitcoin's
2. a bulkier, but more expressive register-oriented backend like IELE
3. postponing the decision and incrementally extending the existing language for atomic swaps

I'm leaning toward option 3 today and then moving toward option 2 after we demonstrate our minimal, custom language meets our performance targets.

[garious]

Wadler discussing Plutus Core and IELE:
https://www.youtube.com/watch?v=IqA-mI2olFA

[garious]

Here's a smart contract language that looks more in line with the way we evaluate smart contracts concurrently: https://github.com/rchain/Rholang

[garious]

In v0.5.0, we'll have the same contract language as v.0.4.0. Going forward, we'll create an interface into a safe execution environment. We need to come up with a deterministic way to charge contracts for the use of network resources. EVM's gas-per-instruction is too arbitrary and unnecessarily low-level. Anything that can be computed within the duration of a single sig-verify is effectively the same price in our pipeline.

[bgorlick]

Simplicity: A New Language for Blockchains - by Russel O'Conner is worth a read during research on this. It would still likely need a more natural language ontop of it, such as eg. Lua.
Abstract: https://arxiv.org/abs/1711.03028
PDF: https://arxiv.org/pdf/1711.03028.pdf

Also, the devlist (captured here) has feedback from several bitcoin-core developers on this proposal, which highlights many of the challenges associated with building smart contracting language: https://www.reddit.com/r/bitcoin_devlist/comments/79r1ma/simplicity_an_alternative_to_script_russell/

[FishmanL]

Race makes it sound like the language itself induces race conditions -- not the sort of connotation you want for an unbiased Or operator, no?

[garious]

@FishmanL, Or is growing on me. Thanks for the suggestion.

[garious]

A smart contract is a process that is waiting on a set of information. In response to receiving any information in that set, it may optionally send information to other processes, and then move into a new state where it is waiting on a new set of information. Once the process no longer requires information, it is complete.

Below is a Rust implementation of a reusable M-N Multisig combinator. step() returns Ok(()) once the contract has M of N signatures, otherwise NeedsMore.

struct Multisig {
    m: u64,
    sigs: Vec<Signature>,
}

impl Multisig {
   fn new(m: usize, sigs: Vec<Signature>) -> Result<Self> {
       if m == 0 || sigs.len() < m {
           Err(ContractError::Invalid);
       }
       Ok(Multsig{m, sigs})
   }
}

impl Step for Multisig {
   fn step(&mut self, sig: &Signature) -> Result<State> {
       if !self.sigs.contains(sig) {
           return Ok(State::NeedsMore);
       }

       if self.m == 1 {
           return Ok(State::Done);
       }

       self.m -= 1;
       self.sigs.remove(sig);

       Ok(State::NeedsMore)
    }
}

As a result of receiving M signatures, the combinator doesn't do anything in particular, like make a payment. You'd instead, write something such as:

Multisig::new(2, sigs).then(
    Pay::new(42, to)
)

The role of frontend languages then, would be to stitch together combinators in some more intuitive way. For example, in Rust, you'd add some macro magic to write that as:

do!(
   mutisig(2, sigs);
   pay(42, to);
)

[garious]

A little cleaner, if a len() method reacts to changes in the length of sigs, then there's no need for a separate mulitsig instruction:

do!(
     sigs.len() <= 1;
     pay(42, to);
)

This might, however, require an until, once or after annotation:

do!(
     until(sigs.len() <= 1);
     pay(42, to);
)

[garious]

The smart contract engine allows operations like M-N Mulisig to be written in a general purpose programming language. Here's a Lua implementation that executes on the new solua program:

-- M-N Multisig. Pass in a table "{m=M, n=N, tokens=T}" where M is the number
-- of signatures required, and N is a list of the pubkeys identifying
-- those signatures. Once M of len(N) signatures are collected, tokens T
-- are subtracted from account 1 and given to account 4. Note that unlike
-- Rust, Lua is one-based and that account 1 is the first account.

function find(t, x)
    for i, v in pairs(t) do
        if v == x then
            return i
        end
    end
end

function deserialize(bytes)
    return load("return" .. bytes)()
end

local from_account,
      serialize_account,
      state_account,
      to_account = table.unpack(accounts)

local serialize = load(serialize_account.userdata)().serialize

if #state_account.userdata == 0 then
    local cfg = deserialize(data)
    state_account.userdata = serialize(cfg, nil, "s")
    return
end

local cfg = deserialize(state_account.userdata)
local key = deserialize(data)

local i = find(cfg.n, key)
if i == nil then
    return
end

table.remove(cfg.n, i)
cfg.m = cfg.m - 1
state_account.userdata = serialize(cfg, nil, "s")

if cfg.m == 0 then
    from_account.tokens = from_account.tokens - cfg.tokens
    to_account.tokens = to_account.tokens + cfg.tokens

    -- End of game.
    state_account.tokens = 0
end

[garious]

Closing this. Our goal of creating a new concurrent smart contracts language is no more. Instead, we created a concurrency-friendly smart contracts engine, and will provide various safe execution environments, such as a BPF interpreter for C programs and a safe subset of the Lua interpreter for Lua programs.