Thanks.

1. The senders of the G*xi shares should sign the messages using xi private key.   Recipients can verify these and this should be sufficient to prevent a rogue key attacker from controlling x

2. The sender of the G*ki nonces should sign the messages using an "xi*ki" private key.  Recipients can verify these and this should be sufficient to prevent a rogue key attacker from controlling k

I updated this with the signing requirements:

https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-e7860ab34e7f

Hey, I've been working on a threshold scheme for multisignatures.  

I wrote this up, and am pasting it here in the hopes someone can help me find problems with it before I try to bug people on bitcoin-dev again with it and before I try to write up an iacr paper or some nonsense like that (I do think it's nonsense these days...).

https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-e7860ab34e7f

This basically re-uses proven cryptosystems like Schnorr and Shamir secret sharing, and takes advantage of the homomorphic properties of shared secrets in a fairly trivial way that I can't find a problem with.  It also uses the MuSig construction, to prevent participants from being able to birthday-attack parameters of the system.   I don't actually think it's necessary, and I will probably remove it unless someone thinks its needed.

An M of N Bitcoin Multisig Scheme

Currently, the leading proposal for a multisignature scheme is an M of M scheme. I would propose a modification of this protocol that provides both aa noninteractive M of M scheme and an interactive but verifiable M of N scheme.

I’m going to assume that G is a DLP-hard group of some kind, and that curve operations are done using elliptic-curve terminology. EI: Points can be added, and the generator is multiplied by a private key to get a public key.

Terminology:

G : the agreed upon group (secp256k1)
M : the number of participants required to sign.
N : the total number of participants. (N≥M)
H : a hash function of some kind. (SHA3)
P: the order of group G

The public parameters “G”, “M” and “N” must be agreed upon by all participants. If not, consensus verification will fail.
M of M Scheme

I’m going to begin with a description of the M of M scheme. Extending it to M of N requires an application of “secret redistribution”, which is well reviewed and proven not to leak information about the underlying secrets. I will provide an explanation of how to use it at the end.

To initiate a multisig scheme, each of the first “M” participants generates a secure random number “x”. Then, each participant “i” publishes their public key, G*xi.

Each party interprets the public keys as shares in a Shamir sharing scheme. Put simply, lagrange coefficients are calculated using Xi = H(G*xi). The coefficients are ordered, based on the sort order of X.

for i1 in sorted(Xis):
    coeff[i1]=1
    for i2 in Xis:
        diff = (i2-i1)%P
        inv = modinv(diff, P)
        val = i2 *inv%P
        coeff[i1]=coeff[i1]*val%P     

These coefficients are used to multiply each point by. The results are summed, and that is the “bitcoin public key” — the key that these participants are signing for.

for share in shares:
    point = coincurve.PublicKey(share.data)
    s = point.multiply(coeff[share.index])
    vals.append(s)

point_sum = coincurve.PublicKey.combine_keys(vals)

So, now we have an M of M public key. Nobody can possibly know the private key, and having M-1 devices gives you zero knowledge of the implied private key “x”. In addition there is no meaningful way share participants can influence the resulting implied key.

We can call this G*x, or “the public key”… in the signing scheme below.

Signing:

The participants in the scheme can now generate Schorr-style multisignatures.

When signing, each participant “i” rolls a random nonce “ki”. Each signing participant computes a “blinding parameter L”. These are akin to those used in the MuSig proposal.

L = H(X1, X2, X3…XM, 1)
X = SUM(H(L1,Xi))  ### i think this may be unnecessary.   M-1 attackers simply cannot influence either k or x in a meaningful way.
R  = G*k
e = H(R, M, X)
si = ki - xi * e

The signature share is (si, e).

It’s clear that a single particpant cannot choose a “weak public key”. In the proposed Shamir’s scheme, the value of M-1 shares has zero impact on the entropy contained in the final result. The same logic applies to the “implied k”. The value of e must be the same for all participants.

Verification:

The signatures must also be subjected to the lagrange coefficients algorithm above.

Each si is combined to a single “S” by multiplying the coeffs (calculated above) and the result is summed:

s = sum(coeff[index] * si)

Finally, you perform the same verification as in Schnorr.

rv = G*s + G*x*e
ev = H(r, M, X1)
assert(ev == e)

The math winds up about the same as well. The only variable the attacker controls at signature time is k. M-1 attackers don’t affect the randomness of k.

Derviation showing this still works.

rv = G*(k - x*e) + G(*x*e)
rv = G*(k) == R

One thing to understand is that after interpolation, the resulting “x” and Gx and “signatures” are combined correctly.

Shamir secrets shares are homomorphic in addition, subtraction, multiplication and addition, so this is something we get “for free”.

It is also why ECDSA can’t be used in a Shamir scheme. The modular inverse function will not work and shares could not be combined.
Addition of Share Participants:

Thus far, this scheme can be done without rounds of approvals. Share participants can generate keys offline and without participation from each other.

In order to create additional participants, they must be added to a larger implied polynomial using “secret redistribution”.

A quick summary of how this is done doesn’t do it justice, but there are lots of implementations and descriptions of secret share redistribution to choose from. For example: https://github.com/dfinity/vss

Summary: Each of M participants “shards” his share into N “sub shares” labeled 1..N, using Shamir’s secret sharing algorithm for an M of N scheme and using random coefficients. These subshares are, further, delivered to each of the corresponding share participants. They are then separately interpolated and combined to form new shares “xi” . Each participant must then publish the new G*xi. Each participant can now verify that the new combined and implied key G*x for all M subsets of N is the same as the original key G*x. ( Failure to verify this implies that one of the participants is functioning incorrectly and cannot sign — not that there is some sort of weakness. )

Redistribution can be used to *remove* participants, *add* them, or otherwise change the M of N scheme without compromising the scheme.

It’s notable that when using “secret redistribution” the addition of share participants does not change the verification algorithm, nor does it expose any information about the secret key or the implied secret key.

Caveats:

Also important to note that this entire article (and multisig schemes in general) assume that there are other mechanisms in place for verifying share participants. Any attacker that controls M of N keys using MITM techniques will be able to sign using any multisig scheme.

Public keys should be shared in-person using QR codes or, at least, using verbal or other verification techniques for keys shared online.

Currently, the leading proposal for a multisignature scheme is an M of M scheme. I would propose a modification of this protocol that provides both aa noninteractive M of M scheme and an interactive but verifiable M of N scheme.

I’m going to assume that G is a DLP-hard group of some kind, and that curve operations are done using elliptic-curve terminology. EI: Points can be added, and the generator is multiplied by a private key to get a public key.

Can ck signal bit 1 and bit 4 both?

yeah, it's more like... if it's a nonstandard port, mark it as such, and connect much less frequently....ie: only one nonstandard port connection per day... with a doubling backoffs on failure, and random time to attempt.   this would allow nonstandard ports to exist.   any web server can handle an extra 10k requests evenly spread out through the day, so no risk of ddos.   if this seems to work, and it's useful, and it doesn't turn into a mosh pit on testnet, the levels can be slowly raised to 10 nonstandard peers per day, or whatever.

Yes, it does.   4MB, but 2.1 "effective" increase based on current traffic patterns.   

We need this block size increase today, because fees are going to become a big barrier preventing adoption as bitcoin price is bloated by institutional involvement in the coming year.

Also, since there's no way we can record every person's coffee and pizza purchases in the whole world in a single block chain, Bitcoin is going to need chained unconfirmed transactions ASAP as well.   

Segwit fixes both of these problems fairly quickly.   There's a cool compression algo coming out that can also triple the rate without bloating the chain at a loss of anonymity... but I wouldn't relay on that vaporware.  Segwit is real and is the only tested solution to date.   (( Bitcoin Classic was probably OK too.. (simple 2MB fork), but it never got off the ground. ))

What does that even mean?   That's the crazy thing people keep saying.   Ant pool still mines empty blocks every day.   How are they "full"?   Some time in January 2015, zero and 1 satoshi fee transactions started backing up the mem pool.   


If you want to get to $0.01 fees and $5000 coins, you'd need fast and efficient 100MB blocks that can be easily and quickly transmitted to all nodes in the network.   100MB is crazy and can never work.   Networks just don't scale that way.   So let's please stop fooling ourselves and pretend off-chain scaling *isn't* the end game here.

I ran a survey over at reddit.   What percent of Bitcoin transactions are "off chain".   Predictably, big blockers say ZERO.  Because everything else is credit.   Which is true... but that doesn't mean that poor people need cheap ways of moving gold internationally for pennies.

There's like 4000 nodes running core, and 3000 of them are signaling segwit.   There are about 400 nodes signaling "other things" ... (XT, Classic, BU, etc.).   It's as clear as day on the node side.   Only miners hoping they can delay the fee drop and capacity increase a little longer.

Username: Simul

Thx

In a way, this is like the dotted-quad notation of IPv4, where each "level" of subchains is another dotted quad.   It might be more convenient to use 16 (0-9A-F) as the number of subchains per level.   

I would add that the difficulty of subchains should be vetted in the main chain, so that someone can choose an address that targets a level of difficulty they are comfortable with.   

It seems that subchains can safely be weaker than the main chain, because of the vetting done by the main chain, which acts, effectively, as a series of checkpoints.

Also, some addresses should be reserved for future use.   For example, an alternate hashing scheme could be added to address position 11 in a future where this is seen as desirable.  Again, since this is synched with the main chain, it benefits a great deal from the security the main chain provides, with the possiblity of a long-fork mitigated.   


0 - 10 full block subchains
11 - 15 reserved for future use

You merely need to download the file over and over... which causes the renter to run out of money.   Same as a DOS attack downloading a web page.


Attackers always spend the same money that legitimate hosts spend.   The "attacker" here is running completely legitimate, full copies of the protocol.   The only difference is that they are running multiple docker containers on the same machine... rather than running on multiple machines.   There is simply no way to know that outside of IP.   Just like a DOS attacker runs a fully legitimate client, so too a Sybil attacker runs a legitimate server.


I think that succinctly sums up what I meant in the original post.

Since DDOS and Sybil are inverted forms of similar attacks (multiple clients vs multiple hosts), these decentralized storage networks haven't introduced a "new" problem to the domain of hosting.  Indeed, any existing cloud hosting provider could, today, "claim redundancy" on your data... but physically locate it on the same machine.   The solution to this problem lies in the transport and social layers... not the consensus protocol.

All cloud storage networks, coin or otherwise, are vulnerable to DDOS attacks, where attackers cause renters or hosts to spend enormous sums of money by repeatedly downloading the same files.

• The typical solution to these DDOS attacks remains "IP blocking".   For TCP/IP, this can be effective, and when coupled with some sort of tracing back to the source, results in DDOS attacks that wane and can be responded to fairly rapidly.
• The practice of IP blocking has spawned an open and somewhat contentious network of public and private IP blocklists.   While it is likely that these blocklists will be relevant for storage coins, there will be undoubtedly be a need for blocklists to be maintained that are specific to cloud storage protocols.
• Blocklists, even if fairly maintained, are centralized and many use DNS for distribution (see https://en.wikipedia.org/wiki/DNSBL).  A blockchain protocol for blacklisting may be ideal, with nominations, evidence, voting and expiration all occurring "on chain".   (It should be obvious why blocklists would greatly benefit from decentralization)

All storage coins are additionally vulnerable to a "not really redundant" Sybil attack. 

• Any attacker can quite simply spin up many instances of the protocol on a single host - increasing his exposure and income - while completely defeating the purpose of redundant storage.
• There is currently no way for a renter or user to know where its hosts physically reside, and whether they are on the same machine or not.
• One way of mitigating this is to publish IP addresses of hosts as a part of file contracts or storage advertisements.   Renters should then prefer IP's that are somewhat distributed across the IP space.   This can, of course be defeated by routing diverse IP's to the same data center.   But this can be trivially detected and violators can then be published via the same IP blocklists above... using either DNSBL or blockchain tech.

In summary:

• Any time you are "hosting" data, you need to deal with DDOS attacks.
• However you solve it, I don't care: this solution will, de facto, provide an analogous solution for Sybil attacks on storage network redundancy

So don't worry about Sia/Storj sybil attacks.   They are just inverted DDOS attacks, and those have to be solved anyway.

Will sell 20k at .0003  I know it's a low price, but I need the cash now.  PM me.

You have to burn within the last 50 blocks, you cannot burn more recently than the last 10 blocks.   This effectively implements a "checkpoint".   Change the numbers of blocks as needed so that you're talking about days and hours.

You don't need an audit.   This is Bitcoin, you can publish a signed ledger and tree of debits showing your holdings in BTC, LTC, etc.   

The fact that they are not doing so, despite being repeatedly asked, is very telling.

I pulled all my money out of btc-e, shortly after they refused to respond to the new protocols allowing the signed publishing of reserves and debts.

http://www.reddit.com/r/Bitcoin/comments/1yk4nv/please_ask_your_favorite_exchange_to_prove_that/

+1 Spot on.

Does the pool keep mining fees, or are they distributed along with the block reward?   (I know it's not really important now, maybe .5%, but it will be over the next 6 months).

Do you plan to publish the blocks you mined, and the distribution transactions?

I agree.  If someone's storing all their reserves on one machine, in one wallet, with one password... well, then you've got a problem.  And there's very little they can do to prove they aren't doing that.

But right now, a temporary measure is needed.   

We need to know that these large exchanges aren't running fractional reserves.   Mt. Gox insisted, repeatedly, that 90% of its assets were in cold storage.   But it never published keys and sigs.   And so we find out now that maybe they were making that all up.   People asked for keys and sigs to prove it... but they "demurred" on those requests...because "nobody else" was doing it.

If the Bitcoin Foundation came out with a "BIP" for this... even a simple thing like a standard JSON format and a requirement for SSL, that would be enough for the community to say... hey... there's a standard... why don't you adhere to it.

IMO, the first exchange to go transparent on reserves will see a flood of new business.

Although this does not address liabilities, that is not a chief concern.   By implementing an interim standard for publishing reserve balances, we can quickly placate the investor community on the health of major exchanges:

http://www.reddit.com/r/Bitcoin/comments/1z72wz/btce_et_al_should_publish_their_reserve_balance/


LOCATION:

CONTENT:

Obviously this doesn't address:

• Fiat balances
• Liabilities

These issues can only be properly addressed with audits, since most exchanges don't use BTC protocol internally.  

However, following an audit, the ratio of average volume to liability can be expected to remain fairly stable, providing a public health metric that will give immediate relieve to the current climate of skepticism.  

You can buy stuff at Amazon with btc using https://bitk.in

Or you can go to bitk.in and shop amazon.  Best conversion rates.