>Satoshi Nakamoto wrote:
>> I’ve been working on a new electronic cash system that’s fully
>> peer-to-peer, with no trusted third party.
>>
>> The paper is available at:
>> http://www.bitcoin.org/bitcoin.pdf
>
>We very, very much need such a system, but the way I understand your
>proposal, it does not seem to scale to the required size.
>
>For transferable proof of work tokens to have value, they must have
>monetary value. To have monetary value, they must be transferred within
>a very large network – for example a file trading network akin to
>bittorrent.
>
>To detect and reject a double spending event in a timely manner, one
>must have most past transactions of the coins in the transaction, which,
> naively implemented, requires each peer to have most past
>transactions, or most past transactions that occurred recently. If
>hundreds of millions of people are doing transactions, that is a lot of
>bandwidth – each must know all, or a substantial part thereof.

Long before the network gets anywhere near as large as that, it would be safe
for users to use Simplified Payment Verification (section 8) to check for
double spending, which only requires having the chain of block headers, or
about 12KB per day. Only people trying to create new coins would need to run
network nodes. At first, most users would run network nodes, but as the
network grows beyond a certain point, it would be left more and more to
specialists with server farms of specialized hardware. A server farm would
only need to have one node on the network and the rest of the LAN connects with
that one node.

The bandwidth might not be as prohibitive as you think. A typical transaction
would be about 400 bytes (ECC is nicely compact). Each transaction has to be
broadcast twice, so lets say 1KB per transaction. Visa processed 37 billion
transactions in FY2008, or an average of 100 million transactions per day.
That many transactions would take 100GB of bandwidth, or the size of 12 DVD or
2 HD quality movies, or about $18 worth of bandwidth at current prices.

If the network were to get that big, it would take several years, and by then,
sending 2 HD movies over the Internet would probably not seem like a big deal.

Satoshi Nakamoto

263,353 total views, 9 views today

Re: Bitcoin P2P e-cash paper

NOVEMBER 9, 2008 SATOSHI NAKAMOTO CRYPTOGRAPHY MAILING LIST

James A. Donald wrote:
> The core concept is that lots of entities keep complete and consistent
> information as to who owns which bitcoins.
>
> But maintaining consistency is tricky. It is not clear to me what
> happens when someone reports one transaction to one maintainer, and
> someone else transports another transaction to another maintainer. The
> transaction cannot be known to be valid until it has been incorporated
> into a globally shared view of all past transactions, and no one can
> know that a globally shared view of all past transactions is globally
> shared until after some time has passed, and after many new
> transactions have arrived.
>
> Did you explain how to do this, and it just passed over my head, or
> were you confident it could be done, and a bit vague as to the details?

The proof-of-work chain is the solution to the synchronisation problem, and to
knowing what the globally shared view is without having to trust anyone.

A transaction will quickly propagate throughout the network, so if two versions
of the same transaction were reported at close to the same time, the one with
the head start would have a big advantage in reaching many more nodes first.
Nodes will only accept the first one they see, refusing the second one to
arrive, so the earlier transaction would have many more nodes working on
incorporating it into the next proof-of-work. In effect, each node votes for
its viewpoint of which transaction it saw first by including it in its
proof-of-work effort.

If the transactions did come at exactly the same time and there was an even
split, it’s a toss up based on which gets into a proof-of-work first, and that
decides which is valid.

When a node finds a proof-of-work, the new block is propagated throughout the
network and everyone adds it to the chain and starts working on the next block
after it. Any nodes that had the other transaction will stop trying to include
it in a block, since it’s now invalid according to the accepted chain.

The proof-of-work chain is itself self-evident proof that it came from the
globally shared view. Only the majority of the network together has enough CPU
power to generate such a difficult chain of proof-of-work. Any user, upon
receiving the proof-of-work chain, can see what the majority of the network has
approved. Once a transaction is hashed into a link that’s a few links back in
the chain, it is firmly etched into the global history.

Satoshi Nakamoto

Re: Bitcoin P2P e-cash paper

NOVEMBER 10, 2008 SATOSHI NAKAMOTO CRYPTOGRAPHY MAILING LIST

James A. Donald wrote:
> Furthermore, it cannot be made to work, as in the
> proposed system the work of tracking who owns what coins
> is paid for by seigniorage, which requires inflation.

If you’re having trouble with the inflation issue, it’s easy to tweak it for
transaction fees instead. It’s as simple as this: let the output value from
any transaction be 1 cent less than the input value. Either the client
software automatically writes transactions for 1 cent more than the intended
payment value, or it could come out of the payee’s side. The incentive value
when a node finds a proof-of-work for a block could be the total of the fees in
the block.

Satoshi Nakamoto

Re: Bitcoin P2P e-cash paper

NOVEMBER 14, 2008 SATOSHI NAKAMOTO CRYPTOGRAPHY MAILING LIST

