If you want to use multiple blocks, then pre-define a set of block heights. Repeat the process for each block hash, using the output from the previous HMAC hash as the new key for the next HMAC hash.
This is useless, an attacker will simply try to influence only the last block. |
|
|
|
This new "Bitcoin Beacon" paper has some answers to the OP: http://arxiv.org/abs/1605.04559Maybe in your context people already trust the organizers, so you don't need public verifiability of tiebreaking, and then commit/decommit (with or without penalties) among the organizers is already ok, but the beacon will only help of course (described in section5 of PDF in the arxiv link). |
|
|
|
He accepts a block with the transaction. It is 1 conf, but not 0-conf
It's 0-PoW-conf, I tried to explain to you in post #4 why the merchant would consider this 0-PoW-conf to be inferior superior to 0-conf in Bitcoin, but still inferior to a single PoW confirmation. The paper says that nodes "ban all blocks (blockheaders) with the last Nth stakeholders", but that can happen only if they will discover such headers. Imagine:
All nodes are connected as bipartite graph (every "red" node is connected to a "blue" node, but there is no "red"-"red" or "blue"-"blue" connections)
Attacker sends different blocks to all red nodes, remember, there is no connection between red-red nodes, so red nodes relay blocks only to blue nodes. Each blue node will ban this header. But how can red nodes know about it?
We will need to implement some kind of alert system to avoid new DoS attack vectors. Can you ban the node for sending 2nd, 3rd, 4th ... block with the same header?
I don`t think that system with a user, who can create unlimited number of blocks "for free" will run perfectly.
Can see a problems here and solutions can cause new problems.
What problems specifically? Maybe what you don't understand is that what you describe is exactly the same situation as with Bitcoin right now, the red miner picks transactions as he wishes and tries to solve a red block, the blue miner picks other transactions (in particular a different coinbase) and tries to solve a blue block, and so on, and we get convergence because of the PoW component, both in Bitcoin and in PoA. I tried to show to you in post #4 how "it isn't important whether miners try to extend the single block that the attacker signed" if the objective of the attack is to create netsplits, because it'd be easier to do the attack with regular transactions as in Bitcoin. |
|
|
|
1. he makes one block with his own transaction to merchant and sends this block to the merchant.
2 immediately creates the second block with a double-spend transaction and sends it to other peers.
3. The first block will be orphaned with a high probability, so as merchant's tx.
If the merchant accepts then it's 0-conf security, a sensible merchant will wait for additional confirmations. I tried to explain to you why what you say doesn't make sense, because it's easier to double-spend by offering a higher fee reward to everyone at once. What if the last stakeholder will send a valid blocks. Like he will connect to all peers and send them different, but valid blocks (the "cost" of this kind of action is comparatively low).
How they can choose the "right" one?
If all these different valid blocks don't offer any particular reward to specific addresses, then it's just DoS attack as discussed in section 5.1 of the PoA paper. If the attacker does wish to mix things up by incentivizing different participants to work on diffferent forks, then I tried to explain to you how to accomplish this attack more easily in Bitcoin. If you disagree or don't understand something specific in my reply, then please refer to the text that I wrote and specify why you think that it's wrong, or what's unclear about it. |
|
|
|
4. Also we noticed a possible problem with the original PoA. ONLY the "last" "stakeholder" can set transactions for a new block. When done, he signs and broadcasts a new block to the network. Seems nothing wrong here, but "last" "stakeholder" can produce as many valid blocks as he needs by changing transactions set. So he can split the blockchain and make a double spend. In that case we are planning to give a right of setting up a block to the Proof-of-work miners.
He can split but not double-spend (if you meant 0-confirmation then it doesn't really make sense because it's better to just re-broadcasting competing transaction as in Bitcoin, unlike the last stakeholder who cannot offer a higher fee to all the miners). The last stakeholder can be an attacker who produces many valid blocks, but it isn't much different than attempting DoS on the Bitcoin network, it's discussed in section 5.1 of the PoA paper. Maybe you meant that the last stakeholder could try to create many valid blocks where each block pays a reward to a known PoW-miner address (by somehow sending the block to each miner directly to avoid blacklisting by other nodes), and this way get miners to work on different blocks. But it isn't important whether miners try to extend the single block that the attacker signed, or different blocks that the attacker signed. In fact, an attacker can do the same thing more easily in Bitcoin, by broadcasting conflicting transactions that pay to known miners addresses, so when one miner solves a block that includes the extra payment transaction, the other miners might prefer to continue to try to solve their old block. BTW it's also possible to confiscate the reward of the last stakeholder when he double-signs, see for example section 2.2 of CoA ( http://arxiv.org/abs/1406.5694). In PoA, the reason for letting stakeholders (rather than miners) decide which transactions to include in blocks is that otherwise an external hashpower (without any stake) can attempt to attack by excluding transactions in the blocks, so it's better to give this decision power to entities who have an incentive to keep the network secure. |
|
|
|
So I think it would be an obvious improvement and might well be worth an increase in the resulting master public key size just for additional robustness, I don't know that in practise it would safely permit intentional use of it.
To say that public key size is the problem here seems kind of vague, I think that the main deficiency is that you need to perform m elliptic curve exponentations to derive the next pubkey, instead of a single exponentation. So I'm not sure if the tradeoff between the extra complexity versus the supposed better security makes sense (with non-hierarchical variant), it depends on whether the security improvement is significant in practical scenarios. You use multi-exp which is not N times slower, and wnaf with some big tables on each of your points, so it's only a couple adds even if your coefficients are big. libsecp256k1 on a fast laptop does something like 70k ecdsa verifies per second, and that involves a multiexp on two points (and a number of other expensive operations: a modinv for s and a sqrt to recover the pubkey). So, I don't see why you'd consider that an issue even with hundreds of points. The reason I cited size is that the advantage of the homomorphic derivation over independent keys at all is size, and having to grow the pubkey linearly in use (to be secure in the worst case) erodes that improvement. Hmm wnaf="window non-adjacent form", some more efficient representation it seems, I had to google that... I wasn't aware of these fast multi-exp methods, cool. I'm trying to see if I understand why you say that the pubkey size needs to grow: with an efficient multi-exp as you suggest, we can for example extend BIP32 to make a new child node in the tree hierarchy so that the branch that starts at this child is a non-hierarchical variant with secret sharing of m keys, so that if one (or several) privkeys leak in this branch then all the other privkeys are still secure. But for this we'll need to store m pubkeys at this new child node, which implies the size growth? That's the idea? Maybe that's still a nice extension, because it'd be optional, and even if you prune these m pubkeys they can still be re-derived later from the master privkey, just like non-homomorphic type-1 "subaccounts" can be re-derived from the master privkey. |
|
|
|
So I think that your original non-hierarchical secret sharing variant makes more sense, relative to hierarchical variants. One of the most common use-cases of BIP32 is just a personal wallet where you don't need to decrypt your privkeys to derive more public addresses, and there the non-hierarchical variant is fine.
I don't understand what non-hierarchical variant you are talking about? Everything in the abstract and the OP refers to a hierarchical (HD) wallet. The title of the short paper says "hierarchical", but it actually only specifies the non-hierarchical variant of the OP of the 2011 thread ( https://bitcointalk.org/index.php?topic=19137.0), without chaincodes. With an hierarchical variant you can delegate the root of a sub-tree of the wallet's hierarchy to a third party, without giving this third party access to the other branches of the tree. |
|
|
|
- If you really want to give each child a,b,c,... ability to reveal up to na,nb,nc,... private keys then you need at least 1+na+nb+nc+... master private keys. This isn't a problem if you're the top-level admin because you can generate the private keys deterministically. But if you're an auditor (who is only allowed to know the master public keys and needs to store them explicitly) then you could run into an exponential blow-up of public key size: if you want each node in a k-ary tree of depth d to be able to reveal up to n keys then you need something like (kn)O(d) master keys.
You could follow BIP32 design and derive, for each child, m different tuples of coefficients hash(chaincode,i,j)=(a_{i,j,1},a_{i,j,2},...,a_{i,j,m}) where i is the index (i.e., tree path), and j runs from 1 to m too. This way we obtain m different pubkeys Q_i_1,Q_i_2,...,Q_i_m from the m pubkeys of the parent node Q_parent_1,Q_parent_2,...,Q_parent_m, for example Q_i_1 is a linear combination of the Q_parent_i pubkeys with (a_{i,1,1},a_{i,1,2},...,a_{i,1,m}) coefficients. Similarly to BIP32, you can use hash(chaincode,i,Q_parent_j) instead of hash(chaincode,i,j) to have more entropy. This would mean that the granularity at each branch of the HD wallet is in multiplies of m, which would be a disadvantage with small branches and large m. But the more important thing is that in practice it probably doesn't really accomplish anything, because if there's a security breach and some privkey of node i leaks, then most probably all the m privkeys at that node i leaked along with it. You could argue e.g. that against a theoretical crypto attack that computes a privkey from the pubkey in t time, you'll need to execute an attack of mt total time instead of t time, for a complete break of the HD wallet, but that isn't really interesting. So I think that your original non-hierarchical secret sharing variant makes more sense, relative to hierarchical variants. One of the most common use-cases of BIP32 is just a personal wallet where you don't need to decrypt your privkeys to derive more public addresses, and there the non-hierarchical variant is fine. So I think it would be an obvious improvement and might well be worth an increase in the resulting master public key size just for additional robustness, I don't know that in practise it would safely permit intentional use of it.
To say that public key size is the problem here seems kind of vague, I think that the main deficiency is that you need to perform m elliptic curve exponentations to derive the next pubkey, instead of a single exponentation. So I'm not sure if the tradeoff between the extra complexity versus the supposed better security makes sense (with non-hierarchical variant), it depends on whether the security improvement is significant in practical scenarios. |
|
|
|
1. we need to be able to have an internal organization create the seeds on behalf of a user (at their request.)
I don't think that you want this organization to create the "seed" because it implies that this organization can also steal the user's coins. Maybe what you want is that any user can generate a fresh seed (that derives privkey/pubkey pairs so that only the user knows the privkeys), where the master pubkey and master chaincode (that are derived from the seed that he generated) must be signed by this organization before this "user account" becomes valid on this network? This implies that new users are at the mercy of this organization, e.g., this organization may refuse to sign a new account unless it receives a bribe on the side. Also, if the signing key of this organization is compromised then all bets are off. |
|
|
|
|
Re: deniable encryption
The simple use-case for deniable encryption is an attacker who points a gun at you and demands that you decrypt your Bitcoin wallet so that he can take your coins, hence you decrypt by using a decoy secret key that only gives the attacker a smaller portion of your coins, and while you're in a safe environment you decrypt your wallet with another secret key to access the larger portion of your coins. The attacker might see your screen with your wallet before he approaches you, therefore for everyday use you should prefer to operate with the version of your wallet that only controls the smaller portion of your coins (i.e. the pubkeys that correspond to the larger amount of coins will also be encrypted). This can be done by separate wallet.dat files, but built-in support for BIP32 wallet can be nicer, by selecting some branch in the deterministic tree as your decoy wallet, so you can easily transfer coins to/from that branch (see also post #192 in this thread).
It is easy to see that symmetric deniable encryption implies that the ciphertext must be bigger than the plaintext, simply because ordinary symmetric encryption is highly efficient. Suppose that you have two incompressible files f1 and f2 (i.e. files with high entropy) of same size, and note that the size of AES(f1) is the same as the size of f1. If you could create a ciphertext c1 of same size as f1 that can be decrypted into f1 by using the secret key k1 and can be decrypted into f2 by using another secret key k2, then you effectively compressed (f1,f2) into (c1,k1,k2), which is impossible.
This implies that if the attacker controlled which symmetric encryption algorithm we must use then there's no hope to have deniable encryption, but fortunately we can choose to use by default a symmetric encryption algorithm that expands the size of the ciphertext. Since wallet.dat files are quite small, that isn't really a big deal for end-users.
The straightforward construction for symmetric deniable encryption is simply concatenation, meaning that if we have the real plaintext f1 and the decoy plaintext f2 then the ciphertext is c=(c_1,c_2)=(enc_AES_k_i1(f1),enc_AES_k_i2(f2)) and the decryption algorithm dec(c,k,idx) will invoke dec_AES_k(c_idx), meaning that for {i1,i2}={1,2} the real secret key is (k1,i1) and the decoy secret key is (k2,i2).
The reference Bitcoin client can have by default a checkbox that reads "Support for deniable encryption", and when a user (who doesn't care about deniable encryption) encrypts his wallet the client will simply create a ciphertext that's twice the size of the plaintext where one random half is random data. This checkbox should be on by default, and each user can turn it off if he wishes to have a smaller ciphertext. If the user does care about deniable encryption, he encrypts his wallet with real half and decoy half by using the simple concatenation construction. If an attacker points a gun at this user, he will decrypt with his decoy key, and the attacker cannot tell whether the other half is random data (which would be the case with an ordinary user who didn't specifically choose to use deniable encryption) or not.
To protect against scenarios where the attacker has a reason to suspect that the user did use deniable encryption, and therefore try to force the user to reveal his 2nd secret key, it might be preferable to concatenate some n<N ciphertexts of variable sizes, instead of two ciphertexts of equal size, where n is random and N is some fixed bound. This way, the attacker wouldn't even know how many decoy wallets are contained in the ciphertext.
Edit: actually it isn't completely clear whether AES can be obliviously generated, meaning that (for random k) enc_AES_k(random) could be distinguishable from random (thanks to Hong-Sheng Zhou for this info), but in the worst case we'd just need to invoke AES once to encrypt random plaintext with random key and throw away the key...
|
|
|
|
I meant to ask: If there's only a value cap, that'd mean a miner could trivially blow up the blockchain in size by adding a bunch of near-zero transactions and everyone would accept it as valid.
Not exactly, because the transaction fees policy can be such that if you wish to send a near-zero amount then you have to pay a large fee. I attempted to give a more complete answer in the previous reply, regarding "third tragedy" paragraph in the paper. The data size cap should be aligned with the amount of compensation that the nodes who secure the network get, otherwise it would be unprofitable for them to provide this security. |
|
|
|
I suppose it will just readjust based on the implicit(explicit?) fraction of BTC stakes, as well as the PoW being done?
Yes, by readjusting the PoW difficulty according to how many blocks were created in a retarget window, we can achieve a predictable gap between blocks, where the new difficulty is derived both from the stakeholders' participation level and the PoW participation level. I'm always annoyed that in one breathe people are concerned that miners will mine empty blocks, but similarly we shouldn't worry about PoA stakers to not do it.
Stakeholders shouldn't want to mine empty blocks in a malicious attack to destroy the system, as this would diminish the value of their stake. The bigger concern is closely related to the centralization/monopoly risks, i.e. miners cartel that obtains dominance and could then impose their policies (exclude transactions that don't conform with the fees that they impose, etc.). If PoW mining hardware is completely unusable for anything besides the particular cryptocurrency, then stake and PoW hardware would indeed be very similar in this regard. But ASIC/GPU can be repurposed for other uses, in particular to mine other cryptocurrencies, even as part of auto-switching centralized pool. If we are capping value of blocks, will we have a rule that allows a single transaction block that goes over that limit? Otherwise you wouldn't be able to spend BTC at extremely large valued addresses.
Since the objective is to discourage stakeholders (or miners) from accepting low-fee transactions, I don't see any problem with value cap rule that lets the last transaction overflow. It doesn't have to be a block that includes only a single transaction, for example if the limit is 100 BTC and there are transactions of 70 BTC and 60 BTC (with high proportional fees), then you can include the 70 BTC, then also include the 60 BTC, but then you must finalize the block because 70+60=130 BTC is over the limit. Would the cap value mean miners will just include tons of dust transactions? Or would the value cap be *in addition* to the 1MB data cap?
It's "in addition", see the paragraph that starts with "There is also a third tragedy of the commons problem" in section 2.1 in the paper. The point is that if there's only data size cap and let's say Alice wishes to send a low-value transaction and Bob wishes to send a high-value transaction, then Alice and Bob will compete for space and whoever of the two who offers the higher fee gets included. With the value cap, users who transact with higher values will pay higher fees (same proportional amount but higher in absolute terms), which is more fair. The data size cap is more controversial because it should accommodate the economy and reflect the wishes of the users. This is easier to see when you consider an extreme example, e.g. if Bitcoin allowed only 5 transactions per block now, then obviously everyone will revolt, hence similarly if the transactions volume increases substantially in the future (due to popularity) then the users will revolt if the 1MB cap remains. Or are we hoping the size propagation penalty will naturally force this down? Would this also encourage people to split up their BTC into smaller value, increasing the UTXO set? Just random things to think about.
I failed to understand, what is a size propagation penalty? Why split up into smaller values? |
|
|
|
About the weird post above by coinxed: coins can be destroyed by not redeeming the entire coinbase, and also by sending an unspent output to (non-P2SH) script that always returns false. Some relevant info is discussed in this thread (e.g. post #164), and in footnote 9 in the paper (post #167) etc. What happens if the N PoS "miners" aren't online? That seems quite likely very often.
The reason why you aren't worried that all the PoW miners will go offline is that they're rewarded for their work. Similarly, if stakeholders are rewarded, then we can expect some fraction of them to be online. In section 3.2.1 of the paper we describe how to incentivize a target participation level of the online stake. BTW in case someone prefers to look at the presentation form, here are the slides that I presented in a couple of talks: http://www.cs.technion.ac.il/~idddo/PoAslides.pdf |
|
|
|
PoA academic paper is now public: http://eprint.iacr.org/2014/452It was accepted to NetEcon/SIGMETRICS workshop: http://www.eurecom.fr/~loiseau/W-PIN+NetEcon2014/program.htmlGiven that Charles Lee came up with the original core idea of PoA and helped with our further improvements, he encouraged me to try to implement PoA on a Litecoin testnet (separate from the testnet of the reference Litecoin client), and I'm interested in the Litecoin community reaction towards incorporating PoA into Litecoin. In the paper we have some C++ and Python code for benchmarks, and I now plan the more efficient/complete implementation (with PoA protocol parameter N=1). If you're a programmer who'd like to join this effort then email me. However, forking to obtain controversial goals (as opposed to benign softforks like BIP16) is risky, so it should only be done if needed for actual security improvements (regarding this, see in particular section 2.1 of the PoA paper). When our testnet implementation is ready, we will analyse and re-evaluate whether adding PoA to Litecoin makes sense. Edit: presentation slides at http://www.cs.technion.ac.il/~idddo/PoAslides.pdf |
|
|
|
I think it's solvable in the following way: The node will require that the miner pays him some fee in the generation transaction. When the miner finds a valid nonce, the node will only release the full block if the miner shows him that the nonce matches a generation transaction paying the required fee. This way the node guarantees a fair share of the revenue enabled by his contribution.
Actually, there isn't supposed to be anything secret in the data that the node prepared, right? So in the rare occasion that the miner solves the block, he can broadcast it immediately to the network, and then he (or other members of the pool) can collect the transactions that the node used to create the block, and send all these txns to Bitcoin peers so that the solved block would be valid? In fact, the users who created those txns (and other Bitcoin nodes who just wish to see smooth continuation of the blockchain) have an interest to also pitch in and help with making the solved block valid? The only way to avoid this freeloading issue is if the node that created the block will incorporate a "dummy" txn that has never been broadcasted to the network? That might be messy because of the headers-first sync optimization that Bitcoin clients will probably have by default, i.e. while the broadcasted solved block is considered to be a valid candidate by the network, the miner could say to the node that he agrees to pay only half the fee in exchange for releasing the dummy transaction, or other such forms of abusive behavior? Edit2: Actually I was very much confused, the data is indeed not secret, but I missed the point that the miner only has one branch of the Merkle tree, therefore it should be infeasible to try different permutations with unconfirmed txns, especially if the volume of unconfirmed txns is high (which is one reason why we need multi-PPS in the first place). The extra round-trips of communication between the node and the miner imply that the current form of centralized pools will have an advantage over multi-PPS, especially if the average blocktime is less than 10 minutes as with Litecoin etc., right? Wouldn't this advantage override the benefits of multi-PPS, meaning that miners will prefer not to use multi-PPS because of this? |
|
|
|
Two comments: 1) So far this proposal doesn't explicitly describe how to pay the nodes who construct a block that contains all the transactions minus the coinbase, for their service. If it should be some sort of a subscription service where the PoW miner pays in advance, then this adds to the overhead because the miner has to identify himself when requesting a new block, and there's room for abuse/freeloading i.e. one miner pays and then shares his account (login/password) with other miners, or shares the constructed block (minus the coinbase) with other miners. Another option is that it'd be some kind of an honor system, where miners donate some portion of their profits to the nodes who provide this service, but I'm not sure if that'd be sustainable. 2) In an old thread the issue of performance was discussed, slush's reply ( link) is rather pessimistic. He considers the straightforward setting where the miner submits the entire block to the pool, unlike your followup post about quizzing or using SNARK/SCIP as an improvement. Though unlike the old thread, with multi-PPS there's the added complexity of interacting with separate nodes that construct blocks for the miners, and this should also be taken into account since the miner might request several such blocks during the average 10 minutes interval, as new transactions are being broadcasted over the network. I think that BIP0022 (which probably isn't being used by anyone yet?) was inspired in part by that old thread, so I'm not sure what should be the current assessment regarding the severity of the performance issues. |
|
|
|
|
Show Posts
