From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id C8AF525A for ; Mon, 20 Jun 2016 22:28:50 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-qk0-f179.google.com (mail-qk0-f179.google.com [209.85.220.179]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 861A31AA for ; Mon, 20 Jun 2016 22:28:49 +0000 (UTC) Received: by mail-qk0-f179.google.com with SMTP id t127so60575320qkf.1 for ; Mon, 20 Jun 2016 15:28:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=OsZ+p9l+hGmoM9u4RxmKSQ67+YqKs0/J9XmO06Np8xU=; b=WPfSyB3OVPoutKXotFwbKKBGxdGagouz1QVMINRiTgwR2qDAKS5shnpe5qYtmRgSgM YgQ5VDFfYWvzi9jpI/wsVemPy9BzHL59sT4FT9XZUHeyEwELpxsWzWu0xyYGJC0lzx00 MjriUcxrwT/+V2MaBC2i6Gwy2YK2AxibXllKo+4RkDu6xkHevIvggqDWit+N7pL2H0qF d3KM1J44KBYd32jBhYwQjhmYHbEXIbw45TNXU422/9UyF5e5XJCvu7hTgcEYhfufvH5U Q7pp0JTJh2oCRjK0h0ZrzhH1as3H5GXv0U86gQ8zr4i/Kt15AQIgLVEh30GIApr1eCQV Egsw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=OsZ+p9l+hGmoM9u4RxmKSQ67+YqKs0/J9XmO06Np8xU=; b=OAUfLnB27/71nO9aWxcBSHGS6FHNjlHiQM/6CUjFWNEaX3TRRPCyvCSECjeBwTrUFJ BSt1FtQ7S6xc091sEXMfXKZ4ka/UyA9JcKSXnsCJXj5TucfH7iD2uDwHOjfgGWyiqBZx 3u7bwVbjX8qPlps3DNl7xKrT5wRzMk7F4iGK2Pgu5bZGikFhzKQvYNd/YbhFXWgg4eVu GxdpPah5GgxV6hD6eyFNXgRPsRv7IkFrydW8UYAnY15kqJAV2O0nre28PQNMlrQftZF7 /UYp0VpvAFMgc8NhDO+E1lKNW5GPgkOz9vebPKowcrRGl4kn5Rlf/YOTOZIbNyHG7xlL G8+A== X-Gm-Message-State: ALyK8tLvVCH9I4Q5D43GDt6JiskXsm8kQ0H41XEPkje8J05/Uh+O3PXfCFdFT6W/SlCw50f/W1bkIp8ZJQOTuA== X-Received: by 10.55.46.197 with SMTP id u188mr25153494qkh.84.1466461728748; Mon, 20 Jun 2016 15:28:48 -0700 (PDT) MIME-Version: 1.0 Received: by 10.55.42.88 with HTTP; Mon, 20 Jun 2016 15:28:48 -0700 (PDT) In-Reply-To: <20160620085649.GA29964@fedora-21-dvm> References: <20160620085649.GA29964@fedora-21-dvm> From: Alex Mizrahi Date: Tue, 21 Jun 2016 01:28:48 +0300 Message-ID: To: Peter Todd , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary=001a114f3f286b3be60535bd3a1a X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Mon, 20 Jun 2016 22:29:35 +0000 Subject: Re: [bitcoin-dev] Building Blocks of the State Machine Approach to Consensus X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 20 Jun 2016 22:28:50 -0000 --001a114f3f286b3be60535bd3a1a Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable > All practical single-use seals will be associated with some kind of > condition, > such as a pubkey, or deterministic expression, that needs to be satisfied > for > the seal to be closed. I think it would be useful to classify systems w.r.t. what data is available to condition. I imagine it might be useful if status of other seals is available. > Secondly, the contents of the proof will be able to > commit to new data, such as the transaction spending the output associate= d > with > the seal. > So basically a "condition" returns that "new data", right? If it commits to a data in a recognizable way, then it's practically a function which yields a tuple (valid, new_data). If an oracle doesn't care about data then you can convert it to a predicate using a simple projection. But from point of view of a client, it is a function which returns a tuple. It might help if you describe a type of the condition function. Some related work on UTXO-based smart contracts: 1. Typecoin described in the paper "Peer-to-peer Affine Commitment using Bitcoin" Karl Crary and Michael J. Sullivan Carnegie Mellon University PLDI =E2=80=9915, Portland June 17, 201= 5 I don't see the paper in open access and I've lost my copy, but there are slides: https://www.msully.net/stuff/typecoin-slides.pdf The paper is written by programming language researchers, and thus use fairly complex constructs. The idea is to use the language of linear logic, but it's actually implemented using type-oriented programming. So, basically, they associate logical propositions with transaction outputs. Transactions proof that output-propositions logically follow from input-propositions. The paper first describes as a colored coin kind of a system, where color values are propositions/types. But in the implementation part it became more like a metacoin, as it uses a complete transaction history. A setup with a trusted server is also mentioned. The interesting thing about Typecoin is that a contract language is based on logic, which makes it powerful and -- I guess -- analyzable. However, the paper doesn't mention any performance details, and I guess it's not good. Another problem is that it looks very unusual to people who aren't used to type-oriented programming. 2. Generic coins Seeing how much Typecoin people had to struggle to describe a Bitcoin-style system I decided to describe a generalized Bitcoin-style system, so it can be easily referenced in research. Sadly all I got so far is a draft of an introduction/definition sections: https://github.com/chromaway/ngcccbase/wiki/gc In the first section I described a transaction graph model which is supposed to be general enough to describe any kind of a transaction graph system with explicit dependencies and no "spooky action at distance". As it turns out, any such system can be defined in terms of few predicate functions, however, using these functions directly might be very inefficient. The next section introduces a coin-based model. A coin-based system can be described using a single function called coin kernel which is applied to a transaction and a list of input coinstates. It is then described how to go from a coin-based model to a transaction-graph model. The reverse should also be possible if we add additional restrictions on a transaction-graph model, it's probably enough to define that coin can be spent only once. (Partial coin spends were described in Freimarkets.) There is a fairly shitty prototype in Haskell: https://github.com/baldmaster/ColorCoin 3. flexichains This is a prototype done by me more recently, the interesting thing about it is that it unifies account-based and UTXO-based models in a single model= . We first introduce a notion of record. A record can be of an arbitrary type, the only restriction is that it must have a key which must be unique within a system. Then transaction model can be introduced using two function: txDependencies returns a list of keys of records transaction depends on applyTx takes a transaction and a list of records it depends on and returns either a list of records or an error. A list of records includes * new records which are created by a transaction * updated records will have the same key but different content A simple account-based system can be implement using tuples (pubkey, balance, last_update) as records. In an UTXO-based system records are transaction output, and they should include a spent flag. (Obviously, records with spent flag can be pruned.) A system with custom smart contracts can be implemented by adding some sort of a function or bytecode to records. A Haskell prototype is here: https://bitbucket.org/chromawallet/flexichains/src/21059080bed6?at=3Ddevelo= p (It's kinda broken and incomplete, though.) --001a114f3f286b3be60535bd3a1a Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
=C2=A0
All practical single-use seals will be associated with some kind of conditi= on,
such as a pubkey, or deterministic expression, that needs to be satisfied f= or
the seal to be closed.
=C2=A0
I think it would b= e useful to classify systems w.r.t. what data is available to condition.
I imagine it might be useful if status of other seals is available.=
=C2=A0
Secondly, the contents of = the proof will be able to
commit to new data, such as the transaction sp= ending the output associated with
the seal.
<= br>
So basically a "condition" returns that "new d= ata", right?
If it commits to a data in a recognizable way, = then it's practically a function which yields a tuple (valid, new_data)= .
If an oracle doesn't care about data then you can convert i= t to a predicate using a simple projection.
But from point of vie= w of a client, it is a function which returns a tuple.

=
It might help if you describe a type of the condition function.
<= div>
Some related work on UTXO-based smart contracts:

1. Typecoin described in the paper
"Peer-t= o-peer Affine Commitment using Bitcoin" Karl Crary and Michael J. Sullivan Carnegie Mellon University PLDI =E2=80=9915, Portland June 17, 2015

I don't see the paper in open ac= cess and I've lost my copy, but there are slides:=C2=A0https://www.msully.net/stuff/t= ypecoin-slides.pdf

The paper is written by pro= gramming language researchers, and thus use fairly complex constructs.
The idea is to use the language of linear logic, but it's actuall= y implemented using type-oriented programming.
So, basically, the= y associate logical propositions with transaction outputs. Transactions pro= of that output-propositions logically follow from input-propositions.
=
The paper first describes as a colored coin kind of a system, where co= lor values are propositions/types.
But in the implementation part= it became more like a metacoin, as it uses a complete transaction history.=
A setup with a trusted server is also mentioned.

<= /div>
The interesting thing about Typecoin is that a contract language = is based on logic, which makes it powerful and -- I guess -- analyzable. Ho= wever, the paper doesn't mention any performance details, and I guess i= t's not good.
Another problem is that it looks very unusual t= o people who aren't used to type-oriented programming.

2. Generic coins
Seeing how much Typecoin people had to = struggle to describe a Bitcoin-style system I decided to describe a general= ized Bitcoin-style system, so it can be easily referenced in research. Sadl= y all I got so far is a draft of an introduction/definition sections:=C2=A0= https://github.c= om/chromaway/ngcccbase/wiki/gc

In the first se= ction I described a transaction graph model which is supposed to be general= enough to describe any kind of a transaction graph system with explicit de= pendencies and no "spooky action at distance". As it turns out, a= ny such system can be defined in terms of few predicate functions, however,= using these functions directly might be very inefficient.

The next section introduces a coin-based model. A coin-based syste= m can be described using a single function called coin kernel which is appl= ied to a transaction and a list of input coinstates.
It is then d= escribed how to go from a coin-based model to a transaction-graph model.
The reverse should also be possible if we add additional restrictio= ns on a transaction-graph model, it's probably enough to define that co= in can be spent only once. (Partial coin spends were described in Freimarke= ts.)

There is a fairly shitty prototype in Haskell= :=C2=A0https://github.c= om/baldmaster/ColorCoin

3. flexichains
This is a prototype done by me more recently, the interesting thing abou= t it is that it unifies account-based and UTXO-based models in a single mod= el.

We first introduce a notion of record. A recor= d can be of an arbitrary type, the only restriction is that it must have a = key which must be unique within a system.
Then transaction model = can be introduced using two function:
=C2=A0 txDependencies retur= ns a list of keys of records transaction depends on
=C2=A0 applyT= x takes a transaction and a list of records it depends on and returns eithe= r a list of records or an error.

A list of records= includes
=C2=A0* new records which are created by a transaction<= /div>
=C2=A0* updated records will have the same key but different cont= ent

A simple account-based system can be implement= using tuples (pubkey, balance, last_update) as records.
In an UT= XO-based system records are transaction output, and they should include a s= pent flag. (Obviously, records with spent flag can be pruned.)
A = system with custom smart contracts can be implemented by adding some sort o= f a function or bytecode to records.

(It's kinda broken a= nd incomplete, though.)

--001a114f3f286b3be60535bd3a1a--