Re: Bitcoin P2P e-cash paper

2008-11-09 Thread Satoshi Nakamoto
Hal Finney wrote:
 it is mentioned that if a broadcast transaction does not reach all nodes,
 it is OK, as it will get into the block chain before long. How does this
 happen - what if the node that creates the next block (the first node
 to find the hashcash collision) did not hear about the transaction,
 and then a few more blocks get added also by nodes that did not hear
 about that transaction? Do all the nodes that did hear it keep that
 transaction around, hoping to incorporate it into a block once they get
 lucky enough to be the one which finds the next collision?

Right, nodes keep transactions in their working set until they get into a 
block.  If a transaction reaches 90% of nodes, then each time a new block is 
found, it has a 90% chance of being in it.


 Or for example, what if a node is keeping two or more chains around as
 it waits to see which grows fastest, and a block comes in for chain A
 which would include a double-spend of a coin that is in chain B? Is that
 checked for or not? (This might happen if someone double-spent and two
 different sets of nodes heard about the two different transactions with
 the same coin.)

That does not need to be checked for.  The transaction in whichever branch ends 
up getting ahead becomes the valid one, the other is invalid.  If someone tries 
to double spend like that, one and only one spend will always become valid, the 
others invalid.

Receivers of transactions will normally need to hold transactions for perhaps 
an hour or more to allow time for this kind of possibility to be resolved.  
They can still re-spend the coins immediately, but they should wait before 
taking an action such as shipping goods.  


 I also don't understand exactly how double-spending, or cancelling
 transactions, is accomplished by a superior attacker who is able to muster
 more computing power than all the honest participants. I see that he can
 create new blocks and add them to create the longest chain, but how can
 he erase or add old transactions in the chain? As the attacker sends out
 his new blocks, aren't there consistency checks which honest nodes can
 perform, to make sure that nothing got erased? More explanation of this
 attack would be helpful, in order to judge the gains to an attacker from
 this, versus simply using his computing power to mint new coins honestly.

The attacker isn't adding blocks to the end.  He has to go back and redo the 
block his transaction is in and all the blocks after it, as well as any new 
blocks the network keeps adding to the end while he's doing that.  He's 
rewriting history.  Once his branch is longer, it becomes the new valid one.

This touches on a key point.  Even though everyone present may see the 
shenanigans going on, there's no way to take advantage of that fact. 

It is strictly necessary that the longest chain is always considered the valid 
one.  Nodes that were present may remember that one branch was there first and 
got replaced by another, but there would be no way for them to convince those 
who were not present of this.  We can't have subfactions of nodes that cling to 
one branch that they think was first, others that saw another branch first, and 
others that joined later and never saw what happened.  The CPU power 
proof-of-work vote must have the final say.  The only way for everyone to stay 
on the same page is to believe that the longest chain is always the valid one, 
no matter what.


 As far as the spending transactions, what checks does the recipient of a
 coin have to perform? Does she need to go back through the coin's entire
 history of transfers, and make sure that every transaction on the list is
 indeed linked into the timestamp block chain? Or can she just do the
 latest one? 

The recipient just needs to verify it back to a depth that is sufficiently far 
back in the block chain, which will often only require a depth of 2 
transactions.  All transactions before that can be discarded.


 Do the timestamp nodes check transactions, making sure that
 the previous transaction on a coin is in the chain, thereby enforcing
 the rule that all transactions in the chain represent valid coins?

Right, exactly.  When a node receives a block, it checks the signatures of 
every transaction in it against previous transactions in blocks.  Blocks can 
only contain transactions that depend on valid transactions in previous blocks 
or the same block.  Transaction C could depend on transaction B in the same 
block and B depends on transaction A in an earlier block.


 Sorry about all the questions, but as I said this does seem to be a
 very promising and original idea, and I am looking forward to seeing
 how the concept is further developed. It would be helpful to see a more
 process oriented description of the idea, with concrete details of the
 data structures for the various objects (coins, blocks, transactions),
 the data which is included in messages, and algorithmic descriptions
 of the procedures for 

Re: Bitcoin P2P e-cash paper

2008-11-09 Thread James A. Donald

--
Satoshi Nakamoto wrote:
 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.

OK, suppose one node incorporates a bunch of
transactions in its proof of work, all of them honest
legitimate single spends and another node incorporates a
slightly different bunch of transactions in its proof of
work, all of them equally honest legitimate single
spends, and both proofs are generated at about the same
time.