Hal Finney wrote:
> I think it is necessary that nodes keep a separate
> pending-transaction list associated with each candidate chain.
> … One might also ask … how many candidate chains must
> a given node keep track of at one time, on average?

Fortunately, it’s only necessary to keep a pending-transaction pool for the
current best branch. When a new block arrives for the best branch,
ConnectBlock removes the block’s transactions from the pending-tx pool. If a
different branch becomes longer, it calls DisconnectBlock on the main branch
down to the fork, returning the block transactions to the pending-tx pool, and
calls ConnectBlock on the new branch, sopping back up any transactions that
were in both branches. It’s expected that reorgs like this would be rare and
shallow.

With this optimisation, candidate branches are not really any burden. They
just sit on the disk and don’t require attention unless they ever become the
main chain.

> Or as James raised earlier, if the network broadcast
> is reliable but depends on a potentially slow flooding
> algorithm, how does that impact performance?

Broadcasts will probably be almost completely reliable. TCP transmissions are
rarely ever dropped these days, and the broadcast protocol has a retry
mechanism to get the data from other nodes after a while. If broadcasts turn
out to be slower in practice than expected, the target time between blocks may
have to be increased to avoid wasting resources. We want blocks to usually
propagate in much less time than it takes to generate them, otherwise nodes
would spend too much time working on obsolete blocks.

I’m planning to run an automated test with computers randomly sending payments
to each other and randomly dropping packets.

> 3. The bitcoin system turns out to be socially useful and valuable, so
> that node operators feel that they are making a beneficial contribution
> to the world by their efforts (similar to the various “@Home” compute
> projects where people volunteer their compute resources for good causes).
>
> In this case it seems to me that simple altruism can suffice to keep the
> network running properly.

It’s very attractive to the libertarian viewpoint if we can explain it
properly. I’m better with code than with words though.

Satoshi Nakamoto

Re: Bitcoin P2P e-cash paper

NOVEMBER 17, 2008 SATOSHI NAKAMOTO CRYPTOGRAPHY MAILING LIST

I’ll try and hurry up and release the sourcecode as soon as possible to serve
as a reference to help clear up all these implementation questions.

Ray Dillinger (Bear) wrote:
> When a coin is spent, the buyer and seller digitally sign a (blinded)
> transaction record.

Only the buyer signs, and there’s no blinding.

> If someone double spends, then the transaction record
> can be unblinded revealing the identity of the cheater.

Identities are not used, and there’s no reliance on recourse. It’s all
prevention.

> This is done via a fairly standard cut-and-choose
> algorithm where the buyer responds to several challenges
> with secret shares

No challenges or secret shares. A basic transaction is just what you see in
the figure in section 2. A signature (of the buyer) satisfying the public key
of the previous transaction, and a new public key (of the seller) that must be
satisfied to spend it the next time.

> They may also receive chains as long as the one they’re trying to
> extend while they work, in which the last few “links” are links
> that are *not* in common with the chain on which they’re working.
> These they ignore.

Right, if it’s equal in length, ties are broken by keeping the earliest one
received.

> If it contains a double spend, then they create a “transaction”
> which is a proof of double spending, add it to their pool A,
> broadcast it, and continue work.

There’s no need for reporting of “proof of double spending” like that. If the
same chain contains both spends, then the block is invalid and rejected.

Same if a block didn’t have enough proof-of-work. That block is invalid and
rejected. There’s no need to circulate a report about it. Every node could
see that and reject it before relaying it.

If there are two competing chains, each containing a different version of the
same transaction, with one trying to give money to one person and the other
trying to give the same money to someone else, resolving which of the spends is
valid is what the whole proof-of-work chain is about.

We’re not “on the lookout” for double spends to sound the alarm and catch the
cheater. We merely adjudicate which one of the spends is valid. Receivers of
transactions must wait a few blocks to make sure that resolution has had time
to complete. Would be cheaters can try and simultaneously double-spend all
they want, and all they accomplish is that within a few blocks, one of the
spends becomes valid and the others become invalid. Any later double-spends
are immediately rejected once there’s already a spend in the main chain.

Even if an earlier spend wasn’t in the chain yet, if it was already in all the
nodes’ pools, then the second spend would be turned away by all those nodes
that already have the first spend.

> If the new chain is accepted, then they give up on adding their
> current link, dump all the transactions from pool L back into pool
> A (along with transactions they’ve received or created since
> starting work), eliminate from pool A those transaction records
> which are already part of a link in the new chain, and start work
> again trying to extend the new chain.

Right. They also refresh whenever a new transaction comes in, so L pretty much
contains everything in A all the time.

> CPU-intensive digital signature algorithm to
> sign the chain including the new block L.

It’s a Hashcash style SHA-256 proof-of-work (partial pre-image of zero), not a
signature.

