Verifying Account Transfer in Dafny

user_19209333 0
Viewed 46

I'm trying to verify a simple account transfer in Dafny, and this is what I came up with:

function sum(items: seq<int>): int
decreases |items| {
    if items == []
    then 0
    else items[0] + sum(items[1..])
}

method transfer(accounts: array<int>, balance: int, from: int, to: int)
requires from >= 0 && from < accounts.Length;
requires to >= 0 && to < accounts.Length;
requires accounts.Length > 0;
requires sum(accounts[..]) == balance;
ensures sum(accounts[..]) == balance;
modifies accounts;
{
    accounts[from] := accounts[from] - 1;
    accounts[to] := accounts[to] + 1;
    return;
}

I'm just transferring one token at a time here (though actually I want to transfer an arbitrary amount). Eitherway, it doesn't verify. I'm wondering what else I need to do?

dafny formal-verification
2 Answers

Here is one way to do it.

The problem is that Dafny does not know anything about the sum function, so we have to teach it a few facts.

function sum(items: seq<int>): int
decreases |items| {
    if items == []
    then 0
    else items[0] + sum(items[1..])
}

lemma sum_append(xs: seq<int>, ys: seq<int>)
  ensures sum(xs + ys) == sum(xs) + sum(ys)
{
  if xs == [] {
    assert [] + ys == ys;
  } else {
    assert (xs + ys)[1..] == xs[1..] + ys;
  }
}

lemma sum_focus(xs: seq<int>, i: int)
  requires 0 <= i < |xs|
  ensures sum(xs) == sum(xs[..i]) + xs[i] + sum(xs[i+1..])
{
  calc {
    sum(xs);
    { assert xs == xs[..i] + [xs[i]] + xs[i+1..]; }
    sum(xs[..i] + [xs[i]] + xs[i+1..]);
    { forall xs, ys { sum_append(xs, ys); } }
    sum(xs[..i]) + xs[i] + sum(xs[i+1..]);
  }
}

method transfer(accounts: array<int>, balance: int, from: int, to: int)
requires from >= 0 && from < accounts.Length;
requires to >= 0 && to < accounts.Length;
requires accounts.Length > 0;
requires sum(accounts[..]) == balance;
ensures sum(accounts[..]) == balance;
modifies accounts;
{
    sum_focus(accounts[..], from);
    accounts[from] := accounts[from] - 1;
    sum_focus(accounts[..], from);

    sum_focus(accounts[..], to);
    accounts[to] := accounts[to] + 1;
    sum_focus(accounts[..], to);
}

The idea is that the sum_focus lemma allows us to break up the sum of an array into the sum of elements before i, plus the element at i, plus the sum of elements after i. This "focusing" step allows Dafny to reason about the assignment statements that write to the array elements accounts[from] and accounts[to].

Alternative version of sum_focus:

lemma sum_focus(xs: seq<int>, i: int)
  requires 0 <= i < |xs|
  ensures sum(xs) == sum(xs[..i]) + xs[i] + sum(xs[i+1..])
{
  calc {
    sum(xs);
    { assert xs == xs[..i] + [xs[i]] + xs[i+1..]; }
    sum(xs[..i] + [xs[i]] + xs[i+1..]);
    {
      sum_append(xs[..i] + [xs[i]], xs[i+1..]);
      sum_append(xs[..i], [xs[i]]);
    }
    sum(xs[..i]) + xs[i] + sum(xs[i+1..]);
  }
}
user_4382670

Ok, based on your suggestion I came up with this:

function sum(items: seq<int>): int
decreases |items| {
    if items == []
    then 0
    else items[0] + sum(items[1..])
}

lemma diff(xs: seq<int>, ys: seq<int>, acc: int, amt: int)
requires |xs| == |ys| && 0 <= acc < |xs|;
requires (forall k:int :: (0 <= k < |xs|) ==> (k == acc || xs[k] == ys[k]));
requires xs[acc] == ys[acc] + amt;
ensures sum(xs) == sum(ys) + amt;
{
    if acc == 0 {
        assert xs[1..] == ys[1..];
    } else {
        diff(xs[1..],ys[1..],acc-1,amt);
    }
}


method transfer(accounts: array<int>, balance: int, from: int, to: int)
requires from >= 0 && from < accounts.Length;
requires to >= 0 && to < accounts.Length;
requires accounts.Length > 0;
requires sum(accounts[..]) == balance;
ensures sum(accounts[..]) == balance;
modifies accounts;
{
    var 'accounts : seq<int> := accounts[..];
    accounts[from] := accounts[from] - 1;
    var ''accounts : seq<int> := accounts[..];
    diff(accounts[..],'accounts,from,-1);
    accounts[to] := accounts[to] + 1;
    diff(accounts[..],''accounts,to,1);
    return;
}

That seems to go through. Its a bit clunky though --- I prefer your way.

user_192093330
Related