Guest User

Bitcoin

a guest
Jan 6th, 2014
1,332
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Satoshi Nakamoto Sat, 01 Nov 2008 16:16:33 -0700
  2.  
  3. I've been working on a new electronic cash system that's fully
  4. peer-to-peer, with no trusted third party.
  5.  
  6. The paper is available at:
  7. http://www.bitcoin.org/bitcoin.pdf
  8.  
  9. The main properties:
  10. Double-spending is prevented with a peer-to-peer network.
  11. No mint or other trusted parties.
  12. Participants can be anonymous.
  13. New coins are made from Hashcash style proof-of-work.
  14. The proof-of-work for new coin generation also powers the
  15. network to prevent double-spending.
  16.  
  17. Bitcoin: A Peer-to-Peer Electronic Cash System
  18.  
  19. Abstract. A purely peer-to-peer version of electronic cash would
  20. allow online payments to be sent directly from one party to another
  21. without the burdens of going through a financial institution.
  22. Digital signatures provide part of the solution, but the main
  23. benefits are lost if a trusted party is still required to prevent
  24. double-spending. We propose a solution to the double-spending
  25. problem using a peer-to-peer network. The network timestamps
  26. transactions by hashing them into an ongoing chain of hash-based
  27. proof-of-work, forming a record that cannot be changed without
  28. redoing the proof-of-work. The longest chain not only serves as
  29. proof of the sequence of events witnessed, but proof that it came
  30. from the largest pool of CPU power. As long as honest nodes control
  31. the most CPU power on the network, they can generate the longest
  32. chain and outpace any attackers. The network itself requires
  33. minimal structure. Messages are broadcasted on a best effort basis,
  34. and nodes can leave and rejoin the network at will, accepting the
  35. longest proof-of-work chain as proof of what happened while they
  36. were gone.
  37.  
  38. Full paper at:
  39. http://www.bitcoin.org/bitcoin.pdf
  40.  
  41. Satoshi Nakamoto
  42.  
  43. ---------------------------------------------------------------------
  44. The Cryptography Mailing List
  45. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  46.  
  47. James A. Donald Sun, 02 Nov 2008 17:55:45 -0800
  48.  
  49. Satoshi Nakamoto wrote:
  50. I've been working on a new electronic cash system that's fully
  51. peer-to-peer, with no trusted third party.
  52.  
  53. The paper is available at:
  54. http://www.bitcoin.org/bitcoin.pdf
  55.  
  56. 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.
  57.  
  58. 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.
  59.  
  60. 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.
  61.  
  62. ---------------------------------------------------------------------
  63. The Cryptography Mailing List
  64. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  65.  
  66. John Levine Mon, 03 Nov 2008 11:45:11 -0800
  67.  
  68. > As long as honest nodes control the most CPU power on the network,
  69. > they can generate the longest chain and outpace any attackers.
  70.  
  71. But they don't. Bad guys routinely control zombie farms of 100,000
  72. machines or more. People I know who run a blacklist of spam sending
  73. zombies tell me they often see a million new zombies a day.
  74.  
  75. This is the same reason that hashcash can't work on today's Internet
  76. -- the good guys have vastly less computational firepower than the bad
  77. guys.
  78.  
  79. I also have my doubts about other issues, but this one is the killer.
  80.  
  81. R's,
  82. John
  83.  
  84.  
  85. ---------------------------------------------------------------------
  86. The Cryptography Mailing List
  87. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  88.  
  89. Satoshi Nakamoto Sun, 02 Nov 2008 17:56:27 -0800
  90.  
  91. >Satoshi Nakamoto wrote:
  92. >> I've been working on a new electronic cash system that's fully
  93. >> peer-to-peer, with no trusted third party.
  94. >>
  95. >> The paper is available at:
  96. >> http://www.bitcoin.org/bitcoin.pdf
  97. >
  98. >We very, very much need such a system, but the way I understand your
  99. >proposal, it does not seem to scale to the required size.
  100. >
  101. >For transferable proof of work tokens to have value, they must have
  102. >monetary value. To have monetary value, they must be transferred within
  103. >a very large network - for example a file trading network akin to
  104. >bittorrent.
  105. >
  106. >To detect and reject a double spending event in a timely manner, one
  107. >must have most past transactions of the coins in the transaction, which,
  108. > naively implemented, requires each peer to have most past
  109. >transactions, or most past transactions that occurred recently. If
  110. >hundreds of millions of people are doing transactions, that is a lot of
  111. >bandwidth - each must know all, or a substantial part thereof.
  112. >
  113.  
  114.  
  115. Long before the network gets anywhere near as large as that, it would be safe
  116. for users to use Simplified Payment Verification (section 8) to check for
  117. double spending, which only requires having the chain of block headers, or
  118. about 12KB per day. Only people trying to create new coins would need to run
  119. network nodes. At first, most users would run network nodes, but as the
  120. network grows beyond a certain point, it would be left more and more to
  121. specialists with server farms of specialized hardware. A server farm would
  122. only need to have one node on the network and the rest of the LAN connects with
  123. that one node.
  124.  
  125. The bandwidth might not be as prohibitive as you think. A typical transaction
  126. would be about 400 bytes (ECC is nicely compact). Each transaction has to be
  127. broadcast twice, so lets say 1KB per transaction. Visa processed 37 billion
  128. transactions in FY2008, or an average of 100 million transactions per day.
  129. That many transactions would take 100GB of bandwidth, or the size of 12 DVD or
  130. 2 HD quality movies, or about $18 worth of bandwidth at current prices.
  131.  
  132. If the network were to get that big, it would take several years, and by then,
  133. sending 2 HD movies over the Internet would probably not seem like a big deal.
  134.  
  135. Satoshi Nakamoto
  136.  
  137. ---------------------------------------------------------------------
  138. The Cryptography Mailing List
  139. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  140.  
  141. James A. Donald Wed, 05 Nov 2008 13:47:40 -0800
  142.  
  143. James A. Donald:
  144. > > To detect and reject a double spending event in a
  145. > > timely manner, one must have most past transactions
  146. > > of the coins in the transaction, which, naively
  147. > > implemented, requires each peer to have most past
  148. > > transactions, or most past transactions that
  149. > > occurred recently. If hundreds of millions of people
  150. > > are doing transactions, that is a lot of bandwidth -
  151. > > each must know all, or a substantial part thereof.
  152.  
  153. Satoshi Nakamoto wrote:
  154. > Long before the network gets anywhere near as large as
  155. > that, it would be Safe for users to use Simplified
  156. > Payment Verification (section 8) to check for double
  157. > spending, which only requires having the chain of
  158. > block headers,
  159.  
  160. If I understand Simplified Payment Verification
  161. correctly:
  162.  
  163. New coin issuers need to store all coins and all recent
  164. coin transfers.
  165.  
  166. There are many new coin issuers, as many as want to be
  167. issuers, but far more coin users.
  168.  
  169. Ordinary entities merely transfer coins. To see if a
  170. coin transfer is OK, they report it to one or more new
  171. coin issuers and see if the new coin issuer accepts it.
  172. New coin issuers check transfers of old coins so that
  173. their new coins have valid form, and they report the
  174. outcome of this check so that people will report their
  175. transfers to the new coin issuer.
  176.  
  177. If someone double spends a coin, and one expenditure is
  178. reported to one new coin issuer, and the other
  179. simultaneously reported to another new coin issuer, then
  180. both issuers to swifly agree on a unique sequence order
  181. of payments. This, however, is a non trivial problem of
  182. a massively distributed massive database, a notoriously
  183. tricky problem, for which there are at present no peer
  184. to peer solutions. Obiously it is a solvable problem,
  185. people solve it all the time, but not an easy problem.
  186. People fail to solve it rather more frequently.
  187.  
  188. But let us suppose that the coin issue network is
  189. dominated by a small number of issuers as seems likely.
  190.  
  191. If a small number of entities are issuing new coins,
  192. this is more resistant to state attack that with a
  193. single issuer, but the government regularly attacks
  194. financial networks, with the financial collapse ensuing
  195. from the most recent attack still under way as I write
  196. this.
  197.  
  198. Government sponsored enterprises enter the business, in
  199. due course bad behavior is made mandatory, and the evil
  200. financial network is bigger than the honest financial
  201. network, with the result that even though everyone knows
  202. what is happening, people continue to use the paper
  203. issued by the evil financial network, because of network
  204. effects - the big, main issuers, are the issuers you use
  205. if you want to do business.
  206.  
  207. Then knowledgeable people complain that the evil
  208. financial network is heading for disaster, that the
  209. government sponsored enterprises are about to cause a
  210. "collapse of the total financial system", as Wallison
  211. and Alan Greenspan complained in 2005, the government
  212. debates shrinking the evil government sponsored
  213. enterprises, as with "S. 190 [109th]: Federal Housing
  214. Enterprise Regulatory Reform Act of 2005" but they find
  215. easy money too seductive, and S. 190 goes down in flames
  216. before a horde of political activists chanting that easy
  217. money is sound, and opposing it is racist, nazi,
  218. ignorant, and generally hateful, the recent S. 190
  219. debate on limiting portfolios (bond issue supporting dud
  220. mortgages) by government sponsored enterprises being a
  221. perfect reprise of the debates on limiting the issue of
  222. new assignats in the 1790s.
  223.  
  224. The big and easy government attacks on money target a
  225. single central money issuer, as with the first of the
  226. modern political attacks, the French Assignat of 1792,
  227. but in the late nineteenth century political attacks on
  228. financial networks began, as for example the Federal
  229. reserve act of 1913, the goal always being to wind up
  230. the network into a single too big to fail entity, and
  231. they have been getting progressively bigger, more
  232. serious, and more disastrous, as with the most recent
  233. one. Each attack is hugely successful, and after the
  234. cataclysm that the attack causes the attackers are
  235. hailed as saviors of the poor, the oppressed, and the
  236. nation generally, and the blame for the the bad
  237. consequences is dumped elsewhere, usually on Jews,
  238. greedy bankers, speculators, etc, because such attacks
  239. are difficult for ordinary people understand. I have
  240. trouble understanding your proposal - ordinary users
  241. will be easily bamboozled by a government sponsored
  242. security update. Further, when the crisis hits, to
  243. disagree with the line, to doubt that the regulators are
  244. right, and the problem is the evil speculators, becomes
  245. political suicide, as it did in America in 2007,
  246. sometimes physical suicide, as in Weimar Germany.
  247.  
  248. Still, it is better, and more resistant to attack by
  249. government sponsored enterprises, than anything I have
  250. seen so far.
  251.  
  252. > Visa processed 37 billion transactions in FY2008, or
  253. > an average of 100 million transactions per day. That
  254. > many transactions would take 100GB of bandwidth, or
  255. > the size of 12 DVD or 2 HD quality movies, or about
  256. > $18 worth of bandwidth at current prices.
  257.  
  258. > If the network were to get that big, it would take
  259. > several years, and by then, sending 2 HD movies over
  260. > the Internet would probably not seem like a big deal.
  261.  
  262. If there were a hundred or a thousand money issuers by
  263. the time the government attacks, the kind of government
  264. attacks on financial networks that we have recently seen
  265. might well be more difficult.
  266.  
  267. But I think we need to concern ourselves with minimizing
  268. the data and bandwidth required by money issuers - for
  269. small coins, the protocol seems wasteful. It would be
  270. nice to have the full protocol for big coins, and some
  271. shortcut for small coins wherein people trust account
  272. based money for small amounts till they get wrapped up
  273. into big coins.
  274.  
  275. The smaller the data storage and bandwidth required for
  276. money issuers, the more resistant the system is the kind
  277. of government attacks on financial networks that we have
  278. recently seen.
  279.  
  280. ---------------------------------------------------------------------
  281. The Cryptography Mailing List
  282. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  283.  
  284. Ray Dillinger Fri, 07 Nov 2008 09:29:47 -0800
  285.  
  286. On Tue, 2008-11-04 at 06:20 +1000, James A. Donald wrote:
  287.  
  288. > If I understand Simplified Payment Verification
  289. > correctly:
  290. >
  291. > New coin issuers need to store all coins and all recent
  292. > coin transfers.
  293. >
  294. > There are many new coin issuers, as many as want to be
  295. > issuers, but far more coin users.
  296. >
  297. > Ordinary entities merely transfer coins. To see if a
  298. > coin transfer is OK, they report it to one or more new
  299. > coin issuers and see if the new coin issuer accepts it.
  300. > New coin issuers check transfers of old coins so that
  301. > their new coins have valid form, and they report the
  302. > outcome of this check so that people will report their
  303. > transfers to the new coin issuer.
  304.  
  305.  
  306. I think the real issue with this system is the market
  307. for bitcoins.
  308.  
  309. Computing proofs-of-work have no intrinsic value. We
  310. can have a limited supply curve (although the "currency"
  311. is inflationary at about 35% as that's how much faster
  312. computers get annually) but there is no demand curve
  313. that intersects it at a positive price point.
  314.  
  315. I know the same (lack of intrinsic value) can be said of
  316. fiat currencies, but an artificial demand for fiat
  317. currencies is created by (among other things) taxation
  318. and legal-tender laws. Also, even a fiat currency can
  319. be an inflation hedge against another fiat currency's
  320. higher rate of inflation. But in the case of bitcoins
  321. the inflation rate of 35% is almost guaranteed by the
  322. technology, there are no supporting mechanisms for
  323. taxation, and no legal-tender laws. People will not
  324. hold assets in this highly-inflationary currency if
  325. they can help it.
  326.  
  327. Bear
  328.  
  329.  
  330. ---------------------------------------------------------------------
  331. The Cryptography Mailing List
  332. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  333.  
  334. James A. Donald Sun, 09 Nov 2008 11:15:00 -0800
  335.  
  336. Satoshi Nakamoto wrote:
  337. > The bandwidth might not be as prohibitive as you
  338. > think. A typical transaction would be about 400 bytes
  339. > (ECC is nicely compact). Each transaction has to be
  340. > broadcast twice, so lets say 1KB per transaction.
  341. > Visa processed 37 billion transactions in FY2008, or
  342. > an average of 100 million transactions per day. That
  343. > many transactions would take 100GB of bandwidth, or
  344. > the size of 12 DVD or 2 HD quality movies, or about
  345. > $18 worth of bandwidth at current prices.
  346.  
  347. The trouble is, you are comparing with the Bankcard
  348. network.
  349.  
  350. But a new currency cannot compete directly with an old,
  351. because network effects favor the old.
  352.  
  353. You have to go where Bankcard does not go.
  354.  
  355. At present, file sharing works by barter for bits. This,
  356. however requires the double coincidence of wants. People
  357. only upload files they are downloading, and once the
  358. download is complete, stop seeding. So only active
  359. files, files that quite a lot of people want at the same
  360. time, are available.
  361.  
  362. File sharing requires extremely cheap transactions,
  363. several transactions per second per client, day in and
  364. day out, with monthly transaction costs being very small
  365. per client, so to support file sharing on bitcoins, we
  366. will need a layer of account money on top of the
  367. bitcoins, supporting transactions of a hundred
  368. thousandth the size of the smallest coin, and to support
  369. anonymity, chaumian money on top of the account money.
  370.  
  371. Let us call a bitcoin bank a bink. The bitcoins stand
  372. in the same relation to account money as gold stood in
  373. the days of the gold standard. The binks, not trusting
  374. each other to be liquid when liquidity is most needed,
  375. settle out any net discrepancies with each other by
  376. moving bit coins around once every hundred thousand
  377. seconds or so, so bitcoins do not change owners that
  378. often, Most transactions cancel out at the account
  379. level. The binks demand bitcoins of each other only
  380. because they don't want to hold account money for too
  381. long. So a relatively small amount of bitcoins
  382. infrequently transacted can support a somewhat larger
  383. amount of account money frequently transacted.
  384.  
  385. ---------------------------------------------------------------------
  386. The Cryptography Mailing List
  387. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  388.  
  389. Satoshi Nakamoto Mon, 03 Nov 2008 11:45:58 -0800
  390.  
  391. >> As long as honest nodes control the most CPU power on the network,
  392. >> they can generate the longest chain and outpace any attackers.
  393. >
  394. >But they don't. Bad guys routinely control zombie farms of 100,000
  395. >machines or more. People I know who run a blacklist of spam sending
  396. >zombies tell me they often see a million new zombies a day.
  397. >
  398. >This is the same reason that hashcash can't work on today's Internet
  399. >-- the good guys have vastly less computational firepower than the bad
  400. >guys.
  401.  
  402. Thanks for bringing up that point.
  403.  
  404. I didn't really make that statement as strong as I could have. The requirement
  405. is that the good guys collectively have more CPU power than any single
  406. attacker.
  407.  
  408. There would be many smaller zombie farms that are not big enough to overpower
  409. the network, and they could still make money by generating bitcoins. The
  410. smaller farms are then the "honest nodes". (I need a better term than
  411. "honest") The more smaller farms resort to generating bitcoins, the higher the
  412. bar gets to overpower the network, making larger farms also too small to
  413. overpower it so that they may as well generate bitcoins too. According to the
  414. "long tail" theory, the small, medium and merely large farms put together
  415. should add up to a lot more than the biggest zombie farm.
  416.  
  417. Even if a bad guy does overpower the network, it's not like he's instantly
  418. rich. All he can accomplish is to take back money he himself spent, like
  419. bouncing a check. To exploit it, he would have to buy something from a
  420. merchant, wait till it ships, then overpower the network and try to take his
  421. money back. I don't think he could make as much money trying to pull a carding
  422. scheme like that as he could by generating bitcoins. With a zombie farm that
  423. big, he could generate more bitcoins than everyone else combined.
  424.  
  425. The Bitcoin network might actually reduce spam by diverting zombie farms to
  426. generating bitcoins instead.
  427.  
  428. Satoshi Nakamoto
  429.  
  430. ---------------------------------------------------------------------
  431. The Cryptography Mailing List
  432. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  433.  
  434. Satoshi Nakamoto Fri, 07 Nov 2008 09:30:36 -0800
  435.  
  436. >[Lengthy exposition of vulnerability of a systm to use-of-force
  437. >monopolies ellided.]
  438. >
  439. >You will not find a solution to political problems in cryptography.
  440.  
  441. Yes, but we can win a major battle in the arms race and gain a new territory of
  442. freedom for several years.
  443.  
  444. Governments are good at cutting off the heads of a centrally controlled
  445. networks like Napster, but pure P2P networks like Gnutella and Tor seem to be
  446. holding their own.
  447.  
  448. Satoshi
  449.  
  450.  
  451. ---------------------------------------------------------------------
  452. The Cryptography Mailing List
  453. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  454.  
  455. "Hal Finney" Sat, 08 Nov 2008 10:57:08 -0800
  456.  
  457. Bitcoin seems to be a very promising idea. I like the idea of basing
  458. security on the assumption that the CPU power of honest participants
  459. outweighs that of the attacker. It is a very modern notion that exploits
  460. the power of the long tail. When Wikipedia started I never thought it
  461. would work, but it has proven to be a great success for some of the
  462. same reasons.
  463.  
  464. I also do think that there is potential value in a form of unforgeable
  465. token whose production rate is predictable and can't be influenced
  466. by corrupt parties. This would be more analogous to gold than to fiat
  467. currencies. Nick Szabo wrote many years ago about what he called "bit
  468. gold"[1] and this could be an implementation of that concept. There have
  469. also been proposals for building light-weight anonymous payment schemes on
  470. top of heavy-weight non-anonymous systems, so Bitcoin could be leveraged
  471. to allow for anonymity even beyond the mechanisms discussed in the paper.
  472.  
  473. Unfortunately I am having trouble fully understanding the system. The
  474. paper describes key concepts and some data structures, but does not
  475. clearly specify the various rules and verifications that the participants
  476. in the system would have to follow.
  477.  
  478. In particular I don't understand exactly what verifications P2P nodes
  479. perform when they receive new blocks from other nodes, and how they
  480. handle transactions that have been broadcast to them. For example, it
  481. is mentioned that if a broadcast transaction does not reach all nodes,
  482. it is OK, as it will get into the block chain before long. How does this
  483. happen - what if the node that creates the "next" block (the first node
  484. to find the hashcash collision) did not hear about the transaction,
  485. and then a few more blocks get added also by nodes that did not hear
  486. about that transaction? Do all the nodes that did hear it keep that
  487. transaction around, hoping to incorporate it into a block once they get
  488. lucky enough to be the one which finds the next collision?
  489.  
  490. Or for example, what if a node is keeping two or more chains around as
  491. it waits to see which grows fastest, and a block comes in for chain A
  492. which would include a double-spend of a coin that is in chain B? Is that
  493. checked for or not? (This might happen if someone double-spent and two
  494. different sets of nodes heard about the two different transactions with
  495. the same coin.)
  496.  
  497. This kind of data management, and the rules for handling all the packets
  498. that are flowing around is largely missing from the paper.
  499.  
  500. I also don't understand exactly how double-spending, or cancelling
  501. transactions, is accomplished by a superior attacker who is able to muster
  502. more computing power than all the honest participants. I see that he can
  503. create new blocks and add them to create the longest chain, but how can
  504. he erase or add old transactions in the chain? As the attacker sends out
  505. his new blocks, aren't there consistency checks which honest nodes can
  506. perform, to make sure that nothing got erased? More explanation of this
  507. attack would be helpful, in order to judge the gains to an attacker from
  508. this, versus simply using his computing power to mint new coins honestly.
  509.  
  510. As far as the spending transactions, what checks does the recipient of a
  511. coin have to perform? Does she need to go back through the coin's entire
  512. history of transfers, and make sure that every transaction on the list is
  513. indeed linked into the "timestamp" block chain? Or can she just do the
  514. latest one? Do the timestamp nodes check transactions, making sure that
  515. the previous transaction on a coin is in the chain, thereby enforcing
  516. the rule that all transactions in the chain represent valid coins?
  517.  
  518. Sorry about all the questions, but as I said this does seem to be a
  519. very promising and original idea, and I am looking forward to seeing
  520. how the concept is further developed. It would be helpful to see a more
  521. process oriented description of the idea, with concrete details of the
  522. data structures for the various objects (coins, blocks, transactions),
  523. the data which is included in messages, and algorithmic descriptions
  524. of the procedures for handling the various events which would occur in
  525. this system. You mentioned that you are working on an implementation,
  526. but I think a more formal, text description of the system would be a
  527. helpful next step.
  528.  
  529. Hal Finney
  530.  
  531. [1] http://unenumerated.blogspot.com/2005/12/bit-gold.html
  532.  
  533. ---------------------------------------------------------------------
  534. The Cryptography Mailing List
  535. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  536.  
  537. Ray Dillinger:
  538. > the "currency" is inflationary at about 35%
  539. > as that's how much faster computers get annually
  540. > ... the inflation rate of 35% is almost guaranteed
  541. > by the technology
  542.  
  543. Increasing hardware speed is handled: "To compensate for increasing hardware
  544. speed and varying interest in running nodes over time, the proof-of-work
  545. difficulty is determined by a moving average targeting an average number of
  546. blocks per hour. If they're generated too fast, the difficulty increases."
  547.  
  548. As computers get faster and the total computing power applied to creating
  549. bitcoins increases, the difficulty increases proportionally to keep the total
  550. new production constant. Thus, it is known in advance how many new bitcoins
  551. will be created every year in the future.
  552.  
  553. The fact that new coins are produced means the money supply increases by a
  554. planned amount, but this does not necessarily result in inflation. If the
  555. supply of money increases at the same rate that the number of people using it
  556. increases, prices remain stable. If it does not increase as fast as demand,
  557. there will be deflation and early holders of money will see its value increase.
  558.  
  559. Coins have to get initially distributed somehow, and a constant rate seems like
  560. the best formula.
  561.  
  562. Satoshi Nakamoto
  563.  
  564.  
  565. ---------------------------------------------------------------------
  566. The Cryptography Mailing List
  567. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  568.  
  569. James A. Donald Sun, 09 Nov 2008 11:16:50 -0800
  570.  
  571. Satoshi Nakamoto wrote:
  572. > Increasing hardware speed is handled: "To compensate
  573. > for increasing hardware speed and varying interest in
  574. > running nodes over time, the proof-of-work difficulty
  575. > is determined by a moving average targeting an average
  576. > number of blocks per hour. If they're generated too
  577. > fast, the difficulty increases."
  578.  
  579. This does not work - your proposal involves
  580. complications I do not think you have thought through.
  581.  
  582. Furthermore, it cannot be made to work, as in the
  583. proposed system the work of tracking who owns what coins
  584. is paid for by seigniorage, which requires inflation.
  585.  
  586. This is not an intolerable flaw - predictable inflation
  587. is less objectionable than inflation that gets jiggered
  588. around from time to time to transfer wealth from one
  589. voting block to another.
  590.  
  591. ---------------------------------------------------------------------
  592. The Cryptography Mailing List
  593. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  594.  
  595. Satoshi Nakamoto Sun, 09 Nov 2008 11:13:34 -0800
  596.  
  597. Hal Finney wrote:
  598. > it is mentioned that if a broadcast transaction does not reach all nodes,
  599. > it is OK, as it will get into the block chain before long. How does this
  600. > happen - what if the node that creates the "next" block (the first node
  601. > to find the hashcash collision) did not hear about the transaction,
  602. > and then a few more blocks get added also by nodes that did not hear
  603. > about that transaction? Do all the nodes that did hear it keep that
  604. > transaction around, hoping to incorporate it into a block once they get
  605. > lucky enough to be the one which finds the next collision?
  606.  
  607. Right, nodes keep transactions in their working set until they get into a
  608. block. If a transaction reaches 90% of nodes, then each time a new block is
  609. found, it has a 90% chance of being in it.
  610.  
  611.  
  612. > Or for example, what if a node is keeping two or more chains around as
  613. > it waits to see which grows fastest, and a block comes in for chain A
  614. > which would include a double-spend of a coin that is in chain B? Is that
  615. > checked for or not? (This might happen if someone double-spent and two
  616. > different sets of nodes heard about the two different transactions with
  617. > the same coin.)
  618.  
  619. That does not need to be checked for. The transaction in whichever branch ends
  620. up getting ahead becomes the valid one, the other is invalid. If someone tries
  621. to double spend like that, one and only one spend will always become valid, the
  622. others invalid.
  623.  
  624. Receivers of transactions will normally need to hold transactions for perhaps
  625. an hour or more to allow time for this kind of possibility to be resolved.
  626. They can still re-spend the coins immediately, but they should wait before
  627. taking an action such as shipping goods.
  628.  
  629.  
  630. > I also don't understand exactly how double-spending, or cancelling
  631. > transactions, is accomplished by a superior attacker who is able to muster
  632. > more computing power than all the honest participants. I see that he can
  633. > create new blocks and add them to create the longest chain, but how can
  634. > he erase or add old transactions in the chain? As the attacker sends out
  635. > his new blocks, aren't there consistency checks which honest nodes can
  636. > perform, to make sure that nothing got erased? More explanation of this
  637. > attack would be helpful, in order to judge the gains to an attacker from
  638. > this, versus simply using his computing power to mint new coins honestly.
  639.  
  640. The attacker isn't adding blocks to the end. He has to go back and redo the
  641. block his transaction is in and all the blocks after it, as well as any new
  642. blocks the network keeps adding to the end while he's doing that. He's
  643. rewriting history. Once his branch is longer, it becomes the new valid one.
  644.  
  645. This touches on a key point. Even though everyone present may see the
  646. shenanigans going on, there's no way to take advantage of that fact.
  647.  
  648. It is strictly necessary that the longest chain is always considered the valid
  649. one. Nodes that were present may remember that one branch was there first and
  650. got replaced by another, but there would be no way for them to convince those
  651. who were not present of this. We can't have subfactions of nodes that cling to
  652. one branch that they think was first, others that saw another branch first, and
  653. others that joined later and never saw what happened. The CPU power
  654. proof-of-work vote must have the final say. The only way for everyone to stay
  655. on the same page is to believe that the longest chain is always the valid one,
  656. no matter what.
  657.  
  658.  
  659. > As far as the spending transactions, what checks does the recipient of a
  660. > coin have to perform? Does she need to go back through the coin's entire
  661. > history of transfers, and make sure that every transaction on the list is
  662. > indeed linked into the "timestamp" block chain? Or can she just do the
  663. > latest one?
  664.  
  665. The recipient just needs to verify it back to a depth that is sufficiently far
  666. back in the block chain, which will often only require a depth of 2
  667. transactions. All transactions before that can be discarded.
  668.  
  669.  
  670. > Do the timestamp nodes check transactions, making sure that
  671. > the previous transaction on a coin is in the chain, thereby enforcing
  672. > the rule that all transactions in the chain represent valid coins?
  673.  
  674. Right, exactly. When a node receives a block, it checks the signatures of
  675. every transaction in it against previous transactions in blocks. Blocks can
  676. only contain transactions that depend on valid transactions in previous blocks
  677. or the same block. Transaction C could depend on transaction B in the same
  678. block and B depends on transaction A in an earlier block.
  679.  
  680.  
  681. > Sorry about all the questions, but as I said this does seem to be a
  682. > very promising and original idea, and I am looking forward to seeing
  683. > how the concept is further developed. It would be helpful to see a more
  684. > process oriented description of the idea, with concrete details of the
  685. > data structures for the various objects (coins, blocks, transactions),
  686. > the data which is included in messages, and algorithmic descriptions
  687. > of the procedures for handling the various events which would occur in
  688. > this system. You mentioned that you are working on an implementation,
  689. > but I think a more formal, text description of the system would be a
  690. > helpful next step.
  691.  
  692. I appreciate your questions. I actually did this kind of backwards. I had to
  693. write all the code before I could convince myself that I could solve every
  694. problem, then I wrote the paper. I think I will be able to release the code
  695. sooner than I could write a detailed spec. You're already right about most of
  696. your assumptions where you filled in the blanks.
  697.  
  698. Satoshi Nakamoto
  699.  
  700.  
  701. ---------------------------------------------------------------------
  702. The Cryptography Mailing List
  703. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  704.  
  705. Satoshi Nakamoto Sun, 09 Nov 2008 11:14:17 -0800
  706.  
  707. James A. Donald wrote:
  708. > The core concept is that lots of entities keep complete and consistent
  709. > information as to who owns which bitcoins.
  710. >
  711. > But maintaining consistency is tricky. It is not clear to me what
  712. > happens when someone reports one transaction to one maintainer, and
  713. > someone else transports another transaction to another maintainer. The
  714. > transaction cannot be known to be valid until it has been incorporated
  715. > into a globally shared view of all past transactions, and no one can
  716. > know that a globally shared view of all past transactions is globally
  717. > shared until after some time has passed, and after many new
  718. > transactions have arrived.
  719. >
  720. > Did you explain how to do this, and it just passed over my head, or
  721. > were you confident it could be done, and a bit vague as to the details?
  722.  
  723. The proof-of-work chain is the solution to the synchronisation problem, and to
  724. knowing what the globally shared view is without having to trust anyone.
  725.  
  726. A transaction will quickly propagate throughout the network, so if two versions
  727. of the same transaction were reported at close to the same time, the one with
  728. the head start would have a big advantage in reaching many more nodes first.
  729. Nodes will only accept the first one they see, refusing the second one to
  730. arrive, so the earlier transaction would have many more nodes working on
  731. incorporating it into the next proof-of-work. In effect, each node votes for
  732. its viewpoint of which transaction it saw first by including it in its
  733. proof-of-work effort.
  734.  
  735. If the transactions did come at exactly the same time and there was an even
  736. split, it's a toss up based on which gets into a proof-of-work first, and that
  737. decides which is valid.
  738.  
  739. When a node finds a proof-of-work, the new block is propagated throughout the
  740. network and everyone adds it to the chain and starts working on the next block
  741. after it. Any nodes that had the other transaction will stop trying to include
  742. it in a block, since it's now invalid according to the accepted chain.
  743.  
  744. The proof-of-work chain is itself self-evident proof that it came from the
  745. globally shared view. Only the majority of the network together has enough CPU
  746. power to generate such a difficult chain of proof-of-work. Any user, upon
  747. receiving the proof-of-work chain, can see what the majority of the network has
  748. approved. Once a transaction is hashed into a link that's a few links back in
  749. the chain, it is firmly etched into the global history.
  750.  
  751. Satoshi Nakamoto
  752.  
  753.  
  754. ---------------------------------------------------------------------
  755. The Cryptography Mailing List
  756. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  757.  
  758. James A. Donald Sun, 09 Nov 2008 11:15:38 -0800
  759.  
  760. --
  761. Satoshi Nakamoto wrote:
  762. > The proof-of-work chain is the solution to the
  763. > synchronisation problem, and to knowing what the
  764. > globally shared view is without having to trust
  765. > anyone.
  766. >
  767. > A transaction will quickly propagate throughout the
  768. > network, so if two versions of the same transaction
  769. > were reported at close to the same time, the one with
  770. > the head start would have a big advantage in reaching
  771. > many more nodes first. Nodes will only accept the
  772. > first one they see, refusing the second one to arrive,
  773. > so the earlier transaction would have many more nodes
  774. > working on incorporating it into the next
  775. > proof-of-work. In effect, each node votes for its
  776. > viewpoint of which transaction it saw first by
  777. > including it in its proof-of-work effort.
  778.  
  779. OK, suppose one node incorporates a bunch of
  780. transactions in its proof of work, all of them honest
  781. legitimate single spends and another node incorporates a
  782. slightly different bunch of transactions in its proof of
  783. work, all of them equally honest legitimate single
  784. spends, and both proofs are generated at about the same
  785. time.
  786.  
  787. What happens then?
  788.  
  789. ---------------------------------------------------------------------
  790. The Cryptography Mailing List
  791. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  792.  
  793. Satoshi Nakamoto Sun, 09 Nov 2008 11:17:24 -0800
  794.  
  795. James A. Donald wrote:
  796. >OK, suppose one node incorporates a bunch of
  797. >transactions in its proof of work, all of them honest
  798. >legitimate single spends and another node incorporates a
  799. >different bunch of transactions in its proof of
  800. >work, all of them equally honest legitimate single
  801. >spends, and both proofs are generated at about the same
  802. >time.
  803. >
  804. >What happens then?
  805.  
  806. They both broadcast their blocks. All nodes receive them and keep both, but
  807. only work on the one they received first. We'll suppose exactly half received
  808. one first, half the other.
  809.  
  810. In a short time, all the transactions will finish propagating so that everyone
  811. has the full set. The nodes working on each side will be trying to add the
  812. transactions that are missing from their side. When the next proof-of-work is
  813. found, whichever previous block that node was working on, that branch becomes
  814. longer and the tie is broken. Whichever side it is, the new block will contain
  815. the other half of the transactions, so in either case, the branch will contain
  816. all transactions. Even in the unlikely event that a split happened twice in a
  817. row, both sides of the second split would contain the full set of transactions
  818. anyway.
  819.  
  820. It's not a problem if transactions have to wait one or a few extra cycles to
  821. get into a block.
  822.  
  823. Satoshi Nakamoto
  824.  
  825.  
  826.  
  827. ---------------------------------------------------------------------
  828. The Cryptography Mailing List
  829. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  830.  
  831. James A. Donald Mon, 10 Nov 2008 11:08:43 -0800
  832.  
  833. --
  834. > James A. Donald wrote:
  835. >> OK, suppose one node incorporates a bunch of
  836. >> transactions in its proof of work, all of them honest
  837. >> legitimate single spends and another node
  838. >> incorporates a different bunch of transactions in its
  839. >> proof of work, all of them equally honest legitimate
  840. >> single spends, and both proofs are generated at about
  841. >> the same time.
  842. >>
  843. >> What happens then?
  844.  
  845. Satoshi Nakamoto wrote:
  846. > They both broadcast their blocks. All nodes receive
  847. > them and keep both, but only work on the one they
  848. > received first. We'll suppose exactly half received
  849. > one first, half the other.
  850. >
  851. > In a short time, all the transactions will finish
  852. > propagating so that everyone has the full set. The
  853. > nodes working on each side will be trying to add the
  854. > transactions that are missing from their side. When
  855. > the next proof-of-work is found, whichever previous
  856. > block that node was working on, that branch becomes
  857. > longer and the tie is broken. Whichever side it is,
  858. > the new block will contain the other half of the
  859. > transactions, so in either case, the branch will
  860. > contain all transactions. Even in the unlikely event
  861. > that a split happened twice in a row, both sides of
  862. > the second split would contain the full set of
  863. > transactions anyway.
  864. >
  865. > It's not a problem if transactions have to wait one or
  866. > a few extra cycles to get into a block.
  867.  
  868. So what happened to the coin that lost the race?
  869.  
  870. On the one hand, we want people who make coins to be
  871. motivated to keep and record all transactions, and
  872. obtain an up to date record of all transactions in a
  873. timely manner. On the other hand, it is a bit harsh if
  874. the guy who came second is likely to lose his coin.
  875.  
  876. Further, your description of events implies restrictions
  877. on timing and coin generation - that the entire network
  878. generates coins slowly compared to the time required for
  879. news of a new coin to flood the network, otherwise the
  880. chains diverge more and more, and no one ever knows
  881. which chain is the winner.
  882.  
  883. You need to make these restrictions explicit, for
  884. network flood time may well be quite slow.
  885.  
  886. Which implies that the new coin rate is slower.
  887.  
  888. We want spenders to have certainty that their
  889. transaction is valid at the time it takes a spend to
  890. flood the network, not at the time it takes for branch
  891. races to be resolved.
  892.  
  893. At any given time, for example at 1 040 689 138 seconds
  894. we can look back at the past and say:
  895.  
  896. At 1 040 688 737 seconds, node 5 was *it*, and
  897. he incorporated all the coins he had discovered
  898. into the chain, and all the new transactions he
  899. knew about on top of the previous link
  900.  
  901. At 1 040 688 792 seconds, node 2 was *it*, and
  902. he incorporated all the coins he had discovered
  903. into the chain, and all the new transactions he
  904. knew about into the chain on top of node 5's
  905. link.
  906.  
  907. At 1 040 688 745 seconds, node 7 was *it*, and
  908. he incorporated all the coins he had discovered
  909. into the chain, and all the new transactions he
  910. knew about into the chain on top of node 2's
  911. link.
  912.  
  913. But no one can know who is *it* right now
  914.  
  915. So how does one know when to reveal one's coins? One
  916. solution is that one does not. One incorporates a hash
  917. of the coin secret whenever one thinks one might be
  918. *it*, and after that hash is securely in the chain,
  919. after one knows that one was *it* at the time, one can
  920. then safely spend the coin that one has found, revealing
  921. the secret.
  922.  
  923. This solution takes care of the coin revelation problem,
  924. but does not solve the spend recording problem. If one
  925. node is ignoring all spends that it does not care about,
  926. it suffers no adverse consequences. We need a protocol
  927. in which your prospects of becoming *it* also depend on
  928. being seen by other nodes as having a reasonably up to
  929. date and complete list of spends - which this protocol
  930. is not, and your protocol is not either.
  931.  
  932. ---------------------------------------------------------------------
  933. The Cryptography Mailing List
  934. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  935.  
  936. Satoshi Nakamoto Mon, 10 Nov 2008 11:09:26 -0800
  937.  
  938. James A. Donald wrote:
  939. > Furthermore, it cannot be made to work, as in the
  940. > proposed system the work of tracking who owns what coins
  941. > is paid for by seigniorage, which requires inflation.
  942.  
  943. If you're having trouble with the inflation issue, it's easy to tweak it for
  944. transaction fees instead. It's as simple as this: let the output value from
  945. any transaction be 1 cent less than the input value. Either the client
  946. software automatically writes transactions for 1 cent more than the intended
  947. payment value, or it could come out of the payee's side. The incentive value
  948. when a node finds a proof-of-work for a block could be the total of the fees in
  949. the block.
  950.  
  951. Satoshi Nakamoto
  952.  
  953.  
  954. ---------------------------------------------------------------------
  955. The Cryptography Mailing List
  956. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  957.  
  958. Satoshi Nakamoto Tue, 11 Nov 2008 06:30:22 -0800
  959.  
  960. James A. Donald wrote:
  961. > So what happened to the coin that lost the race?
  962. >
  963. > ... it is a bit harsh if the guy who came second
  964. > is likely to lose his coin.
  965.  
  966. When there are multiple double-spent versions of the same transaction, one and
  967. only one will become valid.
  968.  
  969. The receiver of a payment must wait an hour or so before believing that it's
  970. valid. The network will resolve any possible double-spend races by then.
  971.  
  972. The guy who received the double-spend that became invalid never thought he had
  973. it in the first place. His software would have shown the transaction go from
  974. "unconfirmed" to "invalid". If necessary, the UI can be made to hide
  975. transactions until they're sufficiently deep in the block chain.
  976.  
  977.  
  978. > Further, your description of events implies restrictions
  979. > on timing and coin generation - that the entire network
  980. > generates coins slowly compared to the time required for
  981. > news of a new coin to flood the network
  982.  
  983. Sorry if I didn't make that clear. The target time between blocks will
  984. probably be 10 minutes.
  985.  
  986. Every block includes its creation time. If the time is off by more than 36
  987. hours, other nodes won't work on it. If the timespan over the last 6*24*30
  988. blocks is less than 15 days, blocks are being generated too fast and the
  989. proof-of-work difficulty doubles. Everyone does the same calculation with the
  990. same chain data, so they all get the same result at the same link in the chain.
  991.  
  992.  
  993. > We want spenders to have certainty that their
  994. > transaction is valid at the time it takes a spend to
  995. > flood the network, not at the time it takes for branch
  996. > races to be resolved.
  997.  
  998. Instantant non-repudiability is not a feature, but it's still much faster than
  999. existing systems. Paper cheques can bounce up to a week or two later. Credit
  1000. card transactions can be contested up to 60 to 180 days later. Bitcoin
  1001. transactions can be sufficiently irreversible in an hour or two.
  1002.  
  1003.  
  1004. > If one node is ignoring all spends that it does not
  1005. > care about, it suffers no adverse consequences.
  1006.  
  1007. With the transaction fee based incentive system I recently posted, nodes would
  1008. have an incentive to include all the paying transactions they receive.
  1009.  
  1010. Satoshi Nakamoto
  1011.  
  1012. ---------------------------------------------------------------------
  1013. The Cryptography Mailing List
  1014. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  1015.  
  1016. James A. Donald Thu, 13 Nov 2008 07:13:21 -0800
  1017.  
  1018. Satoshi Nakamoto wrote:
  1019. > When there are multiple double-spent versions of the
  1020. > same transaction, one and only one will become valid.
  1021.  
  1022. That is not the question I am asking.
  1023.  
  1024. It is not trust that worries me, it is how it is
  1025. possible to have a a globally shared view even if
  1026. everyone is well behaved.
  1027.  
  1028. The process for arriving at a globally shared view of
  1029. who owns what bitgold coins is insufficiently specified.
  1030. Once specified, then we can start considering whether
  1031. everyone has incentives to behave correctly.
  1032.  
  1033. It is not sufficient that everyone knows X. We also
  1034. need everyone to know that everyone knows X, and that
  1035. everyone knows that everyone knows that everyone knows X
  1036. - which, as in the Byzantine Generals problem, is the
  1037. classic hard problem of distributed data processing.
  1038.  
  1039. This problem becomes harder when X is quite possibly a
  1040. very large amount of data - agreement on who was the
  1041. owner of every bitgold coin at such and such a time.
  1042.  
  1043. And then on top of that we need everyone to have a
  1044. motive to behave in such a fashion that agreement
  1045. arises. I cannot see that they have motive when I do
  1046. not know the behavior to be motivated.
  1047.  
  1048. You keep repeating your analysis of the system under
  1049. attack. We cannot say how the system will behave under
  1050. attack until we know how the system is supposed to
  1051. behave when not under attack.
  1052.  
  1053. If there are a lot of transactions, it is hard to
  1054. efficiently discover the discrepancies between one
  1055. node's view and another node's view, and because new
  1056. transactions are always arriving, no two nodes will ever
  1057. have the same view, even if all nodes are honest, and
  1058. all reported transactions are correct and true single
  1059. spends.
  1060.  
  1061. We should be able to accomplish a system where two nodes
  1062. are likely to come to agreement as to who owned what
  1063. bitgold coins at some very recent past time, but it is
  1064. not simple to do so.
  1065.  
  1066. If one node constructs a hash that represents its
  1067. knowledge of who owned what bitgold coins at a
  1068. particular time, and another node wants to check that
  1069. hash, it is not simple to do it in such a way that
  1070. agreement is likely, and disagreement between honest
  1071. well behaved nodes is efficiently detected and
  1072. efficiently resolved.
  1073.  
  1074. And if we had a specification of how agreement is
  1075. generated, it is not obvious why the second node has
  1076. incentive to check that hash.
  1077.  
  1078. The system has to work in such a way that nodes can
  1079. easily and cheaply change their opinion about recent
  1080. transactions, so as to reach consensus, but in order to
  1081. provide finality and irreversibility, once consensus has
  1082. been reached, and then new stuff has be piled on top of
  1083. old consensus, in particular new bitgold has been piled
  1084. on top of old consensus, it then becomes extremely
  1085. difficult to go back and change what was decided.
  1086.  
  1087. Saying that is how it works, does not give us a method
  1088. to make it work that way.
  1089.  
  1090. > The receiver of a payment must wait an hour or so
  1091. > before believing that it's valid. The network will
  1092. > resolve any possible double-spend races by then.
  1093.  
  1094. You keep discussing attacks. I find it hard to think
  1095. about response to attack when it is not clear to me what
  1096. normal behavior is in the case of good conduct by each
  1097. and every party.
  1098.  
  1099. Distributed databases are *hard* even when all the
  1100. databases perfectly follow the will of a single owner.
  1101. Messages get lost, links drop, syncrhonization delays
  1102. become abnormal, and entire machines go up in flames,
  1103. and the network as a whole has to take all this in its
  1104. stride.
  1105.  
  1106. Figuring out how to do this is hard, even in the
  1107. complete absence of attacks. Then when we have figured
  1108. out how to handle all this, then come attacks.
  1109.  
  1110. ---------------------------------------------------------------------
  1111. The Cryptography Mailing List
  1112. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  1113.  
  1114. "Hal Finney" Thu, 13 Nov 2008 13:05:36 -0800
  1115.  
  1116. James A. Donald writes:
  1117. > Satoshi Nakamoto wrote:
  1118. > > When there are multiple double-spent versions of the
  1119. > > same transaction, one and only one will become valid.
  1120. >
  1121. > That is not the question I am asking.
  1122. >
  1123. > It is not trust that worries me, it is how it is
  1124. > possible to have a a globally shared view even if
  1125. > everyone is well behaved.
  1126. >
  1127. > The process for arriving at a globally shared view of
  1128. > who owns what bitgold coins is insufficiently specified.
  1129.  
  1130. I agree that the description is not completely clear on how these matters
  1131. are handled. Satoshi has suggested that releasing source code may be the
  1132. best way to clarify the design. As I have tried to work through details on
  1133. my own, it does appear that the rules become rather complicated and indeed
  1134. one needs at least a pseudo-code algorithm to specify the behavior. So
  1135. perhaps writing real code is not a bad way to go. I found that there is
  1136. a sourceforge project set up for bitgold, although it does not have any
  1137. code yet.
  1138.  
  1139. In answer to James' specific question, about what happens when different
  1140. nodes see different sets of transactions, due to imperfect broadcast, here
  1141. is how I understand it. Each node must be prepared to maintain potentially
  1142. several "candidate" block chains, each of which may eventually turn out
  1143. to become the longest one, the one which wins. Once a given block chain
  1144. becomes sufficiently longer than a competitor, the shorter one can be
  1145. deleted. This length differential is a parameter which depends on the
  1146. node's threat model for how much compute power an attacker can marshall,
  1147. in terms of the fraction of the "honst" P2P network's work capacity,
  1148. and is estimated in the paper. The idea is that once a chain gets far
  1149. enough behind the longest one, there is essentially no chance that it
  1150. can ever catch up.
  1151.  
  1152. In order to resolve the issue James raised, I think it is necessary
  1153. that nodes keep a separate pending-transaction list associated with
  1154. each candidate chain. This list would include all transactions the node
  1155. has received (via broadcast by the transactees) but which have not yet
  1156. been incorporated into that block chain. At any given time, the node is
  1157. working to extend the longest block chain, and the block it is working
  1158. to find a hash collision for will include all of the pending transactions
  1159. associated with that chain.
  1160.  
  1161. I think that this way, when a candidate chain is deleted because it
  1162. got too much shorter than the longest one, transactions in it are
  1163. not lost, but have continued to be present in the pending-transaction
  1164. list associated with the longest chain, in those nodes which heard the
  1165. original transaction broadcast. (I have also considered whether nodes
  1166. should add transactions to their pending-transaction list that they
  1167. learn about through blocks from other nodes, even if those blocks do
  1168. not end up making their way into the longest block chain; but I'm not
  1169. sure if that is necessary or helpful.)
  1170.  
  1171. Once these rules are clarified, more formal modeling will be helpful in
  1172. understanding the behavior of the network given imperfect reliability. For
  1173. example, if on average a fraction f of P2P nodes receive a given
  1174. transaction broadcast, then I think one would expect 1/f block-creation
  1175. times to elapse before the transaction appears in what is destined to
  1176. become the longest chain. One might also ask, given that the P2P network
  1177. broadcast is itself imperfectly reliable, how many candidate chains
  1178. must a given node keep track of at one time, on average? Or as James
  1179. raised earlier, if the network broadcast is reliable but depends on a
  1180. potentially slow flooding algorithm, how does that impact performance?
  1181.  
  1182. > And then on top of that we need everyone to have a
  1183. > motive to behave in such a fashion that agreement
  1184. > arises. I cannot see that they have motive when I do
  1185. > not know the behavior to be motivated.
  1186.  
  1187. I am somewhat less worried about motivation. I'd be satisfied if the
  1188. system can meet the following criteria:
  1189.  
  1190. 1. No single node operator, or small collection of node operators
  1191. which controls only a small fraction of overall network resources,
  1192. can effectively cheat, if other players are honest.
  1193.  
  1194. 2. The long tail of node operators is sufficiently large that no small
  1195. collection of nodes can control more than a small fraction of overall
  1196. resources. (Here, the "tail" refers to a ranking based on amount of
  1197. resources controlled by each operator.)
  1198.  
  1199. 3. The bitcoin system turns out to be socially useful and valuable, so
  1200. that node operators feel that they are making a beneficial contribution
  1201. to the world by their efforts (similar to the various "@Home" compute
  1202. projects where people volunteer their compute resources for good causes).
  1203.  
  1204. In this case it seems to me that simple altruism can suffice to keep the
  1205. network running properly.
  1206.  
  1207. > Distributed databases are *hard* even when all the
  1208. > databases perfectly follow the will of a single owner.
  1209. > Messages get lost, links drop, syncrhonization delays
  1210. > become abnormal, and entire machines go up in flames,
  1211. > and the network as a whole has to take all this in its
  1212. > stride.
  1213.  
  1214. A very good point, and a more complete specification is necessary in order
  1215. to understand how the network will respond to imperfections like this. I
  1216. am looking forward to seeing more detail emerge.
  1217.  
  1218. One thing I might mention is that in many ways bitcoin is two independent
  1219. ideas: a way of solving the kinds of problems James lists here, of
  1220. creating a globally consistent but decentralized database; and then using
  1221. it for a system similar to Wei Dai's b-money (which is referenced in the
  1222. paper) but transaction/coin based rather than account based. Solving the
  1223. global, massively decentralized database problem is arguably the harder
  1224. part, as James emphasizes. The use of proof-of-work as a tool for this
  1225. purpose is a novel idea well worth further review IMO.
  1226.  
  1227. Hal Finney
  1228.  
  1229. ---------------------------------------------------------------------
  1230. The Cryptography Mailing List
  1231. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  1232.  
  1233. Satoshi Nakamoto Thu, 13 Nov 2008 19:34:25 -0800
  1234.  
  1235. James A. Donald wrote:
  1236. > It is not sufficient that everyone knows X. We also
  1237. > need everyone to know that everyone knows X, and that
  1238. > everyone knows that everyone knows that everyone knows X
  1239. > - which, as in the Byzantine Generals problem, is the
  1240. > classic hard problem of distributed data processing.
  1241.  
  1242. The proof-of-work chain is a solution to the Byzantine Generals' Problem. I'll
  1243. try to rephrase it in that context.
  1244.  
  1245. A number of Byzantine Generals each have a computer and want to attack the
  1246. King's wi-fi by brute forcing the password, which they've learned is a certain
  1247. number of characters in length. Once they stimulate the network to generate a
  1248. packet, they must crack the password within a limited time to break in and
  1249. erase the logs, otherwise they will be discovered and get in trouble. They
  1250. only have enough CPU power to crack it fast enough if a majority of them attack
  1251. at the same time.
  1252.  
  1253. They don't particularly care when the attack will be, just that they all agree.
  1254. It has been decided that anyone who feels like it will announce a time, and
  1255. whatever time is heard first will be the official attack time. The problem is
  1256. that the network is not instantaneous, and if two generals announce different
  1257. attack times at close to the same time, some may hear one first and others hear
  1258. the other first.
  1259.  
  1260. They use a proof-of-work chain to solve the problem. Once each general
  1261. receives whatever attack time he hears first, he sets his computer to solve an
  1262. extremely difficult proof-of-work problem that includes the attack time in its
  1263. hash. The proof-of-work is so difficult, it's expected to take 10 minutes of
  1264. them all working at once before one of them finds a solution. Once one of the
  1265. generals finds a proof-of-work, he broadcasts it to the network, and everyone
  1266. changes their current proof-of-work computation to include that proof-of-work
  1267. in the hash they're working on. If anyone was working on a different attack
  1268. time, they switch to this one, because its proof-of-work chain is now longer.
  1269.  
  1270. After two hours, one attack time should be hashed by a chain of 12
  1271. proofs-of-work. Every general, just by verifying the difficulty of the
  1272. proof-of-work chain, can estimate how much parallel CPU power per hour was
  1273. expended on it and see that it must have required the majority of the computers
  1274. to produce that much proof-of-work in the allotted time. They had to all have
  1275. seen it because the proof-of-work is proof that they worked on it. If the CPU
  1276. power exhibited by the proof-of-work chain is sufficient to crack the password,
  1277. they can safely attack at the agreed time.
  1278.  
  1279. The proof-of-work chain is how all the synchronisation, distributed database
  1280. and global view problems you've asked about are solved.
  1281.  
  1282.  
  1283. ---------------------------------------------------------------------
  1284. The Cryptography Mailing List
  1285. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  1286.  
  1287. Ray Dillinger Mon, 17 Nov 2008 09:04:04 -0800
  1288.  
  1289. Okay.... I'm going to summarize this protocol as I understand it.
  1290.  
  1291. I'm filling in some operational details that aren't in the paper
  1292. by supplementing what you wrote with what my own "design sense"
  1293. tells me are critical missing bits or "obvious" methodologies for
  1294. use.
  1295.  
  1296. First, people spend computer power creating a pool of coins to use
  1297. as money. Each coin is a proof-of-work meeting whatever criteria
  1298. were in effect for money at the time it was created. The time of
  1299. creation (and therefore the criteria) is checkable later because
  1300. people can see the emergence of this particular coin in the
  1301. transaction chain and track it through all its "consensus view"
  1302. spends. (more later on coin creation tied to adding a link).
  1303.  
  1304. When a coin is spent, the buyer and seller digitally sign a (blinded)
  1305. transaction record, and broadcast it to a bunch of nodes whose purpose
  1306. is keeping track of consensus regarding coin ownership. If someone
  1307. double spends, then the transaction record can be unblinded revealing
  1308. the identity of the cheater. This is done via a fairly standard cut-
  1309. and-choose algorithm where the buyer responds to several challenges
  1310. with secret shares, and the seller then asks him to "unblind" and
  1311. checks all but one, verifying that they do contain secret shares any
  1312. two of which are sufficient to identify the buyer. In this case the
  1313. seller accepts the unblinded spend record as "probably" containing
  1314. a valid secret share.
  1315.  
  1316. The nodes keeping track of consensus regarding coin ownership are in
  1317. a loop where they are all trying to "add a link" to the longest chain
  1318. they've so far recieved. They have a pool of reported transactions
  1319. which they've not yet seen in a "consensus" signed chain. I'm going
  1320. to call this pool "A". They attempt to add a link to the chain by
  1321. moving everything from pool A into a pool "L" and using a CPU-
  1322. intensive digital signature algorithm to sign the chain including
  1323. the new block L. This results in a chain extended by a block
  1324. containing all the transaction records they had in pool L, plus
  1325. the node's digital signature. While they do this, new
  1326. transaction records continue to arrive and go into pool A again
  1327. for the next cycle of work.
  1328.  
  1329. They may also recieve chains as long as the one they're trying to
  1330. extend while they work, in which the last few "links" are links
  1331. that are *not* in common with the chain on which they're working.
  1332. These they ignore. (? Do they ignore them? Under what
  1333. circumstances would these become necessary to ever look at again,
  1334. bearing in mind that any longer chain based on them will include
  1335. them?)
  1336.  
  1337. But if they recieve a _longer_ chain while working, they
  1338. immediately check all the transactions in the new links to make
  1339. sure it contains no double spends and that the "work factors" of
  1340. all new links are appropriate. If it contains a double spend,
  1341. then they create a "transaction" which is a proof of double
  1342. spending, add it to their pool A, broadcast it, and continue work.
  1343. If one of the "new" links has an inappropriate work factor (ie,
  1344. someone didn't put enough CPU into it for it to be "licit"
  1345. according to the rules) a new "transaction" which is a proof
  1346. of the protocol violation by the link-creating node is created,
  1347. broadcast, and added to pool A, and the chain is rejected. In
  1348. the case of no double spends and appropriate work factors for
  1349. all links not yet seen, they accept the new chain as consensus.
  1350.  
  1351. If the new chain is accepted, then they give up on adding their
  1352. current link, dump all the transactions from pool L back into pool
  1353. A (along with transactions they've recieved or created since
  1354. starting work), eliminate from pool A those transaction records
  1355. which are already part of a link in the new chain, and start work
  1356. again trying to extend the new chain.
  1357.  
  1358. If they complete work on a chain extended with their new link, they
  1359. broadcast it and immediately start work on another new link with
  1360. all the transactions that have accumulated in pool A since they
  1361. began work.
  1362.  
  1363. Do I understand it correctly?
  1364.  
  1365.  
  1366.  
  1367.  
  1368. Biggest Technical Problem:
  1369.  
  1370. Is there a mechanism to make sure that the "chain" does not consist
  1371. solely of links added by just the 3 or 4 fastest nodes? 'Cause a
  1372. broadcast transaction record could easily miss those 3 or 4 nodes
  1373. and if it does, and those nodes continue to dominate the chain, the
  1374. transaction might never get added.
  1375.  
  1376. To remedy this, you need to either ensure provable propagation of
  1377. transactions, or vary the work factor for a node depending on how
  1378. many links have been added since that node's most recent link.
  1379.  
  1380. Unfortunately, both measures can be defeated by sock puppets.
  1381. This is probably the worst problem with your protocol as it
  1382. stands right now; you need some central point to control the
  1383. identities (keys) of the nodes and prevent people from making
  1384. new sock puppets.
  1385.  
  1386. Provable propagation would mean that When Bob accepts a new chain
  1387. from Alice, he needs to make sure that Alice has (or gets) all
  1388. transactions in his "A" and "L" pools. He sends them, and
  1389. Alice sends back a signed hash to prove she got them. Once
  1390. Alice has recieved this block of transactions, if any subsequent
  1391. chains including a link added by Alice do not include those
  1392. transactions at or before that link, then Bob should be able to
  1393. publish the block he sent Alice, along with her signature, in a
  1394. transaction as proof that Alice violated protocol. Sock puppets
  1395. defeat this because Alice just signs subsequent chains using a
  1396. new key, pretending to be a different node.
  1397.  
  1398. If we go with varying the work factor depending on how many new
  1399. links there are, then we're right back to domination by the 3
  1400. or 4 fastest nodes, except now they're joined by 600 or so
  1401. sock puppets which they use to avoid the work factor penalty.
  1402.  
  1403. If we solve the sock-puppet issue, or accept that there's a central
  1404. point controlling the generation of new keys, then generation of
  1405. coins should be tied to the act of successfully adding a block to
  1406. the "consensus" chain. This is simple to do; creation of a coin
  1407. is a transaction, it gets added along with all the other transactions
  1408. in the block. But you can only create one coin per link, and of
  1409. course if your version of the chain isn't the one that gets accepted,
  1410. then in the "accepted" view you don't have the coin and can't spend
  1411. it. This gives the people maintaining the consensus database a
  1412. reason to spend CPU cycles, especially since the variance in work
  1413. factor by number of links added since their own last link (outlined
  1414. above) guarantees that everyone, not just the 3 or 4 fastest nodes,
  1415. occasionally gets the opportunity to create a coin.
  1416.  
  1417. Also, the work requirement for adding a link to the chain should
  1418. vary (again exponentially) with the number of links added to that
  1419. chain in the previous week, causing the rate of coin generation
  1420. (and therefore inflation) to be strictly controlled.
  1421.  
  1422. You need coin aggregation for this to scale. There needs to be
  1423. a "provable" transaction where someone retires ten single coins
  1424. and creates a new coin with denomination ten, etc. This is not
  1425. too hard, using the same infrastructure you've already got; it
  1426. simply becomes part of the chain, and when the chain is accepted
  1427. consensus, then everybody can see that it happened.
  1428.  
  1429.  
  1430.  
  1431. Bear
  1432.  
  1433.  
  1434.  
  1435. ---------------------------------------------------------------------
  1436. The Cryptography Mailing List
  1437. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  1438.  
  1439. James A. Donald Tue, 18 Nov 2008 14:52:26 -0800
  1440.  
  1441. Ray Dillinger wrote:
  1442. > Okay.... I'm going to summarize this protocol as I
  1443. > understand it.
  1444. >
  1445. > I'm filling in some operational details that aren't in
  1446. > the paper by supplementing what you wrote with what my
  1447. > own "design sense" tells me are critical missing bits
  1448. > or "obvious" methodologies for use.
  1449.  
  1450. There are a number of significantly different ways this
  1451. could be implemented. I have been working on my own
  1452. version based on Patricia hash trees, (not yet ready to
  1453. post, will post in a week or so) with the consensus
  1454. generation being a generalization of file sharing using
  1455. Merkle hash trees. Patricia hash trees where the high
  1456. order part of the Patricia key represents the high order
  1457. part of the time can be used to share data that evolves
  1458. in time. The algorithm, if implemented by honest
  1459. correctly functioning peers, regularly generates
  1460. consensus hashes of the recent past - thereby addressing
  1461. the problem I have been complaining about - that we have
  1462. a mechanism to protect against consensus distortion by
  1463. dishonest or malfunctioning peers, which is useless
  1464. absent a definition of consensus generation by honest
  1465. and correctly functioning peers.
  1466.  
  1467. > First, people spend computer power creating a pool of
  1468. > coins to use as money. Each coin is a proof-of-work
  1469. > meeting whatever criteria were in effect for money at
  1470. > the time it was created. The time of creation (and
  1471. > therefore the criteria) is checkable later because
  1472. > people can see the emergence of this particular coin
  1473. > in the transaction chain and track it through all its
  1474. > "consensus view" spends. (more later on coin creation
  1475. > tied to adding a link).
  1476. >
  1477. > When a coin is spent, the buyer and seller digitally
  1478. > sign a (blinded) transaction record, and broadcast it
  1479. > to a bunch of nodes whose purpose is keeping track of
  1480. > consensus regarding coin ownership.
  1481.  
  1482. I don't think your blinding works.
  1483.  
  1484. If there is a public record of who owns what coin, we
  1485. have to generate a public diff on changes in that
  1486. record, so the record will show that a coin belonged to
  1487. X, and soon thereafter belonged to Y. I don't think
  1488. blinding can be made to work. We can blind the
  1489. transaction details easily enough, by only making hashes
  1490. of the details public, (X paid Y for
  1491. 49vR7xmwYcKXt9zwPJ943h9bHKC2pG68m) but that X paid Y is
  1492. going to be fairly obvious.
  1493.  
  1494. If when Joe spends a coin to me, then I have to have the
  1495. ability to ask "Does Joe rightfully own this coin", then
  1496. it is difficult to see how this can be implemented in a
  1497. distributed protocol without giving people the ability
  1498. to trawl through data detecting that Joe paid me.
  1499.  
  1500. To maintain a consensus on who owns what coins, who owns
  1501. what coins has to be public.
  1502.  
  1503. We can build a privacy layer on top of this - account
  1504. money and chaumian money based on bitgold coins, much as
  1505. the pre 1915 US banking system layered account money and
  1506. bank notes on top of gold coins, and indeed we have to
  1507. build a layer on top to bring the transaction cost down
  1508. to the level that supports agents performing micro
  1509. transactions, as needed for bandwidth control, file
  1510. sharing, and charging non white listed people to send us
  1511. communications.
  1512.  
  1513. So the entities on the public record are entities
  1514. functioning like pre 1915 banks - let us call them
  1515. binks, for post 1934 banks no longer function like that.
  1516.  
  1517. > But if they recieve a _longer_ chain while working,
  1518. > they immediately check all the transactions in the new
  1519. > links to make sure it contains no double spends and
  1520. > that the "work factors" of all new links are
  1521. > appropriate.
  1522.  
  1523. I am troubled that this involves frequent
  1524. retransmissions of data that is already mostly known.
  1525. Consensus and widely distributed beliefs about bitgold
  1526. ownership already involves significant cost. Further,
  1527. each transmission of data is subject to data loss, which
  1528. can result in thrashing, with the risk that the
  1529. generation of consensus may slow below the rate of new
  1530. transactions. We already have problems getting the cost
  1531. down to levels that support micro transactions by
  1532. software agents, which is the big unserved market -
  1533. bandwidth control, file sharing, and charging non white
  1534. listed people to send us communications.
  1535.  
  1536. To work as useful project, has to be as efficient as it
  1537. can be - hence my plan to use a Patricia hash tree
  1538. because it identifies and locate small discrepancies
  1539. between peers that are mostly in agreement already,
  1540. without them needing to transmit their complete data.
  1541.  
  1542. We also want to avoid very long hash chains that have to
  1543. be frequently checked in order to validate things. Any
  1544. time a hash chain can potentially become enormously long
  1545. over time, we need to ensure that no one ever has to
  1546. rewalk the full length. Chains that need to be
  1547. re-walked can only be permitted to grow as the log of
  1548. the total number of transactions - if they grow as the
  1549. log of the transactions in any one time period plus the
  1550. total number of time periods, we have a problem.
  1551.  
  1552. > Biggest Technical Problem:
  1553. >
  1554. > Is there a mechanism to make sure that the "chain"
  1555. > does not consist solely of links added by just the 3
  1556. > or 4 fastest nodes? 'Cause a broadcast transaction
  1557. > record could easily miss those 3 or 4 nodes and if it
  1558. > does, and those nodes continue to dominate the chain,
  1559. > the transaction might never get added.
  1560. >
  1561. > To remedy this, you need to either ensure provable
  1562. > propagation of transactions, or vary the work factor
  1563. > for a node depending on how many links have been added
  1564. > since that node's most recent link.
  1565. >
  1566. > Unfortunately, both measures can be defeated by sock
  1567. > puppets. This is probably the worst problem with your
  1568. > protocol as it stands right now; you need some central
  1569. > point to control the identities (keys) of the nodes
  1570. > and prevent people from making new sock puppets.
  1571.  
  1572. We need a protocol wherein to be a money tracking peer
  1573. (an entity that validates spends) you have to be
  1574. accepted by at least two existing peers who agree to
  1575. synchronize data with you - presumably through human
  1576. intervention by the owners of existing peers, and these
  1577. two human approved synchronization paths indirectly
  1578. connect you to the other peers in the network through
  1579. at least one graph cycle.
  1580.  
  1581. If peer X is only connected to the rest of the network
  1582. by one existing peer, peer Y, perhaps because X's
  1583. directly connecting peer has dropped out, then X is
  1584. demoted to a client, not a peer - any transactions X
  1585. submits are relabeled by Y as submitted to Y, not X, and
  1586. the time of submission (which forms part of the Patricia
  1587. key) is the time X submitted them to Y, not the time
  1588. they were submitted to X.
  1589.  
  1590. The algorithm must be able swiftly detect malfunctioning
  1591. peers, and automatically exclude them from the consensus
  1592. temporarily - which means that transactions submitted
  1593. through malfunctioning peers do not get included in the
  1594. consensus, therefore have to be resubmitted, and peers
  1595. may find themselves temporarily demoted to clients,
  1596. because one of the peers through which they were
  1597. formerly connected to the network has been dropped by
  1598. the consensus.
  1599.  
  1600. If a peer gets a lot of automatic temporary exclusions,
  1601. there may be human intervention by the owners of those
  1602. peers to which it exchanges data directly to permanently
  1603. drop them.
  1604.  
  1605. Since peers get accepted by human invite, they have
  1606. reputation to lose, therefore we can make the null
  1607. hypothesis (the primary Bayesian prior) honest intent,
  1608. valid data, but unreliable data transmission - trust
  1609. with infrequent random verification. Designing the
  1610. system on this basis considerably reduces processing
  1611. costs.
  1612.  
  1613. Recall that SET died on its ass in large part because
  1614. every transaction involved innumerable public key
  1615. operations. Similarly, we have huge security flaws in
  1616. https because it has so many redundant public key
  1617. operations that web site designers try to minimize the
  1618. use of https to cover only those areas that truly need
  1619. it - and they always get the decision as to what truly
  1620. needs it subtly wrong.
  1621.  
  1622. Efficiency is critical, particularly as the part of the
  1623. market not yet served is the market for very low cost
  1624. transactions.
  1625.  
  1626. > If we solve the sock-puppet issue, or accept that
  1627. > there's a central point controlling the generation of
  1628. > new keys,
  1629.  
  1630. A central point will invite attack, will be attacked.
  1631.  
  1632. The problem with computer networked money is that the
  1633. past can so easily be revised, so nodes come under
  1634. pressure to adjust the past - "I did not pay that"
  1635. swiftly becomes "I should not have paid that", which
  1636. requires arbitration, which is costly, and introduces
  1637. uncertainty, which is costly, and invites government
  1638. regulation, which is apt to be utterly ruinous and
  1639. wholly devastating.
  1640.  
  1641. For many purposes, reversal and arbitration is highly
  1642. desirable, but there is no way anyone can compete with
  1643. the arbitration provided by Visa and Mastercard, for
  1644. they have network effects on their side, and they do a
  1645. really good job of arbitration, at which they have vast
  1646. experience, accumulated skills, wisdom, and good repute.
  1647. So any new networked transaction system has to target
  1648. the demand for final and irreversible transactions.
  1649.  
  1650. The idea of a distributed network consensus is that one
  1651. has a lot of peers in a lot of jurisdictions, and once a
  1652. transaction has entered into the consensus, undoing it
  1653. is damn near impossible - one would have to pressure
  1654. most of the peers in most of the jurisdictions to agree,
  1655. and many of them don't even talk your language, and
  1656. those that do, will probably pretend that they do not.
  1657. So people will not even try.
  1658.  
  1659. To avoid pressure, the network has to avoid any central
  1660. point at which pressure can be applied. Recall Nero's
  1661. wish that Rome had a single throat that he could cut. If
  1662. we provide them with such a throat, it will be cut.
  1663.  
  1664. ---------------------------------------------------------------------
  1665. The Cryptography Mailing List
  1666. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  1667.  
  1668. Satoshi Nakamoto Fri, 14 Nov 2008 14:29:22 -0800
  1669.  
  1670. Hal Finney wrote:
  1671. > I think it is necessary that nodes keep a separate
  1672. > pending-transaction list associated with each candidate chain.
  1673. > ... One might also ask ... how many candidate chains must
  1674. > a given node keep track of at one time, on average?
  1675.  
  1676. Fortunately, it's only necessary to keep a pending-transaction pool for the
  1677. current best branch. When a new block arrives for the best branch,
  1678. ConnectBlock removes the block's transactions from the pending-tx pool. If a
  1679. different branch becomes longer, it calls DisconnectBlock on the main branch
  1680. down to the fork, returning the block transactions to the pending-tx pool, and
  1681. calls ConnectBlock on the new branch, sopping back up any transactions that
  1682. were in both branches. It's expected that reorgs like this would be rare and
  1683. shallow.
  1684.  
  1685. With this optimisation, candidate branches are not really any burden. They
  1686. just sit on the disk and don't require attention unless they ever become the
  1687. main chain.
  1688.  
  1689.  
  1690. > Or as James raised earlier, if the network broadcast
  1691. > is reliable but depends on a potentially slow flooding
  1692. > algorithm, how does that impact performance?
  1693.  
  1694. Broadcasts will probably be almost completely reliable. TCP transmissions are
  1695. rarely ever dropped these days, and the broadcast protocol has a retry
  1696. mechanism to get the data from other nodes after a while. If broadcasts turn
  1697. out to be slower in practice than expected, the target time between blocks may
  1698. have to be increased to avoid wasting resources. We want blocks to usually
  1699. propagate in much less time than it takes to generate them, otherwise nodes
  1700. would spend too much time working on obsolete blocks.
  1701.  
  1702. I'm planning to run an automated test with computers randomly sending payments
  1703. to each other and randomly dropping packets.
  1704.  
  1705.  
  1706. > 3. The bitcoin system turns out to be socially useful and valuable, so
  1707. > that node operators feel that they are making a beneficial contribution
  1708. > to the world by their efforts (similar to the various "@Home" compute
  1709. > projects where people volunteer their compute resources for good causes).
  1710. >
  1711. > In this case it seems to me that simple altruism can suffice to keep the
  1712. > network running properly.
  1713.  
  1714. It's very attractive to the libertarian viewpoint if we can explain it
  1715. properly. I'm better with code than with words though.
  1716.  
  1717. Satoshi Nakamoto
  1718.  
  1719. ---------------------------------------------------------------------
  1720. The Cryptography Mailing List
  1721. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  1722.  
  1723. James A. Donald Mon, 17 Nov 2008 09:06:45 -0800
  1724.  
  1725. Satoshi Nakamoto wrote:
  1726. > Fortunately, it's only necessary to keep a
  1727. > pending-transaction pool for the current best branch.
  1728.  
  1729. This requires that we know, that is to say an honest
  1730. well behaved peer whose communications and data storage
  1731. is working well knows, what the current best branch is -
  1732. but of course, the problem is that we are trying to
  1733. discover, trying to converge upon, a best branch, which
  1734. is not easy at the best of times, and becomes harder
  1735. when another peer is lying about its connectivity and
  1736. capabilities, and yet another peer has just had a major
  1737. disk drive failure obfuscated by a software crash, and
  1738. the international fibers connecting yet a third peer
  1739. have been attacked by terrorists.
  1740.  
  1741. > When a new block arrives for the best branch,
  1742. > ConnectBlock removes the block's transactions from
  1743. > the pending-tx pool. If a different branch becomes
  1744. > longer
  1745.  
  1746. Which presupposes the branches exist, that they are
  1747. fully specified and complete. If they exist as complete
  1748. works, rather than works in progress, then the problem
  1749. is already solved, for the problem is making progress.
  1750.  
  1751. > Broadcasts will probably be almost completely
  1752. > reliable.
  1753.  
  1754. There is a trade off between timeliness and reliability.
  1755. One can make a broadcast arbitrarily reliable if time is
  1756. of no consequence. However, when one is talking of
  1757. distributed data, time is always of consequence, because
  1758. it is all about synchronization (that peers need to have
  1759. corresponding views at corresponding times) so when one
  1760. does distributed data processing, broadcasts are always
  1761. highly unreliable Attempts to ensure that each
  1762. message arrives at least once result in increased timing
  1763. variation. Thus one has to make a protocol that is
  1764. either UDP or somewhat UDP like, in that messages are
  1765. small, failure of messages to arrive is common, messages
  1766. can arrive in different order to the order in which they
  1767. were sent, and the same message may arrive multiple
  1768. times. Either we have UDP, or we need to accommodate
  1769. the same problems as UDP has on top of TCP connections.
  1770.  
  1771. Rather than assuming that each message arrives at least
  1772. once, we have to make a mechanism such that the
  1773. information arrives even though conveyed by messages
  1774. that frequently fail to arrive.
  1775.  
  1776. > TCP transmissions are rarely ever dropped these days
  1777.  
  1778. People always load connections near maximum. When a
  1779. connection is near maximum, TCP connections suffer
  1780. frequent unreasonably long delays, and connections
  1781. simply fail a lot - your favorite web cartoon somehow
  1782. shows it is loading forever, and you try again, or it
  1783. comes up with a little x in place of a picture, and you
  1784. try again
  1785.  
  1786. Further very long connections - for example ftp
  1787. downloads of huge files, seldom complete. If you try to
  1788. ftp a movie, you are unlikely to get anywhere unless
  1789. both client and server have a resume mechanism so that
  1790. they can talk about partially downloaded files.
  1791.  
  1792. UDP connections, for example Skype video calls, also
  1793. suffer frequent picture freezes, loss of quality, and so
  1794. forth, and have to have mechanisms to keep going
  1795. regardless.
  1796.  
  1797. > It's very attractive to the libertarian viewpoint if
  1798. > we can explain it properly. I'm better with code than
  1799. > with words though.
  1800.  
  1801. No, it is very attractive to the libertarian if we can
  1802. design a mechanism that will scale to the point of
  1803. providing the benefits of rapidly irreversible payment,
  1804. immune to political interference, over the internet,
  1805. to very large numbers of people. You have an outline
  1806. and proposal for such a design, which is a big step
  1807. forward, but the devil is in the little details.
  1808.  
  1809. I really should provide a fleshed out version of your
  1810. proposal, rather than nagging you to fill out the blind
  1811. spots.
  1812.  
  1813. ---------------------------------------------------------------------
  1814. The Cryptography Mailing List
  1815. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  1816.  
  1817. Satoshi Nakamoto Mon, 17 Nov 2008 09:04:47 -0800
  1818.  
  1819. I'll try and hurry up and release the sourcecode as soon as possible to serve
  1820. as a reference to help clear up all these implementation questions.
  1821.  
  1822.  
  1823. Ray Dillinger (Bear) wrote:
  1824. > When a coin is spent, the buyer and seller digitally sign a (blinded)
  1825. > transaction record.
  1826.  
  1827. Only the buyer signs, and there's no blinding.
  1828.  
  1829.  
  1830. > If someone double spends, then the transaction record
  1831. > can be unblinded revealing the identity of the cheater.
  1832.  
  1833. Identities are not used, and there's no reliance on recourse. It's all
  1834. prevention.
  1835.  
  1836.  
  1837. > This is done via a fairly standard cut-and-choose
  1838. > algorithm where the buyer responds to several challenges
  1839. > with secret shares
  1840.  
  1841. No challenges or secret shares. A basic transaction is just what you see in
  1842. the figure in section 2. A signature (of the buyer) satisfying the public key
  1843. of the previous transaction, and a new public key (of the seller) that must be
  1844. satisfied to spend it the next time.
  1845.  
  1846.  
  1847. > They may also receive chains as long as the one they're trying to
  1848. > extend while they work, in which the last few "links" are links
  1849. > that are *not* in common with the chain on which they're working.
  1850. > These they ignore.
  1851.  
  1852. Right, if it's equal in length, ties are broken by keeping the earliest one
  1853. received.
  1854.  
  1855.  
  1856. > If it contains a double spend, then they create a "transaction"
  1857. > which is a proof of double spending, add it to their pool A,
  1858. > broadcast it, and continue work.
  1859.  
  1860. There's no need for reporting of "proof of double spending" like that. If the
  1861. same chain contains both spends, then the block is invalid and rejected.
  1862.  
  1863. Same if a block didn't have enough proof-of-work. That block is invalid and
  1864. rejected. There's no need to circulate a report about it. Every node could
  1865. see that and reject it before relaying it.
  1866.  
  1867. If there are two competing chains, each containing a different version of the
  1868. same transaction, with one trying to give money to one person and the other
  1869. trying to give the same money to someone else, resolving which of the spends is
  1870. valid is what the whole proof-of-work chain is about.
  1871.  
  1872. We're not "on the lookout" for double spends to sound the alarm and catch the
  1873. cheater. We merely adjudicate which one of the spends is valid. Receivers of
  1874. transactions must wait a few blocks to make sure that resolution has had time
  1875. to complete. Would be cheaters can try and simultaneously double-spend all
  1876. they want, and all they accomplish is that within a few blocks, one of the
  1877. spends becomes valid and the others become invalid. Any later double-spends
  1878. are immediately rejected once there's already a spend in the main chain.
  1879.  
  1880. Even if an earlier spend wasn't in the chain yet, if it was already in all the
  1881. nodes' pools, then the second spend would be turned away by all those nodes
  1882. that already have the first spend.
  1883.  
  1884.  
  1885. > If the new chain is accepted, then they give up on adding their
  1886. > current link, dump all the transactions from pool L back into pool
  1887. > A (along with transactions they've received or created since
  1888. > starting work), eliminate from pool A those transaction records
  1889. > which are already part of a link in the new chain, and start work
  1890. > again trying to extend the new chain.
  1891.  
  1892. Right. They also refresh whenever a new transaction comes in, so L pretty much
  1893. contains everything in A all the time.
  1894.  
  1895.  
  1896. > CPU-intensive digital signature algorithm to
  1897. > sign the chain including the new block L.
  1898.  
  1899. It's a Hashcash style SHA-256 proof-of-work (partial pre-image of zero), not a
  1900. signature.
  1901.  
  1902.  
  1903. > Is there a mechanism to make sure that the "chain" does not consist
  1904. > solely of links added by just the 3 or 4 fastest nodes? 'Cause a
  1905. > broadcast transaction record could easily miss those 3 or 4 nodes
  1906. > and if it does, and those nodes continue to dominate the chain, the
  1907. > transaction might never get added.
  1908.  
  1909. If you're thinking of it as a CPU-intensive digital signing, then you may be
  1910. thinking of a race to finish a long operation first and the fastest always
  1911. winning.
  1912.  
  1913. The proof-of-work is a Hashcash style SHA-256 collision finding. It's a
  1914. memoryless process where you do millions of hashes a second, with a small
  1915. chance of finding one each time. The 3 or 4 fastest nodes' dominance would
  1916. only be proportional to their share of the total CPU power. Anyone's chance of
  1917. finding a solution at any time is proportional to their CPU power.
  1918.  
  1919. There will be transaction fees, so nodes will have an incentive to receive and
  1920. include all the transactions they can. Nodes will eventually be compensated by
  1921. transaction fees alone when the total coins created hits the pre-determined
  1922. ceiling.
  1923.  
  1924.  
  1925. > Also, the work requirement for adding a link to the chain should
  1926. > vary (again exponentially) with the number of links added to that
  1927. > chain in the previous week, causing the rate of coin generation
  1928. > (and therefore inflation) to be strictly controlled.
  1929.  
  1930. Right.
  1931.  
  1932.  
  1933. > You need coin aggregation for this to scale. There needs to be
  1934. > a "provable" transaction where someone retires ten single coins
  1935. > and creates a new coin with denomination ten, etc.
  1936.  
  1937. Every transaction is one of these. Section 9, Combining and Splitting Value.
  1938.  
  1939.  
  1940. Satoshi Nakamoto
  1941.  
  1942.  
  1943.  
  1944. ---------------------------------------------------------------------
  1945. The Cryptography Mailing List
  1946. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  1947.  
  1948. Ray Dillinger Mon, 17 Nov 2008 09:05:24 -0800
  1949.  
  1950. On Sat, 2008-11-15 at 12:43 +0800, Satoshi Nakamoto wrote:
  1951.  
  1952. > I'll try and hurry up and release the sourcecode as soon as possible
  1953. > to serve as a reference to help clear up all these implementation
  1954. > questions.
  1955.  
  1956. > Ray Dillinger (Bear) wrote:
  1957. > > When a coin is spent, the buyer and seller digitally sign a (blinded)
  1958. > > transaction record.
  1959. >
  1960. > Only the buyer signs, and there's no blinding.
  1961. >
  1962. >
  1963. > > If someone double spends, then the transaction record
  1964. > > can be unblinded revealing the identity of the cheater.
  1965. >
  1966. > Identities are not used, and there's no reliance on recourse. It's all
  1967. > prevention.
  1968.  
  1969. Okay, that's surprising. If you're not using buyer/seller
  1970. identities, then you are not checking that a spend is being made
  1971. by someone who actually is the owner of (on record as having
  1972. recieved) the coin being spent.
  1973.  
  1974. There are three categories of identity that are useful to
  1975. think about. Category one: public. Real-world identities
  1976. are a matter of record and attached to every transaction.
  1977. Category two: Pseudonymous. There are persistent "identities"
  1978. within the system and people can see if something was done by
  1979. the same nym that did something else, but there's not necessarily
  1980. any way of linking the nyms with real-world identities. Category
  1981. three: unlinkably anonymous. There is no concept of identity,
  1982. persistent or otherwise. No one can say or prove whether the
  1983. agents involved in any transaction are the same agents as involved
  1984. in any other transaction.
  1985.  
  1986. Are you claiming category 3 as you seem to be, or category 2?
  1987. Lots of people don't distinguish between anonymous and
  1988. pseudonymous protocols, so it's worth asking exactly what
  1989. you mean here.
  1990.  
  1991. Anyway: I'll proceed on the assumption that you meant very
  1992. nearly (as nearly as I can imagine, anyway) what you said,
  1993. unlinkably anonymous. That means that instead of an "identity",
  1994. a spender has to demonstrate knowledge of a secret known only
  1995. to the real owner of the coin. One way to do this would be
  1996. to have the person recieving the coin generate an asymmetric
  1997. key pair, and then have half of it published with the
  1998. transaction. In order to spend the coin later, s/he must
  1999. demonstrate posession of the other half of the asymmetric
  2000. key pair, probably by using it to sign the key provided by
  2001. the new seller. So we cannot prove anything about "identity",
  2002. but we can prove that the spender of the coin is someone who
  2003. knows a secret that the person who recieved the coin knows.
  2004.  
  2005. And what you say next seems to confirm this:
  2006.  
  2007. > No challenges or secret shares. A basic transaction is just
  2008. > what you see in the figure in section 2. A signature (of the
  2009. > buyer) satisfying the public key of the previous transaction,
  2010. > and a new public key (of the seller) that must be satisfied to
  2011. > spend it the next time.
  2012.  
  2013.  
  2014. Note, even though this doesn't involve identity per se, it still
  2015. makes the agent doing the spend linkable to the agent who
  2016. earlier recieved the coin, so these transactions are linkable.
  2017. In order to counteract this, the owner of the coin needs to
  2018. make a transaction, indistinguishable to others from any
  2019. normal transaction, in which he creates a new key pair and
  2020. transfers the coin to its posessor (ie, has one sock puppet
  2021. "spend" it to another). No change in real-world identity of
  2022. the owner, but the transaction "linkable" to the agent who spent
  2023. the coin is unlinked. For category-three unlinkability, this
  2024. has to be done a random number of times - maybe one to six
  2025. times?
  2026.  
  2027.  
  2028. BTW, could you please learn to use carriage returns?? Your
  2029. lines are scrolling stupidly off to the right and I have to
  2030. scroll to see what the heck you're saying, then edit to add
  2031. carriage returns before I respond.
  2032.  
  2033.  
  2034. > > If it contains a double spend, then they create a "transaction"
  2035. > > which is a proof of double spending, add it to their pool A,
  2036. > > broadcast it, and continue work.
  2037.  
  2038. > There's no need for reporting of "proof of double spending" like
  2039. > that. If the same chain contains both spends, then the block is
  2040. > invalid and rejected.
  2041.  
  2042. > Same if a block didn't have enough proof-of-work. That block is
  2043. > invalid and rejected. There's no need to circulate a report
  2044. > about it. Every node could see that and reject it before relaying it.
  2045.  
  2046. Mmmm. I don't know if I'm comfortable with that. You're saying
  2047. there's no effort to identify and exclude nodes that don't
  2048. cooperate? I suspect this will lead to trouble and possible DOS
  2049. attacks.
  2050.  
  2051. > If there are two competing chains, each containing a different
  2052. > version of the same transaction, with one trying to give money
  2053. > to one person and the other trying to give the same money to
  2054. > someone else, resolving which of the spends is valid is what
  2055. > the whole proof-of-work chain is about.
  2056.  
  2057. Okay, when you say "same" transaction, and you're talking about
  2058. transactions that are obviously different, you mean a double
  2059. spend, right? Two transactions signed with the same key?
  2060.  
  2061. > We're not "on the lookout" for double spends to sound the alarm
  2062. > and catch the cheater. We merely adjudicate which one of the
  2063. > spends is valid. Receivers of transactions must wait a few
  2064. > blocks to make sure that resolution has had time to complete.
  2065.  
  2066. Until.... until what? How does anybody know when a transaction
  2067. has become irrevocable? Is "a few" blocks three? Thirty? A
  2068. hundred? Does it depend on the number of nodes? Is it logarithmic
  2069. or linear in number of nodes?
  2070.  
  2071.  
  2072. > Would be cheaters can try and simultaneously double-spend all
  2073. > they want, and all they accomplish is that within a few blocks,
  2074. > one of the spends becomes valid and the others become invalid.
  2075.  
  2076. But in the absence of identity, there's no downside to them
  2077. if spends become invalid, if they've already recieved the
  2078. goods they double-spent for (access to website, download,
  2079. whatever). The merchants are left holding the bag with
  2080. "invalid" coins, unless they wait that magical "few blocks"
  2081. (and how can they know how many?) before treating the spender
  2082. as having paid.
  2083.  
  2084. The consumers won't do this if they spend their coin and it takes
  2085. an hour to clear before they can do what they spent their coin on.
  2086. The merchants won't do it if there's no way to charge back a
  2087. customer when they find the that their coin is invalid because
  2088. the customer has doublespent.
  2089.  
  2090. > Even if an earlier spend wasn't in the chain yet, if it was
  2091. > already in all the nodes' pools, then the second spend would
  2092. > be turned away by all those nodes that already have the first
  2093. > spend.
  2094.  
  2095. So there's a possibility of an early catch when the broadcasts of
  2096. the initial simultaneous spends interfere with each other. I assume
  2097. here that the broadcasts are done by the sellers, since the buyer
  2098. has a possible disincentive to broadly disseminate spends.
  2099.  
  2100. > > If the new chain is accepted, then they give up on adding their
  2101. > > current link ... and start work again trying to extend the new
  2102. > > chain.
  2103. >
  2104. > Right. They also refresh whenever a new transaction comes in,
  2105. > so L pretty much contains everything in A all the time.
  2106.  
  2107. Okay, that's a big difference between a proof of work that takes
  2108. a huge set number of CPU cycles and a proof of work that takes a
  2109. tiny number of CPU cycles but has a tiny chance of success. You
  2110. can change the data set while working, and it doesn't mean you
  2111. need to start over. This is good in this case, as it means nobody
  2112. has to hold recently recieved transactions out of the link they're
  2113. working on.
  2114.  
  2115. > > Is there a mechanism to make sure that the "chain" does not consist
  2116. > > solely of links added by just the 3 or 4 fastest nodes?
  2117.  
  2118. > If you're thinking of it as a CPU-intensive digital signing, then
  2119. > you may be thinking of a race to finish a long operation first and
  2120. > the fastest always winning.
  2121.  
  2122. Right. That was the misconception I was working with. Again, the
  2123. difference between a proof taking a huge set number of CPU cycles
  2124. and a proof that takes a tiny number of CPU cycles but has a tiny
  2125. chance of success.
  2126.  
  2127. > Anyone's chance of finding a solution at any
  2128. > time is proportional to their CPU power.
  2129.  
  2130. It's like a random variation in the work factor; in this way it works
  2131. in your favor.
  2132.  
  2133. > There will be transaction fees, so nodes will have an incentive
  2134. > to receive and include all the transactions they can. Nodes
  2135. > will eventually be compensated by transaction fees alone when
  2136. > the total coins created hits the pre-determined ceiling.
  2137.  
  2138. I don't understand how "transaction fees" would work, and how the money
  2139. would find its way from the agents doing transactions to those running
  2140. the network. But the economic effect is the same (albeit somewhat
  2141. randomized) if adding a link to the chain allows the node to create
  2142. a coin, so I would stick with that.
  2143.  
  2144. Also, be aware that the compute power of different nodes can be
  2145. expected to vary by two orders of magnitude at any given moment in
  2146. history.
  2147.  
  2148. Bear
  2149.  
  2150.  
  2151. ---------------------------------------------------------------------
  2152. The Cryptography Mailing List
  2153. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  2154.  
  2155. Nicolas Williams Tue, 18 Nov 2008 14:51:44 -0800
  2156.  
  2157. On Fri, Nov 14, 2008 at 11:04:21PM -0800, Ray Dillinger wrote:
  2158. > On Sat, 2008-11-15 at 12:43 +0800, Satoshi Nakamoto wrote:
  2159. > > > If someone double spends, then the transaction record
  2160. > > > can be unblinded revealing the identity of the cheater.
  2161. > >
  2162. > > Identities are not used, and there's no reliance on recourse. It's all
  2163. > > prevention.
  2164. >
  2165. > Okay, that's surprising. If you're not using buyer/seller
  2166. > identities, then you are not checking that a spend is being made
  2167. > by someone who actually is the owner of (on record as having
  2168. > recieved) the coin being spent.
  2169.  
  2170. How do identities help? It's supposed to be anonymous cash, right? And
  2171. say you identify a double spender after the fact, then what? Perhaps
  2172. you're looking at a disposable ID. Or perhaps you can't chase them
  2173. down.
  2174.  
  2175. Double spend detection needs to be real-time or near real-time.
  2176.  
  2177. Nico
  2178. --
  2179.  
  2180. ---------------------------------------------------------------------
  2181. The Cryptography Mailing List
  2182. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  2183.  
  2184. Satoshi Nakamoto Mon, 17 Nov 2008 09:06:02 -0800
  2185.  
  2186. Ray Dillinger wrote:
  2187. > One way to do this would be
  2188. > to have the person recieving the coin generate an asymmetric
  2189. > key pair, and then have half of it published with the
  2190. > transaction. In order to spend the coin later, s/he must
  2191. > demonstrate posession of the other half of the asymmetric
  2192. > key pair, probably by using it to sign the key provided by
  2193. > the new seller.
  2194.  
  2195. Right, it's ECC digital signatures. A new key pair is used for every
  2196. transaction.
  2197.  
  2198. It's not pseudonymous in the sense of nyms identifying people, but it
  2199. is at least a little pseudonymous in that the next action on a coin
  2200. can be identified as being from the owner of that coin.
  2201.  
  2202.  
  2203. > Mmmm. I don't know if I'm comfortable with that. You're saying
  2204. > there's no effort to identify and exclude nodes that don't
  2205. > cooperate? I suspect this will lead to trouble and possible DOS
  2206. > attacks.
  2207.  
  2208. There is no reliance on identifying anyone. As you've said, it's
  2209. futile and can be trivially defeated with sock puppets.
  2210.  
  2211. The credential that establishes someone as real is the ability to
  2212. supply CPU power.
  2213.  
  2214.  
  2215. > Until.... until what? How does anybody know when a transaction
  2216. > has become irrevocable? Is "a few" blocks three? Thirty? A
  2217. > hundred? Does it depend on the number of nodes? Is it logarithmic
  2218. > or linear in number of nodes?
  2219.  
  2220. Section 11 calculates the worst case under attack. Typically, 5 or
  2221. 10 blocks is enough for that. If you're selling something that
  2222. doesn't merit a network-scale attack to steal it, in practice you
  2223. could cut it closer.
  2224.  
  2225.  
  2226. > But in the absence of identity, there's no downside to them
  2227. > if spends become invalid, if they've already received the
  2228. > goods they double-spent for (access to website, download,
  2229. > whatever). The merchants are left holding the bag with
  2230. > "invalid" coins, unless they wait that magical "few blocks"
  2231. > (and how can they know how many?) before treating the spender
  2232. > as having paid.
  2233. >
  2234. > The consumers won't do this if they spend their coin and it takes
  2235. > an hour to clear before they can do what they spent their coin on.
  2236. > The merchants won't do it if there's no way to charge back a
  2237. > customer when they find the that their coin is invalid because
  2238. > the customer has doublespent.
  2239.  
  2240. This is a version 2 problem that I believe can be solved fairly
  2241. satisfactorily for most applications.
  2242.  
  2243. The race is to spread your transaction on the network first. Think 6
  2244. degrees of freedom -- it spreads exponentially. It would only take
  2245. something like 2 minutes for a transaction to spread widely enough
  2246. that a competitor starting late would have little chance of grabbing
  2247. very many nodes before the first one is overtaking the whole network.
  2248. During those 2 minutes, the merchant's nodes can be watching for a
  2249. double-spent transaction. The double-spender would not be able to
  2250. blast his alternate transaction out to the world without the merchant
  2251. getting it, so he has to wait before starting.
  2252.  
  2253. If the real transaction reaches 90% and the double-spent tx reaches
  2254. 10%, the double-spender only gets a 10% chance of not paying, and 90%
  2255. chance his money gets spent. For almost any type of goods, that's
  2256. not going to be worth it for the scammer.
  2257.  
  2258. Information based goods like access to website or downloads are
  2259. non-fencible. Nobody is going to be able to make a living off
  2260. stealing access to websites or downloads. They can go to the file
  2261. sharing networks to steal that. Most instant-access products aren't
  2262. going to have a huge incentive to steal.
  2263.  
  2264. If a merchant actually has a problem with theft, they can make the
  2265. customer wait 2 minutes, or wait for something in e-mail, which many
  2266. already do. If they really want to optimize, and it's a large
  2267. download, they could cancel the download in the middle if the
  2268. transaction comes back double-spent. If it's website access,
  2269. typically it wouldn't be a big deal to let the customer have access
  2270. for 5 minutes and then cut off access if it's rejected. Many such
  2271. sites have a free trial anyway.
  2272.  
  2273. Satoshi Nakamoto
  2274.  
  2275.  
  2276. ---------------------------------------------------------------------
  2277. The Cryptography Mailing List
  2278. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  2279.  
  2280. Satoshi Nakamoto Mon, 17 Nov 2008 13:33:04 -0800
  2281.  
  2282. James A. Donald wrote:
  2283. > > Fortunately, it's only necessary to keep a
  2284. > > pending-transaction pool for the current best branch.
  2285. >
  2286. > This requires that we know, that is to say an honest
  2287. > well behaved peer whose communications and data storage
  2288. > is working well knows, what the current best branch is -
  2289.  
  2290. I mean a node only needs the pending-tx pool for the best branch it
  2291. has. The branch that it currently thinks is the best branch.
  2292. That's the branch it'll be trying to make a block out of, which is
  2293. all it needs the pool for.
  2294.  
  2295.  
  2296. > > Broadcasts will probably be almost completely
  2297. > > reliable.
  2298. >
  2299. > Rather than assuming that each message arrives at least
  2300. > once, we have to make a mechanism such that the
  2301. > information arrives even though conveyed by messages
  2302. > that frequently fail to arrive.
  2303.  
  2304. I think I've got the peer networking broadcast mechanism covered.
  2305.  
  2306. Each node sends its neighbours an inventory list of hashes of the
  2307. new blocks and transactions it has. The neighbours request the
  2308. items they don't have yet. If the item never comes through after a
  2309. timeout, they request it from another neighbour that had it. Since
  2310. all or most of the neighbours should eventually have each item,
  2311. even if the coms get fumbled up with one, they can get it from any
  2312. of the others, trying one at a time.
  2313.  
  2314. The inventory-request-data scheme introduces a little latency, but
  2315. it ultimately helps speed more by keeping extra data blocks off the
  2316. transmit queues and conserving bandwidth.
  2317.  
  2318.  
  2319. > You have an outline
  2320. > and proposal for such a design, which is a big step
  2321. > forward, but the devil is in the little details.
  2322.  
  2323. I believe I've worked through all those little details over the
  2324. last year and a half while coding it, and there were a lot of them.
  2325. The functional details are not covered in the paper, but the
  2326. sourcecode is coming soon. I sent you the main files.
  2327. (available by request at the moment, full release soon)
  2328.  
  2329. Satoshi Nakamoto
  2330.  
  2331.  
  2332. ---------------------------------------------------------------------
  2333. The Cryptography Mailing List
  2334. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
  2335.  
  2336. James A. Donald Tue, 18 Nov 2008 14:52:59 -0800
  2337.  
  2338. Nicolas Williams wrote:
  2339. > How do identities help? It's supposed to be anonymous
  2340. > cash, right?
  2341.  
  2342. Actually no. It is however supposed to be pseudonymous,
  2343. so dinging someone's reputation still does not help
  2344. much.
  2345.  
  2346. > And say you identify a double spender after the fact,
  2347. > then what? Perhaps you're looking at a disposable ID.
  2348. > Or perhaps you can't chase them down.
  2349. >
  2350. > Double spend detection needs to be real-time or near
  2351. > real-time.
  2352.  
  2353. Near real time means we have to use UDP or equivalent,
  2354. rather than TCP or equivalent, and we have to establish
  2355. an approximate consensus, not necessarily the final
  2356. consensus, not necessarily exact agreement, but close to
  2357. it, in a reasonably small number of round trips.
  2358.  
  2359. ---------------------------------------------------------------------
  2360. The Cryptography Mailing List
  2361. Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RAW Paste Data