EOS - Developer’s Log Stardate 201707.3

dan (71)in #eos • 7 years ago (edited)

Today I met with the team 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.

7 years ago in #eos by dan (71)

$1,357.76

Sort:

Trending

There are 4 pages

Pages

[-]

dan (71) 7 years ago

My apologies, key board shortcuts ended up submitting this before I was done and I had not yet declined payouts.

$35.83

[-]

fyrstikken (75) 7 years ago

And why should you not be allowed to be upvoted just like the rest of us? I think your posts are very valuable and we are a legion who thinks the same. Take Our Upvotes! Never Decline!

$10.86

18 votes

[-]

shla-rafia (68) 7 years ago

yes

$0.00

[-]

matt-a (65) 7 years ago

Agreed.

$0.00

[-]

cryptonfused (46) 7 years ago

Because payouts are declined it is obviously unecessary. It is actually helpful to the community. It would be better to say " thank you for declining payouts"

$0.00

[-]

blockrush (58) 7 years ago

@fyrstikken, self-upvoting might be part of the reasons why a new platform could overtake Steemit > https://steemit.com/steemit/@blockrush/is-wildspark-the-steemit-killer-blockrush

$0.00

[-]

fiveboringgames (68) 7 years ago

You know what to put in the next update so

$1.20

4 votes

[-]

hamzazaman (30) 7 years ago

Yeah U Are Right Offcoure He Know What To Put In The Next Update so

$0.00

[-]

ir3m0del (42) 7 years ago

battletoads

$0.00

[-]

tomino (54) 7 years ago

Please don't apologize for beeing awesome :-)

$0.70

7 votes

[-]

matt-a (65) 7 years ago (edited)

Like a mother apologizing for giving birth. Come on now, Dan! Accept and reap your rewards!

I, personally, knowing that you don't even need it, feel great giving you a 100% upvote. You've navigated the majority of this into existence, and that's something to be proud of. I understand being humble, but you have the right to be proud. You've emancipated and liberated countless human beings with your work. Take time to reflect on that. If you have that ability and execute it, you damn well better believe you have the right to take pride in it all.

Dude, you're spearheading some seriously revolutionary shit. Just saying. It's (well, was) the 4th of July! Independence! Emancipation! Sovereignty! FREEDOM! That is what you are doing. Reward the shit out of this post as hard as you can. You and your Dad are straight up on George Washington levels in my eyes.

The platforms that now exist now give myself, my family, my friends, and those that I care about, and society at large a one way ticket to life, liberty, and the pursuit of happiness. And on a cryptographically secure route! We live in some wild times . . . This is pioneer territory . . .

I guess that I'm just writing to say that I don't think that you should apologize for anything. You all have bestowed upon the Earth something fierce! A tool that two human beings can utilize to facilitate the transfer of value as they see fit. True liberation. Take pride in it, and sleep well.

HAPPY (late) 4TH OF JULYYYY!!!