> Is there a mechanism to make sure that the “chain” does not consist
> solely of links added by just the 3 or 4 fastest nodes? ‘Cause a
> broadcast transaction record could easily miss those 3 or 4 nodes
> and if it does, and those nodes continue to dominate the chain, the
> transaction might never get added.

If you’re thinking of it as a CPU-intensive digital signing, then you may be
thinking of a race to finish a long operation first and the fastest always
winning.

The proof-of-work is a Hashcash style SHA-256 collision finding. It’s a
memoryless process where you do millions of hashes a second, with a small
chance of finding one each time. The 3 or 4 fastest nodes’ dominance would
only be proportional to their share of the total CPU power. Anyone’s chance of
finding a solution at any time is proportional to their CPU power.

There will be transaction fees, so nodes will have an incentive to receive and
include all the transactions they can. Nodes will eventually be compensated by
transaction fees alone when the total coins created hits the pre-determined
ceiling.

> Also, the work requirement for adding a link to the chain should
> vary (again exponentially) with the number of links added to that
> chain in the previous week, causing the rate of coin generation
> (and therefore inflation) to be strictly controlled.

Right.

> You need coin aggregation for this to scale. There needs to be
> a “provable” transaction where someone retires ten single coins
> and creates a new coin with denomination ten, etc.

Every transaction is one of these. Section 9, Combining and Splitting Value.
Satoshi Nakamoto

Re: Bitcoin P2P e-cash paper

NOVEMBER 17, 2008 SATOSHI NAKAMOTO CRYPTOGRAPHY MAILING LIST

Ray Dillinger wrote:
> One way to do this would be
> to have the person recieving the coin generate an asymmetric
> key pair, and then have half of it published with the
> transaction. In order to spend the coin later, s/he must
> demonstrate posession of the other half of the asymmetric
> key pair, probably by using it to sign the key provided by
> the new seller.

Right, it’s ECC digital signatures. A new key pair is used for every
transaction.

It’s not pseudonymous in the sense of nyms identifying people, but it
is at least a little pseudonymous in that the next action on a coin
can be identified as being from the owner of that coin.

> Mmmm. I don’t know if I’m comfortable with that. You’re saying
> there’s no effort to identify and exclude nodes that don’t
> cooperate? I suspect this will lead to trouble and possible DOS
> attacks.

There is no reliance on identifying anyone. As you’ve said, it’s
futile and can be trivially defeated with sock puppets.

The credential that establishes someone as real is the ability to
supply CPU power.

> Until…. until what? How does anybody know when a transaction
> has become irrevocable? Is “a few” blocks three? Thirty? A
> hundred? Does it depend on the number of nodes? Is it logarithmic
> or linear in number of nodes?

Section 11 calculates the worst case under attack. Typically, 5 or
10 blocks is enough for that. If you’re selling something that
doesn’t merit a network-scale attack to steal it, in practice you
could cut it closer.

> But in the absence of identity, there’s no downside to them
> if spends become invalid, if they’ve already received the
> goods they double-spent for (access to website, download,
> whatever). The merchants are left holding the bag with
> “invalid” coins, unless they wait that magical “few blocks”
> (and how can they know how many?) before treating the spender
> as having paid.
>
> The consumers won’t do this if they spend their coin and it takes
> an hour to clear before they can do what they spent their coin on.
> The merchants won’t do it if there’s no way to charge back a
> customer when they find the that their coin is invalid because
> the customer has doublespent.

This is a version 2 problem that I believe can be solved fairly
satisfactorily for most applications.

The race is to spread your transaction on the network first. Think 6
degrees of freedom — it spreads exponentially. It would only take
something like 2 minutes for a transaction to spread widely enough
that a competitor starting late would have little chance of grabbing
very many nodes before the first one is overtaking the whole network.
During those 2 minutes, the merchant’s nodes can be watching for a
double-spent transaction. The double-spender would not be able to
blast his alternate transaction out to the world without the merchant
getting it, so he has to wait before starting.

If the real transaction reaches 90% and the double-spent tx reaches
10%, the double-spender only gets a 10% chance of not paying, and 90%
chance his money gets spent. For almost any type of goods, that’s
not going to be worth it for the scammer.

Information based goods like access to website or downloads are
non-fencible. Nobody is going to be able to make a living off
stealing access to websites or downloads. They can go to the file
sharing networks to steal that. Most instant-access products aren’t
going to have a huge incentive to steal.

If a merchant actually has a problem with theft, they can make the
customer wait 2 minutes, or wait for something in e-mail, which many
already do. If they really want to optimize, and it’s a large
download, they could cancel the download in the middle if the
transaction comes back double-spent. If it’s website access,
typically it wouldn’t be a big deal to let the customer have access
for 5 minutes and then cut off access if it’s rejected. Many such
sites have a free trial anyway.

Satoshi Nakamoto