Developer's log stardate 2017-07-07-EOS

Today I met withnecess to discuss the challenges of making smart contracts both easy to develop and easy to execute in parallel. If you are familiar with the challenges associated with parallel execution then you know the general rule that all data must be owned by a single thread. In terms of blockchains, that means all accounts need to own their data. Owning data means that no other thread of execution may read or write the data except by asynchronous message passing.

The Current Balance Problem
Suppose you want to read the current balance of another contract, something that seems like it should be trivial. If the balance is “owned” by another account, say the currency contract, then your contract cannot “read it”. You could attempt to query it by asynchronous communication, but that would be liking sending your bank a letter asking for a balance update and waiting for a response in the mail. By the time you get the response (if you get a response), the balance may already be out of date.

Fortunately, EOS makes it easy for one account to monitor all deposits and withdraws. In this case the reader contract would maintain its own logic duplicating the balance calculation and storage of the currency contract. This approach is also error prone because any small difference in behavior could result in your balance calculation differing from the currency contract.

Another alternative is to use an oracle that will notify your contract of the balance while simultaneously delivering a message to the currency contract. The currency contract will reject the transaction if the oracle lied, therefore, your contact can trust the balance reported. Once again this only lets you know the balance for the split second your transaction is applied and creates a new problem that your transaction can be invalidated if other user actions are modifying your balance at the same instance.

The underlying challenge here is that the balance data is owned by a different thread and therefore it cannot be reliably read and used when needed.

Redefining the Problem
Under the above model, all data is owned by a single account and its code. This makes each account like its own blockchain and communication among accounts tricky. Fortunately, GPU developers have used another parallelization strategy: SMID - single instruction multiple data. Stated more generally, a GPU executes the exact same code over many independent instances of the data. Every pixel and/or vertex is modified by the same set of instructions.

Imagine for a moment that every account balance was represented as pixel in an image. Imagine that a smart contract was defined like a shader. A pixel shader can only write to a single pixel, but it can read from any number of other read-only sources.

Under this model a currency contract is not defined as code that operates on a mapping of account name to balance, but instead as code that operates on a single balance belonging to a single account. The currency contract would not be able to read other accounts balances, but it would know with certainty that all accounts were running the same code.

What would such a contract look like?
void apply_simplecoin_transfer() {
static Transfer message;
static uint64_t balance = 0;
load( thisContract(), “balance”, balance );

readMessage( message );
requireNotify( {message.from, message.to} );

if( thisAccount() == message.to ) {
balance += message.amount;
} else if ( thisAccount() == message.from ) {
assert( message.amount < balance, "insufficient funds" )
balance -= message.amount;
}

if( balance ) store( “balance”, balance );
else remove( “balance”, balance );
}
Notice there are a few subtle differences:

The apply method only modifies a single balance
The behavior of the contract depends upon the value of thisAccount()
The load() method takes an extra parameter specifying the current contract
The store() and remove() methods always use the “balance” key rather than an account key.
If we assume all accounts run this exact same code on their private data, we can still guarantee that there are no double spends. This is possible because every account requires both the sender and receiver to be notified of the message or the message will be rejected (both parties can be notified in parallel).

The receiver knows that the sender must have sufficient funds or the receiver will reject the message; therefore, the receiver can safely increment its own balance. Likewise, the sender knows the receiver will increment his balance so he decrements his own.

What does this give us?
Well now that we have this design pattern we have separated “code” from “data” in terms of parallelization. A single account can now run code provided by other accounts and the code provided by other accounts can now read all data belonging to an account.

Suppose you wanted to build a social media platform where vote weight is proportional to current balance. This is something that requires the social media account to have the ability to read your balance and modify someone else’s post vote totals. In the ideal world it would be nice for @alice to vote for @bob while @sam is voting for @bill. This could be achieved as follows:

void apply_social_vote() {
readMessage( vote );
if( vote.for == thisContract() ) {
load( thisContract(), vote.postid, post );
post.totalvotes += vote.weight;
store( vote.postid, post );
}

if( vote.voter == thisAccount() ) {
static uint64_t balance = 0;
load( "simplecoin", "balance", balance );
assert( balance >= vote.weight, “insufficient balance for vote weight” );
}
}
In this case the contract code does two different things depending upon which data it is operating on. If it is operating on the receiver of the vote, then it increments the total votes. If it is operating on the sender, then it simply verifies the vote.weight <= the balance.

It should be noted that the vote receiver is still unable to read the vote giver’s balance. However, in this model two votes can be processed by 4 different accounts in parallel and it will work so long as the voter reports a vote weight that is accurate.

While it may not be possible to read someone else’s balance while modifying your state, it is possible to read your own balance from the “simplecoin” contract from within the “social” contract.

What is everything so complicated?
As programmers we would love to read whatever we want, whenever we want, and let the computer figure things out. The naive approach is to simply put locks around data. If two people “happen” to read the data at the same time, then one will wait for the other. Unfortunately for blockchain developers, the outcome of these race conditions is not deterministic and therefore could break consensus.

A New Hope
There is a way to allow one account to read another account’s balance; the transaction can declare that it requires read access. The blockchain’s transaction scheduler can then ensure that no one that requires write access will execute code at the same time. Using the old approach to simplecoin (one contract owning all the data), this would create a lot of congestion around that contract as everyone needing to read would be blocking those who want to write and everyone would be bottlenecked by a single contract.

However, using the new approach to simplecoin, the probability that two transactions need to access the same account data at the same time is much lower. This will reduce lock contention and maximize throughput.

Conclusion
Parallelism is hard, especially when you need things to be deterministic while accessing shared data. Fortunately, there are solutions available and design patterns proven by those who design GPUs and computer graphics algorithms.

Disclaimer Nothing in this blog post should be construed to imply any particular feature or functionality of the EOS.IO software. All software designs subject to change as necessary.

Written by Dan