Request for comment / opinions

Hey all,

Vitalik Buterin, founder here.

I would like to ask the community for opinions on a few technical issues around the Ethereum protocol:

1. Should numbers on the stack be bounded to 2^256 as they are now or unbounded? If they are unbounded, the cost of operations and the memory fee would of course be variable; I'm thinking k + c * bytes ^ 3 as the structure for the fee for pushing a value onto stack or memory. The advantages in favor of bounded are:

* Contract creators can count on the fact that the cost of a single operation is bounded
* Reduced risk for security holes in contracts
* Much simpler fee structure
* Reduced risk of implementations getting corrupted with very big integers (eg. what if someone's bigint library does not support more than 1 MB in an integer); however, the c * bytes^3 component should make such attacks infeasible in practice.

The arguments in favor of unbounded are:

* No need for kludges such as SDIV, SMOD and my implementation of SHA256, since negative numbers can be supported.
* You can do RSA crypto inside of contracts that way
* RLP supports unbounded numbers anyway
* Goes with the protocol's general ethic of Pigovian fee regulation only without hard limits

2. Encoding for addresses

Right now, I am thinking of considerably simplifying the encoding for addresses from Bitcoin's. Specifically, Bitcoin works as follows:

hash160 = ripemd160(sha256('04'+pubkey_x+pubkey_y))
hash160wcheck = 'x00' + hash160 + sha256(hash160)[:4]
address = base58encode(hash160wcheck)

I'm thinking

hash160 = sha256(pubkey_x+pubkey_y)[12:]
hash160wcheck = hash160 + sha256(hash160)[:5]
address = base32encode(hash160wcheck)

Where base32encode is an implementation of Zooko's version of base32: http://philzimmermann.com/docs/human-oriented-base-32-encoding.txt

Advantages of my way:

* Makes Ethereum more distinguishable from a marketing standpoint with different-looking addresses
* base32 is slightly simpler to implement since it can be done 5 bytes at a time'
* JS libraries only have to include one hash (sha256), not two, of which one is rather obscure (ripemd160)
* No reason to have the '04' in the hash since that's just for serialization in Bitcoin and in Ethereum we're never serializing pubkeys
* Addresses become easier to read out since you do not need to memorize capitals vs lowercase, and Zooko's more restrictive alphabet further reduces the chance for mistakes

Advantages of existing way:

* BTC addresses can be directly converted into ethereum addresses
* Base58 is slightly more compact (34 chars vs 40)
* People can copy code from BTC libraries rather than using ethereum libraries

Note that there are possible compromises here (eg. remove the '04' and the RIPEMD but keep the base58).

If we can get some discussion going on this stuff that would be great.

Comments

  • rustyrusty Member Posts: 2
    edited January 2014
    1.) I am in favor of using bounded variables for the reasons that I do not see ethereum running in to any problems limiting variables to 2^256 while leaving them unbounded would give rise to vulnerabilities with the unlimited variable size. The overall advantages of unbounded do not really convince me that it would be an advantage to switch. Especially considering that many of its advantages could be implemented elsewhere and using bounded variables encourages simplicity and security.

    2.) I believe it would be extremely important to support the existing developers for bitcoin in the ethereum protocol. Many advantages of your way are minor in terms of utility and personally I believe the ability to port over BTC libraries will help drive community support/development a lot more than your way. However my stance on this is definitely arguable, I am just a fan of having the community of bitcoin developers be able to port their code to the ethereum protocol with ease.
  • mikemike Member Posts: 13
    In whitepaper, should "(15) NOT - pops one item and pushes 1 if S[-1] < S[-2] else 0" r actually read "(15) NOT - pops one item and pushes 1 if S[-1] <> S[-2] else 0"?
  • dannyvanmahldannyvanmahl Member Posts: 13
    I'd have to agree with rusty on his input.
  • VitalikButerinVitalikButerin Administrator Posts: 84 admin
    Okay, thanks for the input.

    For (2), we are likely going with the non-Bitcoin approach though; the reason is that we're switching to sha3 as our main hash in place of sha256 and ripe160, so there's no real possibility for backwards compatibility in any case. But we are still using secp256k1 so there is full compatibility on that side.

    For (1), limited size ints do seem to make more sense at this point.
  • dannyvanmahldannyvanmahl Member Posts: 13
    Sorry for the ramble I'm trying to get these thoughts out before I forget:


    I'm just spewing out conceptual thought but I honestly think I might be on to something.

    What are you proposing as the block time?

    How many ether per block and at what rate will it decrease.


    I'm trying to think of away to implement a block time and ether amnt based in a naturalistic or Darwinian economic perception.

    Does it have to be a constant time and amount?

    What would happen if it was dependent on the amount and rate of transactions. What if miners were able to mine blocks quicker holding a lower amount of transactions thus receiving a lower out of ether. Maybe my strategy of mining would be more conservative with less transactions with lower ether amounts and your be more risky aiming for new densely filled blocks with greater reward.

    So what's would be the variables

    Speed and memory. Maximum amount of transactions allowed in a block(this could be based on a time limit of how long a transaction could be unconfirmed. )

    Maybe a Maximum of 10 minutes but a quicker miner picks you up maybe it will take a minute aka a rapid miner.

    Quantity and rate of transactions taking place? Maybe no maximum amount of transaction per black but simply a time limit, you want to hold off longer and shoot for that 10 minute mark an fill up the block to reach an ether max that's fine but of you get greedy as the clock ticks someone might crack it at 9 minutes.

    Miners waiting longer timers would have more advanced computers possibly?

    This would allow for little guys to still mine ether.

    Could mining also be on a linear curve. Or multiple curves.

    Eventually miners will be able to look at the current amount and rate of ether transacting and based on twit computers abilities discover their equilibrium point which of course will be constantly evolving

    How can mining become alive.
  • dannyvanmahldannyvanmahl Member Posts: 13
    understand with this system the free market will determine the optimal transaction amounts , confirmation time, and award (based on amount of transaction) it will reflect truth if indeed there was a tool for miners to adjust their strategy a based on their machines
  • VitalikButerinVitalikButerin Administrator Posts: 84 admin
    > What are you proposing as the block time?

    60s

    > How many ether per block and at what rate will it decrease.

    Linear forever. Ether per block depends on how much we raise in the fundraiser.
  • dannyvanmahldannyvanmahl Member Posts: 13
    K let me know when the fundraiser is, I
  • petervpeterv Member Posts: 4
    I had always assumed that the RIPEMD layer was to make quantum computation attacks harder by mixing crypto protocols, similarly the double sha256 in the mining protocol.

    I can't find much on sha3 and quantum computing; it looks like the mechanism hasn't been well researched yet.

    Inre: addresses, I would urge an address format that makes for easy regexes -- perhaps just some id characters around the address? I agree it's nice to have something that visually scans as 'ether'.
  • VitalikButerinVitalikButerin Administrator Posts: 84 admin
    > I had always assumed that the RIPEMD layer was to make quantum computation attacks harder by mixing crypto protocols

    All hash algorithms are invulnerable to polytime quantum algorithms (eg. Shor's, which breaks factoring and elliptic curve cryptography) but are vulnerable to Grover's algorithm. So composing hashes doesn't really have a benefit.

    > K let me know when the fundraiser is

    Jan 25
  • arckearcke Member Posts: 34
    All hash algorithms are invulnerable to polytime quantum algorithms (eg. Shor's, which breaks factoring and elliptic curve cryptography) but are vulnerable to Grover's algorithm. So composing hashes doesn't really have a benefit.
    Not sure if I understand this. Do you mean all current and future hash functions can be reverse lookup'ed in sqrt(hashed_bits)*c time on a quantum computer for some constant c?
  • VitalikButerinVitalikButerin Administrator Posts: 84 admin
    All n-bit hash functions can be cracked in 2^(n/2) time. There is no way around this because Grover's takes the circuit of an arbitrary function as its input. But that's not a problem since if quantum computers come in difficulty will just square and we'll be back where we started.
  • arckearcke Member Posts: 34
    edited January 2014
    I see. Interesting to consider, and for most cryptosystems slightly increasing the bitsize does not have to be a problem. I never applied quantum algorithms whilst thinking about cryptographic protocols during my education. For now I understand factoring and discrete log are feasible considering Shor's algorithm which has driven cryptographers towards Merkle trees and lattice-based systems. (https://en.wikipedia.org/wiki/Post-quantum_cryptography)

    Back to ethereum. Nice to see the predictions on Dagger, because current "CPU-coins" have shown weaknesses towards GPU or other specialized hardware. I try to abandon the use of proprietary software and do not use proprietary drivers for my GPU and use cloud servers to mine coins. I know you probably can not say this for sure and only predict to the best of your knowledge so forgive me for asking, but will Dagger remain CPU-only or will it still be possible that GPUs with proprietary drivers will outperform CPU/free drivers by a small but none the less irritating level towards the free software community?
    Post edited by arcke on
  • VitalikButerinVitalikButerin Administrator Posts: 84 admin
    > but will Dagger remain CPU-only or will it still be possible that GPUs with proprietary drivers will outperform CPU/free drivers by a small but none the less irritating level towards the free software community?

    Looking at Dagger now, I have to admit that GPUs may be slightly better; the reason is that my holy grail of 500 MB is nonviable since we do need one round of mining to take a few seconds and not an hour. But it will still be considerably better than Scrypt.
  • mikemike Member Posts: 13
    I just saw at Silicon Valley Bitcoin Meetup that ASIC are coming out for Scrypt mining, with onboard memory, 500 Mb per cell from the sounds of it. They did misspell "Scrypt" as "Script". It would be really good if the cloud and botnet mining can be crippled. This caused a lot of problems with the Protoshares launch.
  • arckearcke Member Posts: 34
    FYI: Cuckoo POW - https://bitcointalk.org/index.php?topic=405483.0

    Just mentioning this. No idea if it is any better or worse than dagger.
  • amlutoamluto Member Posts: 5
    But that's not a problem since if quantum computers come in difficulty will just square and we'll be back where we started.
    Just to clarify: if quantum computers show up, ECDSA will be completely broken, so hash issues will be the least of the problems.
  • aetheraether Member Posts: 1
    Back to the original question #1: I'm going to put in a vote for unbounded numbers. Being able to do RSA easily within the blockchain means that you can do really cool things like implement provable data possession within a contract. This means that a node can prove that it possesses some large amount of data (that is stored outside of the block chain), and a contract can validate that proof cryptographically.
  • arckearcke Member Posts: 34
    I vote for bounded numbers. Security is a big consideration when it comes to a "backbone protocol" and ethereum will be the core of a network. I imagine future services to extend the capabilities of the network and launch an unbounded calculation service just like they would lauch an rsa service.
  • HadrienHadrien MaltaMember Posts: 17 ✭✭
    I vote for:
    1) the stack be bounded to 2^256 to be unbounded
    2) your way in simplifying the encoding for addresses from Bitcoin
  • chris613chris613 Member Posts: 93 ✭✭
    @vitalik‌

    My input follows the trend here:

    (1) Bounded numbers are fine. As for SDIV and friends, it does sort of suck to proliferate two versions of all the opcodes that need it, but x86 did it and managed to survive. I think ethereum asks enough big questions without also asking "what could go wrong with unbounded registers?". Is it actually impossible to do RSA crypto without unbounded stack elements?

    (2)
    >* BTC addresses can be directly converted into ethereum addresses

    I'm not sure I understand what the advantage is here.

    >* Base58 is slightly more compact (34 chars vs 40)

    z-base-32 has other advantages that IMO are worth the 6 bytes. (Either would be an improvement from the current (as of POC-4 at least I think) ethereum addresses, which have no ergonomic encoding at all.

    >* People can copy code from BTC libraries rather than using ethereum libraries

    This is pretty much trivial, right? If your application interops with ethereum, then using the appropriate library, reference code, or spec is not a huge barrier. You wrote the code for everyone to discuss above, it's really just three lines.

    @peterv‌ Mentioned the presence of ripemd was a defence against quantum attacks, to which you correctly responded that it made no real difference for hashes. My understanding of the relationship between these issues is that if you assume a quantum computing attacker, then hash composition leaves you in a better spot, allowing a buffer for when one of the hash algos falls to some future attack. I am under the impression that this is why bitcoin does things this way, but I could be wrong.
  • VitalikButerinVitalikButerin Administrator Posts: 84 admin
    (1) We're going bounded, that's been settled now :)
    (2) You can publish one pubkey, and that pubkey can simultaneously produce a Bitcoin address, a Litecoin address, a Dogecoin address, etc. If we keep secp256k1 the pubkey will also give you an Ethereum address.
    (3) The final intent is to use namereg as the primary usability gain. But I probably will create an advanced encoding using SSSS for addresses, with support for encoding a messaging format into an address for sub-currencies. z-base-32 sounds like the way to go.
Sign In or Register to comment.