MIME-Version: 1.0
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
Subject: Re: [bitcoin-dev] Building Blocks of the State Machine Approach to
	Consensus
Precedence: list

--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--