Attention Bytemaster and other Bitshares Devs, please review VerSum paper.

[BunkerChainLabs-DataSecurityNode]

Very interesting paper.   

My initial thoughts are that this process is like driving a tank as a daily commute vehicle because of the extra security it provides.    It would be expensive, ugly, big, and not practical.

My second thoughts are that this provides a SPV model for authenticating queries on proof of stake systems.   We have always said that a light node should query several servers and verify that they all agree before "trusting" the data. 

My third thought are that transaction throughput would be limited to less than 1% what could be achieved by other means.

... and the fourth unpublished thought is that this inspired a new solution that will bypass thoughts one two and three and make BitShares even more awesome.

Here comes another worker proposal!

[bytemaster]

Very interesting paper.   

My initial thoughts are that this process is like driving a tank as a daily commute vehicle because of the extra security it provides.    It would be expensive, ugly, big, and not practical.

My second thoughts are that this provides a SPV model for authenticating queries on proof of stake systems.   We have always said that a light node should query several servers and verify that they all agree before "trusting" the data. 

My third thought are that transaction throughput would be limited to less than 1% what could be achieved by other means.

[bytemaster]

A VERSUM server running this computation creates around
365 GB of authenticated data structures for a recent snapshot of
the blockchain, which contains 14 GB of Bitcoin blocks and a total
of 30 million transactions.

Yikes! 

[mike623317]

 
You're hurting my head lucky, but this is an interesting read. Would like to hear this as a question on the mumble.

[luckybit]

A fairly recent quote from the legendary Nick Szabo

A block-chain computer, in sharp contrast to a web server, is shared across many such traditional computers controlled by dozens to thousands of people. By its very design each computer checks each other's work, and thus a block chain computer reliably and securely executes our instructions up to the security limits of block chain technology, which is known formally as anonymous and probabilistic Byzantine consensus (sometimes also called Nakamoto  consensus).  The most famous security limit is the much-discussed "51% attack".  We won't discuss this limit the underlying technology further here, other than saying that the oft-used word "trustless" is exaggerated shorthand for the more accurate mouthful "trust-minimized", which I will use here.  "Trust" used in this context means the need to trust remote strangers, and thus be vulnerable to them. 

Trust-minimized code means you can trust the code without trusting the owners of any particular remote computer. A smart phone user in Albania can use the block chain to interact with a computer controlled by somebody in Zimbabwe, and they don't have to know or trust each other in any way, nor do they need to depend on the institutions of either's countries, for the underlying block chain computer to run its code securely and reliably. Regardless of where any of the computers or their owners are, the block chain computer they share will execute as reliably and securely as consensus technology allows, up to the aforementioned limits. This is an extremely high level of reliability, and a very high level of security, compared to web server technology. 

The dawn of trustworthy computing
http://unenumerated.blogspot.com/2014/12/the-dawn-of-trustworthy-computing.html

[luckybit]

Versum builds on the groundbreaking Lambda-Auth paper by Andrew Miller. Lambda-Auth is a breakthrough in cybersecurity because it provides Authenticated Data Structures.

Lambda-Auth Abstract:

Abstract
An authenticated data structure (ADS) is a data structure whose
operations can be carried out by an untrusted prover, the results of
which a verifier can efficiently check as authentic. This is done
by having the prover produce a compact proof that the verifier
can check along with each operation’s result. ADSs thus support
outsourcing data maintenance and processing tasks to untrusted
servers without loss of integrity. Past work on ADSs has focused
on particular data structures (or limited classes of data structures),
one at a time, often with support only for particular operations.

Authenticated Data Structures allow cybersecurity by correctness and verifiability. Programs are "Proofs", and proofs are verifiable. Verifiable computation is the holy grail, it allows the blockchain to outsource computation to nodes with verifiable security. This is a similar approach to Codius but potentially dramatically better because anyone can contribute computation and become a node through a decentralized market and exchange.

VerSum Abstract:

ABSTRACT
VERSUM allows lightweight clients to outsource expensive computations
over large and frequently changing data structures, such as
the Bitcoin or Namecoin blockchains, or a Certificate Transparency
log. VERSUM clients ensure that the output is correct by comparing
the outputs from multiple servers. VERSUM assumes that at least
one server is honest, and crucially, when servers disagree, VERSUM
uses an efficient conflict resolution protocol to determine which
server(s) made a mistake and thus obtain the correct output.
VERSUM’s contribution lies in achieving low server-side overhead
for both incremental re-computation and conflict resolution,
using three key ideas: (1) representing the computation as a functional
program, which allows memoization of previous results; (2)
recording the evaluation trace of the functional program in a carefully
designed computation history to help clients determine which
server made a mistake; and (3) introducing a new authenticated data
structure for sequences, called SEQHASH, that makes it efficient
for servers to construct summaries of computation histories in the
presence of incremental re-computation. Experimental results with
an implementation of VERSUM show that VERSUM can be used
for a variety of computations, that it can support many clients, and
that it can easily keep up with Bitcoin’s rate of new blocks with
transactions.

The algorithms behind VerSum and Lambda Auth open up an entire new field of computer science, is a breakthrough, and a game changer.

This to me suggests that Ethereum developers took a less than optimal approach to smart contracts because the security risks of Turing completeness outweigh the benefits if they are any. Bitshares developers and entrepreneurs who might be interested in this include but are not limited to anyone interested in implementing smart contracts, such as Bytemaster, Toast, DataSecurityNode, Fuzzy.


References

lambda-auth
https://www.cs.umd.edu/~amiller/gpads/gpads.pdf
https://amiller.github.io/lambda-auth/

VerSum
https://people.csail.mit.edu/nickolai/papers/vandenhooff-versum.pdf

computational trinitarianism
http://ncatlab.org/nlab/show/computational%20trinitarianism

codius
https://codius.org/

MC2 Researchers Receive $1.2M NSF Grant for Verifiable Computation
https://www.umiacs.umd.edu/about-us/news/mc2-researchers-receive-12m-nsf-grant-verifiable-computation

Safeguarding Computations in the Cloud
https://www.youtube.com/watch?v=XrjO7N5uv04&feature=youtu.be

Algorithmica
DOI 10.1007/s00453-014-9968-3
Authenticated Hash Tables Based on Cryptographic
Accumulators
http://www.ece.umd.edu/~cpap/published/algorithmica15.pdf