path: root/ee/e85562a9b3b4e4eff00f5e99f0a7f1c79566f7

Return-Path: <alex.mizrahi@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id C8AF525A
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 20 Jun 2016 22:28:49 +0000 (UTC)
Received: by mail-qk0-f179.google.com with SMTP id t127so60575320qkf.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <alex.mizrahi@gmail.com>
Date: Tue, 21 Jun 2016 01:28:48 +0300
Message-ID: <CAE28kUTkBmhLm-7rNVtX7Dm2yYABQiepZX0RCYpBn60Uo9=ehA@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div=
>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px =
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-=
style:solid;padding-left:1ex">
All practical single-use seals will be associated with some kind of conditi=
on,<br>
such as a pubkey, or deterministic expression, that needs to be satisfied f=
or<br>
the seal to be closed.</blockquote><div>=C2=A0</div><div>I think it would b=
e useful to classify systems w.r.t. what data is available to condition.</d=
iv><div>I imagine it might be useful if status of other seals is available.=
</div><div>=C2=A0<br></div><div><blockquote class=3D"gmail_quote" style=3D"=
margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,20=
4,204);border-left-style:solid;padding-left:1ex">Secondly, the contents of =
the proof will be able to<br>commit to new data, such as the transaction sp=
ending the output associated with<br>the seal.<br></blockquote></div><div><=
br></div><div>So basically a &quot;condition&quot; returns that &quot;new d=
ata&quot;, right?</div><div>If it commits to a data in a recognizable way, =
then it&#39;s practically a function which yields a tuple (valid, new_data)=
.</div><div>If an oracle doesn&#39;t care about data then you can convert i=
t to a predicate using a simple projection.</div><div>But from point of vie=
w of a client, it is a function which returns a tuple.</div><div><br></div>=
<div>It might help if you describe a type of the condition function.</div><=
div><br></div><div>Some related work on UTXO-based smart contracts:</div><d=
iv><br></div><div>1. Typecoin described in the paper</div><div>&quot;Peer-t=
o-peer Affine Commitment
using Bitcoin&quot; Karl Crary and Michael J. Sullivan
Carnegie Mellon University
PLDI =E2=80=9915, Portland
June 17, 2015</div><div><br></div><div>I don&#39;t see the paper in open ac=
cess and I&#39;ve lost my copy, but there are slides:=C2=A0<a href=3D"https=
://www.msully.net/stuff/typecoin-slides.pdf">https://www.msully.net/stuff/t=
ypecoin-slides.pdf</a></div><div><br></div><div>The paper is written by pro=
gramming language researchers, and thus use fairly complex constructs.</div=
><div>The idea is to use the language of linear logic, but it&#39;s actuall=
y implemented using type-oriented programming.</div><div>So, basically, the=
y associate logical propositions with transaction outputs. Transactions pro=
of that output-propositions logically follow from input-propositions.</div>=
<div>The paper first describes as a colored coin kind of a system, where co=
lor values are propositions/types.</div><div>But in the implementation part=
 it became more like a metacoin, as it uses a complete transaction history.=
</div><div>A setup with a trusted server is also mentioned.</div><div><br><=
/div><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&#39;t mention any performance details, and I guess i=
t&#39;s not good.</div><div>Another problem is that it looks very unusual t=
o people who aren&#39;t used to type-oriented programming.</div><div><br></=
div><div>2. Generic coins</div><div>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=
<a href=3D"https://github.com/chromaway/ngcccbase/wiki/gc">https://github.c=
om/chromaway/ngcccbase/wiki/gc</a></div><div><br></div><div>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 &quot;spooky action at distance&quot;. 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.</div><div><br></=
div><div>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.</div><div>It is then d=
escribed how to go from a coin-based model to a transaction-graph model.</d=
iv><div>The reverse should also be possible if we add additional restrictio=
ns on a transaction-graph model, it&#39;s probably enough to define that co=
in can be spent only once. (Partial coin spends were described in Freimarke=
ts.)</div><div><br></div><div>There is a fairly shitty prototype in Haskell=
:=C2=A0<a href=3D"https://github.com/baldmaster/ColorCoin">https://github.c=
om/baldmaster/ColorCoin</a></div><div><br></div><div>3. flexichains</div><d=
iv>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.</div><div><br></div><div>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.</div><div>Then transaction model =
can be introduced using two function:</div><div>=C2=A0 txDependencies retur=
ns a list of keys of records transaction depends on</div><div>=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.</div><div><br></div><div>A list of records=
 includes</div><div>=C2=A0* new records which are created by a transaction<=
/div><div>=C2=A0* updated records will have the same key but different cont=
ent</div><div><br></div><div>A simple account-based system can be implement=
 using tuples (pubkey, balance, last_update) as records.</div><div>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.)</div><div>A =
system with custom smart contracts can be implemented by adding some sort o=
f a function or bytecode to records.</div><div><br></div><div>A Haskell pro=
totype is here:=C2=A0<a href=3D"https://bitbucket.org/chromawallet/flexicha=
ins/src/21059080bed6?at=3Ddevelop">https://bitbucket.org/chromawallet/flexi=
chains/src/21059080bed6?at=3Ddevelop</a></div><div>(It&#39;s kinda broken a=
nd incomplete, though.)</div><div><br></div></div></div></div>

--001a114f3f286b3be60535bd3a1a--