[BTC-dev] (CRACKPOTTERY) Notes re: one possible "TRB-I".
Stanislav Datskovskiy
stas@loper-os.org
Tue Feb 28 05:40:22 UTC 2017
Name: casks_s.txt
URL: <http://therealbitcoin.org/ml/btc-dev/attachments/20170228/casks_s.txt?sha1=a201fea937ec3d80bf2eea78ec40a18ca95b111e>
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512
*******************************************************************************
* 0. Caveats. *
***************
(0.0)
Certain constants are specified as 'chosen at genesis'.
This means that they are to retain their value, selected exactly once,
for the lifetime of the Blockchain.
(0.1)
P != NP is taken as a postulate;
as is the existence of a collision-resistant trapdoor function, H;
and the existence of a hard asymmetric cryptosystem (see sect. 1.)
(0.2)
The minimal unit of accounting shall be referred to as a 'Satoshi',
not to be confused with Bitcoin's minimal unit of accounting.
(0.3)
We will err on the side of pedantic restatement of the painfully obvious ,
rather than risking ambiguity.
(0.4)
This is NOT a formal spec! But it would like to become such a thing,
when it grows up.
*******************************************************************************
* 1. Foundations. *
*******************
Let B(i) represent the number of bytes occupied by entity i.
Let C(A(i_1,i_2..i_n)) represent the count of entities in an array entity A.
Let H be a collision-resistant hash function (e.g., Keccak.)
Let Q be a CSPRNG (Blum-Blum-Shub seems to be the only sane choice,
but can use, e.g.,
Q(S, n) = H(S(H(S+1(H(S+2...H(S+n)))))) where S is
the seed; if you are willing to live and die by H.
Let the following functions comprise an asymmetric cryptosystem (e.g., RSA) :
Rk(E) -> SK, PK
(Keypair generation, using entropy input E, yielding
secret key SK and public key PK)
Rs(SK, P) -> SM (sealing, using secret key SK of payload P,
yielding Sealed Message SM.)
Rv(PK, SM) -> B (verification of Sealed Message SM using
public key PK, yielding boolean truth value B)
Re(PK, M, E) -> EM (encryption of message M, to public key PK,
yielding encrypted message EM, after entropic padding
E -- the latter will be omitted below, for clarity,
we will refer simply to Re(PK, M).)
Rd(SK, EM) -> M (decryption of encrypted message EM, using secret key
SK, yielding plaintext message M, after removal of the
padding emplaced by Re.)
*******************************************************************************
* 2. Nodes. *
*************
A Node is a device which verifies and permanently stores the blockchain, and,
under certain circumstances, accepts transactions from other Nodes;
and, also under certain circumstances, transmits transactions to other Nodes.
A Miner is a Node which attempts to create new Blocks, as defined below.
A Relay is a Node which does not attempt to create new blocks.
Note that Miners may relay Transactions, or Blocks, to other nodes, when
they so choose; but this is to be thought of as operating a separate Relay
in the same facility as the Miner.
A Parent of a Relay is a Node upstream from it (i.e. 1 step closer to any Miner)
A Relay parented directly by a Miner will be referred to as an L1 Relay.
A Child of a Node is a Relay downstream (i.e. 1 step further from any Miner.)
An L1 relay is that which is a child of a Miner, etc.
A Miner has no Parents. It ~may~ have one or more children.
A Relay must have one or more Parents, in order to operate.
A Node ~may~ accept another Node as a Child.
A Node ~may~ ask another Node, if the former knows the latter's Public Key
(see below) to become one of its Parents. The would-be Parent ~may~ accept
this request. (Also see below.)
A Leaf is a Relay having no Children. It is operated by someone who does not
attempt to resell his Casks (see below) and is only interested in
getting the Transactions which he produced himself, mined in a timely way.
Note that the operator of a Relay can also author transactions himself,
and may choose to make use of one of his Casks to send a
transaction ~of his own~ upstream (rather than reselling said cask to
a Child Node of his.)
A Tree represents any set of Nodes having one or more Miners in common
upstream. These Miners are said to be its 'Roots.'
*******************************************************************************
* 3. Node Mechanics. *
**********************
Let SKN be : The Secret Key (SK) of a Node. It is kept (surprise!) secret
by the Node's operator. And is, ideally, to be destroyed
if there is apprehension of danger of falling into enemy hands,
like any reasonable Secret Key. SKN is generated via Rk.
Let PKN be : The Public Key (PK) of a Node; generated likewise by Rk.
This key is not necessarily "public" in the ordinary sense:
it should only be shared with the Node's Children. A Node ~may~
choose to share its PKN with someone other than one of
its Children -- in the interest of, for instance, attracting new
Children.
When Rk is used to produce a SKN, PKN keypair, we say that 'a Node is born.'
When a SKN is destroyed, we say that 'a Node has died.'
In order for any Node to communicate with another Node, both Nodes must know
one another's PKN's. How this knowledge is to be arrived at, is deliberately
unspecified in this document.
All communication between any two Nodes consists of messages secured with
asymmetric cryptography, via Re and Rd.
A Child may speak to its Parent ~only when spoken to~.
The ~only~ exception is: a request for an upstream Cask. (see Sect. 4.)
The act of a Parent re-issuing a Cask down to a Child, is called Rolling.
The act of a Child passing a Filled Cask up to a Parent, is called Floating.
Think of 'Rolling' as a Cask moving down-stream; 'Floating' - up-stream.
A Child requesting a Cask, is ~expected~ to produce a Fill for said
Cask and Float it back to the Parent in a timely way. (See Section 5.)
Other than the above, any valid message from a Child to a Parent is
~necessarily~ a Fill of a Cask Rolled by the Parent.
A Relay which wishes to transmit a Transaction may request a Cask from
a Parent. And wait for a Cask to be Rolled down. The request must
contain a value for the desired Promise Height. It must also contain
a Bid, comprising the amount (in Satoshi). See Sect. 5.
The Relay's Parent may or may
not Roll a Cask in answer to this request. If it does, the Cask will
have a Promise Height greater or equal to the one requested by the Child.
This is the block height at which the Child ~must~ Fill the Cask, or
will be regarded by the Parent as having caused a Spill. (see below.)
( Warning: somewhat paradoxically, Spills are a thing that can happen
only to ~empty~ Casks. Perhaps they will end up being called something
else... )
A Leaf which wishes to transmit a Transaction may request a Cask from
its parent. And wait for a Cask to be Rolled down. Just like a Relay,
it must request a particular Promise Height, and offer a Bid.
(See Sect. 5.)
A Relay will Roll no Casks unless it has recently requested and received
a Rolled Cask from one of its Parents. Relays will break this rule
at their immediate peril; see discussion of Husks below.
A Node may, at any time, destroy its SKN, and generate a new one, SKN',
and a new PKN, PKN' , via Rk.
For ALL practical purposes, the old Node - even if it occupies, e.g.,
the old Node's IP, or meatspace facility - is to be thought of as dead!
and a new Node as having been thusly born.
The new Node could attempt to demonstrate a continuity of cryptographic
identity with the dead one, and the dead Node's Parents and Children
~may~, at their option, accept a valid Rs(SK, PKN') as proof of this
continuity, and consequently become Parents and Children, respectively,
of the new Node.
A Node ~may~, at any time, choose to ~Unlink~ one or more of its Parents or
Children. This is the act of removing a Node's PKN from another Node's
list of Parent or Child PKN's, for whatever reason. This disconnects it
from the unlinked Node; said Nodes are no longer in communion.
Unlinking is to be thought of as similar to a WoT Negrating.
Nodes ~may~ use an automatic mechanism to effect Unlinkings; or a manual
one; or some combination of the two; or none at all. This is left wholly
to each particular Node's operator.
Typically, a Node might Unlink a Parent for often Rolling 'Husks';
Typically, a Node might Unlink a Child for often causing 'Spills' :
A 'Husk' is a Cask, received by a Child from one of its Parents,
which is not, upon the coming of the Casks's Promise Height,
found to have carried the payload - the Cask Fill - which said
Child had sent back to its Parent -- into a ~mature block~
(see Section 4.)
It represents a broken promise by the Cask's Roller - to carry
the Cask Fill, via ~his~ Parents, to a Miner, who will cement it
into a Block, at or prior to the Promise Height.
This broken promise ~may~ or may not be his fault; or an upstream
Relay or Miner's -- the Children who were issued the Husk,
have no reason to care! Ultimately, they want their Fills mined!
A 'Spill' is the situation where a Cask that was requested by a Child
from one of its Parents, did not end up Filled prior to the
Promise Height of said Cask.
It represents the failure of a Child to either:
a) Fill the Cask with a Transaction from his own Leaf;
or
b) Fill the Cask by issuing a new Cask to a downstream Child,
and receiving a valid Fill from same.
A Cask Fill that turns out to contain a Transaction which
fails to validate -
is a Spill just the same as a Cask that is Rolled and never Floated
by the Child at all.
The one difference is, that this type of Spill can be diagnosed
prior to the time of a Cask's Promise Height.
This is called a Rotten Fill.
A Cask Fill where the Transaction passed up from the Leaf (Transaction
author) does not offer sufficient Fee (See Sect. 5) to cover a
the cumulative cask-chain, is likewise considered a Rotten Fill.
Under no circumstances is a Rotten Fill a candidate for mining:
No Block containing any Rotten Fill is a valid Block per the Block
validation rules.
Any Spill propagates upstream - if a Child requests, and receives,
a Cask from one of its Parents, and said Cask never makes it to a
Leaf seeking to cause a Transaction to be mined - ~for any reason~ -
the Parent whose Cask was Spilled, is now likewise a Spiller to ~its~
Parent, and so forth, all the way upstream to the original Cask Roller,
a Miner.
Any Cask that gets Rolled, but does not end up Floated, is a Spill.
Any Cask that gets Rolled, then correctly Floated, but fails to
deliver a Leaf's payload into a Block, at or prior to the
specified Promise Height of said Cask - is a Husk.
A Husk propagates downstream - if a Parent rolls one of its Children
a Cask that fails - for any reason at all, other than failure by
said Children to Float the Cask, or if they had Rotten Filled it,
to end up in a mature block
before the specified Promise Height - any of the Child's Children who
have been re-issued this Cask, will likewise end up having been
responsible for a Husk, and will be held thusly responsible by
~their~ Children.
A Node that proves to be a chronic emitter of Husks or Spills ---
for ~whatever reason~ --
is likely to be Unlinked by, respectively, its Children and Parents.
A Node ~may~ attempt to publicly identify a Parent as a frequent
emitter of Husks; or a Child as a frequent cause of Spills, by
publicly sharing the offending Node's PKN, and displaying the Cask
in question. Other Nodes ~may~ take this information into account
when choosing Children or Parents. (See Sect. 5.)
*******************************************************************************
* 4. Blocks. *
**************
A Block, B, is a bitstring consisting of the concatenation of:
Block Header Bh, a bitstring of fixed, constant length.
The exact contents of Bh will vary, see section 7.
Block Payload Bp, a bitstring of fixed, constant length (e.g., 1024 kB)
which represents an array of Holes, S_1 .. S_n,
where n is constant, chosen at genesis.
A Bp in turn consists of a certain fixed number of Holes:
Let Pn = C(Bp) , or the number of Holes in a Bp;
Sl = B(S) , or the number of bytes comprising S, a Hole;
Pl = B(Bp) , or the number of bytes in a Bp.
( E.g., the 1024 kB Payload, could contain 1024 Holes, of 1024 bytes each.
or could be cut up differently, so long as Pn * Sl = Pl . Every Payload
will contain the fixed number of Holes, chosen at genesis.)
A Hole is to be thought of as an empty slot where a transaction can be
emplaced by the Miner. (It can also be re-sold by Relays at a markup,
see below.)
We will begin with the base case of a Miner, but a very similar formulation
will describe the behaviour of a Relay.
In order to set the stage for the creation (mining) of a block B, a Miner
generates, in order:
1) W, a random bitstring. (Preferably using a high-quality TRNG!)
W is kept secret by the Miner, until it is time for the block to be
broadcast to the network at large. At that time, it will be placed in the
corresponding field of Bh.
2) Tickets T_1, T_i, ... T_Pn, generated by computing H(Q(W, i)).
This sequence will be regeneratable on demand by anyone who comes
into later possession of W.
3) A sequence of empty Casks, X_1, X_i, .. X_Pn:
Each Cask X represents an available Hole in a block which the Miner
promises to mine in the near future.
An empty Cask X_i is a bitstring with the following substrings:
T_i - A Ticket corresponding to this empty Cask.
C_i - The Ask, in Satoshi, that the issuer of the Ticket
is asking, for the privilege of filling this Cask.
A_i - The destination Address for payment of C_i.
(See Sect. 5 and 6 re: the mechanics.)
Ph_i - The Promise Height, a Block Height at or prior to
which the Miner promises to produce a mature Block
where this Cask, when Floated, occupies a Hole.
Tickets can be generated ahead of time. However, the Asks may depend on
Bids received from the Miner's Children. (Or they may be fixed.)
An Ask of, e.g., 10 Satoshi, means that any Cask containing a Transaction
that does not ultimately leave 10 Satoshi for the Miner, is considered to
be a Spill!
An particular empty Cask is to be Rolled down to ONE of a Miner's (or any
other Node's) Children. The existence of two Casks, Rolled down by a
particular Node to two separate Children, having identical Tickets - is to
be called a Fib. Fibs are ~the~ 'mortal sin' of the network: all but ONE
recipient of a Fib Cask will end up in the guaranteed possession of a Husk.
Fibs are 'the bezzle.' There is no mathematical means to rule out their
existence. However they ~are~ detectable, and provable as such to any party
in possession of:
1) Their Fibber's PKN
and:
2) The two or more more identically-Ticketed Casks that - together -
constitute the Fib itself.
Therefore, any rational Node operator will configure his Nodes to
immediately unlink -- and publicly expose -- any Node that can be shown to
have emitted a Fib at any point in its existence.
Prior to starting the hashing of a Block (see Sect. 7), a Miner ~may~ wait
for all of the Casks he had Rolled, such as were marked with an appropriate
Promised Height, to be Floated back to him, with valid Transactions inside.
At his peril he may choose to fill prolongedly vacant Holes with Fibs
(Casks created on the spot, and Filled with Transactions the Miner himself
generated, solely to Fill said Casks.) It is in all cases in the best
interest of a Miner to Roll only so many Casks downstream as he thinks will
be Filled in a timely manner, rather than risking a reputation as a
Husk-Roller.
The creation of Fibs of this type can be thought of as similar to an
airline's practice of 'overbooking' a plane.
Ideally, Relays will seek to choose as Parents, those Miners who are known
to emit few or no Husks. This means, at the very least, eschewing Fibs
(given as a Fib is guaranteed to produce one or more Husks.)
*******************************************************************************
* 5. The Rolling of Casks. *
****************************
An Cask is said to be Rolled when it is passed by a Parent to a Child.
Only empty Casks (i.e. those not yet containing a Transaction) may be Rolled.
(Casks that have been Filled with a Transaction - can only be Floated. See
below.)
Rolling a Cask involves a transformation whereby the Parent creates a
Sub-Cask, a new, empty Cask linkable to the one the Parent received (if he is
a Relay) or created ex nihilo (if he is a Miner) by a unidirectionally-
verifiable relation. (It becomes bidirectional when the Miner makes the Cask-
Chain public; see Sect. 6.)
An empty Sub-Cask is produced from an empty Cask via the following process:
T'_i = H(T_i).
And again here, anybody Rolling Casks could choose to Fib - i.e.
to supply two or more distinct Children with empty Casks containing
a repeated T. This is Bad and they ought to Feel Bad. And it will be
~detectably~ and ~opposably~ Bad.
C'_i will be greater than C_i. So that the Relay can turn a profit via
the act of successfully relaying.
A'_i will quite obviously be an Address controlled by the owner of
~this~ Relay, as opposed to one belonging to the Parent's owner.
But in principle, it can be whatever the Relay's operator wants it to
be.
Ph'_i will be a value equal to (living very dangerously) or greater than
Ph_i. Again, it is in the best economic interests of every Relay
to make no promises that it has no strong expectation of being able
to ~reliably~ keep.
The life cycle of a Cask:
Empty Casks originate from Miners, who store them until their Children request
them. (see Sect. 4.) But ultimately they must Roll all the way down to a Leaf,
in order to get Filled:
A Node which originates a Transaction, is definitionally - on that occasion -
a Leaf (see Section 2.)
A Leaf initiates a Transaction by generating the Transaction Payload
(see Sect. 6), and thereafter requesting an empty Cask from one of its Parents.
The request is accompanied by a Bid and a desired Promise Height.
(See Sect. 3).
The Leaf's Parent ~may~ then proceed to Roll an empty Cask, as described above.
The Parent may be a Miner, in which case he is in possession of one or more
empty Casks which he himself has created ex-nihilo; or a Relay, in which case
said Relay requests an empty Cask from one of ~its~ Parents.
A Leaf ought not to request casks which it fails to immediately (if they have
been requested as having a near-term Promise Height) Fill and Float. Or it
is considered, by the affected Parent, as having committed a Spill, and may
consequently end up unlinked by selfsame Parent.
A Leaf may send a request to one of its Parents for an empty Cask having a
Promise Height some ways into the future, if such a thing is required.
But the Parent may or may not be able to supply one, because it will request
it from upstream, and ultimately some Miner in the Tree must be willing to
offer such a Cask and Roll it downstream.
Floating is the act of passing a Filled Cask upstream to a Parent. Floating,
like Rolling, can only move a Cask vertically by one step in the Node tree.
First we will describe the base case: how a Leaf fills and Floats a Cask
that it has received from one of its Parents.
The Leaf operator has crafted a Transaction (see Sect. 6) and wishes to see it
mined by a Miner in a predictable time interval (See Sect. 7.)
Thereby the Transaction's Fee must be greater than or equal to the
empty Cask's C_i (Ask) in order for the Leaf's Parent, who has supplied the
Cask, to not immediately consider the Leaf to have committed a Spill.
The Transaction specifies that it assigns its Fee to ~this particular~ empty
Cask's Cask-Chain by including H(T'_i) (the empty Cask's Ticket) in its sealed
payload. (See Sect. 6 for Transaction format.)
The Cask-Chain refers simply to the path linking the Leaf, via zero or more
Relay middlemen, to a Miner, and the cumulative Ask resulting from this path.
The Leaf now Floats the Filled Cask back to the ~specific~ Parent that it had
received the empty Cask from. The Parent first verifies:
1) That the Ticket in the Floated Cask corresponds to the H(T'_i) that
accompanied the original empty Cask.
Thereby the Leaf proves that it has made use of a valid Ticket issued
by this Parent.
and:
2) That the Transaction in the Floated Cask is valid and includes sufficient
Fee to cover the cumulative Cask-Chain (see Sect. 6)
If both of these conditions are met, the Parent signs (in constant time,
in avoidance of side-channel leakage) the Floated Cask, and passes it in turn
to ~its own~ Parent, from whom it had received the empty cask, using the same
scheme as above ( it signs, via Rs, the string created from the Floated Cask
concatenated with the H(T'_i) Ticket it had received from
its Parent. )
And so on, upstream, until the Filled Cask floats up to a Miner. Who emplaces
it into a Block (or fails to.)
*******************************************************************************
* 6. Transactions and the Cask-Chain. *
***************************************
The life cycle of a Transaction consists of the following stages:
1) Egg.
2) Larva.
3) Adult.
An Egg is a string consisting simply of :
I : Input. The index of an Adult Transaction.
O : An Address. (The structure of Addresses is not specified in this
document.)
C : An Amount, in Satoshi; the amount of the desired transfer.
F : An Amount, in Satoshi, comprising the Fee offered up to the
Leaf's Parent (See Sect. 5.) When the Cask ends up mined, each
Node in the Cask-Chain (as illustrated in Sect. 5) will receive,
to its specified A_i, the portion of this Fee corresponding to the
difference between the C'_i ~it~ specified, and the C_i demanded by
~its~ upstream Parent. In the end, the Miner takes his cut (likewise
specified ahead of time, per Section 4), and the entire Fee is
accounted for.
Q : The Conditions demanded of any future Z which purports to spend
the Output, O, of this Transaction.
An Egg is valid if and only if:
1) C + F is less than or equal to the balance of I.O - the balance
of the Input's Output Address.
A Larva is an Egg which also contains:
T : A Ticket, obtained by H(T_i) from an upstream empty Cask.
(See Sect. 4, 5.)
Z : A Signature, specifying that the conditions imposed by the Input
upon any would-be spender of its Output O, have been met.
The structure of Z is not specified in this document.
A Larva is what ends up Filled into an empty Cask which a Leaf receives
from one of its Parents. In order for a Larva to be valid, the Egg
must be valid; likewise, additionally,
1) Z satisfies I.Q -- the Transaction is validly signed by the
encumberer of its Input
2) The fee F satisfies the Cask-Chain's cumulative Ask (See Sect.
4 and 5.)
A Larva TX becomes an Adult TX ~if and only if~ it is mined, and the block
matures (undergoes N - perhaps 6 ? - confirmations.) Until such a time,
it remains a Larva and cannot become the Input of any new Egg.
*******************************************************************************
* 7. Mining. *
**************
Mining consists of the Empty Cask issuance as described in Sect. 4; the
subsequent receipt of Floated Casks as described in Sects 4, 5, and 6; and
the familiar gymnastics with time-variant Difficulty (not described here,
assumed to resemble the process found in classical Bitcoin).
The one substantial difference is that the hash algorithm must incorporate
the proof-of-storage-of-entire-blockchain as described by mircea_popescu
in his article http://trilema.com/2016/the-necessary-prerequisite-for-any-change-to-the-bitcoin-protocol
.
And that a complete Cask-Chain ends up incorporated into every particular Hole
(see Sect. 4) in a Block, complete with Signatures. This allows each level of the
Tree to determine who, downstream and upstream, had lived up to his declared
promises, and who has not (issued one or more provable Husks, Spills, Fibs.)
The material hashed by the miner in the process of attempting to create a valid
block includes not only the entirety of the Cask material; the output of
mircea_popescu's proof function; but also the value of W used to seed Q (see
Sect. 4), which reveals the Tickets generated by the Miner and passed down in
empty Casks, downstream. And in turn reveals which Relays have fulfilled their
obligations to the Miner. And which Relays have fulfilled theirs to their Parents.
*******************************************************************************
*********************
* To be continued.. *
*********************
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
iQEcBAEBCgAGBQJYtQznAAoJELmCKKABq//HdpAIAK+CkXyqIFx5DhoN9d7B+OKK
Rd/7Cijgb6WdxJCh/AXp86wJghnO2u/JeFVh01GuHHDgcEyQ8zS83q4igcrCcO4K
6rpH7xfV2ctlaVaVJVRUqsgWXE28FyEQlWJn5W5bW9JWMTj9i5C1XDDVnOvpF32G
rH1Vua2jbm0zF1CRTS5XL5CL0NI2c/ZXFI7Rjl8TPKxou60KTJLsX4vUHt8Ywtyh
+0SZieGHolqr525Po3boxVGSqmEmFzEE8l6WR6248Blie9qI0N3BOWrFIZxgRadL
sfN5AhJcA1haYA3tgUrY3gYflEpaNrSnaxGUNPJ5mrTobMgKvmZy1A+0dDeshjI=
=oZHy
-----END PGP SIGNATURE-----
More information about the BTC-dev
mailing list