Re: voting by m of n digital signature?
> Is there a way of constructing a digital signature so > that the signature proves that at least m possessors of > secret keys corresponding to n public keys signed, for n > a dozen or less, without revealing how many more than m, > or which ones signed? Yes there are a number of ways. Usually they involve splitting the private key so that when a quorum of fragment signatures are done, they can be combined and the result verified by the public key. Look for multi-step signing or threshold signatures, for example. Disclaimer: I worked at CertCo who had the "best" technology in this area. It was created for SET. /r$ -- STSM, DataPower Chief Programmer WebSphere DataPower SOA Appliances http://www.ibm.com/software/integration/datapower/ - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
James A. Donald wrote: >OK, suppose one node incorporates a bunch of >transactions in its proof of work, all of them honest >legitimate single spends and another node incorporates a >different bunch of transactions in its proof of >work, all of them equally honest legitimate single >spends, and both proofs are generated at about the same >time. > >What happens then? They both broadcast their blocks. All nodes receive them and keep both, but only work on the one they received first. We'll suppose exactly half received one first, half the other. In a short time, all the transactions will finish propagating so that everyone has the full set. The nodes working on each side will be trying to add the transactions that are missing from their side. When the next proof-of-work is found, whichever previous block that node was working on, that branch becomes longer and the tie is broken. Whichever side it is, the new block will contain the other half of the transactions, so in either case, the branch will contain all transactions. Even in the unlikely event that a split happened twice in a row, both sides of the second split would contain the full set of transactions anyway. It's not a problem if transactions have to wait one or a few extra cycles to get into a block. Satoshi Nakamoto - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
Satoshi Nakamoto wrote: > Increasing hardware speed is handled: "To compensate > for increasing hardware speed and varying interest in > running nodes over time, the proof-of-work difficulty > is determined by a moving average targeting an average > number of blocks per hour. If they're generated too > fast, the difficulty increases." This does not work - your proposal involves complications I do not think you have thought through. Furthermore, it cannot be made to work, as in the proposed system the work of tracking who owns what coins is paid for by seigniorage, which requires inflation. This is not an intolerable flaw - predictable inflation is less objectionable than inflation that gets jiggered around from time to time to transfer wealth from one voting block to another. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
voting by m of n digital signature?
Is there a way of constructing a digital signature so that the signature proves that at least m possessors of secret keys corresponding to n public keys signed, for n a dozen or less, without revealing how many more than m, or which ones signed? - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
-- Satoshi Nakamoto wrote: > The proof-of-work chain is the solution to the > synchronisation problem, and to knowing what the > globally shared view is without having to trust > anyone. > > A transaction will quickly propagate throughout the > network, so if two versions of the same transaction > were reported at close to the same time, the one with > the head start would have a big advantage in reaching > many more nodes first. Nodes will only accept the > first one they see, refusing the second one to arrive, > so the earlier transaction would have many more nodes > working on incorporating it into the next > proof-of-work. In effect, each node votes for its > viewpoint of which transaction it saw first by > including it in its proof-of-work effort. OK, suppose one node incorporates a bunch of transactions in its proof of work, all of them honest legitimate single spends and another node incorporates a slightly different bunch of transactions in its proof of work, all of them equally honest legitimate single spends, and both proofs are generated at about the same time. What happens then? - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
Satoshi Nakamoto wrote: > The bandwidth might not be as prohibitive as you > think. A typical transaction would be about 400 bytes > (ECC is nicely compact). Each transaction has to be > broadcast twice, so lets say 1KB per transaction. > Visa processed 37 billion transactions in FY2008, or > an average of 100 million transactions per day. That > many transactions would take 100GB of bandwidth, or > the size of 12 DVD or 2 HD quality movies, or about > $18 worth of bandwidth at current prices. The trouble is, you are comparing with the Bankcard network. But a new currency cannot compete directly with an old, because network effects favor the old. You have to go where Bankcard does not go. At present, file sharing works by barter for bits. This, however requires the double coincidence of wants. People only upload files they are downloading, and once the download is complete, stop seeding. So only active files, files that quite a lot of people want at the same time, are available. File sharing requires extremely cheap transactions, several transactions per second per client, day in and day out, with monthly transaction costs being very small per client, so to support file sharing on bitcoins, we will need a layer of account money on top of the bitcoins, supporting transactions of a hundred thousandth the size of the smallest coin, and to support anonymity, chaumian money on top of the account money. Let us call a bitcoin bank a bink. The bitcoins stand in the same relation to account money as gold stood in the days of the gold standard. The binks, not trusting each other to be liquid when liquidity is most needed, settle out any net discrepancies with each other by moving bit coins around once every hundred thousand seconds or so, so bitcoins do not change owners that often, Most transactions cancel out at the account level. The binks demand bitcoins of each other only because they don't want to hold account money for too long. So a relatively small amount of bitcoins infrequently transacted can support a somewhat larger amount of account money frequently transacted. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
James A. Donald wrote: > The core concept is that lots of entities keep complete and consistent > information as to who owns which bitcoins. > > But maintaining consistency is tricky. It is not clear to me what > happens when someone reports one transaction to one maintainer, and > someone else transports another transaction to another maintainer. The > transaction cannot be known to be valid until it has been incorporated > into a globally shared view of all past transactions, and no one can > know that a globally shared view of all past transactions is globally > shared until after some time has passed, and after many new > transactions have arrived. > > Did you explain how to do this, and it just passed over my head, or > were you confident it could be done, and a bit vague as to the details? The proof-of-work chain is the solution to the synchronisation problem, and to knowing what the globally shared view is without having to trust anyone. A transaction will quickly propagate throughout the network, so if two versions of the same transaction were reported at close to the same time, the one with the head start would have a big advantage in reaching many more nodes first. Nodes will only accept the first one they see, refusing the second one to arrive, so the earlier transaction would have many more nodes working on incorporating it into the next proof-of-work. In effect, each node votes for its viewpoint of which transaction it saw first by including it in its proof-of-work effort. If the transactions did come at exactly the same time and there was an even split, it's a toss up based on which gets into a proof-of-work first, and that decides which is valid. When a node finds a proof-of-work, the new block is propagated throughout the network and everyone adds it to the chain and starts working on the next block after it. Any nodes that had the other transaction will stop trying to include it in a block, since it's now invalid according to the accepted chain. The proof-of-work chain is itself self-evident proof that it came from the globally shared view. Only the majority of the network together has enough CPU power to generate such a difficult chain of proof-of-work. Any user, upon receiving the proof-of-work chain, can see what the majority of the network has approved. Once a transaction is hashed into a link that's a few links back in the chain, it is firmly etched into the global history. Satoshi Nakamoto - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
Hal Finney wrote: > it is mentioned that if a broadcast transaction does not reach all nodes, > it is OK, as it will get into the block chain before long. How does this > happen - what if the node that creates the "next" block (the first node > to find the hashcash collision) did not hear about the transaction, > and then a few more blocks get added also by nodes that did not hear > about that transaction? Do all the nodes that did hear it keep that > transaction around, hoping to incorporate it into a block once they get > lucky enough to be the one which finds the next collision? Right, nodes keep transactions in their working set until they get into a block. If a transaction reaches 90% of nodes, then each time a new block is found, it has a 90% chance of being in it. > Or for example, what if a node is keeping two or more chains around as > it waits to see which grows fastest, and a block comes in for chain A > which would include a double-spend of a coin that is in chain B? Is that > checked for or not? (This might happen if someone double-spent and two > different sets of nodes heard about the two different transactions with > the same coin.) That does not need to be checked for. The transaction in whichever branch ends up getting ahead becomes the valid one, the other is invalid. If someone tries to double spend like that, one and only one spend will always become valid, the others invalid. Receivers of transactions will normally need to hold transactions for perhaps an hour or more to allow time for this kind of possibility to be resolved. They can still re-spend the coins immediately, but they should wait before taking an action such as shipping goods. > I also don't understand exactly how double-spending, or cancelling > transactions, is accomplished by a superior attacker who is able to muster > more computing power than all the honest participants. I see that he can > create new blocks and add them to create the longest chain, but how can > he erase or add old transactions in the chain? As the attacker sends out > his new blocks, aren't there consistency checks which honest nodes can > perform, to make sure that nothing got erased? More explanation of this > attack would be helpful, in order to judge the gains to an attacker from > this, versus simply using his computing power to mint new coins honestly. The attacker isn't adding blocks to the end. He has to go back and redo the block his transaction is in and all the blocks after it, as well as any new blocks the network keeps adding to the end while he's doing that. He's rewriting history. Once his branch is longer, it becomes the new valid one. This touches on a key point. Even though everyone present may see the shenanigans going on, there's no way to take advantage of that fact. It is strictly necessary that the longest chain is always considered the valid one. Nodes that were present may remember that one branch was there first and got replaced by another, but there would be no way for them to convince those who were not present of this. We can't have subfactions of nodes that cling to one branch that they think was first, others that saw another branch first, and others that joined later and never saw what happened. The CPU power proof-of-work vote must have the final say. The only way for everyone to stay on the same page is to believe that the longest chain is always the valid one, no matter what. > As far as the spending transactions, what checks does the recipient of a > coin have to perform? Does she need to go back through the coin's entire > history of transfers, and make sure that every transaction on the list is > indeed linked into the "timestamp" block chain? Or can she just do the > latest one? The recipient just needs to verify it back to a depth that is sufficiently far back in the block chain, which will often only require a depth of 2 transactions. All transactions before that can be discarded. > Do the timestamp nodes check transactions, making sure that > the previous transaction on a coin is in the chain, thereby enforcing > the rule that all transactions in the chain represent valid coins? Right, exactly. When a node receives a block, it checks the signatures of every transaction in it against previous transactions in blocks. Blocks can only contain transactions that depend on valid transactions in previous blocks or the same block. Transaction C could depend on transaction B in the same block and B depends on transaction A in an earlier block. > Sorry about all the questions, but as I said this does seem to be a > very promising and original idea, and I am looking forward to seeing > how the concept is further developed. It would be helpful to see a more > process oriented description of the idea, with concrete details of the > data structures for the various objects (coins, blocks, transactions), > the data which is included in messages, and algorithmic