What happens then?

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


voting by m of n digital signature?

2008-11-09 Thread James A. Donald

Is there a way of constructing a digital signature so
that the signature proves that at least m possessors of
secret keys corresponding to n public keys signed, for n
a dozen or less, without revealing how many more than m,
or which ones signed?

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: voting by m of n digital signature?

2008-11-09 Thread Richard Salz
 Is there a way of constructing a digital signature so
 that the signature proves that at least m possessors of
 secret keys corresponding to n public keys signed, for n
 a dozen or less, without revealing how many more than m,
 or which ones signed?

Yes there are a number of ways.  Usually they involve splitting the 
private key so that when a quorum of fragment signatures are done, they 
can be combined and the result verified by the public key.   Look for 
multi-step signing or threshold signatures, for example.

Disclaimer: I worked at CertCo who had the best technology in this area. 
It was created for SET.
/r$


--
STSM, DataPower Chief Programmer
WebSphere DataPower SOA Appliances
http://www.ibm.com/software/integration/datapower/

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Bitcoin P2P e-cash paper

2008-11-09 Thread James A. Donald

Satoshi Nakamoto wrote:
 Increasing hardware speed is handled: To compensate
 for increasing hardware speed and varying interest in
 running nodes over time, the proof-of-work difficulty
 is determined by a moving average targeting an average
 number of blocks per hour. If they're generated too
 fast, the difficulty increases.

This does not work - your proposal involves
complications I do not think you have thought through.

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.

This is not an intolerable flaw - predictable inflation
is less objectionable than inflation that gets jiggered
around from time to time to transfer wealth from one
voting block to another.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Bitcoin P2P e-cash paper

2008-11-09 Thread Satoshi Nakamoto
James A. Donald wrote:
OK, suppose one node incorporates a bunch of
transactions in its proof of work, all of them honest
legitimate single spends and another node incorporates a
different bunch of transactions in its proof of
work, all of them equally honest legitimate single
spends, and both proofs are generated at about the same
time.

What happens then?

They both broadcast their blocks.  All nodes receive them and keep both, but 
only work on the one they received first.  We'll suppose exactly half received 
one first, half the other.  

In a short time, all the transactions will finish propagating so that everyone 
has the full set.  The nodes working on each side will be trying to add the 
transactions that are missing from their side.  When the next proof-of-work is 
found, whichever previous block that node was working on, that branch becomes 
longer and the tie is broken.  Whichever side it is, the new block will contain 
the other half of the transactions, so in either case, the branch will contain 
all transactions.  Even in the unlikely event that a split happened twice in a 
row, both sides of the second split would contain the full set of transactions 
anyway.

It's not a problem if transactions have to wait one or a few extra cycles to 
get into a block. 

Satoshi Nakamoto



-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Bitcoin P2P e-cash paper

2008-11-09 Thread Satoshi Nakamoto
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


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Bitcoin P2P e-cash paper

2008-11-09 Thread James A. Donald

Satoshi Nakamoto wrote:
 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.

The trouble is, you are comparing with the Bankcard
network.

But a new currency cannot compete directly with an old,
because network effects favor the old.

You have to go where Bankcard does not go.

At present, file sharing works by barter for bits. This,
however requires the double coincidence of wants. People
only upload files they are downloading, and once the
download is complete, stop seeding. So only active
files, files that quite a lot of people want at the same
time, are available.

File sharing requires extremely cheap transactions,
several transactions per second per client, day in and
day out, with monthly transaction costs being very small
per client, so to support file sharing on bitcoins, we
will need a layer of account money on top of the
bitcoins, supporting transactions of a hundred
thousandth the size of the smallest coin, and to support
anonymity, chaumian money on top of the account money.

Let us call a bitcoin bank a bink.  The bitcoins stand
in the same relation to account money as gold stood in
the days of the gold standard.  The binks, not trusting
each other to be liquid when liquidity is most needed,
settle out any net discrepancies with each other by
moving bit coins around once every hundred thousand
seconds or so, so bitcoins do not change owners that
often,   Most transactions cancel out at the account
level.  The binks demand bitcoins of each other only
because they don't want to hold account money for too
long. So a relatively small amount of bitcoins
infrequently transacted can support a somewhat larger
amount of account money frequently transacted.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]